* [PATCH 1/2] kallsyms: Match compressed tokens on the fly during binary search
2026-09-30 13:21 [PATCH next 0/2] kallsyms: optimise symbol search by name David Laight
@ 2026-09-30 13:21 ` David Laight
2026-09-30 13:21 ` [PATCH 2/2] kallsyms: Optimise symbol name search David Laight
1 sibling, 0 replies; 5+ messages in thread
From: David Laight @ 2026-09-30 13:21 UTC (permalink / raw)
To: Andrew Morton, Petr Mladek, Kees Cook, David Laight,
linux-kernel, linux-kbuild, bpf, Jim Cromie, Lorenzo Stoakes
Cc: Zhen Lei, Luis Chamberlain, Andrey Grodzovsky, Steven Rostedt
From: Jim Cromie <jim.cromie@gmail.com>
kallsyms_lookup_names() runs a binary search across ~184k tokenized
(compressed) symbols. For each of the ~17 comparisons in the search, it
currently decompresses the candidate symbol into a temporary buffer on
the stack before calling strcmp().
Comparing tokenized symbols directly in compressed space is
impossible. The BPE token table assigns values by frequency, not
alphabetical order (e.g. token 0x05 might expand to "zebra" while 0x42
expands to "apple"), so comparing raw token values scrambles
lexicographical order. Even sorting the token table alphabetically
wouldn't help; "bpf_" and "bpf_foo_" do not *have* a determinative
sorting order, because the suffixes following those tokens would
matter.
However, full string expansion at every step is equally wasteful: of
the ~17 strcmps in the binary search, only the last needs to check
all N chars in both strings, earlier steps will know +/- outcome at
char 0,1,2..N-1.
However, full string expansion at every step is equally wasteful: of
the ~17 strcmp()s in the binary search, only the final matching step
needs to test all characters. Earlier non-matching steps diverge at
the first differing character (0..N-1), but the baseline expands every
candidate symbol to the stack unconditionally, before comparing.
So we introduce kallsyms_strcmp_symbol() to compare ASCII search_name
against tokenized symbols on the fly. Like strcmp, it tests the
strings char by char, but when it hits a token in the symbol-string,
it continues the char-test against that token-string, which is in
kallsyms_token_table[]. It returns +- on 1st mismatch.
Measured across all ~184k symbols via CONFIG_KALLSYMS_SELFTEST, this
shaves ~530 ns (~14%) off average kallsyms_lookup_name() latency (from
~3810 ns to ~3280 ns on the default 256:1 baseline) and drops the
512-byte namebuf buffer stack-alloc in kallsyms_lookup_names().
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
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.39.5
^ permalink raw reply [flat|nested] 5+ messages in thread* [PATCH 2/2] kallsyms: Optimise symbol name search
2026-09-30 13:21 [PATCH next 0/2] kallsyms: optimise symbol search by name David Laight
2026-09-30 13:21 ` [PATCH 1/2] kallsyms: Match compressed tokens on the fly during binary search David Laight
@ 2026-09-30 13:21 ` David Laight
2026-10-01 0:45 ` bot+bpf-ci
1 sibling, 1 reply; 5+ messages in thread
From: David Laight @ 2026-09-30 13:21 UTC (permalink / raw)
To: Andrew Morton, Petr Mladek, Kees Cook, David Laight,
linux-kernel, linux-kbuild, bpf, Jim Cromie, Lorenzo Stoakes
Cc: Zhen Lei, Luis Chamberlain, Andrey Grodzovsky, Steven Rostedt
Change the alphabetically ordered lookup table (kallsyms_seqs_of_names)
with one that indexed the table of compressed names rather than the
array of symbol values.
This removes all the linear scans during the binary search for the symbol
name.
Once the name has been found a second binary search of the 'markers' array
followed by a linear scan for the symbols address gives the symbol value.
This linear scan is done once for each address returned, whereas the old
code did the scan for each of the ~17 comparisons in the binary search
(and the binary search is done at least two times for a symbol that appears
once).
For normal kernels the index table stays at 24 bits per symbol (now host
ordered), but a 32 bit table is used if necessary (probably only for
allyesconfig builds - needs 25 bits on x86-64).
Seems to work.
Build for BE kernels will correctly flip the byte order in the index table.
Signed-off-by: David Laight <david.laight.linux@gmail.com>
---
kernel/kallsyms.c | 77 ++++++++++++++++++++++++++------------
kernel/kallsyms_internal.h | 4 +-
scripts/Makefile | 1 +
scripts/kallsyms.c | 50 ++++++++++++++-----------
4 files changed, 85 insertions(+), 47 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..2f39fa850dea 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -177,6 +177,36 @@ static unsigned int get_symbol_offset(unsigned long pos)
return name - kallsyms_names;
}
+/*
+ * Find the value of a symbol givem the offset in the compressed stream.
+ */
+static unsigned long get_name_address(unsigned int name_offset)
+{
+ unsigned int low, pos, high;
+
+ low = 0;
+ high = kallsyms_num_syms >> 8;
+
+ while (high - low > 1) {
+ pos = low + (high - low) / 2;
+ if (name_offset >= kallsyms_markers[pos])
+ low = pos;
+ else
+ high = pos;
+ }
+
+ pos = kallsyms_markers[low];
+ for (low <<= 8; pos < name_offset; low++) {
+ unsigned int len = kallsyms_names[pos];
+ if (len & 0x80)
+ len += (kallsyms_names[pos + 1] << 7) - 0x7f;
+ pos += 1 + len;
+ }
+
+ return kallsyms_sym_address(low);
+}
+
+
unsigned long kallsyms_sym_address(int idx)
{
/* non-relocatable 32-bit kernels just embed the value directly */
@@ -185,14 +215,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 unsigned int get_symbol_name(int index)
{
- unsigned int i, seq = 0;
-
- for (i = 0; i < 3; i++)
- seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
-
- return seq;
+ if (kallsyms_off24_of_names)
+ return kallsyms_off24_of_names[index].v;
+ return kallsyms_off32_of_names[index];
}
static int kallsyms_lookup_names(const char *name,
@@ -201,15 +228,14 @@ static int kallsyms_lookup_names(const char *name,
{
int ret;
int low, mid, high;
- unsigned int seq, off;
+ unsigned int off;
low = 0;
high = kallsyms_num_syms - 1;
while (low <= high) {
mid = low + (high - low) / 2;
- seq = get_symbol_seq(mid);
- off = get_symbol_offset(seq);
+ off = get_symbol_name(mid);
ret = kallsyms_strcmp_symbol(off, name);
if (ret > 0)
low = mid + 1;
@@ -220,23 +246,24 @@ static int kallsyms_lookup_names(const char *name,
}
if (low > high)
- return -ESRCH;
+ return -1;
+
+ ret = off;
low = mid;
while (low) {
- seq = get_symbol_seq(low - 1);
- off = get_symbol_offset(seq);
+ off = get_symbol_name(low - 1);
if (kallsyms_strcmp_symbol(off, name) != 0)
break;
low--;
+ ret = off;
}
*start = low;
if (end) {
high = mid;
while (high < kallsyms_num_syms - 1) {
- seq = get_symbol_seq(high + 1);
- off = get_symbol_offset(seq);
+ off = get_symbol_name(high + 1);
if (kallsyms_strcmp_symbol(off, name) != 0)
break;
high++;
@@ -244,7 +271,7 @@ static int kallsyms_lookup_names(const char *name,
*end = high;
}
- return 0;
+ return ret;
}
/* Lookup the address for this symbol. Returns 0 if not found. */
@@ -258,8 +285,8 @@ unsigned long kallsyms_lookup_name(const char *name)
return 0;
ret = kallsyms_lookup_names(name, &i, NULL);
- if (!ret)
- return kallsyms_sym_address(get_symbol_seq(i));
+ if (ret >= 0)
+ return get_name_address(ret);
return module_kallsyms_lookup_name(name);
}
@@ -289,15 +316,17 @@ 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)
{
- int ret;
- unsigned int i, start, end;
+ int name_offset, ret;
+ unsigned int sym_number, last;
- ret = kallsyms_lookup_names(name, &start, &end);
- if (ret)
+ name_offset = kallsyms_lookup_names(name, &sym_number, &last);
+ if (name_offset < 0)
return 0;
- for (i = start; !ret && i <= end; i++) {
- ret = fn(data, kallsyms_sym_address(get_symbol_seq(i)));
+ for (;; name_offset = get_symbol_name(sym_number)) {
+ ret = fn(data, get_name_address(name_offset));
+ if (ret || ++sym_number > last)
+ break;
cond_resched();
}
diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h
index 81a867dbe57d..be503f3f993f 100644
--- a/kernel/kallsyms_internal.h
+++ b/kernel/kallsyms_internal.h
@@ -13,6 +13,8 @@ extern const char kallsyms_token_table[];
extern const u16 kallsyms_token_index[];
extern const unsigned int kallsyms_markers[];
-extern const u8 kallsyms_seqs_of_names[];
+
+extern struct { unsigned int v:24 __attribute__((packed)); } kallsyms_off24_of_names[] __attribute__((weak));
+extern u32 kallsyms_off32_of_names[] __attribute__((weak));
#endif // LINUX_KALLSYMS_INTERNAL_H_
diff --git a/scripts/Makefile b/scripts/Makefile
index 3434a82a119f..b481c2b291bb 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -29,6 +29,7 @@ generate_rust_target-rust := y
rustdoc_test_builder-rust := y
rustdoc_test_gen-rust := y
+HOSTCFLAGS_kallsyms.o += $(if $(CONFIG_CPU_BIG_ENDIAN),-DCONFIG_CPU_BIG_ENDIAN)
HOSTCFLAGS_tracepoint-update.o = -I$(srctree)/tools/include
HOSTCFLAGS_elf-parse.o = -I$(srctree)/tools/include
HOSTCFLAGS_sorttable.o = -I$(srctree)/tools/include
diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 494852ade6d8..74264ead1efe 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -338,9 +338,8 @@ static void sort_symbols_by_name(void)
static void write_src(void)
{
- unsigned int i, k, off;
+ unsigned int i, k, off, table_size;
unsigned int best_idx[256];
- unsigned int *markers, markers_cnt;
char buf[KSYM_NAME_LEN];
printf("\t.section .rodata, \"a\"\n");
@@ -349,17 +348,10 @@ 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;
- 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;
- table[i]->seq = i;
+ table[i]->seq = off;
/* There cannot be any symbol of length zero. */
if (table[i]->len == 0) {
@@ -396,19 +388,18 @@ static void write_src(void)
*/
expand_symbol(table[i]->sym, table[i]->len, buf);
strcpy((char *)table[i]->sym, buf);
- printf("\t/* %s */\n", table[i]->sym);
+ printf("\t/* %d@%d: %s */\n", i, table[i]->seq, table[i]->sym);
}
+ table_size = off;
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]);
+ for (i = 0; i < table_cnt; i += 256)
+ printf("\t.long\t%u\n", table[i]->seq);
printf(".size kallsyms_markers, . - kallsyms_markers\n");
printf("\n");
- free(markers);
-
output_label("kallsyms_token_table");
off = 0;
for (i = 0; i < 256; i++) {
@@ -448,13 +439,28 @@ static void write_src(void)
printf("\n");
sort_symbols_by_name();
- output_label("kallsyms_seqs_of_names");
- for (i = 0; i < table_cnt; i++)
- printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
- (unsigned char)(table[i]->seq >> 16),
- (unsigned char)(table[i]->seq >> 8),
- (unsigned char)(table[i]->seq >> 0),
- table[i]->sym);
+ if (table_size < (1u << 24)) {
+ output_label("kallsyms_off24_of_names");
+ for (i = 0; i < table_cnt; i++) {
+ printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n",
+#ifdef CONFIG_CPU_BIG_ENDIAN
+ (unsigned char)(table[i]->seq >> 16),
+ (unsigned char)(table[i]->seq >> 8),
+ (unsigned char)(table[i]->seq >> 0),
+#else
+ (unsigned char)(table[i]->seq >> 0),
+ (unsigned char)(table[i]->seq >> 8),
+ (unsigned char)(table[i]->seq >> 16),
+#endif
+ table[i]->sym);
+ }
+ } else {
+ output_label("kallsyms_off32_of_names");
+ for (i = 0; i < table_cnt; i++) {
+ printf("\t.long %#04x\t/* %s */\n",
+ table[i]->seq >> 16, table[i]->sym);
+ }
+ }
printf("\n");
}
--
2.39.5
^ permalink raw reply [flat|nested] 5+ messages in thread