Re: [RFC PATCH v4 4/7] libbpf: Implement lazy sorting validation for binary search optimization

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2025-11-04 at 21:40 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Song Liu <song@kernel.org>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> Signed-off-by: Donglin Peng <dolinux.peng@gmail.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