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

[PATCH 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[] (~191k 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 ~4.3 us latency penalty per hit and
~3.8 us per miss.

This 3-patch series eliminates both overheads while keeping the symbol
table strictly in sequential address order:

0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
   measure name hits, name misses, sprint_symbol(), and table iteration
   latency, with built-in correctness validation and a sysfs trigger.

1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
   index into kallsyms_names[].  This turns get_symbol_offset() into an
   O(1) table lookup, dropping the ~2,176 marker hops per lookup and
   eliminating the legacy kallsyms_markers[] table.

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.

Context & Lineage:

This series was originally developed and benchmarked on mainline (v7.3-rc3).
To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
kernel with pigz if available").

Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
direct binary streaming path (write_incbin).

Glomming onto Lorenzo's build-time acceleration push extends the speedup
theme into runtime: his series speeds up the compile and link, and this
series speeds up runtime symbol lookups by ~18x.

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

Metric                    Baseline      Patched       Speedup
-----------------------------------------------------------------
Name Search Hit           4,370 ns      247 ns        17.7x
Name Search Miss          3,860 ns      195 ns        19.8x
sprint_symbol               440 ns      441 ns        parity
sprint_symbol_no_offset     315 ns      307 ns        parity
Table Full Walk           14,500 us   14,437 us       parity

Address-to-name resolution (sprint_symbol) and sequential table walks
(/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
hardware prefetching.

Hardware PMU Event Counters (perf stat via sysfs run_test trigger):

$ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
    sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'

Counter                 Baseline          Patched           Delta
------------------------------------------------------------------------
Wall-clock elapsed      1.746 s           0.852 s           -51.2%
CPU cycles              7,320,048,030     3,628,523,081     -50.4%
Instructions            9,943,172,792     5,034,260,318     -49.4%
Branches                2,391,663,821     1,173,258,010     -51.0%
Branch-misses             117,241,513        99,805,938     -14.9%
Cache-misses               84,996,149           731,025     -99.1%

Dropping marker scans and avoiding redundant string expansions cuts
4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
(-99.1%) across the test workload.

Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
kallsyms_markers[].

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Jim Cromie (3):
      kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
      kallsyms: Add 3-byte index into compressed symbols to replace marker scans
      kallsyms: Match compressed tokens on the fly during binary search

 kernel/kallsyms.c          | 138 ++++++++++++++-------------
 kernel/kallsyms_internal.h |   2 +-
 lib/Kconfig.debug          |  10 ++
 lib/Makefile               |   1 +
 lib/test_kallsyms_perf.c   | 228 +++++++++++++++++++++++++++++++++++++++++++++
 scripts/kallsyms.c         |  30 +++---
 6 files changed, 322 insertions(+), 87 deletions(-)
---
base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
change-id: 20260919-ksyms-tune-e22a42d8a31a

Best regards,
-- 
Jim Cromie <jim.cromie@gmail.com>

[PATCH 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 2/3] kallsyms: Add 3-byte index into compressed symbols to replace marker scans

[Jim Cromie]

The compressed symbol table (kallsyms_names) packs ~130k kernel symbol
names, in address order, into variable-length records with format
[<len>][<tokenized-strings-wo-\0>].

This layout optimizes address-to-name mapping, but name-to-address
lookups require a linear scan.  To accelerate lookups, kallsyms_markers
was added to record the offset of every 256th entry, cutting the
worst-case walk from 130k to ~128 hops on average.  However, this
still leaves substantial work: during a 17-step binary search in
kallsyms_lookup_names(), the marker walk repeats at every step
(17 * 128), decoding ~2,176 record length headers per lookup.
Address-to-name resolution (sprint_symbol) pays the same 0..255 hop
penalty on every call.

Introduce kallsyms_names_offsets, a 3-byte-per-symbol direct index into
the compressed kallsyms_names table.  scripts/kallsyms.c emits this
table at build-time while writing kallsyms_names, capturing the exact
byte offset for each symbol.  Using 24 bits covers up to 16 MiB of
compressed symbol names, easily spanning the ~2.3 MiB table while
saving 25% space compared to u32 entries.

With kallsyms_names_offsets:

0. get_symbol_offset() performs an O(1) 3-byte table lookup, eliminating
   the ~2,176 header scans per name search.

1. Drop the legacy kallsyms_markers table, saving ~2 KiB of .rodata.

2. Unroll the shift loop in get_symbol_seq() to match
   get_symbol_offset() as a direct 3-byte big-endian load.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
 kernel/kallsyms.c          | 43 +++++++------------------------------------
 kernel/kallsyms_internal.h |  2 +-
 scripts/kallsyms.c         | 30 ++++++++++++++----------------
 3 files changed, 22 insertions(+), 53 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index b9e573e9a10b..21adc5b74ec5 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -113,40 +113,14 @@ static char kallsyms_get_symbol_type(unsigned int off)
 
 
 /*
- * Find the offset on the compressed stream given and index in the
+ * Find the offset on the compressed table given an index in the
  * kallsyms array.
  */
-static unsigned int get_symbol_offset(unsigned long pos)
+static inline unsigned int get_symbol_offset(unsigned long pos)
 {
-	const u8 *name;
-	int i, len;
+	const u8 *p = &kallsyms_names_offsets[3 * pos];
 
-	/*
-	 * Use the closest marker we have. We have markers every 256 positions,
-	 * so that should be close enough.
-	 */
-	name = &kallsyms_names[kallsyms_markers[pos >> 8]];
-
-	/*
-	 * Sequentially scan all the symbols up to the point we're searching
-	 * for. Every symbol is stored in a [<len>][<len> bytes of data] format,
-	 * 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++) {
-		len = *name;
-
-		/*
-		 * If MSB is 1, it is a "big" symbol, so we need to look into
-		 * the next byte (and skip it, too).
-		 */
-		if ((len & 0x80) != 0)
-			len = ((len & 0x7F) | (name[1] << 7)) + 1;
-
-		name = name + len + 1;
-	}
-
-	return name - kallsyms_names;
+	return (p[0] << 16) | (p[1] << 8) | p[2];
 }
 
 unsigned long kallsyms_sym_address(int idx)
@@ -157,14 +131,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;
-
-	for (i = 0; i < 3; i++)
-		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
+	const u8 *p = &kallsyms_seqs_of_names[3 * index];
 
-	return seq;
+	return (p[0] << 16) | (p[1] << 8) | p[2];
 }
 
 static int kallsyms_lookup_names(const char *name,
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..430abccfab63 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -12,7 +12,7 @@ extern const unsigned int kallsyms_num_syms;
 extern const char kallsyms_token_table[];
 extern const u16 kallsyms_token_index[];
 
-extern const unsigned int kallsyms_markers[];
+extern const u8 kallsyms_names_offsets[];
 extern const u8 kallsyms_seqs_of_names[];
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index d996a43c4078..83a8747269ff 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -44,6 +44,7 @@ struct sym_entry {
 	unsigned long long addr;
 	unsigned int len;
 	unsigned int seq;
+	unsigned int byte_off;
 	unsigned char sym[];
 };
 
@@ -393,7 +394,6 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 {
 	unsigned int i, off;
 	unsigned int best_idx[256];
-	unsigned int *markers, markers_cnt;
 	long bin_start;
 	char buf[KSYM_NAME_LEN];
 
@@ -403,18 +403,12 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	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;
-	markers = xmalloc(sizeof(*markers) * markers_cnt);
-
 	output_label("kallsyms_names");
 	bin_start = bin_pos(out_bin_file);
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		if ((i & 0xFF) == 0)
-			markers[i >> 8] = off;
 		table[i]->seq = i;
+		table[i]->byte_off = off;
 
 		/* There cannot be any symbol of length zero. */
 		if (table[i]->len == 0) {
@@ -454,14 +448,6 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf(".size kallsyms_names, . - kallsyms_names\n");
 	printf("\n");
 
-	output_label("kallsyms_markers");
-	for (i = 0; i < markers_cnt; i++)
-		printf("\t.long\t%u\n", markers[i]);
-	printf(".size kallsyms_markers, . - kallsyms_markers\n");
-	printf("\n");
-
-	free(markers);
-
 	output_label("kallsyms_token_table");
 	bin_start = bin_pos(out_bin_file);
 	off = 0;
@@ -478,6 +464,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	output_label("kallsyms_token_index");
 	for (i = 0; i < 256; i++)
 		printf("\t.short\t%d\n", best_idx[i]);
+	printf(".size kallsyms_token_index, . - kallsyms_token_index\n");
 	printf("\n");
 
 	output_label("kallsyms_offsets");
@@ -502,6 +489,16 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 	printf(".size kallsyms_offsets, . - kallsyms_offsets\n");
 	printf("\n");
 
+	output_label("kallsyms_names_offsets");
+	for (i = 0; i < table_cnt; i++)
+		printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
+			(unsigned char)(table[i]->byte_off >> 16),
+			(unsigned char)(table[i]->byte_off >> 8),
+			(unsigned char)(table[i]->byte_off >> 0),
+		       table[i]->sym);
+	printf(".size kallsyms_names_offsets, . - kallsyms_names_offsets\n");
+	printf("\n");
+
 	sort_symbols_by_name();
 	output_label("kallsyms_seqs_of_names");
 	bin_start = bin_pos(out_bin_file);
@@ -511,6 +508,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name)
 		fputc(table[i]->seq >> 0, out_bin_file);
 	}
 	write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file));
