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

["Leizhen (ThunderTown)" <thunder.leizhen@huawei.com>]

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