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