History log of /freebsd-head/sys/sys/queue.h
Revision Date Author Comments
eb397f42a5931fe886f5801660d73b30c03ad607 26-Feb-2020 gahr <gahr@FreeBSD.org> Trim trailing white space in comment

Approved by: cognet
da627eba887bab766caba6f4716a91ca16c39ddd 20-Jun-2019 mav <mav@FreeBSD.org> Add wakeup_any(), cheaper wakeup_one() for taskqueue(9).

wakeup_one() and underlying sleepq_signal() spend additional time trying
to be fair, waking thread with highest priority, sleeping longest time.
But in case of taskqueue there are many absolutely identical threads, and
any fairness between them is quite pointless. It makes even worse, since
round-robin wakeups not only make previous CPU affinity in scheduler quite
useless, but also hide from user chance to see CPU bottlenecks, when
sequential workload with one request at a time looks evenly distributed
between multiple threads.

This change adds new SLEEPQ_UNFAIR flag to sleepq_signal(), making it wakeup
thread that went to sleep last, but no longer in context switch (to avoid
immediate spinning on the thread lock). On top of that new wakeup_any()
function is added, equivalent to wakeup_one(), but setting the flag.
On top of that taskqueue(9) is switchied to wakeup_any() to wakeup its
threads.

As result, on 72-core Xeon v4 machine sequential ZFS write to 12 ZVOLs
with 16KB block size spend 34% less time in wakeup_any() and descendants
then it was spending in wakeup_one(), and total write throughput increased
by ~10% with the same as before CPU usage.

Reviewed by: markj, mmacy
MFC after: 2 weeks
Sponsored by: iXsystems, Inc.
Differential Revision: https://reviews.freebsd.org/D20669
fceb8349bd404327f15ea6185e0bbbf6a7bc5839 31-Oct-2018 glebius <glebius@FreeBSD.org> Define QMD_SAVELINK() only for QUEUE_MACRO_DEBUG_TRASH case. Otherwise
with QUEUE_MACRO_DEBUG_TRACE compilation fails due to unused variable.
e4ec942fc5daced5a2926ce55498af36db5dd419 07-Jun-2018 rrs <rrs@FreeBSD.org> This commit brings in a new refactored TCP stack called Rack.
Rack includes the following features:
- A different SACK processing scheme (the old sack structures are not used).
- RACK (Recent acknowledgment) where counting dup-acks is no longer done
instead time is used to knwo when to retransmit. (see the I-D)
- TLP (Tail Loss Probe) where we will probe for tail-losses to attempt
to try not to take a retransmit time-out. (see the I-D)
- Burst mitigation using TCPHTPS
- PRR (partial rate reduction) see the RFC.

Once built into your kernel, you can select this stack by either
socket option with the name of the stack is "rack" or by setting
the global sysctl so the default is rack.

Note that any connection that does not support SACK will be kicked
back to the "default" base FreeBSD stack (currently known as "default").

To build this into your kernel you will need to enable in your
kernel:
makeoptions WITH_EXTRA_TCP_STACKS=1
options TCPHPTS

Sponsored by: Netflix Inc.
Differential Revision: https://reviews.freebsd.org/D15525
4736ccfd9c3411d50371d7f21f9450a47c19047e 20-Nov-2017 pfg <pfg@FreeBSD.org> sys: further adoption of SPDX licensing ID tags.

Mainly focus on files that use BSD 3-Clause license.

The Software Package Data Exchange (SPDX) group provides a specification
to make it easier for automated tools to detect and summarize well known
opensource licenses. We are gradually adopting the specification, noting
that the tags are considered only advisory and do not, in any way,
superceed or replace the license texts.

Special thanks to Wind River for providing access to "The Duke of
Highlander" tool: an older (2014) run over FreeBSD tree was useful as a
starting point.
7e6cabd06e6caa6a02eeb86308dc0cb3f27e10da 28-Feb-2017 imp <imp@FreeBSD.org> Renumber copyright clause 4

Renumber cluase 4 to 3, per what everybody else did when BSD granted
them permission to remove clause 3. My insistance on keeping the same
numbering for legal reasons is too pedantic, so give up on that point.

Submitted by: Jan Schaumann <jschauma@stevens.edu>
Pull Request: https://github.com/freebsd/freebsd/pull/96
185a9296dcbe3f44ccf3de5c5423f41f9d5085e7 11-Nov-2016 cem <cem@FreeBSD.org> queue.3: Document existing QMD_* macros

Feedback from: bapt, bdrewery, emaste
Sponsored by: Dell EMC Isilon
Differential Revision: https://reviews.freebsd.org/D3983
26315f8bd8a7828fdfa0b8e060d43500a20a0de4 08-Sep-2016 cem <cem@FreeBSD.org> queue(3): Enhance queue debugging macros

Split the QUEUE_MACRO_DEBUG into QUEUE_MACRO_DEBUG_TRACE and
QUEUE_MACRO_DEBUG_TRASH.

Add the debug macrso QMD_IS_TRASHED() and QMD_SLIST_CHECK_PREVPTR().

Document these in queue.3.

Reviewed by: emaste
Sponsored by: Dell EMC Isilon
Differential Revision: https://reviews.freebsd.org/D3984
0aeae89e961290a23a4bb11c8cb5663a86933a88 16-Aug-2016 mckusick <mckusick@FreeBSD.org> Add two new macros, SLIST_CONCAT and LIST_CONCAT. Note in both the
queue.h header file and in the queue.3 manual page that they are O(n)
so should be used only in low-usage paths with short lists (otherwise
an STAILQ or TAILQ should be used).

