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

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

[Jim Cromie via B4 Relay]

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. 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 (~580 ns per lookup).

1. Marker scanning: get_symbol_offset() scans sequentially from the
   nearest 256-symbol marker in kallsyms_names[], decoding an average
   of ~128 ULEB128 record headers per probe (~2,176 header decodes,
   consuming ~3,230 ns to ~5,200 ns per lookup).

Together, these bottlenecks impose a substantial latency penalty during
symbol lookup (~3.8 us to ~6.1 us per probe).  During bulk workloads
such as BPF multi-trampoline attach (e.g. tracing across 64,021 kernel
functions in serial_test_tracing_multi_bench_attach), this compounds
into multiple seconds of attach stall time.

David Laight suggested rounding binary search probes down to multiples
of 256, but kallsyms_names[] is ordered by symbol address while the
binary search operates alphabetically over kallsyms_seqs_of_names[].
Address sequence numbers jump pseudo-randomly across address space on
every probe, meaning address markers cannot be pre-rounded during
alphabetical binary search.

Instead, this 3-patch series addresses both bottlenecks directly in
a clean progression:

0. Patch 1 introduces kallsyms_strcmp_symbol() to compare ASCII queries
   against compressed tokens 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 and saves ~530 ns
   per lookup on unmodified marker infrastructure.

1. Patch 2 increases the static marker density from 256:1 down to 16:1
   (1 marker every 16 symbols) via KALLSYMS_MARKER_SHIFT 4 shared
   between scripts/kallsyms.c and kernel/kallsyms_internal.h.  This cuts
   average marker scan distance by 17x (from 127.5 down to 7.5 hops) and
   drops lookup latency from 6,102 ns to 866 ns (a 7.0x speedup) for
   only +42.2 KiB of write-protected .rodata (0.002% of vmlinux).

2. Patch 3 inlines and unrolls get_symbol_seq() 24-bit sequence index
   reconstruction into direct byte shifts, eliminating loop overhead
   on inner binary search probes.

In-Tree Selftest Progression (virtme-ng, kernel/kallsyms_selftest):
- Baseline (256:1 markers):   6,102 ns / lookup
- 16:1 markers (Patch 2):       866 ns / lookup (7.0x speedup, -85.8%)
- Dynamic 1:1 batch table:      728 ns / lookup (only 138 ns delta)
- Break-even vs 256:1 base:   1,194 queries (6,419 us / 5,374 ns)
- Break-even vs 16:1 markers: 46,514 queries (6,419 us / 138 ns)

What's Unchanged:
0. Address-ordered layout of kallsyms_names[] remains identical.
1. Address-to-name resolution (sprint_symbol, sprint_symbol_no_offset)
   and sequential table iteration (kallsyms_on_each_symbol,
   /proc/kallsyms) remain untouched, maintaining full L1/L2 prefetching.
2. Kernel symbol table encapsulation is preserved with 0 new exported
   symbols, 0 new batch APIs, and 0 Kconfig options.

Memory footprint: +42.2 KiB .rodata added to kernel image (0.002% of
vmlinux).  0 bytes dynamic RAM.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v5:
- Dismiss dynamic 1:1 batch table as unnecessary:
  In v2-v4, a dynamic u32 lookup index allocated in transient RAM was
  explored.  While dynamic 1:1 breaks even against baseline 256:1 after
  ~1,200 queries, comparing dynamic 1:1 against static 16:1 markers
  dismisses the dynamic approach entirely:
  * Static 16:1 markers achieve 866 ns, capturing 97.4% of the maximum
    latency savings of a 1:1 table (an 85.8% reduction from baseline).
  * Dynamic 1:1 gains only an incremental 138 ns (the remaining 2.6%),
    while paying ~6,419 us in allocation setup and synchronize_rcu()
    teardown.
  * Amortizing 6,419 us at 138 ns saved requires 46,514 queries just to
    break even against 16:1 markers.  For any workload under 46k
    queries, dynamic allocation is slower overall.
  * Drop kallsyms_lookup_batch_start/end APIs, mutexes, refcounts,
    transient kvmalloc RAM allocations, and RCU synchronization.
- Drop lib/test_kallsyms_perf benchmark module and
  CONFIG_TEST_KALLSYMS_PERF; existing in-tree CONFIG_KALLSYMS_SELFTEST
  already benchmarks standard kallsyms_lookup_name() without adding
  unmaintained test files in lib/.
