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? > > 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; - 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. 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 > + 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; > + } [...]
