On Tue, Oct 14, 2025 at 7:40 AM Andrii Nakryiko <[email protected]> wrote: > > On Mon, Oct 13, 2025 at 6:16 AM pengdonglin <[email protected]> wrote: > > > > From: pengdonglin <[email protected]> > > > > Currently, when the funcgraph-args feature is in use, the > > btf_find_by_name_kind function is invoked quite frequently. However, > > this function only supports linear search. When the number of btf_type > > entries to search through is large, such as in the vmlinux BTF which > > contains over 80,000 named btf_types, it consumes a significant amount > > of time. > > > > This patch optimizes the btf_find_by_name_kind lookup by sorting BTF > > types according to their names and kinds. Additionally, it modifies > > the search direction. Now, it first searches the BTF and then its base. > > Well, the latter is a meaningful change outside of sorting. Split it > out and justify separately?
Thanks, I will split it out in v2. > > > > > It should be noted that this change incurs some additional memory and > > boot-time overhead. Therefore, the option is disabled by default. > > > > Here is a test case: > > > > # echo 1 > options/funcgraph-args > > # echo function_graph > current_tracer > > > > Before: > > # time cat trace | wc -l > > 124176 > > > > real 0m16.154s > > user 0m0.000s > > sys 0m15.962s > > > > After: > > # time cat trace | wc -l > > 124176 > > > > real 0m0.948s > > user 0m0.000s > > sys 0m0.973s > > > > An improvement of more than 20 times can be observed. > > > > Cc: Eduard Zingerman <[email protected]> > > Cc: Alexei Starovoitov <[email protected]> > > Cc: Andrii Nakryiko <[email protected]> > > Cc: Song Liu <[email protected]> > > Cc: Masami Hiramatsu (Google) <[email protected]> > > Cc: Steven Rostedt <[email protected]> > > Signed-off-by: pengdonglin <[email protected]> > > Signed-off-by: pengdonglin <[email protected]> > > --- > > include/linux/btf.h | 1 + > > kernel/bpf/Kconfig | 13 ++++ > > kernel/bpf/btf.c | 160 +++++++++++++++++++++++++++++++++++++++++--- > > 3 files changed, 165 insertions(+), 9 deletions(-) > > > > Just a few observations (if we decide to do the sorting of BTF by name > in the kernel): > > - given we always know kind we are searching for, I'd sort by kind, > then by name, it probably will be a touch faster because we'll be > quickly skipping lots of elements clustered by kind we don't care > about; Good catch, thanks. > > - instead of having BPF_SORT_BTF_BY_NAME_KIND, we should probably just > have a lazy sorting approach, and maybe employ a bit more > sophisticated heuristic. E.g., not by number of BTF types (or at least > not just by that), but by the total number of entries we had to skip > to find something. For small BTFs we might not reach this budget ever. > For vmlinux BTF we are almost definitely hitting it on > first-second-third search. Once the condition is hit, allocate > sorted_ids index, sort, remember. On subsequent searches use the > index. Thanks, I appreciate the suggestion and will include it in v2. However, due to the memory overhead, I believe a BPF_SORT_BTF_BY_NAME_KIND option might be necessary. > > WDYT? > > [...] > > > +static void btf_sort_by_name_kind(struct btf *btf) > > +{ > > + const struct btf_type *t; > > + struct btf_sorted_ids *sorted_ids; > > + const char *name; > > + u32 *ids; > > + u32 total, cnt = 0; > > + u32 i, j = 0; > > + > > + total = btf_type_cnt(btf); > > + for (i = btf->start_id; i < total; i++) { > > + t = btf_type_by_id(btf, i); > > + name = btf_name_by_offset(btf, t->name_off); > > + if (str_is_empty(name)) > > + continue; > > + cnt++; > > + } > > + > > + /* Use linear search when the number is below the threshold */ > > + if (cnt < 8) > > kind of a random threshold, at least give it a name Thanks, I will fix it in v2. > > > + return; > > + > > + sorted_ids = kvmalloc(struct_size(sorted_ids, ids, cnt), > > GFP_KERNEL); > > + if (!sorted_ids) { > > + pr_warn("Failed to allocate memory for sorted_ids\n"); > > + return; > > + } > > [...]
