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

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