1 /* $NetBSD: kern_condvar.c,v 1.44 2020/03/26 19:46:42 ad Exp $ */ 2 3 /*- 4 * Copyright (c) 2006, 2007, 2008, 2019, 2020 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Andrew Doran. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * Kernel condition variable implementation. 34 */ 35 36 #include <sys/cdefs.h> 37 __KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.44 2020/03/26 19:46:42 ad Exp $"); 38 39 #include <sys/param.h> 40 #include <sys/systm.h> 41 #include <sys/lwp.h> 42 #include <sys/condvar.h> 43 #include <sys/sleepq.h> 44 #include <sys/lockdebug.h> 45 #include <sys/cpu.h> 46 #include <sys/kernel.h> 47 48 /* 49 * Accessors for the private contents of the kcondvar_t data type. 50 * 51 * cv_opaque[0] sleepq_t 52 * cv_opaque[1] description for ps(1) 53 * 54 * cv_opaque[0] is protected by the interlock passed to cv_wait() (enqueue 55 * only), and the sleep queue lock acquired with sleepq_hashlock() (enqueue 56 * and dequeue). 57 * 58 * cv_opaque[1] (the wmesg) is static and does not change throughout the life 59 * of the CV. 60 */ 61 #define CV_SLEEPQ(cv) ((sleepq_t *)(cv)->cv_opaque) 62 #define CV_WMESG(cv) ((const char *)(cv)->cv_opaque[1]) 63 #define CV_SET_WMESG(cv, v) (cv)->cv_opaque[1] = __UNCONST(v) 64 65 #define CV_DEBUG_P(cv) (CV_WMESG(cv) != nodebug) 66 #define CV_RA ((uintptr_t)__builtin_return_address(0)) 67 68 static void cv_unsleep(lwp_t *, bool); 69 static inline void cv_wakeup_one(kcondvar_t *); 70 static inline void cv_wakeup_all(kcondvar_t *); 71 72 syncobj_t cv_syncobj = { 73 .sobj_flag = SOBJ_SLEEPQ_SORTED, 74 .sobj_unsleep = cv_unsleep, 75 .sobj_changepri = sleepq_changepri, 76 .sobj_lendpri = sleepq_lendpri, 77 .sobj_owner = syncobj_noowner, 78 }; 79 80 lockops_t cv_lockops = { 81 .lo_name = "Condition variable", 82 .lo_type = LOCKOPS_CV, 83 .lo_dump = NULL, 84 }; 85 86 static const char deadcv[] = "deadcv"; 87 #ifdef LOCKDEBUG 88 static const char nodebug[] = "nodebug"; 89 90 #define CV_LOCKDEBUG_HANDOFF(l, cv) cv_lockdebug_handoff(l, cv) 91 #define CV_LOCKDEBUG_PROCESS(l, cv) cv_lockdebug_process(l, cv) 92 93 static inline void 94 cv_lockdebug_handoff(lwp_t *l, kcondvar_t *cv) 95 { 96 97 if (CV_DEBUG_P(cv)) 98 l->l_flag |= LW_CVLOCKDEBUG; 99 } 100 101 static inline void 102 cv_lockdebug_process(lwp_t *l, kcondvar_t *cv) 103 { 104 105 if ((l->l_flag & LW_CVLOCKDEBUG) == 0) 106 return; 107 108 l->l_flag &= ~LW_CVLOCKDEBUG; 109 LOCKDEBUG_UNLOCKED(true, cv, CV_RA, 0); 110 } 111 #else 112 #define CV_LOCKDEBUG_HANDOFF(l, cv) __nothing 113 #define CV_LOCKDEBUG_PROCESS(l, cv) __nothing 114 #endif 115 116 /* 117 * cv_init: 118 * 119 * Initialize a condition variable for use. 120 */ 121 void 122 cv_init(kcondvar_t *cv, const char *wmesg) 123 { 124 #ifdef LOCKDEBUG 125 bool dodebug; 126 127 dodebug = LOCKDEBUG_ALLOC(cv, &cv_lockops, 128 (uintptr_t)__builtin_return_address(0)); 129 if (!dodebug) { 130 /* XXX This will break vfs_lockf. */ 131 wmesg = nodebug; 132 } 133 #endif 134 KASSERT(wmesg != NULL); 135 CV_SET_WMESG(cv, wmesg); 136 sleepq_init(CV_SLEEPQ(cv)); 137 } 138 139 /* 140 * cv_destroy: 141 * 142 * Tear down a condition variable. 143 */ 144 void 145 cv_destroy(kcondvar_t *cv) 146 { 147 148 LOCKDEBUG_FREE(CV_DEBUG_P(cv), cv); 149 #ifdef DIAGNOSTIC 150 KASSERT(cv_is_valid(cv)); 151 CV_SET_WMESG(cv, deadcv); 152 #endif 153 } 154 155 /* 156 * cv_enter: 157 * 158 * Look up and lock the sleep queue corresponding to the given 159 * condition variable, and increment the number of waiters. 160 */ 161 static inline void 162 cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l) 163 { 164 sleepq_t *sq; 165 kmutex_t *mp; 166 167 KASSERT(cv_is_valid(cv)); 168 KASSERT(!cpu_intr_p()); 169 KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL); 170 171 LOCKDEBUG_LOCKED(CV_DEBUG_P(cv), cv, mtx, CV_RA, 0); 172 173 l->l_kpriority = true; 174 mp = sleepq_hashlock(cv); 175 sq = CV_SLEEPQ(cv); 176 sleepq_enter(sq, l, mp); 177 sleepq_enqueue(sq, cv, CV_WMESG(cv), &cv_syncobj); 178 mutex_exit(mtx); 179 KASSERT(cv_has_waiters(cv)); 180 } 181 182 /* 183 * cv_exit: 184 * 185 * After resuming execution, check to see if we have been restarted 186 * as a result of cv_signal(). If we have, but cannot take the 187 * wakeup (because of eg a pending Unix signal or timeout) then try 188 * to ensure that another LWP sees it. This is necessary because 189 * there may be multiple waiters, and at least one should take the 190 * wakeup if possible. 191 */ 192 static inline int 193 cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error) 194 { 195 196 mutex_enter(mtx); 197 if (__predict_false(error != 0)) 198 cv_signal(cv); 199 200 LOCKDEBUG_UNLOCKED(CV_DEBUG_P(cv), cv, CV_RA, 0); 201 KASSERT(cv_is_valid(cv)); 202 203 return error; 204 } 205 206 /* 207 * cv_unsleep: 208 * 209 * Remove an LWP from the condition variable and sleep queue. This 210 * is called when the LWP has not been awoken normally but instead 211 * interrupted: for example, when a signal is received. Must be 212 * called with the LWP locked. Will unlock if "unlock" is true. 213 */ 214 static void 215 cv_unsleep(lwp_t *l, bool unlock) 216 { 217 kcondvar_t *cv __diagused; 218 219 cv = (kcondvar_t *)(uintptr_t)l->l_wchan; 220 221 KASSERT(l->l_wchan == (wchan_t)cv); 222 KASSERT(l->l_sleepq == CV_SLEEPQ(cv)); 223 KASSERT(cv_is_valid(cv)); 224 KASSERT(cv_has_waiters(cv)); 225 226 sleepq_unsleep(l, unlock); 227 } 228 229 /* 230 * cv_wait: 231 * 232 * Wait non-interruptably on a condition variable until awoken. 233 */ 234 void 235 cv_wait(kcondvar_t *cv, kmutex_t *mtx) 236 { 237 lwp_t *l = curlwp; 238 239 KASSERT(mutex_owned(mtx)); 240 241 cv_enter(cv, mtx, l); 242 243 /* 244 * We can't use cv_exit() here since the cv might be destroyed before 245 * this thread gets a chance to run. Instead, hand off the lockdebug 246 * responsibility to the thread that wakes us up. 247 */ 248 249 CV_LOCKDEBUG_HANDOFF(l, cv); 250 (void)sleepq_block(0, false); 251 mutex_enter(mtx); 252 } 253 254 /* 255 * cv_wait_sig: 256 * 257 * Wait on a condition variable until a awoken or a signal is received. 258 * Will also return early if the process is exiting. Returns zero if 259 * awoken normally, ERESTART if a signal was received and the system 260 * call is restartable, or EINTR otherwise. 261 */ 262 int 263 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx) 264 { 265 lwp_t *l = curlwp; 266 int error; 267 268 KASSERT(mutex_owned(mtx)); 269 270 cv_enter(cv, mtx, l); 271 error = sleepq_block(0, true); 272 return cv_exit(cv, mtx, l, error); 273 } 274 275 /* 276 * cv_timedwait: 277 * 278 * Wait on a condition variable until awoken or the specified timeout 279 * expires. Returns zero if awoken normally or EWOULDBLOCK if the 280 * timeout expired. 281 * 282 * timo is a timeout in ticks. timo = 0 specifies an infinite timeout. 283 */ 284 int 285 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo) 286 { 287 lwp_t *l = curlwp; 288 int error; 289 290 KASSERT(mutex_owned(mtx)); 291 292 cv_enter(cv, mtx, l); 293 error = sleepq_block(timo, false); 294 return cv_exit(cv, mtx, l, error); 295 } 296 297 /* 298 * cv_timedwait_sig: 299 * 300 * Wait on a condition variable until a timeout expires, awoken or a 301 * signal is received. Will also return early if the process is 302 * exiting. Returns zero if awoken normally, EWOULDBLOCK if the 303 * timeout expires, ERESTART if a signal was received and the system 304 * call is restartable, or EINTR otherwise. 305 * 306 * timo is a timeout in ticks. timo = 0 specifies an infinite timeout. 307 */ 308 int 309 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo) 310 { 311 lwp_t *l = curlwp; 312 int error; 313 314 KASSERT(mutex_owned(mtx)); 315 316 cv_enter(cv, mtx, l); 317 error = sleepq_block(timo, true); 318 return cv_exit(cv, mtx, l, error); 319 } 320 321 /* 322 * Given a number of seconds, sec, and 2^64ths of a second, frac, we 323 * want a number of ticks for a timeout: 324 * 325 * timo = hz*(sec + frac/2^64) 326 * = hz*sec + hz*frac/2^64 327 * = hz*sec + hz*(frachi*2^32 + fraclo)/2^64 328 * = hz*sec + hz*frachi/2^32 + hz*fraclo/2^64, 329 * 330 * where frachi is the high 32 bits of frac and fraclo is the 331 * low 32 bits. 332 * 333 * We assume hz < INT_MAX/2 < UINT32_MAX, so 334 * 335 * hz*fraclo/2^64 < fraclo*2^32/2^64 <= 1, 336 * 337 * since fraclo < 2^32. 338 * 339 * We clamp the result at INT_MAX/2 for a timeout in ticks, since we 340 * can't represent timeouts higher than INT_MAX in cv_timedwait, and 341 * spurious wakeup is OK. Moreover, we don't want to wrap around, 342 * because we compute end - start in ticks in order to compute the 343 * remaining timeout, and that difference cannot wrap around, so we use 344 * a timeout less than INT_MAX. Using INT_MAX/2 provides plenty of 345 * margin for paranoia and will exceed most waits in practice by far. 346 */ 347 static unsigned 348 bintime2timo(const struct bintime *bt) 349 { 350 351 KASSERT(hz < INT_MAX/2); 352 CTASSERT(INT_MAX/2 < UINT32_MAX); 353 if (bt->sec > ((INT_MAX/2)/hz)) 354 return INT_MAX/2; 355 if ((hz*(bt->frac >> 32) >> 32) > (INT_MAX/2 - hz*bt->sec)) 356 return INT_MAX/2; 357 358 return hz*bt->sec + (hz*(bt->frac >> 32) >> 32); 359 } 360 361 /* 362 * timo is in units of ticks. We want units of seconds and 2^64ths of 363 * a second. We know hz = 1 sec/tick, and 2^64 = 1 sec/(2^64th of a 364 * second), from which we can conclude 2^64 / hz = 1 (2^64th of a 365 * second)/tick. So for the fractional part, we compute 366 * 367 * frac = rem * 2^64 / hz 368 * = ((rem * 2^32) / hz) * 2^32 369 * 370 * Using truncating integer division instead of real division will 371 * leave us with only about 32 bits of precision, which means about 372 * 1/4-nanosecond resolution, which is good enough for our purposes. 373 */ 374 static struct bintime 375 timo2bintime(unsigned timo) 376 { 377 378 return (struct bintime) { 379 .sec = timo / hz, 380 .frac = (((uint64_t)(timo % hz) << 32)/hz << 32), 381 }; 382 } 383 384 /* 385 * cv_timedwaitbt: 386 * 387 * Wait on a condition variable until awoken or the specified 388 * timeout expires. Returns zero if awoken normally or 389 * EWOULDBLOCK if the timeout expires. 390 * 391 * On entry, bt is a timeout in bintime. cv_timedwaitbt subtracts 392 * the time slept, so on exit, bt is the time remaining after 393 * sleeping, possibly negative if the complete time has elapsed. 394 * No infinite timeout; use cv_wait_sig instead. 395 * 396 * epsilon is a requested maximum error in timeout (excluding 397 * spurious wakeups). Currently not used, will be used in the 398 * future to choose between low- and high-resolution timers. 399 * Actual wakeup time will be somewhere in [t, t + max(e, r) + s) 400 * where r is the finest resolution of clock available and s is 401 * scheduling delays for scheduler overhead and competing threads. 402 * Time is measured by the interrupt source implementing the 403 * timeout, not by another timecounter. 404 */ 405 int 406 cv_timedwaitbt(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt, 407 const struct bintime *epsilon __diagused) 408 { 409 struct bintime slept; 410 unsigned start, end; 411 int error; 412 413 KASSERTMSG(bt->sec >= 0, "negative timeout"); 414 KASSERTMSG(epsilon != NULL, "specify maximum requested delay"); 415 416 /* 417 * hardclock_ticks is technically int, but nothing special 418 * happens instead of overflow, so we assume two's-complement 419 * wraparound and just treat it as unsigned. 420 */ 421 start = hardclock_ticks; 422 error = cv_timedwait(cv, mtx, bintime2timo(bt)); 423 end = hardclock_ticks; 424 425 slept = timo2bintime(end - start); 426 /* bt := bt - slept */ 427 bintime_sub(bt, &slept); 428 429 return error; 430 } 431 432 /* 433 * cv_timedwaitbt_sig: 434 * 435 * Wait on a condition variable until awoken, the specified 436 * timeout expires, or interrupted by a signal. Returns zero if 437 * awoken normally, EWOULDBLOCK if the timeout expires, or 438 * EINTR/ERESTART if interrupted by a signal. 439 * 440 * On entry, bt is a timeout in bintime. cv_timedwaitbt_sig 441 * subtracts the time slept, so on exit, bt is the time remaining 442 * after sleeping. No infinite timeout; use cv_wait instead. 443 * 444 * epsilon is a requested maximum error in timeout (excluding 445 * spurious wakeups). Currently not used, will be used in the 446 * future to choose between low- and high-resolution timers. 447 */ 448 int 449 cv_timedwaitbt_sig(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt, 450 const struct bintime *epsilon __diagused) 451 { 452 struct bintime slept; 453 unsigned start, end; 454 int error; 455 456 KASSERTMSG(bt->sec >= 0, "negative timeout"); 457 KASSERTMSG(epsilon != NULL, "specify maximum requested delay"); 458 459 /* 460 * hardclock_ticks is technically int, but nothing special 461 * happens instead of overflow, so we assume two's-complement 462 * wraparound and just treat it as unsigned. 463 */ 464 start = hardclock_ticks; 465 error = cv_timedwait_sig(cv, mtx, bintime2timo(bt)); 466 end = hardclock_ticks; 467 468 slept = timo2bintime(end - start); 469 /* bt := bt - slept */ 470 bintime_sub(bt, &slept); 471 472 return error; 473 } 474 475 /* 476 * cv_signal: 477 * 478 * Wake the highest priority LWP waiting on a condition variable. 479 * Must be called with the interlocking mutex held. 480 */ 481 void 482 cv_signal(kcondvar_t *cv) 483 { 484 485 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ 486 KASSERT(cv_is_valid(cv)); 487 488 if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv)))) 489 cv_wakeup_one(cv); 490 } 491 492 /* 493 * cv_wakeup_one: 494 * 495 * Slow path for cv_signal(). Deliberately marked __noinline to 496 * prevent the compiler pulling it in to cv_signal(), which adds 497 * extra prologue and epilogue code. 498 */ 499 static __noinline void 500 cv_wakeup_one(kcondvar_t *cv) 501 { 502 sleepq_t *sq; 503 kmutex_t *mp; 504 lwp_t *l; 505 506 KASSERT(cv_is_valid(cv)); 507 508 mp = sleepq_hashlock(cv); 509 sq = CV_SLEEPQ(cv); 510 l = LIST_FIRST(sq); 511 if (__predict_false(l == NULL)) { 512 mutex_spin_exit(mp); 513 return; 514 } 515 KASSERT(l->l_sleepq == sq); 516 KASSERT(l->l_mutex == mp); 517 KASSERT(l->l_wchan == cv); 518 CV_LOCKDEBUG_PROCESS(l, cv); 519 sleepq_remove(sq, l); 520 mutex_spin_exit(mp); 521 522 KASSERT(cv_is_valid(cv)); 523 } 524 525 /* 526 * cv_broadcast: 527 * 528 * Wake all LWPs waiting on a condition variable. Must be called 529 * with the interlocking mutex held. 530 */ 531 void 532 cv_broadcast(kcondvar_t *cv) 533 { 534 535 /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */ 536 KASSERT(cv_is_valid(cv)); 537 538 if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv)))) 539 cv_wakeup_all(cv); 540 } 541 542 /* 543 * cv_wakeup_all: 544 * 545 * Slow path for cv_broadcast(). Deliberately marked __noinline to 546 * prevent the compiler pulling it in to cv_broadcast(), which adds 547 * extra prologue and epilogue code. 548 */ 549 static __noinline void 550 cv_wakeup_all(kcondvar_t *cv) 551 { 552 sleepq_t *sq; 553 kmutex_t *mp; 554 lwp_t *l, *next; 555 556 KASSERT(cv_is_valid(cv)); 557 558 mp = sleepq_hashlock(cv); 559 sq = CV_SLEEPQ(cv); 560 for (l = LIST_FIRST(sq); l != NULL; l = next) { 561 KASSERT(l->l_sleepq == sq); 562 KASSERT(l->l_mutex == mp); 563 KASSERT(l->l_wchan == cv); 564 next = LIST_NEXT(l, l_sleepchain); 565 CV_LOCKDEBUG_PROCESS(l, cv); 566 sleepq_remove(sq, l); 567 } 568 mutex_spin_exit(mp); 569 570 KASSERT(cv_is_valid(cv)); 571 } 572 573 /* 574 * cv_has_waiters: 575 * 576 * For diagnostic assertions: return non-zero if a condition 577 * variable has waiters. 578 */ 579 bool 580 cv_has_waiters(kcondvar_t *cv) 581 { 582 583 return !LIST_EMPTY(CV_SLEEPQ(cv)); 584 } 585 586 /* 587 * cv_is_valid: 588 * 589 * For diagnostic assertions: return non-zero if a condition 590 * variable appears to be valid. No locks need be held. 591 */ 592 bool 593 cv_is_valid(kcondvar_t *cv) 594 { 595 596 return CV_WMESG(cv) != deadcv && CV_WMESG(cv) != NULL; 597 } 598