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

   1 /***** includes *****/
   2 #include "internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds700_btree_au_element
   8     baue;
   9
  10   lfds700_pal_uint_t
  11     key;
  12 };
  13
  14 struct test_state
  15 {
  16   lfds700_pal_uint_t
  17     insert_existing_count,
  18     number_elements;
  19
  20   struct lfds700_btree_au_state
  21     *baus;
  22
  23   struct test_element
  24     *element_array;
  25 };
  26
  27 /***** private prototypes *****/
  28 static int key_compare_function( void const *new_value, void const *value_in_tree );
  29 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state );
  30
  31
  32
  33
  34
  35 /****************************************************************************/
  36 void test_lfds700_btree_au_random_adds_overwrite_on_existing( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
  37 {
  38   enum lfds700_misc_validity
  39     dvs = LFDS700_MISC_VALIDITY_VALID;
  40
  41   lfds700_pal_uint_t
  42     actual_sum_insert_existing_count,
  43     expected_sum_insert_existing_count,
  44     index = 0,
  45     *key_count_array,
  46     loop,
  47     number_elements,
  48     number_logical_processors,
  49     random_value,
  50     subloop;
  51
  52   struct lfds700_list_asu_element
  53     *lasue;
  54
  55   struct lfds700_btree_au_element
  56     *baue = NULL;
  57
  58   struct lfds700_btree_au_state
  59     baus;
  60
  61   struct lfds700_misc_prng_state
  62     ps;
  63
  64   struct lfds700_misc_validation_info
  65     vi;
  66
  67   struct test_pal_logical_processor
  68     *lp;
  69
  70   struct util_thread_starter_state
  71     *tts;
  72
  73   struct test_state
  74     *ts;
  75
  76   test_pal_thread_state_t
  77     *thread_handles;
  78
  79   void
  80     *key;
  81
  82   assert( list_of_logical_processors != NULL );
  83   // TRD : memory_in_megabytes can be any value in its range
  84
  85   /* TRD : we create a single btree_au
  86            we generate 10k elements per thread (one per logical processor) in an array
  87            we set a random number in each element, which is the key
  88            random numbers are generated are from 0 to 5000, so we must have some duplicates
  89            (we don't use value, so we always pass in a NULL for that when we insert)
  90
  91            each thread loops, adds those elements into the btree, and counts the total number of insert fails
  92            (we don't count on a per value basis because of the performance hit - we'll be TLBing all the time)
  93            this test has the btree_au set to overwrite on add, so duplicates should be eliminated
  94
  95            we then merge the per-thread arrays
  96
  97            we should find in the tree one of every value, and the sum of the counts of each value (beyond the
  98            first value, which was inserted) in the merged arrays should equal the sum of the existing_baues returned
  99            from each thread when they inserted and found an existing element
 100
 101            we check the count of unique values in the merged array and use that when calling the btree_au validation function
 102
 103            we in-order walk and check that what we have in the tree matches what we have in the merged array
 104            and then check the fail counts
 105   */
 106
 107   internal_display_test_name( "Random adds and walking (overwrite on existing key)" );
 108
 109   lfds700_misc_prng_init( &ps );
 110
 111   lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 112
 113   lfds700_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS700_BTREE_AU_EXISTING_KEY_OVERWRITE, NULL );
 114
 115   ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors );
 116   number_elements = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
 117   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 118   {
 119     (ts+loop)->baus = &baus;
 120     (ts+loop)->element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
 121     (ts+loop)->number_elements = number_elements;
 122     (ts+loop)->insert_existing_count = 0;
 123
 124     for( subloop = 0 ; subloop < number_elements ; subloop++ )
 125     {
 126       random_value = LFDS700_MISC_PRNG_GENERATE( &ps );
 127       ((ts+loop)->element_array+subloop)->key = (lfds700_pal_uint_t) floor( (number_elements/2) * ((double) random_value / (double) LFDS700_MISC_PRNG_MAX) );
 128     }
 129   }
 130
 131   thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors );
 132
 133   util_thread_starter_new( &tts, number_logical_processors );
 134
 135   LFDS700_MISC_BARRIER_STORE;
 136
 137   lfds700_misc_force_store();
 138
 139   loop = 0;
 140   lasue = NULL;
 141
 142   while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
 143   {
 144     lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 145     util_thread_starter_start( tts, &thread_handles[loop], loop, lp, thread_adding, ts+loop );
 146     loop++;
 147   }
 148
 149   util_thread_starter_run( tts );
 150
 151   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 152     test_pal_thread_wait( thread_handles[loop] );
 153
 154   util_thread_starter_delete( tts );
 155
 156   free( thread_handles );
 157
 158   LFDS700_MISC_BARRIER_LOAD;
 159
 160   /* TRD : now for validation
 161            make an array equal to number_elements, set all to 0
 162            iterate over every per-thread array, counting the number of each value into this array
 163            so we can know how many elements ought to have failed to be inserted
 164            as well as being able to work out the actual number of elements which should be present in the btree, for the btree validation call
 165   */
 166
 167   key_count_array = util_malloc_wrapper( sizeof(lfds700_pal_uint_t) * number_elements );
 168   for( loop = 0 ; loop < number_elements ; loop++ )
 169     *(key_count_array+loop) = 0;
 170
 171   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 172     for( subloop = 0 ; subloop < number_elements ; subloop++ )
 173       ( *(key_count_array+( (ts+loop)->element_array+subloop)->key) )++;
 174
 175   // TRD : first, btree validation function
 176   vi.min_elements = number_elements;
 177
 178   for( loop = 0 ; loop < number_elements ; loop++ )
 179     if( *(key_count_array+loop) == 0 )
 180       vi.min_elements--;
 181
 182   vi.max_elements = vi.min_elements;
 183
 184   lfds700_btree_au_query( &baus, LFDS700_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) &dvs );
 185
 186   /* TRD : now check the sum of per-thread insert failures
 187            is what it should be, which is the sum of key_count_array,
 188            but with every count minus one (for the single succesful insert)
 189            and where elements of 0 are ignored (i.e. do not have -1 applied)
 190   */
 191
 192   expected_sum_insert_existing_count = 0;
 193
 194   for( loop = 0 ; loop < number_elements ; loop++ )
 195     if( *(key_count_array+loop) != 0 )
 196       expected_sum_insert_existing_count += *(key_count_array+loop) - 1;
 197
 198   actual_sum_insert_existing_count = 0;
 199
 200   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 201     actual_sum_insert_existing_count += (ts+loop)->insert_existing_count;
 202
 203   if( expected_sum_insert_existing_count != actual_sum_insert_existing_count )
 204     dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 205
 206   /* TRD : now compared the combined array and an in-order walk of the tree
 207            ignoring array elements with the value 0, we should find an exact match
 208   */
 209
 210   if( dvs == LFDS700_MISC_VALIDITY_VALID )
 211   {
 212     // TRD : in-order walk over btree_au and check key_count_array matches
 213     while( dvs == LFDS700_MISC_VALIDITY_VALID and lfds700_btree_au_get_by_absolute_position_and_then_by_relative_position(&baus, &baue, LFDS700_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS700_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
 214     {
 215       key = LFDS700_BTREE_AU_GET_KEY_FROM_ELEMENT( *baue );
 216
 217       while( *(key_count_array+index) == 0 )
 218         index++;
 219
 220       if( index++ != (lfds700_pal_uint_t) key )
 221         dvs = LFDS700_MISC_VALIDITY_INVALID_TEST_DATA;
 222     }
 223   }
 224
 225   // TRD : cleanup
 226   free( key_count_array );
 227
 228   lfds700_btree_au_cleanup( &baus, NULL );
 229
 230   // TRD : cleanup
 231   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 232     util_aligned_free( (ts+loop)->element_array );
 233
 234   free( ts );
 235
 236   // TRD : print the test result
 237   internal_display_test_result( 1, "btree_au", dvs );
 238
 239   return;
 240 }
 241
 242
 243
 244
 245
 246 /****************************************************************************/
 247 #pragma warning( disable : 4100 )
 248
 249 static int key_compare_function( void const *new_key, void const *key_in_tree )
 250 {
 251   int
 252     cr = 0;
 253
 254   // TRD : key_new can be any value in its range
 255   // TRD : key_in_tree can be any value in its range
 256
 257   if( (lfds700_pal_uint_t) new_key < (lfds700_pal_uint_t) key_in_tree )
 258     cr = -1;
 259
 260   if( (lfds700_pal_uint_t) new_key > (lfds700_pal_uint_t) key_in_tree )
 261     cr = 1;
 262
 263   return( cr );
 264 }
 265
 266 #pragma warning( default : 4100 )
 267
 268
 269
 270
 271
 272 /****************************************************************************/
 273 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION thread_adding( void *util_thread_starter_thread_state )
 274 {
 275   enum lfds700_btree_au_insert_result
 276     alr;
 277
 278   lfds700_pal_uint_t
 279     index = 0;
 280
 281   struct test_state
 282     *ts;
 283
 284   struct lfds700_btree_au_element
 285     *existing_baue;
 286
 287   struct lfds700_misc_prng_state
 288     ps;
 289
 290   struct util_thread_starter_thread_state
 291     *tsts;
 292
 293   LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 294
 295   assert( util_thread_starter_thread_state != NULL );
 296
 297   tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
 298   ts = (struct test_state *) tsts->thread_user_state;
 299
 300   lfds700_misc_prng_init( &ps );
 301
 302   util_thread_starter_ready_and_wait( tsts );
 303
 304   while( index < ts->number_elements )
 305   {
 306     LFDS700_BTREE_AU_SET_KEY_IN_ELEMENT( (ts->element_array+index)->baue, (ts->element_array+index)->key );
 307     LFDS700_BTREE_AU_SET_VALUE_IN_ELEMENT( (ts->element_array+index)->baue, 0 );
 308     alr = lfds700_btree_au_insert( ts->baus, &(ts->element_array+index)->baue, &existing_baue, &ps );
 309
 310     if( alr == LFDS700_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE )
 311       ts->insert_existing_count++;
 312
 313     index++;
 314   }
 315
 316   LFDS700_MISC_BARRIER_STORE;
 317
 318   lfds700_misc_force_store();
 319
 320   return( (test_pal_thread_return_t) EXIT_SUCCESS );
 321 }
 322