[Crash-utility] [PATCH v4 1/4] Improve the performance of symbol searching for kernel modules

Currently the sequence for symbol_search to search a symbol is: 1) kernel symname hash table, 2) iterate all kernel symbols, 3) iterate all kernel modules and their symbols. In the worst case, if a non-exist symbol been searched, all 3 stages will be went through. The time consuming status for each stage is like: stage 1 stage 2 stage 3 0.007000(ms) 0.593000(ms) 2.421000(ms) stage 3 takes too much time when comparing to stage 1. This patch introduces a symname hash table for kernel modules, to improve the performance of symbol searching. Functions symbol_search and symbol_exists are fundamental and widely used by other crash functions, thus the benefit of performance improvement can get accumulated. For example, "ps -m" and "irq" commands, which call the functions many times, will become faster with the patch. Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; Reviewed-by: Philipp Rudo <prudo(a)redhat.com&gt; --- defs.h | 1 + kernel.c | 1 + symbols.c | 176 ++++++++++++++++++++++++++++-------------------------- 3 files changed, 92 insertions(+), 86 deletions(-) diff --git a/defs.h b/defs.h index eb1c71b..c10ebff 100644 --- a/defs.h +++ b/defs.h @@ -2751,6 +2751,7 @@ struct symbol_table_data { double val_hash_searches; double val_hash_iterations; struct syment *symname_hash[SYMNAME_HASH]; + struct syment *mod_symname_hash[SYMNAME_HASH]; struct symbol_namespace kernel_namespace; struct syment *ext_module_symtable; struct syment *ext_module_symend; diff --git a/kernel.c b/kernel.c index b2c8a0c..307eeee 100644 --- a/kernel.c +++ b/kernel.c @@ -4663,6 +4663,7 @@ reinit_modules(void) kt->mods_installed = 0; clear_text_value_cache(); + memset(st->mod_symname_hash, 0, sizeof(st->mod_symname_hash)); module_init(); } diff --git a/symbols.c b/symbols.c index bf6d94d..7ab47f2 100644 --- a/symbols.c +++ b/symbols.c @@ -64,8 +64,10 @@ static int namespace_ctl(int, struct symbol_namespace *, void *, void *); static void symval_hash_init(void); static struct syment *symval_hash_search(ulong); static void symname_hash_init(void); -static void symname_hash_install(struct syment *); -static struct syment *symname_hash_search(char *); +static void symname_hash_install(struct syment *[], struct syment *); +static void symname_hash_remove(struct syment *[], struct syment *); +static struct syment *symname_hash_search(struct syment *[], char *, + int (*)(struct syment *, char *)); static void gnu_qsort(bfd *, void *, long, unsigned int, asymbol *, asymbol *); static int check_gnu_debuglink(bfd *); static int separate_debug_file_exists(const char *, unsigned long, int *); @@ -1119,7 +1121,7 @@ symname_hash_init(void) struct syment *sp; for (sp = st->symtable; sp < st->symend; sp++) - symname_hash_install(sp); + symname_hash_install(st->symname_hash, sp); if ((sp = symbol_search("__per_cpu_start"))) st->__per_cpu_start = sp->value; @@ -1127,21 +1129,42 @@ symname_hash_init(void) st->__per_cpu_end = sp->value; } +static void +mod_symtable_hash_install_range(struct syment *from, struct syment *to) +{ + struct syment *sp; + + for (sp = from; sp <= to; sp++) + symname_hash_install(st->mod_symname_hash, sp); +} + +static void +mod_symtable_hash_remove_range(struct syment *from, struct syment *to) +{ + struct syment *sp; + + for (sp = from; sp <= to; sp++) + symname_hash_remove(st->mod_symname_hash, sp); +} + /* * Install a single static kernel symbol into the symname_hash. */ static void -symname_hash_install(struct syment *spn) +symname_hash_install(struct syment *table[], struct syment *spn) { struct syment *sp; int index; + if (!spn) + return; + index = SYMNAME_HASH_INDEX(spn->name); spn->cnt = 1; - if ((sp = st->symname_hash[index]) == NULL) - st->symname_hash[index] = spn; - else { + if ((sp = table[index]) == NULL) { + table[index] = spn; + } else { while (sp) { if (STREQ(sp->name, spn->name)) { sp->cnt++; @@ -1157,17 +1180,47 @@ symname_hash_install(struct syment *spn) } } +static void +symname_hash_remove(struct syment *table[], struct syment *spn) +{ + struct syment *sp; + int index; + + if (!spn) + return; + + index = SYMNAME_HASH_INDEX(spn->name); + + if (table[index] == spn) + table[index] = spn->name_hash_next; + + for (sp = table[index]; sp; sp = sp->name_hash_next) { + if (STREQ(sp->name, spn->name)) + sp->cnt--; + if (sp->name_hash_next == spn) + sp->name_hash_next = spn->name_hash_next; + } +} + /* * Static kernel symbol value search */ static struct syment * -symname_hash_search(char *name) +symname_hash_search(struct syment *table[], char *name, + int (*skip_condition)(struct syment *, char *)) { struct syment *sp; + int index; - sp = st->symname_hash[SYMNAME_HASH_INDEX(name)]; + index = SYMNAME_HASH_INDEX(name); + sp = table[index]; while (sp) { + if (skip_condition && skip_condition(sp, name)) { + sp = sp->name_hash_next; + continue; + } + if (STREQ(sp->name, name)) return sp; sp = sp->name_hash_next; @@ -1595,6 +1648,7 @@ store_module_symbols_v1(ulong total, int mods_installed) lm->mod_symend = sp; } } + mod_symtable_hash_install_range(lm->mod_symtable, lm->mod_symend); } st->flags |= MODULE_SYMS; @@ -2075,6 +2129,8 @@ store_module_symbols_v2(ulong total, int mods_installed) lm->mod_init_symend = sp; } } + mod_symtable_hash_install_range(lm->mod_symtable, lm->mod_symend); + mod_symtable_hash_install_range(lm->mod_init_symtable, lm->mod_init_symend); } st->flags |= MODULE_SYMS; @@ -4482,6 +4538,17 @@ symbol_query(char *s, char *print_pad, struct syment **spp) return(cnt); } +static int +skip_symbols(struct syment *sp, char *s) +{ + int pseudos, skip = 0; + + pseudos = (strstr(s, "_MODULE_START_") || strstr(s, "_MODULE_END_") || + strstr(s, "_MODULE_INIT_START_") || strstr(s, "_MODULE_INIT_END_")); + if (!pseudos && MODULE_PSEUDO_SYMBOL(sp)) + skip = 1; + return skip; +} /* * Return the syment of a symbol. @@ -4489,58 +4556,16 @@ symbol_query(char *s, char *print_pad, struct syment **spp) struct syment * symbol_search(char *s) { - int i; - struct syment *sp_hashed, *sp, *sp_end; - struct load_module *lm; - int pseudos, search_init; + struct syment *sp_hashed, *sp; - sp_hashed = symname_hash_search(s); + sp_hashed = symname_hash_search(st->symname_hash, s, NULL); for (sp = sp_hashed ? sp_hashed : st->symtable; sp < st->symend; sp++) { if (STREQ(s, sp->name)) return(sp); } - pseudos = (strstr(s, "_MODULE_START_") || strstr(s, "_MODULE_END_")); - search_init = FALSE; - - for (i = 0; i < st->mods_installed; i++) { - lm = &st->load_modules[i]; - if (lm->mod_flags & MOD_INIT) - search_init = TRUE; - sp = lm->mod_symtable; - sp_end = lm->mod_symend; - - for ( ; sp <= sp_end; sp++) { - if (!pseudos && MODULE_PSEUDO_SYMBOL(sp)) - continue; - if (STREQ(s, sp->name)) - return(sp); - } - } - - if (!search_init) - return((struct syment *)NULL); - - pseudos = (strstr(s, "_MODULE_INIT_START_") || strstr(s, "_MODULE_INIT_END_")); - - for (i = 0; i < st->mods_installed; i++) { - lm = &st->load_modules[i]; - if (!lm->mod_init_symtable) - continue; - sp = lm->mod_init_symtable; - sp_end = lm->mod_init_symend; - - for ( ; sp < sp_end; sp++) { - if (!pseudos && MODULE_PSEUDO_SYMBOL(sp)) - continue; - - if (STREQ(s, sp->name)) - return(sp); - } - } - - return((struct syment *)NULL); + return symname_hash_search(st->mod_symname_hash, s, skip_symbols); } /* @@ -5432,33 +5457,11 @@ value_symbol(ulong value) int symbol_exists(char *symbol) { - int i; - struct syment *sp, *sp_end; - struct load_module *lm; - - if ((sp = symname_hash_search(symbol))) + if (symname_hash_search(st->symname_hash, symbol, NULL)) return TRUE; - for (i = 0; i < st->mods_installed; i++) { - lm = &st->load_modules[i]; - sp = lm->mod_symtable; - sp_end = lm->mod_symend; - - for ( ; sp < sp_end; sp++) { - if (STREQ(symbol, sp->name)) - return(TRUE); - } - - if (lm->mod_init_symtable) { - sp = lm->mod_init_symtable; - sp_end = lm->mod_init_symend; - - for ( ; sp < sp_end; sp++) { - if (STREQ(symbol, sp->name)) - return(TRUE); - } - } - } + if (symname_hash_search(st->mod_symname_hash, symbol, NULL)) + return TRUE; return(FALSE); } @@ -5513,12 +5516,7 @@ per_cpu_symbol_search(char *symbol) int kernel_symbol_exists(char *symbol) { - struct syment *sp; - - if ((sp = symname_hash_search(symbol))) - return TRUE; - else - return FALSE; + return !!(symname_hash_search(st->symname_hash, symbol, NULL)); } /* @@ -5527,7 +5525,7 @@ kernel_symbol_exists(char *symbol) struct syment * kernel_symbol_search(char *symbol) { - return symname_hash_search(symbol); + return symname_hash_search(st->symname_hash, symbol, NULL); } /* @@ -12464,8 +12462,10 @@ store_load_module_symbols(bfd *bfd, int dynamic, void *minisyms, error(INFO, "%s: last symbol: %s is not _MODULE_END_%s?\n", lm->mod_name, lm->mod_load_symend->name, lm->mod_name); + mod_symtable_hash_remove_range(lm->mod_symtable, lm->mod_symend); lm->mod_symtable = lm->mod_load_symtable; lm->mod_symend = lm->mod_load_symend; + mod_symtable_hash_install_range(lm->mod_symtable, lm->mod_symend); lm->mod_flags &= ~MOD_EXT_SYMS; lm->mod_flags |= MOD_LOAD_SYMS; @@ -12495,6 +12495,7 @@ delete_load_module(ulong base_addr) req->name = lm->mod_namelist; gdb_interface(req); } + mod_symtable_hash_remove_range(lm->mod_symtable, lm->mod_symend); if (lm->mod_load_symtable) { free(lm->mod_load_symtable); namespace_ctl(NAMESPACE_FREE, @@ -12504,6 +12505,7 @@ delete_load_module(ulong base_addr) unlink_module(lm); lm->mod_symtable = lm->mod_ext_symtable; lm->mod_symend = lm->mod_ext_symend; + mod_symtable_hash_install_range(lm->mod_symtable, lm->mod_symend); lm->mod_flags &= ~(MOD_LOAD_SYMS|MOD_REMOTE|MOD_NOPATCH); lm->mod_flags |= MOD_EXT_SYMS; lm->mod_load_symtable = NULL; @@ -12532,6 +12534,7 @@ delete_load_module(ulong base_addr) req->name = lm->mod_namelist; gdb_interface(req); } + mod_symtable_hash_remove_range(lm->mod_symtable, lm->mod_symend); if (lm->mod_load_symtable) { free(lm->mod_load_symtable); namespace_ctl(NAMESPACE_FREE, @@ -12541,6 +12544,7 @@ delete_load_module(ulong base_addr) unlink_module(lm); lm->mod_symtable = lm->mod_ext_symtable; lm->mod_symend = lm->mod_ext_symend; + mod_symtable_hash_install_range(lm->mod_symtable, lm->mod_symend); lm->mod_flags &= ~(MOD_LOAD_SYMS|MOD_REMOTE|MOD_NOPATCH); lm->mod_flags |= MOD_EXT_SYMS; lm->mod_load_symtable = NULL; -- 2.29.2