[PATCH 19/27] modpost: use hlist for hash table implementation

From: Masahiro Yamada <masahiroy@kernel.org>
To: linux-kbuild@vger.kernel.org
Cc: linux-kernel@vger.kernel.org,
	Masahiro Yamada <masahiroy@kernel.org>,
	Michal Marek <michal.lkml@markovi.net>,
	Nick Desaulniers <ndesaulniers@google.com>
Subject: [PATCH 19/27] modpost: use hlist for hash table implementation
Date: Mon, 25 Apr 2022 04:08:03 +0900	[thread overview]
Message-ID: <20220424190811.1678416-20-masahiroy@kernel.org> (raw)
In-Reply-To: <20220424190811.1678416-1-masahiroy@kernel.org>

modpost has a simple hash table, which only supports the entry addition
(new_symbol), and search (find_symbol).

I want to have a macro to delete an entry from the hash table, and also
support multiple hash tables.

Instead of extending the own implementation, let's reuse hlist in list.h.
The code originates in included/linux/list.h, and looks familiar for
kernel developers.

I added 4 macros on top of the hlist utility macros:

 - hash_add_symbol

     add a symbol to the given hash table

 - hash_del_symbol

     delete a symbol from the given hash table

 - hash_for_matched_symbol

     traverse the hash table, stopping by the symbol whose name matches

 - hash_for_matched_symbol_safe

     like hash_for_each_symbol, but safe against node removal

While I was here, I increased the hash table size from 1024 to 8192
to decrease the hash collision. We have more and more exported symbols
these days.

I moved ARRAY_SIZE() from file2alias.c to modpost.h because it is needed
in modpost.c as well.

Signed-off-by: Masahiro Yamada <masahiroy@kernel.org>
---

 scripts/mod/file2alias.c |  2 --
 scripts/mod/modpost.c    | 54 +++++++++++++++++++++-------------------
 scripts/mod/modpost.h    |  2 ++
 3 files changed, 30 insertions(+), 28 deletions(-)

diff --git a/scripts/mod/file2alias.c b/scripts/mod/file2alias.c
index 5258247d78ac..e8a9c6816fec 100644
--- a/scripts/mod/file2alias.c
+++ b/scripts/mod/file2alias.c
@@ -734,8 +734,6 @@ static int do_vio_entry(const char *filename, void *symval,
 	return 1;
 }
 
-#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
-
 static void do_input(char *alias,
 		     kernel_ulong_t *arr, unsigned int min, unsigned int max)
 {
diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index fd710aa59bda..908390b4fa80 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -199,13 +199,8 @@ static struct module *new_module(const char *modname)
 	return mod;
 }
 
-/* A hash of all exported symbols,
- * struct symbol is also used for lists of unresolved symbols */
-
-#define SYMBOL_HASH_SIZE 1024
-
 struct symbol {
-	struct symbol *next;
+	struct hlist_node hash_node;
 	struct list_head list;
 	struct module *module;
 	unsigned int crc;
@@ -217,8 +212,6 @@ struct symbol {
 	char name[];
 };
 
-static struct symbol *symbolhash[SYMBOL_HASH_SIZE];
-
 /* This is based on the hash algorithm from gdbm, via tdb */
 static inline unsigned int tdb_hash(const char *name)
 {
@@ -232,38 +225,47 @@ static inline unsigned int tdb_hash(const char *name)
 	return (1103515243 * value + 12345);
 }
 
+/* useful hash macros */
+#define hash_head(table, key)		(&(table)[tdb_hash(key) % ARRAY_SIZE(table)])
+
+#define hash_add_symbol(sym, table)	hlist_add_head(&(sym)->hash_node, \
+						       hash_head(table, (sym)->name))
+
+#define hash_del_symbol(sym)		hlist_del_init(&(sym)->hash_node)
+
+#define hash_for_matched_symbol(sym, table, key) \
+	hlist_for_each_entry(sym, hash_head(table, key), hash_node) \
+		if (!strcmp(sym->name, key))
+
+#define hash_for_matched_symbol_safe(sym, n, table, key) \
+	hlist_for_each_entry_safe(sym, n, hash_head(table, key), hash_node) \
+		if (!strcmp(sym->name, key))
+
+#define HASHTABLE_DECLARE(name, size)	struct hlist_head name[size];
+
+/* hash table of all exported symbols */
+HASHTABLE_DECLARE(exported_symbols, 8192);
+
 /**
  * Allocate a new symbols for use in the hash of exported symbols or
  * the list of unresolved symbols per module
  **/
-static struct symbol *alloc_symbol(const char *name, struct symbol *next)
+static struct symbol *alloc_symbol(const char *name)
 {
 	struct symbol *s = NOFAIL(malloc(sizeof(*s) + strlen(name) + 1));
 
 	memset(s, 0, sizeof(*s));
 	strcpy(s->name, name);
-	s->next = next;
 
 	return s;
 }
 
-/* For the hash of exported symbols */
-static struct symbol *new_symbol(const char *name, struct module *module,
-				 enum export export)
-{
-	unsigned int hash;
-
-	hash = tdb_hash(name) % SYMBOL_HASH_SIZE;
-	symbolhash[hash] = alloc_symbol(name, symbolhash[hash]);
-
-	return symbolhash[hash];
-}
 
 static void sym_add_unresolved(const char *name, struct module *mod, bool weak)
 {
 	struct symbol *sym;
 
-	sym = alloc_symbol(name, NULL);
+	sym = alloc_symbol(name);
 	sym->weak = weak;
 
 	list_add_tail(&sym->list, &mod->unresolved_symbols);
@@ -277,9 +279,8 @@ static struct symbol *find_symbol(const char *name)
 	if (name[0] == '.')
 		name++;
 
-	for (s = symbolhash[tdb_hash(name) % SYMBOL_HASH_SIZE]; s; s = s->next) {
-		if (strcmp(s->name, name) == 0)
-			return s;
+	hash_for_matched_symbol(s, exported_symbols, name) {
+		return s;
 	}
 	return NULL;
 }
@@ -412,11 +413,12 @@ static void sym_add_exported(const char *name, struct module *mod,
 		      s->module->is_vmlinux ? "" : ".ko");
 	}
 
-	s = new_symbol(name, mod, export);
+	s = alloc_symbol(name);
 	s->module = mod;
 	s->is_static = !mod->from_dump;
 	s->export    = export;
 	list_add_tail(&s->list, &mod->exported_symbols);
+	hash_add_symbol(s, exported_symbols);
 }
 
 static void sym_set_crc(const char *name, unsigned int crc)
diff --git a/scripts/mod/modpost.h b/scripts/mod/modpost.h
index 5922b0c39bb7..7c6ece1957fc 100644
--- a/scripts/mod/modpost.h
+++ b/scripts/mod/modpost.h
@@ -14,6 +14,8 @@
 #include "list.h"
 #include "elfconfig.h"
 
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
 /* On BSD-alike OSes elf.h defines these according to host's word size */
 #undef ELF_ST_BIND
 #undef ELF_ST_TYPE
-- 
2.32.0

