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

[David Laight]

On Sun, Nov 24, 2013 at 06:42:40AM -0500, Mouse wrote:
> > (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

-- 
David Laight: da...@l8s.co.uk

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

[Justin Cormack]

On 27 Nov 2013 06:50, "Mouse"  wrote:
>
> > 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

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

[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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[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


- "Christos Zoulas"  wrote:

> On Nov 26,  8:20pm, m...@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 Benjamin
The Linux Box
206 South Fifth Ave. Suite 150
Ann Arbor, MI  48104

http://linuxbox.com

tel.  734-761-4689 
fax.  734-769-8938 
cel.  734-216-5309 

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

[Christos Zoulas]

On Nov 26,  8:20pm, m...@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

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

[Matt W. Benjamin]

What's your issue with TAILQ?

Matt

- "Christos Zoulas"  wrote:

> In article <96497888-f8c7-49f2-958b-532a2093b...@gmail.com>,
> Dennis Ferguson   wrote:
> 
> >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 Benjamin
The Linux Box
206 South Fifth Ave. Suite 150
Ann Arbor, MI  48104

http://linuxbox.com

tel.  734-761-4689 
fax.  734-769-8938 
cel.  734-216-5309 

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

[Christos Zoulas]

In article <96497888-f8c7-49f2-958b-532a2093b...@gmail.com>,
Dennis Ferguson   wrote:

>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

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

[Dennis Ferguson]

On 24 Nov, 2013, at 03:37 , Mouse  wrote:
>> [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

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

[matthew green]

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

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

[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

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

[Mouse]

> (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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[Mouse]

>> 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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[Mouse]

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

gcc thinks it does, apparently.

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

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

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

> 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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

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

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

[Matthew Orgass]

On 2013-11-23 dennis.c.fergu...@gmail.com wrote:


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

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

[David Holland]

On Sat, Nov 23, 2013 at 12:59:04AM -0500, Mouse wrote:
 > > 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".

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

 > (some further notes skipped, no disagreement)
 >
 > > 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.

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

-- 
David A. Holland
dholl...@netbsd.org

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

[Dennis Ferguson]

On 23 Nov, 2013, at 14:48 , John Nemeth  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

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

[John Nemeth]

On Nov 23,  2:16pm, Dennis Ferguson wrote:
} On 22 Nov, 2013, at 21:40 , David Holland  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

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

[Dennis Ferguson]

On 22 Nov, 2013, at 21:40 , David Holland  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
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

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

[Thor Lancelot Simon]

On Sat, Nov 23, 2013 at 12:59:04AM -0500, Mouse wrote:
>
> 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

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

[Daode]

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] 


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
  {
  RealConnx, 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
--- Begin Message ---
> 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.)

> 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

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

> 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   

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

[Mouse]

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

> 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

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

> 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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[David Holland]

On Thu, Nov 21, 2013 at 11:02:24PM -0500, Ken Hornstein wrote:
 > >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.

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

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

-- 
David A. Holland
dholl...@netbsd.org

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

[Dennis Ferguson]

On 22 Nov, 2013, at 03:49 , Rhialto  wrote:
> 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)

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

Dennis Ferguson

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

[Rhialto]

On Fri 22 Nov 2013 at 11:56:05 +0100, Martin Husemann wrote:
> On Thu, Nov 21, 2013 at 11:02:24PM -0500, Ken Hornstein 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.
> 
> 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 :-)

> Martin
-Olaf.
-- 
___ Olaf 'Rhialto' Seibert  -- The Doctor: No, 'eureka' is Greek for
\X/ rhialto/at/xs4all.nl-- 'this bath is too hot.'



pgpXMwYpxlbd8.pgp
Description: PGP signature

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

[Martin Husemann]

On Thu, Nov 21, 2013 at 11:02:24PM -0500, Ken Hornstein 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.

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

Martin

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

[Mouse]

>> 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 HTMLmo...@rodents-montreal.org
/ \ Email!   7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

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

[Ken Hornstein]

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

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

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

[David Holland]

On Thu, Nov 21, 2013 at 08:55:44AM -0500, Ken Hornstein wrote:
 > >On Wed, Nov 20, 2013 at 07:01:15PM -0500, Ken Hornstein wrote:
 > > > #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".

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

-- 
David A. Holland
dholl...@netbsd.org

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

[Alexander Nasonov]

matthew green wrote:
> 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

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

[David Holland]

On Thu, Nov 21, 2013 at 01:16:44AM +0100, Rhialto wrote:
 > 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  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.

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

-- 
David A. Holland
dholl...@netbsd.org

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

[David Holland]

On Wed, Nov 20, 2013 at 07:01:15PM -0500, Ken Hornstein wrote:
 > #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.

-- 
David A. Holland
dholl...@netbsd.org

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

[Ken Hornstein]

>I think it is actually 2 extra pointer deferences,

You're right, my apologies.

>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

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

[Dennis Ferguson]

On 20 Nov, 2013, at 16:01 , Ken Hornstein  wrote:
>> 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.

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.

> 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

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

[Rhialto]

On Wed 20 Nov 2013 at 15:32:20 -0800, Dennis Ferguson wrote:
> 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_Headwhich points to the first real node,
mlh_Tailwhich is always NULL
mlh_TailPredwhich 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_Headpoints to mlh_Tail
mlh_Tailis always NULL
mlh_TailPredpoints 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.
-- 
___ Olaf 'Rhialto' Seibert  -- The Doctor: No, 'eureka' is Greek for
\X/ rhialto/at/xs4all.nl-- 'this bath is too hot.'



pgpGoRV51t32L.pgp
Description: PGP signature

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

[Ken Hornstein]

>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

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

[Dennis Ferguson]

On 20 Nov, 2013, at 12:32 , Zhihao Yuan  wrote:
> On Wed, Nov 20, 2013 at 12:07 PM, Ken Hornstein  wrote:
>> 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?
> 
> 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

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

[Zhihao Yuan]

On Wed, Nov 20, 2013 at 12:07 PM, Ken Hornstein  wrote:
> 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?

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.

-- 
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___
4BSD -- http://4bsd.biz/

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

[Dennis Ferguson]

On 20 Nov, 2013, at 01:54 , matthew green  wrote:
> 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 ""
> 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

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

[Daode]

matthew green  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.0 +0100
  +++ queue.h   2013-11-20 20:55:33.0 +0100
  @@ -640,27 +640,46 @@ struct {
\
   #define QUEUEDEBUG_CIRCLEQ_POSTREMOVE(elm, field)
   #endif
   
  +#include 
   #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;  \
  -

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

[Matthew Orgass]

On 2013-11-20 m...@eterna.com.au wrote:


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

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

[Ken Hornstein]

>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

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 ""
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 -  1.55
+++ queue.h 20 Nov 2013 09:33:42 -
@@ -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((h