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 C25EEC53210 for ; Wed, 4 Jan 2023 17:07:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234927AbjADRH1 (ORCPT ); Wed, 4 Jan 2023 12:07:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57776 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240067AbjADRHT (ORCPT ); Wed, 4 Jan 2023 12:07:19 -0500 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 562C7DEF0; Wed, 4 Jan 2023 09:07:18 -0800 (PST) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id EE851617C2; Wed, 4 Jan 2023 17:07:17 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 5FF89C433A0; Wed, 4 Jan 2023 17:07:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672852037; bh=XIJG7ewqo5kzp9edbZOx9BOvNMni+jLemYlHy7gF5jg=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=kfExFvmItt4dG419jptDEGrPnxaHEl7ANZY3Su0tEfVP9fWO7oyj4EAKfTnr/om74 ohRHZkSDujsAQxXMzO/wDVR6RAGymtNmL5Jla6eiFErIrtUKAuK3JntirLyOJtl9B8 uSMx5PSyx7yu03mz4T7FX51KaNCSi8PNUGW/ekWS0FqraBIyMtW212zxsAcpGrdWQg PePwf21cYLqd27Do/l7O6V7q3kBK+EfOD2pWMqxHpdd98mRDuEXjt9IHslTaCyxNjh zhjmUGRMv8YiAqWQnalrYloStOP/QdV3iDytIohrGr9vQA0VfPChDY69BD+1qFN4xH xe+N83K8+1MpQ== Received: by mail-lf1-f49.google.com with SMTP id b3so51334140lfv.2; Wed, 04 Jan 2023 09:07:17 -0800 (PST) X-Gm-Message-State: AFqh2kp6krRbk5HI6C01pHOWYwSbvnqz/VXnixH+++djHrUFqw37CfSj kxn7jNO8nDsmZbOmJaV9JkaKs7YhRmHc7hcKDuE= X-Google-Smtp-Source: AMrXdXundjKp8Y8z3TAzqVpDm1DiOwJOMJ1w4ildaIhc+9uQOPt8d+wG6ixJzIoFdowAOSSzx68CkqC0YZEraLz7J2w= X-Received: by 2002:a05:6512:3f07:b0:4ca:f873:7cf3 with SMTP id y7-20020a0565123f0700b004caf8737cf3mr3156707lfa.89.1672852035170; Wed, 04 Jan 2023 09:07:15 -0800 (PST) MIME-Version: 1.0 References: <20221230112729.351-1-thunder.leizhen@huawei.com> <20221230112729.351-3-thunder.leizhen@huawei.com> In-Reply-To: From: Song Liu Date: Wed, 4 Jan 2023 09:07:02 -0800 X-Gmail-Original-Message-ID: Message-ID: Subject: Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs() To: Petr Mladek Cc: Zhen Lei , Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Joe Lawrence , Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , 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 Content-Type: text/plain; charset="UTF-8" Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org On Wed, Jan 4, 2023 at 8:25 AM 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. 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 [...]