Re: [PATCH v6 0/3] kallsyms: Accelerate symbol name lookups by ~7x

On Sun 2026-09-27 06:57:28, David Laight wrote:

On Sat, 26 Sep 2026 13:38:59 -0700
Andrew Morton [off-list ref] wrote:

quoted

On Sat, 26 Sep 2026 13:40:11 -0600 Jim Cromie [off-list ref] wrote:

quoted

As measured by kernel/kallsyms_selftest across ~184k symbols,
kallsyms_lookup_names() binary search takes ~6.1 us per lookup due to
two inner-loop costs:  

We don't have a kallsyms maintainer afaik.  Petr is pretty active in
there so let's give him a hopeful cc.

I am not sure if I could find time to look at the code deeper anytime
soon. I put it on my TODO list but I do not promise anything...

Anyway, the kallsyms search speed might be interesting for tracing,
livepatching, bpf, and maybe module loader. AFAIK, Geert used to
interested into the kernel size. Adding them into Cc...

Best Regards,
Petr

quoted

quoted

0. Candidate symbols are fully decompressed into a 512-byte stack buffer
   before calling strcmp(), even though non-matching steps could choose on the
   first differing character (0..N-1).

1. Probes scan sequentially from 256:1 markers in kallsyms_names[],
   decoding an average of 127.5 symbols per probe (~2,170 hops across a
   17-step search).

This 3-patch series addresses both:

0. Patch 1 introduces kallsyms_strcmp_symbol() to compare ASCII queries
   against compressed tokens on the fly, bailing out on first mismatch.
   Drops the 512-byte stack buffer and saves ~530 ns.

1. Patch 2 increases marker density from 256:1 to 16:1, cutting average
   scan distance from 127.5 to 7.5 hops and dropping lookup latency from
   6,102 ns to 866 ns for +42.2 KiB of .rodata.

2. Patch 3 inlines and unrolls get_symbol_seq() 24-bit reconstruction.

Results (kernel/kallsyms_selftest across ~184k symbols):
- Baseline (256:1):  6,102 ns
- Patch 1 (strcmp):  5,572 ns (-530 ns)
- Patch 2 (16:1):      866 ns (7.0x faster)
- Memory: +42.2 KiB .rodata, 0 bytes dynamic RAM  

Can you better explain the tradeoffs here?  Increased memory use?  If
so how much?  Is any change in build time expected?

I've had a thought of a scheme that should give most of the ~19x
improvement of the original patch without increasing the data size and
with only a small increase in code size.
The downside is a slight slow down for sequential access.

The thing to do is replace the 24bit 'symbol number' in the 'sorted by name'
list with the offset of the beginning of the name.
(For very large kernels it may need to be 32bit.)
The binary search for the symbol name then doesn't need a linear scan
and also loses one level of indirection.
You then need to do another binary search over the 'offset of every 256th
entry' table, followed by a linear search to find the correct address.

For sequential access there is a reasonable chance the next symbol is in
the same 256 symbol block (in address order), that can be quickly checked.

I got the code to run in userspace yesterday (with a real kernel symbol
table), I might look at some changes later today.

David

quoted

What isn't addressed in here (afaict) is "who cares".  Is there some
workload which is kallsyms-intensive?

This info really should be right in the first para of the [0/N], and in
detail.  What benefit does this work offer to our users?  Use cases,
example scenarios, etc.

Apologies if I missed this in earlier discussions, but if it was in the
[0/N] this wouldn't matter!