- In patch 2, increase marker density to 16:1 via
  KALLSYMS_MARKER_SHIFT 4 shared between scripts/kallsyms.c and
  kernel/kallsyms_internal.h, and drop all references to dynamic tables
  from the patch body.
- Link to v4: https://lore.kernel.org/r/20260922-ksyms-tune-v4-0-92acea84b911@gmail.com

Changes in v4:
- In patch 1, ignore early boot invocations in param_set_trigger() when
  system_state < SYSTEM_RUNNING to prevent NULL pointer dereference in
  ktime_get_ns() prior to timekeeping_init() (addresses Sashiko review).
- In patch 1, prevent sysfs TOCTOU divide-by-zero panic: reject
  num_iters == 0 in param setter, snapshot iters locally via READ_ONCE,
  and serialize runs with bench_lock mutex (addresses Sashiko review).
- In patch 1, eliminate multi-second boot stall: add run_on_boot
  parameter (default false) so late_initcall only runs benchmark when
  explicitly requested (addresses Sashiko review).
- In patch 1, chunk lookup loops in 4096-iter batches with
  cond_resched() outside the timing bracket to prevent preemption sleep
  time from inflating reported latency (addresses Sashiko review).
- In patch 3, annotate dyn_kallsyms_offsets declaration with __rcu to
  satisfy sparse type checking and prevent address-space warnings across
  rcu_assign_pointer() and rcu_dereference() (addresses Sashiko review).
- In patch 3, use rcu_replace_pointer() with lockdep_is_held() during
  batch teardown to atomically read and clear the pointer while
  satisfying sparse address-space constraints (addresses Sashiko
  review).
- Link to v3: https://lore.kernel.org/r/20260922-ksyms-tune-v3-0-681a34ea05d9@gmail.com

Changes in v3:
- Reorder series: place on-the-fly token matching ahead of marker
  density optimization, establishing an active proof of incremental
  performance deltas across all steps (addresses David Laight review).
- Add inlined and unrolled get_symbol_seq() 24-bit sequence index
  reconstruction into direct byte shifts (addresses David Laight
  review).
- In test_kallsyms_perf, configure as a built-in test (bool) rather
  than a module (tristate) and drop kallsyms iterator EXPORT_SYMBOL_GPL
  exports to avoid exposing internal kernel symbol data (addresses
  Sashiko review).
- In patch 1, optimize kallsyms_strcmp_symbol() by dropping
  skipped_first tracking and checking len at the bottom of the token
  loop (addresses David Laight review).
- Drop 'default m' from lib/Kconfig.debug.
- Fix soft lockup risks by adding cond_resched() every 16k iterations in
  test_kallsyms_perf loops.
- Replace direct 64-bit integer divisions with div_u64() to fix 32-bit
  builds.
- Guard against divide-by-zero when num_iters=0.
- Replace tcp_v4_rcv with panic in hit_symbols to prevent failures wo
  CONFIG_INET.
- Move David Laight to series-wide Cc on cover letter, dropping trailer
  from patch 3.
- Link to v2: https://lore.kernel.org/r/20260922-ksyms-tune-v2-0-a333ee31eac7@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.
- Link to v1: https://lore.kernel.org/r/20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com

---
Jim Cromie (3):
      kallsyms: Match compressed tokens on the fly during binary search
      kallsyms: Increase marker density to 16:1 to accelerate lookups
      kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()

 kernel/kallsyms.c          | 111 +++++++++++++++++++++++++++------------------
 kernel/kallsyms_internal.h |   5 ++
 scripts/kallsyms.c         |  14 ++++--
 3 files changed, 80 insertions(+), 50 deletions(-)
---
base-commit: 93f51579e7df248780214094418f205253383cc5
change-id: 20260919-ksyms-tune-e22a42d8a31a

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

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

[Jim Cromie via B4 Relay]

From: Jim Cromie <jim.cromie@gmail.com>

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. Cuts unindexed lookup latency by ~530 ns (~14% faster) while leaving
   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>
---
Changes in v3:
- Reorder patch ahead of dynamic batch index in series, establishing an
  active proof of string matching savings on unindexed baseline
  (addresses David Laight review).
- Optimize kallsyms_strcmp_symbol(): drop skipped_first tracking and
  test len at loop bottom (addresses David Laight review).
