public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/103964] New: [9/10/11/12 Regression] OVS miscompilation since r0-92313-g5006671f1aaa63cd
@ 2022-01-10 15:12 jakub at gcc dot gnu.org
  2022-01-10 15:18 ` [Bug tree-optimization/103964] " fw at gcc dot gnu.org
                   ` (13 more replies)
  0 siblings, 14 replies; 15+ messages in thread
From: jakub at gcc dot gnu.org @ 2022-01-10 15:12 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103964

            Bug ID: 103964
           Summary: [9/10/11/12 Regression] OVS miscompilation since
                    r0-92313-g5006671f1aaa63cd
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
  Target Milestone: ---

Following testcase is miscompiled e.g. with -g -Og -fno-strict-aliasing
starting with r0-92313-g5006671f1aaa63cd - this is a self-contained testcase
from https://gcc.gnu.org/pipermail/gcc-help/2021-December/141021.html

With current trunk and -g -Og -fno-strict-aliasing (-Og chosen as something
that does just a few optimizations), I see on current gcc trunk the fre1 pass
optimizing:
-  _69 = start.prev;
   # DEBUG list_ => NULL
-  last_49 = _69 + 18446744073709551552;
-  # DEBUG last => last_49
+  # DEBUG last => &MEM <struct ovs_list> [(void *)&start + -64B]
   # DEBUG BEGIN_STMT
-  printf ("first: %p \nlast: %p\n", first_47, last_49);
+  printf ("first: %p \nlast: %p\n", first_47, &MEM <struct ovs_list> [(void
*)&start + -64B]);

We have earlier:
  start.prev = &start;
  start.next = &start;
and .prev stores in between are:
  MEM[(struct ovs_list *)member_59 + 64B].prev = _48;
...
  MEM[(struct ovs_list *)pos_32 + 64B].prev = _15;
I bet the alias oracle assumes that pos_32, being an struct member pointer,
can't overwrite start.prev where start is much smaller than that (has just
struct ovs_list type).
That MEM[(struct ovs_list *)pos_32 + 64B].prev = _15; is actually what
overwrites start.prev.
  # pos_32 = PHI <pos_61(8), pos_62(10)>
and
  _6 = start.next;
  _7 = (long unsigned int) _6;
  _8 = _7 + 18446744073709551552;
  pos_61 = (struct member *) _8;
and
  _11 = pos_32->elem.next;
  _12 = (long unsigned int) _11;
  _13 = _12 + 18446744073709551552;
  pos_62 = (struct member *) _13;

If it wouldn't use uintptr_t in there, I'd say it is clearly UB, doing pointer
arithmetics out of bounds of the start object.  With uintptr_t it just
materializes a pointer known to point outside of the start object.
For -fstrict-aliasing, I think it is just fine to treat it as UB, for
-fno-strict-aliasing I don't know.
I'm afraid Linux kernel and various other projects that copied such
questionable code from it use it heavily.

/* How to build:

>> gcc -O2 -g -o example2 example2.c ^C
>> ./example2
start: 0x7ffc13ba2800
first: 0x1ba32f0
last: 0x7ffc13ba27c0
list is broken!
Start: 0x7ffc13ba2800. start->next: 0x1ba3330, start->next->next: 0x1ba3390,
start->prev: 0x1ba3390

>> gcc -g -o example2 example2.c
>> ./example2
start: 0x7ffd84d91660
first: 0x23b52f0
last: 0x23b5350

Same for clang.
*/

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

////////////////// from include/openvswitch/util.h //////////////////

#define INIT_CONTAINER(OBJECT, POINTER, MEMBER)                               
\
    ((OBJECT) = NULL, ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER))

#define OVS_TYPEOF(OBJECT) typeof(OBJECT)

#define OBJECT_OFFSETOF(OBJECT, MEMBER) offsetof(typeof(*(OBJECT)), MEMBER)

