Problem report: Struct aliasing problem causes Thread_Ready_Chain corruption in 4.6.99.3

[Pavel Pisa]

Hello Thomas and others,

On Tuesday 28 November 2006 18:35, Thomas Doerfler wrote:
> So, I think I could prove that the current GCC miss-interprets and
> mis-optimizes RTEMS chain code in a rather subtile way.
> The current code/compiler adaptation is broken. And we have just
> analyzed ONE function.
>
> by the way: my patch (overlaying Chain_Control with two Chain_node
> structures and accessing Chain_Control through these structures) is not
> yet clean enough to be integrated into RTEMS, because, as Pavel has
> pointed out, it will have alignment problems on some machines.

I have thought a little more about the issue and I do not see
ideal solution still. What I like on Thomas's patch is little
step towards better separations and hidding of chain internals.
I would be happy, if the _Chain_Last / _Chain_First could go
into both, 4.7 and HEAD. This is change, which should not have any impact
on generated code and allows to to more about this problem in future.

As for union + 2 structures overlay, I think, that it is the
best solution if structure fields alignment could be guaranteed.
I have some feeling, that new ARM EABI, which is proposed future
for Linux and other ARM systems and is slowly getting into use,
could be example of incompatibility with proposal. I have not
toolchain for it there built yet, so I cannot test it and be sure
about my prediction. It should not be problem to ask somebody to do check.
But I do not expect, that this new ABI would be used with RTEMS
anytime soon. I do not expect, that any architecture
tools used with RTEMS at this time exhibit this problem.

So I have next suggestion. Apply Thomas's patch and include
attached test in the config.ac . The test checks, that fields
alignment is as expected and that resulting code would
behave correctly.
It should be tested by AC_LINK_IFELSE for target system tools.
Unfortunately this requires compilation and linking, because
AC_COMPILE_IFELSE would not find missing function.

This tests ensures, that RTEMS would not be misscompiled
even for future (yet unknown/unsupported) platform.
It could be used to report error in such case.

Even if patch is included, I am not biased much to any
side in the case of question to add or not to add "-fno-strict-aliasing".
To add is probably better choice for 4.7 to be on safe side.

I see next alternatives in the RTEMS chain problem solution for future
consideration (not 4.7 material in any case):

 1) use Thomas's solution and do not speculate on its possible
    incompatibility until there is real incompatibility
    reported for some future RTEMS architecture.

 2) rewrite lists to use bit 0. for chain end markup.
    This demands less memory than actual solution, it allows
    to have Chain_Control typedefed to Chain_Node_struct.
    It allows to detect that there is no more items on the list
    with one less indirection then actual solution requires.
    It requires some (Chain_Node*)((uintptr_t)((x)->next)&~1)
    in the lists enqueue and dequeue code.
    It is incompatible with architectures, which do not align
    structures to even addresses. I expect, that only architecture
    supported by RTEMS, which has this problem, is AVR.

 3) rewrite lists to Linux kernel style. This use again
    head same as node. This solution has one potential problem,
    that lists do not provide end markup. They allow dequeue
    without list head knowledge, but for enqueue and iterations
    corresponding list head must be known and provided.
    If node is moved to another list during iteration,
    future iteration results in disaster.

Best wishes

            Pavel

--------------------------------------------------------------
#ifndef MY_OFFSETOF
/* offset of structure field */
#define MY_OFFSETOF(_type,_member) \
                ((int)&(((_type*)0)->_member))
#endif /*MY_OFFSET*/

typedef struct Chain_Node_struct Chain_Node;

struct Chain_Node_struct {
  Chain_Node *next;
  Chain_Node *previous;
};

typedef union {
  struct {
    Chain_Node head_node;
    Chain_Node *dummy_head;
  } head_of_chain;
  struct {
    Chain_Node *dummy_tail;
    /** This is the tail of the chain */
    Chain_Node tail_node;
  } tail_of_chain;
} Chain_Control;


void architecture_structure_fields_alignment_incompatible_with_rtems(void);

int main(void)
{
  if(MY_OFFSETOF(Chain_Control,head_of_chain.head_node.previous) !=
     MY_OFFSETOF(Chain_Control,tail_of_chain.tail_node.next))
       architecture_structure_fields_alignment_incompatible_with_rtems();

  return 0;
}
--------------------------------------------------------------

Shorter test version

--------------------------------------------------------------
typedef union {
  struct {
    struct {void *a,*b;} s;
    void *d;
  } x;
  struct {
    void *d;
    struct {void *b, *c;} s;
  } y;
} u;

int main(void)
{
  if( ((int)&(((u*)0)->x.s.b)) !=
      ((int)&(((u*)0)->y.s.b)) )
       architecture_structure_fields_alignment_incompatible_with_rtems();
  return 0;
}
--------------------------------------------------------------