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 <[email protected]> --- 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
