[PATCH 0/3] kallsyms: Accelerate symbol name lookups by ~19x

[Jim Cromie]

kallsyms_lookup_names() resolves symbol names to addresses using a
17-step binary search over kallsyms_names[] (~191k symbols on x86_64).
At each step of the search, two bottlenecks compound to create
substantial lookup latency:

0. Marker scanning: get_symbol_offset() scans sequentially from the
   nearest 256-symbol marker, decoding an average of ~128 ULEB128 record
   headers per probe (~2,176 header decodes per lookup).

1. Redundant string expansion: kallsyms_expand_symbol() decompresses
   the entire candidate symbol into a 512-byte stack buffer (namebuf)
   before calling strcmp(), even though ~94% of binary search probes
   mismatch on the first 1-2 characters.

Together, these bottlenecks impose a ~4.3 us latency penalty per hit and
~3.8 us per miss.

This 3-patch series eliminates both overheads while keeping the symbol
table strictly in sequential address order:

0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
   measure name hits, name misses, sprint_symbol(), and table iteration
   latency, with built-in correctness validation and a sysfs trigger.

1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
   index into kallsyms_names[].  This turns get_symbol_offset() into an
   O(1) table lookup, dropping the ~2,176 marker hops per lookup and
   eliminating the legacy kallsyms_markers[] table.

2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries
   against compressed tokens incrementally on the fly, bailing out on
   the first mismatched character without expanding subsequent tokens.
   This drops the 512-byte namebuf buffer from the kernel stack.

Context & Lineage:

This series was originally developed and benchmarked on mainline (v7.3-rc3).
To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
kernel with pigz if available").

Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
direct binary streaming path (write_incbin).

Glomming onto Lorenzo's build-time acceleration push extends the speedup
theme into runtime: his series speeds up the compile and link, and this
series speeds up runtime symbol lookups by ~18x.

Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):

Metric                    Baseline      Patched       Speedup
-----------------------------------------------------------------
Name Search Hit           4,370 ns      247 ns        17.7x
Name Search Miss          3,860 ns      195 ns        19.8x
sprint_symbol               440 ns      441 ns        parity
sprint_symbol_no_offset     315 ns      307 ns        parity
Table Full Walk           14,500 us   14,437 us       parity

Address-to-name resolution (sprint_symbol) and sequential table walks
(/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
hardware prefetching.

Hardware PMU Event Counters (perf stat via sysfs run_test trigger):

$ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
    sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'

Counter                 Baseline          Patched           Delta
------------------------------------------------------------------------
Wall-clock elapsed      1.746 s           0.852 s           -51.2%
CPU cycles              7,320,048,030     3,628,523,081     -50.4%
Instructions            9,943,172,792     5,034,260,318     -49.4%
Branches                2,391,663,821     1,173,258,010     -51.0%
Branch-misses             117,241,513        99,805,938     -14.9%
Cache-misses               84,996,149           731,025     -99.1%

Dropping marker scans and avoiding redundant string expansions cuts
4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
(-99.1%) across the test workload.

Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
kallsyms_markers[].

Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
---
Jim Cromie (3):
      kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
      kallsyms: Add 3-byte index into compressed symbols to replace marker scans
      kallsyms: Match compressed tokens on the fly during binary search

 kernel/kallsyms.c          | 138 ++++++++++++++-------------
 kernel/kallsyms_internal.h |   2 +-
 lib/Kconfig.debug          |  10 ++
 lib/Makefile               |   1 +
 lib/test_kallsyms_perf.c   | 228 +++++++++++++++++++++++++++++++++++++++++++++
 scripts/kallsyms.c         |  30 +++---
 6 files changed, 322 insertions(+), 87 deletions(-)
---
base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
change-id: 20260919-ksyms-tune-e22a42d8a31a

Best regards,
-- 
Jim Cromie <jim.cromie@xxxxxxxxx>