sparse problem with Linux kernel v5.5

sparse problem with Linux kernel v5.5

[Randy Dunlap]

sparse is v0.6.1.

On kernel v5.5, I can't get past an error on net/core/bpf_sk_storage.c.
Also, what is errno 137? (0x89)

  CHECK   ../net/core/bpf_sk_storage.c
/bin/sh: line 1: 26442 Killed                  sparse -D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise -Wno-return-void -Wno-unknown-attribute -D__x86_64__ --arch=x86_64 -mlittle-endian -m64 -Wp,-MD,net/core/.bpf_sk_storage.o.d -nostdinc -isystem /usr/lib64/gcc/x86_64-suse-linux/7/include -I../arch/x86/include -I./arch/x86/include/generated -I../include -I./include -I../arch/x86/include/uapi -I./arch/x86/include/generated/uapi -I../include/uapi -I./include/generated/uapi -include ../include/linux/kconfig.h -include ../include/linux/compiler_types.h -D__KERNEL__ -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -std=gnu89 -mno-sse -mno-mmx -mno-sse2 -mno-3dnow -mno-avx -m64 -falign-jumps=1 -falign-loops=1 -mno-80387 -mno-fp-ret-in-387 -mpreferred-stack-boundary=3 -mskip-rax-setup -mtune=generic -mno-red-zone -mcmodel=kernel -DCONFIG_X86_X32_ABI -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1 -DCONFIG_AS_CFI_SECTIONS=1 -DCONFIG_AS_SSSE3=1 -DCONFIG_AS_AVX=1 -DCONFIG_AS_AVX2=1 -DCONFIG_AS_AVX512=1 -DCONFIG_AS_SHA1_NI=1 -DCONFIG_AS_SHA256_NI=1 -Wno-sign-compare -fno-asynchronous-unwind-tables -mindirect-branch=thunk-extern -mindirect-branch-register -fno-jump-tables -fno-delete-null-pointer-checks -Wno-frame-address -Wno-format-truncation -Wno-format-overflow -O2 --param=allow-store-data-races=0 -fno-reorder-blocks -fno-ipa-cp-clone -fno-partial-inlining -Wframe-larger-than=2048 -fstack-protector-strong -Wno-unused-but-set-variable -Wimplicit-fallthrough -Wno-unused-const-variable -fno-var-tracking-assignments -pg -mrecord-mcount -mfentry -DCC_USING_FENTRY -fno-inline-functions-called-once -flive-patching=inline-clone -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -fno-strict-overflow -fno-merge-all-constants -fmerge-constants -fno-stack-check -fconserve-stack -Werror=date-time -Werror=incompatible-pointer-types -Werror=designated-init -fsanitize=kernel-address -fasan-shadow-offset=0xdffffc0000000000 --param asan-globals=1 --param asan-instrumentation-with-call-threshold=0 --param asan-stack=1 -fsanitize-coverage=trace-pc -I ../net/core -I ./net/core -DKBUILD_MODFILE='"net/core/bpf_sk_storage"' -DKBUILD_BASENAME='"bpf_sk_storage"' -DKBUILD_MODNAME='"bpf_sk_storage"' ../net/core/bpf_sk_storage.c
make[3]: *** [../scripts/Makefile.build:268: net/core/bpf_sk_storage.o] Error 137


Yes, pid 26442 (Killed) was sparse.
My laptop has 8GB of RAM (x86_64).
I have hit this error 3x, so I would say that it is easily reproducible (for me).

Any ideas/suggestions?


thanks.
-- 
~Randy

Re: sparse problem with Linux kernel v5.5

[Randy Dunlap]

On 2/5/20 8:49 PM, Randy Dunlap wrote:
> sparse is v0.6.1.
> 
> On kernel v5.5, I can't get past an error on net/core/bpf_sk_storage.c.

Sorry, this is on linux-next 2020-0205, not mainline.