+	printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n");
 	printf("\n");
 }
 

-- 
2.55.0

Re: [PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to replace marker scans

[David Laight]

On Sat, 19 Sep 2026 21:58:56 -0600
Jim Cromie <jim.cromie@gmail.com> wrote:

> From: Jim Cromie <jim.cromie@gmail.com>
> To: Andrew Morton <akpm@linux-foundation.org>
> Cc: Lorenzo Stoakes <ljs@kernel.org>, Kees Cook <kees@kernel.org>,   Masahiro Yamada <masahiroy@kernel.org>, linux-kernel@vger.kernel.org,   linux-kbuild@vger.kernel.org, bpf@vger.kernel.org,   Jim Cromie <jim.cromie@gmail.com>
> Subject: [PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to  replace marker scans
> Date: Sat, 19 Sep 2026 21:58:56 -0600
> 
> The compressed symbol table (kallsyms_names) packs ~130k kernel symbol
> names, in address order, into variable-length records with format
> [<len>][<tokenized-strings-wo-\0>].
> 
> This layout optimizes address-to-name mapping, but name-to-address
> lookups require a linear scan.  To accelerate lookups, kallsyms_markers
> was added to record the offset of every 256th entry, cutting the
> worst-case walk from 130k to ~128 hops on average.  However, this
> still leaves substantial work: during a 17-step binary search in
> kallsyms_lookup_names(), the marker walk repeats at every step
> (17 * 128), decoding ~2,176 record length headers per lookup.
> Address-to-name resolution (sprint_symbol) pays the same 0..255 hop
> penalty on every call.
> 
> Introduce kallsyms_names_offsets, a 3-byte-per-symbol direct index into
> the compressed kallsyms_names table.  scripts/kallsyms.c emits this
> table at build-time while writing kallsyms_names, capturing the exact
> byte offset for each symbol.  Using 24 bits covers up to 16 MiB of
> compressed symbol names, easily spanning the ~2.3 MiB table while
> saving 25% space compared to u32 entries.
> 
> With kallsyms_names_offsets:
> 
> 0. get_symbol_offset() performs an O(1) 3-byte table lookup, eliminating
>    the ~2,176 header scans per name search.
> 
> 1. Drop the legacy kallsyms_markers table, saving ~2 KiB of .rodata.
> 
> 2. Unroll the shift loop in get_symbol_seq() to match
>    get_symbol_offset() as a direct 3-byte big-endian load.

Why big-endian?
Most cpu are little endian, gcc 16 and clang 10 will replace two of
the 8bit loads with a 16bit one.

I'd also comment that the overhead is 3 bytes/symbol - with a note
about the average symbol size (excluding rust).
The +573kB sounds like a lot - but isn't that much compared to the
size of the table.

You should only need half the table.
The only odd index you need to check is the last one, and you'll have
just read the symbol below it.

David

[PATCH 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 21adc5b74ec5..3be2b4e74057 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
@@ -91,7 +90,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;
 }
 
@@ -101,16 +100,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 table given an index in the
@@ -145,7 +174,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;
@@ -154,8 +182,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)
@@ -171,8 +198,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--;
 	}
