| 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: <123fde84e56aaa2dcccc16a2eac00d0e28a0823e.camel@gmail.com>
Date: Tue, 04 Nov 2025 16:29:21 -0800
From: Eduard Zingerman <eddyz87@...il.com>
To: Donglin Peng <dolinux.peng@...il.com>, ast@...nel.org
Cc: linux-kernel@...r.kernel.org, bpf@...r.kernel.org, Andrii Nakryiko
<andrii.nakryiko@...il.com>, Alan Maguire <alan.maguire@...cle.com>, Song
Liu <song@...nel.org>, pengdonglin <pengdonglin@...omi.com>
Subject: Re: [RFC PATCH v4 4/7] libbpf: Implement lazy sorting validation
for binary search optimization
On Tue, 2025-11-04 at 21:40 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@...omi.com>
>
> This patch adds lazy validation of BTF type ordering to determine if types
> are sorted by name. The check is performed on first access and cached,
> enabling efficient binary search for sorted BTF while maintaining linear
> search fallback for unsorted cases.
>
> 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: Song Liu <song@...nel.org>
> Signed-off-by: pengdonglin <pengdonglin@...omi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@...il.com>
> ---
> tools/lib/bpf/btf.c | 76 +++++++++++++++++++++++++++++++++++++++++++--
> 1 file changed, 74 insertions(+), 2 deletions(-)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 5af14304409c..0ee00cec5c05 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -26,6 +26,10 @@
>
> #define BTF_MAX_NR_TYPES 0x7fffffffU
> #define BTF_MAX_STR_OFFSET 0x7fffffffU
> +/* sort verification occurs lazily upon first btf_find_type_by_name_kind()
> + * call
> + */
> +#define BTF_NEED_SORT_CHECK ((__u32)-1)
>
> static struct btf_type btf_void;
>
> @@ -96,6 +100,10 @@ struct btf {
> * - doesn't include special [0] void type;
> * - for split BTF counts number of sorted and named types added on
> * top of base BTF.
> + * - BTF_NEED_SORT_CHECK value indicates sort validation will be performed
> + * on first call to btf_find_type_by_name_kind.
> + * - zero value indicates applied sorting check with unsorted BTF or no
> + * named types.
And this can be another flag.
> */
> __u32 nr_sorted_types;
> /* if not NULL, points to the base BTF on top of which the current
> @@ -903,8 +911,67 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
> return type_id;
> }
>
> -/*
> - * Find BTF types with matching names within the [left, right] index range.
> +static int btf_compare_type_names(const void *a, const void *b, void *priv)
> +{
> + struct btf *btf = (struct btf *)priv;
> + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a);
> + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b);
> + const char *na, *nb;
> + bool anon_a, anon_b;
> +
> + na = btf__str_by_offset(btf, ta->name_off);
> + nb = btf__str_by_offset(btf, tb->name_off);
> + anon_a = str_is_empty(na);
> + anon_b = str_is_empty(nb);
> +
> + if (anon_a && !anon_b)
> + return 1;
> + if (!anon_a && anon_b)
> + return -1;
> + if (anon_a && anon_b)
> + return 0;
> +
> + return strcmp(na, nb);
> +}
> +
> +/* Verifies BTF type ordering by name and counts named types.
> + *
> + * Checks that types are sorted in ascending order with named types
> + * before anonymous ones. If verified, sets nr_sorted_types to the
> + * number of named types.
> + */
> +static void btf_check_sorted(struct btf *btf, int start_id)
> +{
> + const struct btf_type *t;
> + int i, n, nr_sorted_types;
> +
> + if (likely(btf->nr_sorted_types != BTF_NEED_SORT_CHECK))
> + return;
> + btf->nr_sorted_types = 0;
> +
> + if (btf->nr_types < 2)
> + return;
> +
> + nr_sorted_types = 0;
> + n = btf__type_cnt(btf);
> + for (n--, i = start_id; i < n; i++) {
^^^
why not -1 one line before?
> + int k = i + 1;
> +
> + if (btf_compare_type_names(&i, &k, btf) > 0)
> + return;
> + t = btf_type_by_id(btf, k);
> + if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
> + nr_sorted_types++;
> + }
> +
> + t = btf_type_by_id(btf, start_id);
> + if (!str_is_empty(btf__str_by_offset(btf, t->name_off)))
> + nr_sorted_types++;
> + if (nr_sorted_types)
> + btf->nr_sorted_types = nr_sorted_types;
I think that maintaining nr_sorted_types only for named types is an
unnecessary complication. Binary search will skip those anyway,
probably in one iteration.
> +}
> +
> +/* Find BTF types with matching names within the [left, right] index range.
> * On success, updates *left and *right to the boundaries of the matching range
> * and returns the leftmost matching index.
> */
> @@ -978,6 +1045,8 @@ static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> }
>
> if (err == -ENOENT) {
> + btf_check_sorted((struct btf *)btf, btf->start_id);
> +
> if (btf->nr_sorted_types) {
> /* binary search */
> __s32 l, r;
> @@ -1102,6 +1171,7 @@ static struct btf *btf_new_empty(struct btf *base_btf)
> btf->fd = -1;
> btf->ptr_sz = sizeof(void *);
> btf->swapped_endian = false;
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
>
> if (base_btf) {
> btf->base_btf = base_btf;
> @@ -1153,6 +1223,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
> btf->start_id = 1;
> btf->start_str_off = 0;
> btf->fd = -1;
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
>
> if (base_btf) {
> btf->base_btf = base_btf;
> @@ -1811,6 +1882,7 @@ static void btf_invalidate_raw_data(struct btf *btf)
> free(btf->raw_data_swapped);
> btf->raw_data_swapped = NULL;
> }
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
> }
>
> /* Ensure BTF is ready to be modified (by splitting into a three memory
Powered by blists - more mailing lists