[Crash-utility] [PATCH v6 1/7] Implement install and remove operations for mod_symname_hash

[lijiang]

On Wed, Oct 20, 2021 at 6:22 PM Tao Liu <ltao at redhat.com> wrote:
>
> Hello lijiang,
>
> Thanks for reviewing the patch!
>
> On Wed, Oct 20, 2021 at 4:46 PM lijiang <lijiang at redhat.com> wrote:
> >
> > Hi, Tao
> > Thank you for the update.
> >
> > On Sat, Oct 16, 2021 at 1:21 PM Tao Liu <ltao at redhat.com> wrote:
> > >
> > > This patch indroduces mod_symname_hash, and its install/remove operations.
> > > Since symbol_search() has to return the lowest address symbol and
> > > symbol_search_next() returns the next lowest symbol, thus the installation
> > > should be sorted ascendingly.
> > >
> > > In mod_symname_hash_install_range scenario, spn are already arranged
> > > ascendingly, so for mod_symname_hash_install:
> > >
> > > Install spn previous to sp:
> > >
> > > If sp is the start of bucket, and
> > > 1) spn->value is smaller than sp->value.
> > >
> > > Install spn next to sp:
> > >
> > > 1) sp->name_hash_next is NULL or
> > > 2) sp->name_hash_next->value larger than spn->value
> > >
> > > spn->value is the kernel address of the symbol and will not change.
> > > So we use it mainly to determine the sequence. When spn->value equals
> > > sp->value, they must be symbols within a kernel module.
> > >
> > > Signed-off-by: Tao Liu <ltao at redhat.com>
> > > ---
> > >  defs.h    |  1 +
> > >  symbols.c | 73 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
> > >  2 files changed, 74 insertions(+)
> > >
> > > diff --git a/defs.h b/defs.h
> > > index cbd45e5..bbdca79 100644
> > > --- a/defs.h
> > > +++ b/defs.h
> > > @@ -2755,6 +2755,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/symbols.c b/symbols.c
> > > index 69dccdb..ad12d1c 100644
> > > --- a/symbols.c
> > > +++ b/symbols.c
> > > @@ -1157,6 +1157,79 @@ symname_hash_install(struct syment *spn)
> > >         }
> > >  }
> > >
> > > +/*
> > > + *  Install a single kernel module symbol into the mod_symname_hash.
> > > + */
> > > +static void
> > > +mod_symname_hash_install(struct syment *spn)
> > > +{
> > > +       struct syment *sp;
> > > +       int index;
> > > +
> > > +       if (!spn)
> > > +               return;
> > > +
> > > +       index = SYMNAME_HASH_INDEX(spn->name);
> > > +
> > > +       sp = st->mod_symname_hash[index];
> > > +
> > > +       if (!sp || (spn->value < sp->value)) {
> > > +               st->mod_symname_hash[index] = spn;
> >                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> > This could overwrite the existing syment if (sp && (spn->value <
> > sp->value)), right?
> >
> I think it won't overwrite existing syment. if (sp && (spn->value <
> > sp->value)), then what we want to do is inserting spn as the start of the bucket, and making sp to be the 2nd one. So st->mod_symname_hash[index] = spn, making spn to be the start of the bucket, then spn->name_hash_next = sp, making sp right after spn.
>
> > > +               spn->name_hash_next = sp;
> > > +               return;
> > > +       }
> > > +       for (; sp; sp = sp->name_hash_next) {
> > > +               if (!sp->name_hash_next ||
> > > +                   spn->value < sp->name_hash_next->value) {
> > > +                       spn->name_hash_next = sp->name_hash_next;
> > > +                       sp->name_hash_next = spn;
> > > +                       return;
> > > +               }
> > > +       }
> > > +}
> > > +
> > > +static void
> > > +mod_symname_hash_remove(struct syment *spn)
> > > +{
> > > +       struct syment *sp;
> > > +       int index;
> > > +
> > > +       if (!spn)
> > > +               return;
> > > +
> > > +       index = SYMNAME_HASH_INDEX(spn->name);
> > > +
> > > +       if (st->mod_symname_hash[index] == spn) {
> > > +               st->mod_symname_hash[index] = spn->name_hash_next;
> > > +               return;
> > > +       }
> > > +
> > > +       for (sp = st->mod_symname_hash[index]; sp; sp = sp->name_hash_next) {
> > > +               if (sp->name_hash_next == spn) {
> > > +                       sp->name_hash_next = spn->name_hash_next;
> > > +                       return;
> > > +               }
> > > +       }
> > > +}
> >
> > Can the above mod_symname_hash_remove() be simplified into the
> > following implementation? The code may become more readable, and I
> > didn't see any obvious performance issues as below.
> >
> > +static void
> > +mod_symname_hash_remove(struct syment *spn)
> > +{
> > +       int index;
> > +       struct syment *sp;
> > +
> > +       if (!spn)
> > +               return;
> > +
> > +       index = SYMNAME_HASH_INDEX(spn->name);
> > +       sp = st->mod_symname_hash[index];
> > +
> > +       while (sp) {
> > +               if (sp == spn) {
> > +                       sp = spn->name_hash_next;
> > +                       spn->name_hash_next = NULL;
> > +                       return;
> > +               }
> > +               sp = sp->name_hash_next;
> > +       }
> > +}
> >
>
> I don't think it can work. if (sp == spn), then sp should be removed
> from the hash table. Since it is a singly linked list, the
> name_hash_next field of the one which is prior to sp should be
> updated. But in the code it is not.
>

I haven't debugged it, just an idea.  I will debug it later. Thanks.

> Thanks,
> Tao Liu
> >
> > > +
> > > +static void
> > > +mod_symtable_hash_install_range(struct syment *from, struct syment *to)
> > > +{
> > > +       struct syment *sp;
> > > +
> > > +       for (sp = from; sp <= to; sp++)
> > > +               mod_symname_hash_install(sp);
> > > +}
> > > +
> > > +static void
> > > +mod_symtable_hash_remove_range(struct syment *from, struct syment *to)
> > > +{
> > > +       struct syment *sp;
> > > +
> > > +       for (sp = from; sp <= to; sp++)
> > > +               mod_symname_hash_remove(sp);
> > > +}
> > > +
> > >  /*
> > >   *  Static kernel symbol value search
> > >   */
> > > --
> > > 2.29.2
> > >
> >
>