diff options
Diffstat (limited to 'share/man/man3/queue.3')
-rw-r--r-- | share/man/man3/queue.3 | 180 |
1 files changed, 151 insertions, 29 deletions
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 index be890fd2cc88..79c8d92decbe 100644 --- a/share/man/man3/queue.3 +++ b/share/man/man3/queue.3 @@ -25,7 +25,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd April 8, 2024 +.Dd April 28, 2025 .Dt QUEUE 3 .Os .Sh NAME @@ -33,6 +33,7 @@ .Nm SLIST_CLASS_HEAD , .Nm SLIST_CONCAT , .Nm SLIST_EMPTY , +.Nm SLIST_EMPTY_ATOMIC , .Nm SLIST_ENTRY , .Nm SLIST_FIRST , .Nm SLIST_FOREACH , @@ -48,11 +49,13 @@ .Nm SLIST_REMOVE , .Nm SLIST_REMOVE_AFTER , .Nm SLIST_REMOVE_HEAD , +.Nm SLIST_SPLIT_AFTER , .Nm SLIST_SWAP , .Nm STAILQ_CLASS_ENTRY , .Nm STAILQ_CLASS_HEAD , .Nm STAILQ_CONCAT , .Nm STAILQ_EMPTY , +.Nm STAILQ_EMPTY_ATOMIC , .Nm STAILQ_ENTRY , .Nm STAILQ_FIRST , .Nm STAILQ_FOREACH , @@ -70,11 +73,14 @@ .Nm STAILQ_REMOVE , .Nm STAILQ_REMOVE_AFTER , .Nm STAILQ_REMOVE_HEAD , +.Nm STAILQ_REVERSE , +.Nm STAILQ_SPLIT_AFTER , .Nm STAILQ_SWAP , .Nm LIST_CLASS_ENTRY , .Nm LIST_CLASS_HEAD , .Nm LIST_CONCAT , .Nm LIST_EMPTY , +.Nm LIST_EMPTY_ATOMIC , .Nm LIST_ENTRY , .Nm LIST_FIRST , .Nm LIST_FOREACH , @@ -91,11 +97,13 @@ .Nm LIST_PREV , .Nm LIST_REMOVE , .Nm LIST_REPLACE , +.Nm LIST_SPLIT_AFTER , .Nm LIST_SWAP , .Nm TAILQ_CLASS_ENTRY , .Nm TAILQ_CLASS_HEAD , .Nm TAILQ_CONCAT , .Nm TAILQ_EMPTY , +.Nm TAILQ_EMPTY_ATOMIC , .Nm TAILQ_ENTRY , .Nm TAILQ_FIRST , .Nm TAILQ_FOREACH , @@ -118,6 +126,7 @@ .Nm TAILQ_PREV , .Nm TAILQ_REMOVE , .Nm TAILQ_REPLACE , +.Nm TAILQ_SPLIT_AFTER , .Nm TAILQ_SWAP .Nd implementations of singly-linked lists, singly-linked tail queues, lists and tail queues @@ -128,6 +137,7 @@ lists and tail queues .Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_EMPTY "SLIST_HEAD *head" +.Fn SLIST_EMPTY_ATOMIC "SLIST_HEAD *head" .Fn SLIST_ENTRY "TYPE" .Fn SLIST_FIRST "SLIST_HEAD *head" .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" @@ -143,12 +153,14 @@ lists and tail queues .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.Fn SLIST_SPLIT_AFTER "SLIST_HEAD *head" "TYPE *elm" "SLIST_HEAD *rest" "SLIST_ENTRY NAME" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" .\" .Fn STAILQ_CLASS_ENTRY "CLASSTYPE" .Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" .Fn STAILQ_EMPTY "STAILQ_HEAD *head" +.Fn STAILQ_EMPTY_ATOMIC "STAILQ_HEAD *head" .Fn STAILQ_ENTRY "TYPE" .Fn STAILQ_FIRST "STAILQ_HEAD *head" .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" @@ -166,12 +178,15 @@ lists and tail queues .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_REVERSE "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" +.Fn STAILQ_SPLIT_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_HEAD *rest" "STAILQ_ENTRY NAME" .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE" .\" .Fn LIST_CLASS_ENTRY "CLASSTYPE" .Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .Fn LIST_EMPTY "LIST_HEAD *head" +.Fn LIST_EMPTY_ATOMIC "LIST_HEAD *head" .Fn LIST_ENTRY "TYPE" .Fn LIST_FIRST "LIST_HEAD *head" .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" @@ -188,12 +203,14 @@ lists and tail queues .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME" .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" .Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME" +.Fn LIST_SPLIT_AFTER "LIST_HEAD *head" "TYPE *elm" "LIST_HEAD *rest" "LIST_ENTRY NAME" .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" .\" .Fn TAILQ_CLASS_ENTRY "CLASSTYPE" .Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE" .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" .Fn TAILQ_EMPTY "TAILQ_HEAD *head" +.Fn TAILQ_EMPTY_ATOMIC "TAILQ_HEAD *head" .Fn TAILQ_ENTRY "TYPE" .Fn TAILQ_FIRST "TAILQ_HEAD *head" .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" @@ -216,6 +233,7 @@ lists and tail queues .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" .Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME" +.Fn TAILQ_SPLIT_AFTER "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_HEAD *rest" "TAILQ_ENTRY NAME" .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" .\" .Sh DESCRIPTION @@ -242,6 +260,8 @@ O(1) removal of an entry from the head of the list. .It Forward traversal through the list. .It +Splitting a list in two after any element in the list. +.It Swapping the contents of two lists. .El .Pp @@ -425,6 +445,10 @@ high-usage code paths or to operate on long lists. The macro .Nm SLIST_EMPTY evaluates to true if there are no elements in the list. +The +.Nm SLIST_EMPTY_ATOMIC +variant has the same behavior, but can be safely used in contexts where it is +possible that a different thread is concurrently updating the list. .Pp The macro .Nm SLIST_ENTRY @@ -535,6 +559,17 @@ A doubly-linked list should be used if this macro is needed in high-usage code paths or to operate on long lists. .Pp The macro +.Nm SLIST_SPLIT_AFTER +splits the list referenced by +.Fa head , +making +.Fa rest +reference the list formed by elements after +.Fa elm +in +.Fa head . +.Pp +The macro .Nm SLIST_SWAP swaps the contents of .Fa head1 @@ -633,6 +668,10 @@ removing all entries from the former. The macro .Nm STAILQ_EMPTY evaluates to true if there are no items on the tail queue. +The +.Nm STAILQ_EMPTY_ATOMIC +variant has the same behavior, but can be safely used in contexts where it is +possible that a different thread is concurrently updating the queue. .Pp The macro .Nm STAILQ_ENTRY @@ -754,6 +793,21 @@ A doubly-linked tail queue should be used if this macro is needed in high-usage code paths or to operate on long tail queues. .Pp The macro +.Nm STAILQ_REVERSE +reverses the queue in place. +.Pp +The macro +.Nm STAILQ_SPLIT_AFTER +splits the tail queue referenced by +.Fa head , +making +.Fa rest +reference the tail queue formed by elements after +.Fa elm +in +.Fa head . +.Pp +The macro .Nm STAILQ_SWAP swaps the contents of .Fa head1 @@ -866,6 +920,10 @@ high-usage code paths or to operate on long lists. The macro .Nm LIST_EMPTY evaluates to true if there are no elements in the list. +The +.Nm LIST_EMPTY_ATOMIC +variant has the same behavior, but can be safely used in contexts where it is +possible that a different thread is concurrently updating the list. .Pp The macro .Nm LIST_ENTRY @@ -978,6 +1036,17 @@ The element must not already be on a list. .Pp The macro +.Nm LIST_SPLIT_AFTER +splits the list referenced by +.Fa head , +making +.Fa rest +reference the list formed by elements after +.Fa elm +in +.Fa head . +.Pp +The macro .Nm LIST_SWAP swaps the contents of .Fa head1 @@ -1084,6 +1153,10 @@ removing all entries from the former. The macro .Nm TAILQ_EMPTY evaluates to true if there are no items on the tail queue. +The +.Nm TAILQ_EMPTY_ATOMIC +variant has the same behavior, but can be safely used in contexts where it is +possible that a different thread is concurrently updating the queue. .Pp The macro .Nm TAILQ_ENTRY @@ -1247,6 +1320,17 @@ The element must not already be on a list. .Pp The macro +.Nm TAILQ_SPLIT_AFTER +splits the tail queue referenced by +.Fa head , +making +.Fa rest +reference the tail queue formed by elements after +.Fa elm +in +.Fa head . +.Pp +The macro .Nm TAILQ_SWAP swaps the contents of .Fa head1 @@ -1312,49 +1396,87 @@ while (n1 != NULL) { TAILQ_INIT(&head); .Ed .Sh DIAGNOSTICS -When debugging -.Nm queue(3) , -it can be useful to trace queue changes. -To enable tracing, define the macro -.Va QUEUE_MACRO_DEBUG_TRACE -at compile time. +.Nm queue(3) +provides several diagnostic and debugging facilities. .Pp -It can also be useful to trash pointers that have been unlinked from a queue, -to detect use after removal. -To enable pointer trashing, define the macro -.Va QUEUE_MACRO_DEBUG_TRASH -at compile time. -The macro -.Fn QMD_IS_TRASHED "void *ptr" -returns true if -.Fa ptr -has been trashed by the -.Va QUEUE_MACRO_DEBUG_TRASH -option. +Check code that performs basic integrity and API conformance checks is +automatically inserted when using queue macros in the kernel if compiling it +with +.Va INVARIANTS . +One can request insertion or elision of check code by respectively defining one +of the macros +.Va QUEUE_MACRO_DEBUG_ASSERTIONS +or +.Va QUEUE_MACRO_NO_DEBUG_ASSERTIONS +before first inclusion of +.In sys/queue.h . +When check code encounters an anomaly, it panics the kernel or aborts the +program. +To this end, in the kernel or in +.Va _STANDALONE +builds, it by default calls +.Fn panic , +while in userland builds it prints the diagnostic message on +.Dv stderr +and then calls +.Fn abort . +These behaviors can be overriden by defining a custom +.Fn QMD_PANIC +macro before first inclusion of +.In sys/queue.h . +The diagnostic messages automatically include the source file, line and function +where the failing check occured. +This behavior can be overriden by defining a custom +.Fn QMD_ASSERT +macro before first inclusion of +.In sys/queue.h . .Pp -In the kernel (with -.Va INVARIANTS -enabled), the +The .Fn SLIST_REMOVE_PREVPTR macro is available to aid debugging: .Bl -hang -offset indent .It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME" .Pp -Removes +Removes element .Fa elm , which must directly follow the element whose .Va &SLIST_NEXT() is .Fa prev , -from the SLIST. -This macro validates that +from the list. +This macro may insert, under conditions detailed above, check code that +validates that .Fa elm -follows +indeed follows .Fa prev -in -.Va INVARIANTS -mode. +in the list +.Po +through the +.Fn QMD_SLIST_CHECK_PREVPTR +macro +.Pc . .El +.Pp +When debugging, it can be useful to trace queue changes. +To enable tracing, define the macro +.Va QUEUE_MACRO_DEBUG_TRACE . +Note that, at the moment, only macros for regular tail queues have been +instrumented. +.Pp +It can also be useful to trash pointers that have been unlinked from a queue, +to detect use after removal. +To enable pointer trashing, define the macro +.Va QUEUE_MACRO_DEBUG_TRASH +at compile time. +Note that, at the moment, only a limited number of macros have been +instrumented. +The macro +.Fn QMD_IS_TRASHED "void *ptr" +returns true if +.Fa ptr +has been trashed by the +.Va QUEUE_MACRO_DEBUG_TRASH +option. .Sh SEE ALSO .Xr arb 3 , .Xr tree 3 |