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

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds710_hash_a_element
   8     hae;
   9
  10   lfds710_pal_uint_t
  11     key;
  12 };
  13
  14 struct test_per_thread_state
  15 {
  16   lfds710_pal_uint_t
  17     number_elements_per_thread,
  18     overwrite_count;
  19
  20   struct lfds710_hash_a_state
  21     *has;
  22
  23   struct test_element
  24     *element_array;
  25 };
  26
  27 /***** private prototypes *****/
  28 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state );
  29 static int key_compare_function( void const *new_key, void const *existing_key );
  30 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash );
  31 static int LIBTEST_PAL_STDLIB_CALLBACK_CALLING_CONVENTION qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 );
  32
  33
  34
  35
  36
  37 /****************************************************************************/
  38 void libtest_tests_hash_a_random_adds_overwrite_on_existing( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  39 {
  40   int
  41     rv;
  42
  43   lfds710_pal_uint_t
  44     actual_sum_overwrite_existing_count,
  45     expected_sum_overwrite_existing_count,
  46     *key_count_array,
  47     loop,
  48     number_elements_per_thread,
  49     number_elements_total,
  50     number_logical_processors,
  51     random_value;
  52
  53   struct lfds710_hash_a_iterate
  54     hai;
  55
  56   struct lfds710_hash_a_element
  57     *hae;
  58
  59   struct lfds710_hash_a_state
  60     has;
  61
  62   struct lfds710_list_asu_element
  63     *lasue = NULL;
  64
  65   struct lfds710_btree_au_state
  66     *baus;
  67
  68   struct lfds710_prng_state
  69     ps;
  70
  71   struct lfds710_misc_validation_info
  72     vi;
  73
  74   struct libtest_logical_processor
  75     *lp;
  76
  77   struct libtest_threadset_per_thread_state
  78     *pts;
  79
  80   struct libtest_threadset_state
  81     ts;
  82
  83   struct test_element
  84     *element_array;
  85
  86   struct test_per_thread_state
  87     *tpts;
  88
  89   void
  90     *key_pointer,
  91     *key;
  92
  93   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  94   LFDS710_PAL_ASSERT( ms != NULL );
  95   LFDS710_PAL_ASSERT( dvs != NULL );
  96
  97   /* TRD : we create a single hash_a
  98            we generate n elements per thread
  99            each element contains a key value, which is set to a random value
 100            (we don't use value, so it's just set to 0)
 101            the threads then run, putting
 102            the threads count their number of overwrite hits
 103            once the threads are done, then we
 104            count the number of each key
 105            from this we figure out the min/max element for hash_a validation, so we call validation
 106            we check the sum of overwrites for each thread is what it should be
 107            then using the hash_a get() we check all the elements we expect are present
 108            and then we iterate over the hash_a
 109            checking we see each key once
 110   */
 111
 112   *dvs = LFDS710_MISC_VALIDITY_VALID;
 113
 114   // TRD : allocate
 115   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 116   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 117   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 118   baus = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct lfds710_btree_au_state) * 1000, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 119   element_array = libshared_memory_alloc_largest_possible_array_from_unknown_node( ms, sizeof(struct test_element) + sizeof(lfds710_pal_uint_t), LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES, &number_elements_total );
 120   key_count_array = (lfds710_pal_uint_t *) ( element_array + number_elements_total );
 121
 122   // TRD : per thread first, for correct rounding, for later code
 123   number_elements_per_thread = number_elements_total / number_logical_processors;
 124   number_elements_total = number_elements_per_thread * number_logical_processors;
 125
 126   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 127
 128   lfds710_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS710_HASH_A_EXISTING_KEY_OVERWRITE, NULL );
 129
 130   // TRD : created an ordered list of unique numbers
 131
 132   for( loop = 0 ; loop < number_elements_total ; loop++ )
 133   {
 134     LFDS710_PRNG_GENERATE( ps, random_value );
 135     (element_array+loop)->key = (lfds710_pal_uint_t) ( (number_elements_total/2) * ((double) random_value / (double) LFDS710_PRNG_MAX) );
 136   }
 137
 138   // TRD : get the threads ready
 139   libtest_threadset_init( &ts, NULL );
 140
 141   loop = 0;
 142
 143   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 144   {
 145     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 146     (tpts+loop)->has = &has;
 147     (tpts+loop)->element_array = element_array + number_elements_per_thread*loop;
 148     (tpts+loop)->overwrite_count = 0;
 149     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 150     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_adding, &tpts[loop] );
 151     loop++;
 152   }
 153
 154   // TRD : run the test
 155   libtest_threadset_run( &ts );
 156
 157   libtest_threadset_cleanup( &ts );
 158
 159   // TRD : validate
 160   LFDS710_MISC_BARRIER_LOAD;
 161
 162   // TRD : now for validation
 163   for( loop = 0 ; loop < number_elements_total ; loop++ )
 164     *(key_count_array+loop) = 0;
 165
 166   for( loop = 0 ; loop < number_elements_total ; loop++ )
 167     ( *(key_count_array + (element_array+loop)->key) )++;
 168
 169   vi.min_elements = number_elements_total;
 170
 171   for( loop = 0 ; loop < number_elements_total ; loop++ )
 172     if( *(key_count_array+loop) == 0 )
 173       vi.min_elements--;
 174
 175   vi.max_elements = vi.min_elements;
 176
 177   lfds710_hash_a_query( &has, LFDS710_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
 178
 179   expected_sum_overwrite_existing_count = 0;
 180
 181   for( loop = 0 ; loop < number_elements_total ; loop++ )
 182     if( *(key_count_array+loop) != 0 )
 183       expected_sum_overwrite_existing_count += *(key_count_array+loop) - 1;
 184
 185   actual_sum_overwrite_existing_count = 0;
 186
 187   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 188     actual_sum_overwrite_existing_count += (tpts+loop)->overwrite_count;
 189
 190   if( expected_sum_overwrite_existing_count != actual_sum_overwrite_existing_count )
 191     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 192
 193   // TRD : now loop over the expected array and check we can get() every element
 194   for( loop = 0 ; loop < number_elements_total ; loop++ )
 195     if( *(key_count_array+loop) > 0 )
 196     {
 197       rv = lfds710_hash_a_get_by_key( &has, NULL, NULL, (void *) loop, &hae );
 198
 199       if( rv != 1 )
 200         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 201     }
 202
 203   /* TRD : now iterate, checking we find every element and no others
 204            to do this in a timely manner, we need to qsort() the key values
 205            and use bsearch() to check for items in the array
 206   */
 207
 208   for( loop = 0 ; loop < number_elements_total ; loop++ )
 209     if( *(key_count_array+loop) != 0 )
 210       *(key_count_array+loop) = loop;
 211     else
 212       *(key_count_array+loop) = 0;
 213
 214   qsort( key_count_array, number_elements_total, sizeof(lfds710_pal_uint_t), qsort_and_bsearch_key_compare_function );
 215
 216   lfds710_hash_a_iterate_init( &has, &hai );
 217
 218   while( *dvs == LFDS710_MISC_VALIDITY_VALID and lfds710_hash_a_iterate(&hai, &hae) )
 219   {
 220     key = LFDS710_HASH_A_GET_KEY_FROM_ELEMENT( *hae );
 221
 222     key_pointer = bsearch( &key, key_count_array, number_elements_total, sizeof(lfds710_pal_uint_t), qsort_and_bsearch_key_compare_function );
 223
 224     if( key_pointer == NULL )
 225       *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 226   }
 227
 228   // TRD : cleanup
 229   lfds710_hash_a_cleanup( &has, NULL );
 230
 231   return;
 232 }
 233
 234
 235
 236
 237
 238 /****************************************************************************/
 239 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
 240 {
 241   enum lfds710_hash_a_insert_result
 242     apr;
 243
 244   lfds710_pal_uint_t
 245     index = 0;
 246
 247   struct test_per_thread_state
 248     *tpts;
 249
 250   struct libtest_threadset_per_thread_state
 251     *pts;
 252
 253   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 254
 255   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 256
 257   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 258
 259   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 260
 261   libtest_threadset_thread_ready_and_wait( pts );
 262
 263   while( index < tpts->number_elements_per_thread )
 264   {
 265     LFDS710_HASH_A_SET_KEY_IN_ELEMENT( (tpts->element_array+index)->hae, (tpts->element_array+index)->key );
 266     LFDS710_HASH_A_SET_VALUE_IN_ELEMENT( (tpts->element_array+index)->hae, 0 );
 267     apr = lfds710_hash_a_insert( tpts->has, &(tpts->element_array+index)->hae, NULL );
 268
 269     if( apr == LFDS710_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE )
 270       tpts->overwrite_count++;
 271
 272     index++;
 273   }
 274
 275   LFDS710_MISC_BARRIER_STORE;
 276
 277   lfds710_misc_force_store();
 278
 279   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 280 }
 281
 282
 283
 284
 285
 286 /****************************************************************************/
 287 #pragma warning( disable : 4100 )
 288
 289 static int key_compare_function( void const *new_key, void const *existing_key )
 290 {
 291   int
 292     cr = 0;
 293
 294   // TRD : new_key can be NULL (i.e. 0)
 295   // TRD : existing_key can be NULL (i.e. 0)
 296
 297   if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) existing_key )
 298     cr = -1;
 299
 300   if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) existing_key )
 301     cr = 1;
 302
 303   return cr;
 304 }
 305
 306 #pragma warning( default : 4100 )
 307
 308
 309
 310
 311
 312 /****************************************************************************/
 313 #pragma warning( disable : 4100 )
 314
 315 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash )
 316 {
 317   // TRD : key can be NULL
 318   LFDS710_PAL_ASSERT( hash != NULL );
 319
 320   *hash = 0;
 321
 322   /* TRD : this function iterates over the user data
 323            and we are using the void pointer *as* key data
 324            so here we need to pass in the addy of key
 325   */
 326
 327   LFDS710_HASH_A_HASH_FUNCTION( (void *) &key, sizeof(lfds710_pal_uint_t), *hash );
 328
 329   return;
 330 }
 331
 332 #pragma warning( default : 4100 )
 333
 334
 335
 336
 337
 338 /****************************************************************************/
 339 static int LIBTEST_PAL_STDLIB_CALLBACK_CALLING_CONVENTION qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 )
 340 {
 341   int
 342     cr = 0;
 343
 344   lfds710_pal_uint_t
 345     s1,
 346     s2;
 347
 348   s1 = *(lfds710_pal_uint_t *) e1;
 349   s2 = *(lfds710_pal_uint_t *) e2;
 350
 351   if( s1 > s2 )
 352     cr = 1;
 353
 354   if( s1 < s2 )
 355     cr = -1;
 356
 357   return cr;
 358 }
 359