[PATCH] module/kallsyms: sort function symbols and use binary search

[PATCH] module/kallsyms: sort function symbols and use binary search

[Stanislaw Gruszka]

Module symbol lookup via find_kallsyms_symbol() performs a linear scan
over the entire symtab when resolving an address. The number of symbols
in module symtabs has grown over the years, largely due to additional
metadata in non-standard sections, making this lookup very slow.

Improve this by separating function symbols during module load, placing
them at the beginning of the symtab, sorting them by address, and using
binary search when resolving addresses in module text.

This also should improve times for linear symbol name lookups, as valid
function symbols are now located at the beginning of the symtab.

The cost of sorting is small relative to module load time. In repeated
module load tests [1], depending on .config options, this change
increases load time between 2% and 4%. With cold caches, the difference
is not measurable, as memory access latency dominates.

The sorting theoretically could be done in compile time, but much more
complicated as we would have to simulate kernel addresses resolution
for symbols, and then correct relocation entries. That would be risky
if get out of sync.

The improvement can be observed when listing ftrace filter functions:

root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
74908

real	0m1.315s
user	0m0.000s
sys	0m1.312s

After:

root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
74911

real	0m0.167s
user	0m0.004s
sys	0m0.175s

(there are three more symbols introduced by the patch)

For livepatch modules, the symtab layout is preserved and the existing
linear search is used. For this case, it should be possible to keep
the original ELF symtab instead of copying it 1:1, but that is outside
the scope of this patch.

Link: https://gist.github.com/sgruszka/09f3fb1dad53a97b1aad96e1927ab117 [1]
Signed-off-by: Stanislaw Gruszka <stf_xl@wp.pl>
---
 include/linux/module.h   |   6 ++
 kernel/module/internal.h |   1 +
 kernel/module/kallsyms.c | 169 ++++++++++++++++++++++++++++-----------
 3 files changed, 131 insertions(+), 45 deletions(-)

