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 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;
  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 }
  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 }
 103 static inline void gl_thread_yield (void)
 104 {
 105   sched_yield ();
 106 }
 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;
 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 }
 122 static inline void gl_thread_join (gl_thread_t thread)
 123 {
 124   if (!pth_join (thread, NULL))
 125     abort ();
 126 }
 127 static inline void gl_thread_yield (void)
 128 {
 129   pth_yield (NULL);
 130 }
 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;
 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 }
 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 }
 152 static inline void gl_thread_yield (void)
 153 {
 154   thr_yield ();
 155 }
 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; };
 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 }
 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 }
 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 }
 199 static inline void gl_thread_yield (void)
 200 {
 201   Sleep (0);
 202 }
 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
 219 random_account (void)
 220 {
 221   return ((unsigned int) rand() >> 3) % ACCOUNT_COUNT;
 222 }
 223
 224 static 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
 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 *
 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
 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
 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 *
 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
 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
 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 *
 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 *
 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
 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;
 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 *
 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
 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
 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
 686 main ()
 687 {
 688   return 77;
 689 }
 690
 691 #endif