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