Linux 6.2 近日合并了一個重要補(bǔ)丁，該補(bǔ)丁能夠?qū)⒁粋€核心內(nèi)核函數(shù)速度提升 715 倍。

從合并的注釋可知，貢獻(xiàn)此補(bǔ)丁的維護(hù)者 Zhen Lei 來自華為，他將 kallsyms_lookup_name () 的平均查找性能提高了 715 倍，從而使內(nèi)核里面舊實(shí)現(xiàn)的時間復(fù)雜度從 O (n) 升級到 O (log (n))，大幅減少查找時間，同時還保留了 /proc/kallsyms 上舊的實(shí)現(xiàn)支持。 kallsyms_lookup_name () 函數(shù)用于根據(jù)名稱查找符號的地址，并可用于查找內(nèi)核符號表中的任何符號。

Zhen Lei 曾在較早的補(bǔ)丁中描述了kallsyms_lookup_name () 的優(yōu)化思路：

目前，要搜索一個符號，我們需要將 'kallsyms_names' 中的符號一個一個展開，然后使用展開后的字符串進(jìn)行比較。這種算法的時間復(fù)雜度是 O (n)。

如果我們像地址一樣按升序?qū)γQ進(jìn)行排序，則可以使用二分查找。這種算法的時間復(fù)雜度是 O (log (n))。

為了不改變 “/proc/kallsyms” 的實(shí)現(xiàn)，表 kallsyms_names [] 仍然按照升序與地址一一對應(yīng)存儲。

添加數(shù)組 kallsyms_seqs_of_names []，以排序后的 names 序號為索引，對應(yīng)的內(nèi)容為排序后的地址序號。例如：假設(shè) NameX 在數(shù)組 kallsyms_seqs_of_names [] 中的索引為 'i'，kallsyms_seqs_of_names [i] 的內(nèi)容為 'k'，則 NameX 對應(yīng)的地址為 kallsyms_addresses [k]。kallsyms_names [] 中的偏移量是 get_symbol_offset (k)。

請注意，使用此方法內(nèi)存使用量將增加 (4 * kallsyms_num_syms) 字節(jié)，接下來的兩個補(bǔ)丁將減少 (1 * kallsyms_num_syms) 字節(jié)并正確處理 CONFIG_LTO_CLANG=y 的情況。

性能測試結(jié)果：(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 倍。

因此，該補(bǔ)丁帶來的唯一缺點(diǎn)是將內(nèi)存占用量增加 3 * kallsyms_num_syms。 Linux 6.2 的模塊代碼還包含一個小的啟動優(yōu)化，將啟動時間縮短了大約 30 毫秒。 相關(guān)鏈接：https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3ba2c3ff98ea8bfb219288dbacf2a23a902c751b

審核編輯 ：李倩