Module Name: src
Committed By: rillig
Date: Sat May 7 17:49:47 UTC 2022
Modified Files:
src/usr.bin/make: compat.c main.c make.1 make.c make.h
src/usr.bin/make/unit-tests: Makefile depsrc-wait.exp depsrc-wait.mk
varname-dot-make-mode.exp varname-dot-make-mode.mk
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.239 -r1.240 src/usr.bin/make/compat.c
cvs rdiff -u -r1.581 -r1.582 src/usr.bin/make/main.c
cvs rdiff -u -r1.308 -r1.309 src/usr.bin/make/make.1
cvs rdiff -u -r1.254 -r1.255 src/usr.bin/make/make.c
cvs rdiff -u -r1.301 -r1.302 src/usr.bin/make/make.h
cvs rdiff -u -r1.312 -r1.313 src/usr.bin/make/unit-tests/Makefile
cvs rdiff -u -r1.2 -r1.3 src/usr.bin/make/unit-tests/depsrc-wait.exp \
src/usr.bin/make/unit-tests/varname-dot-make-mode.mk
cvs rdiff -u -r1.3 -r1.4 src/usr.bin/make/unit-tests/depsrc-wait.mk
cvs rdiff -u -r1.1 -r1.2 \
src/usr.bin/make/unit-tests/varname-dot-make-mode.exp
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/compat.c
diff -u src/usr.bin/make/compat.c:1.239 src/usr.bin/make/compat.c:1.240
--- src/usr.bin/make/compat.c:1.239 Sat May 7 08:01:20 2022
+++ src/usr.bin/make/compat.c Sat May 7 17:49:47 2022
@@ -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);
}
}
Index: src/usr.bin/make/main.c
diff -u src/usr.bin/make/main.c:1.581 src/usr.bin/make/main.c:1.582
--- src/usr.bin/make/main.c:1.581 Sat May 7 08:01:20 2022
+++ src/usr.bin/make/main.c Sat May 7 17:49:47 2022
@@ -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);
Index: src/usr.bin/make/make.1
diff -u src/usr.bin/make/make.1:1.308 src/usr.bin/make/make.1:1.309
--- src/usr.bin/make/make.1:1.308 Mon Apr 18 15:06:27 2022
+++ src/usr.bin/make/make.1 Sat May 7 17:49:47 2022
@@ -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.
Index: src/usr.bin/make/make.c
diff -u src/usr.bin/make/make.c:1.254 src/usr.bin/make/make.c:1.255
--- src/usr.bin/make/make.c:1.254 Sat May 7 10:05:49 2022
+++ src/usr.bin/make/make.c Sat May 7 17:49:47 2022
@@ -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
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);
Index: src/usr.bin/make/make.h
diff -u src/usr.bin/make/make.h:1.301 src/usr.bin/make/make.h:1.302
--- src/usr.bin/make/make.h:1.301 Sat May 7 08:01:20 2022
+++ src/usr.bin/make/make.h Sat May 7 17:49:47 2022
@@ -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;
Index: src/usr.bin/make/unit-tests/Makefile
diff -u src/usr.bin/make/unit-tests/Makefile:1.312 src/usr.bin/make/unit-tests/Makefile:1.313
--- src/usr.bin/make/unit-tests/Makefile:1.312 Mon Apr 18 15:06:28 2022
+++ src/usr.bin/make/unit-tests/Makefile Sat May 7 17:49:47 2022
@@ -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,\[/[^
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
Index: src/usr.bin/make/unit-tests/depsrc-wait.exp
diff -u src/usr.bin/make/unit-tests/depsrc-wait.exp:1.2 src/usr.bin/make/unit-tests/depsrc-wait.exp:1.3
--- src/usr.bin/make/unit-tests/depsrc-wait.exp:1.2 Mon Sep 7 18:40:32 2020
+++ src/usr.bin/make/unit-tests/depsrc-wait.exp Sat May 7 17:49:47 2022
@@ -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
Index: src/usr.bin/make/unit-tests/varname-dot-make-mode.mk
diff -u src/usr.bin/make/unit-tests/varname-dot-make-mode.mk:1.2 src/usr.bin/make/unit-tests/varname-dot-make-mode.mk:1.3
--- src/usr.bin/make/unit-tests/varname-dot-make-mode.mk:1.2 Sun Aug 16 14:25:16 2020
+++ src/usr.bin/make/unit-tests/varname-dot-make-mode.mk Sat May 7 17:49:47 2022
@@ -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
Index: src/usr.bin/make/unit-tests/depsrc-wait.mk
diff -u src/usr.bin/make/unit-tests/depsrc-wait.mk:1.3 src/usr.bin/make/unit-tests/depsrc-wait.mk:1.4
--- src/usr.bin/make/unit-tests/depsrc-wait.mk:1.3 Mon Sep 7 18:40:32 2020
+++ src/usr.bin/make/unit-tests/depsrc-wait.mk Sat May 7 17:49:47 2022
@@ -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
Index: src/usr.bin/make/unit-tests/varname-dot-make-mode.exp
diff -u src/usr.bin/make/unit-tests/varname-dot-make-mode.exp:1.1 src/usr.bin/make/unit-tests/varname-dot-make-mode.exp:1.2
--- src/usr.bin/make/unit-tests/varname-dot-make-mode.exp:1.1 Sun Aug 16 12:07:52 2020
+++ src/usr.bin/make/unit-tests/varname-dot-make-mode.exp Sat May 7 17:49:47 2022
@@ -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
