win-pvdrivers

view liblfds.6/test/src/test_freelist.c @ 1025:aa2e51f67f7c

Fix hibernate under Win8. Change debugprints.
author James Harper <james.harper@bendigoit.com.au>
date Tue Feb 19 15:14:53 2013 +1100 (2013-02-19)
parents 6300617040e0
children
line source
1 #include "internal.h"
7 /****************************************************************************/
8 void test_freelist( void )
9 {
10 printf( "\n"
11 "Freelist Tests\n"
12 "==============\n" );
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();
19 return;
20 }
26 /****************************************************************************/
27 void freelist_test_internal_popping( void )
28 {
29 unsigned int
30 loop,
31 cpu_count,
32 count;
34 thread_state_t
35 *thread_handles;
37 enum data_structure_validity
38 dvs = VALIDITY_VALID;
40 struct freelist_state
41 *fs;
43 struct freelist_element
44 *fe;
46 struct freelist_test_popping_state
47 *ftps;
49 unsigned int
50 *found_count;
52 /* TRD : we create a freelist with 1,000,000 elements
54 the creation function runs in a single thread and creates
55 and pushes those elements onto the freelist
57 each element contains a void pointer which is its element number
59 we then run one thread per CPU
60 where each thread loops, popping as quickly as possible
61 each popped element is pushed onto a thread-local freelist
63 the threads run till the source freelist is empty
65 we then check the thread-local freelists
66 we should find we have every element
68 then tidy up
69 */
71 internal_display_test_name( "Popping" );
73 cpu_count = abstraction_cpu_count();
75 freelist_new( &fs, 1000000, freelist_test_internal_popping_init, NULL );
76 ftps = malloc( sizeof(struct freelist_test_popping_state) * cpu_count );
77 for( loop = 0 ; loop < cpu_count ; loop++ )
78 {
79 (ftps+loop)->fs = fs;
80 freelist_new( &(ftps+loop)->fs_thread_local, 0, NULL, NULL );
81 }
83 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
85 for( loop = 0 ; loop < cpu_count ; loop++ )
86 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps+loop );
88 for( loop = 0 ; loop < cpu_count ; loop++ )
89 abstraction_thread_wait( thread_handles[loop] );
91 free( thread_handles );
93 // TRD : now we check the thread-local freelists
94 found_count = malloc( sizeof(unsigned int) * 1000000 );
95 for( loop = 0 ; loop < 1000000 ; loop++ )
96 *(found_count+loop) = 0;
98 for( loop = 0 ; loop < cpu_count ; loop++ )
99 {
100 while( freelist_pop((ftps+loop)->fs_thread_local, &fe) )
101 {
102 freelist_get_user_data_from_element( fe, (void **) &count );
103 (*(found_count+count))++;
104 freelist_push( fs, fe );
105 }
106 }
108 for( loop = 0 ; loop < 1000000 and dvs == VALIDITY_VALID ; loop++ )
109 {
110 if( *(found_count+loop) == 0 )
111 dvs = VALIDITY_INVALID_MISSING_ELEMENTS;
113 if( *(found_count+loop) > 1 )
114 dvs = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
115 }
117 // TRD : cleanup
118 free( found_count );
119 for( loop = 0 ; loop < cpu_count ; loop++ )
120 freelist_delete( (ftps+loop)->fs_thread_local, NULL, NULL );
121 freelist_delete( fs, NULL, NULL );
123 // TRD : print the test result
124 internal_display_test_result( 1, "freelist", dvs );
126 return;
127 }
133 /****************************************************************************/
134 #pragma warning( disable : 4100 )
136 int freelist_test_internal_popping_init( void **user_data, void *user_state )
137 {
138 static atom_t
139 count = 0;
141 assert( user_data != NULL );
142 assert( user_state == NULL );
144 *(atom_t *) user_data = count++;
146 return( 1 );
147 }
149 #pragma warning( default : 4100 )
155 /****************************************************************************/
156 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping( void *freelist_test_popping_state )
157 {
158 struct freelist_test_popping_state
159 *ftps;
161 struct freelist_element
162 *fe;
164 assert( freelist_test_popping_state != NULL );
166 ftps = (struct freelist_test_popping_state *) freelist_test_popping_state;
168 while( freelist_pop(ftps->fs, &fe) )
169 freelist_push( ftps->fs_thread_local, fe );
171 return( (thread_return_t) EXIT_SUCCESS );
172 }
178 /****************************************************************************/
179 void freelist_test_internal_pushing( void )
180 {
181 unsigned int
182 loop,
183 cpu_count;
185 thread_state_t
186 *thread_handles;
188 enum data_structure_validity
189 dvs;
191 struct freelist_test_pushing_state
192 *ftps;
194 struct freelist_element
195 *fe;
197 struct freelist_state
198 *fs,
199 *cleanup_fs;
201 struct freelist_test_counter_and_thread_number
202 *cnt,
203 *counter_and_number_trackers;
205 struct validation_info
206 vi = { 1000000, 1000000 };
208 /* TRD : we create an empty freelist, which we will push to
210 we then create one freelist per CPU, where this freelist
211 contains 1,000,000/cpu_count number of elements and
212 each element is an incrementing counter and unique ID
213 (from 0 to number of CPUs)
215 we then start one thread per CPU, where each thread is
216 given one of the populated freelists and pops from that
217 to push to the empty freelist
219 the reason for this is to achieve memory pre-allocation
220 which allows the pushing threads to run at maximum speed
222 the threads end when their freelists are empty
224 we then fully pop the now populated main freelist (onto
225 a second freelist, so we can cleanly free all memory),
226 checking that the counts increment on a per unique ID basis
227 and that the number of elements we pop equals 1,000,000
228 (since each element has an incrementing counter which is
229 unique on a per unique ID basis, we can know we didn't lose
230 any elements)
231 */
233 internal_display_test_name( "Pushing" );
235 cpu_count = abstraction_cpu_count();
237 ftps = malloc( sizeof(struct freelist_test_pushing_state) * cpu_count );
239 freelist_new( &fs, 0, NULL, NULL );
241 for( loop = 0 ; loop < cpu_count ; loop++ )
242 {
243 (ftps+loop)->thread_number = (atom_t) loop;
244 freelist_new( &(ftps+loop)->source_fs, 1000000 / cpu_count, freelist_test_internal_pushing_init, (void *) (atom_t) loop );
245 (ftps+loop)->fs = fs;
246 }
248 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
250 for( loop = 0 ; loop < cpu_count ; loop++ )
251 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps+loop );
253 for( loop = 0 ; loop < cpu_count ; loop++ )
254 abstraction_thread_wait( thread_handles[loop] );
256 free( thread_handles );
258 // TRD : now fully pop and verify the main freelist
259 freelist_new( &cleanup_fs, 0, NULL, NULL );
261 counter_and_number_trackers = malloc( sizeof(struct freelist_test_counter_and_thread_number) * cpu_count );
263 for( loop = 0 ; loop < cpu_count ; loop++ )
264 {
265 (counter_and_number_trackers+loop)->counter = (1000000 / cpu_count) * loop;
266 (counter_and_number_trackers+loop)->thread_number = (atom_t) loop;
267 }
269 freelist_query( fs, FREELIST_QUERY_VALIDATE, &vi, (void *) &dvs );
271 while( dvs == VALIDITY_VALID and freelist_pop(fs, &fe) )
272 {
273 static int count = 0;
275 freelist_get_user_data_from_element( fe, (void **) &cnt );
277 if( cnt->counter != (counter_and_number_trackers+cnt->thread_number)->counter++ )
278 dvs = VALIDITY_INVALID_MISSING_ELEMENTS;
280 freelist_push( cleanup_fs, fe );
282 count++;
283 }
285 // TRD : clean up
286 free( counter_and_number_trackers );
288 for( loop = 0 ; loop < cpu_count ; loop++ )
289 freelist_delete( (ftps+loop)->source_fs, NULL, NULL );
291 free( ftps );
293 freelist_delete( cleanup_fs, freelist_test_internal_pushing_delete, NULL );
294 freelist_delete( fs, NULL, NULL );
296 // TRD : print the test result
297 internal_display_test_result( 1, "freelist", dvs );
299 return;
300 }
306 /****************************************************************************/
307 int freelist_test_internal_pushing_init( void **user_data, void *user_state )
308 {
309 struct freelist_test_counter_and_thread_number
310 *ftcatn;
312 static atom_t
313 counter = 0;
315 assert( user_data != NULL );
316 // TRD : user_state is being used as an integer type
318 *user_data = malloc( sizeof(struct freelist_test_counter_and_thread_number) );
320 ftcatn = (struct freelist_test_counter_and_thread_number *) *user_data;
322 ftcatn->counter = counter++;
323 ftcatn->thread_number = (atom_t) user_state;
325 return( 1 );
326 }
332 /****************************************************************************/
333 #pragma warning( disable : 4100 )
335 void freelist_test_internal_pushing_delete( void *user_data, void *user_state )
336 {
337 assert( user_data != NULL );
338 assert( user_state == NULL );
340 free( user_data );
342 return;
343 }
345 #pragma warning( default : 4100 )
351 /****************************************************************************/
352 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_pushing( void *freelist_test_pushing_state )
353 {
354 struct freelist_test_pushing_state
355 *ftps;
357 struct freelist_element
358 *fe;
360 assert( freelist_test_pushing_state != NULL );
362 ftps = (struct freelist_test_pushing_state *) freelist_test_pushing_state;
364 while( freelist_pop(ftps->source_fs, &fe) )
365 freelist_push( ftps->fs, fe );
367 return( (thread_return_t) EXIT_SUCCESS );
368 }
374 /****************************************************************************/
375 void freelist_test_internal_popping_and_pushing( void )
376 {
377 unsigned int
378 loop,
379 cpu_count;
381 thread_state_t
382 *thread_handles;
384 enum data_structure_validity
385 dvs;
387 struct freelist_state
388 *fs;
390 struct freelist_test_popping_and_pushing_state
391 *pps;
393 struct validation_info
394 vi;
396 /* TRD : we have two threads per CPU
397 the threads loop for ten seconds
398 the first thread pushes 100000 elements then pops 100000 elements
399 the second thread pops 100000 elements then pushes 100000 elements
400 all pushes and pops go onto the single main freelist
402 after time is up, all threads push what they have remaining onto
403 the main freelist
405 we then validate the main freelist
406 */
408 internal_display_test_name( "Popping and pushing (10 seconds)" );
410 cpu_count = abstraction_cpu_count();
412 freelist_new( &fs, 100000 * cpu_count, NULL, NULL );
414 pps = malloc( sizeof(struct freelist_test_popping_and_pushing_state) * cpu_count * 2 );
416 for( loop = 0 ; loop < cpu_count ; loop++ )
417 {
418 (pps+loop)->fs = fs;
419 freelist_new( &(pps+loop)->local_fs, 0, NULL, NULL );
421 (pps+loop+cpu_count)->fs = fs;
422 freelist_new( &(pps+loop+cpu_count)->local_fs, 100000, NULL, NULL );
423 }
425 thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
427 for( loop = 0 ; loop < cpu_count ; loop++ )
428 {
429 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping_and_pushing_start_popping, pps+loop );
430 abstraction_thread_start( &thread_handles[loop+cpu_count], loop, freelist_test_internal_thread_popping_and_pushing_start_pushing, pps+loop+cpu_count );
431 }
433 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
434 abstraction_thread_wait( thread_handles[loop] );
436 free( thread_handles );
438 for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
439 freelist_delete( (pps+loop)->local_fs, NULL, NULL );
441 free( pps );
443 vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
445 freelist_query( fs, FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
447 freelist_delete( fs, NULL, NULL );
449 // TRD : print the test result
450 internal_display_test_result( 1, "freelist", dvs );
452 return;
453 }
460 /****************************************************************************/
461 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_popping( void *freelist_test_popping_and_pushing_state )
462 {
463 struct freelist_test_popping_and_pushing_state
464 *pps;
466 struct freelist_element
467 *fe;
469 time_t
470 start_time;
472 unsigned int
473 count;
475 assert( freelist_test_popping_and_pushing_state != NULL );
477 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
479 time( &start_time );
481 while( time(NULL) < start_time + 10 )
482 {
483 count = 0;
485 while( count < 100000 )
486 {
487 freelist_pop( pps->fs, &fe );
489 if( fe != NULL )
490 {
491 freelist_push( pps->local_fs, fe );
492 count++;
493 }
494 }
496 while( freelist_pop(pps->local_fs, &fe) )
497 freelist_push( pps->fs, fe );
498 }
500 return( (thread_return_t) EXIT_SUCCESS );
501 }
507 /****************************************************************************/
508 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_pushing( void *freelist_test_popping_and_pushing_state )
509 {
510 struct freelist_test_popping_and_pushing_state
511 *pps;
513 struct freelist_element
514 *fe;
516 time_t
517 start_time;
519 unsigned int
520 count;
522 assert( freelist_test_popping_and_pushing_state != NULL );
524 pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
526 time( &start_time );
528 while( time(NULL) < start_time + 10 )
529 {
530 while( freelist_pop(pps->local_fs, &fe) )
531 freelist_push( pps->fs, fe );
533 count = 0;
535 while( count < 1000 )
536 {
537 freelist_pop( pps->fs, &fe );
539 if( fe != NULL )
540 {
541 freelist_push( pps->local_fs, fe );
542 count++;
543 }
544 }
545 }
547 // TRD : now push whatever we have in our local freelist
548 while( freelist_pop(pps->local_fs, &fe) )
549 freelist_push( pps->fs, fe );
551 return( (thread_return_t) EXIT_SUCCESS );
552 }
558 /****************************************************************************/
559 void freelist_test_internal_rapid_popping_and_pushing( void )
560 {
561 unsigned int
562 loop,
563 cpu_count;
565 thread_state_t
566 *thread_handles;
568 struct freelist_state
569 *fs;
571 struct validation_info
572 vi;
574 enum data_structure_validity
575 dvs;
577 /* TRD : in these tests there is a fundamental antagonism between
578 how much checking/memory clean up that we do and the
579 likelyhood of collisions between threads in their lock-free
580 operations
582 the lock-free operations are very quick; if we do anything
583 much at all between operations, we greatly reduce the chance
584 of threads colliding
586 so we have some tests which do enough checking/clean up that
587 they can tell the freelist is valid and don't leak memory
588 and here, this test now is one of those which does minimal
589 checking - in fact, the nature of the test is that you can't
590 do any real checking - but goes very quickly
592 what we do is create a small freelist and then run one thread
593 per CPU, where each thread simply pops and then immediately
594 pushes
596 the test runs for ten seconds
598 after the test is done, the only check we do is to traverse
599 the freelist, checking for loops and ensuring the number of
600 elements is correct
601 */
603 internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
605 cpu_count = abstraction_cpu_count();
607 freelist_new( &fs, cpu_count, NULL, NULL );
609 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
611 for( loop = 0 ; loop < cpu_count ; loop++ )
612 abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_rapid_popping_and_pushing, fs );
614 for( loop = 0 ; loop < cpu_count ; loop++ )
615 abstraction_thread_wait( thread_handles[loop] );
617 free( thread_handles );
619 vi.min_elements = cpu_count;
620 vi.max_elements = cpu_count;
622 freelist_query( fs, FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
624 freelist_delete( fs, NULL, NULL );
626 // TRD : print the test result
627 internal_display_test_result( 1, "freelist", dvs );
629 return;
630 }
636 /****************************************************************************/
637 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing( void *freelist_state )
638 {
639 struct freelist_state
640 *fs;
642 struct freelist_element
643 *fe;
645 time_t
646 start_time;
648 assert( freelist_state != NULL );
650 fs = (struct freelist_state *) freelist_state;
652 time( &start_time );
654 while( time(NULL) < start_time + 10 )
655 {
656 freelist_pop( fs, &fe );
657 freelist_push( fs, fe );
658 }
660 return( (thread_return_t) EXIT_SUCCESS );
661 }