Linux 6.2 incorporates a patch submitted by Huawei developer Zhen Lei, which increases the search speed of kallsyms_lookup_name() by 715 times. kallsyms_lookup_name() is used to look up the address of a symbol by name, and can be used to look up any symbol in the kernel symbol table. Zhen Lei previously explained in the patch description that the current search method used by the kernel is to expand the symbols in kallsyms_names one by one, and then search, and the time complexity of this algorithm is O(n). If you sort names in ascending order like addresses, you can use binary search. The time complexity of this algorithm is O(log(n)). Going from O(n) to O(log(n)) lookup time can be drastically reduced.
This article is transferred from: https://www.solidot.org/story?sid=73648
This site is only for collection, and the copyright belongs to the original author.