9:13 a.m.
Currently the sequence for symbol_search to search 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. This patch introduces
a symname hash table for kernel modules, to improve the performance of symbol
searching.
Functions symbol_search and symbol_exists are fundamental and widely used by
other crash functions, thus the benefit of performance improvement can
get accumulated. For example, "ps -m" and "irq" commands, which call
the functions many times, will become faster with the patch.
v4 -> v5:
1) Seperated kernel modules syment install from kernel syment install,
making them 2 independent functions. Thus kernel modules syment can get sorted
when installed into mod_syment_hash. And spn->cnt stays untouched in v5.
2) Removed syment_is_installed check, it is no longer needed for the new
kernel modules syment install function.
3) Splitted the patches into smaller ones for better patch review.
4) Changed SYMNAME_HASH_INDEX macro into symname_hash_index function.
5) v5 patch can be applied to master branch, for crash-7-branch it needs
slightly modification.
Tao Liu (6):
Implement install and remove operations for mod_symname_hash
Integrate symbol_search with mod_symname_hash search
Extend symname_hash_search with hash table select
Intergrate symbol_exists with mod_symname_hash search
Sync module symbols into mod_symtable whenever module symbols change
Refactor SYMNAME_HASH_INDEX macro to be a function
defs.h | 3 +-
kernel.c | 1 +
symbols.c | 212 ++++++++++++++++++++++++++++++++++--------------------
3 files changed, 137 insertions(+), 79 deletions(-)
--
2.29.2
9:13 a.m.
New subject: [PATCH v5 1/6] Implement install and remove operations for mod_symname_hash
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.
Install spn previous to sp:
If sp is the start of bucket, and
1) spn->value is smaller than sp->value, or
2) spn->value equals sp->value and spn is smaller than sp.
Install spn next to sp:
1) spn->value is larger than sp->value, or
2) spn->value equals to sp->value and spn is larger than sp,
spn will stay behind of sp. And if
1) sp->name_hash_next is NULL or
2) sp->name_hash_next->value larger than spn->value
spn will be next to sp.
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, so we use spn
and sp to determine the sequence.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 1 +
symbols.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 82 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..7fb2df7 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1157,6 +1157,87 @@ 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, *tmp;
+ int index;
+
+ if (!spn)
+ return;
+
+ index = SYMNAME_HASH_INDEX(spn->name);
+
+ sp = st->mod_symname_hash[index];
+
+ if (!sp ||
+ (spn->value < sp->value) ||
+ (spn->value == sp->value && spn < sp)) {
+ /*
+ * Install spn to the previous position of sp.
+ */
+ st->mod_symname_hash[index] = spn;
+ spn->name_hash_next = sp;
+ } else {
+ for (; sp; sp = sp->name_hash_next) {
+ if ((spn->value > sp->value) ||
+ (spn->value == sp->value && spn > sp)) {
+ if (!sp->name_hash_next ||
+ spn->value < sp->name_hash_next->value) {
+ /*
+ * Install spn to the next position of sp.
+ */
+ tmp = sp->name_hash_next;
+ sp->name_hash_next = spn;
+ spn->name_hash_next = tmp;
+ break;
+ }
+ }
+ }
+ }
+}
+
+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;
+
+ 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;
+ }
+}
+
+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
4:09 a.m.
New subject: [PATCH v5 1/6] Implement install and remove operations for mod_symname_hash
Hi Tao Liu,
Thanks for the update.
-----Original Message-----
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.
Install spn previous to sp:
If sp is the start of bucket, and
1) spn->value is smaller than sp->value, or
2) spn->value equals sp->value and spn is smaller than sp.
Install spn next to sp:
1) spn->value is larger than sp->value, or
2) spn->value equals to sp->value and spn is larger than sp,
spn will stay behind of sp. And if
1) sp->name_hash_next is NULL or
2) sp->name_hash_next->value larger than spn->value
spn will be next to sp.
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, so we use spn
and sp to determine the sequence.
If sp->value equals to spn->value, they are in the same module, and
spn should be larger than sp, according to mod_symtable_hash_install_range().
Then is it OK to insert spn when sp->value becomes larger than spn->value
like this?
sp = st->mod_symname_hash[index];
if (!sp) {
st->mod_symname_hash[index] = spn;
spn->name_hash_next = NULL;
return;
}
for (; sp; sp = sp->name_hash_next) {
if (sp->value > spn->value || !sp->name_hash_next) {
spn->name_hash_next = sp->name_hash_next;
sp->name_hash_next = spn;
return;
}
}
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 1 +
symbols.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 82 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..7fb2df7 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1157,6 +1157,87 @@ 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, *tmp;
+ int index;
+
+ if (!spn)
+ return;
+
+ index = SYMNAME_HASH_INDEX(spn->name);
+
+ sp = st->mod_symname_hash[index];
+
+ if (!sp ||
+ (spn->value < sp->value) ||
+ (spn->value == sp->value && spn < sp)) {
+ /*
+ * Install spn to the previous position of sp.
+ */
+ st->mod_symname_hash[index] = spn;
+ spn->name_hash_next = sp;
+ } else {
+ for (; sp; sp = sp->name_hash_next) {
+ if ((spn->value > sp->value) ||
+ (spn->value == sp->value && spn > sp)) {
+ if (!sp->name_hash_next ||
+ spn->value < sp->name_hash_next->value) {
+ /*
+ * Install spn to the next position of sp.
+ */
+ tmp = sp->name_hash_next;
+ sp->name_hash_next = spn;
+ spn->name_hash_next = tmp;
+ break;
+ }
+ }
+ }
+ }
+}
+
+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;
I think now we can return here,
+
+ 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;
and here, too.
For the other patches, please wait for a while.
Thanks,
Kazu
+ }
+}
+
+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
7:19 p.m.
New subject: [PATCH v5 1/6] Implement install and remove operations for mod_symname_hash
-----Original Message-----
Hi Tao Liu,
Thanks for the update.
-----Original Message-----
> 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.
>
> Install spn previous to sp:
>
> If sp is the start of bucket, and
> 1) spn->value is smaller than sp->value, or
> 2) spn->value equals sp->value and spn is smaller than sp.
>
> Install spn next to sp:
>
> 1) spn->value is larger than sp->value, or
> 2) spn->value equals to sp->value and spn is larger than sp,
> spn will stay behind of sp. And if
> 1) sp->name_hash_next is NULL or
> 2) sp->name_hash_next->value larger than spn->value
> spn will be next to sp.
>
> 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, so we use spn
> and sp to determine the sequence.
If sp->value equals to spn->value, they are in the same module, and
spn should be larger than sp, according to mod_symtable_hash_install_range().
Then is it OK to insert spn when sp->value becomes larger than spn->value
like this?
sp = st->mod_symname_hash[index];
if (!sp) {
st->mod_symname_hash[index] = spn;
spn->name_hash_next = NULL;
return;
}
for (; sp; sp = sp->name_hash_next) {
if (sp->value > spn->value || !sp->name_hash_next) {
spn->name_hash_next = sp->name_hash_next;
sp->name_hash_next = spn;
return;
}
}
sorry, I was confused, this is a fixed one:
sp = st->mod_symname_hash[index];
if (!sp || sp->value > spn->value) {
spn->name_hash_next = sp;
st->mod_symname_hash[index] = spn;
return;
}
for (; sp; sp = sp->name_hash_next) {
if (!sp->name_hash_next || sp->name_hash_next->value >
spn->value) {
spn->name_hash_next = sp->name_hash_next;
sp->name_hash_next = spn;
return;
}
}
Thanks,
Kazu
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> defs.h | 1 +
> symbols.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 82 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..7fb2df7 100644
> --- a/symbols.c
> +++ b/symbols.c
> @@ -1157,6 +1157,87 @@ 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, *tmp;
> + int index;
> +
> + if (!spn)
> + return;
> +
> + index = SYMNAME_HASH_INDEX(spn->name);
> +
> + sp = st->mod_symname_hash[index];
> +
> + if (!sp ||
> + (spn->value < sp->value) ||
> + (spn->value == sp->value && spn < sp)) {
> + /*
> + * Install spn to the previous position of sp.
> + */
> + st->mod_symname_hash[index] = spn;
> + spn->name_hash_next = sp;
> + } else {
> + for (; sp; sp = sp->name_hash_next) {
> + if ((spn->value > sp->value) ||
> + (spn->value == sp->value && spn > sp)) {
> + if (!sp->name_hash_next ||
> + spn->value < sp->name_hash_next->value) {
> + /*
> + * Install spn to the next position of sp.
> + */
> + tmp = sp->name_hash_next;
> + sp->name_hash_next = spn;
> + spn->name_hash_next = tmp;
> + break;
> + }
> + }
> + }
> + }
> +}
> +
> +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;
I think now we can return here,
> +
> + 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;
and here, too.
For the other patches, please wait for a while.
Thanks,
Kazu
> + }
> +}
> +
> +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
--
Crash-utility mailing list
Crash-utility(a)redhat.com
https://listman.redhat.com/mailman/listinfo/crash-utility
12:25 a.m.
New subject: [PATCH v5 1/6] Implement install and remove operations for mod_symname_hash
Hi Kazu,
On Fri, Oct 15, 2021 at 8:19 AM HAGIO KAZUHITO(萩尾 一仁)
<k-hagio-ab(a)nec.com> wrote:
-----Original Message-----
> Hi Tao Liu,
>
> Thanks for the update.
>
> -----Original Message-----
> > 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.
> >
> > Install spn previous to sp:
> >
> > If sp is the start of bucket, and
> > 1) spn->value is smaller than sp->value, or
> > 2) spn->value equals sp->value and spn is smaller than sp.
> >
> > Install spn next to sp:
> >
> > 1) spn->value is larger than sp->value, or
> > 2) spn->value equals to sp->value and spn is larger than sp,
> > spn will stay behind of sp. And if
> > 1) sp->name_hash_next is NULL or
> > 2) sp->name_hash_next->value larger than spn->value
> > spn will be next to sp.
> >
> > 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, so we use spn
> > and sp to determine the sequence.
>
> If sp->value equals to spn->value, they are in the same module, and
> spn should be larger than sp, according to mod_symtable_hash_install_range().
> Then is it OK to insert spn when sp->value becomes larger than spn->value
> like this?
>
> sp = st->mod_symname_hash[index];
> if (!sp) {
> st->mod_symname_hash[index] = spn;
> spn->name_hash_next = NULL;
> return;
> }
> for (; sp; sp = sp->name_hash_next) {
> if (sp->value > spn->value || !sp->name_hash_next) {
> spn->name_hash_next = sp->name_hash_next;
> sp->name_hash_next = spn;
> return;
> }
> }
sorry, I was confused, this is a fixed one:
sp = st->mod_symname_hash[index];
if (!sp || sp->value > spn->value) {
spn->name_hash_next = sp;
st->mod_symname_hash[index] = spn;
return;
}
for (; sp; sp = sp->name_hash_next) {
if (!sp->name_hash_next || sp->name_hash_next->value >
spn->value) {
spn->name_hash_next = sp->name_hash_next;
sp->name_hash_next = spn;
return;
}
}
Agreed, thanks for the suggestion! I have integrated the fix in the v6 patch.
Thanks,
Tao Liu
Thanks,
Kazu
>
> >
> > Signed-off-by: Tao Liu <ltao(a)redhat.com>
> > ---
> > defs.h | 1 +
> > symbols.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
> > 2 files changed, 82 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..7fb2df7 100644
> > --- a/symbols.c
> > +++ b/symbols.c
> > @@ -1157,6 +1157,87 @@ 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, *tmp;
> > + int index;
> > +
> > + if (!spn)
> > + return;
> > +
> > + index = SYMNAME_HASH_INDEX(spn->name);
> > +
> > + sp = st->mod_symname_hash[index];
> > +
> > + if (!sp ||
> > + (spn->value < sp->value) ||
> > + (spn->value == sp->value && spn < sp)) {
> > + /*
> > + * Install spn to the previous position of sp.
> > + */
> > + st->mod_symname_hash[index] = spn;
> > + spn->name_hash_next = sp;
> > + } else {
> > + for (; sp; sp = sp->name_hash_next) {
> > + if ((spn->value > sp->value) ||
> > + (spn->value == sp->value && spn > sp))
{
> > + if (!sp->name_hash_next ||
> > + spn->value <
sp->name_hash_next->value) {
> > + /*
> > + * Install spn to the next position of sp.
> > + */
> > + tmp = sp->name_hash_next;
> > + sp->name_hash_next = spn;
> > + spn->name_hash_next = tmp;
> > + break;
> > + }
> > + }
> > + }
> > + }
> > +}
> > +
> > +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;
>
> I think now we can return here,
>
> > +
> > + 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;
>
> and here, too.
>
> For the other patches, please wait for a while.
>
> Thanks,
> Kazu
>
>
> > + }
> > +}
> > +
> > +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
>
>
> --
> Crash-utility mailing list
> Crash-utility(a)redhat.com
> https://listman.redhat.com/mailman/listinfo/crash-utility
9:13 a.m.
New subject: [PATCH v5 2/6] Integrate symbol_search with mod_symname_hash search
This patch introduces mod_symname_hash search to symbol_search,
to get a better searching performance.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
Reviewed-by: Philipp Rudo <prudo(a)redhat.com>
---
symbols.c | 58 ++++++++++++++++++-------------------------------------
1 file changed, 19 insertions(+), 39 deletions(-)
diff --git a/symbols.c b/symbols.c
index 7fb2df7..92c066a 100644
--- a/symbols.c
+++ b/symbols.c
@@ -4559,6 +4559,17 @@ symbol_query(char *s, char *print_pad, struct syment **spp)
return(cnt);
}
+static int
+skip_symbols(struct syment *sp, char *s)
+{
+ int pseudos, skip = FALSE;
+
+ 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 = TRUE;
+ return skip;
+}
/*
* Return the syment of a symbol.
@@ -4566,10 +4577,7 @@ 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);
@@ -4578,43 +4586,15 @@ symbol_search(char *s)
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)
+ sp = st->mod_symname_hash[SYMNAME_HASH_INDEX(s)];
+ while (sp) {
+ if (skip_symbols(sp, s)) {
+ sp = sp->name_hash_next;
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);
}
+ if (STREQ(sp->name, s))
+ return sp;
+ sp = sp->name_hash_next;
}
return((struct syment *)NULL);
--
2.29.2
9:13 a.m.
New subject: [PATCH v5 3/6] Extend symname_hash_search with hash table select
Previously symname_hash_search can only search symbols from kernel's
symname_hash. This patch add hash table pointer as parameter for
symname_hash_search. Thus symname_hash_search can be used both for
symname_hash and mod_symname_hash searching.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 14 +++++++-------
1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/symbols.c b/symbols.c
index 92c066a..9373291 100644
--- a/symbols.c
+++ b/symbols.c
@@ -65,7 +65,7 @@ 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 struct syment *symname_hash_search(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 *);
@@ -1242,11 +1242,11 @@ mod_symtable_hash_remove_range(struct syment *from, struct syment
*to)
* Static kernel symbol value search
*/
static struct syment *
-symname_hash_search(char *name)
+symname_hash_search(struct syment *table[], char *name)
{
struct syment *sp;
- sp = st->symname_hash[SYMNAME_HASH_INDEX(name)];
+ sp = table[SYMNAME_HASH_INDEX(name)];
while (sp) {
if (STREQ(sp->name, name))
@@ -4579,7 +4579,7 @@ symbol_search(char *s)
{
struct syment *sp_hashed, *sp;
- sp_hashed = symname_hash_search(s);
+ sp_hashed = symname_hash_search(st->symname_hash, s);
for (sp = sp_hashed ? sp_hashed : st->symtable; sp < st->symend; sp++)
{
if (STREQ(s, sp->name))
@@ -5493,7 +5493,7 @@ symbol_exists(char *symbol)
struct syment *sp, *sp_end;
struct load_module *lm;
- if ((sp = symname_hash_search(symbol)))
+ if ((sp = symname_hash_search(st->symname_hash, symbol)))
return TRUE;
for (i = 0; i < st->mods_installed; i++) {
@@ -5572,7 +5572,7 @@ kernel_symbol_exists(char *symbol)
{
struct syment *sp;
- if ((sp = symname_hash_search(symbol)))
+ if ((sp = symname_hash_search(st->symname_hash, symbol)))
return TRUE;
else
return FALSE;
@@ -5584,7 +5584,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);
}
/*
--
2.29.2
9:13 a.m.
New subject: [PATCH v5 4/6] Intergrate symbol_exists with mod_symname_hash search
This patch introduces mod_symname_hash search to symbol_exists
to improve its performance. And code refactoring for
kernel_symbol_exists.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
Reviewed-by: Philipp Rudo <prudo(a)redhat.com>
---
symbols.c | 35 ++++-------------------------------
1 file changed, 4 insertions(+), 31 deletions(-)
diff --git a/symbols.c b/symbols.c
index 9373291..0a8e614 100644
--- a/symbols.c
+++ b/symbols.c
@@ -5489,33 +5489,11 @@ value_symbol(ulong value)
int
symbol_exists(char *symbol)
{
- int i;
- struct syment *sp, *sp_end;
- struct load_module *lm;
-
- if ((sp = symname_hash_search(st->symname_hash, symbol)))
+ if (symname_hash_search(st->symname_hash, symbol))
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 (symname_hash_search(st->mod_symname_hash, symbol))
+ return TRUE;
return(FALSE);
}
@@ -5570,12 +5548,7 @@ per_cpu_symbol_search(char *symbol)
int
kernel_symbol_exists(char *symbol)
{
- struct syment *sp;
-
- if ((sp = symname_hash_search(st->symname_hash, symbol)))
- return TRUE;
- else
- return FALSE;
+ return !!symname_hash_search(st->symname_hash, symbol);
}
/*
--
2.29.2
9:13 a.m.
New subject: [PATCH v5 5/6] Sync module symbols into mod_symtable whenever module symbols change
Signed-off-by: Tao Liu <ltao(a)redhat.com>
Reviewed-by: Philipp Rudo <prudo(a)redhat.com>
---
kernel.c | 1 +
symbols.c | 9 +++++++++
2 files changed, 10 insertions(+)
diff --git a/kernel.c b/kernel.c
index 3ead4bb..f10b8b2 100644
--- a/kernel.c
+++ b/kernel.c
@@ -4661,6 +4661,7 @@ reinit_modules(void)
st->ext_module_symtable = NULL;
st->load_modules = NULL;
kt->mods_installed = 0;
+ memset(st->mod_symname_hash, 0, sizeof(st->mod_symname_hash));
module_init();
}
diff --git a/symbols.c b/symbols.c
index 0a8e614..b62be1b 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1676,6 +1676,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;
@@ -2156,6 +2157,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;
@@ -12486,8 +12489,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;
@@ -12517,6 +12522,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,
@@ -12526,6 +12532,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;
@@ -12554,6 +12561,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,
@@ -12563,6 +12571,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
9:13 a.m.
New subject: [PATCH v5 6/6] Refactor SYMNAME_HASH_INDEX macro to be a function
SYMNAME_HASH_INDEX is used as the index of symname hash table. It will
be out of range if SYMNAME_HASH_INDEX is negative. This patch avoids
the risk by changing the marco into a function, and casting and calculating
the numbers as unsigned.
Suggested-by: Lianbo Jiang <lijiang(a)redhat.com>
Suggested-by: Philipp Rudo <prudo(a)redhat.com>
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 2 --
symbols.c | 31 +++++++++++++++++++++++--------
2 files changed, 23 insertions(+), 10 deletions(-)
diff --git a/defs.h b/defs.h
index bbdca79..8b356d5 100644
--- a/defs.h
+++ b/defs.h
@@ -2728,8 +2728,6 @@ struct downsized {
(((vaddr) >> machdep->pageshift) % SYMVAL_HASH)
#define SYMNAME_HASH (512)
-#define SYMNAME_HASH_INDEX(name) \
- ((name[0] ^ (name[strlen(name)-1] * name[strlen(name)/2])) % SYMNAME_HASH)
#define PATCH_KERNEL_SYMBOLS_START ((char *)(1))
#define PATCH_KERNEL_SYMBOLS_STOP ((char *)(2))
diff --git a/symbols.c b/symbols.c
index b62be1b..fc0e9f6 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1127,6 +1127,21 @@ symname_hash_init(void)
st->__per_cpu_end = sp->value;
}
+static unsigned int
+symname_hash_index(char *name)
+{
+ unsigned int len, value;
+ unsigned char *array = (unsigned char *)name;
+
+ len = strlen(name);
+ if (!len)
+ error(FATAL, "The length of the symbol name is zero!\n");
+
+ value = array[len - 1] * array[len / 2];
+
+ return (array[0] ^ value) % SYMNAME_HASH;
+}
+
/*
* Install a single static kernel symbol into the symname_hash.
*/
@@ -1134,9 +1149,9 @@ static void
symname_hash_install(struct syment *spn)
{
struct syment *sp;
- int index;
+ unsigned int index;
- index = SYMNAME_HASH_INDEX(spn->name);
+ index = symname_hash_index(spn->name);
spn->cnt = 1;
if ((sp = st->symname_hash[index]) == NULL)
@@ -1164,12 +1179,12 @@ static void
mod_symname_hash_install(struct syment *spn)
{
struct syment *sp, *tmp;
- int index;
+ unsigned int index;
if (!spn)
return;
- index = SYMNAME_HASH_INDEX(spn->name);
+ index = symname_hash_index(spn->name);
sp = st->mod_symname_hash[index];
@@ -1204,12 +1219,12 @@ static void
mod_symname_hash_remove(struct syment *spn)
{
struct syment *sp;
- int index;
+ unsigned int index;
if (!spn)
return;
- index = SYMNAME_HASH_INDEX(spn->name);
+ index = symname_hash_index(spn->name);
if (st->mod_symname_hash[index] == spn)
st->mod_symname_hash[index] = spn->name_hash_next;
@@ -1246,7 +1261,7 @@ symname_hash_search(struct syment *table[], char *name)
{
struct syment *sp;
- sp = table[SYMNAME_HASH_INDEX(name)];
+ sp = table[symname_hash_index(name)];
while (sp) {
if (STREQ(sp->name, name))
@@ -4589,7 +4604,7 @@ symbol_search(char *s)
return(sp);
}
- sp = st->mod_symname_hash[SYMNAME_HASH_INDEX(s)];
+ sp = st->mod_symname_hash[symname_hash_index(s)];
while (sp) {
if (skip_symbols(sp, s)) {
sp = sp->name_hash_next;
--
2.29.2
9:12 p.m.
Hi Tao Liu,
One more comment, the mod_syment_hash also should be printed by help -s,
like symname_hash.
crash> set debug 1
debug: 1
crash> help -s
...
val_hash_iterations: 530 (avg: 75.7)
symname_hash[512]: ff7808
[ 0]: 57 [ 1]: 121 [ 2]: 28 [ 3]: 79 [ 4]: 165 [ 5]: 51
[ 6]: 57 [ 7]: 99 [ 8]: 61 [ 9]: 98 [ 10]: 108 [ 11]: 68
The other patches (2 to 6) look good to me.
Thanks,
Kazu
-----Original Message-----
Currently the sequence for symbol_search to search 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. This patch introduces
a symname hash table for kernel modules, to improve the performance of symbol
searching.
Functions symbol_search and symbol_exists are fundamental and widely used by
other crash functions, thus the benefit of performance improvement can
get accumulated. For example, "ps -m" and "irq" commands, which call
the functions many times, will become faster with the patch.
v4 -> v5:
1) Seperated kernel modules syment install from kernel syment install,
making them 2 independent functions. Thus kernel modules syment can get sorted
when installed into mod_syment_hash. And spn->cnt stays untouched in v5.
2) Removed syment_is_installed check, it is no longer needed for the new
kernel modules syment install function.
3) Splitted the patches into smaller ones for better patch review.
4) Changed SYMNAME_HASH_INDEX macro into symname_hash_index function.
5) v5 patch can be applied to master branch, for crash-7-branch it needs
slightly modification.
Tao Liu (6):
Implement install and remove operations for mod_symname_hash
Integrate symbol_search with mod_symname_hash search
Extend symname_hash_search with hash table select
Intergrate symbol_exists with mod_symname_hash search
Sync module symbols into mod_symtable whenever module symbols change
Refactor SYMNAME_HASH_INDEX macro to be a function
defs.h | 3 +-
kernel.c | 1 +
symbols.c | 212 ++++++++++++++++++++++++++++++++++--------------------
3 files changed, 137 insertions(+), 79 deletions(-)
--
2.29.2
10:07 p.m.
Hi Kazu,
On Fri, Oct 15, 2021 at 10:12 AM HAGIO KAZUHITO(萩尾 一仁)
<k-hagio-ab(a)nec.com> wrote:
Hi Tao Liu,
One more comment, the mod_syment_hash also should be printed by help -s,
like symname_hash.
crash> set debug 1
debug: 1
crash> help -s
...
val_hash_iterations: 530 (avg: 75.7)
symname_hash[512]: ff7808
[ 0]: 57 [ 1]: 121 [ 2]: 28 [ 3]: 79 [ 4]: 165 [ 5]: 51
[ 6]: 57 [ 7]: 99 [ 8]: 61 [ 9]: 98 [ 10]: 108 [ 11]: 68
Thanks for pointing this out. I will implement code for it.
The other patches (2 to 6) look good to me.
Thanks for reviewing the patch, I will get it improved for the v6 patch.
Thanks,
Tao Liu
Thanks,
Kazu
-----Original Message-----
> Currently the sequence for symbol_search to search 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. This patch introduces
> a symname hash table for kernel modules, to improve the performance of symbol
> searching.
>
> Functions symbol_search and symbol_exists are fundamental and widely used by
> other crash functions, thus the benefit of performance improvement can
> get accumulated. For example, "ps -m" and "irq" commands, which
call
> the functions many times, will become faster with the patch.
>
> v4 -> v5:
>
> 1) Seperated kernel modules syment install from kernel syment install,
> making them 2 independent functions. Thus kernel modules syment can get sorted
> when installed into mod_syment_hash. And spn->cnt stays untouched in v5.
> 2) Removed syment_is_installed check, it is no longer needed for the new
> kernel modules syment install function.
> 3) Splitted the patches into smaller ones for better patch review.
> 4) Changed SYMNAME_HASH_INDEX macro into symname_hash_index function.
> 5) v5 patch can be applied to master branch, for crash-7-branch it needs
> slightly modification.
>
> Tao Liu (6):
> Implement install and remove operations for mod_symname_hash
> Integrate symbol_search with mod_symname_hash search
> Extend symname_hash_search with hash table select
> Intergrate symbol_exists with mod_symname_hash search
> Sync module symbols into mod_symtable whenever module symbols change
> Refactor SYMNAME_HASH_INDEX macro to be a function
>
> defs.h | 3 +-
> kernel.c | 1 +
> symbols.c | 212 ++++++++++++++++++++++++++++++++++--------------------
> 3 files changed, 137 insertions(+), 79 deletions(-)
>
> --
> 2.29.2
1137
days inactive
1142
days old
devel@lists.crash-utility.osci.io
11 comments
2 participants
participants (2)
-
HAGIO KAZUHITO(萩尾 一仁) -
Tao Liu