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

[matthew green]

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))

[enh]

+ * this by changing the

the what? :-)

i recently moved bionic from CIRCLEQ
(https://android-review.googlesource.com/#/c/69028/4/libc/bionic/pthread-atfork.c)
to just managing its own list
(https://android-review.googlesource.com/#/c/69028/4/libc/bionic/pthread_atfork.cpp)
because you can't use the existing CIRCLEQ macros in C++.

Post by matthew green
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))

[Ken Hornstein]

Post by matthew green
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 see that at least on MacOS X, sys/queue.h contains the following note:

* Note that circle queues are deprecated, because, as the removal log
* in FreeBSD states, "CIRCLEQs are a disgrace to everything Knuth taught
* us in Volume 1 Chapter 2. [...] Use TAILQ instead, it provides the same
* functionality." Code using them will continue to compile, but they
* are no longer documented on the man page.

I don't think I'm knowledgable enough to speak to the accuracy of that
comment, but would it be simpler just to migrate all of the code over to
TAILQ if the CIRCLEQ ABI is broken as designed?

--Ken

[Zhihao Yuan]

Post by Ken Hornstein
* Note that circle queues are deprecated, because, as the removal log
* in FreeBSD states, "CIRCLEQs are a disgrace to everything Knuth taught
* us in Volume 1 Chapter 2. [...] Use TAILQ instead, it provides the same
* functionality." Code using them will continue to compile, but they
* are no longer documented on the man page.
I don't think I'm knowledgable enough to speak to the accuracy of that
comment, but would it be simpler just to migrate all of the code over to
TAILQ if the CIRCLEQ ABI is broken as designed?

It should not be too hard. Actually, after I mirgrated CIRCLEQ to
TAILQ in nvi2's code,

https://github.com/lichray/nvi2/commits/master?page=9

FreeBSD base already has absolutely no code using CIRCLEQ.

So my suggestion is simple: nuke it out.

[Dennis Ferguson]

Post by Zhihao Yuan

Post by Ken Hornstein
* Note that circle queues are deprecated, because, as the removal log
* in FreeBSD states, "CIRCLEQs are a disgrace to everything Knuth taught
* us in Volume 1 Chapter 2. [...] Use TAILQ instead, it provides the same
* functionality." Code using them will continue to compile, but they
* are no longer documented on the man page.
I don't think I'm knowledgable enough to speak to the accuracy of that
comment, but would it be simpler just to migrate all of the code over to
TAILQ if the CIRCLEQ ABI is broken as designed?

It should not be too hard. Actually, after I mirgrated CIRCLEQ to
TAILQ in nvi2's code,
https://github.com/lichray/nvi2/commits/master?page=9
FreeBSD base already has absolutely no code using CIRCLEQ.
So my suggestion is simple: nuke it out.

This functionally works, but the TAILQ data structure is not the same as
the CIRCLEQ data structure (i.e. no ABI compatibility, if that matters; I'm
not quite sure why it does) and unnecessarily penalizes applications which
need to traverse the list in the tail->head direction.

If one were starting this from scratch I don't think there would be
separate TAILQ and CIRCLEQ implementations, there would instead be one
implementation which used the CIRCLEQ data structure but with NULL in
the .cqe_prev member of the head of the list and the .cqe_next member
at the tail. TAILQ users couldn't tell the difference between this and
the current TAILQ structure in terms of either performance or API, save
for the fact that TAILQ_INSERT_BEFORE() would need to acquire a pointer
to head like the other TAILQ_INSERT_*() macros have, while CIRCLEQ users
wouldn't be penalized for wanting a list which works equally well when
moving in either direction but would get to detect the end of list (in
either direction) with a more conventional comparison to NULL rather
than the disgusting thing they have to do now.

Dennis Ferguson

[Ken Hornstein]

