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