pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/test/src/test_stack.c

   1 #include "internal.h"
   2
   3
   4
   5
   6
   7 /****************************************************************************/
   8 void test_lfds610_stack( void )
   9 {
  10   printf( "\n"
  11           "Stack Tests\n"
  12           "===========\n" );
  13
  14   stack_test_internal_popping();
  15   stack_test_internal_pushing();
  16   stack_test_internal_popping_and_pushing();
  17   stack_test_internal_rapid_popping_and_pushing();
  18
  19   return;
  20 }
  21
  22
  23
  24
  25
  26 /****************************************************************************/
  27 void stack_test_internal_popping( void )
  28 {
  29   unsigned int
  30     loop,
  31     *found_count,
  32     cpu_count;
  33
  34   lfds610_atom_t
  35     count;
  36
  37   thread_state_t
  38     *thread_handles;
  39
  40   enum lfds610_data_structure_validity
  41     dvs = LFDS610_VALIDITY_VALID;
  42
  43   struct lfds610_stack_state
  44     *ss;
  45
  46   struct stack_test_popping_state
  47     *stps;
  48
  49   /* TRD : we create a stack with 1,000,000 elements
  50
  51            we then populate the stack, where each element is
  52            set to contain a void pointer which is its element number
  53
  54            we then run one thread per CPU
  55            where each thread loops, popping as quickly as possible
  56            each popped element is pushed onto a thread-local stack
  57
  58            the threads run till the source stack is empty
  59
  60            we then check the thread-local stacks
  61            we should find we have every element
  62
  63            then tidy up
  64   */
  65
  66   internal_display_test_name( "Popping" );
  67
  68   cpu_count = abstraction_cpu_count();
  69
  70   lfds610_stack_new( &ss, 1000000 );
  71
  72   for( loop = 0 ; loop < 1000000 ; loop++ )
  73     lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
  74
  75   stps = malloc( sizeof(struct stack_test_popping_state) * cpu_count );
  76   for( loop = 0 ; loop < cpu_count ; loop++ )
  77   {
  78     (stps+loop)->ss = ss;
  79     lfds610_stack_new( &(stps+loop)->ss_thread_local, 1000000 );
  80   }
  81
  82   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
  83
  84   for( loop = 0 ; loop < cpu_count ; loop++ )
  85     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping, stps+loop );
  86
  87   for( loop = 0 ; loop < cpu_count ; loop++ )
  88     abstraction_thread_wait( thread_handles[loop] );
  89
  90   free( thread_handles );
  91
  92   // TRD : now we check the thread-local stacks
  93   found_count = malloc( sizeof(unsigned int) * 1000000 );
  94   for( loop = 0 ; loop < 1000000 ; loop++ )
  95     *(found_count+loop) = 0;
  96
  97   for( loop = 0 ; loop < cpu_count ; loop++ )
  98     while( lfds610_stack_pop((stps+loop)->ss_thread_local, (void **) &count) )
  99       (*(found_count+count))++;
 100
 101   for( loop = 0 ; loop < 1000000 and dvs == LFDS610_VALIDITY_VALID ; loop++ )
 102   {
 103     if( *(found_count+loop) == 0 )
 104       dvs = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
 105
 106     if( *(found_count+loop) > 1 )
 107       dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 108   }
 109
 110   // TRD : cleanup
 111   free( found_count );
 112   for( loop = 0 ; loop < cpu_count ; loop++ )
 113     lfds610_stack_delete( (stps+loop)->ss_thread_local, NULL, NULL );
 114   free( stps );
 115   lfds610_stack_delete( ss, NULL, NULL );
 116
 117   // TRD : print the test result
 118   internal_display_test_result( 1, "stack", dvs );
 119
 120   return;
 121 }
 122
 123
 124
 125
 126
 127 /****************************************************************************/
 128 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping( void *stack_test_popping_state )
 129 {
 130   struct stack_test_popping_state
 131     *stps;
 132
 133   lfds610_atom_t
 134     count;
 135
 136   assert( stack_test_popping_state != NULL );
 137
 138   stps = (struct stack_test_popping_state *) stack_test_popping_state;
 139
 140   lfds610_stack_use( stps->ss );
 141
 142   while( lfds610_stack_pop(stps->ss, (void **) &count) )
 143     lfds610_stack_push( stps->ss_thread_local, (void *) count );
 144
 145   return( (thread_return_t) EXIT_SUCCESS );
 146 }
 147
 148
 149
 150
 151
 152 /****************************************************************************/
 153 void stack_test_internal_pushing( void )
 154 {
 155   unsigned int
 156     loop,
 157     cpu_count;
 158
 159   thread_state_t
 160     *thread_handles;
 161
 162   enum lfds610_data_structure_validity
 163     dvs[2];
 164
 165   struct stack_test_pushing_state
 166     *stps;
 167
 168   struct lfds610_stack_state
 169     *ss;
 170
 171   lfds610_atom_t
 172     user_data,
 173     thread,
 174     count,
 175     *per_thread_counters;
 176
 177   struct lfds610_validation_info
 178     vi = { 1000000, 1000000 };
 179
 180   /* TRD : we create a stack with 1,000,000 elements
 181
 182            we then create one thread per CPU, where each thread
 183            pushes as quickly as possible to the stack
 184
 185            the data pushed is a counter and a thread ID
 186
 187            the threads exit when the stack is full
 188
 189            we then validate the stack;
 190
 191            checking that the counts increment on a per unique ID basis
 192            and that the number of elements we pop equals 1,000,000
 193            (since each element has an incrementing counter which is
 194             unique on a per unique ID basis, we can know we didn't lose
 195             any elements)
 196   */
 197
 198   internal_display_test_name( "Pushing" );
 199
 200   cpu_count = abstraction_cpu_count();
 201
 202   stps = malloc( sizeof(struct stack_test_pushing_state) * cpu_count );
 203
 204   // TRD : the main stack
 205   lfds610_stack_new( &ss, 1000000 );
 206
 207   for( loop = 0 ; loop < cpu_count ; loop++ )
 208   {
 209     (stps+loop)->thread_number = (lfds610_atom_t) loop;
 210     (stps+loop)->ss = ss;
 211   }
 212
 213   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
 214
 215   for( loop = 0 ; loop < cpu_count ; loop++ )
 216     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_pushing, stps+loop );
 217
 218   for( loop = 0 ; loop < cpu_count ; loop++ )
 219     abstraction_thread_wait( thread_handles[loop] );
 220
 221   free( thread_handles );
 222
 223   // TRD : the stack is now fully pushed; time to verify
 224   per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
 225
 226   for( loop = 0 ; loop < cpu_count ; loop++ )
 227     *(per_thread_counters+loop) = 1000000;
 228
 229   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, &vi, (void *) dvs );
 230
 231   while( dvs[0] == LFDS610_VALIDITY_VALID and lfds610_stack_pop(ss, (void **) &user_data) )
 232   {
 233     thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
 234     count = (user_data << 8) >> 8;
 235
 236     if( thread >= cpu_count )
 237     {
 238       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
 239       break;
 240     }
 241
 242     if( count > per_thread_counters[thread] )
 243       dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
 244
 245     if( count < per_thread_counters[thread] )
 246       per_thread_counters[thread] = count-1;
 247   }
 248
 249   // TRD : clean up
 250   free( per_thread_counters );
 251
 252   free( stps );
 253
 254   lfds610_stack_delete( ss, NULL, NULL );
 255
 256   // TRD : print the test result
 257   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
 258
 259   return;
 260 }
 261
 262
 263
 264
 265
 266 /****************************************************************************/
 267 thread_return_t CALLING_CONVENTION stack_test_internal_thread_pushing( void *stack_test_pushing_state )
 268 {
 269   struct stack_test_pushing_state
 270     *stps;
 271
 272   lfds610_atom_t
 273     counter = 0;
 274
 275   assert( stack_test_pushing_state != NULL );
 276
 277   stps = (struct stack_test_pushing_state *) stack_test_pushing_state;
 278
 279   lfds610_stack_use( stps->ss );
 280
 281   // TRD : we write (thread_number | counter), where thread_number is the top 8 bits of the lfds610_atom_t
 282   while( lfds610_stack_push(stps->ss, (void **) ((stps->thread_number << (sizeof(lfds610_atom_t)*8-8)) | counter++)) );
 283
 284   return( (thread_return_t) EXIT_SUCCESS );
 285 }
 286
 287
 288
 289
 290
 291 /****************************************************************************/
 292 void stack_test_internal_popping_and_pushing( void )
 293 {
 294   unsigned int
 295     loop,
 296     subloop,
 297     cpu_count;
 298
 299   thread_state_t
 300     *thread_handles;
 301
 302   enum lfds610_data_structure_validity
 303     dvs[2];
 304
 305   struct lfds610_stack_state
 306     *ss;
 307
 308   struct stack_test_popping_and_pushing_state
 309     *stpps;
 310
 311   struct lfds610_validation_info
 312     vi;
 313
 314   /* TRD : we have two threads per CPU
 315            the threads loop for ten seconds
 316            the first thread pushes 100000 elements then pops 100000 elements
 317            the second thread pops 100000 elements then pushes 100000 elements
 318            all pushes and pops go onto the single main stack
 319
 320            after time is up, all threads push what they have remaining onto
 321            the main stack
 322
 323            we then validate the main stack
 324   */
 325
 326   internal_display_test_name( "Popping and pushing (10 seconds)" );
 327
 328   cpu_count = abstraction_cpu_count();
 329
 330   // TRD : just some initial elements so the pushing threads can start immediately
 331   lfds610_stack_new( &ss, 100000 * cpu_count * 2 );
 332
 333   for( loop = 0 ; loop < 100000 * cpu_count ; loop++ )
 334     lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
 335
 336   stpps = malloc( sizeof(struct stack_test_popping_and_pushing_state) * cpu_count * 2 );
 337
 338   for( loop = 0 ; loop < cpu_count ; loop++ )
 339   {
 340     (stpps+loop)->ss = ss;
 341     lfds610_stack_new( &(stpps+loop)->local_ss, 100000 );
 342
 343     (stpps+loop+cpu_count)->ss = ss;
 344     lfds610_stack_new( &(stpps+loop+cpu_count)->local_ss, 100000 );
 345
 346     // TRD : fill the pushing thread stacks
 347     for( subloop = 0 ; subloop < 100000 ; subloop++ )
 348       lfds610_stack_push( (stpps+loop+cpu_count)->local_ss, (void *) (lfds610_atom_t) subloop );
 349   }
 350
 351   thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
 352
 353   for( loop = 0 ; loop < cpu_count ; loop++ )
 354   {
 355     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping_and_pushing_start_popping, stpps+loop );
 356     abstraction_thread_start( &thread_handles[loop+cpu_count], loop, stack_test_internal_thread_popping_and_pushing_start_pushing, stpps+loop+cpu_count );
 357   }
 358
 359   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
 360     abstraction_thread_wait( thread_handles[loop] );
 361
 362   free( thread_handles );
 363
 364   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
 365     lfds610_stack_delete( (stpps+loop)->local_ss, NULL, NULL );
 366
 367   free( stpps );
 368
 369   vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
 370
 371   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
 372
 373   lfds610_stack_delete( ss, NULL, NULL );
 374
 375   // TRD : print the test result
 376   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
 377
 378   return;
 379 }
 380
 381
 382
 383
 384
 385
 386 /****************************************************************************/
 387 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_popping( void *stack_test_popping_and_pushing_state )
 388 {
 389   struct stack_test_popping_and_pushing_state
 390     *stpps;
 391
 392   void
 393     *user_data;
 394
 395   time_t
 396     start_time;
 397
 398   unsigned int
 399     count;
 400
 401   assert( stack_test_popping_and_pushing_state != NULL );
 402
 403   stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
 404
 405   lfds610_stack_use( stpps->ss );
 406   lfds610_stack_use( stpps->local_ss );
 407
 408   time( &start_time );
 409
 410   while( time(NULL) < start_time + 10 )
 411   {
 412     count = 0;
 413
 414     while( count < 100000 )
 415       if( lfds610_stack_pop(stpps->ss, &user_data) )
 416       {
 417         lfds610_stack_push( stpps->local_ss, user_data );
 418         count++;
 419       }
 420
 421     // TRD : return our local stack to the main stack
 422     while( lfds610_stack_pop(stpps->local_ss, &user_data) )
 423       lfds610_stack_push( stpps->ss, user_data );
 424   }
 425
 426   return( (thread_return_t) EXIT_SUCCESS );
 427 }
 428
 429
 430
 431
 432
 433 /****************************************************************************/
 434 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_pushing( void *stack_test_popping_and_pushing_state )
 435 {
 436   struct stack_test_popping_and_pushing_state
 437     *stpps;
 438
 439   void
 440     *user_data;
 441
 442   time_t
 443     start_time;
 444
 445   unsigned int
 446     count;
 447
 448   assert( stack_test_popping_and_pushing_state != NULL );
 449
 450   stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
 451
 452   lfds610_stack_use( stpps->ss );
 453   lfds610_stack_use( stpps->local_ss );
 454
 455   time( &start_time );
 456
 457   while( time(NULL) < start_time + 10 )
 458   {
 459     // TRD : return our local stack to the main stack
 460     while( lfds610_stack_pop(stpps->local_ss, &user_data) )
 461       lfds610_stack_push( stpps->ss, user_data );
 462
 463     count = 0;
 464
 465     while( count < 100000 )
 466       if( lfds610_stack_pop(stpps->ss, &user_data) )
 467       {
 468         lfds610_stack_push( stpps->local_ss, user_data );
 469         count++;
 470       }
 471   }
 472
 473   // TRD : now push whatever we have in our local stack
 474   while( lfds610_stack_pop(stpps->local_ss, &user_data) )
 475     lfds610_stack_push( stpps->ss, user_data );
 476
 477   return( (thread_return_t) EXIT_SUCCESS );
 478 }
 479
 480
 481
 482
 483
 484 /****************************************************************************/
 485 void stack_test_internal_rapid_popping_and_pushing( void )
 486 {
 487   unsigned int
 488     loop,
 489     cpu_count;
 490
 491   thread_state_t
 492     *thread_handles;
 493
 494   struct lfds610_stack_state
 495     *ss;
 496
 497   struct lfds610_validation_info
 498     vi;
 499
 500   enum lfds610_data_structure_validity
 501     dvs[2];
 502
 503   /* TRD : in these tests there is a fundamental antagonism between
 504            how much checking/memory clean up that we do and the
 505            likelyhood of collisions between threads in their lock-free
 506            operations
 507
 508            the lock-free operations are very quick; if we do anything
 509            much at all between operations, we greatly reduce the chance
 510            of threads colliding
 511
 512            so we have some tests which do enough checking/clean up that
 513            they can tell the stack is valid and don't leak memory
 514            and here, this test now is one of those which does minimal
 515            checking - in fact, the nature of the test is that you can't
 516            do any real checking - but goes very quickly
 517
 518            what we do is create a small stack and then run one thread
 519            per CPU, where each thread simply pushes and then immediately
 520            pops
 521
 522            the test runs for ten seconds
 523
 524            after the test is done, the only check we do is to traverse
 525            the stack, checking for loops and ensuring the number of
 526            elements is correct
 527   */
 528
 529   internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
 530
 531   cpu_count = abstraction_cpu_count();
 532
 533   lfds610_stack_new( &ss, cpu_count );
 534
 535   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
 536
 537   for( loop = 0 ; loop < cpu_count ; loop++ )
 538     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_rapid_popping_and_pushing, ss );
 539
 540   for( loop = 0 ; loop < cpu_count ; loop++ )
 541     abstraction_thread_wait( thread_handles[loop] );
 542
 543   free( thread_handles );
 544
 545   vi.min_elements = 0;
 546   vi.max_elements = 0;
 547
 548   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
 549
 550   lfds610_stack_delete( ss, NULL, NULL );
 551
 552   // TRD : print the test result
 553   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
 554
 555   return;
 556 }
 557
 558
 559
 560
 561
 562 /****************************************************************************/
 563 thread_return_t CALLING_CONVENTION stack_test_internal_thread_rapid_popping_and_pushing( void *stack_state )
 564 {
 565   struct lfds610_stack_state
 566     *ss;
 567
 568   void
 569     *user_data = NULL;
 570
 571   time_t
 572     start_time;
 573
 574   assert( stack_state != NULL );
 575
 576   ss = (struct lfds610_stack_state *) stack_state;
 577
 578   lfds610_stack_use( ss );
 579
 580   time( &start_time );
 581
 582   while( time(NULL) < start_time + 10 )
 583   {
 584     lfds610_stack_push( ss, user_data );
 585     lfds610_stack_pop( ss, &user_data );
 586   }
 587
 588   return( (thread_return_t) EXIT_SUCCESS );
 589 }
 590