[PATCHv2 bpf-next 0/3] kallsyms: Optimize the search for module symbols by livepatch and bpf

[PATCHv2 bpf-next 0/3] kallsyms: Optimize the search for module symbols by livepatch and bpf

[Jiri Olsa]

hi,
sending new version of [1] patchset posted originally by Zhen Lei.
It contains 2 changes that improove search performance for livepatch
and bpf.

v2 changes:
  - reworked the bpf change and meassured the performance
  - adding new selftest to benchmark kprobe multi module attachment
  - skipping patch 3 as requested by Zhen Lei
  - added Reviewed-by for patch 1 [Petr Mladek]

thanks,
jirka


[1] https://lore.kernel.org/bpf/20221230112729.351-1-thunder.leizhen@huawei.com/
---
Jiri Olsa (2):
      selftests/bpf: Add serial_test_kprobe_multi_bench_attach_kernel/module tests
      bpf: Change modules resolving for kprobe multi link

Zhen Lei (1):
      livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

 include/linux/module.h                                     |  6 ++++--
 kernel/livepatch/core.c                                    | 10 +---------
 kernel/module/kallsyms.c                                   | 13 ++++++++++++-
 kernel/trace/bpf_trace.c                                   | 95 ++++++++++++++++++++++++++++++++++++++++++++++++---------------------------------------------
 kernel/trace/ftrace.c                                      |  2 +-
 tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c | 21 ++++++++++++++++-----
 6 files changed, 83 insertions(+), 64 deletions(-)

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

[Jiri Olsa]

From: Zhen Lei <thunder.leizhen@huawei.com>

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>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
 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(-)

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;
 }
 
-- 
2.39.0

[PATCHv2 bpf-next 2/3] selftests/bpf: Add serial_test_kprobe_multi_bench_attach_kernel/module tests

[Jiri Olsa]

Add bench test for module portion of the symbols as well.

  # ./test_progs -v -t kprobe_multi_bench_attach_module
  bpf_testmod.ko is already unloaded.
  Loading bpf_testmod.ko...
  Successfully loaded bpf_testmod.ko.
  test_kprobe_multi_bench_attach:PASS:get_syms 0 nsec
  test_kprobe_multi_bench_attach:PASS:kprobe_multi_empty__open_and_load 0 nsec
  test_kprobe_multi_bench_attach:PASS:bpf_program__attach_kprobe_multi_opts 0 nsec
  test_kprobe_multi_bench_attach: found 26620 functions
  test_kprobe_multi_bench_attach: attached in   0.182s
  test_kprobe_multi_bench_attach: detached in   0.082s
  #96      kprobe_multi_bench_attach_module:OK
  Summary: 1/0 PASSED, 0 SKIPPED, 0 FAILED
  Successfully unloaded bpf_testmod.ko.

It's useful for testing kprobe multi link modules resolving.

Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
 .../bpf/prog_tests/kprobe_multi_test.c        | 21 ++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
index c6f37e825f11..017a6996f3fa 100644
--- a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
+++ b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
@@ -322,7 +322,7 @@ static bool symbol_equal(long key1, long key2, void *ctx __maybe_unused)
 	return strcmp((const char *) key1, (const char *) key2) == 0;
 }
 
-static int get_syms(char ***symsp, size_t *cntp)
+static int get_syms(char ***symsp, size_t *cntp, bool kernel)
 {
 	size_t cap = 0, cnt = 0, i;
 	char *name = NULL, **syms = NULL;
@@ -349,8 +349,9 @@ static int get_syms(char ***symsp, size_t *cntp)
 	}
 
 	while (fgets(buf, sizeof(buf), f)) {
-		/* skip modules */
-		if (strchr(buf, '['))
+		if (kernel && strchr(buf, '['))
+			continue;
+		if (!kernel && !strchr(buf, '['))
 			continue;
 
 		free(name);
@@ -404,7 +405,7 @@ static int get_syms(char ***symsp, size_t *cntp)
 	return err;
 }
 
