7 /****************************************************************************/
8 void test_lfds610_queue( void )
14 queue_test_enqueuing();
15 queue_test_dequeuing();
16 queue_test_enqueuing_and_dequeuing();
17 queue_test_rapid_enqueuing_and_dequeuing();
26 /****************************************************************************/
27 void queue_test_enqueuing( void )
36 struct lfds610_queue_state
39 struct queue_test_enqueuing_state
48 struct lfds610_validation_info
49 vi = { 1000000, 1000000 };
51 enum lfds610_data_structure_validity
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
61 when we're done, we check that all the elements are present
62 and increment on a per-thread basis
65 internal_display_test_name( "Enqueuing" );
67 cpu_count = abstraction_cpu_count();
69 lfds610_queue_new( &qs, 1000000 );
71 qtes = malloc( sizeof(struct queue_test_enqueuing_state) * cpu_count );
73 for( loop = 0 ; loop < cpu_count ; loop++ )
76 (qtes+loop)->counter = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
79 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
81 for( loop = 0 ; loop < cpu_count ; loop++ )
82 abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_enqueuer, qtes+loop );
84 for( loop = 0 ; loop < cpu_count ; loop++ )
85 abstraction_thread_wait( thread_handles[loop] );
87 free( thread_handles );
91 /* TRD : first, validate the queue
94 we expect to find element numbers increment on a per thread basis
97 lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, &vi, dvs );
99 per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
101 for( loop = 0 ; loop < cpu_count ; loop++ )
102 *(per_thread_counters+loop) = 0;
104 while( dvs[0] == LFDS610_VALIDITY_VALID and dvs[1] == LFDS610_VALIDITY_VALID and lfds610_queue_dequeue(qs, (void *) &user_data) )
106 thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
107 count = (user_data << 8) >> 8;
109 if( thread >= cpu_count )
111 dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
115 if( count < per_thread_counters[thread] )
116 dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
118 if( count > per_thread_counters[thread] )
119 dvs[0] = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
121 if( count == per_thread_counters[thread] )
122 per_thread_counters[thread]++;
125 free( per_thread_counters );
127 lfds610_queue_delete( qs, NULL, NULL );
129 internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
138 /****************************************************************************/
139 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_enqueuer( void *queue_test_enqueuing_state )
141 struct queue_test_enqueuing_state
144 assert( queue_test_enqueuing_state != NULL );
146 qtes = (struct queue_test_enqueuing_state *) queue_test_enqueuing_state;
148 lfds610_queue_use( qtes->qs );
150 // TRD : top byte of counter is already our thread number
151 while( lfds610_queue_enqueue(qtes->qs, (void *) qtes->counter++) );
153 return( (thread_return_t) EXIT_SUCCESS );
160 /****************************************************************************/
161 void queue_test_dequeuing( void )
170 struct lfds610_queue_state
173 struct queue_test_dequeuing_state
176 struct lfds610_validation_info
179 enum lfds610_data_structure_validity
182 /* TRD : create a queue with 1,000,000 elements
184 use a single thread to enqueue every element
185 each elements user data is an incrementing counter
187 then run one thread per CPU
188 where each busy-works dequeuing
190 when an element is dequeued, we check (on a per-thread basis) the
191 value deqeued is greater than the element previously dequeued
194 internal_display_test_name( "Dequeuing" );
196 cpu_count = abstraction_cpu_count();
198 lfds610_queue_new( &qs, 1000000 );
200 for( loop = 0 ; loop < 1000000 ; loop++ )
201 lfds610_queue_enqueue( qs, (void *) (lfds610_atom_t) loop );
203 qtds = malloc( sizeof(struct queue_test_dequeuing_state) * cpu_count );
205 for( loop = 0 ; loop < cpu_count ; loop++ )
207 (qtds+loop)->qs = qs;
208 (qtds+loop)->error_flag = LOWERED;
211 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
213 for( loop = 0 ; loop < cpu_count ; loop++ )
214 abstraction_thread_start( &thread_handles[loop], loop, queue_test_internal_thread_simple_dequeuer, qtds+loop );
216 for( loop = 0 ; loop < cpu_count ; loop++ )
217 abstraction_thread_wait( thread_handles[loop] );
219 free( thread_handles );
221 // TRD : check queue is empty
222 lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
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;
231 lfds610_queue_delete( qs, NULL, NULL );
233 internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
242 /****************************************************************************/
243 thread_return_t CALLING_CONVENTION queue_test_internal_thread_simple_dequeuer( void *queue_test_dequeuing_state )
245 struct queue_test_dequeuing_state
252 assert( queue_test_dequeuing_state != NULL );
254 qtds = (struct queue_test_dequeuing_state *) queue_test_dequeuing_state;
256 lfds610_queue_use( qtds->qs );
258 lfds610_queue_dequeue( qtds->qs, (void *) &prev_user_data );
260 while( lfds610_queue_dequeue(qtds->qs, (void *) &user_data) )
262 if( user_data <= prev_user_data )
263 qtds->error_flag = RAISED;
265 prev_user_data = user_data;
268 return( (thread_return_t) EXIT_SUCCESS );
275 /****************************************************************************/
276 void queue_test_enqueuing_and_dequeuing( void )
286 struct lfds610_queue_state
289 struct queue_test_enqueuing_and_dequeuing_state
292 struct lfds610_validation_info
295 enum lfds610_data_structure_validity
298 internal_display_test_name( "Enqueuing and dequeuing (10 seconds)" );
300 cpu_count = abstraction_cpu_count();
302 lfds610_queue_new( &qs, cpu_count );
304 qteds = malloc( sizeof(struct queue_test_enqueuing_and_dequeuing_state) * cpu_count );
306 for( loop = 0 ; loop < cpu_count ; loop++ )
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 );
315 for( subloop = 0 ; subloop < cpu_count ; subloop++ )
316 *((qteds+loop)->per_thread_counters+subloop) = 0;
319 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
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 );
324 for( loop = 0 ; loop < cpu_count ; loop++ )
325 abstraction_thread_wait( thread_handles[loop] );
327 free( thread_handles );
329 lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
331 for( loop = 0 ; loop < cpu_count ; loop++ )
332 if( (qteds+loop)->error_flag == RAISED )
333 dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
335 for( loop = 0 ; loop < cpu_count ; loop++ )
336 free( (qteds+loop)->per_thread_counters );
340 lfds610_queue_delete( qs, NULL, NULL );
342 internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
351 /****************************************************************************/
352 thread_return_t CALLING_CONVENTION queue_test_internal_thread_enqueuer_and_dequeuer( void *queue_test_enqueuing_and_dequeuing_state )
354 struct queue_test_enqueuing_and_dequeuing_state
365 assert( queue_test_enqueuing_and_dequeuing_state != NULL );
367 qteds = (struct queue_test_enqueuing_and_dequeuing_state *) queue_test_enqueuing_and_dequeuing_state;
369 lfds610_queue_use( qteds->qs );
373 while( time(NULL) < start_time + 10 )
375 lfds610_queue_enqueue( qteds->qs, (void *) (qteds->counter++) );
376 lfds610_queue_dequeue( qteds->qs, (void *) &user_data );
378 thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
379 count = (user_data << 8) >> 8;
381 if( thread >= qteds->cpu_count )
382 qteds->error_flag = RAISED;
385 if( count < qteds->per_thread_counters[thread] )
386 qteds->error_flag = RAISED;
388 if( count >= qteds->per_thread_counters[thread] )
389 qteds->per_thread_counters[thread] = count+1;
393 return( (thread_return_t) EXIT_SUCCESS );
400 /****************************************************************************/
401 void queue_test_rapid_enqueuing_and_dequeuing( void )
410 struct lfds610_queue_state
413 struct queue_test_rapid_enqueuing_and_dequeuing_state
416 struct lfds610_validation_info
417 vi = { 50000, 50000 };
423 *per_thread_counters;
425 enum lfds610_data_structure_validity
428 internal_display_test_name( "Rapid enqueuing and dequeuing (10 seconds)" );
430 cpu_count = abstraction_cpu_count();
432 lfds610_queue_new( &qs, 100000 );
434 for( loop = 0 ; loop < 50000 ; loop++ )
435 lfds610_queue_enqueue( qs, NULL );
437 qtreds = malloc( sizeof(struct queue_test_rapid_enqueuing_and_dequeuing_state) * cpu_count );
439 for( loop = 0 ; loop < cpu_count ; loop++ )
441 (qtreds+loop)->qs = qs;
442 (qtreds+loop)->counter = (lfds610_atom_t) loop << (sizeof(lfds610_atom_t)*8-8);
445 thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
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 );
450 for( loop = 0 ; loop < cpu_count ; loop++ )
451 abstraction_thread_wait( thread_handles[loop] );
453 free( thread_handles );
455 lfds610_queue_query( qs, LFDS610_QUEUE_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
457 // TRD : now check results
458 per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
460 for( loop = 0 ; loop < cpu_count ; loop++ )
461 *(per_thread_counters+loop) = 0;
463 while( dvs[0] == LFDS610_VALIDITY_VALID and dvs[1] == LFDS610_VALIDITY_VALID and lfds610_queue_dequeue(qs, (void *) &user_data) )
465 thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
466 count = (user_data << 8) >> 8;
468 if( thread >= cpu_count )
470 dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
474 if( per_thread_counters[thread] == 0 )
475 per_thread_counters[thread] = count;
477 if( count < per_thread_counters[thread] )
478 dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
480 if( count >= per_thread_counters[thread] )
481 per_thread_counters[thread] = count+1;
484 free( per_thread_counters );
488 lfds610_queue_delete( qs, NULL, NULL );
490 internal_display_test_result( 2, "queue", dvs[0], "queue freelist", dvs[1] );
499 /****************************************************************************/
500 thread_return_t CALLING_CONVENTION queue_test_internal_thread_rapid_enqueuer_and_dequeuer( void *queue_test_rapid_enqueuing_and_dequeuing_state )
502 struct queue_test_rapid_enqueuing_and_dequeuing_state
511 assert( queue_test_rapid_enqueuing_and_dequeuing_state != NULL );
513 qtreds = (struct queue_test_rapid_enqueuing_and_dequeuing_state *) queue_test_rapid_enqueuing_and_dequeuing_state;
515 lfds610_queue_use( qtreds->qs );
519 while( time(NULL) < start_time + 10 )
521 lfds610_queue_enqueue( qtreds->qs, (void *) (qtreds->counter++) );
522 lfds610_queue_dequeue( qtreds->qs, (void *) &user_data );
525 return( (thread_return_t) EXIT_SUCCESS );