Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/make make: allow to randomize build order of targets
details: https://anonhg.NetBSD.org/src/rev/3870210b5583
branches: trunk
changeset: 365991:3870210b5583
user: rillig <rillig%NetBSD.org@localhost>
date: Sat May 07 17:49:47 2022 +0000
description:
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:
usr.bin/make/compat.c | 60 +++++++++++++++++++++-
usr.bin/make/main.c | 6 +-
usr.bin/make/make.1 | 14 +++--
usr.bin/make/make.c | 30 ++++++++++-
usr.bin/make/make.h | 7 ++-
usr.bin/make/unit-tests/Makefile | 4 +-
usr.bin/make/unit-tests/depsrc-wait.exp | 13 +++-
usr.bin/make/unit-tests/depsrc-wait.mk | 22 ++++++++-
usr.bin/make/unit-tests/varname-dot-make-mode.exp | 30 +++++++++++
usr.bin/make/unit-tests/varname-dot-make-mode.mk | 41 ++++++++++++++-
10 files changed, 201 insertions(+), 26 deletions(-)
diffs (truncated from 410 to 300 lines):
diff -r 807f0bf4984b -r 3870210b5583 usr.bin/make/compat.c
--- a/usr.bin/make/compat.c Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/compat.c Sat May 07 17:49:47 2022 +0000
@@ -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 @@
}
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 -r 807f0bf4984b -r 3870210b5583 usr.bin/make/main.c
--- a/usr.bin/make/main.c Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/main.c Sat May 07 17:49:47 2022 +0000
@@ -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 @@
if (strstr(mode, "meta") != NULL)
meta_mode_init(mode);
#endif
+ if (strstr(mode, "randomize-targets") != NULL)
+ opts.randomizeTargets = true;
}
free(mode);
diff -r 807f0bf4984b -r 3870210b5583 usr.bin/make/make.1
--- a/usr.bin/make/make.1 Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/make.1 Sat May 07 17:49:47 2022 +0000
@@ -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 @@
.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 @@
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 @@
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 -r 807f0bf4984b -r 3870210b5583 usr.bin/make/make.c
--- a/usr.bin/make/make.c Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/make.c Sat May 07 17:49:47 2022 +0000
@@ -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 @@
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 @@
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 -r 807f0bf4984b -r 3870210b5583 usr.bin/make/make.h
--- a/usr.bin/make/make.h Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/make.h Sat May 07 17:49:47 2022 +0000
@@ -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 @@
*/
StringList create;
+ /*
+ * Randomize the order in which the targets from toBeMade are made,
+ * to catch undeclared dependencies.
+ */
+ bool randomizeTargets;
} CmdOpts;
extern CmdOpts opts;
diff -r 807f0bf4984b -r 3870210b5583 usr.bin/make/unit-tests/Makefile
--- a/usr.bin/make/unit-tests/Makefile Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/unit-tests/Makefile Sat May 07 17:49:47 2022 +0000
@@ -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-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 -r 807f0bf4984b -r 3870210b5583 usr.bin/make/unit-tests/depsrc-wait.exp
--- a/usr.bin/make/unit-tests/depsrc-wait.exp Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/unit-tests/depsrc-wait.exp Sat May 07 17:49:47 2022 +0000
@@ -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 -r 807f0bf4984b -r 3870210b5583 usr.bin/make/unit-tests/depsrc-wait.mk
--- a/usr.bin/make/unit-tests/depsrc-wait.mk Sat May 07 17:25:28 2022 +0000
+++ b/usr.bin/make/unit-tests/depsrc-wait.mk Sat May 07 17:49:47 2022 +0000
@@ -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
Home |
Main Index |
Thread Index |
Old Index