From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wr2-f12.google.com (mail-wr2-f12.google.com [74.125.225.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 E37F9493651 for ; Mon, 21 Sep 2026 12:00:19 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.225.76 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789992021; cv=none; b=Ys8lpBp5xwdCcQ4OVg2hH8mka2wrdiwhoBrujGMfoopG3T4lyyT5obypKwKXGmAPI6q0Xyxqu63lBVXEzbTBNPsEer/NrbniZKX2mAb84Dt4xlpT38FHeOD7vS9pkx9I08frfI5vCY2urILw+DIs9b3Ow2zrfdBhe/mmMM+Yw8E= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1789992021; c=relaxed/simple; bh=HgscCTdIhqbObj5IdkVWP+i1xbMxe2IH9fAHraLgLyM=; h=From:Date:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=VOSzo7s0guwfEI3qSIf4tXjwB5btCwySNxSTepDnhMKAB2QaGeKMhC5zR3rxP+gjBEp1lvDmy9CmKctfM3ccw1fvLBOpy75uZ6aKG5Sq/u/Re43VzZvbw3wC0ikhUvAq+xQRDJJFupuCQyU/egQLTpK1FnaNIwCkIEv3qV3suk0= 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=aCLcEXhc; arc=none smtp.client-ip=74.125.225.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="aCLcEXhc" Received: by mail-wr2-f12.google.com with SMTP id ffacd0b85a97d-485984ebf5cso2270727f8f.0 for ; Mon, 21 Sep 2026 05:00:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1789992018; x=1790596818; darn=vger.kernel.org; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:date:from:from:to:cc:subject :date:message-id:reply-to:content-type; bh=QA57d0MWfONjf/OW7F8GGaeRDnISGbQSvosg5yrwN8E=; b=aCLcEXhcAcbruGw8fngH97iYAZg4T/nAdF6IhqfxlkoUZFCgLUMZL6FZL2CQDxD3p5 +d1s0Rt0Q4+SujN76o8o74w1oCyA7y1WFwY77LkyB417b4Y+lpTMBNBnXs5LWveJTP+U Yb4r93f3aJHuqi8xtHFcNmzcMfX00ieRXSHaCg5aBTO+Hzy1HCFpU+P0NPLYZ/CBuG13 tfdVQX+Zy52TI36f20hVDPctyfHG7NoDwU/1A/AbuNniPzHPEqguKCvbKEb4HPElzWwo F9uQ7PBfe6qI0xaWFD74tAutuJ00cbXyKqTqwZcziq9603v6nzthLOsWmfQ4LBz1riDw PgOg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20260707; t=1789992018; x=1790596818; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=QA57d0MWfONjf/OW7F8GGaeRDnISGbQSvosg5yrwN8E=; b=QF0kCnNv0221ztEWg3B1OjU/DtgI+awlJAfykuxjyKzpC68btWyTFTHTSh6d9XlX9D WCnHeck3+TkorhJ0EvlFMtwQT532wyHRMWgKwWyF9GvJ1FGPjAanQbdxYcCyv310xH7e vEkQhvEqOGuQndCYB8juK0nW96EOaEaWzW2Z4dnjjGc2oduNxx7ujcHionX+pt6cjHKB C1bVhjXIBMF4EuO35D4xxBXMFAcnyTip1cGFDmGfEFizlNV4AkC+iH7eWF8wiZLDQIRH 72sgM6iq9orDgB1OeYYnoMOl13HuENO5/tviOG2sky1LiKaK32JX3PbUx/tc+h8w0Cdm Q1Nw== X-Forwarded-Encrypted: i=1; AKwUvBzaxqqwLNIsGFiDA5TBZS9vyf2L68BFDelShy4PRMKQtgrwYlSAIPI0Cgh//sliCqh4x8eHxb35sEhZ7H4=@vger.kernel.org X-Gm-Message-State: AFuF++kqkMBrM7XJf5C9q+jRDERNo5he/27rCUn7DRDKGwkuqKFlVjff LkDCB6ViBqSMgZIz6vtCIJuaRW89HUHNdArnfgd877bKO7cnPp1vo8Zl X-Gm-Gg: AYBFou0IPb5uZBN0NOSPC6ytqCyNoDh126lsgsNXWgBEd6u9iFQM0TzKMbtIJ9zumn9 6c0PCbRAS7BSTmnr2b88zkcG4gSiCdRl7tRFG3/AHnPfjjxRoa6L46Ri8FmTL8zNTZFqZR3mnX2 oMR0Kh6Pv3X0XeMjJl47GoQBgey1hL7Jdqrq4FsJ04HfeQ7PEnQrSw6CTzQCZNSZVtsQGwPUyg1 s4HLTNnU6Zdli7qisgNWWLLv5wCfxef4YHq3QHL5JI19KSt1Rui66BgpIFtR/fEas7kP7q70X6y hABsv8PRQCOIhkCVzZJ7CQN2rMwyVuv9XeJoN5y+jEkU910KdtLG2schjjFglP3PZJ9TwzrmXRs xphPGc4okE1dAqh4I/karB8jv5SxANZ4gLs76fhpVGRsDJrzLjDM7WR7z1exb8z+fp085epeQKd O6lFtyh2jjWX8eex39bnbLSflBjK+lCkuMLYPsF1jajch23ltkSZZfhZ9tuq0WL5+elo5S X-Received: by 2002:a05:6000:18a9:b0:486:fe41:804d with SMTP id ffacd0b85a97d-4871e3b6a68mr15005637f8f.47.1789992018016; Mon, 21 Sep 2026 05:00:18 -0700 (PDT) Received: from krava ([176.74.159.170]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-487245a58a0sm20252895f8f.36.2026.09.21.05.00.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 21 Sep 2026 05:00:17 -0700 (PDT) From: Jiri Olsa X-Google-Original-From: Jiri Olsa Date: Mon, 21 Sep 2026 14:00:15 +0200 To: Jim Cromie Cc: Andrew Morton , Lorenzo Stoakes , Kees Cook , Masahiro Yamada , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, bpf@vger.kernel.org Subject: Re: [PATCH 0/3] kallsyms: Accelerate symbol name lookups by ~19x Message-ID: References: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> Precedence: bulk X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260919-ksyms-tune-v1-0-d85c97da1a32@gmail.com> On Sat, Sep 19, 2026 at 09:58:54PM -0600, Jim Cromie wrote: > kallsyms_lookup_names() resolves symbol names to addresses using a > 17-step binary search over kallsyms_names[] (~191k symbols on x86_64). > At each step of the search, two bottlenecks compound to create > substantial lookup latency: > > 0. Marker scanning: get_symbol_offset() scans sequentially from the > nearest 256-symbol marker, decoding an average of ~128 ULEB128 record > headers per probe (~2,176 header decodes per lookup). > > 1. Redundant string expansion: kallsyms_expand_symbol() decompresses > the entire candidate symbol into a 512-byte stack buffer (namebuf) > before calling strcmp(), even though ~94% of binary search probes > mismatch on the first 1-2 characters. > > Together, these bottlenecks impose a ~4.3 us latency penalty per hit and > ~3.8 us per miss. > > This 3-patch series eliminates both overheads while keeping the symbol > table strictly in sequential address order: > > 0. Patch 1 adds lib/test_kallsyms_perf.ko, a microbenchmark module to > measure name hits, name misses, sprint_symbol(), and table iteration > latency, with built-in correctness validation and a sysfs trigger. > > 1. Patch 2 introduces kallsyms_names_offsets, a build-time 3-byte direct > index into kallsyms_names[]. This turns get_symbol_offset() into an > O(1) table lookup, dropping the ~2,176 marker hops per lookup and > eliminating the legacy kallsyms_markers[] table. > > 2. Patch 3 introduces kallsyms_strcmp_symbol() to compare ASCII queries > against compressed tokens incrementally on the fly, bailing out on > the first mismatched character without expanding subsequent tokens. > This drops the 512-byte namebuf buffer from the kernel stack. > > Context & Lineage: > > This series was originally developed and benchmarked on mainline (v7.3-rc3). > To ensure compatibility with Lorenzo Stoakes' kbuild speedup series (v3), > it has been rebased on top of commit c1c0fd58e281 ("kbuild: compress the > kernel with pigz if available"). > > Rebasing required only a trivial mechanical fix in scripts/kallsyms.c to > align Patch 2 ("Add 3-byte index into compressed symbols") with Lorenzo's > direct binary streaming path (write_incbin). > > Glomming onto Lorenzo's build-time acceleration push extends the speedup > theme into runtime: his series speeds up the compile and link, and this > series speeds up runtime symbol lookups by ~18x. > > Live Microbenchmark Results (via test_kallsyms_perf, 100k iters): > > Metric Baseline Patched Speedup > ----------------------------------------------------------------- > Name Search Hit 4,370 ns 247 ns 17.7x > Name Search Miss 3,860 ns 195 ns 19.8x > sprint_symbol 440 ns 441 ns parity > sprint_symbol_no_offset 315 ns 307 ns parity > Table Full Walk 14,500 us 14,437 us parity > > Address-to-name resolution (sprint_symbol) and sequential table walks > (/proc/kallsyms) remain completely unaffected, maintaining full L1/L2 > hardware prefetching. > > Hardware PMU Event Counters (perf stat via sysfs run_test trigger): > > $ perf stat -e cycles,instructions,branches,branch-misses,cache-misses \ > sh -c 'echo 1 > /sys/module/test_kallsyms_perf/parameters/run_test' > > Counter Baseline Patched Delta > ------------------------------------------------------------------------ > Wall-clock elapsed 1.746 s 0.852 s -51.2% > CPU cycles 7,320,048,030 3,628,523,081 -50.4% > Instructions 9,943,172,792 5,034,260,318 -49.4% > Branches 2,391,663,821 1,173,258,010 -51.0% > Branch-misses 117,241,513 99,805,938 -14.9% > Cache-misses 84,996,149 731,025 -99.1% > > Dropping marker scans and avoiding redundant string expansions cuts > 4.91 billion instructions (-49.4%) and drops 84.2 million cache misses > (-99.1%) across the test workload. > > Memory footprint: +573 KiB .rodata for kallsyms_names_offsets (191k > symbols * 3 bytes on x86_64 defconfig), minus ~2 KiB from dropping > kallsyms_markers[]. > > Signed-off-by: Jim Cromie nice, fyi I checked on tracing_multi benchmark and got bit of speedup as well before: serial_test_tracing_multi_bench_attach: found 64021 functions serial_test_tracing_multi_bench_attach: attached in 2.884s serial_test_tracing_multi_bench_attach: detached in 1.149s 16,515,655,329 cycles:k 41,935,382,635 instructions:k after: serial_test_tracing_multi_bench_attach: found 64021 functions serial_test_tracing_multi_bench_attach: attached in 2.633s serial_test_tracing_multi_bench_attach: detached in 1.159s #558 tracing_multi_bench_attach:OK 15,880,929,751 cycles:k 40,444,002,354 instructions:k we call kallsyms_lookup_name for each attached symbol jirka > --- > Jim Cromie (3): > kallsyms: Add test_kallsyms_perf module to benchmark lookup latency > kallsyms: Add 3-byte index into compressed symbols to replace marker scans > kallsyms: Match compressed tokens on the fly during binary search > > kernel/kallsyms.c | 138 ++++++++++++++------------- > kernel/kallsyms_internal.h | 2 +- > lib/Kconfig.debug | 10 ++ > lib/Makefile | 1 + > lib/test_kallsyms_perf.c | 228 +++++++++++++++++++++++++++++++++++++++++++++ > scripts/kallsyms.c | 30 +++--- > 6 files changed, 322 insertions(+), 87 deletions(-) > --- > base-commit: c1c0fd58e28143fd10071f51f4dcc8249a331513 > change-id: 20260919-ksyms-tune-e22a42d8a31a > > Best regards, > -- > Jim Cromie > >