@@ -183,8 +209,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 0/3] kallsyms: Accelerate symbol name lookups by ~19x

[Jiri Olsa]

On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~191k 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 ~4.3 us latency penalty per hit and
> ~3.8 us per miss.
> 
> This 3-patch series eliminates both overheads while keeping the symbol
> table strictly in sequential address order:
> 
> 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
>    measure name hits, name misses, sprint_symbol(), and table iteration
>    latency, with built-in correctness validation and a sysfs trigger.
> 
> 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
>    index into kallsyms_names[].  This turns get_symbol_offset() into an
>    O(1) table lookup, dropping the ~2,176 marker hops per lookup and
>    eliminating the legacy kallsyms_markers[] table.
> 
> 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.
> 
> Context & Lineage:
> 
> This series was originally developed and benchmarked on mainline (v7.3-rc3).
> To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
> it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
> kernel with pigz if available").
> 
> Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
> align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
> direct binary streaming path (write_incbin).
> 
> Glomming onto Lorenzo's build-time acceleration push extends the speedup
> theme into runtime: his series speeds up the compile and link, and this
> series speeds up runtime symbol lookups by ~18x.
> 
> Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
> 
> Metric                    Baseline      Patched       Speedup
> -----------------------------------------------------------------
> Name Search Hit           4,370 ns      247 ns        17.7x
> Name Search Miss          3,860 ns      195 ns        19.8x
> sprint_symbol               440 ns      441 ns        parity
> sprint_symbol_no_offset     315 ns      307 ns        parity
> Table Full Walk           14,500 us   14,437 us       parity
> 
> Address-to-name resolution (sprint_symbol) and sequential table walks
> (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
> hardware prefetching.
> 
> Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
> 
> $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
>     sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
> 
> Counter                 Baseline          Patched           Delta
> ------------------------------------------------------------------------
> Wall-clock elapsed      1.746 s           0.852 s           -51.2%
> CPU cycles              7,320,048,030     3,628,523,081     -50.4%
> Instructions            9,943,172,792     5,034,260,318     -49.4%
> Branches                2,391,663,821     1,173,258,010     -51.0%
> Branch-misses             117,241,513        99,805,938     -14.9%
> Cache-misses               84,996,149           731,025     -99.1%
> 
> Dropping marker scans and avoiding redundant string expansions cuts
> 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
> (-99.1%) across the test workload.
> 
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].
> 
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>

