src/shuffle.c

   1 /* Provide prerequisite shuffle support.
   2 Copyright (C) 2022 Free Software Foundation, Inc.
   3 This file is part of GNU Make.
   4
   5 GNU Make is free software; you can redistribute it and/or modify it under the
   6 terms of the GNU General Public License as published by the Free Software
   7 Foundation; either version 3 of the License, or (at your option) any later
   8 version.
   9
  10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  12 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License along with
  15 this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 #include "makeint.h"
  18
  19 #include "shuffle.h"
  20
  21 #include "filedef.h"
  22 #include "dep.h"
  23
  24 /* Supported shuffle modes.  */
  25 static void random_shuffle_array (void ** a, size_t len);
  26 static void reverse_shuffle_array (void ** a, size_t len);
  27 static void identity_shuffle_array (void ** a, size_t len);
  28
  29 /* The way goals and rules are shuffled during update.  */
  30 enum shuffle_mode
  31   {
  32     /* No shuffle data is populated or used.  */
  33     sm_none,
  34     /* Random within dependency list.  */
  35     sm_random,
  36     /* Inverse order.  */
  37     sm_reverse,
  38     /* identity order. Differs from SM_NONE by explicitly populating
  39        the traversal order.  */
  40     sm_identity,
  41   };
  42
  43 /* Shuffle configuration.  */
  44 static struct
  45   {
  46     enum shuffle_mode mode;
  47     unsigned int seed;
  48     void (*shuffler) (void **a, size_t len);
  49     char strval[INTSTR_LENGTH + 1];
  50   } config = { sm_none, 0, NULL, "" };
  51
  52 /* Return string value of --shuffle= option passed.
  53    If none was passed or --shuffle=none was used function
  54    returns NULL.  */
  55 const char *
  56 shuffle_get_mode ()
  57 {
  58   return config.strval[0] == '\0' ? NULL : config.strval;
  59 }
  60
  61 void
  62 shuffle_set_mode (const char *cmdarg)
  63 {
  64   /* Parse supported '--shuffle' mode.  */
  65   if (strcasecmp (cmdarg, "reverse") == 0)
  66     {
  67       config.mode = sm_reverse;
  68       config.shuffler = reverse_shuffle_array;
  69       strcpy (config.strval, "reverse");
  70     }
  71   else if (strcasecmp (cmdarg, "identity") == 0)
  72     {
  73       config.mode = sm_identity;
  74       config.shuffler = identity_shuffle_array;
  75       strcpy (config.strval, "identity");
  76     }
  77   else if (strcasecmp (cmdarg, "none") == 0)
  78     {
  79       config.mode = sm_none;
  80       config.shuffler = NULL;
  81       config.strval[0] = '\0';
  82     }
  83   else
  84     {
  85       if (strcasecmp (cmdarg, "random") == 0)
  86         config.seed = make_rand ();
  87       else
  88         {
  89           /* Assume explicit seed.  */
  90           const char *err;
  91           config.seed = make_toui (cmdarg, &err);
  92           if (err)
  93             OSS (fatal, NILF, _("invalid shuffle mode: %s: '%s'"), err, cmdarg);
  94         }
  95
  96       config.mode = sm_random;
  97       config.shuffler = random_shuffle_array;
  98       sprintf (config.strval, "%u", config.seed);
  99     }
 100 }
 101
 102 /* Shuffle array elements using RAND().  */
 103 static void
 104 random_shuffle_array (void **a, size_t len)
 105 {
 106   size_t i;
 107   for (i = 0; i < len; i++)
 108     {
 109       void *t;
 110
 111       /* Pick random element and swap. */
 112       unsigned int j = make_rand () % len;
 113       if (i == j)
 114         continue;
 115
 116       /* Swap. */
 117       t = a[i];
 118       a[i] = a[j];
 119       a[j] = t;
 120     }
 121 }
 122
 123 /* Shuffle array elements using reverse order.  */
 124 static void
 125 reverse_shuffle_array (void **a, size_t len)
 126 {
 127   size_t i;
 128   for (i = 0; i < len / 2; i++)
 129     {
 130       void *t;
 131
 132       /* Pick mirror and swap. */
 133       size_t j = len - 1 - i;
 134
 135       /* Swap. */
 136       t = a[i];
 137       a[i] = a[j];
 138       a[j] = t;
 139     }
 140 }
 141
 142 /* Shuffle array elements using identity order.  */
 143 static void
 144 identity_shuffle_array (void **a UNUSED, size_t len UNUSED)
 145 {
 146   /* No-op!  */
 147 }
 148
 149 /* Shuffle list of dependencies by populating '->shuf'
 150    field in each 'struct dep'.  */
 151 static void
 152 shuffle_deps (struct dep *deps)
 153 {
 154   size_t ndeps = 0;
 155   struct dep *dep;
 156   void **da;
 157   void **dp;
 158
 159   for (dep = deps; dep; dep = dep->next)
 160     {
 161       /* Do not reshuffle prerequisites if any .WAIT is present.  */
 162       if (dep->wait_here)
 163         return;
 164
 165       ndeps++;
 166     }
 167
 168   if (ndeps == 0)
 169     return;
 170
 171   /* Allocate array of all deps, store, shuffle, write back.  */
 172   da = xmalloc (sizeof (struct dep *) * ndeps);
 173
 174   /* Store locally.  */
 175   for (dep = deps, dp = da; dep; dep = dep->next, dp++)
 176     *dp = dep;
 177
 178   /* Shuffle.  */
 179   config.shuffler (da, ndeps);
 180
 181   /* Write back.  */
 182   for (dep = deps, dp = da; dep; dep = dep->next, dp++)
 183     dep->shuf = *dp;
 184
 185   free (da);
 186 }
 187
 188 /* Shuffle 'deps' of each 'file' recursively.  */
 189 static void
 190 shuffle_file_deps_recursive (struct file *f)
 191 {
 192   struct dep *dep;
 193
 194   /* Implicit rules do not always provide any depends.  */
 195   if (!f)
 196     return;
 197
 198   /* Avoid repeated shuffles and loops.  */
 199   if (f->was_shuffled)
 200     return;
 201   f->was_shuffled = 1;
 202
 203   shuffle_deps (f->deps);
 204
 205   /* Shuffle dependencies. */
 206   for (dep = f->deps; dep; dep = dep->next)
 207     shuffle_file_deps_recursive (dep->file);
 208 }
 209
 210 /* Shuffle goal dependencies first, then shuffle dependency list
 211    of each file reachable from goaldep recursively.  Used by
 212    --shuffle flag to introduce artificial non-determinism in build
 213    order.  .*/
 214
 215 void
 216 shuffle_deps_recursive (struct dep *deps)
 217 {
 218   struct dep *dep;
 219
 220   /* Exit early if shuffling was not requested.  */
 221   if (config.mode == sm_none)
 222     return;
 223
 224   /* Do not reshuffle prerequisites if .NOTPARALLEL was specified.  */
 225   if (not_parallel)
 226     return;
 227
 228   /* Set specific seed at the top level of recursion.  */
 229   if (config.mode == sm_random)
 230     make_seed (config.seed);
 231
 232   shuffle_deps (deps);
 233
 234   /* Shuffle dependencies. */
 235   for (dep = deps; dep; dep = dep->next)
 236     shuffle_file_deps_recursive (dep->file);
 237 }