xnu-4903.221.2.tar.gz

[apple/xnu.git] / bsd / sys / queue.h

diff --git a/bsd/sys/queue.h b/bsd/sys/queue.h
index a8e96cd4cec3a114a2c61702ea668c7f2054a603..aa26d76368174d0d426a2557c05d710e2dee4780 100644 (file)
--- a/bsd/sys/queue.h
+++ b/bsd/sys/queue.h
@@ -59,6 +59,15 @@
 #ifndef _SYS_QUEUE_H_
 #define        _SYS_QUEUE_H_
 
 #ifndef _SYS_QUEUE_H_
 #define        _SYS_QUEUE_H_
 

+#ifdef KERNEL_PRIVATE
+#include <kern/debug.h> /* panic function call */
+#include <sys/cdefs.h> /* __improbable in kernelspace */
+#else
+#ifndef __improbable
+#define __improbable(x) (x)            /* noop in userspace */
+#endif /* __improbable */
+#endif /* KERNEL_PRIVATE */
+

 /*
  * This file defines five types of data structures: singly-linked lists,
  * singly-linked tail queues, lists, tail queues, and circular queues.
 /*
  * This file defines five types of data structures: singly-linked lists,
  * singly-linked tail queues, lists, tail queues, and circular queues.


@@ -133,8 +142,11 @@
  * _INSERT_AFTER               +       +       +       +       +
  * _INSERT_TAIL                        -       -       +       +       +
  * _CONCAT                     -       -       +       +       -
  * _INSERT_AFTER               +       +       +       +       +
  * _INSERT_TAIL                        -       -       +       +       +
  * _CONCAT                     -       -       +       +       -

+ * _REMOVE_AFTER               +       -       +       -       -

  * _REMOVE_HEAD                        +       -       +       -       -
  * _REMOVE_HEAD                        +       -       +       -       -

+ * _REMOVE_HEAD_UNTIL          -       -       +       -       -

  * _REMOVE                     +       +       +       +       +
  * _REMOVE                     +       +       +       +       +

+ * _SWAP                       -       +       +       +       -

  *
  */
 #ifdef QUEUE_MACRO_DEBUG
  *
  */
 #ifdef QUEUE_MACRO_DEBUG


