1 #include "internal.h"
\r
7 /****************************************************************************/
\r
8 void test_lfds601_freelist( void )
\r
12 "==============\n" );
\r
14 freelist_test_internal_popping();
\r
15 freelist_test_internal_pushing();
\r
16 freelist_test_internal_popping_and_pushing();
\r
17 freelist_test_internal_rapid_popping_and_pushing();
\r
26 /****************************************************************************/
\r
27 void freelist_test_internal_popping( void )
\r
37 enum lfds601_data_structure_validity
\r
38 dvs = LFDS601_VALIDITY_VALID;
\r
40 struct lfds601_freelist_state
\r
43 struct lfds601_freelist_element
\r
46 struct freelist_test_popping_state
\r
52 /* TRD : we create a freelist with 1,000,000 elements
\r
54 the creation function runs in a single thread and creates
\r
55 and pushes those elements onto the freelist
\r
57 each element contains a void pointer which is its element number
\r
59 we then run one thread per CPU
\r
60 where each thread loops, popping as quickly as possible
\r
61 each popped element is pushed onto a thread-local freelist
\r
63 the threads run till the source freelist is empty
\r
65 we then check the thread-local freelists
\r
66 we should find we have every element
\r
71 internal_display_test_name( "Popping" );
\r
73 cpu_count = abstraction_cpu_count();
\r
75 lfds601_freelist_new( &fs, 1000000, freelist_test_internal_popping_init, NULL );
\r
76 ftps = malloc( sizeof(struct freelist_test_popping_state) * cpu_count );
\r
77 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
79 (ftps+loop)->fs = fs;
\r
80 lfds601_freelist_new( &(ftps+loop)->fs_thread_local, 0, NULL, NULL );
\r
83 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
85 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
86 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps+loop );
\r
88 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
89 abstraction_thread_wait( thread_handles[loop] );
\r
91 free( thread_handles );
\r
93 // TRD : now we check the thread-local freelists
\r
94 found_count = malloc( sizeof(unsigned int) * 1000000 );
\r
95 for( loop = 0 ; loop < 1000000 ; loop++ )
\r
96 *(found_count+loop) = 0;
\r
98 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
100 while( lfds601_freelist_pop((ftps+loop)->fs_thread_local, &fe) )
\r
102 lfds601_freelist_get_user_data_from_element( fe, (void **) &count );
\r
103 (*(found_count+count))++;
\r
104 lfds601_freelist_push( fs, fe );
\r
108 for( loop = 0 ; loop < 1000000 and dvs == LFDS601_VALIDITY_VALID ; loop++ )
\r
110 if( *(found_count+loop) == 0 )
\r
111 dvs = LFDS601_VALIDITY_INVALID_MISSING_ELEMENTS;
\r
113 if( *(found_count+loop) > 1 )
\r
114 dvs = LFDS601_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
\r
118 free( found_count );
\r
119 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
120 lfds601_freelist_delete( (ftps+loop)->fs_thread_local, NULL, NULL );
\r
121 lfds601_freelist_delete( fs, NULL, NULL );
\r
123 // TRD : print the test result
\r
124 internal_display_test_result( 1, "freelist", dvs );
\r
133 /****************************************************************************/
\r
134 #pragma warning( disable : 4100 )
\r
136 int freelist_test_internal_popping_init( void **user_data, void *user_state )
\r
138 static lfds601_atom_t
\r
141 assert( user_data != NULL );
\r
142 assert( user_state == NULL );
\r
144 *(lfds601_atom_t *) user_data = count++;
\r
149 #pragma warning( default : 4100 )
\r
155 /****************************************************************************/
\r
156 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping( void *freelist_test_popping_state )
\r
158 struct freelist_test_popping_state
\r
161 struct lfds601_freelist_element
\r
164 assert( freelist_test_popping_state != NULL );
\r
166 ftps = (struct freelist_test_popping_state *) freelist_test_popping_state;
\r
168 while( lfds601_freelist_pop(ftps->fs, &fe) )
\r
169 lfds601_freelist_push( ftps->fs_thread_local, fe );
\r
171 return( (thread_return_t) EXIT_SUCCESS );
\r
178 /****************************************************************************/
\r
179 void freelist_test_internal_pushing( void )
\r
188 enum lfds601_data_structure_validity
\r
191 struct freelist_test_pushing_state
\r
194 struct lfds601_freelist_element
\r
197 struct lfds601_freelist_state
\r
201 struct freelist_test_counter_and_thread_number
\r
203 *counter_and_number_trackers;
\r
205 struct lfds601_validation_info
\r
206 vi = { 1000000, 1000000 };
\r
208 /* TRD : we create an empty freelist, which we will push to
\r
210 we then create one freelist per CPU, where this freelist
\r
211 contains 1,000,000/cpu_count number of elements and
\r
212 each element is an incrementing counter and unique ID
\r
213 (from 0 to number of CPUs)
\r
215 we then start one thread per CPU, where each thread is
\r
216 given one of the populated freelists and pops from that
\r
217 to push to the empty freelist
\r
219 the reason for this is to achieve memory pre-allocation
\r
220 which allows the pushing threads to run at maximum speed
\r
222 the threads end when their freelists are empty
\r
224 we then fully pop the now populated main freelist (onto
\r
225 a second freelist, so we can cleanly free all memory),
\r
226 checking that the counts increment on a per unique ID basis
\r
227 and that the number of elements we pop equals 1,000,000
\r
228 (since each element has an incrementing counter which is
\r
229 unique on a per unique ID basis, we can know we didn't lose
\r
233 internal_display_test_name( "Pushing" );
\r
235 cpu_count = abstraction_cpu_count();
\r
237 ftps = malloc( sizeof(struct freelist_test_pushing_state) * cpu_count );
\r
239 lfds601_freelist_new( &fs, 0, NULL, NULL );
\r
241 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
243 (ftps+loop)->thread_number = (lfds601_atom_t) loop;
\r
244 lfds601_freelist_new( &(ftps+loop)->source_fs, 1000000 / cpu_count, freelist_test_internal_pushing_init, (void *) (lfds601_atom_t) loop );
\r
245 (ftps+loop)->fs = fs;
\r
248 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
250 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
251 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps+loop );
\r
253 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
254 abstraction_thread_wait( thread_handles[loop] );
\r
256 free( thread_handles );
\r
258 // TRD : now fully pop and verify the main freelist
\r
259 lfds601_freelist_new( &cleanup_fs, 0, NULL, NULL );
\r
261 counter_and_number_trackers = malloc( sizeof(struct freelist_test_counter_and_thread_number) * cpu_count );
\r
263 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
265 (counter_and_number_trackers+loop)->counter = (1000000 / cpu_count) * loop;
\r
266 (counter_and_number_trackers+loop)->thread_number = (lfds601_atom_t) loop;
\r
269 lfds601_freelist_query( fs, LFDS601_FREELIST_QUERY_VALIDATE, &vi, (void *) &dvs );
\r
271 while( dvs == LFDS601_VALIDITY_VALID and lfds601_freelist_pop(fs, &fe) )
\r
273 static int count = 0;
\r
275 lfds601_freelist_get_user_data_from_element( fe, (void **) &cnt );
\r
277 if( cnt->counter != (counter_and_number_trackers+cnt->thread_number)->counter++ )
\r
278 dvs = LFDS601_VALIDITY_INVALID_MISSING_ELEMENTS;
\r
280 lfds601_freelist_push( cleanup_fs, fe );
\r
286 free( counter_and_number_trackers );
\r
288 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
289 lfds601_freelist_delete( (ftps+loop)->source_fs, NULL, NULL );
\r
293 lfds601_freelist_delete( cleanup_fs, freelist_test_internal_pushing_delete, NULL );
\r
294 lfds601_freelist_delete( fs, NULL, NULL );
\r
296 // TRD : print the test result
\r
297 internal_display_test_result( 1, "freelist", dvs );
\r
306 /****************************************************************************/
\r
307 int freelist_test_internal_pushing_init( void **user_data, void *user_state )
\r
309 struct freelist_test_counter_and_thread_number
\r
312 static lfds601_atom_t
\r
315 assert( user_data != NULL );
\r
316 // TRD : user_state is being used as an integer type
\r
318 *user_data = malloc( sizeof(struct freelist_test_counter_and_thread_number) );
\r
320 ftcatn = (struct freelist_test_counter_and_thread_number *) *user_data;
\r
322 ftcatn->counter = counter++;
\r
323 ftcatn->thread_number = (lfds601_atom_t) user_state;
\r
332 /****************************************************************************/
\r
333 #pragma warning( disable : 4100 )
\r
335 void freelist_test_internal_pushing_delete( void *user_data, void *user_state )
\r
337 assert( user_data != NULL );
\r
338 assert( user_state == NULL );
\r
345 #pragma warning( default : 4100 )
\r
351 /****************************************************************************/
\r
352 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_pushing( void *freelist_test_pushing_state )
\r
354 struct freelist_test_pushing_state
\r
357 struct lfds601_freelist_element
\r
360 assert( freelist_test_pushing_state != NULL );
\r
362 ftps = (struct freelist_test_pushing_state *) freelist_test_pushing_state;
\r
364 while( lfds601_freelist_pop(ftps->source_fs, &fe) )
\r
365 lfds601_freelist_push( ftps->fs, fe );
\r
367 return( (thread_return_t) EXIT_SUCCESS );
\r
374 /****************************************************************************/
\r
375 void freelist_test_internal_popping_and_pushing( void )
\r
384 enum lfds601_data_structure_validity
\r
387 struct lfds601_freelist_state
\r
390 struct freelist_test_popping_and_pushing_state
\r
393 struct lfds601_validation_info
\r
396 /* TRD : we have two threads per CPU
\r
397 the threads loop for ten seconds
\r
398 the first thread pushes 100000 elements then pops 100000 elements
\r
399 the second thread pops 100000 elements then pushes 100000 elements
\r
400 all pushes and pops go onto the single main freelist
\r
402 after time is up, all threads push what they have remaining onto
\r
405 we then validate the main freelist
\r
408 internal_display_test_name( "Popping and pushing (10 seconds)" );
\r
410 cpu_count = abstraction_cpu_count();
\r
412 lfds601_freelist_new( &fs, 100000 * cpu_count, NULL, NULL );
\r
414 pps = malloc( sizeof(struct freelist_test_popping_and_pushing_state) * cpu_count * 2 );
\r
416 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
418 (pps+loop)->fs = fs;
\r
419 lfds601_freelist_new( &(pps+loop)->local_fs, 0, NULL, NULL );
\r
421 (pps+loop+cpu_count)->fs = fs;
\r
422 lfds601_freelist_new( &(pps+loop+cpu_count)->local_fs, 100000, NULL, NULL );
\r
425 thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
\r
427 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
429 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping_and_pushing_start_popping, pps+loop );
\r
430 abstraction_thread_start( &thread_handles[loop+cpu_count], loop, freelist_test_internal_thread_popping_and_pushing_start_pushing, pps+loop+cpu_count );
\r
433 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
\r
434 abstraction_thread_wait( thread_handles[loop] );
\r
436 free( thread_handles );
\r
438 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
\r
439 lfds601_freelist_delete( (pps+loop)->local_fs, NULL, NULL );
\r
443 vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
\r
445 lfds601_freelist_query( fs, LFDS601_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
\r
447 lfds601_freelist_delete( fs, NULL, NULL );
\r
449 // TRD : print the test result
\r
450 internal_display_test_result( 1, "freelist", dvs );
\r
460 /****************************************************************************/
\r
461 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_popping( void *freelist_test_popping_and_pushing_state )
\r
463 struct freelist_test_popping_and_pushing_state
\r
466 struct lfds601_freelist_element
\r
475 assert( freelist_test_popping_and_pushing_state != NULL );
\r
477 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
\r
479 time( &start_time );
\r
481 while( time(NULL) < start_time + 10 )
\r
485 while( count < 100000 )
\r
487 lfds601_freelist_pop( pps->fs, &fe );
\r
491 lfds601_freelist_push( pps->local_fs, fe );
\r
496 while( lfds601_freelist_pop(pps->local_fs, &fe) )
\r
497 lfds601_freelist_push( pps->fs, fe );
\r
500 return( (thread_return_t) EXIT_SUCCESS );
\r
507 /****************************************************************************/
\r
508 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_pushing( void *freelist_test_popping_and_pushing_state )
\r
510 struct freelist_test_popping_and_pushing_state
\r
513 struct lfds601_freelist_element
\r
522 assert( freelist_test_popping_and_pushing_state != NULL );
\r
524 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
\r
526 time( &start_time );
\r
528 while( time(NULL) < start_time + 10 )
\r
530 while( lfds601_freelist_pop(pps->local_fs, &fe) )
\r
531 lfds601_freelist_push( pps->fs, fe );
\r
535 while( count < 1000 )
\r
537 lfds601_freelist_pop( pps->fs, &fe );
\r
541 lfds601_freelist_push( pps->local_fs, fe );
\r
547 // TRD : now push whatever we have in our local freelist
\r
548 while( lfds601_freelist_pop(pps->local_fs, &fe) )
\r
549 lfds601_freelist_push( pps->fs, fe );
\r
551 return( (thread_return_t) EXIT_SUCCESS );
\r
558 /****************************************************************************/
\r
559 void freelist_test_internal_rapid_popping_and_pushing( void )
\r
568 struct lfds601_freelist_state
\r
571 struct lfds601_validation_info
\r
574 enum lfds601_data_structure_validity
\r
577 /* TRD : in these tests there is a fundamental antagonism between
\r
578 how much checking/memory clean up that we do and the
\r
579 likelyhood of collisions between threads in their lock-free
\r
582 the lock-free operations are very quick; if we do anything
\r
583 much at all between operations, we greatly reduce the chance
\r
584 of threads colliding
\r
586 so we have some tests which do enough checking/clean up that
\r
587 they can tell the freelist is valid and don't leak memory
\r
588 and here, this test now is one of those which does minimal
\r
589 checking - in fact, the nature of the test is that you can't
\r
590 do any real checking - but goes very quickly
\r
592 what we do is create a small freelist and then run one thread
\r
593 per CPU, where each thread simply pops and then immediately
\r
596 the test runs for ten seconds
\r
598 after the test is done, the only check we do is to traverse
\r
599 the freelist, checking for loops and ensuring the number of
\r
600 elements is correct
\r
603 internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
\r
605 cpu_count = abstraction_cpu_count();
\r
607 lfds601_freelist_new( &fs, cpu_count, NULL, NULL );
\r
609 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
611 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
612 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_rapid_popping_and_pushing, fs );
\r
614 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
615 abstraction_thread_wait( thread_handles[loop] );
\r
617 free( thread_handles );
\r
619 vi.min_elements = cpu_count;
\r
620 vi.max_elements = cpu_count;
\r
622 lfds601_freelist_query( fs, LFDS601_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
\r
624 lfds601_freelist_delete( fs, NULL, NULL );
\r
626 // TRD : print the test result
\r
627 internal_display_test_result( 1, "freelist", dvs );
\r
636 /****************************************************************************/
\r
637 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing( void *lfds601_freelist_state )
\r
639 struct lfds601_freelist_state
\r
642 struct lfds601_freelist_element
\r
648 assert( lfds601_freelist_state != NULL );
\r
650 fs = (struct lfds601_freelist_state *) lfds601_freelist_state;
\r
652 time( &start_time );
\r
654 while( time(NULL) < start_time + 10 )
\r
656 lfds601_freelist_pop( fs, &fe );
\r
657 lfds601_freelist_push( fs, fe );
\r
660 return( (thread_return_t) EXIT_SUCCESS );
\r