lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat,  3 Feb 2024 00:58:23 +0900
From: Masahiro Yamada <masahiroy@...nel.org>
To: linux-kbuild@...r.kernel.org
Cc: linux-kernel@...r.kernel.org,
	Masahiro Yamada <masahiroy@...nel.org>
Subject: [PATCH 25/27] kconfig: convert linked list of files to hash table

Currently, a linked list is used to keep track of all the Kconfig
files that have ever been parsed. Every time the "source" statement
is encountered, the linked list is traversed to check if the file has
been opened before. This prevents the same file from being recorded
in include/config/auto.conf.cmd again.

Given 1500+ Kconfig files parsed, a hashtable is now a more optimal
data structure.

By the way, you may wonder why we check this in the first place.
It matters only when the same file is included multiple times.
In old days, such a use case was forbidden, but commit f094f8a1b273
("kconfig: allow multiple inclusion of the same file") provided a bit
more flexibility. Of course, it is almost hypothetical...

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

 scripts/kconfig/util.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c
index 610d64c01479..abd697ed8de7 100644
--- a/scripts/kconfig/util.c
+++ b/scripts/kconfig/util.c
@@ -7,34 +7,37 @@
 #include <stdarg.h>
 #include <stdlib.h>
 #include <string.h>
+
+#include "hashtable.h"
 #include "lkc.h"
+#include "util.h"
+
+/* hash table of all parsed Kconfig files */
+static HASHTABLE_DEFINE(file_hashtable, 1U << 11);
 
 struct file {
-	struct file *next;
+	struct hlist_node node;
 	char name[];
 };
 
-static struct file *file_list;
-
 /* file already present in list? If not add it */
 const char *file_lookup(const char *name)
 {
 	struct file *file;
 	size_t len;
+	int hash = strhash(name);
 
-	for (file = file_list; file; file = file->next) {
-		if (!strcmp(name, file->name)) {
+	hash_for_each_possible(file_hashtable, file, node, hash)
+		if (!strcmp(name, file->name))
 			return file->name;
-		}
-	}
 
 	len = strlen(name);
 	file = xmalloc(sizeof(*file) + len + 1);
 	memset(file, 0, sizeof(*file));
 	memcpy(file->name, name, len);
 	file->name[len] = '\0';
-	file->next = file_list;
-	file_list = file;
+
+	hash_add(file_hashtable, &file->node, hash);
 
 	str_printf(&autoconf_cmd, "\t%s \\\n", name);
 
-- 
2.40.1


Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