From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=100.103.45.18 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793816456; b=v1BLTNpwjo4hrbZxYu6LGcGxq6nEmYRnfpSB58ZDOADyc95c30rv0W6qhbVgbt+WtGbT GYdtag2L2ouipNgU4ShCnByFSJtQEhuxKVe5teLNODrhS1fcKH92ggyBsYtjTKSYVuA0u qi9jyh9HUEF/jx/cg/Trzq4Ce7zXP08/f5OWql3TKUXIzdYexO0YQylITPMBDDVDGH6Ua x0xDisGLKsrxSQ9E1gPW+4DbVy7oh0Zvkb4K9xhH/eE7p4gRUirFwdNwUvVjW8h3/pL4W wJjGV0f0U+A1r3aaaPs79cBVlLezysErLIotx2XpmN5bElx0dlXehm1Un8atMp5+JkA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793816456; h=Received:DKIM-Signature:From:Date:Subject:MIME-Version:Content-Type: Content-Transfer-Encoding:Message-Id:References:In-Reply-To:To:Cc: X-Mailer:X-Developer-Signature:X-Developer-Key; bh=0DqDoIx7lRhfuNKq589wr+C2KWJLT5p+lz0slHKi9n4=; b=0bNwk2GP2QW15HdZH4yqMXcUVFtHKsLqQkn8JkSwE4dLhUev9SxYBTkyRJ2fntpCVAvT OfUYZmo3nwU69lLee+R6QyjEs+goZlO/Md4rRm7SzqGp2djnaJT2MznzBz/shlXMh0el9 jUt/MgKvkT/2pc1ku9Kk5JnZuyfgtuuAWT0uk2HxJYBIkNfh8EGAXwUBTjNvd/fia1lNm j323gfZrm/JaVa3c6nAc+CJRXxyK0VTgl4r2ZR34LH4SCzrInhnSIxfIeTHxPlrt+uusC vZlsGWQ62DE9MtQld/AdxSSNed3VEO81XxPplNPCffGJhw7WpFUATltufwOKlJ7toTg== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=JsAmcxVx; arc=none smtp.remote-ip=100.103.45.18 Received: from smtp.kernel.org (quasi.space.kernel.org [100.103.45.18]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6CC02606A333; Wed, 4 Nov 2026 18:20:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=JsAmcxVx Received: by smtp.kernel.org (Postfix) with ESMTPSA id 578651F00A25; Wed, 4 Nov 2026 18:20:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1793816456; bh=0DqDoIx7lRhfuNKq589wr+C2KWJLT5p+lz0slHKi9n4=; h=From:Date:Subject:References:In-Reply-To:To:Cc; b=JsAmcxVxWpC0Z5LukTe4dd9iFFOqaJsHrI+KisrlVV+A10rxDP2AJXSeDF8GyoIRW ag2lbD0qpD2JEwF2QB9Qcm6Pr7APy18BEoiyQO+WWHosAJzry1cdXJn21/rejXzkDw DlC49II9epm+Ux7SxxsjGV6hD7fgru6LLJGl7zHRvTyI+OVUB4Ajqw25lOKuOQksbq tj0mZ+SZxA30rCGSbpm/UmsLiY7e1hCID8Xb6aMIqfNtlkBSVOhg88lQ3zBhVZUju/ mhnwIgga5UBZWvfCzYsIu+aVC9t36YPBRwIyfZcPTSn08Z6vjQ4CzonVCWXJIWe8uB SwGV9OD23XFyg== From: "Lorenzo Stoakes (ARM)" Date: Wed, 04 Nov 2026 18:20:20 +0000 Subject: [PATCH v5 02/11] kbuild: implement and use depcheck to check dependency timestamps X-Mailing-List: linux-modules@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Message-Id: <20261104-build-speedup-v5-2-0f6018be8dae@kernel.org> References: <20261104-build-speedup-v5-0-0f6018be8dae@kernel.org> In-Reply-To: <20261104-build-speedup-v5-0-0f6018be8dae@kernel.org> To: Linus Torvalds , Nathan Chancellor , Nicolas Schier , Nick Desaulniers , Bill Wendling , Justin Stitt , Geert Uytterhoeven , Luis Chamberlain , Petr Pavlu , Daniel Gomez , Sami Tolvanen , Aaron Tomlin , Josh Poimboeuf , Peter Zijlstra , Miguel Ojeda , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= , Benno Lossin , Andreas Hindborg , Alice Ryhl , Trevor Gross , Danilo Krummrich , Daniel Almeida , Tamir Duberstein , Alexandre Courbot , =?utf-8?q?Onur_=C3=96zkan?= Cc: ljs@kernel.org, linux-kbuild@vger.kernel.org, linux-kernel@vger.kernel.org, llvm@lists.linux.dev, linux-m68k@lists.linux-m68k.org, linux-modules@vger.kernel.org, rust-for-linux@vger.kernel.org X-Mailer: b4 0.14.3 X-Developer-Signature: v=1; a=openpgp-sha256; l=17199; i=ljs@kernel.org; h=from:subject:message-id; bh=aFDnWuLunNfyD/Ngz8BtRH43v2ft5hULsX2XL76I/9o=; b=owGbwMvMwCV2fu7ZrsZH9SKMp9WSGLJel+fUb2Dx5lv+vWiCW8iLh7cfHupY6e5SdiEnU26Op oOJ1tngjlIWBjEuBlkxRZbnX8T3B4mEzeu84O8GM4eVCWQIAxenAEzkZisjw5JZvzyLD1+Z5vSh fcKSYv2TRz4873m6tc2jYe00RsEW1rOMDE/Kb33Os5VskeLasPmzZ8AV/VsXuU6Efc66HPbAauG bS7wA X-Developer-Key: i=ljs@kernel.org; a=openpgp; fpr=E7F417BF5214569E89D04F46CF9DCD8A81E27F14 Each object's .cmd file lists its header dependencies, which often consists of over a thousand dependencies. When little has changed in the tree, this is what make spends most of its time doing, spending over a second, single-threaded when parsing larger directory trees. It performs considerably more work that is actually necessary to get the job done. This can be done faster in C, so implement scripts/basic/depcheck to do so. It does as little work as possible, reading the .cmd files from a directory's targets and running stat on each dependency only a single time. It generates a fragment holding only the saved command line for a target whose dependencies all exist and are older than it, and the entire .cmd file for any other. A dependency that is also a target of the same directory (e.g. header generated by an if_changed rule) may get remade later in the same make run, so do not treat a target as fresh. That way, Makefile.build simply includes the fragment and the amount of work make has to do is significantly reduced when there is not much work to do. If the operation fails, kbuild falls back to using .cmd files. The result is exactly the same as before. For drivers/gpu/drm/amd/amdgpu in an allmodconfig tree the fragment is a fifth of the size of the .cmd files, make reads it in 10ms instead of 380ms, and the instance goes from 2.2s to 0.4s. Whole build, 128-thread Threadripper 9980X, best of N runs: before after delta ------------------------------- x86 defconfig, no-op make, gcc 1.1s 0.78s -0.30s (-28%) x86 defconfig, no-op make, clang 1.3s 0.94s -0.34s (-27%) x86 allmodconfig, no-op make, gcc 14.5s 12.9s -1.6s (-11%) x86 allmodconfig, no-op make, clang 15.5s 14.2s -1.3s (-9%) x86 allmodconfig, touch mm/vma.c, gcc 34.3s 33.9s -0.33s (-1%) x86 allmodconfig, touch mm/vma.c, clang 33.2s 32.2s -0.98s (-3%) Signed-off-by: Lorenzo Stoakes (ARM) --- Makefile | 1 + scripts/Makefile.build | 15 +- scripts/basic/.gitignore | 1 + scripts/basic/Makefile | 2 +- scripts/basic/depcheck.c | 481 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 498 insertions(+), 2 deletions(-) diff --git a/Makefile b/Makefile index f895752d4b05..d92a5d78b465 100644 --- a/Makefile +++ b/Makefile @@ -2252,6 +2252,7 @@ clean: $(clean-dirs) $(call cmd,rmfiles) @find . $(RCS_FIND_IGNORE) \ \( -name '*.[aios]' -o -name '*.rsi' -o -name '*.ko' -o -name '.*.cmd' \ + -o -name '.depcheck.mk' -o -name '.depcheck.mk.tmp' \ -o -name '*.ko.*' -o -name '*.o.thinlto.bc' \ -o -name '*.dtb' -o -name '*.dtbo' \ -o -name '*.dtb.S' -o -name '*.dtbo.S' \ diff --git a/scripts/Makefile.build b/scripts/Makefile.build index bbe9555c47a8..7b652f169a8f 100644 --- a/scripts/Makefile.build +++ b/scripts/Makefile.build @@ -613,7 +613,20 @@ $(obj)/: $(if $(KBUILD_BUILTIN), $(targets-for-builtin)) \ existing-targets := $(wildcard $(sort $(targets))) --include $(foreach f,$(existing-targets),$(dir $(f)).$(notdir $(f)).cmd) +cmd-files := $(wildcard $(foreach f,$(existing-targets),$(dir $(f)).$(notdir $(f)).cmd)) + +# depcheck checks timestamps first and outputs only saved command lines of +# up-to-date targets, falling back to .cmd files if it fails. A directory +# whose targets all lie elsewhere may not exist in the output tree. +depcheck := $(wildcard $(objtree)/scripts/basic/depcheck) + +ifneq ($(and $(depcheck),$(cmd-files),$(wildcard $(obj))),) +ifeq ($(shell $(depcheck) $(obj)/.depcheck.mk $(cmd-files) && echo ok),ok) +cmd-files := $(obj)/.depcheck.mk +endif +endif + +-include $(cmd-files) # Create directories for object files if they do not exist obj-dirs := $(sort $(patsubst %/,%, $(dir $(targets)))) diff --git a/scripts/basic/.gitignore b/scripts/basic/.gitignore index 07c195f605a1..761ee14f9477 100644 --- a/scripts/basic/.gitignore +++ b/scripts/basic/.gitignore @@ -1,3 +1,4 @@ # SPDX-License-Identifier: GPL-2.0-only +/depcheck /fixdep /randstruct.seed diff --git a/scripts/basic/Makefile b/scripts/basic/Makefile index fb8e2c38fbc7..ff98780e474d 100644 --- a/scripts/basic/Makefile +++ b/scripts/basic/Makefile @@ -2,7 +2,7 @@ # # fixdep: used to generate dependency information during build process -hostprogs-always-y += fixdep +hostprogs-always-y += fixdep depcheck # randstruct: the seed is needed before building the gcc-plugin or # before running a Clang kernel build. diff --git a/scripts/basic/depcheck.c b/scripts/basic/depcheck.c new file mode 100644 index 000000000000..119075353f3b --- /dev/null +++ b/scripts/basic/depcheck.c @@ -0,0 +1,481 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * depcheck - check the dependency timestamps of a directory's targets so that + * make reads only what it needs from their .cmd files. + * + * fixdep writes a .cmd file as: + * + * savedcmd_dir/foo.o := + * + * source_dir/foo.o := dir/foo.c + * + * deps_dir/foo.o := \ + * include/linux/bar.h \ + * $(wildcard include/config/BAZ) \ + * + * dir/foo.o: $(deps_dir/foo.o) + * + * $(deps_dir/foo.o): + * + * and kbuild may append rules of its own after that, such as one making the + * target depend on objtool. + * + * For a target that exists and is newer than every dependency listed, make can + * have nothing to do with the list, so it is left out and only what precedes + * and follows it is passed on; for anything else the .cmd file is passed on in + * full. + * + * Usage: depcheck <.cmd files...> + * + * The output is a makefile fragment to include in place of the .cmd files; a + * non-zero exit status means the caller should include those instead. + */ +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +/* What fixdep writes, see above. */ +#define DEPS_PREFIX "deps_" +#define DEPS_RULE_PREFIX "$(" DEPS_PREFIX +#define RULE_SUFFIX ":" +#define LINE_CONTINUATION " \\" +#define WILDCARD_OPEN "$(wildcard " +#define WILDCARD_CLOSE ")" +#define CMD_SUFFIX ".cmd" + +/* A line of a .cmd file, without its newline. */ +struct line { + const char *text; + size_t len; +}; + +static bool is_blank(char chr) +{ + return chr == ' ' || chr == '\t'; +} + +static bool str_ends_with(const char *str, const char *suffix) +{ + const size_t len = strlen(str), suffix_len = strlen(suffix); + + return len >= suffix_len && !strcmp(str + len - suffix_len, suffix); +} + +static bool line_starts_with(const struct line *line, const char *prefix) +{ + const size_t len = strlen(prefix); + + return line->len >= len && !memcmp(line->text, prefix, len); +} + +static bool line_ends_with(const struct line *line, const char *suffix) +{ + const size_t len = strlen(suffix); + + return line->len >= len && + !memcmp(line->text + line->len - len, suffix, len); +} + +static bool line_is_blank(const struct line *line) +{ + size_t i; + + for (i = 0; i < line->len; i++) + if (!is_blank(line->text[i])) + return false; + + return true; +} + +/* Whether the line ends in " \", continuing the list on the next line. */ +static bool line_is_continued(const struct line *line) +{ + return line_ends_with(line, LINE_CONTINUATION); +} + +static void line_strip_continuation(struct line *line) +{ + if (line_is_continued(line)) + line->len -= strlen(LINE_CONTINUATION); +} + +static void line_trim(struct line *line) +{ + while (line->len && is_blank(line->text[0])) { + line->text++; + line->len--; + } + while (line->len && is_blank(line->text[line->len - 1])) + line->len--; +} + +/* Take the next line out of [*pos, end); false once there are none left. */ +static bool next_line(const char **pos, const char *end, struct line *line) +{ + const char *newline; + + if (*pos >= end) + return false; + + newline = memchr(*pos, '\n', end - *pos); + line->text = *pos; + line->len = (newline ? newline : end) - *pos; + *pos = newline ? newline + 1 : end; + + return true; +} + +/* Describes a dependency file. */ +struct dep { + struct hlist_node hnode; + struct timespec mtime; + bool exists; + char path[]; +}; + +static HASHTABLE_DEFINE(dep_table, 1U << 16); + +/* The targets of this run's .cmd files: anything make may remake this time. */ +struct target { + struct hlist_node hnode; + char path[]; +}; + +static HASHTABLE_DEFINE(target_table, 1U << 12); + +static void add_target(const char *path) +{ + struct target *target = xmalloc(sizeof(*target) + strlen(path) + 1); + + strcpy(target->path, path); + hash_add(target_table, &target->hnode, hash_str(path)); +} + +static bool is_target(const char *path) +{ + const unsigned int key = hash_str(path); + struct target *target; + + hash_for_each_possible(target_table, target, hnode, key) { + if (!strcmp(target->path, path)) + return true; + } + + return false; +} + +static const struct dep *lookup_dep(const char *path) +{ + const unsigned int key = hash_str(path); + struct dep *dep; + struct stat st; + + hash_for_each_possible(dep_table, dep, hnode, key) { + if (!strcmp(dep->path, path)) + return dep; + } + + dep = xcalloc(1, sizeof(*dep) + strlen(path) + 1); + strcpy(dep->path, path); + dep->exists = !stat(path, &st); + if (dep->exists) + dep->mtime = st.st_mtim; + hash_add(dep_table, &dep->hnode, key); + + return dep; +} + +/* Strictly newer, as make compares timestamps. */ +static bool newer(const struct timespec *time_a, const struct timespec *time_b) +{ + if (time_a->tv_sec != time_b->tv_sec) + return time_a->tv_sec > time_b->tv_sec; + + return time_a->tv_nsec > time_b->tv_nsec; +} + +/* + * $(wildcard include/config/FOO) is a prerequisite only while FOO is set: + * unwrap it and say that it is optional. + */ +static bool line_unwrap_wildcard(struct line *line) +{ + if (!line_starts_with(line, WILDCARD_OPEN) || + !line_ends_with(line, WILDCARD_CLOSE)) + return false; + + line->text += strlen(WILDCARD_OPEN); + line->len -= strlen(WILDCARD_OPEN) + strlen(WILDCARD_CLOSE); + + return true; +} + +/* fixdep doubles '$' and escapes '#' in a path: undo that into path[]. */ +static bool unescape_path(const struct line *line, char *path, size_t size) +{ + size_t i, out_len = 0; + + if (line->len >= size) + return false; + + for (i = 0; i < line->len; i++) { + const char chr = line->text[i]; + const char next_chr = i + 1 < line->len ? line->text[i + 1] : '\0'; + + if ((chr == '$' && next_chr == '$') || (chr == '\\' && next_chr == '#')) + i++; + path[out_len++] = line->text[i]; + } + path[out_len] = '\0'; + + return true; +} + +/* Is the path contained in line older than the target? */ +static bool dep_is_fresh(struct line line, const struct timespec *target) +{ + char path[PATH_MAX]; + const struct dep *dep; + bool optional; + + line_strip_continuation(&line); + line_trim(&line); + if (!line.len) + return false; + + optional = line_unwrap_wildcard(&line); + if (!line.len || !unescape_path(&line, path, sizeof(path))) + return false; + + /* A target can get 'remade' so its timestamp is meaningless. */ + if (is_target(path)) + return false; + + dep = lookup_dep(path); + if (!dep->exists) + return optional; + + return !newer(&dep->mtime, target); +} + +/* + * Parse a dependency list which consists of one file per line and determine if + * all dependencies are 'fresh', i.e. older than the target. + */ +static bool deps_are_fresh(const char *pos, const char *end, + const struct timespec *target) +{ + struct line line; + + while (next_line(&pos, end, &line)) { + if (line_is_blank(&line)) + return true; + if (!dep_is_fresh(line, target)) + return false; + if (!line_is_continued(&line)) + return true; + } + + return true; +} + +/* + * Find the "deps_" line in the input. + * + * On success returns true and *deps_off is set to its offset and *list is set + * to the list's own lines start or NULL if the line is not continued. + * + * Otherwise returns false if the prefix cannot be found. + */ +static bool find_deps(const char *buf, size_t len, size_t *deps_off, + const char **list) +{ + const char *pos = buf, *end = buf + len; + struct line line; + + while (next_line(&pos, end, &line)) { + if (!line_starts_with(&line, DEPS_PREFIX)) + continue; + + *deps_off = line.text - buf; + *list = line_is_continued(&line) ? pos : NULL; + return true; + } + + return false; +} + +/* + * Is this the target of a .cmd file, i.e. 'dir/.name.cmd names dir/name.'? + */ +static bool target_of(const char *cmd_path, char *target, size_t size) +{ + const char *slash = strrchr(cmd_path, '/'); + const char *base = slash ? slash + 1 : cmd_path; + const size_t dir_len = base - cmd_path; + const size_t affix_len = strlen(".") + strlen(CMD_SUFFIX); + const size_t base_len = strlen(base); + + if (base[0] != '.' || !str_ends_with(base, CMD_SUFFIX) || + base_len <= affix_len) + return false; + + return snprintf(target, size, "%.*s%.*s", (int)dir_len, cmd_path, + (int)(base_len - affix_len), base + 1) < (int)size; +} + +/* + * Does the .cmd file's target exists and is it newer than everything in its + * dependency list? + * + * Returns true if so and sets *deps_off to the start of the list, otherwise + * returns false. + */ +static bool target_is_fresh(const char *cmd_path, const char *buf, size_t len, + size_t *deps_off) +{ + char target[PATH_MAX]; + struct stat st; + const char *list; + + if (!target_of(cmd_path, target, sizeof(target)) || stat(target, &st)) + return false; + if (!find_deps(buf, len, deps_off, &list)) + return false; + if (!list) + return true; + + return deps_are_fresh(list, buf + len, &st.st_mtim); +} + +static char *read_file(const char *path, size_t *len) +{ + FILE *file = fopen(path, "r"); + struct stat st; + char *buf; + size_t nr_read = 0; + + if (!file) + return NULL; + if (fstat(fileno(file), &st)) { + fclose(file); + return NULL; + } + + buf = xmalloc(st.st_size + 1); + while (nr_read < (size_t)st.st_size) { + const size_t chunk = fread(buf + nr_read, 1, st.st_size - nr_read, file); + + if (!chunk) + break; + nr_read += chunk; + } + fclose(file); + + buf[nr_read] = '\0'; + *len = nr_read; + return buf; +} + +/* + * Find the end of the dependency block: the offset just past its closing + * "$(deps_x):" line. Anything after that was appended by kbuild and is not for + * us to judge. Returns len if the line cannot be found. + */ +static size_t deps_block_end(const char *buf, size_t len, size_t deps_off) +{ + const char *pos = buf + deps_off, *end = buf + len; + struct line line; + + while (next_line(&pos, end, &line)) { + if (line_starts_with(&line, DEPS_RULE_PREFIX) && + line_ends_with(&line, RULE_SUFFIX)) + return pos - buf; + } + + return len; +} + +/* The target is fresh: pass on everything but the dependency block. */ +static void write_without_deps(FILE *out, const char *buf, size_t len, + size_t deps_off) +{ + const size_t tail_off = deps_block_end(buf, len, deps_off); + + fwrite(buf, 1, deps_off, out); + fputc('\n', out); + fwrite(buf + tail_off, 1, len - tail_off, out); +} + +/* + * Generate a fragment for make from one .cmd file - without the dependency + * block if the target is fresh, otherwise all of it. + */ +static void process(FILE *out, const char *cmd_path) +{ + size_t len, deps_off; + char *buf; + + buf = read_file(cmd_path, &len); + if (!buf) + return; + + if (target_is_fresh(cmd_path, buf, len, &deps_off)) + write_without_deps(out, buf, len, deps_off); + else + fwrite(buf, 1, len, out); + + free(buf); +} + +int main(int argc, char **argv) +{ + char tmp_path[PATH_MAX]; + FILE *out; + int i; + + if (argc < 2) { + fprintf(stderr, "usage: %s <.cmd files...>\n", argv[0]); + return 1; + } + + if (snprintf(tmp_path, sizeof(tmp_path), "%s.tmp", argv[1]) >= + (int)sizeof(tmp_path)) { + fprintf(stderr, "%s: path too long\n", argv[1]); + return 1; + } + + out = fopen(tmp_path, "w"); + if (!out) { + perror(tmp_path); + return 1; + } + + for (i = 2; i < argc; i++) { + char target[PATH_MAX]; + + if (target_of(argv[i], target, sizeof(target))) + add_target(target); + } + + for (i = 2; i < argc; i++) + process(out, argv[i]); + + /* Write errors are latched in the stream, so one check at the end covers them all. */ + if (ferror(out) || fclose(out) || rename(tmp_path, argv[1])) { + perror(argv[1]); + unlink(tmp_path); + return 1; + } + + return 0; +} -- 2.56.0