Re: [PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to replace marker scans

[David Laight]

On Sat, 19 Sep 2026 21:58:56 -0600
Jim Cromie <jim.cromie@xxxxxxxxx> wrote:

> From: Jim Cromie <jim.cromie@xxxxxxxxx>
> To: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Cc: Lorenzo Stoakes <ljs@xxxxxxxxxx>, Kees Cook <kees@xxxxxxxxxx>,   Masahiro Yamada <masahiroy@xxxxxxxxxx>, linux-kernel@xxxxxxxxxxxxxxx,   linux-kbuild@xxxxxxxxxxxxxxx, bpf@xxxxxxxxxxxxxxx,   Jim Cromie <jim.cromie@xxxxxxxxx>
> Subject: [PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to  replace marker scans
> Date: Sat, 19 Sep 2026 21:58:56 -0600
> 
> The compressed symbol table (kallsyms_names) packs ~130k kernel symbol
> names, in address order, into variable-length records with format
> [<len>][<tokenized-strings-wo-\0>].
> 
> This layout optimizes address-to-name mapping, but name-to-address
> lookups require a linear scan.  To accelerate lookups, kallsyms_markers
> was added to record the offset of every 256th entry, cutting the
> worst-case walk from 130k to ~128 hops on average.  However, this
> still leaves substantial work: during a 17-step binary search in
> kallsyms_lookup_names(), the marker walk repeats at every step
> (17 * 128), decoding ~2,176 record length headers per lookup.
> Address-to-name resolution (sprint_symbol) pays the same 0..255 hop
> penalty on every call.
> 
> Introduce kallsyms_names_offsets, a 3-byte-per-symbol direct index into
> the compressed kallsyms_names table.  scripts/kallsyms.c emits this
> table at build-time while writing kallsyms_names, capturing the exact
> byte offset for each symbol.  Using 24 bits covers up to 16 MiB of
> compressed symbol names, easily spanning the ~2.3 MiB table while
> saving 25% space compared to u32 entries.
> 
> With kallsyms_names_offsets:
> 
> 0. get_symbol_offset() performs an O(1) 3-byte table lookup, eliminating
>    the ~2,176 header scans per name search.
> 
> 1. Drop the legacy kallsyms_markers table, saving ~2 KiB of .rodata.
> 
> 2. Unroll the shift loop in get_symbol_seq() to match
>    get_symbol_offset() as a direct 3-byte big-endian load.

Why big-endian?
Most cpu are little endian, gcc 16 and clang 10 will replace two of
the 8bit loads with a 16bit one.

I'd also comment that the overhead is 3 bytes/symbol - with a note
about the average symbol size (excluding rust).
The +573kB sounds like a lot - but isn't that much compared to the
size of the table.

You should only need half the table.
The only odd index you need to check is the last one, and you'll have
just read the symbol below it.

David