pd.if.org Git - liblfds/blob - 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