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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <CAErzpms9K8h=76K9=SK_BmhR4hYetrztFpuQ8h8Q4HSZPguUng@mail.gmail.com>
Date: Tue, 9 Dec 2025 11:21:54 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: ast@...nel.org, andrii.nakryiko@...il.com
Cc: eddyz87@...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 Mon, Dec 8, 2025 at 2:24 PM Donglin Peng <dolinux.peng@...il.com> 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);
> +       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);

I think there is no need to check sorting here, because the BTF in this
code path is generated by the compiler. We only need to cover the cases
of vmlinux and kernel module 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;
>
> --
> 2.34.1
>