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

Written by Michael Larabel in Linux Kernel on 13 December 2022 at 06:32 PM EST. 27 Comments
As a nice Christmas present, code merged today to the Linux 6.2 kernel speeds up a core kernel function by a factor of 715x.

The modules code update for the Linux 6.2 cycle notes in the merge:
Tux gets for xmas an improvement to the average lookup performance of kallsyms_lookup_name() by 715x thanks to the work by Zhen Lei, which upgraded our old implementation from being O(n) to O(log(n)), while also retaining the old implementation support on /proc/kallsyms.

The only penalty was increasing the memory footprint by 3 * kallsyms_num_syms.

The kallsyms_lookup_name() function is used for looking up the address of a symbol based on its name and can be used for look-ups on any symbol within the kernel's symbol table.

Zhen Lei of Huawei described the kallsyms_lookup_name optimization in an earlier patch posting:
Currently, to search for a symbol, we need to expand the symbols in 'kallsyms_names' one by one, and then use the expanded string for comparison. It's O(n).

If we sort names in ascending order like addresses, we can also use
binary search. It's O(log(n)).

In order not to change the implementation of "/proc/kallsyms", the table kallsyms_names[] is still stored in a one-to-one correspondence with the address in ascending order.

Add array kallsyms_seqs_of_names[], it's indexed by the sequence number of the sorted names, and the corresponding content is the sequence number of the sorted addresses. For example: Assume that the index of NameX in array kallsyms_seqs_of_names[] is 'i', the content of kallsyms_seqs_of_names[i] is 'k', then the corresponding address of NameX is kallsyms_addresses[k]. The offset in kallsyms_names[] is get_symbol_offset(k).

Note that the memory usage will increase by (4 * kallsyms_num_syms) bytes, the next two patches will reduce (1 * kallsyms_num_syms) bytes and properly handle the case CONFIG_LTO_CLANG=y.

Performance test results: (x86)
min=234, max=10364402, avg=5206926
min=267, max=11168517, avg=5207587
min=1016, max=90894, avg=7272
min=1014, max=93470, avg=7293

The average lookup performance of kallsyms_lookup_name() improved 715x.

This is quite the win for kallsyms_lookup_name and Christmas present with Linux 6.2.

The modules code for Linux 6.2 also contains a minor boot optimization, shaving off around 30 ms of the boot time.
Related News
About The Author
Michael Larabel

Michael Larabel is the principal author of and founded the site in 2004 with a focus on enriching the Linux hardware experience. Michael has written more than 20,000 articles covering the state of Linux hardware support, Linux performance, graphics drivers, and other topics. Michael is also the lead developer of the Phoronix Test Suite, Phoromatic, and automated benchmarking software. He can be followed via Twitter, LinkedIn, or contacted via

Popular News This Week