kallsyms: index symbols by token to speed up table compression

The kallsyms program compresses symbols by figuring out the most commonly
used substrings in all of the input symbols then uses special character
codes to represent them.

For instance, 0xf7 might end up representing "write_", then every single
symbol that contains "write_" can use 0xf7 as a shorthand and save 5 bytes
each time.

'Special' character codes are any byte value that is not used in any
symbol, either due to being an invalid character, or not being present in
any symbol (e.g. if no symbol contains 'z', then 'z' can be used as special
character).

It does this by first figuring out which special characters are available
in insert_real_symbols_in_table(), then iterating through every available
special character, counting how many times each pair of adjacent characters
appear in symbols in build_initial_token_table().

These adjacent pairs are known as 'tokens'.

Token counts are initially obtained by build_initial_token_table(), then
optimize_result() calls find_best_token() to determine the token that
appeared the most number of times and assigns it the next special
character.

Finally, optimize_result() calls compress_symbols() to replace every token
in every symbol with its special character, which updates token_profit[] as
it does so.

This process is repeated for each remaining available special character,
with tokens now perhaps containing previously assigned special
characters (e.g. if 'wr' was assigned 0x80, then the token representing
'wri' would be '\x80i').

This compresses that token by 50% in each symbol it appears in (two bytes
are now represented by one) and thus by repeatedly doing this kallsyms
obtains good symbol compression.

However, compress_symbols() is seriously inefficient - it iterates through
EVERY symbol for EVERY special character assignment, i.e. ~256 *
nr_symbols.

Modern x86-64 kernels, for instance, have ~158,000 symbols, so millions of
iterations are performed, most of which are entirely unnecessary (tokens
don't appear in most symbols).

In practice kallsyms spends half its runtime doing this, two or three times
per vmlinux link step.

Fix this by tracking which symbols each token appears in token_syms[], and
only compress symbols which actually need to be updated.

Each time a token is compressed that token can no longer appear in any
symbol, so that token_syms[] entry can be freed.

However new token_syms[] entries must be created for each new token
containing the assigned special character, but this is bounded by the
number of replacements in the symbol which is very small.

In testing on an x86-64 platform using clang, each kallsyms invocation
dropped from 0.59s to 0.33s with CONFIG_KALLSYMS_ALL set and from 0.38s to
0.22s without it set.

The data was carefully checked and verified to be byte-for-byte identical
for six symbol sets (two vmlinux passes, vmlinux.o, three userspace
binaries) with all option combinations.

As part of this change, additionally refactor the code to be a little
easier to follow.

kallsyms runs two or three times on the serial tail of every build that
links vmlinux, no-op builds do not link and are unchanged.

Whole build, 128-thread Threadripper 9980X, best of N runs:

                                         before   after     delta
                                         -------------------------------
  x86 defconfig, touch mm/vma.c, gcc       11.1s    10.6s    -0.53s (-5%)
  x86 defconfig, touch mm/vma.c, clang     11.1s    10.5s    -0.64s (-6%)
  x86 defconfig, clean, gcc                32.3s    31.3s     -1.0s (-3%)
  x86 defconfig, clean, clang              34.2s    33.3s    -0.89s (-3%)
  x86 allmodconfig, touch mm/vma.c, gcc    39.7s    38.7s     -1.0s (-3%)
  x86 allmodconfig, touch mm/vma.c, clang  40.3s    39.1s     -1.3s (-3%)

Assisted-by: LLM
Reviewed-by: Kees Cook <kees@kernel.org>
Signed-off-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
Link: https://patch.msgid.link/20260923-build-speedup-v4-2-73128809a4a4@kernel.org
Signed-off-by: Nathan Chancellor <nathan@kernel.org>

0 files changed, 0 insertions, 0 deletions