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 char *, unsigned long), } return 0; } +EXPORT_SYMBOL_GPL(kallsyms_on_each_symbol); 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 *, unsigned long), return ret; } +EXPORT_SYMBOL_GPL(kallsyms_on_each_match_symbol); 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 If unsure, say N. +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) += test_rhashtable.o obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_keys.o obj-$(CONFIG_TEST_STATIC_KEYS) += test_static_key_base.o obj-$(CONFIG_TEST_DYNAMIC_DEBUG) += test_dynamic_debug.o +obj-$(CONFIG_TEST_KALLSYMS_PERF) += test_kallsyms_perf.o obj-$(CONFIG_TEST_BITMAP) += 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 = 100000; +module_param(num_iters, uint, 0644); +MODULE_PARM_DESC(num_iters, "Number of iterations per microbenchmark"); + +static const char * const hit_symbols[] = { + "_printk", + "schedule", + "vfs_read", + "do_sys_openat2", + "kernel_clone", + "tcp_v4_rcv", + "kallsyms_lookup_names", + "vm_area_alloc", +}; + +static const char * const miss_symbols[] = { + "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 = data; + + *out = addr; + return 1; +} + +static int count_cb(void *data, const char *name, unsigned long addr) +{ + unsigned long *cnt = data; + + (*cnt)++; + return 0; +} + +static void run_name_lookup_bench(void) +{ + u64 t0, t1, dt_hit, dt_miss; + unsigned long addr = 0; + unsigned int i, nr_hits, nr_misses; + + nr_hits = ARRAY_SIZE(hit_symbols); + nr_misses = ARRAY_SIZE(miss_symbols); + + /* 0. Correctness validation */ + for (i = 0; i < nr_hits; i++) { + const char *sym = hit_symbols[i]; + unsigned long a1 = 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 = 0; i < nr_misses; i++) { + const char *sym = miss_symbols[i]; + unsigned long a1 = 0; + + kallsyms_on_each_match_symbol(match_cb, sym, &a1); + if (a1) + pr_err("CORRECTNESS FAILURE: miss sym '%s' unexpectedly found a1=%lx\n", + sym, a1); + } + + /* 1. Name search: Existing symbols (Hits) */ + t0 = ktime_get_ns(); + for (i = 0; i < num_iters; i++) { + const char *sym = hit_symbols[i % nr_hits]; + + kallsyms_on_each_match_symbol(match_cb, sym, &addr); + OPTIMIZER_HIDE_VAR(addr); + } + t1 = ktime_get_ns(); + dt_hit = t1 - t0; + + /* 2. Name search: Non-existent symbols (Misses - 17 bsearch probes) */ + t0 = ktime_get_ns(); + for (i = 0; i < num_iters; i++) { + const char *sym = miss_symbols[i % nr_misses]; + + kallsyms_on_each_match_symbol(match_cb, sym, &addr); + OPTIMIZER_HIDE_VAR(addr); + } + t1 = ktime_get_ns(); + dt_miss = 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 = 0; + + for (i = 0; i < ARRAY_SIZE(hit_symbols); i++) { + unsigned long addr = 0; + + kallsyms_on_each_match_symbol(match_cb, hit_symbols[i], &addr); + if (addr) + addrs[nr_addrs++] = addr; + } + + if (!nr_addrs) { + pr_warn("Address benchmark skipped: no test addresses resolved\n"); + return; + } + + /* 1. Address-to-name resolution (sprint_symbol) */ + t0 = ktime_get_ns(); + for (i = 0; i < num_iters; i++) { + unsigned long addr = addrs[i % nr_addrs]; + + sprint_symbol(symname, addr); + barrier_data(symname); + } + t1 = ktime_get_ns(); + dt_sprint = t1 - t0; + + /* 2. Address without offset (sprint_symbol_no_offset) */ + t0 = ktime_get_ns(); + for (i = 0; i < num_iters; i++) { + unsigned long addr = addrs[i % nr_addrs]; + + sprint_symbol_no_offset(symname, addr); + barrier_data(symname); + } + t1 = ktime_get_ns(); + dt_bldid = 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 = 0; + int iter = 50; + int i; + + t0 = ktime_get_ns(); + for (i = 0; i < iter; i++) { + total_symbols = 0; + kallsyms_on_each_symbol(count_cb, &total_symbols); + } + t1 = ktime_get_ns(); + dt_walk = 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("==================================================\n"); + pr_info("Starting kallsyms performance benchmark (iters=%u)\n", num_iters); + pr_info("==================================================\n"); + + run_name_lookup_bench(); + run_address_lookup_bench(); + run_table_walk_bench(); + + pr_info("==================================================\n"); + pr_info("kallsyms benchmark complete\n"); + pr_info("==================================================\n"); + + return 0; +} + +static int param_set_trigger(const char *val, const struct kernel_param *kp) +{ + return run_kallsyms_benchmark(); +} + +static const struct kernel_param_ops param_ops_trigger = { + .set = 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"); -- 2.55.0 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) /* - * 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 = &kallsyms_names_offsets[3 * pos]; - /* - * 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]]; - - /* - * 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 = 0; i < (pos & 0xFF); i++) { - len = *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) != 0) - len = ((len & 0x7F) | (name[1] << 7)) + 1; - - name = name + len + 1; - } - - return name - kallsyms_names; + return (p[0] << 16) | (p[1] << 8) | p[2]; } 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); } -static unsigned int get_symbol_seq(int index) +static inline unsigned int get_symbol_seq(int index) { - unsigned int i, seq = 0; - - for (i = 0; i < 3; i++) - seq = (seq << 8) | kallsyms_seqs_of_names[3 * index + i]; + const u8 *p = &kallsyms_seqs_of_names[3 * index]; - return seq; + return (p[0] << 16) | (p[1] << 8) | p[2]; } 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[]; -extern const unsigned int kallsyms_markers[]; +extern const u8 kallsyms_names_offsets[]; extern const u8 kallsyms_seqs_of_names[]; #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[]; }; @@ -393,7 +394,6 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name) { unsigned int i, off; unsigned int best_idx[256]; - unsigned int *markers, markers_cnt; long bin_start; char buf[KSYM_NAME_LEN]; @@ -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"); - /* 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); - output_label("kallsyms_names"); bin_start = bin_pos(out_bin_file); off = 0; for (i = 0; i < table_cnt; i++) { - if ((i & 0xFF) == 0) - markers[i >> 8] = off; table[i]->seq = i; + table[i]->byte_off = off; /* There cannot be any symbol of length zero. */ if (table[i]->len == 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"); - output_label("kallsyms_markers"); - for (i = 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 = bin_pos(out_bin_file); off = 0; @@ -478,6 +464,7 @@ static void write_src(FILE *out_bin_file, const char *out_bin_name) output_label("kallsyms_token_index"); for (i = 0; i < 256; i++) printf("\t.short\t%d\n", best_idx[i]); + printf(".size kallsyms_token_index, . - kallsyms_token_index\n"); printf("\n"); 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"); + output_label("kallsyms_names_offsets"); + for (i = 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 = bin_pos(out_bin_file); @@ -511,6 +508,7 @@ static void write_src(FILE *out_bin_file, const char *out_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"); } -- 2.55.0 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 @@ #include "kallsyms_internal.h" +/* + * Get the compressed symbol length and data pointer. + */ +static inline const u8 *get_symbol_data(unsigned int off, unsigned int *len) +{ + const u8 *p = &kallsyms_names[off]; + unsigned int l = *p++; + + if (unlikely(l & 0x80)) + l = (l & 0x7F) | (*p++ << 7); + *len = l; + + return p; +} + /* * Expand a compressed symbol data into the resulting uncompressed string, * if uncompressed string is too long (>= 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 = 0; + int skipped_first = 0; const char *tptr; - const u8 *data; + unsigned int len; + const u8 *data = get_symbol_data(off, &len); - /* Get the compressed symbol length from the first symbol byte. */ - data = &kallsyms_names[off]; - len = *data; - data++; - off++; - - /* If MSB is 1, it is a "big" symbol, so needs an additional byte. */ - if ((len & 0x80) != 0) { - len = (len & 0x7F) | (*data << 7); - data++; - off++; - } - - /* - * Update the offset to return the offset for the next symbol on - * the compressed stream. - */ - off += len; + off = (data - kallsyms_names) + len; /* * For every byte on the compressed symbol data, copy the table @@ -91,7 +90,7 @@ static unsigned int kallsyms_expand_symbol(unsigned int off, if (maxlen) *result = '\0'; - /* Return to offset to the next symbol. */ + /* Return offset to the next symbol. */ return off; } @@ -101,16 +100,46 @@ static unsigned int kallsyms_expand_symbol(unsigned int 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 = 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 decompressing + * the rest of the symbol name. + */ +static int kallsyms_strcmp_symbol(unsigned int off, const char *name) +{ + int skipped_first = 0; + const char *tptr; + unsigned int len; + const u8 *data = get_symbol_data(off, &len); + + while (len) { + tptr = &kallsyms_token_table[kallsyms_token_index[*data]]; + data++; + len--; + + while (*tptr) { + if (skipped_first) { + int diff = (unsigned char)*name - (unsigned char)*tptr; + + if (diff != 0) + return diff; + name++; + } else { + skipped_first = 1; + } + tptr++; + } + } + + return (unsigned char)*name - '\0'; +} /* * 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]; low = 0; high = kallsyms_num_syms - 1; @@ -154,8 +182,7 @@ static int kallsyms_lookup_names(const char *name, mid = low + (high - low) / 2; seq = get_symbol_seq(mid); off = get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - ret = strcmp(name, namebuf); + ret = kallsyms_strcmp_symbol(off, name); if (ret > 0) low = mid + 1; else if (ret < 0) @@ -171,8 +198,7 @@ static int kallsyms_lookup_names(const char *name, while (low) { seq = get_symbol_seq(low - 1); off = get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - if (strcmp(name, namebuf)) + if (kallsyms_strcmp_symbol(off, name) != 0) break; low--; } @@ -183,8 +209,7 @@ static int kallsyms_lookup_names(const char *name, while (high < kallsyms_num_syms - 1) { seq = get_symbol_seq(high + 1); off = get_symbol_offset(seq); - kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - if (strcmp(name, namebuf)) + if (kallsyms_strcmp_symbol(off, name) != 0) break; high++; } -- 2.55.0