From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=185.226.149.37 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1794911682; b=ZNMF1Am7F1wyC8oq8oCPkXwYN9d+8mNvuORzforBxreH4NuHa4/sHHAHZdK+Q7MgBkEN X7pLhVKKeEVJ1JXW8uEARTDICpWhhSAGuxv/qXIZehgzDow669MaYqgDNYqx+spAUH5HR C48DxRj0xzV0aD9IJ2Ze9exhuH1ipKG9MvJMDOwgVLMjXgoKxd1K0zkSs1NPDeGsUl+Ru xUcVBOg9TxVvqSLnLXv1fhahowFfHsl/cESthXuhdyWU4vmD1hbHc3xB1FS7u/zwDM7yP ZHU8N+pGMlauRAn/A4BgMAYVtFu64ZD4133VTnwAklGnANaJKSnhQ733Di4KevAL1/w== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1794911682; h=DMARC-Filter:Received:DKIM-Signature:Received:Received:From:To:Cc: Subject:Date:Message-Id:X-Mailer:In-Reply-To:References:MIME-Version: Content-Transfer-Encoding; bh=xdvblP+N5Gd4YzHBQJEFvm9RZs4h+QProNeeeXtqUao=; b=dKqMpHRUuIGEqqKVs93aThIESxO5HjA4mFANCVxUGSpGTHJVFPufcD8vSzqoZfPzs8v7 k8ucjFmM5zwDs+1TmcZpitmoAPLop0nSOQb/hBo9Q3hKvEgh9YP27Ix9kh+2h+kdO8Ciz rBSz08WO6FNUjxvJkWhtporqF5Vjxpw8u8+WhOYzJDQ46WuNZsNoFzr2dyRTpyFPBnvgW r5WJTF79cyoYoW3S2mGiAjSGYWCApjkkxUdY1/sw8f38PZQtr2fXp9t/DHa1oSyZRMN/n sWY5bJiNSU2880sKrQVen7r4KVseuhPSvxasJFsi0jnG04J5CPYcG+m8bvCfjFg0wdg== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=fail header.from=gmail.com; spf=pass smtp.mailfrom=runbox.com; dkim=pass header.d=runbox.com header.i=@runbox.com header.a=rsa-sha256 header.s=selector1 header.b=XCrebI3K; arc=none smtp.remote-ip=185.226.149.37 Received: from mailtransmit04.runbox.com (mailtransmit04.runbox.com [185.226.149.37]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (prime256v1) server-signature ECDSA (prime256v1) server-digest SHA256) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7EEC060A381A; Tue, 17 Nov 2026 10:34:41 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.4.2 smtp.subspace.kernel.org 7EEC060A381A Authentication-Results: smtp.subspace.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=runbox.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=runbox.com header.i=@runbox.com header.a=rsa-sha256 header.s=selector1 header.b=XCrebI3K Received: from mailtransmit02.runbox ([10.9.9.162] helo=aibo.runbox.com) by mailtransmit04.runbox.com with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.93) (envelope-from ) id 1xTGW9-001QY8-Ct; Tue, 17 Nov 2026 11:34:25 +0100 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=runbox.com; s=selector1; h=Content-Transfer-Encoding:MIME-Version:References:In-Reply-To :Message-Id:Date:Subject:Cc:To:From; bh=xdvblP+N5Gd4YzHBQJEFvm9RZs4h+QProNeeeXtqUao=; b=XCrebI3KFFZ36YFHpsqt5B/R3M r0mMM0mwwt2seTCSgwB2VIMjWO6yHAGJx6EEMLBsPiFlhAML2dz4imW9IXRXsaJOyQeKdGHkGJrH4 31Fvfb3DNfqLunLR/gcJsIqEB+wT3BwyNlaIHzC/hCE20V0JvIoP0sPa6+2y3ctWLM/1rq6lprhSI I2tY8jSvEU77YxnJZ1d2oZeoP0kG8OSJoOz5WcTz7q0Fr8znl+KbZCxHF+TP3X36GE46W+zIA3Hij T1kNdUVpaslCXehJErn7GFg4ZTzyq256HOwKp1XkBCIb1qbHwuCVdmc4l97RFCefIP6ls5GPH8GLU k8gHY1WA==; Received: from [10.9.9.74] (helo=submission03.runbox) by mailtransmit02.runbox with esmtp (Exim 4.86_2) (envelope-from ) id 1xTGW3-0002FP-WB; Tue, 17 Nov 2026 11:34:20 +0100 Received: by submission03.runbox with esmtpsa [Authenticated ID (1493616)] (TLS1.2:ECDHE_SECP256R1__RSA_PSS_RSAE_SHA256__AES_256_GCM:256) (Exim 4.95) id 1xTGVp-005qHU-8x; Tue, 17 Nov 2026 11:34:05 +0100 From: David Laight To: Petr Mladek , Kees Cook , David Laight , linux-kernel@vger.kernel.org, linux-kbuild@vger.kernel.org, bpf@vger.kernel.org, Jim Cromie , Lorenzo Stoakes Cc: Luis Chamberlain , Andrey Grodzovsky , Steven Rostedt , Andrii Nakryiko , Samuel Wu , linux-kselftest@vger.kernel.org Subject: [PATCH v4 next 09/13] kallsyms: Add a kernel parameter to change the kallsyms_markers[] density Date: Tue, 17 Nov 2026 10:33:48 +0000 Message-Id: <20261117103352.1244657-10-david.laight.linux@gmail.com> X-Mailer: git-send-email 2.39.5 In-Reply-To: <20261117103352.1244657-1-david.laight.linux@gmail.com> References: <20261117103352.1244657-1-david.laight.linux@gmail.com> X-Mailing-List: linux-kbuild@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: 8bit The density is a tradeoff between data size and execution speed. Reducing it from 256 to 64 gives a 35% improvement for name lookups. Change scripts/kallsyms to take the density from a --marker-shift command line parameter so that it can be build specific. Write the value used to the output file to ensure the kernel uses the correct value. The program's default is unchanged at 1 marker per 256 symbols, The kernel config defaults to 1 marker per 64 symbols. This increases the static data by a little less than 1 bit for every two symbols. Signed-off-by: David Laight --- v3: - Previously patches 8 and 9 v4: - Fix rounding of the size of 'markers' array. Allocate oversize, and count the entries added. init/Kconfig | 19 ++++++++++++++ kernel/kallsyms.c | 16 +++++------ kernel/kallsyms_internal.h | 1 + scripts/kallsyms.c | 54 ++++++++++++++++++++++++++------------ scripts/link-vmlinux.sh | 6 +++++ 5 files changed, 70 insertions(+), 26 deletions(-) diff --git a/init/Kconfig b/init/Kconfig index 4013781e0a02..b2db123a51d7 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1908,6 +1908,25 @@ config KALLSYMS symbolic stack backtraces. This increases the size of the kernel somewhat, as all symbols have to be loaded into the kernel image. +config KALLSYMS_MARKER_SHIFT + int "Interval between kallsyms markers (6 => 64, 8 => 256)" + depends on KALLSYMS + default 6 + range 0 24 + help + Set the interval between the kallsyms marker entries as a power of 2. + + This bounds the linear search when locating the name of a symbol + from its index in the array of values (and v.v.). + + Smaller values speed up the search but increase the memory footprint. + Values below 5 (one 32 bit marker every 32 symbols) are unlikely to + make a significant difference because other parts of the code + dominate. + + The default of 6 is a reasonable compromise. It makes looking up a + symbol by name around 35% faster than setting it to 8. + config KALLSYMS_SELFTEST bool "Test the basic functions and performance of kallsyms" depends on KALLSYMS diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index fd42a1a8ed3e..2c4264a3e0c5 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -147,13 +147,11 @@ static int kallsyms_strcmp_symbol(unsigned int off, const char *name) static unsigned int get_symbol_offset(unsigned long pos) { const u8 *name; - int i, len; + int len; - /* - * Use the closest marker we have. We have markers every 256 positions, - * so that should be close enough. - */ - name = &kallsyms_names[kallsyms_markers[pos >> 8]]; + /* Scan from the marker before the requested symbol number */ + name = &kallsyms_names[kallsyms_markers[pos >> kallsyms_marker_shift]]; + pos &= (1 << kallsyms_marker_shift) - 1; /* * Sequentially scan all the symbols up to the point we're searching @@ -161,7 +159,7 @@ static unsigned int get_symbol_offset(unsigned long pos) * so we just need to add the len to the current pointer for every * symbol we wish to skip. */ - for (i = 0; i < (pos & 0xFF); i++) { + while (pos--) { len = *name; /* @@ -185,7 +183,7 @@ static unsigned long get_name_address(unsigned int name_offset) unsigned int low, pos, high; low = 0; - high = ((kallsyms_num_syms - 1) >> 8) + 1; + high = ((kallsyms_num_syms - 1) >> kallsyms_marker_shift) + 1; while (high - low > 1) { pos = low + (high - low) / 2; @@ -196,7 +194,7 @@ static unsigned long get_name_address(unsigned int name_offset) } pos = kallsyms_markers[low]; - for (low <<= 8; pos < name_offset; low++) { + for (low <<= kallsyms_marker_shift; pos < name_offset; low++) { unsigned int len = kallsyms_names[pos]; if (len & 0x80) len += (kallsyms_names[pos + 1] << 7) - 0x7f; diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index 11fb0de92ede..9137870ad00f 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -12,6 +12,7 @@ extern const unsigned int kallsyms_num_syms; extern const char kallsyms_token_table[]; extern const u16 kallsyms_token_index[]; +extern const unsigned int kallsyms_marker_shift; extern const unsigned int kallsyms_markers[]; /* Although constant, size is volatile for better code generation. */ diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 39426f736cb7..f1c952a94e01 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -59,6 +59,8 @@ static unsigned int table_size, table_cnt; static int all_symbols; static int pc_relative; static int verbose; +/* Default to one kallsyms_markers[] entry for each 256 symbols */ +static unsigned long marker_shift = 8; static int big_endian; /* Extracted from the elf file */ @@ -410,7 +412,7 @@ static void write_src(void) { unsigned int i, k, len, off, off_size, table_size; unsigned int best_idx[256]; - unsigned int *markers, markers_cnt; + unsigned int *markers, markers_cnt, markers_mask; unsigned long bin_offset = 0; char buf[1 + KSYM_NAME_LEN]; struct sym_entry *se; @@ -446,9 +448,10 @@ static void write_src(void) stamp("write token table"); /* table of offset markers, that give the offset in the compressed stream - * every 256 symbols */ - markers_cnt = (table_cnt + 255) / 256; - markers = xmalloc(sizeof(*markers) * markers_cnt); + * every (1 << marker_shift) (typically 64 or 256) symbols */ + markers = xmalloc(sizeof(*markers) * ((table_cnt >> marker_shift) + 1)); + markers_cnt = 0; + markers_mask = (1u << marker_shift) - 1; output_label("kallsyms_names"); write_incbin_header("names", &bin_offset); @@ -481,14 +484,14 @@ static void write_src(void) } if (out_bin_file) { - if ((i & 0xFF) == 0) - markers[i >> 8] = big_endian ? htobe32(off) : htole32(off); + if ((i & markers_mask) == 0) + markers[markers_cnt++] = big_endian ? htobe32(off) : htole32(off); fwrite(len, 1, len_len, out_bin_file); fwrite(se->sym, 1, se->len, out_bin_file); } else { - if ((i & 0xFF) == 0) - markers[i >> 8] = off; + if ((i & markers_mask) == 0) + markers[markers_cnt++] = off; printf("\t/* n:%u */\t.byte\t%u", off, len[0]); if (len_len == 2) @@ -509,6 +512,10 @@ static void write_src(void) printf(".size kallsyms_names, . - kallsyms_names\n"); printf("\n"); + output_label("kallsyms_marker_shift"); + printf("\t.long\t%lu\n" , marker_shift); + printf("\n"); + output_label("kallsyms_markers"); if (out_bin_file) { write_incbin_header("markers", &bin_offset); @@ -930,6 +937,7 @@ static void usage(void) "Usage: kallsyms [options] [vmlinux [out.bin]] > out.S\n" " kallsyms --sysmap vmlinux > out.map\n" " --all-symbols Include all local symbols\n" + " --marker-shift=n Interval between makers (6 => 64, 8 => 256)\n" " --pc-relative Output symbol offsets\n" " --sysmap=out.map Text map file\n" " --verbose Extra diagnostic output\n" @@ -950,21 +958,33 @@ int main(int argc, char **argv) while (1) { static const struct option long_options[] = { - {"all-symbols", no_argument, &all_symbols, 1}, - {"pc-relative", no_argument, &pc_relative, 1}, - {"sysmap", optional_argument, NULL, 's'}, - {"verbose", no_argument, &verbose, 1}, + {"all-symbols", no_argument, &all_symbols, 1}, + {"marker-shift", required_argument, NULL, 'm'}, + {"pc-relative", no_argument, &pc_relative, 1}, + {"sysmap", optional_argument, NULL, 's'}, + {"verbose", no_argument, &verbose, 1}, {}, }; - int c = getopt_long(argc, argv, "", long_options, NULL); - - if (c == -1) + switch (getopt_long(argc, argv, "", long_options, NULL)) { + case -1: break; - if (c == 's') + case 0: + continue; + case 'm': + if (!optarg[0]) + continue; + marker_shift = strtoul(optarg, NULL, 10); + if (marker_shift > 24) + usage(); + continue; + case 's': sysmap = optarg ?: ""; - else if (c != 0) + continue; + default: usage(); + } + break; } stamp(NULL); diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh index 44b5a6d78ce5..61cf8f287ebe 100755 --- a/scripts/link-vmlinux.sh +++ b/scripts/link-vmlinux.sh @@ -37,6 +37,10 @@ is_enabled() { grep -q "^$1=y" include/config/auto.conf } +value() { + sed -n "/^$1=/{s///;p;q}" include/config/auto.conf +} + # Nice output in kbuild format # Will be suppressed by "make -s" info() @@ -140,6 +144,8 @@ kallsyms() kallsymopt="${kallsymopt} --pc-relative" fi + kallsymopt="${kallsymopt} --marker-shift=$(value CONFIG_KALLSYMS_MARKER_SHIFT)" + info KSYMS "${2}.S" scripts/kallsyms ${kallsymopt} ${1:+"${1}" "${2}.bin"} > "${2}.S" -- 2.39.5