Re: [Crash-utility] [PATCH v2] Improve the performance of symbol searching for kernel modules

Hi Tao Liu, -----Original Message----- > Currently the sequence for crash searching 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) Just to clarify, which parts of code are meant by the stage 1 and 2? Do you have a result with the patch? > > stage 3 takes too much time when comparing to stage 1. So let's introduce a > symname hash table for kernel modules to improve the performance of symbol > searching. I see that 3) is relatively time-consuming, but I have not had a delay due to the symbol search. Which command did you observe a delay?

Thanks, Kazu > > Signed-off-by: Tao Liu <ltao(a)redhat.com&gt; > --- > v1 -> v2: > - Removed unused variables within the modified functions. > > --- > defs.h | 1 + > kernel.c | 1 + > symbols.c | 189 +++++++++++++++++++++++++++++++----------------------- > 3 files changed, 111 insertions(+), 80 deletions(-) > > diff --git a/defs.h b/defs.h > index eb1c71b..58b8546 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 36fdea2..c56cc34 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..9b64734 100644 > --- a/symbols.c > +++ b/symbols.c > @@ -64,8 +64,9 @@ 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 +1120,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 +1128,48 @@ 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++) { > + if (sp != NULL) { > + 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++) { > + if (sp != NULL) { > + 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; > > index = SYMNAME_HASH_INDEX(spn->name); > + index = index > 0 ? index : -index; > + > spn->cnt = 1; > > - if ((sp = st->symname_hash[index]) == NULL) > - st->symname_hash[index] = spn; > - else { > + if ((sp = table[index]) == NULL) { > + table[index] = spn; > + spn->name_hash_next = NULL; > + } else { > while (sp) { > if (STREQ(sp->name, spn->name)) { > sp->cnt++; > @@ -1151,23 +1179,67 @@ symname_hash_install(struct syment *spn) > sp = sp->name_hash_next; > else { > sp->name_hash_next = spn; > + spn->name_hash_next = NULL; > break; > } > } > } > } > > +static void > +symname_hash_remove(struct syment *table[], struct syment *spn) > +{ > + struct syment *sp, **tmp; > + int index, first_encounter = 1; > + > + index = SYMNAME_HASH_INDEX(spn->name); > + index = index > 0 ? index : -index; > + > + if ((sp = table[index]) == NULL) > + return; > + > + for (tmp = &table[index], sp = table[index]; sp; ) { > + if (STREQ(sp->name, spn->name)) { > + if (sp != spn) { > + sp->cnt--; > + spn->cnt--; > + } else if (!first_encounter) { > + sp->cnt--; > + } else { > + *tmp = sp->name_hash_next; > + first_encounter = 0; > + > + tmp = &(*tmp)->name_hash_next; > + sp = sp->name_hash_next; > + spn->name_hash_next = NULL; > + continue; > + } > + } > + tmp = &sp->name_hash_next; > + sp = sp->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); > + index = index > 0 ? index : -index; > + 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 +1667,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 +2148,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 +4557,16 @@ 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 +4574,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 +5475,13 @@ value_symbol(ulong value) > int > symbol_exists(char *symbol) > { > - int i; > - struct syment *sp, *sp_end; > - struct load_module *lm; > + struct syment *sp; > > - if ((sp = symname_hash_search(symbol))) > + if ((sp = 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 ((sp = symname_hash_search(st->mod_symname_hash, symbol, NULL))) > + return TRUE; > > return(FALSE); > } > @@ -5515,7 +5538,7 @@ kernel_symbol_exists(char *symbol) > { > struct syment *sp; > > - if ((sp = symname_hash_search(symbol))) > + if ((sp = symname_hash_search(st->symname_hash, symbol, NULL))) > return TRUE; > else > return FALSE; > @@ -5527,7 +5550,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 +12487,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 +12520,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 +12530,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 +12559,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 +12569,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 > > -- > Crash-utility mailing list > Crash-utility(a)redhat.com > https://listman.redhat.com/mailman/listinfo/crash-utility -- Crash-utility mailing list Crash-utility(a)redhat.com https://listman.redhat.com/mailman/listinfo/crash-utility