kallsyms: Accelerate symbol name lookups by ~7x
v7 cover kallsyms: Accelerate symbol name lookups by ~7x
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.
---
Changes in v7:
- Lead cover letter with concrete workloads and "who cares" (citing CrowdStrike commit 93e8fd1a565e and 64k BPF selftest attach times) (addresses Andrew Morton review).
- Document lineage from Zhen Lei's 2022 binary search work in commit 60443c88f3a8 (+550 KiB .rodata) and frame this series as completing that optimization (+42 KiB .rodata for 7x faster lookups).
- Explicitly detail memory (+42.2 KiB .rodata, 0 B RAM, -512 B stack)
and build-time (<1 ms) trade-offs in cover letter (addresses Andrew Morton review).
- Detail lack of runtime complexity (0 kmalloc, 0 RCU, 0 locks, 0 new algos).
- Note scripts/kallsyms.c reading KALLSYMS_MARKER_SHIFT from kernel/ header as single source of truth.
- Add Petr Mladek, Zhen Lei, Luis Chamberlain, Andrey Grodzovsky, and Steven Rostedt to Cc list.
- Link to v6: https://lore.kernel.org/r/[email protected]
Changes in v6:
- In patch 1, clarify token matching mechanics and early exit on char 0..N-1; cite CONFIG_KALLSYMS_SELFTEST across all ~184k symbols for the ~530 ns measurement (addresses BPF CI review).
- In patch 1, drop 0-2 list and fix repeated word typo ("the the").
- In patch 2, recast commit body around kallsyms storage trade-offs and drop hunk-by-hunk numbered list (addresses BPF CI review).
- In patch 2, drop 0.002% percentage claim and state absolute .rodata cost (+42 KiB for ~184k symbols).
- In patch 2, drop ephemeral benchmark comment from kernel/kallsyms_internal.h (addresses BPF CI review).
- Link to v5: https://lore.kernel.org/r/[email protected]
Changes in v5:
- Dismiss dynamic 1:1 batch table as unnecessary:
In v2-v4, a dynamic u32 lookup index allocated in transient RAM was explored. While dynamic 1:1 breaks even against baseline 256:1 after ~1,200 queries, comparing dynamic 1:1 against static 16:1 markers dismisses the dynamic approach entirely:
* Static 16:1 markers achieve 866 ns, capturing 97.4% of the maximum latency savings of a 1:1 table (an 85.8% reduction from baseline).
* Dynamic 1:1 gains only an incremental 138 ns (the remaining 2.6%), while paying ~6,419 us in allocation setup and synchronize_rcu() teardown.
* Amortizing 6,419 us at 138 ns saved requires 46,514 queries just to break even against 16:1 markers. For any workload under 46k
queries, dynamic allocation is slower overall.
* Drop kallsyms_lookup_batch_start/end APIs, mutexes, refcounts, transient kvmalloc RAM allocations, and RCU synchronization.
- Drop lib/test_kallsyms_perf benchmark module and CONFIG_TEST_KALLSYMS_PERF; existing in-tree CONFIG_KALLSYMS_SELFTEST already benchmarks standard kallsyms_lookup_name() without adding unmaintained test files in lib/.
- In patch 2, increase marker density to 16:1 via
KALLSYMS_MARKER_SHIFT 4 shared between scripts/kallsyms.c and kernel/kallsyms_internal.h, and drop all references to dynamic tables from the patch body.
- Link to v4: https://lore.kernel.org/r/[email protected]
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 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 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 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 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 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
review).
- Link to v3: https://lore.kernel.org/r/[email protected]
Changes in v3:
- Reorder series: place on-the-fly token matching ahead of marker
density optimization, establishing an active proof of incremental performance deltas across all steps (addresses David Laight review).
- Add inlined and unrolled get_symbol_seq() 24-bit sequence index reconstruction into direct byte shifts (addresses David Laight
review).
- In test_kallsyms_perf, configure 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 review).
- In patch 1, optimize kallsyms_strcmp_symbol() by dropping
skipped_first tracking and checking len at the bottom of the token
loop (addresses David Laight review).
- 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.
- 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.
- Link to v1: https://lore.kernel.org/r/[email protected]
---
Jim Cromie (3):
kallsyms: Match compressed tokens on the fly during binary search
kallsyms: Increase marker density to 16:1 to accelerate lookups
kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
kernel/kallsyms.c | 111 +++++++++++++++++++++++++++------------------ kernel/kallsyms_internal.h | 11 +++++ scripts/kallsyms.c | 14 ++++-- 3 files changed, 86 insertions(+), 50 deletions(-)
---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a
Best regards,
Signature · 1 line
Jim Cromie <[email protected]>
PATCH v7 1/3 kallsyms: Match compressed tokens on the fly during binary search
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().
---
Changes in v6:
- Clarify character match mechanics in commit body (no stack expansion, short-circuit at first divergent char 0..N-1).
- Cite CONFIG_KALLSYMS_SELFTEST across all ~184k symbols for performance measurements.
- Drop stale "unindexed" phrasing and update symbol count to ~184k.
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 later
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
[email protected]
AI reviewRe: [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search
Does the commit message have the same paragraph twice? Both start with "However, full string expansion at every step is equally wasteful" and make the same point about wasteful expansion. The first…
Quoted 21 lines
kallsyms: Match compressed tokens on the fly during binary search
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 callingstrcmp().Comparing tokenized symbols directly in compressed space is impossible. The BPE token table assigns values by frequency, not alphabetical order (e.g. token
0x05might expand to "zebra" while0x42expands 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.
Quoted 5 lines
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.
Does the commit message have the same paragraph twice? Both start with "However, full string expansion at every step is equally wasteful" and make the same point about wasteful expansion. The first version uses rough phrasing ("strcmps", "+/- outcome at char 0,1,2..N-1"), while the second version is more polished ("strcmp()s", "diverge at the first differing character"). Having two paragraphs in a row starting with "However," also makes the rationale harder to follow.
Should one of the paragraphs be removed, probably the first one since the second is clearer?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/36651779347
Re: [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search
In reply to Jim CromieQuoted 6 lines · On Tue, Sep 29, 2026 at 12:07:30PM -0600, Jim Cromie via B4 Relay wrote:
So we introduce
kallsyms_strcmp_symbol()to compare ASCIIsearch_nameagainst 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.
Quoted 6 lines
Measured across all ~184k symbols via
CONFIG_KALLSYMS_SELFTEST, this shaves ~530 ns (~14%) off averagekallsyms_lookup_name()latency (from ~3810 ns to ~3280 ns on the default 256:1 baseline) and drops the 512-byte namebuf buffer stack-alloc inkallsyms_lookup_names().Signed-off-by Jim Cromie <[email protected]>
This is a nice win with no downside. :)
Signature · 1 line
Kees Cook
PATCH v7 2/3 kallsyms: Increase marker density to 16:1 to accelerate lookups
In reply to Jim Cromiekallsyms stores symbols with remarkably efficient packing, and simple streaming unpacking, laid out sequentially in address order. That said, variable-length records make arbitrary access inherently linear. kallsyms_markers[] addressed this by marking stream offsets every 256 symbols, reducing the scan distance by 256x down to an average of 127.5 sequential steps.
While 127.5 hops was negligible for rare, single-shot oops backtraces, both table size (~184k symbols) and lookup traffic have expanded substantially. In alphabetical binary search (kallsyms_lookup_names), each of the ~17 comparison probes must locate candidate symbols via get_symbol_offset(), compounding into ~2,170 sequential symbol hops per lookup. In bulk tracing workloads (such as BPF multi-kprobe attach), this penalty compounds into multi-second latency.
Without altering the underlying storage layout, we can retune this trade-off directly by increasing marker density from 256:1 down to 16:1 (KALLSYMS_MARKER_SHIFT 4) in kernel/kallsyms_internal.h, shared between scripts/kallsyms.c and kernel/kallsyms.c.
This caps the remainder scan at 15 symbols and cuts average scan distance from 127.5 down to 7.5 hops (a 17x reduction). Across a 17-step binary search, total hops collapse from ~2,170 down to ~127. For a kernel with ~184,000 symbols, this adds ~10,800 u32 marker entries (+42 KiB) to write-protected .rodata.
In-tree CONFIG_KALLSYMS_SELFTEST measurements across all ~184k symbols show average lookup latency dropping from 6,102 ns down to 866 ns (a 7.0x speedup).
---
Changes in v6:
- Recast intro around the kallsyms storage/marker trade-off (efficient address packing vs linear search hops).
- Drop hunk-by-hunk numbered list from commit body (addresses BPF CI review).
- Drop 0.002% percentage claim and state absolute .rodata cost (+42 KiB for ~184k symbols).
- Drop ephemeral benchmark comment from kernel/kallsyms_internal.h. replace with scripts/kallsyms.c include ref and __KERNEL__ wrap
Changes in v5:
- Replace dynamic 1:1 batch lookup index (kvmalloc, mutexes, RCU) with static 16:1 marker density (KALLSYMS_MARKER_SHIFT 4) in .rodata (addresses Kees Cook review).
- Eliminate all dynamic RAM allocations, setup/teardown costs, and external batch APIs.
fx2
--- kernel/kallsyms.c | 8 ++++---- kernel/kallsyms_internal.h | 11 +++++++++++ scripts/kallsyms.c | 14 +++++++++----- 3 files changed, 24 insertions(+), 9 deletions(-)
kernel/kallsyms.c +4 -4
@@ -150,10 +150,10 @@ static unsigned int get_symbol_offset(unsigned long pos)int i, len;/* -* Use the closest marker we have. We have markers every 256 positions, -* so that should be close enough. +* Use the closest marker we have. We have markers every +* (1 << KALLSYMS_MARKER_SHIFT) positions, so that should be close enough. */ - name = &kallsyms_names[kallsyms_markers[pos >>8 ]]; + name = &kallsyms_names[kallsyms_markers[pos >>KALLSYMS_MARKER_SHIFT ]];/* * Sequentially scan all the symbols up to the point we're searching
@@ -161,7 +161,7 @@ static unsigned int get_symbol_offset(unsigned long pos)* so we just need to add the len to the current pointer for every * symbol we wish to skip. */ -for (i =0 ; i < (pos &0xFF ); i++) { +for (i =0 ; i < (pos &KALLSYMS_MARKER_MASK ); i++) { len = *name;/*
kernel/kallsyms_internal.h +11 -0
@@ -2,6 +2,16 @@#ifndef LINUX_KALLSYMS_INTERNAL_H_ #define LINUX_KALLSYMS_INTERNAL_H_ +/* +* Provide compile-constants for scripts/kallsyms.c +* so it can build the corresponding kallsyms_marker[] table. +* and wrap the rest in __KERNEL__ +*/ +#define KALLSYMS_MARKER_SHIFT 4 +#define KALLSYMS_MARKER_SIZE (1U << KALLSYMS_MARKER_SHIFT) +#define KALLSYMS_MARKER_MASK (KALLSYMS_MARKER_SIZE - 1U) + +#ifdef __KERNEL__#include <linux/types.h> extern const int kallsyms_offsets[];
@@ -14,5 +24,6 @@ extern const u16 kallsyms_token_index[];extern const unsigned int kallsyms_markers[];extern const u8 kallsyms_seqs_of_names[]; +#endif /* __KERNEL__ */ #endif // LINUX_KALLSYMS_INTERNAL_H_
scripts/kallsyms.c +9 -5
@@ -29,6 +29,8 @@#include <xalloc.h> +#include "../kernel/kallsyms_internal.h" +#define ARRAY_SIZE (arr) (sizeof(arr) / sizeof(arr[0]))#define KSYM_NAME_LEN 512
@@ -349,16 +351,18 @@ static void write_src(void)printf ("\t.long\t%u\n" , table_cnt);printf ("\n" ); -/* table of offset markers, that give the offset in the compressed stream -* every 256 symbols */ - markers_cnt = (table_cnt +255 ) /256 ; +/* +* Table of offset markers, giving the offset in the compressed stream +* every (1 << KALLSYMS_MARKER_SHIFT) symbols. +*/ + markers_cnt = (table_cnt +KALLSYMS_MARKER_MASK ) >>KALLSYMS_MARKER_SHIFT ; markers =xmalloc (sizeof (*markers) * markers_cnt);output_label ("kallsyms_names" ); off =0 ;for (i =0 ; i < table_cnt; i++) { -if ((i &0xFF ) ==0 ) - markers[i >>8 ] = off; +if ((i &KALLSYMS_MARKER_MASK ) ==0 ) + markers[i >>KALLSYMS_MARKER_SHIFT ] = off; table[i]->seq = i;/* There cannot be any symbol of length zero. */
Signature · 1 line
2.55.0
Re: [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups
Quoted 10 lines · On Tue, Sep 29, 2026 at 12:07:31PM -0600, Jim Cromie via B4 Relay wrote:
Without altering the underlying storage layout, we can retune this trade-off directly by increasing marker density from 256:1 down to 16:1 (
KALLSYMS_MARKER_SHIFT4) inkernel/kallsyms_internal.h, shared betweenscripts/kallsyms.candkernel/kallsyms.c.This caps the remainder scan at 15 symbols and cuts average scan distance from 127.5 down to 7.5 hops (a 17x reduction). Across a 17-step binary search, total hops collapse from ~2,170 down to ~127. For a kernel with ~184,000 symbols, this adds ~10,800 u32 marker entries (+42 KiB) to write-protected .rodata.
Thanks for trying a non 1:1 route. I think this is a reasonable time/space trade-off. ~42k .rodata to get a large speed-up.
Signature · 1 line
Kees Cook
PATCH v7 3/3 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
@@ -185,14 +185,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
Re: [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
Quoted 4 lines · On Tue, Sep 29, 2026 at 12:07:32PM -0600, Jim Cromie via B4 Relay wrote:
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.
So... did you actually see any difference in the output binary? This is such a small loop I'd expect every compiler to both inline and unroll it already. *time passes* I've checked; I was mostly right. :)
It's already inlined and unrolled by the compilers, but GCC weirdly didn't see through the array math:
At -O2 GCC (and Clang, mostly the same) on x86_64:
before after lea (%rax,%rax,2),%eax lea (%rax,%rax,2),%edx mov %rax,%rdx movslq %edx,%rdx movzbl seqs(%rax),%eax movzbl seqs(%rdx),%eax lea 0x1(%rdx),%ecx movzbl seqs+2(%rdx),%ecx add $0x2,%edx movzbl seqs+1(%rdx),%edx movzbl seqs(%rcx),%ecx shl $0x10,%eax shl $0x8,%eax shl $0x8,%edx movzbl seqs(%rdx),%edx or %ecx,%eax or %ecx,%eax or %edx,%eax
shl $0x8,%eax
or %edx,%eax
So it's actually the loss of the "+ i" part that does it.
kernel/kallsyms.c unsigned long kallsyms_sym_address(int idx) · line 193
Quoted 12 lines
kernel/kallsyms.c +3
-6-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 ]; }
I'm on the fence about readability, but I think it's improved.
Signature · 1 line
Kees Cook
Re: [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
Quoted 25 lines · On Tue, 29 Sep 2026 23:56:12 -0700 Kees Cook <[email protected]> wrote:
Quoted 4 lines · On Tue, Sep 29, 2026 at 12:07:32PM -0600, Jim Cromie via B4 Relay wrote:
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.So... did you actually see any difference in the output binary? This is such a small loop I'd expect every compiler to both inline and unroll it already. *time passes* I've checked; I was mostly right. :)
It's already inlined and unrolled by the compilers, but GCC weirdly didn't see through the array math:
At -O2 GCC (and Clang, mostly the same) on
x86_64:before after lea (%rax,%rax,2),%eax lea (%rax,%rax,2),%edx mov %rax,%rdx movslq %edx,%rdx movzbl seqs(%rax),%eax movzbl seqs(%rdx),%eax lea 0x1(%rdx),%ecx movzbl seqs+2(%rdx),%ecx add $0x2,%edx movzbl seqs+1(%rdx),%edx movzbl seqs(%rcx),%ecx shl $0x10,%eax shl $0x8,%eax shl $0x8,%edx movzbl seqs(%rdx),%edx or %ecx,%eax or %ecx,%eax or %edx,%eax
Quoted 4 lines
shl $0x8,%eax
or %edx,%eaxSo it's actually the loss of the "+ i" part that does it.
A quick 'register dependency chain count' gives the old as 7 and the new as 6.
The annoying 'movslq' might be removable by making the parameter either 'unsigned int' or 'long' (and might go away if the function in inlined).
Quoted 7 lines
Quoted 7 lines
kernel/kallsyms.c +2
-2-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];
Quoted 8 lines
kernel/kallsyms.c unsigned long kallsyms_sym_address(int idx) · line 193
Quoted 6 lines
kernel/kallsyms.c +1
-4-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 ]; }I'm on the fence about readability, but I think it's improved.
Ditto.
There might be a get_unaligned_be24() but that doesn't help readability.
The code would be better if the value were host-endian. gcc 16+ then uses a 16bit read for two of the bytes. That also lets the table be defined as:
extern struct { unsigned int v:24; } kallsyms_seqs_of_names[];so that accesses can just be kallsyms_seqs_of_names[n].v (Although even gcc 16 seems to do three reads in that case.)
If the cpu supports misaligned accesses you can do a 32bit read and an 8bit shift.
David
Quoted 3 lines
Reviewed-by Kees Cook <[email protected]>
Quoted 21 lines · On Tue, 29 Sep 2026 12:07:29 -0600 Jim Cromie via B4 Relay…
In 2022, commit
60443c88f3a8("kallsyms: Improve the performance ofkallsyms_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 selftestserial_test_kprobe_multi_bench_attachacross 64,000 symbols),kallsyms_lookup_names()spends ~390 ms in raw CPU spin.
Quoted 3 lines
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:
Thanks, this is awesome.
Quoted 21 lines
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.
Quoted 8 lines
Results (
CONFIG_KALLSYMS_SELFTESTacross ~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).
That's the bad news. Can anything be done to reduce this aspect?
Quoted 5 lines
---
Jim Cromie (3):
kallsyms: Match compressed tokens on the fly during binary search
kallsyms: Increase marker density to 16:1 to accelerate lookups
kallsyms: Unroll 24-bit sequence reconstruction inget_symbol_seq()
I'll queue this in mm.git for testing, would prefer not to go further without third-party review, please.