linux-kernel - Re: [PATCH 2/3] bpf: Optimize get_modules_for

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <Y7aSyb0n4B2aCRZH@alley>
Date:   Thu, 5 Jan 2023 10:05:13 +0100
From:   Petr Mladek <pmladek@...e.com>
To:     Song Liu <song@...nel.org>
Cc:     Zhen Lei <thunder.leizhen@...wei.com>,
        Josh Poimboeuf <jpoimboe@...nel.org>,
        Jiri Kosina <jikos@...nel.org>,
        Miroslav Benes <mbenes@...e.cz>,
        Joe Lawrence <joe.lawrence@...hat.com>,
        Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        Andrii Nakryiko <andrii@...nel.org>,
        Martin KaFai Lau <martin.lau@...ux.dev>,
        Yonghong Song <yhs@...com>,
        John Fastabend <john.fastabend@...il.com>,
        KP Singh <kpsingh@...nel.org>,
        Stanislav Fomichev <sdf@...gle.com>,
        Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
        Steven Rostedt <rostedt@...dmis.org>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Mark Rutland <mark.rutland@....com>, bpf@...r.kernel.org,
        linux-trace-kernel@...r.kernel.org, live-patching@...r.kernel.org,
        linux-kernel@...r.kernel.org, Luis Chamberlain <mcgrof@...nel.org>,
        linux-modules@...r.kernel.org
Subject: Re: [PATCH 2/3] bpf: Optimize get_modules_for_addrs()

On Wed 2023-01-04 09:07:02, Song Liu wrote:
> On Wed, Jan 4, 2023 at 8:25 AM Petr Mladek <pmladek@...e.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@...wei.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