broken code only when optimized "-O2"

broken code only when optimized "-O2"

[Adrian Moreno]

[-- Attachment #1: Type: text/plain, Size: 2937 bytes --]

Hello,

I need some help understanding what might be wrong with a piece of code from the 
openvswitch project. By ${subject} I'm not suggesting there's a problem in gcc, 
clang also shows the same behavior so it's likely our code is broken. I am 
kindly asking for help to understand/troubleshoot the problem.

Summary: It seems that certain interaction between two main openvswitch data 
structures, when optimized ("-O2 -flto=auto") is broken.
The two data structures are:

hmap: https://github.com/openvswitch/ovs/blob/master/include/openvswitch/hmap.h
list: https://github.com/openvswitch/ovs/blob/master/include/openvswitch/list.h

I've reproduced the problem outside of openvswitch daemon using a short C 
program (attached)

Code snippet:

struct bond {
     struct hmap members;
};

struct member {
     struct hmap_node hmap_node;
     int order;
     struct ovs_list elem;
};

int main() {
     int ret = 0;
     struct member *member, *member1, *member2;
     struct bond *bond;
     struct ovs_list start = {0};

     bond = malloc(sizeof *bond);
     memset(bond, 0, sizeof (struct bond));
     hmap_init(&bond->members);

     member1 = malloc(sizeof *member1);
     member2 = malloc(sizeof *member2);
     memset(member1, 0, sizeof (struct member));
     memset(member2, 0, sizeof (struct member));

     member1->order = 3;
     member2->order = 2;

     hmap_insert(&bond->members, &member1->hmap_node, (uint32_t)(uintptr_t)member1);
     hmap_insert(&bond->members, &member2->hmap_node, (uint32_t)(uintptr_t)member2);

     ovs_list_init(&start);
     HMAP_FOR_EACH (member, hmap_node, &bond->members) {
        /*
         * Insert member in start (sorted)
         * */
        struct member *pos;
        LIST_FOR_EACH (pos, elem, &start) {
            if (member->order > pos->order) {
                break;
            }
        }
        // TESTED: If I add this printf, the problem disappears
        //printf("Inserting member: %p\n", member);
        ovs_list_insert(&pos->elem, &member->elem);
     }

     /* I've inserted two members into the 'start' list.
      *   first and last have to be either member1 or member2
      * */
     if ((first != member1 && first != member2) || (last != member1 && last != 
member2)) {
         printf("list is broken!\n");
     }

}


What I know for now:
* -fno-strict-aliasing does not fix it
* Only happens with "-O2 -flto=auto"
* If I define 'ovs_list *start' and change the code to use the pointer directly 
and not '&start' the problem disappears. It seems that the LIST_FOR_EACH macros 
prefer an lvalue rather than "&" but I don't get why.
* I'm not able to reproduce without using hmap _and_ ovs_list.
* If I add a compiler barrier (or a call to an external function) after the 
loop, the problem disappears (e.g printf), the problem disappears.

I'd really appreciate any hint or idea to try to understand this problem.

Thanks in advanced.
-- 
Adrián Moreno

[-- Attachment #2: example.c --]
[-- Type: text/x-csrc, Size: 3848 bytes --]

// Reproducer of https://bugzilla.redhat.com/show_bug.cgi?id=2014942
// How to build:
//   Build & install openvswitch
//      git clone https://github.com/openvswitch/ovs
//      cd ovs
//      ./boot.sh && ./configure && make && sudo make install
//   Build this program as:
//      export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig
//      gcc `pkg-config --libs libopenvswitch --static` $CFLAGS -lssl -lcrypto -lcap-ng -o example example.c /usr/local/lib/libopenvswitch.a
//
//   Test:
//   export CFLAGS="-O0 -g"
//   The program runs successfully
//
//   export CFLAGS="-O2 -flto=auto -g"
//   The program fails
//

#include <openvswitch/util.h>
#include <openvswitch/list.h>
#include <openvswitch/hmap.h>
#include <openvswitch/shash.h>

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

struct bond {
    struct hmap members;
};

struct member {
    struct hmap_node hmap_node;
    int order;
    struct ovs_list elem;
};

int main() {
    int ret = 0;
    struct member *member, *member1, *member2;
    struct bond *bond;
    // TESTED: If i create the struct in the heap:
    // struct ovs_list *startp;
    // startp = malloc(sizeof *startp);
    //
    //     TEST 1: If I use start as a struct ovs_list and &start in the rest of the
    //     code, the problem still happens
    //     TEST 2: If I use start as a struct ovs_list* and change the rest of
    //     the code to use start directly (not &start), the problem disappears
    // struct ovs_list start = *startp;


    // TESTED: Same as before but stack allocation
    // If I use a pointer to a stack-allocated ovs_list and change the resto of
    // the code to use start directly (not &start), the problem disappears
    //struct ovs_list sstart;
    //struct ovs_list start = &start;

    struct ovs_list start = {0};

    bond = malloc(sizeof *bond);
    memset(bond, 0, sizeof (struct bond));
    hmap_init(&bond->members);

    member1 = malloc(sizeof *member1);
    member2 = malloc(sizeof *member2);
    memset(member1, 0, sizeof (struct member));
    memset(member2, 0, sizeof (struct member));
    member1->order = 3;
    member2->order = 2;

    hmap_insert(&bond->members, &member1->hmap_node, (uint32_t)(uintptr_t)member1);
    hmap_insert(&bond->members, &member2->hmap_node, (uint32_t)(uintptr_t)member2);

    printf("start: %p\n", &start);
    ovs_list_init(&start);
    HMAP_FOR_EACH (member, hmap_node, &bond->members) {
       /*
        * Insert member in start (sorted)
        * */
       struct member *pos;
       LIST_FOR_EACH (pos, elem, &start) {
           if (member->order > pos->order) {
               break;
           }
       }
       // TESTED: If I add this printf, the problem disappears
       //printf("Inserting member: %p\n", member);
       ovs_list_insert(&pos->elem, &member->elem);
    }

    // TESTED: If, instead of using an hmap to iterate through bond->members, I add them
    // one by one, the problem disappears:
    //insert_ordered(&start, member1);
    //insert_ordered(&start, member2);

    struct member *first = CONTAINER_OF(ovs_list_front(&start), struct member, elem);
    struct member *last = CONTAINER_OF(ovs_list_back(&start), struct member, elem);

    printf("first: %p \nlast: %p\n", first, last);
    /* I've inserted two members into the 'start' list.
     *   first and last have to be either member1 or member2
     * */
    if ((first != member1 && first != member2) || (last != member1 && last != member2)) {
        printf("list is broken!\n");
        printf("Start: %p. start->next: %p, start->next->next: %p, start->prev: %p\n",
               &start, start.next, start.next->next, start.prev);
        ret = 1;
        goto out;

    }

out:
    // cleanup
    free(member1);
    free(member2);
    hmap_destroy(&bond->members);
    free(bond);
    return ret;
}

Re: broken code only when optimized "-O2"

[Stefan Ring]

On Tue, Dec 21, 2021 at 4:40 PM Adrian Moreno via Gcc-help
<gcc-help@gcc.gnu.org> wrote:
>
> I'd really appreciate any hint or idea to try to understand this problem.

I guess the compiler doesn't like the dereferencing of uninitialized
pointers (in the sizeof expressions). I am not 100% sure that this
counts as dereferencing, but I would assume so. Because of this the
compiler will be free to behave however it likes to.

Re: broken code only when optimized "-O2"

[Adrian Moreno]

Hi Stefan,

On 12/21/21 17:05, Stefan Ring wrote:
> On Tue, Dec 21, 2021 at 4:40 PM Adrian Moreno via Gcc-help
> <gcc-help@gcc.gnu.org> wrote:
>>
>> I'd really appreciate any hint or idea to try to understand this problem.
> 
> I guess the compiler doesn't like the dereferencing of uninitialized
> pointers (in the sizeof expressions). I am not 100% sure that this
> counts as dereferencing, but I would assume so. Because of this the
> compiler will be free to behave however it likes to.
> 

I agree that doesn't look good. Replacing them by sizeof (struct ___) 
expressions does not change the behavior though.

Thanks
-- 
Adrián Moreno

Re: broken code only when optimized "-O2"

[Segher Boessenkool]

On Tue, Dec 21, 2021 at 05:13:08PM +0100, Adrian Moreno via Gcc-help wrote:
> On 12/21/21 17:05, Stefan Ring wrote:
> >On Tue, Dec 21, 2021 at 4:40 PM Adrian Moreno via Gcc-help
> ><gcc-help@gcc.gnu.org> wrote:
> >>
> >>I'd really appreciate any hint or idea to try to understand this problem.
> >
> >I guess the compiler doesn't like the dereferencing of uninitialized
> >pointers (in the sizeof expressions). I am not 100% sure that this
> >counts as dereferencing, but I would assume so. Because of this the
> >compiler will be free to behave however it likes to.
> 
> I agree that doesn't look good. Replacing them by sizeof (struct ___) 
> expressions does not change the behavior though.

As required by C.  6.3.2.1/2:
  Except when it is the operand of the sizeof operator, [...], an lvalue
  that does not have array type is converted to the value stored in the
  designated object (and is no longer an lvalue); this is called lvalue
  conversion.

There is no dereferencing.


Segher

Re: broken code only when optimized "-O2"

[David Brown]

On 21/12/2021 17:05, Stefan Ring via Gcc-help wrote:
> On Tue, Dec 21, 2021 at 4:40 PM Adrian Moreno via Gcc-help
> <gcc-help@gcc.gnu.org> wrote:
>>
>> I'd really appreciate any hint or idea to try to understand this problem.
> 
> I guess the compiler doesn't like the dereferencing of uninitialized
> pointers (in the sizeof expressions). I am not 100% sure that this
> counts as dereferencing, but I would assume so. Because of this the
> compiler will be free to behave however it likes to.
> 

The operand of a sizeof expression is not evaluated (unless it is a
VLA).  So there is no problem with the "member1 = malloc(sizeof
*member1);" lines.  (Which is fortunate, because it is a very common idiom!)

I think the next step would be to start pulling in some of the
definitions for the various macros here, and then trying to reduce the
code further to get a smaller test case.

Re: broken code only when optimized "-O2"

[Adrian Moreno]

On 12/21/21 18:05, David Brown wrote:
> On 21/12/2021 17:05, Stefan Ring via Gcc-help wrote:
>> On Tue, Dec 21, 2021 at 4:40 PM Adrian Moreno via Gcc-help
>> <gcc-help@gcc.gnu.org> wrote:
>>>
>>> I'd really appreciate any hint or idea to try to understand this problem.
>>
>> I guess the compiler doesn't like the dereferencing of uninitialized
>> pointers (in the sizeof expressions). I am not 100% sure that this
>> counts as dereferencing, but I would assume so. Because of this the
>> compiler will be free to behave however it likes to.
>>
> 
> The operand of a sizeof expression is not evaluated (unless it is a
> VLA).  So there is no problem with the "member1 = malloc(sizeof
> *member1);" lines.  (Which is fortunate, because it is a very common idiom!)
> 
> I think the next step would be to start pulling in some of the
> definitions for the various macros here, and then trying to reduce the
> code further to get a smaller test case.
> 

