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 */
268typedef struct
269{
270  pthread_mutex_t *mutexPtr;
271  pthread_cond_t cv;
272  int *resultPtr;
273} ptw32_cond_wait_cleanup_args_t;
274
275static void PTW32_CDECL
276ptw32_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
353static INLINE int
354ptw32_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
453int
454pthread_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
511int
512pthread_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