1 #include "internal.h"
\r
7 /****************************************************************************/
\r
8 void test_lfds611_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
39 enum lfds611_data_structure_validity
\r
40 dvs = LFDS611_VALIDITY_VALID;
\r
42 struct lfds611_freelist_state
\r
45 struct lfds611_freelist_element
\r
48 struct freelist_test_popping_state
\r
54 /* TRD : we create a freelist with 1,000,000 elements
\r
56 the creation function runs in a single thread and creates
\r
57 and pushes those elements onto the freelist
\r
59 each element contains a void pointer which is its element number
\r
61 we then run one thread per CPU
\r
62 where each thread loops, popping as quickly as possible
\r
63 each popped element is pushed onto a thread-local freelist
\r
65 the threads run till the source freelist is empty
\r
67 we then check the thread-local freelists
\r
68 we should find we have every element
\r
73 internal_display_test_name( "Popping" );
\r
75 cpu_count = abstraction_cpu_count();
\r
77 lfds611_freelist_new( &fs, 1000000, freelist_test_internal_popping_init, &count );
\r
78 ftps = malloc( sizeof(struct freelist_test_popping_state) * cpu_count );
\r
79 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
81 (ftps+loop)->fs = fs;
\r
82 lfds611_freelist_new( &(ftps+loop)->fs_thread_local, 0, NULL, NULL );
\r
85 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
87 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
88 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps+loop );
\r
90 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
91 abstraction_thread_wait( thread_handles[loop] );
\r
93 free( thread_handles );
\r
95 // TRD : now we check the thread-local freelists
\r
96 found_count = malloc( sizeof(unsigned int) * 1000000 );
\r
97 for( loop = 0 ; loop < 1000000 ; loop++ )
\r
98 *(found_count+loop) = 0;
\r
100 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
102 while( lfds611_freelist_pop((ftps+loop)->fs_thread_local, &fe) )
\r
104 lfds611_freelist_get_user_data_from_element( fe, (void **) &count );
\r
105 (*(found_count+count))++;
\r
106 lfds611_freelist_push( fs, fe );
\r
110 for( loop = 0 ; loop < 1000000 and dvs == LFDS611_VALIDITY_VALID ; loop++ )
\r
112 if( *(found_count+loop) == 0 )
\r
113 dvs = LFDS611_VALIDITY_INVALID_MISSING_ELEMENTS;
\r
115 if( *(found_count+loop) > 1 )
\r
116 dvs = LFDS611_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
\r
120 free( found_count );
\r
121 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
122 lfds611_freelist_delete( (ftps+loop)->fs_thread_local, NULL, NULL );
\r
124 lfds611_freelist_delete( fs, NULL, NULL );
\r
126 // TRD : print the test result
\r
127 internal_display_test_result( 1, "freelist", dvs );
\r
136 /****************************************************************************/
\r
137 #pragma warning( disable : 4100 )
\r
139 int freelist_test_internal_popping_init( void **user_data, void *user_state )
\r
144 assert( user_data != NULL );
\r
145 assert( user_state != NULL );
\r
147 count = (lfds611_atom_t *) user_state;
\r
149 *(lfds611_atom_t *) user_data = (*count)++;
\r
154 #pragma warning( default : 4100 )
\r
160 /****************************************************************************/
\r
161 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping( void *freelist_test_popping_state )
\r
163 struct freelist_test_popping_state
\r
166 struct lfds611_freelist_element
\r
169 assert( freelist_test_popping_state != NULL );
\r
171 ftps = (struct freelist_test_popping_state *) freelist_test_popping_state;
\r
173 lfds611_freelist_use( ftps->fs );
\r
174 lfds611_freelist_use( ftps->fs_thread_local );
\r
176 while( lfds611_freelist_pop(ftps->fs, &fe) )
\r
177 lfds611_freelist_push( ftps->fs_thread_local, fe );
\r
179 return( (thread_return_t) EXIT_SUCCESS );
\r
186 /****************************************************************************/
\r
187 void freelist_test_internal_pushing( void )
\r
199 enum lfds611_data_structure_validity
\r
202 struct freelist_test_pushing_state
\r
205 struct lfds611_freelist_element
\r
208 struct lfds611_freelist_state
\r
212 struct freelist_test_counter_and_thread_number
\r
214 *counter_and_number_trackers;
\r
216 struct lfds611_validation_info
\r
219 /* TRD : we create an empty freelist, which we will push to
\r
221 we then create one freelist per CPU, where this freelist
\r
222 contains 100,000 elements per thread and
\r
223 each element is an incrementing counter and unique ID
\r
224 (from 0 to number of CPUs)
\r
226 we then start one thread per CPU, where each thread is
\r
227 given one of the populated freelists and pops from that
\r
228 to push to the empty freelist
\r
230 the reason for this is to achieve memory pre-allocation
\r
231 which allows the pushing threads to run at maximum speed
\r
233 the threads end when their freelists are empty
\r
235 we then fully pop the now populated main freelist (onto
\r
236 a second freelist, so we can cleanly free all memory),
\r
237 checking that the counts increment on a per unique ID basis
\r
238 and that the number of elements we pop equals 1,000,000 per thread
\r
239 (since each element has an incrementing counter which is
\r
240 unique on a per unique ID basis, we can know we didn't lose
\r
244 internal_display_test_name( "Pushing" );
\r
246 cpu_count = abstraction_cpu_count();
\r
248 ftps = malloc( sizeof(struct freelist_test_pushing_state) * cpu_count );
\r
250 lfds611_freelist_new( &fs, 0, NULL, NULL );
\r
252 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
254 (ftps+loop)->thread_number = (lfds611_atom_t) loop;
\r
255 // TRD : note count is shared across threads, so thread 0 is 0-100000, thread 1 is 100000-200000, etc
\r
256 (ftps+loop)->count = &count;
\r
257 lfds611_freelist_new( &(ftps+loop)->source_fs, 100000, freelist_test_internal_pushing_init, (void *) (ftps+loop) );
\r
258 (ftps+loop)->fs = fs;
\r
261 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
263 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
264 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps+loop );
\r
266 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
267 abstraction_thread_wait( thread_handles[loop] );
\r
269 free( thread_handles );
\r
271 // TRD : now fully pop and verify the main freelist
\r
272 lfds611_freelist_new( &cleanup_fs, 0, NULL, NULL );
\r
274 counter_and_number_trackers = malloc( sizeof(struct freelist_test_counter_and_thread_number) * cpu_count );
\r
276 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
278 (counter_and_number_trackers+loop)->counter = 100000 * loop;
\r
279 (counter_and_number_trackers+loop)->thread_number = (lfds611_atom_t) loop;
\r
282 vi.min_elements = vi.max_elements = 100000 * cpu_count;
\r
284 lfds611_freelist_query( fs, LFDS611_FREELIST_QUERY_VALIDATE, &vi, (void *) &dvs );
\r
286 while( dvs == LFDS611_VALIDITY_VALID and lfds611_freelist_pop(fs, &fe) )
\r
288 lfds611_freelist_get_user_data_from_element( fe, (void **) &cnt );
\r
290 if( cnt->counter != (counter_and_number_trackers+cnt->thread_number)->counter++ )
\r
291 dvs = LFDS611_VALIDITY_INVALID_MISSING_ELEMENTS;
\r
293 lfds611_freelist_push( cleanup_fs, fe );
\r
297 free( counter_and_number_trackers );
\r
299 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
300 lfds611_freelist_delete( (ftps+loop)->source_fs, NULL, NULL );
\r
304 lfds611_freelist_delete( cleanup_fs, freelist_test_internal_pushing_delete, NULL );
\r
305 lfds611_freelist_delete( fs, NULL, NULL );
\r
307 // TRD : print the test result
\r
308 internal_display_test_result( 1, "freelist", dvs );
\r
317 /****************************************************************************/
\r
318 int freelist_test_internal_pushing_init( void **user_data, void *user_state )
\r
320 struct freelist_test_counter_and_thread_number
\r
323 struct freelist_test_pushing_state
\r
326 assert( user_data != NULL );
\r
327 // TRD : user_state is being used as an integer type
\r
329 *user_data = malloc( sizeof(struct freelist_test_counter_and_thread_number) );
\r
330 ftps = (struct freelist_test_pushing_state *) user_state;
\r
332 ftcatn = (struct freelist_test_counter_and_thread_number *) *user_data;
\r
334 ftcatn->counter = (*ftps->count)++;
\r
335 ftcatn->thread_number = ftps->thread_number;
\r
344 /****************************************************************************/
\r
345 #pragma warning( disable : 4100 )
\r
347 void freelist_test_internal_pushing_delete( void *user_data, void *user_state )
\r
349 assert( user_data != NULL );
\r
350 assert( user_state == NULL );
\r
357 #pragma warning( default : 4100 )
\r
363 /****************************************************************************/
\r
364 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_pushing( void *freelist_test_pushing_state )
\r
366 struct freelist_test_pushing_state
\r
369 struct lfds611_freelist_element
\r
372 assert( freelist_test_pushing_state != NULL );
\r
374 ftps = (struct freelist_test_pushing_state *) freelist_test_pushing_state;
\r
376 lfds611_freelist_use( ftps->source_fs );
\r
377 lfds611_freelist_use( ftps->fs );
\r
379 while( lfds611_freelist_pop(ftps->source_fs, &fe) )
\r
380 lfds611_freelist_push( ftps->fs, fe );
\r
382 return( (thread_return_t) EXIT_SUCCESS );
\r
389 /****************************************************************************/
\r
390 void freelist_test_internal_popping_and_pushing( void )
\r
399 enum lfds611_data_structure_validity
\r
402 struct lfds611_freelist_state
\r
405 struct freelist_test_popping_and_pushing_state
\r
408 struct lfds611_validation_info
\r
411 /* TRD : we have two threads per CPU
\r
412 the threads loop for ten seconds
\r
413 the first thread pushes 100000 elements then pops 100000 elements
\r
414 the second thread pops 100000 elements then pushes 100000 elements
\r
415 all pushes and pops go onto the single main freelist
\r
417 after time is up, all threads push what they have remaining onto
\r
420 we then validate the main freelist
\r
423 internal_display_test_name( "Popping and pushing (10 seconds)" );
\r
425 cpu_count = abstraction_cpu_count();
\r
427 lfds611_freelist_new( &fs, 100000 * cpu_count, NULL, NULL );
\r
429 pps = malloc( sizeof(struct freelist_test_popping_and_pushing_state) * cpu_count * 2 );
\r
431 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
433 (pps+loop)->fs = fs;
\r
434 lfds611_freelist_new( &(pps+loop)->local_fs, 0, NULL, NULL );
\r
436 (pps+loop+cpu_count)->fs = fs;
\r
437 lfds611_freelist_new( &(pps+loop+cpu_count)->local_fs, 100000, NULL, NULL );
\r
440 thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
\r
442 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
444 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping_and_pushing_start_popping, pps+loop );
\r
445 abstraction_thread_start( &thread_handles[loop+cpu_count], loop, freelist_test_internal_thread_popping_and_pushing_start_pushing, pps+loop+cpu_count );
\r
448 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
\r
449 abstraction_thread_wait( thread_handles[loop] );
\r
451 free( thread_handles );
\r
453 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
\r
454 lfds611_freelist_delete( (pps+loop)->local_fs, NULL, NULL );
\r
458 vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
\r
460 lfds611_freelist_query( fs, LFDS611_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
\r
462 lfds611_freelist_delete( fs, NULL, NULL );
\r
464 // TRD : print the test result
\r
465 internal_display_test_result( 1, "freelist", dvs );
\r
475 /****************************************************************************/
\r
476 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_popping( void *freelist_test_popping_and_pushing_state )
\r
478 struct freelist_test_popping_and_pushing_state
\r
481 struct lfds611_freelist_element
\r
490 assert( freelist_test_popping_and_pushing_state != NULL );
\r
492 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
\r
494 lfds611_freelist_use( pps->fs );
\r
495 lfds611_freelist_use( pps->local_fs );
\r
497 time( &start_time );
\r
499 while( time(NULL) < start_time + 10 )
\r
503 while( count < 100000 )
\r
505 lfds611_freelist_pop( pps->fs, &fe );
\r
509 lfds611_freelist_push( pps->local_fs, fe );
\r
514 while( lfds611_freelist_pop(pps->local_fs, &fe) )
\r
515 lfds611_freelist_push( pps->fs, fe );
\r
518 return( (thread_return_t) EXIT_SUCCESS );
\r
525 /****************************************************************************/
\r
526 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_pushing( void *freelist_test_popping_and_pushing_state )
\r
528 struct freelist_test_popping_and_pushing_state
\r
531 struct lfds611_freelist_element
\r
540 assert( freelist_test_popping_and_pushing_state != NULL );
\r
542 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
\r
544 lfds611_freelist_use( pps->fs );
\r
545 lfds611_freelist_use( pps->local_fs );
\r
547 time( &start_time );
\r
549 while( time(NULL) < start_time + 10 )
\r
551 while( lfds611_freelist_pop(pps->local_fs, &fe) )
\r
552 lfds611_freelist_push( pps->fs, fe );
\r
556 while( count < 1000 )
\r
558 lfds611_freelist_pop( pps->fs, &fe );
\r
562 lfds611_freelist_push( pps->local_fs, fe );
\r
568 // TRD : now push whatever we have in our local freelist
\r
569 while( lfds611_freelist_pop(pps->local_fs, &fe) )
\r
570 lfds611_freelist_push( pps->fs, fe );
\r
572 return( (thread_return_t) EXIT_SUCCESS );
\r
579 /****************************************************************************/
\r
580 void freelist_test_internal_rapid_popping_and_pushing( void )
\r
589 struct lfds611_freelist_state
\r
592 struct lfds611_validation_info
\r
595 enum lfds611_data_structure_validity
\r
598 /* TRD : in these tests there is a fundamental antagonism between
\r
599 how much checking/memory clean up that we do and the
\r
600 likelyhood of collisions between threads in their lock-free
\r
603 the lock-free operations are very quick; if we do anything
\r
604 much at all between operations, we greatly reduce the chance
\r
605 of threads colliding
\r
607 so we have some tests which do enough checking/clean up that
\r
608 they can tell the freelist is valid and don't leak memory
\r
609 and here, this test now is one of those which does minimal
\r
610 checking - in fact, the nature of the test is that you can't
\r
611 do any real checking - but goes very quickly
\r
613 what we do is create a small freelist and then run one thread
\r
614 per CPU, where each thread simply pops and then immediately
\r
617 the test runs for ten seconds
\r
619 after the test is done, the only check we do is to traverse
\r
620 the freelist, checking for loops and ensuring the number of
\r
621 elements is correct
\r
624 internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
\r
626 cpu_count = abstraction_cpu_count();
\r
628 lfds611_freelist_new( &fs, cpu_count, NULL, NULL );
\r
630 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
\r
632 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
633 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_rapid_popping_and_pushing, fs );
\r
635 for( loop = 0 ; loop < cpu_count ; loop++ )
\r
636 abstraction_thread_wait( thread_handles[loop] );
\r
638 free( thread_handles );
\r
640 vi.min_elements = cpu_count;
\r
641 vi.max_elements = cpu_count;
\r
643 lfds611_freelist_query( fs, LFDS611_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
\r
645 lfds611_freelist_delete( fs, NULL, NULL );
\r
647 // TRD : print the test result
\r
648 internal_display_test_result( 1, "freelist", dvs );
\r
657 /****************************************************************************/
\r
658 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing( void *lfds611_freelist_state )
\r
660 struct lfds611_freelist_state
\r
663 struct lfds611_freelist_element
\r
669 assert( lfds611_freelist_state != NULL );
\r
671 fs = (struct lfds611_freelist_state *) lfds611_freelist_state;
\r
673 lfds611_freelist_use( fs );
\r
675 time( &start_time );
\r
677 while( time(NULL) < start_time + 10 )
\r
679 lfds611_freelist_pop( fs, &fe );
\r
680 lfds611_freelist_push( fs, fe );
\r
683 return( (thread_return_t) EXIT_SUCCESS );
\r