Re: [PATCH v2] Improve the performance of symbol searching for kernel modules

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Hi Tao Liu,

-----Original Message-----
> Currently the sequence for crash searching 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)

Just to clarify, which parts of code are meant by the stage 1 and 2?

Do you have a result with the patch?

> 
> stage 3 takes too much time when comparing to stage 1. So let's introduce a
> symname hash table for kernel modules to improve the performance of symbol
> searching.

I see that 3) is relatively time-consuming, but I have not had a delay
due to the symbol search.  Which command did you observe a delay?

Thanks,
Kazu


> 
> Signed-off-by: Tao Liu <ltao@xxxxxxxxxx>
> ---
> v1 -> v2:
> - Removed unused variables within the modified functions.
> 
> ---
>  defs.h    |   1 +
>  kernel.c  |   1 +
>  symbols.c | 189 +++++++++++++++++++++++++++++++-----------------------
>  3 files changed, 111 insertions(+), 80 deletions(-)
> 
> diff --git a/defs.h b/defs.h
> index eb1c71b..58b8546 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 36fdea2..c56cc34 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..9b64734 100644
> --- a/symbols.c
> +++ b/symbols.c
> @@ -64,8 +64,9 @@ 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 +1120,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 +1128,48 @@ 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++) {
> +		if (sp != NULL) {
> +			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++) {
> +		if (sp != NULL) {
> +			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;
> 
>          index = SYMNAME_HASH_INDEX(spn->name);
> +	index = index > 0 ? index : -index;
> +
>  	spn->cnt = 1;
> 
> -        if ((sp = st->symname_hash[index]) == NULL)
> -        	st->symname_hash[index] = spn;
> -	else {
> +        if ((sp = table[index]) == NULL) {
> +		table[index] = spn;
> +		spn->name_hash_next = NULL;
> +	} else {
>  		while (sp) {
>  	        	if (STREQ(sp->name, spn->name)) {
>  	                	sp->cnt++;
> @@ -1151,23 +1179,67 @@ symname_hash_install(struct syment *spn)
>  				sp = sp->name_hash_next;
>  			else {
>  				sp->name_hash_next = spn;
> +				spn->name_hash_next = NULL;
>  				break;
>  			}
>  		}
>  	}
>  }
> 
> +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;
> +	}
> +}
> +
>  /*
>   *  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);
> +	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;
> +}
> 
>  /*
>   *  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);
>  }
> @@ -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;
> @@ -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;
> --
> 2.29.2
> 
> --
> Crash-utility mailing list
> Crash-utility@xxxxxxxxxx
> https://listman.redhat.com/mailman/listinfo/crash-utility


--
Crash-utility mailing list
Crash-utility@xxxxxxxxxx
https://listman.redhat.com/mailman/listinfo/crash-utility




[Index of Archives]     [Fedora Development]     [Fedora Desktop]     [Fedora SELinux]     [Yosemite News]     [KDE Users]     [Fedora Tools]

 

Powered by Linux