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

   1 /***** includes *****/
   2 #include "libtest_tests_internal.h"
   3
   4 /***** structs *****/
   5 struct test_element
   6 {
   7   struct lfds710_btree_au_element
   8     baue;
   9
  10   lfds710_pal_uint_t
  11     key;
  12 };
  13
  14 struct test_per_thread_state
  15 {
  16   lfds710_pal_uint_t
  17     insert_existing_count,
  18     number_elements_per_thread;
  19
  20   struct lfds710_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 libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state );
  30
  31
  32
  33
  34
  35 /****************************************************************************/
  36 void libtest_tests_btree_au_random_adds_overwrite_on_existing( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
  37 {
  38   lfds710_pal_uint_t
  39     actual_sum_insert_existing_count,
  40     expected_sum_insert_existing_count,
  41     index = 0,
  42     *key_count_array,
  43     loop = 0,
  44     number_elements,
  45     number_elements_per_thread,
  46     number_logical_processors,
  47     random_value,
  48     subloop;
  49
  50   struct lfds710_list_asu_element
  51     *lasue = NULL;
  52
  53   struct lfds710_btree_au_element
  54     *baue = NULL;
  55
  56   struct lfds710_btree_au_state
  57     baus;
  58
  59   struct lfds710_prng_state
  60     ps;
  61
  62   struct lfds710_misc_validation_info
  63     vi;
  64
  65   struct libtest_logical_processor
  66     *lp;
  67
  68   struct libtest_threadset_per_thread_state
  69     *pts;
  70
  71   struct libtest_threadset_state
  72     ts;
  73
  74   struct test_element
  75     *te_array;
  76
  77   struct test_per_thread_state
  78     *tpts;
  79
  80   void
  81     *key;
  82
  83   LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
  84   LFDS710_PAL_ASSERT( ms != NULL );
  85   LFDS710_PAL_ASSERT( dvs != NULL );
  86
  87   /* TRD : we create a single btree_au
  88            we generate 10k elements per thread (one per logical processor) in an array
  89            we set a random number in each element, which is the key
  90            random numbers are generated are from 0 to 5000, so we must have some duplicates
  91            (we don't use value, so we always pass in a NULL for that when we insert)
  92
  93            each thread loops, adds those elements into the btree, and counts the total number of insert fails
  94            (we don't count on a per value basis because of the performance hit - we'll be TLBing all the time)
  95            this test has the btree_au set to overwrite on add, so duplicates should be eliminated
  96
  97            we then merge the per-thread arrays
  98
  99            we should find in the tree one of every value, and the sum of the counts of each value (beyond the
 100            first value, which was inserted) in the merged arrays should equal the sum of the existing_baues returned
 101            from each thread when they inserted and found an existing element
 102
 103            we check the count of unique values in the merged array and use that when calling the btree_au validation function
 104
 105            we in-order walk and check that what we have in the tree matches what we have in the merged array
 106            and then check the fail counts
 107   */
 108
 109   // internal_display_test_name( "Random adds and walking (overwrite on existing key)" );
 110
 111   *dvs = LFDS710_MISC_VALIDITY_VALID;
 112
 113   // TRD : allocate
 114   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 115   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 116   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 117   // TRD : need a counter array later
 118   te_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 );
 119
 120   number_elements_per_thread = number_elements / number_logical_processors;
 121   key_count_array = (lfds710_pal_uint_t *) ( te_array + number_elements );
 122
 123   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 124
 125   lfds710_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS710_BTREE_AU_EXISTING_KEY_OVERWRITE, NULL );
 126
 127   // TRD : get the threads ready
 128   libtest_threadset_init( &ts, NULL );
 129
 130   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 131   {
 132     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 133     (tpts+loop)->baus = &baus;
 134     (tpts+loop)->element_array = te_array + loop * number_elements_per_thread;
 135     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 136     (tpts+loop)->insert_existing_count = 0;
 137     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_adding, &tpts[loop] );
 138
 139     for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
 140     {
 141       LFDS710_PRNG_GENERATE( ps, random_value );
 142       ((tpts+loop)->element_array+subloop)->key = (lfds710_pal_uint_t) ( (number_elements/2) * ((double) random_value / (double) LFDS710_PRNG_MAX) );
 143     }
 144
 145     loop++;
 146   }
 147
 148   LFDS710_MISC_BARRIER_STORE;
 149
 150   lfds710_misc_force_store();
 151
 152   // TRD : run the test
 153   libtest_threadset_run( &ts );
 154
 155   libtest_threadset_cleanup( &ts );
 156
 157   // TRD : validate
 158   LFDS710_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   for( loop = 0 ; loop < number_elements ; loop++ )
 168     *(key_count_array+loop) = 0;
 169
 170   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 171     for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
 172       ( *(key_count_array+( (tpts+loop)->element_array+subloop)->key) )++;
 173
 174   // TRD : first, btree validation function
 175   vi.min_elements = number_elements;
 176
 177   for( loop = 0 ; loop < number_elements ; loop++ )
 178     if( *(key_count_array+loop) == 0 )
 179       vi.min_elements--;
 180
 181   vi.max_elements = vi.min_elements;
 182
 183   lfds710_btree_au_query( &baus, LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
 184
 185   /* TRD : now check the sum of per-thread insert failures
 186            is what it should be, which is the sum of key_count_array,
 187            but with every count minus one (for the single succesful insert)
 188            and where elements of 0 are ignored (i.e. do not have -1 applied)
 189   */
 190
 191   expected_sum_insert_existing_count = 0;
 192
 193   for( loop = 0 ; loop < number_elements ; loop++ )
 194     if( *(key_count_array+loop) != 0 )
 195       expected_sum_insert_existing_count += *(key_count_array+loop) - 1;
 196
 197   actual_sum_insert_existing_count = 0;
 198
 199   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 200     actual_sum_insert_existing_count += (tpts+loop)->insert_existing_count;
 201
 202   if( expected_sum_insert_existing_count != actual_sum_insert_existing_count )
 203     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 204
 205   /* TRD : now compared the combined array and an in-order walk of the tree
 206            ignoring array elements with the value 0, we should find an exact match
 207   */
 208
 209   if( *dvs == LFDS710_MISC_VALIDITY_VALID )
 210   {
 211     // TRD : in-order walk over btree_au and check key_count_array matches
 212     while( *dvs == LFDS710_MISC_VALIDITY_VALID and lfds710_btree_au_get_by_absolute_position_and_then_by_relative_position(&baus, &baue, LFDS710_BTREE_AU_ABSOLUTE_POSITION_SMALLEST_IN_TREE, LFDS710_BTREE_AU_RELATIVE_POSITION_NEXT_LARGER_ELEMENT_IN_ENTIRE_TREE) )
 213     {
 214       key = LFDS710_BTREE_AU_GET_KEY_FROM_ELEMENT( *baue );
 215
 216       while( *(key_count_array+index) == 0 )
 217         index++;
 218
 219       if( index++ != (lfds710_pal_uint_t) key )
 220         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 221     }
 222   }
 223
 224   lfds710_btree_au_cleanup( &baus, NULL );
 225
 226   return;
 227 }
 228
 229
 230
 231
 232
 233 /****************************************************************************/
 234 #pragma warning( disable : 4100 )
 235
 236 static int key_compare_function( void const *new_key, void const *key_in_tree )
 237 {
 238   int
 239     cr = 0;
 240
 241   // TRD : key_new can be any value in its range
 242   // TRD : key_in_tree can be any value in its range
 243
 244   if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) key_in_tree )
 245     cr = -1;
 246
 247   if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) key_in_tree )
 248     cr = 1;
 249
 250   return cr;
 251 }
 252
 253 #pragma warning( default : 4100 )
 254
 255
 256
 257
 258
 259 /****************************************************************************/
 260 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
 261 {
 262   enum lfds710_btree_au_insert_result
 263     alr;
 264
 265   lfds710_pal_uint_t
 266     index = 0;
 267
 268   struct lfds710_btree_au_element
 269     *existing_baue;
 270
 271   struct libtest_threadset_per_thread_state
 272     *pts;
 273
 274   struct test_per_thread_state
 275     *tpts;
 276
 277   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 278
 279   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 280
 281   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 282   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 283
 284   libtest_threadset_thread_ready_and_wait( pts );
 285
 286   while( index < tpts->number_elements_per_thread )
 287   {
 288     LFDS710_BTREE_AU_SET_KEY_IN_ELEMENT( (tpts->element_array+index)->baue, (tpts->element_array+index)->key );
 289     LFDS710_BTREE_AU_SET_VALUE_IN_ELEMENT( (tpts->element_array+index)->baue, 0 );
 290     alr = lfds710_btree_au_insert( tpts->baus, &(tpts->element_array+index)->baue, &existing_baue );
 291
 292     if( alr == LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE )
 293       tpts->insert_existing_count++;
 294
 295     index++;
 296   }
 297
 298   LFDS710_MISC_BARRIER_STORE;
 299
 300   lfds710_misc_force_store();
 301
 302   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 303 }
 304