Post by Dennis Ferguson
This functionally works, but the TAILQ data structure is not the same as
the CIRCLEQ data structure (i.e. no ABI compatibility, if that matters;
I'm not quite sure why it does) and unnecessarily penalizes applications
which need to traverse the list in the tail->head direction.

I know the data structures aren't the same, but if you're using the macros
you don't ever notice this. As for the penalty ... you're talking
about:

#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)

versus

#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

One extra pointer dereference is what we're talking about; I have to
believe that for 99% of applications it wouldn't matter.

Also, I see that CIRCLEQ has more complicated logic if you want to
insert elements at the end of it. So obviously there are tradeoffs (but
again, I don't really think it matters to nearly everybody).

--Ken

--Ken

[Dennis Ferguson]

Post by Ken Hornstein

Post by Dennis Ferguson
This functionally works, but the TAILQ data structure is not the same as
the CIRCLEQ data structure (i.e. no ABI compatibility, if that matters;
I'm not quite sure why it does) and unnecessarily penalizes applications
which need to traverse the list in the tail->head direction.

I know the data structures aren't the same, but if you're using the macros
you don't ever notice this. As for the penalty ... you're talking
#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
versus
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
One extra pointer dereference is what we're talking about; I have to
believe that for 99% of applications it wouldn't matter.

I think it is actually 2 extra pointer deferences, but the important bit
is that one of the pointers is fetched from memory you might not need to
read from at all with a CIRCLEQ. On modern processors one cache miss is
worth a whole big pile of extra instructions, so doing reads from memory
you don't strictly need to touch is about the easiest way to make things
go slower.

Post by Ken Hornstein
Also, I see that CIRCLEQ has more complicated logic if you want to
insert elements at the end of it. So obviously there are tradeoffs (but
again, I don't really think it matters to nearly everybody).

I don't think an extra instruction or two matters nearly as much as extra
reads from unrelated memory. I was unable to measure any difference between
the speed of adding something to the end of a TAILQ and adding something to
the end of a CIRCLEQ, but I was able to measure a difference between
TAILQ_LAST() and CIRCLEQ_LAST() for a list that multiple processors were
adding things to.

Dennis Ferguson

[Ken Hornstein]

Post by Dennis Ferguson
I think it is actually 2 extra pointer deferences,

You're right, my apologies.

Post by Dennis Ferguson
but the important bit
is that one of the pointers is fetched from memory you might not need to
read from at all with a CIRCLEQ. On modern processors one cache miss is
worth a whole big pile of extra instructions, so doing reads from memory
you don't strictly need to touch is about the easiest way to make things
go slower.

I can understand that all, but still ... are people really using this in
ways it would be noticable? If it was a serious issue, we could add the
extra previous element pointer you're talking about to the TAILQ macros
and it seems like that would do everything you want.

In a more practical sense ... it seems the only users of CIRCLEQ_PREV
are in sys/kern/subr_vmem.c and sys/kern/vfs_mount.c. In a lot of the
ones in subr_vmem.c look like the relevant pointers would already be in
the cache (and they're only going back one element, not traversing the
whole list). vfs_mount.c uses in vfs_unmountall1(). CIRCLEQ_LAST is
only used by libform and also in vfs_mount.c.

--Ken

[David Holland]

Post by Ken Hornstein
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

There's another wrinkle, however, which is that this code (TAILQ_PREV)
also violates the strict-aliasing rules. I don't think anyone has
found a clear case of gcc (4.8 or otherwise) tripping on it yet, but
it too really ought to be fixed before it bites someone.

[Ken Hornstein]

Post by David Holland

Post by Ken Hornstein
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

There's another wrinkle, however, which is that this code (TAILQ_PREV)
also violates the strict-aliasing rules. I don't think anyone has
found a clear case of gcc (4.8 or otherwise) tripping on it yet, but
it too really ought to be fixed before it bites someone.

I'll be the first one to admit that the strict-aliasing rules are just
at the limit of my understanding ... but doesn't that depend on how
you use it? You'd have to be using it in a case where it mattered if
it could be the same as another pointer. Okay, I can imagine that
wouldn't be too hard to get into that situation, but it's not in the
same class as the CIRCLEQ macros where the violation of strict-aliasing
rules is directly in the macros themselves.

--Ken

[David Holland]

Post by Ken Hornstein

Post by David Holland

#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

There's another wrinkle, however, which is that this code (TAILQ_PREV)
also violates the strict-aliasing rules. I don't think anyone has
found a clear case of gcc (4.8 or otherwise) tripping on it yet, but
it too really ought to be fixed before it bites someone.

I'll be the first one to admit that the strict-aliasing rules are just
at the limit of my understanding ...

Modulo some administrative details, it's just "no object in memory may
be accessed using more than one type".

Post by Ken Hornstein
but doesn't that depend on how you use it?

Not in this case; the problem is that the cast to struct headname
causes it to read tqh_last from an item in memory that might be a
queue head but is probably actually a queue element.

As for getting bitten by the violation... that depends on the compiler
doing something that depends on the assumption that you didn't make
such an access.

[Ken Hornstein]

Post by David Holland
Modulo some administrative details, it's just "no object in memory may
be accessed using more than one type".

Ok ... I _think_ I see it. But doesn't that mean that like 90% of the casts
used by C programmers are totally wrong? :-)

Post by David Holland

Post by Ken Hornstein
but doesn't that depend on how you use it?

Not in this case; the problem is that the cast to struct headname
causes it to read tqh_last from an item in memory that might be a
queue head but is probably actually a queue element.

Alright, I think I understand. If tqe_prev pointed to a queue entry
that would be the problem, because that memory already has a TAILQ_ENTRY
type.

So ... looking at this code ... it seems like the core problem is that
TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
were the same structure, it wouldn't be an issue. It doesn't quite leap
out to me how that would be possible without changing the API a bit.

--Ken

[Mouse]

Post by Ken Hornstein

Post by David Holland
Modulo some administrative details, it's just "no object in memory
may be accessed using more than one type".

Ok ... I _think_ I see it. But doesn't that mean that like 90% of
the casts used by C programmers are totally wrong? :-)

Yes, or at least wrong by that metric. (The other 10% are things like
casting to char * and copying as a sequence of bytes, which I think is
exempted, though I don't recall details.)

I'm not sure how I feel about the strict-aliasing rules. On the one
hand, it breaks some long-standing traditions; on the other, they are
traditions I mostly think are better off getting broken. I do not like
C's type sloppiness for the most part....

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Anthony Mallet]

On Thursday, at 23:56, Mouse wrote:
| Yes, or at least wrong by that metric. (The other 10% are things like
| casting to char * and copying as a sequence of bytes, which I think is
| exempted, though I don't recall details.

Yes, (char *)ptr is an explicitly allowed exception.

C99:
``An object shall have its stored value accessed only by an lvalue expression
that has one of the following types:

- a type compatible with the effective type of the object,
- a qualified version of a type compatible with the effective type of the object,
- a type that is the signed or unsigned type corresponding to the effective
type of the object,
- a type that is the signed or unsigned type corresponding to a qualified
version of the effective type of the object,
- an aggregate or union type that includes one of the aforementioned types
among its members (including, recursively, a member of a subaggregate or
contained union), or
- a character type. ''

[Matthew Orgass]

Post by Anthony Mallet
| Yes, or at least wrong by that metric. (The other 10% are things like
| casting to char * and copying as a sequence of bytes, which I think is
| exempted, though I don't recall details.
Yes, (char *)ptr is an explicitly allowed exception.

In gcq.h, I used (uint8_t *) instead of (char *) with offsetof and I see
endian.h uses unit8_t to rearrange bytes. It makes more sense that way
IMO, but it sounds like it actually violates strict aliasing while using
char wouldn't. Does anyone with more in depth understanding know if this
is this case?

-Matt

Post by Anthony Mallet
``An object shall have its stored value accessed only by an lvalue expression
- a type compatible with the effective type of the object,
- a qualified version of a type compatible with the effective type of the object,
- a type that is the signed or unsigned type corresponding to the effective
type of the object,
- a type that is the signed or unsigned type corresponding to a qualified
version of the effective type of the object,
- an aggregate or union type that includes one of the aforementioned types
among its members (including, recursively, a member of a subaggregate or
contained union), or
- a character type. ''

[Anthony Mallet]

On Saturday, at 14:20, Matthew Orgass wrote:
| 2013-11-22 ***@laas.fr wrote:
| > Yes, (char *)ptr is an explicitly allowed exception.
|
| In gcq.h, I used (uint8_t *) instead of (char *) with offsetof and I see
| endian.h uses unit8_t to rearrange bytes. It makes more sense that way
| IMO, but it sounds like it actually violates strict aliasing while using
| char wouldn't. Does anyone with more in depth understanding know if this
| is this case?

This may help, although it is still a bit obscure to me:
http://stackoverflow.com/questions/12666146/can-uint8-t-be-a-non-character-type

In practice, is there any real chance that uint8_t is not typedef'ed to a char
on NetBSD?

[Rhialto]

Post by Anthony Mallet
http://stackoverflow.com/questions/12666146/can-uint8-t-be-a-non-character-type
In practice, is there any real chance that uint8_t is not typedef'ed to a char
on NetBSD?

In the mythical PDP-10 port this might be the case.

The PDP-10 doesn't have a fixed character type as such defined by the
programming model, but it does have pointers to "bytes" which may be any
number of bits wide (this width is included in the pointer: see
http://pdp10.nocrew.org/docs/instruction-set/Byte.html ).

For a compiler it might be convenient to say that 'char' is 9 bits (then
4 fit in a word) or 6 bits (6 will fit), but it can also provide 8-bit
quantities in case you really want them and don't mind the 4 wasted bits
when they are packed in a word (which is 36 bits).

-Olaf.

[Mouse]

Post by Matthew Orgass
In gcq.h, I used (uint8_t *) instead of (char *) with offsetof and I
see endian.h uses unit8_t to rearrange bytes. It makes more sense
that way IMO, but it sounds like it actually violates strict aliasing
while using char wouldn't.

There are two possible issues here.

The first is whether uint8_t exists. If it doesn't exist, the code
won't even build; if it does exist, it can't be larger than char,
because CHAR_BIT must be at least 8, and it can't be smaller, because
sizeof(char) is by definition 1 and thus no type can be smaller.

However, even if it does exist and is the same size as char, I see no
reason it has to be `a character type' - different integral types of
the same size can exist, as (for example) on current 32-bit machines
where int and long are identical in size and representation but are
nonetheless distinct types. I know of nothing that forbids the
existence of an integral type the same size as char but not a character
type, though such a thing could exist and I just missed it.

Of course, pragmatically, it is highly unlikely uint8_t will be
anything but unsigned char, so you are almost certain to be OK in
practice.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Laight]

Post by Mouse
Of course, pragmatically, it is highly unlikely uint8_t will be
anything but unsigned char, so you are almost certain to be OK in
practice.

Actually it would be very useful to have a 'byte' type that wasn't 'char'.
One of the unfortunate side effects of the strict aliasing rules are that
whenever you write a 'char' the compiler has to assume it might affect
any memory location that isn't part of the same data item.
(All global data being one item.)

David

[Martin Husemann]

Post by Ken Hornstein
So ... looking at this code ... it seems like the core problem is that
TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
were the same structure, it wouldn't be an issue. It doesn't quite leap
out to me how that would be possible without changing the API a bit.

Right. Let's break the API and fix it for real (which also should cover
making it usable for a C++ compiler).

Martin

[Rhialto]

Post by Martin Husemann

Post by Ken Hornstein
So ... looking at this code ... it seems like the core problem is that
TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
were the same structure, it wouldn't be an issue. It doesn't quite leap
out to me how that would be possible without changing the API a bit.

Right. Let's break the API and fix it for real (which also should cover
making it usable for a C++ compiler).

Since the "tqe_prev" field doesn't actually points to the previous
object in the list, but to the pointer that points to this object, it is
useful for insertion and deletion, but less so for actually finding the
previous object.

The current TAILQ_PREV essentially goes back 2 steps and then 1 forward
(since the forward pointers do point to the objects in the list).

I was thinking of something like this, which breaks the API because the
current TAILQ_PREV takes 'headname' and not 'type' as a parameter:

#defined TAILQ_PREV(elm, type, field) \
(char *)(elm->field.tqe_prev) - offsetof(struct type, field)

(omitting outer parentheses and cast to (struct type *) for readability).

Similarly for TAILQ_LAST:

#defined TAILQ_LAST(elm, type, field) \
(char *)(elm->field.tqe_last) - offsetof(struct type, field)

This saves on memory accesses too, compared with the current version.

I hope my diagram of how the pointers point was correct :-)

Post by Martin Husemann
Martin

-Olaf.

[Dennis Ferguson]

Post by Rhialto
I was thinking of something like this, which breaks the API because the
#defined TAILQ_PREV(elm, type, field) \
(char *)(elm->field.tqe_prev) - offsetof(struct type, field)

This doesn't work, unfortunately. Consider what happens when
elm is at the head of the list.

Dennis Ferguson

[David Holland]

Post by Ken Hornstein

Post by David Holland
Modulo some administrative details, it's just "no object in memory may
be accessed using more than one type".

Ok ... I _think_ I see it. But doesn't that mean that like 90% of the casts
used by C programmers are totally wrong? :-)

Yes. That's why -fno-strict-aliasing is very popular, and would be
more popular if people in general were more aware of the issue.

As noted, inspecting the representation of an object using char * or
unsigned char * is explicitly allowed. And some constructions with
unions are allowed. But other stuff isn't.

Note that the bog-standard (struct sockaddr *) cast that one needs and
conventionally uses to call bind(2), connect(2), accept(2), and
similar is, strictly speaking, illegal.

Post by Ken Hornstein
Alright, I think I understand. If tqe_prev pointed to a queue entry
that would be the problem, because that memory already has a TAILQ_ENTRY
type.

Yes. The idea in C is that when you first access fresh memory, that
imprints it with a type. You're then supposed to use only the same
type to access it again later, until you free() it.

Post by Ken Hornstein
So ... looking at this code ... it seems like the core problem is that
TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
were the same structure, it wouldn't be an issue. It doesn't quite leap
out to me how that would be possible without changing the API a bit.

I think it can be done by sticking an anonymous union into TAILQ_HEAD,
but of course anonymous unions aren't supported until C11.

[Mouse]

Post by David Holland
Note that the bog-standard (struct sockaddr *) cast that one needs
and conventionally uses to call bind(2), connect(2), accept(2), and
similar is, strictly speaking, illegal.

I don't think so. The aliasing rules don't say anything about the
types used when passing around pointers to an object, only about the
types used when actually accessing it. Since the accesses implicit in
calls such as bind() are outside the scope of the abstract C machine, I
don't think there are any nasal demons there. (Library routines like
getnameinfo, on the other hand, probably cannot be implemented without
either breaking the aliasing rules or assuming implementation-specific
things about how the structs are laid out in array-of-character terms.
To be type-correct, the various structs sockaddr_* really need to be a
single discriminated union...and I'm not sure sockaddr_un can ever be
done type-correctly; I'd have to think about it more.)

Post by David Holland
The idea in C is that when you first access fresh memory, that
imprints it with a type. You're then supposed to use only the same
type to access it again later, until you free() it.

Well, not necessarily free(); the freeing implicit in a variable of
automatic storage duration going out of scope also counts. And there
are some exceptions for unions (loosely put, the imprinted type can be
changed by using a different member of the union). And there's the
"character type" escape....

Post by David Holland

So if TAILQ_HEAD and TAILQ_ENTRY were the same structure, it
wouldn't be an issue. It doesn't quite leap out to me how that
would be possible without changing the API a bit.

I think it can be done by sticking an anonymous union into
TAILQ_HEAD,

I'm not sure, since storing through one union member and fetching
through another brings back issues. I'd need to see details to do more
than take guesses, though, of course.

Post by David Holland
but of course anonymous unions aren't supported until C11.

Or gcc; I think gcc had anonymous unions before C11, didn't it?

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Steffen "Daode" Nurpmeso]

The standard committee situation is terribly frustrating in that
things which worked fine on computers which were slower than
todays coffee machines and even existed before i was born get
out-stamped and "improved" for dubious value, e.g. Unix and its
fork(2) and posix_spawn(), and i don't think its funny if
a standard group states

in the process of relaxing the restrictions on asynchronous
signal handlers to allow use of atomics, we inadvertently made
it impossible to use even local variables of non-volatile,
non-atomic type

|automatic storage duration going out of scope also counts. And there
|are some exceptions for unions (loosely put, the imprinted type can be
|changed by using a different member of the union). And there's the
|"character type" escape....

|I'm not sure, since storing through one union member and fetching
|through another brings back issues. I'd need to see details to do more
|than take guesses, though, of course.

I think i've recalled a QT blog ([1], mentioned by me 14 months
ago on a FreeBSD list in equal context) falsely.
Regarding queue.3, however, there is not bit-fiddling with values,
it's just comparison and assigning, which makes me wonder why the
union approach shouldn't work for real.
But maybe in the end it'll be just one more matter of intelligent
compiler overoptimization unless it causes problems, and then the
problem occurs again.

[1] <http://blog.qt.digia.com/blog/2011/06/10/type-punning-and-strict-aliasing/>

It's no fun at all, i too had written code like

// (shares bit space with ConnType)
pri enum Flags {
f_tmask = 3,
f_dipe = 1<<2, // disconnect pending (no more calling)
f_mask = 7
};

pri
mutable Conn *m_slots;

pro _Sender(void)
:
m_slots(NIL)
{}
[..]
_pri boolean _Sender::_Disconnect(
Conn *_c) const
{
RealConn x, rc;
_Nydin;

// try to find an equal (aka the very) connection
for(x.c=_c, rc.c=m_slots; (rc.asint &= ~f_mask); rc.c=rc.c->right) {
switch(ConnType(rc.c->flags & f_tmask)) {
case ct_ptf_o:
if(rc.cfo->obj != x.cfo->obj)
break;
// fall..
case ct_ptf:
if(rc.cf->slot != x.cf->slot)
break;
goto jfree;
case ct_ptm:
if(rc.cml->elobj != x.cml->elobj)
break;
if(rc.cml->slot != x.cml->slot)
break;
goto jfree;
case ct_ptm_t:

To me this makes perfect sense.

--steffen

[Thor Lancelot Simon]

Post by Mouse
To be type-correct, the various structs sockaddr_* really need to be a
single discriminated union...and I'm not sure sockaddr_un can ever be
done type-correctly; I'd have to think about it more.)

GCC's transparent unions are really nice for this.

Thor

[Mouse]

Post by Thor Lancelot Simon

Post by Mouse
To be type-correct, the various structs sockaddr_* really need to be
a single discriminated union...and I'm not sure sockaddr_un can ever
be done type-correctly; I'd have to think about it more.)

GCC's transparent unions are really nice for this.

Yes, though all they do is remove an otherwise-necessary layer of
member naming. The part that I'd really find irritating is having to
allocate the whole union - roughly the equivalent of today's struct
sockaddr_storage - even when I know it's going to hold only one flavour
of sockaddr, which wastes most of the space allocated. (The space
wasted is small enough to be unimportant...in most cases.)

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Holland]

Post by Mouse

Post by David Holland
Note that the bog-standard (struct sockaddr *) cast that one needs
and conventionally uses to call bind(2), connect(2), accept(2), and
similar is, strictly speaking, illegal.

I don't think so. The aliasing rules don't say anything about the
types used when passing around pointers to an object, only about the
types used when actually accessing it.

Indeed. But it *is* accessed via both types. That the kernel copies it
before accessing it doesn't (AIUI) matter. The compiler is not in a
position to see both ends of this at once; but that's why I said
"strictly speaking".

Post by Mouse
To be type-correct, the various structs sockaddr_* really need to be a
single discriminated union...and I'm not sure sockaddr_un can ever be
done type-correctly; I'd have to think about it more.)

Why not? Worst case is that your union is size PATH_MAX plus a bit.

Post by Mouse
(some further notes skipped, no disagreement)

Post by David Holland
I think it can be done by sticking an anonymous union into
TAILQ_HEAD,

I'm not sure, since storing through one union member and fetching
through another brings back issues. I'd need to see details to do more
than take guesses, though, of course.

I believe that was explicitly legalized in C99 TC3.

Post by Mouse

Post by David Holland
but of course anonymous unions aren't supported until C11.

Or gcc; I think gcc had anonymous unions before C11, didn't it?

It's had them for ages and ages, yeah.

[Dennis Ferguson]

Post by David Holland

Post by Ken Hornstein
So ... looking at this code ... it seems like the core problem is that
TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
were the same structure, it wouldn't be an issue. It doesn't quite leap
out to me how that would be possible without changing the API a bit.

I think it can be done by sticking an anonymous union into TAILQ_HEAD,
but of course anonymous unions aren't supported until C11.

It isn't perfectly clear to me that this code has an aliasing problem
the way it is, though. The only thing that matters in the standard are
the types of the lvalue expressions used to access object in storage. The
lvalue expression types used to access the objects in storage in this
case are 'type **', 'type **' and 'type *', which are the types those
objects were stored with and the types that would be used for other
accesses to the same locations. The structure type used to arrive there
should only matter if it is the type of an lvalue expression itself,
e.g. *(struct foo *)ptr(?).

I would be interested in knowing an actual example of the comparison
problem with the CIRCLEQ macro, if the concern isn't theoretical. Since
the C standard explicitly allows a pointer to a structure type to be
converted to the type of its first member and back, to another structure
type and back, or to char * or void * and back, the fact that the two
pointers point at different structure types is by itself insufficient to
prove that they would not compare equal when suitably converted. It seems
like that conclusion would minimally need to depend on proving that there
was no possible use of the structure pointers which wouldn't violate the
aliasing requirements, i.e. that that are no structure members at the same
offsets which have compatible types. That's a rather aggressive optimization,
and is kind of like throwing you in jail for a crime you haven't actually
committed yet (though I guess that happens too).

Dennis Ferguson

[John Nemeth]

On Nov 23, 2:16pm, Dennis Ferguson wrote:
} On 22 Nov, 2013, at 21:40 , David Holland <dholland-***@netbsd.org> wrote:
} >> So ... looking at this code ... it seems like the core problem is that
} >> TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
} >> literally the same structure layout). So if TAILQ_HEAD and TAILQ_ENTRY
} >> were the same structure, it wouldn't be an issue. It doesn't quite leap
} >> out to me how that would be possible without changing the API a bit.
} >
} > I think it can be done by sticking an anonymous union into TAILQ_HEAD,
} > but of course anonymous unions aren't supported until C11.
}
} It isn't perfectly clear to me that this code has an aliasing problem
} the way it is, though. The only thing that matters in the standard are
} the types of the lvalue expressions used to access object in storage. The
} lvalue expression types used to access the objects in storage in this
} case are 'type **', 'type **' and 'type *', which are the types those

"type **" and "type *" are not the same types.

} objects were stored with and the types that would be used for other
} accesses to the same locations. The structure type used to arrive there
} should only matter if it is the type of an lvalue expression itself,
} e.g. *(struct foo *)ptr(?).
}
} I would be interested in knowing an actual example of the comparison
} problem with the CIRCLEQ macro, if the concern isn't theoretical. Since

Uh, do you really think people would be doing all this work
for something that was theoretical? The problem is that gcc 4.8
optimises out the comparison as being always false due to the
anti-alias rule.

} the C standard explicitly allows a pointer to a structure type to be
} converted to the type of its first member and back, to another structure
} type and back, or to char * or void * and back, the fact that the two

I rather doubt that you can convert to a different structure type
and back. Those would definitely be different objects.

} pointers point at different structure types is by itself insufficient to
} prove that they would not compare equal when suitably converted. It seems
} like that conclusion would minimally need to depend on proving that there
} was no possible use of the structure pointers which wouldn't violate the
} aliasing requirements, i.e. that that are no structure members at the same
} offsets which have compatible types. That's a rather aggressive optimization,
} and is kind of like throwing you in jail for a crime you haven't actually
} committed yet (though I guess that happens too).
}
}-- End of excerpt from Dennis Ferguson

[Dennis Ferguson]

Post by John Nemeth
} It isn't perfectly clear to me that this code has an aliasing problem
} the way it is, though. The only thing that matters in the standard are
} the types of the lvalue expressions used to access object in storage. The
} lvalue expression types used to access the objects in storage in this
} case are 'type **', 'type **' and 'type *', which are the types those
"type **" and "type *" are not the same types.

How is that relevant?

The aliasing constraint in the standard starts with

An object shall have its stored value accessed only by an lvalue expression
that has one of the following types...

so what matters is the types of the lvalue expressions used to access the
stored values of objects. The line of code in question accesses three stored
object values, the first with an lvalue expression of 'type **', the second
with an lvalue expression of 'type **' and the third with an lvalue
expression of 'type *' (here, 'type' is the thing you might have provided to
that argument of _TAILQ_ENTRY or _TAILQ_HEAD). Since each of these types is
the same as the type the object it is accessing was originally stored with, and
is the type that other accesses to the same object's storage will be made
with, where's the aliasing problem?

Post by John Nemeth
} objects were stored with and the types that would be used for other
} accesses to the same locations. The structure type used to arrive there
} should only matter if it is the type of an lvalue expression itself,
} e.g. *(struct foo *)ptr(?).
}
} I would be interested in knowing an actual example of the comparison
} problem with the CIRCLEQ macro, if the concern isn't theoretical. Since
Uh, do you really think people would be doing all this work
for something that was theoretical? The problem is that gcc 4.8
optimises out the comparison as being always false due to the
anti-alias rule.

If I thought some of my own code was theoretically invalid C I would
fix it even if I hadn't yet seen a problem with the compilers I had and
even if that required some work. I also often fix it if it is valid,
working C but some compiler warning complains about it (like complaints
about uninitialized variables which are in fact always initialized before
use).

gcc can't correctly eliminate the comparison just because you are asking
it to compare pointers to different structure types. No aliasing issues
arise in any case unless you actually use the pointers to access something,
and there are many ways that two pointers of different structure types can
validly refer to the same object. For example, if one of the pointers were
to an incomplete type it could certainly not eliminate the comparison since
it couldn't know, e.g., whether the other structure pointer was in fact a
pointer to the first member of the structure whose members are unknown to it
(I assume this isn't controversial because you didn't complain about
first-member pointer conversions). It also couldn't know if pointers whose
types it did know were referring to different members of the same union,
perhaps with the union declared in another compilation unit, in which case
not only would it be valid for the pointers to refer to the same object but
it wouldn't violate the aliasing rules to access compatibly typed members at
the start of each structure with the different pointers (that's another bit
the standard allows and the aliasing rules don't prohibit).

If gcc is eliminating the possibility that a comparison for equality might
be true it can only be doing so either by proving that uses made of the
pointers in other parts of the code would violate the alias rules if the
pointers were the same, or perhaps that there are no possible uses of
the pointers which wouldn't violate the aliasing rules based on the
structure layouts. In either case it is doing something quite clever,
so I wouldn't mind seeing an example of this. It is certainly not the
case that the anti-alias rule prevents two pointers to different structure
types from ever comparing equal when suitably converted, the problem with
the macros must be more subtle.

Post by John Nemeth
} the C standard explicitly allows a pointer to a structure type to be
} converted to the type of its first member and back, to another structure
} type and back, or to char * or void * and back, the fact that the two
I rather doubt that you can convert to a different structure type
and back. Those would definitely be different objects.

Actually you can (you just can't necessarily use the converted version of
the pointer to access anything), but nothing here relies on that being true
so we needn't worry about it.

Dennis Ferguson

[Matthew Orgass]

Post by Dennis Ferguson
If gcc is eliminating the possibility that a comparison for equality might
be true it can only be doing so either by proving that uses made of the
pointers in other parts of the code would violate the alias rules if the
pointers were the same, or perhaps that there are no possible uses of
the pointers which wouldn't violate the aliasing rules based on the
structure layouts. In either case it is doing something quite clever,
so I wouldn't mind seeing an example of this. It is certainly not the
case that the anti-alias rule prevents two pointers to different structure
types from ever comparing equal when suitably converted, the problem with
the macros must be more subtle.

I think you are right that it is not a strict aliasing violation.
Looking at the N1570 draft (6.2.6.1 representation of types), it looks
like because the value stored is not of the appropriate type then
accessing it as if it was that type is undefined. Storing a pointer to
the head is allowed as a "trap representation", but accessing it as a
pointer to struct type * is undefined. If this is correct, doing the
comparison with memcmp should result in behavior defined to DTRT.

-Matt

[Anthony Mallet]

On Saturday, at 19:08, Dennis Ferguson wrote:
| gcc can't correctly eliminate the comparison just because you are asking
| it to compare pointers to different structure types. No aliasing issues
| arise in any case unless you actually use the pointers to access something,
| and there are many ways that two pointers of different structure types can
| validly refer to the same object.

(I think that) strict aliasing rules implies that if two types "type{1,2}" do
not match any of the aliasing rules (e.g. type1 is of the same type as
the first member of type2, or type1 is a char, or ...), then any two pointers
ptr{1,2} on type{1,2} respectively _ARE_ different, because *ptr1 != *ptr2 per
the aliasing rules and this implies ptr1 != ptr2.

[Mouse]

Post by Anthony Mallet
(I think that) strict aliasing rules implies that if two types
"type{1,2}" do not match any of the aliasing rules (e.g. type1 is of
the same type as the first member of type2, or type1 is a char, or
...), then any two pointers ptr{1,2} on type{1,2} respectively _ARE_
different, because *ptr1 != *ptr2 per the aliasing rules and this
implies ptr1 != ptr2.

Only if you actually evaluate *ptr1 and *ptr2 (in some cases, I think,
just one of them is enough). Otherwise you're not accessing the
relevant object(s); the rule is about accesses to values, not about
pointers that, if followed, would perform certain accesses to values.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[David Laight]

Post by Mouse

Post by Anthony Mallet
(I think that) strict aliasing rules implies that if two types
"type{1,2}" do not match any of the aliasing rules (e.g. type1 is of
the same type as the first member of type2, or type1 is a char, or
...), then any two pointers ptr{1,2} on type{1,2} respectively _ARE_
different, because *ptr1 != *ptr2 per the aliasing rules and this
implies ptr1 != ptr2.

Only if you actually evaluate *ptr1 and *ptr2 (in some cases, I think,
just one of them is enough). Otherwise you're not accessing the
relevant object(s); the rule is about accesses to values, not about
pointers that, if followed, would perform certain accesses to values.

One option would have bee to replace the comparison:
(void *)foo == (void *)bar
with:
(char *)foo - (char *)0 == (char *)bar - (char *)0

Which the compiler can't optimise away.
well (const char *), but that makes the line too long!

I've had to do something similar to cast to, IIRC, (foo * const *).
In a function that advances a pointer down an array - which might be const.


David

[Mouse]

[The compiler] also couldn't know if pointers whose types it did know
were referring to different members of the same union, perhaps with
the union declared in another compilation unit

The text I have says

[#5] One special guarantee is made in order to simplify the
use of unions: if a union contains several structures that
share a common initial sequence (see below), and if the
union object currently contains one of these structures, it
is permitted to inspect the common initial part of any of
them anywhere that a declaration of the completed type of
the union is visible. Two structures share a common initial
sequence if corresponding members have compatible types
(and, for bit-fields, the same widths) for a sequence of one
or more initial members.

Note that the completed union declaration must be visible for this
exemption to apply, so as I read it the part after the last comma of
the quote I opened this mail with is wrong....

in which case not only would it be valid for the pointers to refer to
the same object but it wouldn't violate the aliasing rules to access
compatibly typed members at the start of each structure with the
different pointers (that's another bit the standard allows and the
aliasing rules don't prohibit).

As I read it, the aliasing rule does prohibit it, but may be overridden
by another rule; the question is whether 6.5.2.3 #5 (the [#5] above)
overrides 6.5 #7 (the anti-alias rule quoted upthread). (My own guess
would be that it does.)

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Dennis Ferguson]

Post by Mouse

[The compiler] also couldn't know if pointers whose types it did know
were referring to different members of the same union, perhaps with
the union declared in another compilation unit

The text I have says
[#5] One special guarantee is made in order to simplify the
use of unions: if a union contains several structures that
share a common initial sequence (see below), and if the
union object currently contains one of these structures, it
is permitted to inspect the common initial part of any of
them anywhere that a declaration of the completed type of
the union is visible. Two structures share a common initial
sequence if corresponding members have compatible types
(and, for bit-fields, the same widths) for a sequence of one
or more initial members.
Note that the completed union declaration must be visible for this
exemption to apply, so as I read it the part after the last comma of
the quote I opened this mail with is wrong....

Ahh, I misremembered that. Since this misunderstanding was the basis
for thinking it might be okay to access objects through different structure
pointers as long as the member types matched what was stored, and since
I know of no other part of the standard which would allow this, I can
see why the compiler could choose to treat this as illegal when no
union is visible. I guess that means the TAILQ macros really are an
accident waiting to happen.

That also makes it clear that, in the CIRCLEQ case, when the pointers
compare equal then any use of both the pointers to access members would
be out-of-spec aliasing. The comparison being deleted is in fact
surrounded by code which uses the both pointers, so I can see why
the compiler might be suspicious enough to warn about it, but the
only actual aliased access is in a branch of the if()s the comparison
would be correctly avoiding if the code were generated. It seems like
the optimizer has moved from requiring that code not do anything which
isn't explicitly allowed by the standard (the TAILQ case) to requiring
code not do things which the standard explicitly allows but which may,
in some circumstance, not be perfectly portable.

I think getting rid of uses of the CIRCLEQ macros was the right thing
to do in any case, since code which works like that doesn't need to
exist. I'm not sure that that TAILQ macros are the best answer
to the problem, though.

Dennis Ferguson

[Christos Zoulas]

Post by Dennis Ferguson
I think getting rid of uses of the CIRCLEQ macros was the right thing
to do in any case, since code which works like that doesn't need to
exist. I'm not sure that that TAILQ macros are the best answer
to the problem, though.

Unfortunately I agree... But in the absence of a better alternative...

christos

[Matt W. Benjamin]

What's your issue with TAILQ?

Matt

Post by Christos Zoulas

Post by Dennis Ferguson
I think getting rid of uses of the CIRCLEQ macros was the right

thing

Post by Dennis Ferguson
to do in any case, since code which works like that doesn't need to
exist. I'm not sure that that TAILQ macros are the best answer
to the problem, though.

Unfortunately I agree... But in the absence of a better
alternative...
christos

--
Matt Benjamin
The Linux Box
206 South Fifth Ave. Suite 150
Ann Arbor, MI 48104

http://linuxbox.com

tel. [phone]
fax. [phone]
cel. 734-216-5309

[Christos Zoulas]

On Nov 26, 8:20pm, ***@linuxbox.com ("Matt W. Benjamin") wrote:
-- Subject: Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ

| What's your issue with TAILQ?

#define TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

etc.

christos

[Matt W. Benjamin]

Let me get on the record. It's basically ridiculous to allow GCC 4.8 to redefine the
set of permitted C expressions such that it breaks BSD.

Matt

Post by Christos Zoulas
-- Subject: Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ
| What's your issue with TAILQ?
#define TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
etc.
christos

--
Matt Benjamin
The Linux Box
206 South Fifth Ave. Suite 150
Ann Arbor, MI 48104

http://linuxbox.com

tel. [phone]
fax. [phone]
cel. 734-216-5309

[Mouse]

Let me get on the record. It's basically ridiculous to allow GCC 4.8
to redefine the set of permitted C expressions such that it breaks
BSD.

gcc 4.8 isn't. C99 did; what's distinctive about gcc 4.8 is that
before that gcc didn't take advantage of the leeway C99 said it had.
These macros have been out-of-spec since the day NetBSD decided it was
going to use C99 rather than some older version of C; it's just that
only now is that out-of-spec-ness actually biting anyone. (That
decision may have been implicit in a compiler version change.)

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Justin Cormack]

Post by Mouse

Let me get on the record. It's basically ridiculous to allow GCC 4.8
to redefine the set of permitted C expressions such that it breaks
BSD.

gcc 4.8 isn't. C99 did; what's distinctive about gcc 4.8 is that
before that gcc didn't take advantage of the leeway C99 said it had.
These macros have been out-of-spec since the day NetBSD decided it was
going to use C99 rather than some older version of C; it's just that
only now is that out-of-spec-ness actually biting anyone. (That
decision may have been implicit in a compiler version change.)

The decision to detect them and then optimise to broken code rather than a
compile time error is what annoys me.

Justin

[Mouse]

Post by Dennis Ferguson
the C standard explicitly allows a pointer to a structure type to be
converted to the type of its first member and back, to another
structure type and back, or to char * or void * and back,

I rather doubt that you can convert to a different structure type and
back.

I feel sure Dennis Ferguson meant "to _a pointer to_ a different
structure type" there.

As I read it, the anti-alias rule doesn't actually say anything about
the pointers themselves, only about what results when you follow them;
if the code never followed the pointers, it could compare them just
fine without risk (though I'm going to ask my go-to C reference person
to check my reading on this point).

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[Matthew Orgass]

Post by Mouse
if the code never followed the pointers, it could compare them just
fine without risk (though I'm going to ask my go-to C reference person
to check my reading on this point).

This is the case with CIRCLEQ, which is what Dennis was pointing out.
It could have used NULL as a sentinel, but instead used the pointer to
some other completely different type it happened to have available.
Additionally, when doing the later comparison the correct type of the
pointer being compared is cast to void * explicitly and there is an
implicit conversion of the incorrectly-typed pointer. It seems like an
interesting C language question if all that is supposed to work.

Looking at section 6.3.2.3 of N1570 (pointers), "trap representation" is
only mentioned for integer conversion to pointer so that idea of mine
seems completely wrong. Conversion between pointers of different types
only mentions differing alignment causing undefined behavior (except for
NULL, which is guaranteed to work). I wouldn't think it would be a
differing alignment issue. I also read Dennis's message again and learned
more :). It sounds like it might be supposed to work. Unless something
requires the cast to be applied to the wrongly typed pointer when doing
the comparison. 6.3.2.3 only guarantees that when converted back it will
compare equal, so I wonder if this does mean that there is supposed to be
an explicit cast (though I don't see anything that seems to say that an
explicit cast is different than an implicit conversion or that casting to
void * wouldn't qualify as "converted back" for this purpose).

I tried and failed to get a simple CIRCLEQ test case to produce
incorrect code on an arch linux system with gcc 4.8.2. Also, I tried
compiling nvi-1.79 (from Keith Bostic's site, because that was easy; there
don't seem to be significant differences from NetBSD CIRCLEQ) with -O2
-fstrict-aliasing -Wstrict-aliasing=1 (and -Wstrict-aliasing=2 and 3; 1
and 3 produced completely different results and 2 produced the combination
of 1 and 3, which is not what I expected from the man page).

There are a couple of strict-alias warnings at level 1 and 2 for CIRCLEQ
(actually the hand coded equivalent of CIRCLEQ_FOREACH), which go away
(without produced output changes) if the cast is moved to the left side of
the comparison. I didn't notice any differences in behavior between the
original code and using __launder_type with a few simple tests, though
that isn't surprising.

I'm not sure it is worth putting more time into (and I'm glad folks have
been removing CIRCLEQ from most places), but casting to struct type * when
storing and casting to typeof(head) on the left side of the comparison
seems likely to make it work reliably (possibly just changing the cast on
the left of the comparison to void * would work too and would be standard
C).

Thanks to everyone doing the gcc update :).

-Matt

[matthew green]

Post by John Nemeth
} I would be interested in knowing an actual example of the comparison
} problem with the CIRCLEQ macro, if the concern isn't theoretical. Since
Uh, do you really think people would be doing all this work
for something that was theoretical? The problem is that gcc 4.8
optimises out the comparison as being always false due to the
anti-alias rule.

correct. CIRCLEQ was broken with GCC 4.8. TAILQ appears fine.

the observations were that nvi(1) would hang while blocking
signals (ie, you had to kill -9 from another window), and
i used tests/lib/libc/db/ to eventually locate the problem.

in these cases, the *INSERT*() macros were never inserting for
the head of the queue, which would cause the iteration macros
to loop forever.


.mrg.

[Mouse]

Post by Dennis Ferguson
It isn't perfectly clear to me that this code has an aliasing problem
the way it is, though.

gcc thinks it does, apparently.

Post by Dennis Ferguson
The only thing that matters in the standard are the types of the
lvalue expressions used to access object in storage. The lvalue
expression types used to access the objects in storage in this case
are 'type **', 'type **' and 'type *',

Um, some of them. There are also the containing objects, which have
(incompatible) struct types (in CIRCLEQ_INSERT_HEAD, for example, I see
both "(elm)->field" and "(head)"). Because the struct types are
incompatible, the compiler is allowed to assume they do not alias one
another, which leads to optimizing away comparisons and thereby
producing nonworking code.

That these lvalue expressions are then further dissected via struct
member access doesn't really change this.

Post by Dennis Ferguson
I would be interested in knowing an actual example of the comparison
problem with the CIRCLEQ macro, if the concern isn't theoretical.

Well, mrg wrote, when starting the thread,

< 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.

which sure looks to me as though it's not just theoretical. (I don't
know personally; mrg's mail implies this was with gcc 4.8, which I
don't run.)

Post by Dennis Ferguson
Since the C standard explicitly allows a pointer to a structure type
to be converted to the type of its first member and back, to another
structure type and back, or to char * or void * and back, the fact
that the two pointers point at different structure types is by itself
insufficient to prove that they would not compare equal when suitably
converted.

True but irrelevant. Whether they actually would compare equal is
irrelevant; since the code follows those pointers, if they do point to
the same object then the code violates the quoted constraint and thus
is off in pure nasal demon territory. So the compiler is entirely
within its rights to assume they do not point to the same object and
thus optimize away the comparison.

Post by Dennis Ferguson
It seems like that conclusion would minimally need to depend on
proving that there was no possible use of the structure pointers
which wouldn't violate the aliasing requirements, i.e. that that are
no structure members at the same offsets which have compatible types.

Again, you're ignoring the struct-valued lvalue expressions involved,
focusing instead on the member-reference expressions containing them.

/~\ The ASCII Mouse
\ / Ribbon Campaign
X Against HTML ***@rodents-montreal.org
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B

[John Nemeth]

On Nov 24, 5:25am, Mouse wrote:
}
} Well, mrg wrote, when starting the thread,
}
} < 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.
}
} which sure looks to me as though it's not just theoretical. (I don't
} know personally; mrg's mail implies this was with gcc 4.8, which I
} don't run.)

The work has now changed to GCC 4.8.2. It is being prepped
for import. The compiler work is basically done. At this point,
it is mostly making sure that NetBSD builds and runs with it.
Since I'm not doing the work, I don't have a timeline, but it
shouldn't be too much longer (FSVO much longer). This means that
sometime in the not too distant future anybody running -current,
or anybody that runs NetBSD 7.0 when it is released will be using
GCC 4.8.2 or later.

}-- End of excerpt from Mouse

[Rhialto]

If one were starting this from scratch [...]

Ever since I grokked the elegance of Lists in AmigaOS, I've always
wondered why other list implementations do it differently.

A list is double linked, and it has dummy first and last nodes (which
aren't part of the data and consist just of the next and prev pointers).
They are elegantly combined in the list header, which consists of 3
pointers:

mlh_Head which points to the first real node,
mlh_Tail which is always NULL
mlh_TailPred which points to the last real node.

Each node in the list starts with a ln_Next and a ln_Prev pointer.

When the list is empty,

mlh_Head points to mlh_Tail
mlh_Tail is always NULL
mlh_TailPred points to mlh_Head.

The first dummy node consists of mlh_Head and mlh_Tail, i.e. its ln_Prev
is NULL, and the last dummy node consists of mlh_Tail and mlh_TailPred,
where its ln_Next is NULL.

This initially confusing situation eliminates all special cases for
node insertion and removal (and traversal isn't made more complicated).

This is more extensively explained in
http://wiki.amigaos.net/index.php/Exec_Lists_and_Queues .

-Olaf.

[David Holland]

Post by Rhialto
Ever since I grokked the elegance of Lists in AmigaOS, I've always
wondered why other list implementations do it differently.

One reason is that with Amiga lists is that the list node structure
needs to be at the beginning of the object, and consequently any
particular object can only be on one list. This is ok for exec.library
(and a lot of other stuff) but falls down in many cases. Part of the
supposed advantage of the <sys/queue.h> types is that they don't have
this limitation.

Also, with current C and C compilers you really can't share the null
end pointer; you need two list nodes in the list head, and they need
to specifically be instances of the list node structure. Having only
the one null not only violates the strict-aliasing rules but also a
bunch of regulations about structure member padding and alignment.

Post by Rhialto
This initially confusing situation eliminates all special cases for
node insertion and removal (and traversal isn't made more complicated).

Traversal is slightly more complicated, in that the start and end
logic has to skip the bookends, and until you're used to the idiom
it's easy to mess this up. And if you do, demons fly out of your
nose...

However, in general I agree with you, it's much more elegant.

[Matthew Orgass]

Post by matthew green
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.
+ * If we ever choose to change the ABI of the CIRCLEQ macros, we could fix
+ * this by changing the

If changing the ABI (or for places where it doesn't matter), please
consider gcq (in gcq.h, gcq(3)). Or use part of it (I think the *_TYPED
macros are drop in replacements for CIRCLEQ). Also, slhchi is the only
thing in the tree that uses it and while in theory some third party
software could use it, I'd assume that in practice anyone who did would
just copy it, so it wouldn't be a problem to alter the interface some if
needed. Also, while I did test it at the time I haven't used it again yet
so it is possible there are bugs lurking outside of what slhci uses.

I don't fully understand the strict aliasing rules, but the only thing
that seems like it might cause trouble is gcq_head(), which is not used
internally but provided to be able to treat any element as the head for
iteration purposes (presumably because you don't have a designated head,
so not CIRCLEQ usage). It casts a struct to a struct that contains only
that struct and is used only to cast back. If that isn't safe, that
function could just be removed and replaced with an explanation of why it
isn't safe, however I expect it to be safe because it is never used except
to cast to the inner type (the head only has a separate type to make it
hard to accidently mess up the argument order).

-Matt

[Steffen "Daode" Nurpmeso]

matthew green <***@eterna.com.au> 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)

[Dennis Ferguson]

Post by matthew green
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.)

I may be misunderstanding something, but it seems like this might
preserve the ABI (e.g. old binaries with a newly-compiled library)
but still represents a change to the API for anything newly
compiled(?). That is, doesn't this code from the kernel have the
same problem that the macros themselves have, or am I missing something?

/*
* sigclear:
*
* Clear all pending signals in the specified set.
*/
void
sigclear(sigpend_t *sp, const sigset_t *mask, ksiginfoq_t *kq)
{
ksiginfo_t *ksi, *next;

if (mask == NULL)
sigemptyset(&sp->sp_set);
else
sigminusset(mask, &sp->sp_set);

ksi = CIRCLEQ_FIRST(&sp->sp_info);
for (; ksi != (void *)&sp->sp_info; ksi = next) {
next = CIRCLEQ_NEXT(ksi, ksi_list);
if (mask == NULL || sigismember(mask, ksi->ksi_signo)) {
CIRCLEQ_REMOVE(&sp->sp_info, ksi, ksi_list);
KASSERT((ksi->ksi_flags & KSI_FROMPOOL) != 0);
KASSERT((ksi->ksi_flags & KSI_QUEUED) != 0);
CIRCLEQ_INSERT_TAIL(kq, ksi, ksi_list);
}
}
}

So is the plan to add the ugly inline to the CIRCLEQ_* macro
definitions, and then fix each program which uses the macros
with the same ugly inline when they are compiled by the new
compiler?

If that's the plan then it seems like it might be better to know
what the final solution looks like before changing any code which
uses the CIRCLEQ macros, so that any code which needs to be fixed
just needs to be fixed once.

Dennis Ferguson

[Alexander Nasonov]

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

I'm pretty sure that __attribute__((__may_alias__)) was on the table
but I wonder why was it rejected?
Thanks,
Alex