-void serial_test_kprobe_multi_bench_attach(void)
+static void test_kprobe_multi_bench_attach(bool kernel)
 {
 	LIBBPF_OPTS(bpf_kprobe_multi_opts, opts);
 	struct kprobe_multi_empty *skel = NULL;
@@ -415,7 +416,7 @@ void serial_test_kprobe_multi_bench_attach(void)
 	char **syms = NULL;
 	size_t cnt = 0, i;
 
-	if (!ASSERT_OK(get_syms(&syms, &cnt), "get_syms"))
+	if (!ASSERT_OK(get_syms(&syms, &cnt, kernel), "get_syms"))
 		return;
 
 	skel = kprobe_multi_empty__open_and_load();
@@ -453,6 +454,16 @@ void serial_test_kprobe_multi_bench_attach(void)
 	}
 }
 
+void serial_test_kprobe_multi_bench_attach_kernel(void)
+{
+	test_kprobe_multi_bench_attach(true);
+}
+
+void serial_test_kprobe_multi_bench_attach_module(void)
+{
+	test_kprobe_multi_bench_attach(false);
+}
+
 void test_kprobe_multi_test(void)
 {
 	if (!ASSERT_OK(load_kallsyms(), "load_kallsyms"))
-- 
2.39.0

[PATCHv2 bpf-next 3/3] bpf: Change modules resolving for kprobe multi link

[Jiri Olsa]

We currently use module_kallsyms_on_each_symbol that iterates all
modules/symbols and we try to lookup each such address in user
provided symbols/addresses to get list of used modules.

This fix instead only iterates provided kprobe addresses and calls
__module_address on each to get list of used modules. This turned
out to be simpler and also bit faster.

On my setup with workload being (executed 10 times):

   # test_progs -t kprobe_multi_bench_attach_module

Current code:

 Performance counter stats for './test.sh' (5 runs):

    76,081,161,596      cycles:k                   ( +-  0.47% )

           18.3867 +- 0.0992 seconds time elapsed  ( +-  0.54% )

With the fix:

 Performance counter stats for './test.sh' (5 runs):

    74,079,889,063      cycles:k                   ( +-  0.04% )

           17.8514 +- 0.0218 seconds time elapsed  ( +-  0.12% )

Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
 kernel/trace/bpf_trace.c | 95 +++++++++++++++++++++-------------------
 1 file changed, 49 insertions(+), 46 deletions(-)

diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 095f7f8d34a1..90c5d5026831 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -2682,69 +2682,79 @@ static void symbols_swap_r(void *a, void *b, int size, const void *priv)
 	}
 }
 
-struct module_addr_args {
-	unsigned long *addrs;
-	u32 addrs_cnt;
+struct modules_array {
 	struct module **mods;
 	int mods_cnt;
 	int mods_cap;
 };
 
-static int module_callback(void *data, const char *name,
-			   struct module *mod, unsigned long addr)
+static int add_module(struct modules_array *arr, struct module *mod)
 {
-	struct module_addr_args *args = data;
 	struct module **mods;
 
-	/* We iterate all modules symbols and for each we:
-	 * - search for it in provided addresses array
-	 * - if found we check if we already have the module pointer stored
-	 *   (we iterate modules sequentially, so we can check just the last
-	 *   module pointer)
-	 * - take module reference and store it
-	 */
-	if (!bsearch(&addr, args->addrs, args->addrs_cnt, sizeof(addr),
-		       bpf_kprobe_multi_addrs_cmp))
-		return 0;
-
-	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
-		return 0;
-
-	if (args->mods_cnt == args->mods_cap) {
-		args->mods_cap = max(16, args->mods_cap * 3 / 2);
-		mods = krealloc_array(args->mods, args->mods_cap, sizeof(*mods), GFP_KERNEL);
+	if (arr->mods_cnt == arr->mods_cap) {
+		arr->mods_cap = max(16, arr->mods_cap * 3 / 2);
+		mods = krealloc_array(arr->mods, arr->mods_cap, sizeof(*mods), GFP_KERNEL);
 		if (!mods)
 			return -ENOMEM;
-		args->mods = mods;
+		arr->mods = mods;
 	}
 
-	if (!try_module_get(mod))
-		return -EINVAL;
-
-	args->mods[args->mods_cnt] = mod;
-	args->mods_cnt++;
+	arr->mods[arr->mods_cnt] = mod;
+	arr->mods_cnt++;
 	return 0;
 }
 
+static bool has_module(struct modules_array *arr, struct module *mod)
+{
+	int i;
+
+	if (!arr->mods)
+		return false;
+	for (i = arr->mods_cnt; i >= 0; i--) {
+		if (arr->mods[i] == mod)
+			return true;
+	}
+	return false;
+}
+
 static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u32 addrs_cnt)
 {
-	struct module_addr_args args = {
-		.addrs     = addrs,
-		.addrs_cnt = addrs_cnt,
-	};
-	int err;
+	struct modules_array arr = {};
+	u32 i, err = 0;
+
+	for (i = 0; i < addrs_cnt; i++) {
+		struct module *mod;
+
+		preempt_disable();
+		mod = __module_address(addrs[i]);
+		/* Either no module or we it's already stored  */
+		if (!mod || (mod && has_module(&arr, mod))) {
+			preempt_enable();
+			continue;
+		}
+		if (!try_module_get(mod))
+			err = -EINVAL;
+		preempt_enable();
+		if (err)
+			break;
+		err = add_module(&arr, mod);
+		if (err) {
+			module_put(mod);
+			break;
+		}
+	}
 
 	/* We return either err < 0 in case of error, ... */
-	err = module_kallsyms_on_each_symbol(NULL, module_callback, &args);
 	if (err) {
-		kprobe_multi_put_modules(args.mods, args.mods_cnt);
-		kfree(args.mods);
+		kprobe_multi_put_modules(arr.mods, arr.mods_cnt);
+		kfree(arr.mods);
 		return err;
 	}
 
 	/* or number of modules found if everything is ok. */
-	*mods = args.mods;
-	return args.mods_cnt;
+	*mods = arr.mods;
+	return arr.mods_cnt;
 }
 
 int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)
