linux-kernel - Re: [RFC PATCH v4 3/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: <1364f197cb22d16221dd90b76a10378fc5b99917f1e62c9184f9611a91357532@mail.kernel.org>
Date: Tue,  4 Nov 2025 14:15:36 +0000 (UTC)
From: bot+bpf-ci@...nel.org
To: dolinux.peng@...il.com,ast@...nel.org
Cc: linux-kernel@...r.kernel.org,bpf@...r.kernel.org,dolinux.peng@...il.com,eddyz87@...il.com,andrii.nakryiko@...il.com,alan.maguire@...cle.com,song@...nel.org,pengdonglin@...omi.com,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 v4 3/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 3bc03f7fe..5af143044 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -92,6 +92,12 @@ struct btf {
>  	 *   - for split BTF counts number of types added on top of base BTF.
>  	 */
>  	__u32 nr_types;
> +	/* number of sorted and named types in this BTF instance:
> +	 *   - doesn't include special [0] void type;
> +	 *   - for split BTF counts number of sorted and named types added on
> +	 *     top of base BTF.
> +	 */
> +	__u32 nr_sorted_types;

Where is this field initialized? I searched the entire codebase and
found no assignments to nr_sorted_types. Since struct btf is allocated
with calloc() in btf__new() and other allocation functions, this field
will always be zero.

This means the binary search optimization added below will never execute
because the check at btf_find_type_by_name_kind() tests:

    if (btf->nr_sorted_types) {
        /* binary search */
        ...
    }

With nr_sorted_types always zero, the optimization appears to be
completely non-functional in this commit.

>  	/* if not NULL, points to the base BTF on top of which the current
>  	 * split BTF is based
>  	 */

[ ... ]

> @@ -897,44 +903,134 @@ 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)
> +/*
> + * 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.
> + */
> +static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name,
> +						__s32 *left, __s32 *right)
>  {
> -	__u32 i, nr_types = btf__type_cnt(btf);
> +	const struct btf_type *t;
> +	const char *tname;
> +	__s32 l, r, m, lmost, rmost;
> +	int ret;
> +
> +	/* found the leftmost btf_type that matches */
> +	l = *left;
> +	r = *right;
> +	lmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		ret = strcmp(tname, name);

Can strcmp() crash with a NULL tname here? btf__str_by_offset() can
return NULL when offset is invalid (see line 1713 in btf.c). The old
code had a NULL check: "if (name && !strcmp(type_name, name))" and the
new linear search path also checks: "if (tname && !strcmp(tname,
type_name))", but this binary search path calls strcmp() directly.

Though currently unreachable due to nr_sorted_types being zero, if that
initialization issue is fixed, this could dereference NULL.

> +		if (ret < 0) {
> +			l = m + 1;
> +		} else {
> +			if (ret == 0)
> +				lmost = m;
> +			r = m - 1;
> +		}
> +	}
> +
> +	if (lmost == -1)
> +		return -ENOENT;
> +
> +	/* found the rightmost btf_type that matches */
> +	l = lmost;
> +	r = *right;
> +	rmost = -1;
> +	while (l <= r) {
> +		m = l + (r - l) / 2;
> +		t = btf_type_by_id(btf, m);
> +		tname = btf__str_by_offset(btf, t->name_off);
> +		ret = strcmp(tname, name);

Same potential NULL dereference issue here.

> +		if (ret <= 0) {
> +			if (ret == 0)
> +				rmost = m;
> +			l = m + 1;
> +		} else {
> +			r = m - 1;
> +		}
> +	}
> +
> +	*left = lmost;
> +	*right = rmost;
> +	return lmost;
> +}

[ ... ]


---
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/19070905166