| 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
| ||
|
Message-Id: <20ace4a32dae5b4dcac499d8cb78ac5cab73d75a69b07b67113b7fbbb6e5ef45@mail.kernel.org>
Date: Thu, 6 Nov 2025 13:40:02 +0000 (UTC)
From: bot+bpf-ci@...nel.org
To: dolinux.peng@...il.com,ast@...nel.org
Cc: eddyz87@...il.com,andrii.nakryiko@...il.com,zhangxiaoqin@...omi.com,linux-kernel@...r.kernel.org,bpf@...r.kernel.org,dolinux.peng@...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: [PATCH v5 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 97451a929..30be62ee2 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -26,6 +26,10 @@
>
> #define BTF_MAX_NR_TYPES 0x7fffffffU
> #define BTF_MAX_STR_OFFSET 0x7fffffffU
> +/*
> + * sort verification occurs lazily upon first btf_find_type_by_name_kind() call
> + */
> +#define BTF_NEED_SORT_CHECK ((__u32)-1)
[ ... ]
> @@ -92,6 +96,16 @@ 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.
> + * - BTF_NEED_SORT_CHECK value indicates sort validation will be performed
> + * on first call to btf_find_type_by_name_kind.
> + * - zero value indicates applied sorting check with unsorted BTF or no
> + * named types.
> + */
> + __u32 nr_sorted_types;
[ ... ]
> @@ -897,44 +911,126 @@ 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)
> +/* Performs binary search within specified type ID range to find the leftmost
> + * BTF type matching the given name. The search assumes types are sorted by
> + * name in lexicographical order within the specified range.
> + *
> + * Return: Type ID of leftmost matching type, or -ENOENT if not found
> + */
> +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, 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__str_by_offset(btf, t->name_off);
> + ret = strcmp(tname, name);
> ^^^^^^
Can strcmp receive a NULL tname here? Anonymous types have name_off=0,
and btf__str_by_offset() can return NULL for invalid offsets. The old
btf__find_by_name() checked "if (name && !strcmp(...))" before calling
strcmp.
> + if (ret < 0) {
> + l = m + 1;
> + } else {
> + if (ret == 0)
> + lmost = m;
> + r = m - 1;
> + }
> + }
> +
> + return lmost;
> +}
> +
> +/* Searches for a BTF type by name and optionally by kind. The function first
> + * checks if the search should start from the base BTF (if @start_id is before
> + * current BTF's start_id). If types are sorted, it uses binary search to find
> + * the leftmost matching type and then verifies the kind. For unsorted types,
> + * it falls back to linear search through all types.
> + *
> + * The function handles split BTF scenarios by recursively searching in base
> + * BTFs when necessary. When @kind is -1, only the name matching is performed.
> + *
> + * Return: Type ID of matching type on success, -ENOENT if not found
> + */
> +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 != BTF_NEED_SORT_CHECK) {
Where is nr_sorted_types updated from BTF_NEED_SORT_CHECK? I only see
three assignments in the entire file:
btf_new_empty(): btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
btf_new(): btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
btf_invalidate_raw_data(): btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
The comment claims "sort verification occurs lazily upon first
btf_find_type_by_name_kind() call" but this function never updates
nr_sorted_types. Does this mean the binary search path never executes?
> + /* binary search */
> + __s32 end_id;
> + bool skip_first;
> + int ret;
> +
> + end_id = btf->start_id + btf->nr_sorted_types - 1;
> + ret = btf_find_type_by_name_bsearch(btf, type_name, start_id, end_id);
> + if (ret < 0)
> + goto out;
> + if (kind == -1)
> + return ret;
> + skip_first = true;
> + do {
> + t = btf_type_by_id(btf, ret);
> + if (BTF_INFO_KIND(t->info) != kind) {
> + if (skip_first) {
> + skip_first = false;
> + continue;
> + }
> + } else if (skip_first) {
> + return ret;
> + }
> + tname = btf__str_by_offset(btf, t->name_off);
> + if (!strcmp(tname, type_name))
> ^^^^^^
Same NULL dereference concern here - tname isn't checked before strcmp.
> + return ret;
> + else
> + break;
> + } while (++ret <= end_id);
> + } else {
> + /* linear search */
> + __u32 i, total;
>
> - if (!strcmp(type_name, "void"))
> - return 0;
> -
> - for (i = 1; i < nr_types; i++) {
> - const struct btf_type *t = btf__type_by_id(btf, i);
> - const char *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))
> + return i;
> + }
> }
>
> - return libbpf_err(-ENOENT);
> +out:
> + return err;
> }
[ ... ]
> @@ -1006,6 +1102,7 @@ static struct btf *btf_new_empty(struct btf *base_btf)
> btf->fd = -1;
> btf->ptr_sz = sizeof(void *);
> btf->swapped_endian = false;
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
>
> if (base_btf) {
> btf->base_btf = base_btf;
[ ... ]
> @@ -1057,6 +1154,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b
> btf->start_id = 1;
> btf->start_str_off = 0;
> btf->fd = -1;
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
>
> if (base_btf) {
> btf->base_btf = base_btf;
[ ... ]
> @@ -1715,6 +1813,7 @@ static void btf_invalidate_raw_data(struct btf *btf)
> free(btf->raw_data_swapped);
> btf->raw_data_swapped = NULL;
> }
> + btf->nr_sorted_types = BTF_NEED_SORT_CHECK;
> }
[ ... ]
---
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/19137195500
Powered by blists - more mailing lists