From: Kees Cook <kees@kernel.org>
To: jim.cromie@gmail.com
Cc: Andrew Morton <akpm@linux-foundation.org>,
Petr Mladek <pmladek@suse.com>,
Zhen Lei <thunder.leizhen@huawei.com>,
Luis Chamberlain <mcgrof@kernel.org>,
Andrey Grodzovsky <andrey.grodzovsky@crowdstrike.com>,
Steven Rostedt <rostedt@goodmis.org>,
Lorenzo Stoakes <ljs@kernel.org>,
David Laight <david.laight.linux@gmail.com>,
Masahiro Yamada <masahiroy@kernel.org>,
Jiri Olsa <olsajiri@gmail.com>,
linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org,
bpf@vger.kernel.org
Subject: Re: [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups
Date: Tue, 29 Sep 2026 23:28:26 -0700 [thread overview]
Message-ID: <202609292326.C88BC5F0@keescook> (raw)
In-Reply-To: <20260929-ksyms-tune-v7-2-be568ceef41e@gmail.com>
On Tue, Sep 29, 2026 at 12:07:31PM -0600, Jim Cromie via B4 Relay wrote:
> Without altering the underlying storage layout, we can retune this
> trade-off directly by increasing marker density from 256:1 down to
> 16:1 (KALLSYMS_MARKER_SHIFT 4) in kernel/kallsyms_internal.h, shared
> between scripts/kallsyms.c and kernel/kallsyms.c.
>
> This caps the remainder scan at 15 symbols and cuts average scan distance
> from 127.5 down to 7.5 hops (a 17x reduction). Across a 17-step binary
> search, total hops collapse from ~2,170 down to ~127. For a kernel with
> ~184,000 symbols, this adds ~10,800 u32 marker entries (+42 KiB) to
> write-protected .rodata.
Thanks for trying a non 1:1 route. I think this is a reasonable time/space
trade-off. ~42k .rodata to get a large speed-up.
Reviewed-by: Kees Cook <kees@kernel.org>
--
Kees Cook
next prev parent reply other threads:[~2026-09-30 6:28 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-09-29 18:07 [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Jim Cromie via B4 Relay
2026-09-29 18:07 ` [PATCH v7 1/3] kallsyms: Match compressed tokens on the fly during binary search Jim Cromie via B4 Relay
2026-09-30 1:17 ` bot+bpf-ci
2026-09-30 6:26 ` Kees Cook
2026-09-29 18:07 ` [PATCH v7 2/3] kallsyms: Increase marker density to 16:1 to accelerate lookups Jim Cromie via B4 Relay
2026-09-30 6:28 ` Kees Cook [this message]
2026-09-29 18:07 ` [PATCH v7 3/3] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() Jim Cromie via B4 Relay
2026-09-30 6:56 ` Kees Cook
2026-09-29 18:45 ` [PATCH v7 0/3] kallsyms: Accelerate symbol name lookups by ~7x Andrew Morton
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=202609292326.C88BC5F0@keescook \
--to=kees@kernel.org \
--cc=akpm@linux-foundation.org \
--cc=andrey.grodzovsky@crowdstrike.com \
--cc=bpf@vger.kernel.org \
--cc=david.laight.linux@gmail.com \
--cc=jim.cromie@gmail.com \
--cc=linux-kbuild@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=ljs@kernel.org \
--cc=masahiroy@kernel.org \
--cc=mcgrof@kernel.org \
--cc=olsajiri@gmail.com \
--cc=pmladek@suse.com \
--cc=rostedt@goodmis.org \
--cc=thunder.leizhen@huawei.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®