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 毫秒。 相關鏈接：https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3ba2c3ff98ea8bfb219288dbacf2a23a902c751b

審核編輯 ：李倩