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

[Kees Cook <kees@kernel.org>]

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