[PATCH 1/3] modprobe: use hash table for module entry database

Timo Teräs timo.teras at iki.fi
Sat Jun 18 15:56:46 UTC 2011


We get a lot of entries there, and lookups are done many, many
times. This gives a significant performance improvement.

Signed-off-by: Timo Teräs <timo.teras at iki.fi>
---
 modutils/modprobe.c |   13 ++++++++++---
 1 files changed, 10 insertions(+), 3 deletions(-)

diff --git a/modutils/modprobe.c b/modutils/modprobe.c
index 678f4be..b3767ac 100644
--- a/modutils/modprobe.c
+++ b/modutils/modprobe.c
@@ -157,8 +157,10 @@ 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 *db[DB_HASH_SIZE]; /* 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;
@@ -195,9 +197,14 @@ 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 int hash = 5381, i;
 
 	filename2modname(module, modname);
-	for (l = G.db; l != NULL; l = l->link) {
+	for (i = 0; modname[i]; i++)
+		hash = ((hash << 5) + hash) + modname[i];
+	hash %= DB_HASH_SIZE;
+
+	for (l = G.db[hash]; l != NULL; l = l->link) {
 		e = (struct module_entry *) l->data;
 		if (strcmp(e->modname, modname) == 0)
 			return e;
@@ -207,7 +214,7 @@ 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;
 }
-- 
1.7.1



More information about the busybox mailing list