Huawei increases average search performance by 715 times with Linux 6.2

In the Linux 6.2 code release, Huawei contributed code from Zheng Lei, which increases the speed of core kernel features by 715 times. The kallsyms_lookup_name () function is used to query the address of a symbol according to its name and can be used to query any symbol in the kernel symbol table.

Huawei has been one of the top contributors to the Linux kernel community and the company is continuously adding new code to this open-source operating system.

Below you can check the complete Huawei code contribution that improved the lookup performance for Linux 6.2.

“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. This is O(n).

We can also use binary search if we sort names in ascending order like addresses. And that’s O(log(n)).

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

Add the array kallsyms_seqs_of_names[], which takes the serial number of the sorted name as the index, and the corresponding content is the serial number of the sorted address.

For example, suppose the index of NameX in the array kallsyms_seqs_of_names[] is ‘i’, and 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 x kallsyms_num_syms) bytes, the next two patches will reduce it by (1 x 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() improved 715x.

(source)