From nobody Thu Sep 24 21:19:01 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 C17FA3CB541 for ; Sun, 20 Sep 2026 03:59:04 +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=1789876746; cv=none; b=evvHpM9AV9pWKyyj3rZbYtY0w+8VXHypnBy5RNG0cBv0DC43fYKv9b5dDN1e6pZOOwDhW0YfDTIjCeQf2yxhBfzJG2HiISfbcfs8SfcIISo8w+8mnFI6f3b8IIVZB+kpinQFsKT09MJ+zjDalW9DLYJCddbcGpGT6cJVhKh0zDI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789876746; c=relaxed/simple; bh=nSVguYsya202ycWnyh7LvZPegeG4xaW8+imMMxZ/vE0=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=IUNYyMRi9XLcuZHjVbarMXdvzBeOfE4wQQOJ4jftmFEJErj4OasZXnUJ8ATO8mPYOMXLezC7IEUj7bMSaV5abJypu4dfhxj9oamSNgTP4MfaqP/kOROcq2IPXHSj7XbstK+Y4EhL7+xJGzvt3gGvP6yNXB/iBG+SHYXH0uDVwSA= 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=hqwa5UZL; 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="hqwa5UZL" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-466ccdd76a9so1724638fac.0 for ; Sat, 19 Sep 2026 20:59:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789876743; x=1790481543; 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=hqwa5UZLRCNHzZPVYLStvFu8dHDLkRsCWq65YsbiqxXREAZjGmYK+gz9pMIQLyPwc0 8NEXtSWWYhCZdPG3H2cct89bsGH16hAzGntucqMXA9mckqDgUUZV42M5yU74bqjA/bd0 4NqfxVGZAOnkqTbduKuwL5BuxsQyKzidznAY/ai1ktiutvsknwOfribdjh9amVno8Rsv zjbE2trv82OdWpVvzYjjy0FmGZGfCLj2IC0RmibxXY7kOR4Y6Kli1YeuIF111Ujr+V22 oBopSQFuxZXzPzTQUjFlZRAgFEZs+wiN5bO2qVKTXS0KlgitNQDIvY5ybT6to0fnB0Zi rDzQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789876743; x=1790481543; 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=VOdio5n7iF6Gv2XjQ8/3SiPjaP2bXhuBPnI7vDsIwrPaVPXC/VGu6tfobcfRcCZDr+ EisM1ln/wxPQ66Obu1xB9Io4gvS8lOi7U1mPQN1SmsmEwb8uG5lObSr1uEXztT7PuxAr eit7d6zXCJziCDIN10c8tMGk35jcVD7zK1bt0Syfh4jA9P3OyX6o1nZk1nTEw/kycf+p rFP4z5AIz7rKdw7exLKPjXVD/ysEiKddbYEDMKIEKWjSPOooB2BCPfocWCnJnnq05ZgC tInUf4jKUoubDfUusL4XvUk82XeMUXYNwKe64XlS3mdIQ0/hmdL7MOEf6Zt+OmS08UBC s9/Q== X-Forwarded-Encrypted: i=1; AKwUvBy2Ohu1Y3rGavvzgK/kodBEXil3hyBA7JVlBgLS5I1qmA0/zbTurnk27kZk18ovewYzRX0GSlx6xoPkYZ8=@vger.kernel.org X-Gm-Message-State: AFuF++l3UysCBeRRhc1crE0z9RcmNboybZPi9GPY4ysn4p7HgjtHmOWB OTzC0jYt0iOI+x/FY3x/rQuVklI0E0P7vLirBLGU4N+GjQV88cqYdRjN X-Gm-Gg: AYBFou1qFDD7DOJx5zeSkents2ke6RfttZAzi+Gzo0do+EdOelVsUKKnMn48ag5SBHh faw1x8SPxVsoRAcpJqTHXo+14qOxDlfYAcWt4r72WHfry9ggFcBhMg16Em19evBe5EceHEJkOIk RjnF86eAeAvA/pyFkIiqN2H+EoRxVs/yNxjXRtxHQ61Na/xMyhkEp/qUEGhh6djcWmfTGIRxAUF FWkjspzevN4+pfo4NSIcVghG3dYmi9fCQzHe0QM/sImWGL67Czr4ETBVQm8EyPcVpI1YEo1dTex 37QP4kFT6Q/RSrjhET+8kOFhZ4UHIo+pXtqBFEYY7xG4IeLs78EmTkzWWhmf9dcSjiMBkRDyla2 mtsAkWtzeORU8kMQVilbqlJUZiknK0XssOdgFiPDgYwf5snDve6TT24h12VleDw1Rswj3p1ELYZ ZbvcQnxonS+2x27JbISq7/BgwmBFpvhj2mkPd9/Y7vzWtmR80PVjMbWcUfJkqLYtAWE7tHWvjx5 g10gpmGfMJwnQgZBNpD9d9qCADHC+klSpOJR9UMhZWD3sWa70l78bI648FUe5e3APGpUgY52H9R LVljn0ogksMiZ8ecgoKd X-Received: by 2002:a05:6820:1c9a:b0:6cd:3fdc:a933 with SMTP id 006d021491bc7-6cd3fecc3e5mr3449090eaf.80.1789876743558; Sat, 19 Sep 2026 20:59:03 -0700 (PDT) Received: from [192.168.0.197] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-4881f4d7861sm4146915fac.1.2026.09.19.20.59.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 20:59:02 -0700 (PDT) From: Jim Cromie Date: Sat, 19 Sep 2026 21:58:55 -0600 Subject: [PATCH 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: <20260919-ksyms-tune-v1-1-d85c97da1a32@gmail.com> References: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> In-Reply-To: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , 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=1789876740; l=9420; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=nSVguYsya202ycWnyh7LvZPegeG4xaW8+imMMxZ/vE0=; b=a7B9miUPH8gTO/u2Uk31hK0exxzWkLBwVe5iAlQATS4u4hLAGfj1phiyt7a60rP7m6PxAYp+R GLR8d9sBTB+ANEnD36U56DdWK3Ujl/PicYimkjnIEGlfpuf5uQhievV 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 21:19:01 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 251663CDBB7 for ; Sun, 20 Sep 2026 03:59:06 +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=1789876748; cv=none; b=OFG78sxlRFhqD+T3HHbp/cco42uGUJx/PA5OfIck7u9bmtNB/D7bRNj2Y4UQP7B5BZT9UUF2d1Jrzzswvld9BbnCP52OlWGl2MgjVds9aJbNPjMCRGeRycI8mOKvdXal/abZSe/AvWQ1sFqDIjZGNz8Bp89Gt5jskgd9nmEwRDY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789876748; c=relaxed/simple; bh=Pmx36gQOuPwOlhgjUxsxj611prlgdw6+8eilpqQR+lY=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=tH0DIFiqgdwBjdlykc8sP4S65YLmw4UFTOwdclV+NhE1g3xQ+QdIk449fub5dvfzZrfFdSqtrTCWY2EVooGZTRgbMUgnypGHzBUVViP2dqYX7trwgz1E04+Plsi35hg7oqZmf8orQVJUaMVxecUS+LoE406yBSQ0Dj2NZMTNqeo= 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=CODjGH4k; 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="CODjGH4k" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-482620dc91bso1461861fac.2 for ; Sat, 19 Sep 2026 20:59:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789876745; x=1790481545; 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=K6vJ2DRK9H1Alr5nUnbVfDQuEMO7fFwDEgneTA5sWg8=; b=CODjGH4kxI2+vgU6bfPlW+d9KDNXtz0RdphukPsuo1UEEiluQGsVS73m58ari3p4Wd pVrpBwT7xifClQAUnN2wQHuV6fAfVqnyilZqdovq5lEWYrv6ONBzh3TeQrhMWTJvXSCo BTCe38Y/IIU7NQstQFxvq7ZSNEe3hE3mr5JvcPjcUe2SWV8rCsXjfhpsqUuktzotc5Yf kH9aDDXf1+TT6R8p7QX0hGqvCVDVofXqa3bHvM+zV4TrNxAjIgsXWgYITFfmPG9rJfES omtY6kaqe/tFljsdrabVrwZMOw8FGG9Vy5EqG3GG2LXZvqLe4yv6huqiy3BLNAiRqdkg jijQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789876745; x=1790481545; 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=K6vJ2DRK9H1Alr5nUnbVfDQuEMO7fFwDEgneTA5sWg8=; b=X2tv2e0aRmevZRI/wHFpygJA7JFmM3pzuh98p6Umw7fS9HrwCeBg9PooOmFADaTJmF D4JDJG5rXurRwH5A2zpeuhBZt4gMVMpheNeipaQA4AmgJGdyieCiDssNNQwHpLN9Xd2m xqz2zwN9/2pqVYeYyZoePEOWBdRxRK86ELbfA1MK06ond/boYy/+yBIypcZP9YGm9EUy 0CHtK48PjYe2OTcjh24UsU40KEebEZ2u/978Zqhq8LF45TwquaaVg25iEjiPjZ7Qvh0T OYBk3Bp17s2AZckHc7aJsVxPjz7gtLMiIXsScD6sMe93D4gBVS44hdpDplGIM/gVmsxU JHoA== X-Forwarded-Encrypted: i=1; AKwUvBzDCfKCtKcnWF2LNaYCrh5qS60QmNd0dDBjzU/4AUVGKQ9MBJnQKphskjk0+CiHxvoo1qejTkYXMtKxQwY=@vger.kernel.org X-Gm-Message-State: AFuF++nWAk6+I/H+5ARD0+GRu7dYEhVS0lAZUhwPpaV+nHTkLm41HB+z sZblhfKkiaXp8JGDtDjc/0PrHXjTlW0DkqHg+YXWTEp37Lp+YCAeytJH X-Gm-Gg: AYBFou3YYbqoAWsQqMfZl1gZE95ACeBRDlOtVzXatws4mVd47MEeghcgarh/ObvEtZx W1+R+PZS7VWX2DMRPUcHGkBpKD/NG894RXi75UcgX4rnuQLDvu0tOnJcMqQHzhqRXmhQBP23REk +7/nPYXt+I+Ds/nu/CRW3O4LJQddlE5CHq7xHrPioIwjOgvJKYUUpB+JfO8bMmCBW455lOulRXc /EbCbDdTkFYaOVJTHrZmsPOz/Rx5w90uChlthRB42s67NMM2trfU+590nAVpDFpVylC0T4H/U/w 7A3AgGDVfWAz8POIBeWzbgAExyOwt4/EigXoW+Axh1H+NFy23QM+M5qjIP5Iz57mMZvl0zfVBpF 3BfVKUMudqiKwV8N7wtHtY0OEhBtUiMY5gC1rpLp9kGmV8iAhx0soSFjL+RYCwBFX+cOMx38JVV Rt4UXglk+heRHne+yJUpl22pwKOH8y0RoBMiqrS5fSwO+wlzXP7Zts4nn0kZfx3eK+UfGo2Yqwu ko3F7nNU5yCpraYjnUoUYAA7wUAKyxA7sacdA2AczAD19WPuLRacAa51MX1hq1WmGtqMnoZQi1+ WgkxDS/JDLCCVrlCQDU= X-Received: by 2002:a05:6871:7a9:b0:46a:d6a3:8c22 with SMTP id 586e51a60fabf-486e4f1a11amr6340429fac.12.1789876745027; Sat, 19 Sep 2026 20:59:05 -0700 (PDT) Received: from [192.168.0.197] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-4881f4d7861sm4146915fac.1.2026.09.19.20.59.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 20:59:04 -0700 (PDT) From: Jim Cromie Date: Sat, 19 Sep 2026 21:58:56 -0600 Subject: [PATCH 2/3] kallsyms: Add 3-byte index into compressed symbols to replace marker scans 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: <20260919-ksyms-tune-v1-2-d85c97da1a32@gmail.com> References: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> In-Reply-To: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , 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=1789876740; l=7312; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=Pmx36gQOuPwOlhgjUxsxj611prlgdw6+8eilpqQR+lY=; b=sfnlZSte8huyN8cCnE1xR1U7rA3Brj5kEawMEvQBh5NVii/Rmruw7ABN5HyiB9QXTp2QSXtta sKYKEPJ97U0B4tmP6mGtFhwtShBXwxL59FYa6SnhOLdAb2YhRBokaoX X-Developer-Key: i=jim.cromie@gmail.com; a=ed25519; pk=C6E5ODlPQo7ZBynATXH9wg7K6HxP0pIXyf4s38Qw0XE= The compressed symbol table (kallsyms_names) packs ~130k kernel symbol names, in address order, into variable-length records with format [][]. This layout optimizes address-to-name mapping, but name-to-address lookups require a linear scan. To accelerate lookups, kallsyms_markers was added to record the offset of every 256th entry, cutting the worst-case walk from 130k to ~128 hops on average. However, this still leaves substantial work: during a 17-step binary search in kallsyms_lookup_names(), the marker walk repeats at every step (17 * 128), decoding ~2,176 record length headers per lookup. Address-to-name resolution (sprint_symbol) pays the same 0..255 hop penalty on every call. Introduce kallsyms_names_offsets, a 3-byte-per-symbol direct index into the compressed kallsyms_names table. scripts/kallsyms.c emits this table at build-time while writing kallsyms_names, capturing the exact byte offset for each symbol. Using 24 bits covers up to 16 MiB of compressed symbol names, easily spanning the ~2.3 MiB table while saving 25% space compared to u32 entries. With kallsyms_names_offsets: 0. get_symbol_offset() performs an O(1) 3-byte table lookup, eliminating the ~2,176 header scans per name search. 1. Drop the legacy kallsyms_markers table, saving ~2 KiB of .rodata. 2. Unroll the shift loop in get_symbol_seq() to match get_symbol_offset() as a direct 3-byte big-endian load. Signed-off-by: Jim Cromie --- kernel/kallsyms.c | 43 +++++++------------------------------------ kernel/kallsyms_internal.h | 2 +- scripts/kallsyms.c | 30 ++++++++++++++---------------- 3 files changed, 22 insertions(+), 53 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index b9e573e9a10b..21adc5b74ec5 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -113,40 +113,14 @@ static char kallsyms_get_symbol_type(unsigned int off) =20 =20 /* - * Find the offset on the compressed stream given and index in the + * Find the offset on the compressed table given an index in the * kallsyms array. */ -static unsigned int get_symbol_offset(unsigned long pos) +static inline unsigned int get_symbol_offset(unsigned long pos) { - const u8 *name; - int i, len; + const u8 *p =3D &kallsyms_names_offsets[3 * pos]; =20 - /* - * Use the closest marker we have. We have markers every 256 positions, - * so that should be close enough. - */ - name =3D &kallsyms_names[kallsyms_markers[pos >> 8]]; - - /* - * Sequentially scan all the symbols up to the point we're searching - * for. Every symbol is stored in a [][ bytes of data] format, - * so we just need to add the len to the current pointer for every - * symbol we wish to skip. - */ - for (i =3D 0; i < (pos & 0xFF); i++) { - len =3D *name; - - /* - * If MSB is 1, it is a "big" symbol, so we need to look into - * the next byte (and skip it, too). - */ - if ((len & 0x80) !=3D 0) - len =3D ((len & 0x7F) | (name[1] << 7)) + 1; - - name =3D name + len + 1; - } - - return name - kallsyms_names; + return (p[0] << 16) | (p[1] << 8) | p[2]; } =20 unsigned long kallsyms_sym_address(int idx) @@ -157,14 +131,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; - - for (i =3D 0; i < 3; i++) - seq =3D (seq << 8) | kallsyms_seqs_of_names[3 * index + i]; + const u8 *p =3D &kallsyms_seqs_of_names[3 * index]; =20 - return seq; + return (p[0] << 16) | (p[1] << 8) | p[2]; } =20 static int kallsyms_lookup_names(const char *name, diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index 81a867dbe57d..430abccfab63 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -12,7 +12,7 @@ extern const unsigned int kallsyms_num_syms; extern const char kallsyms_token_table[]; extern const u16 kallsyms_token_index[]; =20 -extern const unsigned int kallsyms_markers[]; +extern const u8 kallsyms_names_offsets[]; extern const u8 kallsyms_seqs_of_names[]; =20 #endif // LINUX_KALLSYMS_INTERNAL_H_ diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index d996a43c4078..83a8747269ff 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -44,6 +44,7 @@ struct sym_entry { unsigned long long addr; unsigned int len; unsigned int seq; + unsigned int byte_off; unsigned char sym[]; }; =20 @@ -393,7 +394,6 @@ static void write_src(FILE *out_bin_file, const char *o= ut_bin_name) { unsigned int i, off; unsigned int best_idx[256]; - unsigned int *markers, markers_cnt; long bin_start; char buf[KSYM_NAME_LEN]; =20 @@ -403,18 +403,12 @@ static void write_src(FILE *out_bin_file, const char = *out_bin_name) printf("\t.long\t%u\n", table_cnt); printf("\n"); =20 - /* table of offset markers, that give the offset in the compressed stream - * every 256 symbols */ - markers_cnt =3D (table_cnt + 255) / 256; - markers =3D xmalloc(sizeof(*markers) * markers_cnt); - output_label("kallsyms_names"); bin_start =3D bin_pos(out_bin_file); off =3D 0; for (i =3D 0; i < table_cnt; i++) { - if ((i & 0xFF) =3D=3D 0) - markers[i >> 8] =3D off; table[i]->seq =3D i; + table[i]->byte_off =3D off; =20 /* There cannot be any symbol of length zero. */ if (table[i]->len =3D=3D 0) { @@ -454,14 +448,6 @@ static void write_src(FILE *out_bin_file, const char *= out_bin_name) printf(".size kallsyms_names, . - kallsyms_names\n"); printf("\n"); =20 - output_label("kallsyms_markers"); - for (i =3D 0; i < markers_cnt; i++) - printf("\t.long\t%u\n", markers[i]); - printf(".size kallsyms_markers, . - kallsyms_markers\n"); - printf("\n"); - - free(markers); - output_label("kallsyms_token_table"); bin_start =3D bin_pos(out_bin_file); off =3D 0; @@ -478,6 +464,7 @@ static void write_src(FILE *out_bin_file, const char *o= ut_bin_name) output_label("kallsyms_token_index"); for (i =3D 0; i < 256; i++) printf("\t.short\t%d\n", best_idx[i]); + printf(".size kallsyms_token_index, . - kallsyms_token_index\n"); printf("\n"); =20 output_label("kallsyms_offsets"); @@ -502,6 +489,16 @@ static void write_src(FILE *out_bin_file, const char *= out_bin_name) printf(".size kallsyms_offsets, . - kallsyms_offsets\n"); printf("\n"); =20 + output_label("kallsyms_names_offsets"); + for (i =3D 0; i < table_cnt; i++) + printf("\t.byte 0x%02x, 0x%02x, 0x%02x\t/* %s */\n", + (unsigned char)(table[i]->byte_off >> 16), + (unsigned char)(table[i]->byte_off >> 8), + (unsigned char)(table[i]->byte_off >> 0), + table[i]->sym); + printf(".size kallsyms_names_offsets, . - kallsyms_names_offsets\n"); + printf("\n"); + sort_symbols_by_name(); output_label("kallsyms_seqs_of_names"); bin_start =3D bin_pos(out_bin_file); @@ -511,6 +508,7 @@ static void write_src(FILE *out_bin_file, const char *o= ut_bin_name) fputc(table[i]->seq >> 0, out_bin_file); } write_incbin(out_bin_name, bin_start, bin_pos(out_bin_file)); + printf(".size kallsyms_seqs_of_names, . - kallsyms_seqs_of_names\n"); printf("\n"); } =20 --=20 2.55.0 From nobody Thu Sep 24 21:19:01 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 A48403CF21A for ; Sun, 20 Sep 2026 03:59:07 +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=1789876749; cv=none; b=FvPECw9AT3aVwOlrzgyP+LyySqT5Mzh/0MRweG9inuW2fu1AmYQOdobGNICG0HFY4IAA+jsnPs6PvNrVN8z5zRq7roRWoe1TuNhctUAk7IXUuy6b2Hk2VYhbkpJoUP336kIKkQCvYTQSqwwSAO4sr/Yyq3d1CUFtSaJR/nzykoY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789876749; c=relaxed/simple; bh=LumYwkTWkCz84GQ68MaksoLHoAbrKV8RYga/OmBRWWs=; h=From:Date:Subject:MIME-Version:Content-Type:Message-Id:References: In-Reply-To:To:Cc; b=YXCWk4+SJN714tV6lE+3ztODddVpgOVDKzSNRegQSg1hq4j4R4XYV5WPMXmQ2AlY7h9Ka/uecZ/sFUa7Zd3A/1c66kgEQtTJpi2J6MEpvIkx9cwRk9OrrCTGQSiwneMUVa5goJ1RVXoaTmskDOJdHx3JqZG8aa0tB/FkcolsfYw= 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=Wffv17K4; 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="Wffv17K4" Received: by mail-oa2-f12.google.com with SMTP id 586e51a60fabf-466ccdd76a9so1724661fac.0 for ; Sat, 19 Sep 2026 20:59:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789876746; x=1790481546; 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=SpHEPLob7KaPi++v6k6BcQW51q0CtS8LphwQtLRxilE=; b=Wffv17K4gh6S7m20WqfeJcK5j9YLtH873wwPf9IdQ8kxflCt/hQFfBXEM8Qa5DzNT9 7DZy4njZFVsTh6ABwBhYmdxh4qLPKVGJFhEWvHHOicO/559z63STggAXcj3PE6xr3yu5 2+SbmI8DJx+1AhQ1JFB0g5XbtwEz6OWoMgiuWHFcSm+cbb+ITmx9L2720gf2IN6y3G3/ AVYELfmWZj8okdMbqEcFxv7bgnfx2je8Y+enzBvX1n7wfvukEFJkqbjEn2dZaxziissW CwtefMluFof67/40pOtcQWB/QhjTBapuTr78qHGX2iAPCQs9TJEN/E+7akSwZMxx3Ng/ QNnA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789876746; x=1790481546; 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=SpHEPLob7KaPi++v6k6BcQW51q0CtS8LphwQtLRxilE=; b=pw4qiDCTRdPPx654X4Wt8LZyJ39vLe9tEfU3f+MCe0BZ6KA34RRZunVkpTqI1Dru1a NhdaDNiGEYDidULihE8fc+4L40DxpWvRQ+XWC50iTliCuKb+gyTU2sFz1ejIBl6KM562 Ea/UciG4LFCv+/Sc9J1I0G0oRnx02SKhIE7cM5OCtSloGrjf+DL8H02Gnt5pmGT/qch7 B7Y5b+alzAxyYhUuMJ+9Z4JEaOPBmIcfeH42JlY425YNNBphhs8O7SUajP/70e5Tcdb4 3pjt2bnb9URarw4g2wlrlxVhNndS5FwO2HCyFOBB/sRjPw/uJ9j1VO/j4SYuEkq2f8Np Bxug== X-Forwarded-Encrypted: i=1; AKwUvBydC3S+kwS9mm+jvPLb4Do86KOQfS1N9RJWvmEbyVYgxPcgraAlM3CzExYST0K1OV4ZOC5DFaDTHPIxFec=@vger.kernel.org X-Gm-Message-State: AFuF++n/16yslKKp+t8YvaaRfqzaoT0xrawPuULjCnm6QweuLx6/qy3B vo6W5fP0lquLeAXeKn51XAjKBj2uVm7ykBPGW7FQuqYRQfbhNVg0BaT3 X-Gm-Gg: AYBFou1/MHyAcE44/E++omrJekf0UWW1rabJfeNkQ32Ko/eANgIvld/WAQaDt4bgB4w u88AOmSyTc5/UKrKacKCKauMXxuJLFDfda360+x3GSSOZFB6kIZpR5SJIhC0y+ENfYpmICVpylL 9fzFJm0PTTm42jvho2MWylLVcG7n9ACsslz7eMQxo6RY8Iazzrr1NXYjmtJp6dsT8r+3wUdn4+c YATxjsfjccvo1UtvPTKnup2H3TzKzWw690DyQY+Eu43sbJ8F6MSGMi6N8ox9pBiQBXSjkPODwc5 LEF0B1s/0DB6UZl/MuZQ+48P3fktjwiWQ+hvMBvH0QkdTv2FFbH8xzFbeDcTSPjks8rQaKPCL69 VzolvlP9wtmmdFfRsX/ifW3ixxPOZIhbrPymElwHYHSXdJwMzWkfNteF9OOa2A2WCVBVXwyPVNi yGUPmi+8CovmBakHxwQfDTt8QPGEi0qJiQZC4eOSmdYlNkQEzERSNHAn0zcLMYsblFS1FY9RhgU GpX1XyGzDXhTkyytsmfQ/PNPOCNStDGRNwOgeEf64IOePG7BaKiD3yvM0tNVskWqhDmrANxBzQz 8fdk4Xa8tlpkLQlfuvqW X-Received: by 2002:a05:6820:4b18:b0:6cd:3fdc:a935 with SMTP id 006d021491bc7-6cd3fecc3c1mr3196386eaf.82.1789876746486; Sat, 19 Sep 2026 20:59:06 -0700 (PDT) Received: from [192.168.0.197] (c-98-38-17-99.hsd1.co.comcast.net. [98.38.17.99]) by smtp.googlemail.com with ESMTPSA id 586e51a60fabf-4881f4d7861sm4146915fac.1.2026.09.19.20.59.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Sep 2026 20:59:05 -0700 (PDT) From: Jim Cromie Date: Sat, 19 Sep 2026 21:58:57 -0600 Subject: [PATCH 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: <20260919-ksyms-tune-v1-3-d85c97da1a32@gmail.com> References: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> In-Reply-To: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> To: Andrew Morton Cc: Lorenzo Stoakes , Kees Cook , 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=1789876740; l=6186; i=jim.cromie@gmail.com; s=20260203; h=from:subject:message-id; bh=LumYwkTWkCz84GQ68MaksoLHoAbrKV8RYga/OmBRWWs=; b=oS3hBEoeOTkeYDkz1jG8Ny3J/8fwD+3PwYvYnH6Ac/Mpbw5Lm1Ne4swRspc9e85QONQzuKzMD VLchWBUNSXtDQZUCborGNhn92k+CKydkQQ3Pfws1HSTfIh43VLgd4Ds 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 21adc5b74ec5..3be2b4e74057 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 @@ -91,7 +90,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 @@ -101,16 +100,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 table given an index in the @@ -145,7 +174,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; @@ -154,8 +182,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) @@ -171,8 +198,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--; } @@ -183,8 +209,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