bug-make
[Top][All Lists]
Advanced

[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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]