2 #include "libtest_tests_internal.h"
7 struct lfds710_btree_au_element
14 struct test_per_thread_state
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_fail_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_failure_count,
40 expected_sum_insert_failure_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 fail 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 insert fails from
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 *dvs = LFDS710_MISC_VALIDITY_VALID;
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 );
118 number_elements_per_thread = number_elements / number_logical_processors;
119 key_count_array = (lfds710_pal_uint_t *) ( te_array + number_elements );
121 lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
123 lfds710_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS710_BTREE_AU_EXISTING_KEY_FAIL, NULL );
125 // TRD : get the threads ready
126 libtest_threadset_init( &ts, NULL );
128 while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
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] );
137 for( subloop = 0 ; subloop < number_elements_per_thread ; subloop++ )
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) );
146 LFDS710_MISC_BARRIER_STORE;
148 lfds710_misc_force_store();
150 // TRD : run the test
151 libtest_threadset_run( &ts );
153 libtest_threadset_cleanup( &ts );
156 LFDS710_MISC_BARRIER_LOAD;
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
165 for( loop = 0 ; loop < number_elements ; loop++ )
166 *(key_count_array+loop) = 0;
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) )++;
172 // TRD : first, btree validation function
173 vi.min_elements = number_elements;
175 for( loop = 0 ; loop < number_elements ; loop++ )
176 if( *(key_count_array+loop) == 0 )
179 vi.max_elements = vi.min_elements;
181 lfds710_btree_au_query( &baus, LFDS710_BTREE_AU_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
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)
189 expected_sum_insert_failure_count = 0;
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;
195 actual_sum_insert_failure_count = 0;
197 for( loop = 0 ; loop < number_logical_processors ; loop++ )
198 actual_sum_insert_failure_count += (tpts+loop)->insert_fail_count;
200 if( expected_sum_insert_failure_count != actual_sum_insert_failure_count )
201 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
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
207 if( *dvs == LFDS710_MISC_VALIDITY_VALID )
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) )
212 key = LFDS710_BTREE_AU_GET_KEY_FROM_ELEMENT( *baue );
214 while( *(key_count_array+index) == 0 )
217 if( index++ != (lfds710_pal_uint_t) key )
218 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
222 lfds710_btree_au_cleanup( &baus, NULL );
231 /****************************************************************************/
232 #pragma warning( disable : 4100 )
234 static int key_compare_function( void const *new_key, void const *key_in_tree )
239 // TRD : key_new can be any value in its range
240 // TRD : key_in_tree can be any value in its range
242 if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) key_in_tree )
245 if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) key_in_tree )
251 #pragma warning( default : 4100 )
257 /****************************************************************************/
258 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
260 enum lfds710_btree_au_insert_result
266 struct libtest_threadset_per_thread_state
269 struct test_per_thread_state
272 LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
274 LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
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 );
279 libtest_threadset_thread_ready_and_wait( pts );
281 while( index < tpts->number_elements_per_thread )
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 );
287 if( alr == LFDS710_BTREE_AU_INSERT_RESULT_FAILURE_EXISTING_KEY )
288 tpts->insert_fail_count++;
293 LFDS710_MISC_BARRIER_STORE;
295 lfds710_misc_force_store();
297 return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);