From: Sergei Trofimovich <siarh...@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