Re: [PATCH] kallsyms: cache bpf symbols to avoid quadratic iteration

[Alexei Starovoitov]

On Thu, Jan 29, 2026 at 8:50 PM Ivan Babrou via B4 Relay
<devnull+ivan.cloudflare.com@xxxxxxxxxx> wrote:
>
> From: Ivan Babrou <ivan@xxxxxxxxxxxxxx>
>
> The existing code iterates the whole list of bpf ksyms until the right
> one is found, which means quadratic complexity on top of linked list
> pointer chasing under rcu. This is't noticeable for most installations,
> but when one has 10000 bpf programs loaded, things start to add up and
> reading from `/proc/kallsyms` slows down a lot.

How real is this? 10k bpf programs?

>  static int get_ksymbol_bpf(struct kallsym_iter *iter)
>  {
> +       unsigned int index = iter->pos - iter->pos_ftrace_mod_end;
>         int ret;
>
> +       if (iter->bpf_cache) {
> +               if (index >= iter->bpf_cache_count) {
> +                       iter->pos_bpf_end = iter->pos;
> +                       return 0;
> +               }
> +
> +               strscpy(iter->module_name, "bpf", MODULE_NAME_LEN);
> +               iter->exported = 0;
> +               strscpy(iter->name, iter->bpf_cache[index].name, KSYM_NAME_LEN);
> +               iter->value = iter->bpf_cache[index].value;
> +               iter->type = BPF_SYM_ELF_TYPE;
> +
> +               return 1;
> +       }

I'm sure there are other ways to speed up get_ksymbol_bpf().
bpf_kallsyms is a list, but the same symbols are also in
struct latch_tree_root bpf_tree
Integrate it into get_ksymbol_bpf().
latch_tree_find() will be surely faster than linear search in the list.
Or go the extra mile and implement an iterator for latch_tree.

pw-bot: cr