Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1559350 > unrolled thread

llist code relies on undefined behaviour, upsets llvm/clang

Back to article view | Back to linux.kernel

Contents

  llist code relies on undefined behaviour, upsets llvm/clang Anton Blanchard <anton@samba.org> - 2017-01-15 22:40 +0100
    Re: llist code relies on undefined behaviour, upsets llvm/clang Peter Zijlstra <peterz@infradead.org> - 2017-01-16 10:10 +0100
      Re: llist code relies on undefined behaviour, upsets llvm/clang Anton Blanchard <anton@samba.org> - 2017-01-16 12:50 +0100
        Re: llist code relies on undefined behaviour, upsets llvm/clang Peter Zijlstra <peterz@infradead.org> - 2017-01-16 14:00 +0100
          Re: llist code relies on undefined behaviour, upsets llvm/clang Andrey Ryabinin <ryabinin.a.a@gmail.com> - 2017-01-16 14:10 +0100
    RE: llist code relies on undefined behaviour, upsets llvm/clang David Laight <David.Laight@ACULAB.COM> - 2017-01-16 15:40 +0100
      Re: llist code relies on undefined behaviour, upsets llvm/clang Peter Zijlstra <peterz@infradead.org> - 2017-01-16 17:30 +0100

#1559350 — llist code relies on undefined behaviour, upsets llvm/clang

Hi,

I was debugging a hang on a ppc64le kernel built with clang, and it
looks to be undefined behaviour with pointer wrapping in the llist code.

A test case is below. llist_for_each_entry() does container_of() on a
NULL pointer, which wraps our pointer negative, then adds the same
offset back in and expects to get back to NULL. Unfortunately clang
decides that this can never be NULL and optimises it into an infinite
loop.

Build with -DFIX, such that the llist_node has a zero offset from the
start of the struct, and things work.

Is anyone other than ppc64le building kernels with llvm/clang these
days? This should reproduce on ARM64 and x86-64.

Anton
--

#include <stdio.h>

#define __compiler_offsetof(a, b)                                       \
        __builtin_offsetof(a, b)

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)  __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)
#endif

struct llist_node {
        struct llist_node *next;
};

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

#define llist_entry(ptr, type, member)          \
        container_of(ptr, type, member)

#define llist_for_each_entry(pos, node, member)                         \
        for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
             &(pos)->member != NULL;                                    \
             (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))

struct foo {
#ifndef FIX
	unsigned long a;
#endif
	struct llist_node ll;
};

void working(void);

struct llist_node *ptr;

void bar(void)
{
	struct foo *f;

	llist_for_each_entry(f, ptr, ll) {
	}

	working();
}

[toc] | [next] | [standalone]

#1559528

On Mon, Jan 16, 2017 at 08:36:00AM +1100, Anton Blanchard wrote:
> Hi,
> 
> I was debugging a hang on a ppc64le kernel built with clang, and it
> looks to be undefined behaviour with pointer wrapping in the llist code.
> 
> A test case is below. llist_for_each_entry() does container_of() on a
> NULL pointer, which wraps our pointer negative, then adds the same
> offset back in and expects to get back to NULL. Unfortunately clang
> decides that this can never be NULL and optimises it into an infinite
> loop.
> 
> Build with -DFIX, such that the llist_node has a zero offset from the
> start of the struct, and things work.
> 
> Is anyone other than ppc64le building kernels with llvm/clang these
> days? This should reproduce on ARM64 and x86-64.

Last I checked I couldn't build a x86_64 kernel with llvm. So no, not
something I've ever ran into.


Also, I would argue that this is broken in llvm, the kernel very much
relies on things like this all over the place. Sure, we're way outside
of what the C language spec says, but who bloody cares ;-)

If llvm wants to compile the kernel, it needs to learn the C dialect the
kernel uses.

[toc] | [prev] | [next] | [standalone]

#1559663

Hi Peter,

> Last I checked I couldn't build a x86_64 kernel with llvm. So no, not
> something I've ever ran into.
> 
> Also, I would argue that this is broken in llvm, the kernel very much
> relies on things like this all over the place. Sure, we're way outside
> of what the C language spec says, but who bloody cares ;-)

True, but is there anything preventing gcc from implementing this
optimisation in the future? If we are relying on undefined behaviour we
should have a -fno-strict-* option to cover it.

> If llvm wants to compile the kernel, it needs to learn the C dialect
> the kernel uses.

LLVM has done that before (eg adding -fno-strict-overflow). I don't
think that option covers this case however.

Anton

[toc] | [prev] | [next] | [standalone]

#1559698

