| 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: <CAErzpmsvvi_dhiJs+Fmyy7R-gKqh3TkiuJCj4U5K6XXJyV6pJA@mail.gmail.com>
Date: Sat, 15 Jun 2024 19:49:18 +0800
From: Donglin Peng <dolinux.peng@...il.com>
To: Eduard Zingerman <eddyz87@...il.com>
Cc: ast@...nel.org, andrii <andrii@...nel.org>, alan.maguire@...cle.com,
acme@...nel.org, daniel@...earbox.net, mhiramat@...nel.org, song@...nel.org,
haoluo@...gle.com, yonghong.song@...ux.dev, bpf@...r.kernel.org,
linux-kernel@...r.kernel.org
Subject: Re: [RFC PATCH v3] bpf: Using binary search to improve the
performance of btf_find_by_name_kind
On Tue, Jun 11, 2024 at 6:13 PM Eduard Zingerman <eddyz87@...il.com> wrote:
>
> On Sat, 2024-06-08 at 07:08 -0700, Donglin Peng wrote:
>
> [...]
>
> > Changes in RFC v3:
> > - Sort the btf types during the build process in order to reduce memory usage
> > and decrease boot time.
> >
> > RFC v2:
> > - https://lore.kernel.org/all/20230909091646.420163-1-pengdonglin@sangfor.com.cn
> > ---
> > include/linux/btf.h | 1 +
> > kernel/bpf/btf.c | 160 +++++++++++++++++++++++++++++++++---
>
> I think that kernel part is in a good shape,
> please split it as a separate commit.
Okay, thanks.
>
> > tools/lib/bpf/btf.c | 195 ++++++++++++++++++++++++++++++++++++++++++++
> > 3 files changed, 345 insertions(+), 11 deletions(-)
>
> [...]
>
> > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> > index 2d0840ef599a..93c1ab677bfa 100644
>
> I'm not sure that libbpf is the best place to put this functionality,
> as there might be different kinds of orderings
> (e.g. see a fresh commit to bpftool to output stable vmlinux.h:
> 94133cf24bb3 "bpftool: Introduce btf c dump sorting").
Thanks, I think it would be better to put it into the libbpf. However, I would
also like to hear the opinions of others.
>
> I'm curious what Andrii, Alan and Arnaldo think on libbpf vs pahole
> for this feature.
>
> Also, I have a selftests build failure with this patch-set
> (and I suspect that a bunch of dedup test cases would need an update):
I appologize for the bug in my patch that caused the issue. I will fix it.
>
> $ pwd
> /home/eddy/work/bpf-next/tools/testing/selftests/bpf
> $ make -j14 test_progs
> ...
>
> GEN-SKEL [test_progs] access_map_in_map.skel.h
> Binary files /home/eddy/work/bpf-next/tools/testing/selftests/bpf/access_map_in_map.bpf.linked2.o and /home/eddy/work/bpf-next/tools/testing/selftests/bpf/access_map_in_map.bpf.linked3.o differ
> make: *** [Makefile:658: /home/eddy/work/bpf-next/tools/testing/selftests/bpf/access_map_in_map.skel.h] Error 1
> make: *** Waiting for unfinished jobs....
Sorry, I neglected to perform an ID remap for the btf_types in the BTF.ext
section. I will fix it.
>
> If this change remains in libbpf, I think it would be great to update
> btf_find_by_name_kind() to work the same way as kernel one.
Sounds good, we might do it later.
>
> > --- a/tools/lib/bpf/btf.c
> > +++ b/tools/lib/bpf/btf.c
>
> [...]
>
> > +static int btf_sort_type_by_name(struct btf *btf)
> > +{
> > + struct btf_type *bt;
> > + __u32 *new_type_offs = NULL, *new_type_offs_noname = NULL;
> > + __u32 *maps = NULL, *found_offs;
> > + void *new_types_data = NULL, *loc_data;
> > + int i, j, k, type_cnt, ret = 0, type_size;
> > + __u32 data_size;
> > +
> > + if (btf_ensure_modifiable(btf))
> > + return libbpf_err(-ENOMEM);
> > +
> > + type_cnt = btf->nr_types;
> > + data_size = btf->type_offs_cap * sizeof(*new_type_offs);
> > +
> > + maps = (__u32 *)malloc(type_cnt * sizeof(__u32));
> > + if (!maps) {
> > + ret = -ENOMEM;
> > + goto err_out;
> > + }
> > +
> > + new_type_offs = (__u32 *)malloc(data_size);
> > + if (!new_type_offs) {
> > + ret = -ENOMEM;
> > + goto err_out;
> > + }
> > +
> > + new_type_offs_noname = (__u32 *)malloc(data_size);
> > + if (!new_type_offs_noname) {
> > + ret = -ENOMEM;
> > + goto err_out;
> > + }
>
> What is the point of separating offsets in new_type_offs vs
> new_type_offs_noname? It should be possible to use a single offsets
> array and have a comparison function that puts all named types before
> unnamed.
Great, you are right.
>
> > +
> > + new_types_data = malloc(btf->types_data_cap);
> > + if (!new_types_data) {
> > + ret = -ENOMEM;
> > + goto err_out;
> > + }
> > +
> > + memset(new_type_offs, 0, data_size);
> > +
> > + for (i = 0, j = 0, k = 0; i < type_cnt; i++) {
> > + const char *name;
> > +
> > + bt = (struct btf_type *)(btf->types_data + btf->type_offs[i]);
> > + name = btf__str_by_offset(btf, bt->name_off);
> > + if (!name || !name[0])
> > + new_type_offs_noname[k++] = btf->type_offs[i];
> > + else
> > + new_type_offs[j++] = btf->type_offs[i];
> > + }
> > +
> > + memmove(new_type_offs + j, new_type_offs_noname, sizeof(__u32) * k);
> > +
> > + qsort_r(new_type_offs, j, sizeof(*new_type_offs),
> > + btf_compare_type_name, btf);
> > +
> > + for (i = 0; i < type_cnt; i++) {
> > + found_offs = bsearch(&new_type_offs[i], btf->type_offs, type_cnt,
> > + sizeof(__u32), btf_compare_offs);
> > + if (!found_offs) {
> > + ret = -EINVAL;
> > + goto err_out;
> > + }
> > + maps[found_offs - btf->type_offs] = i;
> > + }
> > +
> > + loc_data = new_types_data;
> > + for (i = 0; i < type_cnt; i++, loc_data += type_size) {
> > + bt = (struct btf_type *)(btf->types_data + new_type_offs[i]);
> > + type_size = btf_type_size(bt);
> > + if (type_size < 0) {
> > + ret = type_size;
> > + goto err_out;
> > + }
> > +
> > + memcpy(loc_data, bt, type_size);
> > +
> > + bt = (struct btf_type *)loc_data;
> > + switch (btf_kind(bt)) {
>
> Please take a look at btf_dedup_remap_types(): it uses newly added
> iterator interface to enumerate all ID references in the type.
> It could be used here to avoid enumerating every BTF kind.
> Also, the d->hypot_map could be used instead of `maps`.
> And if so, I think that it should be possible to put this pass before
> btf_dedup_remap_types() in order for it to do the remapping.
Thank you. I will revise the code.
>
> Alternatively, it might make sense to merge this pass with
> btf_dedup_compact_types() in order to minimize number of operations,
> e.g. as in my crude attempt:
> https://github.com/eddyz87/bpf/tree/binsort-btf-dedup
Thank you. I would refer to your patch.
> (fails with similar selftests issue).
In addition to the bug in my patch, I have also identified a bug in
linker_fixup_btf
in the libbpf. After resolving the issue, the selftests successfully
passed, and I will
create a new patch to address the bug.
>
> > + case BTF_KIND_PTR:
> > + case BTF_KIND_CONST:
> > + case BTF_KIND_VOLATILE:
> > + case BTF_KIND_RESTRICT:
> > + case BTF_KIND_TYPEDEF:
> > + case BTF_KIND_TYPE_TAG:
> > + case BTF_KIND_FUNC:
> > + case BTF_KIND_VAR:
> > + case BTF_KIND_DECL_TAG:
> > + bt->type = btf_get_mapped_type(btf, maps, bt->type);
> > + break;
>
> [...]
Powered by blists - more mailing lists