Skip to contentSkip to conversation

kallsyms: Accelerate symbol name lookups by ~19x

PATCH Superseded Jim Cromie 3 participants 8 messages Sep 22

Subsystems (3)

v2 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Jim Cromie

author
#0 lore raw

v2 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. Marker scanning: get_symbol_offset() scans sequentially from the nearest 256-symbol marker, decoding an average of ~128 ULEB128 record headers per probe (~2,176 header decodes per lookup).

1. Redundant string expansion: kallsyms_expand_symbol() decompresses the entire candidate symbol into a 512-byte stack buffer (namebuf) before calling strcmp(), even though ~94% of binary search probes mismatch on the first 1-2 characters.

Together, these bottlenecks impose a ~3.8 us latency penalty per hit and ~3.6 us per miss.

This 3-patch series eliminates both overheads while keeping the symbol table strictly in sequential address order and adding 0 bytes to .rodata:

0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to measure unindexed vs dynamic indexed name searches, address resolution, and table iteration latency, with built-in correctness validation and a sysfs trigger.

1. Patch 2 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.

2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries against compressed tokens incrementally on the fly, bailing out on the first mismatched character without expanding subsequent tokens. This drops the 512-byte namebuf buffer from the kernel stack.

Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):

Metric Baseline Patched Speedup
-----------------------------------------------------------------

Name Search Hit           3,811 ns      246 ns        15.5x
Name Search Miss          3,625 ns      196 ns        18.5x
sprint_symbol               412 ns      412 ns        parity
sprint_symbol_no_offset     300 ns      300 ns        parity
Table Full Walk           13,626 us   13,626 us       parity

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 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 (3):
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
kallsyms: Add dynamic lookup index for batch resolution
kallsyms: Match compressed tokens on the fly during binary search

 include/linux/kallsyms.h |  13 +++
 kernel/kallsyms.c        | 210 ++++++++++++++++++++++++++++--------
 lib/Kconfig.debug        |  10 ++
 lib/Makefile             |   1 +
 lib/test_kallsyms_perf.c | 269 +++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 457 insertions(+), 46 deletions(-)

---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a

Best regards,

Signature · 1 line
Jim Cromie <[email protected]>
author
#1 lore raw

PATCH v2 1/3 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/.

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.

---
 kernel/kallsyms.c        |   2 +
 lib/Kconfig.debug        |  10 +++
 lib/Makefile             |   1 +
 lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 241 insertions(+)
kernel/kallsyms.c +2 -0
index aec2f06858af..b9e573e9a10b 100644
@@ -261,6 +261,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
 	}
 	return 0;
 }
+EXPORT_SYMBOL_GPL(kallsyms_on_each_symbol);
 
 int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 				  const char *name, void *data)
@@ -279,6 +280,7 @@ int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 
 	return ret;
 }
+EXPORT_SYMBOL_GPL(kallsyms_on_each_match_symbol);
 
 static unsigned long get_symbol_pos(unsigned long addr,
 				    unsigned long *symbolsize,
lib/Kconfig.debug +10 -0
index 134b15a44625..2a8b1aaee23b 100644
@@ -3122,6 +3122,16 @@ config TEST_STATIC_KEYS
 
 	  If unsure, say N.
 
+config TEST_KALLSYMS_PERF
+	tristate "kallsyms performance benchmark test module"
+	default m
+	help
+	  This builds the test_kallsyms_perf module 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
index dfab958327c5..149968ff3f6b 100644
@@ -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 +228 -0

228 lines not on this page · raw message

Signature · 1 line
2.55.0
#2 lore raw

Re: [PATCH v2 1/3] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency

Thank you for your contribution! Sashiko AI review found 6 potential issue(s) to consider: - [High] kallsyms: re-exporting iterators breaks security encapsulation - [High] kallsyms: missing…

Thank you for your contribution! Sashiko AI review found 6 potential issue(s) to consider:
- [High] kallsyms: re-exporting iterators breaks security encapsulation
- [High] kallsyms: missing preemption in tight loops causes soft lockups
- [High] kallsyms: divide by zero in latency calculation via module parameter
- [High] kallsyms: direct 64-bit division breaks 32-bit builds
- [Medium] kallsyms: test module spuriously fails on kernels without IPv4
- [Low] kconfig: test module set to 'default m' pollutes builds
--

commit 6589e2eb779ca1b70f6d786ad47e1be731aba20e
Author: Jim Cromie <[email protected]>
kallsyms: Add test_kallsyms_perf module to benchmark lookup latency

This commit adds a lightweight microbenchmark module in lib/ to evaluate optimizations and measure performance regressions across kallsyms lookups.

kernel/kallsyms.c int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long), · line 264

