2 #include "libtest_tests_internal.h"
7 struct lfds710_hash_a_element
14 struct test_per_thread_state
17 number_elements_per_thread,
20 struct lfds710_hash_a_state
27 /***** private prototypes *****/
28 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state );
29 static int key_compare_function( void const *new_key, void const *existing_key );
30 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash );
31 static int LIBTEST_PAL_STDLIB_CALLBACK_CALLING_CONVENTION qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 );
37 /****************************************************************************/
38 void libtest_tests_hash_a_random_adds_overwrite_on_existing( struct lfds710_list_asu_state *list_of_logical_processors, struct libshared_memory_state *ms, enum lfds710_misc_validity *dvs )
44 actual_sum_overwrite_existing_count,
45 expected_sum_overwrite_existing_count,
48 number_elements_per_thread,
49 number_elements_total,
50 number_logical_processors,
53 struct lfds710_hash_a_iterate
56 struct lfds710_hash_a_element
59 struct lfds710_hash_a_state
62 struct lfds710_list_asu_element
65 struct lfds710_btree_au_state
68 struct lfds710_prng_state
71 struct lfds710_misc_validation_info
74 struct libtest_logical_processor
77 struct libtest_threadset_per_thread_state
80 struct libtest_threadset_state
86 struct test_per_thread_state
93 LFDS710_PAL_ASSERT( list_of_logical_processors != NULL );
94 LFDS710_PAL_ASSERT( ms != NULL );
95 LFDS710_PAL_ASSERT( dvs != NULL );
97 /* TRD : we create a single hash_a
98 we generate n elements per thread
99 each element contains a key value, which is set to a random value
100 (we don't use value, so it's just set to 0)
101 the threads then run, putting
102 the threads count their number of overwrite hits
103 once the threads are done, then we
104 count the number of each key
105 from this we figure out the min/max element for hash_a validation, so we call validation
106 we check the sum of overwrites for each thread is what it should be
107 then using the hash_a get() we check all the elements we expect are present
108 and then we iterate over the hash_a
109 checking we see each key once
112 *dvs = LFDS710_MISC_VALIDITY_VALID;
115 lfds710_list_asu_query( list_of_logical_processors, LFDS710_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
116 tpts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct test_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
117 pts = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct libtest_threadset_per_thread_state) * number_logical_processors, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
118 baus = libshared_memory_alloc_from_unknown_node( ms, sizeof(struct lfds710_btree_au_state) * 1000, LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES );
119 element_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_total );
120 key_count_array = (lfds710_pal_uint_t *) ( element_array + number_elements_total );
122 // TRD : per thread first, for correct rounding, for later code
123 number_elements_per_thread = number_elements_total / number_logical_processors;
124 number_elements_total = number_elements_per_thread * number_logical_processors;
126 lfds710_prng_init_valid_on_current_logical_core( &ps, LFDS710_PRNG_SEED );
128 lfds710_hash_a_init_valid_on_current_logical_core( &has, baus, 1000, key_compare_function, key_hash_function, LFDS710_HASH_A_EXISTING_KEY_OVERWRITE, NULL );
130 // TRD : created an ordered list of unique numbers
132 for( loop = 0 ; loop < number_elements_total ; loop++ )
134 LFDS710_PRNG_GENERATE( ps, random_value );
135 (element_array+loop)->key = (lfds710_pal_uint_t) ( (number_elements_total/2) * ((double) random_value / (double) LFDS710_PRNG_MAX) );
138 // TRD : get the threads ready
139 libtest_threadset_init( &ts, NULL );
143 while( LFDS710_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors,lasue) )
145 lp = LFDS710_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
146 (tpts+loop)->has = &has;
147 (tpts+loop)->element_array = element_array + number_elements_per_thread*loop;
148 (tpts+loop)->overwrite_count = 0;
149 (tpts+loop)->number_elements_per_thread = number_elements_per_thread;
150 libtest_threadset_add_thread( &ts, &pts[loop], lp, thread_adding, &tpts[loop] );
154 // TRD : run the test
155 libtest_threadset_run( &ts );
157 libtest_threadset_cleanup( &ts );
160 LFDS710_MISC_BARRIER_LOAD;
162 // TRD : now for validation
163 for( loop = 0 ; loop < number_elements_total ; loop++ )
164 *(key_count_array+loop) = 0;
166 for( loop = 0 ; loop < number_elements_total ; loop++ )
167 ( *(key_count_array + (element_array+loop)->key) )++;
169 vi.min_elements = number_elements_total;
171 for( loop = 0 ; loop < number_elements_total ; loop++ )
172 if( *(key_count_array+loop) == 0 )
175 vi.max_elements = vi.min_elements;
177 lfds710_hash_a_query( &has, LFDS710_HASH_A_QUERY_SINGLETHREADED_VALIDATE, (void *) &vi, (void *) dvs );
179 expected_sum_overwrite_existing_count = 0;
181 for( loop = 0 ; loop < number_elements_total ; loop++ )
182 if( *(key_count_array+loop) != 0 )
183 expected_sum_overwrite_existing_count += *(key_count_array+loop) - 1;
185 actual_sum_overwrite_existing_count = 0;
187 for( loop = 0 ; loop < number_logical_processors ; loop++ )
188 actual_sum_overwrite_existing_count += (tpts+loop)->overwrite_count;
190 if( expected_sum_overwrite_existing_count != actual_sum_overwrite_existing_count )
191 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
193 // TRD : now loop over the expected array and check we can get() every element
194 for( loop = 0 ; loop < number_elements_total ; loop++ )
195 if( *(key_count_array+loop) > 0 )
197 rv = lfds710_hash_a_get_by_key( &has, NULL, NULL, (void *) loop, &hae );
200 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
203 /* TRD : now iterate, checking we find every element and no others
204 to do this in a timely manner, we need to qsort() the key values
205 and use bsearch() to check for items in the array
208 for( loop = 0 ; loop < number_elements_total ; loop++ )
209 if( *(key_count_array+loop) != 0 )
210 *(key_count_array+loop) = loop;
212 *(key_count_array+loop) = 0;
214 qsort( key_count_array, number_elements_total, sizeof(lfds710_pal_uint_t), qsort_and_bsearch_key_compare_function );
216 lfds710_hash_a_iterate_init( &has, &hai );
218 while( *dvs == LFDS710_MISC_VALIDITY_VALID and lfds710_hash_a_iterate(&hai, &hae) )
220 key = LFDS710_HASH_A_GET_KEY_FROM_ELEMENT( *hae );
222 key_pointer = bsearch( &key, key_count_array, number_elements_total, sizeof(lfds710_pal_uint_t), qsort_and_bsearch_key_compare_function );
224 if( key_pointer == NULL )
225 *dvs = LFDS710_MISC_VALIDITY_INVALID_TEST_DATA;
229 lfds710_hash_a_cleanup( &has, NULL );
238 /****************************************************************************/
239 static libshared_pal_thread_return_t LIBSHARED_PAL_THREAD_CALLING_CONVENTION thread_adding( void *libtest_threadset_per_thread_state )
241 enum lfds710_hash_a_insert_result
247 struct test_per_thread_state
250 struct libtest_threadset_per_thread_state
253 LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
255 LFDS710_PAL_ASSERT( libtest_threadset_per_thread_state != NULL );
257 pts = (struct libtest_threadset_per_thread_state *) libtest_threadset_per_thread_state;
259 tpts = LIBTEST_THREADSET_GET_USER_STATE_FROM_PER_THREAD_STATE( *pts );
261 libtest_threadset_thread_ready_and_wait( pts );
263 while( index < tpts->number_elements_per_thread )
265 LFDS710_HASH_A_SET_KEY_IN_ELEMENT( (tpts->element_array+index)->hae, (tpts->element_array+index)->key );
266 LFDS710_HASH_A_SET_VALUE_IN_ELEMENT( (tpts->element_array+index)->hae, 0 );
267 apr = lfds710_hash_a_insert( tpts->has, &(tpts->element_array+index)->hae, NULL );
269 if( apr == LFDS710_HASH_A_PUT_RESULT_SUCCESS_OVERWRITE )
270 tpts->overwrite_count++;
275 LFDS710_MISC_BARRIER_STORE;
277 lfds710_misc_force_store();
279 return LIBSHARED_PAL_THREAD_RETURN_CAST(RETURN_SUCCESS);
286 /****************************************************************************/
287 #pragma warning( disable : 4100 )
289 static int key_compare_function( void const *new_key, void const *existing_key )
294 // TRD : new_key can be NULL (i.e. 0)
295 // TRD : existing_key can be NULL (i.e. 0)
297 if( (lfds710_pal_uint_t) new_key < (lfds710_pal_uint_t) existing_key )
300 if( (lfds710_pal_uint_t) new_key > (lfds710_pal_uint_t) existing_key )
306 #pragma warning( default : 4100 )
312 /****************************************************************************/
313 #pragma warning( disable : 4100 )
315 static void key_hash_function( void const *key, lfds710_pal_uint_t *hash )
317 // TRD : key can be NULL
318 LFDS710_PAL_ASSERT( hash != NULL );
322 /* TRD : this function iterates over the user data
323 and we are using the void pointer *as* key data
324 so here we need to pass in the addy of key
327 LFDS710_HASH_A_HASH_FUNCTION( (void *) &key, sizeof(lfds710_pal_uint_t), *hash );
332 #pragma warning( default : 4100 )
338 /****************************************************************************/
339 static int LIBTEST_PAL_STDLIB_CALLBACK_CALLING_CONVENTION qsort_and_bsearch_key_compare_function( void const *e1, void const *e2 )
348 s1 = *(lfds710_pal_uint_t *) e1;
349 s2 = *(lfds710_pal_uint_t *) e2;