Re: [PATCH bpf-next v10 06/13] btf: Optimize type lookup with binary search

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2025-12-18 at 19:30 +0800, Donglin Peng wrote:
> From: pengdonglin <pengdonglin@xiaomi.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@gmail.com>
> Cc: Alexei Starovoitov <ast@kernel.org>
> Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Cc: Alan Maguire <alan.maguire@oracle.com>
> Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
> Cc: Xiaoqin Zhang <zhangxiaoqin@xiaomi.com>
> Signed-off-by: pengdonglin <pengdonglin@xiaomi.com>
> ---

(One nit below).

Acked-by: Eduard Zingerman <eddyz87@gmail.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?

> +		/* 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);