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

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

[Zhen Lei]

Patches 7-8 in [1] have been delayed until now due to merge conflicts. The
current patch 1/3 corresponds to patch 7/9 in [1], and the current patch 3/3
corresponds to patch 8/9 in [1]. But there are some changes. Originally, only
livepatch uses function module_kallsyms_on_each_symbol(), it find the specified
function for the specified module. Now, bpf also uses function
module_kallsyms_on_each_symbol(), it needs to traverse all the modules. So for
the new parameter 'modname' of module_kallsyms_on_each_symbol(), if it's NULL,
the symbols of all modules are still traversed for compatibility with the case
of bpf.

Patch 2/3 is new, as I understand it, it should be fine. If it doesn't work,
then patch 3/3 should be dropped.

[1] https://lkml.org/lkml/2022/11/2/225

Zhen Lei (3):
  livepatch: Improve the search performance of
    module_kallsyms_on_each_symbol()
  bpf: Optimize get_modules_for_addrs()
  kallsyms: Delete an unused parameter related to
    {module_}kallsyms_on_each_symbol()

 include/linux/kallsyms.h   |   3 +-
 include/linux/module.h     |   8 +--
 kernel/kallsyms.c          |   5 +-
 kernel/kallsyms_selftest.c |   6 +--
 kernel/livepatch/core.c    |  13 +----
 kernel/module/kallsyms.c   |  16 ++++--
 kernel/trace/bpf_trace.c   | 101 +++++++++++++++----------------------
 kernel/trace/ftrace.c      |   5 +-
 8 files changed, 67 insertions(+), 90 deletions(-)

-- 
2.25.1

[PATCH 1/3] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Zhen Lei]

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).

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 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 8c5909c0076c6e1..514bc81568c5220 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 201f0c0482fb56d..c973ed9e42f8177 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 4523f99b03589e3..ab2376a1be88e7e 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 3bbd3f0c810c895..5f3be4bc16403a5 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -2737,7 +2737,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 442438b93fe9804..d249a55d9005765 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.25.1

Re: [PATCH 1/3] livepatch: Improve the search performance of module_kallsyms_on_each_symbol()

[Petr Mladek]

On Fri 2022-12-30 19:27:27, Zhen Lei wrote:
> 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).
> 
> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>

Looks good to me:

Reviewed-by: Petr Mladek <pmladek@suse.com>

Best Regards,
Petr

[PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Zhen Lei]

Function __module_address() can quickly return the pointer of the module
to which an address belongs. We do not need to traverse the symbols of all
modules to check whether each address in addrs[] is the start address of
the corresponding symbol, because register_fprobe_ips() will do this check
later.

Assuming that there are m modules, each module has n symbols on average,
and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
and the time complexity of current method is O(K * (log(m) + M)), M <= m.
(m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
the ratio is still greater than 1. Therefore, the new method will
generally have better performance.

Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
 1 file changed, 40 insertions(+), 61 deletions(-)

diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 5f3be4bc16403a5..0ff9037098bd241 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
 {
-	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;
+	int i, j, err;
+	int mods_cnt = 0;
+	int mods_cap = 0;
+	struct module *mod;
+	struct module **mods = NULL;
 
-	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
-		return 0;
+	for (i = 0; i < addrs_cnt; i++) {
+		mod = __module_address(addrs[i]);
+		if (!mod)
+			continue;
 
-	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 (!mods)
-			return -ENOMEM;
-		args->mods = mods;
-	}
+		/* check if we already have the module pointer stored */
+		for (j = 0; j < mods_cnt; j++) {
+			if (mods[j] == mod)
+				break;
+		}
+		if (j < mods_cnt)
+			continue;
 
-	if (!try_module_get(mod))
-		return -EINVAL;
+		if (mods_cnt == mods_cap) {
+			struct module **new_mods;
 
-	args->mods[args->mods_cnt] = mod;
-	args->mods_cnt++;
-	return 0;
-}
+			mods_cap = max(16, mods_cap * 3 / 2);
+			new_mods = krealloc_array(mods, mods_cap, sizeof(*mods), GFP_KERNEL);
+			if (!new_mods) {
+				err = -ENOMEM;
+				goto failed;
+			}
+			mods = new_mods;
+		}
 
-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;
+		if (!try_module_get(mod)) {
+			err = -EINVAL;
+			goto failed;
+		}
 
-	/* 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);
-		return err;
+		mods[mods_cnt] = mod;
+		mods_cnt++;
 	}
 
-	/* or number of modules found if everything is ok. */
-	*mods = args.mods;
-	return args.mods_cnt;
+	*out_mods = mods;
+	return mods_cnt;
+
+failed:
+	kprobe_multi_put_modules(mods, mods_cnt);
+	kfree(mods);
+	return err;
 }
 
 int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)
@@ -2859,13 +2845,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.25.1

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Petr Mladek]

On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> Function __module_address() can quickly return the pointer of the module
> to which an address belongs. We do not need to traverse the symbols of all
> modules to check whether each address in addrs[] is the start address of
> the corresponding symbol, because register_fprobe_ips() will do this check
> later.
> 
> Assuming that there are m modules, each module has n symbols on average,
> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> the ratio is still greater than 1. Therefore, the new method will
> generally have better performance.
> 
> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> ---
>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>  1 file changed, 40 insertions(+), 61 deletions(-)
> 
> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> index 5f3be4bc16403a5..0ff9037098bd241 100644
> --- a/kernel/trace/bpf_trace.c
> +++ b/kernel/trace/bpf_trace.c
> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>  {
> -	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;
> +	int i, j, err;
> +	int mods_cnt = 0;
> +	int mods_cap = 0;
> +	struct module *mod;
> +	struct module **mods = NULL;
>  
> -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> -		return 0;
> +	for (i = 0; i < addrs_cnt; i++) {
> +		mod = __module_address(addrs[i]);

This must be called under module_mutex to make sure that the module
would not disappear.

> +		if (!mod)
> +			continue;
>  
> -	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 (!mods)
> -			return -ENOMEM;
> -		args->mods = mods;
> -	}
> +		/* check if we already have the module pointer stored */
> +		for (j = 0; j < mods_cnt; j++) {
> +			if (mods[j] == mod)
> +				break;
> +		}

This might get optimized like the original code.

My understanding is that the addresses are sorted in "addrs" array.
So, the address is either part of the last found module or it belongs
to a completely new module.

	for (i = 0; i < addrs_cnt; i++) {
		/*
		 * The adresses are sorted. The adress either belongs
		 * to the last found module or a new one.
		 *
		 * This is safe because we already have reference
		 * on the found modules.
		 */
		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
			continue;

		mutex_lock(&module_mutex);
		mod = __module_address(addrs[i]);
		if (mod && !try_module_get(mod)) {
			mutex_unlock(&module_mutex);
			goto failed;
		}
		mutex_unlock(&module_mutex);

		/*
		 * Nope when the address was not from a module.
		 *
		 * Is this correct? What if the module has gone in
		 * the meantime? Anyway, the original code
		 * worked this way.
		 *
		 * FIXME: I would personally make sure that it is part
		 * of vmlinux or so.
		 */
		if (!mod)
			continue;

		/* store the module into mods array */
		...




> +		if (j < mods_cnt)
> +			continue;
>  
> -	if (!try_module_get(mod))
> -		return -EINVAL;
> +		if (mods_cnt == mods_cap) {
> +			struct module **new_mods;
>  
> -	args->mods[args->mods_cnt] = mod;
> -	args->mods_cnt++;
> -	return 0;
> -}
> +			mods_cap = max(16, mods_cap * 3 / 2);
> +			new_mods = krealloc_array(mods, mods_cap, sizeof(*mods), GFP_KERNEL);
> +			if (!new_mods) {
> +				err = -ENOMEM;
> +				goto failed;
> +			}
> +			mods = new_mods;
> +		}
>  
> -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;
> +		if (!try_module_get(mod)) {
> +			err = -EINVAL;
> +			goto failed;
> +		}
>  
> -	/* 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);
> -		return err;
> +		mods[mods_cnt] = mod;
> +		mods_cnt++;
>  	}
>  
> -	/* or number of modules found if everything is ok. */
> -	*mods = args.mods;
> -	return args.mods_cnt;
> +	*out_mods = mods;
> +	return mods_cnt;
> +
> +failed:
> +	kprobe_multi_put_modules(mods, mods_cnt);
> +	kfree(mods);
> +	return err;
>  }
>  
>  int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)

