[PATCH v3 0/4] kallsyms: Accelerate symbol name lookups by ~19x
From: Jim Cromie
Date: Tue Sep 22 2026 - 15:10:49 EST
kallsyms_lookup_names() resolves symbol names to addresses using a
17-step binary search over kallsyms_names[] (~184k symbols on x86_64).
At each step of the search, two bottlenecks compound to create
substantial lookup latency:
0. 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 (~580 ns per lookup).
1. Marker scanning: get_symbol_offset() scans sequentially from the
nearest 256-symbol marker in kallsyms_names[], decoding an average
of ~128 ULEB128 record headers per probe (~2,176 header decodes,
consuming ~3,230 ns per lookup).
Together, these bottlenecks impose a ~3.8 us latency penalty per hit and
~3.6 us per miss.
This 4-patch series eliminates both overheads in a structured
progression while keeping the symbol table strictly in sequential
address order and adding 0 bytes to .rodata:
0. Patch 1 adds lib/test_kallsyms_perf, a microbenchmark module built
directly into vmlinux (CONFIG_TEST_KALLSYMS_PERF=bool) to benchmark
unindexed vs dynamic indexed name searches, address resolution, and
table iteration latency without exporting internal kallsyms iterators
to loadable modules.
1. Patch 2 introduces kallsyms_strcmp_symbol() to compare ASCII queries
against compressed tokens 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 and saves ~530 ns
per lookup on unmodified marker infrastructure.
2. Patch 3 introduces a dynamic u32 lookup index bracketed by
kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end().
It allocates ~736 KiB in transient RAM via kvmalloc_array() only
while bulk workloads (BPF attach, module loading) run, resolves
each probe in O(1) with 0 hops, and leaves .rodata bloat at exactly
0 bytes while retaining kallsyms_markers[] as fallback. Both
test_kallsyms_perf and kallsyms_selftest are updated to benchmark
batch resolution side-by-side.
3. Patch 4 inlines and unrolls get_symbol_seq() 24-bit sequence index
reconstruction into direct byte shifts, eliminating loop overhead
on inner binary search probes.
Live Microbenchmark Progression (via test_kallsyms_perf, 100k iters):
Metric Baseline (1) Token Match (2) Batch Index (3) Total Speedup
------------------------------------------------------------------------------------------
Name Search Hit 3,811 ns 3,280 ns 246 ns 15.5x
Name Search Miss 3,625 ns 3,095 ns 196 ns 18.5x
sprint_symbol 412 ns 412 ns 412 ns parity
sprint_symbol_no_offset 300 ns 300 ns 300 ns parity
Table Full Walk 13,626 us 13,626 us 13,626 us parity
Kernel stack buffer 512 B 0 B 0 B -512 B
In-Tree Selftest Verification (CONFIG_KALLSYMS_SELFTEST, 184k symbols):
In addition to test_kallsyms_perf, the existing upstream selftest in
kernel/kallsyms_selftest.c was run across all 183,990 symbols on boot,
repeating all tests inside an active batch window:
Metric Unindexed (markers) Batch Index (active) Delta
-----------------------------------------------------------------------------------
kallsyms_lookup_name() (avg) 3,926 ns 675 ns 5.8x faster
kallsyms_lookup_name() (min) 311 ns 171 ns 1.8x faster
on_each_match_symbol() 3,507 ns 1,142 ns 3.1x faster
kallsyms_on_each_symbol() 14.7 ms 15.5 ms parity
Basic function validation PASS PASS 100% correct
Batch setup (184k entries) N/A 1,037 us ~1.0 ms
Batch teardown (sync RCU) N/A 3,440 us ~3.4 ms
Address-to-name resolution (sprint_symbol) and sequential table walks
(/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
hardware prefetching.
Memory footprint: +0 KiB .rodata added to kernel image. Transient RAM
is ~736 KiB (184k * 4 bytes) allocated only during active batch
lookup sessions.
Signed-off-by: Jim Cromie <jim.cromie@xxxxxxxxx>
---
Changes in v3:
- Reorder series: place on-the-fly token matching (patch 2) ahead of
dynamic batch lookup index (patch 3), establishing an active proof of
incremental performance deltas across all steps (addresses David
Laight review).
- Add patch 4: inline and unroll get_symbol_seq() 24-bit sequence index
reconstruction into direct byte shifts (addresses David Laight
review).
- In patch 1, configure CONFIG_TEST_KALLSYMS_PERF as a built-in test
(bool) rather than a module (tristate) and drop kallsyms iterator
EXPORT_SYMBOL_GPL exports to avoid exposing internal kernel symbol
data (addresses Sashiko AI review).
- In patch 2, optimize kallsyms_strcmp_symbol() by dropping
skipped_first tracking and checking len at the bottom of the token
loop (addresses David Laight review).
- In patch 3, rely on get_symbol_data() helper introduced in patch 2 to
preserve bisectability (addresses Sashiko AI review).
- In patch 3, fix use-after-free race on dyn_kallsyms_offsets: bracket
table dereference and array read with rcu_read_lock() and replace
rcu_dereference_raw() with rcu_dereference() inside
get_symbol_offset() to protect external readers (lookup_symbol_name,
kallsyms_lookup_buildid, reset_iter) against concurrent batch
teardown (addresses Sashiko AI review).
- In patch 3, update kallsyms_selftest to add a second lookup pass
bracketed by batch start/end to report batch latency in the in-tree
selftest.
- Drop 'default m' from lib/Kconfig.debug.
- Fix soft lockup risks by adding cond_resched() every 16k iterations in
test_kallsyms_perf loops.
- Replace direct 64-bit integer divisions with div_u64() to fix 32-bit
builds.
- Guard against divide-by-zero when num_iters=0.
- Replace tcp_v4_rcv with panic in hit_symbols to prevent failures wo
CONFIG_INET.
- Add batch lookup setup/teardown timing and query amortization
break-even logging to test_kallsyms_perf.
- Move David Laight to series-wide Cc on cover letter, dropping trailer
from patch 3.
- Link to v2: https://lore.kernel.org/r/20260922-ksyms-tune-v2-0-a333ee31eac7@xxxxxxxxx
Changes in v2:
- Replaced static build-time 3-byte offset table with a dynamic u32
index bracketed by kallsyms_lookup_batch_start() and
kallsyms_lookup_batch_end().
- Dropped .rodata image footprint addition from +573 KiB to 0 KiB,
addressing Kees Cook's memory footprint objection.
- Native u32 loads in transient RAM eliminate 24-bit big-endian shifts
and unaligned loads, addressing David Laight's endianness critique.
- Direct O(1) table indexing provides 0 hops for all symbol lookups
without remainder logic or odd/even branching.
- Restored scripts/kallsyms.c and kernel/kallsyms_internal.h to pristine
state, leaving legacy kallsyms_markers[] as safety fallback.
- Rebased out Lorenzo Stoakes' kbuild series; this series is now
completely decoupled and applies cleanly directly onto mainline.
- Updated test_kallsyms_perf to benchmark unindexed marker scans and
dynamic index side by side in a single run.
- Link to v1: https://lore.kernel.org/r/20260919-ksyms-tune-v1-0-d85c97da1a32@xxxxxxxxx
---
Jim Cromie (4):
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
kallsyms: Match compressed tokens on the fly during binary search
kallsyms: Add dynamic lookup index for batch resolution
kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
include/linux/kallsyms.h | 13 +++
kernel/kallsyms.c | 213 ++++++++++++++++++++++++++--------
kernel/kallsyms_selftest.c | 16 +++
lib/Kconfig.debug | 10 ++
lib/Makefile | 1 +
lib/test_kallsyms_perf.c | 281 +++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 488 insertions(+), 46 deletions(-)
---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a
Best regards,
--
Jim Cromie <jim.cromie@xxxxxxxxx>