src/native_client_sdk/src/libraries/third_party/pthreads-win32/pthread_cond_wait.c

   1 /*
   2  * pthread_cond_wait.c
   3  *
   4  * Description:
   5  * This translation unit implements condition variables and their primitives.
   6  *
   7  *
   8  * --------------------------------------------------------------------------
   9  *
  10  *      Pthreads-win32 - POSIX Threads Library for Win32
  11  *      Copyright(C) 1998 John E. Bossom
  12  *      Copyright(C) 1999,2005 Pthreads-win32 contributors
  13  *
  14  *      Contact Email: rpj@callisto.canberra.edu.au
  15  *
  16  *      The current list of contributors is contained
  17  *      in the file CONTRIBUTORS included with the source
  18  *      code distribution. The list can also be seen at the
  19  *      following World Wide Web location:
  20  *      http://sources.redhat.com/pthreads-win32/contributors.html
  21  *
  22  *      This library is free software; you can redistribute it and/or
  23  *      modify it under the terms of the GNU Lesser General Public
  24  *      License as published by the Free Software Foundation; either
  25  *      version 2 of the License, or (at your option) any later version.
  26  *
  27  *      This library is distributed in the hope that it will be useful,
  28  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  29  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  30  *      Lesser General Public License for more details.
  31  *
  32  *      You should have received a copy of the GNU Lesser General Public
  33  *      License along with this library in the file COPYING.LIB;
  34  *      if not, write to the Free Software Foundation, Inc.,
  35  *      59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  36  *
  37  * -------------------------------------------------------------
  38  * Algorithm:
  39  * The algorithm used in this implementation is that developed by
  40  * Alexander Terekhov in colaboration with Louis Thomas. The bulk
  41  * of the discussion is recorded in the file README.CV, which contains
  42  * several generations of both colaborators original algorithms. The final
  43  * algorithm used here is the one referred to as
  44  *
  45  *     Algorithm 8a / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL
  46  *
  47  * presented below in pseudo-code as it appeared:
  48  *
  49  *
  50  * given:
  51  * semBlockLock - bin.semaphore
  52  * semBlockQueue - semaphore
  53  * mtxExternal - mutex or CS
  54  * mtxUnblockLock - mutex or CS
  55  * nWaitersGone - int
  56  * nWaitersBlocked - int
  57  * nWaitersToUnblock - int
  58  *
  59  * wait( timeout ) {
  60  *
  61  *   [auto: register int result          ]     // error checking omitted
  62  *   [auto: register int nSignalsWasLeft ]
  63  *   [auto: register int nWaitersWasGone ]
  64  *
  65  *   sem_wait( semBlockLock );
  66  *   nWaitersBlocked++;
  67  *   sem_post( semBlockLock );
  68  *
  69  *   unlock( mtxExternal );
  70  *   bTimedOut = sem_wait( semBlockQueue,timeout );
  71  *
  72  *   lock( mtxUnblockLock );
  73  *   if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
  74  *     if ( bTimeout ) {                       // timeout (or canceled)
  75  *       if ( 0 != nWaitersBlocked ) {
  76  *         nWaitersBlocked--;
  77  *       }
  78  *       else {
  79  *         nWaitersGone++;                     // count spurious wakeups.
  80  *       }
  81  *     }
  82  *     if ( 0 == --nWaitersToUnblock ) {
  83  *       if ( 0 != nWaitersBlocked ) {
  84  *         sem_post( semBlockLock );           // open the gate.
  85  *         nSignalsWasLeft = 0;                // do not open the gate
  86  *                                             // below again.
  87  *       }
  88  *       else if ( 0 != (nWaitersWasGone = nWaitersGone) ) {
  89  *         nWaitersGone = 0;
  90  *       }
  91  *     }
  92  *   }
  93  *   else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or
  94  *                                             // spurious semaphore :-)
  95  *     sem_wait( semBlockLock );
  96  *     nWaitersBlocked -= nWaitersGone;     // something is going on here
  97  *                                          //  - test of timeouts? :-)
  98  *     sem_post( semBlockLock );
  99  *     nWaitersGone = 0;
 100  *   }
 101  *   unlock( mtxUnblockLock );
 102  *
 103  *   if ( 1 == nSignalsWasLeft ) {
 104  *     if ( 0 != nWaitersWasGone ) {
 105  *       // sem_adjust( semBlockQueue,-nWaitersWasGone );
 106  *       while ( nWaitersWasGone-- ) {
 107  *         sem_wait( semBlockQueue );       // better now than spurious later
 108  *       }
 109  *     } sem_post( semBlockLock );          // open the gate
 110  *   }
 111  *
 112  *   lock( mtxExternal );
 113  *
 114  *   return ( bTimedOut ) ? ETIMEOUT : 0;
 115  * }
 116  *
 117  * signal(bAll) {
 118  *
 119  *   [auto: register int result         ]
 120  *   [auto: register int nSignalsToIssue]
 121  *
 122  *   lock( mtxUnblockLock );
 123  *
 124  *   if ( 0 != nWaitersToUnblock ) {        // the gate is closed!!!
 125  *     if ( 0 == nWaitersBlocked ) {        // NO-OP
 126  *       return unlock( mtxUnblockLock );
 127  *     }
 128  *     if (bAll) {
 129  *       nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
 130  *       nWaitersBlocked = 0;
 131  *     }
 132  *     else {
 133  *       nSignalsToIssue = 1;
 134  *       nWaitersToUnblock++;
 135  *       nWaitersBlocked--;
 136  *     }
 137  *   }
 138  *   else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
 139  *     sem_wait( semBlockLock );                  // close the gate
 140  *     if ( 0 != nWaitersGone ) {
 141  *       nWaitersBlocked -= nWaitersGone;
 142  *       nWaitersGone = 0;
 143  *     }
 144  *     if (bAll) {
 145  *       nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
 146  *       nWaitersBlocked = 0;
 147  *     }
 148  *     else {
 149  *       nSignalsToIssue = nWaitersToUnblock = 1;
 150  *       nWaitersBlocked--;
 151  *     }
 152  *   }
 153  *   else { // NO-OP
 154  *     return unlock( mtxUnblockLock );
 155  *   }
 156  *
 157  *   unlock( mtxUnblockLock );
 158  *   sem_post( semBlockQueue,nSignalsToIssue );
 159  *   return result;
 160  * }
 161  * -------------------------------------------------------------
 162  *
 163  *     Algorithm 9 / IMPL_SEM,UNBLOCK_STRATEGY == UNBLOCK_ALL
 164  *
 165  * presented below in pseudo-code; basically 8a...
 166  *                                      ...BUT W/O "spurious wakes" prevention:
 167  *
 168  *
 169  * given:
 170  * semBlockLock - bin.semaphore
 171  * semBlockQueue - semaphore
 172  * mtxExternal - mutex or CS
 173  * mtxUnblockLock - mutex or CS
 174  * nWaitersGone - int
 175  * nWaitersBlocked - int
 176  * nWaitersToUnblock - int
 177  *
 178  * wait( timeout ) {
 179  *
 180  *   [auto: register int result          ]     // error checking omitted
 181  *   [auto: register int nSignalsWasLeft ]
 182  *
 183  *   sem_wait( semBlockLock );
 184  *   ++nWaitersBlocked;
 185  *   sem_post( semBlockLock );
 186  *
 187  *   unlock( mtxExternal );
 188  *   bTimedOut = sem_wait( semBlockQueue,timeout );
 189  *
 190  *   lock( mtxUnblockLock );
 191  *   if ( 0 != (nSignalsWasLeft = nWaitersToUnblock) ) {
 192  *     --nWaitersToUnblock;
 193  *   }
 194  *   else if ( INT_MAX/2 == ++nWaitersGone ) { // timeout/canceled or
 195  *                                             // spurious semaphore :-)
 196  *     sem_wait( semBlockLock );
 197  *     nWaitersBlocked -= nWaitersGone;        // something is going on here
 198  *                                             //  - test of timeouts? :-)
 199  *     sem_post( semBlockLock );
 200  *     nWaitersGone = 0;
 201  *   }
 202  *   unlock( mtxUnblockLock );
 203  *
 204  *   if ( 1 == nSignalsWasLeft ) {
 205  *     sem_post( semBlockLock );               // open the gate
 206  *   }
 207  *
 208  *   lock( mtxExternal );
 209  *
 210  *   return ( bTimedOut ) ? ETIMEOUT : 0;
 211  * }
 212  *
 213  * signal(bAll) {
 214  *
 215  *   [auto: register int result         ]
 216  *   [auto: register int nSignalsToIssue]
 217  *
 218  *   lock( mtxUnblockLock );
 219  *
 220  *   if ( 0 != nWaitersToUnblock ) {        // the gate is closed!!!
 221  *     if ( 0 == nWaitersBlocked ) {        // NO-OP
 222  *       return unlock( mtxUnblockLock );
 223  *     }
 224  *     if (bAll) {
 225  *       nWaitersToUnblock += nSignalsToIssue=nWaitersBlocked;
 226  *       nWaitersBlocked = 0;
 227  *     }
 228  *     else {
 229  *       nSignalsToIssue = 1;
 230  *       ++nWaitersToUnblock;
 231  *       --nWaitersBlocked;
 232  *     }
 233  *   }
 234  *   else if ( nWaitersBlocked > nWaitersGone ) { // HARMLESS RACE CONDITION!
 235  *     sem_wait( semBlockLock );                  // close the gate
 236  *     if ( 0 != nWaitersGone ) {
 237  *       nWaitersBlocked -= nWaitersGone;
 238  *       nWaitersGone = 0;
 239  *     }
 240  *     if (bAll) {
 241  *       nSignalsToIssue = nWaitersToUnblock = nWaitersBlocked;
 242  *       nWaitersBlocked = 0;
 243  *     }
 244  *     else {
 245  *       nSignalsToIssue = nWaitersToUnblock = 1;
 246  *       --nWaitersBlocked;
 247  *     }
 248  *   }
 249  *   else { // NO-OP
 250  *     return unlock( mtxUnblockLock );
 251  *   }
 252  *
 253  *   unlock( mtxUnblockLock );
 254  *   sem_post( semBlockQueue,nSignalsToIssue );
 255  *   return result;
 256  * }
 257  * -------------------------------------------------------------
 258  *
 259  */
 260
 261 #include "pthread.h"
 262 #include "implement.h"
 263
 264 /*
 265  * Arguments for cond_wait_cleanup, since we can only pass a
 266  * single void * to it.
 267  */
 268 typedef struct
 269 {
 270   pthread_mutex_t *mutexPtr;
 271   pthread_cond_t cv;
 272   int *resultPtr;
 273 } ptw32_cond_wait_cleanup_args_t;
 274
 275 static void PTW32_CDECL
 276 ptw32_cond_wait_cleanup (void *args)
 277 {
 278   ptw32_cond_wait_cleanup_args_t *cleanup_args =
 279     (ptw32_cond_wait_cleanup_args_t *) args;
 280   pthread_cond_t cv = cleanup_args->cv;
 281   int *resultPtr = cleanup_args->resultPtr;
 282   int nSignalsWasLeft;
 283   int result;
 284
 285   /*
 286    * Whether we got here as a result of signal/broadcast or because of
 287    * timeout on wait or thread cancellation we indicate that we are no
 288    * longer waiting. The waiter is responsible for adjusting waiters
 289    * (to)unblock(ed) counts (protected by unblock lock).
 290    */
 291   if ((result = pthread_mutex_lock (&(cv->mtxUnblockLock))) != 0)
 292     {
 293       *resultPtr = result;
 294       return;
 295     }
 296
 297   if (0 != (nSignalsWasLeft = cv->nWaitersToUnblock))
 298     {
 299       --(cv->nWaitersToUnblock);
 300     }
 301   else if (INT_MAX / 2 == ++(cv->nWaitersGone))
 302     {
 303       /* Use the non-cancellable version of sem_wait() */
 304       if (ptw32_semwait (&(cv->semBlockLock)) != 0)
 305         {
 306           *resultPtr = errno;
 307           /*
 308            * This is a fatal error for this CV,
 309            * so we deliberately don't unlock
 310            * cv->mtxUnblockLock before returning.
 311            */
 312           return;
 313         }
 314       cv->nWaitersBlocked -= cv->nWaitersGone;
 315       if (sem_post (&(cv->semBlockLock)) != 0)
 316         {
 317           *resultPtr = errno;
 318           /*
 319            * This is a fatal error for this CV,
 320            * so we deliberately don't unlock
 321            * cv->mtxUnblockLock before returning.
 322            */
 323           return;
 324         }
 325       cv->nWaitersGone = 0;
 326     }
 327
 328   if ((result = pthread_mutex_unlock (&(cv->mtxUnblockLock))) != 0)
 329     {
 330       *resultPtr = result;
 331       return;
 332     }
 333
 334   if (1 == nSignalsWasLeft)
 335     {
 336       if (sem_post (&(cv->semBlockLock)) != 0)
 337         {
 338           *resultPtr = errno;
 339           return;
 340         }
 341     }
 342
 343   /*
 344    * XSH: Upon successful return, the mutex has been locked and is owned
 345    * by the calling thread.
 346    */
 347   if ((result = pthread_mutex_lock (cleanup_args->mutexPtr)) != 0)
 348     {
 349       *resultPtr = result;
 350     }
 351 }                               /* ptw32_cond_wait_cleanup */
 352
 353 static INLINE int
 354 ptw32_cond_timedwait (pthread_cond_t * cond,
 355                       pthread_mutex_t * mutex, const struct timespec *abstime)
 356 {
 357   int result = 0;
 358   pthread_cond_t cv;
 359   ptw32_cond_wait_cleanup_args_t cleanup_args;
 360
 361   if (cond == NULL || *cond == NULL)
 362     {
 363       return EINVAL;
 364     }
 365
 366   /*
 367    * We do a quick check to see if we need to do more work
 368    * to initialise a static condition variable. We check
 369    * again inside the guarded section of ptw32_cond_check_need_init()
 370    * to avoid race conditions.
 371    */
 372   if (*cond == PTHREAD_COND_INITIALIZER)
 373     {
 374       result = ptw32_cond_check_need_init (cond);
 375     }
 376
 377   if (result != 0 && result != EBUSY)
 378     {
 379       return result;
 380     }
 381
 382   cv = *cond;
 383
 384   /* Thread can be cancelled in sem_wait() but this is OK */
 385   if (sem_wait (&(cv->semBlockLock)) != 0)
 386     {
 387       return errno;
 388     }
 389
 390   ++(cv->nWaitersBlocked);
 391
 392   if (sem_post (&(cv->semBlockLock)) != 0)
 393     {
 394       return errno;
 395     }
 396
 397   /*
 398    * Setup this waiter cleanup handler
 399    */
 400   cleanup_args.mutexPtr = mutex;
 401   cleanup_args.cv = cv;
 402   cleanup_args.resultPtr = &result;
 403
 404 #if defined(_MSC_VER) && _MSC_VER < 1400
 405 #pragma inline_depth(0)
 406 #endif
 407   pthread_cleanup_push (ptw32_cond_wait_cleanup, (void *) &cleanup_args);
 408
 409   /*
 410    * Now we can release 'mutex' and...
 411    */
 412   if ((result = pthread_mutex_unlock (mutex)) == 0)
 413     {
 414
 415       /*
 416        * ...wait to be awakened by
 417        *              pthread_cond_signal, or
 418        *              pthread_cond_broadcast, or
 419        *              timeout, or
 420        *              thread cancellation
 421        *
 422        * Note:
 423        *
 424        *      sem_timedwait is a cancellation point,
 425        *      hence providing the mechanism for making
 426        *      pthread_cond_wait a cancellation point.
 427        *      We use the cleanup mechanism to ensure we
 428        *      re-lock the mutex and adjust (to)unblock(ed) waiters
 429        *      counts if we are cancelled, timed out or signalled.
 430        */
 431       if (sem_timedwait (&(cv->semBlockQueue), abstime) != 0)
 432         {
 433           result = errno;
 434         }
 435     }
 436
 437   /*
 438    * Always cleanup
 439    */
 440   pthread_cleanup_pop (1);
 441 #if defined(_MSC_VER) && _MSC_VER < 1400
 442 #pragma inline_depth()
 443 #endif
 444
 445   /*
 446    * "result" can be modified by the cleanup handler.
 447    */
 448   return result;
 449
 450 }                               /* ptw32_cond_timedwait */
 451
 452
 453 int
 454 pthread_cond_wait (pthread_cond_t * cond, pthread_mutex_t * mutex)
 455      /*
 456       * ------------------------------------------------------
 457       * DOCPUBLIC
 458       *      This function waits on a condition variable until
 459       *      awakened by a signal or broadcast.
 460       *
 461       *      Caller MUST be holding the mutex lock; the
 462       *      lock is released and the caller is blocked waiting
 463       *      on 'cond'. When 'cond' is signaled, the mutex
 464       *      is re-acquired before returning to the caller.
 465       *
 466       * PARAMETERS
 467       *      cond
 468       *              pointer to an instance of pthread_cond_t
 469       *
 470       *      mutex
 471       *              pointer to an instance of pthread_mutex_t
 472       *
 473       *
 474       * DESCRIPTION
 475       *      This function waits on a condition variable until
 476       *      awakened by a signal or broadcast.
 477       *
 478       *      NOTES:
 479       *
 480       *      1)      The function must be called with 'mutex' LOCKED
 481       *              by the calling thread, or undefined behaviour
 482       *              will result.
 483       *
 484       *      2)      This routine atomically releases 'mutex' and causes
 485       *              the calling thread to block on the condition variable.
 486       *              The blocked thread may be awakened by
 487       *                      pthread_cond_signal or
 488       *                      pthread_cond_broadcast.
 489       *
 490       * Upon successful completion, the 'mutex' has been locked and
 491       * is owned by the calling thread.
 492       *
 493       *
 494       * RESULTS
 495       *              0               caught condition; mutex released,
 496       *              EINVAL          'cond' or 'mutex' is invalid,
 497       *              EINVAL          different mutexes for concurrent waits,
 498       *              EINVAL          mutex is not held by the calling thread,
 499       *
 500       * ------------------------------------------------------
 501       */
 502 {
 503   /*
 504    * The NULL abstime arg means INFINITE waiting.
 505    */
 506   return (ptw32_cond_timedwait (cond, mutex, NULL));
 507
 508 }                               /* pthread_cond_wait */
 509
 510
 511 int
 512 pthread_cond_timedwait (pthread_cond_t * cond,
 513                         pthread_mutex_t * mutex,
 514                         const struct timespec *abstime)
 515      /*
 516       * ------------------------------------------------------
 517       * DOCPUBLIC
 518       *      This function waits on a condition variable either until
 519       *      awakened by a signal or broadcast; or until the time
 520       *      specified by abstime passes.
 521       *
 522       * PARAMETERS
 523       *      cond
 524       *              pointer to an instance of pthread_cond_t
 525       *
 526       *      mutex
 527       *              pointer to an instance of pthread_mutex_t
 528       *
 529       *      abstime
 530       *              pointer to an instance of (const struct timespec)
 531       *
 532       *
 533       * DESCRIPTION
 534       *      This function waits on a condition variable either until
 535       *      awakened by a signal or broadcast; or until the time
 536       *      specified by abstime passes.
 537       *
 538       *      NOTES:
 539       *      1)      The function must be called with 'mutex' LOCKED
 540       *              by the calling thread, or undefined behaviour
 541       *              will result.
 542       *
 543       *      2)      This routine atomically releases 'mutex' and causes
 544       *              the calling thread to block on the condition variable.
 545       *              The blocked thread may be awakened by
 546       *                      pthread_cond_signal or
 547       *                      pthread_cond_broadcast.
 548       *
 549       *
 550       * RESULTS
 551       *              0               caught condition; mutex released,
 552       *              EINVAL          'cond', 'mutex', or abstime is invalid,
 553       *              EINVAL          different mutexes for concurrent waits,
 554       *              EINVAL          mutex is not held by the calling thread,
 555       *              ETIMEDOUT       abstime ellapsed before cond was signaled.
 556       *
 557       * ------------------------------------------------------
 558       */
 559 {
 560   if (abstime == NULL)
 561     {
 562       return EINVAL;
 563     }
 564
 565   return (ptw32_cond_timedwait (cond, mutex, abstime));
 566
 567 }                               /* pthread_cond_timedwait */