include/linux/filter.h | 16 ++++++++++++++++ kernel/bpf/core.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ kernel/kallsyms.c | 34 ++++++++++++++++++++++++++++++++-- 3 files changed, 94 insertions(+), 2 deletions(-)
From: Ivan Babrou <ivan@cloudflare.com>
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.
Instead of doing that, we can cache the list of bpf symbols in linear
time when `/proc/kallsyms` is opened, which makes the whole thing fast.
Reading `/proc/kallsyms` on Apple M3 Pro in a VM and measuring system time:
Before:
* 15 bpf symbols: ~35ms
* 10015 bpf symbols: ~1250ms
After:
* 15 bpf symbols: ~35ms
* 10015 bpf symbols: ~50ms
Testing in production on v6.12 series (with ~10000 bpf ksyms as well):
* On AMD EPYC 9684X (Zen4): ~870ms -> ~100ms
* On Ampere Altra Max M128-30: ~4650ms -> ~70ms
Signed-off-by: Ivan Babrou <ivan@cloudflare.com>
---
include/linux/filter.h | 16 ++++++++++++++++
kernel/bpf/core.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
kernel/kallsyms.c | 34 ++++++++++++++++++++++++++++++++--
3 files changed, 94 insertions(+), 2 deletions(-)
diff --git a/include/linux/filter.h b/include/linux/filter.h
index 973233b82dc1..bbeef2d1b7f4 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -648,6 +648,11 @@ static inline bool insn_is_cast_user(const struct bpf_insn *insn)
offsetof(TYPE, MEMBER); \
})
+struct bpf_ksym_cache_entry {
+ unsigned long value;
+ char name[KSYM_NAME_LEN];
+};
+
/* A struct sock_filter is architecture independent. */
struct compat_sock_fprog {
u16 len;
@@ -1378,6 +1383,9 @@ int __bpf_address_lookup(unsigned long addr, unsigned long *size,
bool is_bpf_text_address(unsigned long addr);
int bpf_get_kallsym(unsigned int symnum, unsigned long *value, char *type,
char *sym);
+
+int bpf_get_all_kallsyms(struct bpf_ksym_cache_entry **cache_ptr,
+ unsigned int *count_ptr);
struct bpf_prog *bpf_prog_ksym_find(unsigned long addr);
static inline int
@@ -1446,6 +1454,14 @@ static inline int bpf_get_kallsym(unsigned int symnum, unsigned long *value,
return -ERANGE;
}
+static inline int bpf_get_all_kallsyms(struct bpf_ksym_cache_entry **cache_ptr,
+ unsigned int *count_ptr)
+{
+ *cache_ptr = NULL;
+ *count_ptr = 0;
+ return 0;
+}
+
static inline struct bpf_prog *bpf_prog_ksym_find(unsigned long addr)
{
return NULL;
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index d595fe512498..4b04865441e0 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -806,6 +806,52 @@ int bpf_get_kallsym(unsigned int symnum, unsigned long *value, char *type,
return ret;
}
+int bpf_get_all_kallsyms(struct bpf_ksym_cache_entry **cache_ptr,
+ unsigned int *count_ptr)
+{
+ struct bpf_ksym_cache_entry *cache;
+ struct bpf_ksym *ksym;
+ unsigned int count = 0;
+ unsigned int i = 0;
+
+ if (!bpf_jit_kallsyms_enabled()) {
+ *cache_ptr = NULL;
+ *count_ptr = 0;
+ return 0;
+ }
+
+ rcu_read_lock();
+ list_for_each_entry_rcu(ksym, &bpf_kallsyms, lnode)
+ count++;
+ rcu_read_unlock();
+
+ if (count == 0) {
+ *cache_ptr = NULL;
+ *count_ptr = 0;
+ return 0;
+ }
+
+ cache = kvmalloc_array(count, sizeof(*cache), GFP_KERNEL);
+ if (!cache)
+ return -ENOMEM;
+
+ rcu_read_lock();
+ list_for_each_entry_rcu(ksym, &bpf_kallsyms, lnode) {
+ if (i >= count) {
+ /* List grew since we counted, oh well */
+ break;
+ }
+ strscpy(cache[i].name, ksym->name, KSYM_NAME_LEN);
+ cache[i].value = ksym->start;
+ i++;
+ }
+ rcu_read_unlock();
+
+ *cache_ptr = cache;
+ *count_ptr = i;
+ return 0;
+}
+
int bpf_jit_add_poke_descriptor(struct bpf_prog *prog,
struct bpf_jit_poke_descriptor *poke)
{
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 1e7635864124..a41706a0b298 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -563,6 +563,8 @@ struct kallsym_iter {
char module_name[MODULE_NAME_LEN];
int exported;
int show_value;
+ struct bpf_ksym_cache_entry *bpf_cache;
+ unsigned int bpf_cache_count;
};
static int get_ksymbol_mod(struct kallsym_iter *iter)
@@ -600,11 +602,27 @@ static int get_ksymbol_ftrace_mod(struct kallsym_iter *iter)
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;
+ }
+
strscpy(iter->module_name, "bpf", MODULE_NAME_LEN);
iter->exported = 0;
- ret = bpf_get_kallsym(iter->pos - iter->pos_ftrace_mod_end,
+ ret = bpf_get_kallsym(index,
&iter->value, &iter->type,
iter->name);
if (ret < 0) {
@@ -859,9 +877,21 @@ static int kallsyms_open(struct inode *inode, struct file *file)
* the result here at open time.
*/
iter->show_value = kallsyms_show_value(file->f_cred);
+
+ bpf_get_all_kallsyms(&iter->bpf_cache, &iter->bpf_cache_count);
+
return 0;
}
+static int kallsyms_release(struct inode *inode, struct file *file)
+{
+ struct seq_file *m = file->private_data;
+ struct kallsym_iter *iter = m->private;
+
+ kvfree(iter->bpf_cache);
+ return seq_release_private(inode, file);
+}
+
#ifdef CONFIG_KGDB_KDB
const char *kdb_walk_kallsyms(loff_t *pos)
{
@@ -886,7 +916,7 @@ static const struct proc_ops kallsyms_proc_ops = {
.proc_open = kallsyms_open,
.proc_read = seq_read,
.proc_lseek = seq_lseek,
- .proc_release = seq_release_private,
+ .proc_release = kallsyms_release,
};
static int __init kallsyms_init(void)
---
base-commit: 7d0a66e4bb9081d75c82ec4957c50034cb0ea449
change-id: 20260129-ivan-bpf-ksym-cache-9a76daf22fc2
Best regards,
--
Ivan Babrou <ivan@cloudflare.com>On Thu, Jan 29, 2026 at 8:50 PM Ivan Babrou via B4 Relay
<devnull+ivan.cloudflare.com@kernel.org> wrote:
>
> From: Ivan Babrou <ivan@cloudflare.com>
>
> 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
On Thu, Feb 5, 2026 at 3:11 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Jan 29, 2026 at 8:50 PM Ivan Babrou via B4 Relay
> <devnull+ivan.cloudflare.com@kernel.org> wrote:
> >
> > From: Ivan Babrou <ivan@cloudflare.com>
> >
> > 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?
Very much real.
> > 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.
How do you feel about Florian's (cc'd) patch here?
* https://gist.github.com/florianl/41e2bce29ffde797536eef9b2e47ba92
I can take a stab at using bpf_tree like you suggested, but if you
like his patch, we can just go with that.
>
> pw-bot: cr
On Thu, Feb 5, 2026 at 7:24 PM Ivan Babrou <ivan@cloudflare.com> wrote:
>
> On Thu, Feb 5, 2026 at 3:11 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Thu, Jan 29, 2026 at 8:50 PM Ivan Babrou via B4 Relay
> > <devnull+ivan.cloudflare.com@kernel.org> wrote:
> > >
> > > From: Ivan Babrou <ivan@cloudflare.com>
> > >
> > > 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?
>
> Very much real.
I'm sure you know that each bpf prog is at least one page.
So you're burning 40 Mbyte minimum.
You need to redesign it. There is no reason to replicate
the more or less the same prog 10k times.
>
> > > 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.
>
> How do you feel about Florian's (cc'd) patch here?
>
> * https://gist.github.com/florianl/41e2bce29ffde797536eef9b2e47ba92
>
> I can take a stab at using bpf_tree like you suggested, but if you
> like his patch, we can just go with that.
Sigh. Did you think of RCU life times with that patch?
*iter = ksym;
rcu_read_unlock();
What happens with that value after unlock?
struct bpf_ksym *ksym = *iter;
what is being read here?
© 2016 - 2026 Red Hat, Inc.