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