From fcdf7197cf23ef452c30f376d31d73bdf7946de8 Mon Sep 17 00:00:00 2001 From: Zhen Lei Date: Wed, 2 Nov 2022 16:49:13 +0800 Subject: scripts/kallsyms: rename build_initial_tok_table() Except for the function build_initial_tok_table(), no token abbreviation is used elsewhere. $ cat scripts/kallsyms.c | grep tok | wc -l 33 $ cat scripts/kallsyms.c | grep token | wc -l 31 Here, it would be clearer to use the full name. Signed-off-by: Zhen Lei Reviewed-by: Petr Mladek Signed-off-by: Luis Chamberlain --- scripts/kallsyms.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'scripts') diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 03fa07ad45d9..ab105bdde4ef 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -573,7 +573,7 @@ static void forget_symbol(const unsigned char *symbol, int len) } /* do the initial token count */ -static void build_initial_tok_table(void) +static void build_initial_token_table(void) { unsigned int i; @@ -698,7 +698,7 @@ static void insert_real_symbols_in_table(void) static void optimize_token_table(void) { - build_initial_tok_table(); + build_initial_token_table(); insert_real_symbols_in_table(); -- cgit v1.2.3 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 --- kernel/kallsyms.c | 86 ++++++++++++++++++++++++++++++++++++++++------ kernel/kallsyms_internal.h | 1 + scripts/kallsyms.c | 37 ++++++++++++++++++++ 3 files changed, 113 insertions(+), 11 deletions(-) (limited to 'scripts') diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 60c20f301a6b..ba351dfa109b 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -187,26 +187,90 @@ static bool cleanup_symbol_name(char *s) return false; } +static int compare_symbol_name(const char *name, char *namebuf) +{ + int ret; + + ret = strcmp(name, namebuf); + if (!ret) + return ret; + + if (cleanup_symbol_name(namebuf) && !strcmp(name, namebuf)) + return 0; + + return ret; +} + +static int kallsyms_lookup_names(const char *name, + unsigned int *start, + unsigned int *end) +{ + int ret; + int low, mid, high; + unsigned int seq, off; + char namebuf[KSYM_NAME_LEN]; + + low = 0; + high = kallsyms_num_syms - 1; + + while (low <= high) { + mid = low + (high - low) / 2; + seq = kallsyms_seqs_of_names[mid]; + off = get_symbol_offset(seq); + kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); + ret = compare_symbol_name(name, namebuf); + if (ret > 0) + low = mid + 1; + else if (ret < 0) + high = mid - 1; + else + break; + } + + if (low > high) + return -ESRCH; + + low = mid; + while (low) { + seq = kallsyms_seqs_of_names[low - 1]; + off = get_symbol_offset(seq); + kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); + if (compare_symbol_name(name, namebuf)) + break; + low--; + } + *start = low; + + if (end) { + high = mid; + while (high < kallsyms_num_syms - 1) { + seq = kallsyms_seqs_of_names[high + 1]; + off = get_symbol_offset(seq); + kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); + if (compare_symbol_name(name, namebuf)) + break; + high++; + } + *end = high; + } + + return 0; +} + /* Lookup the address for this symbol. Returns 0 if not found. */ unsigned long kallsyms_lookup_name(const char *name) { - char namebuf[KSYM_NAME_LEN]; - unsigned long i; - unsigned int off; + int ret; + unsigned int i; /* Skip the search for empty string. */ if (!*name) return 0; - for (i = 0, off = 0; i < kallsyms_num_syms; i++) { - off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - - if (strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); + ret = kallsyms_lookup_names(name, &i, NULL); + if (!ret) + return kallsyms_sym_address(kallsyms_seqs_of_names[i]); - if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); - } return module_kallsyms_lookup_name(name); } diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index 2d0c6f2f0243..a04b7a5cb1e3 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -26,5 +26,6 @@ extern const char kallsyms_token_table[] __weak; extern const u16 kallsyms_token_index[] __weak; extern const unsigned int kallsyms_markers[] __weak; +extern const unsigned int kallsyms_seqs_of_names[] __weak; #endif // LINUX_KALLSYMS_INTERNAL_H_ 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 From 010a0aad39fccceba4a07d30d163158a39c704f3 Mon Sep 17 00:00:00 2001 From: Zhen Lei Date: Wed, 2 Nov 2022 16:49:15 +0800 Subject: kallsyms: Correctly sequence symbols when CONFIG_LTO_CLANG=y LLVM appends various suffixes for local functions and variables, suffixes observed: - foo.llvm.[0-9a-f]+ - foo.[0-9a-f]+ Therefore, when CONFIG_LTO_CLANG=y, kallsyms_lookup_name() needs to truncate the suffix of the symbol name before comparing the local function or variable name. Old implementation code: - if (strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); - if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); The preceding process is traversed by address from low to high. That is, for those with the same name after the suffix is removed, the one with the smallest address is returned first. Therefore, when sorting in the tool, if the raw names are the same, they should be sorted by address in ascending order. ASCII[.] = 2e ASCII[0-9] = 30,39 ASCII[A-Z] = 41,5a ASCII[_] = 5f ASCII[a-z] = 61,7a According to the preceding ASCII code values, the following sorting result is strictly followed. --------------------------------- | main-key | sub-key | |---------------------------------| | | addr_lowest | | | ... | | . | ... | | | addr_highest | |---------------------------------| | ? | | //? is [_A-Za-z0-9] --------------------------------- Signed-off-by: Zhen Lei Signed-off-by: Luis Chamberlain --- scripts/kallsyms.c | 36 ++++++++++++++++++++++++++++++++++-- scripts/link-vmlinux.sh | 4 ++++ 2 files changed, 38 insertions(+), 2 deletions(-) (limited to 'scripts') diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index df2d93fb0e8d..07ecf7e5c49f 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -78,6 +78,7 @@ static unsigned int table_size, table_cnt; static int all_symbols; static int absolute_percpu; static int base_relative; +static int lto_clang; static int token_profit[0x10000]; @@ -89,7 +90,7 @@ static unsigned char best_table_len[256]; static void usage(void) { fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] " - "[--base-relative] in.map > out.S\n"); + "[--base-relative] [--lto-clang] in.map > out.S\n"); exit(1); } @@ -411,6 +412,34 @@ static int symbol_absolute(const struct sym_entry *s) return s->percpu_absolute; } +static char * s_name(char *buf) +{ + /* Skip the symbol type */ + return buf + 1; +} + +static void cleanup_symbol_name(char *s) +{ + char *p; + + if (!lto_clang) + return; + + /* + * ASCII[.] = 2e + * ASCII[0-9] = 30,39 + * ASCII[A-Z] = 41,5a + * ASCII[_] = 5f + * ASCII[a-z] = 61,7a + * + * As above, replacing '.' with '\0' does not affect the main sorting, + * but it helps us with subsorting. + */ + p = strchr(s, '.'); + if (p) + *p = '\0'; +} + static int compare_names(const void *a, const void *b) { int ret; @@ -421,7 +450,9 @@ static int compare_names(const void *a, const void *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]); + cleanup_symbol_name(s_name(sa_namebuf)); + cleanup_symbol_name(s_name(sb_namebuf)); + ret = strcmp(s_name(sa_namebuf), s_name(sb_namebuf)); if (!ret) { if (sa->addr > sb->addr) return 1; @@ -855,6 +886,7 @@ int main(int argc, char **argv) {"all-symbols", no_argument, &all_symbols, 1}, {"absolute-percpu", no_argument, &absolute_percpu, 1}, {"base-relative", no_argument, &base_relative, 1}, + {"lto-clang", no_argument, <o_clang, 1}, {}, }; diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh index 918470d768e9..32e573943cf0 100755 --- a/scripts/link-vmlinux.sh +++ b/scripts/link-vmlinux.sh @@ -156,6 +156,10 @@ kallsyms() kallsymopt="${kallsymopt} --base-relative" fi + if is_enabled CONFIG_LTO_CLANG; then + kallsymopt="${kallsymopt} --lto-clang" + fi + info KSYMS ${2} scripts/kallsyms ${kallsymopt} ${1} > ${2} } -- cgit v1.2.3 From 19bd8981dc2ee35fdc81ab1b0104b607c917d470 Mon Sep 17 00:00:00 2001 From: Zhen Lei Date: Wed, 2 Nov 2022 16:49:16 +0800 Subject: kallsyms: Reduce the memory occupied by kallsyms_seqs_of_names[] kallsyms_seqs_of_names[] records the symbol index sorted by address, the maximum value in kallsyms_seqs_of_names[] is the number of symbols. And 2^24 = 16777216, which means that three bytes are enough to store the index. This can help us save (1 * kallsyms_num_syms) bytes of memory. Signed-off-by: Zhen Lei Signed-off-by: Luis Chamberlain --- kernel/kallsyms.c | 18 ++++++++++++++---- kernel/kallsyms_internal.h | 2 +- scripts/kallsyms.c | 5 ++++- 3 files changed, 19 insertions(+), 6 deletions(-) (limited to 'scripts') diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index ba351dfa109b..48f36fd7e10b 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -201,6 +201,16 @@ static int compare_symbol_name(const char *name, char *namebuf) return ret; } +static 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]; + + return seq; +} + static int kallsyms_lookup_names(const char *name, unsigned int *start, unsigned int *end) @@ -215,7 +225,7 @@ static int kallsyms_lookup_names(const char *name, while (low <= high) { mid = low + (high - low) / 2; - seq = kallsyms_seqs_of_names[mid]; + seq = get_symbol_seq(mid); off = get_symbol_offset(seq); kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); ret = compare_symbol_name(name, namebuf); @@ -232,7 +242,7 @@ static int kallsyms_lookup_names(const char *name, low = mid; while (low) { - seq = kallsyms_seqs_of_names[low - 1]; + seq = get_symbol_seq(low - 1); off = get_symbol_offset(seq); kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); if (compare_symbol_name(name, namebuf)) @@ -244,7 +254,7 @@ static int kallsyms_lookup_names(const char *name, if (end) { high = mid; while (high < kallsyms_num_syms - 1) { - seq = kallsyms_seqs_of_names[high + 1]; + seq = get_symbol_seq(high + 1); off = get_symbol_offset(seq); kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); if (compare_symbol_name(name, namebuf)) @@ -269,7 +279,7 @@ unsigned long kallsyms_lookup_name(const char *name) ret = kallsyms_lookup_names(name, &i, NULL); if (!ret) - return kallsyms_sym_address(kallsyms_seqs_of_names[i]); + return kallsyms_sym_address(get_symbol_seq(i)); return module_kallsyms_lookup_name(name); } diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index a04b7a5cb1e3..27fabdcc40f5 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -26,6 +26,6 @@ extern const char kallsyms_token_table[] __weak; extern const u16 kallsyms_token_index[] __weak; extern const unsigned int kallsyms_markers[] __weak; -extern const unsigned int kallsyms_seqs_of_names[] __weak; +extern const u8 kallsyms_seqs_of_names[] __weak; #endif // LINUX_KALLSYMS_INTERNAL_H_ diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 07ecf7e5c49f..04e04fbd9625 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -600,7 +600,10 @@ static void write_src(void) 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("\t.byte 0x%02x, 0x%02x, 0x%02x\n", + (unsigned char)(table[i]->seq >> 16), + (unsigned char)(table[i]->seq >> 8), + (unsigned char)(table[i]->seq >> 0)); printf("\n"); output_label("kallsyms_token_table"); -- cgit v1.2.3