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)

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.

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

Hi Tao, great patch. I have some comments and questions though. On Sun, 22 Aug 2021 09:51:12 +0800 Tao Liu <ltao(a)redhat.com&gt; wrote: > 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) > > 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. > > 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]; ^^^^^^^^ there are quite some whitespace damages throughout the patch. Most of them seem to origin from old code that gets copy & pasted. It would be great if you could fix them on the lines you are touching.

> 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); > + } > + } > +} 1. 'if (sp)' is the same like 'if (sp != NULL)' but shorter. That's why personally I prefer the first version :)

2. Wouldn't it make sense to move this check to the beginning of symname_hash_{install,remove}? Then also the other users like symname_hash_init would benefit.

> /* > * 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; true, in theory index could be negative which would be really bad. But isn't that an independent problem from the rest of the patch? If so this change should go in an extra patch. Furthermore the fix should be done in SYMNAME_HASH_INDEX so that all of its users are fixed. The way I see it this should be enough (using abs from stdlib.h) #define SYMNAME_HASH_INDEX(name) \ - ((name[0] ^ (name[strlen(name)-1] * name[strlen(name)/2])) % SYMNAME_HASH) + (abs((name[0] ^ (name[strlen(name)-1] * name[strlen(name)/2])) % SYMNAME_HASH))

> 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; similar to above, isn't explicitly setting spn->name_hash_next = NULL an independent problem from the rest of the changes and thus should go to a separate patch?

> + } 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; What do you need tmp for? The way I see it you only assign to it but never really use it.

> + } > +} > + > /* > * 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 *)) this line should be indented to match the open parentheses after the function name.

> { > 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; > +} It took really long for me to wrap my head around what is happening here but in the end I'm pretty sure that the extra filtering is unnecessary and can simply be dropped without problem. To be fair what you are doing seems correct it's just by cleaning up the code the problem became more obvious...

Let's see what is happening here: 1) strstr returns a pointer to the start of the second string if is is contained in the first one and NULL otherwise. This means 'pseudos' is true if 's' contains any of the _MODULE_* strings, i.e. if s is a pseudo symbol. 2) MODULE_PSEUDO_SYMBOL does basically the same only that it checks 'sp->name' instead of 's' and enforces that the "_MODULE_*" strings are at the beginning of the symbol name not just contained in it. Let's look at the different cases 3.1) both 's' and 'sp' are proper, i.e. no pseudo, symbols This means skip_symbols returns false so symname_hash_search doesn't skip the symbol but compares 's' to 'sp->name' to check if 'sp' is the symbol you are searching for. This is basically the case you want. 3.2) both 's' and 'sp' are pseudo symbols Again skip_symbols returns false and symname_hash_search compares 's' with 'sp->name' to check if 'sp' is the symbol you are searching for. I'm not entirely sure if this way symname_hash_search is intended to be used but I also don't see a reason why it shouldn't be done. 3.3) 's' is a pseudo and 'sp' a proper symbol same like 3.2). 3.4) 's' is a proper symbol and 'sp' a psudo symbol here skip_symbols returns true and symname_hash_search skips this case. So the only case that is filtered out is 3.4 in which 's' must not contain any '_MODULES_*' while 'sp->name' has to start with one. But that's something a simple STREQ can handle like in case 3.3. So what's the point in having this extra filtering?

From my view it is the only use case for the skip. I agree the code should be optimized.

> /* > * 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); > } Isn't this function basically identical to symbol_search and thus can be abbreviated to return !!(symbol_search(symbol));

> @@ -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; same like above. This could be abbreviated to return !!(symname_hash_search(st->symname_hash, symbol, NULL));

> @@ -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; I must admit I don't understand how the last two functions work, so I'm relying on Kazu to comment on those.

Thanks Philipp

Hi Tao, On Tue, 31 Aug 2021 16:52:33 +0800 Tao Liu <ltao(a)redhat.com&gt; wrote: > Hi Philipp, > > Thanks for reviewing the patch and the comments! you're welcome > > On Mon, Aug 30, 2021 at 05:49:32PM +0200, Philipp Rudo wrote: > > Hi Tao, > > > > great patch. I have some comments and questions though. > > > > On Sun, 22 Aug 2021 09:51:12 +0800 > > Tao Liu <ltao(a)redhat.com&gt; wrote: > > > > > 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) > > > > > > 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. > > > > > > 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]; > > ^^^^^^^^ > > there are quite some whitespace damages throughout the patch. Most > > of them seem to origin from old code that gets copy & pasted. It > > would be great if you could fix them on the lines you are touching. > > > > OK, I will replace the whitespace with tabs. > > > > 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); > > > + } > > > + } > > > +} > > > > 1. 'if (sp)' is the same like 'if (sp != NULL)' but shorter. > > That's why personally I prefer the first version :) > > Agreed. > > > > > 2. Wouldn't it make sense to move this check to the beginning of > > symname_hash_{install,remove}? Then also the other users like > > symname_hash_init would benefit. > > Good suggestion, agreed. > > > > > > /* > > > * 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; > > > > true, in theory index could be negative which would be really bad. But > > isn't that an independent problem from the rest of the patch? If so > > this change should go in an extra patch. > > Furthermore the fix should be done in SYMNAME_HASH_INDEX so that all of > > its users are fixed. The way I see it this should be enough (using abs > > from stdlib.h) > > > > #define SYMNAME_HASH_INDEX(name) \ > > - ((name[0] ^ (name[strlen(name)-1] * name[strlen(name)/2])) % SYMNAME_HASH) > > + (abs((name[0] ^ (name[strlen(name)-1] * name[strlen(name)/2])) % SYMNAME_HASH)) > > > > The index can be negative, though rare, but it is essential to make this patch run > properly. I have encountered a few cases, though I couldn't remenber clearly, which contains > symbols like: "\x77mod". As a result, I got a negative index. I prefer to keep it in > this patch, and I agree with your abs version. I absolutely agree, the fix is necessary. Nevertheless I would like to have the change in a separate patch. In my opinion it is very beneficial to make patches/commits as small as possible. In the long run this helps a lot as this helps you with, e.g. bisecting a problem or backporting the fix to a distro. But most important every patch/commit also contains a description what and why something changed. This is important documentation for other developers and something I miss in crash.

Anyway that's my personal opinion. In the end Kazu and Lianbo as Maintainer have to say what they prefer. > > > > > 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; > > > > similar to above, isn't explicitly setting spn->name_hash_next = NULL > > an independent problem from the rest of the changes and thus should go > > to a separate patch? > > > > Agreed. > > > > + } 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; > > > > What do you need tmp for? The way I see it you only assign to it but > > never really use it. > > > > Since the elements arranged by the hash table are singly linked list. > If we want to remove a specific element out of the list, we need to update > the field which the previous element used to point to the next element. To > do that, I keep the address of the previous-element-pointing-to-the-next field > into tmp variable, well yes, but in the only case where you use tmp you have sp == spn. So you already have two pointers to the same element and don't need a third one to keep the same value. > You can see it is used in code: *tmp = sp->name_hash_next; But in that line you only store the value in tmp. Where do read it from tmp? I only found this tmp = &(*tmp)->name_hash_next; but that again stores the new value in tmp. For the scenario you described above I'd expect to have some lines like this tmp = sp->name_hash_next->name_hash_next; sp->name_hash_next = NULL; sp = tmp;

> > > + } > > > +} > > > + > > > /* > > > * 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 *)) > > > > this line should be indented to match the open parentheses after the > > function name. > > OK. > > > > > > { > > > 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; > > > +} > > > > It took really long for me to wrap my head around what is happening > > here but in the end I'm pretty sure that the extra filtering is > > unnecessary and can simply be dropped without problem. To be fair > > what you are doing seems correct it's just by cleaning up the code the > > problem became more obvious... > > > > Me too, hard for me to figure out what's going on here. My thought was don't > go too far at one step, for now I just tried to keep it as it was. When > the code is stable enough, then get this part optimized... you are right. Better to make small steps and your change already is a big improvement. > > Let's see what is happening here: > > > > 1) strstr returns a pointer to the start of the second string if is is > > contained in the first one and NULL otherwise. This means 'pseudos' > > is true if 's' contains any of the _MODULE_* strings, i.e. if s is a > > pseudo symbol. > > > > 2) MODULE_PSEUDO_SYMBOL does basically the same only that it checks > > 'sp->name' instead of 's' and enforces that the "_MODULE_*" strings > > are at the beginning of the symbol name not just contained in it. > > > > Let's look at the different cases > > > > 3.1) both 's' and 'sp' are proper, i.e. no pseudo, symbols > > This means skip_symbols returns false so symname_hash_search > > doesn't skip the symbol but compares 's' to 'sp->name' to check if > > 'sp' is the symbol you are searching for. This is basically the > > case you want. > > > > 3.2) both 's' and 'sp' are pseudo symbols > > Again skip_symbols returns false and symname_hash_search compares > > 's' with 'sp->name' to check if 'sp' is the symbol you are > > searching for. I'm not entirely sure if this way > > symname_hash_search is intended to be used but I also don't see a > > reason why it shouldn't be done. > > > > 3.3) 's' is a pseudo and 'sp' a proper symbol > > same like 3.2). > > > > 3.4) 's' is a proper symbol and 'sp' a psudo symbol > > here skip_symbols returns true and symname_hash_search skips this > > case. > > > > So the only case that is filtered out is 3.4 in which 's' must not > > contain any '_MODULES_*' while 'sp->name' has to start with one. But > > that's something a simple STREQ can handle like in case 3.3. So what's > > the point in having this extra filtering? > > As you pointed out, the only case to skip is 3.4): A) s is not pseudo, and B) sp is psedudo. > But the "pseudo" of s is different from the "psedudo" of sp. > > Let's say "_MODULE_START_", "_MODULE_END_", "_MODULE_INIT_START_", "_MODULE_INIT_END_" > are true pseudo symbols. > > For s is not pseudo, s can be one of "proper symbol" and "_MODULE_SECTION_" symbol. > For sp is pseudo, sp can be one of "true pseudo symbol" and "_MODULE_SECTION_" symbol. > > Since "proper symbol" and "true pseudo symbol" can never be the same, so skip it or not doesn't > matter, it cannot pass the STREQ check later. The only case left is _MODULE_SECTION_ symbol. > If s and sp are both _MODULE_SECTION_ symbol, even they are equal string, it will be skipped. > From my view it is the only use case for the skip. I agree the code should be optimized. true, I missed the _MODULE_SECTION_ case... although I'm not sure why this case should be treated differently to the other _MODULE_* cases...

> > > /* > > > * 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); > > > } > > > > Isn't this function basically identical to symbol_search and thus can > > be abbreviated to > > > > return !!(symbol_search(symbol)); > > In the original symbol_search, there are 3 stages to find a symbol: > 1) search in kernel symbols hash table. > 2) iterate over all kernel symbols. > 3) iterate over all kernel mods and their symbols. > > As for symbol_exists, it only do 1) 3) stages. Personally I think stage 2) is > unnecessary, but I didn't have a strong reason to remove it. Thus I didn't > replace symbol_exists with symbol_search directly. If stage 2) can be removed, > then I'm OK with your modification. you are right. Better wait till case 2) got removed properly. Otherwise we might introduce a bug now... > > > @@ -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; > > > > same like above. This could be abbreviated to > > > > return !!(symname_hash_search(st->symname_hash, symbol, NULL)); > > > > Agreed, this one can be replaced this way. > > > > @@ -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; > > > > I must admit I don't understand how the last two functions work, so I'm > > relying on Kazu to comment on those. > > The difference of mod symbols and kernel symbols, is that kernel symbols will not change after loaded > into hash table, mod symbols can get modified by "mod" cmd. Whenever mod symbols changed, it should > be synced to mod symbols hash table. The above changed lines are trying to do that. Thanks for the explanation. However, my main problem is less what it does but more how it does it. For example in delete_load_module first all symbols from lm->mod_symtab are removed. Then lm->mod_symtab is changed to lm->mod_ext_symtab and then all symbols are installed again. Why? What's the difference between the mod_symtab and mod_ext_symtab? At least when looking at store_module_symbols_v{1,2} both should be the same...

Thanks Philipp

Hi Tao Liu, Philipp Thanks for the patch and review.

> > > > > +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; > > > > > > > > What do you need tmp for? The way I see it you only assign to it but > > > > never really use it. > > > > > > > > > > Since the elements arranged by the hash table are singly linked list. > > > If we want to remove a specific element out of the list, we need to update > > > the field which the previous element used to point to the next element. To > > > do that, I keep the address of the previous-element-pointing-to-the-next field > > > into tmp variable, > > > > well yes, but in the only case where you use tmp you have sp == spn. So > > you already have two pointers to the same element and don't need a third > > one to keep the same value. > > > > > You can see it is used in code: *tmp = sp->name_hash_next; > > > > But in that line you only store the value in tmp. Where do read it from > > tmp? I only found this > > > > tmp = &(*tmp)->name_hash_next; > > > > but that again stores the new value in tmp. For the scenario you > > described above I'd expect to have some lines like this > > > > tmp = sp->name_hash_next->name_hash_next; > > sp->name_hash_next = NULL; > > sp = tmp; > > > > I tried to elimitate the "tmp" variable but failed, I will be appreciated if > you can do it for me? > > My thought was, since struct syment is a singly linked list, sp and spn are used > to judge if the element which sp pointing to > should be removed from the list or not. To remove sp from the list, the element > which prior to sp should point to the element which follows sp. So I need a > varible which can always track the element which is prior to sp. The variable > "tmp" achieves that, actually it is the field where the prior element should > be updated when removing sp from the list. As you can see, tmp is not equivalent > to sp and spn. Is that loop replaced with this? maybe missing something. 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; }

(spn will be freed right after this, no need to update?)

> > > > > > + } > > > > > +} > > > > > + > > > > > /* > > > > > * 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 *)) > > > > > > > > this line should be indented to match the open parentheses after the > > > > function name. > > > > > > OK. > > > > > > > > > > > > { > > > > > 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; > > > > > +} > > > > > > > > It took really long for me to wrap my head around what is happening > > > > here but in the end I'm pretty sure that the extra filtering is > > > > unnecessary and can simply be dropped without problem. To be fair > > > > what you are doing seems correct it's just by cleaning up the code the > > > > problem became more obvious... > > > > > > > > > > Me too, hard for me to figure out what's going on here. My thought was don't > > > go too far at one step, for now I just tried to keep it as it was. When > > > the code is stable enough, then get this part optimized... > > > > you are right. Better to make small steps and your change already is a > > big improvement. > > > > > > Let's see what is happening here: > > > > > > > > 1) strstr returns a pointer to the start of the second string if is is > > > > contained in the first one and NULL otherwise. This means 'pseudos' > > > > is true if 's' contains any of the _MODULE_* strings, i.e. if s is a > > > > pseudo symbol. > > > > > > > > 2) MODULE_PSEUDO_SYMBOL does basically the same only that it checks > > > > 'sp->name' instead of 's' and enforces that the "_MODULE_*" strings > > > > are at the beginning of the symbol name not just contained in it. > > > > > > > > Let's look at the different cases > > > > > > > > 3.1) both 's' and 'sp' are proper, i.e. no pseudo, symbols > > > > This means skip_symbols returns false so symname_hash_search > > > > doesn't skip the symbol but compares 's' to 'sp->name' to check if > > > > 'sp' is the symbol you are searching for. This is basically the > > > > case you want. > > > > > > > > 3.2) both 's' and 'sp' are pseudo symbols > > > > Again skip_symbols returns false and symname_hash_search compares > > > > 's' with 'sp->name' to check if 'sp' is the symbol you are > > > > searching for. I'm not entirely sure if this way > > > > symname_hash_search is intended to be used but I also don't see a > > > > reason why it shouldn't be done. > > > > > > > > 3.3) 's' is a pseudo and 'sp' a proper symbol > > > > same like 3.2). > > > > > > > > 3.4) 's' is a proper symbol and 'sp' a psudo symbol > > > > here skip_symbols returns true and symname_hash_search skips this > > > > case. > > > > > > > > So the only case that is filtered out is 3.4 in which 's' must not > > > > contain any '_MODULES_*' while 'sp->name' has to start with one. But > > > > that's something a simple STREQ can handle like in case 3.3. So what's > > > > the point in having this extra filtering? > > > > > > As you pointed out, the only case to skip is 3.4): A) s is not pseudo, and B) sp is psedudo. > > > But the "pseudo" of s is different from the "psedudo" of sp. > > > > > > Let's say "_MODULE_START_", "_MODULE_END_", "_MODULE_INIT_START_", "_MODULE_INIT_END_" > > > are true pseudo symbols. > > > > > > For s is not pseudo, s can be one of "proper symbol" and "_MODULE_SECTION_" symbol. > > > For sp is pseudo, sp can be one of "true pseudo symbol" and "_MODULE_SECTION_" symbol. > > > > > > Since "proper symbol" and "true pseudo symbol" can never be the same, so skip it or not doesn't > > > matter, it cannot pass the STREQ check later. The only case left is _MODULE_SECTION_ symbol. > > > If s and sp are both _MODULE_SECTION_ symbol, even they are equal string, it will be skipped. > > > From my view it is the only use case for the skip. I agree the code should be optimized. > > > > true, I missed the _MODULE_SECTION_ case... although I'm not sure why > > this case should be treated differently to the other _MODULE_* cases... > > > > Me neither, just keep it as it was... > > > > > > /* > > > > > * 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); > > > > > } > > > > > > > > Isn't this function basically identical to symbol_search and thus can > > > > be abbreviated to > > > > > > > > return !!(symbol_search(symbol)); > > > > > > In the original symbol_search, there are 3 stages to find a symbol: > > > 1) search in kernel symbols hash table. > > > 2) iterate over all kernel symbols. > > > 3) iterate over all kernel mods and their symbols. > > > > > > As for symbol_exists, it only do 1) 3) stages. Personally I think stage 2) is > > > unnecessary, but I didn't have a strong reason to remove it. Thus I didn't > > > replace symbol_exists with symbol_search directly. If stage 2) can be removed, > > > then I'm OK with your modification. > > > > you are right. Better wait till case 2) got removed properly. Otherwise > > we might introduce a bug now... > > > > > > > @@ -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; > > > > > > > > same like above. This could be abbreviated to > > > > > > > > return !!(symname_hash_search(st->symname_hash, symbol, NULL)); > > > > > > > > > > Agreed, this one can be replaced this way. > > > > > > > > @@ -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; > > > > > > > > I must admit I don't understand how the last two functions work, so I'm > > > > relying on Kazu to comment on those. > > > > > > The difference of mod symbols and kernel symbols, is that kernel symbols will not change after loaded > > > into hash table, mod symbols can get modified by "mod" cmd. Whenever mod symbols changed, it should > > > be synced to mod symbols hash table. The above changed lines are trying to do that. > > > > Thanks for the explanation. However, my main problem is less what it > > does but more how it does it. > > > > For example in delete_load_module first all symbols from lm->mod_symtab > > are removed. Then lm->mod_symtab is changed to lm->mod_ext_symtab and > > then all symbols are installed again. Why? What's the difference > > between the mod_symtab and mod_ext_symtab? At least when looking at > > store_module_symbols_v{1,2} both should be the same... > > No, lm->mod_symtable and lm->mod_ext_symtable are not always the same. > lm->mod_symtable will be assigned to lm->mod_load_symtable in > symbols.c:store_load_module_symbols. When invoke 'mod -S/-s' in crash, > the modules(.ko) will be read into, the symbols will get refreshed. If 'mod -d' > remove the modules, the symbols will be restored to mod_ext_symtable. > > My understanding is, lm->mod_ext_symtable is read from vmcore, and > lm->mod_load_symtable is read from (.ko) file. Though mostly the symbols > are the same, but we cannot guarantee that... Right, probably if no CONFIG_KALLSYMS, the number of symbols in lm->mod_ext_symtable will be less than lm->mod_load_symbable. Thanks, Kazu