[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH v2] Add '--shuffle' argument support
|
From: |
Sergei Trofimovich |
|
Subject: |
[PATCH v2] Add '--shuffle' argument support |
|
Date: |
Fri, 18 Feb 2022 23:50:09 +0000 |
From: Sergei Trofimovich <siarheit@google.com>
The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j g1 g2 g3' mode.
The implementation is to introduce second order into each dependency chain:
1. existing order is syntactic order reachable via 'dep->next'
2. new order is shuffled order stored as 'dep->shuf' in each 'dep'
When goals or prerequisites are updated we use shuffled order when
'--shuffle' is passed to make. When recipes are evaluated we use
syntactic order of parameters.
Sample execution looks like:
$ while echo ======= && rm -f a b && make --shuffle; do sleep 1; done
=======
touch a
cp a b
=======
cp a b
cp: cannot stat 'a': No such file or directory
make: *** [Makefile:5: b] Error 1 --shuffle=1644097687
Note: here first run succeeds while second run fails and exposes the bug in
Makefile. --shuffle=1644097687 allows us to rerun the same build sequence
again.
* Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
* builddos.bat: Add shuf.o into build script.
* doc/make.1: Add '--shuffle' option description.
* doc/make.texi: Add '--shuffle' option description.
* src/dep.h (DEP): Add 'shuf' field to store shuffled order.
* src/filedef.h (struct file): Add 'was_shuffled' bit flag to guard against
circular dependencies.
* src/implicit.c (pattern_search): Reshuffle dependencies for targets
dynamically extended with dependencies from implicit rules.
* src/job.c (child_error): Print shuffle parameter used for dependency
shuffling.
* src/main.c: Add '--shuffle' option handling.
* src/remake.c (update_goal_chain): Change goal traversal order to shuffled.
* src/shuf.c: New file with shuffle infrastructure.
* src/shuf.h: New file with shuffle infrastructure declarations.
* tests/scripts/options/shuffle-reverse: New file with basic tests.
---
Makefile.am | 5 +-
builddos.bat | 3 +-
doc/make.1 | 34 +++++
doc/make.texi | 51 +++++++
src/dep.h | 1 +
src/filedef.h | 2 +
src/implicit.c | 9 ++
src/job.c | 19 ++-
src/main.c | 45 ++++++
src/remake.c | 54 ++++---
src/shuf.c | 202 ++++++++++++++++++++++++++
src/shuf.h | 34 +++++
tests/scripts/options/shuffle-reverse | 112 ++++++++++++++
13 files changed, 542 insertions(+), 29 deletions(-)
create mode 100644 src/shuf.c
create mode 100644 src/shuf.h
create mode 100644 tests/scripts/options/shuffle-reverse
diff --git a/Makefile.am b/Makefile.am
index 9be60fec..3ad19e0c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,8 +35,9 @@ make_SRCS = src/ar.c src/arscan.c src/commands.c
src/commands.h \
src/hash.c src/hash.h src/implicit.c src/job.c src/job.h \
src/load.c src/loadapi.c src/main.c src/makeint.h src/misc.c \
src/os.h src/output.c src/output.h src/read.c src/remake.c \
- src/rule.c src/rule.h src/signame.c src/strcache.c \
- src/variable.c src/variable.h src/version.c src/vpath.c
+ src/rule.c src/rule.h src/shuf.h src/shuf.c src/signame.c \
+ src/strcache.c src/variable.c src/variable.h src/version.c \
+ src/vpath.c
w32_SRCS = src/w32/pathstuff.c src/w32/w32os.c src/w32/compat/dirent.c \
src/w32/compat/posixfcn.c src/w32/include/dirent.h \
diff --git a/builddos.bat b/builddos.bat
index 9cecabec..cfb224c2 100644
--- a/builddos.bat
+++ b/builddos.bat
@@ -68,12 +68,13 @@ gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib
-DHAVE_CONFIG_H -O2 -g %XSRC%/s
gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/src/remote-stub.c -o remote-stub.o
gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/src/getopt.c -o getopt.o
gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/src/getopt1.c -o getopt1.o
+gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/src/shuf.c -o shuf.o
gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/lib/glob.c -o lib/glob.o
gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/lib/fnmatch.c -o lib/fnmatch.o
@echo off
echo commands.o > respf.$$$
for %%f in (job output dir file misc main read remake rule implicit default
variable) do echo %%f.o >> respf.$$$
-for %%f in (expand function vpath hash strcache version ar arscan signame
remote-stub getopt getopt1) do echo %%f.o >> respf.$$$
+for %%f in (expand function vpath hash strcache version ar arscan signame
remote-stub getopt getopt1 shuf) do echo %%f.o >> respf.$$$
for %%f in (lib\glob lib\fnmatch) do echo %%f.o >> respf.$$$
rem gcc -c -I./src -I%XSRC% -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g
%XSRC%/guile.c -o guile.o
rem echo guile.o >> respf.$$$
diff --git a/doc/make.1 b/doc/make.1
index cca833fa..bc347016 100644
--- a/doc/make.1
+++ b/doc/make.1
@@ -319,6 +319,40 @@ Turn off
.BR \-w ,
even if it was turned on implicitly.
.TP 0.5i
+.BI \-\-shuffle "[=MODE]"
+Enable goal and prerequisite dependency order shuffling at execution.
+Simulate reordering similar to one frequently seen in parallel (
+.B \-j
+) execution mode. Shuffling is useful to increase possibility to trigger
+bugs that stem from incompletely specified dependencies in targets.
+
+If the
+.I MODE
+is omitted, then the behavior is the same as if
+.I random
+was specified.
+.I MODE
+may be one of the following values:
+.I random
+to shuffle dependencies in random order,
+.I identity
+to preserve dependencies in original order while
+using shuffling infrastructure (useful for debugging
+.B make
+itself, does not affect actual ordering),
+.I reverse
+reverses order for every goal and dependency,
+.I none
+disables shuffling infrastructure completely
+(identical to not passing
+.B \-\-shuffle
+at all),
+.I <seed>
+enables
+.I random
+mode and specifies exact random seed (to reproduce exactly the same build
+order on rerun).
+.TP 0.5i
\fB\-W\fR \fIfile\fR, \fB\-\-what\-if\fR=\fIfile\fR,
\fB\-\-new\-file\fR=\fIfile\fR, \fB\-\-assume\-new\fR=\fIfile\fR
Pretend that the target
.I file
diff --git a/doc/make.texi b/doc/make.texi
index 14476515..e9065fa4 100644
--- a/doc/make.texi
+++ b/doc/make.texi
@@ -9422,6 +9422,57 @@ from the top-level @code{make} via @code{MAKEFLAGS}
(@pxref{Recursion, ,Recursive Use of @code{make}})
or if you set @samp{-k} in @code{MAKEFLAGS} in your environment.@refill
+@item --shuffle[=@var{mode}]
+@cindex @code{--shuffle}
+@c Extra blank line here makes the table look better.
+
+The primary purpose of this option is to expose missing or incomplete
+dependencies in Makefiles designed to work in parallel (@samp{-j})
+execution mode.
+
+When executed in order build parallelism problems are sometimes only
+seen on heavy loaded machines with high parallelism. @samp{--shuffle}
+allows triggering subset of these bugs by reordering goals and targets.
+That way we have a chance to expose missing dependency even in serial
+(@samp{-j1}) mode!
+
+Note that @code{make --shuffle clean all install} does reorder goals
+similar to how @code{make -j clean all install} runs all targets in
+parallel.
+
+@samp{--shuffle=} accepts an optional value:
+
+@table @code
+@item random
+Shuffle dependencies in random order. This is equivalent to using
+@samp{--shuffle} without extra parameters.
+
+Calls to child @code{$(MAKE)} passes through seed value picked by parent
+process. That way we can reproduce build order by passing seed value
+explicitly on future reruns.
+
+@item identity
+Preserve dependencies in original order while using shuffling
+infrastructure (useful for debugging @code{make} itself). Functionally
+identical to @samp{--shuffle=none}.
+
+@item reverse
+Reverse order of every goal and dependency. It's a simple shuffling
+scheme that guarantees predictable ordering that differs from default.
+Useful for @code{make} own test suite and for lightweight deterministic
+test of a build system.
+
+@item none
+Disable shuffling infrastructure completely (identical to not passing
+@samp{--shuffle} option at all). Useful to explicitly negate of previous
+@samp{--shuffle} options.
+
+@item <@var{seed}>
+Enables @samp{random} mode and specified exact random seed (useful
+when if is desirable to reproduce exactly the same build order on rerun).
+@var{seed} has to be a numeric value. Example use is @samp{--shuffle=12345}.
+@end table
+
@item -t
@cindex @code{-t}
@itemx --touch
diff --git a/src/dep.h b/src/dep.h
index e492a0b3..f7556ce2 100644
--- a/src/dep.h
+++ b/src/dep.h
@@ -46,6 +46,7 @@ struct nameseq
#define DEP(_t) \
NAMESEQ (_t); \
struct file *file; \
+ _t *shuf; \
const char *stem; \
unsigned int flags : 8; \
unsigned int changed : 1; \
diff --git a/src/filedef.h b/src/filedef.h
index 0b9f6e17..d36a6011 100644
--- a/src/filedef.h
+++ b/src/filedef.h
@@ -108,6 +108,8 @@ struct file
pattern-specific variables. */
unsigned int no_diag:1; /* True if the file failed to update and no
diagnostics has been issued (dontcare). */
+ unsigned int was_shuffled:1; /* Did we already shuffle 'deps'? used when
+ --shuffle passes through the graph. */
};
diff --git a/src/implicit.c b/src/implicit.c
index 2b5bdce3..8b84c317 100644
--- a/src/implicit.c
+++ b/src/implicit.c
@@ -22,6 +22,7 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
#include "variable.h"
#include "job.h" /* struct child, used inside commands.h */
#include "commands.h" /* set_file_variables */
+#include "shuf.h"
#include <assert.h>
static int pattern_search (struct file *file, int archive,
@@ -1029,8 +1030,16 @@ pattern_search (struct file *file, int archive,
dep->next = file->deps;
file->deps = dep;
+
+ /* File changed it's dependencies. Schedule regeneration. */
+ file->was_shuffled = 0;
}
+ /* TODO: could we make this shuffle more deterministic and less
+ dependent on current filesystem state? */
+ if (! file->was_shuffled)
+ shuffle_file_deps_recursive (file);
+
if (!tryrules[foundrule].checked_lastslash)
{
/* Always allocate new storage, since STEM might be on the stack for an
diff --git a/src/job.c b/src/job.c
index 9ae3cd6b..d907be1f 100644
--- a/src/job.c
+++ b/src/job.c
@@ -25,6 +25,8 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
#include "commands.h"
#include "variable.h"
#include "os.h"
+#include "dep.h"
+#include "shuf.h"
/* Default shell to use. */
#ifdef WINDOWS32
@@ -539,6 +541,7 @@ child_error (struct child *child,
const struct file *f = child->file;
const floc *flocp = &f->cmds->fileinfo;
const char *nm;
+ const char *shuf;
size_t l;
if (ignored && run_silent)
@@ -562,7 +565,16 @@ child_error (struct child *child,
nm = a;
}
- l = strlen (pre) + strlen (nm) + strlen (f->name) + strlen (post);
+ shuf = shuffle_get_str_value ();
+ if (shuf[0])
+ {
+ char *a = alloca (11 + strlen (shuf) + 1);
+ sprintf (a, " --shuffle=%s", shuf);
+ shuf = a;
+ }
+
+ l = strlen (pre) + strlen (nm) + strlen (f->name) + strlen (post)
+ + strlen (shuf);
OUTPUT_SET (&child->output);
@@ -570,12 +582,13 @@ child_error (struct child *child,
if (exit_sig == 0)
error (NILF, l + INTSTR_LENGTH,
- _("%s[%s: %s] Error %d%s"), pre, nm, f->name, exit_code, post);
+ _("%s[%s: %s] Error %d%s%s"), pre, nm, f->name, exit_code, post,
+ shuf);
else
{
const char *s = strsignal (exit_sig);
error (NILF, l + strlen (s) + strlen (dump),
- "%s[%s: %s] %s%s%s", pre, nm, f->name, s, dump, post);
+ "%s[%s: %s] %s%s%s%s", pre, nm, f->name, s, dump, post, shuf);
}
OUTPUT_UNSET ();
diff --git a/src/main.c b/src/main.c
index aed4d815..dd1713c2 100644
--- a/src/main.c
+++ b/src/main.c
@@ -24,6 +24,7 @@ this program. If not, see <http://www.gnu.org/licenses/>. */
#include "rule.h"
#include "debug.h"
#include "getopt.h"
+#include "shuf.h"
#include <assert.h>
#ifdef _AMIGA
@@ -233,6 +234,12 @@ static const int inf_jobs = 0;
static char *jobserver_auth = NULL;
+/* Shuffle mode for goals and prerequisites. */
+
+static char *shuffle_mode_arg = NULL;
+static enum shuffle_mode sm = sm_none;
+static int shuffle_seed = 0;
+
/* Handle for the mutex used on Windows to synchronize output of our
children under -O. */
@@ -358,6 +365,9 @@ static const char *const usage[] =
N_("\
-R, --no-builtin-variables Disable the built-in variable settings.\n"),
N_("\
+ --shuffle[=[<seed>|random|identity|reverse|none]\n\
+ Perform shuffle of prerequisites and goals.\n"),
+ N_("\
-s, --silent, --quiet Don't echo recipes.\n"),
N_("\
--no-silent Echo recipes (disable --silent mode).\n"),
@@ -472,6 +482,7 @@ static const struct command_switch switches[] =
{ CHAR_MAX+8, flag_off, &silent_flag, 1, 1, 0, 0, &default_silent_flag,
"no-silent" },
{ CHAR_MAX+9, string, &jobserver_auth, 1, 0, 0, 0, 0, "jobserver-fds" },
+ { CHAR_MAX+10, string, &shuffle_mode_arg, 1, 1, 0, "random", 0, "shuffle"
},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
@@ -1498,6 +1509,36 @@ main (int argc, char **argv, char **envp)
arg_job_slots = env_slots;
}
+ /* Handle shuffle mode argument. */
+ if (shuffle_mode_arg)
+ {
+ if (streq (shuffle_mode_arg, "none"))
+ sm = sm_none;
+ else if (streq (shuffle_mode_arg, "identity"))
+ sm = sm_identity;
+ else if (streq (shuffle_mode_arg, "reverse"))
+ sm = sm_reverse;
+ else if (streq (shuffle_mode_arg, "random"))
+ sm = sm_random;
+ /* Assume explicit seed if starts from a digit. */
+ else if (ISDIGIT (shuffle_mode_arg[0]))
+ {
+ sm = sm_random;
+ shuffle_seed = atoi (shuffle_mode_arg);
+ }
+ else
+ {
+ O (error, NILF, _("error: unsupported --shuffle= option."));
+ die (MAKE_FAILURE);
+ }
+ set_shuffle_mode (sm, shuffle_seed);
+
+ /* Write fixed seed back to argument list to propagate fixed seed
+ to child $(MAKE) runs. */
+ free (shuffle_mode_arg);
+ shuffle_mode_arg = xstrdup (shuffle_get_str_value ());
+ }
+
/* Set a variable specifying whether stdout/stdin is hooked to a TTY. */
#ifdef HAVE_ISATTY
if (isatty (fileno (stdout)))
@@ -2652,6 +2693,10 @@ main (int argc, char **argv, char **envp)
O (fatal, NILF, _("No targets specified and no makefile found"));
}
+ /* Shuffle prerequisites to catch makefiles with incomplete depends. */
+
+ shuffle_goaldeps_recursive (goals);
+
/* Update the goals. */
DB (DB_BASIC, (_("Updating goal targets....\n")));
diff --git a/src/remake.c b/src/remake.c
index bd6d8e51..82d24017 100644
--- a/src/remake.c
+++ b/src/remake.c
@@ -93,8 +93,8 @@ update_goal_chain (struct goaldep *goaldeps)
enum update_status status = us_none;
/* Duplicate the chain so we can remove things from it. */
-
- struct dep *goals = copy_dep_chain ((struct dep *)goaldeps);
+ struct dep *goals_orig = copy_dep_chain ((struct dep *)goaldeps);
+ struct dep *goals = goals_orig;
goal_list = rebuilding_makefiles ? goaldeps : NULL;
@@ -108,7 +108,7 @@ update_goal_chain (struct goaldep *goaldeps)
while (goals != 0)
{
- struct dep *g, *lastgoal;
+ struct dep *gu, *g, *lastgoal;
/* Start jobs that are waiting for the load to go down. */
@@ -119,13 +119,15 @@ update_goal_chain (struct goaldep *goaldeps)
reap_children (1, 0);
lastgoal = 0;
- g = goals;
- while (g != 0)
+ gu = goals;
+ while (gu != 0)
{
/* Iterate over all double-colon entries for this file. */
struct file *file;
int stop = 0, any_not_updated = 0;
+ g = gu->shuf ? gu->shuf : gu;
+
goal_dep = g;
for (file = g->file->double_colon ? g->file->double_colon : g->file;
@@ -235,31 +237,30 @@ update_goal_chain (struct goaldep *goaldeps)
/* This goal is finished. Remove it from the chain. */
if (lastgoal == 0)
- goals = g->next;
+ goals = gu->next;
else
- lastgoal->next = g->next;
+ lastgoal->next = gu->next;
- /* Free the storage. */
- free (g);
-
- g = lastgoal == 0 ? goals : lastgoal->next;
+ gu = lastgoal == 0 ? goals : lastgoal->next;
if (stop)
break;
}
else
{
- lastgoal = g;
- g = g->next;
+ lastgoal = gu;
+ gu = gu->next;
}
}
/* If we reached the end of the dependency graph update CONSIDERED
for the next pass. */
- if (g == 0)
+ if (gu == 0)
++considered;
}
+ free_dep_chain (goals_orig);
+
if (rebuilding_makefiles)
{
touch_flag = t;
@@ -424,7 +425,7 @@ update_file_1 (struct file *file, unsigned int depth)
FILE_TIMESTAMP this_mtime;
int noexist, must_make, deps_changed;
struct file *ofile;
- struct dep *d, *ad;
+ struct dep *du, *d, *ad;
struct dep amake;
int running = 0;
@@ -532,16 +533,18 @@ update_file_1 (struct file *file, unsigned int depth)
struct dep *lastd = 0;
/* Find the deps we're scanning */
- d = ad->file->deps;
+ du = ad->file->deps;
ad = ad->next;
- while (d)
+ while (du)
{
enum update_status new;
FILE_TIMESTAMP mtime;
int maybe_make;
int dontcare = 0;
+ d = du->shuf ? du->shuf : du;
+
check_renamed (d->file);
mtime = file_mtime (d->file);
@@ -551,14 +554,16 @@ update_file_1 (struct file *file, unsigned int depth)
{
OSS (error, NILF, _("Circular %s <- %s dependency dropped."),
file->name, d->file->name);
+
/* We cannot free D here because our the caller will still have
a reference to it when we were called recursively via
check_dep below. */
if (lastd == 0)
- file->deps = d->next;
+ file->deps = du->next;
else
- lastd->next = d->next;
- d = d->next;
+ lastd->next = du->next;
+
+ du = du->next;
continue;
}
@@ -607,8 +612,8 @@ update_file_1 (struct file *file, unsigned int depth)
d->changed = ((file_mtime (d->file) != mtime)
|| (mtime == NONEXISTENT_MTIME));
- lastd = d;
- d = d->next;
+ lastd = du;
+ du = du->next;
}
}
@@ -617,7 +622,9 @@ update_file_1 (struct file *file, unsigned int depth)
if (must_make || always_make_flag)
{
- for (d = file->deps; d != 0; d = d->next)
+ for (du = file->deps; du != 0; du = du->next)
+ {
+ d = du->shuf ? du->shuf : du;
if (d->file->intermediate)
{
enum update_status new;
@@ -669,6 +676,7 @@ update_file_1 (struct file *file, unsigned int depth)
d->changed = ((file->phony && file->cmds != 0)
|| file_mtime (d->file) != mtime);
}
+ }
}
finish_updating (file);
diff --git a/src/shuf.c b/src/shuf.c
new file mode 100644
index 00000000..5c631bad
--- /dev/null
+++ b/src/shuf.c
@@ -0,0 +1,202 @@
+/* Declarations for target shuffling support.
+Copyright (C) 2022-2022 Free Software Foundation, Inc.
+This file is part of GNU Make.
+
+GNU Make is free software; you can redistribute it and/or modify it under the
+terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program. If not, see <http://www.gnu.org/licenses/>. */
+
+#include <stddef.h>
+
+#include "makeint.h"
+#include "filedef.h"
+#include "dep.h"
+#include "shuf.h"
+
+static void random_shuffle_array (void ** a, size_t len);
+static void reverse_shuffle_array (void ** a, size_t len);
+static void identity_shuffle_array (void ** a, size_t len);
+
+static enum shuffle_mode sm = sm_none;
+static void (*shuffler)(void ** a, size_t len) = 0;
+/* Enough to hold largest '-1234567890' value. */
+static char shuffle_str_value[12];
+
+const char *
+shuffle_get_str_value (void)
+{
+ return shuffle_str_value;
+}
+
+void
+set_shuffle_mode (enum shuffle_mode mode, int seed)
+{
+ sm = mode;
+
+ switch (mode)
+ {
+ case sm_random:
+ if (seed == 0)
+ seed = (int)time(NULL);
+ srand (seed);
+ shuffler = random_shuffle_array;
+ sprintf(shuffle_str_value, "%d", seed);
+ break;
+ case sm_reverse:
+ shuffler = reverse_shuffle_array;
+ strcpy(shuffle_str_value, "reverse");
+ break;
+ case sm_identity:
+ shuffler = identity_shuffle_array;
+ strcpy(shuffle_str_value, "identity");
+ break;
+ case sm_none:
+ shuffle_str_value[0] = '\0';
+ break;
+ }
+}
+
+/* Shuffle array elements using RAND(). */
+static void
+random_shuffle_array (void ** a, size_t len)
+{
+ for (unsigned int i = 0; i < len; i++)
+ {
+ void * t;
+
+ /* Pick random element and swap. */
+ unsigned int j = rand () % len;
+ if (i == j) continue;
+
+ /* Swap. */
+ t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+}
+
+/* Shuffle array elements using reverse order. */
+static void
+reverse_shuffle_array (void ** a, size_t len)
+{
+ for (unsigned int i = 0; i < len / 2; i++)
+ {
+ void * t;
+
+ /* Pick mirror and swap. */
+ unsigned int j = len - 1 - i;
+
+ /* Swap. */
+ t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+}
+
+/* Shuffle array elements using identity order. */
+static void
+identity_shuffle_array (void ** /* a */, size_t /* len */)
+{
+ /* No-op! */
+}
+
+/* A shuffle_goaldeps_recursive sibling. Shuffles 'deps'
+ of each 'file' recursively. */
+void
+shuffle_file_deps_recursive(struct file * f)
+{
+ unsigned int deps = 0;
+ struct dep * dep;
+
+ /* Exit early if shuffling was not requested. */
+ if (sm == sm_none) return;
+
+ /* Implicit rules do not always provide any depends. */
+ if (!f) return;
+
+ /* Avoid repeated shuffles and loops. */
+ if (f->was_shuffled)
+ return;
+ f->was_shuffled = 1;
+
+ /* TODO: below is almost identical to goaldeps shuffle. The only difference
+ is a type change. Worth deduplicating? */
+ for (dep = f->deps; dep; dep = dep->next)
+ deps++;
+
+ /* Allocate array of all deps, store, shuffle, write pointers back. */
+ if (deps)
+ {
+ void ** da = xmalloc (sizeof(struct dep *) * deps);
+ void ** dp;
+
+ /* Store. */
+ for (dep = f->deps, dp = da; dep; dep = dep->next, dp++)
+ *dp = dep;
+
+ /* Shuffle. */
+ shuffler (da, deps);
+
+ /* Write back. */
+ for (dep = f->deps, dp = da; dep; dep = dep->next, dp++)
+ dep->shuf = *dp;
+
+ free (da);
+ }
+
+ /* Shuffle dependencies. */
+ /* TODO: this is a naive recursion. Is it good enough? Or better change it
+ to queue based implementation? */
+ for (dep = f->deps; dep; dep = dep->next)
+ shuffle_file_deps_recursive (dep->file);
+}
+
+/* Shuffle goal dependencies first, then shuffle dependency list
+ of each file reachable from goaldep recursively. Used by
+ --shuffle flag to introduce artificial non-determinism in build
+ order. Returns pointer to head of shuffled list. */
+
+void
+shuffle_goaldeps_recursive(struct goaldep * g)
+{
+ struct goaldep * dep;
+ unsigned int goaldeps = 0;
+
+ /* Exit early if shuffling was not requested. */
+ if (sm == sm_none) return;
+
+ for (dep = g; dep; dep = dep->next)
+ goaldeps++;
+
+ /* Allocate array of all goaldeps, store, shuffle, write pointers back. */
+ if (goaldeps)
+ {
+ void ** da = xmalloc (sizeof(struct goaldep *) * goaldeps);
+ void ** dp;
+
+ /* Store. */
+ for (dep = g, dp = da; dep; dep = dep->next, dp++)
+ *dp = dep;
+
+ /* Shuffle. */
+ shuffler (da, goaldeps);
+
+ /* Write back. */
+ for (dep = g, dp = da; dep; dep = dep->next, dp++)
+ dep->shuf = *dp;
+
+ free (da);
+ }
+
+ /* Shuffle dependencies. */
+ for (dep = g; dep; dep = dep->next)
+ shuffle_file_deps_recursive (dep->file);
+}
diff --git a/src/shuf.h b/src/shuf.h
new file mode 100644
index 00000000..ad694551
--- /dev/null
+++ b/src/shuf.h
@@ -0,0 +1,34 @@
+/* Declarations for target shuffling support.
+Copyright (C) 2022-2022 Free Software Foundation, Inc.
+This file is part of GNU Make.
+
+GNU Make is free software; you can redistribute it and/or modify it under the
+terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* The way goals and rules are shuffled during update. */
+enum shuffle_mode
+ {
+ /* No shuffle data is populated or used. */
+ sm_none,
+ /* Random within dependency list. */
+ sm_random,
+ /* Inverse order. */
+ sm_reverse,
+ /* identity order. Differs from SM_NONE by explicitly populating
+ the traversal order. */
+ sm_identity,
+ };
+
+const char * shuffle_get_str_value (void);
+void set_shuffle_mode (enum shuffle_mode mode, int seed);
+void shuffle_file_deps_recursive (struct file * f);
+void shuffle_goaldeps_recursive (struct goaldep * g);
diff --git a/tests/scripts/options/shuffle-reverse
b/tests/scripts/options/shuffle-reverse
new file mode 100644
index 00000000..eb88f9b5
--- /dev/null
+++ b/tests/scripts/options/shuffle-reverse
@@ -0,0 +1,112 @@
+# -*-perl-*-
+
+$description = "Test the --shuffle option.";
+
+$details = "Verify that --shuffle has expected effect on target order and
argument order.";
+
+run_make_test('
+%:
+ @echo $@
+all: a b c
+',
+'--shuffle=reverse', 'c
+b
+a
+all');
+
+run_make_test('
+%:
+ @echo $@
+all: a b c
+',
+'--shuffle=none', 'a
+b
+c
+all');
+
+run_make_test('
+%:
+ @echo $@
+all: a b c
+',
+'--shuffle=identity', 'a
+b
+c
+all');
+
+# Make sure prerequisites get reverse order and commands don't get affected.
+run_make_test('
+all: foo.o
+ @echo $@
+%.o : %.c
+ @echo cc -c -o $@ $<
+foo.o : foo.c foo.h bar.h baz.h
+%.h:
+ @echo $@
+%.c:
+ @echo $@
+',
+'--shuffle=reverse', 'baz.h
+bar.h
+foo.h
+foo.c
+cc -c -o foo.o foo.c
+all');
+
+# Make sure pattern prerequisites get reverse order and commands don't get
affected.
+run_make_test('
+all: foo_
+ @echo $@
+foo%: arg%1 arg%2 arg%3 arg%4
+ @echo bld $@ $< $(word 3,$^) $(word 2,$^) $(word 4,$^)
+
+arg%:
+ @echo $@
+',
+'--shuffle=reverse', 'arg_4
+arg_3
+arg_2
+arg_1
+bld foo_ arg_1 arg_3 arg_2 arg_4
+all');
+
+# Check if make can survive circular dependency.
+run_make_test('
+all: a_ b_
+ @echo $@
+%_:
+ @echo $@
+
+a_: b_
+b_: a_
+',
+'--shuffle=reverse', 'make: Circular a_ <- b_ dependency dropped.
+a_
+b_
+all');
+
+# Check if order-only dependencies get reordered.
+run_make_test('
+all: a_
+ @echo $@
+%_:
+ @echo $@
+a_: b_ c_ | d_ e_
+',
+'--shuffle=reverse', 'e_
+d_
+c_
+b_
+a_
+all');
+
+# Check if goals are reordered.
+run_make_test('
+%_:
+ @echo $@
+',
+'--shuffle=reverse a_ b_ c_', 'c_
+b_
+a_');
+
+1;
--
2.35.1