Linux 6.2 Speeds Up A Function By 715x - kallsyms_lookup_name()

[NobodyXu]

This kind of thing is a hidden performance cost of using C. Associative arrays are a basic feature of most higher-level languages, by this point. It's somewhat disheartening that there are still linear searches in the kernel, but I'd bet this isn't the last.

While I do agree that C's std lib sucks, using associative array isn't a good idea here.

First, associative arrays like hashmap, btreemap, or other tree based map always have a much higher overhead than plain array.
Sorting the array can archive the same performance as btreemap or other tree based map since they are O(log(n)), the advantage of associative arrays is that you can add/remove new items at runtime quickly, but it doesn't need the functionality here.

Second, it's hard to construct an associative array at compile time. For hashmap, you might be able to workaround this since it can be backed by an array, but tree based map needs to allocate a lot of small nodes and that would need users to allocate an array of small nodes at compile time.
A small sorted array, is easiest to archive here.

[coder]

As far as reason understand this, now you have to sort the symbols one more time, once per name, once per address (that might be kinda free depending on linker tricks).

So n*log2(n) additional cost for sorting, you will need roughly log2(n) lookups before you "break even". And you use more memory.

Depending on the type of sort, it's not necessarily O(n log n) to sort a nearly-ordered list. Another option would be to simply do in-order insertions, as the list grows. However, that wouldn't work too well, if the cost of an insertion is O(n), as is the case for a simple array.

[coder]

While I do agree that C's std lib sucks,

It's not only the std lib (which is irrelevant for kernel development), but also that the language is strongly-typed but lacks good support for type-safe generics (aside from the function overloading macro hack they added in like C11).

using associative array isn't a good idea here.

First, associative arrays like hashmap, btreemap, or other tree based map always have a much higher overhead than plain array.
Sorting the array can archive the same performance as btreemap or other tree based map since they are O(log(n)), the advantage of associative arrays is that you can add/remove new items at runtime quickly, but it doesn't need the functionality here.

But cheap insertions and removals would seem to be important, here.

And, for lookups, hash tables actually scale better than binary searches! So, if your symbol table grows large enough, hash is going to win.

Second, it's hard to construct an associative array at compile time.

You lost me. Why are we doing this at compile-time? I thought the kernel is creating the sorted index at runtime, as modules are loaded & unloaded.

[NobodyXu]

It's not only the std lib (which is irrelevant for kernel development), but also that the language is strongly-typed but lacks good support for type-safe generics (aside from the function overloading macro hack they added in like C11).

I agree.

But cheap insertions and removals would seem to be important, here.

And, for lookups, hash tables actually scale better than binary searches! So, if your symbol table grows large enough, hash is going to win.


You lost me. Why are we doing this at compile-time? I thought the kernel is creating the sorted index at runtime, as modules are loaded & unloaded.

I forgot that symbols can be added/removed by modules, then associative array does seem to be more appropriate here.

Though I still have doubt about hashmap as it wastes a lot of memory to archive the O(1) speed.

[discordian]

Depending on the type of sort, it's not necessarily O(n log n) to sort a nearly-ordered list.[/FONT]

Yeah, if you are unlucky it might be O(n * n), and your source data is always ordered by-address.

Another option would be to simply do in-order insertions, as the list grows. However, that wouldn't work too well, if the cost of an insertion is O(n), as is the case for a simple array.

Which is kinda the point, if you just focus on a single issue (name lookup), while ignoring that this also means you need to process your data every time it changes.

I don't think you will need symbol lookup often during normal use. if you load modules (like attaching an USB device that needs one) it might help for the lookup, but then you need to sort the array again with new symbols *from the added module*.

TBH, I would think its not worth it, and the disadvantages weigh more (while still having little practical effect).

[ryao]

The obvious question, which is not answered in the article, would be: when is this function actually used? Just during boot-up? Or permanently while the kernel is running? When modules are loaded?

A 700x performance gain is great. Yet, if this function is only called e.g. on kernel startup, it doesn't really matter that much.

It is only used by kprobe, eBPF, kgdb, KCSAN and a hack in the mips code that exists for no apparent reason:

https://elixir.bootlin.com/linux/lat...ms_lookup_name

It also is reportedly abused by Android vendors:

https://lwn.net/Articles/813350/

The removal of the symbol export does nothing to discourage them from abusing it given that root kit authors are having a field day publishing work arounds:

https://github.com/4ltern4te/kallsym...up_name_finder

That said, this speedup really does not matter very much. If I had to guess, it is being done to make debugging slightly faster. I might appreciate it being faster at some point, but I am not a normal Linux user.

[Marekk]

The obvious question, which is not answered in the article, would be: when is this function actually used? Just during boot-up? Or permanently while the kernel is running? When modules are loaded?

A 700x performance gain is great. Yet, if this function is only called e.g. on kernel startup, it doesn't really matter that much.

For example for livepatching, tracing, or when stacktrace is generated in kernel log

[Danny3]

This is only useful for kernel debugging. Do you do this?

No, but it that case it should be speeding up kernel development, so still good to have, especially on a LTS kernel.