[PATCH v2 0/3] kallsyms: Accelerate symbol name lookups by ~19x

[PATCH v2 0/3] kallsyms: Accelerate symbol name lookups by ~19x

[Jim Cromie]

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.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
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/20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com

---
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,
-- 
Jim Cromie <jim.cromie@gmail.com>

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

[Jim Cromie]

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.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/kallsyms.c        |   2 +
 lib/Kconfig.debug        |  10 +++
 lib/Makefile             |   1 +
 lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 241 insertions(+)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index aec2f06858af..b9e573e9a10b 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -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,
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 134b15a44625..2a8b1aaee23b 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -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
diff --git a/lib/Makefile b/lib/Makefile
index dfab958327c5..149968ff3f6b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -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)
diff --git a/lib/test_kallsyms_perf.c b/lib/test_kallsyms_perf.c
new file mode 100644
index 000000000000..c649e55dae3b
--- /dev/null
+++ b/lib/test_kallsyms_perf.c
@@ -0,0 +1,228 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * Microbenchmark and correctness test module for kallsyms subsystem
+ *
+ * Measures CPU latency across:
+ *  - Name-to-Address binary search (hits & misses)
+ *  - Address-to-Name symbol resolution (sprint_symbol, buildid)
+ *  - Full kernel symbol iteration (kallsyms_on_each_symbol)
+ */
+
+#define pr_fmt(fmt) "test_kallsyms: " fmt
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/kallsyms.h>
+#include <linux/ktime.h>
+#include <linux/compiler.h>
+
+static unsigned int num_iters = 100000;
+module_param(num_iters, uint, 0644);
+MODULE_PARM_DESC(num_iters, "Number of iterations per microbenchmark");
+
+static const char * const hit_symbols[] = {
+	"_printk",
+	"schedule",
+	"vfs_read",
+	"do_sys_openat2",
+	"kernel_clone",
+	"tcp_v4_rcv",
+	"kallsyms_lookup_names",
+	"vm_area_alloc",
+};
+
+static const char * const miss_symbols[] = {
+	"nonexistent_symbol_0001",
+	"xyz_dummy_missing_symbol",
+	"__never_compiled_in_kernel",
+	"ext4_nonexistent_func_xyz",
+	"bpf_not_real_helper_stub",
+	"vfs_missing_handler_probe",
+	"tcp_v4_unimplemented_path",
+	"driver_fake_init_routine",
+};
+
+static int match_cb(void *data, unsigned long addr)
+{
+	unsigned long *out = data;
+
+	*out = addr;
+	return 1;
+}
+
+static int count_cb(void *data, const char *name, unsigned long addr)
+{
+	unsigned long *cnt = data;
+
+	(*cnt)++;
+	return 0;
+}
+
+static void run_name_lookup_bench(void)
+{
+	u64 t0, t1, dt_hit, dt_miss;
+	unsigned long addr = 0;
+	unsigned int i, nr_hits, nr_misses;
+
+	nr_hits = ARRAY_SIZE(hit_symbols);
+	nr_misses = ARRAY_SIZE(miss_symbols);
+
+	/* 0. Correctness validation */
+	for (i = 0; i < nr_hits; i++) {
+		const char *sym = hit_symbols[i];
+		unsigned long a1 = 0;
+
+		kallsyms_on_each_match_symbol(match_cb, sym, &a1);
+		if (!a1)
+			pr_err("CORRECTNESS FAILURE: hit sym '%s' not found\n", sym);
+	}
+	for (i = 0; i < nr_misses; i++) {
+		const char *sym = miss_symbols[i];
+		unsigned long a1 = 0;
+
+		kallsyms_on_each_match_symbol(match_cb, sym, &a1);
+		if (a1)
+			pr_err("CORRECTNESS FAILURE: miss sym '%s' unexpectedly found a1=%lx\n",
+			       sym, a1);
+	}
+
+	/* 1. Name search: Existing symbols (Hits) */
+	t0 = ktime_get_ns();
+	for (i = 0; i < num_iters; i++) {
+		const char *sym = hit_symbols[i % nr_hits];
+
+		kallsyms_on_each_match_symbol(match_cb, sym, &addr);
+		OPTIMIZER_HIDE_VAR(addr);
+	}
+	t1 = ktime_get_ns();
+	dt_hit = t1 - t0;
+
+	/* 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);
+	}
+	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);
+	pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
+		dt_miss / num_iters, dt_miss / 1000000, num_iters);
+}
+
+static void run_address_lookup_bench(void)
+{
+	u64 t0, t1, dt_sprint, dt_bldid;
+	char symname[KSYM_SYMBOL_LEN];
+	unsigned long addrs[ARRAY_SIZE(hit_symbols)];
+	unsigned int i, nr_addrs = 0;
+
+	for (i = 0; i < ARRAY_SIZE(hit_symbols); i++) {
+		unsigned long addr = 0;
+
+		kallsyms_on_each_match_symbol(match_cb, hit_symbols[i], &addr);
+		if (addr)
+			addrs[nr_addrs++] = addr;
+	}
+
+	if (!nr_addrs) {
+		pr_warn("Address benchmark skipped: no test addresses resolved\n");
+		return;
+	}
+
+	/* 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);
+	}
+	t1 = ktime_get_ns();
+	dt_sprint = t1 - t0;
+
+	/* 2. Address without offset (sprint_symbol_no_offset) */
+	t0 = ktime_get_ns();
+	for (i = 0; i < num_iters; i++) {
+		unsigned long addr = addrs[i % nr_addrs];
+
+		sprint_symbol_no_offset(symname, addr);
+		barrier_data(symname);
+	}
+	t1 = ktime_get_ns();
+	dt_bldid = t1 - t0;
+
+	pr_info("sprint_symbol:           %llu ns/lookup (%llu ms total, %u iters)\n",
+		dt_sprint / num_iters, dt_sprint / 1000000, num_iters);
+	pr_info("sprint_symbol_no_offset: %llu ns/lookup (%llu ms total, %u iters)\n",
+		dt_bldid / num_iters, dt_bldid / 1000000, num_iters);
+}
+
+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();
+	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);
+}
+
+static int run_kallsyms_benchmark(void)
+{
+	pr_info("==================================================\n");
+	pr_info("Starting kallsyms performance benchmark (iters=%u)\n", num_iters);
+	pr_info("==================================================\n");
+
+	run_name_lookup_bench();
+	run_address_lookup_bench();
+	run_table_walk_bench();
+
+	pr_info("==================================================\n");
+	pr_info("kallsyms benchmark complete\n");
+	pr_info("==================================================\n");
+
+	return 0;
+}
+
+static int param_set_trigger(const char *val, const struct kernel_param *kp)
+{
+	return run_kallsyms_benchmark();
+}
+
+static const struct kernel_param_ops param_ops_trigger = {
+	.set = param_set_trigger,
+};
+module_param_cb(run_test, &param_ops_trigger, NULL, 0200);
+MODULE_PARM_DESC(run_test, "Write 1 to trigger kallsyms benchmark run");
+
+static int __init test_kallsyms_init(void)
+{
+	return run_kallsyms_benchmark();
+}
+
+static void __exit test_kallsyms_exit(void)
+{
+	pr_info("test_kallsyms module unloaded\n");
+}
+
+module_init(test_kallsyms_init);
+module_exit(test_kallsyms_exit);
+
+MODULE_DESCRIPTION("Microbenchmark test module for kallsyms subsystem");
+MODULE_AUTHOR("Jim Cromie <jim.cromie@gmail.com>");
+MODULE_LICENSE("GPL");

