pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/test_and_benchmark/libtest/src/libtest_tests/libtest_tests_btree_addonly_unbalanced_random_adds_fail.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_fail_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_fail_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_failure_count,
  40     expected_sum_insert_failure_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 fail 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 insert fails from
 101            each thread
 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   *dvs = LFDS710_MISC_VALIDITY_VALID;
 110
 111   // TRD : allocate
 112   lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
 113   tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 114   pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
 115   // TRD : need a counter array later
 116   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 );
 117
 118   number_elements_per_thread = number_elements / number_logical_processors;
 119   key_count_array = (lfds710_pal_uint_t *) ( te_array + number_elements );
 120
 121   lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
 122
 123   lfds710_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS710_BTREE_AU_EXISTING_KEY_FAIL, NULL );
 124
 125   // TRD : get the threads ready
 126   libtest_threadset_init( &ts, NULL );
 127
 128   while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
 129   {
 130     lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
 131     (tpts+loop)->baus = &baus;
 132     (tpts+loop)->element_array = te_array + loop * number_elements_per_thread;
 133     (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
 134     (tpts+loop)->insert_fail_count = 0;
 135     libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_adding, &tpts[loop] );
 136
 137     for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
 138     {
 139       LFDS710_PRNG_GENERATE( ps, random_value );
 140       ((tpts+loop)->element_array+subloop)->key = (lfds710_pal_uint_t) ( (number_elements/2) * ((double) random_value / (double) LFDS710_PRNG_MAX) );
 141     }
 142
 143     loop++;
 144   }
 145
 146   LFDS710_MISC_BARRIER_STORE;
 147
 148   lfds710_misc_force_store();
 149
 150   // TRD : run the test
 151   libtest_threadset_run( &ts );
 152
 153   libtest_threadset_cleanup( &ts );
 154
 155   // TRD : validate
 156   LFDS710_MISC_BARRIER_LOAD;
 157
 158   /* TRD : now for validation
 159            make an array equal to number_elements, set all to 0
 160            iterate over every per-thread array, counting the number of each value into this array
 161            so we can know how many elements ought to have failed to be inserted
 162            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
 163   */
 164
 165   for( loop = 0 ; loop < number_elements ; loop++ )
 166     *(key_count_array+loop) = 0;
 167
 168   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 169     for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
 170       ( *(key_count_array+( (tpts+loop)->element_array+subloop)->key) )++;
 171
 172   // TRD : first, btree validation function
 173   vi.min_elements = number_elements;
 174
 175   for( loop = 0 ; loop < number_elements ; loop++ )
 176     if( *(key_count_array+loop) == 0 )
 177       vi.min_elements--;
 178
 179   vi.max_elements = vi.min_elements;
 180
 181   lfds710_btree_au_query( &baus, LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
 182
 183   /* TRD : now check the sum of per-thread insert failures
 184            is what it should be, which is the sum of key_count_array,
 185            but with every count minus one (for the single succesful insert)
 186            and where elements of 0 are ignored (i.e. do not have -1 applied)
 187   */
 188
 189   expected_sum_insert_failure_count = 0;
 190
 191   for( loop = 0 ; loop < number_elements ; loop++ )
 192     if( *(key_count_array+loop) != 0 )
 193       expected_sum_insert_failure_count += *(key_count_array+loop) - 1;
 194
 195   actual_sum_insert_failure_count = 0;
 196
 197   for( loop = 0 ; loop < number_logical_processors ; loop++ )
 198     actual_sum_insert_failure_count += (tpts+loop)->insert_fail_count;
 199
 200   if( expected_sum_insert_failure_count != actual_sum_insert_failure_count )
 201     *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 202
 203   /* TRD : now compared the combined array and an in-order walk of the tree
 204            ignoring array elements with the value 0, we should find an exact match
 205   */
 206
 207   if( *dvs == LFDS710_MISC_VALIDITY_VALID )
 208   {
 209     // TRD : in-order walk over btree_au and check key_count_array matches
 210     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) )
 211     {
 212       key = LFDS710_BTREE_AU_GET_KEY_FROM_ELEMENT( *baue );
 213
 214       while( *(key_count_array+index) == 0 )
 215         index++;
 216
 217       if( index++ != (lfds710_pal_uint_t) key )
 218         *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
 219     }
 220   }
 221
 222   lfds710_btree_au_cleanup( &baus, NULL );
 223
 224   return;
 225 }
 226
 227
 228
 229
 230
 231 /****************************************************************************/
 232 #pragma warning( disable : 4100 )
 233
 234 static int key_compare_function( void const *new_key, void const *key_in_tree )
 235 {
 236   int
 237     cr = 0;
 238
 239   // TRD : key_new can be any value in its range
 240   // TRD : key_in_tree can be any value in its range
 241
 242   if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) key_in_tree )
 243     cr = -1;
 244
 245   if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) key_in_tree )
 246     cr = 1;
 247
 248   return cr;
 249 }
 250
 251 #pragma warning( default : 4100 )
 252
 253
 254
 255
 256
 257 /****************************************************************************/
 258 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
 259 {
 260   enum lfds710_btree_au_insert_result
 261     alr;
 262
 263   lfds710_pal_uint_t
 264     index = 0;
 265
 266   struct libtest_threadset_per_thread_state
 267     *pts;
 268
 269   struct test_per_thread_state
 270     *tpts;
 271
 272   LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
 273
 274   LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
 275
 276   pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
 277   tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
 278
 279   libtest_threadset_thread_ready_and_wait( pts );
 280
 281   while( index < tpts->number_elements_per_thread )
 282   {
 283     LFDS710_BTREE_AU_SET_KEY_IN_ELEMENT( (tpts->element_array+index)->baue, (tpts->element_array+index)->key );
 284     LFDS710_BTREE_AU_SET_VALUE_IN_ELEMENT( (tpts->element_array+index)->baue, 0 );
 285     alr = lfds710_btree_au_insert( tpts->baus, &(tpts->element_array+index)->baue, NULL );
 286
 287     if( alr == LFDS710_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY )
 288       tpts->insert_fail_count++;
 289
 290     index++;
 291   }
 292
 293   LFDS710_MISC_BARRIER_STORE;
 294
 295   lfds710_misc_force_store();
 296
 297   return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
 298 }
 299