> Also, what is errno 137? (0x89)
> 
>   CHECK   ../net/core/bpf_sk_storage.c
> /bin/sh: line 1: 26442 Killed                  sparse -D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise -Wno-return-void -Wno-unknown-attribute -D__x86_64__ --arch=x86_64 -mlittle-endian -m64 -Wp,-MD,net/core/.bpf_sk_storage.o.d -nostdinc -isystem /usr/lib64/gcc/x86_64-suse-linux/7/include -I../arch/x86/include -I./arch/x86/include/generated -I../include -I./include -I../arch/x86/include/uapi -I./arch/x86/include/generated/uapi -I../include/uapi -I./include/generated/uapi -include ../include/linux/kconfig.h -include ../include/linux/compiler_types.h -D__KERNEL__ -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -std=gnu89 -mno-sse -mno-mmx -mno-sse2 -mno-3dnow -mno-avx -m64 -falign-jumps=1 -falign-loops=1 -mno-80387 -mno-fp-ret-in-387 -mpreferred-stack-boundary=3 -mskip-rax-setup -mtune=generic -mno-red-zone -mcmodel=kernel -DCONFIG_X86_X32_ABI -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1 -DCONFIG_AS_CFI_SECTIONS=1 -DCONFIG_AS_SSSE3=1 -DCONFIG_AS_AVX=1 -DCONFIG_AS_AVX2=1 -DCONFIG_AS_AVX512=1 -DCONFIG_AS_SHA1_NI=1 -DCONFIG_AS_SHA256_NI=1 -Wno-sign-compare -fno-asynchronous-unwind-tables -mindirect-branch=thunk-extern -mindirect-branch-register -fno-jump-tables -fno-delete-null-pointer-checks -Wno-frame-address -Wno-format-truncation -Wno-format-overflow -O2 --param=allow-store-data-races=0 -fno-reorder-blocks -fno-ipa-cp-clone -fno-partial-inlining -Wframe-larger-than=2048 -fstack-protector-strong -Wno-unused-but-set-variable -Wimplicit-fallthrough -Wno-unused-const-variable -fno-var-tracking-assignments -pg -mrecord-mcount -mfentry -DCC_USING_FENTRY -fno-inline-functions-called-once -flive-patching=inline-clone -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -fno-strict-overflow -fno-merge-all-constants -fmerge-constants -fno-stack-check -fconserve-stack -Werror=date-time -Werror=incompatible-pointer-types -Werror=designated-init -fsanitize=kernel-address -fasan-shadow-offset=0xdffffc0000000000 --param asan-globals=1 --param asan-instrumentation-with-call-threshold=0 --param asan-stack=1 -fsanitize-coverage=trace-pc -I ../net/core -I ./net/core -DKBUILD_MODFILE='"net/core/bpf_sk_storage"' -DKBUILD_BASENAME='"bpf_sk_storage"' -DKBUILD_MODNAME='"bpf_sk_storage"' ../net/core/bpf_sk_storage.c
> make[3]: *** [../scripts/Makefile.build:268: net/core/bpf_sk_storage.o] Error 137
> 
> 
> Yes, pid 26442 (Killed) was sparse.
> My laptop has 8GB of RAM (x86_64).
> I have hit this error 3x, so I would say that it is easily reproducible (for me).
> 
> Any ideas/suggestions?
> 
> 
> thanks.
> 


-- 
~Randy
Reported-by: Randy Dunlap <rdunlap@infradead.org>

Re: sparse problem with Linux kernel v5.5

[Linus Torvalds]

On Thu, Feb 6, 2020 at 4:49 AM Randy Dunlap <rdunlap@infradead.org> wrote:
>
> Also, what is errno 137? (0x89)

I think that's just "killed by signal 9" (the high bit is "killed by
signal", the low bits are the signal number).

SIGKILL - oom? What does 'dmesg' say? Maybe there's some exponential
memory use triggered by something in that bpf_sk_storage file..

                Linus

Re: sparse problem with Linux kernel v5.5

[Luc Van Oostenryck]

On Thu, Feb 06, 2020 at 07:18:45AM +0000, Linus Torvalds wrote:
> On Thu, Feb 6, 2020 at 4:49 AM Randy Dunlap <rdunlap@infradead.org> wrote:
> >
> > Also, what is errno 137? (0x89)
> 
> I think that's just "killed by signal 9" (the high bit is "killed by
> signal", the low bits are the signal number).
> 
> SIGKILL - oom? What does 'dmesg' say? Maybe there's some exponential
> memory use triggered by something in that bpf_sk_storage file..
> 

