diff options
| author | rillig <rillig@NetBSD.org> | 2022-05-07 17:49:47 +0000 |
|---|---|---|
| committer | rillig <rillig@NetBSD.org> | 2022-05-07 17:49:47 +0000 |
| commit | 88bfda226b0daf6aa9a98e6d4d9ea5ed26981fcd (patch) | |
| tree | eb61cfa0cbdffdb0dede694c957fb260e7190ea2 /usr.bin/make | |
| parent | c4192bec8245e8ce280bb74eca8820dca4e9574c (diff) | |
make: allow to randomize build order of targets
In complex dependency structures, when a build fails, a probable cause
is a missing dependency declaration between some files. In compat mode,
the build order is deterministic, in jobs mode, it is somewhat
deterministic. To explore more edge cases, add the line ".MAKE.MODE +=
randomize-targets" somewhere in the makefile.
Fixes PR bin/45226 by riastradh. Reviewed by christos.
Diffstat (limited to 'usr.bin/make')
| -rw-r--r-- | usr.bin/make/compat.c | 60 | ||||
| -rw-r--r-- | usr.bin/make/main.c | 6 | ||||
| -rw-r--r-- | usr.bin/make/make.1 | 14 | ||||
| -rw-r--r-- | usr.bin/make/make.c | 30 | ||||
| -rw-r--r-- | usr.bin/make/make.h | 7 | ||||
| -rw-r--r-- | usr.bin/make/unit-tests/Makefile | 4 | ||||
| -rw-r--r-- | usr.bin/make/unit-tests/depsrc-wait.exp | 13 | ||||
| -rw-r--r-- | usr.bin/make/unit-tests/depsrc-wait.mk | 22 | ||||
| -rw-r--r-- | usr.bin/make/unit-tests/varname-dot-make-mode.exp | 30 | ||||
| -rw-r--r-- | usr.bin/make/unit-tests/varname-dot-make-mode.mk | 41 |
10 files changed, 201 insertions, 26 deletions
diff --git a/usr.bin/make/compat.c b/usr.bin/make/compat.c index 6e653129acb..6f12cc1ae6c 100644 --- a/usr.bin/make/compat.c +++ b/usr.bin/make/compat.c @@ -1,4 +1,4 @@ -/* $NetBSD: compat.c,v 1.239 2022/05/07 08:01:20 rillig Exp $ */ +/* $NetBSD: compat.c,v 1.240 2022/05/07 17:49:47 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990 The Regents of the University of California. @@ -91,7 +91,7 @@ #include "pathnames.h" /* "@(#)compat.c 8.2 (Berkeley) 3/19/94" */ -MAKE_RCSID("$NetBSD: compat.c,v 1.239 2022/05/07 08:01:20 rillig Exp $"); +MAKE_RCSID("$NetBSD: compat.c,v 1.240 2022/05/07 17:49:47 rillig Exp $"); static GNode *curTarg = NULL; static pid_t compatChild; @@ -459,13 +459,65 @@ RunCommands(GNode *gn) } static void +MakeInRandomOrder(GNode **gnodes, GNode **end, GNode *pgn) +{ + GNode **it; + size_t r; + + for (r = (size_t)(end - gnodes); r >= 2; r--) { + /* Biased, but irrelevant in practice. */ + size_t i = (size_t)random() % r; + GNode *t = gnodes[r - 1]; + gnodes[r - 1] = gnodes[i]; + gnodes[i] = t; + } + + for (it = gnodes; it != end; it++) + Compat_Make(*it, pgn); +} + +static void +MakeWaitGroupsInRandomOrder(GNodeList *gnodes, GNode *pgn) +{ + Vector vec; + GNodeListNode *ln; + GNode **nodes; + size_t i, n, start; + + Vector_Init(&vec, sizeof(GNode *)); + for (ln = gnodes->first; ln != NULL; ln = ln->next) + *(GNode **)Vector_Push(&vec) = ln->datum; + nodes = vec.items; + n = vec.len; + + start = 0; + for (i = 0; i < n; i++) { + if (nodes[i]->type & OP_WAIT) { + MakeInRandomOrder(nodes + start, nodes + i, pgn); + Compat_Make(nodes[i], pgn); + start = i + 1; + } + } + MakeInRandomOrder(nodes + start, nodes + i, pgn); + + Vector_Done(&vec); +} + +static void MakeNodes(GNodeList *gnodes, GNode *pgn) { GNodeListNode *ln; + if (Lst_IsEmpty(gnodes)) + return; + if (opts.randomizeTargets) { + MakeWaitGroupsInRandomOrder(gnodes, pgn); + return; + } + for (ln = gnodes->first; ln != NULL; ln = ln->next) { - GNode *cohort = ln->datum; - Compat_Make(cohort, pgn); + GNode *cgn = ln->datum; + Compat_Make(cgn, pgn); } } diff --git a/usr.bin/make/main.c b/usr.bin/make/main.c index c89c19cc476..b3be90bb950 100644 --- a/usr.bin/make/main.c +++ b/usr.bin/make/main.c @@ -1,4 +1,4 @@ -/* $NetBSD: main.c,v 1.581 2022/05/07 08:01:20 rillig Exp $ */ +/* $NetBSD: main.c,v 1.582 2022/05/07 17:49:47 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -111,7 +111,7 @@ #include "trace.h" /* "@(#)main.c 8.3 (Berkeley) 3/19/94" */ -MAKE_RCSID("$NetBSD: main.c,v 1.581 2022/05/07 08:01:20 rillig Exp $"); +MAKE_RCSID("$NetBSD: main.c,v 1.582 2022/05/07 17:49:47 rillig Exp $"); #if defined(MAKE_NATIVE) && !defined(lint) __COPYRIGHT("@(#) Copyright (c) 1988, 1989, 1990, 1993 " "The Regents of the University of California. " @@ -799,6 +799,8 @@ MakeMode(void) if (strstr(mode, "meta") != NULL) meta_mode_init(mode); #endif + if (strstr(mode, "randomize-targets") != NULL) + opts.randomizeTargets = true; } free(mode); diff --git a/usr.bin/make/make.1 b/usr.bin/make/make.1 index 923bfc2324c..fe3ede6e685 100644 --- a/usr.bin/make/make.1 +++ b/usr.bin/make/make.1 @@ -1,4 +1,4 @@ -.\" $NetBSD: make.1,v 1.308 2022/04/18 15:06:27 rillig Exp $ +.\" $NetBSD: make.1,v 1.309 2022/05/07 17:49:47 rillig Exp $ .\" .\" Copyright (c) 1990, 1993 .\" The Regents of the University of California. All rights reserved. @@ -29,7 +29,7 @@ .\" .\" from: @(#)make.1 8.4 (Berkeley) 3/19/94 .\" -.Dd April 18, 2022 +.Dd May 7, 2022 .Dt MAKE 1 .Os .Sh NAME @@ -978,6 +978,10 @@ If .Va bf is True, when a .meta file is created, mark the target .Ic .SILENT . +.It Pa randomize-targets +In both compat and parallel mode, do not make the targets in the usual order, +but instead randomize their order. +This mode can be used to detect undeclared dependencies between files. .El .It Va .MAKE.META.BAILIWICK In "meta" mode, provides a list of prefixes which @@ -2250,8 +2254,9 @@ will to it and update the value of .Ql Va .OBJDIR . .It Ic .ORDER -The named targets are made in sequence. +In parallel mode, the named targets are made in sequence. This ordering does not add targets to the list of targets to be made. +.Pp Since the dependents of a target do not get built until the target itself could be built, unless .Ql a @@ -2262,9 +2267,6 @@ the following is a dependency loop: b: a .Ed .Pp -The ordering imposed by -.Ic .ORDER -is only relevant for parallel makes. .\" XXX: NOT YET!!!! .\" .It Ic .PARALLEL .\" The named targets are executed in parallel mode. diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c index 297df62a368..fa1e594a1b1 100644 --- a/usr.bin/make/make.c +++ b/usr.bin/make/make.c @@ -1,4 +1,4 @@ -/* $NetBSD: make.c,v 1.254 2022/05/07 10:05:49 rillig Exp $ */ +/* $NetBSD: make.c,v 1.255 2022/05/07 17:49:47 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -104,7 +104,7 @@ #include "job.h" /* "@(#)make.c 8.1 (Berkeley) 6/6/93" */ -MAKE_RCSID("$NetBSD: make.c,v 1.254 2022/05/07 10:05:49 rillig Exp $"); +MAKE_RCSID("$NetBSD: make.c,v 1.255 2022/05/07 17:49:47 rillig Exp $"); /* Sequence # to detect recursion. */ static unsigned int checked_seqno = 1; @@ -932,6 +932,28 @@ GNode_SetLocalVars(GNode *gn) gn->flags.doneAllsrc = true; } +static void +ScheduleRandomly(GNode *gn) +{ + GNodeListNode *ln; + size_t i, n; + + n = 0; + for (ln = toBeMade.first; ln != NULL; ln = ln->next) + n++; + i = n > 0 ? (size_t)random() % (n + 1) : 0; + + if (i == 0) { + Lst_Append(&toBeMade, gn); + return; + } + i--; + + for (ln = toBeMade.first; i > 0; ln = ln->next) + i--; + Lst_InsertBefore(&toBeMade, ln, gn); +} + static bool MakeBuildChild(GNode *cn, GNodeListNode *toBeMadeNext) { @@ -957,7 +979,9 @@ MakeBuildChild(GNode *cn, GNodeListNode *toBeMadeNext) cn->name, cn->cohort_num); cn->made = REQUESTED; - if (toBeMadeNext == NULL) + if (opts.randomizeTargets && !(cn->type & OP_WAIT)) + ScheduleRandomly(cn); + else if (toBeMadeNext == NULL) Lst_Append(&toBeMade, cn); else Lst_InsertBefore(&toBeMade, toBeMadeNext, cn); diff --git a/usr.bin/make/make.h b/usr.bin/make/make.h index 67ddbfa480d..38e4e5914dc 100644 --- a/usr.bin/make/make.h +++ b/usr.bin/make/make.h @@ -1,4 +1,4 @@ -/* $NetBSD: make.h,v 1.301 2022/05/07 08:01:20 rillig Exp $ */ +/* $NetBSD: make.h,v 1.302 2022/05/07 17:49:47 rillig Exp $ */ /* * Copyright (c) 1988, 1989, 1990, 1993 @@ -769,6 +769,11 @@ typedef struct CmdOpts { */ StringList create; + /* + * Randomize the order in which the targets from toBeMade are made, + * to catch undeclared dependencies. + */ + bool randomizeTargets; } CmdOpts; extern CmdOpts opts; diff --git a/usr.bin/make/unit-tests/Makefile b/usr.bin/make/unit-tests/Makefile index 67904fbeba8..c2f2db165fb 100644 --- a/usr.bin/make/unit-tests/Makefile +++ b/usr.bin/make/unit-tests/Makefile @@ -1,4 +1,4 @@ -# $NetBSD: Makefile,v 1.312 2022/04/18 15:06:28 rillig Exp $ +# $NetBSD: Makefile,v 1.313 2022/05/07 17:49:47 rillig Exp $ # # Unit tests for make(1) # @@ -541,8 +541,10 @@ SED_CMDS.varname-dot-shell+= -e 's,\[/[^] ]*\],[(details omitted)],g' SED_CMDS.varname-empty= ${.OBJDIR .PARSEDIR .PATH .SHELL:L:@v@-e '/\\$v/d'@} # Some tests need an additional round of postprocessing. +POSTPROC.depsrc-wait= sed -e '/^---/d' -e 's,^\(: Making 3[abc]\)[123]$$,\1,' POSTPROC.deptgt-suffixes= awk '/^\#\*\*\* Suffixes/,/^never-stop/' POSTPROC.gnode-submake= awk '/Input graph/, /^$$/' +POSTPROC.varname-dot-make-mode= sed 's,^\(: Making [abc]\)[123]$$,\1,' # Some tests reuse other tests, which makes them unnecessarily fragile. export-all.rawout: export.mk diff --git a/usr.bin/make/unit-tests/depsrc-wait.exp b/usr.bin/make/unit-tests/depsrc-wait.exp index d1a60fbaa6e..36bcb067815 100644 --- a/usr.bin/make/unit-tests/depsrc-wait.exp +++ b/usr.bin/make/unit-tests/depsrc-wait.exp @@ -1,13 +1,18 @@ ---- a --- echo a a ---- b1 --- echo b1 b1 ---- b --- echo b b ---- x --- echo x x +: Making 3a +: Making 3a +: Making 3a +: Making 3b +: Making 3b +: Making 3b +: Making 3c +: Making 3c +: Making 3c exit status 0 diff --git a/usr.bin/make/unit-tests/depsrc-wait.mk b/usr.bin/make/unit-tests/depsrc-wait.mk index 95b0ea96e0a..ab974d47c29 100644 --- a/usr.bin/make/unit-tests/depsrc-wait.mk +++ b/usr.bin/make/unit-tests/depsrc-wait.mk @@ -1,9 +1,15 @@ -# $NetBSD: depsrc-wait.mk,v 1.3 2020/09/07 18:40:32 rillig Exp $ +# $NetBSD: depsrc-wait.mk,v 1.4 2022/05/07 17:49:47 rillig Exp $ # # Tests for the special source .WAIT in dependency declarations, # which adds a sequence point between the nodes to its left and the nodes # to its right. +all: .PHONY + @${MAKE} -r -f ${MAKEFILE} x + @${MAKE} -r -f ${MAKEFILE} three-by-three + + +.if make(x) # Even though the build could run massively parallel, the .WAIT imposes a # strict ordering in this example, which forces the targets to be made in # exactly this order. @@ -19,3 +25,17 @@ b: b1 echo b b1: echo b1 +.endif + + +# There are 3 groups of 3 targets, with .WAIT barriers in between. Each of +# these groups has to be made completely before starting the next group. +# See Makefile, POSTPROC for the postprocessing that takes place. +.if make(three-by-three) +.MAKEFLAGS: -j5 +.MAKE.MODE+= randomize-targets + +three-by-three: .WAIT 3a1 3a2 3a3 .WAIT 3b1 3b2 3b3 .WAIT 3c1 3c2 3c3 .WAIT +3a1 3a2 3a3 3b1 3b2 3b3 3c1 3c2 3c3: + : Making ${.TARGET} +.endif diff --git a/usr.bin/make/unit-tests/varname-dot-make-mode.exp b/usr.bin/make/unit-tests/varname-dot-make-mode.exp index 39a9383953d..fa033e718b0 100644 --- a/usr.bin/make/unit-tests/varname-dot-make-mode.exp +++ b/usr.bin/make/unit-tests/varname-dot-make-mode.exp @@ -1 +1,31 @@ +randomize compat mode: +: Making a +: Making a +: Making a +: Making b +: Making b +: Making b +: Making c +: Making c +: Making c +randomize jobs mode (-j1): +: Making a +: Making a +: Making a +: Making b +: Making b +: Making b +: Making c +: Making c +: Making c +randomize jobs mode (-j5): +: Making a +: Making a +: Making a +: Making b +: Making b +: Making b +: Making c +: Making c +: Making c exit status 0 diff --git a/usr.bin/make/unit-tests/varname-dot-make-mode.mk b/usr.bin/make/unit-tests/varname-dot-make-mode.mk index ee75a54ebd7..169aa17cdc3 100644 --- a/usr.bin/make/unit-tests/varname-dot-make-mode.mk +++ b/usr.bin/make/unit-tests/varname-dot-make-mode.mk @@ -1,8 +1,41 @@ -# $NetBSD: varname-dot-make-mode.mk,v 1.2 2020/08/16 14:25:16 rillig Exp $ +# $NetBSD: varname-dot-make-mode.mk,v 1.3 2022/05/07 17:49:47 rillig Exp $ # # Tests for the special .MAKE.MODE variable. -# TODO: Implementation +# TODO: test .MAKE.MODE "meta", or see meta mode tests. +# TODO: test .MAKE.MODE "compat" -all: - @:; + +# See Makefile, POSTPROC for the postprocessing that takes place. +# See the .rawout file for the raw output before stripping the digits. +all: .PHONY make-mode-randomize-targets + + +# By adding the word "randomize-targets" to the variable .MAKE.MODE, the +# targets are not made in declaration order, but rather in random order. This +# mode helps to find undeclared dependencies between files. +# +# History +# Added on 2022-05-07. +# +# See also +# https://gnats.netbsd.org/45226 +make-mode-randomize-targets: .PHONY + @echo "randomize compat mode:" + @${MAKE} -r -f ${MAKEFILE} randomize-targets + + @echo "randomize jobs mode (-j1):" + @${MAKE} -r -f ${MAKEFILE} -j1 randomize-targets + + @echo "randomize jobs mode (-j5):" + @${MAKE} -r -f ${MAKEFILE} -j5 randomize-targets | grep '^:' + +.if make(randomize-targets) +randomize-targets: .WAIT a1 a2 a3 .WAIT b1 b2 b3 .WAIT c1 c2 c3 .WAIT +a1 a2 a3 b1 b2 b3 c1 c2 c3: + : Making ${.TARGET} + +# .MAKE.MODE is evaluated after parsing all files, so it suffices to switch +# the mode after defining the targets. +.MAKE.MODE+= randomize-targets +.endif |
