1 /* 2 * Copyright (c) 1995 John Birrell <jb@cimlogic.com.au>. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by John Birrell. 16 * 4. Neither the name of the author nor the names of any co-contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY JOHN BIRRELL AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * $FreeBSD$ 33 */ 34 #include <stdlib.h> 35 #include <errno.h> 36 #include <string.h> 37 #include <pthread.h> 38 #include "thr_private.h" 39 40 /* 41 * Proctect two different threads calling a pthread_cond_* function 42 * from accidentally initializing the condition variable twice. 43 */ 44 static spinlock_t static_cond_lock = _SPINLOCK_INITIALIZER; 45 46 /* 47 * Prototypes 48 */ 49 static inline int cond_init(pthread_cond_t *); 50 static pthread_t cond_queue_deq(pthread_cond_t); 51 static void cond_queue_remove(pthread_cond_t, pthread_t); 52 static void cond_queue_enq(pthread_cond_t, pthread_t); 53 static int cond_signal(pthread_cond_t *, int); 54 static int cond_wait_common(pthread_cond_t *, 55 pthread_mutex_t *, const struct timespec *); 56 57 __weak_reference(_pthread_cond_init, pthread_cond_init); 58 __weak_reference(_pthread_cond_destroy, pthread_cond_destroy); 59 __weak_reference(_pthread_cond_wait, pthread_cond_wait); 60 __weak_reference(_pthread_cond_timedwait, pthread_cond_timedwait); 61 __weak_reference(_pthread_cond_signal, pthread_cond_signal); 62 __weak_reference(_pthread_cond_broadcast, pthread_cond_broadcast); 63 64 #define COND_LOCK(c) \ 65 do { \ 66 if (umtx_lock(&(c)->c_lock, curthread->thr_id)) \ 67 abort(); \ 68 } while (0) 69 70 #define COND_UNLOCK(c) \ 71 do { \ 72 if (umtx_unlock(&(c)->c_lock, curthread->thr_id)) \ 73 abort(); \ 74 } while (0) 75 76 77 /* Reinitialize a condition variable to defaults. */ 78 int 79 _cond_reinit(pthread_cond_t *cond) 80 { 81 if (cond == NULL) 82 return (EINVAL); 83 84 if (*cond == NULL) 85 return (pthread_cond_init(cond, NULL)); 86 87 /* 88 * Initialize the condition variable structure: 89 */ 90 TAILQ_INIT(&(*cond)->c_queue); 91 (*cond)->c_flags = COND_FLAGS_INITED; 92 (*cond)->c_type = COND_TYPE_FAST; 93 (*cond)->c_mutex = NULL; 94 (*cond)->c_seqno = 0; 95 bzero(&(*cond)->c_lock, sizeof((*cond)->c_lock)); 96 97 return (0); 98 } 99 100 int 101 _pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *cond_attr) 102 { 103 enum pthread_cond_type type; 104 pthread_cond_t pcond; 105 106 if (cond == NULL) 107 return (EINVAL); 108 109 /* 110 * Check if a pointer to a condition variable attribute 111 * structure was passed by the caller: 112 */ 113 if (cond_attr != NULL && *cond_attr != NULL) 114 type = (*cond_attr)->c_type; 115 else 116 /* Default to a fast condition variable: */ 117 type = COND_TYPE_FAST; 118 119 /* Process according to condition variable type: */ 120 switch (type) { 121 case COND_TYPE_FAST: 122 break; 123 default: 124 return (EINVAL); 125 break; 126 } 127 128 if ((pcond = (pthread_cond_t) 129 malloc(sizeof(struct pthread_cond))) == NULL) 130 return (ENOMEM); 131 /* 132 * Initialise the condition variable 133 * structure: 134 */ 135 TAILQ_INIT(&pcond->c_queue); 136 pcond->c_flags |= COND_FLAGS_INITED; 137 pcond->c_type = type; 138 pcond->c_mutex = NULL; 139 pcond->c_seqno = 0; 140 bzero(&pcond->c_lock, sizeof(pcond->c_lock)); 141 142 *cond = pcond; 143 144 return (0); 145 } 146 147 int 148 _pthread_cond_destroy(pthread_cond_t *cond) 149 { 150 if (cond == NULL || *cond == NULL) 151 return (EINVAL); 152 153 COND_LOCK(*cond); 154 155 /* 156 * Free the memory allocated for the condition 157 * variable structure: 158 */ 159 free(*cond); 160 161 /* 162 * NULL the caller's pointer now that the condition 163 * variable has been destroyed: 164 */ 165 *cond = NULL; 166 167 return (0); 168 } 169 170 int 171 _pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) 172 { 173 int rval; 174 175 rval = cond_wait_common(cond, mutex, NULL); 176 177 /* This should never happen. */ 178 if (rval == ETIMEDOUT) 179 abort(); 180 181 return (rval); 182 } 183 184 int 185 _pthread_cond_timedwait(pthread_cond_t * cond, pthread_mutex_t * mutex, 186 const struct timespec * abstime) 187 { 188 if (abstime == NULL || abstime->tv_nsec >= 1000000000) 189 return (EINVAL); 190 191 return (cond_wait_common(cond, mutex, abstime)); 192 } 193 194 static int 195 cond_wait_common(pthread_cond_t * cond, pthread_mutex_t * mutex, 196 const struct timespec * abstime) 197 { 198 int rval = 0; 199 int done = 0; 200 int seqno; 201 int mtxrval; 202 203 204 _thread_enter_cancellation_point(); 205 206 if (cond == NULL) 207 return (EINVAL); 208 /* 209 * If the condition variable is statically initialized, perform dynamic 210 * initialization. 211 */ 212 if (*cond == PTHREAD_COND_INITIALIZER && (rval = cond_init(cond)) != 0) 213 return (rval); 214 215 216 COND_LOCK(*cond); 217 218 /* 219 * If the condvar was statically allocated, properly 220 * initialize the tail queue. 221 */ 222 if (((*cond)->c_flags & COND_FLAGS_INITED) == 0) { 223 TAILQ_INIT(&(*cond)->c_queue); 224 (*cond)->c_flags |= COND_FLAGS_INITED; 225 } 226 227 /* Process according to condition variable type. */ 228 229 switch ((*cond)->c_type) { 230 /* Fast condition variable: */ 231 case COND_TYPE_FAST: 232 if ((mutex == NULL) || (((*cond)->c_mutex != NULL) && 233 ((*cond)->c_mutex != *mutex))) { 234 COND_UNLOCK(*cond); 235 rval = EINVAL; 236 break; 237 } 238 /* Remember the mutex */ 239 (*cond)->c_mutex = *mutex; 240 241 if ((rval = _mutex_cv_unlock(mutex)) != 0) { 242 if (rval == -1){ 243 printf("foo"); 244 fflush(stdout); 245 abort(); 246 } 247 248 COND_UNLOCK(*cond); 249 break; 250 } 251 252 /* 253 * We need to protect the queue operations. It also 254 * protects c_seqno and the pthread flag fields. This is 255 * dropped before calling _thread_suspend() and reaquired 256 * when we return. 257 */ 258 259 _thread_critical_enter(curthread); 260 /* 261 * c_seqno is protected. 262 */ 263 seqno = (*cond)->c_seqno; 264 265 do { 266 /* 267 * Queue the running thread on the condition 268 * variable. 269 */ 270 cond_queue_enq(*cond, curthread); 271 272 if (curthread->cancelflags & PTHREAD_CANCELLING) { 273 /* 274 * POSIX Says that we must relock the mutex 275 * even if we're being canceled. 276 */ 277 _thread_critical_exit(curthread); 278 COND_UNLOCK(*cond); 279 _mutex_cv_lock(mutex); 280 pthread_testcancel(); 281 PANIC("Shouldn't have come back."); 282 } 283 284 PTHREAD_SET_STATE(curthread, PS_COND_WAIT); 285 _thread_critical_exit(curthread); 286 COND_UNLOCK(*cond); 287 rval = _thread_suspend(curthread, (struct timespec *)abstime); 288 if (rval != 0 && rval != EAGAIN && rval != EINTR) { 289 printf("foo"); 290 fflush(stdout); 291 abort(); 292 } 293 COND_LOCK(*cond); 294 _thread_critical_enter(curthread); 295 296 done = (seqno != (*cond)->c_seqno); 297 298 /* 299 * If we timed out, this will remove us from the 300 * queue. Otherwise, if we were signaled it does 301 * nothing because this thread won't be on the queue. 302 */ 303 cond_queue_remove(*cond, curthread); 304 305 } while ((done == 0) && (rval == 0)); 306 /* 307 * If we timed out someone still may have signaled us 308 * before we got a chance to run again. We check for 309 * this by looking to see if our state is RUNNING. 310 */ 311 if (rval == EAGAIN) { 312 if (curthread->state != PS_RUNNING) { 313 PTHREAD_SET_STATE(curthread, PS_RUNNING); 314 rval = ETIMEDOUT; 315 } else 316 rval = 0; 317 } 318 _thread_critical_exit(curthread); 319 COND_UNLOCK(*cond); 320 321 mtxrval = _mutex_cv_lock(mutex); 322 323 /* 324 * If the mutex failed return that error, otherwise we're 325 * returning ETIMEDOUT. 326 */ 327 if (mtxrval == -1) { 328 printf("foo"); 329 fflush(stdout); 330 abort(); 331 } 332 if (mtxrval != 0) 333 rval = mtxrval; 334 335 break; 336 337 /* Trap invalid condition variable types: */ 338 default: 339 COND_UNLOCK(*cond); 340 rval = EINVAL; 341 break; 342 } 343 344 _thread_leave_cancellation_point(); 345 346 return (rval); 347 } 348 349 int 350 _pthread_cond_signal(pthread_cond_t * cond) 351 { 352 return (cond_signal(cond, 0)); 353 } 354 355 int 356 _pthread_cond_broadcast(pthread_cond_t * cond) 357 { 358 return (cond_signal(cond, 1)); 359 } 360 361 static int 362 cond_signal(pthread_cond_t * cond, int broadcast) 363 { 364 int rval = 0; 365 pthread_t pthread; 366 367 if (cond == NULL) 368 return (EINVAL); 369 /* 370 * If the condition variable is statically initialized, perform dynamic 371 * initialization. 372 */ 373 if (*cond == PTHREAD_COND_INITIALIZER && (rval = cond_init(cond)) != 0) 374 return (rval); 375 376 COND_LOCK(*cond); 377 378 /* Process according to condition variable type: */ 379 switch ((*cond)->c_type) { 380 /* Fast condition variable: */ 381 case COND_TYPE_FAST: 382 (*cond)->c_seqno++; 383 384 /* 385 * Enter a loop to bring all (or only one) threads off the 386 * condition queue: 387 */ 388 do { 389 /* 390 * Wake up the signaled thread. It will be returned 391 * to us locked, and with signals disabled. 392 */ 393 if ((pthread = cond_queue_deq(*cond)) != NULL) { 394 PTHREAD_NEW_STATE(pthread, PS_RUNNING); 395 _thread_critical_exit(pthread); 396 } 397 } while (broadcast && pthread != NULL); 398 399 break; 400 401 /* Trap invalid condition variable types: */ 402 default: 403 rval = EINVAL; 404 break; 405 } 406 407 COND_UNLOCK(*cond); 408 409 410 return (rval); 411 } 412 413 void 414 _cond_wait_backout(pthread_t pthread) 415 { 416 pthread_cond_t cond; 417 418 cond = pthread->data.cond; 419 if (cond == NULL) 420 return; 421 422 COND_LOCK(cond); 423 424 /* Process according to condition variable type: */ 425 switch (cond->c_type) { 426 /* Fast condition variable: */ 427 case COND_TYPE_FAST: 428 _thread_critical_enter(curthread); 429 430 cond_queue_remove(cond, pthread); 431 432 _thread_critical_exit(curthread); 433 break; 434 435 default: 436 break; 437 } 438 439 COND_UNLOCK(cond); 440 } 441 442 /* 443 * Dequeue a waiting thread from the head of a condition queue in 444 * descending priority order. 445 */ 446 static pthread_t 447 cond_queue_deq(pthread_cond_t cond) 448 { 449 pthread_t pthread; 450 451 while ((pthread = TAILQ_FIRST(&cond->c_queue)) != NULL) { 452 _thread_critical_enter(pthread); 453 TAILQ_REMOVE(&cond->c_queue, pthread, sqe); 454 cond_queue_remove(cond, pthread); 455 if ((pthread->cancelflags & PTHREAD_CANCELLING) == 0 && 456 pthread->state == PS_COND_WAIT) 457 /* 458 * Only exit the loop when we find a thread 459 * that hasn't timed out or been canceled; 460 * those threads are already running and don't 461 * need their run state changed. 462 */ 463 break; 464 else 465 _thread_critical_exit(pthread); 466 } 467 468 return(pthread); 469 } 470 471 /* 472 * Remove a waiting thread from a condition queue in descending priority 473 * order. 474 */ 475 static void 476 cond_queue_remove(pthread_cond_t cond, pthread_t pthread) 477 { 478 /* 479 * Because pthread_cond_timedwait() can timeout as well 480 * as be signaled by another thread, it is necessary to 481 * guard against removing the thread from the queue if 482 * it isn't in the queue. 483 */ 484 if (pthread->flags & PTHREAD_FLAGS_IN_CONDQ) { 485 TAILQ_REMOVE(&cond->c_queue, pthread, sqe); 486 pthread->flags &= ~PTHREAD_FLAGS_IN_CONDQ; 487 } 488 /* Check for no more waiters. */ 489 if (TAILQ_FIRST(&cond->c_queue) == NULL) 490 cond->c_mutex = NULL; 491 } 492 493 /* 494 * Enqueue a waiting thread to a condition queue in descending priority 495 * order. 496 */ 497 static void 498 cond_queue_enq(pthread_cond_t cond, pthread_t pthread) 499 { 500 pthread_t tid = TAILQ_LAST(&cond->c_queue, cond_head); 501 char *name; 502 503 name = pthread->name ? pthread->name : "unknown"; 504 if ((pthread->flags & PTHREAD_FLAGS_IN_CONDQ) != 0) 505 _thread_printf(2, "Thread (%s:%u) already on condq\n", 506 pthread->name, pthread->uniqueid); 507 if ((pthread->flags & PTHREAD_FLAGS_IN_MUTEXQ) != 0) 508 _thread_printf(2, "Thread (%s:%u) already on mutexq\n", 509 pthread->name, pthread->uniqueid); 510 PTHREAD_ASSERT_NOT_IN_SYNCQ(pthread); 511 512 /* 513 * For the common case of all threads having equal priority, 514 * we perform a quick check against the priority of the thread 515 * at the tail of the queue. 516 */ 517 if ((tid == NULL) || (pthread->active_priority <= tid->active_priority)) 518 TAILQ_INSERT_TAIL(&cond->c_queue, pthread, sqe); 519 else { 520 tid = TAILQ_FIRST(&cond->c_queue); 521 while (pthread->active_priority <= tid->active_priority) 522 tid = TAILQ_NEXT(tid, sqe); 523 TAILQ_INSERT_BEFORE(tid, pthread, sqe); 524 } 525 pthread->flags |= PTHREAD_FLAGS_IN_CONDQ; 526 pthread->data.cond = cond; 527 } 528 529 static inline int 530 cond_init(pthread_cond_t *cond) 531 { 532 int error = 0; 533 _SPINLOCK(&static_cond_lock); 534 if (*cond == PTHREAD_COND_INITIALIZER) 535 error = _pthread_cond_init(cond, NULL); 536 _SPINUNLOCK(&static_cond_lock); 537 return (error); 538 } 539 540