7 struct lfds700_list_aos_element
21 number_elements_per_thread;
23 struct lfds700_list_aos_state
30 /***** private prototypes *****/
31 static int new_ordered_with_cursor_compare_function( void const *value_new, void const *value_in_list );
32 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *util_thread_starter_thread_state );
33 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *util_thread_starter_thread_state );
39 /****************************************************************************/
40 void test_lfds700_list_aos_new_ordered_with_cursor( struct lfds700_list_asu_state *list_of_logical_processors, lfds700_pal_uint_t memory_in_megabytes )
42 enum lfds700_misc_validity
43 dvs = LFDS700_MISC_VALIDITY_VALID;
47 number_elements_per_thread,
48 number_elements_total,
49 number_logical_processors,
53 struct lfds700_list_aos_state
56 struct lfds700_list_asu_element
59 struct lfds700_misc_prng_state
62 struct lfds700_misc_validation_info
65 struct test_pal_logical_processor
68 struct util_thread_starter_state
77 test_pal_thread_state_t
80 assert( list_of_logical_processors != NULL );
81 // TRD : memory_in_megabytes can be any value in its range
83 /* TRD : run two threads per logical processor
85 the test runs for 10 seconds
87 the first thread loops over a pre-set list of random numbers
88 continually adding them using ordered insert
90 the second thread keeps iterating over the list, checking that
91 each element is larger than its predecessor
94 internal_display_test_name( "New ordered with cursor (%d seconds)", TEST_DURATION_IN_SECONDS );
96 lfds700_misc_prng_init( &ps );
98 lfds700_list_asu_query( list_of_logical_processors, LFDS700_LIST_ASU_QUERY_GET_POTENTIALLY_INACCURATE_COUNT, NULL, (void **) &number_logical_processors );
100 lfds700_list_aos_init_valid_on_current_logical_core( &laoss, new_ordered_with_cursor_compare_function, LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY, NULL );
102 /* TRD : create randomly ordered number array with unique elements
104 unique isn't necessary - the list will sort anyway - but
105 it permits slightly better validation
108 number_elements_per_thread = ( memory_in_megabytes * ONE_MEGABYTE_IN_BYTES ) / ( sizeof(struct test_element) * number_logical_processors );
110 // TRD : or the test takes a looooooong time...
111 if( number_elements_per_thread > 1000 )
112 number_elements_per_thread = 1000;
114 number_elements_total = number_elements_per_thread * number_logical_processors;
116 element_array = util_aligned_malloc( sizeof(struct test_element) * number_elements_total, LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES );
118 for( loop = 0 ; loop < number_elements_total ; loop++ )
119 (element_array+loop)->element_number = loop;
121 for( loop = 0 ; loop < number_elements_total ; loop++ )
123 offset = LFDS700_MISC_PRNG_GENERATE( &ps );
124 offset %= number_elements_total;
125 temp = (element_array + offset)->element_number;
126 (element_array + offset)->element_number = (element_array + loop)->element_number;
127 (element_array + loop)->element_number = temp;
130 ts = util_malloc_wrapper( sizeof(struct test_state) * number_logical_processors * 2 );
132 // TRD : the insert threads
133 for( loop = 0 ; loop < number_logical_processors ; loop++ )
135 (ts+loop)->laoss = &laoss;
136 (ts+loop)->element_array = element_array + number_elements_per_thread*loop;
137 (ts+loop)->error_flag = LOWERED;
138 (ts+loop)->number_elements_per_thread = number_elements_per_thread;
141 // TRD : the cursor threads
142 for( loop = number_logical_processors ; loop < number_logical_processors * 2 ; loop++ )
144 (ts+loop)->laoss = &laoss;
145 (ts+loop)->element_array = NULL;
146 (ts+loop)->error_flag = LOWERED;
149 thread_handles = util_malloc_wrapper( sizeof(test_pal_thread_state_t) * number_logical_processors * 2 );
151 util_thread_starter_new( &tts, number_logical_processors * 2 );
153 LFDS700_MISC_BARRIER_STORE;
155 lfds700_misc_force_store();
159 while( LFDS700_LIST_ASU_GET_START_AND_THEN_NEXT(*list_of_logical_processors, lasue) )
161 lp = LFDS700_LIST_ASU_GET_VALUE_FROM_ELEMENT( *lasue );
162 util_thread_starter_start( tts, &thread_handles[loop], loop, lp, new_ordered_with_cursor_insert_thread, ts+loop );
163 util_thread_starter_start( tts, &thread_handles[loop+number_logical_processors], loop+number_logical_processors, lp, new_ordered_with_cursor_cursor_thread, ts+loop+number_logical_processors );
167 util_thread_starter_run( tts );
169 for( loop = 0 ; loop < number_logical_processors * 2 ; loop++ )
170 test_pal_thread_wait( thread_handles[loop] );
172 util_thread_starter_delete( tts );
174 free( thread_handles );
176 /* TRD : validate the resultant list
178 the cursor threads were checking for orderedness
179 if that failed, they raise their error_flag
180 so validate the list, then check error_flags
183 LFDS700_MISC_BARRIER_LOAD;
185 vi.min_elements = vi.max_elements = number_elements_total;
187 lfds700_list_aos_query( &laoss, LFDS700_LIST_AOS_QUERY_SINGLETHREADED_VALIDATE, &vi, &dvs );
189 if( dvs == LFDS700_MISC_VALIDITY_VALID )
190 for( loop = number_logical_processors ; loop < number_logical_processors * 2 ; loop++ )
191 if( (ts+loop)->error_flag == RAISED )
192 dvs = LFDS700_MISC_VALIDITY_INVALID_ORDER;
194 lfds700_list_aos_cleanup( &laoss, NULL );
196 util_aligned_free( element_array );
200 internal_display_test_result( 1, "list_aos", dvs );
209 /****************************************************************************/
210 #pragma warning( disable : 4100 )
212 static int new_ordered_with_cursor_compare_function( void const *value_new, void const *value_in_list )
221 // TRD : value_new can be any value in its range
222 // TRD : value_in_list can be any value in its range
224 e1 = (struct test_element *) value_new;
225 e2 = (struct test_element *) value_in_list;
227 if( e1->element_number < e2->element_number )
230 if( e1->element_number > e2->element_number )
236 #pragma warning( default : 4100 )
242 /****************************************************************************/
243 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_insert_thread( void *util_thread_starter_thread_state )
248 struct lfds700_misc_prng_state
254 struct util_thread_starter_thread_state
257 LFDS700_MISC_BARRIER_LOAD;
259 assert( util_thread_starter_thread_state != NULL );
261 tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
262 ts = (struct test_state *) tsts->thread_user_state;
264 lfds700_misc_prng_init( &ps );
266 util_thread_starter_ready_and_wait( tsts );
268 for( loop = 0 ; loop < ts->number_elements_per_thread ; loop++ )
270 LFDS700_LIST_AOS_SET_KEY_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
271 LFDS700_LIST_AOS_SET_VALUE_IN_ELEMENT( (ts->element_array+loop)->laose, ts->element_array+loop );
272 lfds700_list_aos_insert( ts->laoss, &(ts->element_array+loop)->laose, NULL, &ps );
275 LFDS700_MISC_BARRIER_STORE;
277 lfds700_misc_force_store();
279 return( (test_pal_thread_return_t) EXIT_SUCCESS );
286 /****************************************************************************/
287 static test_pal_thread_return_t TEST_PAL_CALLING_CONVENTION new_ordered_with_cursor_cursor_thread( void *util_thread_starter_thread_state )
295 struct lfds700_list_aos_element
304 struct util_thread_starter_thread_state
311 LFDS700_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE;
313 assert( util_thread_starter_thread_state != NULL );
315 tsts = (struct util_thread_starter_thread_state *) util_thread_starter_thread_state;
316 ts = (struct test_state *) tsts->thread_user_state;
318 util_thread_starter_ready_and_wait( tsts );
320 current_time = start_time = time( NULL );
322 while( current_time < start_time + TEST_DURATION_IN_SECONDS )
324 prev_element_number = 0;
326 laose = LFDS700_LIST_AOS_GET_START( *ts->laoss );
328 // TRD : we may get start before any element has been added to the list
332 element = LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( *laose );
334 if( element->element_number < prev_element_number )
335 ts->error_flag = RAISED;
337 prev_element_number = element->element_number;
339 laose = LFDS700_LIST_AOS_GET_NEXT( *laose );
341 while( laose != NULL )
343 element = LFDS700_LIST_AOS_GET_VALUE_FROM_ELEMENT( *laose );
345 if( element->element_number <= prev_element_number )
346 ts->error_flag = RAISED;
348 prev_element_number = element->element_number;
350 laose = LFDS700_LIST_AOS_GET_NEXT( *laose );
353 if( time_loop++ == REDUCED_TIME_LOOP_COUNT )
356 time( ¤t_time );
360 LFDS700_MISC_BARRIER_STORE;
362 lfds700_misc_force_store();
364 return( (test_pal_thread_return_t) EXIT_SUCCESS );