-- 
2.55.0

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

[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.

Cc: David Laight <david.laight.linux@gmail.com>
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 include/linux/kallsyms.h |  13 ++++++
 kernel/kallsyms.c        | 111 ++++++++++++++++++++++++++++++++++++++++++-----
 lib/test_kallsyms_perf.c |  53 +++++++++++++++++++---
 3 files changed, 161 insertions(+), 16 deletions(-)

diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index d5dd54c53ace..6e39795ac509 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -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)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index b9e573e9a10b..862a6b773ac5 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -22,6 +22,9 @@
 #include <linux/sched.h>	/* for cond_resched */
 #include <linux/ctype.h>
 #include <linux/slab.h>
+#include <linux/vmalloc.h>
+#include <linux/mutex.h>
+#include <linux/rcupdate.h>
 #include <linux/filter.h>
 #include <linux/ftrace.h>
 #include <linux/kprobes.h>
@@ -113,10 +116,10 @@ static char kallsyms_get_symbol_type(unsigned int off)
 
 
 /*
- * Find the offset on the compressed stream given and index in the
- * kallsyms array.
+ * Find the offset on the compressed stream given an index in the
+ * kallsyms array using legacy markers.
  */
-static unsigned int get_symbol_offset(unsigned long pos)
+static unsigned int get_symbol_offset_marker(unsigned long pos)
 {
 	const u8 *name;
 	int i, len;
@@ -149,6 +152,93 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	return name - kallsyms_names;
 }
 
