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/expr.h | 2 +- scripts/kconfig/util.c | 7 +++++-- 2 files changed, 6 insertions(+), 3 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h index 85e0d1ab3c8a..760b1e681b43 100644 --- a/scripts/kconfig/expr.h +++ b/scripts/kconfig/expr.h @@ -19,7 +19,7 @@ extern "C" { struct file { struct file *next; - const char *name; + char name[]; }; typedef enum tristate { 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/expr.h | 7 ------- scripts/kconfig/lexer.l | 5 ++--- scripts/kconfig/lkc.h | 2 +- scripts/kconfig/menu.c | 2 -- scripts/kconfig/util.c | 13 ++++++++++--- 5 files changed, 13 insertions(+), 16 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/expr.h b/scripts/kconfig/expr.h index 760b1e681b43..d667f9aa041e 100644 --- a/scripts/kconfig/expr.h +++ b/scripts/kconfig/expr.h @@ -17,11 +17,6 @@ extern "C" { #include #endif -struct file { - struct file *next; - char name[]; -}; - typedef enum tristate { no, mod, yes } tristate; @@ -275,8 +270,6 @@ struct jump_key { struct menu *target; }; -extern struct file *file_list; - extern struct symbol symbol_yes, symbol_no, symbol_mod; extern struct symbol *modules_sym; extern int cdebug; diff --git a/scripts/kconfig/lexer.l b/scripts/kconfig/lexer.l index 71f651bb82ba..89544c3a1a29 100644 --- a/scripts/kconfig/lexer.l +++ b/scripts/kconfig/lexer.l @@ -401,13 +401,12 @@ void zconf_initscan(const char *name) exit(1); } - cur_filename = file_lookup(name)->name; + cur_filename = file_lookup(name); yylineno = 1; } void zconf_nextfile(const char *name) { - struct file *file = file_lookup(name); struct buffer *buf = xmalloc(sizeof(*buf)); bool recur_include = false; @@ -443,7 +442,7 @@ void zconf_nextfile(const char *name) } yylineno = 1; - cur_filename = file->name; + cur_filename = file_lookup(name); } static void zconf_endfile(void) diff --git a/scripts/kconfig/lkc.h b/scripts/kconfig/lkc.h index d8249052f2e3..71afcbd56273 100644 --- a/scripts/kconfig/lkc.h +++ b/scripts/kconfig/lkc.h @@ -52,7 +52,7 @@ static inline void xfwrite(const void *str, size_t len, size_t count, FILE *out) } /* util.c */ -struct file *file_lookup(const char *name); +const char *file_lookup(const char *name); void *xmalloc(size_t size); void *xcalloc(size_t nmemb, size_t size); void *xrealloc(void *p, size_t size); diff --git a/scripts/kconfig/menu.c b/scripts/kconfig/menu.c index b879576d1ab4..f701382f8a69 100644 --- a/scripts/kconfig/menu.c +++ b/scripts/kconfig/menu.c @@ -16,8 +16,6 @@ static const char nohelp_text[] = "There is no help available for this option."; struct menu rootmenu; static struct menu **last_entry_ptr; -struct file *file_list; - void menu_warn(struct menu *menu, const char *fmt, ...) { va_list ap; 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/lkc.h | 1 + scripts/kconfig/symbol.c | 9 --------- scripts/kconfig/util.c | 10 ++++++++++ 3 files changed, 11 insertions(+), 9 deletions(-) (limited to 'scripts/kconfig/util.c') diff --git a/scripts/kconfig/lkc.h b/scripts/kconfig/lkc.h index 71afcbd56273..e69d7c59d930 100644 --- a/scripts/kconfig/lkc.h +++ b/scripts/kconfig/lkc.h @@ -52,6 +52,7 @@ static inline void xfwrite(const void *str, size_t len, size_t count, FILE *out) } /* util.c */ +unsigned int strhash(const char *s); const char *file_lookup(const char *name); void *xmalloc(size_t size); void *xcalloc(size_t nmemb, size_t size); diff --git a/scripts/kconfig/symbol.c b/scripts/kconfig/symbol.c index dae630a74e50..3dbe3a19622b 100644 --- a/scripts/kconfig/symbol.c +++ b/scripts/kconfig/symbol.c @@ -803,15 +803,6 @@ bool sym_is_changeable(struct symbol *sym) return sym->visible > sym->rev_dep.tri; } -static unsigned strhash(const char *s) -{ - /* fnv32 hash */ - unsigned hash = 2166136261U; - for (; *s; s++) - hash = (hash ^ *s) * 0x01000193; - return hash; -} - struct symbol *sym_lookup(const char *name, int flags) { struct symbol *symbol; 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