| 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: <CAErzpmsYWLBMvkW9eQqAfGOp23oThn=aXt4tqouah5NZus4rBA@mail.gmail.com>
Date: Fri, 7 Nov 2025 15:29:09 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: bot+bpf-ci@...nel.org
Cc: ast@...nel.org, eddyz87@...il.com, andrii.nakryiko@...il.com,
zhangxiaoqin@...omi.com, linux-kernel@...r.kernel.org, bpf@...r.kernel.org,
alan.maguire@...cle.com, song@...nel.org, pengdonglin@...omi.com,
andrii@...nel.org, daniel@...earbox.net, martin.lau@...nel.org,
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
On Thu, Nov 6, 2025 at 9:40 PM <bot+bpf-ci@...nel.org> wrote:
>
> > 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.
The binary search is effectively disabled in this patch since
`nr_sorted_types` starts as
`BTF_NEED_SORT_CHECK`. The actual sorting validation and name verification will
be handled by `btf_check_sorted()` in the following patch, making this
implementation
safe.
>
> > + 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?
Yes, at least in the current patch. However, in a subsequent patch,
the btf_check_sorted
function will be introduced and invoked during calls to
btf_find_type_by_name_kind.
If the BTF data is sorted, btf_check_sorted will return true, enabling
the execution of
binary search for improved lookup efficiency.
>
> > + /* 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.
Ditto.
>
> > + 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