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

Petr Mladek
2026-05-05T12:24:46Z

On Fri 2026-03-27 12:00:05, 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.
>
> 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.
>
> Before:
>
> 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.

What is the exact motivation for the special handling of livepatch modules,
please?

Honestly, I am always a bit lost in the various symbol tables. It is
possile that I have got something wrong.

Anyway, my understanding is that there are two aspects which are important
for livepatches:

1. Livepatches need to preserve special symbols which are used to
relocate symbols which were local in the original code, see
Documentation/livepatch/module-elf-format.rst

IMHO, this is why layout_symtab() computes space for all core
symbols in livepatch modules and copies them in add_kallsyms().

The symtab is normally released when the module is loaded.
But livepatch modules make its own copy of the important
parts, see copy_module_elf().

IMHO, the sorting of function symbols vs other symbols does
not matter here. I believe that the special relocation
symbols are not affected by this.

2. Livepatches _rely on the sorting_ of symbols in the module.
The special relocation symbols might define a symbol position,
see

.klp.sym.objname.symbol_name,sympos

in the documentation. It defines the position of the symbol
when there are more symbols of the same name, see
klp_match_callback() in kernel/livepatch/core.c.

I am afraid that _this patch might break_ this when it moves
function symbols before non-funciton ones. I guess that
the symbols of the same name will not longer be groupped.

Idea: Is the shufling really important for the performance, please?

I would expect that binary search would have a good performance
even without the shuffling. It puts aside half of the symbols in
one cycle.

Note that the binary search in find_kallsyms_symbol() is perfectly
fine. The livepatch code explicitly iterates over all symbols using
module_kallsyms_on_each_symbol(), see klp_find_object_symbol().

Best Regards,
Petr