kernel/kallsyms.c | 138 ++++++++++++++------------- kernel/kallsyms_internal.h | 2 +- lib/Kconfig.debug | 10 ++ lib/Makefile | 1 + lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++ scripts/kallsyms.c | 30 +++--- 6 files changed, 322 insertions(+), 87 deletions(-)
kallsyms_lookup_names() resolves symbol names to addresses using a
17-step binary search over kallsyms_names[] (~191k symbols on x86_64).
At each step of the search, two bottlenecks compound to create
substantial lookup latency:
0. Marker scanning: get_symbol_offset() scans sequentially from the
nearest 256-symbol marker, decoding an average of ~128 ULEB128 record
headers per probe (~2,176 header decodes per lookup).
1. 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.
Together, these bottlenecks impose a ~4.3 us latency penalty per hit and
~3.8 us per miss.
This 3-patch series eliminates both overheads while keeping the symbol
table strictly in sequential address order:
0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
measure name hits, name misses, sprint_symbol(), and table iteration
latency, with built-in correctness validation and a sysfs trigger.
1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
index into kallsyms_names[]. This turns get_symbol_offset() into an
O(1) table lookup, dropping the ~2,176 marker hops per lookup and
eliminating the legacy kallsyms_markers[] table.
2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries
against compressed tokens incrementally 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.
Context & Lineage:
This series was originally developed and benchmarked on mainline (v7.3-rc3).
To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
kernel with pigz if available").
Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
direct binary streaming path (write_incbin).
Glomming onto Lorenzo's build-time acceleration push extends the speedup
theme into runtime: his series speeds up the compile and link, and this
series speeds up runtime symbol lookups by ~18x.
Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
Metric Baseline Patched Speedup
-----------------------------------------------------------------
Name Search Hit 4,370 ns 247 ns 17.7x
Name Search Miss 3,860 ns 195 ns 19.8x
sprint_symbol 440 ns 441 ns parity
sprint_symbol_no_offset 315 ns 307 ns parity
Table Full Walk 14,500 us 14,437 us parity
Address-to-name resolution (sprint_symbol) and sequential table walks
(/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
hardware prefetching.
Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
$ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
Counter Baseline Patched Delta
------------------------------------------------------------------------
Wall-clock elapsed 1.746 s 0.852 s -51.2%
CPU cycles 7,320,048,030 3,628,523,081 -50.4%
Instructions 9,943,172,792 5,034,260,318 -49.4%
Branches 2,391,663,821 1,173,258,010 -51.0%
Branch-misses 117,241,513 99,805,938 -14.9%
Cache-misses 84,996,149 731,025 -99.1%
Dropping marker scans and avoiding redundant string expansions cuts
4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
(-99.1%) across the test workload.
Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
kallsyms_markers[].
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Jim Cromie (3):
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
kallsyms: Add 3-byte index into compressed symbols to replace marker scans
kallsyms: Match compressed tokens on the fly during binary search
kernel/kallsyms.c | 138 ++++++++++++++-------------
kernel/kallsyms_internal.h | 2 +-
lib/Kconfig.debug | 10 ++
lib/Makefile | 1 +
lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++
scripts/kallsyms.c | 30 +++---
6 files changed, 322 insertions(+), 87 deletions(-)
---
base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
change-id: 20260919-ksyms-tune-e22a42d8a31a
Best regards,
--
Jim Cromie <jim.cromie@gmail.com>
On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote: > Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k > symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping > kallsyms_markers[]. The speed-up is impressive, but I have to say 500KB is not exactly trivial. It's not _huge_, but it's not small. Is the rate of symbol lookups in the kernel high enough to justify this loss of memory? -- Kees Cook
On Mon, Sep 21, 2026 at 5:07 PM Kees Cook <kees@kernel.org> wrote: > > On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote: > > Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k > > symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping > > kallsyms_markers[]. > > The speed-up is impressive, but I have to say 500KB is not exactly > trivial. It's not _huge_, but it's not small. Is the rate of symbol > lookups in the kernel high enough to justify this loss of memory? > IIUC the use is quite lumpy. so a dynamic allocation could solve all the problems. 1- 32 bit table, since 24 bit fiddling is silly on table thats freed soon. 2- can do David Laights stride-2 thing almost for free 3 - 0 bytes rodata 4 - no conflict with Lorenzo's patchset - no touches to scripts/kallsyms.c It could be batch-loaded and freed, w fallback to existing slow search. or left around till OOM I will play with this. > -- > Kees Cook
On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~191k symbols on x86_64).
> At each step of the search, two bottlenecks compound to create
> substantial lookup latency:
>
> 0. Marker scanning: get_symbol_offset() scans sequentially from the
> nearest 256-symbol marker, decoding an average of ~128 ULEB128 record
> headers per probe (~2,176 header decodes per lookup).
>
> 1. 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.
>
> Together, these bottlenecks impose a ~4.3 us latency penalty per hit and
> ~3.8 us per miss.
>
> This 3-patch series eliminates both overheads while keeping the symbol
> table strictly in sequential address order:
>
> 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
> measure name hits, name misses, sprint_symbol(), and table iteration
> latency, with built-in correctness validation and a sysfs trigger.
>
> 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
> index into kallsyms_names[]. This turns get_symbol_offset() into an
> O(1) table lookup, dropping the ~2,176 marker hops per lookup and
> eliminating the legacy kallsyms_markers[] table.
>
> 2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries
> against compressed tokens incrementally 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.
>
> Context & Lineage:
>
> This series was originally developed and benchmarked on mainline (v7.3-rc3).
> To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
> it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
> kernel with pigz if available").
>
> Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
> align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
> direct binary streaming path (write_incbin).
>
> Glomming onto Lorenzo's build-time acceleration push extends the speedup
> theme into runtime: his series speeds up the compile and link, and this
> series speeds up runtime symbol lookups by ~18x.
>
> Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
>
> Metric Baseline Patched Speedup
> -----------------------------------------------------------------
> Name Search Hit 4,370 ns 247 ns 17.7x
> Name Search Miss 3,860 ns 195 ns 19.8x
> sprint_symbol 440 ns 441 ns parity
> sprint_symbol_no_offset 315 ns 307 ns parity
> Table Full Walk 14,500 us 14,437 us parity
>
> Address-to-name resolution (sprint_symbol) and sequential table walks
> (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
> hardware prefetching.
>
> Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
>
> $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
> sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
>
> Counter Baseline Patched Delta
> ------------------------------------------------------------------------
> Wall-clock elapsed 1.746 s 0.852 s -51.2%
> CPU cycles 7,320,048,030 3,628,523,081 -50.4%
> Instructions 9,943,172,792 5,034,260,318 -49.4%
> Branches 2,391,663,821 1,173,258,010 -51.0%
> Branch-misses 117,241,513 99,805,938 -14.9%
> Cache-misses 84,996,149 731,025 -99.1%
>
> Dropping marker scans and avoiding redundant string expansions cuts
> 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
> (-99.1%) across the test workload.
>
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].
>
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
All very nice :)
I'm glad this work seems to be inspiring other work in the same area! I think
there's a load of improvements to be had across the board.
I will try to have a look through through though my workload is crazy
lately and the build stuff is often taking chunks of the weekend so not
sure if I'll have time, but I did at least want to say - awesome :)
> ---
> Jim Cromie (3):
> kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
> kallsyms: Add 3-byte index into compressed symbols to replace marker scans
> kallsyms: Match compressed tokens on the fly during binary search
>
> kernel/kallsyms.c | 138 ++++++++++++++-------------
> kernel/kallsyms_internal.h | 2 +-
> lib/Kconfig.debug | 10 ++
> lib/Makefile | 1 +
> lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++
> scripts/kallsyms.c | 30 +++---
> 6 files changed, 322 insertions(+), 87 deletions(-)
> ---
> base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
> change-id: 20260919-ksyms-tune-e22a42d8a31a
>
> Best regards,
> --
> Jim Cromie <jim.cromie@gmail.com>
>
--
Cheers, Lorenzo
On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~191k symbols on x86_64).
> At each step of the search, two bottlenecks compound to create
> substantial lookup latency:
>
> 0. Marker scanning: get_symbol_offset() scans sequentially from the
> nearest 256-symbol marker, decoding an average of ~128 ULEB128 record
> headers per probe (~2,176 header decodes per lookup).
>
> 1. 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.
>
> Together, these bottlenecks impose a ~4.3 us latency penalty per hit and
> ~3.8 us per miss.
>
> This 3-patch series eliminates both overheads while keeping the symbol
> table strictly in sequential address order:
>
> 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
> measure name hits, name misses, sprint_symbol(), and table iteration
> latency, with built-in correctness validation and a sysfs trigger.
>
> 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
> index into kallsyms_names[]. This turns get_symbol_offset() into an
> O(1) table lookup, dropping the ~2,176 marker hops per lookup and
> eliminating the legacy kallsyms_markers[] table.
>
> 2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries
> against compressed tokens incrementally 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.
>
> Context & Lineage:
>
> This series was originally developed and benchmarked on mainline (v7.3-rc3).
> To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
> it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
> kernel with pigz if available").
>
> Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
> align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
> direct binary streaming path (write_incbin).
>
> Glomming onto Lorenzo's build-time acceleration push extends the speedup
> theme into runtime: his series speeds up the compile and link, and this
> series speeds up runtime symbol lookups by ~18x.
>
> Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
>
> Metric Baseline Patched Speedup
> -----------------------------------------------------------------
> Name Search Hit 4,370 ns 247 ns 17.7x
> Name Search Miss 3,860 ns 195 ns 19.8x
> sprint_symbol 440 ns 441 ns parity
> sprint_symbol_no_offset 315 ns 307 ns parity
> Table Full Walk 14,500 us 14,437 us parity
>
> Address-to-name resolution (sprint_symbol) and sequential table walks
> (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
> hardware prefetching.
>
> Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
>
> $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
> sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
>
> Counter Baseline Patched Delta
> ------------------------------------------------------------------------
> Wall-clock elapsed 1.746 s 0.852 s -51.2%
> CPU cycles 7,320,048,030 3,628,523,081 -50.4%
> Instructions 9,943,172,792 5,034,260,318 -49.4%
> Branches 2,391,663,821 1,173,258,010 -51.0%
> Branch-misses 117,241,513 99,805,938 -14.9%
> Cache-misses 84,996,149 731,025 -99.1%
>
> Dropping marker scans and avoiding redundant string expansions cuts
> 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
> (-99.1%) across the test workload.
>
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].
>
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
nice, fyi I checked on tracing_multi benchmark and got bit of
speedup as well
before:
serial_test_tracing_multi_bench_attach: found 64021 functions
serial_test_tracing_multi_bench_attach: attached in 2.884s
serial_test_tracing_multi_bench_attach: detached in 1.149s
16,515,655,329 cycles:k
41,935,382,635 instructions:k
after:
serial_test_tracing_multi_bench_attach: found 64021 functions
serial_test_tracing_multi_bench_attach: attached in 2.633s
serial_test_tracing_multi_bench_attach: detached in 1.159s
#558 tracing_multi_bench_attach:OK
15,880,929,751 cycles:k
40,444,002,354 instructions:k
we call kallsyms_lookup_name for each attached symbol
jirka
> ---
> Jim Cromie (3):
> kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
> kallsyms: Add 3-byte index into compressed symbols to replace marker scans
> kallsyms: Match compressed tokens on the fly during binary search
>
> kernel/kallsyms.c | 138 ++++++++++++++-------------
> kernel/kallsyms_internal.h | 2 +-
> lib/Kconfig.debug | 10 ++
> lib/Makefile | 1 +
> lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++
> scripts/kallsyms.c | 30 +++---
> 6 files changed, 322 insertions(+), 87 deletions(-)
> ---
> base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
> change-id: 20260919-ksyms-tune-e22a42d8a31a
>
> Best regards,
> --
> Jim Cromie <jim.cromie@gmail.com>
>
>
© 2016 - 2026 Red Hat, Inc.