@@ -170,21 +182,50 @@ struct qm_trace {
 #define        TRASHIT(x)
 #endif /* QUEUE_MACRO_DEBUG */
 
 #define        TRASHIT(x)
 #endif /* QUEUE_MACRO_DEBUG */
 

+/*
+ * Horrible macros to enable use of code that was meant to be C-specific
+ *   (and which push struct onto type) in C++; without these, C++ code
+ *   that uses these macros in the context of a class will blow up
+ *   due to "struct" being preprended to "type" by the macros, causing
+ *   inconsistent use of tags.
+ *
+ * This approach is necessary because these are macros; we have to use
+ *   these on a per-macro basis (because the queues are implemented as
+ *   macros, disabling this warning in the scope of the header file is
+ *   insufficient), whuch means we can't use #pragma, and have to use
+ *   _Pragma.  We only need to use these for the queue macros that
+ *   prepend "struct" to "type" and will cause C++ to blow up.
+ */
+#if defined(__clang__) && defined(__cplusplus)
+#define __MISMATCH_TAGS_PUSH                                           \
+       _Pragma("clang diagnostic push")                                \
+       _Pragma("clang diagnostic ignored \"-Wmismatched-tags\"")
+#define __MISMATCH_TAGS_POP                                            \
+       _Pragma("clang diagnostic pop")
+#else
+#define __MISMATCH_TAGS_PUSH
+#define __MISMATCH_TAGS_POP
+#endif
+

 /*
  * Singly-linked List declarations.
  */
 #define        SLIST_HEAD(name, type)                                          \
 /*
  * Singly-linked List declarations.
  */
 #define        SLIST_HEAD(name, type)                                          \

+__MISMATCH_TAGS_PUSH                                                   \

 struct name {                                                          \
        struct type *slh_first; /* first element */                     \
 struct name {                                                          \
        struct type *slh_first; /* first element */                     \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 #define        SLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }
 
 #define        SLIST_ENTRY(type)                                               \
 
 #define        SLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }
 
 #define        SLIST_ENTRY(type)                                               \

+__MISMATCH_TAGS_PUSH                                                   \

 struct {                                                               \
        struct type *sle_next;  /* next element */                      \
 struct {                                                               \
        struct type *sle_next;  /* next element */                      \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 /*
  * Singly-linked List functions.
 
 /*
  * Singly-linked List functions.


@@ -224,7 +265,9 @@ struct {                                                            \
 
 #define        SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 
 
 #define        SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 

-#define        SLIST_REMOVE(head, elm, type, field) do {                       \
+#define        SLIST_REMOVE(head, elm, type, field)                            \
+__MISMATCH_TAGS_PUSH                                                   \
+do {                                                                   \

        if (SLIST_FIRST((head)) == (elm)) {                             \
                SLIST_REMOVE_HEAD((head), field);                       \
        }                                                               \
        if (SLIST_FIRST((head)) == (elm)) {                             \
                SLIST_REMOVE_HEAD((head), field);                       \
        }                                                               \


@@ -232,10 +275,15 @@ struct {                                                          \
                struct type *curelm = SLIST_FIRST((head));              \
                while (SLIST_NEXT(curelm, field) != (elm))              \
                        curelm = SLIST_NEXT(curelm, field);             \
                struct type *curelm = SLIST_FIRST((head));              \
                while (SLIST_NEXT(curelm, field) != (elm))              \
                        curelm = SLIST_NEXT(curelm, field);             \

-               SLIST_NEXT(curelm, field) =                             \
-                   SLIST_NEXT(SLIST_NEXT(curelm, field), field);       \
+               SLIST_REMOVE_AFTER(curelm, field);                      \

        }                                                               \
        TRASHIT((elm)->field.sle_next);                                 \
        }                                                               \
        TRASHIT((elm)->field.sle_next);                                 \

+} while (0)                                                            \
+__MISMATCH_TAGS_POP
+
+#define SLIST_REMOVE_AFTER(elm, field) do {                            \
+       SLIST_NEXT(elm, field) =                                        \
+           SLIST_NEXT(SLIST_NEXT(elm, field), field);                  \

 } while (0)
 
 #define        SLIST_REMOVE_HEAD(head, field) do {                             \
 } while (0)
 
 #define        SLIST_REMOVE_HEAD(head, field) do {                             \


@@ -246,18 +294,22 @@ struct {                                                          \
  * Singly-linked Tail queue declarations.
  */
 #define        STAILQ_HEAD(name, type)                                         \
  * Singly-linked Tail queue declarations.
  */
 #define        STAILQ_HEAD(name, type)                                         \

+__MISMATCH_TAGS_PUSH                                                   \

 struct name {                                                          \
        struct type *stqh_first;/* first element */                     \
        struct type **stqh_last;/* addr of last next element */         \
 struct name {                                                          \
        struct type *stqh_first;/* first element */                     \
        struct type **stqh_last;/* addr of last next element */         \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 #define        STAILQ_HEAD_INITIALIZER(head)                                   \
        { NULL, &(head).stqh_first }
 
 #define        STAILQ_ENTRY(type)                                              \
 
 #define        STAILQ_HEAD_INITIALIZER(head)                                   \
        { NULL, &(head).stqh_first }
 
 #define        STAILQ_ENTRY(type)                                              \

+__MISMATCH_TAGS_PUSH                                                   \

 struct {                                                               \
        struct type *stqe_next; /* next element */                      \
 struct {                                                               \
        struct type *stqe_next; /* next element */                      \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 /*
  * Singly-linked Tail queue functions.
 
 /*
  * Singly-linked Tail queue functions.


@@ -309,14 +361,18 @@ struct {                                                          \
 } while (0)
 
 #define        STAILQ_LAST(head, type, field)                                  \
 } while (0)
 
 #define        STAILQ_LAST(head, type, field)                                  \

+__MISMATCH_TAGS_PUSH                                                   \

        (STAILQ_EMPTY((head)) ?                                         \
                NULL :                                                  \
                ((struct type *)(void *)                                \
        (STAILQ_EMPTY((head)) ?                                         \
                NULL :                                                  \
                ((struct type *)(void *)                                \

-               ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
+               ((char *)((head)->stqh_last) - __offsetof(struct type, field))))\
+__MISMATCH_TAGS_POP

 
 #define        STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 
 
 #define        STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 

-#define        STAILQ_REMOVE(head, elm, type, field) do {                      \
+#define        STAILQ_REMOVE(head, elm, type, field)                           \
+__MISMATCH_TAGS_PUSH                                                   \
+do {                                                                   \

        if (STAILQ_FIRST((head)) == (elm)) {                            \
                STAILQ_REMOVE_HEAD((head), field);                      \
        }                                                               \
        if (STAILQ_FIRST((head)) == (elm)) {                            \
                STAILQ_REMOVE_HEAD((head), field);                      \
        }                                                               \


@@ -324,12 +380,11 @@ struct {                                                          \
                struct type *curelm = STAILQ_FIRST((head));             \
                while (STAILQ_NEXT(curelm, field) != (elm))             \
                        curelm = STAILQ_NEXT(curelm, field);            \
                struct type *curelm = STAILQ_FIRST((head));             \
                while (STAILQ_NEXT(curelm, field) != (elm))             \
                        curelm = STAILQ_NEXT(curelm, field);            \

-               if ((STAILQ_NEXT(curelm, field) =                       \
-                    STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
-                       (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
+               STAILQ_REMOVE_AFTER(head, curelm, field);               \

        }                                                               \
        TRASHIT((elm)->field.stqe_next);                                \
        }                                                               \
        TRASHIT((elm)->field.stqe_next);                                \

-} while (0)
+} while (0)                                                            \
+__MISMATCH_TAGS_POP

 
 #define        STAILQ_REMOVE_HEAD(head, field) do {                            \
        if ((STAILQ_FIRST((head)) =                                     \
 
 #define        STAILQ_REMOVE_HEAD(head, field) do {                            \
        if ((STAILQ_FIRST((head)) =                                     \


@@ -337,56 +392,85 @@ struct {                                                          \
                (head)->stqh_last = &STAILQ_FIRST((head));              \
 } while (0)
 
                (head)->stqh_last = &STAILQ_FIRST((head));              \
 } while (0)
 

-#define        STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {                 \
-       if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
-               (head)->stqh_last = &STAILQ_FIRST((head));              \
+#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {                 \
+       if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \
+               (head)->stqh_last = &STAILQ_FIRST((head));              \

 } while (0)
 
 } while (0)
 

+#define STAILQ_REMOVE_AFTER(head, elm, field) do {                     \
+       if ((STAILQ_NEXT(elm, field) =                                  \
+            STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)      \
+               (head)->stqh_last = &STAILQ_NEXT((elm), field);         \
+} while (0)
+
+#define STAILQ_SWAP(head1, head2, type)                                        \
+__MISMATCH_TAGS_PUSH                                                   \
+do {                                                                   \
+       struct type *swap_first = STAILQ_FIRST(head1);                  \
+       struct type **swap_last = (head1)->stqh_last;                   \
+       STAILQ_FIRST(head1) = STAILQ_FIRST(head2);                      \
+       (head1)->stqh_last = (head2)->stqh_last;                        \
+       STAILQ_FIRST(head2) = swap_first;                               \
+       (head2)->stqh_last = swap_last;                                 \
+       if (STAILQ_EMPTY(head1))                                        \
+               (head1)->stqh_last = &STAILQ_FIRST(head1);              \
+       if (STAILQ_EMPTY(head2))                                        \
+               (head2)->stqh_last = &STAILQ_FIRST(head2);              \
+} while (0)                                                            \
+__MISMATCH_TAGS_POP
+
+

 /*
  * List declarations.
  */
 #define        LIST_HEAD(name, type)                                           \
 /*
  * List declarations.
  */
 #define        LIST_HEAD(name, type)                                           \

+__MISMATCH_TAGS_PUSH                                                   \

 struct name {                                                          \
        struct type *lh_first;  /* first element */                     \
 struct name {                                                          \
        struct type *lh_first;  /* first element */                     \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 #define        LIST_HEAD_INITIALIZER(head)                                     \
        { NULL }
 
 #define        LIST_ENTRY(type)                                                \
 
 #define        LIST_HEAD_INITIALIZER(head)                                     \
        { NULL }
 
 #define        LIST_ENTRY(type)                                                \

+__MISMATCH_TAGS_PUSH                                                   \

 struct {                                                               \
        struct type *le_next;   /* next element */                      \
        struct type **le_prev;  /* address of previous next element */  \
 struct {                                                               \
        struct type *le_next;   /* next element */                      \
        struct type **le_prev;  /* address of previous next element */  \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 /*
  * List functions.
  */
 
 
 /*
  * List functions.
  */
 

-#if (defined(_KERNEL) && defined(INVARIANTS)) || defined(QUEUE_MACRO_DEBUG)
-#define        QMD_LIST_CHECK_HEAD(head, field) do {                           \
-       if (LIST_FIRST((head)) != NULL &&                               \
-           LIST_FIRST((head))->field.le_prev !=                        \
-            &LIST_FIRST((head)))                                       \
-               panic("Bad list head %p first->prev != head", (head));  \
+#ifdef KERNEL_PRIVATE
+#define        LIST_CHECK_HEAD(head, field) do {                               \
+       if (__improbable(                                               \
+             LIST_FIRST((head)) != NULL &&                             \
+             LIST_FIRST((head))->field.le_prev !=                      \
+             &LIST_FIRST((head))))                                     \
+                    panic("Bad list head %p first->prev != head", (head));     \

 } while (0)
 
 } while (0)
 

-#define        QMD_LIST_CHECK_NEXT(elm, field) do {                            \
-       if (LIST_NEXT((elm), field) != NULL &&                          \
-           LIST_NEXT((elm), field)->field.le_prev !=                   \
-            &((elm)->field.le_next))                                   \
-               panic("Bad link elm %p next->prev != elm", (elm));      \
+#define        LIST_CHECK_NEXT(elm, field) do {                                \
+       if (__improbable(                                               \
+             LIST_NEXT((elm), field) != NULL &&                        \
+             LIST_NEXT((elm), field)->field.le_prev !=                 \
+             &((elm)->field.le_next)))                                 \
+                    panic("Bad link elm %p next->prev != elm", (elm)); \

 } while (0)
 
 } while (0)
 

-#define        QMD_LIST_CHECK_PREV(elm, field) do {                            \
-       if (*(elm)->field.le_prev != (elm))                             \
+#define        LIST_CHECK_PREV(elm, field) do {                                \
+       if (__improbable(*(elm)->field.le_prev != (elm)))               \

                panic("Bad link elm %p prev->next != elm", (elm));      \
 } while (0)
 #else
                panic("Bad link elm %p prev->next != elm", (elm));      \
 } while (0)
 #else

-#define        QMD_LIST_CHECK_HEAD(head, field)
-#define        QMD_LIST_CHECK_NEXT(elm, field)
-#define        QMD_LIST_CHECK_PREV(elm, field)
-#endif /* (_KERNEL && INVARIANTS) || QUEUE_MACRO_DEBUG */
+#define        LIST_CHECK_HEAD(head, field)
+#define        LIST_CHECK_NEXT(elm, field)
+#define        LIST_CHECK_PREV(elm, field)
+#endif /* KERNEL_PRIVATE */

 
 #define        LIST_EMPTY(head)        ((head)->lh_first == NULL)
 
 
 #define        LIST_EMPTY(head)        ((head)->lh_first == NULL)
 


@@ -407,7 +491,7 @@ struct {                                                            \
 } while (0)
 
 #define        LIST_INSERT_AFTER(listelm, elm, field) do {                     \
 } while (0)
 
 #define        LIST_INSERT_AFTER(listelm, elm, field) do {                     \

-       QMD_LIST_CHECK_NEXT(listelm, field);                            \
+       LIST_CHECK_NEXT(listelm, field);                                \

        if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
                LIST_NEXT((listelm), field)->field.le_prev =            \
                    &LIST_NEXT((elm), field);                           \
        if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
                LIST_NEXT((listelm), field)->field.le_prev =            \
                    &LIST_NEXT((elm), field);                           \


@@ -416,7 +500,7 @@ struct {                                                            \
 } while (0)
 
 #define        LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
 } while (0)
 
 #define        LIST_INSERT_BEFORE(listelm, elm, field) do {                    \

-       QMD_LIST_CHECK_PREV(listelm, field);                            \
+       LIST_CHECK_PREV(listelm, field);                                \

        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        LIST_NEXT((elm), field) = (listelm);                            \
        *(listelm)->field.le_prev = (elm);                              \
        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        LIST_NEXT((elm), field) = (listelm);                            \
        *(listelm)->field.le_prev = (elm);                              \


@@ -424,7 +508,7 @@ struct {                                                            \
 } while (0)
 
 #define        LIST_INSERT_HEAD(head, elm, field) do {                         \
 } while (0)
 
 #define        LIST_INSERT_HEAD(head, elm, field) do {                         \

-       QMD_LIST_CHECK_HEAD((head), field);                             \
+       LIST_CHECK_HEAD((head), field);                         \

        if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
                LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
        LIST_FIRST((head)) = (elm);                                     \
        if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)     \
                LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
        LIST_FIRST((head)) = (elm);                                     \


@@ -434,8 +518,8 @@ struct {                                                            \
 #define        LIST_NEXT(elm, field)   ((elm)->field.le_next)
 
 #define        LIST_REMOVE(elm, field) do {                                    \
 #define        LIST_NEXT(elm, field)   ((elm)->field.le_next)
 
 #define        LIST_REMOVE(elm, field) do {                                    \

-       QMD_LIST_CHECK_NEXT(elm, field);                                \
-       QMD_LIST_CHECK_PREV(elm, field);                                \
+       LIST_CHECK_NEXT(elm, field);                            \
+       LIST_CHECK_PREV(elm, field);                            \

        if (LIST_NEXT((elm), field) != NULL)                            \
                LIST_NEXT((elm), field)->field.le_prev =                \
                    (elm)->field.le_prev;                               \
        if (LIST_NEXT((elm), field) != NULL)                            \
                LIST_NEXT((elm), field)->field.le_prev =                \
                    (elm)->field.le_prev;                               \


@@ -444,29 +528,73 @@ struct {                                                          \
        TRASHIT((elm)->field.le_prev);                                  \
 } while (0)
 
        TRASHIT((elm)->field.le_prev);                                  \
 } while (0)
 

+#define LIST_SWAP(head1, head2, type, field)                           \
+__MISMATCH_TAGS_PUSH                                                   \
+do {                                                                   \
+       struct type *swap_tmp = LIST_FIRST((head1));                    \
+       LIST_FIRST((head1)) = LIST_FIRST((head2));                      \
+       LIST_FIRST((head2)) = swap_tmp;                                 \
+       if ((swap_tmp = LIST_FIRST((head1))) != NULL)                   \
+               swap_tmp->field.le_prev = &LIST_FIRST((head1));         \
+       if ((swap_tmp = LIST_FIRST((head2))) != NULL)                   \
+               swap_tmp->field.le_prev = &LIST_FIRST((head2));         \
+} while (0)                                                            \
+__MISMATCH_TAGS_POP
+

 /*
  * Tail queue declarations.
  */
 #define        TAILQ_HEAD(name, type)                                          \
 /*
  * Tail queue declarations.
  */
 #define        TAILQ_HEAD(name, type)                                          \

+__MISMATCH_TAGS_PUSH                                                   \

 struct name {                                                          \
        struct type *tqh_first; /* first element */                     \
        struct type **tqh_last; /* addr of last next element */         \
        TRACEBUF                                                        \
 struct name {                                                          \
        struct type *tqh_first; /* first element */                     \
        struct type **tqh_last; /* addr of last next element */         \
        TRACEBUF                                                        \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 #define        TAILQ_HEAD_INITIALIZER(head)                                    \
        { NULL, &(head).tqh_first }
 
 #define        TAILQ_ENTRY(type)                                               \
 
 #define        TAILQ_HEAD_INITIALIZER(head)                                    \
        { NULL, &(head).tqh_first }
 
 #define        TAILQ_ENTRY(type)                                               \

+__MISMATCH_TAGS_PUSH                                                   \

 struct {                                                               \
        struct type *tqe_next;  /* next element */                      \
        struct type **tqe_prev; /* address of previous next element */  \
        TRACEBUF                                                        \
 struct {                                                               \
        struct type *tqe_next;  /* next element */                      \
        struct type **tqe_prev; /* address of previous next element */  \
        TRACEBUF                                                        \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 /*
  * Tail queue functions.
  */
 
 /*
  * Tail queue functions.
  */

+#ifdef KERNEL_PRIVATE
+#define TAILQ_CHECK_HEAD(head, field) do {                             \
+       if (__improbable(                                               \
+             TAILQ_FIRST((head)) != NULL &&                            \
+             TAILQ_FIRST((head))->field.tqe_prev !=                    \
+             &TAILQ_FIRST((head))))                                    \
+                    panic("Bad tailq head %p first->prev != head", (head));    \
+} while (0)
+
+#define TAILQ_CHECK_NEXT(elm, field) do {                              \
+       if (__improbable(                                               \
+             TAILQ_NEXT((elm), field) != NULL &&                       \
+             TAILQ_NEXT((elm), field)->field.tqe_prev !=               \
+             &((elm)->field.tqe_next)))                                \
+                    panic("Bad tailq elm %p next->prev != elm", (elm));        \
+} while(0)
+
+#define        TAILQ_CHECK_PREV(elm, field) do {                               \
+       if (__improbable(*(elm)->field.tqe_prev != (elm)))              \
+             panic("Bad tailq elm %p prev->next != elm", (elm));       \
+} while(0)
+#else
+#define        TAILQ_CHECK_HEAD(head, field)
+#define        TAILQ_CHECK_NEXT(elm, field)
+#define        TAILQ_CHECK_PREV(elm, field)
+#endif /* KERNEL_PRIVATE */
+

 #define        TAILQ_CONCAT(head1, head2, field) do {                          \
        if (!TAILQ_EMPTY(head2)) {                                      \
                *(head1)->tqh_last = (head2)->tqh_first;                \
 #define        TAILQ_CONCAT(head1, head2, field) do {                          \
        if (!TAILQ_EMPTY(head2)) {                                      \
                *(head1)->tqh_last = (head2)->tqh_first;                \


@@ -508,7 +636,9 @@ struct {                                                            \
        QMD_TRACE_HEAD(head);                                           \
 } while (0)
 
        QMD_TRACE_HEAD(head);                                           \
 } while (0)
 

+

 #define        TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
 #define        TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \

+        TAILQ_CHECK_NEXT(listelm, field);                              \

        if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    &TAILQ_NEXT((elm), field);                          \
        if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    &TAILQ_NEXT((elm), field);                          \


@@ -523,6 +653,7 @@ struct {                                                            \
 } while (0)
 
 #define        TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
 } while (0)
 
 #define        TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \

+        TAILQ_CHECK_PREV(listelm, field);                              \

        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
        TAILQ_NEXT((elm), field) = (listelm);                           \
        *(listelm)->field.tqe_prev = (elm);                             \
        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
        TAILQ_NEXT((elm), field) = (listelm);                           \
        *(listelm)->field.tqe_prev = (elm);                             \


@@ -532,6 +663,7 @@ struct {                                                            \
 } while (0)
 
 #define        TAILQ_INSERT_HEAD(head, elm, field) do {                        \
 } while (0)
 
 #define        TAILQ_INSERT_HEAD(head, elm, field) do {                        \

+        TAILQ_CHECK_HEAD(head, field);                                 \

        if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
                TAILQ_FIRST((head))->field.tqe_prev =                   \
                    &TAILQ_NEXT((elm), field);                          \
        if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)   \
                TAILQ_FIRST((head))->field.tqe_prev =                   \
                    &TAILQ_NEXT((elm), field);                          \


@@ -553,14 +685,20 @@ struct {                                                          \
 } while (0)
 
 #define        TAILQ_LAST(head, headname)                                      \
 } while (0)
 
 #define        TAILQ_LAST(head, headname)                                      \

-       (*(((struct headname *)((head)->tqh_last))->tqh_last))
+__MISMATCH_TAGS_PUSH                                                   \
+       (*(((struct headname *)((head)->tqh_last))->tqh_last))          \
+__MISMATCH_TAGS_POP

 
 #define        TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 
 #define        TAILQ_PREV(elm, headname, field)                                \
 
 #define        TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 
 #define        TAILQ_PREV(elm, headname, field)                                \

-       (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+__MISMATCH_TAGS_PUSH                                                   \
+       (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))     \
+__MISMATCH_TAGS_POP

 
 #define        TAILQ_REMOVE(head, elm, field) do {                             \
 
 #define        TAILQ_REMOVE(head, elm, field) do {                             \

+        TAILQ_CHECK_NEXT(elm, field);                                  \
+        TAILQ_CHECK_PREV(elm, field);                                  \

        if ((TAILQ_NEXT((elm), field)) != NULL)                         \
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    (elm)->field.tqe_prev;                              \
        if ((TAILQ_NEXT((elm), field)) != NULL)                         \
                TAILQ_NEXT((elm), field)->field.tqe_prev =              \
                    (elm)->field.tqe_prev;                              \


@@ -574,24 +712,76 @@ struct {                                                          \
        QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 
        QMD_TRACE_ELEM(&(elm)->field);                                  \
 } while (0)
 

+/*
+ * Why did they switch to spaces for this one macro?
+ */
+#define TAILQ_SWAP(head1, head2, type, field)                           \
+__MISMATCH_TAGS_PUSH                                                    \
+do {                                                                    \
+       struct type *swap_first = (head1)->tqh_first;                   \
+       struct type **swap_last = (head1)->tqh_last;                    \
+       (head1)->tqh_first = (head2)->tqh_first;                        \
+       (head1)->tqh_last = (head2)->tqh_last;                          \
+       (head2)->tqh_first = swap_first;                                \
+       (head2)->tqh_last = swap_last;                                  \
+       if ((swap_first = (head1)->tqh_first) != NULL)                  \
+               swap_first->field.tqe_prev = &(head1)->tqh_first;       \
+       else                                                            \
+               (head1)->tqh_last = &(head1)->tqh_first;                \
+       if ((swap_first = (head2)->tqh_first) != NULL)                  \
+               swap_first->field.tqe_prev = &(head2)->tqh_first;       \
+       else                                                            \
+               (head2)->tqh_last = &(head2)->tqh_first;                \
+} while (0)                                                             \
+__MISMATCH_TAGS_POP
+

 /*
  * Circular queue definitions.
  */
 #define CIRCLEQ_HEAD(name, type)                                       \
 /*
  * Circular queue definitions.
  */
 #define CIRCLEQ_HEAD(name, type)                                       \

+__MISMATCH_TAGS_PUSH                                                   \

 struct name {                                                          \
        struct type *cqh_first;         /* first element */             \
        struct type *cqh_last;          /* last element */              \
 struct name {                                                          \
        struct type *cqh_first;         /* first element */             \
        struct type *cqh_last;          /* last element */              \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 #define CIRCLEQ_ENTRY(type)                                            \
 
 #define CIRCLEQ_ENTRY(type)                                            \

+__MISMATCH_TAGS_PUSH                                                   \

 struct {                                                               \
        struct type *cqe_next;          /* next element */              \
        struct type *cqe_prev;          /* previous element */          \
 struct {                                                               \
        struct type *cqe_next;          /* next element */              \
        struct type *cqe_prev;          /* previous element */          \

-}
+}                                                                      \
+__MISMATCH_TAGS_POP

 
 /*
  * Circular queue functions.
  */
 
 /*
  * Circular queue functions.
  */

+#ifdef KERNEL_PRIVATE
+#define        CIRCLEQ_CHECK_HEAD(head, field) do {                            \
+       if (__improbable(                                               \
+             CIRCLEQ_FIRST((head)) != ((void*)(head)) &&               \
+             CIRCLEQ_FIRST((head))->field.cqe_prev != ((void*)(head))))\
+                    panic("Bad circleq head %p first->prev != head", (head));  \
+} while(0)
+#define        CIRCLEQ_CHECK_NEXT(head, elm, field) do {                       \
+       if (__improbable(                                               \
+             CIRCLEQ_NEXT((elm), field) != ((void*)(head)) &&          \
+             CIRCLEQ_NEXT((elm), field)->field.cqe_prev != (elm)))     \
+                    panic("Bad circleq elm %p next->prev != elm", (elm));      \
+} while(0)
+#define        CIRCLEQ_CHECK_PREV(head, elm, field) do {                       \
+       if (__improbable(                                               \
+             CIRCLEQ_PREV((elm), field) != ((void*)(head)) &&          \
+             CIRCLEQ_PREV((elm), field)->field.cqe_next != (elm)))     \
+                    panic("Bad circleq elm %p prev->next != elm", (elm));      \
+} while(0)
+#else
+#define        CIRCLEQ_CHECK_HEAD(head, field)
+#define        CIRCLEQ_CHECK_NEXT(head, elm, field)
+#define        CIRCLEQ_CHECK_PREV(head, elm, field)
+#endif /* KERNEL_PRIVATE */
+

 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
 
 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
 
 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)


