ld.lld: error: kernel image bigger than KERNEL_IMAGE_SIZE

[whentojump]

After llvm/llvm-project#82448 gets merged LLVM 19 no longer works.

During build:

  CALL    scripts/checksyscalls.sh
  CALL    scripts/atomic/check-atomics.sh
  DESCEND objtool
  CHK     include/generated/compile.h
  GEN     .version
  CHK     include/generated/compile.h
  UPD     include/generated/compile.h
  CC      init/version.o
  AR      init/built-in.a
  LD      vmlinux.o
  MODPOST vmlinux.symvers
WARNING: modpost: vmlinux.o(.text+0xcc807): Section mismatch in reference from the function test_bit() to the variable .init.data:numa_nodes_parsed
The function test_bit() references
the variable __initdata numa_nodes_parsed.
This is often because test_bit lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

WARNING: modpost: vmlinux.o(.text+0xcc862): Section mismatch in reference from the function __nodes_weight() to the variable .init.data:numa_nodes_parsed
The function __nodes_weight() references
the variable __initdata numa_nodes_parsed.
This is often because __nodes_weight lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

WARNING: modpost: vmlinux.o(.text+0xcc8bb): Section mismatch in reference from the function __first_node() to the variable .init.data:numa_nodes_parsed
The function __first_node() references
the variable __initdata numa_nodes_parsed.
This is often because __first_node lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

WARNING: modpost: vmlinux.o(.text+0xcc943): Section mismatch in reference from the function __next_node() to the variable .init.data:numa_nodes_parsed
The function __next_node() references
the variable __initdata numa_nodes_parsed.
This is often because __next_node lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

WARNING: modpost: vmlinux.o(.text+0xcc9b8): Section mismatch in reference from the function set_bit() to the variable .init.data:numa_nodes_parsed
The function set_bit() references
the variable __initdata numa_nodes_parsed.
This is often because set_bit lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

WARNING: modpost: vmlinux.o(.text+0xcc9f8): Section mismatch in reference from the function set_bit() to the variable .init.data:numa_nodes_parsed
The function set_bit() references
the variable __initdata numa_nodes_parsed.
This is often because set_bit lacks a __initdata
annotation or the annotation of numa_nodes_parsed is wrong.

  MODINFO modules.builtin.modinfo
  GEN     modules.builtin
  LD      .tmp_vmlinux.kallsyms1
ld.lld: error: kernel image bigger than KERNEL_IMAGE_SIZE
ld.lld: error: kernel image bigger than KERNEL_IMAGE_SIZE
ld.lld: error: kernel image bigger than KERNEL_IMAGE_SIZE
make: *** [Makefile:1233: vmlinux] Error 1

More information will be posted here.

Note: if we follow the current documentation we will checkout a snapshot earlier this week (2024-06-11) and should not be affected.

[sugamadhiakri]

I was able to reproduce this!

[whentojump]

@sugamadhiakri Thanks for confirming! Did you also try checking out f5dcfb9968a3 of LLVM and completing the rest of workflow? That commit should work.

About this problem, I'm thinking of a few things we could do,

1. In previous successful runs, understand the binary layout and measure sections sizes etc of vmlinux.
2. Apply techniques mentioned here to reduce the binary size.
3. Find a proper threshold and apply -fmcdc-max-conditions, -fmcdc-max-test-vectors flags. See [MC/DC][Coverage] Loosen the limit of NumConds from 6 llvm/llvm-project#82448.
4. Can we separate .covmapping from the kernel binary? Related: mailing list, Alan's talk

[whentojump]

5. "Meta's option" of debuginfo correlation Talk, RFC
6. Maybe even modify KERNEL_IMAGE_SIZE (thanks to @oppelt-boeing for his input)

[whentojump]

For (6), I experimented locally with fb6e024f49ddbf1a018eccab7ccfa7c1f41964d0. We can circumvent the linker script assertion by

diff --git a/arch/x86/kernel/vmlinux.lds.S b/arch/x86/kernel/vmlinux.lds.S
index 412ab19aa..9ff93b586 100644
--- a/arch/x86/kernel/vmlinux.lds.S
+++ b/arch/x86/kernel/vmlinux.lds.S
@@ -495,8 +495,10 @@ SECTIONS
 /*
  * The ASSERT() sink to . is intentional, for binutils 2.14 compatibility:
  */