nice, fyi I checked on tracing_multi benchmark and got bit of
speedup as well

before:

serial_test_tracing_multi_bench_attach: found 64021 functions
serial_test_tracing_multi_bench_attach: attached in   2.884s
serial_test_tracing_multi_bench_attach: detached in   1.149s

    16,515,655,329      cycles:k
    41,935,382,635      instructions:k

after:

serial_test_tracing_multi_bench_attach: found 64021 functions
serial_test_tracing_multi_bench_attach: attached in   2.633s
serial_test_tracing_multi_bench_attach: detached in   1.159s
#558     tracing_multi_bench_attach:OK

    15,880,929,751      cycles:k
    40,444,002,354      instructions:k

we call kallsyms_lookup_name for each attached symbol

jirka


> ---
> Jim Cromie (3):
>       kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
>       kallsyms: Add 3-byte index into compressed symbols to replace marker scans
>       kallsyms: Match compressed tokens on the fly during binary search
> 
>  kernel/kallsyms.c          | 138 ++++++++++++++-------------
>  kernel/kallsyms_internal.h |   2 +-
>  lib/Kconfig.debug          |  10 ++
>  lib/Makefile               |   1 +
>  lib/test_kallsyms_perf.c   | 228 +++++++++++++++++++++++++++++++++++++++++++++
>  scripts/kallsyms.c         |  30 +++---
>  6 files changed, 322 insertions(+), 87 deletions(-)
> ---
> base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
> change-id: 20260919-ksyms-tune-e22a42d8a31a
> 
> Best regards,
> -- 
> Jim Cromie <jim.cromie@gmail.com>
> 
> 

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

[Lorenzo Stoakes (ARM)]

