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@gmail.com>
---
Changes in v4:
- In patch 1, ignore early boot invocations in param_set_trigger() when
  system_state < SYSTEM_RUNNING to prevent NULL pointer dereference in
  ktime_get_ns() prior to timekeeping_init() (addresses Sashiko AI review).
- In patch 1, prevent sysfs TOCTOU divide-by-zero panic: reject num_iters
  == 0 in param setter, snapshot iters locally via READ_ONCE, and serialize
  runs with bench_lock mutex (addresses Sashiko AI review).
- In patch 1, eliminate multi-second boot stall: add run_on_boot parameter
  (default false) so late_initcall only runs benchmark when explicitly
  requested (addresses Sashiko AI review).
- In patch 1, chunk lookup loops in 4096-iter batches with cond_resched()
  outside the timing bracket to prevent preemption sleep time from
  inflating reported latency (addresses Sashiko AI review).
- In patch 3, annotate dyn_kallsyms_offsets declaration with __rcu to
  satisfy sparse type checking and prevent address-space warnings across
  rcu_assign_pointer() and rcu_dereference() (addresses Sashiko AI review).
- In patch 3, use rcu_replace_pointer() with lockdep_is_held() during
  batch teardown to atomically read and clear the pointer while satisfying
  sparse address-space constraints (addresses Sashiko AI review).
- Link to v3: https://lore.kernel.org/r/20260922-ksyms-tune-v3-0-681a34ea05d9@gmail.com

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@gmail.com

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@gmail.com

---
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          | 212 ++++++++++++++++++++++------
 kernel/kallsyms_selftest.c |  16 +++
 lib/Kconfig.debug          |  10 ++
 lib/Makefile               |   1 +
 lib/test_kallsyms_perf.c   | 341 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 547 insertions(+), 46 deletions(-)
---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a

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

On Tue, Sep 22, 2026 at 02:08:17PM -0600, Jim Cromie wrote:
> 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.
> [...]
> - Dropped .rodata image footprint addition from +573 KiB to 0 KiB,
>   addressing Kees Cook's memory footprint objection.

Ah, very cool; thanks for giving the dynamic route a try! (Also, please
wait a few days between versions and give humans some time to reply.)

I spent some time trying to understand all the timings here, and with
a problem statement of "tens of thousands of functions", I'd want
to understand how common that workload is. Even module loading isn't
anywhere near that high, and AIUI, most kprobe loads of that size are
roughly one-offs, and what Jiri measured was the most extreme possible
attach we could see, and that is a synthetic workload. (And kallsyms
was ~7% of the attach.) I struggle to see a problem that needs solving.

What we have today is a 1:256 mapping, so the walk penalty in ~128 steps
per symbol lookup. With your proposed 1:1 there's no walk penalty, but
we either pay a lifetime .rodata cost or a startup/teardown cost and
temporary dynamic allocation cost.

Right now the startup time for the dynamic table appears to need ~1500
symbol look-ups to break even compared to today's 1:256 mapping.

How would a 1:8 table in .rodata compare, for example? It's not 1:1 but
it should get you something like 95% of the speed (84ns) for a 8x less
.rodata memory compared to the 1:1 in .rodata. And the table might be
small enough that cache locality helps more?

Anyway, I'd be curious to see the benchmarks at alternative densities as
there is a clear space vs time trade-off here, and moving into dynamic
allocation changes the measurements again.

But dominating all of this is the question of how common it is to do
tens of thousands of symbol lookups with a fast path need. As a 1-time
cost or even every few hours, it's hard to justify either size (1:1 in
.rodata for all Linux systems) or complexity (RCU-locked 1:1 allocation
built on the fly).

-Kees

-- 
Kees Cook

On Wed, 23 Sep 2026 00:12:29 -0700
Kees Cook <kees@kernel.org> wrote:

I think you are at ~15x now.

> On Tue, Sep 22, 2026 at 02:08:17PM -0600, Jim Cromie wrote:
> > 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.
> > [...]
> > - Dropped .rodata image footprint addition from +573 KiB to 0 KiB,
> >   addressing Kees Cook's memory footprint objection.  
> 
> Ah, very cool; thanks for giving the dynamic route a try! (Also, please
> wait a few days between versions and give humans some time to reply.)
> 
> I spent some time trying to understand all the timings here, and with
> a problem statement of "tens of thousands of functions", I'd want
> to understand how common that workload is. Even module loading isn't
> anywhere near that high, and AIUI, most kprobe loads of that size are
> roughly one-offs, and what Jiri measured was the most extreme possible
> attach we could see, and that is a synthetic workload. (And kallsyms
> was ~7% of the attach.) I struggle to see a problem that needs solving.
> 
> What we have today is a 1:256 mapping, so the walk penalty in ~128 steps
> per symbol lookup.

According the the commit message(s) the existing code does a full binary
chop so gets the ~128 step walk penalty for every stage.
If the new index were rounded down to a multiple of 256 (the algorithm
works with any index between the existing high and low ones) then the
walk penalty would only be needed to find the last item in the 256 entry
block.

I can think of a variety of schemes for scanning the last 256 entries.
A simple (optimised) linear scan may not be too bad.
Or save some offsets in a small on-stack u16[] array as you scan for
an item to compare against - allowing a binary chop through the scanned
items (may need a final linear scan).

David

> With your proposed 1:1 there's no walk penalty, but
> we either pay a lifetime .rodata cost or a startup/teardown cost and
> temporary dynamic allocation cost.
> 
> Right now the startup time for the dynamic table appears to need ~1500
> symbol look-ups to break even compared to today's 1:256 mapping.
> 
> How would a 1:8 table in .rodata compare, for example? It's not 1:1 but
> it should get you something like 95% of the speed (84ns) for a 8x less
> .rodata memory compared to the 1:1 in .rodata. And the table might be
> small enough that cache locality helps more?
> 
> Anyway, I'd be curious to see the benchmarks at alternative densities as
> there is a clear space vs time trade-off here, and moving into dynamic
> allocation changes the measurements again.
> 
> But dominating all of this is the question of how common it is to do
> tens of thousands of symbol lookups with a fast path need. As a 1-time
> cost or even every few hours, it's hard to justify either size (1:1 in
> .rodata for all Linux systems) or complexity (RCU-locked 1:1 allocation
> built on the fly).

Also how may lookups do you need in a batch to break even?

David

> 
> -Kees
>