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

[Eduard Zingerman <eddyz87@gmail.com>]

On Tue, 2025-12-16 at 15:38 -0800, Eduard Zingerman wrote:
> 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) {
            ^^^^^^^^^^^^^^^^^^^^^^^^
Also, previous implementation worked for anonymous types, but this one
will not work because of the 'max(start_id, btf->sorted_start_id)', right?
Maybe check that type is not anonymous in the condition above?

> > +		__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)
> >  {
> 
> [...]