Reviewed by: kib
00d578928eca75be320b36d37543a7e2a4f9fbdb 27-May-2016 grehan <grehan@FreeBSD.org> Create branch for bhyve graphics import.
7ba3672103058a6825dfa6d5734ca8acb8eadc4e 08-Oct-2015 hselasky <hselasky@FreeBSD.org> MFC r284915:
Make the system queue header file fully usable within C++ programs by
adding macros to define class lists.

This change is backwards compatible for all use within C and C++
programs. Only C++ programs will have added support to use the queue
macros within classes. Previously the queue macros could only be used
within structures.

The queue.3 manual page has been updated to describe the new
functionality and some alphabetic sorting has been done while
at it.

Differential Revision: https://reviews.freebsd.org/D2745
PR: 200827 (exp-run)
0647fdddb3df86e40812519e4913a3f61d94c95c 28-Jun-2015 hselasky <hselasky@FreeBSD.org> Make the system queue header file fully usable within C++ programs by
adding macros to define class lists.

This change is backwards compatible for all use within C and C++
programs. Only C++ programs will have added support to use the queue
macros within classes. Previously the queue macros could only be used
within structures.

The queue.3 manual page has been updated to describe the new
functionality and some alphabetic sorting has been done while
at it.

Differential Revision: https://reviews.freebsd.org/D2745
PR: 200827 (exp-run)
MFC after: 2 weeks
44aa7d6b569e5f997965c09a5baddfb9646fd353 05-Mar-2015 hselasky <hselasky@FreeBSD.org> MFC r279241 and r279242:
Fix debugging macros.
5d5968a67194ec25d7cf35e8257cb2cd952e3d06 24-Feb-2015 hselasky <hselasky@FreeBSD.org> Pass macro arguments properly.

MFC after: 1 week
7903c02c5ac9ffd482bd34b70f326a87b47a4869 24-Feb-2015 hselasky <hselasky@FreeBSD.org> Fix order of arguments in the TRACEBUF_INITIALIZER macro so that we
can define QUEUE_MACRO_DEBUG to debug list problems.

MFC after: 1 week
eb1a5f8de9f7ea602c373a710f531abbf81141c4 21-Feb-2014 gjb <gjb@FreeBSD.org> Move ^/user/gjb/hacking/release-embedded up one directory, and remove
^/user/gjb/hacking since this is likely to be merged to head/ soon.

Sponsored by: The FreeBSD Foundation
6b01bbf146ab195243a8e7d43bb11f8835c76af8 27-Dec-2013 gjb <gjb@FreeBSD.org> Copy head@r259933 -> user/gjb/hacking/release-embedded for initial
inclusion of (at least) arm builds with the release.

Sponsored by: The FreeBSD Foundation
aa062bf6589686389ca402c436434104bf4ecd10 18-Jun-2013 lstewart <lstewart@FreeBSD.org> Add new FOREACH_FROM variants of the queue(3) FOREACH macros which can
optionally start the traversal from a previously found element by passing the
element in as "var". Passing a NULL "var" retains the same semantics as the
regular FOREACH macros.

Kudos to phk for suggesting the "FROM" suffix instead of my original proposal.

Reviewed by: jhb (previous version), rpaulo
MFC after: 1 week
40a2400cbed1f40f70252328eeb5d4001f0a6fbb 06-Feb-2013 glebius <glebius@FreeBSD.org> Fixes to QUEUE_MACRO_DEBUG support:
- Add const quilifiers to fields that store value of __FILE__.
- Use long type for fields that store value of __LINE__.
- Sort and style(9) debugging fields.
- Add initializer for debugging fields into TAILQ_INITIALIZER macro.

PR: 175759
Submitted by: Andrey Simonenko <simon comsys.ntu-kpi.kiev.ua>
Reviewed by: bde
99d1aaa56cf0459d3f1e15b2347cf5abafe86af9 13-Sep-2012 ed <ed@FreeBSD.org> Rename __member2struct() to __containerof().

Compared to __member2struct(), this macro has the following advantages:

- It ensures that the type of the pointer is compatible with the member
field of the structure (or a void pointer).
- It works properly in combination with volatile and const, though
unfortunately it drops these qualifiers from the returned value.

mdf@ proposed to add the container_of() macro, just like Linux has.
Eventually I decided against this, as <sys/param.h> is included all over
the place. It seems container_of() on Linux is specific to the kernel,
not userspace. I'd rather not pollute userspace with this.

I also thought about adding __container_of(), but this would have two
advantages. Xorg seems to already have a __container_of(), which is not
compatible with this version. Also, the underscore in the middle
conflicts with our existing macros (__offsetof, __rangeof, etc).

I'm changing member2struct() to use its old code, as the extra
strictness of this new macro conflicts with existing code (read: cxgb).

MFC after: 1 month
202ff54e3b7adcda33efa5d4056604ce0de59bc6 12-Sep-2012 ed <ed@FreeBSD.org> Correctness: use __member2struct() on the correct fields.

The prev-pointers point to the next-pointers of the previous element --
not the ENTRY structure. The next-pointers are stored in the ENTRY
structures first, so the code would already work correctly. Still, it is
more accurate to use the next-fields.

To prevent misuse of __member2struct() in the future, I've got a patch
that requires the pointer to be passed to this macro to be compatible
with the member of the structure. I'll commit this patch after I've
tested it properly.

MFC after: 1 month.
0fa239bbd777d6f3e2661e7e950511e42bf4e720 12-Sep-2012 ed <ed@FreeBSD.org> Implement LIST_PREV().

Regular LISTs have been implemented in such a way that the prev-pointer
does not point to the previous element, but to the next-pointer stored
in the previous element. This is done to simplify LIST_REMOVE(). This
macro can be implemented without knowing the address of the list head.