Quoted 9 lines
kernel/kallsyms.c +1 -0
index aec2f06858afd..b9e573e9a10b9 100644
@@ -261,6 +261,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
 	}
 	return 0;
 }
+EXPORT_SYMBOL_GPL(kallsyms_on_each_symbol);

[Severity: High]
Does exporting this function directly reverse the security protection introduced by commit 0bd476e6c6719 ("kallsyms: unexport kallsyms_lookup_name() and kallsyms_on_each_symbol()")?

It appears this allows any GPL-compatible out-of-tree module to bypass symbol exports and resolve unexported symbols by passing a custom match function.

kernel/kallsyms.c int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), · line 283

Quoted 7 lines
kernel/kallsyms.c +1 -0
 int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 				  const char *name, void *data)
@@ -279,6 +280,7 @@ int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 
 	return ret;
 }
+EXPORT_SYMBOL_GPL(kallsyms_on_each_match_symbol);

[Severity: High]
Can this export similarly be abused by loadable modules to circumvent the EXPORT_SYMBOL mechanism and resolve unexported symbols natively?

lib/Kconfig.debug config TEST_STATIC_KEYS · line 3127

Quoted 11 lines
lib/Kconfig.debug +3 -0
index 134b15a44625e..2a8b1aaee23b3 100644
@@ -3122,6 +3122,16 @@ config TEST_STATIC_KEYS
 
 	  If unsure, say N.
 
+config TEST_KALLSYMS_PERF
+	tristate "kallsyms performance benchmark test module"
+	default m

[Severity: Low]
Is it intended to have this test module enabled by default? Setting this to default m pollutes default configurations and slows down compilation.

[ ... ]

Quoted 6 lines
lib/test_kallsyms_perf.c new file +0 -0
new file mode 100644
index 0000000000000..c649e55dae3b8
@@ -0,0 +1,228 @@

[ ... ]

lib/test_kallsyms_perf.c line 22

Quoted 3 lines
lib/test_kallsyms_perf.c new file +3 -0
+static unsigned int num_iters = 100000;
+module_param(num_iters, uint, 0644);
+MODULE_PARM_DESC(num_iters, "Number of iterations per microbenchmark");

[Severity: High]
What happens if num_iters is set to 0 via sysfs?

Since this parameter is globally writable and unchecked, could a user write 0 and instantly trigger a hardware divide-by-zero exception during the latency calculations below?

lib/test_kallsyms_perf.c line 30