- Guard first token with while (*tptr) to handle 1-byte type tokens.
- Introduce get_symbol_data() helper in this patch for reuse in later
  subsystems.

Changes in v2:
- Rebase onto mainline v7.3-rc4, removing external dependencies on
  Lorenzo Stoakes' kbuild series.
---
 kernel/kallsyms.c | 94 ++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 59 insertions(+), 35 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index aec2f06858af..d18d78e626db 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -34,6 +34,21 @@
 
 #include "kallsyms_internal.h"
 
+/*
+ * Get the compressed symbol length and data pointer.
+ */
+static inline const u8 *get_symbol_data(unsigned int off, unsigned int *len)
+{
+	const u8 *p = &kallsyms_names[off];
+	unsigned int l = *p++;
+
+	if (unlikely(l & 0x80))
+		l = (l & 0x7F) | (*p++ << 7);
+	*len = l;
+
+	return p;
+}
+
 /*
  * Expand a compressed symbol data into the resulting uncompressed string,
  * if uncompressed string is too long (>= maxlen), it will be truncated,
@@ -42,28 +57,12 @@
 static unsigned int kallsyms_expand_symbol(unsigned int off,
 					   char *result, size_t maxlen)
 {
-	int len, skipped_first = 0;
+	int skipped_first = 0;
 	const char *tptr;
-	const u8 *data;
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
 
-	/* Get the compressed symbol length from the first symbol byte. */
-	data = &kallsyms_names[off];
-	len = *data;
-	data++;
-	off++;
-
-	/* If MSB is 1, it is a "big" symbol, so needs an additional byte. */
-	if ((len & 0x80) != 0) {
-		len = (len & 0x7F) | (*data << 7);
-		data++;
-		off++;
-	}
-
-	/*
-	 * Update the offset to return the offset for the next symbol on
-	 * the compressed stream.
-	 */
-	off += len;
+	off = (data - kallsyms_names) + len;
 
 	/*
 	 * For every byte on the compressed symbol data, copy the table
@@ -101,14 +100,43 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
  */
 static char kallsyms_get_symbol_type(unsigned int off)
 {
-	/*
-	 * Get just the first code, look it up in the token table,
-	 * and return the first char from this token. If MSB of length
-	 * is 1, it is a "big" symbol, so needs an additional byte.
-	 */
-	if (kallsyms_names[off] & 0x80)
-		off++;
-	return kallsyms_token_table[kallsyms_token_index[kallsyms_names[off + 1]]];
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
+
+	return kallsyms_token_table[kallsyms_token_index[*data]];
+}
+
+/*
+ * Compare an uncompressed ASCII string against a compressed symbol table entry.
+ * Returns negative if name < sym, positive if name > sym, 0 if equal.
+ * Exits immediately on the first mismatched character without decompressing
+ * the rest of the symbol name.
+ */
+static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
+{
+	const char *tptr;
+	unsigned int len;
+	const u8 *data = get_symbol_data(off, &len);
+
+	tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
+	while (*tptr) {
+		int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+		if (diff)
+			return diff;
+	}
+
+	while (--len) {
+		tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
+		do {
+			int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+			if (diff)
+				return diff;
+		} while (*tptr);
+	}
+
+	return (unsigned char)*name;
 }
 
 
