奇客内核补丁将 kallsyms_lookup_name()查找速度提高 715 倍

奇客资讯 • 2年前扫码分享

我是创始人李岩：很抱歉！给自己产品做个广告，点击进来看看。

Linux 6.2 合并了华为开发者 Zhen Lei 递交的一个补丁，将 kallsyms_lookup_name()的查找速度提高了 715 倍。kallsyms_lookup_name() 用于根据名字查找一个符号的地址，能用于查找内核符号表中的任何符号。Zhen Lei 此前在补丁描述中解释说，目前内核使用的查找方法是将 kallsyms_names 中的符号逐一展开，然后查找，这种算法的时间复杂度是 O(n)。如果像地址一样将名字按升序排序，可以使用二进制搜索。这种算法的时间复杂度是 O(log(n))。从 O(n) 到 O(log(n)) 查找时间可以大幅减少。