Hi Randy,
What config are you using?

Here, on next-20200205 (commit 14b549456391a8b8f812529896b2690c16349734)
the file bpf_sk_storage.c is not compiled with the default config
(I suppose because of CONFIG_BPF_SYSCALL).
With allyesconfig, I see nothing particular ('-fmem-report' added):
  $ time sparse -fmem-report -D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise -Wno-return-void -Wno-unknown-attribute  -D__x86_64__ --arch=x86 -mlittle-endian -m64 -Wp,-MD,net/core/.bpf_sk_storage.o.d  -nostdinc -isystem /usr/lib/gcc/x86_64-linux-gnu/8/include -I./arch/x86/include -I./arch/x86/include/generated  -I./include -I./arch/x86/include/uapi -I./arch/x86/include/generated/uapi -I./include/uapi -I./include/generated/uapi -include ./include/linux/kconfig.h -include ./include/linux/compiler_types.h -D__KERNEL__ -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Wno-format-security -std=gnu89 -mno-sse -mno-mmx -mno-sse2 -mno-3dnow -mno-avx -m64 -falign-jumps=1 -falign-loops=1 -mno-80387 -mno-fp-ret-in-387 -mpreferred-stack-boundary=3 -mskip-rax-setup -mtune=generic -mno-red-zone -mcmodel=kernel -DCONFIG_X86_X32_ABI -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1 -DCONFIG_AS_CFI_SECTIONS=1 -DCONFIG_AS_SSSE3=1 -DCONFIG_AS_AVX=1 -DCONFIG_AS_AVX2=1 -DCONFIG_AS_AVX512=1 -DCONFIG_AS_SHA1_NI=1 -DCONFIG_AS_SHA256_NI=1 -Wno-sign-compare -fno-asynchronous-unwind-tables -mindirect-branch=thunk-extern -mindirect-branch-register -fno-jump-tables -fno-delete-null-pointer-checks -Wno-frame-address -Wno-format-truncation -Wno-format-overflow -O2 --param=allow-store-data-races=0 -fno-reorder-blocks -fno-ipa-cp-clone -fno-partial-inlining -Wframe-larger-than=2048 -fstack-protector-strong -Wno-unused-but-set-variable -Wimplicit-fallthrough -Wno-unused-const-variable -fno-var-tracking-assignments -pg -mrecord-mcount -mfentry -DCC_USING_FENTRY -fno-inline-functions-called-once -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wno-stringop-truncation -fno-strict-overflow -fno-merge-all-constants -fmerge-constants -fno-stack-check -fconserve-stack -Werror=date-time -Werror=incompatible-pointer-types -Werror=designated-init -fmacro-prefix-map=./= -fcf-protection=none -Wno-packed-not-aligned    -fsanitize=kernel-address -fasan-shadow-offset=0xdffffc0000000000   --param asan-globals=1   --param asan-instrumentation-with-call-threshold=0   --param asan-stack=1   --param asan-instrument-allocas=1   -fsanitize-coverage=trace-pc -fsanitize-coverage=trace-cmp    -DKBUILD_MODFILE='"net/core/bpf_sk_storage"' -DKBUILD_BASENAME='"bpf_sk_storage"' -DKBUILD_MODNAME='"bpf_sk_storage"' net/core/bpf_sk_storage.c; echo $?
       allocator:   allocs,      bytes,      total,  %usage,  average
          tokens:        0,          0,          0,   0.00%,     0.00
     identifiers:    56223,    2262233,    2490368,  90.84%,    40.24
         symbols:   799200,  172627200,  173441024,  99.53%,   216.00
     expressions: 39852179, 2550539456, 2555543552,  99.80%,    64.00
      statements:   663762,   53100960,   53182464,  99.85%,    80.00
          scopes:    18206,     291296,     294912,  98.77%,    16.00
     basic_block:     1736,     180544,     196608,  91.83%,   104.00
     instruction:     7289,     583120,     589824,  98.86%,    80.00
          pseudo:     5181,     207240,     229376,  90.35%,    40.00
     pseudo_user:     6967,     111472,     131072,  85.05%,    16.00
        ptr list:   961807,  123111296,  123600896,  99.60%,   128.00
        multijmp:      275,       6600,      32768,  20.14%,    24.00
       asm rules:      241,       5784,      32768,  17.65%,    24.00
 asm constraints:      218,       6976,      32768,  21.29%,    32.00
        contexts:       42,        672,      32768,   2.05%,    16.00
         strings:    11288,     329766,     360448,  91.49%,    29.21
           bytes:    31957,     125216,     131072,  95.53%,     3.92
           total: 42416571, 2903489831, 2910322688,  99.77%,    68.45

