| 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
| ||
|
Message-ID: <CAErzpmuqB_b9gM4JX6ACFh0oL7Ov57GF09pt0dtMm9YjY4tYXw@mail.gmail.com>
Date: Fri, 19 Dec 2025 13:07:15 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: ast@...nel.org, andrii.nakryiko@...il.com, zhangxiaoqin@...omi.com,
ihor.solodrai@...ux.dev, linux-kernel@...r.kernel.org, bpf@...r.kernel.org,
pengdonglin <pengdonglin@...omi.com>, Alan Maguire <alan.maguire@...cle.com>
Subject: Re: [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search
On Fri, Dec 19, 2025 at 5:38 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> > From: pengdonglin <pengdonglin@...omi.com>
> >
> > Improve btf_find_by_name_kind() performance by adding binary search
> > support for sorted types. Falls back to linear search for compatibility.
> >
> > Cc: Eduard Zingerman <eddyz87@...il.com>
> > Cc: Alexei Starovoitov <ast@...nel.org>
> > Cc: Andrii Nakryiko <andrii.nakryiko@...il.com>
> > Cc: Alan Maguire <alan.maguire@...cle.com>
> > Cc: Ihor Solodrai <ihor.solodrai@...ux.dev>
> > Cc: Xiaoqin Zhang <zhangxiaoqin@...omi.com>
> > Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> > ---
>
> (One nit below).
>
> Acked-by: Eduard Zingerman <eddyz87@...il.com>
>
> > kernel/bpf/btf.c | 85 +++++++++++++++++++++++++++++++++++++++++++-----
> > 1 file changed, 76 insertions(+), 9 deletions(-)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0de8fc8a0e0b..0394f0c8ef74 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -259,6 +259,7 @@ struct btf {
> > void *nohdr_data;
> > struct btf_header hdr;
> > u32 nr_types; /* includes VOID for base BTF */
> > + u32 sorted_start_id;
> > u32 types_size;
> > u32 data_size;
> > refcount_t refcnt;
> > @@ -494,6 +495,11 @@ static bool btf_type_is_modifier(const struct btf_type *t)
> > return false;
> > }
> >
> > +static int btf_start_id(const struct btf *btf)
> > +{
> > + return btf->start_id + (btf->base_btf ? 0 : 1);
> > +}
> > +
> > bool btf_type_is_void(const struct btf_type *t)
> > {
> > return t == &btf_void;
> > @@ -544,21 +550,79 @@ u32 btf_nr_types(const struct btf *btf)
> > return total;
> > }
> >
> > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> > + s32 start_id, s32 end_id)
> > +{
> > + const struct btf_type *t;
> > + const char *tname;
> > + s32 l, r, m, lmost = -ENOENT;
> > + int ret;
> > +
> > + l = start_id;
> > + r = end_id;
> > + while (l <= r) {
> > + m = l + (r - l) / 2;
> > + t = btf_type_by_id(btf, m);
> > + tname = btf_name_by_offset(btf, t->name_off);
> > + ret = strcmp(tname, name);
> > + if (ret < 0) {
> > + l = m + 1;
> > + } else {
> > + if (ret == 0)
> > + lmost = m;
> > + r = m - 1;
> > + }
> > + }
> > +
> > + return lmost;
> > +}
> > +
> > s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind)
> > {
> > + const struct btf *base_btf = btf_base_btf(btf);
> > const struct btf_type *t;
> > const char *tname;
> > - u32 i, total;
> > + s32 idx;
> >
> > - total = btf_nr_types(btf);
> > - for (i = 1; i < total; i++) {
> > - t = btf_type_by_id(btf, i);
> > - if (BTF_INFO_KIND(t->info) != kind)
> > - continue;
> > + if (base_btf) {
> > + idx = btf_find_by_name_kind(base_btf, name, kind);
> > + if (idx > 0)
> > + return idx;
> > + }
> >
> > - tname = btf_name_by_offset(btf, t->name_off);
> > - if (!strcmp(tname, name))
> > - return i;
> > + if (btf->sorted_start_id > 0 && name[0]) {
> ^^^^^^^^^^^^^^^^^^^^^^^^
> Nit: Maybe pull the is_sorted helper into this patch-set?
Thanks, will do it.
>
> > + /* skip anonymous types */
> > + s32 start_id = btf->sorted_start_id;
> > + s32 end_id = btf_nr_types(btf) - 1;
> > +
> > + idx = btf_find_by_name_bsearch(btf, name, start_id, end_id);
> > + if (idx < 0)
> > + return -ENOENT;
> > +
> > + t = btf_type_by_id(btf, idx);
> > + if (BTF_INFO_KIND(t->info) == kind)
> > + return idx;
> > +
> > + for (idx++; idx <= end_id; idx++) {
> > + t = btf_type_by_id(btf, idx);
> > + tname = btf_name_by_offset(btf, t->name_off);
> > + if (strcmp(tname, name) != 0)
> > + return -ENOENT;
> > + if (BTF_INFO_KIND(t->info) == kind)
> > + return idx;
> > + }
> > + } else {
> > + u32 i, total;
> > +
> > + total = btf_nr_types(btf);
> > + for (i = btf_start_id(btf); i < total; i++) {
> > + t = btf_type_by_id(btf, i);
> > + if (BTF_INFO_KIND(t->info) != kind)
> > + continue;
> > + tname = btf_name_by_offset(btf, t->name_off);
> > + if (strcmp(tname, name) == 0)
> > + return i;
> > + }
> > }
> >
> > return -ENOENT;
> > @@ -5791,6 +5855,7 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
> > goto errout;
> > }
> > env->btf = btf;
> > + btf->sorted_start_id = 0;
> >
> > data = kvmalloc(attr->btf_size, GFP_KERNEL | __GFP_NOWARN);
> > if (!data) {
> > @@ -6210,6 +6275,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
> > btf->data = data;
> > btf->data_size = data_size;
> > btf->kernel_btf = true;
> > + btf->sorted_start_id = 0;
> > snprintf(btf->name, sizeof(btf->name), "%s", name);
> >
> > err = btf_parse_hdr(env);
> > @@ -6327,6 +6393,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
> > btf->start_id = base_btf->nr_types;
> > btf->start_str_off = base_btf->hdr.str_len;
> > btf->kernel_btf = true;
> > + btf->sorted_start_id = 0;
> > snprintf(btf->name, sizeof(btf->name), "%s", module_name);
> >
> > btf->data = kvmemdup(data, data_size, GFP_KERNEL | __GFP_NOWARN);
Powered by blists - more mailing lists