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