Re: [PATCH v3 next 09/13] kallsyms: Add a kernel parameter to change the kallsyms_markers[] density

From: Samuel Wu

Date: Fri Nov 13 2026 - 20:02:20 EST


On Wed, Nov 11, 2026 at 3:59 AM David Laight
<david.laight.linux@xxxxxxxxx> wrote:
>
> 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 <david.laight.linux@xxxxxxxxx>
> ---
>
> v3: Previously patches 8 and 9
>
> init/Kconfig | 19 +++++++++++++++
> kernel/kallsyms.c | 16 ++++++-------
> kernel/kallsyms_internal.h | 1 +
> scripts/kallsyms.c | 49 ++++++++++++++++++++++++++------------
> scripts/link-vmlinux.sh | 6 +++++
> 5 files changed, 67 insertions(+), 24 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 930ec27a53c0..c27aaabccd1b 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 */
>
> @@ -441,8 +443,8 @@ 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;
> + * every (1 << marker_shift) (typically 64 or 256) symbols */
> + markers_cnt = (table_cnt + 255) >> marker_shift;

Should be (table_cnt + (1 << marker_shift) - 1) >> marker_shift.

Otherwise, looks good to me!

> markers = xmalloc(sizeof(*markers) * markers_cnt);
>
> output_label("kallsyms_names");
> @@ -476,14 +478,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 & ((1u << marker_shift) - 1)) == 0)
> + markers[i >> marker_shift] = 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 & ((1u << marker_shift) - 1)) == 0)
> + markers[i >> marker_shift] = off;
>
> printf("\t/* n:%u */\t.byte\t%u", off, len[0]);
> if (len_len == 2)
> @@ -504,6 +506,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);
> @@ -926,6 +932,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"
> @@ -946,21 +953,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
>