On Mon, Oct 28, 2024 at 5:22 PM Donglin Peng dolinux.peng@gmail.com 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@gmail.com
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.
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 */
[...]