From nobody Thu Sep 24 16:56:47 2026 Received: from mail-oi2-f12.google.com (mail-oi2-f12.google.com [74.125.231.204]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EDDED3F9287 for ; Tue, 22 Sep 2026 07:19:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.204 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061572; cv=none; b=lGRXV3BfHf/0r3hp5Ak6xHuz+Xec4HN1/0H3Nv/dmak22S4PJwGZYFeK/6R7CooYn2qFLv2o1j/9tnJN99QtAmitJeP0iP8+gNNhuLM27h34Wic86rwOO52GdUUrIG9oxh+3YCD5G/Ww1YLEzBtar5JJPOYYo5oDJhVWGxsHFcQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061572; c=relaxed/simple; bh=nSVguYsya202ycWnyh7LvZPegeG4xaW8+imMMxZ/vE0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=WdgjJzttsl9+85K/G1G1Nzal8SixWR+91+PxfBSoKRJ+HlgPsJG0EnfS/S+hvFz0ZrCJtLZJFPZLdRAHjfn5Z+LNwnea2ssaIZJU5O4hjYAaywSr1Q8KFhf1IZV0igHuzMO5KL0XryFLo0oiqDsjaJm9qbAChQvNyDg3tOpknrw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=dgBTw7oO; arc=none smtp.client-ip=74.125.231.204 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dgBTw7oO" Received: by mail-oi2-f12.google.com with SMTP id 46e09a7af769-7fcb425fb68so2200624a34.0 for ; Tue, 22 Sep 2026 00:19:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790061566; x=1790666366; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=bmJ/GHOMUIczVGv6/n/Tv9sle3osoP7bDLoj2krszHI=; b=dgBTw7oOZA23iu4wXb7qc/iD57xlTBLOTnDzQWVURula1HwG6p5EQduJNQIXzl7YJc Ave/P23fsz37IQNzCh9t3rX5+5GWoJI+aK/+fatBoEyzEv5qIHvb3A+WtFhNCJjeNC/P +OJjW7gNfc9ZRKiLB/LCtlXPnjD2f/Do32yTCDW/JIzZ6QFJXyjPI1exhc7olfnl9KvB WTEf+OFmT2cMlABlHST/PkgwxvEcee2spbwA42UUoYjUR8o10yRagEvX7j1LreB60t1g APdqo+GYj8oGQaBbLdetZHcl9/0YxmI2UToVFu54S7bAgbJFeVIIJeDyBDgQCM34dG7k YyLQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790061566; x=1790666366; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=bmJ/GHOMUIczVGv6/n/Tv9sle3osoP7bDLoj2krszHI=; b=RT625TRB5NjrnphULyoYTlpBLlDWinacnWpAHNZOeJcRc+OSAsilWPrsj9gKPr+UCs By81UDDlFvO60da5Ze4GUmcOsiyn6+7rHlACf5b+eeBUi9K7l8nyObqhjCxefSyEmR3G EzoVk0swOZc3coWpcwdVo4TslzgYRR63moQXq3yC4DGeD4FT8YSqpMCMHrxdaylLaDfN lVB+HMisBKE1CmjJWpUVRmz61kVjyca8+AKmJDYH/Wk3+jeYNrOWZJbofG6ajnn+jM/z 9d8owMI/NG2Z3Xo7iu3gsHDH2+xjK76pTmXmScquTpPVlGFa9ZQnDCbOssmaEJiyWSYK x7Ng== X-Forwarded-Encrypted: i=1; AKwUvBx14tHRY8PhATSIuwXEtxAe/e+FXC2ioM4ysqh372RE/g0eU/0oBrxexUyqzEqP7vDBt3VqwIVtfxlQ1AI=@vger.kernel.org X-Gm-Message-State: AFuF++lq13zX8FwBDBmx9GTqv5Hlf4UjTIJtatnZWn0hT5NJPFmsrKfG R/ll3jQWoJO7cSDAZ78JPJ2qgXHaHvzEoIjrV2emCxq8W/upHsnGn34A X-Gm-Gg: AYBFou2Zjl9H2biJI7g0Evu7tdlN3lp8drTmeROgYwtaG867vpBaXb93A73SvLbWfqb MIBq/CCKuhZOOQPFzGQoz2KdVKLkzyMITMaNQuO9HFkfX2+4tGUWKQzpnhn4iuc2O2e8gh5ylsC 2oHOpQfLceKdjWXsutky/dPgFHObR6k6K7Cl6Hflgj0Y2xlyDgw08e1GAdLkhBPlN6bIaTh9T4+ Zv91caWj/czUXNrllmazpNaUyGVHMPx1jdTAy2pRPUmXhym5AFxbYW5H46RWfFNX4nPECPImD8P Dklpzqt52qNCr6USRTQgTKlZ4z2pii30xiPZzSQDdxpJH20/LeOayFiDc7EWVocL+F67H8ZmhDS +NfC4Yok7Fc5atd2EdVut1E4RMsn19+FOrEOP5PQZmMnN3F2ExfaM0Fued8N6XPfFsmQx/UX58m QvuGnJ7/XruEas6bZR+QGkyhUs8wB3TziMOJTC23G1X4M0fwqe6t3aP8AHGm+++zK6s24vvPbch +RmmoTYDF1KC6XccOuVoyXprCcrgGAWOMyXGpYvQLsMoT/FurzMrstNPXipFgIIc7SpKglDFzOn bD+pMHpFQl7XfKvwqro= X-Received: by 2002:a05:6830:640c:b0:806:14ab:a7b0 with SMTP id 46e09a7af769-80de34e4a1dmr15923768a34.30.1790061566127; Tue, 22 Sep 2026 00:19:26 -0700 (PDT) Received: from [100.82.231.29] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 46e09a7af769-814e598483esm1116801a34.5.2026.09.22.00.19.24 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 00:19:24 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 01:19:19 -0600 Subject: [PATCH v2 1/3] kallsyms: Add test_kallsyms_perf module to benchmark lookup latency 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: <20260922-ksyms-tune-v2-1-a333ee31eac7@gmail.com> References: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> In-Reply-To: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , David Laight , Masahiro Yamada , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, bpf@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1790061561; l=9420; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=nSVguYsya202ycWnyh7LvZPegeG4xaW8+imMMxZ/vE0=; b=M40Tnq70kMCwXYdnlB38866DboPA2ZN1I1tZZ7qIKK8ql+u+rH/AbB7QCS0H1W+kD8zV6zlPb TS5W3545ZXRAQ91WdTj+rDYBi6+CJ2Rv8uUUNPYcqWeLSnNnFFr6HWx X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= To evaluate optimizations and measure performance regressions across kallsyms lookups, add a lightweight microbenchmark module in lib/. 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 --- kernel/kallsyms.c | 2 + lib/Kconfig.debug | 10 +++ lib/Makefile | 1 + lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++= ++++ 4 files changed, 241 insertions(+) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index aec2f06858af..b9e573e9a10b 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -261,6 +261,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const cha= r *, unsigned long), } return 0; } +EXPORT_SYMBOL_GPL(kallsyms_on_each_symbol); =20 int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), const char *name, void *data) @@ -279,6 +280,7 @@ int kallsyms_on_each_match_symbol(int (*fn)(void *, uns= igned long), =20 return ret; } +EXPORT_SYMBOL_GPL(kallsyms_on_each_match_symbol); =20 static unsigned long get_symbol_pos(unsigned long addr, unsigned long *symbolsize, diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 134b15a44625..2a8b1aaee23b 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -3122,6 +3122,16 @@ config TEST_STATIC_KEYS =20 If unsure, say N. =20 +config TEST_KALLSYMS_PERF + tristate "kallsyms performance benchmark test module" + default m + help + This builds the test_kallsyms_perf module 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) +=3D test_rhashtable.o obj-$(CONFIG_TEST_STATIC_KEYS) +=3D test_static_keys.o obj-$(CONFIG_TEST_STATIC_KEYS) +=3D test_static_key_base.o obj-$(CONFIG_TEST_DYNAMIC_DEBUG) +=3D test_dynamic_debug.o +obj-$(CONFIG_TEST_KALLSYMS_PERF) +=3D test_kallsyms_perf.o =20 obj-$(CONFIG_TEST_BITMAP) +=3D 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..c649e55dae3b --- /dev/null +++ b/lib/test_kallsyms_perf.c @@ -0,0 +1,228 @@ +// 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 +#include +#include +#include +#include +#include + +static unsigned int num_iters =3D 100000; +module_param(num_iters, uint, 0644); +MODULE_PARM_DESC(num_iters, "Number of iterations per microbenchmark"); + +static const char * const hit_symbols[] =3D { + "_printk", + "schedule", + "vfs_read", + "do_sys_openat2", + "kernel_clone", + "tcp_v4_rcv", + "kallsyms_lookup_names", + "vm_area_alloc", +}; + +static const char * const miss_symbols[] =3D { + "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 =3D data; + + *out =3D addr; + return 1; +} + +static int count_cb(void *data, const char *name, unsigned long addr) +{ + unsigned long *cnt =3D data; + + (*cnt)++; + return 0; +} + +static void run_name_lookup_bench(void) +{ + u64 t0, t1, dt_hit, dt_miss; + unsigned long addr =3D 0; + unsigned int i, nr_hits, nr_misses; + + nr_hits =3D ARRAY_SIZE(hit_symbols); + nr_misses =3D ARRAY_SIZE(miss_symbols); + + /* 0. Correctness validation */ + for (i =3D 0; i < nr_hits; i++) { + const char *sym =3D hit_symbols[i]; + unsigned long a1 =3D 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 =3D 0; i < nr_misses; i++) { + const char *sym =3D miss_symbols[i]; + unsigned long a1 =3D 0; + + kallsyms_on_each_match_symbol(match_cb, sym, &a1); + if (a1) + pr_err("CORRECTNESS FAILURE: miss sym '%s' unexpectedly found a1=3D%lx\= n", + sym, a1); + } + + /* 1. Name search: Existing symbols (Hits) */ + t0 =3D ktime_get_ns(); + for (i =3D 0; i < num_iters; i++) { + const char *sym =3D hit_symbols[i % nr_hits]; + + kallsyms_on_each_match_symbol(match_cb, sym, &addr); + OPTIMIZER_HIDE_VAR(addr); + } + t1 =3D ktime_get_ns(); + dt_hit =3D t1 - t0; + + /* 2. Name search: Non-existent symbols (Misses - 17 bsearch probes) */ + t0 =3D ktime_get_ns(); + for (i =3D 0; i < num_iters; i++) { + const char *sym =3D miss_symbols[i % nr_misses]; + + kallsyms_on_each_match_symbol(match_cb, sym, &addr); + OPTIMIZER_HIDE_VAR(addr); + } + t1 =3D ktime_get_ns(); + dt_miss =3D t1 - t0; + + pr_info("Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\n", + dt_hit / num_iters, dt_hit / 1000000, num_iters); + pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n", + dt_miss / num_iters, dt_miss / 1000000, num_iters); +} + +static void run_address_lookup_bench(void) +{ + u64 t0, t1, dt_sprint, dt_bldid; + char symname[KSYM_SYMBOL_LEN]; + unsigned long addrs[ARRAY_SIZE(hit_symbols)]; + unsigned int i, nr_addrs =3D 0; + + for (i =3D 0; i < ARRAY_SIZE(hit_symbols); i++) { + unsigned long addr =3D 0; + + kallsyms_on_each_match_symbol(match_cb, hit_symbols[i], &addr); + if (addr) + addrs[nr_addrs++] =3D addr; + } + + if (!nr_addrs) { + pr_warn("Address benchmark skipped: no test addresses resolved\n"); + return; + } + + /* 1. Address-to-name resolution (sprint_symbol) */ + t0 =3D ktime_get_ns(); + for (i =3D 0; i < num_iters; i++) { + unsigned long addr =3D addrs[i % nr_addrs]; + + sprint_symbol(symname, addr); + barrier_data(symname); + } + t1 =3D ktime_get_ns(); + dt_sprint =3D t1 - t0; + + /* 2. Address without offset (sprint_symbol_no_offset) */ + t0 =3D ktime_get_ns(); + for (i =3D 0; i < num_iters; i++) { + unsigned long addr =3D addrs[i % nr_addrs]; + + sprint_symbol_no_offset(symname, addr); + barrier_data(symname); + } + t1 =3D ktime_get_ns(); + dt_bldid =3D t1 - t0; + + pr_info("sprint_symbol: %llu ns/lookup (%llu ms total, %u iters= )\n", + dt_sprint / num_iters, dt_sprint / 1000000, num_iters); + pr_info("sprint_symbol_no_offset: %llu ns/lookup (%llu ms total, %u iters= )\n", + dt_bldid / num_iters, dt_bldid / 1000000, num_iters); +} + +static void run_table_walk_bench(void) +{ + u64 t0, t1, dt_walk; + unsigned long total_symbols =3D 0; + int iter =3D 50; + int i; + + t0 =3D ktime_get_ns(); + for (i =3D 0; i < iter; i++) { + total_symbols =3D 0; + kallsyms_on_each_symbol(count_cb, &total_symbols); + } + t1 =3D ktime_get_ns(); + dt_walk =3D t1 - t0; + + pr_info("Table Full Walk: %llu us/pass (%lu symbols scanned, %d passes)\= n", + (dt_walk / iter) / 1000, total_symbols, iter); +} + +static int run_kallsyms_benchmark(void) +{ + pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); + pr_info("Starting kallsyms performance benchmark (iters=3D%u)\n", num_ite= rs); + pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); + + run_name_lookup_bench(); + run_address_lookup_bench(); + run_table_walk_bench(); + + pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); + pr_info("kallsyms benchmark complete\n"); + pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); + + return 0; +} + +static int param_set_trigger(const char *val, const struct kernel_param *k= p) +{ + return run_kallsyms_benchmark(); +} + +static const struct kernel_param_ops param_ops_trigger =3D { + .set =3D 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) +{ + return run_kallsyms_benchmark(); +} + +static void __exit test_kallsyms_exit(void) +{ + pr_info("test_kallsyms module unloaded\n"); +} + +module_init(test_kallsyms_init); +module_exit(test_kallsyms_exit); + +MODULE_DESCRIPTION("Microbenchmark test module for kallsyms subsystem"); +MODULE_AUTHOR("Jim Cromie "); +MODULE_LICENSE("GPL"); --=20 2.55.0 From nobody Thu Sep 24 16:56:47 2026 Received: from mail-oi2-f13.google.com (mail-oi2-f13.google.com [74.125.231.205]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5D7B938910F for ; Tue, 22 Sep 2026 07:19:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.205 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061579; cv=none; b=EH1RounD2rVmmtGjMum5R5z5ZCda65G6W43Cieb+ZS0BtlFcaAOlt5YOpFzvVZr69U/PSF48V/KII0YZvzmYlFG/iPKUYhE0QRB851JxgTJT8WzIUYzbPPez2lRFhJmU2lGdsumyaJZten0qFCAoo1RcL8vNLpfKWjEsOXBNgFg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061579; c=relaxed/simple; bh=VXF7SFbi3SiEc8w+AaV9LOPsYv26WbWeBrNzDMs66V0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=SiQSxahDc3lzNKa84+TwucaHbP5LMxw3JHjaF4GplAxX6k6xsr+cfLt3H4O8lXqHsECUEBW5JzekkhV8YOx73eoaHujVua6zp4MZedZVdjul9uGHZCCIFRBV8ZNB4pYV6iB2bCpe8mkXHkUWAuw1VrCK4WtSeo1V2oWPIQUKsac= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Rvsvsc8r; arc=none smtp.client-ip=74.125.231.205 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Rvsvsc8r" Received: by mail-oi2-f13.google.com with SMTP id 46e09a7af769-80a71781323so1715819a34.1 for ; Tue, 22 Sep 2026 00:19:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790061568; x=1790666368; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=gq4+tOf8JUQD9uEs0/FCCs0grSUtXcKgbtbsmVE9gz0=; b=Rvsvsc8rO8CPfB4au//cdaJaOTfQ8dtdLci6KdaD9HAJ1isZk/8PJHdX/60yup9mhh h5a/iRKFEbzE+KDkavQGZo9V2ZkQyc/QawdDRKX27kV/aUG3MtX4Kz+g0k/8m4SUzFK3 RN9ZZRBxxAZ4aFmq83GXTwNlgeZTYXTsOgDgtEKLNKJFqdEe6biFF8gBV5JR/3ozH12B dU4/+MMUh7xqa7cMdNPfDL2MzFoumdIXOydSGvw617fVS2qC3SHMQ6XA1vsWbf7+dZem laFpkm0M0feUZGqEpaAQMXEyvcyjpmhvdX2ri/7rPWC2q/U+v4bVVHWeRV1nUlILkNBm 3uWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790061568; x=1790666368; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=gq4+tOf8JUQD9uEs0/FCCs0grSUtXcKgbtbsmVE9gz0=; b=dPjWz5nwLTYXqggpB1YhpXP5a9N0Uv+PFdxKljs7boic6vdORbzL3IUW/aWjcrVSvw Oz59FYkdw7cPTtP7rX5ZXTjCoQpfDoSOkq3EQX29+nAZjfIf8FVN38ms+BXFpLyutO8f nNQnngm4uSsIdn49TzTYycqqnps1BiAWeAe5CMlowKHWUh9kKn5RV6l27LDxo8+I/GEw AxNTlURbDV0NDsDxuoe6s16w7w+wXrckscY6ZW7JeCuZoSA1udEJZCDYT2WQgIDx24cd sVAD5qQfanwsD843sfca2WBgnAJpn9/IdlD4aPxsA8pj/yE0iJkZZ027srYq1h2oKT1q Azhg== X-Forwarded-Encrypted: i=1; AKwUvBw0csM4dgg93vwOGolvl+YKBlDHDy+qBY0u6FUdhoVp0g9/0G4SyQm+/a7ZUSBqw15DXURduwSQ6Vgg87U=@vger.kernel.org X-Gm-Message-State: AFuF++n+ys4HnU/jiiyZJnLf20iP08XweRrj+wYUar6I/9qh1DrU9Fow 9gxT1q4CiGpm3bEBAXm5/dWDaq2vZJuZMZdeDC17L+/K3/0/Ws0MjkW7 X-Gm-Gg: AYBFou1LzSMfOY/AbWPizoDZ0/gc8ovV33R6hVsYnGia1V+7BPpXv04J2YbRqlnqql5 VrJbd5TrXo0pU1nj2Pfps/jaNlOqTmyl7ueBLVZJKTyYE98NU0YoqCE/NAMVf975075eaaIfXdQ dwzXIniXIid+x8XrTfQPjXIzoBRjfUZq2Mk22FiJxdVJEPihYAnrl1pEaZH6t1vV6pddyOs3Q1t unWky6YlmkeKyZBGGIgURTttGIzhIbmu+BdJcfwx1ckt+cvi4FDcA/oVY20ekXMei+WbJVWjVcM 4sfqlQFnjvp65Foj5d/lD7tiZs8jnBl1usOjxNXhDOilTMwTW2Kg7vdhHY8CM/5JEXpPyLGux2u jnwZm6XwPpIy/T+p5nOSC+/+rkVn+Gfmtrs/YQkcGKps9fUgfMWfVvI1VXE0BMPYWz9KasxWPrw Vb+oHwbm1Nf+6w+/MTb4OiuLVxkCboF+xVPEJrjL+ES5atDGom+58q+mW4xZ97wzry9TLfRt54w 2PVmmjbmxKmBHOEzTS76+mI1DxKc25NiJOUI1/722l5zvo8P2OhXGqg67KY3AiPOqgm7lFKgHxT 4KrpPyf/yOweH6xkejM= X-Received: by 2002:a05:6830:412a:b0:801:6bec:ff18 with SMTP id 46e09a7af769-80ddfd6c36fmr13455911a34.2.1790061567693; Tue, 22 Sep 2026 00:19:27 -0700 (PDT) Received: from [100.82.231.29] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 46e09a7af769-814e598483esm1116801a34.5.2026.09.22.00.19.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 00:19:26 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 01:19:20 -0600 Subject: [PATCH v2 2/3] kallsyms: Add dynamic lookup index for batch resolution 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: <20260922-ksyms-tune-v2-2-a333ee31eac7@gmail.com> References: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> In-Reply-To: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , David Laight , Masahiro Yamada , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, bpf@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1790061561; l=10695; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=VXF7SFbi3SiEc8w+AaV9LOPsYv26WbWeBrNzDMs66V0=; b=nSSlD4vheC++KE48rvYgEv2c7psFBLMZmwygyCBjYwFTuSMDlhIMJ/YxA/L/5oSXJukaB7N0+ vwl98g/UJVUDFi02h7cMvhWvDW0sIPPliyBPmjGeZFLv8QrFkEgSy01 X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= 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 (~4.5 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. 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 against concurrent batch teardown. 4. Unroll the 3-byte shift loop in get_symbol_seq() into straight-line shifts. 5. Update test_kallsyms_perf to benchmark unindexed marker scans and the dynamic batch index side by side, reporting batch setup and teardown latency alongside query amortization break-even points. Cc: David Laight Signed-off-by: Jim Cromie --- include/linux/kallsyms.h | 13 ++++++ kernel/kallsyms.c | 111 ++++++++++++++++++++++++++++++++++++++++++-= ---- lib/test_kallsyms_perf.c | 53 +++++++++++++++++++--- 3 files changed, 161 insertions(+), 16 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); =20 +/* 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); =20 @@ -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*/ =20 static inline void print_ip_sym(const char *loglvl, unsigned long ip) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index b9e573e9a10b..862a6b773ac5 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -22,6 +22,9 @@ #include /* for cond_resched */ #include #include +#include +#include +#include #include #include #include @@ -113,10 +116,10 @@ static char kallsyms_get_symbol_type(unsigned int off) =20 =20 /* - * 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; @@ -149,6 +152,93 @@ static unsigned int get_symbol_offset(unsigned long po= s) return name - kallsyms_names; } =20 +/* + * Dynamic symbol offset table. + * Allocated on demand during high-volume lookup batches and reclaimed aft= er. + */ +static u32 *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 =3D kallsyms_names; + u32 *offsets; + unsigned int i; + + offsets =3D kvmalloc_array(kallsyms_num_syms, sizeof(u32), GFP_KERNEL); + if (!offsets) + return NULL; + + for (i =3D 0; i < kallsyms_num_syms; i++) { + unsigned int len; + const u8 *data; + + offsets[i] =3D name - kallsyms_names; + data =3D get_symbol_data(offsets[i], &len); + name =3D data + len; + } + + return offsets; +} + +int kallsyms_lookup_batch_start(void) +{ + int ret =3D 0; + + mutex_lock(&dyn_kallsyms_mutex); + if (!dyn_kallsyms_refcnt) { + u32 *offsets =3D kallsyms_build_offsets(); + + if (!offsets) { + ret =3D -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 =3D NULL; + + mutex_lock(&dyn_kallsyms_mutex); + if (WARN_ON(!dyn_kallsyms_refcnt)) + goto out; + + if (--dyn_kallsyms_refcnt =3D=3D 0) { + offsets =3D dyn_kallsyms_offsets; + rcu_assign_pointer(dyn_kallsyms_offsets, NULL); + } +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) +{ + u32 *offsets =3D rcu_dereference_raw(dyn_kallsyms_offsets); + + if (offsets) + return offsets[pos]; + + return get_symbol_offset_marker(pos); +} + unsigned long kallsyms_sym_address(int idx) { /* non-relocatable 32-bit kernels just embed the value directly */ @@ -157,14 +247,11 @@ unsigned long kallsyms_sym_address(int idx) return (unsigned long)offset_to_ptr(kallsyms_offsets + idx); } =20 -static unsigned int get_symbol_seq(int index) +static inline unsigned int get_symbol_seq(int index) { - unsigned int i, seq =3D 0; + const u8 *p =3D &kallsyms_seqs_of_names[3 * index]; =20 - for (i =3D 0; i < 3; i++) - seq =3D (seq << 8) | kallsyms_seqs_of_names[3 * index + i]; - - return seq; + return (p[0] << 16) | (p[1] << 8) | p[2]; } =20 static int kallsyms_lookup_names(const char *name, @@ -179,6 +266,7 @@ static int kallsyms_lookup_names(const char *name, low =3D 0; high =3D kallsyms_num_syms - 1; =20 + rcu_read_lock(); while (low <=3D high) { mid =3D low + (high - low) / 2; seq =3D get_symbol_seq(mid); @@ -193,8 +281,10 @@ static int kallsyms_lookup_names(const char *name, break; } =20 - if (low > high) + if (low > high) { + rcu_read_unlock(); return -ESRCH; + } =20 low =3D mid; while (low) { @@ -219,6 +309,7 @@ static int kallsyms_lookup_names(const char *name, } *end =3D high; } + rcu_read_unlock(); =20 return 0; } diff --git a/lib/test_kallsyms_perf.c b/lib/test_kallsyms_perf.c index c649e55dae3b..df7ee96bdafa 100644 --- a/lib/test_kallsyms_perf.c +++ b/lib/test_kallsyms_perf.c @@ -16,6 +16,7 @@ #include #include #include +#include =20 static unsigned int num_iters =3D 100000; module_param(num_iters, uint, 0644); @@ -59,7 +60,7 @@ static int count_cb(void *data, const char *name, unsigne= d long addr) return 0; } =20 -static void run_name_lookup_bench(void) +static void run_name_lookup_bench(const char *mode, u64 *avg_hit_ns, u64 *= avg_miss_ns) { u64 t0, t1, dt_hit, dt_miss; unsigned long addr =3D 0; @@ -109,10 +110,15 @@ static void run_name_lookup_bench(void) t1 =3D ktime_get_ns(); dt_miss =3D t1 - t0; =20 - pr_info("Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\n", - dt_hit / num_iters, dt_hit / 1000000, num_iters); - pr_info("Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\n", - dt_miss / num_iters, dt_miss / 1000000, num_iters); + if (avg_hit_ns) + *avg_hit_ns =3D div_u64(dt_hit, num_iters); + if (avg_miss_ns) + *avg_miss_ns =3D div_u64(dt_miss, num_iters); + + pr_info("[%s] Name Search Hit: %llu ns/lookup (%llu ms total, %u iters)\= n", + mode, div_u64(dt_hit, num_iters), div_u64(dt_hit, 1000000), num_iters); + pr_info("[%s] Name Search Miss: %llu ns/lookup (%llu ms total, %u iters)\= n", + mode, div_u64(dt_miss, num_iters), div_u64(dt_miss, 1000000), num_iters); } =20 static void run_address_lookup_bench(void) @@ -184,11 +190,46 @@ static void run_table_walk_bench(void) =20 static int run_kallsyms_benchmark(void) { + u64 unindexed_hit =3D 0, unindexed_miss =3D 0; + u64 dyn_hit =3D 0, dyn_miss =3D 0; + u64 t0, t1, dt_start =3D 0, dt_end =3D 0; + int ret; + pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); pr_info("Starting kallsyms performance benchmark (iters=3D%u)\n", num_ite= rs); pr_info("=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D\n"); =20 - run_name_lookup_bench(); + /* 1. Benchmark baseline unindexed marker scan */ + run_name_lookup_bench("Unindexed (markers)", &unindexed_hit, &unindexed_m= iss); + + /* 2. Benchmark dynamic lookup index */ + t0 =3D ktime_get_ns(); + ret =3D kallsyms_lookup_batch_start(); + t1 =3D ktime_get_ns(); + dt_start =3D t1 - t0; + + if (ret) { + pr_err("Failed to start kallsyms lookup batch: %d\n", ret); + } else { + run_name_lookup_bench("Dynamic Index", &dyn_hit, &dyn_miss); + + t0 =3D ktime_get_ns(); + kallsyms_lookup_batch_end(); + t1 =3D ktime_get_ns(); + dt_end =3D 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 =3D 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(); run_table_walk_bench(); =20 --=20 2.55.0 From nobody Thu Sep 24 16:56:47 2026 Received: from mail-oi2-f43.google.com (mail-oi2-f43.google.com [74.125.231.235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 61ADD511E6E for ; Tue, 22 Sep 2026 07:19:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.235 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061579; cv=none; b=lH8KdfcXDLve8nvQZ/Qfw9zfZCBZAK6ohNiLNDAuv6fCqxFhX4RtdB0tih7xYjnJWr8uWeKQMmg4Rfjw7MdnWOZJSNvnTrUU+jPQORISEtISGH8g/nG0XLUH30WNikGiDFLIYVNIqfm/5fj/HCWza8bg+0toXCFCp8Y/S6Tdw2E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790061579; c=relaxed/simple; bh=9+xXUpbmhRcfphY9oEfLvGM9tZCICquHCMD3yOi8tIk=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=WS2dmW+IztKy11jtSLCGAgiyZEu+tsIM4WEj92+YiD2ogI23GszKcu/3MnRBYXhWu62wqUXGuNL1luPhsn0kehmXOoJKAZwQeuT4NC4yZuyv1URnag2haMovt2LyFNVlpanljmZBlVlEp5MtIXy4evgjqfxsPgRVQwF4mDTXb4Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=BAtIGZnG; arc=none smtp.client-ip=74.125.231.235 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BAtIGZnG" Received: by mail-oi2-f43.google.com with SMTP id 46e09a7af769-7f4f0d1779dso3330110a34.2 for ; Tue, 22 Sep 2026 00:19:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790061569; x=1790666369; darn=vger.kernel.org; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=U9x3FI5E4GbuVg0Jfsu35zQ33gdkfajY2nImRMYOyJE=; b=BAtIGZnGN6Wph4it868B9tZapl14iGOUMvokwOo3HUHwT4wBh/0wqCDN8VV/kI6bPK DzfcvFygSfaz9YbbYH0pOWrIvPh8NfHafL5MezzROsNErXMN9xxYqjqF5POSS4aqWoMd 5NX8vRqcQqBi//89WI/xuhMd72OWGnPT5/mZVGMvvMzoDcCCbBJzEWsA1POyk5Rk85pi YCMreAOmt3wb42nGGI5PXoDeuXhAHfzAKPk7zogVCxYaD35JqyB3nGzSM92ZwY3rskGi Y/RMUH64uQH1ip/sFLfgG/DtyWHXRuVJYWDmIXG5e6iAsg2niKOaqh5cPekv5j/jWrCq cihQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790061569; x=1790666369; h=cc:to:in-reply-to:references:message-id:content-transfer-encoding :content-type:mime-version:subject:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=U9x3FI5E4GbuVg0Jfsu35zQ33gdkfajY2nImRMYOyJE=; b=hghYbeiqNAulu2PDdxCokHpei0x0CRjz1I3y0f32HgYco+atzmFlY5PmEtaiyPLUmw yCID2CjU2qVJxpgWXs/opf8hX/qwxlFp1vHyhp73KTALFl4yanSo1JOLkw36R65QLU80 biUJ1OwgCc7T/1dBAQevFUDXlB4AqyzkEqbd0QlyRXKD457UN6mCKv8qUjioHdK+EVjI L9e7q1dVAkuwbxUU3+lZdYiiG3xb4ProEvDYlW2Nv7JkzJqRW7/r5LrxjWx5Ig8UXzlb MZnfaVSCILZr1UUzohkm1NdrGkLj5Rj5pv+e4jIWkycD3vpbv6F0Cs3khFRSzd+AXkXc xCLg== X-Forwarded-Encrypted: i=1; AKwUvBy0XJkRdpOUIepuk/tlBoqcWVXbIpfhortlauEU+vyeI2t+q0q6JtjSGqF8WHw79h9D3IUW/sS7x42gnGs=@vger.kernel.org X-Gm-Message-State: AFuF++nPafUZAwz+i7oqWTiif+kRWRnvOSpOnLaoB00vckbEtNmfCm3C ev+2/eZtlmeIYEUEz2zBXzvFCa4k5pKJLNdqHhEb54lkSyQtb2v/o+Iv X-Gm-Gg: AYBFou13N2HPKS45IVLtcP/kw/dr4hJolAVjAe7BNR0k2KT6BozIMZd4XMEd5M8d2YR tML8OdF9gckZK/KiXNmtdbAa99pIlzGEr0pZh6629HtYRqif/53QD0aU7UVnok6XFYoF7EkWDim zkrJFzeR3KSZDPiex/Hwc4lr01Ygv5/es6DatqPLKc6piDJa7wjlgjNpGWlCUwLC96OEJhEsk7w 4mbfKCYd7yQCXQUepVcZo9CLEvgu6Hr9mtD5ZaeOgv3pNRdzxTZ50e7Vnj37E5gvzMrSzzAyNqf xkuu03Z028Hw2eVW037iF++MczIcWPiAc4K9f5IbNqW0BLOo3Uxrfbm46Ibf7BDbuiFOYyO0xiY JzJqFZiMcjr1jIx5KCzdNvk1RxsPuGcqrEXqXhqNMcG0SXJSR5kjCfeR2lFzj0j/G6Ivt4UVQJo Vb7FoWDw5C4DF+fRSwmfZlEY78T/r0aHTvIo4+dyO0p65HjCwjuTtiXArmytEG7NJTndNXmRHsi N/R1tQHkF3jjSe9jNGc+lxs8yS5xYYi4E2YlH7/zBa+sP+VKoL6vKTrSKnYPODlQS1Ug1+R68lR 3txKkWKPmWN2cKh63H4= X-Received: by 2002:a05:6830:81ca:b0:80b:6c70:94b9 with SMTP id 46e09a7af769-80de27dc7cfmr15537606a34.19.1790061569165; Tue, 22 Sep 2026 00:19:29 -0700 (PDT) Received: from [100.82.231.29] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 46e09a7af769-814e598483esm1116801a34.5.2026.09.22.00.19.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 00:19:28 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 01:19:21 -0600 Subject: [PATCH v2 3/3] kallsyms: Match compressed tokens on the fly during binary search 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: <20260922-ksyms-tune-v2-3-a333ee31eac7@gmail.com> References: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> In-Reply-To: <20260922-ksyms-tune-v2-0-a333ee31eac7@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , David Laight , Masahiro Yamada , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, bpf@vger.kernel.org, Jim Cromie X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=ed25519-sha256; t=1790061561; l=6187; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=9+xXUpbmhRcfphY9oEfLvGM9tZCICquHCMD3yOi8tIk=; b=zvOk3ZkgBsIKOndl6sO4Rqw248xKhWqXl2uhZas4Z5pbHJ3c+gNrOlSTb0rUNyBL4je9U9P4V sF+gitZnIB5CO1l8uvrKFK/4s0k6FN9UBAVmfs1iON3kx3I1T7uaQ5A X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= 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. Leaves sequential address ordering and kallsyms_expand_symbol() streaming invariants intact for /proc/kallsyms and table walks. Signed-off-by: Jim Cromie --- kernel/kallsyms.c | 97 ++++++++++++++++++++++++++++++++++-----------------= ---- 1 file changed, 61 insertions(+), 36 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 862a6b773ac5..4a04d63e4b7d 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -37,6 +37,21 @@ =20 #include "kallsyms_internal.h" =20 +/* + * Get the compressed symbol length and data pointer. + */ +static inline const u8 *get_symbol_data(unsigned int off, unsigned int *le= n) +{ + const u8 *p =3D &kallsyms_names[off]; + unsigned int l =3D *p++; + + if (unlikely(l & 0x80)) + l =3D (l & 0x7F) | (*p++ << 7); + *len =3D l; + + return p; +} + /* * Expand a compressed symbol data into the resulting uncompressed string, * if uncompressed string is too long (>=3D maxlen), it will be truncated, @@ -45,28 +60,12 @@ static unsigned int kallsyms_expand_symbol(unsigned int off, char *result, size_t maxlen) { - int len, skipped_first =3D 0; + int skipped_first =3D 0; const char *tptr; - const u8 *data; + unsigned int len; + const u8 *data =3D get_symbol_data(off, &len); =20 - /* Get the compressed symbol length from the first symbol byte. */ - data =3D &kallsyms_names[off]; - len =3D *data; - data++; - off++; - - /* If MSB is 1, it is a "big" symbol, so needs an additional byte. */ - if ((len & 0x80) !=3D 0) { - len =3D (len & 0x7F) | (*data << 7); - data++; - off++; - } - - /* - * Update the offset to return the offset for the next symbol on - * the compressed stream. - */ - off +=3D len; + off =3D (data - kallsyms_names) + len; =20 /* * For every byte on the compressed symbol data, copy the table @@ -94,7 +93,7 @@ static unsigned int kallsyms_expand_symbol(unsigned int o= ff, if (maxlen) *result =3D '\0'; =20 - /* Return to offset to the next symbol. */ + /* Return offset to the next symbol. */ return off; } =20 @@ -104,16 +103,46 @@ static unsigned int kallsyms_expand_symbol(unsigned i= nt 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 =3D get_symbol_data(off, &len); + + return kallsyms_token_table[kallsyms_token_index[*data]]; } =20 +/* + * 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 decompressi= ng + * the rest of the symbol name. + */ +static int kallsyms_strcmp_symbol(unsigned int off, const char *name) +{ + int skipped_first =3D 0; + const char *tptr; + unsigned int len; + const u8 *data =3D get_symbol_data(off, &len); + + while (len) { + tptr =3D &kallsyms_token_table[kallsyms_token_index[*data]]; + data++; + len--; + + while (*tptr) { + if (skipped_first) { + int diff =3D (unsigned char)*name - (unsigned char)*tptr; + + if (diff !=3D 0) + return diff; + name++; + } else { + skipped_first =3D 1; + } + tptr++; + } + } + + return (unsigned char)*name - '\0'; +} =20 /* * Find the offset on the compressed stream given an index in the @@ -261,7 +290,6 @@ static int kallsyms_lookup_names(const char *name, int ret; int low, mid, high; unsigned int seq, off; - char namebuf[KSYM_NAME_LEN]; =20 low =3D 0; high =3D kallsyms_num_syms - 1; @@ -271,8 +299,7 @@ static int kallsyms_lookup_names(const char *name, mid =3D low + (high - low) / 2; seq =3D get_symbol_seq(mid); off =3D get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - ret =3D strcmp(name, namebuf); + ret =3D kallsyms_strcmp_symbol(off, name); if (ret > 0) low =3D mid + 1; else if (ret < 0) @@ -290,8 +317,7 @@ static int kallsyms_lookup_names(const char *name, while (low) { seq =3D get_symbol_seq(low - 1); off =3D get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - if (strcmp(name, namebuf)) + if (kallsyms_strcmp_symbol(off, name) !=3D 0) break; low--; } @@ -302,8 +328,7 @@ static int kallsyms_lookup_names(const char *name, while (high < kallsyms_num_syms - 1) { seq =3D get_symbol_seq(high + 1); off =3D get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - if (strcmp(name, namebuf)) + if (kallsyms_strcmp_symbol(off, name) !=3D 0) break; high++; } --=20 2.55.0