| Message ID | 20241029002208.1947947-2-dolinux.peng@gmail.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF |
| Headers | show |
| Series | bpf: Using binary search to improve the performance of btf_find_by_name_kind | expand |
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, 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. 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 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 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 */ > > > [...]
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);