pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/test/src/test_lfds700_hash_addonly_random_adds_overwrite.c

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds700_hash_a_element
   8     hae;
   9
  10   lfds700_pal_uint_t
  11     key;
  12 };
  13
  14 struct test_state
  15 {
  16   lfds700_pal_uint_t
  17     number_elements_per_thread,
  18     overwrite_count;
  19
  20   struct lfds700_hash_a_state
  21     *has;
  22
  23   struct test_element
  24     *element_array;
  25 };
  26
  27 /***** private prototypes *****/
  28 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_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, lfds700_pal_uint_t *hash );
  31 static int qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 );
  32
  33
  34
  35
  36
  37 /****************************************************************************/
  38 void test_lfds700_hash_a_random_adds_overwrite_on_existing( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
  39 {
  40   enum lfds700_misc_validity
  41     dvs = LFDS700_MISC_VALIDITY_VALID;
  42
  43   int
  44     rv;
  45
  46   lfds700_pal_uint_t
  47     actual_sum_overwrite_existing_count,
  48     expected_sum_overwrite_existing_count,
  49     *key_count_array,
  50     loop,
  51     number_elements_per_thread,
  52     number_elements_total,
  53     number_logical_processors,
  54     random_value;
  55
  56   struct lfds700_hash_a_iterate
  57     hai;
  58
  59   struct lfds700_hash_a_element
  60     *hae;
  61
  62   struct lfds700_hash_a_state
  63     has;
  64
  65   struct lfds700_list_asu_element
  66     *lasue = NULL;
  67
  68   struct lfds700_btree_au_state
  69     *baus;
  70
  71   struct lfds700_misc_prng_state
  72     ps;
  73
  74   struct lfds700_misc_validation_info
  75     vi;
  76
  77   struct test_pal_logical_processor
  78     *lp;
  79
  80   struct util_thread_starter_state
  81     *tts;
  82
  83   struct test_element
  84     *element_array;
  85
  86   struct test_state
  87     *ts;
  88
  89   test_pal_thread_state_t
  90     *thread_handles;
  91
  92   void
  93     *key_pointer,
  94     *key;
  95
  96   assert( list_of_logical_processors != NULL );
  97   // TRD : memory_in_megabytes can be any value in its range
  98
  99   /* TRD : we create a single hash_a
 100            we generate n elements per thread
 101            each element contains a key value, which is set to a random value
 102            (we don't use value, so it's just set to 0)
 103            the threads then run, putting
 104            the threads count their number of overwrite hits
 105            once the threads are done, then we
 106            count the number of each key
 107            from this we figure out the min/max element for hash_a validation, so we call validation
 108            we check the sum of overwrites for each thread is what it should be
 109            then using the hash_a get() we check all the elements we expect are present
 110            and then we iterate over the hash_a
 111            checking we see each key once
 112   */
 113
 114   internal_display_test_name( "Random adds, get and iterate (overwrite on existing key)" );
 115
 116   lfds700_misc_prng_init( &ps );
 117
 118   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 119
 120   baus = util_aligned_malloc( sizeof(struct lfds700_btree_au_state) * 1000, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 121
 122   lfds700_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS700_HASH_A_EXISTING_KEY_OVERWRITE, NULL );
 123
 124   // TRD : we divide by 2 beccause we have to allocate a second array of this size later
 125   number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors ) / 2;
 126   number_elements_total = number_elements_per_thread * number_logical_processors;
 127
 128   // TRD : created an ordered list of unique numbers
 129   element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements_total, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 130
 131   for( loop = 0 ; loop < number_elements_total ; loop++ )
 132   {
 133     random_value = LFDS700_MISC_PRNG_GENERATE( &ps );
 134     (element_array+loop)->key = (lfds700_pal_uint_t) floor( (number_elements_total/2) * ((double) random_value / (double) LFDS700_MISC_PRNG_MAX) );
 135   }
 136
 137   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 138
 139   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 140   {
 141     (ts+loop)->has = &has;
 142     (ts+loop)->element_array = element_array + number_elements_per_thread*loop;
 143     (ts+loop)->overwrite_count = 0;
 144     (ts+loop)->number_elements_per_thread = number_elements_per_thread;
 145   }
 146
 147   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 148
 149   util_thread_starter_new( &tts, number_logical_processors );
 150
 151   LFDS700_MISC_BARRIER_STORE;
 152
 153   lfds700_misc_force_store();
 154
 155   loop = 0;
 156
 157   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 158   {
 159     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 160     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_adding, ts+loop );
 161     loop++;
 162   }
 163
 164   util_thread_starter_run( tts );
 165
 166   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 167     test_pal_thread_wait( thread_handles[loop] );
 168
 169   util_thread_starter_delete( tts );
 170
 171   free( thread_handles );
 172
 173   LFDS700_MISC_BARRIER_LOAD;
 174
 175   // TRD : now for validation
 176   key_count_array = util_malloc_wrapper( sizeof(lfds700_pal_uint_t) * number_elements_total );
 177   for( loop = 0 ; loop < number_elements_total ; loop++ )
 178     *(key_count_array+loop) = 0;
 179
 180   for( loop = 0 ; loop < number_elements_total ; loop++ )
 181     ( *(key_count_array + (element_array+loop)->key) )++;
 182
 183   vi.min_elements = number_elements_total;
 184
 185   for( loop = 0 ; loop < number_elements_total ; loop++ )
 186     if( *(key_count_array+loop) == 0 )
 187       vi.min_elements--;
 188
 189   vi.max_elements = vi.min_elements;
 190
 191   lfds700_hash_a_query( &has, LFDS700_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) &dvs );
 192
 193   expected_sum_overwrite_existing_count = 0;
 194
 195   for( loop = 0 ; loop < number_elements_total ; loop++ )
 196     if( *(key_count_array+loop) != 0 )
 197       expected_sum_overwrite_existing_count += *(key_count_array+loop) - 1;
 198
 199   actual_sum_overwrite_existing_count = 0;
 200
 201   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 202     actual_sum_overwrite_existing_count += (ts+loop)->overwrite_count;
 203
 204   if( expected_sum_overwrite_existing_count != actual_sum_overwrite_existing_count )
 205     dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 206
 207   // TRD : now loop over the expected array and check we can get() every element
 208   for( loop = 0 ; loop < number_elements_total ; loop++ )
 209     if( *(key_count_array+loop) > 0 )
 210     {
 211       rv = lfds700_hash_a_get_by_key( &has, (void *) loop, &hae );
 212
 213       if( rv != 1 )
 214         dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 215     }
 216
 217   /* TRD : now iterate, checking we find every element and no others
 218            to do this in a timely manner, we need to qsort() the key values
 219            and use bsearch() to check for items in the array
 220   */
 221
 222   for( loop = 0 ; loop < number_elements_total ; loop++ )
 223     if( *(key_count_array+loop) != 0 )
 224       *(key_count_array+loop) = loop;
 225     else
 226       *(key_count_array+loop) = 0;
 227
 228   qsort( key_count_array, number_elements_total, sizeof(lfds700_pal_uint_t), qsort_and_bsearch_key_compare_function );
 229
 230   lfds700_hash_a_iterate_init( &has, &hai );
 231
 232   while( dvs == LFDS700_MISC_VALIDITY_VALID and lfds700_hash_a_iterate(&hai, &hae) )
 233   {
 234     key = LFDS700_HASH_A_GET_KEY_FROM_ELEMENT( *hae );
 235
 236     key_pointer = bsearch( &key, key_count_array, number_elements_total, sizeof(lfds700_pal_uint_t), qsort_and_bsearch_key_compare_function );
 237
 238     if( key_pointer == NULL )
 239       dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 240   }
 241
 242   // TRD : cleanup
 243   lfds700_hash_a_cleanup( &has, NULL );
 244
 245   util_aligned_free( baus );
 246
 247   free( ts );
 248
 249   util_aligned_free( element_array );
 250
 251   free( key_count_array );
 252
 253   // TRD : print the test result
 254   internal_display_test_result( 1, "hash_a", dvs );
 255
 256   return;
 257 }
 258
 259
 260
 261
 262
 263 /****************************************************************************/
 264 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state )
 265 {
 266   enum lfds700_hash_a_insert_result
 267     apr;
 268
 269   lfds700_pal_uint_t
 270     index = 0;
 271
 272   struct test_state
 273     *ts;
 274
 275   struct lfds700_misc_prng_state
 276     ps;
 277
 278   struct util_thread_starter_thread_state
 279     *tsts;
 280
 281   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 282
 283   assert( util_thread_starter_thread_state != NULL );
 284
 285   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 286   ts = (struct test_state *) tsts->thread_user_state;
 287
 288   lfds700_misc_prng_init( &ps );
 289
 290   util_thread_starter_ready_and_wait( tsts );
 291
 292   while( index < ts->number_elements_per_thread )
 293   {
 294     LFDS700_HASH_A_SET_KEY_IN_ELEMENT( (ts->element_array+index)->hae, (ts->element_array+index)->key );
 295     LFDS700_HASH_A_SET_VALUE_IN_ELEMENT( (ts->element_array+index)->hae, 0 );
 296     apr = lfds700_hash_a_insert( ts->has, &(ts->element_array+index)->hae, NULL, &ps );
 297
 298     if( apr == LFDS700_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE )
 299       ts->overwrite_count++;
 300
 301     index++;
 302   }
 303
 304   LFDS700_MISC_BARRIER_STORE;
 305
 306   lfds700_misc_force_store();
 307
 308   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 309 }
 310
 311
 312
 313
 314
 315 /****************************************************************************/
 316 #pragma warning( disable : 4100 )
 317
 318 static int key_compare_function( void const *new_key, void const *existing_key )
 319 {
 320   int
 321     cr = 0;
 322
 323   // TRD : new_key can be NULL (i.e. 0)
 324   // TRD : existing_key can be NULL (i.e. 0)
 325
 326   if( (lfds700_pal_uint_t) new_key < (lfds700_pal_uint_t) existing_key )
 327     cr = -1;
 328
 329   if( (lfds700_pal_uint_t) new_key > (lfds700_pal_uint_t) existing_key )
 330     cr = 1;
 331
 332   return( cr );
 333 }
 334
 335 #pragma warning( default : 4100 )
 336
 337
 338
 339
 340
 341 /****************************************************************************/
 342 #pragma warning( disable : 4100 )
 343
 344 static void key_hash_function( void const *key, lfds700_pal_uint_t *hash )
 345 {
 346   // TRD : key can be NULL
 347   assert( hash != NULL );
 348
 349   *hash = 0;
 350
 351   /* TRD : this function iterates over the user data
 352            and we are using the void pointer *as* key data
 353            so here we need to pass in the addy of key
 354   */
 355
 356   LFDS700_HASH_A_32BIT_HASH_FUNCTION( (void *) &key, sizeof(lfds700_pal_uint_t), *hash );
 357
 358   return;
 359 }
 360
 361 #pragma warning( default : 4100 )
 362
 363
 364
 365
 366
 367 /****************************************************************************/
 368 static int qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 )
 369 {
 370   int
 371     cr = 0;
 372
 373   lfds700_pal_uint_t
 374     s1,
 375     s2;
 376
 377   s1 = *(lfds700_pal_uint_t *) e1;
 378   s2 = *(lfds700_pal_uint_t *) e2;
 379
 380   if( s1 > s2 )
 381     cr = 1;
 382
 383   if( s1 < s2 )
 384     cr = -1;
 385
 386   return( cr );
 387 }
 388