#define OBJECT_CONTAINING(POINTER, OBJECT, MEMBER)                            
\
    ((OVS_TYPEOF(OBJECT))(                                                    
\
        void*)((char*)(POINTER)-OBJECT_OFFSETOF(OBJECT, MEMBER)))

#define OBJECT_MEMBER(POINTER, OBJECT, MEMBER)                                
\
    ((OVS_TYPEOF(&POINTER->MEMBER))                                           
\
        ((uintptr_t) POINTER + OBJECT_OFFSETOF(POINTER, MEMBER)))

#define ASSIGN_CONTAINER(OBJECT, POINTER, MEMBER)                             
\
    ((OBJECT) = OBJECT_CONTAINING(POINTER, OBJECT, MEMBER), (void)0)

#define HMAP_FOR_EACH(NODE, MEMBER, HMAP)                                     
\
    HMAP_FOR_EACH_INIT(NODE, MEMBER, HMAP, (void)0)
#define HMAP_FOR_EACH_INIT(NODE, MEMBER, HMAP, ...)                           
\
    for (INIT_CONTAINER(NODE, hmap_first(HMAP), MEMBER), __VA_ARGS__;         
\
         (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) ||                   
\
         ((NODE = NULL), 0);                                                  
\
         ASSIGN_CONTAINER(NODE, hmap_next(HMAP, &(NODE)->MEMBER), MEMBER))

#define LIST_FOR_EACH(ITER, MEMBER, LIST)                                     
\
    for (INIT_CONTAINER(ITER, (LIST)->next, MEMBER);                          
\
         &(ITER)->MEMBER != (LIST);                                           
\
         ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.next, MEMBER))

////////////// from lib/list.c / include/openvswitch/list.h /////////////////

struct ovs_list {
    struct ovs_list* prev; /* Previous list element. */
    struct ovs_list* next; /* Next list element. */
};

static inline void ovs_list_init(struct ovs_list* list)
{
    list->next = list->prev = list;
}

static inline void ovs_list_insert(struct ovs_list* before,
                                   struct ovs_list* elem)
{
    elem->prev = before->prev;
    elem->next = before;
    before->prev->next = elem;
    before->prev = elem;
}

#define CONTAINER_OF(POINTER, STRUCT, MEMBER)                                 
\
    ((STRUCT*)(void*)((char*)(POINTER)-offsetof(STRUCT, MEMBER)))

#define CONST_CAST(TYPE, POINTER) ((TYPE)(POINTER))

static inline struct ovs_list* ovs_list_front(const struct ovs_list* list_)
{
    struct ovs_list* list = CONST_CAST(struct ovs_list*, list_);

    // ovs_assert(!ovs_list_is_empty(list));

    return list->next;
}

/* Returns the back element in 'list_'.
   Undefined behavior if 'list_' is empty. */
static inline struct ovs_list* ovs_list_back(const struct ovs_list* list_)
{
    struct ovs_list* list = CONST_CAST(struct ovs_list*, list_);

    // ovs_assert(!ovs_list_is_empty(list));

    return list->prev;
}

////////////////////////////////////////////////////////////////////////////////

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