Otherwise, it looks good. IMHO, the new code looks more straightforward
than the original one.

Best Regards,
Petr

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Song Liu]

On Wed, Jan 4, 2023 at 8:25 AM Petr Mladek <pmladek@suse.com> wrote:
>
> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> > Function __module_address() can quickly return the pointer of the module
> > to which an address belongs. We do not need to traverse the symbols of all
> > modules to check whether each address in addrs[] is the start address of
> > the corresponding symbol, because register_fprobe_ips() will do this check
> > later.
> >
> > Assuming that there are m modules, each module has n symbols on average,
> > and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> > complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> > and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> > (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> > the ratio is still greater than 1. Therefore, the new method will
> > generally have better performance.
> >
> > Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> > ---
> >  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
> >  1 file changed, 40 insertions(+), 61 deletions(-)
> >
> > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > index 5f3be4bc16403a5..0ff9037098bd241 100644
> > --- a/kernel/trace/bpf_trace.c
> > +++ b/kernel/trace/bpf_trace.c
> > @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
> >  {
> > -     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;
> > +     int i, j, err;
> > +     int mods_cnt = 0;
> > +     int mods_cap = 0;
> > +     struct module *mod;
> > +     struct module **mods = NULL;
> >
> > -     if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> > -             return 0;
> > +     for (i = 0; i < addrs_cnt; i++) {
> > +             mod = __module_address(addrs[i]);
>
> This must be called under module_mutex to make sure that the module
> would not disappear.

module_mutex is not available outside kernel/module/. The common
practice is to disable preempt before calling __module_address().
CONFIG_LOCKDEP should catch this.

Thanks,
Song

[...]

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/5 1:07, Song Liu wrote:
> On Wed, Jan 4, 2023 at 8:25 AM Petr Mladek <pmladek@suse.com> wrote:
>>
>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>> Function __module_address() can quickly return the pointer of the module
>>> to which an address belongs. We do not need to traverse the symbols of all
>>> modules to check whether each address in addrs[] is the start address of
>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>> later.
>>>
>>> Assuming that there are m modules, each module has n symbols on average,
>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>> the ratio is still greater than 1. Therefore, the new method will
>>> generally have better performance.
>>>
>>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>>> ---
>>>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>>>  1 file changed, 40 insertions(+), 61 deletions(-)
>>>
>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>> index 5f3be4bc16403a5..0ff9037098bd241 100644
>>> --- a/kernel/trace/bpf_trace.c
>>> +++ b/kernel/trace/bpf_trace.c
>>> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>>>  {
>>> -     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;
>>> +     int i, j, err;
>>> +     int mods_cnt = 0;
>>> +     int mods_cap = 0;
>>> +     struct module *mod;
>>> +     struct module **mods = NULL;
>>>
>>> -     if (args->mods && args->mods[args->mods_cnt - 1] == mod)
>>> -             return 0;
>>> +     for (i = 0; i < addrs_cnt; i++) {
>>> +             mod = __module_address(addrs[i]);
>>
>> This must be called under module_mutex to make sure that the module
>> would not disappear.

Yes, mod needs to be protected, thanks.

> 
> module_mutex is not available outside kernel/module/. The common
> practice is to disable preempt before calling __module_address().

Yes, I've looked elsewhere, and all calling preempt_disable() for
RCU read protection. I will fix it.

> CONFIG_LOCKDEP should catch this.
> 
> Thanks,
> Song
> 
> [...]
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Petr Mladek]

On Wed 2023-01-04 09:07:02, Song Liu wrote:
> On Wed, Jan 4, 2023 at 8:25 AM Petr Mladek <pmladek@suse.com> wrote:
> >
> > On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> > > Function __module_address() can quickly return the pointer of the module
> > > to which an address belongs. We do not need to traverse the symbols of all
> > > modules to check whether each address in addrs[] is the start address of
> > > the corresponding symbol, because register_fprobe_ips() will do this check
> > > later.
> > >
> > > Assuming that there are m modules, each module has n symbols on average,
> > > and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> > > complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> > > and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> > > (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> > > the ratio is still greater than 1. Therefore, the new method will
> > > generally have better performance.
> > >
> > > Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> > > ---
> > >  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
> > >  1 file changed, 40 insertions(+), 61 deletions(-)
> > >
> > > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > > index 5f3be4bc16403a5..0ff9037098bd241 100644
> > > --- a/kernel/trace/bpf_trace.c
> > > +++ b/kernel/trace/bpf_trace.c
> > > @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
> > >  {
> > > -     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;
> > > +     int i, j, err;
> > > +     int mods_cnt = 0;
> > > +     int mods_cap = 0;
> > > +     struct module *mod;
> > > +     struct module **mods = NULL;
> > >
> > > -     if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> > > -             return 0;
> > > +     for (i = 0; i < addrs_cnt; i++) {
> > > +             mod = __module_address(addrs[i]);
> >
> > This must be called under module_mutex to make sure that the module
> > would not disappear.
> 
> module_mutex is not available outside kernel/module/. The common
> practice is to disable preempt before calling __module_address().
> CONFIG_LOCKDEP should catch this.

I see. Sigh, it is always better to take mutex than disable
preemption. But it might be acceptable in this case. We just need
to be careful.

First, the preemption must stay disabled all the time until
try_module_get(). Otherwise the returned struct module could
disappear in the meantime.

Second, krealloc_array() has to be called with preemption
enabled. It is perfectly fine to do it after try_module_get().

Best Regards,
Petr

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/5 17:05, Petr Mladek wrote:
> On Wed 2023-01-04 09:07:02, Song Liu wrote:
>> On Wed, Jan 4, 2023 at 8:25 AM Petr Mladek <pmladek@suse.com> wrote:
>>>
>>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>>> Function __module_address() can quickly return the pointer of the module
>>>> to which an address belongs. We do not need to traverse the symbols of all
>>>> modules to check whether each address in addrs[] is the start address of
>>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>>> later.
>>>>
>>>> Assuming that there are m modules, each module has n symbols on average,
>>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>>> the ratio is still greater than 1. Therefore, the new method will
>>>> generally have better performance.
>>>>
>>>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>>>> ---
>>>>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>>>>  1 file changed, 40 insertions(+), 61 deletions(-)
>>>>
>>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>>> index 5f3be4bc16403a5..0ff9037098bd241 100644
>>>> --- a/kernel/trace/bpf_trace.c
>>>> +++ b/kernel/trace/bpf_trace.c
>>>> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>>>>  {
>>>> -     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;
>>>> +     int i, j, err;
>>>> +     int mods_cnt = 0;
>>>> +     int mods_cap = 0;
>>>> +     struct module *mod;
>>>> +     struct module **mods = NULL;
>>>>
>>>> -     if (args->mods && args->mods[args->mods_cnt - 1] == mod)
>>>> -             return 0;
>>>> +     for (i = 0; i < addrs_cnt; i++) {
>>>> +             mod = __module_address(addrs[i]);
>>>
>>> This must be called under module_mutex to make sure that the module
>>> would not disappear.
>>
>> module_mutex is not available outside kernel/module/. The common
>> practice is to disable preempt before calling __module_address().
>> CONFIG_LOCKDEP should catch this.
> 
> I see. Sigh, it is always better to take mutex than disable
> preemption. But it might be acceptable in this case. We just need
> to be careful.
> 
> First, the preemption must stay disabled all the time until
> try_module_get(). Otherwise the returned struct module could
> disappear in the meantime.
> 
> Second, krealloc_array() has to be called with preemption
> enabled. It is perfectly fine to do it after try_module_get().

Okay, thanks for the heads-up.

> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/5 0:25, Petr Mladek wrote:
> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>> Function __module_address() can quickly return the pointer of the module
>> to which an address belongs. We do not need to traverse the symbols of all
>> modules to check whether each address in addrs[] is the start address of
>> the corresponding symbol, because register_fprobe_ips() will do this check
>> later.
>>
>> Assuming that there are m modules, each module has n symbols on average,
>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>> the ratio is still greater than 1. Therefore, the new method will
>> generally have better performance.
>>
>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>> ---
>>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>>  1 file changed, 40 insertions(+), 61 deletions(-)
>>
>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>> index 5f3be4bc16403a5..0ff9037098bd241 100644
>> --- a/kernel/trace/bpf_trace.c
>> +++ b/kernel/trace/bpf_trace.c
>> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>>  {
>> -	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;
>> +	int i, j, err;
>> +	int mods_cnt = 0;
>> +	int mods_cap = 0;
>> +	struct module *mod;
>> +	struct module **mods = NULL;
>>  
>> -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
>> -		return 0;
>> +	for (i = 0; i < addrs_cnt; i++) {
>> +		mod = __module_address(addrs[i]);
> 
> This must be called under module_mutex to make sure that the module
> would not disappear.
> 
>> +		if (!mod)
>> +			continue;
>>  
>> -	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 (!mods)
>> -			return -ENOMEM;
>> -		args->mods = mods;
>> -	}
>> +		/* check if we already have the module pointer stored */
>> +		for (j = 0; j < mods_cnt; j++) {
>> +			if (mods[j] == mod)
>> +				break;
>> +		}
> 
> This might get optimized like the original code.
> 
> My understanding is that the addresses are sorted in "addrs" array.
> So, the address is either part of the last found module or it belongs
> to a completely new module.

I'm in a hurry to get to the airport now. I will reply next week.
move_module() shows that a module has three layouts, and the memory
area is discontinuous. I originally wanted to implement what you
suggested below. I'll analyze it in depth next week. Maybe it'll work.


> 
> 	for (i = 0; i < addrs_cnt; i++) {
> 		/*
> 		 * The adresses are sorted. The adress either belongs
> 		 * to the last found module or a new one.
> 		 *
> 		 * This is safe because we already have reference
> 		 * on the found modules.
> 		 */
> 		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
> 			continue;
> 
> 		mutex_lock(&module_mutex);
> 		mod = __module_address(addrs[i]);
> 		if (mod && !try_module_get(mod)) {
> 			mutex_unlock(&module_mutex);
> 			goto failed;
> 		}
> 		mutex_unlock(&module_mutex);
> 
> 		/*
> 		 * Nope when the address was not from a module.
> 		 *
> 		 * Is this correct? What if the module has gone in
> 		 * the meantime? Anyway, the original code
> 		 * worked this way.
> 		 *
> 		 * FIXME: I would personally make sure that it is part
> 		 * of vmlinux or so.
> 		 */
> 		if (!mod)
> 			continue;
> 
> 		/* store the module into mods array */
> 		...
> 
> 
> 
> 
>> +		if (j < mods_cnt)
>> +			continue;
>>  
>> -	if (!try_module_get(mod))
>> -		return -EINVAL;
>> +		if (mods_cnt == mods_cap) {
>> +			struct module **new_mods;
>>  
>> -	args->mods[args->mods_cnt] = mod;
>> -	args->mods_cnt++;
>> -	return 0;
>> -}
>> +			mods_cap = max(16, mods_cap * 3 / 2);
>> +			new_mods = krealloc_array(mods, mods_cap, sizeof(*mods), GFP_KERNEL);
>> +			if (!new_mods) {
>> +				err = -ENOMEM;
>> +				goto failed;
>> +			}
>> +			mods = new_mods;
>> +		}
>>  
>> -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;
>> +		if (!try_module_get(mod)) {
>> +			err = -EINVAL;
>> +			goto failed;
>> +		}
>>  
>> -	/* 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);
>> -		return err;
>> +		mods[mods_cnt] = mod;
>> +		mods_cnt++;
>>  	}
>>  
>> -	/* or number of modules found if everything is ok. */
>> -	*mods = args.mods;
>> -	return args.mods_cnt;
>> +	*out_mods = mods;
>> +	return mods_cnt;
>> +
>> +failed:
>> +	kprobe_multi_put_modules(mods, mods_cnt);
>> +	kfree(mods);
>> +	return err;
>>  }
>>  
>>  int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)
> 
> Otherwise, it looks good. IMHO, the new code looks more straightforward
> than the original one.
> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Petr Mladek]

On Wed 2023-01-04 17:25:08, Petr Mladek wrote:
> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> > Function __module_address() can quickly return the pointer of the module
> > to which an address belongs. We do not need to traverse the symbols of all
> > modules to check whether each address in addrs[] is the start address of
> > the corresponding symbol, because register_fprobe_ips() will do this check
> > later.
> > 
> > Assuming that there are m modules, each module has n symbols on average,
> > and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> > complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> > and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> > (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> > the ratio is still greater than 1. Therefore, the new method will
> > generally have better performance.
> > 
> > Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> > ---
> >  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
> >  1 file changed, 40 insertions(+), 61 deletions(-)
> > 
> > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > index 5f3be4bc16403a5..0ff9037098bd241 100644
> > --- a/kernel/trace/bpf_trace.c
> > +++ b/kernel/trace/bpf_trace.c
> > @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
> >  {
> > -	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;
> > +	int i, j, err;
> > +	int mods_cnt = 0;
> > +	int mods_cap = 0;
> > +	struct module *mod;
> > +	struct module **mods = NULL;
> >  
> > -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> > -		return 0;
> > +	for (i = 0; i < addrs_cnt; i++) {
> > +		mod = __module_address(addrs[i]);
> 
> This must be called under module_mutex to make sure that the module
> would not disappear.
> 
> > +		if (!mod)
> > +			continue;
> >  
> > -	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 (!mods)
> > -			return -ENOMEM;
> > -		args->mods = mods;
> > -	}
> > +		/* check if we already have the module pointer stored */
> > +		for (j = 0; j < mods_cnt; j++) {
> > +			if (mods[j] == mod)
> > +				break;
> > +		}
> 
> This might get optimized like the original code.
> 
> My understanding is that the addresses are sorted in "addrs" array.
> So, the address is either part of the last found module or it belongs
> to a completely new module.

I thought more about it and I think that I was wrong, see below.

> 	for (i = 0; i < addrs_cnt; i++) {
> 		/*
> 		 * The adresses are sorted. The adress either belongs
> 		 * to the last found module or a new one.
> 		 *
> 		 * This is safe because we already have reference
> 		 * on the found modules.
> 		 */
> 		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
> 			continue;

within_module() checks two sections (init and core). They are
allocated separately, see module_alloc() called in move_module().

There might be a section from another modules between the init
and core section of a module.

The optimization worked in the original code because
module_kallsyms_on_each_symbol() always iterated over all
symbols from a module.

That said, I am not sure if bpf trace might be added for
symbols in the module init section. But it might be
better to stay on the safe side.

Best Regards,
Petr

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/5 17:32, Petr Mladek wrote:
> On Wed 2023-01-04 17:25:08, Petr Mladek wrote:
>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>> Function __module_address() can quickly return the pointer of the module
>>> to which an address belongs. We do not need to traverse the symbols of all
>>> modules to check whether each address in addrs[] is the start address of
>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>> later.
>>>
>>> Assuming that there are m modules, each module has n symbols on average,
>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>> the ratio is still greater than 1. Therefore, the new method will
>>> generally have better performance.
>>>
>>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>>> ---
>>>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>>>  1 file changed, 40 insertions(+), 61 deletions(-)
>>>
>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>> index 5f3be4bc16403a5..0ff9037098bd241 100644
>>> --- a/kernel/trace/bpf_trace.c
>>> +++ b/kernel/trace/bpf_trace.c
>>> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>>>  {
>>> -	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;
>>> +	int i, j, err;
>>> +	int mods_cnt = 0;
>>> +	int mods_cap = 0;
>>> +	struct module *mod;
>>> +	struct module **mods = NULL;
>>>  
>>> -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
>>> -		return 0;
>>> +	for (i = 0; i < addrs_cnt; i++) {
>>> +		mod = __module_address(addrs[i]);
>>
>> This must be called under module_mutex to make sure that the module
>> would not disappear.
>>
>>> +		if (!mod)
>>> +			continue;
>>>  
>>> -	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 (!mods)
>>> -			return -ENOMEM;
>>> -		args->mods = mods;
>>> -	}
>>> +		/* check if we already have the module pointer stored */
>>> +		for (j = 0; j < mods_cnt; j++) {
>>> +			if (mods[j] == mod)
>>> +				break;
>>> +		}
>>
>> This might get optimized like the original code.
>>
>> My understanding is that the addresses are sorted in "addrs" array.
>> So, the address is either part of the last found module or it belongs
>> to a completely new module.
> 
> I thought more about it and I think that I was wrong, see below.
> 
>> 	for (i = 0; i < addrs_cnt; i++) {
>> 		/*
>> 		 * The adresses are sorted. The adress either belongs
>> 		 * to the last found module or a new one.
>> 		 *
>> 		 * This is safe because we already have reference
>> 		 * on the found modules.
>> 		 */
>> 		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
>> 			continue;
> 
> within_module() checks two sections (init and core). They are
> allocated separately, see module_alloc() called in move_module().
> 
> There might be a section from another modules between the init
> and core section of a module.
> 
> The optimization worked in the original code because
> module_kallsyms_on_each_symbol() always iterated over all
> symbols from a module.
> 
> That said, I am not sure if bpf trace might be added for
> symbols in the module init section. But it might be
> better to stay on the safe side.

Yes.

> 
> Best Regards,
> Petr
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Jiri Olsa]

On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> > Function __module_address() can quickly return the pointer of the module
> > to which an address belongs. We do not need to traverse the symbols of all
> > modules to check whether each address in addrs[] is the start address of
> > the corresponding symbol, because register_fprobe_ips() will do this check
> > later.

hum, for some reason I can see only replies to this patch and
not the actual patch.. I'll dig it out of the lore I guess

> > 
> > Assuming that there are m modules, each module has n symbols on average,
> > and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> > complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> > and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> > (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> > the ratio is still greater than 1. Therefore, the new method will
> > generally have better performance.

could you try to benchmark that? I tried something similar but was not
able to get better performance

I'll review and run my benchmark test tomorrow

thanks,
jirka

> > 
> > Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
> > ---
> >  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
> >  1 file changed, 40 insertions(+), 61 deletions(-)
> > 
> > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > index 5f3be4bc16403a5..0ff9037098bd241 100644
> > --- a/kernel/trace/bpf_trace.c
> > +++ b/kernel/trace/bpf_trace.c
> > @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
> >  {
> > -	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;
> > +	int i, j, err;
> > +	int mods_cnt = 0;
> > +	int mods_cap = 0;
> > +	struct module *mod;
> > +	struct module **mods = NULL;
> >  
> > -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
> > -		return 0;
> > +	for (i = 0; i < addrs_cnt; i++) {
> > +		mod = __module_address(addrs[i]);
> 
> This must be called under module_mutex to make sure that the module
> would not disappear.
> 
> > +		if (!mod)
> > +			continue;
> >  
> > -	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 (!mods)
> > -			return -ENOMEM;
> > -		args->mods = mods;
> > -	}
> > +		/* check if we already have the module pointer stored */
> > +		for (j = 0; j < mods_cnt; j++) {
> > +			if (mods[j] == mod)
> > +				break;
> > +		}
> 
> This might get optimized like the original code.
> 
> My understanding is that the addresses are sorted in "addrs" array.
> So, the address is either part of the last found module or it belongs
> to a completely new module.
> 
> 	for (i = 0; i < addrs_cnt; i++) {
> 		/*
> 		 * The adresses are sorted. The adress either belongs
> 		 * to the last found module or a new one.
> 		 *
> 		 * This is safe because we already have reference
> 		 * on the found modules.
> 		 */
> 		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
> 			continue;
> 
> 		mutex_lock(&module_mutex);
> 		mod = __module_address(addrs[i]);
> 		if (mod && !try_module_get(mod)) {
> 			mutex_unlock(&module_mutex);
> 			goto failed;
> 		}
> 		mutex_unlock(&module_mutex);
> 
> 		/*
> 		 * Nope when the address was not from a module.
> 		 *
> 		 * Is this correct? What if the module has gone in
> 		 * the meantime? Anyway, the original code
> 		 * worked this way.
> 		 *
> 		 * FIXME: I would personally make sure that it is part
> 		 * of vmlinux or so.
> 		 */
> 		if (!mod)
> 			continue;
> 
> 		/* store the module into mods array */
> 		...
> 
> 
> 
> 
> > +		if (j < mods_cnt)
> > +			continue;
> >  
> > -	if (!try_module_get(mod))
> > -		return -EINVAL;
> > +		if (mods_cnt == mods_cap) {
> > +			struct module **new_mods;
> >  
> > -	args->mods[args->mods_cnt] = mod;
> > -	args->mods_cnt++;
> > -	return 0;
> > -}
> > +			mods_cap = max(16, mods_cap * 3 / 2);
> > +			new_mods = krealloc_array(mods, mods_cap, sizeof(*mods), GFP_KERNEL);
> > +			if (!new_mods) {
> > +				err = -ENOMEM;
> > +				goto failed;
> > +			}
> > +			mods = new_mods;
> > +		}
> >  
> > -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;
> > +		if (!try_module_get(mod)) {
> > +			err = -EINVAL;
> > +			goto failed;
> > +		}
> >  
> > -	/* 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);
> > -		return err;
> > +		mods[mods_cnt] = mod;
> > +		mods_cnt++;
> >  	}
> >  
> > -	/* or number of modules found if everything is ok. */
> > -	*mods = args.mods;
> > -	return args.mods_cnt;
> > +	*out_mods = mods;
> > +	return mods_cnt;
> > +
> > +failed:
> > +	kprobe_multi_put_modules(mods, mods_cnt);
> > +	kfree(mods);
> > +	return err;
> >  }
> >  
> >  int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)
> 
> Otherwise, it looks good. IMHO, the new code looks more straightforward
> than the original one.
> 
> Best Regards,
> Petr

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Jiri Olsa]

On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
> > On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> > > Function __module_address() can quickly return the pointer of the module
> > > to which an address belongs. We do not need to traverse the symbols of all
> > > modules to check whether each address in addrs[] is the start address of
> > > the corresponding symbol, because register_fprobe_ips() will do this check
> > > later.
> 
> hum, for some reason I can see only replies to this patch and
> not the actual patch.. I'll dig it out of the lore I guess
> 
> > > 
> > > Assuming that there are m modules, each module has n symbols on average,
> > > and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> > > complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> > > and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> > > (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> > > the ratio is still greater than 1. Therefore, the new method will
> > > generally have better performance.
> 
> could you try to benchmark that? I tried something similar but was not
> able to get better performance

hm looks like I tried the smilar thing (below) like you did,
but wasn't able to get better performace

I guess your goal is to get rid of the module arg in
module_kallsyms_on_each_symbol callback that we use?
I'm ok with the change if the performace is not worse

jirka


---
diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 5b9008bc597b..3280c22009f1 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -2692,23 +2692,16 @@ struct module_addr_args {
 	int mods_cap;
 };
 
-static int module_callback(void *data, const char *name,
-			   struct module *mod, unsigned long addr)
+static int add_module(struct module_addr_args *args, 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)
+	/* We iterate sorted addresses and for each within module we:
+	 * - check if we already have the module pointer stored for it
+	 *   (we iterate sorted addresses 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;
 
@@ -2734,10 +2727,24 @@ static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u3
 		.addrs     = addrs,
 		.addrs_cnt = addrs_cnt,
 	};
-	int err;
+	u32 i, err = 0;
+
+	for (i = 0; !err && i < addrs_cnt; i++) {
+		struct module *mod;
+		bool found = false;
+
+		preempt_disable();
+		mod = __module_text_address(addrs[i]);
+		found = mod && try_module_get(mod);
+		preempt_enable();
+
+		if (found) {
+			err = add_module(&args, mod);
+			module_put(mod);
+		}
+	}
 
 	/* We return either err < 0 in case of error, ... */
-	err = module_kallsyms_on_each_symbol(module_callback, &args);
 	if (err) {
 		kprobe_multi_put_modules(args.mods, args.mods_cnt);
 		kfree(args.mods);
@@ -2862,7 +2869,8 @@ int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *pr
 	} else {
 		/*
 		 * We need to sort addrs array even if there are no cookies
-		 * provided, to allow bsearch in get_modules_for_addrs.
+		 * provided, to allow sequential address walk in
+		 * get_modules_for_addrs.
 		 */
 		sort(addrs, cnt, sizeof(*addrs),
 		       bpf_kprobe_multi_addrs_cmp, NULL);

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/6 17:45, Jiri Olsa wrote:
> On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
>> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
>>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>>> Function __module_address() can quickly return the pointer of the module
>>>> to which an address belongs. We do not need to traverse the symbols of all
>>>> modules to check whether each address in addrs[] is the start address of
>>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>>> later.
>>
>> hum, for some reason I can see only replies to this patch and
>> not the actual patch.. I'll dig it out of the lore I guess
>>
>>>>
>>>> Assuming that there are m modules, each module has n symbols on average,
>>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>>> the ratio is still greater than 1. Therefore, the new method will
>>>> generally have better performance.
>>
>> could you try to benchmark that? I tried something similar but was not
>> able to get better performance
> 
> hm looks like I tried the smilar thing (below) like you did,

Yes. I just found out you're working on this improvement, too.

> but wasn't able to get better performace

Your implementation below is already the limit that can be optimized.
If the performance is not improved, it indicates that this place is
not the bottleneck.

> 
> I guess your goal is to get rid of the module arg in
> module_kallsyms_on_each_symbol callback that we use?

It's not a bad thing to keep argument 'mod' for function
module_kallsyms_on_each_symbol(), but for kallsyms_on_each_symbol(),
it's completely redundant. Now these two functions often use the
same hook function. So I carefully analyzed get_modules_for_addrs(),
which is the only place that involves the use of parameter 'mod'.
Looks like there's a possibility of eliminating parameter 'mod'.

> I'm ok with the change if the performace is not worse

OK, thanks.

> 
> jirka
> 
> 
> ---
> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> index 5b9008bc597b..3280c22009f1 100644
> --- a/kernel/trace/bpf_trace.c
> +++ b/kernel/trace/bpf_trace.c
> @@ -2692,23 +2692,16 @@ struct module_addr_args {
>  	int mods_cap;
>  };
>  
> -static int module_callback(void *data, const char *name,
> -			   struct module *mod, unsigned long addr)
> +static int add_module(struct module_addr_args *args, 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)
> +	/* We iterate sorted addresses and for each within module we:
> +	 * - check if we already have the module pointer stored for it
> +	 *   (we iterate sorted addresses 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;

There'll be problems Petr mentioned.

https://lkml.org/lkml/2023/1/5/191

>  
> @@ -2734,10 +2727,24 @@ static int get_modules_for_addrs(struct module ***mods, unsigned long *addrs, u3
>  		.addrs     = addrs,
>  		.addrs_cnt = addrs_cnt,
>  	};
> -	int err;
> +	u32 i, err = 0;
> +
> +	for (i = 0; !err && i < addrs_cnt; i++) {
> +		struct module *mod;
> +		bool found = false;
> +
> +		preempt_disable();
> +		mod = __module_text_address(addrs[i]);
> +		found = mod && try_module_get(mod);
> +		preempt_enable();
> +
> +		if (found) {
> +			err = add_module(&args, mod);
> +			module_put(mod);
> +		}
> +	}
>  
>  	/* We return either err < 0 in case of error, ... */
> -	err = module_kallsyms_on_each_symbol(module_callback, &args);
>  	if (err) {
>  		kprobe_multi_put_modules(args.mods, args.mods_cnt);
>  		kfree(args.mods);
> @@ -2862,7 +2869,8 @@ int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *pr
>  	} else {
>  		/*
>  		 * We need to sort addrs array even if there are no cookies
> -		 * provided, to allow bsearch in get_modules_for_addrs.
> +		 * provided, to allow sequential address walk in
> +		 * get_modules_for_addrs.
>  		 */
>  		sort(addrs, cnt, sizeof(*addrs),
>  		       bpf_kprobe_multi_addrs_cmp, NULL);
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Jiri Olsa]

On Mon, Jan 09, 2023 at 04:51:37PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2023/1/6 17:45, Jiri Olsa wrote:
> > On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
> >> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
> >>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> >>>> Function __module_address() can quickly return the pointer of the module
> >>>> to which an address belongs. We do not need to traverse the symbols of all
> >>>> modules to check whether each address in addrs[] is the start address of
> >>>> the corresponding symbol, because register_fprobe_ips() will do this check
> >>>> later.
> >>
> >> hum, for some reason I can see only replies to this patch and
> >> not the actual patch.. I'll dig it out of the lore I guess
> >>
> >>>>
> >>>> Assuming that there are m modules, each module has n symbols on average,
> >>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> >>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> >>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> >>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> >>>> the ratio is still greater than 1. Therefore, the new method will
> >>>> generally have better performance.
> >>
> >> could you try to benchmark that? I tried something similar but was not
> >> able to get better performance
> > 
> > hm looks like I tried the smilar thing (below) like you did,
> 
> Yes. I just found out you're working on this improvement, too.
> 
> > but wasn't able to get better performace
> 
> Your implementation below is already the limit that can be optimized.
> If the performance is not improved, it indicates that this place is
> not the bottleneck.
> 
> > 
> > I guess your goal is to get rid of the module arg in
> > module_kallsyms_on_each_symbol callback that we use?
> 
> It's not a bad thing to keep argument 'mod' for function
> module_kallsyms_on_each_symbol(), but for kallsyms_on_each_symbol(),
> it's completely redundant. Now these two functions often use the
> same hook function. So I carefully analyzed get_modules_for_addrs(),
> which is the only place that involves the use of parameter 'mod'.
> Looks like there's a possibility of eliminating parameter 'mod'.
> 
> > I'm ok with the change if the performace is not worse
> 
> OK, thanks.
> 
> > 
> > jirka
> > 
> > 
> > ---
> > diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> > index 5b9008bc597b..3280c22009f1 100644
> > --- a/kernel/trace/bpf_trace.c
> > +++ b/kernel/trace/bpf_trace.c
> > @@ -2692,23 +2692,16 @@ struct module_addr_args {
> >  	int mods_cap;
> >  };
> >  
> > -static int module_callback(void *data, const char *name,
> > -			   struct module *mod, unsigned long addr)
> > +static int add_module(struct module_addr_args *args, 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)
> > +	/* We iterate sorted addresses and for each within module we:
> > +	 * - check if we already have the module pointer stored for it
> > +	 *   (we iterate sorted addresses 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;
> 
> There'll be problems Petr mentioned.
> 
> https://lkml.org/lkml/2023/1/5/191

ok, makes sense.. I guess we could just search args->mods in here?
are you going to send new version, or should I update my patch with that?

thanks,
jirka

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/9 21:48, Jiri Olsa wrote:
> On Mon, Jan 09, 2023 at 04:51:37PM +0800, Leizhen (ThunderTown) wrote:
>>
>>
>> On 2023/1/6 17:45, Jiri Olsa wrote:
>>> On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
>>>> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
>>>>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>>>>> Function __module_address() can quickly return the pointer of the module
>>>>>> to which an address belongs. We do not need to traverse the symbols of all
>>>>>> modules to check whether each address in addrs[] is the start address of
>>>>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>>>>> later.
>>>>
>>>> hum, for some reason I can see only replies to this patch and
>>>> not the actual patch.. I'll dig it out of the lore I guess
>>>>
>>>>>>
>>>>>> Assuming that there are m modules, each module has n symbols on average,
>>>>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>>>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>>>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>>>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>>>>> the ratio is still greater than 1. Therefore, the new method will
>>>>>> generally have better performance.
>>>>
>>>> could you try to benchmark that? I tried something similar but was not
>>>> able to get better performance
>>>
>>> hm looks like I tried the smilar thing (below) like you did,
>>
>> Yes. I just found out you're working on this improvement, too.
>>
>>> but wasn't able to get better performace
>>
>> Your implementation below is already the limit that can be optimized.
>> If the performance is not improved, it indicates that this place is
>> not the bottleneck.
>>
>>>
>>> I guess your goal is to get rid of the module arg in
>>> module_kallsyms_on_each_symbol callback that we use?
>>
>> It's not a bad thing to keep argument 'mod' for function
>> module_kallsyms_on_each_symbol(), but for kallsyms_on_each_symbol(),
>> it's completely redundant. Now these two functions often use the
>> same hook function. So I carefully analyzed get_modules_for_addrs(),
>> which is the only place that involves the use of parameter 'mod'.
>> Looks like there's a possibility of eliminating parameter 'mod'.
>>
>>> I'm ok with the change if the performace is not worse
>>
>> OK, thanks.
>>
>>>
>>> jirka
>>>
>>>
>>> ---
>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>> index 5b9008bc597b..3280c22009f1 100644
>>> --- a/kernel/trace/bpf_trace.c
>>> +++ b/kernel/trace/bpf_trace.c
>>> @@ -2692,23 +2692,16 @@ struct module_addr_args {
>>>  	int mods_cap;
>>>  };
>>>  
>>> -static int module_callback(void *data, const char *name,
>>> -			   struct module *mod, unsigned long addr)
>>> +static int add_module(struct module_addr_args *args, 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)
>>> +	/* We iterate sorted addresses and for each within module we:
>>> +	 * - check if we already have the module pointer stored for it
>>> +	 *   (we iterate sorted addresses 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;
>>
>> There'll be problems Petr mentioned.
>>
>> https://lkml.org/lkml/2023/1/5/191
> 
> ok, makes sense.. I guess we could just search args->mods in here?
> are you going to send new version, or should I update my patch with that?

It's better for you to update! I'm not familiar with the bpf module.

> 
> thanks,
> jirka
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/9 23:11, Leizhen (ThunderTown) wrote:
> 
> 
> On 2023/1/9 21:48, Jiri Olsa wrote:
>> On Mon, Jan 09, 2023 at 04:51:37PM +0800, Leizhen (ThunderTown) wrote:
>>>
>>>
>>> On 2023/1/6 17:45, Jiri Olsa wrote:
>>>> On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
>>>>> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
>>>>>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>>>>>> Function __module_address() can quickly return the pointer of the module
>>>>>>> to which an address belongs. We do not need to traverse the symbols of all
>>>>>>> modules to check whether each address in addrs[] is the start address of
>>>>>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>>>>>> later.
>>>>>
>>>>> hum, for some reason I can see only replies to this patch and
>>>>> not the actual patch.. I'll dig it out of the lore I guess
>>>>>
>>>>>>>
>>>>>>> Assuming that there are m modules, each module has n symbols on average,
>>>>>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>>>>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>>>>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>>>>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>>>>>> the ratio is still greater than 1. Therefore, the new method will
>>>>>>> generally have better performance.
>>>>>
>>>>> could you try to benchmark that? I tried something similar but was not
>>>>> able to get better performance
>>>>
>>>> hm looks like I tried the smilar thing (below) like you did,
>>>
>>> Yes. I just found out you're working on this improvement, too.
>>>
>>>> but wasn't able to get better performace
>>>
>>> Your implementation below is already the limit that can be optimized.
>>> If the performance is not improved, it indicates that this place is
>>> not the bottleneck.
>>>
>>>>
>>>> I guess your goal is to get rid of the module arg in
>>>> module_kallsyms_on_each_symbol callback that we use?
>>>
>>> It's not a bad thing to keep argument 'mod' for function
>>> module_kallsyms_on_each_symbol(), but for kallsyms_on_each_symbol(),
>>> it's completely redundant. Now these two functions often use the
>>> same hook function. So I carefully analyzed get_modules_for_addrs(),
>>> which is the only place that involves the use of parameter 'mod'.
>>> Looks like there's a possibility of eliminating parameter 'mod'.
>>>
>>>> I'm ok with the change if the performace is not worse
>>>
>>> OK, thanks.
>>>
>>>>
>>>> jirka
>>>>
>>>>
>>>> ---
>>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>>> index 5b9008bc597b..3280c22009f1 100644
>>>> --- a/kernel/trace/bpf_trace.c
>>>> +++ b/kernel/trace/bpf_trace.c
>>>> @@ -2692,23 +2692,16 @@ struct module_addr_args {
>>>>  	int mods_cap;
>>>>  };
>>>>  
>>>> -static int module_callback(void *data, const char *name,
>>>> -			   struct module *mod, unsigned long addr)
>>>> +static int add_module(struct module_addr_args *args, 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)
>>>> +	/* We iterate sorted addresses and for each within module we:
>>>> +	 * - check if we already have the module pointer stored for it
>>>> +	 *   (we iterate sorted addresses 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;
>>>
>>> There'll be problems Petr mentioned.
>>>
>>> https://lkml.org/lkml/2023/1/5/191
>>
>> ok, makes sense.. I guess we could just search args->mods in here?
>> are you going to send new version, or should I update my patch with that?
> 
> It's better for you to update! I'm not familiar with the bpf module.

Hi Jiri:
  Can you attach patch 1/3 when you send the new patch? There's a little
dependency. Petr has already replied OK to patch 1/3, see [1].
  Patch 3/3 is just a cleanup, I'll delay updating it after v6.3-rc1, it
also has a dependency on another patch [2].

[1] https://lkml.org/lkml/2023/1/4/627
[2] https://lkml.org/lkml/2023/1/10/534



> 
>>
>> thanks,
>> jirka
>> .
>>
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Jiri Olsa]

On Wed, Jan 11, 2023 at 04:41:21PM +0800, Leizhen (ThunderTown) wrote:
> 
> 
> On 2023/1/9 23:11, Leizhen (ThunderTown) wrote:
> > 
> > 
> > On 2023/1/9 21:48, Jiri Olsa wrote:
> >> On Mon, Jan 09, 2023 at 04:51:37PM +0800, Leizhen (ThunderTown) wrote:
> >>>
> >>>
> >>> On 2023/1/6 17:45, Jiri Olsa wrote:
> >>>> On Thu, Jan 05, 2023 at 10:31:12PM +0100, Jiri Olsa wrote:
> >>>>> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
> >>>>>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
> >>>>>>> Function __module_address() can quickly return the pointer of the module
> >>>>>>> to which an address belongs. We do not need to traverse the symbols of all
> >>>>>>> modules to check whether each address in addrs[] is the start address of
> >>>>>>> the corresponding symbol, because register_fprobe_ips() will do this check
> >>>>>>> later.
> >>>>>
> >>>>> hum, for some reason I can see only replies to this patch and
> >>>>> not the actual patch.. I'll dig it out of the lore I guess
> >>>>>
> >>>>>>>
> >>>>>>> Assuming that there are m modules, each module has n symbols on average,
> >>>>>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
> >>>>>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
> >>>>>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
> >>>>>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
> >>>>>>> the ratio is still greater than 1. Therefore, the new method will
> >>>>>>> generally have better performance.
> >>>>>
> >>>>> could you try to benchmark that? I tried something similar but was not
> >>>>> able to get better performance
> >>>>
> >>>> hm looks like I tried the smilar thing (below) like you did,
> >>>
> >>> Yes. I just found out you're working on this improvement, too.
> >>>
> >>>> but wasn't able to get better performace
> >>>
> >>> Your implementation below is already the limit that can be optimized.
> >>> If the performance is not improved, it indicates that this place is
> >>> not the bottleneck.
> >>>
> >>>>
> >>>> I guess your goal is to get rid of the module arg in
> >>>> module_kallsyms_on_each_symbol callback that we use?
> >>>
> >>> It's not a bad thing to keep argument 'mod' for function
> >>> module_kallsyms_on_each_symbol(), but for kallsyms_on_each_symbol(),
> >>> it's completely redundant. Now these two functions often use the
> >>> same hook function. So I carefully analyzed get_modules_for_addrs(),
> >>> which is the only place that involves the use of parameter 'mod'.
> >>> Looks like there's a possibility of eliminating parameter 'mod'.
> >>>
> >>>> I'm ok with the change if the performace is not worse
> >>>
> >>> OK, thanks.
> >>>
> >>>>
> >>>> jirka
> >>>>
> >>>>
> >>>> ---
> >>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
> >>>> index 5b9008bc597b..3280c22009f1 100644
> >>>> --- a/kernel/trace/bpf_trace.c
> >>>> +++ b/kernel/trace/bpf_trace.c
> >>>> @@ -2692,23 +2692,16 @@ struct module_addr_args {
> >>>>  	int mods_cap;
> >>>>  };
> >>>>  
> >>>> -static int module_callback(void *data, const char *name,
> >>>> -			   struct module *mod, unsigned long addr)
> >>>> +static int add_module(struct module_addr_args *args, 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)
> >>>> +	/* We iterate sorted addresses and for each within module we:
> >>>> +	 * - check if we already have the module pointer stored for it
> >>>> +	 *   (we iterate sorted addresses 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;
> >>>
> >>> There'll be problems Petr mentioned.
> >>>
> >>> https://lkml.org/lkml/2023/1/5/191
> >>
> >> ok, makes sense.. I guess we could just search args->mods in here?
> >> are you going to send new version, or should I update my patch with that?
> > 
> > It's better for you to update! I'm not familiar with the bpf module.
> 
> Hi Jiri:
>   Can you attach patch 1/3 when you send the new patch? There's a little
> dependency. Petr has already replied OK to patch 1/3, see [1].
>   Patch 3/3 is just a cleanup, I'll delay updating it after v6.3-rc1, it
> also has a dependency on another patch [2].

ok, will do

jirka

Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

[Leizhen (ThunderTown)]

On 2023/1/6 5:31, Jiri Olsa wrote:
> On Wed, Jan 04, 2023 at 05:25:08PM +0100, Petr Mladek wrote:
>> On Fri 2022-12-30 19:27:28, Zhen Lei wrote:
>>> Function __module_address() can quickly return the pointer of the module
>>> to which an address belongs. We do not need to traverse the symbols of all
>>> modules to check whether each address in addrs[] is the start address of
>>> the corresponding symbol, because register_fprobe_ips() will do this check
>>> later.
> 
> hum, for some reason I can see only replies to this patch and
> not the actual patch.. I'll dig it out of the lore I guess

https://lkml.org/lkml/2022/12/30/195

> 
>>>
>>> Assuming that there are m modules, each module has n symbols on average,
>>> and the number of addresses 'addrs_cnt' is abbreviated as K. Then the time
>>> complexity of the original method is O(K * log(K)) + O(m * n * log(K)),
>>> and the time complexity of current method is O(K * (log(m) + M)), M <= m.
>>> (m * n * log(K)) / (K * m) ==> n / log2(K). Even if n is 10 and K is 128,
>>> the ratio is still greater than 1. Therefore, the new method will
>>> generally have better performance.
> 
> could you try to benchmark that? I tried something similar but was not
> able to get better performance

I'm just theoretically analyzing, at least the performance won't get worse.

> 
> I'll review and run my benchmark test tomorrow
> 
> thanks,
> jirka
> 
>>>
>>> Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
>>> ---
>>>  kernel/trace/bpf_trace.c | 101 ++++++++++++++++-----------------------
>>>  1 file changed, 40 insertions(+), 61 deletions(-)
>>>
>>> diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
>>> index 5f3be4bc16403a5..0ff9037098bd241 100644
>>> --- a/kernel/trace/bpf_trace.c
>>> +++ b/kernel/trace/bpf_trace.c
>>> @@ -2684,69 +2684,55 @@ 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 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 get_modules_for_addrs(struct module ***out_mods, unsigned long *addrs, u32 addrs_cnt)
>>>  {
>>> -	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;
>>> +	int i, j, err;
>>> +	int mods_cnt = 0;
>>> +	int mods_cap = 0;
>>> +	struct module *mod;
>>> +	struct module **mods = NULL;
>>>  
>>> -	if (args->mods && args->mods[args->mods_cnt - 1] == mod)
>>> -		return 0;
>>> +	for (i = 0; i < addrs_cnt; i++) {
>>> +		mod = __module_address(addrs[i]);
>>
>> This must be called under module_mutex to make sure that the module
>> would not disappear.
>>
>>> +		if (!mod)
>>> +			continue;
>>>  
>>> -	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 (!mods)
>>> -			return -ENOMEM;
>>> -		args->mods = mods;
>>> -	}
>>> +		/* check if we already have the module pointer stored */
>>> +		for (j = 0; j < mods_cnt; j++) {
>>> +			if (mods[j] == mod)
>>> +				break;
>>> +		}
>>
>> This might get optimized like the original code.
>>
>> My understanding is that the addresses are sorted in "addrs" array.
>> So, the address is either part of the last found module or it belongs
>> to a completely new module.
>>
>> 	for (i = 0; i < addrs_cnt; i++) {
>> 		/*
>> 		 * The adresses are sorted. The adress either belongs
>> 		 * to the last found module or a new one.
>> 		 *
>> 		 * This is safe because we already have reference
>> 		 * on the found modules.
>> 		 */
>> 		 if (mods_cnt && within_module(addrs[i], mods[mods_cnt - 1]))
>> 			continue;
>>
>> 		mutex_lock(&module_mutex);
>> 		mod = __module_address(addrs[i]);
>> 		if (mod && !try_module_get(mod)) {
>> 			mutex_unlock(&module_mutex);
>> 			goto failed;
>> 		}
>> 		mutex_unlock(&module_mutex);
>>
>> 		/*
>> 		 * Nope when the address was not from a module.
>> 		 *
>> 		 * Is this correct? What if the module has gone in
>> 		 * the meantime? Anyway, the original code
>> 		 * worked this way.
>> 		 *
>> 		 * FIXME: I would personally make sure that it is part
>> 		 * of vmlinux or so.
>> 		 */
>> 		if (!mod)
>> 			continue;
>>
>> 		/* store the module into mods array */
>> 		...
>>
>>
>>
>>
>>> +		if (j < mods_cnt)
>>> +			continue;
>>>  
>>> -	if (!try_module_get(mod))
>>> -		return -EINVAL;
>>> +		if (mods_cnt == mods_cap) {
>>> +			struct module **new_mods;
>>>  
>>> -	args->mods[args->mods_cnt] = mod;
>>> -	args->mods_cnt++;
>>> -	return 0;
>>> -}
>>> +			mods_cap = max(16, mods_cap * 3 / 2);
>>> +			new_mods = krealloc_array(mods, mods_cap, sizeof(*mods), GFP_KERNEL);
>>> +			if (!new_mods) {
>>> +				err = -ENOMEM;
>>> +				goto failed;
>>> +			}
>>> +			mods = new_mods;
>>> +		}
>>>  
>>> -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;
>>> +		if (!try_module_get(mod)) {
>>> +			err = -EINVAL;
>>> +			goto failed;
>>> +		}
>>>  
>>> -	/* 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);
>>> -		return err;
>>> +		mods[mods_cnt] = mod;
>>> +		mods_cnt++;
>>>  	}
>>>  
>>> -	/* or number of modules found if everything is ok. */
>>> -	*mods = args.mods;
>>> -	return args.mods_cnt;
>>> +	*out_mods = mods;
>>> +	return mods_cnt;
>>> +
>>> +failed:
>>> +	kprobe_multi_put_modules(mods, mods_cnt);
>>> +	kfree(mods);
>>> +	return err;
>>>  }
>>>  
>>>  int bpf_kprobe_multi_link_attach(const union bpf_attr *attr, struct bpf_prog *prog)
>>
>> Otherwise, it looks good. IMHO, the new code looks more straightforward
>> than the original one.
>>
>> Best Regards,
>> Petr
> .
> 

-- 
Regards,
  Zhen Lei

[PATCH 3/3] kallsyms: Delete an unused parameter related to {module_}kallsyms_on_each_symbol()

[Zhen Lei]

The parameter 'struct module *' in the hook function associated with
{module_}kallsyms_on_each_symbol() is no longer used. Delete it.

Suggested-by: Petr Mladek <pmladek@suse.com>
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
---
 include/linux/kallsyms.h   | 3 +--
 include/linux/module.h     | 6 ++----
 kernel/kallsyms.c          | 5 ++---
 kernel/kallsyms_selftest.c | 6 +++---
 kernel/livepatch/core.c    | 3 +--
 kernel/module/kallsyms.c   | 5 ++---
 kernel/trace/ftrace.c      | 3 +--
 7 files changed, 12 insertions(+), 19 deletions(-)

diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index 0065209cc00424b..d4079b3d951d1ef 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -67,8 +67,7 @@ static inline void *dereference_symbol_descriptor(void *ptr)
 
 #ifdef CONFIG_KALLSYMS
 unsigned long kallsyms_sym_address(int idx);
-int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
-				      unsigned long),
+int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
 			    void *data);
 int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
 				  const char *name, void *data);
diff --git a/include/linux/module.h b/include/linux/module.h
index 514bc81568c5220..39f928e9d9fed7e 100644
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -880,13 +880,11 @@ static inline bool module_sig_ok(struct module *module)
 
 #if defined(CONFIG_MODULES) && defined(CONFIG_KALLSYMS)
 int module_kallsyms_on_each_symbol(const char *modname,
-				   int (*fn)(void *, const char *,
-					     struct module *, unsigned long),
+				   int (*fn)(void *, const char *, unsigned long),
 				   void *data);
 #else
 static inline int module_kallsyms_on_each_symbol(const char *modname,
-						 int (*fn)(void *, const char *,
-						 struct module *, unsigned long),
+						 int (*fn)(void *, const char *, unsigned long),
 						 void *data)
 {
 	return -EOPNOTSUPP;
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 83f499182c9aa31..77747391f49b66c 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -288,8 +288,7 @@ unsigned long kallsyms_lookup_name(const char *name)
  * Iterate over all symbols in vmlinux.  For symbols from modules use
  * module_kallsyms_on_each_symbol instead.
  */
-int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
-				      unsigned long),
+int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
 			    void *data)
 {
 	char namebuf[KSYM_NAME_LEN];
@@ -299,7 +298,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *,
 
 	for (i = 0, off = 0; i < kallsyms_num_syms; i++) {
 		off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
-		ret = fn(data, namebuf, NULL, kallsyms_sym_address(i));
+		ret = fn(data, namebuf, kallsyms_sym_address(i));
 		if (ret != 0)
 			return ret;
 		cond_resched();
diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
index 9c94f06aa951971..1b6891a0a79052b 100644
--- a/kernel/kallsyms_selftest.c
+++ b/kernel/kallsyms_selftest.c
@@ -97,7 +97,7 @@ static struct test_item test_items[] = {
 
 static char stub_name[KSYM_NAME_LEN];
 
-static int stat_symbol_len(void *data, const char *name, struct module *mod, unsigned long addr)
+static int stat_symbol_len(void *data, const char *name, unsigned long addr)
 {
 	*(u32 *)data += strlen(name);
 
@@ -156,7 +156,7 @@ static void test_kallsyms_compression_ratio(void)
 	pr_info(" ---------------------------------------------------------\n");
 }
 
-static int lookup_name(void *data, const char *name, struct module *mod, unsigned long addr)
+static int lookup_name(void *data, const char *name, unsigned long addr)
 {
 	u64 t0, t1, t;
 	unsigned long flags;
@@ -212,7 +212,7 @@ static bool match_cleanup_name(const char *s, const char *name)
 	return !strncmp(s, name, len);
 }
 
-static int find_symbol(void *data, const char *name, struct module *mod, unsigned long addr)
+static int find_symbol(void *data, const char *name, unsigned long addr)
 {
 	struct test_stat *stat = (struct test_stat *)data;
 
diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c
index c973ed9e42f8177..bdb40a4b1f29845 100644
--- a/kernel/livepatch/core.c
+++ b/kernel/livepatch/core.c
@@ -142,8 +142,7 @@ static int klp_match_callback(void *data, unsigned long addr)
 	return 0;
 }
 
-static int klp_find_callback(void *data, const char *name,
-			     struct module *mod, unsigned long addr)
+static int klp_find_callback(void *data, const char *name, unsigned long addr)
 {
 	struct klp_find_arg *args = data;
 
diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c
index ab2376a1be88e7e..c4fe856e5052ff7 100644
--- a/kernel/module/kallsyms.c
+++ b/kernel/module/kallsyms.c
@@ -495,8 +495,7 @@ unsigned long module_kallsyms_lookup_name(const char *name)
 }
 
 int module_kallsyms_on_each_symbol(const char *modname,
-				   int (*fn)(void *, const char *,
-					     struct module *, unsigned long),
+				   int (*fn)(void *, const char *, unsigned long),
 				   void *data)
 {
 	struct module *mod;
@@ -525,7 +524,7 @@ int module_kallsyms_on_each_symbol(const char *modname,
 				continue;
 
 			ret = fn(data, kallsyms_symbol_name(kallsyms, i),
-				 mod, kallsyms_symbol_value(sym));
+				 kallsyms_symbol_value(sym));
 			if (ret != 0)
 				goto out;
 		}
diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index d249a55d9005765..8f12524f8062686 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -8271,8 +8271,7 @@ struct kallsyms_data {
  * and returns 1 in case we resolved all the requested symbols,
  * 0 otherwise.
  */
-static int kallsyms_callback(void *data, const char *name,
-			     struct module *mod, unsigned long addr)
+static int kallsyms_callback(void *data, const char *name, unsigned long addr)
 {
 	struct kallsyms_data *args = data;
 	const char **sym;
-- 
2.25.1