Linux 6.2 近日合并了一个重要补丁，该补丁能够将一个核心内核函数速度提升 715 倍。
![]()
从合并的注释可知，贡献此补丁的维护者 Zhen Lei 来自华为，他将 kallsyms_lookup_name() 的平均查找性能提高了 715 倍，从而使内核里面旧实现的时间复杂度从 O(n) 升级到 O(log(n))，大幅减少查找时间，同时还保留了 /proc/kallsyms 上旧的实现支持。
kallsyms_lookup_name() 函数用于根据名称查找符号的地址，并可用于查找内核符号表中的任何符号。
![]()
Zhen Lei 曾在较早的补丁中描述了 kallsyms_lookup_name() 的优化思路：
目前，要搜索一个符号，我们需要将'kallsyms_names'中的符号一个一个展开，然后使用展开后的字符串进行比较。这种算法的时间复杂度是 O(n)。
如果我们像地址一样按升序对名称进行排序，则可以使用二分查找。这种算法的时间复杂度是 O(log(n))。
为了不改变“/proc/kallsyms”的实现，表 kallsyms_names[] 仍然按照升序与地址一一对应存储。
添加数组 kallsyms_seqs_of_names[]，以排序后的 names 序号为索引，对应的内容为排序后的地址序号。例如：假设 NameX 在数组 kallsyms_seqs_of_names[] 中的索引为 'i'，kallsyms_seqs_of_names[i] 的内容为'k'，则 NameX 对应的地址为 kallsyms_addresses[k]。kallsyms_names[] 中的偏移量是 get_symbol_offset(k)。
请注意，使用此方法内存使用量将增加 (4 * kallsyms_num_syms) 字节，接下来的两个补丁将减少 (1 * kallsyms_num_syms) 字节并正确处理 CONFIG_LTO_CLANG=y 的情况。
性能测试结果：(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
kallsyms_lookup_name() 的平均查找性能提高了 715 倍。
因此，该补丁带来的唯一缺点是将内存占用量增加 3 * kallsyms_num_syms。
Linux 6.2 的模块代码还包含一个小的启动优化，将启动时间缩短了大约 30 毫秒。
