]>
Commit | Line | Data |
---|---|---|
8dd890d9 AZN |
1 | /* Test that threads generate distinct streams of randomness. |
2 | Copyright (C) 2022 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> | |
35363b53 | 20 | #include <sched.h> |
8dd890d9 | 21 | #include <stdio.h> |
8dd890d9 | 22 | #include <stdlib.h> |
35363b53 | 23 | #include <string.h> |
8dd890d9 AZN |
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. */ | |
35363b53 | 30 | enum { count_per_thread = 2048 }; |
8dd890d9 AZN |
31 | |
32 | /* Number of threads computing randomness. */ | |
35363b53 | 33 | enum { inner_threads = 4 }; |
8dd890d9 | 34 | |
35363b53 AZ |
35 | /* Number of threads launching other threads. */ |
36 | static int outer_threads = 1; | |
8dd890d9 AZN |
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 (bytes, 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 (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 (&global_result_lock); | |
121 | size_t old_size = dynarray_blob_size (&global_result); | |
122 | TEST_VERIFY_EXIT | |
123 | (dynarray_blob_resize (&global_result, | |
124 | old_size + dynarray_blob_size (result))); | |
125 | memcpy (dynarray_blob_begin (&global_result) + old_size, | |
126 | dynarray_blob_begin (result), | |
127 | dynarray_blob_size (result) * sizeof (struct blob)); | |
128 | xpthread_mutex_unlock (&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 (&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 (&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); | |
168 | ||
169 | dynarray_blob_free (&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, inner_thread, func); | |
186 | ||
187 | for (int i = 0; i < inner_threads; ++i) | |
188 | xpthread_join (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, get_one_blob_thread, &args[1]); | |
223 | pthread_t thr2 = xpthread_create (NULL, get_one_blob_thread, &args[2]); | |
224 | get_one_blob_thread (&args[0]); | |
225 | xpthread_join (thr1); | |
226 | xpthread_join (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 (&result); | |
238 | ||
239 | /* Three blobs from each subprocess. */ | |
240 | struct blob *shared_result | |
241 | = support_shared_allocate (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 (fork_thread_subprocess, &arg); | |
248 | ||
249 | for (int i = 0; i < 3; ++i) | |
250 | { | |
251 | struct blob *place = dynarray_blob_emplace (&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); | |
263 | dynarray_blob_free (&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, fork_thread, func); | |
274 | ||
275 | pthread_t threads[outer_threads]; | |
276 | for (int i = 0; i < outer_threads; ++i) | |
277 | threads[i] = xpthread_create (NULL, outer_thread, func); | |
278 | ||
279 | for (int i = 0; i < outer_threads; ++i) | |
280 | xpthread_join (threads[i]); | |
281 | ||
282 | __atomic_store_n (&termination_requested, true, __ATOMIC_RELAXED); | |
283 | xpthread_join (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 (&global_result); | |
290 | int expected_blobs | |
291 | = count_per_thread * inner_threads * outer_threads * outer_rounds; | |
292 | printf ("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 minimun number of | |
299 | results. */ | |
300 | printf ("info: %s: %zu blob results observed\n", fname, | |
301 | dynarray_blob_size (&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 (&global_result), | |
306 | dynarray_blob_size (&global_result), | |
307 | sizeof (struct blob), compare_blob); | |
308 | struct blob *end = dynarray_blob_end (&global_result); | |
309 | for (struct blob *p = dynarray_blob_begin (&global_result) + 1; | |
310 | p < end; ++p) | |
311 | { | |
312 | if (compare_blob (p - 1, p) == 0) | |
313 | { | |
314 | support_record_failure (); | |
315 | char *quoted = support_quote_blob (p->bytes, p->size); | |
316 | printf ("error: %s: duplicate blob: \"%s\" (%d bytes)\n", | |
317 | fname, quoted, (int) p->size); | |
318 | printf (" first source: thread %d, index %u\n", | |
319 | p[-1].thread_id, p[-1].index); | |
320 | printf (" second source: thread %d, index %u\n", | |
321 | p[0].thread_id, p[0].index); | |
322 | free (quoted); | |
323 | } | |
324 | } | |
325 | ||
326 | dynarray_blob_free (&global_result); | |
327 | ||
328 | return 0; | |
329 | } | |
330 | ||
331 | static int | |
332 | do_test (void) | |
333 | { | |
35363b53 AZ |
334 | /* Do not run more threads than the maximum of schedulable CPUs. */ |
335 | cpu_set_t cpuset; | |
336 | if (sched_getaffinity (0, sizeof 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 ("info: outer_threads=%d inner_threads=%d\n", outer_threads, | |
344 | inner_threads); | |
345 | ||
8dd890d9 AZN |
346 | do_test_func ("arc4random", generate_arc4random); |
347 | do_test_func ("arc4random_buf", generate_arc4random_buf); | |
348 | do_test_func ("arc4random_uniform", generate_arc4random_uniform); | |
349 | ||
350 | return 0; | |
351 | } | |
352 | ||
353 | #include <support/test-driver.c> |