pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.1/test/src/test_queue.c

   1 #include "internal.h"\r
   2 \r
   3 \r
   4 \r
   5 \r
   6 \r
   7 /****************************************************************************/\r
   8 void test_lfds601_queue( void )\r
   9 {\r
  10   printf( "\n"\r
  11           "Queue Tests\n"\r
  12           "===========\n" );\r
  13 \r
  14   queue_test_enqueuing();\r
  15   queue_test_dequeuing();\r
  16   queue_test_enqueuing_and_dequeuing();\r
  17   queue_test_rapid_enqueuing_and_dequeuing();\r
  18 \r
  19   return;\r
  20 }\r
  21 \r
  22 \r
  23 \r
  24 \r
  25 \r
  26 /****************************************************************************/\r
  27 void queue_test_enqueuing( void )\r
  28 {\r
  29   unsigned int\r
  30     loop,\r
  31     cpu_count;\r
  32 \r
  33   thread_state_t\r
  34     *thread_handles;\r
  35 \r
  36   struct lfds601_queue_state\r
  37     *qs;\r
  38 \r
  39   struct queue_test_enqueuing_state\r
  40     *qtes;\r
  41 \r
  42   lfds601_atom_t\r
  43     user_data,\r
  44     thread,\r
  45     count,\r
  46     *per_thread_counters;\r
  47 \r
  48   struct lfds601_validation_info\r
  49     vi = { 1000000, 1000000 };\r
  50 \r
  51   enum lfds601_data_structure_validity\r
  52     dvs[2];\r
  53 \r
  54   /* TRD : create an empty queue with 1,000,000 elements in its freelist\r
  55            then run one thread per CPU\r
  56            where each thread busy-works, enqueuing elements (until there are no more elements)\r
  57            each element's void pointer of user data is (thread number | element number)\r
  58            where element_number is a thread-local counter starting at 0\r
  59            where the thread_number occupies the top byte\r
  60 \r
  61            when we're done, we check that all the elements are present\r
  62            and increment on a per-thread basis\r
  63   */\r
  64 \r
  65   internal_display_test_name( "Enqueuing" );\r
  66 \r
  67   cpu_count = abstraction_cpu_count();\r
  68 \r
  69   lfds601_queue_new( &qs, 1000000 );\r
  70 \r
  71   qtes = malloc( sizeof(struct queue_test_enqueuing_state) * cpu_count );\r
  72 \r
  73   for( loop = 0 ; loop < cpu_count ; loop++ )\r
  74   {\r
  75     (qtes+loop)->qs = qs;\r
  76     (qtes+loop)->counter = (lfds601_atom_t) loop << (sizeof(lfds601_atom_t)*8-8);\r
  77   }\r
  78 \r
  79   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
  80 \r
  81   for( loop = 0 ; loop < cpu_count ; loop++ )\r
  82     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_enqueuer, qtes+loop );\r
  83 \r
  84   for( loop = 0 ; loop < cpu_count ; loop++ )\r
  85     abstraction_thread_wait( thread_handles[loop] );\r
  86 \r
  87   free( thread_handles );\r
  88 \r
  89   free( qtes );\r
  90 \r
  91   /* TRD : first, validate the queue\r
  92 \r
  93            then dequeue\r
  94            we expect to find element numbers increment on a per thread basis\r
  95   */\r
  96 \r
  97   lfds601_queue_query( qs, LFDS601_QUEUE_QUERY_VALIDATE, &vi, dvs );\r
  98 \r
  99   per_thread_counters = malloc( sizeof(lfds601_atom_t) * cpu_count );\r
 100 \r
 101   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 102     *(per_thread_counters+loop) = 0;\r
 103 \r
 104   while( dvs[0] == LFDS601_VALIDITY_VALID and dvs[1] == LFDS601_VALIDITY_VALID and lfds601_queue_dequeue(qs, (void *) &user_data) )\r
 105   {\r
 106     thread = user_data >> (sizeof(lfds601_atom_t)*8-8);\r
 107     count = (user_data << 8) >> 8;\r
 108 \r
 109     if( thread >= cpu_count )\r
 110     {\r
 111       dvs[0] = LFDS601_VALIDITY_INVALID_TEST_DATA;\r
 112       break;\r
 113     }\r
 114 \r
 115     if( count < per_thread_counters[thread] )\r
 116       dvs[0] = LFDS601_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 117 \r
 118     if( count > per_thread_counters[thread] )\r
 119       dvs[0] = LFDS601_VALIDITY_INVALID_MISSING_ELEMENTS;\r
 120 \r
 121     if( count == per_thread_counters[thread] )\r
 122       per_thread_counters[thread]++;\r
 123   }\r
 124 \r
 125   free( per_thread_counters );\r
 126 \r
 127   lfds601_queue_delete( qs, NULL, NULL );\r
 128 \r
 129   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 130 \r
 131   return;\r
 132 }\r
 133 \r
 134 \r
 135 \r
 136 \r
 137 \r
 138 /****************************************************************************/\r
 139 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_enqueuer( void *queue_test_enqueuing_state )\r
 140 {\r
 141   struct queue_test_enqueuing_state\r
 142     *qtes;\r
 143 \r
 144   assert( queue_test_enqueuing_state != NULL );\r
 145 \r
 146   qtes = (struct queue_test_enqueuing_state *) queue_test_enqueuing_state;\r
 147 \r
 148   // TRD : top byte of counter is already our thread number\r
 149   while( lfds601_queue_enqueue(qtes->qs, (void *) qtes->counter++) );\r
 150 \r
 151   return( (thread_return_t) EXIT_SUCCESS );\r
 152 }\r
 153 \r
 154 \r
 155 \r
 156 \r
 157 \r
 158 /****************************************************************************/\r
 159 void queue_test_dequeuing( void )\r
 160 {\r
 161   unsigned int\r
 162     loop,\r
 163     cpu_count;\r
 164 \r
 165   thread_state_t\r
 166     *thread_handles;\r
 167 \r
 168   struct lfds601_queue_state\r
 169     *qs;\r
 170 \r
 171   struct queue_test_dequeuing_state\r
 172     *qtds;\r
 173 \r
 174   struct lfds601_validation_info\r
 175     vi = { 0, 0 };\r
 176 \r
 177   enum lfds601_data_structure_validity\r
 178     dvs[2];\r
 179 \r
 180   /* TRD : create a queue with 1,000,000 elements\r
 181 \r
 182            use a single thread to enqueue every element\r
 183            each elements user data is an incrementing counter\r
 184 \r
 185            then run one thread per CPU\r
 186            where each busy-works dequeuing\r
 187 \r
 188            when an element is dequeued, we check (on a per-thread basis) the\r
 189            value deqeued is greater than the element previously dequeued\r
 190   */\r
 191 \r
 192   internal_display_test_name( "Dequeuing" );\r
 193 \r
 194   cpu_count = abstraction_cpu_count();\r
 195 \r
 196   lfds601_queue_new( &qs, 1000000 );\r
 197 \r
 198   for( loop = 0 ; loop < 1000000 ; loop++ )\r
 199     lfds601_queue_enqueue( qs, (void *) (lfds601_atom_t) loop );\r
 200 \r
 201   qtds = malloc( sizeof(struct queue_test_dequeuing_state) * cpu_count );\r
 202 \r
 203   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 204   {\r
 205     (qtds+loop)->qs = qs;\r
 206     (qtds+loop)->error_flag = LOWERED;\r
 207   }\r
 208 \r
 209   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 210 \r
 211   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 212     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_dequeuer, qtds+loop );\r
 213 \r
 214   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 215     abstraction_thread_wait( thread_handles[loop] );\r
 216 \r
 217   free( thread_handles );\r
 218 \r
 219   // TRD : check queue is empty\r
 220   lfds601_queue_query( qs, LFDS601_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 221 \r
 222   // TRD : check for raised error flags\r
 223   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 224     if( (qtds+loop)->error_flag == RAISED )\r
 225       dvs[0] = LFDS601_VALIDITY_INVALID_TEST_DATA;\r
 226 \r
 227   free( qtds );\r
 228 \r
 229   lfds601_queue_delete( qs, NULL, NULL );\r
 230 \r
 231   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 232 \r
 233   return;\r
 234 }\r
 235 \r
 236 \r
 237 \r
 238 \r
 239 \r
 240 /****************************************************************************/\r
 241 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_dequeuer( void *queue_test_dequeuing_state )\r
 242 {\r
 243   struct queue_test_dequeuing_state\r
 244     *qtds;\r
 245 \r
 246   lfds601_atom_t\r
 247     *prev_user_data,\r
 248     *user_data;\r
 249 \r
 250   assert( queue_test_dequeuing_state != NULL );\r
 251 \r
 252   qtds = (struct queue_test_dequeuing_state *) queue_test_dequeuing_state;\r
 253 \r
 254   lfds601_queue_dequeue( qtds->qs, (void *) &prev_user_data );\r
 255 \r
 256   while( lfds601_queue_dequeue(qtds->qs, (void *) &user_data) )\r
 257   {\r
 258     if( user_data <= prev_user_data )\r
 259       qtds->error_flag = RAISED;\r
 260 \r
 261     prev_user_data = user_data;\r
 262   }\r
 263 \r
 264   return( (thread_return_t) EXIT_SUCCESS );\r
 265 }\r
 266 \r
 267 \r
 268 \r
 269 \r
 270 \r
 271 /****************************************************************************/\r
 272 void queue_test_enqueuing_and_dequeuing( void )\r
 273 {\r
 274   unsigned int\r
 275     loop,\r
 276     subloop,\r
 277     cpu_count;\r
 278 \r
 279   thread_state_t\r
 280     *thread_handles;\r
 281 \r
 282   struct lfds601_queue_state\r
 283     *qs;\r
 284 \r
 285   struct queue_test_enqueuing_and_dequeuing_state\r
 286     *qteds;\r
 287 \r
 288   struct lfds601_validation_info\r
 289     vi = { 0, 0 };\r
 290 \r
 291   enum lfds601_data_structure_validity\r
 292     dvs[2];\r
 293 \r
 294   internal_display_test_name( "Enqueuing and dequeuing (10 seconds)" );\r
 295 \r
 296   cpu_count = abstraction_cpu_count();\r
 297 \r
 298   lfds601_queue_new( &qs, cpu_count );\r
 299 \r
 300   qteds = malloc( sizeof(struct queue_test_enqueuing_and_dequeuing_state) * cpu_count );\r
 301 \r
 302   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 303   {\r
 304     (qteds+loop)->qs = qs;\r
 305     (qteds+loop)->thread_number = loop;\r
 306     (qteds+loop)->counter = (lfds601_atom_t) loop << (sizeof(lfds601_atom_t)*8-8);\r
 307     (qteds+loop)->cpu_count = cpu_count;\r
 308     (qteds+loop)->error_flag = LOWERED;\r
 309     (qteds+loop)->per_thread_counters = malloc( sizeof(lfds601_atom_t) * cpu_count );\r
 310 \r
 311     for( subloop = 0 ; subloop < cpu_count ; subloop++ )\r
 312       *((qteds+loop)->per_thread_counters+subloop) = 0;\r
 313   }\r
 314 \r
 315   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 316 \r
 317   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 318     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_enqueuer_and_dequeuer, qteds+loop );\r
 319 \r
 320   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 321     abstraction_thread_wait( thread_handles[loop] );\r
 322 \r
 323   free( thread_handles );\r
 324 \r
 325   lfds601_queue_query( qs, LFDS601_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 326 \r
 327   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 328     if( (qteds+loop)->error_flag == RAISED )\r
 329       dvs[0] = LFDS601_VALIDITY_INVALID_TEST_DATA;\r
 330 \r
 331   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 332     free( (qteds+loop)->per_thread_counters );\r
 333 \r
 334   free( qteds );\r
 335 \r
 336   lfds601_queue_delete( qs, NULL, NULL );\r
 337 \r
 338   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 339 \r
 340   return;\r
 341 }\r
 342 \r
 343 \r
 344 \r
 345 \r
 346 \r
 347 /****************************************************************************/\r
 348 thread_return_t CALLING_CONVENTION queue_test_internal_thread_enqueuer_and_dequeuer( void *queue_test_enqueuing_and_dequeuing_state )\r
 349 {\r
 350   struct queue_test_enqueuing_and_dequeuing_state\r
 351     *qteds;\r
 352 \r
 353   time_t\r
 354     start_time;\r
 355 \r
 356   lfds601_atom_t\r
 357     thread,\r
 358     count,\r
 359     user_data;\r
 360 \r
 361   assert( queue_test_enqueuing_and_dequeuing_state != NULL );\r
 362 \r
 363   qteds = (struct queue_test_enqueuing_and_dequeuing_state *) queue_test_enqueuing_and_dequeuing_state;\r
 364 \r
 365   time( &start_time );\r
 366 \r
 367   while( time(NULL) < start_time + 10 )\r
 368   {\r
 369     lfds601_queue_enqueue( qteds->qs, (void *) (qteds->counter++) );\r
 370     lfds601_queue_dequeue( qteds->qs, (void *) &user_data );\r
 371 \r
 372     thread = user_data >> (sizeof(lfds601_atom_t)*8-8);\r
 373     count = (user_data << 8) >> 8;\r
 374 \r
 375     if( thread >= qteds->cpu_count )\r
 376       qteds->error_flag = RAISED;\r
 377     else\r
 378     {\r
 379       if( count < qteds->per_thread_counters[thread] )\r
 380         qteds->error_flag = RAISED;\r
 381 \r
 382       if( count >= qteds->per_thread_counters[thread] )\r
 383         qteds->per_thread_counters[thread] = count+1;\r
 384     }\r
 385   }\r
 386 \r
 387   return( (thread_return_t) EXIT_SUCCESS );\r
 388 }\r
 389 \r
 390 \r
 391 \r
 392 \r
 393 \r
 394 /****************************************************************************/\r
 395 void queue_test_rapid_enqueuing_and_dequeuing( void )\r
 396 {\r
 397   unsigned int\r
 398     loop,\r
 399     cpu_count;\r
 400 \r
 401   thread_state_t\r
 402     *thread_handles;\r
 403 \r
 404   struct lfds601_queue_state\r
 405     *qs;\r
 406 \r
 407   struct queue_test_rapid_enqueuing_and_dequeuing_state\r
 408     *qtreds;\r
 409 \r
 410   struct lfds601_validation_info\r
 411     vi = { 50000, 50000 };\r
 412 \r
 413   lfds601_atom_t\r
 414     user_data,\r
 415     thread,\r
 416     count,\r
 417     *per_thread_counters;\r
 418 \r
 419   enum lfds601_data_structure_validity\r
 420     dvs[2];\r
 421 \r
 422   internal_display_test_name( "Rapid enqueuing and dequeuing (10 seconds)" );\r
 423 \r
 424   cpu_count = abstraction_cpu_count();\r
 425 \r
 426   lfds601_queue_new( &qs, 100000 );\r
 427 \r
 428   for( loop = 0 ; loop < 50000 ; loop++ )\r
 429     lfds601_queue_enqueue( qs, NULL );\r
 430 \r
 431   qtreds = malloc( sizeof(struct queue_test_rapid_enqueuing_and_dequeuing_state) * cpu_count );\r
 432 \r
 433   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 434   {\r
 435     (qtreds+loop)->qs = qs;\r
 436     (qtreds+loop)->counter = (lfds601_atom_t) loop << (sizeof(lfds601_atom_t)*8-8);\r
 437   }\r
 438 \r
 439   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 440 \r
 441   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 442     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_rapid_enqueuer_and_dequeuer, qtreds+loop );\r
 443 \r
 444   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 445     abstraction_thread_wait( thread_handles[loop] );\r
 446 \r
 447   free( thread_handles );\r
 448 \r
 449   lfds601_queue_query( qs, LFDS601_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 450 \r
 451   // TRD : now check results\r
 452   per_thread_counters = malloc( sizeof(lfds601_atom_t) * cpu_count );\r
 453 \r
 454   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 455     *(per_thread_counters+loop) = 0;\r
 456 \r
 457   while( dvs[0] == LFDS601_VALIDITY_VALID and dvs[1] == LFDS601_VALIDITY_VALID and lfds601_queue_dequeue(qs, (void *) &user_data) )\r
 458   {\r
 459     thread = user_data >> (sizeof(lfds601_atom_t)*8-8);\r
 460     count = (user_data << 8) >> 8;\r
 461 \r
 462     if( thread >= cpu_count )\r
 463     {\r
 464       dvs[0] = LFDS601_VALIDITY_INVALID_TEST_DATA;\r
 465       break;\r
 466     }\r
 467 \r
 468     if( per_thread_counters[thread] == 0 )\r
 469       per_thread_counters[thread] = count;\r
 470 \r
 471     if( count < per_thread_counters[thread] )\r
 472       dvs[0] = LFDS601_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 473 \r
 474     if( count >= per_thread_counters[thread] )\r
 475       per_thread_counters[thread] = count+1;\r
 476   }\r
 477 \r
 478   free( per_thread_counters );\r
 479 \r
 480   free( qtreds );\r
 481 \r
 482   lfds601_queue_delete( qs, NULL, NULL );\r
 483 \r
 484   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 485 \r
 486   return;\r
 487 }\r
 488 \r
 489 \r
 490 \r
 491 \r
 492 \r
 493 /****************************************************************************/\r
 494 thread_return_t CALLING_CONVENTION queue_test_internal_thread_rapid_enqueuer_and_dequeuer( void *queue_test_rapid_enqueuing_and_dequeuing_state )\r
 495 {\r
 496   struct queue_test_rapid_enqueuing_and_dequeuing_state\r
 497     *qtreds;\r
 498 \r
 499   time_t\r
 500     start_time;\r
 501 \r
 502   lfds601_atom_t\r
 503     user_data;\r
 504 \r
 505   assert( queue_test_rapid_enqueuing_and_dequeuing_state != NULL );\r
 506 \r
 507   qtreds = (struct queue_test_rapid_enqueuing_and_dequeuing_state *) queue_test_rapid_enqueuing_and_dequeuing_state;\r
 508 \r
 509   time( &start_time );\r
 510 \r
 511   while( time(NULL) < start_time + 10 )\r
 512   {\r
 513     lfds601_queue_enqueue( qtreds->qs, (void *) (qtreds->counter++) );\r
 514     lfds601_queue_dequeue( qtreds->qs, (void *) &user_data );\r
 515   }\r
 516 \r
 517   return( (thread_return_t) EXIT_SUCCESS );\r
 518 }\r
 519 \r