Linux 6.2 recently incorporated a critical patch that speeds up a core kernel function by a factor of 715.

As can be seen from the merged comments, the maintainer Zhen Lei who contributed this patch is from Huawei. He improved the average lookup performance of kallsyms_lookup_name() by 715 times, and upgraded the old implementation in the kernel from O(n) to O(log(n )), while also retaining support for the old implementation on /proc/kallsyms.

Zhen Lei was in an earlier patchDescribed The optimization idea of ​​kallsyms_lookup_name:

Currently, to search for a symbol, we need to expand the symbols in ‘kallsyms_names’ one by one, and then use the expanded strings for comparison. is O(n).

We can also use binary search if we sort names in ascending order like addresses. It is O(log(n)).

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

Add array kallsyms_seqs_of_names[], with the sorted name serial number as the index, and the corresponding content is the sorted address serial number. Example: Suppose NameX is in the array kallsyms_seqs_of_names[]index ‘i’ in kallsyms_seqs_of_names[i]The content is ‘k’, then the address corresponding to NameX is kallsyms_addresses[k]. kallsyms_names[] The offset in is get_symbol_offset(k).

Note that the memory usage will increase by (4 * kallsyms_num_syms) bytes, the next two patches will reduce it by (1 * kallsyms_num_syms) bytes and correctly handle the case of 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() was improved by a factor of 715.

The only downside brought by this patch is to increase the memory footprint by 3 * kallsyms_num_syms.

The kallsyms_lookup_name() function is used to look up the address of a symbol by name and can be used to look up any symbol in the kernel symbol table.

The module code for Linux 6.2 also includes a small startup optimization that reduces startup time by about 30 milliseconds.