[llvm-dev] broken C code only when optimized "-O2"

[Dimitry Andric via llvm-dev]

On 21 Dec 2021, at 17:30, Adrian Moreno via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> 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 clang, gcc 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.
> * If I add -fsanitize=undefined the problem disappears!

Not for me:

% clang -g -fsanitize=undefined -I/Users/dim/tmp/vswitch/foo/include example.c -o example -L/Users/dim/tmp/vswitch/foo/lib -lopenvswitch

% ./example
start: 0x16ee6f618
example.c:78:5: runtime error: applying zero offset to null pointer
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior example.c:78:5 in
example.c:78:5: runtime error: applying zero offset to null pointer
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior example.c:78:5 in
first: 0x600003200270
last: 0x6000032002a0

It looks like the HMAP_FOR_EACH() macro uses null pointer arithmetic. The problem appears to be in https://github.com/openvswitch/ovs/blob/master/include/openvswitch/util.h#L94 :

/* Given OBJECT of type pointer-to-structure, expands to the offset of MEMBER
 * within an instance of the structure.
 *
 * The GCC-specific version avoids the technicality of undefined behavior if
 * OBJECT is null, invalid, or not yet initialized.  This makes some static
 * checkers (like Coverity) happier.  But the non-GCC version does not actually
 * dereference any pointer, so it would be surprising for it to cause any
 * problems in practice.
 */
#ifdef __GNUC__
#define OBJECT_OFFSETOF(OBJECT, MEMBER) offsetof(typeof(*(OBJECT)), MEMBER)
#else
#define OBJECT_OFFSETOF(OBJECT, MEMBER) \
    ((char *) &(OBJECT)->MEMBER - (char *) (OBJECT))
#endif

The comment is incorrect here, because dereferencing a null pointer, as done in *(OBJECT), is definitely undefined behavior.

-Dimitry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 223 bytes
Desc: Message signed with OpenPGP
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211221/5ac63076/attachment.sig>