All of lore.kernel.org
 help / color / mirror / Atom feed
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 v2 26/26] modpost: use hlist for hash table implementation
Date: Sun,  1 May 2022 17:40:32 +0900	[thread overview]
Message-ID: <20220501084032.1025918-27-masahiroy@kernel.org> (raw)
In-Reply-To: <20220501084032.1025918-1-masahiroy@kernel.org>

Import hlist macros from include/linux/list.h to implement the hash
table in a more generic way.

While I was here, I increased the hash table size from 1024 to 8192
to decrease the hash collision.

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>
---

Changes in v2:
  - Move to the end of the series because this is now optional

 scripts/mod/file2alias.c |  2 --
 scripts/mod/list.h       | 52 ++++++++++++++++++++++++++++++++++++++++
 scripts/mod/modpost.c    | 39 +++++++++++++++---------------
 scripts/mod/modpost.h    |  2 ++
 4 files changed, 73 insertions(+), 22 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/list.h b/scripts/mod/list.h
index a924a6c4aa4d..c60dbaa70d6b 100644
--- a/scripts/mod/list.h
+++ b/scripts/mod/list.h
@@ -210,4 +210,56 @@ static inline int list_empty(const struct list_head *head)
 	     !list_entry_is_head(pos, head, member);			\
 	     pos = n, n = list_next_entry(n, member))
 
+/*
+ * Double linked lists with a single pointer list head.
+ * Mostly useful for hash tables where the two pointer list head is
+ * too wasteful.
+ * You lose the ability to access the tail in O(1).
+ */
+
+struct hlist_head {
+	struct hlist_node *first;
+};
+
+struct hlist_node {
+	struct hlist_node *next, **pprev;
+};
+
+/**
+ * hlist_add_head - add a new entry at the beginning of the hlist
+ * @n: new entry to be added
+ * @h: hlist head to add it after
+ *
+ * Insert a new entry after the specified head.
+ * This is good for implementing stacks.
+ */
+static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
+{
+	struct hlist_node *first = h->first;
+
+	n->next = first;
+	if (first)
+		first->pprev = &n->next;
+	h->first = n;
+	n->pprev = &h->first;
+}
+
+#define hlist_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define hlist_entry_safe(ptr, type, member) \
+	({ typeof(ptr) ____ptr = (ptr); \
+	   ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
+	})
+
+/**
+ * hlist_for_each_entry	- iterate over list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the hlist_node within the struct.
+ */
+#define hlist_for_each_entry(pos, head, member)				\
+	for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
+	     pos;							\
+	     pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
+
 #endif /* LIST_H */
diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
index 85fcac84d2d1..ebd544717b91 100644
--- a/scripts/mod/modpost.c
+++ b/scripts/mod/modpost.c
@@ -207,13 +207,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;	/* link to the hash table */
 	struct list_head list;	/* link to module::exported_symbols or module::unresolved_symbols */
 	struct module *module;
 	char *namespace;
