On Tue, Oct 14, 2025 at 7:40 AM Andrii Nakryiko
[off-list ref] wrote:

On Mon, Oct 13, 2025 at 6:16 AM pengdonglin [off-list ref] wrote:

quoted

From: pengdonglin <redacted>

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.

quoted

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 <eddyz87@gmail.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Andrii Nakryiko <redacted>
Cc: Song Liu <song@kernel.org>
Cc: Masami Hiramatsu (Google) <mhiramat@kernel.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: pengdonglin <redacted>
Signed-off-by: pengdonglin <redacted>
---
 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?

[...]

quoted

+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.

quoted

+               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;
+       }

[...]