From nobody Sun Feb 8 08:47:41 2026 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 44718D515; Fri, 30 Jan 2026 04:50:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769748612; cv=none; b=EcNk06Af/uM4Zh2qzuoy+8esB3L0dxa+zOGIYkcDJ//Y4g4Y6Pf16L5zPkX6z9OqmTEdlNsjFo4oqGC964CDU1inFkZo5c/iOv9859JwJypOYIkUM7QqTb2f1hM2AVIkBIsqeUp6W3Or+7/ySQe4z6/6F8/96hW8sf4al3nElYU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769748612; c=relaxed/simple; bh=JF6FXLSQF6Tm36QElrQo+xLZq9jhNkO3ZXXK6Fi0K/E=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:To:Cc; b=kyb0dM2IBWEpHfQwE2UdGA1YbHMcA5Z5cTUoIsKR3LHsANF9NOExCm0s+3D2G48bX23IOKlPEqgsoLJ6PzxmfpTTkgPeEx+6Ijk6XUsp/v4orWgx1M7f1C5Ki9HIuKwb+OVcHL+Qs/yEt/7o1BpAA5BIlxy+PfZ0E3couvOMjW8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=nUHilQoK; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="nUHilQoK" Received: by smtp.kernel.org (Postfix) with ESMTPS id 906EFC4CEF7; Fri, 30 Jan 2026 04:50:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1769748611; bh=JF6FXLSQF6Tm36QElrQo+xLZq9jhNkO3ZXXK6Fi0K/E=; h=From:Date:Subject:To:Cc:Reply-To:From; b=nUHilQoKnOH1J7PN14uJk0U29EK0XOYaRTMoOw8oG+iOfbc5LK7Y9RncmXej/z29u 6gnzN8R8LdljRWrVc8tZt6ItjfxBhzbpflkjyZIxjWuiTQx/SQIufRlc16TTWBurbu ageqM31iiHAEns+2Op7aBcNFyAU5p9fPutLt+TTGRtKsJmxHCdu+ehcPOTXJP7KPRt 3Y/cDQJCPdaekkPpYJnxB0jUTt4uUWJjr6lvEu0aA6pdQ7nYWP/vEaperV0W09naUK YkbxXCKe7fAehJxol6FyyhYBY3kag7o+FibHjGTqx7JW6hAGq8XpH9crmLR0u1kMsd CRcDJW3Xq4pKA== Received: from aws-us-west-2-korg-lkml-1.web.codeaurora.org (localhost.localdomain [127.0.0.1]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7AC77D73E9F; Fri, 30 Jan 2026 04:50:11 +0000 (UTC) From: Ivan Babrou via B4 Relay Date: Thu, 29 Jan 2026 20:50:09 -0800 Subject: [PATCH] kallsyms: cache bpf symbols to avoid quadratic iteration Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Message-Id: <20260129-ivan-bpf-ksym-cache-v1-1-ca503070dcc0@cloudflare.com> X-B4-Tracking: v=1; b=H4sIAIA4fGkC/x3MMQqAMAxA0atIZgOaoaJXEYdYUxvEKi2IIr27x fEN/7+QJKokGKoXolya9AgFbV2B9RxWQV2KgRoyTUs96sUB59Phlp4dLVsv2HNnFnZEzhKU8oz i9P6v45TzB35OvodlAAAA X-Change-ID: 20260129-ivan-bpf-ksym-cache-9a76daf22fc2 To: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , Yonghong Song , John Fastabend , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa Cc: bpf@vger.kernel.org, linux-kernel@vger.kernel.org, kernel-team@cloudflare.com, Ivan Babrou X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1769748610; l=6130; i=ivan@cloudflare.com; s=20260129; h=from:subject:message-id; bh=avRlwtbPUTu7O0+jWkoiT910bjkizQeh0wXWXc3nVW4=; b=N1IWMxMUHHUnVd74gRQtqU90xbq8LlA5QNfBpYnRDcSJeDfy0/LzjPA3aUcsvjjMXcnVNUvVA LvOtv03yHXTBJDElP+93zIL3yRyP0Bb8R8YpGtMJ1mmWTtg0BAJoDiS X-Developer-Key: i=ivan@cloudflare.com; a=ed25519; pk=QuczbiE/RJ0pw+SbDTjDyQUEsdy0dZym4mt+5Rp7PtA= X-Endpoint-Received: by B4 Relay for ivan@cloudflare.com/20260129 with auth_id=621 X-Original-From: Ivan Babrou Reply-To: ivan@cloudflare.com From: Ivan Babrou 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 --- 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); \ }) =20 +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); =20 static inline int @@ -1446,6 +1454,14 @@ static inline int bpf_get_kallsym(unsigned int symnu= m, unsigned long *value, return -ERANGE; } =20 +static inline int bpf_get_all_kallsyms(struct bpf_ksym_cache_entry **cache= _ptr, + unsigned int *count_ptr) +{ + *cache_ptr =3D NULL; + *count_ptr =3D 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; } =20 +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 =3D 0; + unsigned int i =3D 0; + + if (!bpf_jit_kallsyms_enabled()) { + *cache_ptr =3D NULL; + *count_ptr =3D 0; + return 0; + } + + rcu_read_lock(); + list_for_each_entry_rcu(ksym, &bpf_kallsyms, lnode) + count++; + rcu_read_unlock(); + + if (count =3D=3D 0) { + *cache_ptr =3D NULL; + *count_ptr =3D 0; + return 0; + } + + cache =3D 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 >=3D count) { + /* List grew since we counted, oh well */ + break; + } + strscpy(cache[i].name, ksym->name, KSYM_NAME_LEN); + cache[i].value =3D ksym->start; + i++; + } + rcu_read_unlock(); + + *cache_ptr =3D cache; + *count_ptr =3D 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; }; =20 static int get_ksymbol_mod(struct kallsym_iter *iter) @@ -600,11 +602,27 @@ static int get_ksymbol_ftrace_mod(struct kallsym_iter= *iter) =20 static int get_ksymbol_bpf(struct kallsym_iter *iter) { + unsigned int index =3D iter->pos - iter->pos_ftrace_mod_end; int ret; =20 + if (iter->bpf_cache) { + if (index >=3D iter->bpf_cache_count) { + iter->pos_bpf_end =3D iter->pos; + return 0; + } + + strscpy(iter->module_name, "bpf", MODULE_NAME_LEN); + iter->exported =3D 0; + strscpy(iter->name, iter->bpf_cache[index].name, KSYM_NAME_LEN); + iter->value =3D iter->bpf_cache[index].value; + iter->type =3D BPF_SYM_ELF_TYPE; + + return 1; + } + strscpy(iter->module_name, "bpf", MODULE_NAME_LEN); iter->exported =3D 0; - ret =3D bpf_get_kallsym(iter->pos - iter->pos_ftrace_mod_end, + ret =3D 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 f= ile *file) * the result here at open time. */ iter->show_value =3D kallsyms_show_value(file->f_cred); + + bpf_get_all_kallsyms(&iter->bpf_cache, &iter->bpf_cache_count); + return 0; } =20 +static int kallsyms_release(struct inode *inode, struct file *file) +{ + struct seq_file *m =3D file->private_data; + struct kallsym_iter *iter =3D 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 =3D { .proc_open =3D kallsyms_open, .proc_read =3D seq_read, .proc_lseek =3D seq_lseek, - .proc_release =3D seq_release_private, + .proc_release =3D kallsyms_release, }; =20 static int __init kallsyms_init(void) --- base-commit: 7d0a66e4bb9081d75c82ec4957c50034cb0ea449 change-id: 20260129-ivan-bpf-ksym-cache-9a76daf22fc2 Best regards, --=20 Ivan Babrou