Re: [PATCH bpf-next v9 04/10] libbpf: Optimize type lookup with binary search for sorted BTF

[Eduard Zingerman <eddyz87@gmail.com>]

On Mon, 2025-12-08 at 14:23 +0800, Donglin Peng wrote:

[...]

Lgtm, one question below.

>  static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id,
>  				   const char *type_name, __u32 kind)
>  {
> -	__u32 i, nr_types = btf__type_cnt(btf);
> +	const struct btf_type *t;
> +	const char *tname;
> +	__s32 idx;
> +
> +	if (start_id < btf->start_id) {
> +		idx = btf_find_by_name_kind(btf->base_btf, start_id,
> +			type_name, kind);
> +		if (idx >= 0)
> +			return idx;
> +		start_id = btf->start_id;
> +	}
>  
> -	if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void"))
> +	if (kind == BTF_KIND_UNKN || strcmp(type_name, "void") == 0)
>  		return 0;
>  
> -	for (i = start_id; i < nr_types; i++) {
> -		const struct btf_type *t = btf__type_by_id(btf, i);
> -		const char *name;
> +	if (btf->sorted_start_id > 0) {
> +		__s32 end_id = btf__type_cnt(btf) - 1;
> +
> +		/* skip anonymous types */
> +		start_id = max(start_id, btf->sorted_start_id);
> +		idx = btf_find_by_name_bsearch(btf, type_name, start_id, end_id);
> +		if (unlikely(idx < 0))
> +			return libbpf_err(-ENOENT);
> +
> +		if (unlikely(kind == -1))
> +			return idx;
> +
> +		t = btf_type_by_id(btf, idx);
> +		if (likely(BTF_INFO_KIND(t->info) == kind))
> +			return idx;
> +
> +		for (idx++; idx <= end_id; idx++) {
> +			t = btf__type_by_id(btf, idx);
> +			tname = btf__str_by_offset(btf, t->name_off);
> +			if (strcmp(tname, type_name) != 0)
> +				return libbpf_err(-ENOENT);
> +			if (btf_kind(t) == kind)
                            ^^^^^^^^^^^^^^^^^^^
                Is kind != -1 check missing here?

> +				return idx;
> +		}
> +	} else {
> +		__u32 i, total;
>  
> -		if (btf_kind(t) != kind)
> -			continue;
> -		name = btf__name_by_offset(btf, t->name_off);
> -		if (name && !strcmp(type_name, name))
> -			return i;
> +		total = btf__type_cnt(btf);
> +		for (i = start_id; i < total; i++) {
> +			t = btf_type_by_id(btf, i);
> +			if (kind != -1 && btf_kind(t) != kind)
> +				continue;
> +			tname = btf__str_by_offset(btf, t->name_off);
> +			if (tname && strcmp(tname, type_name) == 0)

Nit: no need for `tname &&` part, as we found out.

> +				return i;
> +		}
>  	}
>  
>  	return libbpf_err(-ENOENT);
>  }
>  
> +/* the kind value of -1 indicates that kind matching should be skipped */
> +__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> +{
> +	return btf_find_by_name_kind(btf, btf->start_id, type_name, -1);
> +}
> +
>  __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name,
>  				 __u32 kind)
>  {

[...]