Unfortunately this makes it harder to implement LIST_PREV(), which is
why this macro was never here. Still, it is possible to implement this
macro. If the prev-pointer points to the list head, we return NULL.
Otherwise we simply subtract the offset of the prev-pointer within the
structure.

It's not as efficient as traversing forward of course, but in practice
it shouldn't be that bad. In almost all use cases, people will want to
compare the value returned by LIST_PREV() against NULL, so an optimizing
compiler will not emit code that does more branching than TAILQs.

While there, make the code a bit more readable by introducing
__member2struct(). This makes STAILQ_LAST() far more readable.

MFC after: 1 month
9ff3491e673bf8c43598fcc1af408f5e7c80e854 13-May-2011 attilio <attilio@FreeBSD.org> MFC
5e42f0aa77ffb598869c2e7abc8dc01ea61052b6 13-May-2011 mdf <mdf@FreeBSD.org> Note that the _SWAP operation is supported for all list/queue types.
Also place STAILQ_REMOVE_HEAD in alphabetical order. Lastly, document
the _SWAP macros.

PR: kern/143033
MFC after: 1 week
ff0f2f76b263109af717dd850f6f5d51c4ad5e49 03-Dec-2010 kib <kib@FreeBSD.org> Add SLIST_SWAP() macro.

MFC after: 1 week
09f9c897d33c41618ada06fbbcf1a9b3812dee53 19-Oct-2010 jamie <jamie@FreeBSD.org> A new jail(8) with a configuration file, to replace the work currently done
by /etc/rc.d/jail.
f1216d1f0ade038907195fc114b7e630623b402c 19-Mar-2010 delphij <delphij@FreeBSD.org> Create a custom branch where I will be able to do the merge.
04e0b967eab26a8d23959497b64c0b95643a8a59 27-Feb-2010 emaste <emaste@FreeBSD.org> MFC r204106:

Avoid corrupting the list or queue if _REMOVE is invoked with a
reference to the head.

PR: kern/119307
1739980e918430b64d94ecba54b8b4b4a817da3d 20-Feb-2010 emaste <emaste@FreeBSD.org> Avoid corrupting the list or queue if _REMOVE is invoked with a
reference to the head.

PR: kern/119307
MFC After: 1 week
3779b68747cdae9d6e156307aae1ecb97b52d4ea 27-May-2009 ed <ed@FreeBSD.org> Rename the queue macros I introduced last year.

Last year I added SLIST_REMOVE_NEXT and STAILQ_REMOVE_NEXT, to remove
entries behind an element in the list, using O(1) time. I recently
discovered NetBSD also has a similar macro, called SLIST_REMOVE_AFTER.
In my opinion this approach is a lot better:

- It doesn't have the unused first argument of the list pointer. I added
this, mainly because OpenBSD also had it.

- The _AFTER suffix makes a lot more sense, because it is related to
SLIST_INSERT_AFTER. _NEXT is only used to iterate through the list.

The reason why I want to rename this now, is to make sure we don't
release a major version with the badly named macros.
b5e46da5a4947a10803c1a0b6b56b6d42e74f536 27-May-2009 zml <zml@FreeBSD.org> fail(9) support:

Add support for kernel fault injection using KFAIL_POINT_* macros and
fail_point_* infrastructure. Add example fail point in vfs_bio.c to
simulate VM buf pressure.

Approved by: dfr (mentor)
c449acd9713997c2bfebe8866784b115becf82b5 26-Apr-2009 ed <ed@FreeBSD.org> Remove the unused insque() and remque() functions.

We have no code in the tree that uses these anymore. New code should
just use the regular queue(3) macros.
d0569666c1317b58321c14eb169eed985dae0866 24-Nov-2008 imp <imp@FreeBSD.org> This isn't needed...
1fb41331504c4c74d2816bf07759defa4fdc91e2 23-Nov-2008 sam <sam@FreeBSD.org> prepare makefs for import to base
19b6af98ec71398e77874582eb84ec5310c7156f 22-Nov-2008 dfr <dfr@FreeBSD.org> Clone Kip's Xen on stable/6 tree so that I can work on improving FreeBSD/amd64
performance in Xen's HVM mode.
cf5320822f93810742e3d4a1ac8202db8482e633 19-Oct-2008 lulf <lulf@FreeBSD.org> - Import the HEAD csup code which is the basis for the cvsmode work.
d5f58395c36e992d3a854bd647f411bb67b6471b 22-May-2008 ed <ed@FreeBSD.org> Introduce REMOVE_NEXT() macro's for SLIST and STAILQ.

Even though single linked lists allow items to be removed at constant time
(when the previous element is known), the queue macro's don't allow this.
Implement new REMOVE_NEXT() macro's. Because the REMOVE() macro's also
contain the same code, make it call REMOVE_NEXT().

The OpenBSD version of SLIST_REMOVE_NEXT() needs a reference to the list
head, even though it is unused. We'd better mimic this. The STAILQ version
also needs a reference to the list. This means the prototypes of both
macro's are the same.

Approved by: philip (mentor)
PR: kern/121117
50c8ee114ad38f16d64c82159ae8ec78a261766a 24-Oct-2006 ru <ru@FreeBSD.org> Remove the non-standard and undocumented STAILQ_REMOVE_HEAD_UNTIL()
macro now that we no longer use it.
53db512ce5b60400dabc8e025e61721ea6d20479 26-May-2006 emaste <emaste@FreeBSD.org> Add sanity checking for QUEUE(3) TAILQs under INVARIANTS (similar to
the LIST checks). Races may lead to list corruption, which can be
difficult to unravel in a post-mortem analysis. These checks verify
that the prev and next pointers are consistent when inserting or
removing elements, thus catching any corruption earlier.
92d97b5fc035d6d48d32cd4dd74b19a8be5b23ef 26-May-2006 emaste <emaste@FreeBSD.org> QUEUE_MACRO_DEBUG is intended for userland code, so don't include checks
that call panic under it.
a57a1bf0d8dfbe8f92bb6526ca0e42478210edf0 03-Mar-2006 mux <mux@FreeBSD.org> Cast the pointer to void * before casting it back to struct type * in
STAILQ_LAST. This quiets a warning from GCC about increased required
alignment for the cast.

