stdlib/tst-arc4random-thread.c

   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>
  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 (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 {
 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
 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>