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

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

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

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

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

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

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

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

性能測(cè)試結(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 的模塊代碼還包含一個(gè)小的啟動(dòng)優(yōu)化，將啟動(dòng)時(shí)間縮短了大約 30 毫秒。 相關(guān)鏈接：https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=3ba2c3ff98ea8bfb219288dbacf2a23a902c751b

審核編輯 ：李倩