[Crash-utility] [PATCH v2] Improve the performance of symbol searching for kernel modules
Philipp Rudo
prudo at redhat.com
Wed Sep 8 17:50:32 UTC 2021
Hi Kazu,
totally missed your mail...
On Wed, 8 Sep 2021 09:37:05 +0000
HAGIO KAZUHITO(萩尾 一仁) <k-hagio-ab at nec.com> wrote:
> 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;
> }
I think that should work and improve the code quite substantially.
> (spn will be freed right after this, no need to update?)
I don't think updating spn is necessary. Updating spn->cnt will grant
you a sanity check as AFAIK it must be zero after the for-loop. Not
sure if it's worth it though.
Thanks
Philipp
> >
> > > > > > + }
> > > > > > +}
> > > > > > +
> > > > > > /*
> > > > > > * 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
>
More information about the Crash-utility
mailing list