On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> kallsyms_lookup_names() resolves symbol names to addresses using a
> 17-step binary search over kallsyms_names[] (~191k 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 ~4.3 us latency penalty per hit and
> ~3.8 us per miss.
>
> This 3-patch series eliminates both overheads while keeping the symbol
> table strictly in sequential address order:
>
> 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to
>    measure name hits, name misses, sprint_symbol(), and table iteration
>    latency, with built-in correctness validation and a sysfs trigger.
>
> 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct
>    index into kallsyms_names[].  This turns get_symbol_offset() into an
>    O(1) table lookup, dropping the ~2,176 marker hops per lookup and
>    eliminating the legacy kallsyms_markers[] table.
>
> 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.
>
> Context & Lineage:
>
> This series was originally developed and benchmarked on mainline (v7.3-rc3).
> To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3),
> it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the
> kernel with pigz if available").
>
> Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to
> align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's
> direct binary streaming path (write_incbin).
>
> Glomming onto Lorenzo's build-time acceleration push extends the speedup
> theme into runtime: his series speeds up the compile and link, and this
> series speeds up runtime symbol lookups by ~18x.
>
> Live Microbenchmark Results (via test_kallsyms_perf, 100k iters):
>
> Metric                    Baseline      Patched       Speedup
> -----------------------------------------------------------------
> Name Search Hit           4,370 ns      247 ns        17.7x
> Name Search Miss          3,860 ns      195 ns        19.8x
> sprint_symbol               440 ns      441 ns        parity
> sprint_symbol_no_offset     315 ns      307 ns        parity
> Table Full Walk           14,500 us   14,437 us       parity
>
> Address-to-name resolution (sprint_symbol) and sequential table walks
> (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2
> hardware prefetching.
>
> Hardware PMU Event Counters (perf stat via sysfs run_test trigger):
>
> $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \
>     sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test'
>
> Counter                 Baseline          Patched           Delta
> ------------------------------------------------------------------------
> Wall-clock elapsed      1.746 s           0.852 s           -51.2%
> CPU cycles              7,320,048,030     3,628,523,081     -50.4%
> Instructions            9,943,172,792     5,034,260,318     -49.4%
> Branches                2,391,663,821     1,173,258,010     -51.0%
> Branch-misses             117,241,513        99,805,938     -14.9%
> Cache-misses               84,996,149           731,025     -99.1%
>
> Dropping marker scans and avoiding redundant string expansions cuts
> 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses
> (-99.1%) across the test workload.
>
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].
>
> Signed-off-by: Jim Cromie <jim.cromie@gmail.com>

All very nice :)

I'm glad this work seems to be inspiring other work in the same area! I think
there's a load of improvements to be had across the board.

I will try to have a look through through though my workload is crazy
lately and the build stuff is often taking chunks of the weekend so not
sure if I'll have time, but I did at least want to say - awesome :)

> ---
> Jim Cromie (3):
>       kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
>       kallsyms: Add 3-byte index into compressed symbols to replace marker scans
>       kallsyms: Match compressed tokens on the fly during binary search
>
>  kernel/kallsyms.c          | 138 ++++++++++++++-------------
>  kernel/kallsyms_internal.h |   2 +-
>  lib/Kconfig.debug          |  10 ++
>  lib/Makefile               |   1 +
>  lib/test_kallsyms_perf.c   | 228 +++++++++++++++++++++++++++++++++++++++++++++
>  scripts/kallsyms.c         |  30 +++---
>  6 files changed, 322 insertions(+), 87 deletions(-)
> ---
> base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513
> change-id: 20260919-ksyms-tune-e22a42d8a31a
>
> Best regards,
> --
> Jim Cromie <jim.cromie@gmail.com>
>

--
Cheers, Lorenzo

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

[Kees Cook]

On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> kallsyms_markers[].

The speed-up is impressive, but I have to say 500KB is not exactly
trivial. It's not _huge_, but it's not small. Is the rate of symbol
lookups in the kernel high enough to justify this loss of memory?

-- 
Kees Cook

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

[jim.cromie]

On Mon, Sep 21, 2026 at 5:07 PM Kees Cook <kees@kernel.org> wrote:
>
> On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote:
> > Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k
> > symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping
> > kallsyms_markers[].
>
> The speed-up is impressive, but I have to say 500KB is not exactly
> trivial. It's not _huge_, but it's not small. Is the rate of symbol
> lookups in the kernel high enough to justify this loss of memory?
>

IIUC the use is quite lumpy.
so a dynamic allocation could solve all the problems.
1- 32 bit table, since 24 bit fiddling is silly on table thats freed soon.
2- can do David Laights stride-2 thing almost for free
3 - 0 bytes rodata
4 - no conflict with Lorenzo's patchset - no touches to scripts/kallsyms.c

It could be batch-loaded and freed, w fallback to existing slow search.
or left around till OOM
I will play with this.


> --
> Kees Cook