@@ -607,6 +797,7 @@ struct {                                                            \
 } while (0)
 
 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
 } while (0)
 
 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \

+        CIRCLEQ_CHECK_NEXT(head, listelm, field);                      \

        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
        (elm)->field.cqe_prev = (listelm);                              \
        if ((listelm)->field.cqe_next == (void *)(head))                \
        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
        (elm)->field.cqe_prev = (listelm);                              \
        if ((listelm)->field.cqe_next == (void *)(head))                \


@@ -617,6 +808,7 @@ struct {                                                            \
 } while (0)
 
 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {          \
 } while (0)
 
 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {          \

+        CIRCLEQ_CHECK_PREV(head, listelm, field);                      \

        (elm)->field.cqe_next = (listelm);                              \
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
        if ((listelm)->field.cqe_prev == (void *)(head))                \
        (elm)->field.cqe_next = (listelm);                              \
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
        if ((listelm)->field.cqe_prev == (void *)(head))                \


@@ -627,6 +819,7 @@ struct {                                                            \
 } while (0)
 
 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                     \
 } while (0)
 
 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                     \

+        CIRCLEQ_CHECK_HEAD(head, field);                               \

        (elm)->field.cqe_next = (head)->cqh_first;                      \
        (elm)->field.cqe_prev = (void *)(head);                         \
        if ((head)->cqh_last == (void *)(head))                         \
        (elm)->field.cqe_next = (head)->cqh_first;                      \
        (elm)->field.cqe_prev = (void *)(head);                         \
        if ((head)->cqh_last == (void *)(head))                         \


