tech-userlevel archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work



matthew green <mrg%eterna.com.au@localhost> wrote:
 |while preparing to update to GCC 4.8 i discovered that our sys/queue.h
 |CIRCLEQ macros violate C aliasing rules, ultimately leading to the
 |compiler eliding comparisons it declared as always false.

I am far away from penetrating these C sequence point and aliasing
semantics, and face it in an unacademic way on a case-by-case base.
But couldn't this particular problem be truly solved by enwrapping
all of it in unions, so that the tests end up as tests against
char* or integer:

  -#define      CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void 
*)(head))
  +#define      CIRCLEQ_EMPTY(head)             ((head)->_d.cqh_first._i == 
(uintptr_t)&(head)->_x[0])

A blind dash off with _INIT(), _INSERT_HEAD(), _FOREACH() and
_EMPTY().  Maybe the inner unions are redundant, so; i have never
used queue.3 and thus didn't know what i really need, but.
Even if, it'd need stdint.h for uintptr_t (or stddef.h for
ptrdiff_t).

In fact i'm not really convinced from
  +     for ((var) = ((head)->_d.cqh_first._p);                         \
  +             (uintptr_t)(var) != (uintptr_t)&(head)->_x[0];          \
  +             (var) = ((var)->field._d.cqe_next._p))
