pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libtest/src/libtest_tests/libtest_tests_prng_generate.c

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_per_thread_state
   6 {
   7   struct lfds710_prng_state
   8     *ps;
   9
  10   lfds710_pal_uint_t
  11     read_index,
  12     *output_array;
  13 };
  14
  15 /***** private prototyps *****/
  16 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_generate( void *libtest_threadset_per_thread_state );
  17
  18
  19
  20
  21
  22 /****************************************************************************/
  23 void libtest_tests_prng_generate( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  24 {
  25   enum flag
  26     duplicate_flag = LOWERED,
  27     finished_flag = LOWERED;
  28
  29   lfds710_pal_uint_t
  30     *output_arrays,
  31     index = 0,
  32     loop = 0,
  33     mean = 0,
  34     *merged_output_arrays,
  35     merged_write_index = 0,
  36     number_logical_processors,
  37     smallest_prng_value,
  38     ten_percent,
  39     thread_to_bump = 0;
  40
  41   struct lfds710_list_asu_element
  42     *lasue = NULL;
  43
  44   struct libtest_logical_processor
  45     *lp;
  46
  47   struct lfds710_prng_state
  48     ps;
  49
  50   struct libtest_threadset_per_thread_state
  51     *pts;
  52
  53   struct libtest_threadset_state
  54     ts;
  55
  56   struct test_per_thread_state
  57     *tpts;
  58
  59   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  60   LFDS710_PAL_ASSERT( ms != NULL );
  61   LFDS710_PAL_ASSERT( dvs != NULL );
  62
  63   /* TRD : here we test the atomic PRNG
  64            we create an array, an output buffer, of 128 elements per thread
  65            we have a single, global PRNG
  66            we start all the threads and let them run for test duration seconds
  67            (to ensure they are all running together)
  68            each thread loops, writing new numbers to its output array
  69            obviously in test duration seconds it will write many more than 128 elements -
  70            it just loops over the output array
  71
  72            then when we're done we merge sort the output arrays (no qsort, not using standard library)
  73            the number of duplicates should be 0
  74            and the standard deviation should be 25% of LFDS710_PRNG_MAX
  75   */
  76
  77   *dvs = LFDS710_MISC_VALIDITY_VALID;
  78
  79   // TRD : allocate
  80   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
  81   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  82   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  83   output_arrays = libshared_memory_alloc_from_unknown_node( ms, sizeof(lfds710_pal_uint_t) * 128 * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  84   merged_output_arrays = libshared_memory_alloc_from_unknown_node( ms, sizeof(lfds710_pal_uint_t) * 128 * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
  85
  86   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
  87
  88   libtest_threadset_init( &ts, NULL );
  89
  90   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
  91   {
  92     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
  93
  94     (tpts+loop)->ps = &ps;
  95     (tpts+loop)->output_array = output_arrays + (loop * 128);
  96     (tpts+loop)->read_index = 0; // TRD : convenient to alloc here, as we need one per thread, used in validation
  97
  98     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_generate, &tpts[loop] );
  99
 100     loop++;
 101   }
 102
 103   LFDS710_MISC_BARRIER_STORE;
 104
 105   lfds710_misc_force_store();
 106
 107   // TRD : run the test
 108   libtest_threadset_run( &ts );
 109   libtest_threadset_cleanup( &ts );
 110
 111   // TRD : validate
 112   LFDS710_MISC_BARRIER_LOAD;
 113
 114   // TRD : merge sort the counter arrays into merged_output_array
 115   while( finished_flag == LOWERED )
 116   {
 117     smallest_prng_value = LFDS710_PRNG_MAX;
 118     finished_flag = RAISED;
 119
 120     for( loop = 0 ; loop < number_logical_processors ; loop++ )
 121       if( tpts[loop].read_index < 128 and tpts[loop].output_array[ tpts[loop].read_index ] < smallest_prng_value )
 122       {
 123         smallest_prng_value = tpts[loop].output_array[ tpts[loop].read_index ];
 124         thread_to_bump = loop;
 125         finished_flag = LOWERED;
 126       }
 127
 128     tpts[thread_to_bump].read_index++;
 129     merged_output_arrays[ merged_write_index++ ] = smallest_prng_value;
 130   }
 131
 132   // TRD : now check for duplicates
 133   while( duplicate_flag == LOWERED and index < (128 * number_logical_processors) - 2 )
 134   {
 135     if( merged_output_arrays[index] == merged_output_arrays[index+1] )
 136       duplicate_flag = RAISED;
 137     index++;
 138   }
 139
 140   if( duplicate_flag == RAISED )
 141     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 142
 143   // TRD : now for standard deviation (integer math only is allowed, and we can't sum the outputs because we'll overflow)
 144   for( loop = 0 ; loop < 128 * number_logical_processors ; loop++ )
 145     mean += merged_output_arrays[loop] / (128*number_logical_processors);
 146
 147   /* TRD : the mean of an unsigned 64 bit is 9223372036854775808
 148            the mean of an unsigned 32 bit is 2147483648
 149            there are 128 random numbers per thread
 150            the more numbers there are, the more closely we should approach the expected mean
 151            it'd take me a while - if I could - to work out the expected deviation for a given number of numbers
 152            empirically, a single logical core (128 numbers) shouldn't be more than 10% off
 153   */
 154
 155   ten_percent = LFDS710_PRNG_MAX / 10;
 156
 157   if( mean < (LFDS710_PRNG_MAX / 2) - ten_percent or mean > (LFDS710_PRNG_MAX / 2) + ten_percent )
 158     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 159
 160   // TRD : should add a standard deviation check here
 161
 162   return;
 163 }
 164
 165
 166
 167
 168
 169 /****************************************************************************/
 170 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_generate( void *libtest_threadset_per_thread_state )
 171 {
 172   lfds710_pal_uint_t
 173     index = 0,
 174     time_loop = 0;
 175
 176   struct test_per_thread_state
 177     *tpts;
 178
 179   struct libtest_threadset_per_thread_state
 180     *pts;
 181
 182   time_t
 183     current_time,
 184     start_time;
 185
 186   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 187
 188   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 189
 190   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 191   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 192
 193   libtest_threadset_thread_ready_and_wait( pts );
 194
 195   current_time = start_time = time( NULL );
 196
 197   while( current_time < start_time + TEST_DURATION_IN_SECONDS )
 198   {
 199     LFDS710_PRNG_GENERATE( *tpts->ps, tpts->output_array[index] );
 200
 201     // TRD : 128 element array, so masking on 128-1 makes us loop, much faster than modulus
 202     index = ( (index+1) & 0x7F );
 203
 204     if( time_loop++ == TIME_LOOP_COUNT )
 205     {
 206       time_loop = 0;
 207       time( &current_time );
 208     }
 209   }
 210
 211   LFDS710_MISC_BARRIER_STORE;
 212
 213   lfds710_misc_force_store();
 214
 215   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 216 }
 217