* MODULES.html.sh: Add include_next.
[gnulib.git] / tests / test-lock.c
1 /* Test of locking in multithreaded situations.
2    Copyright (C) 2005 Free Software Foundation, Inc.
3
4    This program is free software; you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation; either version 2, or (at your option)
7    any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU General Public License for more details.
13
14    You should have received a copy of the GNU General Public License
15    along with this program; if not, write to the Free Software Foundation,
16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
17
18 /* Written by Bruno Haible <bruno@clisp.org>, 2005.  */
19
20 #include <config.h>
21
22 #if USE_POSIX_THREADS || USE_SOLARIS_THREADS || USE_PTH_THREADS || USE_WIN32_THREADS
23
24 #if USE_POSIX_THREADS
25 # define TEST_POSIX_THREADS 1
26 #endif
27 #if USE_SOLARIS_THREADS
28 # define TEST_SOLARIS_THREADS 1
29 #endif
30 #if USE_PTH_THREADS
31 # define TEST_PTH_THREADS 1
32 #endif
33 #if USE_WIN32_THREADS
34 # define TEST_WIN32_THREADS 1
35 #endif
36
37 /* Whether to enable locking.
38    Uncomment this to get a test program without locking, to verify that
39    it crashes.  */
40 #define ENABLE_LOCKING 1
41
42 /* Which tests to perform.
43    Uncomment some of these, to verify that all tests crash if no locking
44    is enabled.  */
45 #define DO_TEST_LOCK 1
46 #define DO_TEST_RWLOCK 1
47 #define DO_TEST_RECURSIVE_LOCK 1
48 #define DO_TEST_ONCE 1
49
50 /* Whether to help the scheduler through explicit yield().
51    Uncomment this to see if the operating system has a fair scheduler.  */
52 #define EXPLICIT_YIELD 1
53
54 /* Whether to print debugging messages.  */
55 #define ENABLE_DEBUGGING 0
56
57 /* Number of simultaneous threads.  */
58 #define THREAD_COUNT 10
59
60 /* Number of operations performed in each thread.
61    This is quite high, because with a smaller count, say 5000, we often get
62    an "OK" result even without ENABLE_LOCKING (on Linux/x86).  */
63 #define REPEAT_COUNT 50000
64
65 #include <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68
69 #if !ENABLE_LOCKING
70 # undef USE_POSIX_THREADS
71 # undef USE_SOLARIS_THREADS
72 # undef USE_PTH_THREADS
73 # undef USE_WIN32_THREADS
74 #endif
75 #include "lock.h"
76
77 #if ENABLE_DEBUGGING
78 # define dbgprintf printf
79 #else
80 # define dbgprintf if (0) printf
81 #endif
82
83 #if TEST_POSIX_THREADS
84 # include <pthread.h>
85 # include <sched.h>
86 typedef pthread_t gl_thread_t;
87 static inline gl_thread_t gl_thread_create (void * (*func) (void *), void *arg)
88 {
89   pthread_t thread;
90   if (pthread_create (&thread, NULL, func, arg) != 0)
91     abort ();
92   return thread;
93 }
94 static inline void gl_thread_join (gl_thread_t thread)
95 {
96   void *retval;
97   if (pthread_join (thread, &retval) != 0)
98     abort ();
99 }
100 static inline void gl_thread_yield (void)
101 {
102   sched_yield ();
103 }
104 static inline void * gl_thread_self (void)
105 {
106   return (void *) pthread_self ();
107 }
108 #endif
109 #if TEST_PTH_THREADS
110 # include <pth.h>
111 typedef pth_t gl_thread_t;
112 static inline gl_thread_t gl_thread_create (void * (*func) (void *), void *arg)
113 {
114   pth_t thread = pth_spawn (NULL, func, arg);
115   if (thread == NULL)
116     abort ();
117   return thread;
118 }
119 static inline void gl_thread_join (gl_thread_t thread)
120 {
121   if (!pth_join (thread, NULL))
122     abort ();
123 }
124 static inline void gl_thread_yield (void)
125 {
126   pth_yield (NULL);
127 }
128 static inline void * gl_thread_self (void)
129 {
130   return pth_self ();
131 }
132 #endif
133 #if TEST_SOLARIS_THREADS
134 # include <thread.h>
135 typedef thread_t gl_thread_t;
136 static inline gl_thread_t gl_thread_create (void * (*func) (void *), void *arg)
137 {
138   thread_t thread;
139   if (thr_create (NULL, 0, func, arg, 0, &thread) != 0)
140     abort ();
141   return thread;
142 }
143 static inline void gl_thread_join (gl_thread_t thread)
144 {
145   void *retval;
146   if (thr_join (thread, NULL, &retval) != 0)
147     abort ();
148 }
149 static inline void gl_thread_yield (void)
150 {
151   thr_yield ();
152 }
153 static inline void * gl_thread_self (void)
154 {
155   return (void *) thr_self ();
156 }
157 #endif
158 #if TEST_WIN32_THREADS
159 # include <windows.h>
160 typedef HANDLE gl_thread_t;
161 /* Use a wrapper function, instead of adding WINAPI through a cast.  */
162 struct wrapper_args { void * (*func) (void *); void *arg; };
163 static DWORD WINAPI wrapper_func (void *varg)
164 {
165   struct wrapper_args *warg = (struct wrapper_args *)varg;
166   void * (*func) (void *) = warg->func;
167   void *arg = warg->arg;
168   free (warg);
169   func (arg);
170   return 0;
171 }
172 static inline gl_thread_t gl_thread_create (void * (*func) (void *), void *arg)
173 {
174   struct wrapper_args *warg =
175     (struct wrapper_args *) malloc (sizeof (struct wrapper_args));
176   if (warg == NULL)
177     abort ();
178   warg->func = func;
179   warg->arg = arg;
180   {
181     DWORD thread_id;
182     HANDLE thread =
183       CreateThread (NULL, 100000, wrapper_func, warg, 0, &thread_id);
184     if (thread == NULL)
185       abort ();
186     return thread;
187   }
188 }
189 static inline void gl_thread_join (gl_thread_t thread)
190 {
191   if (WaitForSingleObject (thread, INFINITE) == WAIT_FAILED)
192     abort ();
193   if (!CloseHandle (thread))
194     abort ();
195 }
196 static inline void gl_thread_yield (void)
197 {
198   Sleep (0);
199 }
200 static inline void * gl_thread_self (void)
201 {
202   return (void *) GetCurrentThreadId ();
203 }
204 #endif
205 #if EXPLICIT_YIELD
206 # define yield() gl_thread_yield ()
207 #else
208 # define yield()
209 #endif
210
211 #define ACCOUNT_COUNT 4
212
213 static int account[ACCOUNT_COUNT];
214
215 static int
216 random_account (void)
217 {
218   return ((unsigned int) rand() >> 3) % ACCOUNT_COUNT;
219 }
220
221 static void
222 check_accounts (void)
223 {
224   int i, sum;
225
226   sum = 0;
227   for (i = 0; i < ACCOUNT_COUNT; i++)
228     sum += account[i];
229   if (sum != ACCOUNT_COUNT * 1000)
230     abort ();
231 }
232
233 /* Test normal locks by having several bank accounts and several threads
234    which shuffle around money between the accounts and another thread
235    checking that all the money is still there.  */
236
237 gl_lock_define_initialized(static, my_lock)
238
239 static void *
240 lock_mutator_thread (void *arg)
241 {
242   int repeat;
243
244   for (repeat = REPEAT_COUNT; repeat > 0; repeat--)
245     {
246       int i1, i2, value;
247
248       dbgprintf ("Mutator %p before lock\n", gl_thread_self ());
249       gl_lock_lock (my_lock);
250       dbgprintf ("Mutator %p after  lock\n", gl_thread_self ());
251
252       i1 = random_account ();
253       i2 = random_account ();
254       value = ((unsigned int) rand() >> 3) % 10;
255       account[i1] += value;
256       account[i2] -= value;
257
258       dbgprintf ("Mutator %p before unlock\n", gl_thread_self ());
259       gl_lock_unlock (my_lock);
260       dbgprintf ("Mutator %p after  unlock\n", gl_thread_self ());
261
262       dbgprintf ("Mutator %p before check lock\n", gl_thread_self ());
263       gl_lock_lock (my_lock);
264       check_accounts ();
265       gl_lock_unlock (my_lock);
266       dbgprintf ("Mutator %p after  check unlock\n", gl_thread_self ());
267
268       yield ();
269     }
270
271   dbgprintf ("Mutator %p dying.\n", gl_thread_self ());
272   return NULL;
273 }
274
275 static volatile int lock_checker_done;
276
277 static void *
278 lock_checker_thread (void *arg)
279 {
280   while (!lock_checker_done)
281     {
282       dbgprintf ("Checker %p before check lock\n", gl_thread_self ());
283       gl_lock_lock (my_lock);
284       check_accounts ();
285       gl_lock_unlock (my_lock);
286       dbgprintf ("Checker %p after  check unlock\n", gl_thread_self ());
287
288       yield ();
289     }
290
291   dbgprintf ("Checker %p dying.\n", gl_thread_self ());
292   return NULL;
293 }
294
295 void
296 test_lock (void)
297 {
298   int i;
299   gl_thread_t checkerthread;
300   gl_thread_t threads[THREAD_COUNT];
301
302   /* Initialization.  */
303   for (i = 0; i < ACCOUNT_COUNT; i++)
304     account[i] = 1000;
305   lock_checker_done = 0;
306
307   /* Spawn the threads.  */
308   checkerthread = gl_thread_create (lock_checker_thread, NULL);
309   for (i = 0; i < THREAD_COUNT; i++)
310     threads[i] = gl_thread_create (lock_mutator_thread, NULL);
311
312   /* Wait for the threads to terminate.  */
313   for (i = 0; i < THREAD_COUNT; i++)
314     gl_thread_join (threads[i]);
315   lock_checker_done = 1;
316   gl_thread_join (checkerthread);
317   check_accounts ();
318 }
319
320 /* Test read-write locks by having several bank accounts and several threads
321    which shuffle around money between the accounts and several other threads
322    that check that all the money is still there.  */
323
324 gl_rwlock_define_initialized(static, my_rwlock)
325
326 static void *
327 rwlock_mutator_thread (void *arg)
328 {
329   int repeat;
330
331   for (repeat = REPEAT_COUNT; repeat > 0; repeat--)
332     {
333       int i1, i2, value;
334
335       dbgprintf ("Mutator %p before wrlock\n", gl_thread_self ());
336       gl_rwlock_wrlock (my_rwlock);
337       dbgprintf ("Mutator %p after  wrlock\n", gl_thread_self ());
338
339       i1 = random_account ();
340       i2 = random_account ();
341       value = ((unsigned int) rand() >> 3) % 10;
342       account[i1] += value;
343       account[i2] -= value;
344
345       dbgprintf ("Mutator %p before unlock\n", gl_thread_self ());
346       gl_rwlock_unlock (my_rwlock);
347       dbgprintf ("Mutator %p after  unlock\n", gl_thread_self ());
348
349       yield ();
350     }
351
352   dbgprintf ("Mutator %p dying.\n", gl_thread_self ());
353   return NULL;
354 }
355
356 static volatile int rwlock_checker_done;
357
358 static void *
359 rwlock_checker_thread (void *arg)
360 {
361   while (!rwlock_checker_done)
362     {
363       dbgprintf ("Checker %p before check rdlock\n", gl_thread_self ());
364       gl_rwlock_rdlock (my_rwlock);
365       check_accounts ();
366       gl_rwlock_unlock (my_rwlock);
367       dbgprintf ("Checker %p after  check unlock\n", gl_thread_self ());
368
369       yield ();
370     }
371
372   dbgprintf ("Checker %p dying.\n", gl_thread_self ());
373   return NULL;
374 }
375
376 void
377 test_rwlock (void)
378 {
379   int i;
380   gl_thread_t checkerthreads[THREAD_COUNT];
381   gl_thread_t threads[THREAD_COUNT];
382
383   /* Initialization.  */
384   for (i = 0; i < ACCOUNT_COUNT; i++)
385     account[i] = 1000;
386   rwlock_checker_done = 0;
387
388   /* Spawn the threads.  */
389   for (i = 0; i < THREAD_COUNT; i++)
390     checkerthreads[i] = gl_thread_create (rwlock_checker_thread, NULL);
391   for (i = 0; i < THREAD_COUNT; i++)
392     threads[i] = gl_thread_create (rwlock_mutator_thread, NULL);
393
394   /* Wait for the threads to terminate.  */
395   for (i = 0; i < THREAD_COUNT; i++)
396     gl_thread_join (threads[i]);
397   rwlock_checker_done = 1;
398   for (i = 0; i < THREAD_COUNT; i++)
399     gl_thread_join (checkerthreads[i]);
400   check_accounts ();
401 }
402
403 /* Test recursive locks by having several bank accounts and several threads
404    which shuffle around money between the accounts (recursively) and another
405    thread checking that all the money is still there.  */
406
407 gl_recursive_lock_define_initialized(static, my_reclock)
408
409 static void
410 recshuffle (void)
411 {
412   int i1, i2, value;
413
414   dbgprintf ("Mutator %p before lock\n", gl_thread_self ());
415   gl_recursive_lock_lock (my_reclock);
416   dbgprintf ("Mutator %p after  lock\n", gl_thread_self ());
417
418   i1 = random_account ();
419   i2 = random_account ();
420   value = ((unsigned int) rand() >> 3) % 10;
421   account[i1] += value;
422   account[i2] -= value;
423
424   /* Recursive with probability 0.5.  */
425   if (((unsigned int) rand() >> 3) % 2)
426     recshuffle ();
427
428   dbgprintf ("Mutator %p before unlock\n", gl_thread_self ());
429   gl_recursive_lock_unlock (my_reclock);
430   dbgprintf ("Mutator %p after  unlock\n", gl_thread_self ());
431 }
432
433 static void *
434 reclock_mutator_thread (void *arg)
435 {
436   int repeat;
437
438   for (repeat = REPEAT_COUNT; repeat > 0; repeat--)
439     {
440       recshuffle ();
441
442       dbgprintf ("Mutator %p before check lock\n", gl_thread_self ());
443       gl_recursive_lock_lock (my_reclock);
444       check_accounts ();
445       gl_recursive_lock_unlock (my_reclock);
446       dbgprintf ("Mutator %p after  check unlock\n", gl_thread_self ());
447
448       yield ();
449     }
450
451   dbgprintf ("Mutator %p dying.\n", gl_thread_self ());
452   return NULL;
453 }
454
455 static volatile int reclock_checker_done;
456
457 static void *
458 reclock_checker_thread (void *arg)
459 {
460   while (!reclock_checker_done)
461     {
462       dbgprintf ("Checker %p before check lock\n", gl_thread_self ());
463       gl_recursive_lock_lock (my_reclock);
464       check_accounts ();
465       gl_recursive_lock_unlock (my_reclock);
466       dbgprintf ("Checker %p after  check unlock\n", gl_thread_self ());
467
468       yield ();
469     }
470
471   dbgprintf ("Checker %p dying.\n", gl_thread_self ());
472   return NULL;
473 }
474
475 void
476 test_recursive_lock (void)
477 {
478   int i;
479   gl_thread_t checkerthread;
480   gl_thread_t threads[THREAD_COUNT];
481
482   /* Initialization.  */
483   for (i = 0; i < ACCOUNT_COUNT; i++)
484     account[i] = 1000;
485   reclock_checker_done = 0;
486
487   /* Spawn the threads.  */
488   checkerthread = gl_thread_create (reclock_checker_thread, NULL);
489   for (i = 0; i < THREAD_COUNT; i++)
490     threads[i] = gl_thread_create (reclock_mutator_thread, NULL);
491
492   /* Wait for the threads to terminate.  */
493   for (i = 0; i < THREAD_COUNT; i++)
494     gl_thread_join (threads[i]);
495   reclock_checker_done = 1;
496   gl_thread_join (checkerthread);
497   check_accounts ();
498 }
499
500 /* Test once-only execution by having several threads attempt to grab a
501    once-only task simultaneously (triggered by releasing a read-write lock).  */
502
503 gl_once_define(static, fresh_once)
504 static int ready[THREAD_COUNT];
505 static gl_lock_t ready_lock[THREAD_COUNT];
506 #if ENABLE_LOCKING
507 static gl_rwlock_t fire_signal[REPEAT_COUNT];
508 #else
509 static volatile int fire_signal_state;
510 #endif
511 static gl_once_t once_control;
512 static int performed;
513 gl_lock_define_initialized(static, performed_lock)
514
515 static void
516 once_execute (void)
517 {
518   gl_lock_lock (performed_lock);
519   performed++;
520   gl_lock_unlock (performed_lock);
521 }
522
523 static void *
524 once_contender_thread (void *arg)
525 {
526   int id = (int) (long) arg;
527   int repeat;
528
529   for (repeat = 0; repeat <= REPEAT_COUNT; repeat++)
530     {
531       /* Tell the main thread that we're ready.  */
532       gl_lock_lock (ready_lock[id]);
533       ready[id] = 1;
534       gl_lock_unlock (ready_lock[id]);
535
536       if (repeat == REPEAT_COUNT)
537         break;
538
539       dbgprintf ("Contender %p waiting for signal for round %d\n",
540                  gl_thread_self (), repeat);
541 #if ENABLE_LOCKING
542       /* Wait for the signal to go.  */
543       gl_rwlock_rdlock (fire_signal[repeat]);
544       /* And don't hinder the others (if the scheduler is unfair).  */
545       gl_rwlock_unlock (fire_signal[repeat]);
546 #else
547       /* Wait for the signal to go.  */
548       while (fire_signal_state <= repeat)
549         yield ();
550 #endif
551       dbgprintf ("Contender %p got the     signal for round %d\n",
552                  gl_thread_self (), repeat);
553
554       /* Contend for execution.  */
555       gl_once (once_control, once_execute);
556     }
557
558   return NULL;
559 }
560
561 void
562 test_once (void)
563 {
564   int i, repeat;
565   gl_thread_t threads[THREAD_COUNT];
566
567   /* Initialize all variables.  */
568   for (i = 0; i < THREAD_COUNT; i++)
569     {
570       ready[i] = 0;
571       gl_lock_init (ready_lock[i]);
572     }
573 #if ENABLE_LOCKING
574   for (i = 0; i < REPEAT_COUNT; i++)
575     gl_rwlock_init (fire_signal[i]);
576 #else
577   fire_signal_state = 0;
578 #endif
579
580   /* Block all fire_signals.  */
581   for (i = REPEAT_COUNT-1; i >= 0; i--)
582     gl_rwlock_wrlock (fire_signal[i]);
583
584   /* Spawn the threads.  */
585   for (i = 0; i < THREAD_COUNT; i++)
586     threads[i] = gl_thread_create (once_contender_thread, (void *) (long) i);
587
588   for (repeat = 0; repeat <= REPEAT_COUNT; repeat++)
589     {
590       /* Wait until every thread is ready.  */
591       dbgprintf ("Main thread before synchonizing for round %d\n", repeat);
592       for (;;)
593         {
594           int ready_count = 0;
595           for (i = 0; i < THREAD_COUNT; i++)
596             {
597               gl_lock_lock (ready_lock[i]);
598               ready_count += ready[i];
599               gl_lock_unlock (ready_lock[i]);
600             }
601           if (ready_count == THREAD_COUNT)
602             break;
603           yield ();
604         }
605       dbgprintf ("Main thread after  synchonizing for round %d\n", repeat);
606
607       if (repeat > 0)
608         {
609           /* Check that exactly one thread executed the once_execute()
610              function.  */
611           if (performed != 1)
612             abort ();
613         }
614
615       if (repeat == REPEAT_COUNT)
616         break;
617
618       /* Preparation for the next round: Initialize once_control.  */
619       memcpy (&once_control, &fresh_once, sizeof (gl_once_t));
620
621       /* Preparation for the next round: Reset the performed counter.  */
622       performed = 0;
623
624       /* Preparation for the next round: Reset the ready flags.  */
625       for (i = 0; i < THREAD_COUNT; i++)
626         {
627           gl_lock_lock (ready_lock[i]);
628           ready[i] = 0;
629           gl_lock_unlock (ready_lock[i]);
630         }
631
632       /* Signal all threads simultaneously.  */
633       dbgprintf ("Main thread giving signal for round %d\n", repeat);
634 #if ENABLE_LOCKING
635       gl_rwlock_unlock (fire_signal[repeat]);
636 #else
637       fire_signal_state = repeat + 1;
638 #endif
639     }
640
641   /* Wait for the threads to terminate.  */
642   for (i = 0; i < THREAD_COUNT; i++)
643     gl_thread_join (threads[i]);
644 }
645
646 int
647 main ()
648 {
649 #if TEST_PTH_THREADS
650   if (!pth_init ())
651     abort ();
652 #endif
653
654 #if DO_TEST_LOCK
655   printf ("Starting test_lock ..."); fflush (stdout);
656   test_lock ();
657   printf (" OK\n"); fflush (stdout);
658 #endif
659 #if DO_TEST_RWLOCK
660   printf ("Starting test_rwlock ..."); fflush (stdout);
661   test_rwlock ();
662   printf (" OK\n"); fflush (stdout);
663 #endif
664 #if DO_TEST_RECURSIVE_LOCK
665   printf ("Starting test_recursive_lock ..."); fflush (stdout);
666   test_recursive_lock ();
667   printf (" OK\n"); fflush (stdout);
668 #endif
669 #if DO_TEST_ONCE
670   printf ("Starting test_once ..."); fflush (stdout);
671   test_once ();
672   printf (" OK\n"); fflush (stdout);
673 #endif
674
675   return 0;
676 }
677
678 #else
679
680 /* No multithreading available.  */
681
682 int
683 main ()
684 {
685   return 77;
686 }
687
688 #endif