Quoted 7 lines
lib/test_kallsyms_perf.c new file +7 -0
+static const char * const hit_symbols[] = {
+	"_printk",
+	"schedule",
+	"vfs_read",
+	"do_sys_openat2",
+	"kernel_clone",
+	"tcp_v4_rcv",

[Severity: Medium]
Is it guaranteed that tcp_v4_rcv will be present on all kernel configurations?

If the kernel is built without IPv4 support (CONFIG_INET), won't this valid symbol be missing, causing the correctness validation in run_name_lookup_bench() to emit a false failure?

[ ... ]

Quoted 3 lines
lib/test_kallsyms_perf.c new file +3 -0
+static void run_name_lookup_bench(void)
+{
+	u64 t0, t1, dt_hit, dt_miss;

[ ... ]

lib/test_kallsyms_perf.c line 108

Quoted 8 lines
lib/test_kallsyms_perf.c new file +8 -0
+	/* 2. Name search: Non-existent symbols (Misses - 17 bsearch probes) */
+	t0 = ktime_get_ns();
+	for (i = 0; i < num_iters; i++) {
+		const char *sym = miss_symbols[i % nr_misses];
+
+		kallsyms_on_each_match_symbol(match_cb, sym, &addr);
+		OPTIMIZER_HIDE_VAR(addr);
+	}

[Severity: High]
Could large values of num_iters in this tight loop stall the CPU and trigger soft lockups on CONFIG_PREEMPT_NONE or CONFIG_PREEMPT_VOLUNTARY kernels, since cond_resched() is not invoked?

lib/test_kallsyms_perf.c line 113

Quoted 5 lines
lib/test_kallsyms_perf.c new file +5 -0
+	t1 = ktime_get_ns();
+	dt_miss = t1 - t0;
+
+	pr_info("Name Search Hit:  %llu ns/lookup (%llu ms total, %u iters)\n",
+		dt_hit / num_iters, dt_hit / 1000000, num_iters);

[Severity: High]
Does this direct 64-bit division of dt_hit (a u64) by num_iters break 32-bit builds?

This typically causes link-time failures due to an undefined reference to __udivdi3 on 32-bit architectures. Even with a transition to div_u64() in later commits, the divisor would still need to be checked against zero.

[ ... ]

Quoted 3 lines
lib/test_kallsyms_perf.c new file +3 -0
+static void run_address_lookup_bench(void)
+{
+	u64 t0, t1, dt_sprint, dt_bldid;

[ ... ]

lib/test_kallsyms_perf.c line 145

Quoted 8 lines
lib/test_kallsyms_perf.c new file +8 -0
+	/* 1. Address-to-name resolution (sprint_symbol) */
+	t0 = ktime_get_ns();
+	for (i = 0; i < num_iters; i++) {
+		unsigned long addr = addrs[i % nr_addrs];
+
+		sprint_symbol(symname, addr);
+		barrier_data(symname);
+	}

[Severity: High]
Similar to the name search loop, could this tight loop executing millions of operations without yielding the CPU trigger soft lockup panics?

[ ... ]

lib/test_kallsyms_perf.c line 161

Quoted 2 lines
lib/test_kallsyms_perf.c new file +2 -0
+	pr_info("sprint_symbol:           %llu ns/lookup (%llu ms total, %u iters)\n",
+		dt_sprint / num_iters, dt_sprint / 1000000, num_iters);

[Severity: High]
Could this also trigger a divide-by-zero hardware exception if num_iters is set to 0?

[ ... ]

Quoted 8 lines
lib/test_kallsyms_perf.c new file +8 -0
+static void run_table_walk_bench(void)
+{
+	u64 t0, t1, dt_walk;
+	unsigned long total_symbols = 0;
+	int iter = 50;
+	int i;
+
+	t0 = ktime_get_ns();

lib/test_kallsyms_perf.c line 183

Quoted 10 lines
lib/test_kallsyms_perf.c new file +10 -0
+	for (i = 0; i < iter; i++) {
+		total_symbols = 0;
+		kallsyms_on_each_symbol(count_cb, &total_symbols);
+	}
+	t1 = ktime_get_ns();
+	dt_walk = t1 - t0;
+
+	pr_info("Table Full Walk:  %llu us/pass (%lu symbols scanned, %d passes)\n",
+		(dt_walk / iter) / 1000, total_symbols, iter);
+}

[Severity: High]
Does the 64-bit division here (dt_walk / iter) also break 32-bit builds with an undefined reference to __udivdi3?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
author
#3 lore raw

PATCH v2 2/3 kallsyms: Add dynamic lookup index for batch resolution

In reply to Jim Cromie

kallsyms_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 (~4.5 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.

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 against concurrent batch teardown.

4. Unroll the 3-byte shift loop in get_symbol_seq() into straight-line shifts.

5. Update test_kallsyms_perf to benchmark unindexed marker scans and the dynamic batch index side by side, reporting batch setup and teardown latency alongside query amortization break-even points.

---
 include/linux/kallsyms.h |  13 ++++++
 kernel/kallsyms.c        | 111 ++++++++++++++++++++++++++++++++++++++++++-----
 lib/test_kallsyms_perf.c |  53 +++++++++++++++++++---
 3 files changed, 161 insertions(+), 16 deletions(-)
include/linux/kallsyms.h +13 -0
index d5dd54c53ace..6e39795ac509 100644
@@ -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 +101 -10

157 lines not on this page · raw message

lib/test_kallsyms_perf.c +47 -6

81 lines not on this page · raw message

Signature · 1 line
2.55.0
#4 lore raw

Re: [PATCH v2 2/3] kallsyms: Add dynamic lookup index for batch resolution

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [High] kallsyms: use-after-free on dyn_kallsyms_offsets in lookup paths - [Low] kallsyms: undeclared…

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] kallsyms: use-after-free on dyn_kallsyms_offsets in lookup paths
- [Low] kallsyms: undeclared get_symbol_data() causes build failure
--

commit ab1fc0aa56a3930399c450aad78232a641c6e73f
Author: Jim Cromie <[email protected]>
kallsyms: Add dynamic lookup index for batch resolution

This commit introduces a dynamically allocated lookup index for kallsyms to accelerate batch symbol resolution. The index is built on-demand in transient RAM and freed when the batch concludes, falling back to a linear scan otherwise.

Quoted 4 lines
kernel/kallsyms.c +0 -0
index b9e573e9a10b9..862a6b773ac5e 100644

[ ... ]

Quoted 6 lines
kernel/kallsyms.c +6 -0
+static u32 *kallsyms_build_offsets(void)
+{
+	const u8 *name = kallsyms_names;
+	u32 *offsets;
+	unsigned int i;
+

kernel/kallsyms.c static unsigned int get_symbol_offset(unsigned long pos) · line 178

Quoted 10 lines
kernel/kallsyms.c +10 -0
+	offsets = kvmalloc_array(kallsyms_num_syms, sizeof(u32), GFP_KERNEL);
+	if (!offsets)
+		return NULL;
+
+	for (i = 0; i < kallsyms_num_syms; i++) {
+		unsigned int len;
+		const u8 *data;
+
+		offsets[i] = name - kallsyms_names;
+		data = get_symbol_data(offsets[i], &len);

[Severity: Low]
Does this cause a build failure? I noticed that get_symbol_data() does not seem to be declared or defined in the codebase at this commit. Even if it is introduced in a later patch in the series, each commit should compile independently to preserve git bisectability.

Quoted 5 lines
kernel/kallsyms.c +5 -0
+		name = data + len;
+	}
+
+	return offsets;
+}

[ ... ]

kernel/kallsyms.c static unsigned int get_symbol_offset(unsigned long pos) · line 237

Quoted 10 lines
kernel/kallsyms.c +10 -0
+/*
+ * Find the offset on the compressed table given an index in the
+ * kallsyms array.
+ */
+static inline unsigned int get_symbol_offset(unsigned long pos)
+{
+	u32 *offsets = rcu_dereference_raw(dyn_kallsyms_offsets);
+
+	if (offsets)
+		return offsets[pos];

[Severity: High]
Could this lead to a use-after-free when kallsyms_lookup_batch_end() tears down the batch?

Because rcu_dereference_raw() is used here, static analysis and lockdep cannot verify whether rcu_read_lock() is held. Readers like the /proc/kallsyms seq_file iterators (e.g., reset_iter()) or exported APIs (like lookup_symbol_name() or kallsyms_lookup_buildid()) can call this function in preemptible contexts without RCU protection.

If a reader is preempted after dereferencing the pointer but before accessing the array element, and another thread completes kallsyms_lookup_batch_end(), synchronize_rcu() will not wait for the preempted reader, which will then access the freed array.

Quoted 3 lines
kernel/kallsyms.c +3 -0
+
+	return get_symbol_offset_marker(pos);
+}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
author
#5 lore raw

PATCH v2 3/3 kallsyms: Match compressed tokens on the fly during binary search

In reply to Jim Cromie

kallsyms_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. Leaves sequential address ordering and kallsyms_expand_symbol() streaming invariants intact for /proc/kallsyms and table walks.

---
 kernel/kallsyms.c | 97 ++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 61 insertions(+), 36 deletions(-)
kernel/kallsyms.c +61 -36
index 862a6b773ac5..4a04d63e4b7d 100644
@@ -37,6 +37,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,
@@ -45,28 +60,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
@@ -94,7 +93,7 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
 	if (maxlen)
 		*result = '\0';
 
-	/* Return to offset to the next symbol. */
+	/* Return offset to the next symbol. */
 	return off;
 }
 
@@ -104,16 +103,46 @@ 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)
+{
+	int skipped_first = 0;
+	const char *tptr;
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
+
+	while (len) {
+		tptr = &kallsyms_token_table[kallsyms_token_index[*data]];
+		data++;
+		len--;
+
+		while (*tptr) {
+			if (skipped_first) {
+				int diff = (unsigned char)*name - (unsigned char)*tptr;
+
+				if (diff != 0)
+					return diff;
+				name++;
+			} else {
+				skipped_first = 1;
+			}
+			tptr++;
+		}
+	}
+
+	return (unsigned char)*name - '\0';
+}
 
 /*
  * Find the offset on the compressed stream given an index in the
@@ -261,7 +290,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;
@@ -271,8 +299,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)
@@ -290,8 +317,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--;
 	}
@@ -302,8 +328,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
#6 lore raw

Re: [PATCH v2 3/3] kallsyms: Match compressed tokens on the fly during binary search

Quoted 32 lines · On Tue, 22 Sep 2026 01:19:21 -0600 Jim Cromie <[email protected]> wrote:

kallsyms_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. Leaves sequential address ordering and kallsyms_expand_symbol() streaming invariants intact for /proc/kallsyms and table walks.

...

Quoted 24 lines
kernel/kallsyms.c +24 -0
+/*
+ * 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)
+{
+	int skipped_first = 0;
+	const char *tptr;
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
+
+	while (len) {
+		tptr = &kallsyms_token_table[kallsyms_token_index[*data]];
+		data++;
+		len--;
+
+		while (*tptr) {
+			if (skipped_first) {
+				int diff = (unsigned char)*name - (unsigned char)*tptr;
+
+				if (diff != 0)
+					return diff;

kernel/kallsyms.c static unsigned int kallsyms_expand_symbol(unsigned int off, · line 145

Quoted 10 lines
kernel/kallsyms.c +10 -0
+				name++;
+			} else {
+				skipped_first = 1;
+			}
+			tptr++;
+		}
+	}
+
+	return (unsigned char)*name - '\0';
+}

Since len can't be zero you can move the test to the bottom and remove the skipped_first test completely. Something like:

	tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
	for (;;) {
		do {
			int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
			if (diff)
				return diff;
		} while (*tptr);
		if (!--len)
			break;
		tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
	}
	return (unsigned char)*name;

Also 'char' is now 'unsigned char' in all kernel builds you don't need the casts.
But I'd make the types explicitly 'unsigned char' just in case.

David

Quoted 3 lines

/*
* Find the offset on the compressed stream given an index in the

...

#7 lore raw
In reply to Jim Cromie
Quoted 9 lines · On Tue, 22 Sep 2026 01:19:18 -0600 Jim Cromie <[email protected]> wrote:

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. Marker scanning: get_symbol_offset() scans sequentially from the nearest 256-symbol marker, decoding an average of ~128 ULEB128 record headers per probe (~2,176 header decodes per lookup).

Quoted 7 lines

1. Redundant string expansion: kallsyms_expand_symbol() decompresses the entire candidate symbol into a 512-byte stack buffer (namebuf) before calling strcmp(), even though ~94% of binary search probes mismatch on the first 1-2 characters.

Together, these bottlenecks impose a ~3.8 us latency penalty per hit and ~3.6 us per miss.

How much does just doing change 1 give you?
Might be worth putting that patch first.

If you do the binary chop using only 256 aligned symbols it won't add any more stages but means you don't need to scan until the 256 symbol block has been identified.
At that point there are two options:
B: A linear scan - average 128 compare per lookup.
A: Generate a table of the offsets for the next 128 symbols and do
a binary scan (only read the second 128 if in the second half).

The linear scan may not be too bad.
You can get the first data byte while sorting out the length and then to an initial check that the first few characters match before adding in the complexity of the loop along the compressed data.

David