int main()
{
    int i, ret = 0;
    struct member *member, *members[2];

    /*
     TESTED: If i create the struct ovs_list in the heap and
     change the rest of the program to use start instead of &start,
     the problem disappears

     struct ovs_list *start = malloc(sizeof (struct ovs_list));
     if (start) {
         memset(start, 0, sizeof (struct bond));
     }

    TESTED: If I create an entire struct member and I use it's embedded
ovs_list
     (ensuring we have enough stack space so that any pointer arithmetics will
    always fall into addressable area), the problem dissapears

     struct member sstart = {};
     struct ovs_list *start = &sstart.elem;

    */

    struct ovs_list start = {0};

    // Boilerplate initialization
    for (i = 0; i < 2; i++) {
        members[i] = malloc(sizeof(struct member));
        if (members[i]) {
            memset(members[i], 0, sizeof(struct member));
        }
    }

    // Set arbitrary order
    members[0]->order = 3;
    members[1]->order = 2;

    printf("start: %p\n", &start);
    ovs_list_init(&start);

    /* Original code.
    HMAP_FOR_EACH (member, hmap_node, &bond->members) {
       struct member *pos;
       LIST_FOR_EACH (pos, elem, &start) {
           if (member->order > pos->order) {
               break;
           }
       }
       //printf("Inserting member: %p\n", member);
       ovs_list_insert(&pos->elem, &member->elem);
    }
    What follows is the same code with the macros expanded.
    */

    for (i = 0; i < 2; i++) {
        struct member* pos;

        member = members[i];

        /* LIST_FOR_EACH (pos, elem, &start) {
         * 'char *' casts replaced with 'uintptr_t' to make clang also fail. */
        for (((pos) = ((void*)0),
            ((pos) = ((typeof(pos))(void*)((uintptr_t)((&start)->next) -
                                           __builtin_offsetof(struct member,
                                                              elem)))));
             &(pos)->elem != (&start);
             // Alternative ways to check:
             //(uintptr_t) pos + __builtin_offsetof(struct member, elem) !=
(uintptr_t)(&start);
             //OBJECT_MEMBER(pos, struct member, elem) != (&start);
             ((pos) = ((typeof(pos))(void*)((uintptr_t)((pos)->elem.next) -
                                            __builtin_offsetof(struct member,
                                                               elem))))) {
            if (member->order > pos->order) {
                break;
            }
        }

        // TESTED: If I add this printf, the problem disappears
        //printf("pos: %p\n", pos);

        // Original version of the code.  Doesn't work:
        ovs_list_insert(&pos->elem, &member->elem);

        // TESTED: This works:
        //ovs_list_insert((void *)((uintptr_t)pos + __builtin_offsetof(struct
member,elem)), &member->elem);
        // TESTED: This doesn't work:
        //ovs_list_insert((void *)((char *   )pos + __builtin_offsetof(struct
member,elem)), &member->elem);


        // TESTED: This also work:
        //ovs_list_insert((void *)((uintptr_t)pos + 64), &member->elem);
        // TESTED: This doesn't:
        //ovs_list_insert((void *)((char *   )pos + 64), &member->elem);

        // Just a prettier wrapper for __builtin_offsetof math.  Works:
        //ovs_list_insert(OBJECT_MEMBER(pos, struct member, elem),
&member->elem);
    }

    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 != members[0] && first != members[1]) ||
        (last != members[0] && last != members[1])) {
        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(members[0]);
    free(members[1]);
    return ret;
}

^ permalink raw reply	[flat|nested] 15+ messages in thread
end of thread, other threads:[~2022-01-11 17:57 UTC | newest]

Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-01-10 15:12 [Bug tree-optimization/103964] New: [9/10/11/12 Regression] OVS miscompilation since r0-92313-g5006671f1aaa63cd jakub at gcc dot gnu.org
2022-01-10 15:18 ` [Bug tree-optimization/103964] " fw at gcc dot gnu.org
2022-01-10 15:58 ` jakub at gcc dot gnu.org
2022-01-11  2:52 ` pinskia at gcc dot gnu.org
2022-01-11  8:15 ` rguenth at gcc dot gnu.org
2022-01-11  8:38 ` rguenth at gcc dot gnu.org
2022-01-11 11:19 ` i.maximets at ovn dot org
2022-01-11 12:11 ` jakub at gcc dot gnu.org
2022-01-11 13:58 ` i.maximets at ovn dot org
2022-01-11 14:06 ` rguenth at gcc dot gnu.org
2022-01-11 14:47 ` jakub at gcc dot gnu.org
2022-01-11 16:46 ` i.maximets at ovn dot org
2022-01-11 17:00 ` jakub at gcc dot gnu.org
2022-01-11 17:10 ` i.maximets at ovn dot org
2022-01-11 17:57 ` jakub at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).