From e12e0acb92329f95a77121f489b491d84b6a2c33 Mon Sep 17 00:00:00 2001 From: Timo Teras Date: Mon, 20 Jun 2011 09:38:13 +0200 Subject: modprobe: use hash table. speeds up significantly if modprobe.dep is large function old new delta helper_get_module 106 157 +51 config_file_action 413 431 +18 modprobe_main 690 706 +16 do_modprobe 580 588 +8 add_probe 81 83 +2 load_modules_dep 192 190 -2 get_or_add_modentry 10 - -10 ------------------------------------------------------------------------------ (add/remove: 0/1 grow/shrink: 5/1 up/down: 95/-12) Total: 83 bytes Signed-off-by: Timo Teras Signed-off-by: Denys Vlasenko --- modutils/modprobe.c | 43 +++++++++++++++++++++++++++++-------------- 1 file changed, 29 insertions(+), 14 deletions(-) (limited to 'modutils/modprobe.c') diff --git a/modutils/modprobe.c b/modutils/modprobe.c index 678f4be..c1a1828 100644 --- a/modutils/modprobe.c +++ b/modutils/modprobe.c @@ -157,20 +157,21 @@ struct module_entry { /* I'll call it ME. */ llist_t *deps; /* strings. modules we depend on */ }; +#define DB_HASH_SIZE 256 + struct globals { - llist_t *db; /* MEs of all modules ever seen (caching for speed) */ llist_t *probes; /* MEs of module(s) requested on cmdline */ char *cmdline_mopts; /* module options from cmdline */ int num_unresolved_deps; /* bool. "Did we have 'symbol:FOO' requested on cmdline?" */ smallint need_symbols; struct utsname uts; + llist_t *db[DB_HASH_SIZE]; /* MEs of all modules ever seen (caching for speed) */ } FIX_ALIASING; -#define G (*(struct globals*)&bb_common_bufsiz1) -#define INIT_G() do { } while (0) -struct BUG_G_too_big { - char BUG_G_too_big[sizeof(G) <= COMMON_BUFSIZE ? 1 : -1]; -}; +#define G (*ptr_to_globals) +#define INIT_G() do { \ + SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \ +} while (0) static int read_config(const char *path); @@ -190,14 +191,26 @@ static char *gather_options_str(char *opts, const char *append) return opts; } +/* These three functions called many times, optimizing for speed. + * Users reported minute-long delays when they runn iptables repeatedly + * (iptables use modprobe to install needed kernel modules). + */ static struct module_entry *helper_get_module(const char *module, int create) { char modname[MODULE_NAME_LEN]; struct module_entry *e; llist_t *l; + unsigned i; + unsigned hash; filename2modname(module, modname); - for (l = G.db; l != NULL; l = l->link) { + + hash = 0; + for (i = 0; modname[i]; i++) + hash = ((hash << 5) + hash) + modname[i]; + hash %= DB_HASH_SIZE; + + for (l = G.db[hash]; l; l = l->link) { e = (struct module_entry *) l->data; if (strcmp(e->modname, modname) == 0) return e; @@ -207,15 +220,15 @@ static struct module_entry *helper_get_module(const char *module, int create) e = xzalloc(sizeof(*e)); e->modname = xstrdup(modname); - llist_add_to(&G.db, e); + llist_add_to(&G.db[hash], e); return e; } -static struct module_entry *get_or_add_modentry(const char *module) +static ALWAYS_INLINE struct module_entry *get_or_add_modentry(const char *module) { return helper_get_module(module, 1); } -static struct module_entry *get_modentry(const char *module) +static ALWAYS_INLINE struct module_entry *get_modentry(const char *module) { return helper_get_module(module, 0); } @@ -275,7 +288,7 @@ static int FAST_FUNC config_file_action(const char *filename, continue; filename2modname(tokens[1], wildcard); - for (l = G.probes; l != NULL; l = l->link) { + for (l = G.probes; l; l = l->link) { m = (struct module_entry *) l->data; if (fnmatch(wildcard, m->modname, 0) != 0) continue; @@ -377,7 +390,6 @@ static char *parse_and_add_kcmdline_module_options(char *options, const char *mo static int do_modprobe(struct module_entry *m) { int rc, first; - llist_t *l; if (!(m->flags & MODULE_FLAG_FOUND_IN_MODDEP)) { if (!(option_mask32 & INSMOD_OPT_SILENT)) @@ -390,8 +402,11 @@ static int do_modprobe(struct module_entry *m) if (!(option_mask32 & OPT_REMOVE)) m->deps = llist_rev(m->deps); - for (l = m->deps; l != NULL; l = l->link) - DBG("dep: %s", l->data); + if (0) { + llist_t *l; + for (l = m->deps; l; l = l->link) + DBG("dep: %s", l->data); + } first = 1; rc = 0; -- cgit v1.1