pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.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_lfds611_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 lfds611_queue_state\r
  37     *qs;\r
  38 \r
  39   struct queue_test_enqueuing_state\r
  40     *qtes;\r
  41 \r
  42   lfds611_atom_t\r
  43     user_data,\r
  44     thread,\r
  45     count,\r
  46     *per_thread_counters;\r
  47 \r
  48   struct lfds611_validation_info\r
  49     vi = { 1000000, 1000000 };\r
  50 \r
  51   enum lfds611_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   lfds611_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 = (lfds611_atom_t) loop << (sizeof(lfds611_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   lfds611_queue_query( qs, LFDS611_QUEUE_QUERY_VALIDATE, &vi, dvs );\r
  98 \r
  99   per_thread_counters = malloc( sizeof(lfds611_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] == LFDS611_VALIDITY_VALID and dvs[1] == LFDS611_VALIDITY_VALID and lfds611_queue_dequeue(qs, (void *) &user_data) )\r
 105   {\r
 106     thread = user_data >> (sizeof(lfds611_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] = LFDS611_VALIDITY_INVALID_TEST_DATA;\r
 112       break;\r
 113     }\r
 114 \r
 115     if( count < per_thread_counters[thread] )\r
 116       dvs[0] = LFDS611_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 117 \r
 118     if( count > per_thread_counters[thread] )\r
 119       dvs[0] = LFDS611_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   lfds611_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   lfds611_queue_use( qtes->qs );\r
 149 \r
 150   // TRD : top byte of counter is already our thread number\r
 151   while( lfds611_queue_enqueue(qtes->qs, (void *) qtes->counter++) );\r
 152 \r
 153   return( (thread_return_t) EXIT_SUCCESS );\r
 154 }\r
 155 \r
 156 \r
 157 \r
 158 \r
 159 \r
 160 /****************************************************************************/\r
 161 void queue_test_dequeuing( void )\r
 162 {\r
 163   unsigned int\r
 164     loop,\r
 165     cpu_count;\r
 166 \r
 167   thread_state_t\r
 168     *thread_handles;\r
 169 \r
 170   struct lfds611_queue_state\r
 171     *qs;\r
 172 \r
 173   struct queue_test_dequeuing_state\r
 174     *qtds;\r
 175 \r
 176   struct lfds611_validation_info\r
 177     vi = { 0, 0 };\r
 178 \r
 179   enum lfds611_data_structure_validity\r
 180     dvs[2];\r
 181 \r
 182   /* TRD : create a queue with 1,000,000 elements\r
 183 \r
 184            use a single thread to enqueue every element\r
 185            each elements user data is an incrementing counter\r
 186 \r
 187            then run one thread per CPU\r
 188            where each busy-works dequeuing\r
 189 \r
 190            when an element is dequeued, we check (on a per-thread basis) the\r
 191            value deqeued is greater than the element previously dequeued\r
 192   */\r
 193 \r
 194   internal_display_test_name( "Dequeuing" );\r
 195 \r
 196   cpu_count = abstraction_cpu_count();\r
 197 \r
 198   lfds611_queue_new( &qs, 1000000 );\r
 199 \r
 200   for( loop = 0 ; loop < 1000000 ; loop++ )\r
 201     lfds611_queue_enqueue( qs, (void *) (lfds611_atom_t) loop );\r
 202 \r
 203   qtds = malloc( sizeof(struct queue_test_dequeuing_state) * cpu_count );\r
 204 \r
 205   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 206   {\r
 207     (qtds+loop)->qs = qs;\r
 208     (qtds+loop)->error_flag = LOWERED;\r
 209   }\r
 210 \r
 211   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 212 \r
 213   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 214     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_dequeuer, qtds+loop );\r
 215 \r
 216   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 217     abstraction_thread_wait( thread_handles[loop] );\r
 218 \r
 219   free( thread_handles );\r
 220 \r
 221   // TRD : check queue is empty\r
 222   lfds611_queue_query( qs, LFDS611_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 223 \r
 224   // TRD : check for raised error flags\r
 225   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 226     if( (qtds+loop)->error_flag == RAISED )\r
 227       dvs[0] = LFDS611_VALIDITY_INVALID_TEST_DATA;\r
 228 \r
 229   free( qtds );\r
 230 \r
 231   lfds611_queue_delete( qs, NULL, NULL );\r
 232 \r
 233   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 234 \r
 235   return;\r
 236 }\r
 237 \r
 238 \r
 239 \r
 240 \r
 241 \r
 242 /****************************************************************************/\r
 243 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_dequeuer( void *queue_test_dequeuing_state )\r
 244 {\r
 245   struct queue_test_dequeuing_state\r
 246     *qtds;\r
 247 \r
 248   lfds611_atom_t\r
 249     *prev_user_data,\r
 250     *user_data;\r
 251 \r
 252   assert( queue_test_dequeuing_state != NULL );\r
 253 \r
 254   qtds = (struct queue_test_dequeuing_state *) queue_test_dequeuing_state;\r
 255 \r
 256   lfds611_queue_use( qtds->qs );\r
 257 \r
 258   lfds611_queue_dequeue( qtds->qs, (void *) &prev_user_data );\r
 259 \r
 260   while( lfds611_queue_dequeue(qtds->qs, (void *) &user_data) )\r
 261   {\r
 262     if( user_data <= prev_user_data )\r
 263       qtds->error_flag = RAISED;\r
 264 \r
 265     prev_user_data = user_data;\r
 266   }\r
 267 \r
 268   return( (thread_return_t) EXIT_SUCCESS );\r
 269 }\r
 270 \r
 271 \r
 272 \r
 273 \r
 274 \r
 275 /****************************************************************************/\r
 276 void queue_test_enqueuing_and_dequeuing( void )\r
 277 {\r
 278   unsigned int\r
 279     loop,\r
 280     subloop,\r
 281     cpu_count;\r
 282 \r
 283   thread_state_t\r
 284     *thread_handles;\r
 285 \r
 286   struct lfds611_queue_state\r
 287     *qs;\r
 288 \r
 289   struct queue_test_enqueuing_and_dequeuing_state\r
 290     *qteds;\r
 291 \r
 292   struct lfds611_validation_info\r
 293     vi = { 0, 0 };\r
 294 \r
 295   enum lfds611_data_structure_validity\r
 296     dvs[2];\r
 297 \r
 298   internal_display_test_name( "Enqueuing and dequeuing (10 seconds)" );\r
 299 \r
 300   cpu_count = abstraction_cpu_count();\r
 301 \r
 302   lfds611_queue_new( &qs, cpu_count );\r
 303 \r
 304   qteds = malloc( sizeof(struct queue_test_enqueuing_and_dequeuing_state) * cpu_count );\r
 305 \r
 306   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 307   {\r
 308     (qteds+loop)->qs = qs;\r
 309     (qteds+loop)->thread_number = loop;\r
 310     (qteds+loop)->counter = (lfds611_atom_t) loop << (sizeof(lfds611_atom_t)*8-8);\r
 311     (qteds+loop)->cpu_count = cpu_count;\r
 312     (qteds+loop)->error_flag = LOWERED;\r
 313     (qteds+loop)->per_thread_counters = malloc( sizeof(lfds611_atom_t) * cpu_count );\r
 314 \r
 315     for( subloop = 0 ; subloop < cpu_count ; subloop++ )\r
 316       *((qteds+loop)->per_thread_counters+subloop) = 0;\r
 317   }\r
 318 \r
 319   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 320 \r
 321   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 322     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_enqueuer_and_dequeuer, qteds+loop );\r
 323 \r
 324   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 325     abstraction_thread_wait( thread_handles[loop] );\r
 326 \r
 327   free( thread_handles );\r
 328 \r
 329   lfds611_queue_query( qs, LFDS611_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 330 \r
 331   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 332     if( (qteds+loop)->error_flag == RAISED )\r
 333       dvs[0] = LFDS611_VALIDITY_INVALID_TEST_DATA;\r
 334 \r
 335   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 336     free( (qteds+loop)->per_thread_counters );\r
 337 \r
 338   free( qteds );\r
 339 \r
 340   lfds611_queue_delete( qs, NULL, NULL );\r
 341 \r
 342   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 343 \r
 344   return;\r
 345 }\r
 346 \r
 347 \r
 348 \r
 349 \r
 350 \r
 351 /****************************************************************************/\r
 352 thread_return_t CALLING_CONVENTION queue_test_internal_thread_enqueuer_and_dequeuer( void *queue_test_enqueuing_and_dequeuing_state )\r
 353 {\r
 354   struct queue_test_enqueuing_and_dequeuing_state\r
 355     *qteds;\r
 356 \r
 357   time_t\r
 358     start_time;\r
 359 \r
 360   lfds611_atom_t\r
 361     thread,\r
 362     count,\r
 363     user_data;\r
 364 \r
 365   assert( queue_test_enqueuing_and_dequeuing_state != NULL );\r
 366 \r
 367   qteds = (struct queue_test_enqueuing_and_dequeuing_state *) queue_test_enqueuing_and_dequeuing_state;\r
 368 \r
 369   lfds611_queue_use( qteds->qs );\r
 370 \r
 371   time( &start_time );\r
 372 \r
 373   while( time(NULL) < start_time + 10 )\r
 374   {\r
 375     lfds611_queue_enqueue( qteds->qs, (void *) (qteds->counter++) );\r
 376     lfds611_queue_dequeue( qteds->qs, (void *) &user_data );\r
 377 \r
 378     thread = user_data >> (sizeof(lfds611_atom_t)*8-8);\r
 379     count = (user_data << 8) >> 8;\r
 380 \r
 381     if( thread >= qteds->cpu_count )\r
 382       qteds->error_flag = RAISED;\r
 383     else\r
 384     {\r
 385       if( count < qteds->per_thread_counters[thread] )\r
 386         qteds->error_flag = RAISED;\r
 387 \r
 388       if( count >= qteds->per_thread_counters[thread] )\r
 389         qteds->per_thread_counters[thread] = count+1;\r
 390     }\r
 391   }\r
 392 \r
 393   return( (thread_return_t) EXIT_SUCCESS );\r
 394 }\r
 395 \r
 396 \r
 397 \r
 398 \r
 399 \r
 400 /****************************************************************************/\r
 401 void queue_test_rapid_enqueuing_and_dequeuing( void )\r
 402 {\r
 403   unsigned int\r
 404     loop,\r
 405     cpu_count;\r
 406 \r
 407   thread_state_t\r
 408     *thread_handles;\r
 409 \r
 410   struct lfds611_queue_state\r
 411     *qs;\r
 412 \r
 413   struct queue_test_rapid_enqueuing_and_dequeuing_state\r
 414     *qtreds;\r
 415 \r
 416   struct lfds611_validation_info\r
 417     vi = { 50000, 50000 };\r
 418 \r
 419   lfds611_atom_t\r
 420     user_data,\r
 421     thread,\r
 422     count,\r
 423     *per_thread_counters;\r
 424 \r
 425   enum lfds611_data_structure_validity\r
 426     dvs[2];\r
 427 \r
 428   internal_display_test_name( "Rapid enqueuing and dequeuing (10 seconds)" );\r
 429 \r
 430   cpu_count = abstraction_cpu_count();\r
 431 \r
 432   lfds611_queue_new( &qs, 100000 );\r
 433 \r
 434   for( loop = 0 ; loop < 50000 ; loop++ )\r
 435     lfds611_queue_enqueue( qs, NULL );\r
 436 \r
 437   qtreds = malloc( sizeof(struct queue_test_rapid_enqueuing_and_dequeuing_state) * cpu_count );\r
 438 \r
 439   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 440   {\r
 441     (qtreds+loop)->qs = qs;\r
 442     (qtreds+loop)->counter = (lfds611_atom_t) loop << (sizeof(lfds611_atom_t)*8-8);\r
 443   }\r
 444 \r
 445   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );\r
 446 \r
 447   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 448     abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_rapid_enqueuer_and_dequeuer, qtreds+loop );\r
 449 \r
 450   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 451     abstraction_thread_wait( thread_handles[loop] );\r
 452 \r
 453   free( thread_handles );\r
 454 \r
 455   lfds611_queue_query( qs, LFDS611_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );\r
 456 \r
 457   // TRD : now check results\r
 458   per_thread_counters = malloc( sizeof(lfds611_atom_t) * cpu_count );\r
 459 \r
 460   for( loop = 0 ; loop < cpu_count ; loop++ )\r
 461     *(per_thread_counters+loop) = 0;\r
 462 \r
 463   while( dvs[0] == LFDS611_VALIDITY_VALID and dvs[1] == LFDS611_VALIDITY_VALID and lfds611_queue_dequeue(qs, (void *) &user_data) )\r
 464   {\r
 465     thread = user_data >> (sizeof(lfds611_atom_t)*8-8);\r
 466     count = (user_data << 8) >> 8;\r
 467 \r
 468     if( thread >= cpu_count )\r
 469     {\r
 470       dvs[0] = LFDS611_VALIDITY_INVALID_TEST_DATA;\r
 471       break;\r
 472     }\r
 473 \r
 474     if( per_thread_counters[thread] == 0 )\r
 475       per_thread_counters[thread] = count;\r
 476 \r
 477     if( count < per_thread_counters[thread] )\r
 478       dvs[0] = LFDS611_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;\r
 479 \r
 480     if( count >= per_thread_counters[thread] )\r
 481       per_thread_counters[thread] = count+1;\r
 482   }\r
 483 \r
 484   free( per_thread_counters );\r
 485 \r
 486   free( qtreds );\r
 487 \r
 488   lfds611_queue_delete( qs, NULL, NULL );\r
 489 \r
 490   internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );\r
 491 \r
 492   return;\r
 493 }\r
 494 \r
 495 \r
 496 \r
 497 \r
 498 \r
 499 /****************************************************************************/\r
 500 thread_return_t CALLING_CONVENTION queue_test_internal_thread_rapid_enqueuer_and_dequeuer( void *queue_test_rapid_enqueuing_and_dequeuing_state )\r
 501 {\r
 502   struct queue_test_rapid_enqueuing_and_dequeuing_state\r
 503     *qtreds;\r
 504 \r
 505   time_t\r
 506     start_time;\r
 507 \r
 508   lfds611_atom_t\r
 509     user_data;\r
 510 \r
 511   assert( queue_test_rapid_enqueuing_and_dequeuing_state != NULL );\r
 512 \r
 513   qtreds = (struct queue_test_rapid_enqueuing_and_dequeuing_state *) queue_test_rapid_enqueuing_and_dequeuing_state;\r
 514 \r
 515   lfds611_queue_use( qtreds->qs );\r
 516 \r
 517   time( &start_time );\r
 518 \r
 519   while( time(NULL) < start_time + 10 )\r
 520   {\r
 521     lfds611_queue_enqueue( qtreds->qs, (void *) (qtreds->counter++) );\r
 522     lfds611_queue_dequeue( qtreds->qs, (void *) &user_data );\r
 523   }\r
 524 \r
 525   return( (thread_return_t) EXIT_SUCCESS );\r
 526 }\r
 527 \r