On Sat, Feb 19, 2022 at 09:57:13AM +0200, Eli Zaretskii wrote:
> > * Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
> > * builddos.bat: Add shuf.o into build script.
> This should also update build_w32.bat, which is used to build Make on
> MS-Windows. I think NEWS should also call out the new feature.
Sounds good! Added there and to makefile.com.
> > +Note that @code{make --shuffle clean all install} does reorder goals
> > +similar to how @code{make -j clean all install} runs all targets in
>
> These should use @kbd, not @code, since you are describing commands
> the user will type. I also recommend to wrap each one in @w{..}, so
> that these (long) command isn't broken between 2 lines.
Changed to @w{@kbd{..}}.
> > +@samp{--shuffle=} accepts an optional value:
>
> I think nowadays it's customary to use @option as markup for
> command-line options (unless Make wants to keep its manual compatible
> to very old versions of Texinfo -- this is up to Paul to decide).
I left it as is as I see on @option{} being used in make.texi.
Can do as a separate patch if others agree.
> > + /* TODO: could we make this shuffle more deterministic and less
> > + dependent on current filesystem state? */
> > + if (! file->was_shuffled)
> > + shuffle_file_deps_recursive (file);
>
> Should this TODO be resolved before installing the feature?
Sounds good. Added re-seeding for each implicit dependency to get
more deterministic shuffling.
> > + /* 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 ());
> > + }
>
> Should this be factored out and put on shuf.c?
Sounds goo.d Moved out to shuf.c. Only left small option rewrite bit in main.c.
> > + switch (mode)
> > + {
> > + case sm_random:
> > + if (seed == 0)
> > + seed = (int)time(NULL);
> > + srand (seed);
> > + shuffler = random_shuffle_array;
> > + sprintf(shuffle_str_value, "%d", seed);
> ^^
> Stylistic comment: I believe our style is to leave one space between
> the function name and the opening parenthesis (here and elsewhere in
> the patch).
Good catch! Added whitespace everywhere in the new code.
> > +random_shuffle_array (void ** a, size_t len)
> > +{
> > + for (unsigned int i = 0; i < len; i++)
> ^^^^^^^^^^^^^^^^^^^
> This requires some minimal level of ANSI C support that I'm not sure
> Make already requires. Older compilers will error out here.
i think it does. Moved out to a separate declaration and switched to
size_t while at it to match function argument type.
> > + /* TODO: below is almost identical to goaldeps shuffle. The only
> > difference
> > + is a type change. Worth deduplicating? */
>
> Another TODO.
Deduplicated by coercing 'strct goaldep*' traversal into 'struct dep *'.
Similar to other dep.h primitives.
> > + /* Shuffle dependencies. */
> > + /* TODO: this is a naive recursion. Is it good enough? Or better
> > change it
> > + to queue based implementation? */
>
> And another one.
Dropped a TODO as it's no worse than naive recursion in update_file_1.
> > --- /dev/null
> > +++ b/tests/scripts/options/shuffle-reverse
>
> This test doesn't seem to test the random option. I understand why
> this is not easy, but shouldn't it still be tested, if only to make
> sure the option works, and also that different seeds produce different
> outcomes?
Added tests/scripts/misc/rand-shuf test to test for random order and
for unchanged order for a fixed seed.
Attaching v3-0001-Add-shuffle-argument-support.patch with all the above applied.
Thank you for thorough review, Eli!
--
Sergei
>From 42a1df1b2873a3e362936cef474273dca08d2c57 Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich <siarh...@google.com>
Date: Fri, 4 Feb 2022 22:43:28 +0000
Subject: [PATCH v3] Add '--shuffle' argument support
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.
There are a few shuffle modes available:
- --shuffle (or --shuffle=random): use random seed and produce random order
- --shuffle=identity: use original order, but store and use it explicitly
(most useful for GNU make testing)
- --shuffle=reverse: use inverse order for every goal list and prerequisite
list. It is frequently enough to trigger simplest bugs.
- --shuffle=none: disable shuffle infrastructure completely. Useful to negate
effect of previous --shuffle options.
* Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
* builddos.bat: Add shuf.o into build script.
* build_w32.bat: Add shuf.c into build script.
* doc/make.1: Add '--shuffle' option description.
* doc/make.texi: Add '--shuffle' option description.
* makefile.com: Add shuf.c into build script.
* 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/misc/rand-shuf: New file with randomness tests.
* tests/scripts/options/shuffle-reverse: New file with basic tests.
---
Makefile.am | 5 +-
build_w32.bat | 1 +
builddos.bat | 3 +-
doc/make.1 | 34 ++++
doc/make.texi | 51 ++++++
makefile.com | 2 +-
src/dep.h | 1 +
src/filedef.h | 2 +
src/implicit.c | 7 +
src/job.c | 21 ++-
src/main.c | 29 ++++
src/remake.c | 138 ++++++++-------
src/shuf.c | 241 ++++++++++++++++++++++++++
src/shuf.h | 23 +++
tests/scripts/misc/rand-shuf | 40 +++++
tests/scripts/options/shuffle-reverse | 112 ++++++++++++
16 files changed, 638 insertions(+), 72 deletions(-)
create mode 100644 src/shuf.c
create mode 100644 src/shuf.h
create mode 100644 tests/scripts/misc/rand-shuf
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/build_w32.bat b/build_w32.bat
index 17066d72..06a234e1 100755
--- a/build_w32.bat
+++ b/build_w32.bat
@@ -257,6 +257,7 @@ call :Compile src/read
call :Compile src/remake
call :Compile src/remote-stub
call :Compile src/rule
+call :Compile src/shuf
call :Compile src/signame
call :Compile src/strcache
call :Compile src/variable
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..3e6b5bbe 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 @w{@kbd{make --shuffle clean all install}} does reorder goals
+similar to how @w{@kbd{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/makefile.com b/makefile.com
index eff906ef..c86a673a 100644
--- a/makefile.com
+++ b/makefile.com
@@ -76,7 +76,7 @@ $ filelist = "[.src]ar [.src]arscan [.src]commands
[.src]default [.src]dir " + -
"[.src]hash [.src]implicit [.src]job [.src]load [.src]main " + -
"[.src]misc [.src]read [.src]remake [.src]remote-stub " + -
"[.src]rule [.src]output [.src]signame [.src]variable " + -
- "[.src]version [.src]strcache [.src]vpath " + -
+ "[.src]version [.src]shuf [.src]strcache [.src]vpath " + -
"[.src]vmsfunctions [.src]vmsify [.src]vms_progname " + -
"[.src]vms_exit [.src]vms_export_symbol " + -
"[.lib]alloca [.lib]fnmatch [.lib]glob [.src]getopt1 [.src]getopt"
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..bdefd775 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,14 @@ 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;
}
+ if (!file->was_shuffled)
+ shuffle_deps_recursive (file->deps);
+
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..cd5c83f4 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,18 @@ child_error (struct child *child,
nm = a;
}
- l = strlen (pre) + strlen (nm) + strlen (f->name) + strlen (post);
+ shuf = shuffle_get_mode ();
+ if (shuf)
+ {
+ char *a = alloca (11 + strlen (shuf) + 1);
+ sprintf (a, " --shuffle=%s", shuf);
+ shuf = a;
+ }
+ else
+ shuf = "";
+
+ l = strlen (pre) + strlen (nm) + strlen (f->name) + strlen (post)
+ + strlen (shuf);
OUTPUT_SET (&child->output);
@@ -570,12 +584,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..e8526e4a 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,10 @@ static const int inf_jobs = 0;
static char *jobserver_auth = NULL;
+/* Shuffle mode for goals and prerequisites. */
+
+static char *shuffle_mode = NULL;
+
/* Handle for the mutex used on Windows to synchronize output of our
children under -O. */
@@ -358,6 +363,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 +480,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, 1, 1, 0, "random", 0, "shuffle" },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }
};
@@ -1498,6 +1507,22 @@ main (int argc, char **argv, char **envp)
arg_job_slots = env_slots;
}
+ /* Handle shuffle mode argument. */
+ if (shuffle_mode)
+ {
+ const char *effective_mode;
+ shuffle_set_mode (shuffle_mode);
+
+ /* Write fixed seed back to argument list to propagate mode and
+ fixed seed to child $(MAKE) runs. */
+ free (shuffle_mode);
+ effective_mode = shuffle_get_mode ();
+ if (effective_mode)
+ shuffle_mode = xstrdup (effective_mode);
+ else
+ shuffle_mode = NULL;
+ }
+
/* Set a variable specifying whether stdout/stdin is hooked to a TTY. */
#ifdef HAVE_ISATTY
if (isatty (fileno (stdout)))
@@ -2652,6 +2677,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..4f25d4de 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;
-
- /* Free the storage. */
- free (g);
+ lastgoal->next = gu->next;
- 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,58 +622,61 @@ update_file_1 (struct file *file, unsigned int depth)
if (must_make || always_make_flag)
{
- for (d = file->deps; d != 0; d = d->next)
- if (d->file->intermediate)
- {
- enum update_status new;
- int dontcare = 0;
+ for (du = file->deps; du != 0; du = du->next)
+ {
+ d = du->shuf ? du->shuf : du;
+ if (d->file->intermediate)
+ {
+ enum update_status new;
+ int dontcare = 0;
- FILE_TIMESTAMP mtime = file_mtime (d->file);
- check_renamed (d->file);
- d->file->parent = file;
+ FILE_TIMESTAMP mtime = file_mtime (d->file);
+ check_renamed (d->file);
+ d->file->parent = file;
- /* Inherit dontcare flag from our parent. */
- if (rebuilding_makefiles)
- {
- dontcare = d->file->dontcare;
- d->file->dontcare = file->dontcare;
- }
+ /* Inherit dontcare flag from our parent. */
+ if (rebuilding_makefiles)
+ {
+ dontcare = d->file->dontcare;
+ d->file->dontcare = file->dontcare;
+ }
- /* We may have already considered this file, when we didn't know
- we'd need to update it. Force update_file() to consider it and
- not prune it. */
- d->file->considered = 0;
+ /* We may have already considered this file, when we didn't know
+ we'd need to update it. Force update_file() to consider it
and
+ not prune it. */
+ d->file->considered = 0;
- new = update_file (d->file, depth);
- if (new > dep_status)
- dep_status = new;
+ new = update_file (d->file, depth);
+ if (new > dep_status)
+ dep_status = new;
- /* Restore original dontcare flag. */
- if (rebuilding_makefiles)
- d->file->dontcare = dontcare;
+ /* Restore original dontcare flag. */
+ if (rebuilding_makefiles)
+ d->file->dontcare = dontcare;
- check_renamed (d->file);
+ check_renamed (d->file);
- {
- struct file *f = d->file;
- if (f->double_colon)
- f = f->double_colon;
- do
- {
- running |= (f->command_state == cs_running
- || f->command_state == cs_deps_running);
- f = f->prev;
- }
- while (f != 0);
- }
+ {
+ struct file *f = d->file;
+ if (f->double_colon)
+ f = f->double_colon;
+ do
+ {
+ running |= (f->command_state == cs_running
+ || f->command_state == cs_deps_running);
+ f = f->prev;
+ }
+ while (f != 0);
+ }
- if (dep_status && !keep_going_flag)
- break;
+ if (dep_status && !keep_going_flag)
+ break;
- if (!running)
- d->changed = ((file->phony && file->cmds != 0)
- || file_mtime (d->file) != mtime);
- }
+ if (!running)
+ 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..0a8ff5b1
--- /dev/null
+++ b/src/shuf.c
@@ -0,0 +1,241 @@
+/* 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"
+
+/* Supported shuffle modes. */
+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);
+
+/* 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,
+ };
+
+/* Shuffle configuration. */
+static struct {
+ enum shuffle_mode mode;
+ int seed;
+ void (*shuffler)(void ** a, size_t len);
+ /* Enough to hold largest '-1234567890' value. */
+ char strval[12];
+} config = { sm_none, 0, 0, { 0 }, };
+
+/* Return string value of --shuffle= option passed.
+ If none was passed or --shuffle=none was used function
+ returns NULL. */
+const char *
+shuffle_get_mode (void)
+{
+ if (!config.strval[0])
+ return NULL;
+
+ return config.strval;
+}
+
+void
+shuffle_set_mode (const char *cmdarg)
+{
+ enum shuffle_mode mode;
+ int seed = 0;
+
+ /* Parse supported '--shuffle' mode. */
+ if (streq (cmdarg, "random"))
+ mode = sm_random;
+ else if (streq (cmdarg, "reverse"))
+ mode = sm_reverse;
+ else if (streq (cmdarg, "identity"))
+ mode = sm_identity;
+ else if (streq (cmdarg, "none"))
+ mode = sm_none;
+ /* Assume explicit seed if starts from a digit. */
+ else if (ISDIGIT (cmdarg[0]))
+ {
+ mode = sm_random;
+ seed = atoi (cmdarg);
+ }
+ else
+ {
+ O (error, NILF, _("error: unsupported '--shuffle' mode."));
+ die (MAKE_FAILURE);
+ }
+
+ /* Update shuffle configuration. */
+ config.mode = mode;
+
+ switch (mode)
+ {
+ case sm_random:
+ if (seed == 0)
+ seed = (int)time (NULL);
+ config.seed = seed;
+ config.shuffler = random_shuffle_array;
+ sprintf (config.strval, "%d", seed);
+ break;
+ case sm_reverse:
+ config.shuffler = reverse_shuffle_array;
+ strcpy (config.strval, "reverse");
+ break;
+ case sm_identity:
+ config.shuffler = identity_shuffle_array;
+ strcpy (config.strval, "identity");
+ break;
+ case sm_none:
+ config.strval[0] = '\0';
+ break;
+ }
+}
+
+/* Shuffle array elements using RAND(). */
+static void
+random_shuffle_array (void ** a, size_t len)
+{
+ size_t i;
+ for (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)
+{
+ size_t i;
+ for (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! */
+}
+
+/* Shuffle list of dependencies by populating '->next'
+ field in each 'struct dep'. */
+static void
+shuffle_deps (struct dep *deps)
+{
+ size_t ndeps = 0;
+ struct dep *dep;
+ void **da;
+ void **dp;
+
+ for (dep = deps; dep; dep = dep->next)
+ ndeps++;
+
+ if (ndeps == 0)
+ return;
+
+ /* Allocate array of all deps, store, shuffle, write back. */
+ da = xmalloc (sizeof (struct dep *) * ndeps);
+
+ /* Store locally. */
+ for (dep = deps, dp = da; dep; dep = dep->next, dp++)
+ *dp = dep;
+
+ /* Shuffle. */
+ config.shuffler (da, ndeps);
+
+ /* Write back. */
+ for (dep = deps, dp = da; dep; dep = dep->next, dp++)
+ dep->shuf = *dp;
+
+ free (da);
+}
+
+/* Shuffle 'deps' of each 'file' recursively. */
+static void
+shuffle_file_deps_recursive (struct file *f)
+{
+ struct dep * dep;
+
+ /* 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;
+
+ shuffle_deps (f->deps);
+
+ /* Shuffle dependencies. */
+ 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. .*/
+
+void
+shuffle_deps_recursive (struct dep *deps)
+{
+ struct dep *dep;
+
+ /* Exit early if shuffling was not requested. */
+ if (config.mode == sm_none)
+ return;
+
+ /* Set specific seed at the top level of recursion. */
+ if (config.mode == sm_random)
+ srand (config.seed);
+
+ shuffle_deps (deps);
+
+ /* Shuffle dependencies. */
+ for (dep = deps; 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..fb473b7d
--- /dev/null
+++ b/src/shuf.h
@@ -0,0 +1,23 @@
+/* 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/>. */
+
+void shuffle_set_mode (const char *cmdarg);
+const char * shuffle_get_mode (void);
+void shuffle_deps_recursive (struct dep * g);
+SI void shuffle_goaldeps_recursive (struct goaldep *goaldeps)
+{
+ shuffle_deps_recursive ((struct dep *)goaldeps);
+}
diff --git a/tests/scripts/misc/rand-shuf b/tests/scripts/misc/rand-shuf
new file mode 100644
index 00000000..ec7daf1a
--- /dev/null
+++ b/tests/scripts/misc/rand-shuf
@@ -0,0 +1,40 @@
+# -*-perl-*-
+$description = "Test shuffle randomness.";
+
+# TEST 1: Fixed seed should yield the same order from run to run.
+
+$makefile = &get_tmpfile;
+
+open(MAKEFILE, "> $makefile");
+print MAKEFILE <<'EOF';
+# More target prerequisites lower collision chance in TEST 2
+all: a_ b_ c_ d_ e_ f_ g_ i_ j_ k_ l_
+%:
+ echo $@
+EOF
+close(MAKEFILE);
+
+$log1 = &get_logfile;
+$log2 = &get_logfile;
+&run_make_with_options($makefile, "--shuffle=12345", $log1);
+&run_make_with_options($makefile, "--shuffle=12345", $log2);
+
+&compare_output(&read_file_into_string($log1), $log2);
+
+# TEST 2: Sequential runs should produce different orders.
+
+$log3 = &get_logfile;
+$log4 = &get_logfile;
+&run_make_with_options($makefile, "--shuffle", $log3);
+# --shuffle uses random seed based on current time in seconds.
+# Give it chance to change seed.
+sleep(2);
+&run_make_with_options($makefile, "--shuffle", $log4);
+
+++$tests_run;
+if (&read_file_into_string($log3) ne &read_file_into_string($log4)) {
+ print "ok\n" if $debug;
+ ++$tests_passed;
+}
+
+1;
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
