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 }