Idea from: cognet
10886fe6c5be6f90e5ca1b7e92c1fcd3f425d787 23-Nov-2005 emaste <emaste@FreeBSD.org> Userland applications may include queue.h and define INVARIANTS
but not provide a panic(9) implementation. Thus, enable the sanity
checks under INVARIANTS only if _KERNEL is also defined.

Submitted by: jmallett
Approved by: rwatson (mentor)
50b1ba762b66c4f2056c0aa72e275ba857413419 18-Nov-2005 emaste <emaste@FreeBSD.org> Add sanity checking for QUEUE(3) lists under INVARIANTS. Races may lead
to list corruption, which can be difficult to unravel in a post-mortem
analysis. These checks verify that prev and next pointers are consistent
when inserting or removing elements, thus catching any corruption earlier.

Also use TRASHIT to break LIST and SLIST link pointers on element removal,
from mlaier via -hackers.

Reviewed by: mlaier
Approved by: rwatson (mentor)
f20506c826c5778591a2a08bacd02cf2b80fbf91 16-Aug-2005 phk <phk@FreeBSD.org> MFC: fix typo in debugging statement.

Approved by: re@
2ac2686959ccdac6ef61d98503e36ec27961be97 08-Aug-2005 phk <phk@FreeBSD.org> Fix typo so QUEUE_MACRO_DEBUG works again.

PR: 84654
Submitted by: Antoine.Pelisse@xloling.org (apelisse@gmail.com)
c85a3e95f78bb183ec62ae6ef948265e7ade6b7a 02-Mar-2005 joerg <joerg@FreeBSD.org> netchild's mega-patch to isolate compiler dependencies into a central
place.

This moves the dependency on GCC's and other compiler's features into
the central sys/cdefs.h file, while the individual source files can
then refer to #ifdef __COMPILER_FEATURE_FOO where they by now used to
refer to #if __GNUC__ > 3.1415 && __BARC__ <= 42.

By now, GCC and ICC (the Intel compiler) have been actively tested on
IA32 platforms by netchild. Extension to other compilers is supposed
to be possible, of course.

