* [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind
@ 2024-10-29 0:22 Donglin Peng
2024-10-29 0:22 ` [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Donglin Peng
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Donglin Peng @ 2024-10-29 0:22 UTC (permalink / raw)
To: andrii, eddyz87
Cc: ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest,
linux-kernel, Donglin Peng
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(-)
--
2.34.1
^ permalink raw reply [flat|nested] 13+ messages in thread* [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name 2024-10-29 0:22 [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng @ 2024-10-29 0:22 ` Donglin Peng 2024-10-29 21:58 ` Andrii Nakryiko 2024-10-29 0:22 ` [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng 2024-10-29 0:22 ` [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind Donglin Peng 2 siblings, 1 reply; 13+ messages in thread From: Donglin Peng @ 2024-10-29 0:22 UTC (permalink / raw) To: andrii, eddyz87 Cc: ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel, Donglin Peng 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(-) 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 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name 2024-10-29 0:22 ` [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Donglin Peng @ 2024-10-29 21:58 ` Andrii Nakryiko 2024-10-30 15:12 ` Donglin Peng 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2024-10-29 21:58 UTC (permalink / raw) To: Donglin Peng Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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 > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name 2024-10-29 21:58 ` Andrii Nakryiko @ 2024-10-30 15:12 ` Donglin Peng 2024-10-30 17:35 ` Andrii Nakryiko 0 siblings, 1 reply; 13+ messages in thread From: Donglin Peng @ 2024-10-30 15:12 UTC (permalink / raw) To: Andrii Nakryiko Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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 > > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name 2024-10-30 15:12 ` Donglin Peng @ 2024-10-30 17:35 ` Andrii Nakryiko 0 siblings, 0 replies; 13+ messages in thread From: Andrii Nakryiko @ 2024-10-30 17:35 UTC (permalink / raw) To: Donglin Peng Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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 */ > > > [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind 2024-10-29 0:22 [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng 2024-10-29 0:22 ` [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Donglin Peng @ 2024-10-29 0:22 ` Donglin Peng 2024-10-29 22:13 ` Andrii Nakryiko 2024-10-29 0:22 ` [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind Donglin Peng 2 siblings, 1 reply; 13+ messages in thread From: Donglin Peng @ 2024-10-29 0:22 UTC (permalink / raw) To: andrii, eddyz87 Cc: ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel, Donglin Peng 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. Tested-by: Masami Hiramatsu (Google) <mhiramat@kernel.org> Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> --- v4: - move the modification of libbpf to another patch 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 --- include/linux/btf.h | 1 + kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 147 insertions(+), 11 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index b8a583194c4a..64c35aaa22fa 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); bool btf_is_vmlinux(const struct btf *btf); struct module *btf_try_get_module(const struct btf *btf); u32 btf_nr_types(const struct btf *btf); +u32 btf_type_cnt(const struct btf *btf); struct btf *btf_base_btf(const struct btf *btf); bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, const struct btf_member *m, diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 5cd1c7a23848..6d0d58989640 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -262,6 +262,7 @@ struct btf { u32 data_size; refcount_t refcnt; u32 id; + u32 nr_types_sorted; struct rcu_head rcu; struct btf_kfunc_set_tab *kfunc_set_tab; struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) return total; } -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +u32 btf_type_cnt(const struct btf *btf) +{ + return btf->start_id + btf->nr_types; +} + +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, + int *start, int *end) { const struct btf_type *t; - const char *tname; - u32 i, total; + const char *name_buf; + int low, low_start, mid, high, high_end; + int ret, start_id; + + start_id = btf->base_btf ? btf->start_id : 1; + low_start = low = start_id; + high_end = high = start_id + btf->nr_types_sorted - 1; + + while (low <= high) { + mid = low + (high - low) / 2; + t = btf_type_by_id(btf, mid); + name_buf = btf_name_by_offset(btf, t->name_off); + ret = strcmp(name, name_buf); + if (ret > 0) + low = mid + 1; + else if (ret < 0) + high = mid - 1; + else + break; + } - total = btf_nr_types(btf); - for (i = 1; i < total; i++) { - t = btf_type_by_id(btf, i); - if (BTF_INFO_KIND(t->info) != kind) - continue; + if (low > high) + return -ESRCH; - tname = btf_name_by_offset(btf, t->name_off); - if (!strcmp(tname, name)) - return i; + if (start) { + low = mid; + while (low > low_start) { + t = btf_type_by_id(btf, low-1); + name_buf = btf_name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + low--; + } + *start = low; + } + + if (end) { + high = mid; + while (high < high_end) { + t = btf_type_by_id(btf, high+1); + name_buf = btf_name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + high++; + } + *end = high; } + return mid; +} + +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) +{ + const struct btf_type *t; + const char *tname; + int start, end; + s32 id, total; + + do { + if (btf->nr_types_sorted) { + /* binary search */ + id = btf_find_by_name_bsearch(btf, name, &start, &end); + if (id > 0) { + while (start <= end) { + t = btf_type_by_id(btf, start); + if (BTF_INFO_KIND(t->info) == kind) + return start; + start++; + } + } + } else { + /* linear search */ + total = btf_type_cnt(btf); + for (id = btf->base_btf ? btf->start_id : 1; + id < total; id++) { + t = btf_type_by_id(btf, id); + if (BTF_INFO_KIND(t->info) != kind) + continue; + + tname = btf_name_by_offset(btf, t->name_off); + if (!strcmp(tname, name)) + return id; + } + } + btf = btf->base_btf; + } while (btf); + return -ENOENT; } @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty return kctx_type_id; } +static int btf_check_sort(struct btf *btf, int start_id) +{ + int i, n, nr_names = 0; + + n = btf_nr_types(btf); + for (i = start_id; i < n; i++) { + const struct btf_type *t; + const char *name; + + t = btf_type_by_id(btf, i); + if (!t) + return -EINVAL; + + name = btf_str_by_offset(btf, t->name_off); + if (!str_is_empty(name)) + nr_names++; + } + + for (i = 0; i < nr_names - 1; i++) { + const struct btf_type *t1, *t2; + const char *s1, *s2; + + t1 = btf_type_by_id(btf, start_id + i); + if (!t1) + return -EINVAL; + + s1 = btf_str_by_offset(btf, t1->name_off); + if (str_is_empty(s1)) + goto out; + + t2 = btf_type_by_id(btf, start_id + i + 1); + if (!t2) + return -EINVAL; + + s2 = btf_str_by_offset(btf, t2->name_off); + if (str_is_empty(s2)) + goto out; + + if (strcmp(s1, s2) > 0) + goto out; + } + + btf->nr_types_sorted = nr_names; +out: + return 0; +} + BTF_ID_LIST(bpf_ctx_convert_btf_id) BTF_ID(struct, bpf_ctx_convert) @@ -6212,6 +6339,10 @@ struct btf *btf_parse_vmlinux(void) if (IS_ERR(btf)) goto err_out; + err = btf_check_sort(btf, 1); + if (err) + goto err_out; + /* btf_parse_vmlinux() runs under bpf_verifier_lock */ bpf_ctx_convert.t = btf_type_by_id(btf, bpf_ctx_convert_btf_id[0]); err = btf_alloc_id(btf); @@ -6315,6 +6446,10 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, base_btf = vmlinux_btf; } + err = btf_check_sort(btf, btf_nr_types(base_btf)); + if (err) + goto errout; + btf_verifier_env_free(env); refcount_set(&btf->refcnt, 1); return btf; -- 2.34.1 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind 2024-10-29 0:22 ` [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng @ 2024-10-29 22:13 ` Andrii Nakryiko 2024-10-30 15:00 ` Donglin Peng 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2024-10-29 22:13 UTC (permalink / raw) To: Donglin Peng Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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)). 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. > > Tested-by: Masami Hiramatsu (Google) <mhiramat@kernel.org> > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > --- > v4: > - move the modification of libbpf to another patch > > 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 > --- > include/linux/btf.h | 1 + > kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- > 2 files changed, 147 insertions(+), 11 deletions(-) > > diff --git a/include/linux/btf.h b/include/linux/btf.h > index b8a583194c4a..64c35aaa22fa 100644 > --- a/include/linux/btf.h > +++ b/include/linux/btf.h > @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); > bool btf_is_vmlinux(const struct btf *btf); > struct module *btf_try_get_module(const struct btf *btf); > u32 btf_nr_types(const struct btf *btf); > +u32 btf_type_cnt(const struct btf *btf); > struct btf *btf_base_btf(const struct btf *btf); > bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, > const struct btf_member *m, > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > index 5cd1c7a23848..6d0d58989640 100644 > --- a/kernel/bpf/btf.c > +++ b/kernel/bpf/btf.c > @@ -262,6 +262,7 @@ struct btf { > u32 data_size; > refcount_t refcnt; > u32 id; > + u32 nr_types_sorted; > struct rcu_head rcu; > struct btf_kfunc_set_tab *kfunc_set_tab; > struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; > @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) > return total; > } > > -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > +u32 btf_type_cnt(const struct btf *btf) > +{ > + return btf->start_id + btf->nr_types; > +} > + > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, > + int *start, int *end) > { > const struct btf_type *t; > - const char *tname; > - u32 i, total; > + const char *name_buf; > + int low, low_start, mid, high, high_end; > + int ret, start_id; > + > + start_id = btf->base_btf ? btf->start_id : 1; > + low_start = low = start_id; > + high_end = high = start_id + btf->nr_types_sorted - 1; > + > + while (low <= high) { > + mid = low + (high - low) / 2; > + t = btf_type_by_id(btf, mid); > + name_buf = btf_name_by_offset(btf, t->name_off); > + ret = strcmp(name, name_buf); > + if (ret > 0) > + low = mid + 1; > + else if (ret < 0) > + high = mid - 1; > + else > + break; > + } > > - total = btf_nr_types(btf); > - for (i = 1; i < total; i++) { > - t = btf_type_by_id(btf, i); > - if (BTF_INFO_KIND(t->info) != kind) > - continue; > + if (low > high) > + return -ESRCH; > > - tname = btf_name_by_offset(btf, t->name_off); > - if (!strcmp(tname, name)) > - return i; > + if (start) { > + low = mid; > + while (low > low_start) { > + t = btf_type_by_id(btf, low-1); > + name_buf = btf_name_by_offset(btf, t->name_off); > + if (strcmp(name, name_buf)) > + break; > + low--; > + } > + *start = low; > + } > + > + if (end) { > + high = mid; > + while (high < high_end) { > + t = btf_type_by_id(btf, high+1); > + name_buf = btf_name_by_offset(btf, t->name_off); > + if (strcmp(name, name_buf)) > + break; > + high++; > + } > + *end = high; > } > this is an overcomplicated implementation, you need something like find_linfo() implementation in kernel/bpf/log.c. Note how much shorter and leaner it is. I also don't think you need to return `end`. Given you always start from start and linearly scan forward, you just need to make sure that you never go beyond the BTF type array, for which you can use btf_type_cnt(). So no need for doing this linear scan twice. > + return mid; > +} > + > +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > +{ > + const struct btf_type *t; > + const char *tname; > + int start, end; > + s32 id, total; > + > + do { > + if (btf->nr_types_sorted) { > + /* binary search */ > + id = btf_find_by_name_bsearch(btf, name, &start, &end); > + if (id > 0) { > + while (start <= end) { > + t = btf_type_by_id(btf, start); > + if (BTF_INFO_KIND(t->info) == kind) > + return start; > + start++; > + } > + } > + } else { > + /* linear search */ > + total = btf_type_cnt(btf); > + for (id = btf->base_btf ? btf->start_id : 1; > + id < total; id++) { > + t = btf_type_by_id(btf, id); > + if (BTF_INFO_KIND(t->info) != kind) > + continue; > + > + tname = btf_name_by_offset(btf, t->name_off); > + if (!strcmp(tname, name)) > + return id; > + } > + } > + btf = btf->base_btf; > + } while (btf); > + > return -ENOENT; > } > > @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty > return kctx_type_id; > } > > +static int btf_check_sort(struct btf *btf, int start_id) > +{ > + int i, n, nr_names = 0; > + > + n = btf_nr_types(btf); > + for (i = start_id; i < n; i++) { > + const struct btf_type *t; > + const char *name; > + > + t = btf_type_by_id(btf, i); > + if (!t) > + return -EINVAL; > + > + name = btf_str_by_offset(btf, t->name_off); > + if (!str_is_empty(name)) > + nr_names++; > + } > + this loop makes zero sense to me, what are you trying to achieve with it and why? > + for (i = 0; i < nr_names - 1; i++) { just start from start_id + 1, all the way to n, and check that sorting invariant holds for all items > + const struct btf_type *t1, *t2; > + const char *s1, *s2; > + > + t1 = btf_type_by_id(btf, start_id + i); > + if (!t1) > + return -EINVAL; > + > + s1 = btf_str_by_offset(btf, t1->name_off); > + if (str_is_empty(s1)) > + goto out; > + > + t2 = btf_type_by_id(btf, start_id + i + 1); > + if (!t2) > + return -EINVAL; > + > + s2 = btf_str_by_offset(btf, t2->name_off); > + if (str_is_empty(s2)) > + goto out; > + > + if (strcmp(s1, s2) > 0) > + goto out; > + } > + > + btf->nr_types_sorted = nr_names; > +out: > + return 0; > +} [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind 2024-10-29 22:13 ` Andrii Nakryiko @ 2024-10-30 15:00 ` Donglin Peng 2024-10-30 17:33 ` Andrii Nakryiko 0 siblings, 1 reply; 13+ messages in thread From: Donglin Peng @ 2024-10-30 15:00 UTC (permalink / raw) To: Andrii Nakryiko Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel On Wed, Oct 30, 2024 at 6:13 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)). 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. > > > > Tested-by: Masami Hiramatsu (Google) <mhiramat@kernel.org> > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > --- > > v4: > > - move the modification of libbpf to another patch > > > > 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 > > --- > > include/linux/btf.h | 1 + > > kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- > > 2 files changed, 147 insertions(+), 11 deletions(-) > > > > diff --git a/include/linux/btf.h b/include/linux/btf.h > > index b8a583194c4a..64c35aaa22fa 100644 > > --- a/include/linux/btf.h > > +++ b/include/linux/btf.h > > @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); > > bool btf_is_vmlinux(const struct btf *btf); > > struct module *btf_try_get_module(const struct btf *btf); > > u32 btf_nr_types(const struct btf *btf); > > +u32 btf_type_cnt(const struct btf *btf); > > struct btf *btf_base_btf(const struct btf *btf); > > bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, > > const struct btf_member *m, > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > > index 5cd1c7a23848..6d0d58989640 100644 > > --- a/kernel/bpf/btf.c > > +++ b/kernel/bpf/btf.c > > @@ -262,6 +262,7 @@ struct btf { > > u32 data_size; > > refcount_t refcnt; > > u32 id; > > + u32 nr_types_sorted; > > struct rcu_head rcu; > > struct btf_kfunc_set_tab *kfunc_set_tab; > > struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; > > @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) > > return total; > > } > > > > -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > +u32 btf_type_cnt(const struct btf *btf) > > +{ > > + return btf->start_id + btf->nr_types; > > +} > > + > > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, > > + int *start, int *end) > > { > > const struct btf_type *t; > > - const char *tname; > > - u32 i, total; > > + const char *name_buf; > > + int low, low_start, mid, high, high_end; > > + int ret, start_id; > > + > > + start_id = btf->base_btf ? btf->start_id : 1; > > + low_start = low = start_id; > > + high_end = high = start_id + btf->nr_types_sorted - 1; > > + > > + while (low <= high) { > > + mid = low + (high - low) / 2; > > + t = btf_type_by_id(btf, mid); > > + name_buf = btf_name_by_offset(btf, t->name_off); > > + ret = strcmp(name, name_buf); > > + if (ret > 0) > > + low = mid + 1; > > + else if (ret < 0) > > + high = mid - 1; > > + else > > + break; > > + } > > > > - total = btf_nr_types(btf); > > - for (i = 1; i < total; i++) { > > - t = btf_type_by_id(btf, i); > > - if (BTF_INFO_KIND(t->info) != kind) > > - continue; > > + if (low > high) > > + return -ESRCH; > > > > - tname = btf_name_by_offset(btf, t->name_off); > > - if (!strcmp(tname, name)) > > - return i; > > + if (start) { > > + low = mid; > > + while (low > low_start) { > > + t = btf_type_by_id(btf, low-1); > > + name_buf = btf_name_by_offset(btf, t->name_off); > > + if (strcmp(name, name_buf)) > > + break; > > + low--; > > + } > > + *start = low; > > + } > > + > > + if (end) { > > + high = mid; > > + while (high < high_end) { > > + t = btf_type_by_id(btf, high+1); > > + name_buf = btf_name_by_offset(btf, t->name_off); > > + if (strcmp(name, name_buf)) > > + break; > > + high++; > > + } > > + *end = high; > > } > > > > this is an overcomplicated implementation, you need something like > find_linfo() implementation in kernel/bpf/log.c. Note how much shorter > and leaner it is. > > I also don't think you need to return `end`. Given you always start > from start and linearly scan forward, you just need to make sure that > you never go beyond the BTF type array, for which you can use > btf_type_cnt(). So no need for doing this linear scan twice. Thank you, but the situation here is different. When the btf file is sorted, the btf_types with a name are placed at the beginning of the file, while those without a name are placed at the end. Additionally, if there are multiple btf_types with the same name in a btf file, they will have different kinds, and these btf_types with the same name will be grouped together. For example, in the following case: ... [13561] FUNC 'bp_constraints_unlock' type_id=105264 linkage=static [13562] STRUCT 'bp_cpuinfo' size=20 vlen=2 'cpu_pinned' type_id=66670 bits_offset=0 'tsk_pinned' type_id=13568 bits_offset=32 [13563] VAR 'bp_cpuinfo' type_id=103076, linkage=static [13564] FUNC 'bp_init_aperfmperf' type_id=70013 linkage=static [13565] STRUCT 'bp_patching_desc' size=16 vlen=3 ... Both 13562 and 13563 have the name 'bp_cpuinfo', but their kinds are different. Therefore, when using the btf_find_by_name_bsearch function to find the btf_type named 'bp_cpuinfo', the start parameter will be set to 11562 and the end parameter will be set to 11563. We can then check their kind to obtain the correct btf_type. > > > + return mid; > > +} > > + > > +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > +{ > > + const struct btf_type *t; > > + const char *tname; > > + int start, end; > > + s32 id, total; > > + > > + do { > > + if (btf->nr_types_sorted) { > > + /* binary search */ > > + id = btf_find_by_name_bsearch(btf, name, &start, &end); > > + if (id > 0) { > > + while (start <= end) { > > + t = btf_type_by_id(btf, start); > > + if (BTF_INFO_KIND(t->info) == kind) > > + return start; > > + start++; > > + } > > + } > > + } else { > > + /* linear search */ > > + total = btf_type_cnt(btf); > > + for (id = btf->base_btf ? btf->start_id : 1; > > + id < total; id++) { > > + t = btf_type_by_id(btf, id); > > + if (BTF_INFO_KIND(t->info) != kind) > > + continue; > > + > > + tname = btf_name_by_offset(btf, t->name_off); > > + if (!strcmp(tname, name)) > > + return id; > > + } > > + } > > + btf = btf->base_btf; > > + } while (btf); > > + > > return -ENOENT; > > } > > > > @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty > > return kctx_type_id; > > } > > > > +static int btf_check_sort(struct btf *btf, int start_id) > > +{ > > + int i, n, nr_names = 0; > > + > > + n = btf_nr_types(btf); > > + for (i = start_id; i < n; i++) { > > + const struct btf_type *t; > > + const char *name; > > + > > + t = btf_type_by_id(btf, i); > > + if (!t) > > + return -EINVAL; > > + > > + name = btf_str_by_offset(btf, t->name_off); > > + if (!str_is_empty(name)) > > + nr_names++; > > + } > > + > > this loop makes zero sense to me, what are you trying to achieve with > it and why? As previously mentioned, if the btf file is sorted, the btf_type with a name will be placed at the beginning of the file in ascending order, while those without a name will be placed at the end. Therefore, we can verify if the btf file is sorted by following these steps: Step 1: Count the number of btf_types with a name and store it as nr_names. Step 2: Inspect the first nr_names btf_types. If any of the following cases occur, it indicates that the btf file is not sorted: 1. A btf_type without a name is encountered. 2. The name of the current btf_type is greater than the name of the next btf_type. > > > + for (i = 0; i < nr_names - 1; i++) { > > just start from start_id + 1, all the way to n, and check that sorting > invariant holds for all items > > > + const struct btf_type *t1, *t2; > > + const char *s1, *s2; > > + > > + t1 = btf_type_by_id(btf, start_id + i); > > + if (!t1) > > + return -EINVAL; > > + > > + s1 = btf_str_by_offset(btf, t1->name_off); > > + if (str_is_empty(s1)) > > + goto out; > > + > > + t2 = btf_type_by_id(btf, start_id + i + 1); > > + if (!t2) > > + return -EINVAL; > > + > > + s2 = btf_str_by_offset(btf, t2->name_off); > > + if (str_is_empty(s2)) > > + goto out; > > + > > + if (strcmp(s1, s2) > 0) > > + goto out; > > + } > > + > > + btf->nr_types_sorted = nr_names; > > +out: > > + return 0; > > +} > > [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind 2024-10-30 15:00 ` Donglin Peng @ 2024-10-30 17:33 ` Andrii Nakryiko 2024-10-31 11:57 ` Donglin Peng 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2024-10-30 17:33 UTC (permalink / raw) To: Donglin Peng Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel On Wed, Oct 30, 2024 at 8:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote: > > On Wed, Oct 30, 2024 at 6:13 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)). 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. > > > > > > Tested-by: Masami Hiramatsu (Google) <mhiramat@kernel.org> > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > > --- > > > v4: > > > - move the modification of libbpf to another patch > > > > > > 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 > > > --- > > > include/linux/btf.h | 1 + > > > kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- > > > 2 files changed, 147 insertions(+), 11 deletions(-) > > > > > > diff --git a/include/linux/btf.h b/include/linux/btf.h > > > index b8a583194c4a..64c35aaa22fa 100644 > > > --- a/include/linux/btf.h > > > +++ b/include/linux/btf.h > > > @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); > > > bool btf_is_vmlinux(const struct btf *btf); > > > struct module *btf_try_get_module(const struct btf *btf); > > > u32 btf_nr_types(const struct btf *btf); > > > +u32 btf_type_cnt(const struct btf *btf); > > > struct btf *btf_base_btf(const struct btf *btf); > > > bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, > > > const struct btf_member *m, > > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > > > index 5cd1c7a23848..6d0d58989640 100644 > > > --- a/kernel/bpf/btf.c > > > +++ b/kernel/bpf/btf.c > > > @@ -262,6 +262,7 @@ struct btf { > > > u32 data_size; > > > refcount_t refcnt; > > > u32 id; > > > + u32 nr_types_sorted; > > > struct rcu_head rcu; > > > struct btf_kfunc_set_tab *kfunc_set_tab; > > > struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; > > > @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) > > > return total; > > > } > > > > > > -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > > +u32 btf_type_cnt(const struct btf *btf) > > > +{ > > > + return btf->start_id + btf->nr_types; > > > +} > > > + > > > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, > > > + int *start, int *end) > > > { > > > const struct btf_type *t; > > > - const char *tname; > > > - u32 i, total; > > > + const char *name_buf; > > > + int low, low_start, mid, high, high_end; > > > + int ret, start_id; > > > + > > > + start_id = btf->base_btf ? btf->start_id : 1; > > > + low_start = low = start_id; > > > + high_end = high = start_id + btf->nr_types_sorted - 1; > > > + > > > + while (low <= high) { > > > + mid = low + (high - low) / 2; > > > + t = btf_type_by_id(btf, mid); > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > + ret = strcmp(name, name_buf); > > > + if (ret > 0) > > > + low = mid + 1; > > > + else if (ret < 0) > > > + high = mid - 1; > > > + else > > > + break; > > > + } > > > > > > - total = btf_nr_types(btf); > > > - for (i = 1; i < total; i++) { > > > - t = btf_type_by_id(btf, i); > > > - if (BTF_INFO_KIND(t->info) != kind) > > > - continue; > > > + if (low > high) > > > + return -ESRCH; > > > > > > - tname = btf_name_by_offset(btf, t->name_off); > > > - if (!strcmp(tname, name)) > > > - return i; > > > + if (start) { > > > + low = mid; > > > + while (low > low_start) { > > > + t = btf_type_by_id(btf, low-1); > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > + if (strcmp(name, name_buf)) > > > + break; > > > + low--; > > > + } > > > + *start = low; > > > + } > > > + > > > + if (end) { > > > + high = mid; > > > + while (high < high_end) { > > > + t = btf_type_by_id(btf, high+1); > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > + if (strcmp(name, name_buf)) > > > + break; > > > + high++; > > > + } > > > + *end = high; > > > } > > > > > > > this is an overcomplicated implementation, you need something like > > find_linfo() implementation in kernel/bpf/log.c. Note how much shorter > > and leaner it is. > > > > I also don't think you need to return `end`. Given you always start > > from start and linearly scan forward, you just need to make sure that > > you never go beyond the BTF type array, for which you can use > > btf_type_cnt(). So no need for doing this linear scan twice. > > Thank you, but the situation here is different. When > the btf file is sorted, the btf_types with a name are > placed at the beginning of the file, while those without > a name are placed at the end. Additionally, if there > are multiple btf_types with the same name in a btf file, > they will have different kinds, and these btf_types with > the same name will be grouped together. For example, in > the following case: > > ... > [13561] FUNC 'bp_constraints_unlock' type_id=105264 linkage=static > [13562] STRUCT 'bp_cpuinfo' size=20 vlen=2 > 'cpu_pinned' type_id=66670 bits_offset=0 > 'tsk_pinned' type_id=13568 bits_offset=32 > [13563] VAR 'bp_cpuinfo' type_id=103076, linkage=static > [13564] FUNC 'bp_init_aperfmperf' type_id=70013 linkage=static > [13565] STRUCT 'bp_patching_desc' size=16 vlen=3 > ... > > Both 13562 and 13563 have the name 'bp_cpuinfo', but their > kinds are different. Therefore, when using the btf_find_by_name_bsearch > function to find the btf_type named 'bp_cpuinfo', the start > parameter will be set to 11562 and the end parameter will > be set to 11563. We can then check their kind to obtain the > correct btf_type. I understand that, thank you. find_linfo() shows an example of binary search to find the rightmost item that's <= than requested search key. You have a similar problem here. You need to find the leftmost item that's equal to the search key. Both of these problems are solved by binary search without any extra post-processing and linear scans. > > > > > > + return mid; > > > +} > > > + > > > +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > > +{ > > > + const struct btf_type *t; > > > + const char *tname; > > > + int start, end; > > > + s32 id, total; > > > + > > > + do { > > > + if (btf->nr_types_sorted) { > > > + /* binary search */ > > > + id = btf_find_by_name_bsearch(btf, name, &start, &end); > > > + if (id > 0) { > > > + while (start <= end) { > > > + t = btf_type_by_id(btf, start); > > > + if (BTF_INFO_KIND(t->info) == kind) > > > + return start; > > > + start++; > > > + } > > > + } > > > + } else { > > > + /* linear search */ > > > + total = btf_type_cnt(btf); > > > + for (id = btf->base_btf ? btf->start_id : 1; > > > + id < total; id++) { > > > + t = btf_type_by_id(btf, id); > > > + if (BTF_INFO_KIND(t->info) != kind) > > > + continue; > > > + > > > + tname = btf_name_by_offset(btf, t->name_off); > > > + if (!strcmp(tname, name)) > > > + return id; > > > + } > > > + } > > > + btf = btf->base_btf; > > > + } while (btf); > > > + > > > return -ENOENT; > > > } > > > > > > @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty > > > return kctx_type_id; > > > } > > > > > > +static int btf_check_sort(struct btf *btf, int start_id) > > > +{ > > > + int i, n, nr_names = 0; > > > + > > > + n = btf_nr_types(btf); > > > + for (i = start_id; i < n; i++) { > > > + const struct btf_type *t; > > > + const char *name; > > > + > > > + t = btf_type_by_id(btf, i); > > > + if (!t) > > > + return -EINVAL; > > > + > > > + name = btf_str_by_offset(btf, t->name_off); > > > + if (!str_is_empty(name)) > > > + nr_names++; > > > + } > > > + > > > > this loop makes zero sense to me, what are you trying to achieve with > > it and why? > > As previously mentioned, if the btf file is sorted, the > btf_type with a name will be placed at the beginning of > the file in ascending order, while those without a name > will be placed at the end. Therefore, we can verify if > the btf file is sorted by following these steps: > > Step 1: Count the number of btf_types with a name and > store it as nr_names. > > Step 2: Inspect the first nr_names btf_types. If any of > the following cases occur, it indicates that the > btf file is not sorted: > 1. A btf_type without a name is encountered. > 2. The name of the current btf_type is greater than > the name of the next btf_type. This is convoluted and unnecessary. Just go over all items and validate that each pair maintains the sorting criteria. > > > > > > + for (i = 0; i < nr_names - 1; i++) { > > > > just start from start_id + 1, all the way to n, and check that sorting > > invariant holds for all items > > > > > + const struct btf_type *t1, *t2; > > > + const char *s1, *s2; > > > + > > > + t1 = btf_type_by_id(btf, start_id + i); > > > + if (!t1) > > > + return -EINVAL; > > > + > > > + s1 = btf_str_by_offset(btf, t1->name_off); > > > + if (str_is_empty(s1)) > > > + goto out; > > > + > > > + t2 = btf_type_by_id(btf, start_id + i + 1); > > > + if (!t2) > > > + return -EINVAL; > > > + > > > + s2 = btf_str_by_offset(btf, t2->name_off); > > > + if (str_is_empty(s2)) > > > + goto out; > > > + > > > + if (strcmp(s1, s2) > 0) > > > + goto out; > > > + } > > > + > > > + btf->nr_types_sorted = nr_names; > > > +out: > > > + return 0; > > > +} > > > > [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind 2024-10-30 17:33 ` Andrii Nakryiko @ 2024-10-31 11:57 ` Donglin Peng 0 siblings, 0 replies; 13+ messages in thread From: Donglin Peng @ 2024-10-31 11:57 UTC (permalink / raw) To: Andrii Nakryiko Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel On Thu, Oct 31, 2024 at 1:33 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Wed, Oct 30, 2024 at 8:00 AM Donglin Peng <dolinux.peng@gmail.com> wrote: > > > > On Wed, Oct 30, 2024 at 6:13 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)). 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. > > > > > > > > Tested-by: Masami Hiramatsu (Google) <mhiramat@kernel.org> > > > > Signed-off-by: Donglin Peng <dolinux.peng@gmail.com> > > > > --- > > > > v4: > > > > - move the modification of libbpf to another patch > > > > > > > > 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 > > > > --- > > > > include/linux/btf.h | 1 + > > > > kernel/bpf/btf.c | 157 ++++++++++++++++++++++++++++++++++++++++---- > > > > 2 files changed, 147 insertions(+), 11 deletions(-) > > > > > > > > diff --git a/include/linux/btf.h b/include/linux/btf.h > > > > index b8a583194c4a..64c35aaa22fa 100644 > > > > --- a/include/linux/btf.h > > > > +++ b/include/linux/btf.h > > > > @@ -216,6 +216,7 @@ bool btf_is_module(const struct btf *btf); > > > > bool btf_is_vmlinux(const struct btf *btf); > > > > struct module *btf_try_get_module(const struct btf *btf); > > > > u32 btf_nr_types(const struct btf *btf); > > > > +u32 btf_type_cnt(const struct btf *btf); > > > > struct btf *btf_base_btf(const struct btf *btf); > > > > bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, > > > > const struct btf_member *m, > > > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > > > > index 5cd1c7a23848..6d0d58989640 100644 > > > > --- a/kernel/bpf/btf.c > > > > +++ b/kernel/bpf/btf.c > > > > @@ -262,6 +262,7 @@ struct btf { > > > > u32 data_size; > > > > refcount_t refcnt; > > > > u32 id; > > > > + u32 nr_types_sorted; > > > > struct rcu_head rcu; > > > > struct btf_kfunc_set_tab *kfunc_set_tab; > > > > struct btf_id_dtor_kfunc_tab *dtor_kfunc_tab; > > > > @@ -548,23 +549,102 @@ u32 btf_nr_types(const struct btf *btf) > > > > return total; > > > > } > > > > > > > > -s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > > > +u32 btf_type_cnt(const struct btf *btf) > > > > +{ > > > > + return btf->start_id + btf->nr_types; > > > > +} > > > > + > > > > +static s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, > > > > + int *start, int *end) > > > > { > > > > const struct btf_type *t; > > > > - const char *tname; > > > > - u32 i, total; > > > > + const char *name_buf; > > > > + int low, low_start, mid, high, high_end; > > > > + int ret, start_id; > > > > + > > > > + start_id = btf->base_btf ? btf->start_id : 1; > > > > + low_start = low = start_id; > > > > + high_end = high = start_id + btf->nr_types_sorted - 1; > > > > + > > > > + while (low <= high) { > > > > + mid = low + (high - low) / 2; > > > > + t = btf_type_by_id(btf, mid); > > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > > + ret = strcmp(name, name_buf); > > > > + if (ret > 0) > > > > + low = mid + 1; > > > > + else if (ret < 0) > > > > + high = mid - 1; > > > > + else > > > > + break; > > > > + } > > > > > > > > - total = btf_nr_types(btf); > > > > - for (i = 1; i < total; i++) { > > > > - t = btf_type_by_id(btf, i); > > > > - if (BTF_INFO_KIND(t->info) != kind) > > > > - continue; > > > > + if (low > high) > > > > + return -ESRCH; > > > > > > > > - tname = btf_name_by_offset(btf, t->name_off); > > > > - if (!strcmp(tname, name)) > > > > - return i; > > > > + if (start) { > > > > + low = mid; > > > > + while (low > low_start) { > > > > + t = btf_type_by_id(btf, low-1); > > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > > + if (strcmp(name, name_buf)) > > > > + break; > > > > + low--; > > > > + } > > > > + *start = low; > > > > + } > > > > + > > > > + if (end) { > > > > + high = mid; > > > > + while (high < high_end) { > > > > + t = btf_type_by_id(btf, high+1); > > > > + name_buf = btf_name_by_offset(btf, t->name_off); > > > > + if (strcmp(name, name_buf)) > > > > + break; > > > > + high++; > > > > + } > > > > + *end = high; > > > > } > > > > > > > > > > this is an overcomplicated implementation, you need something like > > > find_linfo() implementation in kernel/bpf/log.c. Note how much shorter > > > and leaner it is. > > > > > > I also don't think you need to return `end`. Given you always start > > > from start and linearly scan forward, you just need to make sure that > > > you never go beyond the BTF type array, for which you can use > > > btf_type_cnt(). So no need for doing this linear scan twice. > > > > Thank you, but the situation here is different. When > > the btf file is sorted, the btf_types with a name are > > placed at the beginning of the file, while those without > > a name are placed at the end. Additionally, if there > > are multiple btf_types with the same name in a btf file, > > they will have different kinds, and these btf_types with > > the same name will be grouped together. For example, in > > the following case: > > > > ... > > [13561] FUNC 'bp_constraints_unlock' type_id=105264 linkage=static > > [13562] STRUCT 'bp_cpuinfo' size=20 vlen=2 > > 'cpu_pinned' type_id=66670 bits_offset=0 > > 'tsk_pinned' type_id=13568 bits_offset=32 > > [13563] VAR 'bp_cpuinfo' type_id=103076, linkage=static > > [13564] FUNC 'bp_init_aperfmperf' type_id=70013 linkage=static > > [13565] STRUCT 'bp_patching_desc' size=16 vlen=3 > > ... > > > > Both 13562 and 13563 have the name 'bp_cpuinfo', but their > > kinds are different. Therefore, when using the btf_find_by_name_bsearch > > function to find the btf_type named 'bp_cpuinfo', the start > > parameter will be set to 11562 and the end parameter will > > be set to 11563. We can then check their kind to obtain the > > correct btf_type. > > I understand that, thank you. find_linfo() shows an example of binary > search to find the rightmost item that's <= than requested search key. > You have a similar problem here. You need to find the leftmost item > that's equal to the search key. Thank you, I will modify it. > > Both of these problems are solved by binary search without any extra > post-processing and linear scans. Thank you, I get it. > > > > > > > > > > + return mid; > > > > +} > > > > + > > > > +s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind) > > > > +{ > > > > + const struct btf_type *t; > > > > + const char *tname; > > > > + int start, end; > > > > + s32 id, total; > > > > + > > > > + do { > > > > + if (btf->nr_types_sorted) { > > > > + /* binary search */ > > > > + id = btf_find_by_name_bsearch(btf, name, &start, &end); > > > > + if (id > 0) { > > > > + while (start <= end) { > > > > + t = btf_type_by_id(btf, start); > > > > + if (BTF_INFO_KIND(t->info) == kind) > > > > + return start; > > > > + start++; > > > > + } > > > > + } > > > > + } else { > > > > + /* linear search */ > > > > + total = btf_type_cnt(btf); > > > > + for (id = btf->base_btf ? btf->start_id : 1; > > > > + id < total; id++) { > > > > + t = btf_type_by_id(btf, id); > > > > + if (BTF_INFO_KIND(t->info) != kind) > > > > + continue; > > > > + > > > > + tname = btf_name_by_offset(btf, t->name_off); > > > > + if (!strcmp(tname, name)) > > > > + return id; > > > > + } > > > > + } > > > > + btf = btf->base_btf; > > > > + } while (btf); > > > > + > > > > return -ENOENT; > > > > } > > > > > > > > @@ -6141,6 +6221,53 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty > > > > return kctx_type_id; > > > > } > > > > > > > > +static int btf_check_sort(struct btf *btf, int start_id) > > > > +{ > > > > + int i, n, nr_names = 0; > > > > + > > > > + n = btf_nr_types(btf); > > > > + for (i = start_id; i < n; i++) { > > > > + const struct btf_type *t; > > > > + const char *name; > > > > + > > > > + t = btf_type_by_id(btf, i); > > > > + if (!t) > > > > + return -EINVAL; > > > > + > > > > + name = btf_str_by_offset(btf, t->name_off); > > > > + if (!str_is_empty(name)) > > > > + nr_names++; > > > > + } > > > > + > > > > > > this loop makes zero sense to me, what are you trying to achieve with > > > it and why? > > > > As previously mentioned, if the btf file is sorted, the > > btf_type with a name will be placed at the beginning of > > the file in ascending order, while those without a name > > will be placed at the end. Therefore, we can verify if > > the btf file is sorted by following these steps: > > > > Step 1: Count the number of btf_types with a name and > > store it as nr_names. > > > > Step 2: Inspect the first nr_names btf_types. If any of > > the following cases occur, it indicates that the > > btf file is not sorted: > > 1. A btf_type without a name is encountered. > > 2. The name of the current btf_type is greater than > > the name of the next btf_type. > > This is convoluted and unnecessary. Just go over all items and > validate that each pair maintains the sorting criteria. Thank you, I will modify it. > > > > > > > > > > + for (i = 0; i < nr_names - 1; i++) { > > > > > > just start from start_id + 1, all the way to n, and check that sorting > > > invariant holds for all items > > > > > > > + const struct btf_type *t1, *t2; > > > > + const char *s1, *s2; > > > > + > > > > + t1 = btf_type_by_id(btf, start_id + i); > > > > + if (!t1) > > > > + return -EINVAL; > > > > + > > > > + s1 = btf_str_by_offset(btf, t1->name_off); > > > > + if (str_is_empty(s1)) > > > > + goto out; > > > > + > > > > + t2 = btf_type_by_id(btf, start_id + i + 1); > > > > + if (!t2) > > > > + return -EINVAL; > > > > + > > > > + s2 = btf_str_by_offset(btf, t2->name_off); > > > > + if (str_is_empty(s2)) > > > > + goto out; > > > > + > > > > + if (strcmp(s1, s2) > 0) > > > > + goto out; > > > > + } > > > > + > > > > + btf->nr_types_sorted = nr_names; > > > > +out: > > > > + return 0; > > > > +} > > > > > > [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind 2024-10-29 0:22 [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng 2024-10-29 0:22 ` [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Donglin Peng 2024-10-29 0:22 ` [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng @ 2024-10-29 0:22 ` Donglin Peng 2024-10-29 22:15 ` Andrii Nakryiko 2 siblings, 1 reply; 13+ messages in thread From: Donglin Peng @ 2024-10-29 0:22 UTC (permalink / raw) To: andrii, eddyz87 Cc: ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel, Donglin Peng 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(-) 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 */ @@ -896,46 +900,111 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } -__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +static __s32 btf__find_by_name_bsearch(const struct btf *btf, const char *name, + int *start, int *end) { - __u32 i, nr_types = btf__type_cnt(btf); + const struct btf_type *t; + const char *name_buf; + int low, low_start, mid, high, high_end; + int ret; + + low_start = low = btf->start_id; + high_end = high = btf->start_id + btf->nr_types_sorted - 1; + + while (low <= high) { + mid = low + (high - low) / 2; + t = btf__type_by_id(btf, mid); + name_buf = btf__name_by_offset(btf, t->name_off); + ret = strcmp(name, name_buf); + if (ret > 0) + low = mid + 1; + else if (ret < 0) + high = mid - 1; + else + break; + } - if (!strcmp(type_name, "void")) - return 0; + if (low > high) + return -ESRCH; - for (i = 1; i < nr_types; i++) { - const struct btf_type *t = btf__type_by_id(btf, i); - const char *name = btf__name_by_offset(btf, t->name_off); + if (start) { + low = mid; + while (low > low_start) { + t = btf__type_by_id(btf, low-1); + name_buf = btf__name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + low--; + } + *start = low; + } - if (name && !strcmp(type_name, name)) - return i; + if (end) { + high = mid; + while (high < high_end) { + t = btf__type_by_id(btf, high+1); + name_buf = btf__name_by_offset(btf, t->name_off); + if (strcmp(name, name_buf)) + break; + high++; + } + *end = high; } - return libbpf_err(-ENOENT); + return mid; } static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, const char *type_name, __u32 kind) { - __u32 i, nr_types = btf__type_cnt(btf); + const struct btf_type *t; + const char *tname; + int start, end, id; + __u32 nr_types; if (kind == BTF_KIND_UNKN || !strcmp(type_name, "void")) return 0; - for (i = start_id; i < nr_types; i++) { - const struct btf_type *t = btf__type_by_id(btf, i); - const char *name; - - if (btf_kind(t) != kind) + while (btf) { + if (btf->start_id < start_id) { + btf = btf->base_btf; continue; - name = btf__name_by_offset(btf, t->name_off); - if (name && !strcmp(type_name, name)) - return i; + } + + if (btf->nr_types_sorted) { + id = btf__find_by_name_bsearch(btf, type_name, &start, &end); + if (id > 0) { + while (start <= end) { + t = btf__type_by_id(btf, start); + if (kind == BTF_KIND_MAX || + btf_kind(t) == kind) + return start; + start++; + } + } + } else { + nr_types = btf__type_cnt(btf); + for (id = btf->start_id; id < nr_types; id++) { + t = btf__type_by_id(btf, id); + if (kind != BTF_KIND_MAX && btf_kind(t) != kind) + continue; + + tname = btf__name_by_offset(btf, t->name_off); + if (tname && !strcmp(tname, type_name)) + return id; + } + } + btf = btf__base_btf(btf); } return libbpf_err(-ENOENT); } +__s32 btf__find_by_name(const struct btf *btf, const char *type_name) +{ + return btf_find_by_name_kind(btf, 1, type_name, BTF_KIND_MAX); +} + __s32 btf__find_by_name_kind_own(const struct btf *btf, const char *type_name, __u32 kind) { @@ -989,6 +1058,7 @@ static struct btf *btf_new_empty(struct btf *base_btf) return ERR_PTR(-ENOMEM); btf->nr_types = 0; + btf->nr_types_sorted = 0; btf->start_id = 1; btf->start_str_off = 0; btf->fd = -1; @@ -1032,6 +1102,53 @@ struct btf *btf__new_empty_split(struct btf *base_btf) return libbpf_ptr(btf_new_empty(base_btf)); } +static int btf_check_sort(struct btf *btf, __u32 start_id) +{ + __u32 i, n, nr_names = 0; + + n = btf__type_cnt(btf); + for (i = start_id; i < n; i++) { + const struct btf_type *t; + const char *name; + + t = btf__type_by_id(btf, i); + if (!t) + return libbpf_err(-EINVAL); + + name = btf__str_by_offset(btf, t->name_off); + if (!str_is_empty(name)) + nr_names++; + } + + for (i = 0; i < nr_names - 1; i++) { + const struct btf_type *t1, *t2; + const char *s1, *s2; + + t1 = btf__type_by_id(btf, start_id + i); + if (!t1) + return libbpf_err(-EINVAL); + + s1 = btf__str_by_offset(btf, t1->name_off); + if (str_is_empty(s1)) + goto out; + + t2 = btf__type_by_id(btf, start_id + i + 1); + if (!t2) + return libbpf_err(-EINVAL); + + s2 = btf__str_by_offset(btf, t2->name_off); + if (str_is_empty(s2)) + goto out; + + if (strcmp(s1, s2) > 0) + goto out; + } + + btf->nr_types_sorted = nr_names; +out: + return 0; +} + static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf) { struct btf *btf; @@ -1042,6 +1159,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf) return ERR_PTR(-ENOMEM); btf->nr_types = 0; + btf->nr_types_sorted = 0; btf->start_id = 1; btf->start_str_off = 0; btf->fd = -1; @@ -1071,6 +1189,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf) err = btf_parse_str_sec(btf); err = err ?: btf_parse_type_sec(btf); err = err ?: btf_sanity_check(btf); + err = err ?: btf_check_sort(btf, btf->start_id); if (err) goto done; @@ -1690,6 +1809,8 @@ static int btf_ensure_modifiable(struct btf *btf) btf->types_data_cap = btf->hdr->type_len; btf->strs_data = NULL; btf->strs_set = set; + /* clear when splitting */ + btf->nr_types_sorted = 0; /* if BTF was created from scratch, all strings are guaranteed to be * unique and deduplicated */ -- 2.34.1 ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind 2024-10-29 0:22 ` [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind Donglin Peng @ 2024-10-29 22:15 ` Andrii Nakryiko 2024-10-30 15:24 ` Donglin Peng 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2024-10-29 22:15 UTC (permalink / raw) To: Donglin Peng Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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. 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 > */ [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind 2024-10-29 22:15 ` Andrii Nakryiko @ 2024-10-30 15:24 ` Donglin Peng 0 siblings, 0 replies; 13+ messages in thread From: Donglin Peng @ 2024-10-30 15:24 UTC (permalink / raw) To: Andrii Nakryiko Cc: andrii, eddyz87, ast, rostedt, mhiramat, bpf, linux-trace-kernel, linux-kselftest, linux-kernel 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 > > */ > > [...] ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2024-10-31 11:57 UTC | newest] Thread overview: 13+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2024-10-29 0:22 [PATCH v4 0/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng 2024-10-29 0:22 ` [PATCH v4 1/3] libbpf: Sort btf_types in ascending order by name Donglin Peng 2024-10-29 21:58 ` Andrii Nakryiko 2024-10-30 15:12 ` Donglin Peng 2024-10-30 17:35 ` Andrii Nakryiko 2024-10-29 0:22 ` [PATCH v4 2/3] bpf: Using binary search to improve the performance of btf_find_by_name_kind Donglin Peng 2024-10-29 22:13 ` Andrii Nakryiko 2024-10-30 15:00 ` Donglin Peng 2024-10-30 17:33 ` Andrii Nakryiko 2024-10-31 11:57 ` Donglin Peng 2024-10-29 0:22 ` [PATCH v4 3/3] libbpf: Using binary search to improve the performance of btf__find_by_name_kind Donglin Peng 2024-10-29 22:15 ` Andrii Nakryiko 2024-10-30 15:24 ` Donglin Peng
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox