1 /* $NetBSD: kern_mutex.c,v 1.97 2021/04/03 14:56:14 thorpej Exp $ */ 2 3 /*- 4 * Copyright (c) 2002, 2006, 2007, 2008, 2019 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Jason R. Thorpe and 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 mutex implementation, modeled after those found in Solaris, 34 * a description of which can be found in: 35 * 36 * Solaris Internals: Core Kernel Architecture, Jim Mauro and 37 * Richard McDougall. 38 */ 39 40 #define __MUTEX_PRIVATE 41 42 #include <sys/cdefs.h> 43 __KERNEL_RCSID(0, "$NetBSD: kern_mutex.c,v 1.97 2021/04/03 14:56:14 thorpej Exp $"); 44 45 #include <sys/param.h> 46 #include <sys/atomic.h> 47 #include <sys/proc.h> 48 #include <sys/mutex.h> 49 #include <sys/sched.h> 50 #include <sys/sleepq.h> 51 #include <sys/systm.h> 52 #include <sys/lockdebug.h> 53 #include <sys/kernel.h> 54 #include <sys/intr.h> 55 #include <sys/lock.h> 56 #include <sys/types.h> 57 #include <sys/cpu.h> 58 #include <sys/pserialize.h> 59 60 #include <dev/lockstat.h> 61 62 #include <machine/lock.h> 63 64 /* 65 * When not running a debug kernel, spin mutexes are not much 66 * more than an splraiseipl() and splx() pair. 67 */ 68 69 #if defined(DIAGNOSTIC) || defined(MULTIPROCESSOR) || defined(LOCKDEBUG) 70 #define FULL 71 #endif 72 73 /* 74 * Debugging support. 75 */ 76 77 #define MUTEX_WANTLOCK(mtx) \ 78 LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \ 79 (uintptr_t)__builtin_return_address(0), 0) 80 #define MUTEX_TESTLOCK(mtx) \ 81 LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \ 82 (uintptr_t)__builtin_return_address(0), -1) 83 #define MUTEX_LOCKED(mtx) \ 84 LOCKDEBUG_LOCKED(MUTEX_DEBUG_P(mtx), (mtx), NULL, \ 85 (uintptr_t)__builtin_return_address(0), 0) 86 #define MUTEX_UNLOCKED(mtx) \ 87 LOCKDEBUG_UNLOCKED(MUTEX_DEBUG_P(mtx), (mtx), \ 88 (uintptr_t)__builtin_return_address(0), 0) 89 #define MUTEX_ABORT(mtx, msg) \ 90 mutex_abort(__func__, __LINE__, mtx, msg) 91 92 #if defined(LOCKDEBUG) 93 94 #define MUTEX_DASSERT(mtx, cond) \ 95 do { \ 96 if (__predict_false(!(cond))) \ 97 MUTEX_ABORT(mtx, "assertion failed: " #cond); \ 98 } while (/* CONSTCOND */ 0) 99 100 #else /* LOCKDEBUG */ 101 102 #define MUTEX_DASSERT(mtx, cond) /* nothing */ 103 104 #endif /* LOCKDEBUG */ 105 106 #if defined(DIAGNOSTIC) 107 108 #define MUTEX_ASSERT(mtx, cond) \ 109 do { \ 110 if (__predict_false(!(cond))) \ 111 MUTEX_ABORT(mtx, "assertion failed: " #cond); \ 112 } while (/* CONSTCOND */ 0) 113 114 #else /* DIAGNOSTIC */ 115 116 #define MUTEX_ASSERT(mtx, cond) /* nothing */ 117 118 #endif /* DIAGNOSTIC */ 119 120 /* 121 * Some architectures can't use __cpu_simple_lock as is so allow a way 122 * for them to use an alternate definition. 123 */ 124 #ifndef MUTEX_SPINBIT_LOCK_INIT 125 #define MUTEX_SPINBIT_LOCK_INIT(mtx) __cpu_simple_lock_init(&(mtx)->mtx_lock) 126 #endif 127 #ifndef MUTEX_SPINBIT_LOCKED_P 128 #define MUTEX_SPINBIT_LOCKED_P(mtx) __SIMPLELOCK_LOCKED_P(&(mtx)->mtx_lock) 129 #endif 130 #ifndef MUTEX_SPINBIT_LOCK_TRY 131 #define MUTEX_SPINBIT_LOCK_TRY(mtx) __cpu_simple_lock_try(&(mtx)->mtx_lock) 132 #endif 133 #ifndef MUTEX_SPINBIT_LOCK_UNLOCK 134 #define MUTEX_SPINBIT_LOCK_UNLOCK(mtx) __cpu_simple_unlock(&(mtx)->mtx_lock) 135 #endif 136 137 #ifndef MUTEX_INITIALIZE_SPIN_IPL 138 #define MUTEX_INITIALIZE_SPIN_IPL(mtx, ipl) \ 139 ((mtx)->mtx_ipl = makeiplcookie((ipl))) 140 #endif 141 142 /* 143 * Spin mutex SPL save / restore. 144 */ 145 146 #define MUTEX_SPIN_SPLRAISE(mtx) \ 147 do { \ 148 struct cpu_info *x__ci; \ 149 int x__cnt, s; \ 150 s = splraiseipl(MUTEX_SPIN_IPL(mtx)); \ 151 x__ci = curcpu(); \ 152 x__cnt = x__ci->ci_mtx_count--; \ 153 __insn_barrier(); \ 154 if (x__cnt == 0) \ 155 x__ci->ci_mtx_oldspl = (s); \ 156 } while (/* CONSTCOND */ 0) 157 158 #define MUTEX_SPIN_SPLRESTORE(mtx) \ 159 do { \ 160 struct cpu_info *x__ci = curcpu(); \ 161 int s = x__ci->ci_mtx_oldspl; \ 162 __insn_barrier(); \ 163 if (++(x__ci->ci_mtx_count) == 0) \ 164 splx(s); \ 165 } while (/* CONSTCOND */ 0) 166 167 /* 168 * Memory barriers. 169 */ 170 #ifdef __HAVE_ATOMIC_AS_MEMBAR 171 #define MUTEX_MEMBAR_ENTER() 172 #define MUTEX_MEMBAR_EXIT() 173 #else 174 #define MUTEX_MEMBAR_ENTER() membar_enter() 175 #define MUTEX_MEMBAR_EXIT() membar_exit() 176 #endif 177 178 /* 179 * For architectures that provide 'simple' mutexes: they provide a 180 * CAS function that is either MP-safe, or does not need to be MP 181 * safe. Adaptive mutexes on these architectures do not require an 182 * additional interlock. 183 */ 184 185 #ifdef __HAVE_SIMPLE_MUTEXES 186 187 #define MUTEX_OWNER(owner) \ 188 (owner & MUTEX_THREAD) 189 #define MUTEX_HAS_WAITERS(mtx) \ 190 (((int)(mtx)->mtx_owner & MUTEX_BIT_WAITERS) != 0) 191 192 #define MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug) \ 193 do { \ 194 if (!dodebug) \ 195 (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \ 196 } while (/* CONSTCOND */ 0) 197 198 #define MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl) \ 199 do { \ 200 (mtx)->mtx_owner = MUTEX_BIT_SPIN; \ 201 if (!dodebug) \ 202 (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \ 203 MUTEX_INITIALIZE_SPIN_IPL((mtx), (ipl)); \ 204 MUTEX_SPINBIT_LOCK_INIT((mtx)); \ 205 } while (/* CONSTCOND */ 0) 206 207 #define MUTEX_DESTROY(mtx) \ 208 do { \ 209 (mtx)->mtx_owner = MUTEX_THREAD; \ 210 } while (/* CONSTCOND */ 0) 211 212 #define MUTEX_SPIN_P(owner) \ 213 (((owner) & MUTEX_BIT_SPIN) != 0) 214 #define MUTEX_ADAPTIVE_P(owner) \ 215 (((owner) & MUTEX_BIT_SPIN) == 0) 216 217 #define MUTEX_DEBUG_P(mtx) (((mtx)->mtx_owner & MUTEX_BIT_NODEBUG) == 0) 218 #if defined(LOCKDEBUG) 219 #define MUTEX_OWNED(owner) (((owner) & ~MUTEX_BIT_NODEBUG) != 0) 220 #define MUTEX_INHERITDEBUG(n, o) (n) |= (o) & MUTEX_BIT_NODEBUG 221 #else /* defined(LOCKDEBUG) */ 222 #define MUTEX_OWNED(owner) ((owner) != 0) 223 #define MUTEX_INHERITDEBUG(n, o) /* nothing */ 224 #endif /* defined(LOCKDEBUG) */ 225 226 static inline int 227 MUTEX_ACQUIRE(kmutex_t *mtx, uintptr_t curthread) 228 { 229 int rv; 230 uintptr_t oldown = 0; 231 uintptr_t newown = curthread; 232 233 MUTEX_INHERITDEBUG(oldown, mtx->mtx_owner); 234 MUTEX_INHERITDEBUG(newown, oldown); 235 rv = MUTEX_CAS(&mtx->mtx_owner, oldown, newown); 236 MUTEX_MEMBAR_ENTER(); 237 return rv; 238 } 239 240 static inline int 241 MUTEX_SET_WAITERS(kmutex_t *mtx, uintptr_t owner) 242 { 243 int rv; 244 rv = MUTEX_CAS(&mtx->mtx_owner, owner, owner | MUTEX_BIT_WAITERS); 245 MUTEX_MEMBAR_ENTER(); 246 return rv; 247 } 248 249 static inline void 250 MUTEX_RELEASE(kmutex_t *mtx) 251 { 252 uintptr_t newown; 253 254 MUTEX_MEMBAR_EXIT(); 255 newown = 0; 256 MUTEX_INHERITDEBUG(newown, mtx->mtx_owner); 257 mtx->mtx_owner = newown; 258 } 259 #endif /* __HAVE_SIMPLE_MUTEXES */ 260 261 /* 262 * Patch in stubs via strong alias where they are not available. 263 */ 264 265 #if defined(LOCKDEBUG) 266 #undef __HAVE_MUTEX_STUBS 267 #undef __HAVE_SPIN_MUTEX_STUBS 268 #endif 269 270 #ifndef __HAVE_MUTEX_STUBS 271 __strong_alias(mutex_enter,mutex_vector_enter); 272 __strong_alias(mutex_exit,mutex_vector_exit); 273 #endif 274 275 #ifndef __HAVE_SPIN_MUTEX_STUBS 276 __strong_alias(mutex_spin_enter,mutex_vector_enter); 277 __strong_alias(mutex_spin_exit,mutex_vector_exit); 278 #endif 279 280 static void mutex_abort(const char *, size_t, const kmutex_t *, 281 const char *); 282 static void mutex_dump(const volatile void *, lockop_printer_t); 283 284 lockops_t mutex_spin_lockops = { 285 .lo_name = "Mutex", 286 .lo_type = LOCKOPS_SPIN, 287 .lo_dump = mutex_dump, 288 }; 289 290 lockops_t mutex_adaptive_lockops = { 291 .lo_name = "Mutex", 292 .lo_type = LOCKOPS_SLEEP, 293 .lo_dump = mutex_dump, 294 }; 295 296 syncobj_t mutex_syncobj = { 297 .sobj_flag = SOBJ_SLEEPQ_SORTED, 298 .sobj_unsleep = turnstile_unsleep, 299 .sobj_changepri = turnstile_changepri, 300 .sobj_lendpri = sleepq_lendpri, 301 .sobj_owner = (void *)mutex_owner, 302 }; 303 304 /* 305 * mutex_dump: 306 * 307 * Dump the contents of a mutex structure. 308 */ 309 static void 310 mutex_dump(const volatile void *cookie, lockop_printer_t pr) 311 { 312 const volatile kmutex_t *mtx = cookie; 313 uintptr_t owner = mtx->mtx_owner; 314 315 pr("owner field : %#018lx wait/spin: %16d/%d\n", 316 (long)MUTEX_OWNER(owner), MUTEX_HAS_WAITERS(mtx), 317 MUTEX_SPIN_P(owner)); 318 } 319 320 /* 321 * mutex_abort: 322 * 323 * Dump information about an error and panic the system. This 324 * generates a lot of machine code in the DIAGNOSTIC case, so 325 * we ask the compiler to not inline it. 326 */ 327 static void __noinline 328 mutex_abort(const char *func, size_t line, const kmutex_t *mtx, const char *msg) 329 { 330 331 LOCKDEBUG_ABORT(func, line, mtx, (MUTEX_SPIN_P(mtx->mtx_owner) ? 332 &mutex_spin_lockops : &mutex_adaptive_lockops), msg); 333 } 334 335 /* 336 * mutex_init: 337 * 338 * Initialize a mutex for use. Note that adaptive mutexes are in 339 * essence spin mutexes that can sleep to avoid deadlock and wasting 340 * CPU time. We can't easily provide a type of mutex that always 341 * sleeps - see comments in mutex_vector_enter() about releasing 342 * mutexes unlocked. 343 */ 344 void _mutex_init(kmutex_t *, kmutex_type_t, int, uintptr_t); 345 void 346 _mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl, 347 uintptr_t return_address) 348 { 349 lockops_t *lockops __unused; 350 bool dodebug; 351 352 memset(mtx, 0, sizeof(*mtx)); 353 354 if (ipl == IPL_NONE || ipl == IPL_SOFTCLOCK || 355 ipl == IPL_SOFTBIO || ipl == IPL_SOFTNET || 356 ipl == IPL_SOFTSERIAL) { 357 lockops = (type == MUTEX_NODEBUG ? 358 NULL : &mutex_adaptive_lockops); 359 dodebug = LOCKDEBUG_ALLOC(mtx, lockops, return_address); 360 MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug); 361 } else { 362 lockops = (type == MUTEX_NODEBUG ? 363 NULL : &mutex_spin_lockops); 364 dodebug = LOCKDEBUG_ALLOC(mtx, lockops, return_address); 365 MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl); 366 } 367 } 368 369 void 370 mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl) 371 { 372 373 _mutex_init(mtx, type, ipl, (uintptr_t)__builtin_return_address(0)); 374 } 375 376 /* 377 * mutex_destroy: 378 * 379 * Tear down a mutex. 380 */ 381 void 382 mutex_destroy(kmutex_t *mtx) 383 { 384 uintptr_t owner = mtx->mtx_owner; 385 386 if (MUTEX_ADAPTIVE_P(owner)) { 387 MUTEX_ASSERT(mtx, !MUTEX_OWNED(owner)); 388 MUTEX_ASSERT(mtx, !MUTEX_HAS_WAITERS(mtx)); 389 } else { 390 MUTEX_ASSERT(mtx, !MUTEX_SPINBIT_LOCKED_P(mtx)); 391 } 392 393 LOCKDEBUG_FREE(MUTEX_DEBUG_P(mtx), mtx); 394 MUTEX_DESTROY(mtx); 395 } 396 397 #ifdef MULTIPROCESSOR 398 /* 399 * mutex_oncpu: 400 * 401 * Return true if an adaptive mutex owner is running on a CPU in the 402 * system. If the target is waiting on the kernel big lock, then we 403 * must release it. This is necessary to avoid deadlock. 404 */ 405 static bool 406 mutex_oncpu(uintptr_t owner) 407 { 408 struct cpu_info *ci; 409 lwp_t *l; 410 411 KASSERT(kpreempt_disabled()); 412 413 if (!MUTEX_OWNED(owner)) { 414 return false; 415 } 416 417 /* 418 * See lwp_dtor() why dereference of the LWP pointer is safe. 419 * We must have kernel preemption disabled for that. 420 */ 421 l = (lwp_t *)MUTEX_OWNER(owner); 422 ci = l->l_cpu; 423 424 if (ci && ci->ci_curlwp == l) { 425 /* Target is running; do we need to block? */ 426 return (ci->ci_biglock_wanted != l); 427 } 428 429 /* Not running. It may be safe to block now. */ 430 return false; 431 } 432 #endif /* MULTIPROCESSOR */ 433 434 /* 435 * mutex_vector_enter: 436 * 437 * Support routine for mutex_enter() that must handle all cases. In 438 * the LOCKDEBUG case, mutex_enter() is always aliased here, even if 439 * fast-path stubs are available. If a mutex_spin_enter() stub is 440 * not available, then it is also aliased directly here. 441 */ 442 void 443 mutex_vector_enter(kmutex_t *mtx) 444 { 445 uintptr_t owner, curthread; 446 turnstile_t *ts; 447 #ifdef MULTIPROCESSOR 448 u_int count; 449 #endif 450 LOCKSTAT_COUNTER(spincnt); 451 LOCKSTAT_COUNTER(slpcnt); 452 LOCKSTAT_TIMER(spintime); 453 LOCKSTAT_TIMER(slptime); 454 LOCKSTAT_FLAG(lsflag); 455 456 /* 457 * Handle spin mutexes. 458 */ 459 KPREEMPT_DISABLE(curlwp); 460 owner = mtx->mtx_owner; 461 if (MUTEX_SPIN_P(owner)) { 462 #if defined(LOCKDEBUG) && defined(MULTIPROCESSOR) 463 u_int spins = 0; 464 #endif 465 KPREEMPT_ENABLE(curlwp); 466 MUTEX_SPIN_SPLRAISE(mtx); 467 MUTEX_WANTLOCK(mtx); 468 #ifdef FULL 469 if (MUTEX_SPINBIT_LOCK_TRY(mtx)) { 470 MUTEX_LOCKED(mtx); 471 return; 472 } 473 #if !defined(MULTIPROCESSOR) 474 MUTEX_ABORT(mtx, "locking against myself"); 475 #else /* !MULTIPROCESSOR */ 476 477 LOCKSTAT_ENTER(lsflag); 478 LOCKSTAT_START_TIMER(lsflag, spintime); 479 count = SPINLOCK_BACKOFF_MIN; 480 481 /* 482 * Spin testing the lock word and do exponential backoff 483 * to reduce cache line ping-ponging between CPUs. 484 */ 485 do { 486 while (MUTEX_SPINBIT_LOCKED_P(mtx)) { 487 SPINLOCK_SPIN_HOOK; 488 SPINLOCK_BACKOFF(count); 489 #ifdef LOCKDEBUG 490 if (SPINLOCK_SPINOUT(spins)) 491 MUTEX_ABORT(mtx, "spinout"); 492 #endif /* LOCKDEBUG */ 493 } 494 } while (!MUTEX_SPINBIT_LOCK_TRY(mtx)); 495 496 if (count != SPINLOCK_BACKOFF_MIN) { 497 LOCKSTAT_STOP_TIMER(lsflag, spintime); 498 LOCKSTAT_EVENT(lsflag, mtx, 499 LB_SPIN_MUTEX | LB_SPIN, 1, spintime); 500 } 501 LOCKSTAT_EXIT(lsflag); 502 #endif /* !MULTIPROCESSOR */ 503 #endif /* FULL */ 504 MUTEX_LOCKED(mtx); 505 return; 506 } 507 508 curthread = (uintptr_t)curlwp; 509 510 MUTEX_DASSERT(mtx, MUTEX_ADAPTIVE_P(owner)); 511 MUTEX_ASSERT(mtx, curthread != 0); 512 MUTEX_ASSERT(mtx, !cpu_intr_p()); 513 MUTEX_WANTLOCK(mtx); 514 515 if (panicstr == NULL) { 516 KDASSERT(pserialize_not_in_read_section()); 517 LOCKDEBUG_BARRIER(&kernel_lock, 1); 518 } 519 520 LOCKSTAT_ENTER(lsflag); 521 522 /* 523 * Adaptive mutex; spin trying to acquire the mutex. If we 524 * determine that the owner is not running on a processor, 525 * then we stop spinning, and sleep instead. 526 */ 527 for (;;) { 528 if (!MUTEX_OWNED(owner)) { 529 /* 530 * Mutex owner clear could mean two things: 531 * 532 * * The mutex has been released. 533 * * The owner field hasn't been set yet. 534 * 535 * Try to acquire it again. If that fails, 536 * we'll just loop again. 537 */ 538 if (MUTEX_ACQUIRE(mtx, curthread)) 539 break; 540 owner = mtx->mtx_owner; 541 continue; 542 } 543 if (__predict_false(MUTEX_OWNER(owner) == curthread)) { 544 MUTEX_ABORT(mtx, "locking against myself"); 545 } 546 #ifdef MULTIPROCESSOR 547 /* 548 * Check to see if the owner is running on a processor. 549 * If so, then we should just spin, as the owner will 550 * likely release the lock very soon. 551 */ 552 if (mutex_oncpu(owner)) { 553 LOCKSTAT_START_TIMER(lsflag, spintime); 554 count = SPINLOCK_BACKOFF_MIN; 555 do { 556 KPREEMPT_ENABLE(curlwp); 557 SPINLOCK_BACKOFF(count); 558 KPREEMPT_DISABLE(curlwp); 559 owner = mtx->mtx_owner; 560 } while (mutex_oncpu(owner)); 561 LOCKSTAT_STOP_TIMER(lsflag, spintime); 562 LOCKSTAT_COUNT(spincnt, 1); 563 if (!MUTEX_OWNED(owner)) 564 continue; 565 } 566 #endif 567 568 ts = turnstile_lookup(mtx); 569 570 /* 571 * Once we have the turnstile chain interlock, mark the 572 * mutex as having waiters. If that fails, spin again: 573 * chances are that the mutex has been released. 574 */ 575 if (!MUTEX_SET_WAITERS(mtx, owner)) { 576 turnstile_exit(mtx); 577 owner = mtx->mtx_owner; 578 continue; 579 } 580 581 #ifdef MULTIPROCESSOR 582 /* 583 * mutex_exit() is permitted to release the mutex without 584 * any interlocking instructions, and the following can 585 * occur as a result: 586 * 587 * CPU 1: MUTEX_SET_WAITERS() CPU2: mutex_exit() 588 * ---------------------------- ---------------------------- 589 * .. acquire cache line 590 * .. test for waiters 591 * acquire cache line <- lose cache line 592 * lock cache line .. 593 * verify mutex is held .. 594 * set waiters .. 595 * unlock cache line .. 596 * lose cache line -> acquire cache line 597 * .. clear lock word, waiters 598 * return success 599 * 600 * There is another race that can occur: a third CPU could 601 * acquire the mutex as soon as it is released. Since 602 * adaptive mutexes are primarily spin mutexes, this is not 603 * something that we need to worry about too much. What we 604 * do need to ensure is that the waiters bit gets set. 605 * 606 * To allow the unlocked release, we need to make some 607 * assumptions here: 608 * 609 * o Release is the only non-atomic/unlocked operation 610 * that can be performed on the mutex. (It must still 611 * be atomic on the local CPU, e.g. in case interrupted 612 * or preempted). 613 * 614 * o At any given time, MUTEX_SET_WAITERS() can only ever 615 * be in progress on one CPU in the system - guaranteed 616 * by the turnstile chain lock. 617 * 618 * o No other operations other than MUTEX_SET_WAITERS() 619 * and release can modify a mutex with a non-zero 620 * owner field. 621 * 622 * o The result of a successful MUTEX_SET_WAITERS() call 623 * is an unbuffered write that is immediately visible 624 * to all other processors in the system. 625 * 626 * o If the holding LWP switches away, it posts a store 627 * fence before changing curlwp, ensuring that any 628 * overwrite of the mutex waiters flag by mutex_exit() 629 * completes before the modification of curlwp becomes 630 * visible to this CPU. 631 * 632 * o cpu_switchto() posts a store fence after setting curlwp 633 * and before resuming execution of an LWP. 634 * 635 * o _kernel_lock() posts a store fence before setting 636 * curcpu()->ci_biglock_wanted, and after clearing it. 637 * This ensures that any overwrite of the mutex waiters 638 * flag by mutex_exit() completes before the modification 639 * of ci_biglock_wanted becomes visible. 640 * 641 * We now post a read memory barrier (after setting the 642 * waiters field) and check the lock holder's status again. 643 * Some of the possible outcomes (not an exhaustive list): 644 * 645 * 1. The on-CPU check returns true: the holding LWP is 646 * running again. The lock may be released soon and 647 * we should spin. Importantly, we can't trust the 648 * value of the waiters flag. 649 * 650 * 2. The on-CPU check returns false: the holding LWP is 651 * not running. We now have the opportunity to check 652 * if mutex_exit() has blatted the modifications made 653 * by MUTEX_SET_WAITERS(). 654 * 655 * 3. The on-CPU check returns false: the holding LWP may 656 * or may not be running. It has context switched at 657 * some point during our check. Again, we have the 658 * chance to see if the waiters bit is still set or 659 * has been overwritten. 660 * 661 * 4. The on-CPU check returns false: the holding LWP is 662 * running on a CPU, but wants the big lock. It's OK 663 * to check the waiters field in this case. 664 * 665 * 5. The has-waiters check fails: the mutex has been 666 * released, the waiters flag cleared and another LWP 667 * now owns the mutex. 668 * 669 * 6. The has-waiters check fails: the mutex has been 670 * released. 671 * 672 * If the waiters bit is not set it's unsafe to go asleep, 673 * as we might never be awoken. 674 */ 675 membar_consumer(); 676 if (mutex_oncpu(owner)) { 677 turnstile_exit(mtx); 678 owner = mtx->mtx_owner; 679 continue; 680 } 681 membar_consumer(); 682 if (!MUTEX_HAS_WAITERS(mtx)) { 683 turnstile_exit(mtx); 684 owner = mtx->mtx_owner; 685 continue; 686 } 687 #endif /* MULTIPROCESSOR */ 688 689 LOCKSTAT_START_TIMER(lsflag, slptime); 690 691 turnstile_block(ts, TS_WRITER_Q, mtx, &mutex_syncobj); 692 693 LOCKSTAT_STOP_TIMER(lsflag, slptime); 694 LOCKSTAT_COUNT(slpcnt, 1); 695 696 owner = mtx->mtx_owner; 697 } 698 KPREEMPT_ENABLE(curlwp); 699 700 LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SLEEP1, 701 slpcnt, slptime); 702 LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SPIN, 703 spincnt, spintime); 704 LOCKSTAT_EXIT(lsflag); 705 706 MUTEX_DASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread); 707 MUTEX_LOCKED(mtx); 708 } 709 710 /* 711 * mutex_vector_exit: 712 * 713 * Support routine for mutex_exit() that handles all cases. 714 */ 715 void 716 mutex_vector_exit(kmutex_t *mtx) 717 { 718 turnstile_t *ts; 719 uintptr_t curthread; 720 721 if (MUTEX_SPIN_P(mtx->mtx_owner)) { 722 #ifdef FULL 723 if (__predict_false(!MUTEX_SPINBIT_LOCKED_P(mtx))) { 724 MUTEX_ABORT(mtx, "exiting unheld spin mutex"); 725 } 726 MUTEX_UNLOCKED(mtx); 727 MUTEX_SPINBIT_LOCK_UNLOCK(mtx); 728 #endif 729 MUTEX_SPIN_SPLRESTORE(mtx); 730 return; 731 } 732 733 #ifndef __HAVE_MUTEX_STUBS 734 /* 735 * On some architectures without mutex stubs, we can enter here to 736 * release mutexes before interrupts and whatnot are up and running. 737 * We need this hack to keep them sweet. 738 */ 739 if (__predict_false(cold)) { 740 MUTEX_UNLOCKED(mtx); 741 MUTEX_RELEASE(mtx); 742 return; 743 } 744 #endif 745 746 curthread = (uintptr_t)curlwp; 747 MUTEX_DASSERT(mtx, curthread != 0); 748 MUTEX_ASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread); 749 MUTEX_UNLOCKED(mtx); 750 #if !defined(LOCKDEBUG) 751 __USE(curthread); 752 #endif 753 754 #ifdef LOCKDEBUG 755 /* 756 * Avoid having to take the turnstile chain lock every time 757 * around. Raise the priority level to splhigh() in order 758 * to disable preemption and so make the following atomic. 759 */ 760 { 761 int s = splhigh(); 762 if (!MUTEX_HAS_WAITERS(mtx)) { 763 MUTEX_RELEASE(mtx); 764 splx(s); 765 return; 766 } 767 splx(s); 768 } 769 #endif 770 771 /* 772 * Get this lock's turnstile. This gets the interlock on 773 * the sleep queue. Once we have that, we can clear the 774 * lock. If there was no turnstile for the lock, there 775 * were no waiters remaining. 776 */ 777 ts = turnstile_lookup(mtx); 778 779 if (ts == NULL) { 780 MUTEX_RELEASE(mtx); 781 turnstile_exit(mtx); 782 } else { 783 MUTEX_RELEASE(mtx); 784 turnstile_wakeup(ts, TS_WRITER_Q, 785 TS_WAITERS(ts, TS_WRITER_Q), NULL); 786 } 787 } 788 789 #ifndef __HAVE_SIMPLE_MUTEXES 790 /* 791 * mutex_wakeup: 792 * 793 * Support routine for mutex_exit() that wakes up all waiters. 794 * We assume that the mutex has been released, but it need not 795 * be. 796 */ 797 void 798 mutex_wakeup(kmutex_t *mtx) 799 { 800 turnstile_t *ts; 801 802 ts = turnstile_lookup(mtx); 803 if (ts == NULL) { 804 turnstile_exit(mtx); 805 return; 806 } 807 MUTEX_CLEAR_WAITERS(mtx); 808 turnstile_wakeup(ts, TS_WRITER_Q, TS_WAITERS(ts, TS_WRITER_Q), NULL); 809 } 810 #endif /* !__HAVE_SIMPLE_MUTEXES */ 811 812 /* 813 * mutex_owned: 814 * 815 * Return true if the current LWP (adaptive) or CPU (spin) 816 * holds the mutex. 817 */ 818 int 819 mutex_owned(const kmutex_t *mtx) 820 { 821 822 if (mtx == NULL) 823 return 0; 824 if (MUTEX_ADAPTIVE_P(mtx->mtx_owner)) 825 return MUTEX_OWNER(mtx->mtx_owner) == (uintptr_t)curlwp; 826 #ifdef FULL 827 return MUTEX_SPINBIT_LOCKED_P(mtx); 828 #else 829 return 1; 830 #endif 831 } 832 833 /* 834 * mutex_owner: 835 * 836 * Return the current owner of an adaptive mutex. Used for 837 * priority inheritance. 838 */ 839 lwp_t * 840 mutex_owner(const kmutex_t *mtx) 841 { 842 843 MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx->mtx_owner)); 844 return (struct lwp *)MUTEX_OWNER(mtx->mtx_owner); 845 } 846 847 /* 848 * mutex_owner_running: 849 * 850 * Return true if an adaptive mutex is unheld, or held and the owner is 851 * running on a CPU. For the pagedaemon only - do not document or use 852 * in other code. 853 */ 854 bool 855 mutex_owner_running(const kmutex_t *mtx) 856 { 857 #ifdef MULTIPROCESSOR 858 uintptr_t owner; 859 bool rv; 860 861 MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx->mtx_owner)); 862 kpreempt_disable(); 863 owner = mtx->mtx_owner; 864 rv = !MUTEX_OWNED(owner) || mutex_oncpu(MUTEX_OWNER(owner)); 865 kpreempt_enable(); 866 return rv; 867 #else 868 return mutex_owner(mtx) == curlwp; 869 #endif 870 } 871 872 /* 873 * mutex_ownable: 874 * 875 * When compiled with DEBUG and LOCKDEBUG defined, ensure that 876 * the mutex is available. We cannot use !mutex_owned() since 877 * that won't work correctly for spin mutexes. 878 */ 879 int 880 mutex_ownable(const kmutex_t *mtx) 881 { 882 883 #ifdef LOCKDEBUG 884 MUTEX_TESTLOCK(mtx); 885 #endif 886 return 1; 887 } 888 889 /* 890 * mutex_tryenter: 891 * 892 * Try to acquire the mutex; return non-zero if we did. 893 */ 894 int 895 mutex_tryenter(kmutex_t *mtx) 896 { 897 uintptr_t curthread; 898 899 /* 900 * Handle spin mutexes. 901 */ 902 if (MUTEX_SPIN_P(mtx->mtx_owner)) { 903 MUTEX_SPIN_SPLRAISE(mtx); 904 #ifdef FULL 905 if (MUTEX_SPINBIT_LOCK_TRY(mtx)) { 906 MUTEX_WANTLOCK(mtx); 907 MUTEX_LOCKED(mtx); 908 return 1; 909 } 910 MUTEX_SPIN_SPLRESTORE(mtx); 911 #else 912 MUTEX_WANTLOCK(mtx); 913 MUTEX_LOCKED(mtx); 914 return 1; 915 #endif 916 } else { 917 curthread = (uintptr_t)curlwp; 918 MUTEX_ASSERT(mtx, curthread != 0); 919 if (MUTEX_ACQUIRE(mtx, curthread)) { 920 MUTEX_WANTLOCK(mtx); 921 MUTEX_LOCKED(mtx); 922 MUTEX_DASSERT(mtx, 923 MUTEX_OWNER(mtx->mtx_owner) == curthread); 924 return 1; 925 } 926 } 927 928 return 0; 929 } 930 931 #if defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) 932 /* 933 * mutex_spin_retry: 934 * 935 * Support routine for mutex_spin_enter(). Assumes that the caller 936 * has already raised the SPL, and adjusted counters. 937 */ 938 void 939 mutex_spin_retry(kmutex_t *mtx) 940 { 941 #ifdef MULTIPROCESSOR 942 u_int count; 943 LOCKSTAT_TIMER(spintime); 944 LOCKSTAT_FLAG(lsflag); 945 #ifdef LOCKDEBUG 946 u_int spins = 0; 947 #endif /* LOCKDEBUG */ 948 949 MUTEX_WANTLOCK(mtx); 950 951 LOCKSTAT_ENTER(lsflag); 952 LOCKSTAT_START_TIMER(lsflag, spintime); 953 count = SPINLOCK_BACKOFF_MIN; 954 955 /* 956 * Spin testing the lock word and do exponential backoff 957 * to reduce cache line ping-ponging between CPUs. 958 */ 959 do { 960 while (MUTEX_SPINBIT_LOCKED_P(mtx)) { 961 SPINLOCK_BACKOFF(count); 962 #ifdef LOCKDEBUG 963 if (SPINLOCK_SPINOUT(spins)) 964 MUTEX_ABORT(mtx, "spinout"); 965 #endif /* LOCKDEBUG */ 966 } 967 } while (!MUTEX_SPINBIT_LOCK_TRY(mtx)); 968 969 LOCKSTAT_STOP_TIMER(lsflag, spintime); 970 LOCKSTAT_EVENT(lsflag, mtx, LB_SPIN_MUTEX | LB_SPIN, 1, spintime); 971 LOCKSTAT_EXIT(lsflag); 972 973 MUTEX_LOCKED(mtx); 974 #else /* MULTIPROCESSOR */ 975 MUTEX_ABORT(mtx, "locking against myself"); 976 #endif /* MULTIPROCESSOR */ 977 } 978 #endif /* defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) */ 979