From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9FB97C53210 for ; Thu, 5 Jan 2023 09:40:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231290AbjAEJkO (ORCPT ); Thu, 5 Jan 2023 04:40:14 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44950 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230471AbjAEJkN (ORCPT ); Thu, 5 Jan 2023 04:40:13 -0500 Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 464A9544E1; Thu, 5 Jan 2023 01:40:12 -0800 (PST) Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id C97806BCE9; Thu, 5 Jan 2023 09:32:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=susede1; t=1672911154; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=GfrBRkojWZ5wSAZVEYUzeElYRu2x1ZaqlGLpQM2iEDg=; b=eJ9EewVVG17Zq1paOFU+Vxn1uYwM+B3pteGCxVy2WDcALlOBGhnSTbR3GqbQ97m9Spqdnf Cr/0sZlPnsEW+W4uakHaFRcBJ+XRd/giFZhLF5b42ID3orqUXqNZDCe4LQrlGvsJpMQxYu srnPtSlsEDFGzX7MrqGO5EOEiM67ew4= Received: from suse.cz (unknown [10.100.201.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 639952C16E; Thu, 5 Jan 2023 09:32:34 +0000 (UTC) Date: Thu, 5 Jan 2023 10:32:34 +0100 From: Petr Mladek To: Zhen Lei Cc: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Joe Lawrence , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Song Liu , Yonghong Song , John Fastabend , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Steven Rostedt , Masami Hiramatsu , Mark Rutland , bpf@vger.kernel.org, linux-trace-kernel@vger.kernel.org, live-patching@vger.kernel.org, linux-kernel@vger.kernel.org, Luis Chamberlain , linux-modules@vger.kernel.org Subject: Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs() Message-ID: References: <20221230112729.351-1-thunder.leizhen@huawei.com> <20221230112729.351-3-thunder.leizhen@huawei.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org 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 > > --- > > 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