Problem report: Struct aliasing problem causes Thread_Ready_Chain corruption in 4.6.99.3

[Pavel Pisa]

Hello Joel and Thomas,

On Tuesday 21 November 2006 22:59, Joel Sherrill wrote:
> Thomas Doerfler (nt) wrote:
> > Joel,
> >
> > I am not convinced. I have looked at your patch, and I think it just
> > overlays two "Chain_Node" structures to the existing "Chain_Control"
> > structure, but as far as I see, all accesses to the Chain_Control are
> > still performed directly to the three pointers first/permanent_null/last
> > and since you did NOT change the accesses to Chain_Control, the aliasing
> > problem will still be there.
>
> Which version?  #1 or #2?
>
> You are right for version #1.  All it did was try to address permanent
> head/tail nodes.
>
> Version #2 put the current structure in an anonymous structure which
> should have
> improved the overlay.  But I didn't try to eliminate the use of
> first/last as you did.

I have spent some time thinking about problem.
I believe, that use of Joel's #2 union could work for 
"Permanent_Head". I think, that horror described
by Till Straumann does not apply there, because both
(direct pointers in unnamed union member and pointers
in the "Permanent_Head") are of same type and compiler
should assume, that these can point each to other
and that in the fact pointers of same type (Chain_Node **)
are used to access and modify pointer fields in both cases.

But I am convinced that "Permanent_Tail" solution is incorrect
for targets with 32-bit pointers but 64-bit structure alignments.
In the fact dereferencing of "permanent_null" on offset 4-bytes
and typecasting it to 8-bytes structure pointer is illegal in theory
but in practice layout would be reordered to be same as for
"Permanent_Head" if packed is not used. If packed is used, then
assignment to (Chain_Node *) is illegal.

The unnamed union and structure members are great feature
of many C compilers but not part of C99 standard.
Use of these would  outlaw ancient GCC versions (<=2.95.x)
for RTEMS compilation. Not problem for me, but it could be
problem for somebody else.

> > And as far as I understood, here we MAY run into a problem: For the
> > compiler, the operations done via the node_ptr have absolutely nothing
> > to do with the operations done via the "the_chain" pointer. The logic
> > behind this is as follows:
> >
> >   1.) node_ptr is of type "Chain_Node *".
> >   2.) the_chain is of type "Chain_Control *".
            the case #2 should inform compiler, that "Chain_Control *"
            contains "Chain_Node *" on beginning. There is no guarantee
            about the second the offseted "Chain_Node *". In the fact
            compiler can assume, that "permanent_null" cannot alias
            with "first" field due to alignment rules
> >   3.) Both data types are totally distinct
> >   4.) Strict type control makes sure, that any modification done using
...
> > I have the impression, that we ust tell the compiler, that Chain_Control
> > actually consists of two (or at least one and a half) Chain_Node
> > structures, and (!!!) that we are actually accessing these structures
> > when we work with Chain_Control (!!!). Therefore, in your patch, all
> > accesses that currently still use Chain_Control.first MUST be redirected
> > to Chain_Control.Permanent_Head.Node.next. Only then the compiler has
> > the knowledge that an access using a node_ptr MAY influence the elements
> > in Chain_Control that are acutally used.
> >
> > I have worked out a patch that implements this, I have also added two
> > macros _Chain_First(Chain_Control *) and _Chain_last(Chain_Control *) to
> > encapsulate all accesses to "first" and "last".

I like these.
I have actually started to write mail suggesting to add _Chain_First
and _Chain_Last to solve union use problems. But after more
thinking, I am getting to conclusion, that there is no good
solution for 3/2 of "Chain_Node" encapsulation.

> >> shared between the nodes), but maybe it is not SO important. In that
> >> case, Chain_Control might also be defined as follows:
> >>
> >> typedef union {
> >>   struct Chain_Node_struct head;
> >>   struct Chain_Node_struct tail;
> >> } Chain_Control;
> >>

I think, that your suggestion for 16 byte control structure
is the most right one for actual list functionality. Other
solution is to use same solution as Linux and Windows NT
utilizes. They use head consisting of only one "Chain_Node".
But this solution has no sentinel and each time when move
through list is performed check against equality with list
head (Chain_Control *) has to be performed.
Another solution is to abuse bit 0 of pointers to mark
sentinels. All RTEMS supported architectures perform alignment
to two bytes at least (probably except AVR), but checking
and setting of bit 0 would probably complicate some operations
a little. Not so much when I think about this little more.
But it would require significant cleanup. The direct access
to next and previous has to be disabled in such case.
New functions _Chain_Next and _Chain_Previous has to be used.
These would return pointer or NULL. But these changes could
help to cleanup code. Etc. It could be really well
optimized solution without memory space overhead.
May it be it worth to be tested one day.

Best wishes

               Pavel