From nobody Thu Sep 24 14:26:06 2026 Received: from mail-oa2-f12.google.com (mail-oa2-f12.google.com [74.125.231.76]) (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 ABA9C2F39C2 for ; Tue, 22 Sep 2026 20:08:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.76 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107729; cv=none; b=VfgnSusiXWlTFe7vTLVaMz2QLssPyiME37z3Alr8pb8MElWrgBnzQle5YTaH9ku79LPfQsSF1srtPYuyiTJeCV64AWSV53nmF1fQsEawut1LBOXcgwwKjV0eTqmsACO7ChqevW4MuTgLrEKG0LLAixNo4WigNL9LzEFDGt4wKLk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107729; c=relaxed/simple; bh=oV2R0UvbYfIVB77jCAXauJRFelOAEdJiPFl6JJAX4x8=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=ARe3AtvQ2baqBfHpgFYO/pDf5tuf0JE/vMwjPVbyyD62Cl4PCQngb0yApbnU/qVDMUwK0IF42neLNjvA9/lwHqXNv7Fth9Yf5aA9cm5P7K5pNTZE0itZKmvrPIzkBkblzaTFHlSEABSN98TnG7LKcqrAbHkFH92pigK7iS4oljg= 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=pCRgEqE4; arc=none smtp.client-ip=74.125.231.76 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="pCRgEqE4" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-466ccde2ad9so228310fac.1 for ; Tue, 22 Sep 2026 13:08:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790107707; x=1790712507; 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=LBg7HSnbebtbldS1DMZtF5kZINYwBocaor4sCHxt5Tc=; b=pCRgEqE4khEDpdPRa3ou3l33bl7/a+DblSU+2/H144HfKfaOlc3cPdpzVaXtD8IZfp tVhJ/j+UfkjmLUiCtEC9C6GwKMkEZtxhV39AW583WJQLim/fdgeTWCinUEXgBpOw5FJ/ j0C0QXFIr2djUyp3zr64Fu0dzOESwKhp9Q8Mgml3jnbbVXBER6mYfbz9HJ9kvVvouJOc pUgXTRqTNy9O4uNFlg1hPhvvYTZcuWc1q9s67sldmbC0osoVi7FgDUzVKuqJvGaIrLeW hQC+azg+v3pgmoyvd+1LU0vw86b+rzZUhZyr2tM6liH/w1FxlT1OaEclEbAW2DMyp5Ej ft9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790107707; x=1790712507; 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=LBg7HSnbebtbldS1DMZtF5kZINYwBocaor4sCHxt5Tc=; b=VArAzAYKSrLJ+80UsnJ3qD9h+lqGtRQzgLI87i054NfPZ2+vAH+LvNTG1VJdLlDguW J7foRTcSeZi30aQqIRm2f5lqMWzxWfHn5OZtGEZDW3zPVftxv5HJJqkG1VoJEAvAsHf8 CpQUQN0v1xZ29nOzflK9HqCivLIlJFY4dLgh4eB3PhnQidmVQYhsWwLIofAL8/qd3++4 Kng5m5xVRRkQWt6upcmCMfiiX8+X3oktJWFJtpsDVYLdlONv2ogbr6ntDy5gradfLf4q K3A3Dum6yZjjNAZfFL3NnexNw67C2UOdQDZNsi2Evy9mqKjX/XLZBp75u0A2HyV9NE5a 8ZCw== X-Forwarded-Encrypted: i=1; AKwUvBxMatUB9JNG9mGOcSG9+09WJRkG5L3xecIoC6UZzcwmxP6bdxzCBQL4u5RGsryQOPVgsTtoujRlQI2WEfU=@vger.kernel.org X-Gm-Message-State: AFuF++kj0cNy3fou52ZPj5SSs2lwVYVuUh3L/VIpW+0q5pB4qcR1bo1P lIDvOVxpE7M8NAUZstQyihDyGCI5yam+QUFgn4/LWhE6f4Dz9o6GuF07L3Mw4g== X-Gm-Gg: AYBFou0dQ8LY6q2M8RQPGEWjDDCxJ5ZNaCvtBMVjFDSRVA/85oiwCSRFhE9tdKI1fXq SCIUuS3+//QvYK0gr3vJ/rlFGPJ1htwI1fM1AUo+p2kxxQyHeLK5yiNsV0uXAl5rxT6u/EHdsfF CeQ3ZSc0R7i9j0A+KWdPfNHr+KKpihvGVaYs6YpMBHKA1n3aEHxDWx6noTrZcvXp3kHKbUaLbxA ehpq3T18VEWghqvB2946uZyttzOhTBDQIAoBohxYXQxweu/DuyvXHrpmG8/KEZvNRKQzAKzcMMu RIcteqkqsgWsHuKbwfRCt1H1fk/nNowxG2hldWcHHZ5X9wFRyqwevBRBDOBeeg7Xest0qAbFSGU yRYKMg35XVbFUzP3Gq+5DBTPqGI0tDBIEvw3QZQGKS2/OnLQPf8e1eFcbsVQMgydckPcJ0vXzMh RI48EJvBmxhYEle4K2lxVyfNQQSleNZaRQa1I72S9iLUf0RA7Zx3/An674vFWpfh03tTpkSA0WK iIXJL9i+NT3G/hDwX1qOAUCS7KBKyANqEPLLlK4UTzct8I6Pk7umi8bYb1KooSVER9vwsCYsK/R gH3tOYL+ml3Idbs+ZIl/Rn7zo3xuFg== X-Received: by 2002:a05:6870:239b:b0:485:d31b:775f with SMTP id 586e51a60fabf-4908ab4a750mr780817fac.29.1790107707408; Tue, 22 Sep 2026 13:08: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 586e51a60fabf-4908eb9237asm564087fac.12.2026.09.22.13.08.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 13:08:26 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 14:08:18 -0600 Subject: [PATCH v4 1/4] 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-v4-1-92acea84b911@gmail.com> References: <20260922-ksyms-tune-v4-0-92acea84b911@gmail.com> In-Reply-To: <20260922-ksyms-tune-v4-0-92acea84b911@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=1790107704; l=12494; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=oV2R0UvbYfIVB77jCAXauJRFelOAEdJiPFl6JJAX4x8=; b=4RC9VqdWCoHfhnvqxQjqjGuKtFE8tpMesrUk8A7+J44QEhTnOF5OBqOU8fJOYC7+dIna2lG1N ZoOQW0suFA+BWYKk4EhY44KSQ0Za8f9KWsWJtmaG2uND9w5tKqmshhW 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/. 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 --- 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 =3D=3D 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=3D0. - 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 =20 If unsure, say N. =20 +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) +=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..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 +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define BENCH_CHUNK_SIZE 4096 + +static unsigned int num_iters =3D 100000; + +static int param_set_num_iters(const char *val, const struct kernel_param = *kp) +{ + unsigned int n; + int ret; + + ret =3D kstrtouint(val, 0, &n); + if (ret) + return ret; + if (!n) + return -EINVAL; + + *((unsigned int *)kp->arg) =3D n; + return 0; +} + +static const struct kernel_param_ops param_ops_num_iters =3D { + .set =3D param_set_num_iters, + .get =3D 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[] =3D { + "_printk", + "schedule", + "vfs_read", + "do_sys_openat2", + "kernel_clone", + "panic", + "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(unsigned int iters) +{ + u64 t0, t1, dt_hit =3D 0, dt_miss =3D 0; + 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) */ + for (i =3D 0; i < iters; i +=3D BENCH_CHUNK_SIZE) { + unsigned int chunk =3D min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); + unsigned int j; + + cond_resched(); + t0 =3D ktime_get_ns(); + for (j =3D 0; j < chunk; j++) { + const char *sym =3D hit_symbols[(i + j) % 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) */ + for (i =3D 0; i < iters; i +=3D BENCH_CHUNK_SIZE) { + unsigned int chunk =3D min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); + unsigned int j; + + cond_resched(); + t0 =3D ktime_get_ns(); + for (j =3D 0; j < chunk; j++) { + const char *sym =3D miss_symbols[(i + j) % 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", + 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 =3D 0, dt_bldid =3D 0; + 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) */ + for (i =3D 0; i < iters; i +=3D BENCH_CHUNK_SIZE) { + unsigned int chunk =3D min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); + unsigned int j; + + cond_resched(); + t0 =3D ktime_get_ns(); + for (j =3D 0; j < chunk; j++) { + unsigned long addr =3D addrs[(i + j) % 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) */ + for (i =3D 0; i < iters; i +=3D BENCH_CHUNK_SIZE) { + unsigned int chunk =3D min_t(unsigned int, BENCH_CHUNK_SIZE, iters - i); + unsigned int j; + + cond_resched(); + t0 =3D ktime_get_ns(); + for (j =3D 0; j < chunk; j++) { + unsigned long addr =3D addrs[(i + j) % 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", + 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 =3D 0; + unsigned long total_symbols =3D 0; + int iter =3D 50; + int i; + + for (i =3D 0; i < iter; i++) { + total_symbols =3D 0; + cond_resched(); + t0 =3D ktime_get_ns(); + kallsyms_on_each_symbol(count_cb, &total_symbols); + t1 =3D ktime_get_ns(); + dt_walk +=3D 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 =3D 0; + + if (!mutex_trylock(&bench_lock)) { + pr_warn("Benchmark already running\n"); + return -EBUSY; + } + + iters =3D READ_ONCE(num_iters); + if (!iters) { + pr_err("num_iters must be non-zero\n"); + ret =3D -EINVAL; + goto out; + } + + 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", iters); + 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(iters); + run_address_lookup_bench(iters); + 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"); + +out: + mutex_unlock(&bench_lock); + return ret; +} + +static int param_set_trigger(const char *val, const struct kernel_param *k= p) +{ + if (system_state < SYSTEM_RUNNING) { + pr_warn("Early boot run ignored; use test_kallsyms_perf.run_on_boot=3D1 = or trigger via sysfs\n"); + return 0; + } + 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) +{ + 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 "); +MODULE_LICENSE("GPL"); --=20 2.55.0 From nobody Thu Sep 24 14:26:06 2026 Received: from mail-oa2-f12.google.com (mail-oa2-f12.google.com [74.125.231.76]) (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 1F89B3A0E86 for ; Tue, 22 Sep 2026 20:08:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.76 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107725; cv=none; b=BQpsAnCt445HdWZilxKiW/Rn0i8ht7o+VglyEVSgLUpup3Fjz7ztTlh+cbir5BHOo20p3AjkMzzfnbitmH6zJfPTsyjZ6wxfyFeKoPjD20W0U4xG3cD9YeVy8aVDkPOSWv6cgGx9i8RgHe0Dba1xEiVhlywToKKrB4pfiwiaV98= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107725; c=relaxed/simple; bh=uSwF8oSlv0A6TNXHp0b7ZlXImXaVRQqeD6cloMWgLIg=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=R6X5lrzKtsH3nfgY6r5nXkjG0SWZYWY+QhuZ5aEqfteUCVirqOUqfsJkyQhJF+UjpRAwS6e1+PTLuvHQIqO7VM67IxaBKotWSWH8tcQ0cV40iwNFPgNR0WoPglZuqEDBS4FO0UpaCEQ2/f2ZGio+SpzqPtKzsksVaEB5VlZQxUQ= 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=qXi/mCry; arc=none smtp.client-ip=74.125.231.76 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="qXi/mCry" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-483c65c2fa7so192532fac.1 for ; Tue, 22 Sep 2026 13:08:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790107709; x=1790712509; 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=hU8R4H4DyIVzYPzLtsXcibjq0wK/EbWMtmm1iMO2MGU=; b=qXi/mCryMvu6Qjzs7V7B1D+PkPGpTy8bq2gwbBZXZhxc4YfmTnRgntUxqPF6YuJS3S hhBdirNiKrFrcytPDYq+k/JizqnLdIAi58RcuOl8B8Q6mwDPCXauR9odeTsdw0xhOJFA 9eu3wi/UWdLKxf7R3IQBrEgoDPLBwldCsx7ggyekIZCY39CNZtZYLKPzmyKxz8W+jhvY KJM2ddLWKtRIZagsgF/y83A/l2JZvKc24tmStJsSkv68hHmXz+fMLv3AEs/UgWcbLxzI DIxawRUshu8Bius8GJAyrJeTONMt12ZwgSvUBTes5ZjFovTZqGPR2pcSVIwmhRqIYlq5 jMRw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790107709; x=1790712509; 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=hU8R4H4DyIVzYPzLtsXcibjq0wK/EbWMtmm1iMO2MGU=; b=0oJLhWuBKF0DfV1+S08y2rZpHLmF+TMqrQ+vAbL7D/C1nX405oS3u5JqQKWgb+ynjv DYvOoxEXa2M9FTvqzUPRUhxVTWOEIb4++47iGNcVnZs7Q7IJKz9wJFLkALpBUWc1LIfN 6+nX8CONyXKTZCouxOucKvIPxinQP+0Xkcp4/Lurhx14kpMClYC1qkvrcG6ITMN7FPFL EekzAj+gKNe3vHnPXX41Dg8h47p5DvS6G3Yirp4YQl/QbJKcZgpB4i5XGWYrSWY3VXac jiOIsKJho9yF7+1/bEXUgg53nh8Jf0MAy+VpvKw26knbwD4XPwtbfZTUluoICmkOAEza ffog== X-Forwarded-Encrypted: i=1; AKwUvByJ08qNWvFuGfyPUNz9clRLETIYxAJcViBawIadg+ByWiFr7mFXiLjIyqmE6mxyUYtNUrsqQiV69+7Sn3s=@vger.kernel.org X-Gm-Message-State: AFuF++kK48L8xK6uChDvbPrtzymiiAaFgLTGQbAq7VvaSXTDsVyaNLPR eoIbTLZN6OfPOKmf6bXUSn1uGXvlLm/Qsx1XAS5GXvL7pin2IQFiztnwpbPR7A== X-Gm-Gg: AYBFou00s2anhrztWz2WJf6lhRB560d94i6/CYUR+FrbQBiaJMd2Cq42AxWAA/uq6ce 5QAn6e6ZOpB6G+Gook/u/eF81Jmk0VhkGO/24m+eDuAl8AWbT/u5JBqJhAUxZ7typX8ZR2zq3SF fIQOUBe4lY80nb3eKF1I7WoAO8lepPhkEfsVlCkk7G5fKWRt+uKoA2Yhafp7110qDsVInHLxdHX SKlsldvjpg39aEPG/UvRs+Y5n8V4aUSYP1RNhzEdKKenaGCZYrSbHJu0pPmtnENd3E50btmjQXF ZHZY3QnwlpAclU4P9zYLKseUwt7OaRdfQ9wqSZ1pAUD+Rp+AdNeHWdJ2jPCdrBkRk115oE1El/S KUShXG13NYXohUJHOP/8P2Bt8BnL4Wf6cXNM7olgaeufD/QATr6dx1JrcBkA80vqFZkkCtIdUQv Vq1Tp8feb2RvjoxmXHAF0YsBYLpcPAGg1PzVkUqn36HoQvqNcbY09orRxC2CcfKcKhaavqfDAUi n5QIF1E3IJ78lYRDdP02scoO7UIluM87BabA6NOelcEPSZKPmIf682sKq3WSeqDPJFWIDmqNqTQ DBAPDxaZ8Gfm+yMLiT4= X-Received: by 2002:a05:6820:c84:b0:6cd:3fcc:96ce with SMTP id 006d021491bc7-6d2d4011734mr383971eaf.76.1790107708875; Tue, 22 Sep 2026 13:08:28 -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 586e51a60fabf-4908eb9237asm564087fac.12.2026.09.22.13.08.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 13:08:28 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 14:08:19 -0600 Subject: [PATCH v4 2/4] 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-v4-2-92acea84b911@gmail.com> References: <20260922-ksyms-tune-v4-0-92acea84b911@gmail.com> In-Reply-To: <20260922-ksyms-tune-v4-0-92acea84b911@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=1790107704; l=6596; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=uSwF8oSlv0A6TNXHp0b7ZlXImXaVRQqeD6cloMWgLIg=; b=/tW6RZRloOuryOC5xA4efhF3zwIkn8HHOER8txp3BY+91F5eJdUteV4ztrCpuKMcTnyJpH2+R kyP+0nRyZ3uCS8oMyRS2eUwNGKoru1wbFDQ+/KP2i3xCifRtQPccFFb 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. 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 --- 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 @@ =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, @@ -42,28 +57,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 @@ -101,14 +100,43 @@ 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]]; +} + +/* + * 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) +{ + const char *tptr; + unsigned int len; + const u8 *data =3D get_symbol_data(off, &len); + + tptr =3D &kallsyms_token_table[kallsyms_token_index[*data++]] + 1; + while (*tptr) { + int diff =3D (unsigned char)*name++ - (unsigned char)*tptr++; + + if (diff) + return diff; + } + + while (--len) { + tptr =3D &kallsyms_token_table[kallsyms_token_index[*data++]]; + do { + int diff =3D (unsigned char)*name++ - (unsigned char)*tptr++; + + if (diff) + return diff; + } while (*tptr); + } + + return (unsigned char)*name; } =20 =20 @@ -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]; =20 low =3D 0; high =3D kallsyms_num_syms - 1; @@ -183,8 +210,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) @@ -200,8 +226,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--; } @@ -212,8 +237,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 From nobody Thu Sep 24 14:26:06 2026 Received: from mail-oa2-f12.google.com (mail-oa2-f12.google.com [74.125.231.76]) (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 DEC213E1683 for ; Tue, 22 Sep 2026 20:08:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.76 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107737; cv=none; b=GXsOnqF9Ciz7PegFZsb5KgVrCe5DHw/8/HV80K2nxW5r7iETJmjaiofxVRGKuZol2ea1vr8DLBouHskY9CE5G2wPvMb+QtaPFijkj8lusSsXlRXMqYRScohj7yyfiLhXO9rXYpipc/ce0ad3+/GV5FUK37rIJNSVJQlnWcz35pk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107737; c=relaxed/simple; bh=GAU8soK/soIgxIPJa40VL+WIbNoKOxxllpQZSMNrvVo=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=Nrm1EVbhtFDfCtnDeB0p2Jja/YhJlIXfgFOx9zlttn6rv0XjtW62B0nsUraitiVnDBKKw4zYOmcBRdvnao+CjnD1khW5SHV9KN8NFgAIzqNejSFWnRYC2estovzE67qmJAMmDPReq0abFq42n+bagfVN/jv8iMU4+clr17v7BXw= 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=AileT8pK; arc=none smtp.client-ip=74.125.231.76 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="AileT8pK" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-46accbdfb21so257131fac.1 for ; Tue, 22 Sep 2026 13:08:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790107711; x=1790712511; 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=sbNl4k+W1q7yiAA0aGRbWPBqZ/1TEL1hl7cPMNaYBEs=; b=AileT8pKyvMXhY/8nsz6ACGn5o0cwbihSHu8M5o6JwcyW2yuu06K3+C8SKA5rRqLeO Rzv1Xysp4Vb9rNBRNwt6w2qf9pdnEyveQ/Oqotx1wKKcDHnNnbmO14Fo+RkoWoEeoB/c ENcfw5UarsBOje5tx82MJ0bdvjTiaVvPPnhOUxxg11GWuCCfWx1Hddm8JtftdiONgokb 3MFX1tYLneu8IrixlUla3V1BU9otaEnWVItlCIqNaEH4WAEtSBnVcmfpfdIGZfubmyot 8V/iFZnZTrdjqAQA9sCsJcSLhyuCscQSHF/iUBxNIfRh7fqVDHLy3iA8qTOOuh9eXKw8 33Xg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790107711; x=1790712511; 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=sbNl4k+W1q7yiAA0aGRbWPBqZ/1TEL1hl7cPMNaYBEs=; b=k0YtDrN7uOeYNyj9Ore7aQIQC27PLgSl17E/EwStFi0MOKSNxgYfQ3oFzkYTQMABKw uFczEFZ84AZhgH6XXcD88AS4xjxnAeCsIZSJekUmS5Fyr7VZugG+q767xSRHPK9jvmQT AFpoh3D6ZD7eFT4QIygE+yvtCoQjUo88JlJCn77Ph4SddHc8NMqIay71vI1yI3eOGGX/ nLkqgDDXnWYGcv3mTNZoH+ueWCuzKg3tIHei/bi3+2m93gQD7Ui+IGqEUBnLOquR7DcI n1nelC7vQUib0BgnK7kDoWrUt2NzKJylcdk8k9RfWbXDZZwMqwwiAPiv5dPMpsU/RCX2 A6Wg== X-Forwarded-Encrypted: i=1; AKwUvBy/5feeWzGXcaN+eMciNYLN1BLCchkQ2tsrGpWea8lqJauzc56DVG43eIg3Qz7GF23J9P/YcvRYWssO930=@vger.kernel.org X-Gm-Message-State: AFuF++kTNP5hLSOr8Jmha6ISiZsopFtqO8o34tPLlP4S5TWXWuC9a5SY 8rGj6NsLv2VJ9IZNHDo0Kn7vxQeJCJ9ovBOp3a8ZQDGsmkYowWjMhmUe X-Gm-Gg: AYBFou0GcNOjdBkMCvBhFTLlfTLFnHX7iZr7l7tN6gFmhgaNinWzDp/nDcKGUkNecsB dvepPsbOhPAo2n7zn4asnetzdjg3xfTPgiSJQ96a6GkyvxYBbNPXvmaGoylIShz96nOcdkBIeVW ShC7mR3jTuVMQi76GzR5pCE9e9wlFI6GVbhUUcV9rR0Ug12OYL44HgfI/IgLxmlaj4KeHYhoLYR 1mq1rHTP6u8SoM4dzF2YJ8ZRyK2hwnDJxQYFnQ0/WtQt+P3zxEagI2+FNAayJR6u3IMnU7KI/ob wQRAm2UtAbo81akJZskB5KIvpC4IVMW7/MF35nrkZm7c1JDoEr0kDqnUGN8WY3eT+pg+sHT5MCc YZMyjhVTBzSFu1QgGy7tgPybl28uWvxO1jzvN1uDMr4uqMdSFamYraPfbAS6FH7Ry3gLMx/0dMJ cIs3HIb8iYJPnydhsNvPJZtd/dpGKfc6aaqd17P0qAGXDAy5OOYrKQqGtVadvGvCVBnspxNosSi rxCVjJGaU/+C28yM0rMlJc2q30hTsVb+fDDw217J6FGtaDwTHZJLT1GYFZlzwlcUjM0he2df8td nhc36d9VCPvZsE1yC1E0mLT5iRTjaQ== X-Received: by 2002:a05:6871:340c:b0:48f:e363:5cc9 with SMTP id 586e51a60fabf-4908c5fc720mr685685fac.55.1790107710505; Tue, 22 Sep 2026 13:08:30 -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 586e51a60fabf-4908eb9237asm564087fac.12.2026.09.22.13.08.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 13:08:29 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 14:08:20 -0600 Subject: [PATCH v4 3/4] 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-v4-3-92acea84b911@gmail.com> References: <20260922-ksyms-tune-v4-0-92acea84b911@gmail.com> In-Reply-To: <20260922-ksyms-tune-v4-0-92acea84b911@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=1790107704; l=13772; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=GAU8soK/soIgxIPJa40VL+WIbNoKOxxllpQZSMNrvVo=; b=fTsqZWFey3zeLGk8mlnrfpOeY4sMTsFvBW4VUCETSnZEzwPTWrX9UXMVYOpDOqd9cwXnciyPD tWdDJI6RBSgA59X376C7eN2KRgTvK8tWzCl6XbVVu8LEzkfziycyfwV 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 (~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 --- 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); =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 d18d78e626db..bb34b4c0f690 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 @@ -90,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 @@ -139,12 +142,11 @@ static int kallsyms_strcmp_symbol(unsigned int off, c= onst char *name) return (unsigned char)*name; } =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; @@ -177,6 +179,99 @@ 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 __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 =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 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 =3D rcu_dereference(dyn_kallsyms_offsets); + if (offsets) { + off =3D 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 =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); @@ -219,8 +315,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) { @@ -243,6 +341,7 @@ static int kallsyms_lookup_names(const char *name, } *end =3D high; } + rcu_read_unlock(); =20 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, un= signed long addr) static void test_perf_kallsyms_lookup_name(void) { struct test_stat stat; + int ret; =20 memset(&stat, 0, sizeof(stat)); stat.min =3D 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=3D%d, max=3D%d, avg= =3D%lld\n", stat.min, stat.max, div_u64(stat.sum, stat.real_cnt)); + + ret =3D kallsyms_lookup_batch_start(); + if (ret) { + pr_err("kallsyms_lookup_batch_start() failed: %d\n", ret); + return; + } + + memset(&stat, 0, sizeof(stat)); + stat.min =3D 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.rea= l_cnt); + pr_info("The time spent on each symbol is (ns): min=3D%d, max=3D%d, avg= =3D%lld\n", + stat.min, stat.max, div_u64(stat.sum, stat.real_cnt)); } =20 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, unsigne= d long addr) return 0; } =20 -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 =3D 0, dt_miss =3D 0; unsigned long addr =3D 0; @@ -153,10 +154,15 @@ static void run_name_lookup_bench(unsigned int iters) dt_miss +=3D t1 - t0; } =20 - 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 =3D div_u64(dt_hit, iters); + if (avg_miss_ns) + *avg_miss_ns =3D 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); } =20 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 =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 =3D 0; =20 if (!mutex_trylock(&bench_lock)) { @@ -261,7 +270,37 @@ static int run_kallsyms_benchmark(void) pr_info("Starting kallsyms performance benchmark (iters=3D%u)\n", iters); 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(iters); + /* 1. Benchmark baseline unindexed marker scan */ + run_name_lookup_bench("Unindexed (markers)", iters, &unindexed_hit, &unin= dexed_miss); + + /* 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", iters, &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(iters); run_table_walk_bench(); =20 --=20 2.55.0 From nobody Thu Sep 24 14:26:06 2026 Received: from mail-oa2-f12.google.com (mail-oa2-f12.google.com [74.125.231.76]) (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 22227397936 for ; Tue, 22 Sep 2026 20:08:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.231.76 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107748; cv=none; b=OmNkJ7aShgdS+ElLHRn4XQoG27l4Y2cxb6fuC8ku9Q/ujBfJsO8uogeZG67fkUir62Z+ENzq792ckggMUHn+vltH/iWtdIeaSmXydAX+Lzy3LWWHlNLAai8tDyzLHd/1iOphe+MQpDMVhGfIN3KPQ0K3zKueYMK5yBxcsOhJ/jo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1790107748; c=relaxed/simple; bh=q0sZDppUsa+eu5sPpZoAEi+M6OKVy6NJVptfUVXehJQ=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=cGJUJkFdX/5tiCg7stKpG4HLKHbJ6HkkkBR1wXQl+CDhBcjUmItktLmkr9cC7nBw510oJNtMBP3QbahXORRVR/h8OBiId2sr0tXROC8djExXUZ/2i2NABEbxjr+KYt8V3AzvNX14P9HcTuvGNmAt4FmSCvvBrIkH+L5hgN1uNB8= 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=h1+oAekl; arc=none smtp.client-ip=74.125.231.76 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="h1+oAekl" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-47c57070c52so82731fac.0 for ; Tue, 22 Sep 2026 13:08:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1790107711; x=1790712511; 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=AlFlDOH8oZxKnMeTYk9lUtSf3sYQz7J3e363i7elvXc=; b=h1+oAekldty/KlscOKiGPYVEtvgOO2vLr2xMaL1f78rh2FMC/qnCkoKhbEm2U/fsrv 1h7wA/Mpc2IJobVP8meGgjHsOatUjfbWcHaWQOMkbypk0+/3UHKafiXnok3Th06GOmw6 kUMYL3njRRlIbisYK7A7jZCm3vUTiYPdysm2ZMzvM5XxOm4xYS8lJBwSrsu2i5QgTxN4 jObObBzwlpvEWRIgnXb0X+NvxD1MLge0vgs5o7rNNMMYtFkmgDKlYXDU7EqHEN7SpWpm 7fYq+lZqQ+ZJdG/fM0XQ6Trhrqx2+2qipAN7fyk+XYOVcynfJwfQ/7ifnPCjLpZmhWZI r0Ag== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1790107711; x=1790712511; 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=AlFlDOH8oZxKnMeTYk9lUtSf3sYQz7J3e363i7elvXc=; b=2ZTEHaqwwKtCDeAgISJ/1pzDN0F56YLoa90iCjzS916decXx0eQVlrvOgcA3powDSZ y1dP8e8rCT5SZCiKRuH+TphBTKLSPCvNAaDI1nZcnD449T2ckPvVnSJl5gwphunqT78R opgMFfnAaFLYuy8LRnEfzgXU1m3Ll3EhTrm/n0ycqmyQQcj+048YYAn5Ff9LjzyNd1x5 0MRJjcg+HY+mFz3Afk9sOYVsabV1tar7boqzXc03Jkpcxkgo/hhNRC24vY3chMFlaG4o Y8nRxoY/t3QqjVzNaAptd9pOk3SS+HkLcEtMesnDmEI8gDPhYe9yAOQ/d8385GGFUCeR HAtg== X-Forwarded-Encrypted: i=1; AKwUvBx6wbf35ha1qMe4vJyiDaz481t8vIkip+SEu/eFAmYeBtSF0iEn5SYxazaPR75C7TC16LU3ezYfvo0N5wc=@vger.kernel.org X-Gm-Message-State: AFuF++nVE/vieOgLx165X+4C2F2BPTr0Uosii6Sj7S/cytcvFxZvxF3J FSiqpqf2rY5Y2fuo5cLxooamF3Gd7GWtFSr73QcSjLlcyJ+7BrmniqC6 X-Gm-Gg: AYBFou2/LaBriEFp0qRzUUfN2pR4Cw3vfSJ3nzvY7reETLakHbwMH8TfjXXqEOdp9kU pOq4Wi12asUY04h+2ZxA4H4kkPFhjoe3sNTH3OtA/OYEpK+HUl0pzYvMh3lIuBBfr+p5j81+VVW sSEg4Xu8l//mZv20vM5AYOwYwTyv2Pnmlgq+aHcbA757K3NEAlXODVkcRgciGRtWBYtXarkXf2a eNCWroYhIrdtyeSibAlPV8J/h+KbNVX/RDtPPHGV0x6g7ILn58iuE0Mp8WFg/ZPQlAzonK0zksD sfEOeVNioRdhx+AwcNmnWQ1VXPkSoKvAtSwn2wd/3POGk+7I+vOIdXTq04uP1hJFceEPoaBIpKJ jSrSMW61quAmiZdI6SxQkMGiZ1D4obbT0NbkfU6+fYix04BrNvgm//V6V4LxtNEgpm3xBO+OJCX tZ6K+3Z6xi5IsosVt1G3rGLVd665rNlP0UidH8Mu+u2TiY5DzkPXHTqYHZsssMRCLGgLbRAMJAi hUa59fXMsD15v/4wbYaj1BnUodKaNgNWe3cssCXzMW4Sx297xqOIyHBh9Njx3Go9uJUhgcMGOwG DrPGjcpTKqTZHv/dNbxvRZahTmqtxnkG+yp7jU4a X-Received: by 2002:a05:6870:e996:b0:48f:82a7:84cc with SMTP id 586e51a60fabf-4908e34ec00mr569116fac.0.1790107711491; Tue, 22 Sep 2026 13:08:31 -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 586e51a60fabf-4908eb9237asm564087fac.12.2026.09.22.13.08.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 22 Sep 2026 13:08:31 -0700 (PDT) From: Jim Cromie Date: Tue, 22 Sep 2026 14:08:21 -0600 Subject: [PATCH v4 4/4] kallsyms: Unroll 24-bit sequence reconstruction in get_symbol_seq() 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-v4-4-92acea84b911@gmail.com> References: <20260922-ksyms-tune-v4-0-92acea84b911@gmail.com> In-Reply-To: <20260922-ksyms-tune-v4-0-92acea84b911@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=1790107704; l=1647; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=q0sZDppUsa+eu5sPpZoAEi+M6OKVy6NJVptfUVXehJQ=; b=YtdomdHVifgDSmUNlCebB5wNAipNPmPSACPDou6l7lL+wvQSUi9uR5FwEr5jNvxcdDOPZLnBM 6f2Qs6omN03AmSblhpXa5N5LBIdHGXVNnX0ZTVbc9Yh66o/qdxqaklq X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= 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 --- 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); } =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, --=20 2.55.0