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 ---
- To: tech-kern%netbsd.org@localhost, tech-userlevel%netbsd.org@localhost
- Subject: in which we present an ugly hack to make sys/queue.h CIRCLEQ work
- From: matthew green <mrg%eterna.com.au@localhost>
- Date: Wed, 20 Nov 2013 20:54:10 +1100
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 ---