1 | /* Test that threads generate distinct streams of randomness. |
2 | Copyright (C) 2022-2024 Free Software Foundation, Inc. |
3 | This file is part of the GNU C Library. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <https://www.gnu.org/licenses/>. */ |
18 | |
19 | #include <array_length.h> |
20 | #include <sched.h> |
21 | #include <stdio.h> |
22 | #include <stdlib.h> |
23 | #include <string.h> |
24 | #include <support/check.h> |
25 | #include <support/namespace.h> |
26 | #include <support/support.h> |
27 | #include <support/xthread.h> |
28 | |
29 | /* Number of arc4random_buf calls per thread. */ |
30 | enum { count_per_thread = 2048 }; |
31 | |
32 | /* Number of threads computing randomness. */ |
33 | enum { inner_threads = 4 }; |
34 | |
35 | /* Number of threads launching other threads. */ |
36 | static int outer_threads = 1; |
37 | |
38 | /* Number of launching rounds performed by the outer threads. */ |
39 | enum { outer_rounds = 10 }; |
40 | |
41 | /* Maximum number of bytes generated in an arc4random call. */ |
42 | enum { max_size = 32 }; |
43 | |
44 | /* Sizes generated by threads. Must be long enough to be unique with |
45 | high probability. */ |
46 | static const int sizes[] = { 12, 15, 16, 17, 24, 31, max_size }; |
47 | |
48 | /* Data structure to capture randomness results. */ |
49 | struct blob |
50 | { |
51 | unsigned int size; |
52 | int thread_id; |
53 | unsigned int index; |
54 | unsigned char bytes[max_size]; |
55 | }; |
56 | |
57 | struct subprocess_args |
58 | { |
59 | struct blob *blob; |
60 | void (*func)(unsigned char *, size_t); |
61 | }; |
62 | |
63 | static void |
64 | generate_arc4random (unsigned char *bytes, size_t size) |
65 | { |
66 | int i; |
67 | for (i = 0; i < size / sizeof (uint32_t); i++) |
68 | { |
69 | uint32_t x = arc4random (); |
70 | memcpy (&bytes[4 * i], &x, sizeof x); |
71 | } |
72 | int rem = size % sizeof (uint32_t); |
73 | if (rem > 0) |
74 | { |
75 | uint32_t x = arc4random (); |
76 | memcpy (&bytes[4 * i], &x, rem); |
77 | } |
78 | } |
79 | |
80 | static void |
81 | generate_arc4random_buf (unsigned char *bytes, size_t size) |
82 | { |
83 | arc4random_buf (buf: bytes, size: size); |
84 | } |
85 | |
86 | static void |
87 | generate_arc4random_uniform (unsigned char *bytes, size_t size) |
88 | { |
89 | for (int i = 0; i < size; i++) |
90 | bytes[i] = arc4random_uniform (upper_bound: 256); |
91 | } |
92 | |
93 | #define DYNARRAY_STRUCT dynarray_blob |
94 | #define DYNARRAY_ELEMENT struct blob |
95 | #define DYNARRAY_PREFIX dynarray_blob_ |
96 | #include <malloc/dynarray-skeleton.c> |
97 | |
98 | /* Sort blob elements by length first, then by comparing the data |
99 | member. */ |
100 | static int |
101 | compare_blob (const void *left1, const void *right1) |
102 | { |
103 | const struct blob *left = left1; |
104 | const struct blob *right = right1; |
105 | |
106 | if (left->size != right->size) |
107 | /* No overflow due to limited range. */ |
108 | return left->size - right->size; |
109 | return memcmp (left->bytes, right->bytes, left->size); |
110 | } |
111 | |
112 | /* Used to store the global result. */ |
113 | static pthread_mutex_t global_result_lock = PTHREAD_MUTEX_INITIALIZER; |
114 | static struct dynarray_blob global_result; |
115 | |
116 | /* Copy data to the global result, with locking. */ |
117 | static void |
118 | copy_result_to_global (struct dynarray_blob *result) |
119 | { |
120 | xpthread_mutex_lock (mutex: &global_result_lock); |
121 | size_t old_size = dynarray_blob_size (list: &global_result); |
122 | TEST_VERIFY_EXIT |
123 | (dynarray_blob_resize (&global_result, |
124 | old_size + dynarray_blob_size (result))); |
125 | memcpy (dynarray_blob_begin (list: &global_result) + old_size, |
126 | dynarray_blob_begin (list: result), |
127 | dynarray_blob_size (list: result) * sizeof (struct blob)); |
128 | xpthread_mutex_unlock (mutex: &global_result_lock); |
129 | } |
130 | |
131 | /* Used to assign unique thread IDs. Accessed atomically. */ |
132 | static int next_thread_id; |
133 | |
134 | static void * |
135 | inner_thread (void *closure) |
136 | { |
137 | void (*func) (unsigned char *, size_t) = closure; |
138 | |
139 | /* Use local result to avoid global lock contention while generating |
140 | randomness. */ |
141 | struct dynarray_blob result; |
142 | dynarray_blob_init (list: &result); |
143 | |
144 | int thread_id = __atomic_fetch_add (&next_thread_id, 1, __ATOMIC_RELAXED); |
145 | |
146 | /* Determine the sizes to be used by this thread. */ |
147 | int size_slot = thread_id % (array_length (sizes) + 1); |
148 | bool switch_sizes = size_slot == array_length (sizes); |
149 | if (switch_sizes) |
150 | size_slot = 0; |
151 | |
152 | /* Compute the random blobs. */ |
153 | for (int i = 0; i < count_per_thread; ++i) |
154 | { |
155 | struct blob *place = dynarray_blob_emplace (list: &result); |
156 | TEST_VERIFY_EXIT (place != NULL); |
157 | place->size = sizes[size_slot]; |
158 | place->thread_id = thread_id; |
159 | place->index = i; |
160 | func (place->bytes, place->size); |
161 | |
162 | if (switch_sizes) |
163 | size_slot = (size_slot + 1) % array_length (sizes); |
164 | } |
165 | |
166 | /* Store the blobs in the global result structure. */ |
167 | copy_result_to_global (result: &result); |
168 | |
169 | dynarray_blob_free (list: &result); |
170 | |
171 | return NULL; |
172 | } |
173 | |
174 | /* Launch the inner threads and wait for their termination. */ |
175 | static void * |
176 | outer_thread (void *closure) |
177 | { |
178 | void (*func) (unsigned char *, size_t) = closure; |
179 | |
180 | for (int round = 0; round < outer_rounds; ++round) |
181 | { |
182 | pthread_t threads[inner_threads]; |
183 | |
184 | for (int i = 0; i < inner_threads; ++i) |
185 | threads[i] = xpthread_create (NULL, thread_func: inner_thread, closure: func); |
186 | |
187 | for (int i = 0; i < inner_threads; ++i) |
188 | xpthread_join (thr: threads[i]); |
189 | } |
190 | |
191 | return NULL; |
192 | } |
193 | |
194 | static bool termination_requested; |
195 | |
196 | /* Call arc4random_buf to fill one blob with 16 bytes. */ |
197 | static void * |
198 | get_one_blob_thread (void *closure) |
199 | { |
200 | struct subprocess_args *arg = closure; |
201 | struct blob *result = arg->blob; |
202 | |
203 | result->size = 16; |
204 | arg->func (result->bytes, result->size); |
205 | return NULL; |
206 | } |
207 | |
208 | /* Invoked from fork_thread to actually obtain randomness data. */ |
209 | static void |
210 | fork_thread_subprocess (void *closure) |
211 | { |
212 | struct subprocess_args *arg = closure; |
213 | struct blob *shared_result = arg->blob; |
214 | |
215 | struct subprocess_args args[3] = |
216 | { |
217 | { shared_result + 0, arg->func }, |
218 | { shared_result + 1, arg->func }, |
219 | { shared_result + 2, arg->func } |
220 | }; |
221 | |
222 | pthread_t thr1 = xpthread_create (NULL, thread_func: get_one_blob_thread, closure: &args[1]); |
223 | pthread_t thr2 = xpthread_create (NULL, thread_func: get_one_blob_thread, closure: &args[2]); |
224 | get_one_blob_thread (closure: &args[0]); |
225 | xpthread_join (thr: thr1); |
226 | xpthread_join (thr: thr2); |
227 | } |
228 | |
229 | /* Continuously fork subprocesses to obtain a little bit of |
230 | randomness. */ |
231 | static void * |
232 | fork_thread (void *closure) |
233 | { |
234 | void (*func)(unsigned char *, size_t) = closure; |
235 | |
236 | struct dynarray_blob result; |
237 | dynarray_blob_init (list: &result); |
238 | |
239 | /* Three blobs from each subprocess. */ |
240 | struct blob *shared_result |
241 | = support_shared_allocate (size: 3 * sizeof (*shared_result)); |
242 | |
243 | while (!__atomic_load_n (&termination_requested, __ATOMIC_RELAXED)) |
244 | { |
245 | /* Obtain the results from a subprocess. */ |
246 | struct subprocess_args arg = { shared_result, func }; |
247 | support_isolate_in_subprocess (callback: fork_thread_subprocess, closure: &arg); |
248 | |
249 | for (int i = 0; i < 3; ++i) |
250 | { |
251 | struct blob *place = dynarray_blob_emplace (list: &result); |
252 | TEST_VERIFY_EXIT (place != NULL); |
253 | place->size = shared_result[i].size; |
254 | place->thread_id = -1; |
255 | place->index = i; |
256 | memcpy (place->bytes, shared_result[i].bytes, place->size); |
257 | } |
258 | } |
259 | |
260 | support_shared_free (shared_result); |
261 | |
262 | copy_result_to_global (result: &result); |
263 | dynarray_blob_free (list: &result); |
264 | |
265 | return NULL; |
266 | } |
267 | |
268 | /* Launch the outer threads and wait for their termination. */ |
269 | static void |
270 | run_outer_threads (void (*func)(unsigned char *, size_t)) |
271 | { |
272 | /* Special thread that continuously calls fork. */ |
273 | pthread_t fork_thread_id = xpthread_create (NULL, thread_func: fork_thread, closure: func); |
274 | |
275 | pthread_t threads[outer_threads]; |
276 | for (int i = 0; i < outer_threads; ++i) |
277 | threads[i] = xpthread_create (NULL, thread_func: outer_thread, closure: func); |
278 | |
279 | for (int i = 0; i < outer_threads; ++i) |
280 | xpthread_join (thr: threads[i]); |
281 | |
282 | __atomic_store_n (&termination_requested, true, __ATOMIC_RELAXED); |
283 | xpthread_join (thr: fork_thread_id); |
284 | } |
285 | |
286 | static int |
287 | do_test_func (const char *fname, void (*func)(unsigned char *, size_t)) |
288 | { |
289 | dynarray_blob_init (list: &global_result); |
290 | int expected_blobs |
291 | = count_per_thread * inner_threads * outer_threads * outer_rounds; |
292 | printf (format: "info: %s: minimum of %d blob results expected\n" , |
293 | fname, expected_blobs); |
294 | |
295 | run_outer_threads (func); |
296 | |
297 | /* The forking thread delivers a non-deterministic number of |
298 | results, which is why expected_blobs is only a minimum number of |
299 | results. */ |
300 | printf (format: "info: %s: %zu blob results observed\n" , fname, |
301 | dynarray_blob_size (list: &global_result)); |
302 | TEST_VERIFY (dynarray_blob_size (&global_result) >= expected_blobs); |
303 | |
304 | /* Verify that there are no duplicates. */ |
305 | qsort (dynarray_blob_begin (list: &global_result), |
306 | dynarray_blob_size (list: &global_result), |
307 | sizeof (struct blob), compare_blob); |
308 | struct blob *end = dynarray_blob_end (list: &global_result); |
309 | for (struct blob *p = dynarray_blob_begin (list: &global_result) + 1; |
310 | p < end; ++p) |
311 | { |
312 | if (compare_blob (left1: p - 1, right1: p) == 0) |
313 | { |
314 | support_record_failure (); |
315 | char *quoted = support_quote_blob (blob: p->bytes, length: p->size); |
316 | printf (format: "error: %s: duplicate blob: \"%s\" (%d bytes)\n" , |
317 | fname, quoted, (int) p->size); |
318 | printf (format: " first source: thread %d, index %u\n" , |
319 | p[-1].thread_id, p[-1].index); |
320 | printf (format: " second source: thread %d, index %u\n" , |
321 | p[0].thread_id, p[0].index); |
322 | free (ptr: quoted); |
323 | } |
324 | } |
325 | |
326 | dynarray_blob_free (list: &global_result); |
327 | |
328 | return 0; |
329 | } |
330 | |
331 | static int |
332 | do_test (void) |
333 | { |
334 | /* Do not run more threads than the maximum of schedulable CPUs. */ |
335 | cpu_set_t cpuset; |
336 | if (sched_getaffinity (pid: 0, cpusetsize: sizeof cpuset, cpuset: &cpuset) == 0) |
337 | { |
338 | unsigned int ncpus = CPU_COUNT (&cpuset); |
339 | /* Limit the number to not overload the system. */ |
340 | outer_threads = (ncpus / 2) / inner_threads ?: 1; |
341 | } |
342 | |
343 | printf (format: "info: outer_threads=%d inner_threads=%d\n" , outer_threads, |
344 | inner_threads); |
345 | |
346 | do_test_func (fname: "arc4random" , func: generate_arc4random); |
347 | do_test_func (fname: "arc4random_buf" , func: generate_arc4random_buf); |
348 | do_test_func (fname: "arc4random_uniform" , func: generate_arc4random_uniform); |
349 | |
350 | return 0; |
351 | } |
352 | |
353 | #include <support/test-driver.c> |
354 | |