kallsyms: match compressed tokens on the fly during binary search

Patch series "kallsyms: Accelerate symbol name lookups by ~7x", v7.

In 2022, commit 60443c88f3a8 ("kallsyms: Improve the performance of
kallsyms_lookup_name()") introduced kallsyms_seqs_of_names[] (+550 KiB
.rodata), transforming an O(N) linear scan into an O(log N) binary search
(5.2 ms -> ~7.2 us).  While this was a major step forward, the binary
search inner loop was left decompressing full candidate names and scanning
across sparse 256:1 markers on every probe.

Modern fleet observability, security daemons (e.g.  CrowdStrike Falcon,
Cilium, Datadog, Falco), and tracing tools resolve thousands of kernel
functions by name at boot or service start.

CrowdStrike recently hit this in production:

commit 93e8fd1a565e ("ftrace: Use kallsyms binary search for single-symbol lookup")

Attaching just 50 kprobe.session programs caused an 858 ms attach stall
with 25% CPU burned in kallsyms.  That commit routed single-symbol libbpf
attach directly to kallsyms_lookup_name().  In larger workloads (such as
the BPF selftest serial_test_kprobe_multi_bench_attach across 64,000
symbols), kallsyms_lookup_names() spends ~390 ms in raw CPU spin.

This series accelerates kallsyms_lookup_names() by 7.0x (from 6,102 ns
down to 866 ns per lookup), cutting 64k-symbol attach from ~390 ms to ~55
ms, by fixing two inner-loop bottlenecks:

0. Candidate symbols are fully decompressed into a 512-byte stack buffer
   before calling strcmp(), even though ~16 of the 17 search steps
   mismatch at the first differing character (0..N-1, heavily
   front-loaded toward 0-2).

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).

The 3-patch progression:

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 (CONFIG_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)

Trade-offs:
- .rodata footprint: +42.2 KiB (+10,782 u32 entries for ~184k symbols,
  ~0.1% of loaded kernel image).
- Runtime overhead: 0 bytes dynamic RAM (no kmalloc/kvmalloc), 0 RCU,
  0 new locks, and 0 new algorithms.
- Kernel stack: -512 bytes freed in kallsyms_lookup_names().
- Build tooling: scripts/kallsyms.c includes
  ../kernel/kallsyms_internal.h (guarded by #ifdef __KERNEL__) so host
  build and kernel runtime share KALLSYMS_MARKER_SHIFT 4 as a single
  source of truth.
- Build time: Unmeasurable delta (< 1 ms in scripts/kallsyms.c).

What's Unchanged:
- Symbol table layout in address order remains identical.
- Streaming decompression for /proc/kallsyms and sprint_symbol() is
  untouched.
- 0 new user-facing APIs, 0 new locking primitives, 0 Kconfig options.


This patch (of 3):

kallsyms_lookup_names() runs a binary search across ~184k tokenized
(compressed) symbols.  For each of the ~17 comparisons in the search, it
currently decompresses the candidate symbol into a temporary buffer on the
stack before calling strcmp().

Comparing tokenized symbols directly in compressed space is impossible. 
The BPE token table assigns values by frequency, not alphabetical order
(e.g.  token 0x05 might expand to "zebra" while 0x42 expands to "apple"),
so comparing raw token values scrambles lexicographical order.  Even
sorting the token table alphabetically wouldn't help; "bpf_" and
"bpf_foo_" do not *have* a determinative sorting order, because the
suffixes following those tokens would matter.

However, full string expansion at every step is equally wasteful: of the
~17 strcmps in the binary search, only the last needs to check all N chars
in both strings, earlier steps will know +/- outcome at char 0,1,2..N-1.

However, full string expansion at every step is equally wasteful: of the
~17 strcmp()s in the binary search, only the final matching step needs to
test all characters.  Earlier non-matching steps diverge at the first
differing character (0..N-1), but the baseline expands every candidate
symbol to the stack unconditionally, before comparing.

So we introduce kallsyms_strcmp_symbol() to compare ASCII search_name
against tokenized symbols on the fly.  Like strcmp, it tests the strings
char by char, but when it hits a token in the symbol-string, it continues
the char-test against that token-string, which is in
kallsyms_token_table[].  It returns +- on 1st mismatch.

Measured across all ~184k symbols via CONFIG_KALLSYMS_SELFTEST, this
shaves ~530 ns (~14%) off average kallsyms_lookup_name() latency (from
~3810 ns to ~3280 ns on the default 256:1 baseline) and drops the 512-byte
namebuf buffer stack-alloc in kallsyms_lookup_names().

Link: https://lore.kernel.org/20260929-ksyms-tune-v7-0-be568ceef41e@gmail.com
Link: https://lore.kernel.org/20260929-ksyms-tune-v7-1-be568ceef41e@gmail.com
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Reviewed-by: Kees Cook <kees@kernel.org>
Cc: Petr Mladek <pmladek@suse.com>
Cc: Zhen Lei <thunder.leizhen@huawei.com>
Cc: Luis Chamberlain <mcgrof@kernel.org>
Cc: Andrey Grodzovsky <andrey.grodzovsky@crowdstrike.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: David Laight <david.laight.linux@gmail.com>
Cc: Masahiro Yamada <masahiroy@kernel.org>
Cc: Jiri Olsa <olsajiri@gmail.com>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>

0 files changed, 0 insertions, 0 deletions