+/*
+ * Dynamic symbol offset table.
+ * Allocated on demand during high-volume lookup batches and reclaimed after.
+ */
+static u32 *dyn_kallsyms_offsets __read_mostly;
+static DEFINE_MUTEX(dyn_kallsyms_mutex);
+static unsigned int dyn_kallsyms_refcnt;
+
+static u32 *kallsyms_build_offsets(void)
+{
+	const u8 *name = kallsyms_names;
+	u32 *offsets;
+	unsigned int i;
+
+	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);
+		name = data + len;
+	}
+
+	return offsets;
+}
+
+int kallsyms_lookup_batch_start(void)
+{
+	int ret = 0;
+
+	mutex_lock(&dyn_kallsyms_mutex);
+	if (!dyn_kallsyms_refcnt) {
+		u32 *offsets = kallsyms_build_offsets();
+
+		if (!offsets) {
+			ret = -ENOMEM;
+			goto out;
+		}
+		rcu_assign_pointer(dyn_kallsyms_offsets, offsets);
+	}
+	dyn_kallsyms_refcnt++;
+out:
+	mutex_unlock(&dyn_kallsyms_mutex);
+	return ret;
+}
+EXPORT_SYMBOL_GPL(kallsyms_lookup_batch_start);
+
+void kallsyms_lookup_batch_end(void)
+{
+	u32 *offsets = NULL;
+
+	mutex_lock(&dyn_kallsyms_mutex);
+	if (WARN_ON(!dyn_kallsyms_refcnt))
+		goto out;
+
+	if (--dyn_kallsyms_refcnt == 0) {
+		offsets = dyn_kallsyms_offsets;
+		rcu_assign_pointer(dyn_kallsyms_offsets, NULL);
+	}
+out:
+	mutex_unlock(&dyn_kallsyms_mutex);
+
+	if (offsets) {
+		synchronize_rcu();
+		kvfree(offsets);
+	}
+}
+EXPORT_SYMBOL_GPL(kallsyms_lookup_batch_end);
+
+/*
+ * 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];
+
+	return get_symbol_offset_marker(pos);
+}
+
 unsigned long kallsyms_sym_address(int idx)
 {
 	/* non-relocatable 32-bit kernels just embed the value directly */
@@ -157,14 +247,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,
@@ -179,6 +266,7 @@ static int kallsyms_lookup_names(const char *name,
 	low = 0;
 	high = kallsyms_num_syms - 1;
 
+	rcu_read_lock();
 	while (low <= high) {
 		mid = low + (high - low) / 2;
 		seq = get_symbol_seq(mid);
@@ -193,8 +281,10 @@ static int kallsyms_lookup_names(const char *name,
 			break;
 	}
 
-	if (low > high)
+	if (low > high) {
+		rcu_read_unlock();
 		return -ESRCH;
+	}
 
 	low = mid;
 	while (low) {
@@ -219,6 +309,7 @@ static int kallsyms_lookup_names(const char *name,
 		}
 		*end = high;
 	}
+	rcu_read_unlock();
 
 	return 0;
 }
diff --git a/lib/test_kallsyms_perf.c b/lib/test_kallsyms_perf.c
index c649e55dae3b..df7ee96bdafa 100644
--- a/lib/test_kallsyms_perf.c
+++ b/lib/test_kallsyms_perf.c
@@ -16,6 +16,7 @@
 #include <linux/kallsyms.h>
 #include <linux/ktime.h>
 #include <linux/compiler.h>
+#include <linux/math.h>
 
 static unsigned int num_iters = 100000;
 module_param(num_iters, uint, 0644);
@@ -59,7 +60,7 @@ static int count_cb(void *data, const char *name, unsigned long addr)
 	return 0;
 }
 
