华为开发者贡献 Linux 内核补丁,将核心内核函数速度提升 715 倍
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[] 仍然按照升序与地址一一对应存储。...
