llist code relies on undefined behaviour, upsets llvm/clang

llist code relies on undefined behaviour, upsets llvm/clang

[Anton Blanchard]

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

Re: llist code relies on undefined behaviour, upsets llvm/clang

[Peter Zijlstra]

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.

Re: llist code relies on undefined behaviour, upsets llvm/clang

[Anton Blanchard]

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

Re: llist code relies on undefined behaviour, upsets llvm/clang

[Peter Zijlstra]

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?

Re: llist code relies on undefined behaviour, upsets llvm/clang

[Andrey Ryabinin]

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

RE: llist code relies on undefined behaviour, upsets llvm/clang

[David Laight]

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

RE: llist code relies on undefined behaviour, upsets llvm/clang

[David Laight]

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.
>=20
> 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) =3D llist_entry((node), typeof(*(pos)), member);      =
 \
>              &(pos)->member !=3D NULL;                                   =
 \
>              (pos) =3D llist_entry((pos)->member.next, typeof(*(pos)), me=
mber))

Maybe the above could be rewritten as (untested):
		for ((pos) =3D NULL; (!(pos) ? (node) : ((pos)->member.next) || (pos) =3D=
 0) && \
			(((pos) =3D !(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 'po=
s =3D=3D 0'
it should generate the same code.

	David

Re: llist code relies on undefined behaviour, upsets llvm/clang

[Peter Zijlstra]

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.