linux-kernel - Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <fac834d1e096215cef3e1211d329e92b2e5eb1efe2c3f06881fc051ecafd743d@mail.kernel.org>
Date: Wed, 19 Nov 2025 04:11:44 +0000 (UTC)
From: bot+bpf-ci@...nel.org
To: dolinux.peng@...il.com,ast@...nel.org,andrii.nakryiko@...il.com
Cc: eddyz87@...il.com,zhangxiaoqin@...omi.com,linux-kernel@...r.kernel.org,bpf@...r.kernel.org,pengdonglin@...omi.com,alan.maguire@...cle.com,song@...nel.org,ast@...nel.org,andrii@...nel.org,daniel@...earbox.net,martin.lau@...nel.org,eddyz87@...il.com,yonghong.song@...ux.dev,clm@...a.com,ihor.solodrai@...ux.dev
Subject: Re: [RFC PATCH v7 4/7] libbpf: Optimize type lookup with binary search for sorted BTF

> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 71d464690..555703b37 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c

[ ... ]

> @@ -897,44 +903,93 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id)
>  	return type_id;
>  }
>
> -__s32 btf__find_by_name(const struct btf *btf, const char *type_name)
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +						__s32 start_id, __s32 end_id)
>  {
> -	__u32 i, nr_types = btf__type_cnt(btf);
> +	const struct btf_type *t;
> +	const char *tname;
> +	__s32 l, r, m;
> +
> +	l = start_id;
> +	r = end_id;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		if (strcmp(tname, name) >= 0) {
                    ^^^^^^
Can strcmp() handle a NULL tname here? The btf__str_by_offset()
function returns NULL when offset is out of range (line 1674 returns
"errno = EINVAL, NULL"), but strcmp() requires non-NULL arguments.

The original linear search code at line 971 checks "if (tname &&
!strcmp(tname, type_name))" before calling strcmp(). Should the binary
search path also check for NULL?

> +			if (l == r)
> +				return r;
> +			r = m;
> +		} else {
> +			l = m + 1;
> +		}
> +	}
> +
> +	return btf__type_cnt(btf);
> +}
> +
> +static __s32 btf_find_type_by_name_kind(const struct btf *btf, int start_id,
> +				   const char *type_name, __u32 kind)
> +{
> +	const struct btf_type *t;
> +	const char *tname;
> +	int err = -ENOENT;
> +
> +	if (start_id < btf->start_id) {
> +		err = btf_find_type_by_name_kind(btf->base_btf, start_id,
> +			type_name, kind);
> +		if (err > 0)
> +			goto out;
> +		start_id = btf->start_id;
> +	}
> +
> +	if (btf->nr_sorted_types > 0) {
> +		/* binary search */
> +		__s32 end_id;
> +		int idx;
> +
> +		end_id = btf->start_id + btf->nr_sorted_types - 1;
> +		idx = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> +		for (; 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))
                            ^^^^^^
Same question here - can tname be NULL at this point?

> +				goto out;
> +			if (kind == -1 || btf_kind(t) == kind)
> +				return idx;
> +		}
> +	} else {
> +		/* linear search */
> +		__u32 i, total;
> +
> +		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))
> +				return i;
> +		}
> +	}

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/19488781158