@@ -2857,13 +2867,6 @@ int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *pr
 		       bpf_kprobe_multi_cookie_cmp,
 		       bpf_kprobe_multi_cookie_swap,
 		       link);
-	} else {
-		/*
-		 * We need to sort addrs array even if there are no cookies
-		 * provided, to allow bsearch in get_modules_for_addrs.
-		 */
-		sort(addrs, cnt, sizeof(*addrs),
-		       bpf_kprobe_multi_addrs_cmp, NULL);
 	}
 
 	err = get_modules_for_addrs(&link->mods, addrs, cnt);
-- 
2.39.0

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

[Song Liu]

On Fri, Jan 13, 2023 at 6:43 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> From: Zhen Lei <thunder.leizhen@huawei.com>
>
> 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>
> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>

Acked-by: Song Liu <song@kernel.org>

> ---
>  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(-)
>
> 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;
>  }
>
> --
> 2.39.0
>

Re: [PATCHv2 bpf-next 2/3] selftests/bpf: Add serial_test_kprobe_multi_bench_attach_kernel/module tests

[Song Liu]

On Fri, Jan 13, 2023 at 6:43 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> Add bench test for module portion of the symbols as well.
>
>   # ./test_progs -v -t kprobe_multi_bench_attach_module
>   bpf_testmod.ko is already unloaded.
>   Loading bpf_testmod.ko...
>   Successfully loaded bpf_testmod.ko.
>   test_kprobe_multi_bench_attach:PASS:get_syms 0 nsec
>   test_kprobe_multi_bench_attach:PASS:kprobe_multi_empty__open_and_load 0 nsec
>   test_kprobe_multi_bench_attach:PASS:bpf_program__attach_kprobe_multi_opts 0 nsec
>   test_kprobe_multi_bench_attach: found 26620 functions
>   test_kprobe_multi_bench_attach: attached in   0.182s
>   test_kprobe_multi_bench_attach: detached in   0.082s
>   #96      kprobe_multi_bench_attach_module:OK
>   Summary: 1/0 PASSED, 0 SKIPPED, 0 FAILED
>   Successfully unloaded bpf_testmod.ko.
>
> It's useful for testing kprobe multi link modules resolving.
>
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>

Acked-by: Song Liu <song@kernel.org>

