pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.0/test/src/test_freelist.c

   1 #include "internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 void test_lfds600_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     count;
  33
  34   thread_state_t
  35     *thread_handles;
  36
  37   enum data_structure_validity
  38     dvs = VALIDITY_VALID;
  39
  40   struct lfds600_freelist_state
  41     *fs;
  42
  43   struct lfds600_freelist_element
  44     *fe;
  45
  46   struct freelist_test_popping_state
  47     *ftps;
  48
  49   unsigned int
  50     *found_count;
  51
  52   /* TRD : we create a freelist with 1,000,000 elements
  53
  54            the creation function runs in a single thread and creates
  55            and pushes those elements onto the freelist
  56
  57            each element contains a void pointer which is its element number
  58
  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
  62
  63            the threads run till the source freelist is empty
  64
  65            we then check the thread-local freelists
  66            we should find we have every element
  67
  68            then tidy up
  69   */
  70
  71   internal_display_test_name( "Popping" );
  72
  73   cpu_count = abstraction_cpu_count();
  74
  75   lfds600_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     lfds600_freelist_new( &(ftps+loop)->fs_thread_local, 0, NULL, NULL );
  81   }
  82
  83   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
  84
  85   for( loop = 0 ; loop < cpu_count ; loop++ )
  86     abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_popping, ftps+loop );
  87
  88   for( loop = 0 ; loop < cpu_count ; loop++ )
  89     abstraction_thread_wait( thread_handles[loop] );
  90
  91   free( thread_handles );
  92
  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;
  97
  98   for( loop = 0 ; loop < cpu_count ; loop++ )
  99   {
 100     while( lfds600_freelist_pop((ftps+loop)->fs_thread_local, &fe) )
 101     {
 102       lfds600_freelist_get_user_data_from_element( fe, (void **) &count );
 103       (*(found_count+count))++;
 104       lfds600_freelist_push( fs, fe );
 105     }
 106   }
 107
 108   for( loop = 0 ; loop < 1000000 and dvs == VALIDITY_VALID ; loop++ )
 109   {
 110     if( *(found_count+loop) == 0 )
 111       dvs = VALIDITY_INVALID_MISSING_ELEMENTS;
 112
 113     if( *(found_count+loop) > 1 )
 114       dvs = VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 115   }
 116
 117   // TRD : cleanup
 118   free( found_count );
 119   for( loop = 0 ; loop < cpu_count ; loop++ )
 120     lfds600_freelist_delete( (ftps+loop)->fs_thread_local, NULL, NULL );
 121   lfds600_freelist_delete( fs, NULL, NULL );
 122
 123   // TRD : print the test result
 124   internal_display_test_result( 1, "freelist", dvs );
 125
 126   return;
 127 }
 128
 129
 130
 131
 132
 133 /****************************************************************************/
 134 #pragma warning( disable : 4100 )
 135
 136 int freelist_test_internal_popping_init( void **user_data, void *user_state )
 137 {
 138   static lfds600_atom_t
 139     count = 0;
 140
 141   assert( user_data != NULL );
 142   assert( user_state == NULL );
 143
 144   *(lfds600_atom_t *) user_data = count++;
 145
 146   return( 1 );
 147 }
 148
 149 #pragma warning( default : 4100 )
 150
 151
 152
 153
 154
 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;
 160
 161   struct lfds600_freelist_element
 162     *fe;
 163
 164   assert( freelist_test_popping_state != NULL );
 165
 166   ftps = (struct freelist_test_popping_state *) freelist_test_popping_state;
 167
 168   while( lfds600_freelist_pop(ftps->fs, &fe) )
 169     lfds600_freelist_push( ftps->fs_thread_local, fe );
 170
 171   return( (thread_return_t) EXIT_SUCCESS );
 172 }
 173
 174
 175
 176
 177
 178 /****************************************************************************/
 179 void freelist_test_internal_pushing( void )
 180 {
 181   unsigned int
 182     loop,
 183     cpu_count;
 184
 185   thread_state_t
 186     *thread_handles;
 187
 188   enum data_structure_validity
 189     dvs;
 190
 191   struct freelist_test_pushing_state
 192     *ftps;
 193
 194   struct lfds600_freelist_element
 195     *fe;
 196
 197   struct lfds600_freelist_state
 198     *fs,
 199     *cleanup_fs;
 200
 201   struct freelist_test_counter_and_thread_number
 202     *cnt,
 203     *counter_and_number_trackers;
 204
 205   struct lfds600_validation_info
 206     vi = { 1000000, 1000000 };
 207
 208   /* TRD : we create an empty freelist, which we will push to
 209
 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)
 214
 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
 218
 219            the reason for this is to achieve memory pre-allocation
 220            which allows the pushing threads to run at maximum speed
 221
 222            the threads end when their freelists are empty
 223
 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   */
 232
 233   internal_display_test_name( "Pushing" );
 234
 235   cpu_count = abstraction_cpu_count();
 236
 237   ftps = malloc( sizeof(struct freelist_test_pushing_state) * cpu_count );
 238
 239   lfds600_freelist_new( &fs, 0, NULL, NULL );
 240
 241   for( loop = 0 ; loop < cpu_count ; loop++ )
 242   {
 243     (ftps+loop)->thread_number = (lfds600_atom_t) loop;
 244     lfds600_freelist_new( &(ftps+loop)->source_fs, 1000000 / cpu_count, freelist_test_internal_pushing_init, (void *) (lfds600_atom_t) loop );
 245     (ftps+loop)->fs = fs;
 246   }
 247
 248   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
 249
 250   for( loop = 0 ; loop < cpu_count ; loop++ )
 251     abstraction_thread_start( &thread_handles[loop], loop, freelist_test_internal_thread_pushing, ftps+loop );
 252
 253   for( loop = 0 ; loop < cpu_count ; loop++ )
 254     abstraction_thread_wait( thread_handles[loop] );
 255
 256   free( thread_handles );
 257
 258   // TRD : now fully pop and verify the main freelist
 259   lfds600_freelist_new( &cleanup_fs, 0, NULL, NULL );
 260
 261   counter_and_number_trackers = malloc( sizeof(struct freelist_test_counter_and_thread_number) * cpu_count );
 262
 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 = (lfds600_atom_t) loop;
 267   }
 268
 269   lfds600_freelist_query( fs, LFDS600_FREELIST_QUERY_VALIDATE, &vi, (void *) &dvs );
 270
 271   while( dvs == VALIDITY_VALID and lfds600_freelist_pop(fs, &fe) )
 272   {
 273     static int count = 0;
 274
 275     lfds600_freelist_get_user_data_from_element( fe, (void **) &cnt );
 276
 277     if( cnt->counter != (counter_and_number_trackers+cnt->thread_number)->counter++ )
 278       dvs = VALIDITY_INVALID_MISSING_ELEMENTS;
 279
 280     lfds600_freelist_push( cleanup_fs, fe );
 281
 282     count++;
 283   }
 284
 285   // TRD : clean up
 286   free( counter_and_number_trackers );
 287
 288   for( loop = 0 ; loop < cpu_count ; loop++ )
 289     lfds600_freelist_delete( (ftps+loop)->source_fs, NULL, NULL );
 290
 291   free( ftps );
 292
 293   lfds600_freelist_delete( cleanup_fs, freelist_test_internal_pushing_delete, NULL );
 294   lfds600_freelist_delete( fs, NULL, NULL );
 295
 296   // TRD : print the test result
 297   internal_display_test_result( 1, "freelist", dvs );
 298
 299   return;
 300 }
 301
 302
 303
 304
 305
 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;
 311
 312   static lfds600_atom_t
 313     counter = 0;
 314
 315   assert( user_data != NULL );
 316   // TRD : user_state is being used as an integer type
 317
 318   *user_data = malloc( sizeof(struct freelist_test_counter_and_thread_number) );
 319
 320   ftcatn = (struct freelist_test_counter_and_thread_number *) *user_data;
 321
 322   ftcatn->counter = counter++;
 323   ftcatn->thread_number = (lfds600_atom_t) user_state;
 324
 325   return( 1 );
 326 }
 327
 328
 329
 330
 331
 332 /****************************************************************************/
 333 #pragma warning( disable : 4100 )
 334
 335 void freelist_test_internal_pushing_delete( void *user_data, void *user_state )
 336 {
 337   assert( user_data != NULL );
 338   assert( user_state == NULL );
 339
 340   free( user_data );
 341
 342   return;
 343 }
 344
 345 #pragma warning( default : 4100 )
 346
 347
 348
 349
 350
 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;
 356
 357   struct lfds600_freelist_element
 358     *fe;
 359
 360   assert( freelist_test_pushing_state != NULL );
 361
 362   ftps = (struct freelist_test_pushing_state *) freelist_test_pushing_state;
 363
 364   while( lfds600_freelist_pop(ftps->source_fs, &fe) )
 365     lfds600_freelist_push( ftps->fs, fe );
 366
 367   return( (thread_return_t) EXIT_SUCCESS );
 368 }
 369
 370
 371
 372
 373
 374 /****************************************************************************/
 375 void freelist_test_internal_popping_and_pushing( void )
 376 {
 377   unsigned int
 378     loop,
 379     cpu_count;
 380
 381   thread_state_t
 382     *thread_handles;
 383
 384   enum data_structure_validity
 385     dvs;
 386
 387   struct lfds600_freelist_state
 388     *fs;
 389
 390   struct freelist_test_popping_and_pushing_state
 391     *pps;
 392
 393   struct lfds600_validation_info
 394     vi;
 395
 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
 401
 402            after time is up, all threads push what they have remaining onto
 403            the main freelist
 404
 405            we then validate the main freelist
 406   */
 407
 408   internal_display_test_name( "Popping and pushing (10 seconds)" );
 409
 410   cpu_count = abstraction_cpu_count();
 411
 412   lfds600_freelist_new( &fs, 100000 * cpu_count, NULL, NULL );
 413
 414   pps = malloc( sizeof(struct freelist_test_popping_and_pushing_state) * cpu_count * 2 );
 415
 416   for( loop = 0 ; loop < cpu_count ; loop++ )
 417   {
 418     (pps+loop)->fs = fs;
 419     lfds600_freelist_new( &(pps+loop)->local_fs, 0, NULL, NULL );
 420
 421     (pps+loop+cpu_count)->fs = fs;
 422     lfds600_freelist_new( &(pps+loop+cpu_count)->local_fs, 100000, NULL, NULL );
 423   }
 424
 425   thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
 426
 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   }
 432
 433   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
 434     abstraction_thread_wait( thread_handles[loop] );
 435
 436   free( thread_handles );
 437
 438   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
 439     lfds600_freelist_delete( (pps+loop)->local_fs, NULL, NULL );
 440
 441   free( pps );
 442
 443   vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
 444
 445   lfds600_freelist_query( fs, LFDS600_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
 446
 447   lfds600_freelist_delete( fs, NULL, NULL );
 448
 449   // TRD : print the test result
 450   internal_display_test_result( 1, "freelist", dvs );
 451
 452   return;
 453 }
 454
 455
 456
 457
 458
 459
 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;
 465
 466   struct lfds600_freelist_element
 467     *fe;
 468
 469   time_t
 470     start_time;
 471
 472   unsigned int
 473     count;
 474
 475   assert( freelist_test_popping_and_pushing_state != NULL );
 476
 477   pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
 478
 479   time( &start_time );
 480
 481   while( time(NULL) < start_time + 10 )
 482   {
 483     count = 0;
 484
 485     while( count < 100000 )
 486     {
 487       lfds600_freelist_pop( pps->fs, &fe );
 488
 489       if( fe != NULL )
 490       {
 491         lfds600_freelist_push( pps->local_fs, fe );
 492         count++;
 493       }
 494     }
 495
 496     while( lfds600_freelist_pop(pps->local_fs, &fe) )
 497       lfds600_freelist_push( pps->fs, fe );
 498   }
 499
 500   return( (thread_return_t) EXIT_SUCCESS );
 501 }
 502
 503
 504
 505
 506
 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;
 512
 513   struct lfds600_freelist_element
 514     *fe;
 515
 516   time_t
 517     start_time;
 518
 519   unsigned int
 520     count;
 521
 522   assert( freelist_test_popping_and_pushing_state != NULL );
 523
 524   pps = (struct freelist_test_popping_and_pushing_state *) freelist_test_popping_and_pushing_state;
 525
 526   time( &start_time );
 527
 528   while( time(NULL) < start_time + 10 )
 529   {
 530     while( lfds600_freelist_pop(pps->local_fs, &fe) )
 531       lfds600_freelist_push( pps->fs, fe );
 532
 533     count = 0;
 534
 535     while( count < 1000 )
 536     {
 537       lfds600_freelist_pop( pps->fs, &fe );
 538
 539       if( fe != NULL )
 540       {
 541         lfds600_freelist_push( pps->local_fs, fe );
 542         count++;
 543       }
 544     }
 545   }
 546
 547   // TRD : now push whatever we have in our local freelist
 548   while( lfds600_freelist_pop(pps->local_fs, &fe) )
 549     lfds600_freelist_push( pps->fs, fe );
 550
 551   return( (thread_return_t) EXIT_SUCCESS );
 552 }
 553
 554
 555
 556
 557
 558 /****************************************************************************/
 559 void freelist_test_internal_rapid_popping_and_pushing( void )
 560 {
 561   unsigned int
 562     loop,
 563     cpu_count;
 564
 565   thread_state_t
 566     *thread_handles;
 567
 568   struct lfds600_freelist_state
 569     *fs;
 570
 571   struct lfds600_validation_info
 572     vi;
 573
 574   enum data_structure_validity
 575     dvs;
 576
 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
 581
 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
 585
 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
 591
 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
 595
 596            the test runs for ten seconds
 597
 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   */
 602
 603   internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
 604
 605   cpu_count = abstraction_cpu_count();
 606
 607   lfds600_freelist_new( &fs, cpu_count, NULL, NULL );
 608
 609   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
 610
 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 );
 613
 614   for( loop = 0 ; loop < cpu_count ; loop++ )
 615     abstraction_thread_wait( thread_handles[loop] );
 616
 617   free( thread_handles );
 618
 619   vi.min_elements = cpu_count;
 620   vi.max_elements = cpu_count;
 621
 622   lfds600_freelist_query( fs, LFDS600_FREELIST_QUERY_VALIDATE, (void *) &vi, (void *) &dvs );
 623
 624   lfds600_freelist_delete( fs, NULL, NULL );
 625
 626   // TRD : print the test result
 627   internal_display_test_result( 1, "freelist", dvs );
 628
 629   return;
 630 }
 631
 632
 633
 634
 635
 636 /****************************************************************************/
 637 thread_return_t CALLING_CONVENTION freelist_test_internal_thread_rapid_popping_and_pushing( void *lfds600_freelist_state )
 638 {
 639   struct lfds600_freelist_state
 640     *fs;
 641
 642   struct lfds600_freelist_element
 643     *fe;
 644
 645   time_t
 646     start_time;
 647
 648   assert( lfds600_freelist_state != NULL );
 649
 650   fs = (struct lfds600_freelist_state *) lfds600_freelist_state;
 651
 652   time( &start_time );
 653
 654   while( time(NULL) < start_time + 10 )
 655   {
 656     lfds600_freelist_pop( fs, &fe );
 657     lfds600_freelist_push( fs, fe );
 658   }
 659
 660   return( (thread_return_t) EXIT_SUCCESS );
 661 }
 662