Submitted by: netchild
Reviewed by: various developers on arch@, some time ago
f0bf889d0d2ea7d83fd3b67266a98c89cdf14853 07-Jan-2005 imp <imp@FreeBSD.org> /* -> /*- for license, minor formatting changes
9e1925f5605eb84767aaedbc35ab643a8f9f90a5 07-Apr-2004 imp <imp@FreeBSD.org> Remove advertising clause from University of California Regent's license,
per letter dated July 22, 1999.

Approved by: core
dfcfecd6e4814a1fdc3096be66f268458048399f 12-Mar-2004 trhodes <trhodes@FreeBSD.org> These are changes to allow to use the Intel C/C++ compiler (lang/icc)
to build the kernel. It doesn't affect the operation if gcc.

Most of the changes are just adding __INTEL_COMPILER to #ifdef's, as
icc v8 may define __GNUC__ some parts may look strange but are
necessary.

Additional changes:
- in_cksum.[ch]:
* use a generic C version instead of the assembly version in the !gcc
case (ASM code breaks with the optimizations icc does)
-> no bad checksums with an icc compiled kernel
Help from: andre, grehan, das
Stolen from: alpha version via ppc version
The entire checksum code should IMHO be replaced with the DragonFly
version (because it isn't guaranteed future revisions of gcc will
include similar optimizations) as in:
---snip---
Revision Changes Path
1.12 +1 -0 src/sys/conf/files.i386
1.4 +142 -558 src/sys/i386/i386/in_cksum.c
1.5 +33 -69 src/sys/i386/include/in_cksum.h
1.5 +2 -0 src/sys/netinet/igmp.c
1.6 +0 -1 src/sys/netinet/in.h
1.6 +2 -0 src/sys/netinet/ip_icmp.c

1.4 +3 -4 src/contrib/ipfilter/ip_compat.h
1.3 +1 -2 src/sbin/natd/icmp.c
1.4 +0 -1 src/sbin/natd/natd.c
1.48 +1 -0 src/sys/conf/files
1.2 +0 -1 src/sys/conf/files.amd64
1.13 +0 -1 src/sys/conf/files.i386
1.5 +0 -1 src/sys/conf/files.pc98
1.7 +1 -1 src/sys/contrib/ipfilter/netinet/fil.c
1.10 +2 -3 src/sys/contrib/ipfilter/netinet/ip_compat.h
1.10 +1 -1 src/sys/contrib/ipfilter/netinet/ip_fil.c
1.7 +1 -1 src/sys/dev/netif/txp/if_txp.c
1.7 +1 -1 src/sys/net/ip_mroute/ip_mroute.c
1.7 +1 -2 src/sys/net/ipfw/ip_fw2.c
1.6 +1 -2 src/sys/netinet/igmp.c
1.4 +158 -116 src/sys/netinet/in_cksum.c
1.6 +1 -1 src/sys/netinet/ip_gre.c
1.7 +1 -2 src/sys/netinet/ip_icmp.c
1.10 +1 -1 src/sys/netinet/ip_input.c
1.10 +1 -2 src/sys/netinet/ip_output.c
1.13 +1 -2 src/sys/netinet/tcp_input.c
1.9 +1 -2 src/sys/netinet/tcp_output.c
1.10 +1 -1 src/sys/netinet/tcp_subr.c
1.10 +1 -1 src/sys/netinet/tcp_syncache.c
1.9 +1 -2 src/sys/netinet/udp_usrreq.c

1.5 +1 -2 src/sys/netinet6/ipsec.c
1.5 +1 -2 src/sys/netproto/ipsec/ipsec.c
1.5 +1 -1 src/sys/netproto/ipsec/ipsec_input.c
1.4 +1 -2 src/sys/netproto/ipsec/ipsec_output.c

and finally remove
sys/i386/i386 in_cksum.c
sys/i386/include in_cksum.h
---snip---
- endian.h:
* DTRT in C++ mode
- quad.h:
* we don't use gcc v1 anymore, remove support for it
Suggested by: bde (long ago)
- assym.h:
* avoid zero-length arrays (remove dependency on a gcc specific
feature)
This change changes the contents of the object file, but as it's
only used to generate some values for a header, and the generator
knows how to handle this, there's no impact in the gcc case.
Explained by: bde
Submitted by: Marius Strobl <marius@alchemy.franken.de>
- aicasm.c:
* minor change to teach it about the way icc spells "-nostdinc"
Not approved by: gibbs (no reply to my mail)
- bump __FreeBSD_version (lang/icc needs to know about the changes)

Incarnations of this patch survive gcc compiles since a loooong time,
I use it on my desktop. An icc compiled kernel works since Nov. 2003
(exceptions: snd_* if used as modules), it survives a build of the
entire ports collection with icc.

Parts of this commit contains suggestions or submissions from
Marius Strobl <marius@alchemy.franken.de>.

Reviewed by: -arch
Submitted by: netchild
d822b4a77254150edb5672c9163920221303b91d 14-Aug-2003 kan <kan@FreeBSD.org> Add safe _FOREACH iterators to the rest of the queue.h types.
3fe501b46e30bf978f14392fe7cdebf3da7b324b 13-Aug-2003 bmilekic <bmilekic@FreeBSD.org> Add LIST_FOREACH_SAFE, which is like LIST_FOREACH but allows you
to walk the list and remove the current item and destroy/free it.

Alexander Kabaev will likely do the equivalent for the other list
types, but I just happened to have this one sitting in a local
non-FreeBSD tree already.
e7bcbc4dbfb3670fa4b840cd0b67ad74f0ab1239 05-Aug-2002 alfred <alfred@FreeBSD.org> Add a macro for SLIST traversal 'SLIST_FOREACH_PREVPTR',
this macro keeps a pointer to the previous element's next
pointer to allow for search and O(1) removal.
ebfda4c0dd6bcd6c81042231fbc8f0a68f0cc7cf 08-Jul-2002 mike <mike@FreeBSD.org> Move __offsetof() macro from <machine/ansi.h> to <sys/cdefs.h>. It's
hardly MD, since all our platforms share the same macro. It's not
really compiler dependent either, but this helps in reducing
<machine/ansi.h> to only type definitions.
86ce3862f7dc4893fb2bc2f87a6a96c042172036 02-Jul-2002 julian <julian@FreeBSD.org> check in the version if this that compiles, not the one that doesn't
db96a0403089a5473d7fdbe94390250ad9a6dc3e 02-Jul-2002 julian <julian@FreeBSD.org> Make some more debugging code go away when debugging is not turned on.
1cf028d546d703743175c129990d41e737245be7 29-Jun-2002 julian <julian@FreeBSD.org> Oops, that was a heck of a lot more debugging left onthan I intended..
turn it off!

I don't know if people think that these debugging macros are worth keeping
or not but I'll keep them for a short while, while the danger of
queue stuffups in the (rather complicated) run queue code exists.
aa2dc0a5d9e7a19420c153cd414fefa8498eab71 29-Jun-2002 julian <julian@FreeBSD.org> Part 1 of KSE-III

The ability to schedule multiple threads per process
(one one cpu) by making ALL system calls optionally asynchronous.
to come: ia64 and power-pc patches, patches for gdb, test program (in tools)

Reviewed by: Almost everyone who counts
(at various times, peter, jhb, matt, alfred, mini, bernd,
and a cast of thousands)

NOTE: this is still Beta code, and contains lots of debugging stuff.
expect slight instability in signals..
18d687d9dea2a4816a3851861c5d807504a9fba9 17-Apr-2002 tmm <tmm@FreeBSD.org> Parenthesize some macro arguments.

PR: 20024
Submitted by: Tony Finch <dot@dotat.at>
c62faa9e3496b76a85ea9fa61b97daabc90fcbf9 17-Apr-2002 tmm <tmm@FreeBSD.org> Add macros for concatenating tailqs and stailqs.

PR: 20024
Submitted by: Tony Finch <dot@dotat.at> (TAILQ_CONCAT)
3b2d03b60a11ce28e58a87212bcccedd306f2c81 19-Mar-2002 alfred <alfred@FreeBSD.org> Remove __P
b7ccf7682354416b1052b26aeb5c0daefd8ad3b3 11-Dec-2001 sheldonh <sheldonh@FreeBSD.org> Correct a comment that should have been updated in rev 1.43, when
CIRCLEQ was removed.

PR: kern/32688
Submitted by: Jordan DeLong <fracture@allusion.net>
e107fbbb1a6371a4d7841cd71acef3612f186f41 28-Sep-2001 luigi <luigi@FreeBSD.org> namei.h: move "struct componentname" definition outside "struct nameidata",
and provide a valid STDC/C++ definition for function NDINIT

queue.h libkern.h: put explicit casts from void * in insque, remque and memset

(for the records, these changes are necessary to let the files
compile with g++, which is used to build a FreeBSD module
for "Click" -- see www.pdos.lcs.mit.edu/click/ .
Given that they have zero impact on our code, it is worthwhile
to have them in.

MFC after: 3 days
db19e4509b93d340ff88b738dcd46c32b88fdf83 29-Dec-2000 phk <phk@FreeBSD.org> CIRCLEQs are a disgrace to everything Knuth taught us in Volume 1 Chapter 2.

Retire them before anybody starts to use them again.

Use TAILQ instead, it provides the same functionality.
54ca48450cf20c453a092aa95d086cd5c5751fcf 27-Oct-2000 phk <phk@FreeBSD.org> Convert all users of fldoff() to offsetof(). fldoff() is bad
because it only takes a struct tag which makes it impossible to
use unions, typedefs etc.

Define __offsetof() in <machine/ansi.h>

Define offsetof() in terms of __offsetof() in <stddef.h> and <sys/types.h>

Remove myriad of local offsetof() definitions.

Remove includes of <stddef.h> in kernel code.

NB: Kernelcode should *never* include from /usr/include !

Make <sys/queue.h> include <machine/ansi.h> to avoid polluting the API.

Deprecate <struct.h> with a warning. The warning turns into an error on
01-12-2000 and the file gets removed entirely on 01-01-2001.

Paritials reviews by: various.
Significant brucifications by: bde
7db5793b7f5fa7716616953eab087fd10f0a2fe4 22-Oct-2000 phk <phk@FreeBSD.org> Don't bogusly include <struct.h>

Bogusly define our own versions of strbase() and fldoff() until we
have sorted out where they live in the kernel.
fac663d11354c0cfe9f62843a23e5ccb37ea15bb 03-Aug-2000 hsu <hsu@FreeBSD.org> Make check for empty list in STAILQ_LAST() more readable.
5fdba512ea50675f172def79a1732e58d3baf048 03-Aug-2000 hsu <hsu@FreeBSD.org> Restore STAILQ_LAST() semantics to match that of TAILQ_LAST()
and CIRCLEQ_LAST(). Return the last element instead of a pointer
to the next field of the last element.

Reviewed by: dfr
961b97d43458f3c57241940cabebb3bedf7e4c00 26-May-2000 jake <jake@FreeBSD.org> Back out the previous change to the queue(3) interface.
It was not discussed and should probably not happen.

Requested by: msmith and others
d93fbc99166053b75c2eeb69b5cb603cfaf79ec0 23-May-2000 jake <jake@FreeBSD.org> Change the way that the queue(3) structures are declared; don't assume that
the type argument to *_HEAD and *_ENTRY is a struct.

Suggested by: phk
Reviewed by: phk
Approved by: mdodd
8846e3be2e5414c8d79ef5e0ea4d518d21312abc 21-May-2000 jake <jake@FreeBSD.org> Major style cleanup; make ordering and internal use of the macros consistent.
Hopefully enforce KNF conformance. Add a missing _HEAD_INITIALIZER.

Reviewed by: archie, phk, bde
(bde did not like all of it)
Approved by: mdodd
0a725efcf4b081aadadcacda0fb6bb49f018146f 01-May-2000 archie <archie@FreeBSD.org> Add TAILQ_FOREACH_REVERSE() macro.

Submitted by: Jake Burkholder <jburkhol@home.com>
3e88ebfc3bb1caf670976b0728a058d37f5b2d3a 27-Apr-2000 archie <archie@FreeBSD.org> Add a new macro CIRCLEQ_FOREACH_REVERSE for traversing through a
circle queue in the reverse direction (from tail to head).
b42951578188c5aab5c9f8cbcde4a743f8092cdc 02-Apr-2000 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'ALSA'.
efc73ae8d083dbe66442d5d8f77a96e1b594dd56 24-Mar-2000 asmodai <asmodai@FreeBSD.org> Fix spelling, slingly -> singly.

Submitted by: nrahlstr
15b9bcb121e1f3735a2c98a11afdb52a03301d7e 29-Dec-1999 peter <peter@FreeBSD.org> Change #ifdef KERNEL to #ifdef _KERNEL in the public headers. "KERNEL"
is an application space macro and the applications are supposed to be free
to use it as they please (but cannot). This is consistant with the other
BSD's who made this change quite some time ago. More commits to come.
ad79c6009cc16320a9a1ee513845cb84a567ec52 30-Oct-1999 imp <imp@FreeBSD.org> Macro needed for NEWCARD kernel and STAILQ emulation.

Pointed out by Richard Wackerbar
bb81fe937104c2742b86fbe1f35b69fbb9e3f905 05-Oct-1999 n_hibma <n_hibma@FreeBSD.org> Add SLIST_HEAD_INITIALIZER for static initialisation of SLISTs.
f1d29df71c7afe5137bb040f3409f92caa5059fb 30-Aug-1999 jdp <jdp@FreeBSD.org> Add STAILQ_FOREACH.
3b842d34e82312a8004a7ecd65ccdb837ef72ac1 28-Aug-1999 peter <peter@FreeBSD.org> $Id$ -> $FreeBSD$
fc4fed17f006f4bbde2a9d1ca68fbd3d3df754d2 06-Jul-1999 n_hibma <n_hibma@FreeBSD.org> Backout the previous change. Claimed to break compatibility with
NetBSD.

Requested-By: John Polstra
ea3879346228a463d59821089bc65954cc4a9a31 03-Jul-1999 n_hibma <n_hibma@FreeBSD.org> Remove bogus argument to LIST_HEAD_INITIALIZER
4fc9be52674835f5e227469c3f47fb7178a78cff 20-Apr-1999 n_hibma <n_hibma@FreeBSD.org> Remove feature creep: STAILQ_REMOVE_HEAD_UNTIL added it for convenience
but we can do without it.
531ff5b8561108f923439587aedf8722dc5b53aa 07-Jan-1999 n_hibma <n_hibma@FreeBSD.org> Name change suggested by Justin (QUEUE->UNTIL)
6b0a11c013bb11bbed19aea0a563ebb393a899ef 06-Jan-1999 n_hibma <n_hibma@FreeBSD.org> Copied STAILQ_HEAD_INITIALIZER and LIST_HEAD_INITIALIZER from NetBSD, and
added STAILQ_REMOVE_HEAD_QUEUE to emulate NetBSD's SIMPLEQ_REMOVE_HEAD (that
removes not only the first element but a queue of elements).
a6105f339f56f388d28b084c6f6d032762d7d29e 24-Jun-1998 phk <phk@FreeBSD.org> When some functions were added to sys/queue.h (1.15, 1.16),
the queue diagram (in comment, showing member functions)
update were slipped.

PR: 7048
Submitted by: SAWADA Mizuki <miz@qb3.so-net.ne.jp>
e808ec6c240ba5d862451966eae5f7568191167b 12-May-1998 gibbs <gibbs@FreeBSD.org> Fix the termination test in CIRCLEQ_FOREACH.

Prompted by: Julian Assange <proff@iq.org>
4f3c123867a02aee7258ec91783c0e538162ee80 24-Feb-1998 julian <julian@FreeBSD.org> Add the 'do/while hack' to all the queue macros
to allow them to be more generally used.

Submitted by: Kirk McKusick (from some of his trees)
(possibly some cleanups to follow)
0506343883d62f6649f7bbaf1a436133cef6261d 11-Jan-1998 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'jb'.
7c6e96080c4fb49bf912942804477d202a53396c 10-Jan-1998 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'JB'.
7b9f919ed235457123a015b58539151943ddce6b 02-Nov-1997 gibbs <gibbs@FreeBSD.org> Correct the definition of CIRCLEQ_EMPTY. It would give a false positive
if the queue contained only one element.

Submitted by: Greg Ansley <gja@ansley.com>
d9cbf6234075f423cb8f26077912985a28de1af8 21-Sep-1997 gibbs <gibbs@FreeBSD.org> buf.h:
Change the definition of a buffer queue so that bufqdisksort can
properly deal with bordered writes.

Add inline functions for accessing buffer queues. This should be
considered an opaque data structure by clients.

callout.h:
New callout implementation.

device.h:
Add support for CAM interrupts.

disk.h:
disklabel.h:
tqdisksort->bufqdisksort

kernel.h:
Add new configuration entries for configuration hooks and calling
cpu_rootconf and cpu_dumpconf.

param.h:
Add a priority for sleeping waiting on config hooks.

proc.h:
Update for new callout implementation.

queue.h:
Add TAILQ_HEAD_INITIALIZER from NetBSD.

systm.h:
Add prototypes for cpu_root/dumpconf, splcam, splsoftcam, etc..
bd600a2a025f267f2b5ffa36fa177965fda7584f 25-Aug-1997 phk <phk@FreeBSD.org> Add SLIST_FOREACH
3ff0dc0cb9c912ce6e939036661e3c3137b1e7a4 07-May-1997 dfr <dfr@FreeBSD.org> Add accessors for STAILQ.

Reviewed by: phk
49413144285b96e53655b462df08b8d18fa92e82 27-Apr-1997 phk <phk@FreeBSD.org> Add some more "member functions" to these. Still not complete.
fe8656a98fc996e1091e2cde2fa1b51aa822093f 14-Apr-1997 phk <phk@FreeBSD.org> Add LIST_FIRST, LIST_FOREACH and LIST_NEXT
94b6d727947e1242356988da003ea702d41a97de 22-Feb-1997 peter <peter@FreeBSD.org> Back out part 1 of the MCFH that changed $Id$ to $FreeBSD$. We are not
ready for it yet.
808a36ef658c1810327b5d329469bcf5dad24b28 14-Jan-1997 jkh <jkh@FreeBSD.org> Make the long-awaited change from $Id$ to $FreeBSD$

This will make a number of things easier in the future, as well as (finally!)
avoiding the Id-smashing problem which has plagued developers for so long.

Boy, I'm glad we're not using sup anymore. This update would have been
insane otherwise.
f1d17a487d67ecb4abe31aa12d94c1fd17e0513b 29-Dec-1996 phk <phk@FreeBSD.org> Add
SLIST_EMPTY(head)
SLIST_FIRST(head)
SLIST_NEXT(elm, field)

Which do the obvious things while hiding implementation details.
242e10df110e682d1d2f90d9734a4fd3436f24c1 18-May-1996 dyson <dyson@FreeBSD.org> This set of commits to the VM system does the following, and contain
contributions or ideas from Stephen McKay <syssgm@devetir.qld.gov.au>,
Alan Cox <alc@cs.rice.edu>, David Greenman <davidg@freebsd.org> and me:

More usage of the TAILQ macros. Additional minor fix to queue.h.
Performance enhancements to the pageout daemon.
Addition of a wait in the case that the pageout daemon
has to run immediately.
Slightly modify the pageout algorithm.
Significant revamp of the pmap/fork code:
1) PTE's and UPAGES's are NO LONGER in the process's map.
2) PTE's and UPAGES's reside in their own objects.
3) TOTAL elimination of recursive page table pagefaults.
4) The page directory now resides in the PTE object.
5) Implemented pmap_copy, thereby speeding up fork time.
6) Changed the pv entries so that the head is a pointer
and not an entire entry.
7) Significant cleanup of pmap_protect, and pmap_remove.
8) Removed significant amounts of machine dependent
fork code from vm_glue. Pushed much of that code into
the machine dependent pmap module.
9) Support more completely the reuse of already zeroed
pages (Page table pages and page directories) as being
already zeroed.
Performance and code cleanups in vm_map:
1) Improved and simplified allocation of map entries.
2) Improved vm_map_copy code.
3) Corrected some minor problems in the simplify code.
Implemented splvm (combo of splbio and splimp.) The VM code now
seldom uses splhigh.
Improved the speed of and simplified kmem_malloc.
Minor mod to vm_fault to avoid using pre-zeroed pages in the case
of objects with backing objects along with the already
existant condition of having a vnode. (If there is a backing
object, there will likely be a COW... With a COW, it isn't
necessary to start with a pre-zeroed page.)
Minor reorg of source to perhaps improve locality of ref.
88dda49bb233320ac75fdb2c834957e1f237b4b1 08-Apr-1996 phk <phk@FreeBSD.org> Add five macros to TAILQ family to improve readability.
1f233472df4a82eba0fe2bd474203b4c65f791d4 31-Mar-1996 gibbs <gibbs@FreeBSD.org> Implement the SLIST and the STAILQ macros. This gives a program all the
aesthetics of using the 4.4 queue macros without paying undo space or time
in scenartios where a singly-linked list works fine.

From queue.h:
/*
* A singly-linked list is headed by a single forward pointer. The elements
* are singly linked for minimum space and pointer manipulation overhead at
* the expense of O(n) removal for arbitrary elements. New elements can be
* added to the list after an existing element or at the head of the list.
* Elements being removed from the head of the list should use the explicit
* macro for this purpose for optimum efficiency. A singly-linked list may
* only be traversed in the forward direction. Singly-linked lists are ideal
* for applications with large datasets and few or no removals or for
* implementing a LIFO queue.
*
* A singly-linked tail queue is headed by a pair of pointers, one to the
* head of the list and the other to the tail of the list. The elements are
* singly linked for minimum space and pointer manipulation overhead at the
* expense of O(n) removal for arbitrary elements. New elements can be added
* to the list after an existing element, at the head of the list, or at the
* end of the list. Elements being removed from the head of the tail queue
* should use the explicit macro for this purpose for optimum efficiency.
* A singly-linked tail queue may only be traversed in the forward direction.
* Singly-linked tail queues are ideal for applications with large datasets
* and few or no removals or for implementing a FIFO queue.
*/
73a498e93ef77f792f958b4a1ea0d9ad0490888a 11-Mar-1996 peter <peter@FreeBSD.org> Import 4.4BSD-Lite2 onto the vendor branch, note that in the kernel, all
files are off the vendor branch, so this should not change anything.