diff --git a/include/linux/module.h b/include/linux/module.h
index ac254525014c..4da0289fba02 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -379,8 +379,14 @@ struct module_memory {
 struct mod_kallsyms {
 	Elf_Sym *symtab;
 	unsigned int num_symtab;
+	unsigned int num_func_syms;
 	char *strtab;
 	char *typetab;
+
+	unsigned int (*search)(struct mod_kallsyms *kallsyms,
+			       struct module_memory *mod_mem,
+			       unsigned long addr, unsigned long *bestval,
+			       unsigned long *nextval);
 };
 
 #ifdef CONFIG_LIVEPATCH
diff --git a/kernel/module/internal.h b/kernel/module/internal.h
index 618202578b42..6a4d498619b1 100644
--- a/kernel/module/internal.h
+++ b/kernel/module/internal.h
@@ -73,6 +73,7 @@ struct load_info {
 	bool sig_ok;
 #ifdef CONFIG_KALLSYMS
 	unsigned long mod_kallsyms_init_off;
+	unsigned long num_func_syms;
 #endif
 #ifdef CONFIG_MODULE_DECOMPRESS
 #ifdef CONFIG_MODULE_STATS
diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c
index 0fc11e45df9b..9e131baae441 100644
--- a/kernel/module/kallsyms.c
+++ b/kernel/module/kallsyms.c
@@ -10,6 +10,7 @@
 #include <linux/kallsyms.h>
 #include <linux/buildid.h>
 #include <linux/bsearch.h>
+#include <linux/sort.h>
 #include "internal.h"
 
 /* Lookup exported symbol in given range of kernel_symbols */
@@ -103,6 +104,95 @@ static bool is_core_symbol(const Elf_Sym *src, const Elf_Shdr *sechdrs,
 	return true;
 }
 
+static inline bool is_func_symbol(const Elf_Sym *sym)
+{
+	return sym->st_shndx != SHN_UNDEF && sym->st_size != 0 &&
+	       ELF_ST_TYPE(sym->st_info) == STT_FUNC;
+}
+
+static unsigned int bsearch_kallsyms_symbol(struct mod_kallsyms *kallsyms,
+					    struct module_memory *mod_mem,
+					    unsigned long addr,
+					    unsigned long *bestval,
+					    unsigned long *nextval)
+
+{
+	unsigned int mid, low = 1, high = kallsyms->num_func_syms + 1;
+	unsigned int best = 0;
+	unsigned long thisval;
+
+	while (low < high) {
+		mid = low + (high - low) / 2;
+		thisval = kallsyms_symbol_value(&kallsyms->symtab[mid]);
+
+		if (thisval <= addr) {
+			*bestval = thisval;
+			best = mid;
+			low = mid + 1;
+		} else {
+			*nextval = thisval;
+			high = mid;
+		}
+	}
+
+	return best;
+}
+
+static const char *kallsyms_symbol_name(struct mod_kallsyms *kallsyms,
+					unsigned int symnum)
+{
+	return kallsyms->strtab + kallsyms->symtab[symnum].st_name;
+}
+
+static unsigned int search_kallsyms_symbol(struct mod_kallsyms *kallsyms,
+					   struct module_memory *mod_mem,
+					   unsigned long addr,
+					   unsigned long *bestval,
+					   unsigned long *nextval)
+{
+	unsigned int i, best = 0;
+
+	/*
+	 * Scan for closest preceding symbol, and next symbol. (ELF
+	 * starts real symbols at 1).
+	 */
+	for (i = 1; i < kallsyms->num_symtab; i++) {
+		const Elf_Sym *sym = &kallsyms->symtab[i];
+		unsigned long thisval = kallsyms_symbol_value(sym);
+
+		if (sym->st_shndx == SHN_UNDEF)
+			continue;
+
+		/*
+		 * We ignore unnamed symbols: they're uninformative
+		 * and inserted at a whim.
+		 */
+		if (*kallsyms_symbol_name(kallsyms, i) == '\0' ||
+		    is_mapping_symbol(kallsyms_symbol_name(kallsyms, i)))
+			continue;
+
+		if (thisval <= addr && thisval > *bestval) {
+			best = i;
+			*bestval = thisval;
+		}
+		if (thisval > addr && thisval < *nextval)
+			*nextval = thisval;
+	}
+
+	return best;
+}
+
+static int elf_sym_cmp(const void *a, const void *b)
+{
+	const Elf_Sym *sym_a = a;
+	const Elf_Sym *sym_b = b;
+
+	if (sym_a->st_value < sym_b->st_value)
+		return -1;
+
+	return sym_a->st_value > sym_b->st_value;
+}
+
 /*
  * We only allocate and copy the strings needed by the parts of symtab
  * we keep.  This is simple, but has the effect of making multiple
@@ -115,9 +205,10 @@ void layout_symtab(struct module *mod, struct load_info *info)
 	Elf_Shdr *symsect = info->sechdrs + info->index.sym;
 	Elf_Shdr *strsect = info->sechdrs + info->index.str;
 	const Elf_Sym *src;
-	unsigned int i, nsrc, ndst, strtab_size = 0;
+	unsigned int i, nsrc, ndst, nfunc, strtab_size = 0;
 	struct module_memory *mod_mem_data = &mod->mem[MOD_DATA];
 	struct module_memory *mod_mem_init_data = &mod->mem[MOD_INIT_DATA];
+	bool is_lp_mod = is_livepatch_module(mod);
 
 	/* Put symbol section at end of init part of module. */
 	symsect->sh_flags |= SHF_ALLOC;
@@ -129,12 +220,14 @@ void layout_symtab(struct module *mod, struct load_info *info)
 	nsrc = symsect->sh_size / sizeof(*src);
 
 	/* Compute total space required for the core symbols' strtab. */
-	for (ndst = i = 0; i < nsrc; i++) {
-		if (i == 0 || is_livepatch_module(mod) ||
+	for (ndst = nfunc = i = 0; i < nsrc; i++) {
+		if (i == 0 || is_lp_mod ||
 		    is_core_symbol(src + i, info->sechdrs, info->hdr->e_shnum,
 				   info->index.pcpu)) {
 			strtab_size += strlen(&info->strtab[src[i].st_name]) + 1;
 			ndst++;
+			if (!is_lp_mod && is_func_symbol(src + i))
+				nfunc++;
 		}
 	}
 
@@ -156,6 +249,7 @@ void layout_symtab(struct module *mod, struct load_info *info)
 	mod_mem_init_data->size = ALIGN(mod_mem_init_data->size,
 					__alignof__(struct mod_kallsyms));
 	info->mod_kallsyms_init_off = mod_mem_init_data->size;
+	info->num_func_syms = nfunc;
 
 	mod_mem_init_data->size += sizeof(struct mod_kallsyms);
 	info->init_typeoffs = mod_mem_init_data->size;
@@ -169,7 +263,7 @@ void layout_symtab(struct module *mod, struct load_info *info)
  */
 void add_kallsyms(struct module *mod, const struct load_info *info)
 {
-	unsigned int i, ndst;
+	unsigned int i, di, nfunc, ndst;
 	const Elf_Sym *src;
 	Elf_Sym *dst;
 	char *s;
@@ -178,6 +272,7 @@ void add_kallsyms(struct module *mod, const struct load_info *info)
 	void *data_base = mod->mem[MOD_DATA].base;
 	void *init_data_base = mod->mem[MOD_INIT_DATA].base;
 	struct mod_kallsyms *kallsyms;
+	bool is_lp_mod = is_livepatch_module(mod);
 
 	kallsyms = init_data_base + info->mod_kallsyms_init_off;
 
@@ -186,6 +281,7 @@ void add_kallsyms(struct module *mod, const struct load_info *info)
 	/* Make sure we get permanent strtab: don't use info->strtab. */
 	kallsyms->strtab = (void *)info->sechdrs[info->index.str].sh_addr;
 	kallsyms->typetab = init_data_base + info->init_typeoffs;
+	kallsyms->search = search_kallsyms_symbol;
 
 	/*
 	 * Now populate the cut down core kallsyms for after init
@@ -194,19 +290,30 @@ void add_kallsyms(struct module *mod, const struct load_info *info)
 	mod->core_kallsyms.symtab = dst = data_base + info->symoffs;
 	mod->core_kallsyms.strtab = s = data_base + info->stroffs;
 	mod->core_kallsyms.typetab = data_base + info->core_typeoffs;
+	mod->core_kallsyms.search = is_lp_mod ? search_kallsyms_symbol :
+						bsearch_kallsyms_symbol;
+
 	strtab_size = info->core_typeoffs - info->stroffs;
 	src = kallsyms->symtab;
-	for (ndst = i = 0; i < kallsyms->num_symtab; i++) {
+	ndst = info->num_func_syms + 1;
+
+	for (nfunc = i = 0; i < kallsyms->num_symtab; i++) {
 		kallsyms->typetab[i] = elf_type(src + i, info);
-		if (i == 0 || is_livepatch_module(mod) ||
+		if (i == 0 || is_lp_mod ||
 		    is_core_symbol(src + i, info->sechdrs, info->hdr->e_shnum,
 				   info->index.pcpu)) {
 			ssize_t ret;
 
-			mod->core_kallsyms.typetab[ndst] =
-				kallsyms->typetab[i];
-			dst[ndst] = src[i];
-			dst[ndst++].st_name = s - mod->core_kallsyms.strtab;
+			if (i == 0)
+				di = 0;
+			else if (!is_lp_mod && is_func_symbol(src + i))
+				di = 1 + nfunc++;
+			else
+				di = ndst++;
+
+			mod->core_kallsyms.typetab[di] = kallsyms->typetab[i];
+			dst[di] = src[i];
+			dst[di].st_name = s - mod->core_kallsyms.strtab;
 			ret = strscpy(s, &kallsyms->strtab[src[i].st_name],
 				      strtab_size);
 			if (ret < 0)
@@ -216,9 +323,13 @@ void add_kallsyms(struct module *mod, const struct load_info *info)
 		}
 	}
 
+	WARN_ON_ONCE(nfunc != info->num_func_syms);
+	sort(dst + 1, nfunc, sizeof(Elf_Sym), elf_sym_cmp, NULL);
+
 	/* Set up to point into init section. */
 	rcu_assign_pointer(mod->kallsyms, kallsyms);
 	mod->core_kallsyms.num_symtab = ndst;
+	mod->core_kallsyms.num_func_syms = nfunc;
 }
 
 #if IS_ENABLED(CONFIG_STACKTRACE_BUILD_ID)
@@ -241,11 +352,6 @@ void init_build_id(struct module *mod, const struct load_info *info)
 }
 #endif
 
-static const char *kallsyms_symbol_name(struct mod_kallsyms *kallsyms, unsigned int symnum)
-{
-	return kallsyms->strtab + kallsyms->symtab[symnum].st_name;
-}
-
 /*
  * Given a module and address, find the corresponding symbol and return its name
  * while providing its size and offset if needed.
@@ -255,7 +361,7 @@ static const char *find_kallsyms_symbol(struct module *mod,
 					unsigned long *size,
 					unsigned long *offset)
 {
-	unsigned int i, best = 0;
+	unsigned int best;
 	unsigned long nextval, bestval;
 	struct mod_kallsyms *kallsyms = rcu_dereference(mod->kallsyms);
 	struct module_memory *mod_mem;
@@ -267,36 +373,9 @@ static const char *find_kallsyms_symbol(struct module *mod,
 		mod_mem = &mod->mem[MOD_TEXT];
 
 	nextval = (unsigned long)mod_mem->base + mod_mem->size;
+	bestval = kallsyms_symbol_value(&kallsyms->symtab[0]);
 
-	bestval = kallsyms_symbol_value(&kallsyms->symtab[best]);
-
-	/*
-	 * Scan for closest preceding symbol, and next symbol. (ELF
-	 * starts real symbols at 1).
-	 */
-	for (i = 1; i < kallsyms->num_symtab; i++) {
-		const Elf_Sym *sym = &kallsyms->symtab[i];
-		unsigned long thisval = kallsyms_symbol_value(sym);
-
-		if (sym->st_shndx == SHN_UNDEF)
-			continue;
-
-		/*
-		 * We ignore unnamed symbols: they're uninformative
-		 * and inserted at a whim.
-		 */
-		if (*kallsyms_symbol_name(kallsyms, i) == '\0' ||
-		    is_mapping_symbol(kallsyms_symbol_name(kallsyms, i)))
-			continue;
-
-		if (thisval <= addr && thisval > bestval) {
-			best = i;
-			bestval = thisval;
-		}
-		if (thisval > addr && thisval < nextval)
-			nextval = thisval;
-	}
-
+	best = kallsyms->search(kallsyms, mod_mem, addr, &bestval, &nextval);
 	if (!best)
 		return NULL;
 
-- 
2.50.1

Re: [PATCH] module/kallsyms: sort function symbols and use binary search

[Petr Pavlu]

On 3/17/26 12:04 PM, Stanislaw Gruszka wrote:
> Module symbol lookup via find_kallsyms_symbol() performs a linear scan
> over the entire symtab when resolving an address. The number of symbols
> in module symtabs has grown over the years, largely due to additional
> metadata in non-standard sections, making this lookup very slow.
> 
> Improve this by separating function symbols during module load, placing
> them at the beginning of the symtab, sorting them by address, and using
> binary search when resolving addresses in module text.

Doesn't considering only function symbols break the expected behavior
with CONFIG_KALLSYMS_ALL=y. For instance, when using kdb, is it still
able to see all symbols in a module? The module loader should be remain
consistent with the main kallsyms code regarding which symbols can be
looked up.

> 
> This also should improve times for linear symbol name lookups, as valid
> function symbols are now located at the beginning of the symtab.
> 
> The cost of sorting is small relative to module load time. In repeated
> module load tests [1], depending on .config options, this change
> increases load time between 2% and 4%. With cold caches, the difference
> is not measurable, as memory access latency dominates.
> 
> The sorting theoretically could be done in compile time, but much more
> complicated as we would have to simulate kernel addresses resolution
> for symbols, and then correct relocation entries. That would be risky
> if get out of sync.
> 
> The improvement can be observed when listing ftrace filter functions:
> 
> root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
> 74908
> 
> real	0m1.315s
> user	0m0.000s
> sys	0m1.312s
> 
> After:
> 
> root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
> 74911
> 
> real	0m0.167s
> user	0m0.004s
> sys	0m0.175s
> 
> (there are three more symbols introduced by the patch)

This looks as a reasonable improvement.

> 
> For livepatch modules, the symtab layout is preserved and the existing
> linear search is used. For this case, it should be possible to keep
> the original ELF symtab instead of copying it 1:1, but that is outside
> the scope of this patch.

Livepatch modules are already handled specially by the kallsyms module
code so excluding them from this optimization is probably ok.

However, it might be worth revisiting this exception. I believe that
livepatch support requires the original symbol table for relocations to
remain usable. It might make sense to investigate whether updating the
relocation data with the adjusted symbol indexes would be sensible.

-- 
Thanks,
Petr

Re: [PATCH] module/kallsyms: sort function symbols and use binary search

[Stanislaw Gruszka]

Hi,

On Mon, Mar 23, 2026 at 02:06:43PM +0100, Petr Pavlu wrote:
> On 3/17/26 12:04 PM, Stanislaw Gruszka wrote:
> > Module symbol lookup via find_kallsyms_symbol() performs a linear scan
> > over the entire symtab when resolving an address. The number of symbols
> > in module symtabs has grown over the years, largely due to additional
> > metadata in non-standard sections, making this lookup very slow.
> > 
> > Improve this by separating function symbols during module load, placing
> > them at the beginning of the symtab, sorting them by address, and using
> > binary search when resolving addresses in module text.
> 
> Doesn't considering only function symbols break the expected behavior
> with CONFIG_KALLSYMS_ALL=y. For instance, when using kdb, is it still
> able to see all symbols in a module? The module loader should be remain
> consistent with the main kallsyms code regarding which symbols can be
> looked up.

We already have a CONFIG_KALLSYMS_ALL=y inconsistency between kernel and 
module symbol lookup, independent of this patch. find_kallsyms_symbol()
restricts the search to MOD_TEXT (or MOD_INIT_TEXT) address ranges, so
it cannot resolve data or rodata symbols.

This appears to be acceptable in practice, most kallsyms_lookup() users are
interested in function symbols. Users relying on CONFIG_KALLSYMS_ALL=y
seems to use name-based lookups or iterate over the full symtab. Though kdb 
looks like the exception: it can resolve data symbols by address in the kernel,
but not in modules. But, I think, resolving symbols by name is more common for
kdb.

To make the behavior consistent, we could either: extend find_kallsyms_symbol()
to cover data/rodata symbols (for CONFIG_KALLSYSM_ALL), or restrict
kallsyms_lookup() to text symbols and introduce a separate API for data symbols
lookup for users that really need that. I think second option is better, as
some (maybe most) users are not interested in all symbols, even if
CONFIG_KALLSYSM_ALL is set.

However, either would require substantial rework and is outside the scope
of this patch.

Regards
Stanislaw

> > This also should improve times for linear symbol name lookups, as valid
> > function symbols are now located at the beginning of the symtab.
> > 
> > The cost of sorting is small relative to module load time. In repeated
> > module load tests [1], depending on .config options, this change
> > increases load time between 2% and 4%. With cold caches, the difference
> > is not measurable, as memory access latency dominates.
> > 
> > The sorting theoretically could be done in compile time, but much more
> > complicated as we would have to simulate kernel addresses resolution
> > for symbols, and then correct relocation entries. That would be risky
> > if get out of sync.
> > 
> > The improvement can be observed when listing ftrace filter functions:
> > 
> > root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
> > 74908
> > 
> > real	0m1.315s
> > user	0m0.000s
> > sys	0m1.312s
> > 
> > After:
> > 
> > root@nano:~# time cat /sys/kernel/tracing/available_filter_functions | wc -l
> > 74911
> > 
> > real	0m0.167s
> > user	0m0.004s
> > sys	0m0.175s
> > 
> > (there are three more symbols introduced by the patch)
> 
> This looks as a reasonable improvement.
> 
> > 
> > For livepatch modules, the symtab layout is preserved and the existing
> > linear search is used. For this case, it should be possible to keep
> > the original ELF symtab instead of copying it 1:1, but that is outside
> > the scope of this patch.
> 
> Livepatch modules are already handled specially by the kallsyms module
> code so excluding them from this optimization is probably ok.
> 
> However, it might be worth revisiting this exception. I believe that
> livepatch support requires the original symbol table for relocations to
> remain usable. It might make sense to investigate whether updating the
> relocation data with the adjusted symbol indexes would be sensible.
> 
> -- 
> Thanks,
> Petr

Re: [PATCH] module/kallsyms: sort function symbols and use binary search

[Petr Pavlu]

On 3/24/26 1:53 PM, Stanislaw Gruszka wrote:
> Hi,
> 
> On Mon, Mar 23, 2026 at 02:06:43PM +0100, Petr Pavlu wrote:
>> On 3/17/26 12:04 PM, Stanislaw Gruszka wrote:
>>> Module symbol lookup via find_kallsyms_symbol() performs a linear scan
>>> over the entire symtab when resolving an address. The number of symbols
>>> in module symtabs has grown over the years, largely due to additional
>>> metadata in non-standard sections, making this lookup very slow.
>>>
>>> Improve this by separating function symbols during module load, placing
>>> them at the beginning of the symtab, sorting them by address, and using
>>> binary search when resolving addresses in module text.
>>
>> Doesn't considering only function symbols break the expected behavior
>> with CONFIG_KALLSYMS_ALL=y. For instance, when using kdb, is it still
>> able to see all symbols in a module? The module loader should be remain
>> consistent with the main kallsyms code regarding which symbols can be
>> looked up.
> 
> We already have a CONFIG_KALLSYMS_ALL=y inconsistency between kernel and 
> module symbol lookup, independent of this patch. find_kallsyms_symbol()
> restricts the search to MOD_TEXT (or MOD_INIT_TEXT) address ranges, so
> it cannot resolve data or rodata symbols.

My understanding is that find_kallsyms_symbol() can identify all symbols
in a module by their addresses. However, the issue I see with
MOD_TEXT/MOD_INIT_TEXT is that the function may incorrectly calculate
the size of symbols that are not within these ranges, which is a bug
that should be fixed.

A test using kdb confirms that non-text symbols can be found by their
addresses. The following shows the current behavior with 7.0-rc5 when
printing a module parameter in mlx4_en:

[1]kdb> mds __param_arr_num_vfs
0xffffffffc1209f20 0000000100000003   ........
0xffffffffc1209f28 ffffffffc0fbf07c [mlx4_core]num_vfs_argc  
0xffffffffc1209f30 ffffffff8844bba0 param_ops_byte  
0xffffffffc1209f38 ffffffffc0fbf080 [mlx4_core]num_vfs  
0xffffffffc1209f40 000000785f69736d   msi_x...
0xffffffffc1209f48 656c5f6775626564   debug_le
0xffffffffc1209f50 00000000006c6576   vel.....
0xffffffffc1209f58 0000000000000000   ........

.. and the behavior with the proposed patch:

[1]kdb> mds __param_arr_num_vfs
0xffffffffc1077f20 0000000100000003   ........
0xffffffffc1077f28 ffffffffc104707c   |p......
0xffffffffc1077f30 ffffffffb4a4bba0 param_ops_byte  
0xffffffffc1077f38 ffffffffc1047080   .p......
0xffffffffc1077f40 000000785f69736d   msi_x...
0xffffffffc1077f48 656c5f6775626564   debug_le
0xffffffffc1077f50 00000000006c6576   vel.....
0xffffffffc1077f58 0000000000000000   ........

-- 
Thanks,
Petr

Re: [PATCH] module/kallsyms: sort function symbols and use binary search

[Stanislaw Gruszka]

On Tue, Mar 24, 2026 at 05:00:19PM +0100, Petr Pavlu wrote:
> On 3/24/26 1:53 PM, Stanislaw Gruszka wrote:
> > Hi,
> > 
> > On Mon, Mar 23, 2026 at 02:06:43PM +0100, Petr Pavlu wrote:
> >> On 3/17/26 12:04 PM, Stanislaw Gruszka wrote:
> >>> Module symbol lookup via find_kallsyms_symbol() performs a linear scan
> >>> over the entire symtab when resolving an address. The number of symbols
> >>> in module symtabs has grown over the years, largely due to additional
> >>> metadata in non-standard sections, making this lookup very slow.
> >>>
> >>> Improve this by separating function symbols during module load, placing
> >>> them at the beginning of the symtab, sorting them by address, and using
> >>> binary search when resolving addresses in module text.
> >>
> >> Doesn't considering only function symbols break the expected behavior
> >> with CONFIG_KALLSYMS_ALL=y. For instance, when using kdb, is it still
> >> able to see all symbols in a module? The module loader should be remain
> >> consistent with the main kallsyms code regarding which symbols can be
> >> looked up.
> > 
> > We already have a CONFIG_KALLSYMS_ALL=y inconsistency between kernel and 
> > module symbol lookup, independent of this patch. find_kallsyms_symbol()
> > restricts the search to MOD_TEXT (or MOD_INIT_TEXT) address ranges, so
> > it cannot resolve data or rodata symbols.
> 
> My understanding is that find_kallsyms_symbol() can identify all symbols
> in a module by their addresses. However, the issue I see with
> MOD_TEXT/MOD_INIT_TEXT is that the function may incorrectly calculate
> the size of symbols that are not within these ranges, which is a bug
> that should be fixed.

You are right, I misinterpreted the code:

	if (within_module_init(addr, mod))
		mod_mem = &mod->mem[MOD_INIT_TEXT];
	else
		mod_mem = &mod->mem[MOD_TEXT];

	nextval = (unsigned long)mod_mem->base + mod_mem->size;

	bestval = kallsyms_symbol_value(&kallsyms->symtab[best]);

For best = 0, bestval is also 0 as it comes from the ELF null symbol.

> A test using kdb confirms that non-text symbols can be found by their
> addresses. The following shows the current behavior with 7.0-rc5 when
> printing a module parameter in mlx4_en:
> 
> [1]kdb> mds __param_arr_num_vfs
> 0xffffffffc1209f20 0000000100000003   ........
> 0xffffffffc1209f28 ffffffffc0fbf07c [mlx4_core]num_vfs_argc  
> 0xffffffffc1209f30 ffffffff8844bba0 param_ops_byte  
> 0xffffffffc1209f38 ffffffffc0fbf080 [mlx4_core]num_vfs  
> 0xffffffffc1209f40 000000785f69736d   msi_x...
> 0xffffffffc1209f48 656c5f6775626564   debug_le
> 0xffffffffc1209f50 00000000006c6576   vel.....
> 0xffffffffc1209f58 0000000000000000   ........
> 
> .. and the behavior with the proposed patch:
> 
> [1]kdb> mds __param_arr_num_vfs
> 0xffffffffc1077f20 0000000100000003   ........
> 0xffffffffc1077f28 ffffffffc104707c   |p......
> 0xffffffffc1077f30 ffffffffb4a4bba0 param_ops_byte  
> 0xffffffffc1077f38 ffffffffc1047080   .p......
> 0xffffffffc1077f40 000000785f69736d   msi_x...
> 0xffffffffc1077f48 656c5f6775626564   debug_le
> 0xffffffffc1077f50 00000000006c6576   vel.....
> 0xffffffffc1077f58 0000000000000000   ........

Thanks for testing and pointing this out. Patch indeed breaks
the CONFIG_KALLSYMS_ALL case. 

I think, possible fix would be to track the relevant sections in 
__layout_sections() and use defined symbols from those sections,
instead of just function symbols. 

Regards
Stanislaw

Re: [PATCH] module/kallsyms: sort function symbols and use binary search

[Stanislaw Gruszka]

On Wed, Mar 25, 2026 at 09:26:56AM +0100, Stanislaw Gruszka wrote:
> On Tue, Mar 24, 2026 at 05:00:19PM +0100, Petr Pavlu wrote:
> > On 3/24/26 1:53 PM, Stanislaw Gruszka wrote:
> > > Hi,
> > > 
> > > On Mon, Mar 23, 2026 at 02:06:43PM +0100, Petr Pavlu wrote:
> > >> On 3/17/26 12:04 PM, Stanislaw Gruszka wrote:
> > >>> Module symbol lookup via find_kallsyms_symbol() performs a linear scan
> > >>> over the entire symtab when resolving an address. The number of symbols
> > >>> in module symtabs has grown over the years, largely due to additional
> > >>> metadata in non-standard sections, making this lookup very slow.
> > >>>
> > >>> Improve this by separating function symbols during module load, placing
> > >>> them at the beginning of the symtab, sorting them by address, and using
> > >>> binary search when resolving addresses in module text.
> > >>
> > >> Doesn't considering only function symbols break the expected behavior
> > >> with CONFIG_KALLSYMS_ALL=y. For instance, when using kdb, is it still
> > >> able to see all symbols in a module? The module loader should be remain
> > >> consistent with the main kallsyms code regarding which symbols can be
> > >> looked up.
> > > 
> > > We already have a CONFIG_KALLSYMS_ALL=y inconsistency between kernel and 
> > > module symbol lookup, independent of this patch. find_kallsyms_symbol()
> > > restricts the search to MOD_TEXT (or MOD_INIT_TEXT) address ranges, so
> > > it cannot resolve data or rodata symbols.
> > 
> > My understanding is that find_kallsyms_symbol() can identify all symbols
> > in a module by their addresses. However, the issue I see with
> > MOD_TEXT/MOD_INIT_TEXT is that the function may incorrectly calculate
> > the size of symbols that are not within these ranges, which is a bug
> > that should be fixed.
> 
> You are right, I misinterpreted the code:
> 
> 	if (within_module_init(addr, mod))
> 		mod_mem = &mod->mem[MOD_INIT_TEXT];
> 	else
> 		mod_mem = &mod->mem[MOD_TEXT];
> 
> 	nextval = (unsigned long)mod_mem->base + mod_mem->size;
> 
> 	bestval = kallsyms_symbol_value(&kallsyms->symtab[best]);
> 
> For best = 0, bestval is also 0 as it comes from the ELF null symbol.
> 
> > A test using kdb confirms that non-text symbols can be found by their
> > addresses. The following shows the current behavior with 7.0-rc5 when
> > printing a module parameter in mlx4_en:
> > 
> > [1]kdb> mds __param_arr_num_vfs
> > 0xffffffffc1209f20 0000000100000003   ........
> > 0xffffffffc1209f28 ffffffffc0fbf07c [mlx4_core]num_vfs_argc  
> > 0xffffffffc1209f30 ffffffff8844bba0 param_ops_byte  
> > 0xffffffffc1209f38 ffffffffc0fbf080 [mlx4_core]num_vfs  
> > 0xffffffffc1209f40 000000785f69736d   msi_x...
> > 0xffffffffc1209f48 656c5f6775626564   debug_le
> > 0xffffffffc1209f50 00000000006c6576   vel.....
> > 0xffffffffc1209f58 0000000000000000   ........
> > 
> > .. and the behavior with the proposed patch:
> > 
> > [1]kdb> mds __param_arr_num_vfs
> > 0xffffffffc1077f20 0000000100000003   ........
> > 0xffffffffc1077f28 ffffffffc104707c   |p......
> > 0xffffffffc1077f30 ffffffffb4a4bba0 param_ops_byte  
> > 0xffffffffc1077f38 ffffffffc1047080   .p......
> > 0xffffffffc1077f40 000000785f69736d   msi_x...
> > 0xffffffffc1077f48 656c5f6775626564   debug_le
> > 0xffffffffc1077f50 00000000006c6576   vel.....
> > 0xffffffffc1077f58 0000000000000000   ........
> 
> Thanks for testing and pointing this out. Patch indeed breaks
> the CONFIG_KALLSYMS_ALL case. 
> 
> I think, possible fix would be to track the relevant sections in 
> __layout_sections() and use defined symbols from those sections,
> instead of just function symbols. 

I considered sorting data symbols as well, but this is nontrivial, 
it is difficult to reliably distinguish real data sections from metadata
sections containing symbols we do not want to include.

An alternative approach is to check the module memory type and fall back to
a linear search for ranges other than MOD_TEXT. This approach would also
fix the incorrect nextval/size problem.

Regards
Stanislaw