1 /* $OpenBSD: uthread_cond.c,v 1.14 2003/12/23 19:31:05 brad Exp $ */
2 /*
3 * Copyright (c) 1995 John Birrell <jb@cimlogic.com.au>.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. All advertising materials mentioning features or use of this software
15 * must display the following acknowledgement:
16 * This product includes software developed by John Birrell.
17 * 4. Neither the name of the author nor the names of any co-contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY JOHN BIRRELL AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 *
33 * $FreeBSD: uthread_cond.c,v 1.18 1999/08/30 00:02:07 deischen Exp $
34 */
35 #include <stdlib.h>
36 #include <errno.h>
37 #include <string.h>
38 #ifdef _THREAD_SAFE
39 #include <pthread.h>
40 #include "pthread_private.h"
41
42 /*
43 * Prototypes
44 */
45 static inline pthread_t cond_queue_deq(pthread_cond_t);
46 static inline void cond_queue_remove(pthread_cond_t, pthread_t);
47 static inline void cond_queue_enq(pthread_cond_t, pthread_t);
48
49 /* Reinitialize a condition variable to defaults. */
50 int
_cond_reinit(pthread_cond_t * cond)51 _cond_reinit(pthread_cond_t *cond)
52 {
53 int ret = 0;
54
55 if (cond == NULL)
56 ret = EINVAL;
57 else if (*cond == NULL)
58 ret = pthread_cond_init(cond, NULL);
59 else {
60 /*
61 * Initialize the condition variable structure:
62 */
63 TAILQ_INIT(&(*cond)->c_queue);
64 (*cond)->c_flags = COND_FLAGS_INITED;
65 (*cond)->c_type = COND_TYPE_FAST;
66 (*cond)->c_mutex = NULL;
67 (*cond)->c_seqno = 0;
68 _SPINLOCK_INIT(&(*cond)->lock);
69 }
70 return (ret);
71 }
72
73 int
pthread_cond_init(pthread_cond_t * cond,const pthread_condattr_t * cond_attr)74 pthread_cond_init(pthread_cond_t * cond, const pthread_condattr_t * cond_attr)
75 {
76 enum pthread_cond_type type;
77 pthread_cond_t pcond;
78 int rval = 0;
79
80 if (cond == NULL)
81 rval = EINVAL;
82 else {
83 /*
84 * Check if a pointer to a condition variable attribute
85 * structure was passed by the caller:
86 */
87 if (cond_attr != NULL && *cond_attr != NULL) {
88 /* Default to a fast condition variable: */
89 type = (*cond_attr)->c_type;
90 } else {
91 /* Default to a fast condition variable: */
92 type = COND_TYPE_FAST;
93 }
94
95 /* Process according to condition variable type: */
96 switch (type) {
97 /* Fast condition variable: */
98 case COND_TYPE_FAST:
99 /* Nothing to do here. */
100 break;
101
102 /* Trap invalid condition variable types: */
103 default:
104 /* Return an invalid argument error: */
105 rval = EINVAL;
106 break;
107 }
108
109 /* Check for no errors: */
110 if (rval == 0) {
111 if ((pcond = (pthread_cond_t)
112 malloc(sizeof(struct pthread_cond))) == NULL) {
113 rval = ENOMEM;
114 } else {
115 /*
116 * Initialise the condition variable
117 * structure:
118 */
119 TAILQ_INIT(&pcond->c_queue);
120 pcond->c_flags |= COND_FLAGS_INITED;
121 pcond->c_type = type;
122 pcond->c_mutex = NULL;
123 pcond->c_seqno = 0;
124 _SPINLOCK_INIT(&pcond->lock);
125 *cond = pcond;
126 }
127 }
128 }
129 /* Return the completion status: */
130 return (rval);
131 }
132
133 int
pthread_cond_destroy(pthread_cond_t * cond)134 pthread_cond_destroy(pthread_cond_t * cond)
135 {
136 int rval = 0;
137
138 if (cond == NULL || *cond == NULL)
139 rval = EINVAL;
140 else {
141 /* Lock the condition variable structure: */
142 _SPINLOCK(&(*cond)->lock);
143
144 /*
145 * Free the memory allocated for the condition
146 * variable structure:
147 */
148 free(*cond);
149
150 /*
151 * NULL the caller's pointer now that the condition
152 * variable has been destroyed:
153 */
154 *cond = NULL;
155 }
156 /* Return the completion status: */
157 return (rval);
158 }
159
160 int
pthread_cond_wait(pthread_cond_t * cond,pthread_mutex_t * mutex)161 pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t * mutex)
162 {
163 struct pthread *curthread = _get_curthread();
164 int rval = 0;
165 int done = 0;
166 int interrupted = 0;
167 int seqno;
168
169 /* This is a cancellation point: */
170 _thread_enter_cancellation_point();
171
172 if (cond == NULL) {
173 /* No longer in a cancellation point: */
174 _thread_leave_cancellation_point();
175 return (EINVAL);
176 }
177
178 /*
179 * If the condition variable is statically initialized,
180 * perform the dynamic initialization:
181 */
182 if (*cond == NULL &&
183 (rval = pthread_cond_init(cond, NULL)) != 0) {
184 /* No longer in a cancellation point: */
185 _thread_leave_cancellation_point();
186 return (rval);
187 }
188
189 /*
190 * Enter a loop waiting for a condition signal or broadcast
191 * to wake up this thread. A loop is needed in case the waiting
192 * thread is interrupted by a signal to execute a signal handler.
193 * It is not (currently) possible to remain in the waiting queue
194 * while running a handler. Instead, the thread is interrupted
195 * and backed out of the waiting queue prior to executing the
196 * signal handler.
197 */
198 do {
199 /* Lock the condition variable structure: */
200 _SPINLOCK(&(*cond)->lock);
201
202 /*
203 * If the condvar was statically allocated, properly
204 * initialize the tail queue.
205 */
206 if (((*cond)->c_flags & COND_FLAGS_INITED) == 0) {
207 TAILQ_INIT(&(*cond)->c_queue);
208 (*cond)->c_flags |= COND_FLAGS_INITED;
209 }
210
211 /* Process according to condition variable type: */
212 switch ((*cond)->c_type) {
213 /* Fast condition variable: */
214 case COND_TYPE_FAST:
215 if ((mutex == NULL) || (((*cond)->c_mutex != NULL) &&
216 ((*cond)->c_mutex != *mutex))) {
217 /* Unlock the condition variable structure: */
218 _SPINUNLOCK(&(*cond)->lock);
219
220 /* Return invalid argument error: */
221 rval = EINVAL;
222 } else {
223 /* Reset the timeout and interrupted flags: */
224 curthread->timeout = 0;
225 curthread->interrupted = 0;
226
227 /*
228 * Queue the running thread for the condition
229 * variable:
230 */
231 cond_queue_enq(*cond, curthread);
232
233 /* Remember the mutex and sequence number: */
234 (*cond)->c_mutex = *mutex;
235 seqno = (*cond)->c_seqno;
236
237 /* Wait forever: */
238 curthread->wakeup_time.tv_sec = -1;
239
240 /* Unlock the mutex: */
241 if ((rval = _mutex_cv_unlock(mutex)) != 0) {
242 /*
243 * Cannot unlock the mutex, so remove
244 * the running thread from the condition
245 * variable queue:
246 */
247 cond_queue_remove(*cond, curthread);
248
249 /* Check for no more waiters: */
250 if (TAILQ_FIRST(&(*cond)->c_queue) ==
251 NULL)
252 (*cond)->c_mutex = NULL;
253
254 /* Unlock the condition variable structure: */
255 _SPINUNLOCK(&(*cond)->lock);
256 } else {
257 /*
258 * Schedule the next thread and unlock
259 * the condition variable structure:
260 */
261 _thread_kern_sched_state_unlock(PS_COND_WAIT,
262 &(*cond)->lock, __FILE__, __LINE__);
263
264 done = (seqno != (*cond)->c_seqno);
265
266 interrupted = curthread->interrupted;
267
268 /*
269 * Check if the wait was interrupted
270 * (canceled) or needs to be resumed
271 * after handling a signal.
272 */
273 if (interrupted != 0) {
274 /*
275 * Lock the mutex and ignore any
276 * errors. Note that even
277 * though this thread may have
278 * been canceled, POSIX requires
279 * that the mutex be reacquired
280 * prior to cancellation.
281 */
282 (void)_mutex_cv_lock(mutex);
283 } else {
284 /*
285 * Lock the condition variable
286 * while removing the thread.
287 */
288 _SPINLOCK(&(*cond)->lock);
289
290 cond_queue_remove(*cond,
291 curthread);
292
293 /* Check for no more waiters: */
294 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
295 (*cond)->c_mutex = NULL;
296
297 _SPINUNLOCK(&(*cond)->lock);
298
299 /* Lock the mutex: */
300 rval = _mutex_cv_lock(mutex);
301 }
302 }
303 }
304 break;
305
306 /* Trap invalid condition variable types: */
307 default:
308 /* Unlock the condition variable structure: */
309 _SPINUNLOCK(&(*cond)->lock);
310
311 /* Return an invalid argument error: */
312 rval = EINVAL;
313 break;
314 }
315
316 if ((interrupted != 0) && (curthread->continuation != NULL))
317 curthread->continuation((void *) curthread);
318 } while ((done == 0) && (rval == 0));
319
320 /* No longer in a cancellation point: */
321 _thread_leave_cancellation_point();
322
323 /* Return the completion status: */
324 return (rval);
325 }
326
327 int
pthread_cond_timedwait(pthread_cond_t * cond,pthread_mutex_t * mutex,const struct timespec * abstime)328 pthread_cond_timedwait(pthread_cond_t * cond, pthread_mutex_t * mutex,
329 const struct timespec * abstime)
330 {
331 struct pthread *curthread = _get_curthread();
332 int rval = 0;
333 int done = 0;
334 int interrupted = 0;
335 int seqno;
336
337 /* This is a cancellation point: */
338 _thread_enter_cancellation_point();
339
340 if (cond == NULL ||
341 abstime == NULL || abstime->tv_sec < 0 || abstime->tv_nsec < 0 ||
342 abstime->tv_nsec >= 1000000000) {
343 /* No longer in a cancellation point: */
344 _thread_leave_cancellation_point();
345 return (EINVAL);
346 }
347 /*
348 * If the condition variable is statically initialized, perform dynamic
349 * initialization.
350 */
351 if (*cond == NULL && (rval = pthread_cond_init(cond, NULL)) != 0) {
352 /* No longer in a cancellation point: */
353 _thread_leave_cancellation_point();
354 return (rval);
355 }
356
357 /*
358 * Enter a loop waiting for a condition signal or broadcast
359 * to wake up this thread. A loop is needed in case the waiting
360 * thread is interrupted by a signal to execute a signal handler.
361 * It is not (currently) possible to remain in the waiting queue
362 * while running a handler. Instead, the thread is interrupted
363 * and backed out of the waiting queue prior to executing the
364 * signal handler.
365 */
366 do {
367 /* Lock the condition variable structure: */
368 _SPINLOCK(&(*cond)->lock);
369
370 /*
371 * If the condvar was statically allocated, properly
372 * initialize the tail queue.
373 */
374 if (((*cond)->c_flags & COND_FLAGS_INITED) == 0) {
375 TAILQ_INIT(&(*cond)->c_queue);
376 (*cond)->c_flags |= COND_FLAGS_INITED;
377 }
378
379 /* Process according to condition variable type: */
380 switch ((*cond)->c_type) {
381 /* Fast condition variable: */
382 case COND_TYPE_FAST:
383 if ((mutex == NULL) || (((*cond)->c_mutex != NULL) &&
384 ((*cond)->c_mutex != *mutex))) {
385 /* Return invalid argument error: */
386 rval = EINVAL;
387
388 /* Unlock the condition variable structure: */
389 _SPINUNLOCK(&(*cond)->lock);
390 } else {
391 /* Set the wakeup time: */
392 curthread->wakeup_time.tv_sec =
393 abstime->tv_sec;
394 curthread->wakeup_time.tv_nsec =
395 abstime->tv_nsec;
396
397 /* Reset the timeout and interrupted flags: */
398 curthread->timeout = 0;
399 curthread->interrupted = 0;
400
401 /*
402 * Queue the running thread for the condition
403 * variable:
404 */
405 cond_queue_enq(*cond, curthread);
406
407 /* Remember the mutex and sequence number: */
408 (*cond)->c_mutex = *mutex;
409 seqno = (*cond)->c_seqno;
410
411 /* Unlock the mutex: */
412 if ((rval = _mutex_cv_unlock(mutex)) != 0) {
413 /*
414 * Cannot unlock the mutex, so remove
415 * the running thread from the condition
416 * variable queue:
417 */
418 cond_queue_remove(*cond, curthread);
419
420 /* Check for no more waiters: */
421 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
422 (*cond)->c_mutex = NULL;
423
424 /* Unlock the condition variable structure: */
425 _SPINUNLOCK(&(*cond)->lock);
426 } else {
427 /*
428 * Schedule the next thread and unlock
429 * the condition variable structure:
430 */
431 _thread_kern_sched_state_unlock(PS_COND_WAIT,
432 &(*cond)->lock, __FILE__, __LINE__);
433
434 done = (seqno != (*cond)->c_seqno);
435
436 interrupted = curthread->interrupted;
437
438 /*
439 * Check if the wait was interrupted
440 * (canceled) or needs to be resumed
441 * after handling a signal.
442 */
443 if (interrupted != 0) {
444 /*
445 * Lock the mutex and ignore any
446 * errors. Note that even
447 * though this thread may have
448 * been canceled, POSIX requires
449 * that the mutex be reacquired
450 * prior to cancellation.
451 */
452 (void)_mutex_cv_lock(mutex);
453 } else {
454 /*
455 * Lock the condition variable
456 * while removing the thread.
457 */
458 _SPINLOCK(&(*cond)->lock);
459
460 cond_queue_remove(*cond,
461 curthread);
462
463 /* Check for no more waiters: */
464 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
465 (*cond)->c_mutex = NULL;
466
467 _SPINUNLOCK(&(*cond)->lock);
468
469 /* Lock the mutex: */
470 rval = _mutex_cv_lock(mutex);
471
472 /*
473 * Return ETIMEDOUT if the wait
474 * timed out and there wasn't an
475 * error locking the mutex:
476 */
477 if ((curthread->timeout != 0)
478 && rval == 0)
479 rval = ETIMEDOUT;
480
481 }
482 }
483 }
484 break;
485
486 /* Trap invalid condition variable types: */
487 default:
488 /* Unlock the condition variable structure: */
489 _SPINUNLOCK(&(*cond)->lock);
490
491 /* Return an invalid argument error: */
492 rval = EINVAL;
493 break;
494 }
495
496 if ((interrupted != 0) && (curthread->continuation != NULL))
497 curthread->continuation((void *) curthread);
498 } while ((done == 0) && (rval == 0));
499
500 /* No longer in a cancellation point: */
501 _thread_leave_cancellation_point();
502
503 /* Return the completion status: */
504 return (rval);
505 }
506
507 int
pthread_cond_signal(pthread_cond_t * cond)508 pthread_cond_signal(pthread_cond_t * cond)
509 {
510 int rval = 0;
511 pthread_t pthread;
512
513 if (cond == NULL)
514 rval = EINVAL;
515 /*
516 * If the condition variable is statically initialized, perform dynamic
517 * initialization.
518 */
519 else if (*cond != NULL || (rval = pthread_cond_init(cond, NULL)) == 0) {
520 /*
521 * Defer signals to protect the scheduling queues
522 * from access by the signal handler:
523 */
524 _thread_kern_sig_defer();
525
526 /* Lock the condition variable structure: */
527 _SPINLOCK(&(*cond)->lock);
528
529 /* Process according to condition variable type: */
530 switch ((*cond)->c_type) {
531 /* Fast condition variable: */
532 case COND_TYPE_FAST:
533 /* Increment the sequence number: */
534 (*cond)->c_seqno++;
535
536 if ((pthread = cond_queue_deq(*cond)) != NULL) {
537 /*
538 * Unless the thread is currently suspended,
539 * allow it to run. If the thread is suspended,
540 * make a note that the thread isn't in a wait
541 * queue any more.
542 */
543 if (pthread->state != PS_SUSPENDED)
544 PTHREAD_NEW_STATE(pthread,PS_RUNNING);
545 else
546 pthread->suspended = SUSP_NOWAIT;
547 }
548
549 /* Check for no more waiters: */
550 if (TAILQ_FIRST(&(*cond)->c_queue) == NULL)
551 (*cond)->c_mutex = NULL;
552 break;
553
554 /* Trap invalid condition variable types: */
555 default:
556 /* Return an invalid argument error: */
557 rval = EINVAL;
558 break;
559 }
560
561 /* Unlock the condition variable structure: */
562 _SPINUNLOCK(&(*cond)->lock);
563
564 /*
565 * Undefer and handle pending signals, yielding if
566 * necessary:
567 */
568 _thread_kern_sig_undefer();
569 }
570
571 /* Return the completion status: */
572 return (rval);
573 }
574
575 int
pthread_cond_broadcast(pthread_cond_t * cond)576 pthread_cond_broadcast(pthread_cond_t * cond)
577 {
578 int rval = 0;
579 pthread_t pthread;
580
581 if (cond == NULL)
582 rval = EINVAL;
583 /*
584 * If the condition variable is statically initialized, perform dynamic
585 * initialization.
586 */
587 else if (*cond != NULL || (rval = pthread_cond_init(cond, NULL)) == 0) {
588 /*
589 * Defer signals to protect the scheduling queues
590 * from access by the signal handler:
591 */
592 _thread_kern_sig_defer();
593
594 /* Lock the condition variable structure: */
595 _SPINLOCK(&(*cond)->lock);
596
597 /* Process according to condition variable type: */
598 switch ((*cond)->c_type) {
599 /* Fast condition variable: */
600 case COND_TYPE_FAST:
601 /* Increment the sequence number: */
602 (*cond)->c_seqno++;
603
604 /*
605 * Enter a loop to bring all threads off the
606 * condition queue:
607 */
608 while ((pthread = cond_queue_deq(*cond)) != NULL) {
609 /*
610 * Unless the thread is currently suspended,
611 * allow it to run. If the thread is suspended,
612 * make a note that the thread isn't in a wait
613 * queue any more.
614 */
615 if (pthread->state != PS_SUSPENDED)
616 PTHREAD_NEW_STATE(pthread,PS_RUNNING);
617 else
618 pthread->suspended = SUSP_NOWAIT;
619 }
620
621 /* There are no more waiting threads: */
622 (*cond)->c_mutex = NULL;
623 break;
624
625 /* Trap invalid condition variable types: */
626 default:
627 /* Return an invalid argument error: */
628 rval = EINVAL;
629 break;
630 }
631
632 /* Unlock the condition variable structure: */
633 _SPINUNLOCK(&(*cond)->lock);
634
635 /*
636 * Undefer and handle pending signals, yielding if
637 * necessary:
638 */
639 _thread_kern_sig_undefer();
640 }
641
642 /* Return the completion status: */
643 return (rval);
644 }
645
646 /*
647 * Dequeue a waiting thread from the head of a condition queue in
648 * descending priority order.
649 */
650 static inline pthread_t
cond_queue_deq(pthread_cond_t cond)651 cond_queue_deq(pthread_cond_t cond)
652 {
653 pthread_t pthread;
654
655 while ((pthread = TAILQ_FIRST(&cond->c_queue)) != NULL) {
656 TAILQ_REMOVE(&cond->c_queue, pthread, sqe);
657 pthread->flags &= ~PTHREAD_FLAGS_IN_CONDQ;
658 if ((pthread->timeout == 0) && (pthread->interrupted == 0))
659 /*
660 * Only exit the loop when we find a thread
661 * that hasn't timed out or been canceled;
662 * those threads are already running and don't
663 * need their run state changed.
664 */
665 break;
666 }
667
668 return(pthread);
669 }
670
671 /*
672 * Remove a waiting thread from a condition queue in descending priority
673 * order.
674 */
675 static inline void
cond_queue_remove(pthread_cond_t cond,pthread_t pthread)676 cond_queue_remove(pthread_cond_t cond, pthread_t pthread)
677 {
678 /*
679 * Because pthread_cond_timedwait() can timeout as well
680 * as be signaled by another thread, it is necessary to
681 * guard against removing the thread from the queue if
682 * it isn't in the queue.
683 */
684 if (pthread->flags & PTHREAD_FLAGS_IN_CONDQ) {
685 TAILQ_REMOVE(&cond->c_queue, pthread, sqe);
686 pthread->flags &= ~PTHREAD_FLAGS_IN_CONDQ;
687 }
688 }
689
690 /*
691 * Enqueue a waiting thread to a condition queue in descending priority
692 * order.
693 */
694 static inline void
cond_queue_enq(pthread_cond_t cond,pthread_t pthread)695 cond_queue_enq(pthread_cond_t cond, pthread_t pthread)
696 {
697 pthread_t tid = TAILQ_LAST(&cond->c_queue, cond_head);
698
699 PTHREAD_ASSERT_NOT_IN_SYNCQ(pthread);
700
701 /*
702 * For the common case of all threads having equal priority,
703 * we perform a quick check against the priority of the thread
704 * at the tail of the queue.
705 */
706 if ((tid == NULL) || (pthread->active_priority <= tid->active_priority))
707 TAILQ_INSERT_TAIL(&cond->c_queue, pthread, sqe);
708 else {
709 tid = TAILQ_FIRST(&cond->c_queue);
710 while (pthread->active_priority <= tid->active_priority)
711 tid = TAILQ_NEXT(tid, sqe);
712 TAILQ_INSERT_BEFORE(tid, pthread, sqe);
713 }
714 pthread->flags |= PTHREAD_FLAGS_IN_CONDQ;
715 pthread->data.cond = cond;
716 }
717 #endif
718