4:01 a.m.
This patch set improves symbol_search/symbol_exists performance by introducing hash
table for kernel modules symbols.
v2 -> v3:
1) Seperate v2 patch into multiple patches.
2) Several code indented formatting.
3) Moved "if (sp != NULL)" check from mod_symtable_hash_install/remove_range
into symname_hash_install/remove, and shorten it to be "if (!sp)" check.
4) Replaced "index = index > 0 ? index : -index;" into abs() in
SYMNAME_HASH_INDEX macro.
5) Replaced the code of remove hash table elements in symname_hash_remove with
Kazu's version, and variable "tmp" of v2 patch get removed.
6) Removed "first_encounter" check in symname_hash_remove.
7) Add assert check in symname_hash_install.
Tao Liu (4):
Improve the performance of symbol searching for kernel modules
Get the absolute value of SYMNAME_HASH_INDEX
Set name_hash_next field to be NULL for the newly installed elements
Add assert check if an element is installed one more time
defs.h | 3 +-
kernel.c | 1 +
symbols.c | 170 +++++++++++++++++++++++++++++-------------------------
3 files changed, 95 insertions(+), 79 deletions(-)
--
2.29.2
4:01 a.m.
New subject: [PATCH v3 1/4] Improve the performance of symbol searching for kernel modules
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.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 1 +
kernel.c | 1 +
symbols.c | 167 +++++++++++++++++++++++++++++-------------------------
3 files changed, 91 insertions(+), 78 deletions(-)
diff --git a/defs.h b/defs.h
index eb1c71b..c10ebff 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 b2c8a0c..307eeee 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..44415da 100644
--- a/symbols.c
+++ b/symbols.c
@@ -64,8 +64,10 @@ 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 +1121,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 +1129,42 @@ 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++)
+ 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++)
+ 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;
+ if (!spn)
+ return;
+
index = SYMNAME_HASH_INDEX(spn->name);
spn->cnt = 1;
- if ((sp = st->symname_hash[index]) == NULL)
- st->symname_hash[index] = spn;
- else {
+ if ((sp = table[index]) == NULL) {
+ table[index] = spn;
+ } else {
while (sp) {
if (STREQ(sp->name, spn->name)) {
sp->cnt++;
@@ -1157,17 +1180,47 @@ symname_hash_install(struct syment *spn)
}
}
+static void
+symname_hash_remove(struct syment *table[], struct syment *spn)
+{
+ struct syment *sp;
+ int index;
+
+ if (!spn)
+ return;
+
+ index = SYMNAME_HASH_INDEX(spn->name);
+
+ 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;
+ }
+}
+
/*
* 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);
+ 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 +1648,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 +2129,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 +4538,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 = 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.
@@ -4494,53 +4561,14 @@ symbol_search(char *s)
struct load_module *lm;
int pseudos, search_init;
- 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);
}
/*
@@ -5436,29 +5464,11 @@ symbol_exists(char *symbol)
struct syment *sp, *sp_end;
struct load_module *lm;
- if ((sp = symname_hash_search(symbol)))
+ if (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 (symname_hash_search(st->mod_symname_hash, symbol, NULL))
+ return TRUE;
return(FALSE);
}
@@ -5513,12 +5523,7 @@ per_cpu_symbol_search(char *symbol)
int
kernel_symbol_exists(char *symbol)
{
- struct syment *sp;
-
- if ((sp = symname_hash_search(symbol)))
- return TRUE;
- else
- return FALSE;
+ return !!(symname_hash_search(st->symname_hash, symbol, NULL));
}
/*
@@ -5527,7 +5532,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 +12469,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 +12502,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 +12512,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 +12541,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 +12551,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
3:59 a.m.
New subject: [PATCH v3 1/4] Improve the performance of symbol searching for kernel modules
Hi Tao,
On Tue, 14 Sep 2021 17:01:51 +0800
Tao Liu <ltao(a)redhat.com> wrote:
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.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 1 +
kernel.c | 1 +
symbols.c | 167 +++++++++++++++++++++++++++++-------------------------
3 files changed, 91 insertions(+), 78 deletions(-)
[...]
diff --git a/symbols.c b/symbols.c
index bf6d94d..44415da 100644
--- a/symbols.c
+++ b/symbols.c
[...]
@@ -4494,53 +4561,14 @@ symbol_search(char *s)
struct load_module *lm;
int pseudos, search_init;
with big parts of the function removed some variables are no longer
used. Please remove their declaration.
- 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);
}
/*
@@ -5436,29 +5464,11 @@ symbol_exists(char *symbol)
struct syment *sp, *sp_end;
struct load_module *lm;
same like above.
Thanks
Philipp
- if ((sp = symname_hash_search(symbol)))
+ if (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 (symname_hash_search(st->mod_symname_hash, symbol, NULL))
+ return TRUE;
return(FALSE);
}
@@ -5513,12 +5523,7 @@ per_cpu_symbol_search(char *symbol)
int
kernel_symbol_exists(char *symbol)
{
- struct syment *sp;
-
- if ((sp = symname_hash_search(symbol)))
- return TRUE;
- else
- return FALSE;
+ return !!(symname_hash_search(st->symname_hash, symbol, NULL));
}
/*
@@ -5527,7 +5532,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 +12469,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 +12502,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 +12512,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 +12541,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 +12551,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;
8:24 p.m.
New subject: [PATCH v3 1/4] Improve the performance of symbol searching for kernel modules
Hi Philipp,
On Fri, Sep 17, 2021 at 5:00 PM Philipp Rudo <prudo(a)redhat.com> wrote:
Hi Tao,
On Tue, 14 Sep 2021 17:01:51 +0800
Tao Liu <ltao(a)redhat.com> wrote:
> 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.
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> defs.h | 1 +
> kernel.c | 1 +
> symbols.c | 167 +++++++++++++++++++++++++++++-------------------------
> 3 files changed, 91 insertions(+), 78 deletions(-)
[...]
> diff --git a/symbols.c b/symbols.c
> index bf6d94d..44415da 100644
> --- a/symbols.c
> +++ b/symbols.c
[...]
> @@ -4494,53 +4561,14 @@ symbol_search(char *s)
> struct load_module *lm;
> int pseudos, search_init;
with big parts of the function removed some variables are no longer
used. Please remove their declaration.
Sure, thanks for pointing it out.
> - 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);
> }
>
> /*
> @@ -5436,29 +5464,11 @@ symbol_exists(char *symbol)
> struct syment *sp, *sp_end;
> struct load_module *lm;
same like above.
Thanks
Philipp
Thanks,
Tao Liu
> - if ((sp = symname_hash_search(symbol)))
> + if (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 (symname_hash_search(st->mod_symname_hash, symbol, NULL))
> + return TRUE;
>
> return(FALSE);
> }
> @@ -5513,12 +5523,7 @@ per_cpu_symbol_search(char *symbol)
> int
> kernel_symbol_exists(char *symbol)
> {
> - struct syment *sp;
> -
> - if ((sp = symname_hash_search(symbol)))
> - return TRUE;
> - else
> - return FALSE;
> + return !!(symname_hash_search(st->symname_hash, symbol, NULL));
> }
>
> /*
> @@ -5527,7 +5532,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 +12469,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 +12502,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 +12512,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 +12541,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 +12551,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;
4:01 a.m.
New subject: [PATCH v3 2/4] Get the absolute value of SYMNAME_HASH_INDEX
SYMNAME_HASH_INDEX is used as the index of symname hash table. It will
be out of range if SYMNAME_HASH_INDEX is negative. Let's get its absolute
value to avoid such risk.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
defs.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/defs.h b/defs.h
index c10ebff..3129f06 100644
--- a/defs.h
+++ b/defs.h
@@ -2725,7 +2725,7 @@ struct downsized {
#define SYMNAME_HASH (512)
#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))
#define PATCH_KERNEL_SYMBOLS_START ((char *)(1))
#define PATCH_KERNEL_SYMBOLS_STOP ((char *)(2))
--
2.29.2
4:01 a.m.
New subject: [PATCH v3 3/4] Set name_hash_next field to be NULL for the newly installed elements
The newly installed element may contain junk data in the name_hash_next
field. If it does, it will corrupt the hash table. Thus name_hash_next
field should be set to NULL when the element is installed successfully
into the hash table.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 2 ++
1 file changed, 2 insertions(+)
diff --git a/symbols.c b/symbols.c
index 44415da..f8b4998 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1164,6 +1164,7 @@ symname_hash_install(struct syment *table[], struct syment *spn)
if ((sp = table[index]) == NULL) {
table[index] = spn;
+ spn->name_hash_next = NULL;
} else {
while (sp) {
if (STREQ(sp->name, spn->name)) {
@@ -1174,6 +1175,7 @@ symname_hash_install(struct syment *table[], struct syment *spn)
sp = sp->name_hash_next;
else {
sp->name_hash_next = spn;
+ spn->name_hash_next = NULL;
break;
}
}
--
2.29.2
4:01 a.m.
New subject: [PATCH v3 4/4] Add assert check if an element is installed one more time
symname_hash_install won't check if spn has been installed before. If
it does, the second install will corrupt the hash table as well as
spn->cnt counting. It should never happen in normal cases, but we need
get notified if it happens.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 1 +
1 file changed, 1 insertion(+)
diff --git a/symbols.c b/symbols.c
index f8b4998..a453a6a 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1167,6 +1167,7 @@ symname_hash_install(struct syment *table[], struct syment *spn)
spn->name_hash_next = NULL;
} else {
while (sp) {
+ assert(sp != spn);
if (STREQ(sp->name, spn->name)) {
sp->cnt++;
spn->cnt++;
--
2.29.2
4:09 a.m.
New subject: [PATCH v3 4/4] Add assert check if an element is installed one more time
Hi Tao,
On Tue, 14 Sep 2021 17:01:54 +0800
Tao Liu <ltao(a)redhat.com> wrote:
symname_hash_install won't check if spn has been installed
before. If
it does, the second install will corrupt the hash table as well as
spn->cnt counting. It should never happen in normal cases, but we need
get notified if it happens.
Signed-off-by: Tao Liu <ltao(a)redhat.com>
---
symbols.c | 1 +
1 file changed, 1 insertion(+)
diff --git a/symbols.c b/symbols.c
index f8b4998..a453a6a 100644
--- a/symbols.c
+++ b/symbols.c
@@ -1167,6 +1167,7 @@ symname_hash_install(struct syment *table[], struct syment *spn)
spn->name_hash_next = NULL;
} else {
while (sp) {
+ assert(sp != spn);
the change makes totally sense. Although I'm not sure if the 'assert'
isn't too strict. In my opinion printing a warning + ignoring the
duplicate symbol would be better.
In my opinion an 'assert' should only be used, in situations a program
cannot be recovered from. But for the case when a symbol is added twice
we can 'recover' from by simply ignoring the second request.
Thanks
Philipp
if (STREQ(sp->name, spn->name)) {
sp->cnt++;
spn->cnt++;
1:36 a.m.
New subject: [PATCH v3 4/4] Add assert check if an element is installed one more time
On Fri, Sep 17, 2021 at 5:09 PM Philipp Rudo <prudo(a)redhat.com> wrote:
Hi Tao,
On Tue, 14 Sep 2021 17:01:54 +0800
Tao Liu <ltao(a)redhat.com> wrote:
> symname_hash_install won't check if spn has been installed before. If
> it does, the second install will corrupt the hash table as well as
> spn->cnt counting. It should never happen in normal cases, but we need
> get notified if it happens.
>
> Signed-off-by: Tao Liu <ltao(a)redhat.com>
> ---
> symbols.c | 1 +
> 1 file changed, 1 insertion(+)
>
> diff --git a/symbols.c b/symbols.c
> index f8b4998..a453a6a 100644
> --- a/symbols.c
> +++ b/symbols.c
> @@ -1167,6 +1167,7 @@ symname_hash_install(struct syment *table[], struct syment
*spn)
> spn->name_hash_next = NULL;
> } else {
> while (sp) {
> + assert(sp != spn);
the change makes totally sense. Although I'm not sure if the 'assert'
isn't too strict. In my opinion printing a warning + ignoring the
duplicate symbol would be better.
In my opinion an 'assert' should only be used, in situations a program
cannot be recovered from. But for the case when a symbol is added twice
we can 'recover' from by simply ignoring the second request.
OK. I will replace it with a function which can check if spn exists in
the hashtable.
Thanks,
Tao Liu
Thanks
Philipp
> if (STREQ(sp->name, spn->name)) {
> sp->cnt++;
> spn->cnt++;
4:15 a.m.
Hi Tao,
thanks, v3 is almost perfect. The only thing you should do in patch 1
is to cleanup some unused variable declarations. With that fixed you
can add my
Reviewed-by: Philipp Rudo <prudo(a)redhat.com>
to the first three patches.
All in all the last patch is fine too. I only think that the 'assert'
is too strict and it would be better to replace it by a warning +
continue.
Thanks
Philipp
On Tue, 14 Sep 2021 17:01:50 +0800
Tao Liu <ltao(a)redhat.com> wrote:
This patch set improves symbol_search/symbol_exists performance by
introducing hash
table for kernel modules symbols.
v2 -> v3:
1) Seperate v2 patch into multiple patches.
2) Several code indented formatting.
3) Moved "if (sp != NULL)" check from mod_symtable_hash_install/remove_range
into symname_hash_install/remove, and shorten it to be "if (!sp)" check.
4) Replaced "index = index > 0 ? index : -index;" into abs() in
SYMNAME_HASH_INDEX macro.
5) Replaced the code of remove hash table elements in symname_hash_remove with
Kazu's version, and variable "tmp" of v2 patch get removed.
6) Removed "first_encounter" check in symname_hash_remove.
7) Add assert check in symname_hash_install.
Tao Liu (4):
Improve the performance of symbol searching for kernel modules
Get the absolute value of SYMNAME_HASH_INDEX
Set name_hash_next field to be NULL for the newly installed elements
Add assert check if an element is installed one more time
defs.h | 3 +-
kernel.c | 1 +
symbols.c | 170 +++++++++++++++++++++++++++++-------------------------
3 files changed, 95 insertions(+), 79 deletions(-)
1:40 a.m.
Hi Philipp,
On Fri, Sep 17, 2021 at 5:15 PM Philipp Rudo <prudo(a)redhat.com> wrote:
Hi Tao,
thanks, v3 is almost perfect. The only thing you should do in patch 1
is to cleanup some unused variable declarations. With that fixed you
can add my
Reviewed-by: Philipp Rudo <prudo(a)redhat.com>
to the first three patches.
OK, I will add your Reviewed-by sign, thanks again for reviewing the patch!
All in all the last patch is fine too. I only think that the
'assert'
is too strict and it would be better to replace it by a warning +
continue.
Yeah, I will get it improved and send out the v4 patch.
Thanks,
Tao Liu
Thanks
Philipp
On Tue, 14 Sep 2021 17:01:50 +0800
Tao Liu <ltao(a)redhat.com> wrote:
> This patch set improves symbol_search/symbol_exists performance by introducing hash
> table for kernel modules symbols.
>
> v2 -> v3:
>
> 1) Seperate v2 patch into multiple patches.
> 2) Several code indented formatting.
> 3) Moved "if (sp != NULL)" check from
mod_symtable_hash_install/remove_range
> into symname_hash_install/remove, and shorten it to be "if (!sp)"
check.
> 4) Replaced "index = index > 0 ? index : -index;" into abs() in
> SYMNAME_HASH_INDEX macro.
> 5) Replaced the code of remove hash table elements in symname_hash_remove with
> Kazu's version, and variable "tmp" of v2 patch get removed.
> 6) Removed "first_encounter" check in symname_hash_remove.
> 7) Add assert check in symname_hash_install.
>
> Tao Liu (4):
> Improve the performance of symbol searching for kernel modules
> Get the absolute value of SYMNAME_HASH_INDEX
> Set name_hash_next field to be NULL for the newly installed elements
> Add assert check if an element is installed one more time
>
> defs.h | 3 +-
> kernel.c | 1 +
> symbols.c | 170 +++++++++++++++++++++++++++++-------------------------
> 3 files changed, 95 insertions(+), 79 deletions(-)
>
1196
days inactive
1200
days old
devel@lists.crash-utility.osci.io
10 comments
2 participants
participants (2)
-
Philipp Rudo -
Tao Liu