From: Donglin Peng This patch adds validation to verify BTF type name sorting, enabling binary search optimization for lookups. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Song Liu Cc: Xiaoqin Zhang Signed-off-by: Donglin Peng --- tools/lib/bpf/btf.c | 59 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 1d19d95da1d0..d872abff42e1 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -903,6 +903,64 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } +/* Anonymous types (with empty names) are considered greater than named types + * and are sorted after them. Two anonymous types are considered equal. Named + * types are compared lexicographically. + */ +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; + bool anon_a, anon_b; + + na = btf__str_by_offset(btf, ta->name_off); + nb = btf__str_by_offset(btf, tb->name_off); + anon_a = str_is_empty(na); + anon_b = str_is_empty(nb); + + if (anon_a && !anon_b) + return 1; + if (!anon_a && anon_b) + return -1; + if (anon_a && anon_b) + return 0; + + return strcmp(na, nb); +} + +/* Verifies that BTF types are sorted in ascending order according to their + * names, with named types appearing before anonymous types. If the ordering + * is correct, counts the number of named types and updates the BTF object's + * nr_sorted_types field. + */ +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k = 0, n, nr_sorted_types; + + if (btf->nr_types < 2) + return; + + nr_sorted_types = 0; + n = btf__type_cnt(btf) - 1; + for (i = btf->start_id; i < n; i++) { + k = i + 1; + if (btf_compare_type_names(&i, &k, btf) > 0) + return; + t = btf_type_by_id(btf, i); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + } + + t = btf_type_by_id(btf, k); + if (!str_is_empty(btf__str_by_offset(btf, t->name_off))) + nr_sorted_types++; + if (nr_sorted_types) + btf->nr_sorted_types = nr_sorted_types; +} + static __s32 btf_find_type_by_name_bsearch(const struct btf *btf, const char *name, __s32 start_id, __s32 end_id) { @@ -1148,6 +1206,7 @@ static struct btf *btf_new(const void *data, __u32 size, struct btf *base_btf, b err = err ?: btf_sanity_check(btf); if (err) goto done; + btf_check_sorted(btf); done: if (err) { -- 2.34.1