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

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 23 Nov, 2013, at 14:48 , John Nemeth <jnemeth%cue.bc.ca@localhost> wrote:
> On Nov 23,  2:16pm, Dennis Ferguson wrote:
> } 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?

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

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