Yes, that's the road I'm taking. Thanks for the suggestion.

One of the things that originally felt smelly was that the fact that the macros 
that iterate the list elements assume the "struct ovs_list" element is embedded 
into another "struct member":

struct member *pos = 0;

for ((((pos) = ((struct member *) (void *) ((uintptr_t)(void *)((&start)->next) 
- __builtin_offsetof (struct member, elem)))));
      &(pos)->elem != (&start);
      ((pos) = ((struct member *) (void *) ((uintptr_t)(void 
*)((pos)->elem.next) - __builtin_offsetof (struct member , elem)
)))) {
    [... use pos ]

however, the beginning of the list is a "struct ovs_list" defined in the stack 
and not embedded into a "struct member".

Therefore, "(&start)->next - __builtin_offsetof (struct member, elem)" actually 
points to somewhere in the stack that contains who knows what. (Note: initially 
start->next = start)

In fact, if I make the struct offsets zero:

struct member {
     struct ovs_list elem;
     [ ... ]
     int order;
};

... the code works. However if I use:

struct member {
     int padding[10];
     struct ovs_list elem;
     [ ... ]
     int order;
};

... the code fails.

Does anything of what I'm saying make sense so far?

If the code inside the loop just made use of "pos" through "(&pos->elem)" then 
the compiler could(?) be ok with it but the loop actually contains:
            if (member->order > pos->order) {
                break;
            }

So here I do not know what the compiler would think about "pos" if it happens to 
point to some invalid stack address.

Thanks for the help.

-- 
Adrián Moreno

Re: broken code only when optimized "-O2"

[Florian Weimer]

* Adrian Moreno via Gcc-help:

> So here I do not know what the compiler would think about "pos" if it
> happens to point to some invalid stack address.

In such cases, the compiler typically assumes that the code in question
is never executed.  This means that the comparison does not need to be
performed, among other things.

Thanks,
Florian

Re: broken code only when optimized "-O2"

[Adrian Moreno]

On 12/22/21 11:27, Florian Weimer wrote:
> * Adrian Moreno via Gcc-help:
> 
>> So here I do not know what the compiler would think about "pos" if it
>> happens to point to some invalid stack address.
> 
> In such cases, the compiler typically assumes that the code in question
> is never executed.  This means that the comparison does not need to be
> performed, among other things.
> 

So it wouldn't cause undefined behavior?

Thanks.
-- 
Adrián Moreno

Re: broken code only when optimized "-O2"

[Xi Ruoyao]

On Wed, 2021-12-22 at 11:34 +0100, Adrian Moreno via Gcc-help wrote:
> 
> 
> On 12/22/21 11:27, Florian Weimer wrote:
> > * Adrian Moreno via Gcc-help:
> > 
> > > So here I do not know what the compiler would think about "pos" if
> > > it
> > > happens to point to some invalid stack address.
> > 
> > In such cases, the compiler typically assumes that the code in
> > question
> > is never executed.  This means that the comparison does not need to
> > be
> > performed, among other things.
> > 
> 
> So it wouldn't cause undefined behavior?

It *is* undefined behavior, and the compiler can remove any execution
paths which will eventually hit an undefined behavior.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University

Re: broken code only when optimized "-O2"

[LIU Hao]

[-- Attachment #1.1: Type: text/plain, Size: 757 bytes --]

在 2021-12-21 23:40, Adrian Moreno via Gcc-help 写道:
> Hello,
> 
> I need some help understanding what might be wrong with a piece of code from the openvswitch 
> project. By ${subject} I'm not suggesting there's a problem in gcc, clang also shows the same 
> behavior so it's likely our code is broken. I am kindly asking for help to understand/troubleshoot 
> the problem.
> 

The typical approach to discovering such issues is to use address sanitizer [1] or valgrind [2]. The 
former is usually recommended. Optimization is not necessarily enabled.


[1] https://gcc.gnu.org/onlinedocs/gcc/Instrumentation-Options.html#index-fsanitize_003daddress
[2] https://valgrind.org/docs/manual/quick-start.html


-- 
Best regards,
LIU Hao

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 840 bytes --]

Re: broken code only when optimized "-O2"

[Adrian Moreno]

On 12/22/21 11:36, Xi Ruoyao wrote:
> On Wed, 2021-12-22 at 11:34 +0100, Adrian Moreno via Gcc-help wrote:
>>
>>
>> On 12/22/21 11:27, Florian Weimer wrote:
>>> * Adrian Moreno via Gcc-help:
>>>
>>>> So here I do not know what the compiler would think about "pos" if
>>>> it
>>>> happens to point to some invalid stack address.
>>>
>>> In such cases, the compiler typically assumes that the code in
>>> question
>>> is never executed.  This means that the comparison does not need to
>>> be
>>> performed, among other things.
>>>
>>
>> So it wouldn't cause undefined behavior?
> 
> It *is* undefined behavior, and the compiler can remove any execution
> paths which will eventually hit an undefined behavior.
> 

Thanks for confirming.

-- 
Adrián Moreno