@@ -225,8 +220,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)
 {
@@ -240,6 +233,21 @@ 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_for_matched_symbol(sym, table, key) \
+	hlist_for_each_entry(sym, 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
@@ -254,15 +262,6 @@ static struct symbol *alloc_symbol(const char *name)
 	return s;
 }
 
-/* For the hash of exported symbols */
-static void hash_add_symbol(struct symbol *sym)
-{
-	unsigned int hash;
-
-	hash = tdb_hash(sym->name) % SYMBOL_HASH_SIZE;
-	sym->next = symbolhash[hash];
-	symbolhash[hash] = sym;
-}
 
 static void sym_add_unresolved(const char *name, struct module *mod, bool weak)
 {
@@ -282,8 +281,8 @@ static struct symbol *sym_find_with_module(const char *name, struct module *mod)
 	if (name[0] == '.')
 		name++;
 
-	for (s = symbolhash[tdb_hash(name) % SYMBOL_HASH_SIZE]; s; s = s->next) {
-		if (strcmp(s->name, name) == 0 && (!mod || s->module == mod))
+	hash_for_matched_symbol(s, exported_symbols, name) {
+		if (!mod || s->module == mod)
 			return s;
 	}
 	return NULL;
@@ -427,7 +426,7 @@ static struct symbol *sym_add_exported(const char *name, struct module *mod,
 	s->is_static = !mod->from_dump;
 	s->export    = export;
 	list_add_tail(&s->list, &mod->exported_symbols);
-	hash_add_symbol(s);
+	hash_add_symbol(s, exported_symbols);
 
 	return s;
 }
diff --git a/scripts/mod/modpost.h b/scripts/mod/modpost.h
index 1c2d6498d764..180eb142375e 100644
--- a/scripts/mod/modpost.h
+++ b/scripts/mod/modpost.h
@@ -14,6 +14,8 @@
 #include "list.h"
 #include "elfconfig.h"
 
+#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[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


  parent reply	other threads:[~2022-05-01  8:44 UTC|newest]

Thread overview: 39+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-05-01  8:40 [PATCH v2 00/26] kbuild: yet another series of cleanups (modpost and LTO) Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 01/26] modpost: use bool type where appropriate Masahiro Yamada
2022-05-03 21:43   ` Nick Desaulniers
2022-05-04  5:47     ` Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 02/26] modpost: change mod->gpl_compatible to bool type Masahiro Yamada
2022-05-03 21:45   ` Nick Desaulniers
2022-05-01  8:40 ` [PATCH v2 03/26] modpost: import include/linux/list.h Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 04/26] modpost: traverse modules in order Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 05/26] modpost: add sym_add_unresolved() helper Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 06/26] modpost: traverse unresolved symbols in order Masahiro Yamada
2022-05-03 21:49   ` Nick Desaulniers
2022-05-01  8:40 ` [PATCH v2 07/26] modpost: use doubly linked list for dump_lists Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 08/26] modpost: traverse the namespace_list in order Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 09/26] modpost: dump Module.symvers in the same order of modules.order Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 10/26] modpost: move static EXPORT_SYMBOL check to check_exports() Masahiro Yamada
2022-05-03 21:54   ` Nick Desaulniers
2022-05-01  8:40 ` [PATCH v2 11/26] modpost: make multiple export error Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 12/26] modpost: make sym_add_exported() always allocate a new symbol Masahiro Yamada
2022-05-03 21:56   ` Nick Desaulniers
2022-05-01  8:40 ` [PATCH v2 13/26] modpost: split new_symbol() to symbol allocation and hash table addition Masahiro Yamada
2022-05-03 22:00   ` Nick Desaulniers
2022-05-01  8:40 ` [PATCH v2 14/26] modpost: mitigate false-negatives for static EXPORT_SYMBOL checks Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 15/26] kbuild: record symbol versions in *.cmd files Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 16/26] kbuild: generate a list of objects in vmlinux Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 17/26] modpost: extract symbol versions from *.cmd files Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 18/26] modpost: generate linker script to collect symbol versions Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 19/26] kbuild: embed symbol versions at final link of vmlinux or modules Masahiro Yamada
2022-05-03  2:55   ` Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 20/26] kbuild: stop merging *.symversions Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 21/26] genksyms: adjust the output format for .cmd files Masahiro Yamada
2022-05-04 20:22   ` Nicolas Schier
2022-05-05 13:47     ` Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 22/26] kbuild: do not create *.prelink.o for Clang LTO or IBT Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 23/26] kbuild: make built-in.a rule robust against too long argument error Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 24/26] kbuild: make *.mod " Masahiro Yamada
2022-05-01  8:40 ` [PATCH v2 25/26] modpost: simplify the ->is_static initialization Masahiro Yamada
2022-05-01  8:40 ` Masahiro Yamada [this message]
2022-05-01 12:23 ` [PATCH v2 00/26] kbuild: yet another series of cleanups (modpost and LTO) Masahiro Yamada
2022-05-05  6:55 ` Masahiro Yamada

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220501084032.1025918-27-masahiroy@kernel.org \
    --to=masahiroy@kernel.org \
    --cc=linux-kbuild@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=michal.lkml@markovi.net \
    --cc=ndesaulniers@google.com \
    --subject='Re: [PATCH v2 26/26] modpost: use hlist for hash table implementation' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.