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

From: Stanislaw Gruszka

Date: Tue Nov 17 2026 - 07:12:16 EST


Hi

On Tue, May 05, 2026 at 02:24:41PM +0200, Petr Mladek wrote:
> 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.

Thanks for pointing this out. It took me quite a while to understand
the issue, but I finally got it.

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

One reason I wanted to shuffle the symbols was to also speed up
name-based lookups, assuming that most lookups are for function
symbols. Moving them to the beginning of the table reduces the
number of entries that need to be scanned in the common case.

In my benchmarks, this reduced the average time spent in
__find_kallsyms_symbol_value() from 16 us to 6 us.

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

I'm now going with a separate sorted index table, leaving the original
symtab untouched.

I think the name lookup optimization could be revisited later by
introducing a new function that uses the index table to search only
text symbols, where appropriate.

Regards
Stanislaw