]> pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.0/test/src/test_stack.c
Initial import (all versions, including the new 7.1.0)
[liblfds] / liblfds / liblfds6.1.0 / test / src / test_stack.c
1 #include "internal.h"
2
3
4
5
6
7 /****************************************************************************/
8 void test_lfds610_stack( void )
9 {
10   printf( "\n"
11           "Stack Tests\n"
12           "===========\n" );
13
14   stack_test_internal_popping();
15   stack_test_internal_pushing();
16   stack_test_internal_popping_and_pushing();
17   stack_test_internal_rapid_popping_and_pushing();
18
19   return;
20 }
21
22
23
24
25
26 /****************************************************************************/
27 void stack_test_internal_popping( void )
28 {
29   unsigned int
30     loop,
31     *found_count,
32     cpu_count;
33
34   lfds610_atom_t
35     count;
36
37   thread_state_t
38     *thread_handles;
39
40   enum lfds610_data_structure_validity
41     dvs = LFDS610_VALIDITY_VALID;
42
43   struct lfds610_stack_state
44     *ss;
45
46   struct stack_test_popping_state
47     *stps;
48
49   /* TRD : we create a stack with 1,000,000 elements
50
51            we then populate the stack, where each element is
52            set to contain a void pointer which is its element number
53
54            we then run one thread per CPU
55            where each thread loops, popping as quickly as possible
56            each popped element is pushed onto a thread-local stack
57
58            the threads run till the source stack is empty
59
60            we then check the thread-local stacks
61            we should find we have every element
62
63            then tidy up
64   */
65
66   internal_display_test_name( "Popping" );
67
68   cpu_count = abstraction_cpu_count();
69
70   lfds610_stack_new( &ss, 1000000 );
71
72   for( loop = 0 ; loop < 1000000 ; loop++ )
73     lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
74
75   stps = malloc( sizeof(struct stack_test_popping_state) * cpu_count );
76   for( loop = 0 ; loop < cpu_count ; loop++ )
77   {
78     (stps+loop)->ss = ss;
79     lfds610_stack_new( &(stps+loop)->ss_thread_local, 1000000 );
80   }
81
82   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
83
84   for( loop = 0 ; loop < cpu_count ; loop++ )
85     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping, stps+loop );
86
87   for( loop = 0 ; loop < cpu_count ; loop++ )
88     abstraction_thread_wait( thread_handles[loop] );
89
90   free( thread_handles );
91
92   // TRD : now we check the thread-local stacks
93   found_count = malloc( sizeof(unsigned int) * 1000000 );
94   for( loop = 0 ; loop < 1000000 ; loop++ )
95     *(found_count+loop) = 0;
96
97   for( loop = 0 ; loop < cpu_count ; loop++ )
98     while( lfds610_stack_pop((stps+loop)->ss_thread_local, (void **) &count) )
99       (*(found_count+count))++;
100
101   for( loop = 0 ; loop < 1000000 and dvs == LFDS610_VALIDITY_VALID ; loop++ )
102   {
103     if( *(found_count+loop) == 0 )
104       dvs = LFDS610_VALIDITY_INVALID_MISSING_ELEMENTS;
105
106     if( *(found_count+loop) > 1 )
107       dvs = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
108   }
109
110   // TRD : cleanup
111   free( found_count );
112   for( loop = 0 ; loop < cpu_count ; loop++ )
113     lfds610_stack_delete( (stps+loop)->ss_thread_local, NULL, NULL );
114   free( stps );
115   lfds610_stack_delete( ss, NULL, NULL );
116
117   // TRD : print the test result
118   internal_display_test_result( 1, "stack", dvs );
119
120   return;
121 }
122
123
124
125
126
127 /****************************************************************************/
128 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping( void *stack_test_popping_state )
129 {
130   struct stack_test_popping_state
131     *stps;
132
133   lfds610_atom_t
134     count;
135
136   assert( stack_test_popping_state != NULL );
137
138   stps = (struct stack_test_popping_state *) stack_test_popping_state;
139
140   lfds610_stack_use( stps->ss );
141
142   while( lfds610_stack_pop(stps->ss, (void **) &count) )
143     lfds610_stack_push( stps->ss_thread_local, (void *) count );
144
145   return( (thread_return_t) EXIT_SUCCESS );
146 }
147
148
149
150
151
152 /****************************************************************************/
153 void stack_test_internal_pushing( void )
154 {
155   unsigned int
156     loop,
157     cpu_count;
158
159   thread_state_t
160     *thread_handles;
161
162   enum lfds610_data_structure_validity
163     dvs[2];
164
165   struct stack_test_pushing_state
166     *stps;
167
168   struct lfds610_stack_state
169     *ss;
170
171   lfds610_atom_t
172     user_data,
173     thread,
174     count,
175     *per_thread_counters;
176
177   struct lfds610_validation_info
178     vi = { 1000000, 1000000 };
179
180   /* TRD : we create a stack with 1,000,000 elements
181
182            we then create one thread per CPU, where each thread
183            pushes as quickly as possible to the stack
184
185            the data pushed is a counter and a thread ID
186
187            the threads exit when the stack is full
188
189            we then validate the stack;
190
191            checking that the counts increment on a per unique ID basis
192            and that the number of elements we pop equals 1,000,000
193            (since each element has an incrementing counter which is
194             unique on a per unique ID basis, we can know we didn't lose
195             any elements)
196   */
197
198   internal_display_test_name( "Pushing" );
199
200   cpu_count = abstraction_cpu_count();
201
202   stps = malloc( sizeof(struct stack_test_pushing_state) * cpu_count );
203
204   // TRD : the main stack
205   lfds610_stack_new( &ss, 1000000 );
206
207   for( loop = 0 ; loop < cpu_count ; loop++ )
208   {
209     (stps+loop)->thread_number = (lfds610_atom_t) loop;
210     (stps+loop)->ss = ss;
211   }
212
213   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
214
215   for( loop = 0 ; loop < cpu_count ; loop++ )
216     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_pushing, stps+loop );
217
218   for( loop = 0 ; loop < cpu_count ; loop++ )
219     abstraction_thread_wait( thread_handles[loop] );
220
221   free( thread_handles );
222
223   // TRD : the stack is now fully pushed; time to verify
224   per_thread_counters = malloc( sizeof(lfds610_atom_t) * cpu_count );
225
226   for( loop = 0 ; loop < cpu_count ; loop++ )
227     *(per_thread_counters+loop) = 1000000;
228
229   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, &vi, (void *) dvs );
230
231   while( dvs[0] == LFDS610_VALIDITY_VALID and lfds610_stack_pop(ss, (void **) &user_data) )
232   {
233     thread = user_data >> (sizeof(lfds610_atom_t)*8-8);
234     count = (user_data << 8) >> 8;
235
236     if( thread >= cpu_count )
237     {
238       dvs[0] = LFDS610_VALIDITY_INVALID_TEST_DATA;
239       break;
240     }
241
242     if( count > per_thread_counters[thread] )
243       dvs[0] = LFDS610_VALIDITY_INVALID_ADDITIONAL_ELEMENTS;
244
245     if( count < per_thread_counters[thread] )
246       per_thread_counters[thread] = count-1;
247   }
248
249   // TRD : clean up
250   free( per_thread_counters );
251
252   free( stps );
253
254   lfds610_stack_delete( ss, NULL, NULL );
255
256   // TRD : print the test result
257   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
258
259   return;
260 }
261
262
263
264
265
266 /****************************************************************************/
267 thread_return_t CALLING_CONVENTION stack_test_internal_thread_pushing( void *stack_test_pushing_state )
268 {
269   struct stack_test_pushing_state
270     *stps;
271
272   lfds610_atom_t
273     counter = 0;
274
275   assert( stack_test_pushing_state != NULL );
276
277   stps = (struct stack_test_pushing_state *) stack_test_pushing_state;
278
279   lfds610_stack_use( stps->ss );
280
281   // TRD : we write (thread_number | counter), where thread_number is the top 8 bits of the lfds610_atom_t
282   while( lfds610_stack_push(stps->ss, (void **) ((stps->thread_number << (sizeof(lfds610_atom_t)*8-8)) | counter++)) );
283
284   return( (thread_return_t) EXIT_SUCCESS );
285 }
286
287
288
289
290
291 /****************************************************************************/
292 void stack_test_internal_popping_and_pushing( void )
293 {
294   unsigned int
295     loop,
296     subloop,
297     cpu_count;
298
299   thread_state_t
300     *thread_handles;
301
302   enum lfds610_data_structure_validity
303     dvs[2];
304
305   struct lfds610_stack_state
306     *ss;
307
308   struct stack_test_popping_and_pushing_state
309     *stpps;
310
311   struct lfds610_validation_info
312     vi;
313
314   /* TRD : we have two threads per CPU
315            the threads loop for ten seconds
316            the first thread pushes 100000 elements then pops 100000 elements
317            the second thread pops 100000 elements then pushes 100000 elements
318            all pushes and pops go onto the single main stack
319
320            after time is up, all threads push what they have remaining onto
321            the main stack
322
323            we then validate the main stack
324   */
325
326   internal_display_test_name( "Popping and pushing (10 seconds)" );
327
328   cpu_count = abstraction_cpu_count();
329
330   // TRD : just some initial elements so the pushing threads can start immediately
331   lfds610_stack_new( &ss, 100000 * cpu_count * 2 );
332
333   for( loop = 0 ; loop < 100000 * cpu_count ; loop++ )
334     lfds610_stack_push( ss, (void *) (lfds610_atom_t) loop );
335
336   stpps = malloc( sizeof(struct stack_test_popping_and_pushing_state) * cpu_count * 2 );
337
338   for( loop = 0 ; loop < cpu_count ; loop++ )
339   {
340     (stpps+loop)->ss = ss;
341     lfds610_stack_new( &(stpps+loop)->local_ss, 100000 );
342
343     (stpps+loop+cpu_count)->ss = ss;
344     lfds610_stack_new( &(stpps+loop+cpu_count)->local_ss, 100000 );
345
346     // TRD : fill the pushing thread stacks
347     for( subloop = 0 ; subloop < 100000 ; subloop++ )
348       lfds610_stack_push( (stpps+loop+cpu_count)->local_ss, (void *) (lfds610_atom_t) subloop );
349   }
350
351   thread_handles = malloc( sizeof(thread_state_t) * cpu_count * 2 );
352
353   for( loop = 0 ; loop < cpu_count ; loop++ )
354   {
355     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_popping_and_pushing_start_popping, stpps+loop );
356     abstraction_thread_start( &thread_handles[loop+cpu_count], loop, stack_test_internal_thread_popping_and_pushing_start_pushing, stpps+loop+cpu_count );
357   }
358
359   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
360     abstraction_thread_wait( thread_handles[loop] );
361
362   free( thread_handles );
363
364   for( loop = 0 ; loop < cpu_count * 2 ; loop++ )
365     lfds610_stack_delete( (stpps+loop)->local_ss, NULL, NULL );
366
367   free( stpps );
368
369   vi.min_elements = vi.max_elements = 100000 * cpu_count * 2;
370
371   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
372
373   lfds610_stack_delete( ss, NULL, NULL );
374
375   // TRD : print the test result
376   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
377
378   return;
379 }
380
381
382
383
384
385
386 /****************************************************************************/
387 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_popping( void *stack_test_popping_and_pushing_state )
388 {
389   struct stack_test_popping_and_pushing_state
390     *stpps;
391
392   void
393     *user_data;
394
395   time_t
396     start_time;
397
398   unsigned int
399     count;
400
401   assert( stack_test_popping_and_pushing_state != NULL );
402
403   stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
404
405   lfds610_stack_use( stpps->ss );
406   lfds610_stack_use( stpps->local_ss );
407
408   time( &start_time );
409
410   while( time(NULL) < start_time + 10 )
411   {
412     count = 0;
413
414     while( count < 100000 )
415       if( lfds610_stack_pop(stpps->ss, &user_data) )
416       {
417         lfds610_stack_push( stpps->local_ss, user_data );
418         count++;
419       }
420
421     // TRD : return our local stack to the main stack
422     while( lfds610_stack_pop(stpps->local_ss, &user_data) )
423       lfds610_stack_push( stpps->ss, user_data );
424   }
425
426   return( (thread_return_t) EXIT_SUCCESS );
427 }
428
429
430
431
432
433 /****************************************************************************/
434 thread_return_t CALLING_CONVENTION stack_test_internal_thread_popping_and_pushing_start_pushing( void *stack_test_popping_and_pushing_state )
435 {
436   struct stack_test_popping_and_pushing_state
437     *stpps;
438
439   void
440     *user_data;
441
442   time_t
443     start_time;
444
445   unsigned int
446     count;
447
448   assert( stack_test_popping_and_pushing_state != NULL );
449
450   stpps = (struct stack_test_popping_and_pushing_state *) stack_test_popping_and_pushing_state;
451
452   lfds610_stack_use( stpps->ss );
453   lfds610_stack_use( stpps->local_ss );
454
455   time( &start_time );
456
457   while( time(NULL) < start_time + 10 )
458   {
459     // TRD : return our local stack to the main stack
460     while( lfds610_stack_pop(stpps->local_ss, &user_data) )
461       lfds610_stack_push( stpps->ss, user_data );
462
463     count = 0;
464
465     while( count < 100000 )
466       if( lfds610_stack_pop(stpps->ss, &user_data) )
467       {
468         lfds610_stack_push( stpps->local_ss, user_data );
469         count++;
470       }
471   }
472
473   // TRD : now push whatever we have in our local stack
474   while( lfds610_stack_pop(stpps->local_ss, &user_data) )
475     lfds610_stack_push( stpps->ss, user_data );
476
477   return( (thread_return_t) EXIT_SUCCESS );
478 }
479
480
481
482
483
484 /****************************************************************************/
485 void stack_test_internal_rapid_popping_and_pushing( void )
486 {
487   unsigned int
488     loop,
489     cpu_count;
490
491   thread_state_t
492     *thread_handles;
493
494   struct lfds610_stack_state
495     *ss;
496
497   struct lfds610_validation_info
498     vi;
499
500   enum lfds610_data_structure_validity
501     dvs[2];
502
503   /* TRD : in these tests there is a fundamental antagonism between
504            how much checking/memory clean up that we do and the
505            likelyhood of collisions between threads in their lock-free
506            operations
507
508            the lock-free operations are very quick; if we do anything
509            much at all between operations, we greatly reduce the chance
510            of threads colliding
511
512            so we have some tests which do enough checking/clean up that
513            they can tell the stack is valid and don't leak memory
514            and here, this test now is one of those which does minimal
515            checking - in fact, the nature of the test is that you can't
516            do any real checking - but goes very quickly
517
518            what we do is create a small stack and then run one thread
519            per CPU, where each thread simply pushes and then immediately
520            pops
521
522            the test runs for ten seconds
523
524            after the test is done, the only check we do is to traverse
525            the stack, checking for loops and ensuring the number of
526            elements is correct
527   */
528
529   internal_display_test_name( "Rapid popping and pushing (10 seconds)" );
530
531   cpu_count = abstraction_cpu_count();
532
533   lfds610_stack_new( &ss, cpu_count );
534
535   thread_handles = malloc( sizeof(thread_state_t) * cpu_count );
536
537   for( loop = 0 ; loop < cpu_count ; loop++ )
538     abstraction_thread_start( &thread_handles[loop], loop, stack_test_internal_thread_rapid_popping_and_pushing, ss );
539
540   for( loop = 0 ; loop < cpu_count ; loop++ )
541     abstraction_thread_wait( thread_handles[loop] );
542
543   free( thread_handles );
544
545   vi.min_elements = 0;
546   vi.max_elements = 0;
547
548   lfds610_stack_query( ss, LFDS610_STACK_QUERY_VALIDATE, (void *) &vi, (void *) dvs );
549
550   lfds610_stack_delete( ss, NULL, NULL );
551
552   // TRD : print the test result
553   internal_display_test_result( 2, "stack", dvs[0], "stack freelist", dvs[1] );
554
555   return;
556 }
557
558
559
560
561
562 /****************************************************************************/
563 thread_return_t CALLING_CONVENTION stack_test_internal_thread_rapid_popping_and_pushing( void *stack_state )
564 {
565   struct lfds610_stack_state
566     *ss;
567
568   void
569     *user_data = NULL;
570
571   time_t
572     start_time;
573
574   assert( stack_state != NULL );
575
576   ss = (struct lfds610_stack_state *) stack_state;
577
578   lfds610_stack_use( ss );
579
580   time( &start_time );
581
582   while( time(NULL) < start_time + 10 )
583   {
584     lfds610_stack_push( ss, user_data );
585     lfds610_stack_pop( ss, &user_data );
586   }
587
588   return( (thread_return_t) EXIT_SUCCESS );
589 }
590