[PATCHv3,bpf-next,1/3] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

Commit Message

Jiri Olsa Jan. 16, 2023, 10:10 a.m. UTC

From: Zhen Lei <[e-mail]>

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 <[e-mail]>
Acked-by: Song Liu <[e-mail]>
Signed-off-by: Zhen Lei <[e-mail]>
Signed-off-by: Jiri Olsa <[e-mail]>
---
 include/linux/module.h   |  6 ++++--
 kernel/livepatch/core.c  | 10 +---------
 kernel/module/kallsyms.c | 13 ++++++++++++-
 kernel/trace/bpf_trace.c |  2 +-
 kernel/trace/ftrace.c    |  2 +-
 5 files changed, 19 insertions(+), 14 deletions(-)

Comments

Miroslav Benes Jan. 17, 2023, 2:47 p.m. UTC | #1

On Mon, 16 Jan 2023, Jiri Olsa wrote:

> From: Zhen Lei <[e-mail]>
> 
> 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 <[e-mail]>
> Acked-by: Song Liu <[e-mail]>
> Signed-off-by: Zhen Lei <[e-mail]>
> Signed-off-by: Jiri Olsa <[e-mail]>

Acked-by: Miroslav Benes <[e-mail]>

M

Luis Chamberlain Jan. 17, 2023, 3:25 p.m. UTC | #2

On Tue, Jan 17, 2023 at 03:47:15PM +0100, Miroslav Benes wrote:
> On Mon, 16 Jan 2023, Jiri Olsa wrote:
> 
> > From: Zhen Lei <[e-mail]>
> > 
> > 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 <[e-mail]>
> > Acked-by: Song Liu <[e-mail]>
> > Signed-off-by: Zhen Lei <[e-mail]>
> > Signed-off-by: Jiri Olsa <[e-mail]>
> 
> Acked-by: Miroslav Benes <[e-mail]>

Yes, queued up, thanks!

  Luis

Luis Chamberlain Jan. 17, 2023, 3:26 p.m. UTC | #3

On Tue, Jan 17, 2023 at 07:25:42AM -0800, Luis Chamberlain wrote:
> On Tue, Jan 17, 2023 at 03:47:15PM +0100, Miroslav Benes wrote:
> > On Mon, 16 Jan 2023, Jiri Olsa wrote:
> > 
> > > From: Zhen Lei <[e-mail]>
> > > 
> > > 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 <[e-mail]>
> > > Acked-by: Song Liu <[e-mail]>
> > > Signed-off-by: Zhen Lei <[e-mail]>
> > > Signed-off-by: Jiri Olsa <[e-mail]>
> > 
> > Acked-by: Miroslav Benes <[e-mail]>
> 
> Yes, queued up, thanks!

Sorry that was a reply to a wrong thread, ignore my reply.

  Luis

Luis Chamberlain Jan. 18, 2023, 12:17 a.m. UTC | #4

On Mon, Jan 16, 2023 at 11:10:07AM +0100, Jiri Olsa wrote:
> From: Zhen Lei <[e-mail]>
> 
> 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 <[e-mail]>
> Acked-by: Song Liu <[e-mail]>
> Signed-off-by: Zhen Lei <[e-mail]>
> Signed-off-by: Jiri Olsa <[e-mail]>

Reviewed-by: Luis Chamberlain <[e-mail]>

I'm happy for folks to take this through another tree. I was merging
kallsysm stuff on the modules tree to avoid conflicts with Nick Alcock's
work but after reviewing his v10 series it is quite clear that's no where near
ready now and I don't expect much conflicts even if it was.

  Luis

Patch

diff --git a/include/linux/module.h b/include/linux/module.h
index 8c5909c0076c..514bc81568c5 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -879,11 +879,13 @@  static inline bool module_sig_ok(struct module *module)
 #endif	/* CONFIG_MODULE_SIG */
 
 #if defined(CONFIG_MODULES) && defined(CONFIG_KALLSYMS)
