From: pengdonglin This patch checks whether the BTF is sorted by name in ascending order. If sorted, binary search will be used when looking up types. Cc: Eduard Zingerman Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Alan Maguire Cc: Ihor Solodrai Cc: Xiaoqin Zhang Signed-off-by: pengdonglin --- tools/lib/bpf/btf.c | 46 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 45 insertions(+), 1 deletion(-) diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c index 7f150c869bf6..a53d24704857 100644 --- a/tools/lib/bpf/btf.c +++ b/tools/lib/bpf/btf.c @@ -899,6 +899,49 @@ int btf__resolve_type(const struct btf *btf, __u32 type_id) return type_id; } +/* + * Assuming that types are sorted by name in ascending order. + */ +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; + + na = btf__str_by_offset(btf, ta->name_off); + nb = btf__str_by_offset(btf, tb->name_off); + return strcmp(na, nb); +} + +static void btf_check_sorted(struct btf *btf) +{ + const struct btf_type *t; + int i, k = 0, n; + __u32 sorted_start_id = 0; + + if (btf->nr_types < 2) + return; + + 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 (sorted_start_id == 0 && + !str_is_empty(btf__str_by_offset(btf, t->name_off))) + sorted_start_id = i; + } + + t = btf_type_by_id(btf, k); + if (sorted_start_id == 0 && + !str_is_empty(btf__str_by_offset(btf, t->name_off))) + sorted_start_id = k; + if (sorted_start_id) + btf->sorted_start_id = sorted_start_id; +} + static __s32 btf_find_by_name_bsearch(const struct btf *btf, const char *name, __s32 start_id, __s32 end_id) { @@ -935,7 +978,7 @@ static __s32 btf_find_by_name_kind(const struct btf *btf, int start_id, if (start_id < btf->start_id) { idx = btf_find_by_name_kind(btf->base_btf, start_id, - type_name, kind); + type_name, kind); if (idx >= 0) return idx; start_id = btf->start_id; @@ -1147,6 +1190,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