* [PATCH v4 1/4] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency
2026-09-22 20:08 [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Jim Cromie
@ 2026-09-22 20:08 ` Jim Cromie
2026-09-22 20:08 ` [PATCH v4 2/4] kallsyms: Match compressed tokens on the fly during binary search Jim Cromie
` (3 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: Jim Cromie @ 2026-09-22 20:08 UTC (permalink / raw)
To: Andrew Morton
Cc: Lorenzo Stoakes, Kees Cook, David Laight, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf, Jim Cromie
To evaluate optimizations and measure performance regressions across
kallsyms lookups, add a lightweight microbenchmark module in lib/.
Configure CONFIG_TEST_KALLSYMS_PERF as a built-in test (bool) rather
than a loadable module (tristate). Building the test directly into
vmlinux allows exercising internal kallsyms traversal APIs without
exporting internal symbol iterators (EXPORT_SYMBOL_GPL) to modules,
preserving kernel symbol table encapsulation.
The module exercises the primary kallsyms resolution paths:
0. Name-to-Address binary search: Benchmarks lookups across common
kernel functions (hits) and non-existent symbol strings (misses,
exercising the full binary search tree depth).
1. Address-to-Name resolution: Benchmarks address decoding latency
via sprint_symbol() and sprint_symbol_no_offset().
2. Sequential table scan: Measures complete table iteration latency
via kallsyms_on_each_symbol().
The module exposes a num_iters parameter (default: 100,000) and a
sysfs trigger to repeat benchmark runs on demand.
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v4:
- Ignore early boot invocations in param_set_trigger() when system_state
< SYSTEM_RUNNING to prevent NULL pointer dereference in ktime_get_ns()
prior to timekeeping_init() (addresses Sashiko AI review).
- Prevent sysfs TOCTOU divide-by-zero panic: reject num_iters == 0 in
param setter, snapshot iters locally via READ_ONCE, and serialize runs
with bench_lock mutex (addresses Sashiko AI review).
- Eliminate multi-second boot stall: add run_on_boot parameter (default
false) so late_initcall only runs benchmark when explicitly requested
(addresses Sashiko AI review).
- Chunk lookup loops in 4096-iter batches with cond_resched() outside
the timing bracket to prevent preemption sleep time from inflating
reported latency (addresses Sashiko AI review).
Changes in v3:
- Convert CONFIG_TEST_KALLSYMS_PERF from tristate to bool and drop
kallsyms iterator EXPORT_SYMBOL_GPL exports to preserve security
encapsulation (addresses Sashiko AI review).
- Drop 'default m' from lib/Kconfig.debug.
- Add cond_resched() every 16k iterations to avoid soft lockups.
- Replace direct 64-bit division with div_u64() to fix 32-bit builds.
- Guard against divide-by-zero when num_iters=0.
- Replace tcp_v4_rcv with panic in hit_symbols to prevent failures wo
CONFIG_INET.
- Switch to late_initcall for built-in invocation.
---
lib/Kconfig.debug | 10 ++
lib/Makefile | 1 +
lib/test_kallsyms_perf.c | 302 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 313 insertions(+)
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 134b15a44625..4b9669e64db9 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -3122,6 +3122,16 @@ config TEST_STATIC_KEYS
If unsure, say N.
+config TEST_KALLSYMS_PERF
+ bool "kallsyms performance benchmark test module"
+ depends on KALLSYMS
+ help
+ This builds test_kallsyms_perf to benchmark latency across
+ Name-to-Address binary search, Address-to-Name resolution,
+ and full table walks.
+
+ If unsure, say N.
+
config TEST_DYNAMIC_DEBUG
tristate "Test DYNAMIC_DEBUG"
depends on DYNAMIC_DEBUG
diff --git a/lib/Makefile b/lib/Makefile
index dfab958327c5..149968ff3f6b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -85,6 +85,7 @@ obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o
obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_keys.o
obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_key_base.o
obj-$(CONFIG_TEST_DYNAMIC_DEBUG) += test_dynamic_debug.o
+obj-$(CONFIG_TEST_KALLSYMS_PERF) += test_kallsyms_perf.o
obj-$(CONFIG_TEST_BITMAP) += test_bitmap.o
ifeq ($(CONFIG_CC_IS_CLANG)$(CONFIG_KASAN),yy)
diff --git a/lib/test_kallsyms_perf.c b/lib/test_kallsyms_perf.c
new file mode 100644
index 000000000000..03ff5f1d51c5
--- /dev/null
+++ b/lib/test_kallsyms_perf.c
@@ -0,0 +1,302 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * Microbenchmark and correctness test module for kallsyms subsystem
+ *
+ * Measures CPU latency across:
+ * - Name-to-Address binary search (hits & misses)
+ * - Address-to-Name symbol resolution (sprint_symbol, buildid)
+ * - Full kernel symbol iteration (kallsyms_on_each_symbol)
+ */
+
+#define pr_fmt(fmt) "test_kallsyms: " fmt
+
+#include <linux/init.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/kallsyms.h>
+#include <linux/ktime.h>
+#include <linux/compiler.h>
+#include <linux/sched.h>
+#include <linux/math.h>
+#include <linux/mutex.h>
+#include <linux/minmax.h>
+
+#define BENCH_CHUNK_SIZE 4096
+
+static unsigned int num_iters = 100000;
+
+static int param_set_num_iters(const char *val, const struct kernel_param *kp)
+{
+ unsigned int n;
+ int ret;
+
+ ret = kstrtouint(val, 0, &n);
+ if (ret)
+ return ret;
+ if (!n)
+ return -EINVAL;
+
+ *((unsigned int *)kp->arg) = n;
+ return 0;
+}
+
+static const struct kernel_param_ops param_ops_num_iters = {
+ .set = param_set_num_iters,
+ .get = param_get_uint,
+};
+module_param_cb(num_iters, ¶m_ops_num_iters, &num_iters, 0644);
+MODULE_PARM_DESC(num_iters, "Number of iterations per microbenchmark (must be > 0)");
+
+static bool run_on_boot;
+module_param(run_on_boot, bool, 0444);
+MODULE_PARM_DESC(run_on_boot, "Run benchmark during boot (default: false)");
+
+static DEFINE_MUTEX(bench_lock);
+
+static const char * const hit_symbols[] = {
+ "_printk",
+ "schedule",
+ "vfs_read",
+ "do_sys_openat2",
+ "kernel_clone",
+ "panic",
+ "kallsyms_lookup_names",
+ "vm_area_alloc",
+};
+
+static const char * const miss_symbols[] = {
+ "nonexistent_symbol_0001",
+ "xyz_dummy_missing_symbol",
+ "__never_compiled_in_kernel",
+ "ext4_nonexistent_func_xyz",
+ "bpf_not_real_helper_stub",
+ "vfs_missing_handler_probe",
+ "tcp_v4_unimplemented_path",
+ "driver_fake_init_routine",
+};
+
+static int match_cb(void *data, unsigned long addr)
+{
+ unsigned long *out = data;
+
+ *out = addr;
+ return 1;
+}
+
+static int count_cb(void *data, const char *name, unsigned long addr)
+{
+ unsigned long *cnt = data;
+
+ (*cnt)++;
+ return 0;
+}
+
+static void run_name_lookup_bench(unsigned int iters)
+{
+ u64 t0, t1, dt_hit = 0, dt_miss = 0;
+ unsigned long addr = 0;
+ unsigned int i, nr_hits, nr_misses;
+
+ nr_hits = ARRAY_SIZE(hit_symbols);
+ nr_misses = ARRAY_SIZE(miss_symbols);
+
+ /* 0. Correctness validation */
+ for (i = 0; i < nr_hits; i++) {
+ const char *sym = hit_symbols[i];
+ unsigned long a1 = 0;
+
+ kallsyms_on_each_match_symbol(match_cb, sym, &a1);
+ if (!a1)
+ pr_err("CORRECTNESS FAILURE: hit sym '%s' not found\n", sym);
+ }
+ for (i = 0; i < nr_misses; i++) {
+ const char *sym = miss_symbols[i];
+ unsigned long a1 = 0;
+
+ kallsyms_on_each_match_symbol(match_cb, sym, &a1);
+ if (a1)
+ pr_err("CORRECTNESS FAILURE: miss sym '%s' unexpectedly found a1=%lx\n",
+ sym, a1);
+ }
+
+ /* 1. Name search: Existing symbols (Hits) */
+ for (i = 0; i < iters; i += BENCH_CHUNK_SIZE) {
+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i);
+ unsigned int j;
+
+ cond_resched();
+ t0 = ktime_get_ns();
+ for (j = 0; j < chunk; j++) {
+ const char *sym = hit_symbols[(i + j) % nr_hits];
+
+ kallsyms_on_each_match_symbol(match_cb, sym, &addr);
+ OPTIMIZER_HIDE_VAR(addr);
+ }
+ t1 = ktime_get_ns();
+ dt_hit += t1 - t0;
+ }
+
+ /* 2. Name search: Non-existent symbols (Misses - 17 bsearch probes) */
+ for (i = 0; i < iters; i += BENCH_CHUNK_SIZE) {
+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i);
+ unsigned int j;
+
+ cond_resched();
+ t0 = ktime_get_ns();
+ for (j = 0; j < chunk; j++) {
+ const char *sym = miss_symbols[(i + j) % nr_misses];
+
+ kallsyms_on_each_match_symbol(match_cb, sym, &addr);
+ OPTIMIZER_HIDE_VAR(addr);
+ }
+ t1 = ktime_get_ns();
+ dt_miss += t1 - t0;
+ }
+
+ pr_info("Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\n",
+ div_u64(dt_hit, iters), div_u64(dt_hit, 1000000), iters);
+ pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
+ div_u64(dt_miss, iters), div_u64(dt_miss, 1000000), iters);
+}
+
+static void run_address_lookup_bench(unsigned int iters)
+{
+ u64 t0, t1, dt_sprint = 0, dt_bldid = 0;
+ char symname[KSYM_SYMBOL_LEN];
+ unsigned long addrs[ARRAY_SIZE(hit_symbols)];
+ unsigned int i, nr_addrs = 0;
+
+ for (i = 0; i < ARRAY_SIZE(hit_symbols); i++) {
+ unsigned long addr = 0;
+
+ kallsyms_on_each_match_symbol(match_cb, hit_symbols[i], &addr);
+ if (addr)
+ addrs[nr_addrs++] = addr;
+ }
+
+ if (!nr_addrs) {
+ pr_warn("Address benchmark skipped: no test addresses resolved\n");
+ return;
+ }
+
+ /* 1. Address-to-name resolution (sprint_symbol) */
+ for (i = 0; i < iters; i += BENCH_CHUNK_SIZE) {
+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i);
+ unsigned int j;
+
+ cond_resched();
+ t0 = ktime_get_ns();
+ for (j = 0; j < chunk; j++) {
+ unsigned long addr = addrs[(i + j) % nr_addrs];
+
+ sprint_symbol(symname, addr);
+ barrier_data(symname);
+ }
+ t1 = ktime_get_ns();
+ dt_sprint += t1 - t0;
+ }
+
+ /* 2. Address without offset (sprint_symbol_no_offset) */
+ for (i = 0; i < iters; i += BENCH_CHUNK_SIZE) {
+ unsigned int chunk = min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i);
+ unsigned int j;
+
+ cond_resched();
+ t0 = ktime_get_ns();
+ for (j = 0; j < chunk; j++) {
+ unsigned long addr = addrs[(i + j) % nr_addrs];
+
+ sprint_symbol_no_offset(symname, addr);
+ barrier_data(symname);
+ }
+ t1 = ktime_get_ns();
+ dt_bldid += t1 - t0;
+ }
+
+ pr_info("sprint_symbol: %llu ns/lookup (%llu ms total, %u iters)\n",
+ div_u64(dt_sprint, iters), div_u64(dt_sprint, 1000000), iters);
+ pr_info("sprint_symbol_no_offset: %llu ns/lookup (%llu ms total, %u iters)\n",
+ div_u64(dt_bldid, iters), div_u64(dt_bldid, 1000000), iters);
+}
+
+static void run_table_walk_bench(void)
+{
+ u64 t0, t1, dt_walk = 0;
+ unsigned long total_symbols = 0;
+ int iter = 50;
+ int i;
+
+ for (i = 0; i < iter; i++) {
+ total_symbols = 0;
+ cond_resched();
+ t0 = ktime_get_ns();
+ kallsyms_on_each_symbol(count_cb, &total_symbols);
+ t1 = ktime_get_ns();
+ dt_walk += t1 - t0;
+ }
+
+ pr_info("Table Full Walk: %llu ns/sym (%llu us/pass, %lu symbols scanned, %d passes)\n",
+ div_u64(div_u64(dt_walk, iter), total_symbols ? total_symbols : 1),
+ div_u64(div_u64(dt_walk, iter), 1000), total_symbols, iter);
+}
+
+static int run_kallsyms_benchmark(void)
+{
+ unsigned int iters;
+ int ret = 0;
+
+ if (!mutex_trylock(&bench_lock)) {
+ pr_warn("Benchmark already running\n");
+ return -EBUSY;
+ }
+
+ iters = READ_ONCE(num_iters);
+ if (!iters) {
+ pr_err("num_iters must be non-zero\n");
+ ret = -EINVAL;
+ goto out;
+ }
+
+ pr_info("==================================================\n");
+ pr_info("Starting kallsyms performance benchmark (iters=%u)\n", iters);
+ pr_info("==================================================\n");
+
+ run_name_lookup_bench(iters);
+ run_address_lookup_bench(iters);
+ run_table_walk_bench();
+
+ pr_info("==================================================\n");
+ pr_info("kallsyms benchmark complete\n");
+ pr_info("==================================================\n");
+
+out:
+ mutex_unlock(&bench_lock);
+ return ret;
+}
+
+static int param_set_trigger(const char *val, const struct kernel_param *kp)
+{
+ if (system_state < SYSTEM_RUNNING) {
+ pr_warn("Early boot run ignored; use test_kallsyms_perf.run_on_boot=1 or trigger via sysfs\n");
+ return 0;
+ }
+ return run_kallsyms_benchmark();
+}
+
+static const struct kernel_param_ops param_ops_trigger = {
+ .set = param_set_trigger,
+};
+module_param_cb(run_test, ¶m_ops_trigger, NULL, 0200);
+MODULE_PARM_DESC(run_test, "Write 1 to trigger kallsyms benchmark run");
+
+static int __init test_kallsyms_init(void)
+{
+ if (run_on_boot)
+ return run_kallsyms_benchmark();
+ return 0;
+}
+late_initcall(test_kallsyms_init);
+
+MODULE_DESCRIPTION("Microbenchmark test module for kallsyms subsystem");
+MODULE_AUTHOR("Jim Cromie <jim.cromie@gmail.com>");
+MODULE_LICENSE("GPL");
--
2.55.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH v4 2/4] kallsyms: Match compressed tokens on the fly during binary search
2026-09-22 20:08 [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Jim Cromie
2026-09-22 20:08 ` [PATCH v4 1/4] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency Jim Cromie
@ 2026-09-22 20:08 ` Jim Cromie
2026-09-22 20:08 ` [PATCH v4 3/4] kallsyms: Add dynamic lookup index for batch resolution Jim Cromie
` (2 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: Jim Cromie @ 2026-09-22 20:08 UTC (permalink / raw)
To: Andrew Morton
Cc: Lorenzo Stoakes, Kees Cook, David Laight, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf, Jim Cromie
kallsyms_lookup_names() runs a binary search across kallsyms_names[],
a packed array of ~130k encoded kernel symbols. For each of the ~17
comparisons in the search, it currently decompresses the candidate
symbol into a temporary buffer on the stack before calling strcmp().
Comparing raw tokens directly in compressed space is impossible. The
BPE token table assigns values by frequency, not alphabetical order
(e.g. token 0x05 might expand to "zebra" while 0x42 expands to "apple"),
so comparing raw token values scrambles lexicographical order.
However, full string expansion is equally wasteful: roughly 16 of the
17 binary search steps fail within the first two characters.
Introduce kallsyms_strcmp_symbol() to compare ASCII queries against
compressed tokens on the fly. It walks kallsyms_token_index and
kallsyms_token_table incrementally, matching characters directly and
bailing out on the first character mismatch without expanding subsequent
tokens.
This optimization:
0. Avoids decompressing non-matching tokens, short-circuiting ~94% of
binary search character expansions without adding any tables in
.rodata.
1. Drops the 512-byte namebuf buffer from the kernel stack in
kallsyms_lookup_names().
2. Cuts unindexed lookup latency by ~530 ns (~14% faster) while leaving
sequential address ordering and kallsyms_expand_symbol() streaming
invariants intact for /proc/kallsyms and table walks.
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v3:
- Reorder patch ahead of dynamic batch index in series, establishing an
active proof of string matching savings on unindexed baseline
(addresses David Laight review).
- Optimize kallsyms_strcmp_symbol(): drop skipped_first tracking and
test len at loop bottom (addresses David Laight review).
- Guard first token with while (*tptr) to handle 1-byte type tokens.
- Introduce get_symbol_data() helper in this patch for reuse in later
subsystems.
Changes in v2:
- Rebase onto mainline v7.3-rc4, removing external dependencies on
Lorenzo Stoakes' kbuild series.
---
kernel/kallsyms.c | 94 ++++++++++++++++++++++++++++++++++---------------------
1 file changed, 59 insertions(+), 35 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index aec2f06858af..d18d78e626db 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -34,6 +34,21 @@
#include "kallsyms_internal.h"
+/*
+ * Get the compressed symbol length and data pointer.
+ */
+static inline const u8 *get_symbol_data(unsigned int off, unsigned int *len)
+{
+ const u8 *p = &kallsyms_names[off];
+ unsigned int l = *p++;
+
+ if (unlikely(l & 0x80))
+ l = (l & 0x7F) | (*p++ << 7);
+ *len = l;
+
+ return p;
+}
+
/*
* Expand a compressed symbol data into the resulting uncompressed string,
* if uncompressed string is too long (>= maxlen), it will be truncated,
@@ -42,28 +57,12 @@
static unsigned int kallsyms_expand_symbol(unsigned int off,
char *result, size_t maxlen)
{
- int len, skipped_first = 0;
+ int skipped_first = 0;
const char *tptr;
- const u8 *data;
+ unsigned int len;
+ const u8 *data = get_symbol_data(off, &len);
- /* Get the compressed symbol length from the first symbol byte. */
- data = &kallsyms_names[off];
- len = *data;
- data++;
- off++;
-
- /* If MSB is 1, it is a "big" symbol, so needs an additional byte. */
- if ((len & 0x80) != 0) {
- len = (len & 0x7F) | (*data << 7);
- data++;
- off++;
- }
-
- /*
- * Update the offset to return the offset for the next symbol on
- * the compressed stream.
- */
- off += len;
+ off = (data - kallsyms_names) + len;
/*
* For every byte on the compressed symbol data, copy the table
@@ -101,14 +100,43 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
*/
static char kallsyms_get_symbol_type(unsigned int off)
{
- /*
- * Get just the first code, look it up in the token table,
- * and return the first char from this token. If MSB of length
- * is 1, it is a "big" symbol, so needs an additional byte.
- */
- if (kallsyms_names[off] & 0x80)
- off++;
- return kallsyms_token_table[kallsyms_token_index[kallsyms_names[off + 1]]];
+ unsigned int len;
+ const u8 *data = get_symbol_data(off, &len);
+
+ return kallsyms_token_table[kallsyms_token_index[*data]];
+}
+
+/*
+ * Compare an uncompressed ASCII string against a compressed symbol table entry.
+ * Returns negative if name < sym, positive if name > sym, 0 if equal.
+ * Exits immediately on the first mismatched character without decompressing
+ * the rest of the symbol name.
+ */
+static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
+{
+ const char *tptr;
+ unsigned int len;
+ const u8 *data = get_symbol_data(off, &len);
+
+ tptr = &kallsyms_token_table[kallsyms_token_index[*data++]] + 1;
+ while (*tptr) {
+ int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+ if (diff)
+ return diff;
+ }
+
+ while (--len) {
+ tptr = &kallsyms_token_table[kallsyms_token_index[*data++]];
+ do {
+ int diff = (unsigned char)*name++ - (unsigned char)*tptr++;
+
+ if (diff)
+ return diff;
+ } while (*tptr);
+ }
+
+ return (unsigned char)*name;
}
@@ -174,7 +202,6 @@ static int kallsyms_lookup_names(const char *name,
int ret;
int low, mid, high;
unsigned int seq, off;
- char namebuf[KSYM_NAME_LEN];
low = 0;
high = kallsyms_num_syms - 1;
@@ -183,8 +210,7 @@ static int kallsyms_lookup_names(const char *name,
mid = low + (high - low) / 2;
seq = get_symbol_seq(mid);
off = get_symbol_offset(seq);
- kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
- ret = strcmp(name, namebuf);
+ ret = kallsyms_strcmp_symbol(off, name);
if (ret > 0)
low = mid + 1;
else if (ret < 0)
@@ -200,8 +226,7 @@ static int kallsyms_lookup_names(const char *name,
while (low) {
seq = get_symbol_seq(low - 1);
off = get_symbol_offset(seq);
- kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
- if (strcmp(name, namebuf))
+ if (kallsyms_strcmp_symbol(off, name) != 0)
break;
low--;
}
@@ -212,8 +237,7 @@ static int kallsyms_lookup_names(const char *name,
while (high < kallsyms_num_syms - 1) {
seq = get_symbol_seq(high + 1);
off = get_symbol_offset(seq);
- kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
- if (strcmp(name, namebuf))
+ if (kallsyms_strcmp_symbol(off, name) != 0)
break;
high++;
}
--
2.55.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH v4 3/4] kallsyms: Add dynamic lookup index for batch resolution
2026-09-22 20:08 [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Jim Cromie
2026-09-22 20:08 ` [PATCH v4 1/4] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency Jim Cromie
2026-09-22 20:08 ` [PATCH v4 2/4] kallsyms: Match compressed tokens on the fly during binary search Jim Cromie
@ 2026-09-22 20:08 ` Jim Cromie
2026-09-22 20:08 ` [PATCH v4 4/4] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() Jim Cromie
2026-09-23 7:12 ` [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Kees Cook
4 siblings, 0 replies; 7+ messages in thread
From: Jim Cromie @ 2026-09-22 20:08 UTC (permalink / raw)
To: Andrew Morton
Cc: Lorenzo Stoakes, Kees Cook, David Laight, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf, Jim Cromie
kallsyms_lookup_names() resolves symbol names to addresses using a
binary search over kallsyms_seqs_of_names[]. In baseline, each step
invokes get_symbol_offset(), which scans sequentially from the nearest
256-symbol marker in kallsyms_names[] (averaging ~128 ULEB128 header
decodes per probe, ~2,176 decodes per lookup).
During bulk symbol resolution workloads (e.g. BPF multi-kprobe / fprobe
tracing attaching across tens of thousands of functions), this linear
scan compounds into substantial kernel attach latency (~3.3 us per
lookup). Baking a permanent direct index into .rodata accelerates
lookups but consumes hundreds of KiB of unswappable kernel image memory,
which is unjustified when bulk lookups are infrequent.
Introduce a dynamic u32 lookup index populated on demand in transient
RAM and discarded when the batch workload completes:
0. Expose kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end()
bracketed by a mutex and refcount. On the first caller, allocate a
flat u32 table spanning all kallsyms_num_syms entries (~736 KiB in
transient RAM for ~184k symbols) via kvmalloc_array() and populate
the symbol offsets via a single sequential scan in ~150 us.
1. In get_symbol_offset(), when the dynamic table is active, return
offsets[pos] directly as an O(1) array access with 0 hops, bracketed
by rcu_read_lock() and rcu_read_unlock().
2. If the dynamic table is unallocated (refcount 0), fall back to the
legacy kallsyms_markers[] scan, preserving 100% safety for oops,
panic, NMI, and low-memory environments without any .rodata bloat.
3. Wrap kallsyms_lookup_names() in rcu_read_lock() / rcu_read_unlock()
to ensure lockless lifetime safety across multi-probe searches.
4. Update test_kallsyms_perf and kallsyms_selftest to benchmark both
unindexed marker scans and the dynamic batch index side by side,
reporting batch lookup performance alongside query amortization
break-even points.
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v4:
- Annotate dyn_kallsyms_offsets declaration with __rcu to satisfy sparse
type checking and prevent address-space warnings across
rcu_assign_pointer() and rcu_dereference() (addresses Sashiko AI review).
- Use rcu_replace_pointer() with lockdep_is_held(&dyn_kallsyms_mutex)
during batch teardown to atomically read and clear the pointer while
satisfying sparse address-space constraints (addresses Sashiko AI review).
Changes in v3:
- Reorder patch after on-the-fly token matching (patch 2) to cleanly
isolate and measure the impact of the O(1) dynamic table on top of
fast string matching (addresses David Laight review).
- Consume get_symbol_data() helper introduced in patch 2 to preserve
clean git bisectability (addresses Sashiko AI review).
- Fix use-after-free race on dyn_kallsyms_offsets: bracket table
dereference and array read with rcu_read_lock() and replace
rcu_dereference_raw() with rcu_dereference() inside
get_symbol_offset() to protect external readers (lookup_symbol_name,
kallsyms_lookup_buildid, reset_iter) against concurrent batch
teardown (addresses Sashiko AI review).
- In kallsyms_selftest, add a second lookup pass bracketed by
kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end() to
validate batch resolution in the in-tree selftest.
- Move 24-bit loop unrolling in get_symbol_seq() to standalone patch 4
(addresses David Laight review).
- Move David Laight to series-wide Cc on cover letter, dropping trailer
from this patch.
Changes in v2:
- Rework from static build-time 3-byte table to dynamic u32 index
allocated in transient RAM during batch sessions, dropping +573 KiB
from .rodata to 0 bytes (addresses Kees Cook review).
- Use native u32 indexing to eliminate 24-bit big-endian shifts and
unaligned loads (addresses David Laight review).
- Revert changes to scripts/kallsyms.c and kernel/kallsyms_internal.h,
retaining legacy kallsyms_markers[] as fallback.
---
include/linux/kallsyms.h | 13 ++++++
kernel/kallsyms.c | 111 ++++++++++++++++++++++++++++++++++++++++++---
kernel/kallsyms_selftest.c | 16 +++++++
lib/test_kallsyms_perf.c | 51 ++++++++++++++++++---
4 files changed, 179 insertions(+), 12 deletions(-)
diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h
index d5dd54c53ace..6e39795ac509 100644
--- a/include/linux/kallsyms.h
+++ b/include/linux/kallsyms.h
@@ -74,6 +74,10 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long),
int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long),
const char *name, void *data);
+/* Transient dynamic lookup index bracketing */
+int kallsyms_lookup_batch_start(void);
+void kallsyms_lookup_batch_end(void);
+
/* Lookup the address for a symbol. Returns 0 if not found. */
unsigned long kallsyms_lookup_name(const char *name);
@@ -164,6 +168,15 @@ static inline int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long)
{
return -EOPNOTSUPP;
}
+
+static inline int kallsyms_lookup_batch_start(void)
+{
+ return 0;
+}
+
+static inline void kallsyms_lookup_batch_end(void)
+{
+}
#endif /*CONFIG_KALLSYMS*/
static inline void print_ip_sym(const char *loglvl, unsigned long ip)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index d18d78e626db..bb34b4c0f690 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -22,6 +22,9 @@
#include <linux/sched.h> /* for cond_resched */
#include <linux/ctype.h>
#include <linux/slab.h>
+#include <linux/vmalloc.h>
+#include <linux/mutex.h>
+#include <linux/rcupdate.h>
#include <linux/filter.h>
#include <linux/ftrace.h>
#include <linux/kprobes.h>
@@ -90,7 +93,7 @@ static unsigned int kallsyms_expand_symbol(unsigned int off,
if (maxlen)
*result = '\0';
- /* Return to offset to the next symbol. */
+ /* Return offset to the next symbol. */
return off;
}
@@ -139,12 +142,11 @@ static int kallsyms_strcmp_symbol(unsigned int off, const char *name)
return (unsigned char)*name;
}
-
/*
- * Find the offset on the compressed stream given and index in the
- * kallsyms array.
+ * Find the offset on the compressed stream given an index in the
+ * kallsyms array using legacy markers.
*/
-static unsigned int get_symbol_offset(unsigned long pos)
+static unsigned int get_symbol_offset_marker(unsigned long pos)
{
const u8 *name;
int i, len;
@@ -177,6 +179,99 @@ static unsigned int get_symbol_offset(unsigned long pos)
return name - kallsyms_names;
}
+/*
+ * Dynamic symbol offset table.
+ * Allocated on demand during high-volume lookup batches and reclaimed after.
+ */
+static u32 __rcu *dyn_kallsyms_offsets __read_mostly;
+static DEFINE_MUTEX(dyn_kallsyms_mutex);
+static unsigned int dyn_kallsyms_refcnt;
+
+static u32 *kallsyms_build_offsets(void)
+{
+ const u8 *name = kallsyms_names;
+ u32 *offsets;
+ unsigned int i;
+
+ offsets = kvmalloc_array(kallsyms_num_syms, sizeof(u32), GFP_KERNEL);
+ if (!offsets)
+ return NULL;
+
+ for (i = 0; i < kallsyms_num_syms; i++) {
+ unsigned int len;
+ const u8 *data;
+
+ offsets[i] = name - kallsyms_names;
+ data = get_symbol_data(offsets[i], &len);
+ name = data + len;
+ }
+
+ return offsets;
+}
+
+int kallsyms_lookup_batch_start(void)
+{
+ int ret = 0;
+
+ mutex_lock(&dyn_kallsyms_mutex);
+ if (!dyn_kallsyms_refcnt) {
+ u32 *offsets = kallsyms_build_offsets();
+
+ if (!offsets) {
+ ret = -ENOMEM;
+ goto out;
+ }
+ rcu_assign_pointer(dyn_kallsyms_offsets, offsets);
+ }
+ dyn_kallsyms_refcnt++;
+out:
+ mutex_unlock(&dyn_kallsyms_mutex);
+ return ret;
+}
+EXPORT_SYMBOL_GPL(kallsyms_lookup_batch_start);
+
+void kallsyms_lookup_batch_end(void)
+{
+ u32 *offsets = NULL;
+
+ mutex_lock(&dyn_kallsyms_mutex);
+ if (WARN_ON(!dyn_kallsyms_refcnt))
+ goto out;
+
+ if (--dyn_kallsyms_refcnt == 0)
+ offsets = rcu_replace_pointer(dyn_kallsyms_offsets, NULL,
+ lockdep_is_held(&dyn_kallsyms_mutex));
+out:
+ mutex_unlock(&dyn_kallsyms_mutex);
+
+ if (offsets) {
+ synchronize_rcu();
+ kvfree(offsets);
+ }
+}
+EXPORT_SYMBOL_GPL(kallsyms_lookup_batch_end);
+
+/*
+ * Find the offset on the compressed table given an index in the
+ * kallsyms array.
+ */
+static inline unsigned int get_symbol_offset(unsigned long pos)
+{
+ unsigned int off;
+ u32 *offsets;
+
+ rcu_read_lock();
+ offsets = rcu_dereference(dyn_kallsyms_offsets);
+ if (offsets) {
+ off = offsets[pos];
+ rcu_read_unlock();
+ return off;
+ }
+ rcu_read_unlock();
+
+ return get_symbol_offset_marker(pos);
+}
+
unsigned long kallsyms_sym_address(int idx)
{
/* non-relocatable 32-bit kernels just embed the value directly */
@@ -206,6 +301,7 @@ static int kallsyms_lookup_names(const char *name,
low = 0;
high = kallsyms_num_syms - 1;
+ rcu_read_lock();
while (low <= high) {
mid = low + (high - low) / 2;
seq = get_symbol_seq(mid);
@@ -219,8 +315,10 @@ static int kallsyms_lookup_names(const char *name,
break;
}
- if (low > high)
+ if (low > high) {
+ rcu_read_unlock();
return -ESRCH;
+ }
low = mid;
while (low) {
@@ -243,6 +341,7 @@ static int kallsyms_lookup_names(const char *name,
}
*end = high;
}
+ rcu_read_unlock();
return 0;
}
diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c
index 8f6c4e9b3a1c..aedffc058c0e 100644
--- a/kernel/kallsyms_selftest.c
+++ b/kernel/kallsyms_selftest.c
@@ -178,6 +178,7 @@ static int lookup_name(void *data, const char *name, unsigned long addr)
static void test_perf_kallsyms_lookup_name(void)
{
struct test_stat stat;
+ int ret;
memset(&stat, 0, sizeof(stat));
stat.min = INT_MAX;
@@ -185,6 +186,21 @@ static void test_perf_kallsyms_lookup_name(void)
pr_info("kallsyms_lookup_name() looked up %d symbols\n", stat.real_cnt);
pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n",
stat.min, stat.max, div_u64(stat.sum, stat.real_cnt));
+
+ ret = kallsyms_lookup_batch_start();
+ if (ret) {
+ pr_err("kallsyms_lookup_batch_start() failed: %d\n", ret);
+ return;
+ }
+
+ memset(&stat, 0, sizeof(stat));
+ stat.min = INT_MAX;
+ kallsyms_on_each_symbol(lookup_name, &stat);
+ kallsyms_lookup_batch_end();
+
+ pr_info("kallsyms_lookup_name() (batch) looked up %d symbols\n", stat.real_cnt);
+ pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n",
+ stat.min, stat.max, div_u64(stat.sum, stat.real_cnt));
}
static int find_symbol(void *data, const char *name, unsigned long addr)
diff --git a/lib/test_kallsyms_perf.c b/lib/test_kallsyms_perf.c
index 03ff5f1d51c5..f6c3d5d82e5d 100644
--- a/lib/test_kallsyms_perf.c
+++ b/lib/test_kallsyms_perf.c
@@ -91,7 +91,8 @@ static int count_cb(void *data, const char *name, unsigned long addr)
return 0;
}
-static void run_name_lookup_bench(unsigned int iters)
+static void run_name_lookup_bench(const char *mode, unsigned int iters,
+ u64 *avg_hit_ns, u64 *avg_miss_ns)
{
u64 t0, t1, dt_hit = 0, dt_miss = 0;
unsigned long addr = 0;
@@ -153,10 +154,15 @@ static void run_name_lookup_bench(unsigned int iters)
dt_miss += t1 - t0;
}
- pr_info("Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\n",
- div_u64(dt_hit, iters), div_u64(dt_hit, 1000000), iters);
- pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
- div_u64(dt_miss, iters), div_u64(dt_miss, 1000000), iters);
+ if (avg_hit_ns)
+ *avg_hit_ns = div_u64(dt_hit, iters);
+ if (avg_miss_ns)
+ *avg_miss_ns = div_u64(dt_miss, iters);
+
+ pr_info("[%s] Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\n",
+ mode, div_u64(dt_hit, iters), div_u64(dt_hit, 1000000), iters);
+ pr_info("[%s] Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n",
+ mode, div_u64(dt_miss, iters), div_u64(dt_miss, 1000000), iters);
}
static void run_address_lookup_bench(unsigned int iters)
@@ -243,6 +249,9 @@ static void run_table_walk_bench(void)
static int run_kallsyms_benchmark(void)
{
unsigned int iters;
+ u64 unindexed_hit = 0, unindexed_miss = 0;
+ u64 dyn_hit = 0, dyn_miss = 0;
+ u64 t0, t1, dt_start = 0, dt_end = 0;
int ret = 0;
if (!mutex_trylock(&bench_lock)) {
@@ -261,7 +270,37 @@ static int run_kallsyms_benchmark(void)
pr_info("Starting kallsyms performance benchmark (iters=%u)\n", iters);
pr_info("==================================================\n");
- run_name_lookup_bench(iters);
+ /* 1. Benchmark baseline unindexed marker scan */
+ run_name_lookup_bench("Unindexed (markers)", iters, &unindexed_hit, &unindexed_miss);
+
+ /* 2. Benchmark dynamic lookup index */
+ t0 = ktime_get_ns();
+ ret = kallsyms_lookup_batch_start();
+ t1 = ktime_get_ns();
+ dt_start = t1 - t0;
+
+ if (ret) {
+ pr_err("Failed to start kallsyms lookup batch: %d\n", ret);
+ } else {
+ run_name_lookup_bench("Dynamic Index", iters, &dyn_hit, &dyn_miss);
+
+ t0 = ktime_get_ns();
+ kallsyms_lookup_batch_end();
+ t1 = ktime_get_ns();
+ dt_end = t1 - t0;
+
+ pr_info("[Dynamic Index] Batch setup: %llu us, teardown: %llu us\n",
+ div_u64(dt_start, 1000), div_u64(dt_end, 1000));
+
+ if (unindexed_hit > dyn_hit) {
+ u64 saved = unindexed_hit - dyn_hit;
+
+ pr_info("[Dynamic Index] Amortization break-even: %llu queries (setup), %llu queries (total)\n",
+ DIV_ROUND_UP_ULL(dt_start, saved),
+ DIV_ROUND_UP_ULL(dt_start + dt_end, saved));
+ }
+ }
+
run_address_lookup_bench(iters);
run_table_walk_bench();
--
2.55.0
^ permalink raw reply [flat|nested] 7+ messages in thread* [PATCH v4 4/4] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq()
2026-09-22 20:08 [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Jim Cromie
` (2 preceding siblings ...)
2026-09-22 20:08 ` [PATCH v4 3/4] kallsyms: Add dynamic lookup index for batch resolution Jim Cromie
@ 2026-09-22 20:08 ` Jim Cromie
2026-09-23 7:12 ` [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Kees Cook
4 siblings, 0 replies; 7+ messages in thread
From: Jim Cromie @ 2026-09-22 20:08 UTC (permalink / raw)
To: Andrew Morton
Cc: Lorenzo Stoakes, Kees Cook, David Laight, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf, Jim Cromie
kallsyms_seqs_of_names[] stores 3-byte big-endian sequence indices that
map alphabetical symbol positions to address-ordered symbol records.
Currently, get_symbol_seq() reconstructs each 24-bit integer using a
3-iteration for-loop that shifts and bitwise-ORs each byte sequentially.
During binary search in kallsyms_lookup_names() and duplicate boundary
scans, this loop introduces branch and loop overhead on the hot lookup
path.
Mark get_symbol_seq() as static inline and unroll the 3-byte extraction
into direct byte shifts: (p[0] << 16) | (p[1] << 8) | p[2]. This
eliminates loop induction variable maintenance and allows the compiler
to generate direct loads and constant shifts.
Signed-off-by: Jim Cromie <jim.cromie@gmail.com>
---
Changes in v3:
- Added as a standalone micro-optimization patch (addresses David
Laight review).
---
kernel/kallsyms.c | 9 +++------
1 file changed, 3 insertions(+), 6 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index bb34b4c0f690..35484361201f 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -280,14 +280,11 @@ unsigned long kallsyms_sym_address(int idx)
return (unsigned long)offset_to_ptr(kallsyms_offsets + idx);
}
-static unsigned int get_symbol_seq(int index)
+static inline unsigned int get_symbol_seq(int index)
{
- unsigned int i, seq = 0;
+ const u8 *p = &kallsyms_seqs_of_names[3 * index];
- for (i = 0; i < 3; i++)
- seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i];
-
- return seq;
+ return (p[0] << 16) | (p[1] << 8) | p[2];
}
static int kallsyms_lookup_names(const char *name,
--
2.55.0
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x
2026-09-22 20:08 [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Jim Cromie
` (3 preceding siblings ...)
2026-09-22 20:08 ` [PATCH v4 4/4] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() Jim Cromie
@ 2026-09-23 7:12 ` Kees Cook
2026-09-23 10:00 ` David Laight
4 siblings, 1 reply; 7+ messages in thread
From: Kees Cook @ 2026-09-23 7:12 UTC (permalink / raw)
To: Jim Cromie
Cc: Andrew Morton, Lorenzo Stoakes, David Laight, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf
On Tue, Sep 22, 2026 at 02:08:17PM -0600, Jim Cromie wrote:
> 2. Patch 3 introduces a dynamic u32 lookup index bracketed by
> kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end().
> It allocates ~736 KiB in transient RAM via kvmalloc_array() only
> while bulk workloads (BPF attach, module loading) run, resolves
> each probe in O(1) with 0 hops, and leaves .rodata bloat at exactly
> 0 bytes while retaining kallsyms_markers[] as fallback. Both
> test_kallsyms_perf and kallsyms_selftest are updated to benchmark
> batch resolution side-by-side.
> [...]
> - Dropped .rodata image footprint addition from +573 KiB to 0 KiB,
> addressing Kees Cook's memory footprint objection.
Ah, very cool; thanks for giving the dynamic route a try! (Also, please
wait a few days between versions and give humans some time to reply.)
I spent some time trying to understand all the timings here, and with
a problem statement of "tens of thousands of functions", I'd want
to understand how common that workload is. Even module loading isn't
anywhere near that high, and AIUI, most kprobe loads of that size are
roughly one-offs, and what Jiri measured was the most extreme possible
attach we could see, and that is a synthetic workload. (And kallsyms
was ~7% of the attach.) I struggle to see a problem that needs solving.
What we have today is a 1:256 mapping, so the walk penalty in ~128 steps
per symbol lookup. With your proposed 1:1 there's no walk penalty, but
we either pay a lifetime .rodata cost or a startup/teardown cost and
temporary dynamic allocation cost.
Right now the startup time for the dynamic table appears to need ~1500
symbol look-ups to break even compared to today's 1:256 mapping.
How would a 1:8 table in .rodata compare, for example? It's not 1:1 but
it should get you something like 95% of the speed (84ns) for a 8x less
.rodata memory compared to the 1:1 in .rodata. And the table might be
small enough that cache locality helps more?
Anyway, I'd be curious to see the benchmarks at alternative densities as
there is a clear space vs time trade-off here, and moving into dynamic
allocation changes the measurements again.
But dominating all of this is the question of how common it is to do
tens of thousands of symbol lookups with a fast path need. As a 1-time
cost or even every few hours, it's hard to justify either size (1:1 in
.rodata for all Linux systems) or complexity (RCU-locked 1:1 allocation
built on the fly).
-Kees
--
Kees Cook
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x
2026-09-23 7:12 ` [PATCH v4 0/4] kallsyms: Accelerate symbol name lookups by ~19x Kees Cook
@ 2026-09-23 10:00 ` David Laight
0 siblings, 0 replies; 7+ messages in thread
From: David Laight @ 2026-09-23 10:00 UTC (permalink / raw)
To: Kees Cook
Cc: Jim Cromie, Andrew Morton, Lorenzo Stoakes, Masahiro Yamada,
linux-kernel, linux-kbuild, bpf
On Wed, 23 Sep 2026 00:12:29 -0700
Kees Cook <kees@kernel.org> wrote:
I think you are at ~15x now.
> On Tue, Sep 22, 2026 at 02:08:17PM -0600, Jim Cromie wrote:
> > 2. Patch 3 introduces a dynamic u32 lookup index bracketed by
> > kallsyms_lookup_batch_start() and kallsyms_lookup_batch_end().
> > It allocates ~736 KiB in transient RAM via kvmalloc_array() only
> > while bulk workloads (BPF attach, module loading) run, resolves
> > each probe in O(1) with 0 hops, and leaves .rodata bloat at exactly
> > 0 bytes while retaining kallsyms_markers[] as fallback. Both
> > test_kallsyms_perf and kallsyms_selftest are updated to benchmark
> > batch resolution side-by-side.
> > [...]
> > - Dropped .rodata image footprint addition from +573 KiB to 0 KiB,
> > addressing Kees Cook's memory footprint objection.
>
> Ah, very cool; thanks for giving the dynamic route a try! (Also, please
> wait a few days between versions and give humans some time to reply.)
>
> I spent some time trying to understand all the timings here, and with
> a problem statement of "tens of thousands of functions", I'd want
> to understand how common that workload is. Even module loading isn't
> anywhere near that high, and AIUI, most kprobe loads of that size are
> roughly one-offs, and what Jiri measured was the most extreme possible
> attach we could see, and that is a synthetic workload. (And kallsyms
> was ~7% of the attach.) I struggle to see a problem that needs solving.
>
> What we have today is a 1:256 mapping, so the walk penalty in ~128 steps
> per symbol lookup.
According the the commit message(s) the existing code does a full binary
chop so gets the ~128 step walk penalty for every stage.
If the new index were rounded down to a multiple of 256 (the algorithm
works with any index between the existing high and low ones) then the
walk penalty would only be needed to find the last item in the 256 entry
block.
I can think of a variety of schemes for scanning the last 256 entries.
A simple (optimised) linear scan may not be too bad.
Or save some offsets in a small on-stack u16[] array as you scan for
an item to compare against - allowing a binary chop through the scanned
items (may need a final linear scan).
David
> With your proposed 1:1 there's no walk penalty, but
> we either pay a lifetime .rodata cost or a startup/teardown cost and
> temporary dynamic allocation cost.
>
> Right now the startup time for the dynamic table appears to need ~1500
> symbol look-ups to break even compared to today's 1:256 mapping.
>
> How would a 1:8 table in .rodata compare, for example? It's not 1:1 but
> it should get you something like 95% of the speed (84ns) for a 8x less
> .rodata memory compared to the 1:1 in .rodata. And the table might be
> small enough that cache locality helps more?
>
> Anyway, I'd be curious to see the benchmarks at alternative densities as
> there is a clear space vs time trade-off here, and moving into dynamic
> allocation changes the measurements again.
>
> But dominating all of this is the question of how common it is to do
> tens of thousands of symbol lookups with a fast path need. As a 1-time
> cost or even every few hours, it's hard to justify either size (1:1 in
> .rodata for all Linux systems) or complexity (RCU-locked 1:1 allocation
> built on the fly).
Also how may lookups do you need in a batch to break even?
David
>
> -Kees
>
^ permalink raw reply [flat|nested] 7+ messages in thread