Skip to contentSkip to conversation

kallsyms: optimise symbol search by name

PATCH Superseded David Laight 3 participants 7 messages Sep 30 – Oct 1

Subsystems (2)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover kallsyms: optimise symbol search by name

Patch 1 is from Jim Crome, included so the patch series builds. This is currently in mm-nonmm-unstable

Patch 2 Removes the linear scan from the 'search by name' binary bisect. Data size unchanged for 'sane' kernels.

Seems to work (I'm running it on this system), but I haven't got any performance numbers.

David Laight (1):
kallsyms: Optimise symbol name search

Jim Cromie (1):
kallsyms: Match compressed tokens on the fly during binary search

 kernel/kallsyms.c          | 171 ++++++++++++++++++++++++-------------
 kernel/kallsyms_internal.h |   4 +-
 scripts/Makefile           |   1 +
 scripts/kallsyms.c         |  50 ++++++-----
 4 files changed, 144 insertions(+), 82 deletions(-)
Signature · 1 line
2.39.5
#1 lore raw

PATCH 1/2 kallsyms: Match compressed tokens on the fly during binary search

From: Jim Cromie <[email protected]>

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().

---
 kernel/kallsyms.c | 94 +++++++++++++++++++++++++++++------------------
 1 file changed, 59 insertions(+), 35 deletions(-)
kernel/kallsyms.c +59 -35
index aec2f06858af..d18d78e626db 100644
@@ -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++;
 		}
Signature · 1 line
2.39.5
#2 lore raw

PATCH 2/2 kallsyms: Optimise symbol name search

In reply to David Laight

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.

---
 kernel/kallsyms.c          | 77 ++++++++++++++++++++++++++------------
 kernel/kallsyms_internal.h |  4 +-
 scripts/Makefile           |  1 +
 scripts/kallsyms.c         | 50 ++++++++++++++-----------
 4 files changed, 85 insertions(+), 47 deletions(-)
kernel/kallsyms.c +53 -24
index d18d78e626db..2f39fa850dea 100644
@@ -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();
 	}
 
kernel/kallsyms_internal.h +3 -1
index 81a867dbe57d..be503f3f993f 100644
@@ -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_
scripts/Makefile +1 -0
index 3434a82a119f..b481c2b291bb 100644
@@ -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
scripts/kallsyms.c +28 -22

86 lines not on this page · raw message

Signature · 1 line
2.39.5
#3 lore raw

Re: [PATCH 2/2] kallsyms: Optimise symbol name search

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [High] kallsyms: 32-bit offset truncation in scripts/kallsyms.c causes panic - [Medium] kallsyms…

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] kallsyms: 32-bit offset truncation in scripts/kallsyms.c causes panic
- [Medium] kallsyms: off-by-one in get_name_address binary search bounds doubles scan time --

commit aa83959ffd157437ca56938c0da66225c5fc9aaf
Author: David Laight <[email protected]>

kallsyms: Optimise symbol name search

Change the alphabetically ordered lookup table (kallsyms_seqs_of_names) with one that indexes the table of compressed names rather than the array of symbol values. This removes linear scans during the binary search for the symbol name.

Quoted 4 lines
kernel/kallsyms.c +0 -0
index d18d78e626db2..2f39fa850deae 100644

[ ... ]

Quoted 5 lines
kernel/kallsyms.c +1 -0
@@ -177,6 +177,36 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	return name - kallsyms_names;
 }
 
