[Crash-utility] [PATCH v2] Improve the performance of symbol searching for kernel modules
Tao Liu
ltao at redhat.com
Mon Aug 23 14:07:05 UTC 2021
On Mon, Aug 23, 2021 at 08:24:28AM +0000, HAGIO KAZUHITO(萩尾 一仁) wrote:
> 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?
Hello Kazu,
The target function is symbols.c:symbol_search. The code involved in the 3 stages are:
1) sp_hashed = symname_hash_search(s);
2) for (sp = sp_hashed ? sp_hashed : st->symtable; sp < st->symend; sp++) {
if (STREQ(s, sp->name))
return(sp);
3) for (i = 0; i < st->mods_installed; i++) {
lm = &st->load_modules[i];
....
}
I measured each stage's time by adding the following code to symbol_search:
struct load_module *lm;
int pseudos, search_init;
+ double T1, T2, T3;
+ clock_t start, end;
+ start = clock();
sp_hashed = symname_hash_search(s);
+ end = clock();
+ T1 = (double)(end - start) * 1000.0 / CLOCKS_PER_SEC;
+ start = clock();
for (sp = sp_hashed ? sp_hashed : st->symtable; sp < st->symend; sp++) {
if (STREQ(s, sp->name))
return(sp);
}
+ end = clock();
+ T2 = (double)(end - start) * 1000.0 / CLOCKS_PER_SEC;
pseudos = (strstr(s, "_MODULE_START_") || strstr(s, "_MODULE_END_"));
search_init = FALSE;
+ start = clock();
for (i = 0; i < st->mods_installed; i++) {
lm = &st->load_modules[i];
if (lm->mod_flags & MOD_INIT)
....
return(sp);
}
}
+ end = clock();
+ T3 = (double)(end - start) * 1000.0 / CLOCKS_PER_SEC;
+ printf("%lf %lf %lf\n", T1, T2, T3);
if (!search_init)
return((struct syment *)NULL);
crash> sym blah
T1:0.008000 T2:0.562000 T3:2.435000
symbol not found: blah
possible alternatives:
(none found)
With the v2 patch applied and the time measurement code added:
crash> sym blah
T1:0.003000 T2:0.545000 T3:0.017000
symbol not found: blah
possible alternatives:
(none found)
We can see T3 performs better.
Thanks,
Tao Liu
>
> Thanks,
> Kazu
>
>
> >
> > Signed-off-by: Tao Liu <ltao at redhat.com>
> > ---
> > 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 at redhat.com
> > https://listman.redhat.com/mailman/listinfo/crash-utility
>
>
> --
> Crash-utility mailing list
> Crash-utility at redhat.com
> https://listman.redhat.com/mailman/listinfo/crash-utility
>
More information about the Crash-utility
mailing list