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

On 5/6/26 10:58 AM, Petr Mladek wrote:
> On Tue 2026-05-05 16:37:56, Petr Pavlu wrote:
>> 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.
> 
> My understanding is that the relocations point to symbols which
> are found via the name of the entry. Let's take an example
> from Documentation/livepatch/module-elf-format.rst:
> 
>      73: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT OS [0xff20] .klp.sym.vmlinux.snprintf,0
> 
> This symbol points to snprintf() function in vmlinux object.
> The address of this function is found via kallsyms, see
> klp_find_object_symbol().
> 
> IMHO, it does not matter if we shuffle this entry in the livepatch
> module because the real address is found via kallsyms().
> 
> Even the ordering of the entries in vmlinux is not important in
> _this particular case_ because the "sympos" is zero "0" in this case.
> It means that "snprintf" symbol name is unique in vmlinux.
> 
> The ordering of the symbols in "vmlinux" becomes important
> if the livepatch needs to access a symbol and there are more
> symbols of the same name. This is what I tried to describe
> below.
> 
> I hope that it makes some sense. As I said, I am not familiar
> with the elf format...

Ah, I misunderstood your original point. I agree that reshuffling the
symbol table in a livepatch module will not cause any issues with
binding .klp.sym.<objname>.<symname>,<sympos> symbol references to their
actual definitions in <objname>.

The problem still exists with the .klp.rela sections. They are regular
RELA sections in the sense that each ELF_R_SYM(Elf_Rela::r_info) value
is an index identifying a symbol in the symbol table. If the module
loader reshuffles or filters the original symbol table in any way, the
indexes in Elf_Rela::r_info would need to be adjusted accordingly.

-- 
Thanks,
Petr