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