linux-kernel - Re: [PATCH bpf-next v9 07/10] btf: Verify BTF Sorting

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 for Android: free password hash cracker in your pocket

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

Message-ID: <CAErzpmvhMwKLT4r-MTMiqe3TVyc2ttdsndpVhbM1eLzRCiZOtg@mail.gmail.com>
Date: Wed, 17 Dec 2025 11:26:47 +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 v9 07/10] btf: Verify BTF Sorting

On Wed, Dec 17, 2025 at 8:48 AM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Mon, 2025-12-08 at 14:23 +0800, Donglin Peng wrote:
> > From: pengdonglin <pengdonglin@...omi.com>
> >
> > This patch checks whether the BTF is sorted by name in ascending order.
> > If sorted, binary search will be used when looking up types.
> >
> > Specifically, vmlinux and kernel module BTFs are always sorted during
> > the build phase with anonymous types placed before named types, so we
> > only need to identify the starting ID of named types.
> >
> > 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>
> > ---
> >  kernel/bpf/btf.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 58 insertions(+)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 842f9c0200e4..925cb524f3a8 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -550,6 +550,60 @@ u32 btf_nr_types(const struct btf *btf)
> >       return total;
> >  }
> >
> > +/*
> > + * Assuming that types are sorted by name in ascending order.
> > + */
> > +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> > +{
> > +     struct btf *btf = (struct btf *)priv;
> > +     const struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> > +     const struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> > +     const char *na, *nb;
> > +
> > +     na = btf_name_by_offset(btf, ta->name_off);
> > +     nb = btf_name_by_offset(btf, tb->name_off);
> > +     return strcmp(na, nb);
> > +}
> > +
> > +/* Note that vmlinux and kernel module BTFs are always sorted
> > + * during the building phase.
> > + */
> > +static void btf_check_sorted(struct btf *btf)
> > +{
> > +     const struct btf_type *t;
> > +     bool skip_cmp = btf_is_kernel(btf);
>
> Nit: maybe just do a separate loop when btf_is_kernel(btf) == true?

Thanks, I agree and it will make the code much cleaner.

>
>   for (i = 0, n = btf_nr_types(btf); i < n, i++) {
>     t = btf_type_by_id(btf, i);
>     if (t->name_off) {
>       btf->sorted_start_id = i;
>       return;
>     }
>   }
>   return;
>
> > +     u32 sorted_start_id = 0;
> > +     int i, n, k = 0;
> > +
> > +     if (btf->nr_types < 2)
> > +             return;
> > +
> > +     n = btf_nr_types(btf) - 1;
> > +     for (i = btf_start_id(btf); i < n; i++) {
> > +             k = i + 1;
> > +             if (!skip_cmp &&
> > +                     btf_compare_type_names(&i, &k, btf) > 0)
> > +                     return;
> > +
> > +             if (sorted_start_id == 0) {
> > +                     t = btf_type_by_id(btf, i);
> > +                     if (t->name_off) {
> > +                             sorted_start_id = i;
> > +                             if (skip_cmp)
> > +                                     break;
> > +                     }
> > +             }
> > +     }
> > +
> > +     if (sorted_start_id == 0) {
> > +             t = btf_type_by_id(btf, k);
> > +             if (t->name_off)
> > +                     sorted_start_id = k;
> > +     }
> > +     if (sorted_start_id)
> > +             btf->sorted_start_id = sorted_start_id;
> > +}
> > +
> >  static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name,
> >                                   s32 start_id, s32 end_id)
> >  {
> > @@ -5889,6 +5943,8 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr, u32 uat
> >       if (err)
> >               goto errout;
> >
> > +     btf_check_sorted(btf);
> > +
> >       struct_meta_tab = btf_parse_struct_metas(&env->log, btf);
> >       if (IS_ERR(struct_meta_tab)) {
> >               err = PTR_ERR(struct_meta_tab);
> > @@ -6296,6 +6352,7 @@ static struct btf *btf_parse_base(struct btf_verifier_env *env, const char *name
> >       if (err)
> >               goto errout;
> >
> > +     btf_check_sorted(btf);
> >       refcount_set(&btf->refcnt, 1);
> >
> >       return btf;
> > @@ -6430,6 +6487,7 @@ static struct btf *btf_parse_module(const char *module_name, const void *data,
> >       }
> >
> >       btf_verifier_env_free(env);
> > +     btf_check_sorted(btf);
> >       refcount_set(&btf->refcnt, 1);
> >       return btf;
> >