[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] RFC: add --shuffle[=seed] argument support
From: |
Sergei Trofimovich |
Subject: |
[PATCH] RFC: add --shuffle[=seed] argument support |
Date: |
Sat, 5 Feb 2022 22:04:25 +0000 |
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
- [PATCH] RFC: add --shuffle[=seed] argument support,
Sergei Trofimovich <=
- Re: [PATCH] RFC: add --shuffle[=seed] argument support, Alejandro Colomar (man-pages), 2022/02/05
- Re: [PATCH] RFC: add --shuffle[=seed] argument support, Paul Smith, 2022/02/05
- Re: [PATCH] RFC: add --shuffle[=seed] argument support, Sergei Trofimovich, 2022/02/06
- [PATCH v2] Add '--shuffle' argument support, Sergei Trofimovich, 2022/02/18
- Re: [PATCH v2] Add '--shuffle' argument support, Eli Zaretskii, 2022/02/19
- Re: [PATCH v2] Add '--shuffle' argument support, Sergei Trofimovich, 2022/02/20
- [PATCH v4] Add '--shuffle' argument support, Sergei Trofimovich, 2022/02/20
- Re: [PATCH v4] Add '--shuffle' argument support, Tim Murphy, 2022/02/20
- Re: [PATCH] RFC: add --shuffle[=seed] argument support, Sergei Trofimovich, 2022/02/18