> ---
>  .../bpf/prog_tests/kprobe_multi_test.c        | 21 ++++++++++++++-----
>  1 file changed, 16 insertions(+), 5 deletions(-)
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> index c6f37e825f11..017a6996f3fa 100644
> --- a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> +++ b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> @@ -322,7 +322,7 @@ static bool symbol_equal(long key1, long key2, void *ctx __maybe_unused)
>         return strcmp((const char *) key1, (const char *) key2) == 0;
>  }
>
> -static int get_syms(char ***symsp, size_t *cntp)
> +static int get_syms(char ***symsp, size_t *cntp, bool kernel)
>  {
>         size_t cap = 0, cnt = 0, i;
>         char *name = NULL, **syms = NULL;
> @@ -349,8 +349,9 @@ static int get_syms(char ***symsp, size_t *cntp)
>         }
>
>         while (fgets(buf, sizeof(buf), f)) {
> -               /* skip modules */
> -               if (strchr(buf, '['))
> +               if (kernel && strchr(buf, '['))
> +                       continue;
> +               if (!kernel && !strchr(buf, '['))
>                         continue;
>
>                 free(name);
> @@ -404,7 +405,7 @@ static int get_syms(char ***symsp, size_t *cntp)
>         return err;
>  }
>
> -void serial_test_kprobe_multi_bench_attach(void)
> +static void test_kprobe_multi_bench_attach(bool kernel)
>  {
>         LIBBPF_OPTS(bpf_kprobe_multi_opts, opts);
>         struct kprobe_multi_empty *skel = NULL;
> @@ -415,7 +416,7 @@ void serial_test_kprobe_multi_bench_attach(void)
>         char **syms = NULL;
>         size_t cnt = 0, i;
>
> -       if (!ASSERT_OK(get_syms(&syms, &cnt), "get_syms"))
> +       if (!ASSERT_OK(get_syms(&syms, &cnt, kernel), "get_syms"))
>                 return;
>
>         skel = kprobe_multi_empty__open_and_load();
> @@ -453,6 +454,16 @@ void serial_test_kprobe_multi_bench_attach(void)
>         }
>  }
>
> +void serial_test_kprobe_multi_bench_attach_kernel(void)
> +{
> +       test_kprobe_multi_bench_attach(true);
> +}
> +
> +void serial_test_kprobe_multi_bench_attach_module(void)
> +{
> +       test_kprobe_multi_bench_attach(false);
> +}
> +
>  void test_kprobe_multi_test(void)
>  {
>         if (!ASSERT_OK(load_kallsyms(), "load_kallsyms"))
> --
> 2.39.0
>

Re: [PATCHv2 bpf-next 3/3] bpf: Change modules resolving for kprobe multi link

[Song Liu]

On Fri, Jan 13, 2023 at 6:44 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> We currently use module_kallsyms_on_each_symbol that iterates all
> modules/symbols and we try to lookup each such address in user
> provided symbols/addresses to get list of used modules.
>
> This fix instead only iterates provided kprobe addresses and calls
> __module_address on each to get list of used modules. This turned
> out to be simpler and also bit faster.
>
> On my setup with workload being (executed 10 times):
>
>    # test_progs -t kprobe_multi_bench_attach_module
>
> Current code:
>
>  Performance counter stats for './test.sh' (5 runs):
>
>     76,081,161,596      cycles:k                   ( +-  0.47% )
>
>            18.3867 +- 0.0992 seconds time elapsed  ( +-  0.54% )
>
> With the fix:
>
>  Performance counter stats for './test.sh' (5 runs):
>
>     74,079,889,063      cycles:k                   ( +-  0.04% )
>
>            17.8514 +- 0.0218 seconds time elapsed  ( +-  0.12% )
>
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>
> ---
>  kernel/trace/bpf_trace.c | 95 +++++++++++++++++++++-------------------
>  1 file changed, 49 insertions(+), 46 deletions(-)
>
> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> index 095f7f8d34a1..90c5d5026831 100644
> --- a/kernel/trace/bpf_trace.c
> +++ b/kernel/trace/bpf_trace.c
> @@ -2682,69 +2682,79 @@ static void symbols_swap_r(void *a, void *b, int size, const void *priv)
>         }
>  }
>
> -struct module_addr_args {
> -       unsigned long *addrs;
> -       u32 addrs_cnt;
> +struct modules_array {
>         struct module **mods;
>         int mods_cnt;
>         int mods_cap;
>  };
>
> -static int module_callback(void *data, const char *name,
> -                          struct module *mod, unsigned long addr)
> +static int add_module(struct modules_array *arr, struct module *mod)
>  {
> -       struct module_addr_args *args = data;
>         struct module **mods;
>
> -       /* We iterate all modules symbols and for each we:
> -        * - search for it in provided addresses array
> -        * - if found we check if we already have the module pointer stored
> -        *   (we iterate modules sequentially, so we can check just the last
> -        *   module pointer)
> -        * - take module reference and store it
> -        */
> -       if (!bsearch(&addr, args->addrs, args->addrs_cnt, sizeof(addr),
> -                      bpf_kprobe_multi_addrs_cmp))
> -               return 0;
> -
> -       if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> -               return 0;
> -
> -       if (args->mods_cnt == args->mods_cap) {
> -               args->mods_cap = max(16, args->mods_cap * 3 / 2);
> -               mods = krealloc_array(args->mods, args->mods_cap, sizeof(*mods), GFP_KERNEL);
> +       if (arr->mods_cnt == arr->mods_cap) {
> +               arr->mods_cap = max(16, arr->mods_cap * 3 / 2);
> +               mods = krealloc_array(arr->mods, arr->mods_cap, sizeof(*mods), GFP_KERNEL);
>                 if (!mods)
>                         return -ENOMEM;
> -               args->mods = mods;
> +               arr->mods = mods;
>         }
>
> -       if (!try_module_get(mod))
> -               return -EINVAL;
> -
> -       args->mods[args->mods_cnt] = mod;
> -       args->mods_cnt++;
> +       arr->mods[arr->mods_cnt] = mod;
> +       arr->mods_cnt++;
>         return 0;
>  }
>
> +static bool has_module(struct modules_array *arr, struct module *mod)
> +{
> +       int i;
> +
> +       if (!arr->mods)
> +               return false;
> +       for (i = arr->mods_cnt; i >= 0; i--) {

This should be "i = arr->mods_cnt - 1", no?

> +               if (arr->mods[i] == mod)
> +                       return true;
> +       }
> +       return false;
> +}
> +
>  static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u32 addrs_cnt)
>  {
> -       struct module_addr_args args = {
> -               .addrs     = addrs,
> -               .addrs_cnt = addrs_cnt,
> -       };
> -       int err;
> +       struct modules_array arr = {};
> +       u32 i, err = 0;
> +
> +       for (i = 0; i < addrs_cnt; i++) {
> +               struct module *mod;
> +
> +               preempt_disable();
> +               mod = __module_address(addrs[i]);
> +               /* Either no module or we it's already stored  */
> +               if (!mod || (mod && has_module(&arr, mod))) {

nit: This can be simplified:

     if (!mod || has_module(&arr, mod)) {

> +                       preempt_enable();
> +                       continue;
> +               }

[...]

Re: [PATCHv2 bpf-next 3/3] bpf: Change modules resolving for kprobe multi link

[Jiri Olsa]

On Fri, Jan 13, 2023 at 12:41:50PM -0800, Song Liu wrote:
> On Fri, Jan 13, 2023 at 6:44 AM Jiri Olsa <jolsa@kernel.org> wrote:
> >
> > We currently use module_kallsyms_on_each_symbol that iterates all
> > modules/symbols and we try to lookup each such address in user
> > provided symbols/addresses to get list of used modules.
> >
> > This fix instead only iterates provided kprobe addresses and calls
> > __module_address on each to get list of used modules. This turned
> > out to be simpler and also bit faster.
> >
> > On my setup with workload being (executed 10 times):
> >
> >    # test_progs -t kprobe_multi_bench_attach_module
> >
> > Current code:
> >
> >  Performance counter stats for './test.sh' (5 runs):
> >
> >     76,081,161,596      cycles:k                   ( +-  0.47% )
> >
> >            18.3867 +- 0.0992 seconds time elapsed  ( +-  0.54% )
> >
> > With the fix:
> >
> >  Performance counter stats for './test.sh' (5 runs):
> >
> >     74,079,889,063      cycles:k                   ( +-  0.04% )
> >
> >            17.8514 +- 0.0218 seconds time elapsed  ( +-  0.12% )
> >
> > Signed-off-by: Jiri Olsa <jolsa@kernel.org>
> > ---
> >  kernel/trace/bpf_trace.c | 95 +++++++++++++++++++++-------------------
> >  1 file changed, 49 insertions(+), 46 deletions(-)
> >
> > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > index 095f7f8d34a1..90c5d5026831 100644
> > --- a/kernel/trace/bpf_trace.c
> > +++ b/kernel/trace/bpf_trace.c
> > @@ -2682,69 +2682,79 @@ static void symbols_swap_r(void *a, void *b, int size, const void *priv)
> >         }
> >  }
> >
> > -struct module_addr_args {
> > -       unsigned long *addrs;
> > -       u32 addrs_cnt;
> > +struct modules_array {
> >         struct module **mods;
> >         int mods_cnt;
> >         int mods_cap;
> >  };
> >
> > -static int module_callback(void *data, const char *name,
> > -                          struct module *mod, unsigned long addr)
> > +static int add_module(struct modules_array *arr, struct module *mod)
> >  {
> > -       struct module_addr_args *args = data;
> >         struct module **mods;
> >
> > -       /* We iterate all modules symbols and for each we:
> > -        * - search for it in provided addresses array
> > -        * - if found we check if we already have the module pointer stored
> > -        *   (we iterate modules sequentially, so we can check just the last
> > -        *   module pointer)
> > -        * - take module reference and store it
> > -        */
> > -       if (!bsearch(&addr, args->addrs, args->addrs_cnt, sizeof(addr),
> > -                      bpf_kprobe_multi_addrs_cmp))
> > -               return 0;
> > -
> > -       if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> > -               return 0;
> > -
> > -       if (args->mods_cnt == args->mods_cap) {
> > -               args->mods_cap = max(16, args->mods_cap * 3 / 2);
> > -               mods = krealloc_array(args->mods, args->mods_cap, sizeof(*mods), GFP_KERNEL);
> > +       if (arr->mods_cnt == arr->mods_cap) {
> > +               arr->mods_cap = max(16, arr->mods_cap * 3 / 2);
> > +               mods = krealloc_array(arr->mods, arr->mods_cap, sizeof(*mods), GFP_KERNEL);
> >                 if (!mods)
> >                         return -ENOMEM;
> > -               args->mods = mods;
> > +               arr->mods = mods;
> >         }
> >
> > -       if (!try_module_get(mod))
> > -               return -EINVAL;
> > -
> > -       args->mods[args->mods_cnt] = mod;
> > -       args->mods_cnt++;
> > +       arr->mods[arr->mods_cnt] = mod;
> > +       arr->mods_cnt++;
> >         return 0;
> >  }
> >
> > +static bool has_module(struct modules_array *arr, struct module *mod)
> > +{
> > +       int i;
> > +
> > +       if (!arr->mods)
> > +               return false;
> > +       for (i = arr->mods_cnt; i >= 0; i--) {
> 
> This should be "i = arr->mods_cnt - 1", no?

right

> 
> > +               if (arr->mods[i] == mod)
> > +                       return true;
> > +       }
> > +       return false;
> > +}
> > +
> >  static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u32 addrs_cnt)
> >  {
> > -       struct module_addr_args args = {
> > -               .addrs     = addrs,
> > -               .addrs_cnt = addrs_cnt,
> > -       };
> > -       int err;
> > +       struct modules_array arr = {};
> > +       u32 i, err = 0;
> > +
> > +       for (i = 0; i < addrs_cnt; i++) {
> > +               struct module *mod;
> > +
> > +               preempt_disable();
> > +               mod = __module_address(addrs[i]);
> > +               /* Either no module or we it's already stored  */
> > +               if (!mod || (mod && has_module(&arr, mod))) {
> 
> nit: This can be simplified:
> 
>      if (!mod || has_module(&arr, mod)) {

yep, will change

thanks,
jirka

Re: [PATCHv2 bpf-next 2/3] selftests/bpf: Add serial_test_kprobe_multi_bench_attach_kernel/module tests

[Andrii Nakryiko]

On Fri, Jan 13, 2023 at 6:33 AM Jiri Olsa <jolsa@kernel.org> wrote:
>
> Add bench test for module portion of the symbols as well.
>
>   # ./test_progs -v -t kprobe_multi_bench_attach_module
>   bpf_testmod.ko is already unloaded.
>   Loading bpf_testmod.ko...
>   Successfully loaded bpf_testmod.ko.
>   test_kprobe_multi_bench_attach:PASS:get_syms 0 nsec
>   test_kprobe_multi_bench_attach:PASS:kprobe_multi_empty__open_and_load 0 nsec
>   test_kprobe_multi_bench_attach:PASS:bpf_program__attach_kprobe_multi_opts 0 nsec
>   test_kprobe_multi_bench_attach: found 26620 functions
>   test_kprobe_multi_bench_attach: attached in   0.182s
>   test_kprobe_multi_bench_attach: detached in   0.082s
>   #96      kprobe_multi_bench_attach_module:OK
>   Summary: 1/0 PASSED, 0 SKIPPED, 0 FAILED
>   Successfully unloaded bpf_testmod.ko.
>
> It's useful for testing kprobe multi link modules resolving.
>
> Signed-off-by: Jiri Olsa <jolsa@kernel.org>
> ---
>  .../bpf/prog_tests/kprobe_multi_test.c        | 21 ++++++++++++++-----
>  1 file changed, 16 insertions(+), 5 deletions(-)
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> index c6f37e825f11..017a6996f3fa 100644
> --- a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> +++ b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> @@ -322,7 +322,7 @@ static bool symbol_equal(long key1, long key2, void *ctx __maybe_unused)
>         return strcmp((const char *) key1, (const char *) key2) == 0;
>  }
>
> -static int get_syms(char ***symsp, size_t *cntp)
> +static int get_syms(char ***symsp, size_t *cntp, bool kernel)
>  {
>         size_t cap = 0, cnt = 0, i;
>         char *name = NULL, **syms = NULL;
> @@ -349,8 +349,9 @@ static int get_syms(char ***symsp, size_t *cntp)
>         }
>
>         while (fgets(buf, sizeof(buf), f)) {
> -               /* skip modules */
> -               if (strchr(buf, '['))
> +               if (kernel && strchr(buf, '['))
> +                       continue;
> +               if (!kernel && !strchr(buf, '['))
>                         continue;
>
>                 free(name);
> @@ -404,7 +405,7 @@ static int get_syms(char ***symsp, size_t *cntp)
>         return err;
>  }
>
> -void serial_test_kprobe_multi_bench_attach(void)
> +static void test_kprobe_multi_bench_attach(bool kernel)
>  {
>         LIBBPF_OPTS(bpf_kprobe_multi_opts, opts);
>         struct kprobe_multi_empty *skel = NULL;
> @@ -415,7 +416,7 @@ void serial_test_kprobe_multi_bench_attach(void)
>         char **syms = NULL;
>         size_t cnt = 0, i;
>
> -       if (!ASSERT_OK(get_syms(&syms, &cnt), "get_syms"))
> +       if (!ASSERT_OK(get_syms(&syms, &cnt, kernel), "get_syms"))
>                 return;
>
>         skel = kprobe_multi_empty__open_and_load();
> @@ -453,6 +454,16 @@ void serial_test_kprobe_multi_bench_attach(void)
>         }
>  }
>
> +void serial_test_kprobe_multi_bench_attach_kernel(void)
> +{
> +       test_kprobe_multi_bench_attach(true);
> +}
> +
> +void serial_test_kprobe_multi_bench_attach_module(void)
> +{
> +       test_kprobe_multi_bench_attach(false);
> +}
> +

minor nit: probably would be better to make kernel and module variants
into subtests?



>  void test_kprobe_multi_test(void)
>  {
>         if (!ASSERT_OK(load_kallsyms(), "load_kallsyms"))
> --
> 2.39.0
>

Re: [PATCHv2 bpf-next 2/3] selftests/bpf: Add serial_test_kprobe_multi_bench_attach_kernel/module tests

[Jiri Olsa]

On Fri, Jan 13, 2023 at 02:43:47PM -0800, Andrii Nakryiko wrote:
> On Fri, Jan 13, 2023 at 6:33 AM Jiri Olsa <jolsa@kernel.org> wrote:
> >
> > Add bench test for module portion of the symbols as well.
> >
> >   # ./test_progs -v -t kprobe_multi_bench_attach_module
> >   bpf_testmod.ko is already unloaded.
> >   Loading bpf_testmod.ko...
> >   Successfully loaded bpf_testmod.ko.
> >   test_kprobe_multi_bench_attach:PASS:get_syms 0 nsec
> >   test_kprobe_multi_bench_attach:PASS:kprobe_multi_empty__open_and_load 0 nsec
> >   test_kprobe_multi_bench_attach:PASS:bpf_program__attach_kprobe_multi_opts 0 nsec
> >   test_kprobe_multi_bench_attach: found 26620 functions
> >   test_kprobe_multi_bench_attach: attached in   0.182s
> >   test_kprobe_multi_bench_attach: detached in   0.082s
> >   #96      kprobe_multi_bench_attach_module:OK
> >   Summary: 1/0 PASSED, 0 SKIPPED, 0 FAILED
> >   Successfully unloaded bpf_testmod.ko.
> >
> > It's useful for testing kprobe multi link modules resolving.
> >
> > Signed-off-by: Jiri Olsa <jolsa@kernel.org>
> > ---
> >  .../bpf/prog_tests/kprobe_multi_test.c        | 21 ++++++++++++++-----
> >  1 file changed, 16 insertions(+), 5 deletions(-)
> >
> > diff --git a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> > index c6f37e825f11..017a6996f3fa 100644
> > --- a/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> > +++ b/tools/testing/selftests/bpf/prog_tests/kprobe_multi_test.c
> > @@ -322,7 +322,7 @@ static bool symbol_equal(long key1, long key2, void *ctx __maybe_unused)
> >         return strcmp((const char *) key1, (const char *) key2) == 0;
> >  }
> >
> > -static int get_syms(char ***symsp, size_t *cntp)
> > +static int get_syms(char ***symsp, size_t *cntp, bool kernel)
> >  {
> >         size_t cap = 0, cnt = 0, i;
> >         char *name = NULL, **syms = NULL;
> > @@ -349,8 +349,9 @@ static int get_syms(char ***symsp, size_t *cntp)
> >         }
> >
> >         while (fgets(buf, sizeof(buf), f)) {
> > -               /* skip modules */
> > -               if (strchr(buf, '['))
> > +               if (kernel && strchr(buf, '['))
> > +                       continue;
> > +               if (!kernel && !strchr(buf, '['))
> >                         continue;
> >
> >                 free(name);
> > @@ -404,7 +405,7 @@ static int get_syms(char ***symsp, size_t *cntp)
> >         return err;
> >  }
> >
> > -void serial_test_kprobe_multi_bench_attach(void)
> > +static void test_kprobe_multi_bench_attach(bool kernel)
> >  {
> >         LIBBPF_OPTS(bpf_kprobe_multi_opts, opts);
> >         struct kprobe_multi_empty *skel = NULL;
> > @@ -415,7 +416,7 @@ void serial_test_kprobe_multi_bench_attach(void)
> >         char **syms = NULL;
> >         size_t cnt = 0, i;
> >
> > -       if (!ASSERT_OK(get_syms(&syms, &cnt), "get_syms"))
> > +       if (!ASSERT_OK(get_syms(&syms, &cnt, kernel), "get_syms"))
> >                 return;
> >
> >         skel = kprobe_multi_empty__open_and_load();
> > @@ -453,6 +454,16 @@ void serial_test_kprobe_multi_bench_attach(void)
> >         }
> >  }
> >
> > +void serial_test_kprobe_multi_bench_attach_kernel(void)
> > +{
> > +       test_kprobe_multi_bench_attach(true);
> > +}
> > +
> > +void serial_test_kprobe_multi_bench_attach_module(void)
> > +{
> > +       test_kprobe_multi_bench_attach(false);
> > +}
> > +
> 
> minor nit: probably would be better to make kernel and module variants
> into subtests?

ok, will change that

thanks,
jirka