at the moment.  (hmm.)

  --- queue.h.orig      2013-11-20 20:43:01.000000000 +0100
  +++ queue.h   2013-11-20 20:55:33.000000000 +0100
  @@ -640,27 +640,46 @@ struct {                                                
                \
   #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field)
   #endif
   
  +#include <stdint.h>
   #define      CIRCLEQ_HEAD(name, type)                                        
\
  -struct name {                                                                
\
  -     struct type *cqh_first;         /* first element */             \
  -     struct type *cqh_last;          /* last element */              \
  +union name {                                                         \
  +     struct {                                                        \
  +             union {                                                 \
  +                     uintptr_t       _i;                             \
  +                     struct type     *_p;    /* first element */     \
  +             }               cqh_first;                              \
  +             union {                                                 \
  +                     uintptr_t       _i;                             \
  +                     struct type     *_p;    /* first element */     \
  +             }               cqh_last;       /* last element */      \
  +     }       _d;                                                     \
  +     char    _x[2 * sizeof(uintptr_t)];                              \
   }
   
   #define      CIRCLEQ_HEAD_INITIALIZER(head)                                  
\
  -     { (void *)&head, (void *)&head }
  +     { {{(uintptr_t)&head}, {(uintptr_t)&head}} }
   
   #define      CIRCLEQ_ENTRY(type)                                             
\
  -struct {                                                             \
  -     struct type *cqe_next;          /* next element */              \
  -     struct type *cqe_prev;          /* previous element */          \
  +union {                                                                      
\
  +     struct {                                                        \
  +             union {                                                 \
  +                     uintptr_t       _i;                             \
  +                     struct type     *_p;                            \
  +             }       cqe_next;               /* next element */      \
  +             union {                                                 \
  +                     uintptr_t       _i;                             \
  +                     struct type     *_p;                            \
  +             }       cqe_prev;               /* previous element */  \
  +     }       _d;                                                     \
  +     char    _x[2 * sizeof(uintptr_t)];                              \
   }
   
   /*
    * Circular queue functions.
    */
   #define      CIRCLEQ_INIT(head) do {                                         
\
  -     (head)->cqh_first = (void *)(head);                             \
  -     (head)->cqh_last = (void *)(head);                              \
  +     (head)->_d.cqh_first._i = (uintptr_t)(head);                    \
  +     (head)->_d.cqh_last._i = (uintptr_t)(head);                     \
   } while (/*CONSTCOND*/0)
   
   #define      CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            
\
  @@ -689,13 +708,13 @@ struct {                                                
                \
   
   #define      CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      
\
    QUEUEDEBUG_CIRCLEQ_HEAD((head), field)                              \
  -     (elm)->field.cqe_next = (head)->cqh_first;                      \
  -     (elm)->field.cqe_prev = (void *)(head);                         \
  -     if ((head)->cqh_last == (void *)(head))                         \
  -             (head)->cqh_last = (elm);                               \
  +     (elm)->field._d.cqe_next._i = (head)->_d.cqh_first._i;          \
  +     (elm)->field._d.cqe_prev._i = (uintptr_t)(head);                \
  +     if ((head)->_d.cqh_last._i == (uintptr_t)(head))                \
  +             (head)->_d.cqh_last._p = (elm);                         \
    else                                                                \
  -             (head)->cqh_first->field.cqe_prev = (elm);              \
  -     (head)->cqh_first = (elm);                                      \
  +             (head)->_d.cqh_first._p->field._d.cqe_prev._p = (elm);  \
  +     (head)->_d.cqh_first._p = (elm);                                \
   } while (/*CONSTCOND*/0)
   
   #define      CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      
\
  @@ -726,9 +745,9 @@ struct {                                                  
        \
   } while (/*CONSTCOND*/0)
   
   #define      CIRCLEQ_FOREACH(var, head, field)                               
\
  -     for ((var) = ((head)->cqh_first);                               \
  -             (var) != (const void *)(head);                          \
  -             (var) = ((var)->field.cqe_next))
  +     for ((var) = ((head)->_d.cqh_first._p);                         \
  +             (uintptr_t)(var) != (uintptr_t)&(head)->_x[0];          \
  +             (var) = ((var)->field._d.cqe_next._p))
   
   #define      CIRCLEQ_FOREACH_REVERSE(var, head, field)                       
\
    for ((var) = ((head)->cqh_last);                            \
  @@ -738,7 +757,7 @@ struct {                                                  
        \
   /*
    * Circular queue access methods.
    */
  -#define      CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void 
*)(head))
  +#define      CIRCLEQ_EMPTY(head)             ((head)->_d.cqh_first._i == 
(uintptr_t)&(head)->_x[0])
   #define      CIRCLEQ_FIRST(head)             ((head)->cqh_first)
   #define      CIRCLEQ_LAST(head)              ((head)->cqh_last)
   #define      CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)

--- Begin Message ---
hi folks.


while preparing to update to GCC 4.8 i discovered that our sys/queue.h
CIRCLEQ macros violate C aliasing rules, ultimately leading to the
compiler eliding comparisons it declared as always false.

unfortunately, changing these macros to be strictly C requires changing
the ABI of them, and while we are going to consider such a change, in
the interest of getting things working we present the following hack.
it was inspired by David Holland, and we considered placing it in
sys/cdefs.h for other consumers, but as queue.h currently only relies
on the presence of "NULL" combined with the need for "<sys/queue.h>"
to work correctly for the tools build (which may be on non-netbsd
platforms.)

the visible problems are that the libc DB routines often fail, and
that nvi locks up all the time.

i'm going to commit this soon, but if anyone has more useful hacks or
real fixes, please let me/these lists know and we'll consider them.

i'm also going to purge the tree of several copies of sys/queue.h
present in 3rd party software as a follow change.

thanks to dholland, apb, joerg, martin, matt, and skrll for this
least-worst-so-far solution.


.mrg.


Index: queue.h
===================================================================
RCS file: /cvsroot/src/sys/sys/queue.h,v
retrieving revision 1.55
diff -p -r1.55 queue.h
--- queue.h     17 Jul 2013 15:50:59 -0000      1.55
+++ queue.h     20 Nov 2013 09:33:42 -0000
@@ -602,18 +602,41 @@
 /*
  * Circular queue definitions.
  */
+
+/*
+ * __launder_type():  We use this ugly hack to work around the the compiler
+ * noticing that two types may not alias each other and elide tests in code.
+ * We hit this in the CIRCLEQ macros when comparing 'struct name *' and
+ * 'struct type *' (see CIRCLEQ_HEAD()).  Modern compilers (such as GCC
+ * 4.8) declare these comparisons as always false, causing the code to
+ * not run as designed.
+ *
+ * This hack is only to be used for comparisons and thus can be fully const.
+ * Do not use for assignment.
+ *
+ * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix
+ * this by changing the 
+ */
+static inline const void * __launder_type(const void *);
+static inline const void *
+__launder_type(const void *__x)
+{
+       __asm __volatile("" : "+r" (__x));
+       return __x;
+}
+
 #if defined(_KERNEL) && defined(QUEUEDEBUG)
 #define QUEUEDEBUG_CIRCLEQ_HEAD(head, field)                           \
-       if ((head)->cqh_first != (void *)(head) &&                      \
-           (head)->cqh_first->field.cqe_prev != (void *)(head))        \
+       if ((head)->cqh_first != __launder_type(head) &&                \
+           (head)->cqh_first->field.cqe_prev != __launder_type(head))  \
                panic("CIRCLEQ head forw %p %s:%d", (head),             \
                      __FILE__, __LINE__);                              \
-       if ((head)->cqh_last != (void *)(head) &&                       \
-           (head)->cqh_last->field.cqe_next != (void *)(head))         \
+       if ((head)->cqh_last != __launder_type(head) &&                 \
+           (head)->cqh_last->field.cqe_next != __launder_type(head))   \
                panic("CIRCLEQ head back %p %s:%d", (head),             \
                      __FILE__, __LINE__);
 #define QUEUEDEBUG_CIRCLEQ_ELM(head, elm, field)                       \
-       if ((elm)->field.cqe_next == (void *)(head)) {                  \
+       if ((elm)->field.cqe_next == __launder_type(head)) {            \
                if ((head)->cqh_last != (elm))                          \
                        panic("CIRCLEQ elm last %p %s:%d", (elm),       \
                              __FILE__, __LINE__);                      \
@@ -622,7 +645,7 @@
                        panic("CIRCLEQ elm forw %p %s:%d", (elm),       \
                              __FILE__, __LINE__);                      \
        }                                                               \
-       if ((elm)->field.cqe_prev == (void *)(head)) {                  \
+       if ((elm)->field.cqe_prev == __launder_type(head)) {            \
                if ((head)->cqh_first != (elm))                         \
                        panic("CIRCLEQ elm first %p %s:%d", (elm),      \
                              __FILE__, __LINE__);                      \
@@ -668,7 +691,7 @@
        QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field)                \
        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
        (elm)->field.cqe_prev = (listelm);                              \
-       if ((listelm)->field.cqe_next == (void *)(head))                \
+       if ((listelm)->field.cqe_next == __launder_type(head))          \
                (head)->cqh_last = (elm);                               \
        else                                                            \
                (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
@@ -680,7 +703,7 @@
        QUEUEDEBUG_CIRCLEQ_ELM((head), (listelm), field)                \
        (elm)->field.cqe_next = (listelm);                              \
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
-       if ((listelm)->field.cqe_prev == (void *)(head))                \
+       if ((listelm)->field.cqe_prev == __launder_type(head))          \
                (head)->cqh_first = (elm);                              \
        else                                                            \
                (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
@@ -691,7 +714,7 @@
        QUEUEDEBUG_CIRCLEQ_HEAD((head), field)                          \
        (elm)->field.cqe_next = (head)->cqh_first;                      \
        (elm)->field.cqe_prev = (void *)(head);                         \
-       if ((head)->cqh_last == (void *)(head))                         \
+       if ((head)->cqh_last == __launder_type(head))                   \
                (head)->cqh_last = (elm);                               \
        else                                                            \
                (head)->cqh_first->field.cqe_prev = (elm);              \
@@ -702,7 +725,7 @@
        QUEUEDEBUG_CIRCLEQ_HEAD((head), field)                          \
        (elm)->field.cqe_next = (void *)(head);                         \
        (elm)->field.cqe_prev = (head)->cqh_last;                       \
-       if ((head)->cqh_first == (void *)(head))                        \
+       if ((head)->cqh_first == __launder_type(head))                  \
                (head)->cqh_first = (elm);                              \
        else                                                            \
                (head)->cqh_last->field.cqe_next = (elm);               \
@@ -712,12 +735,12 @@
 #define        CIRCLEQ_REMOVE(head, elm, field) do {                           
\
        QUEUEDEBUG_CIRCLEQ_HEAD((head), field)                          \
        QUEUEDEBUG_CIRCLEQ_ELM((head), (elm), field)                    \
-       if ((elm)->field.cqe_next == (void *)(head))                    \
+       if ((elm)->field.cqe_next == __launder_type(head))              \
                (head)->cqh_last = (elm)->field.cqe_prev;               \
        else                                                            \
                (elm)->field.cqe_next->field.cqe_prev =                 \
                    (elm)->field.cqe_prev;                              \
-       if ((elm)->field.cqe_prev == (void *)(head))                    \
+       if ((elm)->field.cqe_prev == __launder_type(head))              \
                (head)->cqh_first = (elm)->field.cqe_next;              \
        else                                                            \
                (elm)->field.cqe_prev->field.cqe_next =                 \
@@ -727,29 +750,29 @@
 
 #define        CIRCLEQ_FOREACH(var, head, field)                               
\
        for ((var) = ((head)->cqh_first);                               \
-               (var) != (const void *)(head);                          \
+               (var) != (const void *)__launder_type(head);            \
                (var) = ((var)->field.cqe_next))
 
 #define        CIRCLEQ_FOREACH_REVERSE(var, head, field)                       
\
        for ((var) = ((head)->cqh_last);                                \
-               (var) != (const void *)(head);                          \
+               (var) != (const void *)__launder_type(head);            \
                (var) = ((var)->field.cqe_prev))
 
 /*
  * Circular queue access methods.
  */
-#define        CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void 
*)(head))
+#define        CIRCLEQ_EMPTY(head)             ((head)->cqh_first == 
__launder_type(head))
 #define        CIRCLEQ_FIRST(head)             ((head)->cqh_first)
 #define        CIRCLEQ_LAST(head)              ((head)->cqh_last)
 #define        CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
 #define        CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
 
 #define CIRCLEQ_LOOP_NEXT(head, elm, field)                            \
-       (((elm)->field.cqe_next == (void *)(head))                      \
+       (((elm)->field.cqe_next == __launder_type(head))                        
\
            ? ((head)->cqh_first)                                       \
            : (elm->field.cqe_next))
 #define CIRCLEQ_LOOP_PREV(head, elm, field)                            \
-       (((elm)->field.cqe_prev == (void *)(head))                      \
+       (((elm)->field.cqe_prev == __launder_type(head))                        
\
            ? ((head)->cqh_last)                                        \
            : (elm->field.cqe_prev))
 


--- End Message ---


Home | Main Index | Thread Index | Old Index