]> pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/test/src/test_freelist.c
Initial import (all versions, including the new 7.1.0)
[liblfds] / liblfds / liblfds6.1.0 / test / src / test_freelist.c
1 #include "internal.h"
2
3
4
5
6
7 /****************************************************************************/
8 void test_lfds610_freelist( void )
9 {
10   printf( "\n"
11           "Freelist Tests\n"
12           "==============\n" );
13
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();
18
19   return;
20 }
21
22
23
24
25
26 /****************************************************************************/
27 void freelist_test_internal_popping( void )
28 {
29   unsigned int
30     loop,
31     cpu_count;
32
33   lfds610_atom_t
34     count = 0;
35
36   thread_state_t
37     *thread_handles;
38
39   enum lfds610_data_structure_validity
40     dvs = LFDS610_VALIDITY_VALID;
41
42   struct lfds610_freelist_state
43     *fs;
44
45   struct lfds610_freelist_element
46     *fe;
47
48   struct freelist_test_popping_state
49     *ftps;
50
51   unsigned int
52     *found_count;
53
54   /* TRD : we create a freelist with 1,000,000 elements
55
56            the creation function runs in a single thread and creates
57            and pushes those elements onto the freelist
58
59            each element contains a void pointer which is its element number
60
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
64
65            the threads run till the source freelist is empty
66
67            we then check the thread-local freelists
68            we should find we have every element
69
70            then tidy up
71   */
72
73   internal_display_test_name( "Popping" );
74
75   cpu_count = abstraction_cpu_count();
76
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++ )
80   {
81     (ftps+loop)->fs = fs;
82     lfds610_freelist_new( &(ftps+loop)->fs_thread_local, 0, NULL, NULL );
83   }
84
85   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
86
87   for( loop = 0 ; loop < cpu_count ; loop++ )
88     abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps+loop );
89
90   for( loop = 0 ; loop < cpu_count ; loop++ )
91     abstraction_thread_wait( thread_handles[loop] );
92
93   free( thread_handles );
94
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;
99
100   for( loop = 0 ; loop < cpu_count ; loop++ )
101   {
102     while( lfds610_freelist_pop((ftps+loop)->fs_thread_local, &fe) )
103     {
104       lfds610_freelist_get_user_data_from_element( fe, (void **) &count );
105       (*(found_count+count))++;
106       lfds610_freelist_push( fs, fe );
107     }
108   }
109
110   for( loop = 0 ; loop < 1000000 and dvs == LFDS610_VALIDITY_VALID ; loop++ )
111   {
112     if( *(found_count+loop) == 0 )
113       dvs = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
114
115     if( *(found_count+loop) > 1 )
116       dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
117   }
118
119   // TRD : cleanup
120   free( found_count );
121   for( loop = 0 ; loop < cpu_count ; loop++ )
122     lfds610_freelist_delete( (ftps+loop)->fs_thread_local, NULL, NULL );
123   free( ftps );
124   lfds610_freelist_delete( fs, NULL, NULL );
125
126   // TRD : print the test result
127   internal_display_test_result( 1, "freelist", dvs );
128
129   return;
130 }
131
132
133
134
135
136 /****************************************************************************/
137 #pragma warning( disable : 4100 )
138
139 int freelist_test_internal_popping_init( void **user_data, void *user_state )
140 {
141   lfds610_atom_t
142     *count;
143
144   assert( user_data != NULL );
145   assert( user_state != NULL );
146
147   count = (lfds610_atom_t *) user_state;
148
149   *(lfds610_atom_t *) user_data = (*count)++;
150
151   return( 1 );
152 }
153
154 #pragma warning( default : 4100 )
155
156
157
158
159
160 /****************************************************************************/
161 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping( void *freelist_test_popping_state )
162 {
163   struct freelist_test_popping_state
164     *ftps;
165
166   struct lfds610_freelist_element
167     *fe;
168
169   assert( freelist_test_popping_state != NULL );
170
171   ftps = (struct freelist_test_popping_state *) freelist_test_popping_state;
172
173   lfds610_freelist_use( ftps->fs );
174   lfds610_freelist_use( ftps->fs_thread_local );
175
176   while( lfds610_freelist_pop(ftps->fs, &fe) )
177     lfds610_freelist_push( ftps->fs_thread_local, fe );
178
179   return( (thread_return_t) EXIT_SUCCESS );
180 }
181
182
183
184
185
186 /****************************************************************************/
187 void freelist_test_internal_pushing( void )
188 {
189   unsigned int
190     loop,
191     cpu_count;
192
193   lfds610_atom_t
194     count = 0;
195
196   thread_state_t
197     *thread_handles;
198
199   enum lfds610_data_structure_validity
200     dvs;
201
202   struct freelist_test_pushing_state
203     *ftps;
204
205   struct lfds610_freelist_element
206     *fe;
207
208   struct lfds610_freelist_state
209     *fs,
210     *cleanup_fs;
211
212   struct freelist_test_counter_and_thread_number
213     *cnt,
214     *counter_and_number_trackers;
215
216   struct lfds610_validation_info
217     vi;
218
219   /* TRD : we create an empty freelist, which we will push to
220
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)
225
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
229
230            the reason for this is to achieve memory pre-allocation
231            which allows the pushing threads to run at maximum speed
232
233            the threads end when their freelists are empty
234
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
241             any elements)
242   */
243
244   internal_display_test_name( "Pushing" );
245
246   cpu_count = abstraction_cpu_count();
247
248   ftps = malloc( sizeof(struct freelist_test_pushing_state) * cpu_count );
249
250   lfds610_freelist_new( &fs, 0, NULL, NULL );
251
252   for( loop = 0 ; loop < cpu_count ; loop++ )
253   {
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;
259   }
260
261   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
262
263   for( loop = 0 ; loop < cpu_count ; loop++ )
264     abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps+loop );
265
266   for( loop = 0 ; loop < cpu_count ; loop++ )
267     abstraction_thread_wait( thread_handles[loop] );
268
269   free( thread_handles );
270
271   // TRD : now fully pop and verify the main freelist
272   lfds610_freelist_new( &cleanup_fs, 0, NULL, NULL );
273
274   counter_and_number_trackers = malloc( sizeof(struct freelist_test_counter_and_thread_number) * cpu_count );
275
276   for( loop = 0 ; loop < cpu_count ; loop++ )
277   {
278     (counter_and_number_trackers+loop)->counter = 100000 * loop;
279     (counter_and_number_trackers+loop)->thread_number = (lfds610_atom_t) loop;
280   }
281
282   vi.min_elements = vi.max_elements = 100000 * cpu_count;
283
284   lfds610_freelist_query( fs, LFDS610_FREELIST_QUERY_VALIDATE, &vi, (void *) &dvs );
285
286   while( dvs == LFDS610_VALIDITY_VALID and lfds610_freelist_pop(fs, &fe) )
287   {
288     lfds610_freelist_get_user_data_from_element( fe, (void **) &cnt );
289
290     if( cnt->counter != (counter_and_number_trackers+cnt->thread_number)->counter++ )
291       dvs = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
292
293     lfds610_freelist_push( cleanup_fs, fe );
294   }
295
296   // TRD : clean up
297   free( counter_and_number_trackers );
298
299   for( loop = 0 ; loop < cpu_count ; loop++ )
300     lfds610_freelist_delete( (ftps+loop)->source_fs, NULL, NULL );
301
302   free( ftps );
303
304   lfds610_freelist_delete( cleanup_fs, freelist_test_internal_pushing_delete, NULL );
305   lfds610_freelist_delete( fs, NULL, NULL );
306
307   // TRD : print the test result
308   internal_display_test_result( 1, "freelist", dvs );
309
310   return;
311 }
312
313
314
315
316
317 /****************************************************************************/
318 int freelist_test_internal_pushing_init( void **user_data, void *user_state )
319 {
320   struct freelist_test_counter_and_thread_number
321     *ftcatn;
322
323   struct freelist_test_pushing_state
324     *ftps;
325
326   assert( user_data != NULL );
327   // TRD : user_state is being used as an integer type
328
329   *user_data = malloc( sizeof(struct freelist_test_counter_and_thread_number) );
330   ftps = (struct freelist_test_pushing_state *) user_state;
331
332   ftcatn = (struct freelist_test_counter_and_thread_number *) *user_data;
333
334   ftcatn->counter = (*ftps->count)++;
335   ftcatn->thread_number = ftps->thread_number;
336
337   return( 1 );
338 }
339
340
341
342
343
344 /****************************************************************************/
345 #pragma warning( disable : 4100 )
346
347 void freelist_test_internal_pushing_delete( void *user_data, void *user_state )
348 {
349   assert( user_data != NULL );
350   assert( user_state == NULL );
351
352   free( user_data );
353
354   return;
355 }
356
357 #pragma warning( default : 4100 )
358
359
360
361
362
363 /****************************************************************************/
364 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_pushing( void *freelist_test_pushing_state )
365 {
366   struct freelist_test_pushing_state
367     *ftps;
368
369   struct lfds610_freelist_element
370     *fe;
371
372   assert( freelist_test_pushing_state != NULL );
373
374   ftps = (struct freelist_test_pushing_state *) freelist_test_pushing_state;
375
376   lfds610_freelist_use( ftps->source_fs );
377   lfds610_freelist_use( ftps->fs );
378
379   while( lfds610_freelist_pop(ftps->source_fs, &fe) )
380     lfds610_freelist_push( ftps->fs, fe );
381
382   return( (thread_return_t) EXIT_SUCCESS );
383 }
384
385
386
387
388
389 /****************************************************************************/
390 void freelist_test_internal_popping_and_pushing( void )
391 {
392   unsigned int
393     loop,
394     cpu_count;
395
396   thread_state_t
397     *thread_handles;
398
399   enum lfds610_data_structure_validity
400     dvs;
401
402   struct lfds610_freelist_state
403     *fs;
404
405   struct freelist_test_popping_and_pushing_state
406     *pps;
407
408   struct lfds610_validation_info
409     vi;
410
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
416
417            after time is up, all threads push what they have remaining onto
418            the main freelist
419
420            we then validate the main freelist
421   */
422
423   internal_display_test_name( "Popping and pushing (10 seconds)" );
424
425   cpu_count = abstraction_cpu_count();
426
427   lfds610_freelist_new( &fs, 100000 * cpu_count, NULL, NULL );
428
429   pps = malloc( sizeof(struct freelist_test_popping_and_pushing_state) * cpu_count * 2 );
430
431   for( loop = 0 ; loop < cpu_count ; loop++ )
432   {
433     (pps+loop)->fs = fs;
434     lfds610_freelist_new( &(pps+loop)->local_fs, 0, NULL, NULL );
435
436     (pps+loop+cpu_count)->fs = fs;
437     lfds610_freelist_new( &(pps+loop+cpu_count)->local_fs, 100000, NULL, NULL );
438   }
439
440   thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
441
442   for( loop = 0 ; loop < cpu_count ; loop++ )
443   {
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 );
446   }
447
448   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
449     abstraction_thread_wait( thread_handles[loop] );
450
451   free( thread_handles );
452
453   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
454     lfds610_freelist_delete( (pps+loop)->local_fs, NULL, NULL );
455
456   free( pps );
457
458   vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
459
460   lfds610_freelist_query( fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
461
462   lfds610_freelist_delete( fs, NULL, NULL );
463
464   // TRD : print the test result
465   internal_display_test_result( 1, "freelist", dvs );
466
467   return;
468 }
469
470
471
472
473
474
475 /****************************************************************************/
476 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_popping( void *freelist_test_popping_and_pushing_state )
477 {
478   struct freelist_test_popping_and_pushing_state
479     *pps;
480
481   struct lfds610_freelist_element
482     *fe;
483
484   time_t
485     start_time;
486
487   unsigned int
488     count;
489
490   assert( freelist_test_popping_and_pushing_state != NULL );
491
492   pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
493
494   lfds610_freelist_use( pps->fs );
495   lfds610_freelist_use( pps->local_fs );
496
497   time( &start_time );
498
499   while( time(NULL) < start_time + 10 )
500   {
501     count = 0;
502
503     while( count < 100000 )
504     {
505       lfds610_freelist_pop( pps->fs, &fe );
506
507       if( fe != NULL )
508       {
509         lfds610_freelist_push( pps->local_fs, fe );
510         count++;
511       }
512     }
513
514     while( lfds610_freelist_pop(pps->local_fs, &fe) )
515       lfds610_freelist_push( pps->fs, fe );
516   }
517
518   return( (thread_return_t) EXIT_SUCCESS );
519 }
520
521
522
523
524
525 /****************************************************************************/
526 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_popping_and_pushing_start_pushing( void *freelist_test_popping_and_pushing_state )
527 {
528   struct freelist_test_popping_and_pushing_state
529     *pps;
530
531   struct lfds610_freelist_element
532     *fe;
533
534   time_t
535     start_time;
536
537   unsigned int
538     count;
539
540   assert( freelist_test_popping_and_pushing_state != NULL );
541
542   pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
543
544   lfds610_freelist_use( pps->fs );
545   lfds610_freelist_use( pps->local_fs );
546
547   time( &start_time );
548
549   while( time(NULL) < start_time + 10 )
550   {
551     while( lfds610_freelist_pop(pps->local_fs, &fe) )
552       lfds610_freelist_push( pps->fs, fe );
553
554     count = 0;
555
556     while( count < 1000 )
557     {
558       lfds610_freelist_pop( pps->fs, &fe );
559
560       if( fe != NULL )
561       {
562         lfds610_freelist_push( pps->local_fs, fe );
563         count++;
564       }
565     }
566   }
567
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 );
571
572   return( (thread_return_t) EXIT_SUCCESS );
573 }
574
575
576
577
578
579 /****************************************************************************/
580 void freelist_test_internal_rapid_popping_and_pushing( void )
581 {
582   unsigned int
583     loop,
584     cpu_count;
585
586   thread_state_t
587     *thread_handles;
588
589   struct lfds610_freelist_state
590     *fs;
591
592   struct lfds610_validation_info
593     vi;
594
595   enum lfds610_data_structure_validity
596     dvs;
597
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
601            operations
602
603            the lock-free operations are very quick; if we do anything
604            much at all between operations, we greatly reduce the chance
605            of threads colliding
606
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
612
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
615            pushes
616
617            the test runs for ten seconds
618
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
621            elements is correct
622   */
623
624   internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
625
626   cpu_count = abstraction_cpu_count();
627
628   lfds610_freelist_new( &fs, cpu_count, NULL, NULL );
629
630   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
631
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 );
634
635   for( loop = 0 ; loop < cpu_count ; loop++ )
636     abstraction_thread_wait( thread_handles[loop] );
637
638   free( thread_handles );
639
640   vi.min_elements = cpu_count;
641   vi.max_elements = cpu_count;
642
643   lfds610_freelist_query( fs, LFDS610_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
644
645   lfds610_freelist_delete( fs, NULL, NULL );
646
647   // TRD : print the test result
648   internal_display_test_result( 1, "freelist", dvs );
649
650   return;
651 }
652
653
654
655
656
657 /****************************************************************************/
658 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing( void *lfds610_freelist_state )
659 {
660   struct lfds610_freelist_state
661     *fs;
662
663   struct lfds610_freelist_element
664     *fe;
665
666   time_t
667     start_time;
668
669   assert( lfds610_freelist_state != NULL );
670
671   fs = (struct lfds610_freelist_state *) lfds610_freelist_state;
672
673   lfds610_freelist_use( fs );
674
675   time( &start_time );
676
677   while( time(NULL) < start_time + 10 )
678   {
679     lfds610_freelist_pop( fs, &fe );
680     lfds610_freelist_push( fs, fe );
681   }
682
683   return( (thread_return_t) EXIT_SUCCESS );
684 }
685