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

Petr Pavlu
2026-05-05T14:38:00Z

On 5/5/26 2:24 PM, Petr Mladek wrote:
> 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.

I'm not sure if I fully follow the conclusion in this point. My
understanding is that .klp.rela sections still refer to their special
symbols in the symbol table via Elf_Rela::r_info. If the symbol table is
filtered or reordered, these references will end up pointing to
incorrect symbols.

This is also described in Documentation/livepatch/module-elf-format.rst,
section "4.1 A livepatch module's symbol table".

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

I see. So if the module loader sorts the symbol table in a regular
module and a livepatch module exists for that module, the livepatch may
no longer function correctly. This means that the loader cannot even
reorder the symbol table in regular modules.

--
Thanks,
Petr