@@ -174,7 +202,6 @@ static int kallsyms_lookup_names(const char *name,
 	int ret;
 	int low, mid, high;
 	unsigned int seq, off;
-	char namebuf[KSYM_NAME_LEN];
 
 	low = 0;
 	high = kallsyms_num_syms - 1;
@@ -183,8 +210,7 @@ static int kallsyms_lookup_names(const char *name,
 		mid = low + (high - low) / 2;
 		seq = get_symbol_seq(mid);
 		off = get_symbol_offset(seq);
-		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		ret = strcmp(name, namebuf);
+		ret = kallsyms_strcmp_symbol(off, name);
 		if (ret > 0)
 			low = mid + 1;
 		else if (ret < 0)
@@ -200,8 +226,7 @@ static int kallsyms_lookup_names(const char *name,
 	while (low) {
 		seq = get_symbol_seq(low - 1);
 		off = get_symbol_offset(seq);
-		kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		if (strcmp(name, namebuf))
+		if (kallsyms_strcmp_symbol(off, name) != 0)
 			break;
 		low--;
 	}
@@ -212,8 +237,7 @@ static int kallsyms_lookup_names(const char *name,
 		while (high < kallsyms_num_syms - 1) {
 			seq = get_symbol_seq(high + 1);
 			off = get_symbol_offset(seq);
-			kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-			if (strcmp(name, namebuf))
+			if (kallsyms_strcmp_symbol(off, name) != 0)
 				break;
 			high++;
 		}

-- 
2.55.0

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2163 bytes --]

> kallsyms: Match compressed tokens on the fly during binary search
>
> 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. Cuts unindexed lookup latency by ~530 ns (~14% faster) while leaving
>    sequential address ordering and kallsyms_expand_symbol() streaming
>    invariants intact for /proc/kallsyms and table walks.

This isn't a bug, but could the changelog say how the ~530 ns and ~14%
numbers were measured, such as which selftest and roughly how many
symbols? The ~94% figure seems to come from the 16-of-17 binary search
steps estimate mentioned earlier, which is a share of comparisons rather
than character expansions. Could that be reworded to match what it seems
to come from?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/36204745600

[PATCH v5 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups

[Jim Cromie via B4 Relay]

From: Jim Cromie <jim.cromie@gmail.com>

kallsyms_lookup_names() resolves symbol names to addresses using a
binary search over kallsyms_seqs_of_names[].  In baseline, each probe
invokes get_symbol_offset() to find the symbol in kallsyms_names[].
Because markers in kallsyms_markers[] are spaced every 256 symbols in
address order, each probe must sequentially scan and decode ULEB128
lengths across an average of 127.5 symbols from the nearest marker
(~2,176 hops across a 17-step binary search).

During bulk symbol resolution (e.g. BPF multi-kprobe and tracing-multi
attach across tens of thousands of functions), this linear scan penalty
compounds into substantial latency (~4.7 us to ~6.1 us per lookup).

Increase the static marker density from 256:1 down to 16:1 (1 marker
every 1 << 4 symbols):

0. Define KALLSYMS_MARKER_SHIFT as 4 in kernel/kallsyms_internal.h, with
   a matching KALLSYMS_MARKER_MASK of 0x0F.  Guard kernel types so host
   scripts/kallsyms.c can include this header directly as the single
   symbolic source of truth.

1. In scripts/kallsyms.c, emit markers every
   (1 << KALLSYMS_MARKER_SHIFT) symbols into kallsyms_markers[].  For a
   typical kernel with ~184,000 symbols, this increases marker count
   from 719 to 11,501 entries, adding only +42.2 KiB to write-protected
   .rodata (0.002% of vmlinux).

2. In kernel/kallsyms.c:get_symbol_offset(), compute marker offset via
   pos >> KALLSYMS_MARKER_SHIFT and step through
   pos & KALLSYMS_MARKER_MASK.  Because both are compile-time
   constants, GCC emits single bit-shift and AND instructions with zero
   division overhead.

This reduces the maximum sequential scan from 255 down to 15 symbols,
and cuts the average scan from 127.5 down to 7.5 hops (a 17x reduction
in sequential loop hops).  In-tree selftest measurements across all
184,008 symbols show lookup latency dropping from 6,102 ns down to
866 ns (a 7.0x speedup) with zero runtime memory allocation, zero RCU
synchronization, and zero new user-facing APIs or Kconfig options.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v5:
- Replace dynamic 1:1 batch lookup index (kvmalloc, mutexes, RCU) with
  static 16:1 marker density (KALLSYMS_MARKER_SHIFT 4) in .rodata
  (addresses Kees Cook review).
- Eliminate all dynamic RAM allocations, setup/teardown costs, and
  external batch APIs.
---
 kernel/kallsyms.c          |  8 ++++----
 kernel/kallsyms_internal.h |  5 +++++
 scripts/kallsyms.c         | 14 +++++++++-----
 3 files changed, 18 insertions(+), 9 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..91ced7aa797e 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -150,10 +150,10 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	int i, len;
 
 	/*
-	 * Use the closest marker we have. We have markers every 256 positions,
-	 * so that should be close enough.
+	 * Use the closest marker we have. We have markers every
+	 * (1 << KALLSYMS_MARKER_SHIFT) positions, so that should be close enough.
 	 */
-	name = &kallsyms_names[kallsyms_markers[pos >> 8]];
+	name = &kallsyms_names[kallsyms_markers[pos >> KALLSYMS_MARKER_SHIFT]];
 
 	/*
 	 * Sequentially scan all the symbols up to the point we're searching
@@ -161,7 +161,7 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	 * so we just need to add the len to the current pointer for every
 	 * symbol we wish to skip.
 	 */
-	for (i = 0; i < (pos & 0xFF); i++) {
+	for (i = 0; i < (pos & KALLSYMS_MARKER_MASK); i++) {
 		len = *name;
 
 		/*
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..3e6494b7dfc4 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -1,7 +1,11 @@
 /* SPDX-License-Identifier: GPL-2.0-only */
 #ifndef LINUX_KALLSYMS_INTERNAL_H_
 #define LINUX_KALLSYMS_INTERNAL_H_
+#define KALLSYMS_MARKER_SHIFT 4  /* 16:1 sweet spot: +42 KiB .rodata, 17x fewer hops */
+#define KALLSYMS_MARKER_SIZE  (1U << KALLSYMS_MARKER_SHIFT)
+#define KALLSYMS_MARKER_MASK  (KALLSYMS_MARKER_SIZE - 1U)
 
+#ifdef __KERNEL__
 #include <linux/types.h>
 
 extern const int kallsyms_offsets[];
@@ -14,5 +18,6 @@ extern const u16 kallsyms_token_index[];
 
 extern const unsigned int kallsyms_markers[];
 extern const u8 kallsyms_seqs_of_names[];
+#endif /* __KERNEL__ */
 
 #endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 494852ade6d8..be42a9111350 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -29,6 +29,8 @@
 
 #include <xalloc.h>
 
+#include "../kernel/kallsyms_internal.h"
+
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
 
 #define KSYM_NAME_LEN		512
@@ -349,16 +351,18 @@ static void write_src(void)
 	printf("\t.long\t%u\n", table_cnt);
 	printf("\n");
 
-	/* table of offset markers, that give the offset in the compressed stream
-	 * every 256 symbols */
-	markers_cnt = (table_cnt + 255) / 256;
+	/*
+	 * Table of offset markers, giving the offset in the compressed stream
+	 * every (1 << KALLSYMS_MARKER_SHIFT) symbols.
+	 */
+	markers_cnt = (table_cnt + KALLSYMS_MARKER_MASK) >> KALLSYMS_MARKER_SHIFT;
 	markers = xmalloc(sizeof(*markers) * markers_cnt);
 
 	output_label("kallsyms_names");
 	off = 0;
 	for (i = 0; i < table_cnt; i++) {
-		if ((i & 0xFF) == 0)
-			markers[i >> 8] = off;
+		if ((i & KALLSYMS_MARKER_MASK) == 0)
+			markers[i >> KALLSYMS_MARKER_SHIFT] = off;
 		table[i]->seq = i;
 
 		/* There cannot be any symbol of length zero. */

-- 
2.55.0

Re: [PATCH v5 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 4215 bytes --]

> kallsyms: Increase marker density to 16:1 to accelerate lookups
>
> kallsyms_lookup_names() resolves symbol names to addresses using a
> binary search over kallsyms_seqs_of_names[].  In baseline, each probe
> invokes get_symbol_offset() to find the symbol in kallsyms_names[].
> Because markers in kallsyms_markers[] are spaced every 256 symbols in
> address order, each probe must sequentially scan and decode ULEB128
> lengths across an average of 127.5 symbols from the nearest marker
> (~2,176 hops across a 17-step binary search).
>
> During bulk symbol resolution (e.g. BPF multi-kprobe and tracing-multi
> attach across tens of thousands of functions), this linear scan penalty
> compounds into substantial latency (~4.7 us to ~6.1 us per lookup).
>
> Increase the static marker density from 256:1 down to 16:1 (1 marker
> every 1 << 4 symbols):
>
> 0. Define KALLSYMS_MARKER_SHIFT as 4 in kernel/kallsyms_internal.h, with
>    a matching KALLSYMS_MARKER_MASK of 0x0F.  Guard kernel types so host
>    scripts/kallsyms.c can include this header directly as the single
>    symbolic source of truth.
>
> 1. In scripts/kallsyms.c, emit markers every
>    (1 << KALLSYMS_MARKER_SHIFT) symbols into kallsyms_markers[].  For a
>    typical kernel with ~184,000 symbols, this increases marker count
>    from 719 to 11,501 entries, adding only +42.2 KiB to write-protected
>    .rodata (0.002% of vmlinux).
>
> 2. In kernel/kallsyms.c:get_symbol_offset(), compute marker offset via
>    pos >> KALLSYMS_MARKER_SHIFT and step through
>    pos & KALLSYMS_MARKER_MASK.  Because both are compile-time
>    constants, GCC emits single bit-shift and AND instructions with zero
>    division overhead.
>
> This reduces the maximum sequential scan from 255 down to 15 symbols,
> and cuts the average scan from 127.5 down to 7.5 hops (a 17x reduction
> in sequential loop hops).  In-tree selftest measurements across all
> 184,008 symbols show lookup latency dropping from 6,102 ns down to
> 866 ns (a 7.0x speedup) with zero runtime memory allocation, zero RCU
> synchronization, and zero new user-facing APIs or Kconfig options.

This isn't a bug, but could the numbered list be simplified? The items
0-2 restate the diff hunk by hunk, and some of the remarks describe
things the patch doesn't change.

The old code already used 'pos >> 8' and 'pos & 0xFF', so 'zero
division overhead' isn't new to this patch. Similarly, 'zero RCU
synchronization' and 'zero new user-facing APIs' describe things the
patch never touches.

Also, is 0.002% the intended percentage for the extra .rodata? That
would imply a vmlinux of about 2 GiB, but a typical loaded image is
tens of MiB, making the actual percentage closer to 0.1-0.2%.

The useful parts are the lookup-latency motivation and the
memory-versus-speed trade-off. Would dropping the numbered list in
favour of just the rationale make the description clearer?

> diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
> index 81a867dbe57d..3e6494b7dfc4 100644
> --- a/kernel/kallsyms_internal.h
> +++ b/kernel/kallsyms_internal.h
> @@ -1,7 +1,11 @@
>  /* SPDX-License-Identifier: GPL-2.0-only */
>  #ifndef LINUX_KALLSYMS_INTERNAL_H_
>  #define LINUX_KALLSYMS_INTERNAL_H_
> +#define KALLSYMS_MARKER_SHIFT 4  /* 16:1 sweet spot: +42 KiB .rodata, 17x fewer hops */
> +#define KALLSYMS_MARKER_SIZE  (1U << KALLSYMS_MARKER_SHIFT)
> +#define KALLSYMS_MARKER_MASK  (KALLSYMS_MARKER_SIZE - 1U)
>
> +#ifdef __KERNEL__
>  #include <linux/types.h>

This isn't a bug, but would a short comment explaining the trade-off be
enough here, without the specific measurements? The trailing comment
hard-codes benchmark figures from one configuration (about 184k
symbols). The .rodata cost grows with the symbol count, so '+42 KiB'
will be wrong for other configs and will go stale as the kernel grows.

The same measurements are already in the commit message, where they
usually go. Nothing else in this header has comments like this.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/36204745600

[PATCH v5 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()

[Jim Cromie via B4 Relay]

From: Jim Cromie <jim.cromie@gmail.com>

kallsyms_seqs_of_names[] stores 3-byte big-endian sequence indices that
map alphabetical symbol positions to address-ordered symbol records.
Currently, get_symbol_seq() reconstructs each 24-bit integer using a
3-iteration for-loop that shifts and bitwise-ORs each byte sequentially.
During binary search in kallsyms_lookup_names() and duplicate boundary
scans, this loop introduces branch and loop overhead on the hot lookup
path.

Mark get_symbol_seq() as static inline and unroll the 3-byte extraction
into direct byte shifts: (p[0] << 16) | (p[1] << 8) | p[2]. This
eliminates loop induction variable maintenance and allows the compiler
to generate direct loads and constant shifts.

Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v3:
- Added as a standalone micro-optimization patch (addresses David
  Laight review).
---
 kernel/kallsyms.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 91ced7aa797e..52e41879c24b 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -185,14 +185,11 @@ unsigned long kallsyms_sym_address(int idx)
 	return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
 }
 
-static unsigned int get_symbol_seq(int index)
+static inline unsigned int get_symbol_seq(int index)
 {
-	unsigned int i, seq = 0;
+	const u8 *p = &kallsyms_seqs_of_names[3 * index];
 
-	for (i = 0; i < 3; i++)
-		seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
-
-	return seq;
+	return (p[0] << 16) | (p[1] << 8) | p[2];
 }
 
 static int kallsyms_lookup_names(const char *name,

-- 
2.55.0