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

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