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

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)
Before:
min=234, max=10364402, avg=5206926
min=267, max=11168517, avg=5207587
After:
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.