On Mon, Jan 16, 2017 at 10:42:29PM +1100, Anton Blanchard wrote:
> Hi Peter,
> 
> > Last I checked I couldn't build a x86_64 kernel with llvm. So no, not
> > something I've ever ran into.
> > 
> > Also, I would argue that this is broken in llvm, the kernel very much
> > relies on things like this all over the place. Sure, we're way outside
> > of what the C language spec says, but who bloody cares ;-)
> 
> True, but is there anything preventing gcc from implementing this
> optimisation in the future? If we are relying on undefined behaviour we
> should have a -fno-strict-* option to cover it.
> 
> > If llvm wants to compile the kernel, it needs to learn the C dialect
> > the kernel uses.
> 
> LLVM has done that before (eg adding -fno-strict-overflow). I don't
> think that option covers this case however.

Our comment there states:

# disable invalid "can't wrap" optimizations for signed / pointers
KBUILD_CFLAGS   += $(call cc-option,-fno-strict-overflow)

So this option should apply to pointer arithmetic, therefore I would
expect -fno-strict-overflow to actually apply here, or am I missing
something?

[toc] | [prev] | [next] | [standalone]

#1559702

2017-01-16 15:53 GMT+03:00 Peter Zijlstra <peterz@infradead.org>:
> On Mon, Jan 16, 2017 at 10:42:29PM +1100, Anton Blanchard wrote:
>> Hi Peter,
>>
>> > Last I checked I couldn't build a x86_64 kernel with llvm. So no, not
>> > something I've ever ran into.
>> >
>> > Also, I would argue that this is broken in llvm, the kernel very much
>> > relies on things like this all over the place. Sure, we're way outside
>> > of what the C language spec says, but who bloody cares ;-)
>>
>> True, but is there anything preventing gcc from implementing this
>> optimisation in the future? If we are relying on undefined behaviour we
>> should have a -fno-strict-* option to cover it.
>>
>> > If llvm wants to compile the kernel, it needs to learn the C dialect
>> > the kernel uses.
>>
>> LLVM has done that before (eg adding -fno-strict-overflow). I don't
>> think that option covers this case however.
>
> Our comment there states:
>
> # disable invalid "can't wrap" optimizations for signed / pointers
> KBUILD_CFLAGS   += $(call cc-option,-fno-strict-overflow)
>
> So this option should apply to pointer arithmetic, therefore I would
> expect -fno-strict-overflow to actually apply here, or am I missing
> something?

That case is null pointer check optimization.  '->member' has non-zero
offset in struct, so LLVM assumes that pos->member != NULL
and optimize away this check.
LLVM/clang currently doesn't have -fno-delete-null-pointer-checks

[toc] | [prev] | [next] | [standalone]

#1559793

From: Anton Blanchard
> Sent: 15 January 2017 21:36
> I was debugging a hang on a ppc64le kernel built with clang, and it
> looks to be undefined behaviour with pointer wrapping in the llist code.
> 
> A test case is below. llist_for_each_entry() does container_of() on a
> NULL pointer, which wraps our pointer negative, then adds the same
> offset back in and expects to get back to NULL. Unfortunately clang
> decides that this can never be NULL and optimises it into an infinite
> loop.
...
> #define llist_for_each_entry(pos, node, member)                         \
>         for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
>              &(pos)->member != NULL;                                    \
>              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))

Maybe the above could be rewritten as (untested):
		for ((pos) = NULL; (!(pos) ? (node) : ((pos)->member.next) || (pos) = 0) && \
			(((pos) = !(pos) ? llist_entry((node), typeof(*(pos)), member) \
					: llist_entry((pos)->member.next, typeof(*(pos)), member)),1); )
Provided the compiler assumes that the loop body is never executed with 'pos == 0'
it should generate the same code.

	David

[toc] | [prev] | [next] | [standalone]

#1559874

On Mon, Jan 16, 2017 at 02:34:43PM +0000, David Laight wrote:
> From: Anton Blanchard
> > Sent: 15 January 2017 21:36
> > I was debugging a hang on a ppc64le kernel built with clang, and it
> > looks to be undefined behaviour with pointer wrapping in the llist code.
> > 
> > A test case is below. llist_for_each_entry() does container_of() on a
> > NULL pointer, which wraps our pointer negative, then adds the same
> > offset back in and expects to get back to NULL. Unfortunately clang
> > decides that this can never be NULL and optimises it into an infinite
> > loop.
> ...
> > #define llist_for_each_entry(pos, node, member)                         \
> >         for ((pos) = llist_entry((node), typeof(*(pos)), member);       \
> >              &(pos)->member != NULL;                                    \
> >              (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
> 
> Maybe the above could be rewritten as (untested):
> 		for ((pos) = NULL; (!(pos) ? (node) : ((pos)->member.next) || (pos) = 0) && \
> 			(((pos) = !(pos) ? llist_entry((node), typeof(*(pos)), member) \
> 					: llist_entry((pos)->member.next, typeof(*(pos)), member)),1); )
> Provided the compiler assumes that the loop body is never executed with 'pos == 0'
> it should generate the same code.

That's far uglier code and to what point? The compiler should simply not
assume silly things.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web