+/*

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

Quoted 10 lines
kernel/kallsyms.c +10 -0
+ * 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) {

[Severity: Medium]
Since high acts as an exclusive upper bound here, doesn't this omit the final lookup marker from the search space if kallsyms_num_syms is not an exact multiple of 256?

Any kallsyms lookup for symbols in the last partial block (up to 255 symbols) might fall back to the second-to-last marker, unnecessarily doubling the linear scan fallback duration.

Quoted 6 lines
kernel/kallsyms.c +6 -0
+		pos = low + (high - low) / 2;
+		if (name_offset >= kallsyms_markers[pos])
+			low = pos;
+		else
+			high = pos;
+	}

[ ... ]

Quoted 4 lines
scripts/kallsyms.c +0 -0
index 494852ade6d87..74264ead1efe1 100644

[ ... ]

Quoted 21 lines
scripts/kallsyms.c +10 -7
@@ -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),

scripts/kallsyms.c static void write_src(void) · line 461

Quoted 10 lines
scripts/kallsyms.c +10 -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);

[Severity: High]
Does this code inadvertently truncate the 32-bit offset?

When the compressed symbol table exceeds 16MB (such as in allyesconfig builds), this code shifts table[i]->seq right by 16 bits. This unconditionally discards the lower 16 bits of the sequence offset.

Could this corrupt the lookup table kallsyms_off32_of_names and lead to a panic during boot when the kernel attempts to look up wild memory addresses?

Quoted 4 lines
scripts/kallsyms.c +2 -0
+		}
+	}
 	printf("\n");
 }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
#4 lore raw

Re: [PATCH 2/2] kallsyms: Optimise symbol name search

Quoted 41 lines · On Wed, 30 Sep 2026 13:35:25 +0000 [email protected] wrote:

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] kallsyms: 32-bit offset truncation in scripts/kallsyms.c causes panic
- [Medium] kallsyms: off-by-one in get_name_address binary search bounds doubles scan time --

commit aa83959ffd157437ca56938c0da66225c5fc9aaf
Author: David Laight <[email protected]>

kallsyms: Optimise symbol name search

Change the alphabetically ordered lookup table (kallsyms_seqs_of_names) with one that indexes the table of compressed names rather than the array of symbol values. This removes linear scans during the binary search for the symbol name.

Quoted 4 lines
kernel/kallsyms.c +0 -0
index d18d78e626db2..2f39fa850deae 100644

[ ... ]

Quoted 5 lines
kernel/kallsyms.c +1 -0
@@ -177,6 +177,36 @@ static unsigned int get_symbol_offset(unsigned long pos)
 	return name - kallsyms_names;
 }
 
+/*

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

Quoted 10 lines
kernel/kallsyms.c +10 -0
+ * 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) {  

[Severity: Medium]
Since high acts as an exclusive upper bound here, doesn't this omit the final lookup marker from the search space if kallsyms_num_syms is not an exact multiple of 256?

Quoted 3 lines

Any kallsyms lookup for symbols in the last partial block (up to 255 symbols) might fall back to the second-to-last marker, unnecessarily doubling the linear scan fallback duration.

I'll double check.
This matched one of the other scans.
I did check the first and last symbols (by name and number could be found).

Quoted 39 lines
Quoted 7 lines
kernel/kallsyms.c +6 -0
+		pos = low + (high - low) / 2;
+		if (name_offset >= kallsyms_markers[pos])
+			low = pos;
+		else
+			high = pos;
+	}  

[ ... ]

Quoted 4 lines
scripts/kallsyms.c +0 -0
index 494852ade6d87..74264ead1efe1 100644

[ ... ]

Quoted 26 lines
scripts/kallsyms.c +15 -7
@@ -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);
+		}
Quoted 8 lines

scripts/kallsyms.c static void write_src(void) · line 461

Quoted 5 lines
scripts/kallsyms.c +5 -0
+	} 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);  

[Severity: High]
Does this code inadvertently truncate the 32-bit offset?

That is a C&P error :-(

David

Quoted 13 lines

When the compressed symbol table exceeds 16MB (such as in allyesconfig builds), this code shifts table[i]->seq right by 16 bits. This unconditionally discards the lower 16 bits of the sequence offset.

Could this corrupt the lookup table kallsyms_off32_of_names and lead to a panic during boot when the kernel attempts to look up wild memory addresses?

Quoted 4 lines
scripts/kallsyms.c +2 -0
+		}
+	}
 	printf("\n");
 }  
#5 lore raw

Re: [PATCH 2/2] kallsyms: Optimise symbol name search

In reply to David Laight
TL;DR: - kallsyms 24-bit table struct may be padded to 4 bytes on ARM OABI, giving wrong offsets and a possible out-of-bounds read - weak table symbols may not read as NULL on relocatable x86-32, so…
Quoted 1 line

kallsyms: Optimise symbol name search

TL;DR:
- kallsyms 24-bit table struct may be padded to 4 bytes on ARM OABI, giving wrong offsets and a possible out-of-bounds read
- weak table symbols may not read as NULL on relocatable x86-32, so the wrong table may be chosen

kernel/kallsyms_internal.h extern const char kallsyms_token_table[]; · line 17

Quoted 11 lines
kernel/kallsyms_internal.h +2 -1
index 81a867dbe57d..be503f3f993f 100644
@@ -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));

Is this struct guaranteed to be 3 bytes on every architecture?

The packed attribute is on the bitfield member only, not on the struct. That reduces the member alignment, but it does not stop an ABI from padding the struct size. On ARM OABI kernels structures are padded to a multiple of 32 bits. Documentation/driver-api/ioctl.rst says "On ARM OABI user space, structures are padded to multiples of 32-bit", and GCC applies STRUCTURE_SIZE_BOUNDARY unless the record itself is packed.

OABI kernels can still be built. arch/arm/Kconfig offers AEABI as optional for CPU_SA110 || CPU_SA1100, and the assabet, footbridge, rpc, neponset and netwinder defconfigs all have '# CONFIG_AEABI is not set'. For those builds arch/arm/Makefile compiles with -mabi=apcs-gnu.

In that configuration sizeof(kallsyms_off24_of_names[0]) would be 4, but write_src() in scripts/kallsyms.c still writes 3 bytes per entry:

    printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n", ...

get_symbol_name(index) would then read at 4 * index instead of 3 * index for every index > 0:

    if (kallsyms_off24_of_names)
            return kallsyms_off24_of_names[index].v;

That returns garbage offsets, and for the top quarter of the indexes it reads past the end of the table. kallsyms_lookup_names() and kallsyms_on_each_match_symbol() would then compare against arbitrary positions in kallsyms_names, which can be up to 16 MiB past its start, so lookups fail or return wrong addresses, and there is possibly an out-of-bounds read.

The old u8 kallsyms_seqs_of_names[] with manual byte assembly had no layout dependency. Would it be better to put __packed on the struct itself, as struct __una_u32 { u32 x; } __packed; does in include/linux/unaligned/packed_struct.h? Alternatively, a u8 array read with get_unaligned_le24()/get_unaligned_be24() would avoid the problem.

kernel/kallsyms_internal.h extern const char kallsyms_token_table[]; · line 18

Quoted 1 line
kernel/kallsyms_internal.h +1 -0
+extern u32 kallsyms_off32_of_names[] __attribute__((weak));

Can these two weak references be relied on to read back as NULL when the symbol is left undefined?

Commit 951bcae6c5a0 ("kallsyms: Avoid weak references for kallsyms symbols") removed weak references, noting that they need a GOT in position-independent code and are "not usually supported by RIP or PC relative symbol references". Commit c442db3f49f2 ("kbuild: remove PROVIDE() for kallsyms symbols") then added the empty step-0 kallsyms object so that no weak or PROVIDE() fallback is needed.

The previous weak references were always resolved in the final link. Here one of the two symbols is always left unresolved in the final vmlinux, and get_symbol_name() relies on its address being NULL.

That does not seem to hold on every relocatable kernel. On x86-32 with X86_NEED_RELOCS (RELOCATABLE or RANDOMIZE_BASE), the R_386_32 relocation for '$kallsyms_off24_of_names' goes through do_reloc32() in arch/x86/tools/relocs.c. Unlike do_reloc64(), which has:

    if (sym->st_shndx == SHN_UNDEF)
            return 0;

do_reloc32() does not skip undefined symbols, so the relocation is added to relocs32. When the decompressor relocates the kernel by a non-zero delta, the unresolved weak address becomes delta instead of 0.

If the names table needs the 32-bit layout, kallsyms_off24_of_names is the undefined one, so 'if (kallsyms_off24_of_names)' in get_symbol_name() is then true and it reads 3-byte entries from a bogus low address.

Could the generator always emit both labels, with one of them empty, and could the kernel pick the table with a non-weak test, for example by comparing the label addresses or by using a size or flag word?

---
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/36795037147

#6 lore raw

Re: [PATCH 2/2] kallsyms: Optimise symbol name search

Quoted 5 lines · On Thu, 1 Oct 2026 00:45:19 +0000 (UTC) [email protected] wrote:
Quoted 1 line

kallsyms: Optimise symbol name search

TL;DR:
- kallsyms 24-bit table struct may be padded to 4 bytes on ARM OABI, giving wrong offsets and a possible out-of-bounds read

I hate ARM OABI :-)
I think it is the only architecture Linus still supports that aligns structures on 32bit boundaries.

Quoted 2 lines

- weak table symbols may not read as NULL on relocatable x86-32, so the wrong table may be chosen

I'm not entirely happy with that bit of the code.
There is a conditional in every table index.
It is crying out for either a static branch or just compiling the file (or selecting between two object files) once the symbol table size is known. Either removes the need for weak symbols.

Anyone know if there is 'prior art' for a late compilation?

David