From 526396b723a38dbeed35cb9e80814084b9f56329 Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:04 +0900 Subject: kconfig: write Kconfig files to autoconf.cmd in order Currently, include/config/autoconf.cmd saves included Kconfig files in reverse order. While this is not a big deal, it is inconsistent with other *.cmd files generated by fixdep. Output the included Kconfig files in the included order. Signed-off-by: Masahiro Yamada --- scripts/kconfig/util.c | 3 +++ 1 file changed, 3 insertions(+) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index 92e5b2b9761d..958543bb0a37 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -25,6 +25,9 @@ struct file *file_lookup(const char *name) file->name = xstrdup(name); file->next = file_list; file_list = file; + + str_printf(&autoconf_cmd, "\t%s \\\n", name); + return file; } -- cgit From 6676c5bc15e66268c9c9669d5852aa779689c74e Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:15 +0900 Subject: kconfig: make file::name a flexible array member Call malloc() just once to allocate needed memory. Signed-off-by: Masahiro Yamada --- scripts/kconfig/util.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index 958543bb0a37..2636dccea0c9 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -13,6 +13,7 @@ struct file *file_lookup(const char *name) { struct file *file; + size_t len; for (file = file_list; file; file = file->next) { if (!strcmp(name, file->name)) { @@ -20,9 +21,11 @@ struct file *file_lookup(const char *name) } } - file = xmalloc(sizeof(*file)); + len = strlen(name); + file = xmalloc(sizeof(*file) + len + 1); memset(file, 0, sizeof(*file)); - file->name = xstrdup(name); + memcpy(file->name, name, len); + file->name[len] = '\0'; file->next = file_list; file_list = file; -- cgit From 5b058034e3aa600802ab609e8264dc2ca1300ebe Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:16 +0900 Subject: kconfig: change file_lookup() to return the file name Currently, file_lookup() returns a pointer to (struct file), but the callers use only file->name. Make it return the ->name member directly. This adjustment encapsulates struct file and file_list as internal implementation. Signed-off-by: Masahiro Yamada --- scripts/kconfig/util.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index 2636dccea0c9..610d64c01479 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -9,15 +9,22 @@ #include #include "lkc.h" +struct file { + struct file *next; + char name[]; +}; + +static struct file *file_list; + /* file already present in list? If not add it */ -struct file *file_lookup(const char *name) +const char *file_lookup(const char *name) { struct file *file; size_t len; for (file = file_list; file; file = file->next) { if (!strcmp(name, file->name)) { - return file; + return file->name; } } @@ -31,7 +38,7 @@ struct file *file_lookup(const char *name) str_printf(&autoconf_cmd, "\t%s \\\n", name); - return file; + return file->name; } /* Allocate initial growable string */ -- cgit From 7c4aa901bd9d7e95be95a5c888d026b3214bae05 Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:22 +0900 Subject: kconfig: move strhash() to util.c as a global function Remove the 'static' qualifier from strhash() so that it can be accessed from other files. Move it to util.c, which is a more appropriate location. Signed-off-by: Masahiro Yamada --- scripts/kconfig/util.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index 610d64c01479..d6172f2f64c9 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -9,6 +9,16 @@ #include #include "lkc.h" +unsigned int strhash(const char *s) +{ + /* fnv32 hash */ + unsigned int hash = 2166136261U; + + for (; *s; s++) + hash = (hash ^ *s) * 0x01000193; + return hash; +} + struct file { struct file *next; char name[]; -- cgit From 980c9e198f1c5563380bed2a2672e592edf9efaa Mon Sep 17 00:00:00 2001 From: Masahiro Yamada Date: Sat, 3 Feb 2024 00:58:23 +0900 Subject: 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 --- scripts/kconfig/util.c | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c index d6172f2f64c9..439c131b424e 100644 --- a/scripts/kconfig/util.c +++ b/scripts/kconfig/util.c @@ -7,6 +7,8 @@ #include #include #include + +#include "hashtable.h" #include "lkc.h" unsigned int strhash(const char *s) @@ -19,32 +21,32 @@ unsigned int strhash(const char *s) return hash; } +/* 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); -- cgit