excessive stack usage with kernel address sanitizer

[arndb]

Bugzilla Link	38809
Version	unspecified
OS	Linux
Blocks	#4440
Attachments	linux/drivers/video/backlight/ltv350qv.c, preprocessed, reduced
CC	@KernelAddress,@melver,@eugenis,@kcc,@lalozano,@maxim-kuvyrkov,@nathanchance,@nickdesaulniers,@rengolin,@stephenhines

Extended Description

Building the Linux kernel with clang KASAN enabled shows many warnings about possible stack overflow (we limit the frame size per function to 1024 to 2048 byte, depending on configuration, because the per-thread stack is very limited).

I created a reduced test case from one of the scarier warnings:

$ clang-8 ltv350qv.c --target=aarch64-linux-gnu  -c -O2 -Wframe-larger-than=500 -fsanitize=kernel-address  -Wall  -Wno-unused -Wno-sometimes-uninitialized -Werror -mllvm -asan-stack=1 -mllvm -asan-use-after-scope=0
ltv350qv.c:181:6: error: stack frame size of 1760 bytes in function 'fn6' [-Werror,-Wframe-larger-than=]
void fn6() {
     ^
ltv350qv.c:209:6: error: stack frame size of 10048 bytes in function 'fn7' [-Werror,-Wframe-larger-than=]
void fn7() {

I tested this using clang-8.0.0-svn341106-1exp1+020180830200353.1747~1.gbp19b9f6 on Ubuntu, but an old clang-3.9 shows the same behavior.

With gcc, the same function is fine with "asan-use-after-scope" disabled:

$ aarch-linux-gcc-8.0.1 -xc ltv350qv.c   -S -O2 -Wframe-larger-than=100 -fsanitize=kernel-address   -Wall  -Wno-unused -Wno-attributes  -fno-strict-aliasing --param asan-stack=1 -Werror  -fno-sanitize-address-use-after-scope
ltv350qv.c: In function 'fn5':
ltv350qv.c:180:1: error: the frame size of 448 bytes is larger than 100 bytes [-Werror=frame-larger-than=]
 }
 ^
ltv350qv.c: In function 'fn6':
ltv350qv.c:208:1: error: the frame size of 512 bytes is larger than 100 bytes [-Werror=frame-larger-than=]
 }
 ^
cc1: all warnings being treated as errors

but turning on asan-use-after-scope makes gcc as bad as clang, which is expected from the source code (the kernel turns it off by default for this reason):

ltv350qv.c: In function 'fn5':
ltv350qv.c:180:1: error: the frame size of 10000 bytes is larger than 100 bytes [-Werror=frame-larger-than=]
 }
 ^
ltv350qv.c: In function 'fn6':
ltv350qv.c:208:1: error: the frame size of 1984 bytes is larger than 100 bytes [-Werror=frame-larger-than=]
 }

Using -fsantize=address in place of -fsanitize=kernel-address completely avoids the high stack usage with clang, even with asan-use-after-scope enabled:

$ clang-8 ltv350qv.c --target=aarch64-linux-gnu  -c -O2 -Wframe-larger-than=64 -fsanitize=address  -Wall  -Wno-unused -Wno-sometimes-uninitialized -Werror -mllvm -asan-stack=1  -mllvm -asan-use-after-scope=1

