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: 14+ 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 ` Jim Cromie
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-29 18:07 ` Jim Cromie
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-29 18:07 ` Jim Cromie
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-29 18:07 ` Jim Cromie
2026-09-30 6:56 ` Kees Cook
2026-09-30 9:13 ` David Laight
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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.