From 60443c88f3a89fd303a9e8c0e84895910675c316 Mon Sep 17 00:00:00 2001 From: Zhen Lei Date: Wed, 2 Nov 2022 16:49:14 +0800 Subject: kallsyms: Improve the performance of kallsyms_lookup_name() Currently, to search for a symbol, we need to expand the symbols in 'kallsyms_names' one by one, and then use the expanded string for comparison. It's O(n). If we sort names in ascending order like addresses, we can also use binary search. It's O(log(n)). In order not to change the implementation of "/proc/kallsyms", the table kallsyms_names[] is still stored in a one-to-one correspondence with the address in ascending order. Add array kallsyms_seqs_of_names[], it's indexed by the sequence number of the sorted names, and the corresponding content is the sequence number of the sorted addresses. For example: Assume that the index of NameX in array kallsyms_seqs_of_names[] is 'i', the content of kallsyms_seqs_of_names[i] is 'k', then the corresponding address of NameX is kallsyms_addresses[k]. The offset in kallsyms_names[] is get_symbol_offset(k). Note that the memory usage will increase by (4 * kallsyms_num_syms) bytes, the next two patches will reduce (1 * kallsyms_num_syms) bytes and properly handle the case CONFIG_LTO_CLANG=y. Performance test results: (x86) Before: min=234, max=10364402, avg=5206926 min=267, max=11168517, avg=5207587 After: min=1016, max=90894, avg=7272 min=1014, max=93470, avg=7293 The average lookup performance of kallsyms_lookup_name() improved 715x. Signed-off-by: Zhen Lei Signed-off-by: Luis Chamberlain --- scripts/kallsyms.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) (limited to 'scripts') diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index ab105bdde4ef..df2d93fb0e8d 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -49,6 +49,7 @@ _Static_assert( struct sym_entry { unsigned long long addr; unsigned int len; + unsigned int seq; unsigned int start_pos; unsigned int percpu_absolute; unsigned char sym[]; @@ -410,6 +411,35 @@ static int symbol_absolute(const struct sym_entry *s) return s->percpu_absolute; } +static int compare_names(const void *a, const void *b) +{ + int ret; + char sa_namebuf[KSYM_NAME_LEN]; + char sb_namebuf[KSYM_NAME_LEN]; + const struct sym_entry *sa = *(const struct sym_entry **)a; + const struct sym_entry *sb = *(const struct sym_entry **)b; + + expand_symbol(sa->sym, sa->len, sa_namebuf); + expand_symbol(sb->sym, sb->len, sb_namebuf); + ret = strcmp(&sa_namebuf[1], &sb_namebuf[1]); + if (!ret) { + if (sa->addr > sb->addr) + return 1; + else if (sa->addr < sb->addr) + return -1; + + /* keep old order */ + return (int)(sa->seq - sb->seq); + } + + return ret; +} + +static void sort_symbols_by_name(void) +{ + qsort(table, table_cnt, sizeof(table[0]), compare_names); +} + static void write_src(void) { unsigned int i, k, off; @@ -495,6 +525,7 @@ static void write_src(void) for (i = 0; i < table_cnt; i++) { if ((i & 0xFF) == 0) markers[i >> 8] = off; + table[i]->seq = i; /* There cannot be any symbol of length zero. */ if (table[i]->len == 0) { @@ -535,6 +566,12 @@ static void write_src(void) free(markers); + sort_symbols_by_name(); + output_label("kallsyms_seqs_of_names"); + for (i = 0; i < table_cnt; i++) + printf("\t.long\t%u\n", table[i]->seq); + printf("\n"); + output_label("kallsyms_token_table"); off = 0; for (i = 0; i < 256; i++) { -- cgit v1.2.3-58-ga151