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