ltv350qv.c:181:6: error: stack frame size of 96 bytes in function 'fn6' [-Werror,-Wframe-larger-than=]
void fn6() {
     ^
ltv350qv.c:209:6: error: stack frame size of 96 bytes in function 'fn7' [-Werror,-Wframe-larger-than=]
void fn7() {

[KernelAddress]

If I am reading this correctly for fn7 we do 100+x worse than gcc: 10048 for clang, not showing with limit 100 on gcc.

I am also confused by difference between -fsantize=address and -fsanitize=kernel-address. Shouldn't the code be the same except for shadow base?

[arndb]

Looking at the assembler output, the difference here appears to be that this code from the reduced test case

void fn1(struct list_head *new) {
  union {
    typeof(&a) __c[1];
  } b = {{new}};
  *(volatile long *)b.__c;
}
void fn2(struct list_head *new) { fn1(new); }
void fn3(struct spi_transfer *t) { fn2(&t->transfer_list); }

gets completely optimized away by gcc, but not by clang, which produces a complex stack check from any call to fn3().

This is what it looked like in the original code:

static inline __attribute__((always_inline, unused)) __attribute__((no_instrument_function)) __attribute__((always_inline)) void __write_once_size(volatile void *p, void *res, int size)
{
 switch (size) {
 case 1: *(volatile __u8 *)p = *(__u8 *)res; break;
 case 2: *(volatile __u16 *)p = *(__u16 *)res; break;
 case 4: *(volatile __u32 *)p = *(__u32 *)res; break;
 case 8: *(volatile __u64 *)p = *(__u64 *)res; break;
 default:
  __asm__ __volatile__("" : : : "memory");
  __builtin_memcpy((void *)p, (const void *)res, size);
  __asm__ __volatile__("" : : : "memory");
 }
#define WRITE_ONCE(x, val) \
({                                                      \
        union { typeof(x) __val; char __c[1]; } __u =   \
                { .__val = (__force typeof(x)) (val) }; \ 
        __write_once_size(&(x), __u.__c, sizeof(x));    \
        __u.__val;                                      \ 
})
static inline __attribute__((always_inline, unused)) __attribute__((no_instrument_function)) bool __list_add_valid(struct list_head *new,
    struct list_head *prev,
    struct list_head *next)
{
 return true;
}
static inline __attribute__((always_inline, unused)) __attribute__((no_instrument_function)) void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
 if (!__list_add_valid(new, prev, next))
  return;

 next->prev = new;
 new->next = next;
 new->prev = prev;
 WRITE_ONCE(prev->next, new);
}
static inline __attribute__((always_inline, unused)) __attribute__((no_instrument_function)) void list_add_tail(struct list_head *new, struct list_head *head)
{
 __list_add(new, head->prev, head);
}
static inline __attribute__((always_inline, unused)) __attribute__((no_instrument_function)) void
spi_message_add_tail(struct spi_transfer *t, struct spi_message *m)
{
 list_add_tail(&t->transfer_list, &m->transfers);
}

[KernelAddress]

Kostya, can you help to find somebody to work on this?

[arndb]

I've done a new (guided) reduction of the original source code now, which got me to this test case:

struct list_head { struct list_head *next, *prev; };
static void __list_add(struct list_head *new, struct list_head *prev,
           struct list_head *next) {
  prev->next = new;
  next->prev = new;
  new->next = next;
  new->prev = prev;
}
struct spi_transfer {
  struct list_head transfer_list;
  char b[16];
};
struct spi_message {
  struct list_head transfers;
  char b[256];
};
static void
spi_message_add_tail(struct spi_transfer *t, struct spi_message *m) {
  __list_add(&t->transfer_list, &m->transfers, &m->transfers);
}
extern void spi_sync(struct spi_message *msg);
static void ltv350qv_write_reg(void) {
  struct spi_message msg;
  struct spi_transfer index_xfer;
  spi_message_add_tail(&index_xfer, &msg);
  spi_sync(&msg);
}
void ltv350qv_power_on(void) {
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
  ltv350qv_write_reg();
}

This uses 10944 bytes stack frame with clang -fsanitize=kernel-address, compare with 416 bytes with gcc, or 96 bytes using clang -fsanitize=address.

[eugenis]

So this is the old problem of stack slot reuse not working with ASan.
In order to find use-after-scope bugs on, for example, "msg" local variable from the first inlined call to ltv350qv_write_reg, it has to stay unused and cannot overlap with the same variable from the following calls.

Simply disabling use-after-scope detection would not help, this is a fundamental part of asan implementation in LLVM.

[arndb]

So this is the old problem of stack slot reuse not working with ASan.
In order to find use-after-scope bugs on, for example, "msg" local variable
from the first inlined call to ltv350qv_write_reg, it has to stay unused and
cannot overlap with the same variable from the following calls.

Simply disabling use-after-scope detection would not help, this is a
fundamental part of asan implementation in LLVM.

But why does it only affect -fsanitize=kernel-address and not -fsanitize=address then?

Disabling "asan-stack" entirely seems to work, but may be a bit heavy-handed. Are there other sub-options of asan-stack that can be left enabled while we turn off use-after-scope and other options?

For gcc, the kernel already turns off use-after-scope detection to work around the problem, but the normal asan-stack stays enabled.

[eugenis]

Oh, sorry I misunderstood the question.
Userspace asan has the optional "fake stack" feature for use-after-return detection. Each function checks if it is enabled in prologue. This check makes the 10Kb stack allocation appear to be a dynamic alloca, and it does not trigger the warning. But the problem is still there.

[arndb]

[preprocessed linuxhttps://user-images.githubusercontent.com/92601431/143758042-76d92e65-601e-4ca0-8fce-b0a8087b6c97.gz)
I'm preparing a patch to turn off asan-stack=1 in the kernel, which gets rid of almost all such warnings. One interesting instance remains in the attached preprocessed file (not reduced yet):

clang-8 -Wno-gnu -Wno-unused-argument -Wno-unused-value -Wno-sign-compare -Wframe-larger-than=1000 -O2 -fsanitize=kernel-address -mllvm -asan-stack=0 -c go7007-fw.i --target=aarch64-linux -Wno-unused-value -Wno-pointer-sign
/git/arm-soc/drivers/media/usb/go7007/go7007-fw.c:1551:5: warning: stack frame size of 2656 bytes in function
'go7007_construct_fw_image' [-Wframe-larger-than=]

Marking one function (do_special()) as attribute((no_inline)) avoids the issue in this file.

[kcc]

I am not confident we can fix this in clang/llvm.
The difference between gcc and clang, AFAICT, is not in the asan
instrumentation, but in inining.
Looking at the reproducer from #38157 #c4,
if I change ltv350qv_write_reg to always inline, gcc also produces a
huge 10K stack frame,
and making it noinline fixes the stack frame for both gcc and clang.

[eugenis]

The problem with ltv350qv_write_reg could be fixed by tuning inlining heuristics. Right now they assume that inlining an alloca is basically free, while with asan it has a cost that is proportional to its size (for poisoning and unpoisoning, both in code size and run time). This does not address stack frame size directly, but it could be a decent proxy.

[arndb]

The problem with ltv350qv_write_reg could be fixed by tuning inlining
heuristics. Right now they assume that inlining an alloca is basically free,
while with asan it has a cost that is proportional to its size (for
poisoning and unpoisoning, both in code size and run time). This does not
address stack frame size directly, but it could be a decent proxy.

I don't see an alloca() in the function, in fact we don't allow alloca() to be used in the kernel at all (we build with -Wvla).

I am not confident we can fix this in clang/llvm.
The difference between gcc and clang, AFAICT, is not in the asan
instrumentation, but in inining.
Looking at the reproducer from
#38157 #c4,
if I change ltv350qv_write_reg to always inline, gcc also produces a
huge 10K stack frame,
and making it noinline fixes the stack frame for both gcc and clang.

I tried using attribute((always_inline)) but do not see the gcc bug you are referring to:

https://godbolt.org/z/b7Fm4_

We had a related bug in older versions of gcc that would cause stack slots to not be reused when inlining certain functions, but I added workarounds for all instances in the kernel that hit that particular gcc bug, and newer gcc versions all contain that trivial fix (see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81715#c18)

[arndb]

Here is another example (without inline functions) that I reduced from linux/drivers/crypto/ccp/ccp-ops.c:

https://godbolt.org/z/ylsGSQ

struct ccp_op {
  int jobid[50];
};
struct ccp_op fn1(void), a, b, c;
void fn2(struct ccp_op);
void fn3(int d) {
    fn2(a);
    fn1();
    fn2(b);
    fn2(b);
    fn1();
    fn2(a);
    fn1();
    fn2(b);
    fn2(b);
    fn1();
    fn1();
}

$ clang-8 -std=gnu89 -Wframe-larger-than=2048 --target=aarch64-linux -Wall -fsanitize=kernel-address -O2 -c ccp-ops.i
warning: stack frame size of 3320 bytes in function 'fn3' [-Wframe-larger-than=]
$ gcc-8 -std=gnu89 -Wframe-larger-than=100 -Wall -fsanitize=kernel-address --param asan-stack=1 -O2 -c ccp-ops.i
ccp-ops.i: In function ‘fn3’:
ccp-ops.i:73:1: warning: the frame size of 224 bytes is larger than 100 bytes [-Wframe-larger-than=]

[eugenis]

Another idea: when use-after-scope is disabled, we could merge allocas with the same size and non-overlapping lifetimes before creating the mega-alloca. This would make asan reports a bit more ambiguous - stack frame dumps will need to mention multiple possibilities for certain offset ranges.

This will take a non-trivial amount of work.

Re: #​11, "alloca" stands for any stack allocation. There are static allocas (regular variables) and dynamic allocas (actual alloca() calls).

[arndb]

Another idea: when use-after-scope is disabled, we could merge allocas with
the same size and non-overlapping lifetimes before creating the mega-alloca.
This would make asan reports a bit more ambiguous - stack frame dumps will
need to mention multiple possibilities for certain offset ranges.

This will take a non-trivial amount of work.

I would hope something simpler could be done, where the reporting does not have to be made more complicated. Trying to come up with a relevant example that is more like the kernel code I see require much more stack on clang vs gcc, take this program:

// https://godbolt.org/z/Ws2qLZ
struct s { int count; int a[500]; };
int __attribute__((noinline)) may_overflow(struct s *s)
{
        return s->a[s->count];
}
static inline __attribute__((always_inline)) int largestack(int i)
{
        struct s s;
        s.count = i;
        return may_overflow(&s);
}
int main(void)
{
        return largestack(2) +
               largestack(500) + 
               largestack(-2) + 
               largestack(0);
}

Building this with gcc-8 -g -Wall -O2 array.c -fsanitize=address --param asan-stack=1 -fno-sanitize-address-use-after-scope -Wframe-larger-than=10, I see 2KB stack usage and this output:

=================================================================
==3977944==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7ffe8caedbbc at pc 0x000000400a2d bp 0x7ffe8caedb80 sp 0x7ffe8caedb70
READ of size 4 at 0x7ffe8caedbbc thread T0
    #​0 0x400a2c in may_overflow /tmp/array.c:4
    #​1 0x400831 in largestack2 /tmp/array.c:16
    #​2 0x400831 in main /tmp/array.c:20
    #​3 0x7fcd2143282f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #​4 0x400918 in _start (/tmp/a.out+0x400918)

Address 0x7ffe8caedbbc is located in stack of thread T0 at offset 28 in frame
    #​0 0x4007af in main /tmp/array.c:19

  This frame has 1 object(s):
    [32, 2036) 's' <== Memory access at offset 28 underflows this variable

Doing the same thing with clang-8 -g -Wall -O2 array.c -fsanitize=address -mllvm -asan-stack=1 -fno-sanitize-address-use-after-scope -Wframe-larger-than=10, I see 8KB stack usage, and this slightly more elaborate output:

=================================================================
==3977959==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffcfb36c354 at pc 0x0000004f7604 bp 0x7ffcfb36aa80 sp 0x7ffcfb36aa78
READ of size 4 at 0x7ffcfb36c354 thread T0
    #​0 0x4f7603 in may_overflow /tmp/array2.c:4:16
    #​1 0x4f7767 in largestack /tmp/array2.c:10:16
    #​2 0x4f7767 in main /tmp/array2.c:15
    #​3 0x7fdf0781882f in __libc_start_main /build/glibc-Cl5G7W/glibc-2.23/csu/../csu/libc-start.c:291
    #​4 0x41a8d8 in _start (/tmp/a.out+0x41a8d8)

Address 0x7ffcfb36c354 is located in stack of thread T0 at offset 6324 in frame
    #​0 0x4f761f in main /tmp/array2.c:13

  This frame has 4 object(s):
    [32, 2036) 's.i12'
    [2176, 4180) 's.i9'
    [4320, 6324) 's.i6' <== Memory access at offset 6324 overflows this variable
    [6464, 8468) 's.i'

But since the four objects are all conceptually the same variable in the inline function, and I still have the line information, it doesn't seem to help much that there are now four objects listed. Is this something that can perhaps be changed more easily?

Note1: the -Wframe-larger-than= warning message seems wrong for "clang --sanitize=address" (it reports 88 bytes instead of 8KB), but it looks correct with either --sanitize=kernel-address or without asan.

Note2: gcc also merges distinct objects of the same size, and reports a random one in the output if they are of the same type. I assume you'd consider that a bug in gcc, but I also think that it's better than using more stack space, at least in the context of the Linux kernel, where the available stack space is very constrained.

[nickdesaulniers]

I am not confident we can fix this in clang/llvm.
The difference between gcc and clang, AFAICT, is not in the asan
instrumentation, but in inining.
Looking at the reproducer from
#38157 #c4,
if I change ltv350qv_write_reg to always inline, gcc also produces a
huge 10K stack frame,
and making it noinline fixes the stack frame for both gcc and clang.

Would it be worthwhile for us to limit inlining when building with LLVM?

I see a few options in llvm/lib/Analysis/InlineCost.cpp. Perhaps by playing with -mllvm -inline-threshold=<number>, we could reduce the amount of inlining that occurs? I assume that won't break attribute((always_inline)) (when it succeeds), and would help limit the frame sizes from growing too much? Probably won't run as fast, but I think folks are willing to accept that tradeoff.

If we find that that is generally helpful for this very painful and constant source of bugreports, would it be possible for LLVM to simply update that value when using -fsanitize=address?