Re: [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x

[David Laight]

On Wed, 23 Sep 2026 00:12:29 -0700
Kees Cook <kees@xxxxxxxxxx> 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
>