The idea of the change is to introduce non-deterministic ordering into goal and prerequisite traversal to imitate non-deterministic ordering of 'make -j' mode.
The implementation is to reorder lists of goals to build and list of dependencies attached to files reachable via goals. tested on the following problematic Makefile: all: a b a: touch a b: cp a b Sample execution looks like: $ while echo ======= && rm -f a b && make --shuffle; do sleep 1; done ======= random seed: --shuffle=1644097687 touch a cp a b ======= random seed: --shuffle=1644097688 cp a b cp: cannot stat 'a': No such file or directory make: *** [Makefile:5: b] Error 1 Note: here first run succeeds while second run fails exposing the failure. Some high level TODOs: - No documentation for the optin yet. - No(?) environment passing for recursive make. I would prefer to share the same see across all calls to get easier reproducers. - The dependency traversal is naive and uses potentially unbounded stack. - srand() / rand() is used from system libc. This might make it harder to reproduce a failure on another machine. But maybe it's fine. If the general shape is reasonable I can try to get it up to standard. What do you think? * src/dep.h: Add 'shuffle_goaldeps_recursive' helper. * src/filedef.h (struct file): Add 'was_shuffled' bit to track visited files. * src/main.c: Add '--shuffle' argument and it's handling. * src/misc.c: Implement 'shuffle_goaldeps_recursive()' helper. --- src/dep.h | 1 + src/filedef.h | 2 + src/main.c | 23 +++++++++++ src/misc.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 135 insertions(+) diff --git a/src/dep.h b/src/dep.h index e492a0b3..2b098650 100644 --- a/src/dep.h +++ b/src/dep.h @@ -135,3 +135,4 @@ struct dep *copy_dep_chain (const struct dep *d); struct goaldep *read_all_makefiles (const char **makefiles); void eval_buffer (char *buffer, const floc *floc); enum update_status update_goal_chain (struct goaldep *goals); +struct goaldep * shuffle_goaldeps_recursive(struct goaldep * g); 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/main.c b/src/main.c index 2d98a64b..9731f3d3 100644 --- a/src/main.c +++ b/src/main.c @@ -233,6 +233,12 @@ static const int inf_jobs = 0; static char *jobserver_auth = NULL; +#define NO_SHUFFLE (-1) +#define RANDOM_SHUFFLE (0) +static int arg_shuffle_seed = NO_SHUFFLE; +static const int no_shuffle = NO_SHUFFLE; +static const int random_shuffle = RANDOM_SHUFFLE; + /* Handle for the mutex used on Windows to synchronize output of our children under -O. */ @@ -358,6 +364,8 @@ static const char *const usage[] = N_("\ -R, --no-builtin-variables Disable the built-in variable settings.\n"), N_("\ + --shuffle[=seed] Perform random shuffle on prerequisites.\n"), + N_("\ -s, --silent, --quiet Don't echo recipes.\n"), N_("\ --no-silent Echo recipes (disable --silent mode).\n"), @@ -472,6 +480,8 @@ 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, positive_int, &arg_shuffle_seed, 1, 0, 0, &random_shuffle, + &no_shuffle, "shuffle" }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; @@ -1498,6 +1508,11 @@ main (int argc, char **argv, char **envp) arg_job_slots = env_slots; } + if (arg_shuffle_seed == RANDOM_SHUFFLE) + arg_shuffle_seed = (int)time(NULL); + if (arg_shuffle_seed != NO_SHUFFLE) + printf("random seed: --shuffle=%i\n", arg_shuffle_seed); + /* Set a variable specifying whether stdout/stdin is hooked to a TTY. */ #ifdef HAVE_ISATTY if (isatty (fileno (stdout))) @@ -2645,6 +2660,14 @@ 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. */ + if (arg_shuffle_seed != NO_SHUFFLE) + { + /* TODO: provide portable deterministic rand/srand. */ + srand(arg_shuffle_seed); + goals = shuffle_goaldeps_recursive (goals); + } + /* Update the goals. */ DB (DB_BASIC, (_("Updating goal targets....\n"))); diff --git a/src/misc.c b/src/misc.c index f400135b..b46c6d07 100644 --- a/src/misc.c +++ b/src/misc.c @@ -854,3 +854,112 @@ mempcpy (void *dest, const void *src, size_t n) return (char *) memcpy (dest, src, n) + n; } #endif + +/* Shuffle array elements. */ +static void 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; + } +} + +/* A shuffle_goaldeps_recursive sibling. Shuffles 'deps' + of each 'file' recursively. */ +static void +shuffle_file_deps_recursive(struct file * f) +{ + unsigned int deps = 0; + struct dep * dep; + + /* 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) + { + struct dep ** da = xmalloc (sizeof(struct dep *) * (deps + 1)); + struct dep ** dp; + + /* Store. */ + for (dep = f->deps, dp = da; dep; dep = dep->next) + *dp++ = dep; + *dp = NULL; + + /* Shuffle. */ + shuffle_array ((void**)da, deps); + + /* Write back. */ + for (dp = da; *dp; dp++) + (*dp)->next = *(dp + 1); + f->deps = da[0]; + + 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. */ + +struct goaldep * +shuffle_goaldeps_recursive(struct goaldep * g) +{ + struct goaldep * result = 0; + struct goaldep * dep; + unsigned int goaldeps = 0; + + for (dep = g; dep; dep = dep->next) + goaldeps++; + + /* Allocate array of all goaldeps, store, shuffle, write pointers back. */ + if (goaldeps) + { + struct goaldep ** da = xmalloc (sizeof(struct goaldep *) * (goaldeps + 1)); + struct goaldep ** dp; + + /* Store. */ + for (dep = g, dp = da; dep; dep = dep->next) + *dp++ = dep; + *dp = NULL; + + /* Shuffle. */ + shuffle_array ((void**)da, goaldeps); + + /* Write back. */ + for (dp = da; *dp; dp++) + (*dp)->next = *(dp + 1); + result = da[0]; + + free (da); + } + + /* Shuffle dependencies. */ + for (dep = result; dep; dep = dep->next) + shuffle_file_deps_recursive (dep->file); + + return result; +} -- 2.34.1