-int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
+int module_kallsyms_on_each_symbol(const char *modname,
+				   int (*fn)(void *, const char *,
 					     struct module *, unsigned long),
 				   void *data);
 #else
-static inline int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
+static inline int module_kallsyms_on_each_symbol(const char *modname,
+						 int (*fn)(void *, const char *,
 						 struct module *, unsigned long),
 						 void *data)
 {
diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c
index 201f0c0482fb..c973ed9e42f8 100644
--- a/kernel/livepatch/core.c
+++ b/kernel/livepatch/core.c
@@ -118,7 +118,6 @@  static struct klp_object *klp_find_object(struct klp_patch *patch,
 }
 
 struct klp_find_arg {
-	const char *objname;
 	const char *name;
 	unsigned long addr;
 	unsigned long count;
@@ -148,15 +147,9 @@  static int klp_find_callback(void *data, const char *name,
 {
 	struct klp_find_arg *args = data;
 
-	if ((mod && !args->objname) || (!mod && args->objname))
-		return 0;
-
 	if (strcmp(args->name, name))
 		return 0;
 
-	if (args->objname && strcmp(args->objname, mod->name))
-		return 0;
-
 	return klp_match_callback(data, addr);
 }
 
@@ -164,7 +157,6 @@  static int klp_find_object_symbol(const char *objname, const char *name,
 				  unsigned long sympos, unsigned long *addr)
 {
 	struct klp_find_arg args = {
-		.objname = objname,
 		.name = name,
 		.addr = 0,
 		.count = 0,
@@ -172,7 +164,7 @@  static int klp_find_object_symbol(const char *objname, const char *name,
 	};
 
 	if (objname)
-		module_kallsyms_on_each_symbol(klp_find_callback, &args);
+		module_kallsyms_on_each_symbol(objname, klp_find_callback, &args);
 	else
 		kallsyms_on_each_match_symbol(klp_match_callback, name, &args);
 
diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c
index 4523f99b0358..ab2376a1be88 100644
--- a/kernel/module/kallsyms.c
+++ b/kernel/module/kallsyms.c
@@ -494,7 +494,8 @@  unsigned long module_kallsyms_lookup_name(const char *name)
 	return ret;
 }
 
-int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
+int module_kallsyms_on_each_symbol(const char *modname,
+				   int (*fn)(void *, const char *,
 					     struct module *, unsigned long),
 				   void *data)
 {
@@ -509,6 +510,9 @@  int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
 		if (mod->state == MODULE_STATE_UNFORMED)
 			continue;
 
+		if (modname && strcmp(modname, mod->name))
+			continue;
+
 		/* Use rcu_dereference_sched() to remain compliant with the sparse tool */
 		preempt_disable();
 		kallsyms = rcu_dereference_sched(mod->kallsyms);
@@ -525,6 +529,13 @@  int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *,
 			if (ret != 0)
 				goto out;
 		}
+
+		/*
+		 * The given module is found, the subsequent modules do not
+		 * need to be compared.
+		 */
+		if (modname)
+			break;
 	}
 out:
 	mutex_unlock(&module_mutex);
diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 23ce498bca97..095f7f8d34a1 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -2735,7 +2735,7 @@  static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u3
 	int err;
 
 	/* We return either err < 0 in case of error, ... */
-	err = module_kallsyms_on_each_symbol(module_callback, &args);
+	err = module_kallsyms_on_each_symbol(NULL, module_callback, &args);
 	if (err) {
 		kprobe_multi_put_modules(args.mods, args.mods_cnt);
 		kfree(args.mods);
diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 442438b93fe9..d249a55d9005 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -8324,7 +8324,7 @@  int ftrace_lookup_symbols(const char **sorted_syms, size_t cnt, unsigned long *a
 	found_all = kallsyms_on_each_symbol(kallsyms_callback, &args);
 	if (found_all)
 		return 0;
-	found_all = module_kallsyms_on_each_symbol(kallsyms_callback, &args);
+	found_all = module_kallsyms_on_each_symbol(NULL, kallsyms_callback, &args);
 	return found_all ? 0 : -ESRCH;
 }