[Crash-utility] [PATCH v3 1/4] Improve the performance of symbol searching for kernel modules
Tao Liu
ltao at redhat.com
Tue Sep 14 09:01:51 UTC 2021
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 at 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
More information about the Crash-utility
mailing list