* broken code only when optimized "-O2"
@ 2021-12-21 15:40 Adrian Moreno
2021-12-21 16:05 ` Stefan Ring
2021-12-22 15:32 ` LIU Hao
0 siblings, 2 replies; 11+ messages in thread
From: Adrian Moreno @ 2021-12-21 15:40 UTC (permalink / raw)
To: gcc-help
[-- 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;
}
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 15:40 broken code only when optimized "-O2" Adrian Moreno
@ 2021-12-21 16:05 ` Stefan Ring
2021-12-21 16:13 ` Adrian Moreno
2021-12-21 17:05 ` David Brown
2021-12-22 15:32 ` LIU Hao
1 sibling, 2 replies; 11+ messages in thread
From: Stefan Ring @ 2021-12-21 16:05 UTC (permalink / raw)
To: Adrian Moreno; +Cc: gcc-help
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 16:05 ` Stefan Ring
@ 2021-12-21 16:13 ` Adrian Moreno
2021-12-21 16:39 ` Segher Boessenkool
2021-12-21 17:05 ` David Brown
1 sibling, 1 reply; 11+ messages in thread
From: Adrian Moreno @ 2021-12-21 16:13 UTC (permalink / raw)
To: Stefan Ring; +Cc: gcc-help
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 16:13 ` Adrian Moreno
@ 2021-12-21 16:39 ` Segher Boessenkool
0 siblings, 0 replies; 11+ messages in thread
From: Segher Boessenkool @ 2021-12-21 16:39 UTC (permalink / raw)
To: Adrian Moreno; +Cc: Stefan Ring, gcc-help
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 16:05 ` Stefan Ring
2021-12-21 16:13 ` Adrian Moreno
@ 2021-12-21 17:05 ` David Brown
2021-12-22 9:24 ` Adrian Moreno
1 sibling, 1 reply; 11+ messages in thread
From: David Brown @ 2021-12-21 17:05 UTC (permalink / raw)
To: Stefan Ring, Adrian Moreno; +Cc: gcc-help
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 17:05 ` David Brown
@ 2021-12-22 9:24 ` Adrian Moreno
2021-12-22 10:27 ` Florian Weimer
0 siblings, 1 reply; 11+ messages in thread
From: Adrian Moreno @ 2021-12-22 9:24 UTC (permalink / raw)
To: David Brown, Stefan Ring; +Cc: gcc-help
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-22 9:24 ` Adrian Moreno
@ 2021-12-22 10:27 ` Florian Weimer
2021-12-22 10:34 ` Adrian Moreno
0 siblings, 1 reply; 11+ messages in thread
From: Florian Weimer @ 2021-12-22 10:27 UTC (permalink / raw)
To: Adrian Moreno via Gcc-help; +Cc: David Brown, Stefan Ring, Adrian Moreno
* 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-22 10:27 ` Florian Weimer
@ 2021-12-22 10:34 ` Adrian Moreno
2021-12-22 10:36 ` Xi Ruoyao
0 siblings, 1 reply; 11+ messages in thread
From: Adrian Moreno @ 2021-12-22 10:34 UTC (permalink / raw)
To: Florian Weimer, Adrian Moreno via Gcc-help; +Cc: David Brown, Stefan Ring
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-22 10:34 ` Adrian Moreno
@ 2021-12-22 10:36 ` Xi Ruoyao
2021-12-22 16:05 ` Adrian Moreno
0 siblings, 1 reply; 11+ messages in thread
From: Xi Ruoyao @ 2021-12-22 10:36 UTC (permalink / raw)
To: Adrian Moreno, Florian Weimer, Adrian Moreno via Gcc-help; +Cc: David Brown
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-21 15:40 broken code only when optimized "-O2" Adrian Moreno
2021-12-21 16:05 ` Stefan Ring
@ 2021-12-22 15:32 ` LIU Hao
1 sibling, 0 replies; 11+ messages in thread
From: LIU Hao @ 2021-12-22 15:32 UTC (permalink / raw)
To: Adrian Moreno, gcc-help
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: broken code only when optimized "-O2"
2021-12-22 10:36 ` Xi Ruoyao
@ 2021-12-22 16:05 ` Adrian Moreno
0 siblings, 0 replies; 11+ messages in thread
From: Adrian Moreno @ 2021-12-22 16:05 UTC (permalink / raw)
To: Xi Ruoyao, Florian Weimer, Adrian Moreno via Gcc-help; +Cc: David Brown
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2021-12-22 16:05 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-12-21 15:40 broken code only when optimized "-O2" Adrian Moreno
2021-12-21 16:05 ` Stefan Ring
2021-12-21 16:13 ` Adrian Moreno
2021-12-21 16:39 ` Segher Boessenkool
2021-12-21 17:05 ` David Brown
2021-12-22 9:24 ` Adrian Moreno
2021-12-22 10:27 ` Florian Weimer
2021-12-22 10:34 ` Adrian Moreno
2021-12-22 10:36 ` Xi Ruoyao
2021-12-22 16:05 ` Adrian Moreno
2021-12-22 15:32 ` LIU Hao
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).