On Wed, Oct 30, 2024 at 8:00 AM Donglin Peng <dolinux.peng@xxxxxxxxx> wrote:
>
> On Wed, Oct 30, 2024 at 6:13 AM Andrii Nakryiko
> <andrii.nakryiko@xxxxxxxxx> wrote:
> >
> > On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng <dolinux.peng@xxxxxxxxx> 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@xxxxxxxxxx>
> > > Signed-off-by: Donglin Peng <dolinux.peng@xxxxxxxxx>
> > > ---
> > > v4:
> > > - move the modification of libbpf to another patch
> > >
> > > v3:
> > > - Link: https://lore.kernel.org/all/20240608140835.965949-1-dolinux.peng@xxxxxxxxx/
> > > - 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@xxxxxxxxxxxxxx
> > > ---
> > > 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;
> > > +}
> >
> > [...]
