7 /****************************************************************************/
8 void test_lfds610_stack( void )
14 stack_test_internal_popping();
15 stack_test_internal_pushing();
16 stack_test_internal_popping_and_pushing();
17 stack_test_internal_rapid_popping_and_pushing();
26 /****************************************************************************/
27 void stack_test_internal_popping( void )
40 enum lfds610_data_structure_validity
41 dvs = LFDS610_VALIDITY_VALID;
43 struct lfds610_stack_state
46 struct stack_test_popping_state
49 /* TRD : we create a stack with 1,000,000 elements
51 we then populate the stack, where each element is
52 set to contain a void pointer which is its element number
54 we then run one thread per CPU
55 where each thread loops, popping as quickly as possible
56 each popped element is pushed onto a thread-local stack
58 the threads run till the source stack is empty
60 we then check the thread-local stacks
61 we should find we have every element
66 internal_display_test_name( "Popping" );
68 cpu_count = abstraction_cpu_count();
70 lfds610_stack_new( &ss, 1000000 );
72 for( loop = 0 ; loop < 1000000 ; loop++ )
73 lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
75 stps = malloc( sizeof(struct stack_test_popping_state) * cpu_count );
76 for( loop = 0 ; loop < cpu_count ; loop++ )
79 lfds610_stack_new( &(stps+loop)->ss_thread_local, 1000000 );
82 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
84 for( loop = 0 ; loop < cpu_count ; loop++ )
85 abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping, stps+loop );
87 for( loop = 0 ; loop < cpu_count ; loop++ )
88 abstraction_thread_wait( thread_handles[loop] );
90 free( thread_handles );
92 // TRD : now we check the thread-local stacks
93 found_count = malloc( sizeof(unsigned int) * 1000000 );
94 for( loop = 0 ; loop < 1000000 ; loop++ )
95 *(found_count+loop) = 0;
97 for( loop = 0 ; loop < cpu_count ; loop++ )
98 while( lfds610_stack_pop((stps+loop)->ss_thread_local, (void **) &count) )
99 (*(found_count+count))++;
101 for( loop = 0 ; loop < 1000000 and dvs == LFDS610_VALIDITY_VALID ; loop++ )
103 if( *(found_count+loop) == 0 )
104 dvs = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
106 if( *(found_count+loop) > 1 )
107 dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
112 for( loop = 0 ; loop < cpu_count ; loop++ )
113 lfds610_stack_delete( (stps+loop)->ss_thread_local, NULL, NULL );
115 lfds610_stack_delete( ss, NULL, NULL );
117 // TRD : print the test result
118 internal_display_test_result( 1, "stack", dvs );
127 /****************************************************************************/
128 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping( void *stack_test_popping_state )
130 struct stack_test_popping_state
136 assert( stack_test_popping_state != NULL );
138 stps = (struct stack_test_popping_state *) stack_test_popping_state;
140 lfds610_stack_use( stps->ss );
142 while( lfds610_stack_pop(stps->ss, (void **) &count) )
143 lfds610_stack_push( stps->ss_thread_local, (void *) count );
145 return( (thread_return_t) EXIT_SUCCESS );
152 /****************************************************************************/
153 void stack_test_internal_pushing( void )
162 enum lfds610_data_structure_validity
165 struct stack_test_pushing_state
168 struct lfds610_stack_state
175 *per_thread_counters;
177 struct lfds610_validation_info
178 vi = { 1000000, 1000000 };
180 /* TRD : we create a stack with 1,000,000 elements
182 we then create one thread per CPU, where each thread
183 pushes as quickly as possible to the stack
185 the data pushed is a counter and a thread ID
187 the threads exit when the stack is full
189 we then validate the stack;
191 checking that the counts increment on a per unique ID basis
192 and that the number of elements we pop equals 1,000,000
193 (since each element has an incrementing counter which is
194 unique on a per unique ID basis, we can know we didn't lose
198 internal_display_test_name( "Pushing" );
200 cpu_count = abstraction_cpu_count();
202 stps = malloc( sizeof(struct stack_test_pushing_state) * cpu_count );
204 // TRD : the main stack
205 lfds610_stack_new( &ss, 1000000 );
207 for( loop = 0 ; loop < cpu_count ; loop++ )
209 (stps+loop)->thread_number = (lfds610_atom_t) loop;
210 (stps+loop)->ss = ss;
213 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
215 for( loop = 0 ; loop < cpu_count ; loop++ )
216 abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_pushing, stps+loop );
218 for( loop = 0 ; loop < cpu_count ; loop++ )
219 abstraction_thread_wait( thread_handles[loop] );
221 free( thread_handles );
223 // TRD : the stack is now fully pushed; time to verify
224 per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
226 for( loop = 0 ; loop < cpu_count ; loop++ )
227 *(per_thread_counters+loop) = 1000000;
229 lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, &vi, (void *) dvs );
231 while( dvs[0] == LFDS610_VALIDITY_VALID and lfds610_stack_pop(ss, (void **) &user_data) )
233 thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
234 count = (user_data << 8) >> 8;
236 if( thread >= cpu_count )
238 dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
242 if( count > per_thread_counters[thread] )
243 dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
245 if( count < per_thread_counters[thread] )
246 per_thread_counters[thread] = count-1;
250 free( per_thread_counters );
254 lfds610_stack_delete( ss, NULL, NULL );
256 // TRD : print the test result
257 internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
266 /****************************************************************************/
267 thread_return_t CALLING_CONVENTION stack_test_internal_thread_pushing( void *stack_test_pushing_state )
269 struct stack_test_pushing_state
275 assert( stack_test_pushing_state != NULL );
277 stps = (struct stack_test_pushing_state *) stack_test_pushing_state;
279 lfds610_stack_use( stps->ss );
281 // TRD : we write (thread_number | counter), where thread_number is the top 8 bits of the lfds610_atom_t
282 while( lfds610_stack_push(stps->ss, (void **) ((stps->thread_number << (sizeof(lfds610_atom_t)*8-8)) | counter++)) );
284 return( (thread_return_t) EXIT_SUCCESS );
291 /****************************************************************************/
292 void stack_test_internal_popping_and_pushing( void )
302 enum lfds610_data_structure_validity
305 struct lfds610_stack_state
308 struct stack_test_popping_and_pushing_state
311 struct lfds610_validation_info
314 /* TRD : we have two threads per CPU
315 the threads loop for ten seconds
316 the first thread pushes 100000 elements then pops 100000 elements
317 the second thread pops 100000 elements then pushes 100000 elements
318 all pushes and pops go onto the single main stack
320 after time is up, all threads push what they have remaining onto
323 we then validate the main stack
326 internal_display_test_name( "Popping and pushing (10 seconds)" );
328 cpu_count = abstraction_cpu_count();
330 // TRD : just some initial elements so the pushing threads can start immediately
331 lfds610_stack_new( &ss, 100000 * cpu_count * 2 );
333 for( loop = 0 ; loop < 100000 * cpu_count ; loop++ )
334 lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
336 stpps = malloc( sizeof(struct stack_test_popping_and_pushing_state) * cpu_count * 2 );
338 for( loop = 0 ; loop < cpu_count ; loop++ )
340 (stpps+loop)->ss = ss;
341 lfds610_stack_new( &(stpps+loop)->local_ss, 100000 );
343 (stpps+loop+cpu_count)->ss = ss;
344 lfds610_stack_new( &(stpps+loop+cpu_count)->local_ss, 100000 );
346 // TRD : fill the pushing thread stacks
347 for( subloop = 0 ; subloop < 100000 ; subloop++ )
348 lfds610_stack_push( (stpps+loop+cpu_count)->local_ss, (void *) (lfds610_atom_t) subloop );
351 thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
353 for( loop = 0 ; loop < cpu_count ; loop++ )
355 abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping_and_pushing_start_popping, stpps+loop );
356 abstraction_thread_start( &thread_handles[loop+cpu_count], loop, stack_test_internal_thread_popping_and_pushing_start_pushing, stpps+loop+cpu_count );
359 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
360 abstraction_thread_wait( thread_handles[loop] );
362 free( thread_handles );
364 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
365 lfds610_stack_delete( (stpps+loop)->local_ss, NULL, NULL );
369 vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
371 lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
373 lfds610_stack_delete( ss, NULL, NULL );
375 // TRD : print the test result
376 internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
386 /****************************************************************************/
387 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_popping( void *stack_test_popping_and_pushing_state )
389 struct stack_test_popping_and_pushing_state
401 assert( stack_test_popping_and_pushing_state != NULL );
403 stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
405 lfds610_stack_use( stpps->ss );
406 lfds610_stack_use( stpps->local_ss );
410 while( time(NULL) < start_time + 10 )
414 while( count < 100000 )
415 if( lfds610_stack_pop(stpps->ss, &user_data) )
417 lfds610_stack_push( stpps->local_ss, user_data );
421 // TRD : return our local stack to the main stack
422 while( lfds610_stack_pop(stpps->local_ss, &user_data) )
423 lfds610_stack_push( stpps->ss, user_data );
426 return( (thread_return_t) EXIT_SUCCESS );
433 /****************************************************************************/
434 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_pushing( void *stack_test_popping_and_pushing_state )
436 struct stack_test_popping_and_pushing_state
448 assert( stack_test_popping_and_pushing_state != NULL );
450 stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
452 lfds610_stack_use( stpps->ss );
453 lfds610_stack_use( stpps->local_ss );
457 while( time(NULL) < start_time + 10 )
459 // TRD : return our local stack to the main stack
460 while( lfds610_stack_pop(stpps->local_ss, &user_data) )
461 lfds610_stack_push( stpps->ss, user_data );
465 while( count < 100000 )
466 if( lfds610_stack_pop(stpps->ss, &user_data) )
468 lfds610_stack_push( stpps->local_ss, user_data );
473 // TRD : now push whatever we have in our local stack
474 while( lfds610_stack_pop(stpps->local_ss, &user_data) )
475 lfds610_stack_push( stpps->ss, user_data );
477 return( (thread_return_t) EXIT_SUCCESS );
484 /****************************************************************************/
485 void stack_test_internal_rapid_popping_and_pushing( void )
494 struct lfds610_stack_state
497 struct lfds610_validation_info
500 enum lfds610_data_structure_validity
503 /* TRD : in these tests there is a fundamental antagonism between
504 how much checking/memory clean up that we do and the
505 likelyhood of collisions between threads in their lock-free
508 the lock-free operations are very quick; if we do anything
509 much at all between operations, we greatly reduce the chance
512 so we have some tests which do enough checking/clean up that
513 they can tell the stack is valid and don't leak memory
514 and here, this test now is one of those which does minimal
515 checking - in fact, the nature of the test is that you can't
516 do any real checking - but goes very quickly
518 what we do is create a small stack and then run one thread
519 per CPU, where each thread simply pushes and then immediately
522 the test runs for ten seconds
524 after the test is done, the only check we do is to traverse
525 the stack, checking for loops and ensuring the number of
529 internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
531 cpu_count = abstraction_cpu_count();
533 lfds610_stack_new( &ss, cpu_count );
535 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
537 for( loop = 0 ; loop < cpu_count ; loop++ )
538 abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_rapid_popping_and_pushing, ss );
540 for( loop = 0 ; loop < cpu_count ; loop++ )
541 abstraction_thread_wait( thread_handles[loop] );
543 free( thread_handles );
548 lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
550 lfds610_stack_delete( ss, NULL, NULL );
552 // TRD : print the test result
553 internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
562 /****************************************************************************/
563 thread_return_t CALLING_CONVENTION stack_test_internal_thread_rapid_popping_and_pushing( void *stack_state )
565 struct lfds610_stack_state
574 assert( stack_state != NULL );
576 ss = (struct lfds610_stack_state *) stack_state;
578 lfds610_stack_use( ss );
582 while( time(NULL) < start_time + 10 )
584 lfds610_stack_push( ss, user_data );
585 lfds610_stack_pop( ss, &user_data );
588 return( (thread_return_t) EXIT_SUCCESS );