livepatch: Improve the search performance of module_kallsyms_on_each_symbol()
authorZhen Lei <thunder.leizhen@huawei.com>
Mon, 16 Jan 2023 10:10:07 +0000 (11:10 +0100)
committerAlexei Starovoitov <ast@kernel.org>
Fri, 20 Jan 2023 01:07:15 +0000 (17:07 -0800)
commit07cc2c931e8e1083a31f4c51d2244fe264af63bf
tree1abb9ab286d6310e872dcb99448c65bd10a85748
parent92afc5329a5b23d876b215b783d200352d5aaea6
livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

Currently we traverse all symbols of all modules to find the specified
function for the specified module. But in reality, we just need to find
the given module and then traverse all the symbols in it.

Let's add a new parameter 'const char *modname' to function
module_kallsyms_on_each_symbol(), then we can compare the module names
directly in this function and call hook 'fn' after matching. If 'modname'
is NULL, the symbols of all modules are still traversed for compatibility
with other usage cases.

Phase1: mod1-->mod2..(subsequent modules do not need to be compared)
                |
Phase2:          -->f1-->f2-->f3

Assuming that there are m modules, each module has n symbols on average,
then the time complexity is reduced from O(m * n) to O(m) + O(n).

Reviewed-by: Petr Mladek <pmladek@suse.com>
Acked-by: Song Liu <song@kernel.org>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
Signed-off-by: Jiri Olsa <jolsa@kernel.org>
Acked-by: Miroslav Benes <mbenes@suse.cz>
Reviewed-by: Luis Chamberlain <mcgrof@kernel.org>
Link: https://lore.kernel.org/r/20230116101009.23694-2-jolsa@kernel.org
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
include/linux/module.h
kernel/livepatch/core.c
kernel/module/kallsyms.c
kernel/trace/bpf_trace.c
kernel/trace/ftrace.c