real	0m5.391s
user	0m3.594s
sys	0m1.797s
0

In short, using 3G of RAM in 5secs without errors.


-- Luc

Re: sparse problem with Linux kernel v5.5

[Randy Dunlap]

On 2/6/20 3:46 AM, Luc Van Oostenryck wrote:
> On Thu, Feb 06, 2020 at 07:18:45AM +0000, Linus Torvalds wrote:
>> On Thu, Feb 6, 2020 at 4:49 AM Randy Dunlap <rdunlap@infradead.org> wrote:
>>>
>>> Also, what is errno 137? (0x89)
>>
>> I think that's just "killed by signal 9" (the high bit is "killed by
>> signal", the low bits are the signal number).

oh. thanks.
(seems like I asked about something similar around 15 years ago
but now I don't recall it :)

>> SIGKILL - oom? What does 'dmesg' say? Maybe there's some exponential
>> memory use triggered by something in that bpf_sk_storage file..

All of the oom-killer instances list sphinx-build as running, and I often
have OOM problems using it (make htmldocs), so that may be a factor.

This morning sparse is handling bpf_sk_storage.c OK (no sphinx-build running).


But I can post the dmesg output if you want to see it.

> Hi Randy,
> What config are you using?

I'm using allmodconfig.


thanks.
-- 
~Randy

Re: sparse problem with Linux kernel v5.5

[Luc Van Oostenryck]

On Thu, Feb 06, 2020 at 10:25:39AM -0800, Randy Dunlap wrote:
> 
> All of the oom-killer instances list sphinx-build as running, and I often
> have OOM problems using it (make htmldocs), so that may be a factor.
> 
> This morning sparse is handling bpf_sk_storage.c OK (no sphinx-build running).

OK, make sense.
However, I thought that the 5+seconds of runtime with 2.9Gb of memory
consumption I reported earlier was somehow excessive. So, I looked
at the preprocessed file and my editor (and several other tools) chocked
near the end ... It appears that one line is 2.8Mb on a total of 6.2MB
and contains 28968 times the expression for num_possible_cpus().

The origin of this is situted at line 647:
	smap->bucket_log = max_t(u32, 1, ilog2(roundup_pow_of_two(...));
because ilog2() is an 'interesting' macro which is already expanded
inside roundup_pow_of_two().

This exists since the introduction of this file in commit
    6ac99e8f23d4 bpf: Introduce bpf sk local storage
but back then it made sparse consume only about 500Mb of memory on it.
Use of the macro max_t make things even worse in commit 
    85749218e3a6 ("bpf: Fix out of bounds memory access in bpf_sk_storage")

To illustrate the situation, the following patch cuts sparse memory consumption
down to 109Mb in 0.3s:

diff --git a/net/core/bpf_sk_storage.c b/net/core/bpf_sk_storage.c
index 458be6b3eda9..bdf4a1a256c3 100644
--- a/net/core/bpf_sk_storage.c
+++ b/net/core/bpf_sk_storage.c
@@ -644,7 +644,7 @@ static struct bpf_map *bpf_sk_storage_map_alloc(union bpf_attr *attr)
 	bpf_map_init_from_attr(&smap->map, attr);
 
 	/* Use at least 2 buckets, select_bucket() is undefined behavior with 1 bucket */
-	smap->bucket_log = max_t(u32, 1, ilog2(roundup_pow_of_two(num_possible_cpus())));
+	smap->bucket_log = max_t(u32, 1, ilog2(__roundup_pow_of_two(num_possible_cpus())));
 	nbuckets = 1U << smap->bucket_log;
 	cost = sizeof(*smap->buckets) * nbuckets + sizeof(*smap);
 

but a better patch should, I think, directly use ilog2() and avoid the roundup.

Cheers,
-- Luc

Re: sparse problem with Linux kernel v5.5

[Linus Torvalds]

On Thu, Feb 6, 2020 at 12:06 PM Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
>
> However, I thought that the 5+seconds of runtime with 2.9Gb of memory
> consumption I reported earlier was somehow excessive. So, I looked
> at the preprocessed file and my editor (and several other tools) chocked
> near the end ... It appears that one line is 2.8Mb on a total of 6.2MB
> and contains 28968 times the expression for num_possible_cpus().

Whee..

> The origin of this is situted at line 647:
>         smap->bucket_log = max_t(u32, 1, ilog2(roundup_pow_of_two(...));
> because ilog2() is an 'interesting' macro which is already expanded
> inside roundup_pow_of_two().

Yeah, so we have "const_ilog2()" expanding its argument 63 times (to
handle the "just turn it into a constant" case), and so

   ilog2(roundup_pow_of_two(x))

where both ilog2() and roundup_pow_of_two() contains a const_ilog()
ends up internally essentially expanding x 63*63 times. Plus a couple
for the non-constant case.

And in this case 'x' wasn't all that simple to begin with on SMP.

And then the "max_t" thing adds another factor of 7 due to the whole
"let's keep a constant expression constant" with all the careful "can
I use a variable or not" code.

So you get 7*63*63 expansions of num_possible_cpus(), plus that "some
slop" for the other cases.

I wonder if we could just make sparse _warn_ about this kind of
situation with expressions that are very big - even if they turn into
nothing)?

Because I bet it's not good for a real compiler either. Compile time
does matter to people, and this clearly wasn't intentional.

And even if we apply a patch to avoid it here, that's fine, but others
might be lurking.

Of course, sometimes you do want to have that kind of nested expansion
on purpose - creating huge expression lists for some initializer or
whatever. And sometimes the constant value is what you care about, and
are willing to have complex expressions.

I don't think anybody intended for the expression to be quite _that_
complex, though..

> This exists since the introduction of this file in commit
>     6ac99e8f23d4 bpf: Introduce bpf sk local storage
> but back then it made sparse consume only about 500Mb of memory on it.

Well, the fact that sparse memory use has exploded by a factor of 6 is
not exactly good either. What happened?

> but a better patch should, I think, directly use ilog2() and avoid the roundup.

No, I think it would be better to just split that expression up.

Right now the code does:

        /* Use at least 2 buckets, select_bucket() is undefined
behavior with 1 bucket */
        smap->bucket_log = max_t(u32, 1,
ilog2(roundup_pow_of_two(num_possible_cpus())));
        nbuckets = 1U << smap->bucket_log;

so it calculates the log2, and then does "1U << log2".

Instead, it could just calculate the nbuckets first, and then do the
"log2()" on that:

        /* Use at least 2 buckets, select_bucket() is undefined
behavior with 1 bucket */
        nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
        smap->bucket_log = ilog2(buckets);

because honestly, that is just a whole lot more legible anyway. Maybe
even split _that_ up, and have the max_t as a separate thing.

Right now the constant in the comment (2) doesn't match the constant
in the code (1) because the code is too dense for its own good.

Of course, currently that "too dense for its own good" code ends up
evaluating to a constant on UP. Which the easier-to-read code does
not.

I'm not convinced that it makes sense to optimize for UP that much.

                Linus

Re: sparse problem with Linux kernel v5.5

[Martin KaFai Lau]

On Thu, Feb 06, 2020 at 03:47:21PM -0800, Linus Torvalds wrote:
> On Thu, Feb 6, 2020 at 12:06 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > However, I thought that the 5+seconds of runtime with 2.9Gb of memory
> > consumption I reported earlier was somehow excessive. So, I looked
> > at the preprocessed file and my editor (and several other tools) chocked
> > near the end ... It appears that one line is 2.8Mb on a total of 6.2MB
> > and contains 28968 times the expression for num_possible_cpus().
> 
> Whee..
> 
> > The origin of this is situted at line 647:
> >         smap->bucket_log = max_t(u32, 1, ilog2(roundup_pow_of_two(...));
> > because ilog2() is an 'interesting' macro which is already expanded
> > inside roundup_pow_of_two().
> 
> Yeah, so we have "const_ilog2()" expanding its argument 63 times (to
> handle the "just turn it into a constant" case), and so
> 
>    ilog2(roundup_pow_of_two(x))
> 
> where both ilog2() and roundup_pow_of_two() contains a const_ilog()
> ends up internally essentially expanding x 63*63 times. Plus a couple
> for the non-constant case.
> 
> And in this case 'x' wasn't all that simple to begin with on SMP.
> 
> And then the "max_t" thing adds another factor of 7 due to the whole
> "let's keep a constant expression constant" with all the careful "can
> I use a variable or not" code.
> 
> So you get 7*63*63 expansions of num_possible_cpus(), plus that "some
> slop" for the other cases.
> 
> I wonder if we could just make sparse _warn_ about this kind of
> situation with expressions that are very big - even if they turn into
> nothing)?
> 
> Because I bet it's not good for a real compiler either. Compile time
> does matter to people, and this clearly wasn't intentional.
> 
> And even if we apply a patch to avoid it here, that's fine, but others
> might be lurking.
> 
> Of course, sometimes you do want to have that kind of nested expansion
> on purpose - creating huge expression lists for some initializer or
> whatever. And sometimes the constant value is what you care about, and
> are willing to have complex expressions.
> 
> I don't think anybody intended for the expression to be quite _that_
> complex, though..
> 
> > This exists since the introduction of this file in commit
> >     6ac99e8f23d4 bpf: Introduce bpf sk local storage
> > but back then it made sparse consume only about 500Mb of memory on it.
> 
> Well, the fact that sparse memory use has exploded by a factor of 6 is
> not exactly good either. What happened?
> 
> > but a better patch should, I think, directly use ilog2() and avoid the roundup.
> 
> No, I think it would be better to just split that expression up.
> 
> Right now the code does:
> 
>         /* Use at least 2 buckets, select_bucket() is undefined
> behavior with 1 bucket */
>         smap->bucket_log = max_t(u32, 1,
> ilog2(roundup_pow_of_two(num_possible_cpus())));
>         nbuckets = 1U << smap->bucket_log;
> 
> so it calculates the log2, and then does "1U << log2".
> 
> Instead, it could just calculate the nbuckets first, and then do the
> "log2()" on that:
> 
>         /* Use at least 2 buckets, select_bucket() is undefined
> behavior with 1 bucket */
>         nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
>         smap->bucket_log = ilog2(buckets);
> 
> because honestly, that is just a whole lot more legible anyway. Maybe
> even split _that_ up, and have the max_t as a separate thing.
Thanks for the suggestion.  I can post a patch for this.

-- Martin

> 
> Right now the constant in the comment (2) doesn't match the constant
> in the code (1) because the code is too dense for its own good.
> 
> Of course, currently that "too dense for its own good" code ends up
> evaluating to a constant on UP. Which the easier-to-read code does
> not.
> 
> I'm not convinced that it makes sense to optimize for UP that much.
> 
>                 Linus

Re: sparse problem with Linux kernel v5.5

[Uwe Kleine-König]

[-- Attachment #1.1: Type: text/plain, Size: 747 bytes --]

Hello,

On 2/7/20 12:47 AM, Linus Torvalds wrote:
> Instead, it could just calculate the nbuckets first, and then do the
> "log2()" on that:
> 
>         /* Use at least 2 buckets, select_bucket() is undefined
> behavior with 1 bucket */
>         nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
>         smap->bucket_log = ilog2(buckets);


Isn't it kind of ineffective to first round to a power of two and then
take the ilog2 of it?

At a first glance I'd say that

	ilog2(roundup_pow_of_two(x)) == ilog(x - 1) + 1

for x > 1. (Maybe even for x == 1? Didn't care to check, I think it
doesn't matter for the case at hand.)

This RHS might be easier to optimize for the compiler?!

Best regards
Uwe


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: sparse problem with Linux kernel v5.5

[Martin KaFai Lau]

On Fri, Feb 07, 2020 at 07:34:57AM +0100, Uwe Kleine-König wrote:
> Hello,
> 
> On 2/7/20 12:47 AM, Linus Torvalds wrote:
> > Instead, it could just calculate the nbuckets first, and then do the
> > "log2()" on that:
> > 
> >         /* Use at least 2 buckets, select_bucket() is undefined
> > behavior with 1 bucket */
> >         nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
> >         smap->bucket_log = ilog2(buckets);
> 
> 
> Isn't it kind of ineffective to first round to a power of two and then
> take the ilog2 of it?
> 
> At a first glance I'd say that
> 
> 	ilog2(roundup_pow_of_two(x)) == ilog(x - 1) + 1
> 
> for x > 1. (Maybe even for x == 1? Didn't care to check, I think it
> doesn't matter for the case at hand.)
> 
> This RHS might be easier to optimize for the compiler?!
I believe x == 1 needs an extra case since ilog2(0) won't work.

Since this function (map creation) is not on the fast path,
I currently opt for Linus's suggestion which its code is more
self-explanatory.

Thanks,
Martin

Re: sparse problem with Linux kernel v5.5

[Luc Van Oostenryck]

On Thu, Feb 06, 2020 at 03:47:21PM -0800, Linus Torvalds wrote:
> On Thu, Feb 6, 2020 at 12:06 PM Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
> >
> > However, I thought that the 5+seconds of runtime with 2.9Gb of memory
> > consumption I reported earlier was somehow excessive. So, I looked
> > at the preprocessed file and my editor (and several other tools) chocked
> > near the end ... It appears that one line is 2.8Mb on a total of 6.2MB
> > and contains 28968 times the expression for num_possible_cpus().
> 
> Whee..
> 
> > The origin of this is situted at line 647:
> >         smap->bucket_log = max_t(u32, 1, ilog2(roundup_pow_of_two(...));
> > because ilog2() is an 'interesting' macro which is already expanded
> > inside roundup_pow_of_two().
> 
> Yeah, so we have "const_ilog2()" expanding its argument 63 times (to
> handle the "just turn it into a constant" case), and so
> 
>    ilog2(roundup_pow_of_two(x))
> 
> where both ilog2() and roundup_pow_of_two() contains a const_ilog()
> ends up internally essentially expanding x 63*63 times. Plus a couple
> for the non-constant case.
> 
> And in this case 'x' wasn't all that simple to begin with on SMP.
> 
> And then the "max_t" thing adds another factor of 7 due to the whole
> "let's keep a constant expression constant" with all the careful "can
> I use a variable or not" code.
> 
> So you get 7*63*63 expansions of num_possible_cpus(), plus that "some
> slop" for the other cases.

Exactly.
 
> I wonder if we could just make sparse _warn_ about this kind of
> situation with expressions that are very big - even if they turn into
> nothing)?

I guess it wouldn't be hard to keep track of the nesting level of
expressions and issue a warning when some limit is reached.
Keeping track of the total size seems slightly more annoying to track
but seems feasible too.
 
> Because I bet it's not good for a real compiler either. Compile time
> does matter to people, and this clearly wasn't intentional.
> 
> And even if we apply a patch to avoid it here, that's fine, but others
> might be lurking.
> 
> Of course, sometimes you do want to have that kind of nested expansion
> on purpose - creating huge expression lists for some initializer or
> whatever. And sometimes the constant value is what you care about, and
> are willing to have complex expressions.
> 
> I don't think anybody intended for the expression to be quite _that_
> complex, though..

Yes, indeed.
Huge expression lists for initializers should not be a problem in itself,
it's only the nesting of such macros that is problematic.

> > This exists since the introduction of this file in commit
> >     6ac99e8f23d4 bpf: Introduce bpf sk local storage
> > but back then it made sparse consume only about 500Mb of memory on it.
> 
> Well, the fact that sparse memory use has exploded by a factor of 6 is
> not exactly good either. What happened?

The patch 85749218e3a6 ("bpf: Fix out of bounds memory access in bpf_sk_storage")
added the call to max_t().

> > but a better patch should, I think, directly use ilog2() and avoid the roundup.
> 
> No, I think it would be better to just split that expression up.

<snip>

> because honestly, that is just a whole lot more legible anyway. Maybe
> even split _that_ up, and have the max_t as a separate thing.
> 
> Right now the constant in the comment (2) doesn't match the constant
> in the code (1) because the code is too dense for its own good.
> 
> Of course, currently that "too dense for its own good" code ends up
> evaluating to a constant on UP. Which the easier-to-read code does
> not.
> 
> I'm not convinced that it makes sense to optimize for UP that much.

Yes, I agree.


I also think that const_ilog2() could advantageously use __builtin_clz():
Sparse, like gcc, expands it if its argument is constant.


-- Luc

Re: sparse problem with Linux kernel v5.5

[Luc Van Oostenryck]

On Thu, Feb 06, 2020 at 04:34:34PM -0800, Martin KaFai Lau wrote:
> On Thu, Feb 06, 2020 at 03:47:21PM -0800, Linus Torvalds wrote:
> > 
> > Instead, it could just calculate the nbuckets first, and then do the
> > "log2()" on that:
> > 
> >         /* Use at least 2 buckets, select_bucket() is undefined
> > behavior with 1 bucket */
> >         nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
> >         smap->bucket_log = ilog2(buckets);
> > 
> > because honestly, that is just a whole lot more legible anyway. Maybe
> > even split _that_ up, and have the max_t as a separate thing.
> Thanks for the suggestion.  I can post a patch for this.

There is also order_base_2() which,  I think, does exactly what you
need and shouldn't have the current problem.

-- Luc 

Re: sparse problem with Linux kernel v5.5

[Uwe Kleine-König]

[-- Attachment #1.1: Type: text/plain, Size: 1289 bytes --]

Hello,

On 2/7/20 9:29 AM, Martin KaFai Lau wrote:
> On Fri, Feb 07, 2020 at 07:34:57AM +0100, Uwe Kleine-König wrote:
>> Hello,
>>
>> On 2/7/20 12:47 AM, Linus Torvalds wrote:
>>> Instead, it could just calculate the nbuckets first, and then do the
>>> "log2()" on that:
>>>
>>>         /* Use at least 2 buckets, select_bucket() is undefined
>>> behavior with 1 bucket */
>>>         nbuckets = max_t(u32, 2, roundup_pow_of_two(num_possible_cpus()));
>>>         smap->bucket_log = ilog2(buckets);
>>
>>
>> Isn't it kind of ineffective to first round to a power of two and then
>> take the ilog2 of it?
>>
>> At a first glance I'd say that
>>
>> 	ilog2(roundup_pow_of_two(x)) == ilog(x - 1) + 1
>>
>> for x > 1. (Maybe even for x == 1? Didn't care to check, I think it
>> doesn't matter for the case at hand.)
>>
>> This RHS might be easier to optimize for the compiler?!
> I believe x == 1 needs an extra case since ilog2(0) won't work.
> 
> Since this function (map creation) is not on the fast path,
> I currently opt for Linus's suggestion which its code is more
> self-explanatory.

If you put my suggestion in a macro that is called for example

	ilog2_roundup()

you might have both: easier code and self-explanation.

Best regards
Uwe


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: sparse problem with Linux kernel v5.5

[Luc Van Oostenryck]

On Fri, Feb 07, 2020 at 12:34:02PM +0100, Uwe Kleine-König wrote:
> On 2/7/20 9:29 AM, Martin KaFai Lau wrote:
> > I believe x == 1 needs an extra case since ilog2(0) won't work.
> > 
> > Since this function (map creation) is not on the fast path,
> > I currently opt for Linus's suggestion which its code is more
> > self-explanatory.
> 
> If you put my suggestion in a macro that is called for example
> 
> 	ilog2_roundup()
> 
> you might have both: easier code and self-explanation.

This is, essentially, the same as the existing order_base_2().

Best regards,
-- Luc