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 (at) 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 */ 568