tech-kern archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
pserialized queue(9)
The attached patch adds _PSZ variants to all the insert, remove, and
foreach operations in <sys/queue.h> to issue the necessary store
barriers, for insert, and data-dependent load barriers, for foreach.
I made *_REMOVE*_PSZ an alias for *_REMOVE* so that if you're using
pserialize with a queue, all of the operations you perform on it after
initialization are marked with _PSZ. That way it should be easy to
eyeball code for obvious mistakes.
There is no, e.g., LIST_NEXT_PSZ because there's no good way to
express that without expression blocks. Most readers need to iterate
over a queue, anyway, rather than just fetch one entry's next pointer.
I omitted TAILQ_FOREACH_REVERSE_PSZ because, as Dennis observed, TAILQ
reverse traversal violates strict aliasing, so we need a new kind of
queue for that. (It's also not clear it would be useful.)
I have only compile-tested so far -- I'm asking for review on the
concept before I spend a lot of my Copious Spare Time^TM engineering
and running stress tests. Thoughts?
Index: share/man/man3/queue.3
===================================================================
RCS file: /cvsroot/src/share/man/man3/queue.3,v
retrieving revision 1.49
diff -p -u -r1.49 queue.3
--- share/man/man3/queue.3 18 May 2014 15:45:08 -0000 1.49
+++ share/man/man3/queue.3 21 Nov 2014 05:04:36 -0000
@@ -53,7 +53,7 @@
.\"
.\" @(#)queue.3 8.1 (Berkeley) 12/13/93
.\"
-.Dd May 17, 2014
+.Dd November 20, 2014
.Dt QUEUE 3
.Os
.Sh NAME
@@ -64,13 +64,19 @@
.Nm SLIST_EMPTY ,
.Nm SLIST_NEXT ,
.Nm SLIST_FOREACH ,
+.Nm SLIST_FOREACH_PSZ ,
.Nm SLIST_FOREACH_SAFE ,
.Nm SLIST_INIT ,
.Nm SLIST_INSERT_AFTER ,
+.Nm SLIST_INSERT_AFTER_PSZ ,
.Nm SLIST_INSERT_HEAD ,
+.Nm SLIST_INSERT_HEAD_PSZ ,
.Nm SLIST_REMOVE_AFTER ,
+.Nm SLIST_REMOVE_AFTER_PSZ ,
.Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_REMOVE_HEAD_PSZ ,
.Nm SLIST_REMOVE ,
+.Nm SLIST_REMOVE_PSZ ,
.Nm LIST_HEAD ,
.Nm LIST_HEAD_INITIALIZER ,
.Nm LIST_ENTRY ,
@@ -78,12 +84,17 @@
.Nm LIST_EMPTY ,
.Nm LIST_NEXT ,
.Nm LIST_FOREACH ,
+.Nm LIST_FOREACH_PSZ ,
.Nm LIST_FOREACH_SAFE ,
.Nm LIST_INIT ,
.Nm LIST_INSERT_AFTER ,
+.Nm LIST_INSERT_AFTER_PSZ ,
.Nm LIST_INSERT_BEFORE ,
+.Nm LIST_INSERT_BEFORE_PSZ ,
.Nm LIST_INSERT_HEAD ,
+.Nm LIST_INSERT_HEAD_PSZ ,
.Nm LIST_REMOVE ,
+.Nm LIST_REMOVE_PSZ ,
.Nm LIST_REPLACE ,
.Nm LIST_MOVE ,
.Nm SIMPLEQ_HEAD ,
@@ -94,14 +105,21 @@
.Nm SIMPLEQ_NEXT ,
.Nm SIMPLEQ_LAST ,
.Nm SIMPLEQ_FOREACH ,
+.Nm SIMPLEQ_FOREACH_PSZ ,
.Nm SIMPLEQ_FOREACH_SAFE ,
.Nm SIMPLEQ_INIT ,
.Nm SIMPLEQ_INSERT_AFTER ,
+.Nm SIMPLEQ_INSERT_AFTER_PSZ ,
.Nm SIMPLEQ_INSERT_HEAD ,
+.Nm SIMPLEQ_INSERT_HEAD_PSZ ,
.Nm SIMPLEQ_INSERT_TAIL ,
+.Nm SIMPLEQ_INSERT_TAIL_PSZ ,
.Nm SIMPLEQ_REMOVE_AFTER ,
+.Nm SIMPLEQ_REMOVE_AFTER_PSZ ,
.Nm SIMPLEQ_REMOVE_HEAD ,
+.Nm SIMPLEQ_REMOVE_HEAD_PSZ ,
.Nm SIMPLEQ_REMOVE ,
+.Nm SIMPLEQ_REMOVE_PSZ ,
.Nm SIMPLEQ_CONCAT ,
.Nm TAILQ_HEAD ,
.Nm TAILQ_HEAD_INITIALIZER ,
@@ -112,15 +130,21 @@
.Nm TAILQ_PREV ,
.Nm TAILQ_EMPTY ,
.Nm TAILQ_FOREACH ,
+.Nm TAILQ_FOREACH_PSZ ,
.Nm TAILQ_FOREACH_SAFE ,
.Nm TAILQ_FOREACH_REVERSE ,
.Nm TAILQ_FOREACH_REVERSE_SAFE ,
.Nm TAILQ_INIT ,
.Nm TAILQ_INSERT_AFTER ,
+.Nm TAILQ_INSERT_AFTER_PSZ ,
.Nm TAILQ_INSERT_BEFORE ,
+.Nm TAILQ_INSERT_BEFORE_PSZ ,
.Nm TAILQ_INSERT_HEAD ,
+.Nm TAILQ_INSERT_HEAD_PSZ ,
.Nm TAILQ_INSERT_TAIL ,
+.Nm TAILQ_INSERT_TAIL_PSZ ,
.Nm TAILQ_REMOVE ,
+.Nm TAILQ_REMOVE_PSZ ,
.Nm TAILQ_REPLACE ,
.Nm TAILQ_CONCAT ,
.Nm STAILQ_HEAD ,
@@ -131,12 +155,17 @@
.Nm STAILQ_NEXT ,
.Nm STAILQ_LAST ,
.Nm STAILQ_FOREACH ,
+.Nm STAILQ_FOREACH_PSZ ,
.Nm STAILQ_FOREACH_SAFE ,
.Nm STAILQ_INIT ,
.Nm STAILQ_INSERT_AFTER ,
+.Nm STAILQ_INSERT_AFTER_PSZ ,
.Nm STAILQ_INSERT_HEAD ,
+.Nm STAILQ_INSERT_HEAD_PSZ ,
.Nm STAILQ_INSERT_TAIL ,
+.Nm STAILQ_INSERT_TAIL_PSZ ,
.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE_HEAD_PSZ ,
.Nm STAILQ_REMOVE ,
.Nm STAILQ_CONCAT ,
.Nd implementations of singly-linked lists, lists, simple queues, tail queues, and singly-linked tail queues
@@ -153,12 +182,17 @@
.Ft TYPE *
.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_FOREACH_PSZ "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *tmp"
.Fn SLIST_INIT "SLIST_HEAD *head"
.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
+.Fn SLIST_INSERT_HEAD_PSZ "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
+.Fn SLIST_INSERT_AFTER_PSZ "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE_PSZ "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_REMOVE_HEAD_PSZ "SLIST_HEAD *head" "SLIST_ENTRY NAME"
.Pp
.Fn LIST_HEAD "HEADNAME" "TYPE"
.Fn LIST_HEAD_INITIALIZER "head"
@@ -170,12 +204,17 @@
.Ft int
.Fn LIST_EMPTY "LIST_HEAD *head"
.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
+.Fn LIST_FOREACH_PSZ "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *tmp"
.Fn LIST_INIT "LIST_HEAD *head"
.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
+.Fn LIST_INSERT_AFTER_PSZ "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
+.Fn LIST_INSERT_BEFORE_PSZ "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
+.Fn LIST_INSERT_HEAD_PSZ "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
+.Fn LIST_REMOVE_PSZ "TYPE *elm" "LIST_ENTRY NAME"
.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME"
.Fn LIST_MOVE "LIST_HEAD *head1" "LIST_HEAD *head2"
.Pp
@@ -191,14 +230,21 @@
.Ft TYPE *
.Fn SIMPLEQ_LAST "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_FOREACH "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_FOREACH_PSZ "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_FOREACH_SAFE "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" "TYPE *tmp"
.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head"
.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_INSERT_HEAD_PSZ "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_INSERT_TAIL_PSZ "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_INSERT_AFTER_PSZ "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_REMOVE_HEAD_PSZ "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_REMOVE_AFTER_PSZ "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_REMOVE "SIMPLEQ_HEAD *head" "TYPE *elm" "TYPE" "SIMPLEQ_ENTRY NAME"
+.Fn SIMPLEQ_REMOVE_PSZ "SIMPLEQ_HEAD *head" "TYPE *elm" "TYPE" "SIMPLEQ_ENTRY NAME"
.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2"
.Pp
.Fn TAILQ_HEAD "HEADNAME" "TYPE"
@@ -215,15 +261,21 @@
.Ft int
.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
+.Fn TAILQ_FOREACH_PSZ "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *tmp"
.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *tmp"
.Fn TAILQ_INIT "TAILQ_HEAD *head"
.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_INSERT_HEAD_PSZ "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_INSERT_TAIL_PSZ "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_INSERT_AFTER_PSZ "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_INSERT_BEFORE_PSZ "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
+.Fn TAILQ_REMOVE_PSZ "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME"
.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
.Pp
@@ -239,13 +291,19 @@
.Ft TYPE *
.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
+.Fn STAILQ_FOREACH_PSZ "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *tmp"
.Fn STAILQ_INIT "STAILQ_HEAD *head"
.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
+.Fn STAILQ_INSERT_HEAD_PSZ "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
+.Fn STAILQ_INSERT_TAIL_PSZ "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
+.Fn STAILQ_INSERT_AFTER_PSZ "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
+.Fn STAILQ_REMOVE_HEAD_PSZ "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
+.Fn STAILQ_REMOVE_PSZ "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
.Sh DESCRIPTION
These macros define and operate on five types of data structures:
@@ -263,6 +321,14 @@ Removal of any entry in the list.
Forward traversal through the list.
.El
.Pp
+All five structures additionally support variants of the above
+operations that issue the necessary memory barriers for passive
+serialization,
+.Xr pserialize 9 .
+See
+.Sx PASSIVE SERIALIZATION
+for details.
+.Pp
Singly-linked lists are the simplest of the four data structures and
support only the above functionality.
Singly-linked lists are ideal for applications with large datasets and
@@ -1072,6 +1138,60 @@ and
are functionally identical to these simple queue functions,
and are provided for compatibility with
.Fx .
+.Sh PASSIVE SERIALIZATION
+All queue structures support operations that issue the necessary memory
+barriers for passive serialization,
+.Xr pserialize 9 ,
+named with the suffix
+.Li _PSZ .
+Specifically:
+.Bl -bullet -offset indent
+.It
+A writer may publish an entry with
+.Fn *_INSERT_*_PSZ
+(e.g.,
+.Fn TAILQ_INSERT_TAIL_PSZ ) Ns .
+.Pp
+The
+.Fn *_INSERT_*_PSZ
+operations will issue any necessary store barrier before publishing the
+entry to other CPUs.
+.It
+A writer may remove an entry with
+.Fn *_REMOVE*_PSZ
+(e.g.,
+.Fn TAILQ_REMOVE_PSZ )
+and then issue
+.Fn pserialize_perform
+to make sure no more readers have access to it before freeing or
+reusing the memory allocated for it.
+.Pp
+The
+.Fn *_REMOVE*_PSZ
+operations are identical to the non-pserialized versions, but are
+provided nevertheless to make it clearer when passive serialization is
+involved.
+.It
+A reader may iterate over a queue forward (but not backward) with
+.Fn *_FOREACH_PSZ
+(e.g.,
+.Fn TAILQ_FOREACH_PSZ ) Ns .
+.Pp
+The
+.Fn *_FOREACH_PSZ
+macros issue any necessary data-dependent load barrier after fetching
+the pointer to the current entry and before entering the body of the
+loop.
+.Pp
+Writers may use
+.Fn *_FOREACH ;
+they need not use
+.Fn *_FOREACH_PSZ
+(although it would not hurt to do so).
+There are no
+.Fn *_FOREACH_SAFE_PSZ
+macros because readers have no need for it.
+.El
.Sh NOTES
Some of these macros or functions perform no error checking,
and invalid usage leads to undefined behaviour.
Index: sys/sys/queue.h
===================================================================
RCS file: /cvsroot/src/sys/sys/queue.h,v
retrieving revision 1.67
diff -p -u -r1.67 queue.h
--- sys/sys/queue.h 17 May 2014 21:22:56 -0000 1.67
+++ sys/sys/queue.h 21 Nov 2014 05:04:36 -0000
@@ -77,6 +77,17 @@
* A circle queue may be traversed in either direction, but has a more
* complex end of list detection.
*
+ * The *_PSZ variants of the macros here are safe to use with passive
+ * serialization, pserialize(9). Specifically:
+ *
+ * - A writer may publish a new entry with *_INSERT*_PSZ.
+ *
+ * - A writer may remove an entry with *_REMOVE*_PSZ and then issue
+ * pserialize_perform to make sure no more readers have it before
+ * freeing it.
+ *
+ * - A reader may iterate forward over a queue with *_FOREACH_PSZ.
+ *
* For details on the use of these macros, see the queue(3) manual page.
*/
@@ -86,8 +97,15 @@
* portable and it can simply be dropped verbatim into any system.
* The caveat is that on other systems some other header
* must provide NULL before the macros can be used.
+ *
+ * Likewise <sys/atomic.h> -- you will need to redefine the *_PSZ
+ * macros for passive serialization if you want to use other systems'
+ * atomic operations.
+ *
+ * WARNING: QUEUEDEBUG is incompatible with passive serialization.
*/
#ifdef __NetBSD__
+#include <sys/atomic.h>
#include <sys/null.h>
#endif
@@ -124,11 +142,15 @@ struct { \
#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
-#define SLIST_FOREACH(var, head, field) \
- for((var) = (head)->slh_first; \
- (var) != SLIST_END(head); \
+#define _SLIST_FOREACH(var, head, field, barrier) \
+ for ((var) = (head)->slh_first; \
+ ((var) != SLIST_END(head) && (barrier, 1)); \
(var) = (var)->field.sle_next)
+#define SLIST_FOREACH(v,h,f) _SLIST_FOREACH(v,h,f,((void)0))
+#define SLIST_FOREACH_PSZ(v,h,f) \
+ _SLIST_FOREACH(v,h,f,membar_datadep_consumer())
+
#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
for ((var) = SLIST_FIRST((head)); \
(var) != SLIST_END(head) && \
@@ -142,25 +164,39 @@ struct { \
(head)->slh_first = SLIST_END(head); \
} while (/*CONSTCOND*/0)
-#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
+#define _SLIST_INSERT_AFTER(slistelm, elm, field, barrier) do { \
(elm)->field.sle_next = (slistelm)->field.sle_next; \
+ barrier; \
(slistelm)->field.sle_next = (elm); \
} while (/*CONSTCOND*/0)
-#define SLIST_INSERT_HEAD(head, elm, field) do { \
+#define SLIST_INSERT_AFTER(s,e,f) _SLIST_INSERT_AFTER(s,e,f,((void)0))
+#define SLIST_INSERT_AFTER_PSZ(s,e,f) \
+ _SLIST_INSERT_AFTER(s,e,f,membar_producer())
+
+#define _SLIST_INSERT_HEAD(head, elm, field, barrier) do { \
(elm)->field.sle_next = (head)->slh_first; \
+ barrier; \
(head)->slh_first = (elm); \
} while (/*CONSTCOND*/0)
+#define SLIST_INSERT_HEAD(h,e,f) _SLIST_INSERT_HEAD(h,e,f,((void)0))
+#define SLIST_INSERT_HEAD_PSZ(h,e,f) \
+ _SLIST_INSERT_HEAD(s,e,f,membar_producer())
+
#define SLIST_REMOVE_AFTER(slistelm, field) do { \
(slistelm)->field.sle_next = \
SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \
} while (/*CONSTCOND*/0)
+#define SLIST_REMOVE_AFTER_PSZ SLIST_REMOVE_AFTER
+
#define SLIST_REMOVE_HEAD(head, field) do { \
(head)->slh_first = (head)->slh_first->field.sle_next; \
} while (/*CONSTCOND*/0)
+#define SLIST_REMOVE_HEAD_PSZ SLIST_REMOVE_HEAD
+
#define SLIST_REMOVE(head, elm, type, field) do { \
if ((head)->slh_first == (elm)) { \
SLIST_REMOVE_HEAD((head), field); \
@@ -174,6 +210,7 @@ struct { \
} \
} while (/*CONSTCOND*/0)
+#define SLIST_REMOVE_PSZ SLIST_REMOVE
/*
* List definitions.
@@ -200,11 +237,15 @@ struct { \
#define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head))
#define LIST_NEXT(elm, field) ((elm)->field.le_next)
-#define LIST_FOREACH(var, head, field) \
+#define _LIST_FOREACH(var, head, field, barrier) \
for ((var) = ((head)->lh_first); \
- (var) != LIST_END(head); \
+ ((var) != LIST_END(head) && (barrier, 1)); \
(var) = ((var)->field.le_next))
+#define LIST_FOREACH(v,h,f) _LIST_FOREACH(v,h,f,((void)0))
+#define LIST_FOREACH_PSZ(v,h,f) \
+ _LIST_FOREACH(v,h,f,membar_datadep_consumer())
+
#define LIST_FOREACH_SAFE(var, head, field, tvar) \
for ((var) = LIST_FIRST((head)); \
(var) != LIST_END(head) && \
@@ -250,32 +291,48 @@ struct { \
(head)->lh_first = LIST_END(head); \
} while (/*CONSTCOND*/0)
-#define LIST_INSERT_AFTER(listelm, elm, field) do { \
+#define _LIST_INSERT_AFTER(listelm, elm, field, barrier) do { \
QUEUEDEBUG_LIST_OP((listelm), field) \
- if (((elm)->field.le_next = (listelm)->field.le_next) != \
- LIST_END(head)) \
+ (elm)->field.le_next = (listelm)->field.le_next; \
+ (elm)->field.le_prev = &(listelm)->field.le_next; \
+ barrier; \
+ if ((elm)->field.le_next != LIST_END(head)) \
(listelm)->field.le_next->field.le_prev = \
&(elm)->field.le_next; \
(listelm)->field.le_next = (elm); \
- (elm)->field.le_prev = &(listelm)->field.le_next; \
} while (/*CONSTCOND*/0)
-#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
+#define LIST_INSERT_AFTER(l,e,f) _LIST_INSERT_AFTER(l,e,f,((void)0))
+#define LIST_INSERT_AFTER_PSZ(l,e,f) \
+ _LIST_INSERT_AFTER(l,e,f,membar_producer())
+
+#define _LIST_INSERT_BEFORE(listelm, elm, field, barrier) do { \
QUEUEDEBUG_LIST_OP((listelm), field) \
(elm)->field.le_prev = (listelm)->field.le_prev; \
(elm)->field.le_next = (listelm); \
+ barrier; \
*(listelm)->field.le_prev = (elm); \
(listelm)->field.le_prev = &(elm)->field.le_next; \
} while (/*CONSTCOND*/0)
-#define LIST_INSERT_HEAD(head, elm, field) do { \
+#define LIST_INSERT_BEFORE(l,e,f) _LIST_INSERT_BEFORE(l,e,f,((void)0))
+#define LIST_INSERT_BEFORE_PSZ(l,e,f) \
+ _LIST_INSERT_BEFORE(l,e,f,membar_producer())
+
+#define _LIST_INSERT_HEAD(head, elm, field, barrier) do { \
QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
- if (((elm)->field.le_next = (head)->lh_first) != LIST_END(head))\
+ (elm)->field.le_next = (head)->lh_first; \
+ (elm)->field.le_prev = &(head)->lh_first; \
+ barrier; \
+ if ((elm)->field.le_next != LIST_END(head)) \
(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
(head)->lh_first = (elm); \
- (elm)->field.le_prev = &(head)->lh_first; \
} while (/*CONSTCOND*/0)
+#define LIST_INSERT_HEAD(h,e,f) _LIST_INSERT_HEAD(h,e,f,((void)0))
+#define LIST_INSERT_HEAD_PSZ(h,e,f) \
+ _LIST_INSERT_HEAD(h,e,f,membar_producer())
+
#define LIST_REMOVE(elm, field) do { \
QUEUEDEBUG_LIST_OP((elm), field) \
if ((elm)->field.le_next != NULL) \
@@ -285,6 +342,8 @@ struct { \
QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
} while (/*CONSTCOND*/0)
+#define LIST_REMOVE_PSZ LIST_REMOVE
+
#define LIST_REPLACE(elm, elm2, field) do { \
if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
(elm2)->field.le_next->field.le_prev = \
@@ -319,11 +378,15 @@ struct { \
#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head))
#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
-#define SIMPLEQ_FOREACH(var, head, field) \
+#define _SIMPLEQ_FOREACH(var, head, field, barrier) \
for ((var) = ((head)->sqh_first); \
- (var) != SIMPLEQ_END(head); \
+ (var) != SIMPLEQ_END(head) && (barrier, 1); \
(var) = ((var)->field.sqe_next))
+#define SIMPLEQ_FOREACH(v,h,f) _SIMPLEQ_FOREACH(v,h,f,((void)0))
+#define SIMPLEQ_FOREACH_PSZ(v,h,f) \
+ _SIMPLEQ_FOREACH(v,h,f,membar_datadep_consumer())
+
#define SIMPLEQ_FOREACH_SAFE(var, head, field, next) \
for ((var) = ((head)->sqh_first); \
(var) != SIMPLEQ_END(head) && \
@@ -338,35 +401,56 @@ struct { \
(head)->sqh_last = &(head)->sqh_first; \
} while (/*CONSTCOND*/0)
-#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
- if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
+#define _SIMPLEQ_INSERT_HEAD(head, elm, field, barrier) do { \
+ (elm)->field.sqe_next = (head)->sqh_first; \
+ barrier; \
+ if ((elm)->field.sqe_next == NULL) \
(head)->sqh_last = &(elm)->field.sqe_next; \
(head)->sqh_first = (elm); \
} while (/*CONSTCOND*/0)
-#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
+#define SIMPLEQ_INSERT_HEAD(h,e,f) _SIMPLEQ_INSERT_HEAD(h,e,f,((void)0))
+#define SIMPLEQ_INSERT_HEAD_PSZ(h,e,f) \
+ _SIMPLEQ_INSERT_HEAD(h,e,f,membar_producer())
+
+#define _SIMPLEQ_INSERT_TAIL(head, elm, field, barrier) do { \
(elm)->field.sqe_next = NULL; \
+ barrier; \
*(head)->sqh_last = (elm); \
(head)->sqh_last = &(elm)->field.sqe_next; \
} while (/*CONSTCOND*/0)
-#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
- if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
+#define SIMPLEQ_INSERT_TAIL(h,e,f) _SIMPLEQ_INSERT_TAIL(h,e,f,((void)0))
+#define SIMPLEQ_INSERT_TAIL_PSZ(h,e,f) \
+ _SIMPLEQ_INSERT_TAIL(h,e,f,membar_producer())
+
+#define _SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ (elm)->field.sqe_next = (listelm)->field.sqe_next; \
+ barrier; \
+ if ((elm)->field.sqe_next == NULL) \
(head)->sqh_last = &(elm)->field.sqe_next; \
(listelm)->field.sqe_next = (elm); \
} while (/*CONSTCOND*/0)
+#define SIMPLEQ_INSERT_AFTER(h,e,f) _SIMPLEQ_INSERT_AFTER(h,e,f,((void)0))
+#define SIMPLEQ_INSERT_AFTER_PSZ(h,e,f) \
+ _SIMPLEQ_INSERT_AFTER(h,e,f,membar_producer())
+
#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
(head)->sqh_last = &(head)->sqh_first; \
} while (/*CONSTCOND*/0)
+#define SIMPLEQ_REMOVE_HEAD_PSZ SIMPLEQ_REMOVE_HEAD
+
#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
== NULL) \
(head)->sqh_last = &(elm)->field.sqe_next; \
} while (/*CONSTCOND*/0)
+#define SIMPLEQ_REMOVE_AFTER_PSZ SIMPLEQ_REMOVE_AFTER
+
#define SIMPLEQ_REMOVE(head, elm, type, field) do { \
if ((head)->sqh_first == (elm)) { \
SIMPLEQ_REMOVE_HEAD((head), field); \
@@ -380,6 +464,8 @@ struct { \
} \
} while (/*CONSTCOND*/0)
+#define SIMPLEQ_REMOVE_PSZ SIMPLEQ_REMOVE
+
#define SIMPLEQ_CONCAT(head1, head2) do { \
if (!SIMPLEQ_EMPTY((head2))) { \
*(head1)->sqh_last = (head2)->sqh_first; \
@@ -427,11 +513,15 @@ struct { \
#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
-#define TAILQ_FOREACH(var, head, field) \
+#define _TAILQ_FOREACH(var, head, field, barrier) \
for ((var) = ((head)->tqh_first); \
- (var) != TAILQ_END(head); \
+ (var) != TAILQ_END(head) && (barrier, 1); \
(var) = ((var)->field.tqe_next))
+#define TAILQ_FOREACH(v,h,f) _TAILQ_FOREACH(v,h,f,((void)0))
+#define TAILQ_FOREACH_PSZ(v,h,f) \
+ _TAILQ_FOREACH(v,h,f,membar_datadep_consumer())
+
#define TAILQ_FOREACH_SAFE(var, head, field, next) \
for ((var) = ((head)->tqh_first); \
(var) != TAILQ_END(head) && \
@@ -490,45 +580,66 @@ struct { \
(head)->tqh_last = &(head)->tqh_first; \
} while (/*CONSTCOND*/0)
-#define TAILQ_INSERT_HEAD(head, elm, field) do { \
+#define _TAILQ_INSERT_HEAD(head, elm, field, barrier) do { \
QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
- if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head))\
+ (elm)->field.tqe_prev = &(head)->tqh_first; \
+ (elm)->field.tqe_next = (head)->tqh_first; \
+ barrier; \
+ if ((elm)->field.tqe_next != TAILQ_END(head)) \
(head)->tqh_first->field.tqe_prev = \
&(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(head)->tqh_first = (elm); \
- (elm)->field.tqe_prev = &(head)->tqh_first; \
} while (/*CONSTCOND*/0)
-#define TAILQ_INSERT_TAIL(head, elm, field) do { \
+#define TAILQ_INSERT_HEAD(h,e,f) _TAILQ_INSERT_HEAD(h,e,f,((void)0))
+#define TAILQ_INSERT_HEAD_PSZ(h,e,f) \
+ _TAILQ_INSERT_HEAD(h,e,f,membar_producer())
+
+#define _TAILQ_INSERT_TAIL(head, elm, field, barrier) do { \
QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
(elm)->field.tqe_next = TAILQ_END(head); \
(elm)->field.tqe_prev = (head)->tqh_last; \
+ barrier; \
*(head)->tqh_last = (elm); \
(head)->tqh_last = &(elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
-#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
+#define TAILQ_INSERT_TAIL(h,e,f) _TAILQ_INSERT_TAIL(h,e,f,((void)0))
+#define TAILQ_INSERT_TAIL_PSZ(h,e,f) \
+ _TAILQ_INSERT_TAIL(h,e,f,membar_producer())
+
+#define _TAILQ_INSERT_AFTER(head, listelm, elm, field, barrier) do { \
QUEUEDEBUG_TAILQ_OP((listelm), field) \
- if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \
- TAILQ_END(head)) \
+ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
+ (elm)->field.tqe_next = (listelm)->field.tqe_next; \
+ barrier; \
+ if ((elm)->field.tqe_next != TAILQ_END(head)) \
(elm)->field.tqe_next->field.tqe_prev = \
&(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(listelm)->field.tqe_next = (elm); \
- (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
-#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
+#define TAILQ_INSERT_AFTER(h,l,e,f) _TAILQ_INSERT_AFTER(h,l,e,f,((void)0))
+#define TAILQ_INSERT_AFTER_PSZ(h,l,e,f) \
+ _TAILQ_INSERT_AFTER(h,l,e,f,membar_producer())
+
+#define _TAILQ_INSERT_BEFORE(listelm, elm, field, barrier) do { \
QUEUEDEBUG_TAILQ_OP((listelm), field) \
(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
(elm)->field.tqe_next = (listelm); \
+ barrier; \
*(listelm)->field.tqe_prev = (elm); \
(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
+#define TAILQ_INSERT_BEFORE(l,e,f) _TAILQ_INSERT_BEFORE(l,e,f,((void)0))
+#define TAILQ_INSERT_BEFORE_PSZ(l,e,f) \
+ _TAILQ_INSERT_BEFORE(l,e,f,membar_producer())
+
#define TAILQ_REMOVE(head, elm, field) do { \
QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
QUEUEDEBUG_TAILQ_OP((elm), field) \
@@ -541,6 +652,8 @@ struct { \
QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
} while (/*CONSTCOND*/0)
+#define TAILQ_REMOVE_PSZ TAILQ_REMOVE
+
#define TAILQ_REPLACE(head, elm, elm2, field) do { \
if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \
TAILQ_END(head)) \
@@ -595,29 +708,48 @@ struct { \
(head)->stqh_last = &(head)->stqh_first; \
} while (/*CONSTCOND*/0)
-#define STAILQ_INSERT_HEAD(head, elm, field) do { \
- if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
+#define _STAILQ_INSERT_HEAD(head, elm, field, barrier) do { \
+ (elm)->field.stqe_next = (head)->stqh_first; \
+ barrier; \
+ if ((elm)->field.stqe_next == NULL) \
(head)->stqh_last = &(elm)->field.stqe_next; \
(head)->stqh_first = (elm); \
} while (/*CONSTCOND*/0)
-#define STAILQ_INSERT_TAIL(head, elm, field) do { \
+#define STAILQ_INSERT_HEAD(h,e,f) _STAILQ_INSERT_HEAD(h,e,f,((void)0))
+#define STAILQ_INSERT_HEAD_PSZ(h,e,f) \
+ _STAILQ_INSERT_HEAD(h,e,f,membar_producer())
+
+#define _STAILQ_INSERT_TAIL(head, elm, field, barrier) do { \
(elm)->field.stqe_next = NULL; \
+ barrier; \
*(head)->stqh_last = (elm); \
(head)->stqh_last = &(elm)->field.stqe_next; \
} while (/*CONSTCOND*/0)
-#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
- if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
+#define STAILQ_INSERT_TAIL(h,e,f) _STAILQ_INSERT_TAIL(h,e,f,((void)0))
+#define STAILQ_INSERT_TAIL_PSZ(h,e,f) \
+ _STAILQ_INSERT_TAIL(h,e,f,membar_producer())
+
+#define _STAILQ_INSERT_AFTER(head, listelm, elm, field, barrier) do { \
+ (elm)->field.stqe_next = (listelm)->field.stqe_next; \
+ barrier; \
+ if ((elm)->field.stqe_next == NULL) \
(head)->stqh_last = &(elm)->field.stqe_next; \
(listelm)->field.stqe_next = (elm); \
} while (/*CONSTCOND*/0)
+#define STAILQ_INSERT_AFTER(h,l,e,f) _STAILQ_INSERT_AFTER(h,l,e,f,((void)0))
+#define STAILQ_INSERT_AFTER_PSZ(h,l,e,f) \
+ _STAILQ_INSERT_AFTER(h,l,e,f,membar_producer())
+
#define STAILQ_REMOVE_HEAD(head, field) do { \
if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
(head)->stqh_last = &(head)->stqh_first; \
} while (/*CONSTCOND*/0)
+#define STAILQ_REMOVE_HEAD_PSZ STAILQ_REMOVE_HEAD
+
#define STAILQ_REMOVE(head, elm, type, field) do { \
if ((head)->stqh_first == (elm)) { \
STAILQ_REMOVE_HEAD((head), field); \
@@ -631,11 +763,17 @@ struct { \
} \
} while (/*CONSTCOND*/0)
-#define STAILQ_FOREACH(var, head, field) \
+#define STAILQ_REMOVE_PSZ STAILQ_REMOVE
+
+#define _STAILQ_FOREACH(var, head, field, barrier) \
for ((var) = ((head)->stqh_first); \
- (var); \
+ (var) && (barrier, 1); \
(var) = ((var)->field.stqe_next))
+#define STAILQ_FOREACH(v,h,f) _STAILQ_FOREACH(v,h,f,((void)0))
+#define STAILQ_FOREACH_PSZ(v,h,f) \
+ _STAILQ_FOREACH(v,h,f,membar_datadep_consumer())
+
#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
for ((var) = STAILQ_FIRST((head)); \
(var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
Home |
Main Index |
Thread Index |
Old Index