A "U" marker generally means that the file was not changed in between
the 4.4Lite and Lite-2 releases, and does not need a merge. "C" generally
means that there was a change.
[new sys/syscallargs.h file, to be "cvs rm"ed]
c74a394f0fdbc1437617bb61030299a259d50f7d 11-Mar-1996 hsu <hsu@FreeBSD.org> Merge in Lite2: fix comment
optimize TAILQ_INSERT_HEAD
Reviewed by: davidg & bde
7b4fbe06e33c77e2a69704a923cccda45bf0bdf0 12-Feb-1996 gibbs <gibbs@FreeBSD.org> 4.4Lite2 implemented the LIST_INSERT_BEFORE and TAILQ_INSERT_BEFORE
exactly as I did (should have checked there first I guess) except my
macro for TAILQ_INSERT_BEFORE took an unneeded arg. We now match 4.4Lite2.

Suggested by: Jeffrey Hsu <hsu@FreeBSD.org>
2d24ffe647290dcbf969b95b9a51daa87c5301fd 29-Jan-1996 gibbs <gibbs@FreeBSD.org> Add LIST_INSERT_BEFORE and TAILQ_INSERT_BEFORE. These are used by the
new eisaconf code.
35ee95831939f06cb374e771e2a51cf938bff1fa 03-Dec-1995 bde <bde@FreeBSD.org> Moved inline functions for insque() and remque() to <sys/queue.h>.
Protected them with `#ifdef KERNEL' so that <sys/queue.h> is valid C++.
Added the necessary #includes of <sys/queue.h>.

These functions are bogus and should be replaced by the queue macros.
86f1bc4514fdcfd255f37f3218fe234bdc3664fc 05-Nov-1995 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'LINUX'.
c86f0c7a71e7ade3e38b325c186a9cf374e0411e 30-May-1995 rgrimes <rgrimes@FreeBSD.org> Remove trailing whitespace.
2e14d9ebc3d3592c67bdf625af9ebe0dfc386653 14-Mar-1995 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'MATT_THOMAS'.
34cd81d75f398ee455e61969b118639dacbfd7a6 23-Sep-1994 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'MACKERRAS'.
e16baf7a5fe7ac1453381d0017ed1dcdeefbc995 07-Aug-1994 cvs2svn <cvs2svn@FreeBSD.org> This commit was manufactured by cvs2svn to create branch 'SUNRPC'.
8d205697aac53476badf354623abd4e1c7bc5aff 02-Aug-1994 dg <dg@FreeBSD.org> Added $Id$
8fb65ce818b3e3c6f165b583b910af24000768a5 24-May-1994 rgrimes <rgrimes@FreeBSD.org> BSD 4.4 Lite Kernel Sources