Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33;
MIME-Version: 1.0
References: <20230909091646.420163-1-pengdonglin@sangfor.com.cn>
 <20ef8441084c9d5fd54f84987afa77eed7fe148e.camel@gmail.com> <e78dc807b54f80fd3db836df08f71c7d2fb33387.camel@gmail.com>
In-Reply-To: <e78dc807b54f80fd3db836df08f71c7d2fb33387.camel@gmail.com>
From:   Alexei Starovoitov <alexei.starovoitov@gmail.com>
Date:   Tue, 12 Sep 2023 09:40:19 -0700
Message-ID: <CAADnVQL0O_WFYcYQRig7osO0piPdOH2yHkdH0CxCfNV7NkA0Lw@mail.gmail.com>
Subject: Re: [RFC PATCH v2] bpf: Using binary search to improve the
 performance of btf_find_by_name_kind
To:     Eduard Zingerman <eddyz87@gmail.com>
Cc:     Donglin Peng <pengdonglin@sangfor.com.cn>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Alexei Starovoitov <ast@kernel.org>,
        Song Liu <song@kernel.org>, Yonghong Song <yhs@fb.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Masami Hiramatsu <mhiramat@kernel.org>, dinghui@sangfor.com.cn,
        huangcun@sangfor.com.cn, bpf <bpf@vger.kernel.org>,
        LKML <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Tue, Sep 12, 2023 at 7:19=E2=80=AFAM Eduard Zingerman <eddyz87@gmail.com=
> wrote:
>
> On Tue, 2023-09-12 at 16:51 +0300, Eduard Zingerman wrote:
> > On Sat, 2023-09-09 at 02:16 -0700, Donglin Peng wrote:
> > > Currently, we are only using the linear search method to find the typ=
e id
> > > by the name, which has a time complexity of O(n). This change involve=
s
> > > sorting the names of btf types in ascending order and using binary se=
arch,
> > > which has a time complexity of O(log(n)). This idea was inspired by t=
he
> > > following patch:
> > >
> > > 60443c88f3a8 ("kallsyms: Improve the performance of kallsyms_lookup_n=
ame()").
> > >
> > > At present, this improvement is only for searching in vmlinux's and
> > > module's BTFs, and the kind should only be BTF_KIND_FUNC or BTF_KIND_=
STRUCT.
> > >
> > > Another change is the search direction, where we search the BTF first=
 and
> > > then its base, the type id of the first matched btf_type will be retu=
rned.
> > >
> > > Here is a time-consuming result that finding all the type ids of 67,8=
19 kernel
> > > functions in vmlinux's BTF by their names:
> > >
> > > Before: 17000 ms
> > > After:     10 ms
> > >
> > > The average lookup performance has improved about 1700x at the above =
scenario.
> > >
> > > However, this change will consume more memory, for example, 67,819 ke=
rnel
> > > functions will allocate about 530KB memory.
> >
> > Hi Donglin,
> >
> > I think this is a good improvement. However, I wonder, why did you
> > choose to have a separate name map for each BTF kind?
> >
> > I did some analysis for my local testing kernel config and got such num=
bers:
> > - total number of BTF objects: 97350
> > - number of FUNC and STRUCT objects: 51597
> > - number of FUNC, STRUCT, UNION, ENUM, ENUM64, TYPEDEF, DATASEC objects=
: 56817
> >   (these are all kinds for which lookup by name might make sense)
> > - number of named objects: 54246
> > - number of name collisions:
> >   - unique names: 53985 counts
> >   - 2 objects with the same name: 129 counts
> >   - 3 objects with the same name: 3 counts
> >
> > So, it appears that having a single map for all named objects makes
> > sense and would also simplify the implementation, what do you think?
>
> Some more numbers for my config:
> - 13241 types (struct, union, typedef, enum), log2 13241 =3D 13.7
> - 43575 funcs, log2 43575 =3D 15.4
> Thus, having separate map for types vs functions might save ~1.7
> search iterations. Is this a significant slowdown in practice?

What do you propose to do in case of duplicates ?
func and struct can have the same name, but they will have two different
btf_ids. How do we store them ?
Also we might add global vars to BTF. Such request came up several times.
So we need to make sure our search approach scales to
func, struct, vars. I don't recall whether we search any other kinds.
Separate arrays for different kinds seems ok.
It's a bit of code complexity, but it's not an increase in memory.
With 13k structs and 43k funcs it's 56k * (4 + 4) that's 0.5 Mbyte
extra memory. That's quite a bit. Anything we can do to compress it?
Folks requested vmlinux BTF to be a module, so it's loaded on demand.
BTF memory consumption is a concern to many.
I think before we add these per-kind search arrays we better make
BTF optional as a module.