broken code only when optimized "-O2"

[Adrian Moreno <amorenoz@redhat.com>]

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