2 #include "libtest_tests_internal.h"
7 struct lfds710_btree_au_element
14 struct test_per_thread_state
17 insert_existing_count,
18 number_elements_per_thread;
20 struct lfds710_btree_au_state
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 );
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 )
39 actual_sum_insert_existing_count,
40 expected_sum_insert_existing_count,
45 number_elements_per_thread,
46 number_logical_processors,
50 struct lfds710_list_asu_element
53 struct lfds710_btree_au_element
56 struct lfds710_btree_au_state
59 struct lfds710_prng_state
62 struct lfds710_misc_validation_info
65 struct libtest_logical_processor
68 struct libtest_threadset_per_thread_state
71 struct libtest_threadset_state
77 struct test_per_thread_state
83 LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
84 LFDS710_PAL_ASSERT( ms != NULL );
85 LFDS710_PAL_ASSERT( dvs != NULL );
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)
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
97 we then merge the per-thread arrays
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
103 we check the count of unique values in the merged array and use that when calling the btree_au validation function
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
109 // internal_display_test_name( "Random adds and walking (overwrite on existing key)" );
111 *dvs = LFDS710_MISC_VALIDITY_VALID;
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 );
120 number_elements_per_thread = number_elements / number_logical_processors;
121 key_count_array = (lfds710_pal_uint_t *) ( te_array + number_elements );
123 lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
125 lfds710_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS710_BTREE_AU_EXISTING_KEY_OVERWRITE, NULL );
127 // TRD : get the threads ready
128 libtest_threadset_init( &ts, NULL );
130 while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
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] );
139 for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
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) );
148 LFDS710_MISC_BARRIER_STORE;
150 lfds710_misc_force_store();
152 // TRD : run the test
153 libtest_threadset_run( &ts );
155 libtest_threadset_cleanup( &ts );
158 LFDS710_MISC_BARRIER_LOAD;
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
167 for( loop = 0 ; loop < number_elements ; loop++ )
168 *(key_count_array+loop) = 0;
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) )++;
174 // TRD : first, btree validation function
175 vi.min_elements = number_elements;
177 for( loop = 0 ; loop < number_elements ; loop++ )
178 if( *(key_count_array+loop) == 0 )
181 vi.max_elements = vi.min_elements;
183 lfds710_btree_au_query( &baus, LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
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)
191 expected_sum_insert_existing_count = 0;
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;
197 actual_sum_insert_existing_count = 0;
199 for( loop = 0 ; loop < number_logical_processors ; loop++ )
200 actual_sum_insert_existing_count += (tpts+loop)->insert_existing_count;
202 if( expected_sum_insert_existing_count != actual_sum_insert_existing_count )
203 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
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
209 if( *dvs == LFDS710_MISC_VALIDITY_VALID )
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) )
214 key = LFDS710_BTREE_AU_GET_KEY_FROM_ELEMENT( *baue );
216 while( *(key_count_array+index) == 0 )
219 if( index++ != (lfds710_pal_uint_t) key )
220 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
224 lfds710_btree_au_cleanup( &baus, NULL );
233 /****************************************************************************/
234 #pragma warning( disable : 4100 )
236 static int key_compare_function( void const *new_key, void const *key_in_tree )
241 // TRD : key_new can be any value in its range
242 // TRD : key_in_tree can be any value in its range
244 if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) key_in_tree )
247 if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) key_in_tree )
253 #pragma warning( default : 4100 )
259 /****************************************************************************/
260 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
262 enum lfds710_btree_au_insert_result
268 struct lfds710_btree_au_element
271 struct libtest_threadset_per_thread_state
274 struct test_per_thread_state
277 LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
279 LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
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 );
284 libtest_threadset_thread_ready_and_wait( pts );
286 while( index < tpts->number_elements_per_thread )
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 );
292 if( alr == LFDS710_BTREE_AU_INSERT_RESULT_SUCCESS_OVERWRITE )
293 tpts->insert_existing_count++;
298 LFDS710_MISC_BARRIER_STORE;
300 lfds710_misc_force_store();
302 return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);