| Message ID | 20241029002208.1947947-1-dolinux.peng@gmail.com |
|---|---|
| Headers | show |
| Series | bpf: Using binary search to improve the performance of btf_find_by_name_kind | expand |
On Wed, Oct 30, 2024 at 5:58 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > To enhance the searching performance of btf_find_by_name_kind, we > > can sort the btf_types in ascending order based on their names. > > This allows us to implement a binary search method. > > > > Co-developed-by: Eduard Zingerman <eddyz87@gmail.com> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > --- > > v4: > > - Divide the patch into two parts: kernel and libbpf > > - Use Eduard's code to sort btf_types in the btf__dedup function > > - Correct some btf testcases due to modifications of the order of btf_types. > > --- > > tools/lib/bpf/btf.c | 115 +++++-- > > tools/testing/selftests/bpf/prog_tests/btf.c | 296 +++++++++--------- > > .../bpf/prog_tests/btf_dedup_split.c | 64 ++-- > > 3 files changed, 268 insertions(+), 207 deletions(-) > > > > I don't think we should do any extra sorting by default. Maybe we need > some extra API to explicitly re-sort underlying types. But then again, How do you feel about adding a new feature to the '--btf_features' option, which could be used to control sorting? > why just by type name? What if type names are equal, what do we use to > disambiguate. None of this is considered in this patch. If there are multiple btf_types with identical names in a btf file, they will have different kinds. These btf_types will be grouped together after being sorted according to their names. We can determine the range of the group and verify the btf_types within that range by their kind to obtain the appropriate btf_type. > > pw-bot: cr > > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c > > index 3c131039c523..5290e9d59997 100644 > > --- a/tools/lib/bpf/btf.c > > +++ b/tools/lib/bpf/btf.c > > @@ -1,6 +1,9 @@ > > // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) > > /* Copyright (c) 2018 Facebook */ > > > > +#ifndef _GNU_SOURCE > > +#define _GNU_SOURCE > > +#endif > > #include <byteswap.h> > > #include <endian.h> > > #include <stdio.h> > > @@ -4902,6 +4905,49 @@ static int btf_dedup_resolve_fwds(struct btf_dedup *d) > > return err; > > } > > > > +/* compare btf types by name, consider named < anonymous */ > > +static int btf_compare_type_names(const void *a, const void *b, void *priv) > > +{ > > + struct btf *btf = (struct btf *)priv; > > + struct btf_type *ta = btf_type_by_id(btf, *(__u32 *)a); > > + struct btf_type *tb = btf_type_by_id(btf, *(__u32 *)b); > > + const char *na, *nb; > > + > > + /* ta w/o name is greater than tb */ > > + if (!ta->name_off && tb->name_off) > > + return 1; > > + /* tb w/o name is smaller than ta */ > > + if (ta->name_off && !tb->name_off) > > + return -1; > > + > > + na = btf__str_by_offset(btf, ta->name_off); > > + nb = btf__str_by_offset(btf, tb->name_off); > > + return strcmp(na, nb); > > +} > > + > > +static __u32 *get_sorted_canon_types(struct btf_dedup *d, __u32 *cnt) > > +{ > > + int i, j, id, types_cnt = 0; > > + __u32 *sorted_ids; > > + > > + for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) > > + if (d->map[id] == id) > > + ++types_cnt; > > + > > + sorted_ids = calloc(types_cnt, sizeof(*sorted_ids)); > > + if (!sorted_ids) > > + return NULL; > > + > > + for (j = 0, i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) > > + if (d->map[id] == id) > > + sorted_ids[j++] = id; > > + qsort_r(sorted_ids, types_cnt, sizeof(*sorted_ids), > > + btf_compare_type_names, d->btf); > > + *cnt = types_cnt; > > + > > + return sorted_ids; > > +} > > + > > /* > > * Compact types. > > * > > @@ -4915,11 +4961,11 @@ static int btf_dedup_resolve_fwds(struct btf_dedup *d) > > */ > > static int btf_dedup_compact_types(struct btf_dedup *d) > > { > > - __u32 *new_offs; > > - __u32 next_type_id = d->btf->start_id; > > + __u32 canon_types_cnt = 0, canon_types_len = 0; > > + __u32 *new_offs = NULL, *canon_types = NULL; > > const struct btf_type *t; > > - void *p; > > - int i, id, len; > > + void *p, *new_types = NULL; > > + int i, id, len, err; > > > > /* we are going to reuse hypot_map to store compaction remapping */ > > d->hypot_map[0] = 0; > > @@ -4929,36 +4975,61 @@ static int btf_dedup_compact_types(struct btf_dedup *d) > > for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) > > d->hypot_map[id] = BTF_UNPROCESSED_ID; > > > > - p = d->btf->types_data; > > - > > - for (i = 0, id = d->btf->start_id; i < d->btf->nr_types; i++, id++) { > > - if (d->map[id] != id) > > - continue; > > + canon_types = get_sorted_canon_types(d, &canon_types_cnt); > > + if (!canon_types) { > > + err = -ENOMEM; > > + goto out_err; > > + } > > > > + for (i = 0; i < canon_types_cnt; i++) { > > + id = canon_types[i]; > > t = btf__type_by_id(d->btf, id); > > len = btf_type_size(t); > > - if (len < 0) > > - return len; > > + if (len < 0) { > > + err = len; > > + goto out_err; > > + } > > + canon_types_len += len; > > + } > > + > > + new_offs = calloc(canon_types_cnt, sizeof(*new_offs)); > > + new_types = calloc(canon_types_len, 1); > > + if (!new_types || !new_offs) { > > + err = -ENOMEM; > > + goto out_err; > > + } > > > > - memmove(p, t, len); > > - d->hypot_map[id] = next_type_id; > > - d->btf->type_offs[next_type_id - d->btf->start_id] = p - d->btf->types_data; > > + p = new_types; > > + > > + for (i = 0; i < canon_types_cnt; i++) { > > + id = canon_types[i]; > > + t = btf__type_by_id(d->btf, id); > > + len = btf_type_size(t); > > + memcpy(p, t, len); > > + d->hypot_map[id] = d->btf->start_id + i; > > + new_offs[i] = p - new_types; > > p += len; > > - next_type_id++; > > } > > > > /* shrink struct btf's internal types index and update btf_header */ > > - d->btf->nr_types = next_type_id - d->btf->start_id; > > - d->btf->type_offs_cap = d->btf->nr_types; > > - d->btf->hdr->type_len = p - d->btf->types_data; > > - new_offs = libbpf_reallocarray(d->btf->type_offs, d->btf->type_offs_cap, > > - sizeof(*new_offs)); > > - if (d->btf->type_offs_cap && !new_offs) > > - return -ENOMEM; > > + free(d->btf->types_data); > > + free(d->btf->type_offs); > > + d->btf->types_data = new_types; > > d->btf->type_offs = new_offs; > > + d->btf->types_data_cap = canon_types_len; > > + d->btf->type_offs_cap = canon_types_cnt; > > + d->btf->nr_types = canon_types_cnt; > > + d->btf->hdr->type_len = canon_types_len; > > d->btf->hdr->str_off = d->btf->hdr->type_len; > > d->btf->raw_size = d->btf->hdr->hdr_len + d->btf->hdr->type_len + d->btf->hdr->str_len; > > + free(canon_types); > > return 0; > > + > > +out_err: > > + free(canon_types); > > + free(new_types); > > + free(new_offs); > > + return err; > > } > > > > /* > > diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c > > index e63d74ce046f..4dc1e2bfacbb 100644 > > --- a/tools/testing/selftests/bpf/prog_tests/btf.c > > +++ b/tools/testing/selftests/bpf/prog_tests/btf.c > > @@ -7025,26 +7025,26 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(7), 4), /* [1] */ > > /* int */ > > - BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - /* int[16] */ > > - BTF_TYPE_ARRAY_ENC(1, 1, 16), /* [2] */ > > + BTF_TYPE_INT_ENC(NAME_NTH(5), BTF_INT_SIGNED, 0, 32, 4), /* [2] */ > > /* struct s { */ > > BTF_STRUCT_ENC(NAME_NTH(8), 5, 88), /* [3] */ > > - BTF_MEMBER_ENC(NAME_NTH(7), 4, 0), /* struct s *next; */ > > - BTF_MEMBER_ENC(NAME_NTH(1), 5, 64), /* const int *a; */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 128), /* int b[16]; */ > > - BTF_MEMBER_ENC(NAME_NTH(3), 1, 640), /* int c; */ > > - BTF_MEMBER_ENC(NAME_NTH(4), 9, 672), /* float d; */ > > + BTF_MEMBER_ENC(NAME_NTH(7), 7, 0), /* struct s *next; */ > > + BTF_MEMBER_ENC(NAME_NTH(1), 8, 64), /* const int *a; */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 6, 128), /* int b[16]; */ > > + BTF_MEMBER_ENC(NAME_NTH(3), 2, 640), /* int c; */ > > + BTF_MEMBER_ENC(NAME_NTH(4), 1, 672), /* float d; */ > > + BTF_DECL_TAG_ENC(NAME_NTH(2), 3, -1), /* [4] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(2), 3, 1), /* [5] */ > > + /* int[16] */ > > + BTF_TYPE_ARRAY_ENC(1, 2, 16), /* [6] */ > > /* ptr -> [3] struct s */ > > - BTF_PTR_ENC(3), /* [4] */ > > + BTF_PTR_ENC(3), /* [7] */ > > /* ptr -> [6] const int */ > > - BTF_PTR_ENC(6), /* [5] */ > > + BTF_PTR_ENC(9), /* [8] */ > > /* const -> [1] int */ > > - BTF_CONST_ENC(1), /* [6] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(2), 3, -1), /* [7] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(2), 3, 1), /* [8] */ > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(7), 4), /* [9] */ > > + BTF_CONST_ENC(2), /* [9] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0a\0b\0c\0d\0int\0float\0next\0s"), > > @@ -7082,10 +7082,10 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_PTR_ENC(3), /* [1] ptr -> [3] */ > > - BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [2] struct s */ > > - BTF_MEMBER_ENC(NAME_TBD, 1, 0), > > - BTF_STRUCT_ENC(NAME_NTH(2), 0, 0), /* [3] struct x */ > > + BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [1] struct s */ > > + BTF_MEMBER_ENC(NAME_TBD, 3, 0), > > + BTF_STRUCT_ENC(NAME_NTH(2), 0, 0), /* [2] struct x */ > > + BTF_PTR_ENC(2), /* [3] ptr -> [3] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0s\0x"), > > @@ -7123,15 +7123,13 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* CU 1 */ > > - BTF_STRUCT_ENC(0, 0, 1), /* [1] struct {} */ > > - BTF_PTR_ENC(1), /* [2] ptr -> [1] */ > > - BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [3] struct s */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - /* CU 2 */ > > - BTF_PTR_ENC(0), /* [4] ptr -> void */ > > - BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [5] struct s */ > > + BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [1] struct s */ > > BTF_MEMBER_ENC(NAME_NTH(2), 4, 0), > > + BTF_STRUCT_ENC(NAME_NTH(1), 1, 8), /* [2] struct s */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), > > + BTF_STRUCT_ENC(0, 0, 1), /* [3] struct {} */ > > + BTF_PTR_ENC(3), /* [5] ptr -> [1] */ > > + BTF_PTR_ENC(0), /* [4] ptr -> void */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0s\0x"), > > @@ -7182,28 +7180,28 @@ static struct btf_dedup_test dedup_tests[] = { > > BTF_ENUM_ENC(NAME_TBD, 0), > > BTF_ENUM_ENC(NAME_TBD, 1), > > BTF_FWD_ENC(NAME_TBD, 1 /* union kind_flag */), /* [3] fwd */ > > - BTF_TYPE_ARRAY_ENC(2, 1, 7), /* [4] array */ > > - BTF_STRUCT_ENC(NAME_TBD, 1, 4), /* [5] struct */ > > + BTF_STRUCT_ENC(NAME_TBD, 1, 4), /* [4] struct */ > > BTF_MEMBER_ENC(NAME_TBD, 1, 0), > > - BTF_UNION_ENC(NAME_TBD, 1, 4), /* [6] union */ > > + BTF_UNION_ENC(NAME_TBD, 1, 4), /* [5] union */ > > BTF_MEMBER_ENC(NAME_TBD, 1, 0), > > - BTF_TYPEDEF_ENC(NAME_TBD, 1), /* [7] typedef */ > > - BTF_PTR_ENC(0), /* [8] ptr */ > > - BTF_CONST_ENC(8), /* [9] const */ > > - BTF_VOLATILE_ENC(8), /* [10] volatile */ > > - BTF_RESTRICT_ENC(8), /* [11] restrict */ > > - BTF_FUNC_PROTO_ENC(1, 2), /* [12] func_proto */ > > - BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), > > - BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 18), > > - BTF_FUNC_ENC(NAME_TBD, 12), /* [13] func */ > > - BTF_TYPE_FLOAT_ENC(NAME_TBD, 2), /* [14] float */ > > - BTF_DECL_TAG_ENC(NAME_TBD, 13, -1), /* [15] decl_tag */ > > - BTF_DECL_TAG_ENC(NAME_TBD, 13, 1), /* [16] decl_tag */ > > - BTF_DECL_TAG_ENC(NAME_TBD, 7, -1), /* [17] decl_tag */ > > - BTF_TYPE_TAG_ENC(NAME_TBD, 8), /* [18] type_tag */ > > - BTF_TYPE_ENC(NAME_TBD, BTF_INFO_ENC(BTF_KIND_ENUM64, 0, 2), 8), /* [19] enum64 */ > > + BTF_TYPEDEF_ENC(NAME_TBD, 1), /* [6] typedef */ > > + BTF_FUNC_ENC(NAME_TBD, 19), /* [7] func */ > > + BTF_TYPE_FLOAT_ENC(NAME_TBD, 2), /* [8] float */ > > + BTF_DECL_TAG_ENC(NAME_TBD, 7, -1), /* [9] decl_tag */ > > + BTF_DECL_TAG_ENC(NAME_TBD, 7, 1), /* [10] decl_tag */ > > + BTF_DECL_TAG_ENC(NAME_TBD, 6, -1), /* [11] decl_tag */ > > + BTF_TYPE_TAG_ENC(NAME_TBD, 15), /* [12] type_tag */ > > + BTF_TYPE_ENC(NAME_TBD, BTF_INFO_ENC(BTF_KIND_ENUM64, 0, 2), 8), /* [13] enum64 */ > > BTF_ENUM64_ENC(NAME_TBD, 0, 0), > > BTF_ENUM64_ENC(NAME_TBD, 1, 1), > > + BTF_TYPE_ARRAY_ENC(2, 2, 7), /* [14] array */ > > + BTF_PTR_ENC(0), /* [15] ptr */ > > + BTF_CONST_ENC(15), /* [16] const */ > > + BTF_VOLATILE_ENC(15), /* [17] volatile */ > > + BTF_RESTRICT_ENC(15), /* [18] restrict */ > > + BTF_FUNC_PROTO_ENC(1, 2), /* [19] func_proto */ > > + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 1), > > + BTF_FUNC_PROTO_ARG_ENC(NAME_TBD, 12), > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0A\0B\0C\0D\0E\0F\0G\0H\0I\0J\0K\0L\0M\0N\0O\0P\0Q\0R\0S\0T\0U"), > > @@ -7237,9 +7235,14 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > + /* all allowed sizes */ > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 2), > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 4), > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 8), > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 12), > > + BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 16), > > + > > BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 8), > > - /* different name */ > > - BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 32, 8), > > /* different encoding */ > > BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_CHAR, 0, 32, 8), > > BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_BOOL, 0, 32, 8), > > @@ -7249,12 +7252,8 @@ static struct btf_dedup_test dedup_tests[] = { > > BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 27, 8), > > /* different byte size */ > > BTF_TYPE_INT_ENC(NAME_NTH(1), BTF_INT_SIGNED, 0, 32, 4), > > - /* all allowed sizes */ > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 2), > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 4), > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 8), > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 12), > > - BTF_TYPE_FLOAT_ENC(NAME_NTH(3), 16), > > + /* different name */ > > + BTF_TYPE_INT_ENC(NAME_NTH(2), BTF_INT_SIGNED, 0, 32, 8), > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0int\0some other int\0float"), > > @@ -7323,18 +7322,18 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* int */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - /* static int t */ > > - BTF_VAR_ENC(NAME_NTH(2), 1, 0), /* [2] */ > > - /* .bss section */ /* [3] */ > > + /* .bss section */ /* [1] */ > > BTF_TYPE_ENC(NAME_NTH(1), BTF_INFO_ENC(BTF_KIND_DATASEC, 0, 1), 4), > > - BTF_VAR_SECINFO_ENC(2, 0, 4), > > - /* another static int t */ > > - BTF_VAR_ENC(NAME_NTH(2), 1, 0), /* [4] */ > > - /* another .bss section */ /* [5] */ > > + BTF_VAR_SECINFO_ENC(3, 0, 4), > > + /* another .bss section */ /* [2] */ > > BTF_TYPE_ENC(NAME_NTH(1), BTF_INFO_ENC(BTF_KIND_DATASEC, 0, 1), 4), > > BTF_VAR_SECINFO_ENC(4, 0, 4), > > + /* static int t */ > > + BTF_VAR_ENC(NAME_NTH(2), 5, 0), /* [3] */ > > + /* another static int t */ > > + BTF_VAR_ENC(NAME_NTH(2), 5, 0), /* [4] */ > > + /* int */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0.bss\0t"), > > @@ -7371,15 +7370,15 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_VAR_ENC(NAME_NTH(1), 1, 0), /* [2] */ > > - BTF_FUNC_PROTO_ENC(0, 2), /* [3] */ > > - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), > > - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 1), > > - BTF_FUNC_ENC(NAME_NTH(4), 3), /* [4] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [5] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 4, -1), /* [6] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 4, 1), /* [7] */ > > + BTF_FUNC_ENC(NAME_NTH(4), 7), /* [1] */ > > + BTF_VAR_ENC(NAME_NTH(1), 6, 0), /* [2] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [3] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [6] */ > > + BTF_FUNC_PROTO_ENC(0, 2), /* [7] */ > > + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 6), > > + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(3), 6), > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0t\0a1\0a2\0f\0tag"), > > @@ -7419,17 +7418,17 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_FUNC_PROTO_ENC(0, 2), /* [2] */ > > - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 1), > > - BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 1), > > - BTF_FUNC_ENC(NAME_NTH(3), 2), /* [3] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(4), 3, -1), /* [4] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 3, -1), /* [5] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(6), 3, -1), /* [6] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(4), 3, 1), /* [7] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 3, 1), /* [8] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(6), 3, 1), /* [9] */ > > + BTF_FUNC_ENC(NAME_NTH(3), 9), /* [1] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ > > + BTF_FUNC_PROTO_ENC(0, 2), /* [9] */ > > + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(1), 8), > > + BTF_FUNC_PROTO_ARG_ENC(NAME_NTH(2), 8), > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0a1\0a2\0f\0tag1\0tag2\0tag3"), > > @@ -7465,16 +7464,16 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [2] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 1, 0), > > - BTF_MEMBER_ENC(NAME_NTH(3), 1, 32), > > - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [3] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, -1), /* [4] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(6), 2, -1), /* [5] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, 1), /* [6] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(5), 2, 1), /* [7] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(6), 2, 1), /* [8] */ > > + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [1] */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 8, 0), > > + BTF_MEMBER_ENC(NAME_NTH(3), 8, 32), > > + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [2] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, 1), /* [3] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, -1), /* [4] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(5), 1, 1), /* [5] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, -1), /* [6] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(6), 1, 1), /* [7] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [8] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0t\0m1\0m2\0tag1\0tag2\0tag3"), > > @@ -7500,11 +7499,11 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPEDEF_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(2), 2, -1), /* [3] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(3), 2, -1), /* [4] */ > > - BTF_DECL_TAG_ENC(NAME_NTH(4), 2, -1), /* [5] */ > > + BTF_TYPEDEF_ENC(NAME_NTH(1), 5), /* [1] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(2), 1, -1), /* [2] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(3), 1, -1), /* [3] */ > > + BTF_DECL_TAG_ENC(NAME_NTH(4), 1, -1), /* [4] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0t\0tag1\0tag2\0tag3"), > > @@ -7533,12 +7532,12 @@ static struct btf_dedup_test dedup_tests[] = { > > .expect = { > > .raw_types = { > > /* ptr -> tag2 -> tag1 -> int */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ > > - BTF_PTR_ENC(3), /* [4] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [1] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [2] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ > > + BTF_PTR_ENC(2), /* [4] */ > > /* ptr -> tag1 -> int */ > > - BTF_PTR_ENC(2), /* [5] */ > > + BTF_PTR_ENC(1), /* [5] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0tag1\0tag2"), > > @@ -7563,13 +7562,13 @@ static struct btf_dedup_test dedup_tests[] = { > > .expect = { > > .raw_types = { > > /* ptr -> tag2 -> tag1 -> int */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ > > - BTF_PTR_ENC(3), /* [4] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [1] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [2] */ > > /* ptr -> tag2 -> int */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [5] */ > > - BTF_PTR_ENC(5), /* [6] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(2), 4), /* [3] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [4] */ > > + BTF_PTR_ENC(2), /* [5] */ > > + BTF_PTR_ENC(3), /* [6] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0tag1\0tag2"), > > @@ -7594,15 +7593,13 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* ptr -> tag2 -> tag1 -> int */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(2), 2), /* [3] */ > > - BTF_PTR_ENC(3), /* [4] */ > > - /* ptr -> tag1 -> tag2 -> int */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [5] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [6] */ > > - BTF_PTR_ENC(6), /* [7] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [1] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [2] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(2), 1), /* [3] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(2), 5), /* [4] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ > > + BTF_PTR_ENC(3), /* [6] */ > > + BTF_PTR_ENC(2), /* [7] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0tag1\0tag2"), > > @@ -7626,14 +7623,12 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* ptr -> tag1 -> int */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_PTR_ENC(2), /* [3] */ > > - /* ptr -> tag1 -> long */ > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 64, 8), /* [4] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 4), /* [5] */ > > - BTF_PTR_ENC(5), /* [6] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [1] */ > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 5), /* [2] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ > > + BTF_PTR_ENC(1), /* [4] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 64, 8), /* [5] */ > > + BTF_PTR_ENC(2), /* [6] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0tag1"), > > @@ -7656,10 +7651,10 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [1] */ > > - BTF_TYPE_TAG_ENC(NAME_NTH(1), 1), /* [2] */ > > - BTF_TYPE_ENC(NAME_NTH(2), BTF_INFO_ENC(BTF_KIND_STRUCT, 1, 1), 4), /* [3] */ > > + BTF_TYPE_ENC(NAME_NTH(2), BTF_INFO_ENC(BTF_KIND_STRUCT, 1, 1), 4), /* [1] */ > > BTF_MEMBER_ENC(NAME_NTH(3), 2, BTF_MEMBER_OFFSET(0, 0)), > > + BTF_TYPE_TAG_ENC(NAME_NTH(1), 3), /* [2] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0tag1\0t\0m"), > > @@ -7861,10 +7856,10 @@ static struct btf_dedup_test dedup_tests[] = { > > .expect = { > > .raw_types = { > > BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ > > - BTF_PTR_ENC(1), /* [3] */ > > - BTF_TYPEDEF_ENC(NAME_NTH(3), 3), /* [4] */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 3, 0), > > + BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [2] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ > > + BTF_PTR_ENC(1), /* [4] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0foo\0x\0foo_ptr"), > > @@ -7901,10 +7896,10 @@ static struct btf_dedup_test dedup_tests[] = { > > .expect = { > > .raw_types = { > > BTF_UNION_ENC(NAME_NTH(1), 1, 4), /* [1] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ > > - BTF_PTR_ENC(1), /* [3] */ > > - BTF_TYPEDEF_ENC(NAME_NTH(3), 3), /* [4] */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 3, 0), > > + BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [2] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [3] */ > > + BTF_PTR_ENC(1), /* [4] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0foo\0x\0foo_ptr"), > > @@ -7940,14 +7935,12 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* CU 1 */ > > BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ > > - /* CU 2 */ > > - BTF_FWD_ENC(NAME_NTH(3), 1), /* [3] */ > > - BTF_PTR_ENC(3), /* [4] */ > > - BTF_TYPEDEF_ENC(NAME_NTH(3), 4), /* [5] */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 4, 0), > > + BTF_FWD_ENC(NAME_NTH(3), 1), /* [2] */ > > + BTF_TYPEDEF_ENC(NAME_NTH(3), 5), /* [3] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [4] */ > > + BTF_PTR_ENC(2), /* [5] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0foo\0x\0foo_ptr"), > > @@ -7990,18 +7983,15 @@ static struct btf_dedup_test dedup_tests[] = { > > }, > > .expect = { > > .raw_types = { > > - /* CU 1 */ > > BTF_STRUCT_ENC(NAME_NTH(1), 1, 4), /* [1] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [2] */ > > - /* CU 2 */ > > - BTF_FWD_ENC(NAME_NTH(1), 0), /* [3] */ > > - BTF_PTR_ENC(3), /* [4] */ > > - BTF_TYPEDEF_ENC(NAME_NTH(4), 4), /* [5] */ > > - /* CU 3 */ > > - BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [6] */ > > - BTF_MEMBER_ENC(NAME_NTH(2), 2, 0), > > - BTF_MEMBER_ENC(NAME_NTH(3), 2, 0), > > + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), > > + BTF_FWD_ENC(NAME_NTH(1), 0), /* [2] */ > > + BTF_STRUCT_ENC(NAME_NTH(1), 2, 8), /* [3] */ > > + BTF_MEMBER_ENC(NAME_NTH(2), 5, 0), > > + BTF_MEMBER_ENC(NAME_NTH(3), 5, 0), > > + BTF_TYPEDEF_ENC(NAME_NTH(4), 6), /* [4] */ > > + BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */ > > + BTF_PTR_ENC(2), /* [6] */ > > BTF_END_RAW, > > }, > > BTF_STR_SEC("\0foo\0x\0y\0foo_ptr"), > > diff --git a/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c b/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c > > index d9024c7a892a..e50c290b2d8c 100644 > > --- a/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c > > +++ b/tools/testing/selftests/bpf/prog_tests/btf_dedup_split.c > > @@ -311,18 +311,18 @@ static void test_split_struct_duped() { > > "[5] STRUCT 's1' size=16 vlen=2\n" > > "\t'f1' type_id=2 bits_offset=0\n" > > "\t'f2' type_id=4 bits_offset=64", > > - "[6] PTR '(anon)' type_id=8", > > - "[7] PTR '(anon)' type_id=9", > > - "[8] STRUCT 's1' size=16 vlen=2\n" > > - "\t'f1' type_id=6 bits_offset=0\n" > > - "\t'f2' type_id=7 bits_offset=64", > > - "[9] STRUCT 's2' size=40 vlen=4\n" > > - "\t'f1' type_id=6 bits_offset=0\n" > > - "\t'f2' type_id=7 bits_offset=64\n" > > + "[6] STRUCT 's1' size=16 vlen=2\n" > > + "\t'f1' type_id=9 bits_offset=0\n" > > + "\t'f2' type_id=10 bits_offset=64", > > + "[7] STRUCT 's2' size=40 vlen=4\n" > > + "\t'f1' type_id=9 bits_offset=0\n" > > + "\t'f2' type_id=10 bits_offset=64\n" > > "\t'f3' type_id=1 bits_offset=128\n" > > - "\t'f4' type_id=8 bits_offset=192", > > - "[10] STRUCT 's3' size=8 vlen=1\n" > > - "\t'f1' type_id=7 bits_offset=0"); > > + "\t'f4' type_id=6 bits_offset=192", > > + "[8] STRUCT 's3' size=8 vlen=1\n" > > + "\t'f1' type_id=10 bits_offset=0", > > + "[9] PTR '(anon)' type_id=6", > > + "[10] PTR '(anon)' type_id=7"); > > > > cleanup: > > btf__free(btf2); > > @@ -385,13 +385,13 @@ static void test_split_dup_struct_in_cu() > > > > VALIDATE_RAW_BTF( > > btf1, > > - "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > - "[2] STRUCT 's' size=8 vlen=2\n" > > - "\t'a' type_id=3 bits_offset=0\n" > > - "\t'b' type_id=3 bits_offset=0", > > - "[3] STRUCT '(anon)' size=8 vlen=2\n" > > - "\t'f1' type_id=1 bits_offset=0\n" > > - "\t'f2' type_id=1 bits_offset=32"); > > + "[1] STRUCT '(anon)' size=8 vlen=2\n" > > + "\t'f1' type_id=2 bits_offset=0\n" > > + "\t'f2' type_id=2 bits_offset=32", > > + "[2] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > + "[3] STRUCT 's' size=8 vlen=2\n" > > + "\t'a' type_id=1 bits_offset=0\n" > > + "\t'b' type_id=1 bits_offset=0"); > > > > /* and add the same data on top of it */ > > btf2 = btf__new_empty_split(btf1); > > @@ -402,13 +402,13 @@ static void test_split_dup_struct_in_cu() > > > > VALIDATE_RAW_BTF( > > btf2, > > - "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > - "[2] STRUCT 's' size=8 vlen=2\n" > > - "\t'a' type_id=3 bits_offset=0\n" > > - "\t'b' type_id=3 bits_offset=0", > > - "[3] STRUCT '(anon)' size=8 vlen=2\n" > > - "\t'f1' type_id=1 bits_offset=0\n" > > - "\t'f2' type_id=1 bits_offset=32", > > + "[1] STRUCT '(anon)' size=8 vlen=2\n" > > + "\t'f1' type_id=2 bits_offset=0\n" > > + "\t'f2' type_id=2 bits_offset=32", > > + "[2] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > + "[3] STRUCT 's' size=8 vlen=2\n" > > + "\t'a' type_id=1 bits_offset=0\n" > > + "\t'b' type_id=1 bits_offset=0", > > "[4] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > "[5] STRUCT 's' size=8 vlen=2\n" > > "\t'a' type_id=6 bits_offset=0\n" > > @@ -427,13 +427,13 @@ static void test_split_dup_struct_in_cu() > > /* after dedup it should match the original data */ > > VALIDATE_RAW_BTF( > > btf2, > > - "[1] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > - "[2] STRUCT 's' size=8 vlen=2\n" > > - "\t'a' type_id=3 bits_offset=0\n" > > - "\t'b' type_id=3 bits_offset=0", > > - "[3] STRUCT '(anon)' size=8 vlen=2\n" > > - "\t'f1' type_id=1 bits_offset=0\n" > > - "\t'f2' type_id=1 bits_offset=32"); > > + "[1] STRUCT '(anon)' size=8 vlen=2\n" > > + "\t'f1' type_id=2 bits_offset=0\n" > > + "\t'f2' type_id=2 bits_offset=32", > > + "[2] INT 'int' size=4 bits_offset=0 nr_bits=32 encoding=SIGNED", > > + "[3] STRUCT 's' size=8 vlen=2\n" > > + "\t'a' type_id=1 bits_offset=0\n" > > + "\t'b' type_id=1 bits_offset=0"); > > > > cleanup: > > btf__free(btf2); > > -- > > 2.34.1 > >
On Wed, Oct 30, 2024 at 6:15 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > Currently, we are only using the linear search method to find the type id > > by the name, which has a time complexity of O(n). This change involves > > sorting the names of btf types in ascending order and using binary search, > > which has a time complexity of O(log(n)). > > > > Another change is the search direction, where we search the BTF first and > > then its base. > > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > --- > > tools/lib/bpf/btf.c | 159 ++++++++++++++++++++++++++++++++++++++------ > > 1 file changed, 140 insertions(+), 19 deletions(-) > > > > same complaints as with kernel-side implementation > > I'm not sure if this is the right approach, overall. I can see how > pre-sorting might be useful if done by pahole. But then I'd say we > should record some bit somewhere in btf_header claiming that this is > sorted BTF, and then if that bit is set and we confirmed (on the > kernel side) that sorting is indeed correct (and if not, reject, don't > silently ignore), then we can use that sorting to our advantage. Thank you, I also agree. we could utilize a bit of the flags within the btf_header structure to indicate if the btf file has been sorted. > > I don't think libbpf should unconditionally sort or check sorting in > the way that you implemented. > > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c > > index 5290e9d59997..cbf88a6b92e5 100644 > > --- a/tools/lib/bpf/btf.c > > +++ b/tools/lib/bpf/btf.c > > @@ -94,6 +94,10 @@ struct btf { > > * - for split BTF counts number of types added on top of base BTF. > > */ > > __u32 nr_types; > > + /* number of types in this BTF instance which are sorted by name: > > + * - doesn't include special [0] void type; > > + */ > > + __u32 nr_types_sorted; > > /* if not NULL, points to the base BTF on top of which the current > > * split BTF is based > > */ > > [...]
On Wed, Oct 30, 2024 at 8:13 AM Donglin Peng <dolinux.peng@gmail.com> wrote: > > On Wed, Oct 30, 2024 at 5:58 AM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: > > > > On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > > > To enhance the searching performance of btf_find_by_name_kind, we > > > can sort the btf_types in ascending order based on their names. > > > This allows us to implement a binary search method. > > > > > > Co-developed-by: Eduard Zingerman <eddyz87@gmail.com> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > > --- > > > v4: > > > - Divide the patch into two parts: kernel and libbpf > > > - Use Eduard's code to sort btf_types in the btf__dedup function > > > - Correct some btf testcases due to modifications of the order of btf_types. > > > --- > > > tools/lib/bpf/btf.c | 115 +++++-- > > > tools/testing/selftests/bpf/prog_tests/btf.c | 296 +++++++++--------- > > > .../bpf/prog_tests/btf_dedup_split.c | 64 ++-- > > > 3 files changed, 268 insertions(+), 207 deletions(-) > > > > > > > I don't think we should do any extra sorting by default. Maybe we need > > some extra API to explicitly re-sort underlying types. But then again, > > How do you feel about adding a new feature to the '--btf_features' option, > which could be used to control sorting? This is pahole question, and yes, having a --btf_features makes sense to me. > > > why just by type name? What if type names are equal, what do we use to > > disambiguate. None of this is considered in this patch. > > If there are multiple btf_types with identical names in a btf file, > they will have different kinds. These btf_types will be grouped Not necessarily, you can easily have types of the same kind with the same name. But this changes nothing, I'd still define fuller search criteria. > together after being sorted according to their names. We can > determine the range of the group and verify the btf_types within > that range by their kind to obtain the appropriate btf_type. > > > > > pw-bot: cr > > > > > diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c > > > index 3c131039c523..5290e9d59997 100644 > > > --- a/tools/lib/bpf/btf.c > > > +++ b/tools/lib/bpf/btf.c > > > @@ -1,6 +1,9 @@ > > > // SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) > > > /* Copyright (c) 2018 Facebook */ > > > [...]
Currently, we are only using the linear search method to find the type id by the name, which has a time complexity of O(n). This change involves sorting the names of btf types in ascending order and using binary search, which has a time complexity of O(log(n)). This idea was inspired by the following patch: 60443c88f3a8 ("kallsyms: Improve the performance of kallsyms_lookup_name()"). At present, this improvement is only for searching in vmlinux's and module's BTFs. Another change is the search direction, where we search the BTF first and then its base, the type id of the first matched btf_type will be returned. Here is a time-consuming result that finding 87590 type ids by their names in vmlinux's BTF. Before: 158426 ms After: 114 ms The average lookup performance has improved more than 1000x in the above scenario. v4: - Divide the patch into two parts: kernel and libbpf - Use Eduard's code to sort btf_types in the btf__dedup function - Correct some btf testcases due to modifications of the order of btf_types. v3: - Link: https://lore.kernel.org/all/20240608140835.965949-1-dolinux.peng@gmail.com/ - Sort btf_types during build process other than during boot, to reduce the overhead of memory and boot time. v2: - Link: https://lore.kernel.org/all/20230909091646.420163-1-pengdonglin@sangfor.com.cn Donglin Peng (3): libbpf: Sort btf_types in ascending order by name bpf: Using binary search to improve the performance of btf_find_by_name_kind libbpf: Using binary search to improve the performance of btf__find_by_name_kind include/linux/btf.h | 1 + kernel/bpf/btf.c | 157 +++++++++- tools/lib/bpf/btf.c | 274 +++++++++++++--- tools/testing/selftests/bpf/prog_tests/btf.c | 296 +++++++++--------- .../bpf/prog_tests/btf_dedup_split.c | 64 ++-- 5 files changed, 555 insertions(+), 237 deletions(-)