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