On Wed, Oct 30, 2024 at 6:15 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)).
> >
> > Another change is the search direction, where we search the BTF first and
> > then its base.
> >
> > Signed-off-by: Donglin Peng <dolinux.peng@xxxxxxxxx>
> > ---
> > 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
> > */
>
> [...]