-static void run_name_lookup_bench(void)
+static void run_name_lookup_bench(const char *mode, u64 *avg_hit_ns, u64 *avg_miss_ns)
 {
 	u64 t0, t1, dt_hit, dt_miss;
 	unsigned long addr = 0;
@@ -109,10 +110,15 @@ static void run_name_lookup_bench(void)
 	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);
-	pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
-		dt_miss / num_iters, dt_miss / 1000000, num_iters);
+	if (avg_hit_ns)
+		*avg_hit_ns = div_u64(dt_hit, num_iters);
+	if (avg_miss_ns)
+		*avg_miss_ns = div_u64(dt_miss, num_iters);
+
+	pr_info("[%s] Name Search Hit:  %llu ns/lookup (%llu ms total, %u iters)\n",
+		mode, div_u64(dt_hit, num_iters), div_u64(dt_hit, 1000000), num_iters);
+	pr_info("[%s] Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
+		mode, div_u64(dt_miss, num_iters), div_u64(dt_miss, 1000000), num_iters);
 }
 
 static void run_address_lookup_bench(void)
@@ -184,11 +190,46 @@ static void run_table_walk_bench(void)
 
 static int run_kallsyms_benchmark(void)
 {
+	u64 unindexed_hit = 0, unindexed_miss = 0;
+	u64 dyn_hit = 0, dyn_miss = 0;
+	u64 t0, t1, dt_start = 0, dt_end = 0;
+	int ret;
+
 	pr_info("==================================================\n");
 	pr_info("Starting kallsyms performance benchmark (iters=%u)\n", num_iters);
 	pr_info("==================================================\n");
 
-	run_name_lookup_bench();
+	/* 1. Benchmark baseline unindexed marker scan */
+	run_name_lookup_bench("Unindexed (markers)", &unindexed_hit, &unindexed_miss);
+
+	/* 2. Benchmark dynamic lookup index */
+	t0 = ktime_get_ns();
+	ret = kallsyms_lookup_batch_start();
+	t1 = ktime_get_ns();
+	dt_start = t1 - t0;
+
+	if (ret) {
+		pr_err("Failed to start kallsyms lookup batch: %d\n", ret);
+	} else {
+		run_name_lookup_bench("Dynamic Index", &dyn_hit, &dyn_miss);
+
+		t0 = ktime_get_ns();
+		kallsyms_lookup_batch_end();
+		t1 = ktime_get_ns();
+		dt_end = t1 - t0;
+
+		pr_info("[Dynamic Index] Batch setup: %llu us, teardown: %llu us\n",
+			div_u64(dt_start, 1000), div_u64(dt_end, 1000));
+
+		if (unindexed_hit > dyn_hit) {
+			u64 saved = unindexed_hit - dyn_hit;
+
+			pr_info("[Dynamic Index] Amortization break-even: %llu queries (setup), %llu queries (total)\n",
+				DIV_ROUND_UP_ULL(dt_start, saved),
+				DIV_ROUND_UP_ULL(dt_start + dt_end, saved));
+		}
+	}
+
 	run_address_lookup_bench();
 	run_table_walk_bench();
 

-- 
2.55.0

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

[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.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/kallsyms.c | 97 ++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 61 insertions(+), 36 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 862a6b773ac5..4a04d63e4b7d 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -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++;
 		}

-- 
2.55.0

Re: [PATCH v2 0/3] kallsyms: Accelerate symbol name lookups by ~19x

[David Laight]

On Tue, 22 Sep 2026 01:19:18 -0600
Jim Cromie <jim.cromie@gmail.com> 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).
> 
> 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

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

[David Laight]

On Tue, 22 Sep 2026 01:19:21 -0600
Jim Cromie <jim.cromie@gmail.com> 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.
> 
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
...
> +/*
> + * 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';
> +}

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 
		

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