* [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search
2026-09-29 18:07 [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Jim Cromie via B4 Relay
@ 2026-09-29 18:07 ` Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups Jim Cromie via B4 Relay
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Jim Cromie via B4 Relay @ 2026-09-29 18:07 UTC (permalink / raw)
To: Andrew Morton
Cc: Petr Mladek, Zhen Lei, Luis Chamberlain, Andrey Grodzovsky,
Steven Rostedt, Lorenzo Stoakes, Kees Cook, David Laight,
Masahiro Yamada, Jiri Olsa, linux-kernel, linux-kbuild, bpf,
Jim Cromie
From: Jim Cromie <jim.cromie@gmail.com>
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().
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
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(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index aec2f06858af..d18d78e626db 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -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++;
}
--
2.55.0
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups
2026-09-29 18:07 [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search Jim Cromie via B4 Relay
@ 2026-09-29 18:07 ` Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() Jim Cromie via B4 Relay
2026-09-29 18:45 ` [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Andrew Morton
3 siblings, 0 replies; 5+ messages in thread
From: Jim Cromie via B4 Relay @ 2026-09-29 18:07 UTC (permalink / raw)
To: Andrew Morton
Cc: Petr Mladek, Zhen Lei, Luis Chamberlain, Andrey Grodzovsky,
Steven Rostedt, Lorenzo Stoakes, Kees Cook, David Laight,
Masahiro Yamada, Jiri Olsa, linux-kernel, linux-kbuild, bpf,
Jim Cromie
From: Jim Cromie <jim.cromie@gmail.com>
kallsyms 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).
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
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(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..91ced7aa797e 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -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;
/*
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..6a781e4cc77f 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -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_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 494852ade6d8..be42a9111350 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -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. */
--
2.55.0
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
2026-09-29 18:07 [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups Jim Cromie via B4 Relay
@ 2026-09-29 18:07 ` Jim Cromie via B4 Relay
2026-09-29 18:45 ` [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Andrew Morton
3 siblings, 0 replies; 5+ messages in thread
From: Jim Cromie via B4 Relay @ 2026-09-29 18:07 UTC (permalink / raw)
To: Andrew Morton
Cc: Petr Mladek, Zhen Lei, Luis Chamberlain, Andrey Grodzovsky,
Steven Rostedt, Lorenzo Stoakes, Kees Cook, David Laight,
Masahiro Yamada, Jiri Olsa, linux-kernel, linux-kbuild, bpf,
Jim Cromie
From: Jim Cromie <jim.cromie@gmail.com>
kallsyms_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.
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
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(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 91ced7aa797e..52e41879c24b 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -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,
--
2.55.0
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x
2026-09-29 18:07 [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Jim Cromie via B4 Relay
` (2 preceding siblings ...)
2026-09-29 18:07 ` [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() Jim Cromie via B4 Relay
@ 2026-09-29 18:45 ` Andrew Morton
3 siblings, 0 replies; 5+ messages in thread
From: Andrew Morton @ 2026-09-29 18:45 UTC (permalink / raw)
To: jim.cromie
Cc: Jim Cromie via B4 Relay, Petr Mladek, Zhen Lei, Luis Chamberlain,
Andrey Grodzovsky, Steven Rostedt, Lorenzo Stoakes, Kees Cook,
David Laight, Masahiro Yamada, Jiri Olsa, linux-kernel,
linux-kbuild, bpf, Geert Uytterhoeven
On Tue, 29 Sep 2026 12:07:29 -0600 Jim Cromie via B4 Relay <devnull+jim.cromie.gmail.com@kernel.org> wrote:
> 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:
Thanks, this is awesome.
> 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).
That's the bad news. Can anything be done to reduce this aspect?
> ---
> 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()
I'll queue this in mm.git for testing, would prefer not to go further
without third-party review, please.
^ permalink raw reply [flat|nested] 5+ messages in thread