+/*
 . = ASSERT((_end - LOAD_OFFSET <= KERNEL_IMAGE_SIZE),
 	   "kernel image bigger than KERNEL_IMAGE_SIZE");
+*/

 #ifdef CONFIG_X86_64
 /*

Build can finish but boot fails, which is not too surprising. What's important though, is the vmlinux layout with default limits (-fmcdc-max-conditions=32767 -fmcdc-max-test-vectors=2147483646):

Section Headers:
  [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
  [19] __llvm_prf_data   PROGBITS        ffffffff83489660 2689660 af4600 00  WA  0   0  8
  [20] __llvm_prf_cnts   PROGBITS        ffffffff83f7dc60 317dc60 9fb9a8 00  WA  0   0  8
  [21] __llvm_prf_names  PROGBITS        ffffffff84979608 3b79608 330bb4b 00  AR  0   0  1
  [22] __llvm_prf_bits   PROGBITS        ffffffff87c85153 6e85153 4760f744 00  WA  0   0  1
  [23] __llvm_covfun     PROGBITS        0000000000000000 4ed27000 18e780d7 00   R  0   0  8
  [24] __llvm_covmap     PROGBITS        0000000000000000 67b9f0d8 5037cc 00   R  0   0  8

[whentojump]

For (3), I experimented locally with the same LLVM commit. I can confirm we are be able to revert to 6-condition limit. Several CI runs are queueing to binary-search the threshold. Updates will be posted in this reply.

[whentojump]

For (5), this post claims their solution is probably more generalizable than debuginfo correlation

Initially, I explored debug info correlation, which is used for PGO with value profiling disabled. However, it currently only works with DWARF and it's be hard to add such artificial debug info for every function in to CodeView which is used on Windows. So, offloading profile metadata sections at runtime seems to be a platform independent option.

The idea is to build a binary with __llvm_prof_data and __llvm_prf_names's equivalents and another without. The first larger binary can be used for offline analysis and only the second smaller binary has to be loaded at run time.

• I tried out user space examples. It does not work with MC/DC. Will report it.
• It implies we have to produce that large binary anyway, which is not ideal
• I will take a look at debuginfo correlation as well

[whentojump]

According to the CI runs, the threshold seems

• max <= 44 : pass
• max >= 45 : fail

This value in some sense matches our earlier analysis of kernel source: the maximum number of decision was exactly 45, mostly contributed by those macros checking CPUID, e.g. boot_cpu_has.

By ignoring KERNEL_IMAGE_SIZE during linking, we can forcibly obtain a vmlinux that won't boot, but it does tell us what sections are growing the most in the binary. Here's the comparison:

1. Setting max to 44. Pass. Link (GitHub account login required to see the log)

     [Nr] Name              Type            Address          Off    Size   ES Flg Lk Inf Al
     [19] __llvm_prf_data   PROGBITS        ffffffff83489660 2689660 af4600 00  WA  0   0  8
     [20] __llvm_prf_cnts   PROGBITS        ffffffff83f7dc60 317dc60 9fb9a8 00  WA  0   0  8
     [21] __llvm_prf_names  PROGBITS        ffffffff84979608 3b79608 330bb4b 00  AR  0   0  1
     [22] __llvm_prf_bits   PROGBITS        ffffffff87c85153 6e85153 00f744 00  WA  0   0  1
     [23] __llvm_covfun     PROGBITS        0000000000000000 7727000 18e4fc8f 00   R  0   0  8
     [24] __llvm_covmap     PROGBITS        0000000000000000 20576c90 50acc0 00   R  0   0  8
   

2. Setting max to 45. Fail. Link (GitHub account login required to see the log)

     [19] __llvm_prf_data   PROGBITS        ffffffff83489660 2689660 af4600 00  WA  0   0  8
     [20] __llvm_prf_cnts   PROGBITS        ffffffff83f7dc60 317dc60 9fb9a8 00  WA  0   0  8
     [21] __llvm_prf_names  PROGBITS        ffffffff84979608 3b79608 330bb4b 00  AR  0   0  1
     [22] __llvm_prf_bits   PROGBITS        ffffffff87c85153 6e85153 4760f744 00  WA  0   0  1
     [23] __llvm_covfun     PROGBITS        0000000000000000 4ed27000 18e780d7 00   R  0   0  8
     [24] __llvm_covmap     PROGBITS        0000000000000000 67b9f0d8 50acc0 00   R  0   0  8
   

3. Setting max to 32767 (current LLVM limit). Fail. Link (GitHub account login required to see the log)

     [19] __llvm_prf_data   PROGBITS        ffffffff83489660 2689660 af4600 00  WA  0   0  8
     [20] __llvm_prf_cnts   PROGBITS        ffffffff83f7dc60 317dc60 9fb9a8 00  WA  0   0  8
     [21] __llvm_prf_names  PROGBITS        ffffffff84979608 3b79608 330bb4b 00  AR  0   0  1
     [22] __llvm_prf_bits   PROGBITS        ffffffff87c85153 6e85153 4760f744 00  WA  0   0  1
     [23] __llvm_covfun     PROGBITS        0000000000000000 4ed27000 18e780d7 00   R  0   0  8
     [24] __llvm_covmap     PROGBITS        0000000000000000 67b9f0d8 50acc0 00   R  0   0  8
   

Observations:

• Section sizes of __llvm_prf_data, __llvm_prf_cnts, __llvm_prf_names and __llvm_covmap are exactly the same in three runs.
• The quoted part of readelf output for (2) and (3) are exactly the same, indicating no code which was previously not instrumented newly gets counted.
• When those 45-cond decisions get counted, that is, from (2) to (3):
  • __llvm_prf_bits size grows from 00f744 to 4760f744
  • __llvm_covfun size grows from 18e4fc8f to 18e780d7

Implications:

• Apparently __llvm_prf_bits is breaking things much more than other sections. Since __llvm_prf_bits is loaded and updated at run time, any approach that attempts to remove sections not used online (namely __llvm_prf_data, __llvm_prf_names, __llvm_covfun, __llvm_covmap) from the binary cannot solve this problem
• Some of ideas above are still meaningful though to make the workflow lightweight
• We should probably still set the max low,
  • To speed up the workflow
  • In case some day kernel introduces decisions with 32-45 conditions. (32 was the second largest number of conditions according to our previous analysis).

[whentojump]

More measurement where the number 32 further confirms my earlier point

-fmcdc-max-conditions	Section size of __llvm_prf_bits	Full readelf output (GitHub login required)
31	00f73f	link
32	00f744	link
44	00f744	link
45	4760f744	link
32767	4760f744	link

[darko-marinov]

Is the size in bytes? (Does that tool have -h option like many utilities that report size?) So it goes from ~63kB to ~1.1GB? Ignoring those decisions with 45 conditions is clearly the way to go. Another option would be to consider whether the new "bitmap" tracking can be improved (if multiple conditions are mutually exclusive, one may have a more compact encoding).

[whentojump]

Is the size in bytes? (Does that tool have -h option like many utilities that report size?) So it goes from ~63kB to ~1.1GB?

Yes, (no), yes.

new "bitmap"

The encoding of bitmap has not changed. What llvm/llvm-project#82448 does is

• Newly track decisions with 7-32767 conditions
• Reduce the number of bits in the bitmap for each decision. For an $n$-condition decision we don't need all $2^n$ bits because some are in fact duplicate due to short-circuit effect. I believe this is already the best we can do if every condition is independent

if multiple conditions are mutually exclusive, one may have a more compact encoding.

Do you want us (university or Boeing) to do this?

[darko-marinov]

The encoding of bitmap has not changed [...] llvm/llvm-project#82448 [...]
Reduce the number of bits in the bitmap for each decision.

Well, if 82448 reduced the number of bits, then it changes the encoding. :)

I believe this is already the best we can do if every condition is independent

I thought the case with 45 conditions has mostly related conditions, like FLAGS == 2 || FLAGS == 3 || FLAGS == 10 ...

Do you want us (university or Boeing) to do this?

I don't think this is a high priority now if we can build Linux (while not handling just one macro with 45 conditions that appears in many places). But it could be something to revisit later on.