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