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:

quoted

On 5/5/26 2:24 PM, Petr Mladek wrote:

quoted

On Fri 2026-03-27 12:00:05, Stanislaw Gruszka wrote:

quoted

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