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

[Petr Mladek <pmladek@suse.com>]

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

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

Yeah, reordering symbols in regular module might break livepatching.
Namely it might break finding the right symbol when there are
more symbols of the same name.

Best Regards,
Petr