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

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