@@ -653,6 +846,8 @@ struct {                                                            \
 #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
 
 #define        CIRCLEQ_REMOVE(head, elm, field) do {                           \
 #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
 
 #define        CIRCLEQ_REMOVE(head, elm, field) do {                           \

+        CIRCLEQ_CHECK_NEXT(head, elm, field);                          \
+        CIRCLEQ_CHECK_PREV(head, elm, field);                          \

        if ((elm)->field.cqe_next == (void *)(head))                    \
                (head)->cqh_last = (elm)->field.cqe_prev;               \
        else                                                            \
        if ((elm)->field.cqe_next == (void *)(head))                    \
                (head)->cqh_last = (elm)->field.cqe_prev;               \
        else                                                            \


@@ -680,12 +875,37 @@ struct quehead {
 };
 
 #ifdef __GNUC__
 };
 
 #ifdef __GNUC__

+#ifdef KERNEL_PRIVATE
+static __inline void
+chkquenext(void *a)
+{
+       struct quehead *element = (struct quehead *)a;
+       if (__improbable(element->qh_link != NULL &&
+                           element->qh_link->qh_rlink != element)) {
+             panic("Bad que elm %p next->prev != elm", a);
+       }
+}
+
+static __inline void
+chkqueprev(void *a)
+{
+       struct quehead *element = (struct quehead *)a;
+       if (__improbable(element->qh_rlink != NULL &&
+                           element->qh_rlink->qh_link != element)) {
+             panic("Bad que elm %p prev->next != elm", a);
+       }
+}
+#else /* !KERNEL_PRIVATE */
+#define chkquenext(a)
+#define chkqueprev(a)
+#endif /* KERNEL_PRIVATE */

 
 static __inline void
 insque(void *a, void *b)
 {
        struct quehead *element = (struct quehead *)a,
                 *head = (struct quehead *)b;
 
 static __inline void
 insque(void *a, void *b)
 {
        struct quehead *element = (struct quehead *)a,
                 *head = (struct quehead *)b;

+       chkquenext(head);

 
        element->qh_link = head->qh_link;
        element->qh_rlink = head;
 
        element->qh_link = head->qh_link;
        element->qh_rlink = head;


@@ -697,6 +917,8 @@ static __inline void
 remque(void *a)
 {
        struct quehead *element = (struct quehead *)a;
 remque(void *a)
 {
        struct quehead *element = (struct quehead *)a;

+       chkquenext(element);
+       chkqueprev(element);

 
        element->qh_link->qh_rlink = element->qh_rlink;
        element->qh_rlink->qh_link = element->qh_link;
 
        element->qh_link->qh_rlink = element->qh_rlink;
        element->qh_rlink->qh_link = element->qh_link;


@@ -710,7 +932,7 @@ void        remque(void *a);
 
 #endif /* __GNUC__ */
 
 
 #endif /* __GNUC__ */
 

-#endif
+#endif /* NOTFB31 */

 #endif /* _KERNEL */
 
 #endif /* !_SYS_QUEUE_H_ */
 #endif /* _KERNEL */
 
 #endif /* !_SYS_QUEUE_H_ */