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

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.

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

On Mon, Jan 16, 2017 at 10:42:29PM +1100, Anton Blanchard wrote:

Hi Peter,

quoted

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.

quoted

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?

2017-01-16 15:53 GMT+03:00 Peter Zijlstra [off-list ref]:

On Mon, Jan 16, 2017 at 10:42:29PM +1100, Anton Blanchard wrote:

quoted

Hi Peter,

quoted

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.

quoted

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

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

On Mon, Jan 16, 2017 at 02:34:43PM +0000, David Laight wrote:

From: Anton Blanchard

quoted

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.

...

quoted

#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.