kallsyms: Accelerate symbol name lookups by ~19x
Subsystems (3)
v4 cover kallsyms: Accelerate symbol name lookups by ~19x
kallsyms_lookup_names() resolves symbol names to addresses using a 17-step binary search over kallsyms_names[] (~184k symbols on x86_64). At each step of the search, two bottlenecks compound to create substantial lookup latency:
0. 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 (~580 ns per lookup).
1. Marker scanning: get_symbol_offset() scans sequentially from the nearest 256-symbol marker in kallsyms_names[], decoding an average of ~128 ULEB128 record headers per probe (~2,176 header decodes, consuming ~3,230 ns per lookup).
Together, these bottlenecks impose a ~3.8 us latency penalty per hit and ~3.6 us per miss.
This 4-patch series eliminates both overheads in a structured progression while keeping the symbol table strictly in sequential address order and adding 0 bytes to .rodata:
0. Patch 1 adds lib/test_kallsyms_perf, a microbenchmark module built directly into vmlinux (CONFIG_TEST_KALLSYMS_PERF=bool) to benchmark unindexed vs dynamic indexed name searches, address resolution, and table iteration latency without exporting internal kallsyms iterators to loadable modules.
1. Patch 2 introduces kallsyms_strcmp_symbol() to compare ASCII queries against compressed tokens 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 and saves ~530 ns per lookup on unmodified marker infrastructure.
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.
3. Patch 4 inlines and unrolls get_symbol_seq() 24-bit sequence index reconstruction into direct byte shifts, eliminating loop overhead on inner binary search probes.
Live Microbenchmark Progression (via test_kallsyms_perf, 100k iters):
Metric Baseline (1) Token Match (2) Batch Index (3) Total Speedup
------------------------------------------------------------------------------------------
Name Search Hit 3,811 ns 3,280 ns 246 ns 15.5x Name Search Miss 3,625 ns 3,095 ns 196 ns 18.5x sprint_symbol 412 ns 412 ns 412 ns parity sprint_symbol_no_offset 300 ns 300 ns 300 ns parity Table Full Walk 13,626 us 13,626 us 13,626 us parity Kernel stack buffer 512 B 0 B 0 B -512 B
In-Tree Selftest Verification (CONFIG_KALLSYMS_SELFTEST, 184k symbols):
In addition to test_kallsyms_perf, the existing upstream selftest in kernel/kallsyms_selftest.c was run across all 183,990 symbols on boot, repeating all tests inside an active batch window:
Metric Unindexed (markers) Batch Index (active) Delta
-----------------------------------------------------------------------------------
kallsyms_lookup_name() (avg) 3,926 ns 675 ns 5.8x faster kallsyms_lookup_name() (min) 311 ns 171 ns 1.8x faster on_each_match_symbol() 3,507 ns 1,142 ns 3.1x faster kallsyms_on_each_symbol() 14.7 ms 15.5 ms parity Basic function validation PASS PASS 100% correct Batch setup (184k entries) N/A 1,037 us ~1.0 ms Batch teardown (sync RCU) N/A 3,440 us ~3.4 ms
Address-to-name resolution (sprint_symbol) and sequential table walks (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2 hardware prefetching.
Memory footprint: +0 KiB .rodata added to kernel image. Transient RAM is ~736 KiB (184k * 4 bytes) allocated only during active batch lookup sessions.
---
Changes in v4:
- In patch 1, ignore early boot invocations in param_set_trigger() when system_state < SYSTEM_RUNNING to prevent NULL pointer dereference in ktime_get_ns() prior to timekeeping_init() (addresses Sashiko AI review).
- In patch 1, prevent sysfs TOCTOU divide-by-zero panic: reject num_iters == 0 in param setter, snapshot iters locally via READ_ONCE, and serialize runs with bench_lock mutex (addresses Sashiko AI review).
- In patch 1, eliminate multi-second boot stall: add run_on_boot parameter (default false) so late_initcall only runs benchmark when explicitly requested (addresses Sashiko AI review).
- In patch 1, chunk lookup loops in 4096-iter batches with cond_resched() outside the timing bracket to prevent preemption sleep time from inflating reported latency (addresses Sashiko AI review).
- In patch 3, annotate dyn_kallsyms_offsets declaration with __rcu to satisfy sparse type checking and prevent address-space warnings across rcu_assign_pointer() and rcu_dereference() (addresses Sashiko AI review).
- In patch 3, use rcu_replace_pointer() with lockdep_is_held() during batch teardown to atomically read and clear the pointer while satisfying sparse address-space constraints (addresses Sashiko AI review).
- Link to v3: https://lore.kernel.org/r/[email protected]
Changes in v3:
- Reorder series: place on-the-fly token matching (patch 2) ahead of dynamic batch lookup index (patch 3), establishing an active proof of incremental performance deltas across all steps (addresses David
Laight review).
- Add patch 4: inline and unroll get_symbol_seq() 24-bit sequence index reconstruction into direct byte shifts (addresses David Laight
review).
- In patch 1, configure CONFIG_TEST_KALLSYMS_PERF as a built-in test (bool) rather than a module (tristate) and drop kallsyms iterator EXPORT_SYMBOL_GPL exports to avoid exposing internal kernel symbol
data (addresses Sashiko AI review).
- In patch 2, optimize kallsyms_strcmp_symbol() by dropping
skipped_first tracking and checking len at the bottom of the token
loop (addresses David Laight review).
- In patch 3, rely on get_symbol_data() helper introduced in patch 2 to preserve bisectability (addresses Sashiko AI review).
- In patch 3, fix use-after-free race on dyn_kallsyms_offsets: bracket table dereference and array read with rcu_read_lock() and replace rcu_dereference_raw() with rcu_dereference() inside
get_symbol_offset() to protect external readers (lookup_symbol_name, kallsyms_lookup_buildid, reset_iter) against concurrent batch
teardown (addresses Sashiko AI review).
- In patch 3, update kallsyms_selftest to add a second lookup pass bracketed by batch start/end to report batch latency in the in-tree selftest.
- Drop 'default m' from lib/Kconfig.debug.
- Fix soft lockup risks by adding cond_resched() every 16k iterations in test_kallsyms_perf loops.
- Replace direct 64-bit integer divisions with div_u64() to fix 32-bit builds.
- Guard against divide-by-zero when num_iters=0.
- Replace tcp_v4_rcv with panic in hit_symbols to prevent failures wo CONFIG_INET.
- Add batch lookup setup/teardown timing and query amortization break-even logging to test_kallsyms_perf.
- Move David Laight to series-wide Cc on cover letter, dropping trailer from patch 3.
- Link to v2: https://lore.kernel.org/r/[email protected]
Changes in v2:
- Replaced static build-time 3-byte offset table with a dynamic u32
index bracketed by kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end().
- Dropped .rodata image footprint addition from +573 KiB to 0 KiB, addressing Kees Cook's memory footprint objection.
- Native u32 loads in transient RAM eliminate 24-bit big-endian shifts and unaligned loads, addressing David Laight's endianness critique.
- Direct O(1) table indexing provides 0 hops for all symbol lookups without remainder logic or odd/even branching.
- Restored scripts/kallsyms.c and kernel/kallsyms_internal.h to pristine state, leaving legacy kallsyms_markers[] as safety fallback.
- Rebased out Lorenzo Stoakes' kbuild series; this series is now completely decoupled and applies cleanly directly onto mainline.
- Updated test_kallsyms_perf to benchmark unindexed marker scans and dynamic index side by side in a single run.
- Link to v1: https://lore.kernel.org/r/[email protected]
---
Jim Cromie (4):
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
kallsyms: Match compressed tokens on the fly during binary search
kallsyms: Add dynamic lookup index for batch resolution
kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
include/linux/kallsyms.h | 13 ++ kernel/kallsyms.c | 212 ++++++++++++++++++++++------ kernel/kallsyms_selftest.c | 16 +++ lib/Kconfig.debug | 10 ++ lib/Makefile | 1 + lib/test_kallsyms_perf.c | 341 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 547 insertions(+), 46 deletions(-)
---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a
Best regards,
Signature · 1 line
Jim Cromie <[email protected]>
PATCH v4 1/4 kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
To evaluate optimizations and measure performance regressions across kallsyms lookups, add a lightweight microbenchmark module in lib/.
Configure CONFIG_TEST_KALLSYMS_PERF as a built-in test (bool) rather than a loadable module (tristate). Building the test directly into vmlinux allows exercising internal kallsyms traversal APIs without exporting internal symbol iterators (EXPORT_SYMBOL_GPL) to modules, preserving kernel symbol table encapsulation.
The module exercises the primary kallsyms resolution paths:
0. Name-to-Address binary search: Benchmarks lookups across common kernel functions (hits) and non-existent symbol strings (misses, exercising the full binary search tree depth).
1. Address-to-Name resolution: Benchmarks address decoding latency via sprint_symbol() and sprint_symbol_no_offset().
2. Sequential table scan: Measures complete table iteration latency via kallsyms_on_each_symbol().
The module exposes a num_iters parameter (default: 100,000) and a sysfs trigger to repeat benchmark runs on demand.
---
Changes in v4:
- Ignore early boot invocations in param_set_trigger() when system_state < SYSTEM_RUNNING to prevent NULL pointer dereference in ktime_get_ns() prior to timekeeping_init() (addresses Sashiko AI review).
- Prevent sysfs TOCTOU divide-by-zero panic: reject num_iters == 0 in param setter, snapshot iters locally via READ_ONCE, and serialize runs with bench_lock mutex (addresses Sashiko AI review).
- Eliminate multi-second boot stall: add run_on_boot parameter (default false) so late_initcall only runs benchmark when explicitly requested (addresses Sashiko AI review).
- Chunk lookup loops in 4096-iter batches with cond_resched() outside the timing bracket to prevent preemption sleep time from inflating reported latency (addresses Sashiko AI review).
Changes in v3:
- Convert CONFIG_TEST_KALLSYMS_PERF from tristate to bool and drop kallsyms iterator EXPORT_SYMBOL_GPL exports to preserve security encapsulation (addresses Sashiko AI review).
- Drop 'default m' from lib/Kconfig.debug.
- Add cond_resched() every 16k iterations to avoid soft lockups.
- Replace direct 64-bit division with div_u64() to fix 32-bit builds.
- Guard against divide-by-zero when num_iters=0.
- Replace tcp_v4_rcv with panic in hit_symbols to prevent failures wo CONFIG_INET.
- Switch to late_initcall for built-in invocation.
--- lib/Kconfig.debug | 10 ++ lib/Makefile | 1 + lib/test_kallsyms_perf.c | 302 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+)
lib/Kconfig.debug +10 -0
@@ -3122,6 +3122,16 @@ config TEST_STATIC_KEYS If unsure, say N. +config TEST_KALLSYMS_PERF + bool "kallsyms performance benchmark test module" + depends on KALLSYMS + help + This builds test_kallsyms_perf to benchmark latency across + Name-to-Address binary search, Address-to-Name resolution, + and full table walks. + + If unsure, say N. + config TEST_DYNAMIC_DEBUG tristate "Test DYNAMIC_DEBUG" depends on DYNAMIC_DEBUG
lib/Makefile +1 -0
@@ -85,6 +85,7 @@ obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_keys.o obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_key_base.o obj-$(CONFIG_TEST_DYNAMIC_DEBUG) += test_dynamic_debug.o +obj-$(CONFIG_TEST_KALLSYMS_PERF) += test_kallsyms_perf.o obj-$(CONFIG_TEST_BITMAP) += test_bitmap.o ifeq ($(CONFIG_CC_IS_CLANG)$(CONFIG_KASAN),yy)
lib/test_kallsyms_perf.c new file +302 -0
302 lines not on this page · raw message
Signature · 1 line
2.55.0
[email protected]
AI reviewRe: [PATCH v4 1/4] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [High] test_kallsyms: infinite loop on large num_iters due to integer overflow - [Medium] test_kallsyms…
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] test_kallsyms: infinite loop on large num_iters due to integer overflow
- [Medium] test_kallsyms: benchmark latency includes preemption sleep time --
commit 3ac6ce68ed3764cca0a42a3e09873db349d331f2
Author: Jim Cromie <[email protected]>
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
This commit adds a lightweight microbenchmark module to evaluate optimizations and measure performance regressions across kallsyms lookups. It benchmarks name-to-address, address-to-name, and sequential table scans.
Quoted 5 lines
lib/test_kallsyms_perf.c new file +0
-0
[ ... ]
Quoted 2 lines
lib/test_kallsyms_perf.c new file +2
-0+static void run_name_lookup_bench (unsigned int iters) +{
[ ... ]
lib/test_kallsyms_perf.c
Quoted 2 lines
lib/test_kallsyms_perf.c new file +2
-0+/* 1. Name search: Existing symbols (Hits) */ +for (i =0 ; i < iters; i +=BENCH_CHUNK_SIZE ) {
[Severity: High]
Does this unconditionally add BENCH_CHUNK_SIZE to i in a way that can wrap around?
If a user sets num_iters via sysfs to a value approaching UINT_MAX (for example, UINT_MAX - 100), could i wrap around to a small number?
If so, will the termination condition i < iters never be met, causing an infinite loop that permanently holds bench_lock?
lib/test_kallsyms_perf.c line 132
Quoted 9 lines
lib/test_kallsyms_perf.c new file +9
-0+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); +unsigned int j; + +cond_resched (); + t0 =ktime_get_ns (); +for (j =0 ; j < chunk; j++) { +const char *sym = hit_symbols[(i + j) % nr_hits]; + +kallsyms_on_each_match_symbol (match_cb, sym, &addr);
[Severity: Medium]
Do these kallsyms traversal APIs inherently invoke cond_resched() within their internal iteration loops?
If so, does calling them inside the timing bracket (between t0 and t1) defeat the chunking mitigation? Could this include preemption sleep time in the measured benchmark latency?
lib/test_kallsyms_perf.c line 140
Quoted 8 lines
lib/test_kallsyms_perf.c new file +8
-0+OPTIMIZER_HIDE_VAR (addr); + } + t1 =ktime_get_ns (); + dt_hit += t1 - t0; + } + +/* 2. Name search: Non-existent symbols (Misses - 17 bsearch probes) */ +for (i =0 ; i < iters; i +=BENCH_CHUNK_SIZE ) {
[Severity: High]
Can this loop also suffer from the same integer overflow if num_iters is very large?
Quoted 14 lines
lib/test_kallsyms_perf.c new file +14
-0+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); +unsigned int j; + +cond_resched (); + t0 =ktime_get_ns (); +for (j =0 ; j < chunk; j++) { +const char *sym = miss_symbols[(i + j) % nr_misses]; + +kallsyms_on_each_match_symbol (match_cb, sym, &addr); +OPTIMIZER_HIDE_VAR (addr); + } + t1 =ktime_get_ns (); + dt_miss += t1 - t0; + }
[ ... ]
Quoted 2 lines
lib/test_kallsyms_perf.c new file +2
-0+static void run_address_lookup_bench (unsigned int iters) +{
[ ... ]
lib/test_kallsyms_perf.c
Quoted 2 lines
lib/test_kallsyms_perf.c new file +2
-0+/* 1. Address-to-name resolution (sprint_symbol) */ +for (i =0 ; i < iters; i +=BENCH_CHUNK_SIZE ) {
[Severity: High]
Is there a similar risk of wrap-around in this loop when num_iters approaches UINT_MAX?
Quoted 7 lines
lib/test_kallsyms_perf.c new file +7
-0+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); +unsigned int j; + +cond_resched (); + t0 =ktime_get_ns (); +for (j =0 ; j < chunk; j++) { +unsigned long addr = addrs[(i + j) % nr_addrs];
lib/test_kallsyms_perf.c line 200
Quoted 10 lines
lib/test_kallsyms_perf.c new file +10
-0+ +sprint_symbol (symname, addr); +barrier_data (symname); + } + t1 =ktime_get_ns (); + dt_sprint += t1 - t0; + } + +/* 2. Address without offset (sprint_symbol_no_offset) */ +for (i =0 ; i < iters; i +=BENCH_CHUNK_SIZE ) {
[Severity: High]
Could this loop also become infinite due to the same integer overflow condition?
Quoted 14 lines
lib/test_kallsyms_perf.c new file +14
-0+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); +unsigned int j; + +cond_resched (); + t0 =ktime_get_ns (); +for (j =0 ; j < chunk; j++) { +unsigned long addr = addrs[(i + j) % nr_addrs]; + +sprint_symbol_no_offset (symname, addr); +barrier_data (symname); + } + t1 =ktime_get_ns (); + dt_bldid += t1 - t0; + }
[ ... ]
Quoted 2 lines
lib/test_kallsyms_perf.c new file +2
-0+static void run_table_walk_bench (void ) +{
[ ... ]
lib/test_kallsyms_perf.c line 233
Quoted 5 lines
lib/test_kallsyms_perf.c new file +5
-0+for (i =0 ; i < iter; i++) { + total_symbols =0 ; +cond_resched (); + t0 =ktime_get_ns (); +kallsyms_on_each_symbol (count_cb, &total_symbols);
[Severity: Medium]
Does kallsyms_on_each_symbol() also natively invoke cond_resched() inside its iteration loop?
If so, could placing this call inside the timing bracket include preemption sleep time and inflate the measured walk latency?
Quoted 3 lines
lib/test_kallsyms_perf.c new file +3
-0+ t1 =ktime_get_ns (); + dt_walk += t1 - t0; + }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
PATCH v4 2/4 kallsyms: Match compressed tokens on the fly during binary search
In reply to Jim Cromiekallsyms_lookup_names() runs a binary search across kallsyms_names[], a packed array of ~130k encoded kernel 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 raw tokens 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.
However, full string expansion is equally wasteful: roughly 16 of the 17 binary search steps fail within the first two characters.
Introduce kallsyms_strcmp_symbol() to compare ASCII queries against compressed tokens on the fly. It walks kallsyms_token_index and kallsyms_token_table incrementally, matching characters directly and bailing out on the first character mismatch without expanding subsequent tokens.
This optimization:
0. Avoids decompressing non-matching tokens, short-circuiting ~94% of binary search character expansions without adding any tables in .rodata.
1. Drops the 512-byte namebuf buffer from the kernel stack in kallsyms_lookup_names().
2. Cuts unindexed lookup latency by ~530 ns (~14% faster) while leaving sequential address ordering and kallsyms_expand_symbol() streaming invariants intact for /proc/kallsyms and table walks.
---
Changes in v3:
- Reorder patch ahead of dynamic batch index in series, establishing an active proof of string matching savings on unindexed baseline (addresses David Laight review).
- Optimize kallsyms_strcmp_symbol(): drop skipped_first tracking and test len at loop bottom (addresses David Laight review).
- Guard first token with while (*tptr) to handle 1-byte type tokens.
- Introduce get_symbol_data() helper in this patch for reuse in later subsystems.
Changes in v2:
- Rebase onto mainline v7.3-rc4, removing external dependencies on Lorenzo Stoakes' kbuild series.
--- kernel/kallsyms.c | 94 ++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 59 insertions(+), 35 deletions(-)
kernel/kallsyms.c +59 -35
@@ -34,6 +34,21 @@#include "kallsyms_internal.h" +/* +* Get the compressed symbol length and data pointer. +*/ +static inline const u8 *get_symbol_data (unsigned int off,unsigned int *len) +{ +const u8 *p = &kallsyms_names[off]; +unsigned int l = *p++; + +if (unlikely (l &0x80 )) + l = (l &0x7F ) | (*p++ <<7 ); + *len = l; + +return p; +} +/* * Expand a compressed symbol data into the resulting uncompressed string, * if uncompressed string is too long (>= maxlen), it will be truncated,
@@ -42,28 +57,12 @@static unsigned int kallsyms_expand_symbol (unsigned int off,char *result,size_t maxlen) { -int len, skipped_first =0 ; +int skipped_first =0 ;const char *tptr; -const u8 *data; +unsigned int len; +const u8 *data =get_symbol_data (off, &len); -/* Get the compressed symbol length from the first symbol byte. */ - data = &kallsyms_names[off]; - len = *data; - data++; - off++; - -/* If MSB is 1, it is a "big" symbol, so needs an additional byte. */ -if ((len &0x80 ) !=0 ) { - len = (len &0x7F ) | (*data <<7 ); - data++; - off++; - } - -/* -* Update the offset to return the offset for the next symbol on -* the compressed stream. -*/ - off += len; + off = (data - kallsyms_names) + len;/* * For every byte on the compressed symbol data, copy the table
@@ -101,14 +100,43 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,*/ static char kallsyms_get_symbol_type (unsigned int off) { -/* -* Get just the first code, look it up in the token table, -* and return the first char from this token. If MSB of length -* is 1, it is a "big" symbol, so needs an additional byte. -*/ -if (kallsyms_names[off] &0x80 ) - off++; -return kallsyms_token_table[kallsyms_token_index[kallsyms_names[off +1 ]]]; +unsigned int len; +const u8 *data =get_symbol_data (off, &len); + +return kallsyms_token_table[kallsyms_token_index[*data]]; +} + +/* +* Compare an uncompressed ASCII string against a compressed symbol table entry. +* Returns negative if name < sym, positive if name > sym, 0 if equal. +* Exits immediately on the first mismatched character without decompressing +* the rest of the symbol name. +*/ +static int kallsyms_strcmp_symbol (unsigned int off,const char *name) +{ +const char *tptr; +unsigned int len; +const u8 *data =get_symbol_data (off, &len); + + tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] +1 ; +while (*tptr) { +int diff = (unsigned char )*name++ - (unsigned char )*tptr++; + +if (diff) +return diff; + } + +while (--len) { + tptr = &kallsyms_token_table[kallsyms_token_index[*data++]]; +do { +int diff = (unsigned char )*name++ - (unsigned char )*tptr++; + +if (diff) +return diff; + }while (*tptr); + } + +return (unsigned char )*name; }
@@ -174,7 +202,6 @@ static int kallsyms_lookup_names(const char *name,int ret;int low, mid, high;unsigned int seq, off; -char namebuf[KSYM_NAME_LEN ]; low =0 ; high = kallsyms_num_syms -1 ;
@@ -183,8 +210,7 @@ static int kallsyms_lookup_names(const char *name, mid = low + (high - low) /2 ; seq =get_symbol_seq (mid); off =get_symbol_offset (seq); -kallsyms_expand_symbol (off, namebuf,ARRAY_SIZE (namebuf)); - ret =strcmp (name, namebuf); + ret =kallsyms_strcmp_symbol (off, name);if (ret >0 ) low = mid +1 ;else if (ret <0 )
@@ -200,8 +226,7 @@ static int kallsyms_lookup_names(const char *name,while (low) { seq =get_symbol_seq (low -1 ); off =get_symbol_offset (seq); -kallsyms_expand_symbol (off, namebuf,ARRAY_SIZE (namebuf)); -if (strcmp (name, namebuf)) +if (kallsyms_strcmp_symbol (off, name) !=0 )break ; low--; }
@@ -212,8 +237,7 @@ static int kallsyms_lookup_names(const char *name,while (high < kallsyms_num_syms -1 ) { seq =get_symbol_seq (high +1 ); off =get_symbol_offset (seq); -kallsyms_expand_symbol (off, namebuf,ARRAY_SIZE (namebuf)); -if (strcmp (name, namebuf)) +if (kallsyms_strcmp_symbol (off, name) !=0 )break ; high++; }
Signature · 1 line
2.55.0
PATCH v4 3/4 kallsyms: Add dynamic lookup index for batch resolution
In reply to Jim Cromiekallsyms_lookup_names() resolves symbol names to addresses using a binary search over kallsyms_seqs_of_names[]. In baseline, each step invokes get_symbol_offset(), which scans sequentially from the nearest 256-symbol marker in kallsyms_names[] (averaging ~128 ULEB128 header decodes per probe, ~2,176 decodes per lookup).
During bulk symbol resolution workloads (e.g. BPF multi-kprobe / fprobe tracing attaching across tens of thousands of functions), this linear scan compounds into substantial kernel attach latency (~3.3 us per lookup). Baking a permanent direct index into .rodata accelerates lookups but consumes hundreds of KiB of unswappable kernel image memory, which is unjustified when bulk lookups are infrequent.
Introduce a dynamic u32 lookup index populated on demand in transient RAM and discarded when the batch workload completes:
0. Expose kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end() bracketed by a mutex and refcount. On the first caller, allocate a flat u32 table spanning all kallsyms_num_syms entries (~736 KiB in transient RAM for ~184k symbols) via kvmalloc_array() and populate the symbol offsets via a single sequential scan in ~150 us.
1. In get_symbol_offset(), when the dynamic table is active, return offsets[pos] directly as an O(1) array access with 0 hops, bracketed by rcu_read_lock() and rcu_read_unlock().
2. If the dynamic table is unallocated (refcount 0), fall back to the legacy kallsyms_markers[] scan, preserving 100% safety for oops, panic, NMI, and low-memory environments without any .rodata bloat.
3. Wrap kallsyms_lookup_names() in rcu_read_lock() / rcu_read_unlock() to ensure lockless lifetime safety across multi-probe searches.
4. Update test_kallsyms_perf and kallsyms_selftest to benchmark both unindexed marker scans and the dynamic batch index side by side, reporting batch lookup performance alongside query amortization break-even points.
---
Changes in v4:
- Annotate dyn_kallsyms_offsets declaration with __rcu to satisfy sparse type checking and prevent address-space warnings across rcu_assign_pointer() and rcu_dereference() (addresses Sashiko AI review).
- Use rcu_replace_pointer() with lockdep_is_held(&dyn_kallsyms_mutex) during batch teardown to atomically read and clear the pointer while satisfying sparse address-space constraints (addresses Sashiko AI review).
Changes in v3:
- Reorder patch after on-the-fly token matching (patch 2) to cleanly isolate and measure the impact of the O(1) dynamic table on top of fast string matching (addresses David Laight review).
- Consume get_symbol_data() helper introduced in patch 2 to preserve clean git bisectability (addresses Sashiko AI review).
- Fix use-after-free race on dyn_kallsyms_offsets: bracket table dereference and array read with rcu_read_lock() and replace rcu_dereference_raw() with rcu_dereference() inside get_symbol_offset() to protect external readers (lookup_symbol_name, kallsyms_lookup_buildid, reset_iter) against concurrent batch teardown (addresses Sashiko AI review).
- In kallsyms_selftest, add a second lookup pass bracketed by kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end() to validate batch resolution in the in-tree selftest.
- Move 24-bit loop unrolling in get_symbol_seq() to standalone patch 4 (addresses David Laight review).
- Move David Laight to series-wide Cc on cover letter, dropping trailer from this patch.
Changes in v2:
- Rework from static build-time 3-byte table to dynamic u32 index allocated in transient RAM during batch sessions, dropping +573 KiB from .rodata to 0 bytes (addresses Kees Cook review).
- Use native u32 indexing to eliminate 24-bit big-endian shifts and unaligned loads (addresses David Laight review).
- Revert changes to scripts/kallsyms.c and kernel/kallsyms_internal.h, retaining legacy kallsyms_markers[] as fallback.
--- include/linux/kallsyms.h | 13 ++++++ kernel/kallsyms.c | 111 ++++++++++++++++++++++++++++++++++++++++++--- kernel/kallsyms_selftest.c | 16 +++++++ lib/test_kallsyms_perf.c | 51 ++++++++++++++++++--- 4 files changed, 179 insertions(+), 12 deletions(-)
include/linux/kallsyms.h +13 -0
@@ -74,6 +74,10 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),int kallsyms_on_each_match_symbol (int (*fn)(void *,unsigned long ),const char *name,void *data); +/* Transient dynamic lookup index bracketing */ +int kallsyms_lookup_batch_start (void ); +void kallsyms_lookup_batch_end (void ); +/* Lookup the address for a symbol. Returns 0 if not found. */ unsigned long kallsyms_lookup_name (const char *name);
@@ -164,6 +168,15 @@ static inline int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long) {return -EOPNOTSUPP ; } + +static inline int kallsyms_lookup_batch_start (void ) +{ +return 0 ; +} + +static inline void kallsyms_lookup_batch_end (void ) +{ +}#endif /*CONFIG_KALLSYMS*/ static inline void print_ip_sym (const char *loglvl,unsigned long ip)
kernel/kallsyms.c +105 -6
156 lines not on this page · raw message
kernel/kallsyms_selftest.c +16 -0
@@ -178,6 +178,7 @@ static int lookup_name(void *data, const char *name, unsigned long addr)static void test_perf_kallsyms_lookup_name (void ) {struct test_stat stat; +int ret;memset (&stat,0 ,sizeof (stat)); stat.min =INT_MAX ;
@@ -185,6 +186,21 @@ static void test_perf_kallsyms_lookup_name(void)pr_info ("kallsyms_lookup_name() looked up %d symbols\n" , stat.real_cnt);pr_info ("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n" , stat.min, stat.max,div_u64 (stat.sum, stat.real_cnt)); + + ret =kallsyms_lookup_batch_start (); +if (ret) { +pr_err ("kallsyms_lookup_batch_start() failed: %d\n" , ret); +return ; + } + +memset (&stat,0 ,sizeof (stat)); + stat.min =INT_MAX ; +kallsyms_on_each_symbol (lookup_name, &stat); +kallsyms_lookup_batch_end (); + +pr_info ("kallsyms_lookup_name() (batch) looked up %d symbols\n" , stat.real_cnt); +pr_info ("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n" , + stat.min, stat.max,div_u64 (stat.sum, stat.real_cnt)); }static int find_symbol (void *data,const char *name,unsigned long addr)
lib/test_kallsyms_perf.c +45 -6
75 lines not on this page · raw message
Signature · 1 line
2.55.0
PATCH v4 4/4 kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
In reply to Jim Cromiekallsyms_seqs_of_names[] stores 3-byte big-endian sequence indices that map alphabetical symbol positions to address-ordered symbol records. Currently, get_symbol_seq() reconstructs each 24-bit integer using a 3-iteration for-loop that shifts and bitwise-ORs each byte sequentially. During binary search in kallsyms_lookup_names() and duplicate boundary scans, this loop introduces branch and loop overhead on the hot lookup path.
Mark get_symbol_seq() as static inline and unroll the 3-byte extraction into direct byte shifts: (p[0] << 16) | (p[1] << 8) | p[2]. This eliminates loop induction variable maintenance and allows the compiler to generate direct loads and constant shifts.
---
Changes in v3:
- Added as a standalone micro-optimization patch (addresses David Laight review).
--- kernel/kallsyms.c | 9 +++------ 1 file changed, 3 insertions(+), 6 deletions(-)
kernel/kallsyms.c +3 -6
@@ -280,14 +280,11 @@ unsigned long kallsyms_sym_address(int idx)return (unsigned long )offset_to_ptr (kallsyms_offsets + idx); } -static unsigned int get_symbol_seq (int index) +static inline unsigned int get_symbol_seq (int index) { -unsigned int i, seq =0 ; +const u8 *p = &kallsyms_seqs_of_names[3 * index]; -for (i =0 ; i <3 ; i++) - seq = (seq <<8 ) | kallsyms_seqs_of_names[3 * index + i]; - -return seq; +return (p[0 ] <<16 ) | (p[1 ] <<8 ) | p[2 ]; } static int kallsyms_lookup_names(const char *name,
Signature · 1 line
2.55.0
Quoted 11 lines · Jim Cromie
2. Patch 3 introduces a dynamic u32 lookup index bracketed by
kallsyms_lookup_batch_start()andkallsyms_lookup_batch_end(). It allocates ~736 KiB in transient RAM viakvmalloc_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. Bothtest_kallsyms_perfandkallsyms_selftestare 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
Signature · 1 line
Kees Cook
On Wed, 23 Sep 2026 00:12:29 -0700
Kees Cook <[email protected]> wrote:
I think you are at ~15x now.
Quoted 24 lines · Jim Cromie
Quoted 11 lines
2. Patch 3 introduces a dynamic u32 lookup index bracketed by
kallsyms_lookup_batch_start()andkallsyms_lookup_batch_end(). It allocates ~736 KiB in transient RAM viakvmalloc_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. Bothtest_kallsyms_perfandkallsyms_selftestare 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.
Quoted 2 lines
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
Quoted 16 lines
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.
Quoted 5 lines
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
Quoted 3 lines
-Kees