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