1 /* $NetBSD: kern_mutex.c,v 1.70 2018/01/30 07:52:22 ozaki-r Exp $ */ 2 3 /*- 4 * Copyright (c) 2002, 2006, 2007, 2008 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.70 2018/01/30 07:52:22 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 58 #include <dev/lockstat.h> 59 60 #include <machine/lock.h> 61 62 /* 63 * When not running a debug kernel, spin mutexes are not much 64 * more than an splraiseipl() and splx() pair. 65 */ 66 67 #if defined(DIAGNOSTIC) || defined(MULTIPROCESSOR) || defined(LOCKDEBUG) 68 #define FULL 69 #endif 70 71 /* 72 * Debugging support. 73 */ 74 75 #define MUTEX_WANTLOCK(mtx) \ 76 LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \ 77 (uintptr_t)__builtin_return_address(0), 0) 78 #define MUTEX_TESTLOCK(mtx) \ 79 LOCKDEBUG_WANTLOCK(MUTEX_DEBUG_P(mtx), (mtx), \ 80 (uintptr_t)__builtin_return_address(0), -1) 81 #define MUTEX_LOCKED(mtx) \ 82 LOCKDEBUG_LOCKED(MUTEX_DEBUG_P(mtx), (mtx), NULL, \ 83 (uintptr_t)__builtin_return_address(0), 0) 84 #define MUTEX_UNLOCKED(mtx) \ 85 LOCKDEBUG_UNLOCKED(MUTEX_DEBUG_P(mtx), (mtx), \ 86 (uintptr_t)__builtin_return_address(0), 0) 87 #define MUTEX_ABORT(mtx, msg) \ 88 mutex_abort(__func__, __LINE__, mtx, msg) 89 90 #if defined(LOCKDEBUG) 91 92 #define MUTEX_DASSERT(mtx, cond) \ 93 do { \ 94 if (!(cond)) \ 95 MUTEX_ABORT(mtx, "assertion failed: " #cond); \ 96 } while (/* CONSTCOND */ 0); 97 98 #else /* LOCKDEBUG */ 99 100 #define MUTEX_DASSERT(mtx, cond) /* nothing */ 101 102 #endif /* LOCKDEBUG */ 103 104 #if defined(DIAGNOSTIC) 105 106 #define MUTEX_ASSERT(mtx, cond) \ 107 do { \ 108 if (!(cond)) \ 109 MUTEX_ABORT(mtx, "assertion failed: " #cond); \ 110 } while (/* CONSTCOND */ 0) 111 112 #else /* DIAGNOSTIC */ 113 114 #define MUTEX_ASSERT(mtx, cond) /* nothing */ 115 116 #endif /* DIAGNOSTIC */ 117 118 /* 119 * Some architectures can't use __cpu_simple_lock as is so allow a way 120 * for them to use an alternate definition. 121 */ 122 #ifndef MUTEX_SPINBIT_LOCK_INIT 123 #define MUTEX_SPINBIT_LOCK_INIT(mtx) __cpu_simple_lock_init(&(mtx)->mtx_lock) 124 #endif 125 #ifndef MUTEX_SPINBIT_LOCKED_P 126 #define MUTEX_SPINBIT_LOCKED_P(mtx) __SIMPLELOCK_LOCKED_P(&(mtx)->mtx_lock) 127 #endif 128 #ifndef MUTEX_SPINBIT_LOCK_TRY 129 #define MUTEX_SPINBIT_LOCK_TRY(mtx) __cpu_simple_lock_try(&(mtx)->mtx_lock) 130 #endif 131 #ifndef MUTEX_SPINBIT_LOCK_UNLOCK 132 #define MUTEX_SPINBIT_LOCK_UNLOCK(mtx) __cpu_simple_unlock(&(mtx)->mtx_lock) 133 #endif 134 135 #ifndef MUTEX_INITIALIZE_SPIN_IPL 136 #define MUTEX_INITIALIZE_SPIN_IPL(mtx, ipl) \ 137 ((mtx)->mtx_ipl = makeiplcookie((ipl))) 138 #endif 139 140 /* 141 * Spin mutex SPL save / restore. 142 */ 143 144 #define MUTEX_SPIN_SPLRAISE(mtx) \ 145 do { \ 146 struct cpu_info *x__ci; \ 147 int x__cnt, s; \ 148 s = splraiseipl(MUTEX_SPIN_IPL(mtx)); \ 149 x__ci = curcpu(); \ 150 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 *x__ci = curcpu(); \ 159 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 * For architectures that provide 'simple' mutexes: they provide a 167 * CAS function that is either MP-safe, or does not need to be MP 168 * safe. Adaptive mutexes on these architectures do not require an 169 * additional interlock. 170 */ 171 172 #ifdef __HAVE_SIMPLE_MUTEXES 173 174 #define MUTEX_OWNER(owner) \ 175 (owner & MUTEX_THREAD) 176 #define MUTEX_HAS_WAITERS(mtx) \ 177 (((int)(mtx)->mtx_owner & MUTEX_BIT_WAITERS) != 0) 178 179 #define MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug) \ 180 if (!dodebug) \ 181 (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \ 182 do { \ 183 } while (/* CONSTCOND */ 0); 184 185 #define MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl) \ 186 do { \ 187 (mtx)->mtx_owner = MUTEX_BIT_SPIN; \ 188 if (!dodebug) \ 189 (mtx)->mtx_owner |= MUTEX_BIT_NODEBUG; \ 190 MUTEX_INITIALIZE_SPIN_IPL((mtx), (ipl)); \ 191 MUTEX_SPINBIT_LOCK_INIT((mtx)); \ 192 } while (/* CONSTCOND */ 0) 193 194 #define MUTEX_DESTROY(mtx) \ 195 do { \ 196 (mtx)->mtx_owner = MUTEX_THREAD; \ 197 } while (/* CONSTCOND */ 0); 198 199 #define MUTEX_SPIN_P(mtx) \ 200 (((mtx)->mtx_owner & MUTEX_BIT_SPIN) != 0) 201 #define MUTEX_ADAPTIVE_P(mtx) \ 202 (((mtx)->mtx_owner & MUTEX_BIT_SPIN) == 0) 203 204 #define MUTEX_DEBUG_P(mtx) (((mtx)->mtx_owner & MUTEX_BIT_NODEBUG) == 0) 205 #if defined(LOCKDEBUG) 206 #define MUTEX_OWNED(owner) (((owner) & ~MUTEX_BIT_NODEBUG) != 0) 207 #define MUTEX_INHERITDEBUG(n, o) (n) |= (o) & MUTEX_BIT_NODEBUG 208 #else /* defined(LOCKDEBUG) */ 209 #define MUTEX_OWNED(owner) ((owner) != 0) 210 #define MUTEX_INHERITDEBUG(n, o) /* nothing */ 211 #endif /* defined(LOCKDEBUG) */ 212 213 static inline int 214 MUTEX_ACQUIRE(kmutex_t *mtx, uintptr_t curthread) 215 { 216 int rv; 217 uintptr_t oldown = 0; 218 uintptr_t newown = curthread; 219 220 MUTEX_INHERITDEBUG(oldown, mtx->mtx_owner); 221 MUTEX_INHERITDEBUG(newown, oldown); 222 rv = MUTEX_CAS(&mtx->mtx_owner, oldown, newown); 223 MUTEX_RECEIVE(mtx); 224 return rv; 225 } 226 227 static inline int 228 MUTEX_SET_WAITERS(kmutex_t *mtx, uintptr_t owner) 229 { 230 int rv; 231 rv = MUTEX_CAS(&mtx->mtx_owner, owner, owner | MUTEX_BIT_WAITERS); 232 MUTEX_RECEIVE(mtx); 233 return rv; 234 } 235 236 static inline void 237 MUTEX_RELEASE(kmutex_t *mtx) 238 { 239 uintptr_t newown; 240 241 MUTEX_GIVE(mtx); 242 newown = 0; 243 MUTEX_INHERITDEBUG(newown, mtx->mtx_owner); 244 mtx->mtx_owner = newown; 245 } 246 #endif /* __HAVE_SIMPLE_MUTEXES */ 247 248 /* 249 * Patch in stubs via strong alias where they are not available. 250 */ 251 252 #if defined(LOCKDEBUG) 253 #undef __HAVE_MUTEX_STUBS 254 #undef __HAVE_SPIN_MUTEX_STUBS 255 #endif 256 257 #ifndef __HAVE_MUTEX_STUBS 258 __strong_alias(mutex_enter,mutex_vector_enter); 259 __strong_alias(mutex_exit,mutex_vector_exit); 260 #endif 261 262 #ifndef __HAVE_SPIN_MUTEX_STUBS 263 __strong_alias(mutex_spin_enter,mutex_vector_enter); 264 __strong_alias(mutex_spin_exit,mutex_vector_exit); 265 #endif 266 267 static void mutex_abort(const char *, size_t, const kmutex_t *, 268 const char *); 269 static void mutex_dump(const volatile void *); 270 271 lockops_t mutex_spin_lockops = { 272 .lo_name = "Mutex", 273 .lo_type = LOCKOPS_SPIN, 274 .lo_dump = mutex_dump, 275 }; 276 277 lockops_t mutex_adaptive_lockops = { 278 .lo_name = "Mutex", 279 .lo_type = LOCKOPS_SLEEP, 280 .lo_dump = mutex_dump, 281 }; 282 283 syncobj_t mutex_syncobj = { 284 .sobj_flag = SOBJ_SLEEPQ_SORTED, 285 .sobj_unsleep = turnstile_unsleep, 286 .sobj_changepri = turnstile_changepri, 287 .sobj_lendpri = sleepq_lendpri, 288 .sobj_owner = (void *)mutex_owner, 289 }; 290 291 /* 292 * mutex_dump: 293 * 294 * Dump the contents of a mutex structure. 295 */ 296 void 297 mutex_dump(const volatile void *cookie) 298 { 299 const volatile kmutex_t *mtx = cookie; 300 301 printf_nolog("owner field : %#018lx wait/spin: %16d/%d\n", 302 (long)MUTEX_OWNER(mtx->mtx_owner), MUTEX_HAS_WAITERS(mtx), 303 MUTEX_SPIN_P(mtx)); 304 } 305 306 /* 307 * mutex_abort: 308 * 309 * Dump information about an error and panic the system. This 310 * generates a lot of machine code in the DIAGNOSTIC case, so 311 * we ask the compiler to not inline it. 312 */ 313 void __noinline 314 mutex_abort(const char *func, size_t line, const kmutex_t *mtx, const char *msg) 315 { 316 317 LOCKDEBUG_ABORT(func, line, mtx, (MUTEX_SPIN_P(mtx) ? 318 &mutex_spin_lockops : &mutex_adaptive_lockops), msg); 319 } 320 321 /* 322 * mutex_init: 323 * 324 * Initialize a mutex for use. Note that adaptive mutexes are in 325 * essence spin mutexes that can sleep to avoid deadlock and wasting 326 * CPU time. We can't easily provide a type of mutex that always 327 * sleeps - see comments in mutex_vector_enter() about releasing 328 * mutexes unlocked. 329 */ 330 void 331 mutex_init(kmutex_t *mtx, kmutex_type_t type, int ipl) 332 { 333 bool dodebug; 334 335 memset(mtx, 0, sizeof(*mtx)); 336 337 switch (type) { 338 case MUTEX_ADAPTIVE: 339 KASSERT(ipl == IPL_NONE); 340 break; 341 case MUTEX_DEFAULT: 342 case MUTEX_DRIVER: 343 if (ipl == IPL_NONE || ipl == IPL_SOFTCLOCK || 344 ipl == IPL_SOFTBIO || ipl == IPL_SOFTNET || 345 ipl == IPL_SOFTSERIAL) { 346 type = MUTEX_ADAPTIVE; 347 } else { 348 type = MUTEX_SPIN; 349 } 350 break; 351 default: 352 break; 353 } 354 355 switch (type) { 356 case MUTEX_NODEBUG: 357 dodebug = LOCKDEBUG_ALLOC(mtx, NULL, 358 (uintptr_t)__builtin_return_address(0)); 359 MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl); 360 break; 361 case MUTEX_ADAPTIVE: 362 dodebug = LOCKDEBUG_ALLOC(mtx, &mutex_adaptive_lockops, 363 (uintptr_t)__builtin_return_address(0)); 364 MUTEX_INITIALIZE_ADAPTIVE(mtx, dodebug); 365 break; 366 case MUTEX_SPIN: 367 dodebug = LOCKDEBUG_ALLOC(mtx, &mutex_spin_lockops, 368 (uintptr_t)__builtin_return_address(0)); 369 MUTEX_INITIALIZE_SPIN(mtx, dodebug, ipl); 370 break; 371 default: 372 panic("mutex_init: impossible type"); 373 break; 374 } 375 } 376 377 /* 378 * mutex_destroy: 379 * 380 * Tear down a mutex. 381 */ 382 void 383 mutex_destroy(kmutex_t *mtx) 384 { 385 386 if (MUTEX_ADAPTIVE_P(mtx)) { 387 MUTEX_ASSERT(mtx, !MUTEX_OWNED(mtx->mtx_owner) && 388 !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 if (MUTEX_SPIN_P(mtx)) { 460 #if defined(LOCKDEBUG) && defined(MULTIPROCESSOR) 461 u_int spins = 0; 462 #endif 463 MUTEX_SPIN_SPLRAISE(mtx); 464 MUTEX_WANTLOCK(mtx); 465 #ifdef FULL 466 if (MUTEX_SPINBIT_LOCK_TRY(mtx)) { 467 MUTEX_LOCKED(mtx); 468 return; 469 } 470 #if !defined(MULTIPROCESSOR) 471 MUTEX_ABORT(mtx, "locking against myself"); 472 #else /* !MULTIPROCESSOR */ 473 474 LOCKSTAT_ENTER(lsflag); 475 LOCKSTAT_START_TIMER(lsflag, spintime); 476 count = SPINLOCK_BACKOFF_MIN; 477 478 /* 479 * Spin testing the lock word and do exponential backoff 480 * to reduce cache line ping-ponging between CPUs. 481 */ 482 do { 483 if (panicstr != NULL) 484 break; 485 while (MUTEX_SPINBIT_LOCKED_P(mtx)) { 486 SPINLOCK_BACKOFF(count); 487 #ifdef LOCKDEBUG 488 if (SPINLOCK_SPINOUT(spins)) 489 MUTEX_ABORT(mtx, "spinout"); 490 #endif /* LOCKDEBUG */ 491 } 492 } while (!MUTEX_SPINBIT_LOCK_TRY(mtx)); 493 494 if (count != SPINLOCK_BACKOFF_MIN) { 495 LOCKSTAT_STOP_TIMER(lsflag, spintime); 496 LOCKSTAT_EVENT(lsflag, mtx, 497 LB_SPIN_MUTEX | LB_SPIN, 1, spintime); 498 } 499 LOCKSTAT_EXIT(lsflag); 500 #endif /* !MULTIPROCESSOR */ 501 #endif /* FULL */ 502 MUTEX_LOCKED(mtx); 503 return; 504 } 505 506 curthread = (uintptr_t)curlwp; 507 508 MUTEX_DASSERT(mtx, MUTEX_ADAPTIVE_P(mtx)); 509 MUTEX_ASSERT(mtx, curthread != 0); 510 MUTEX_WANTLOCK(mtx); 511 512 if (panicstr == NULL) { 513 LOCKDEBUG_BARRIER(&kernel_lock, 1); 514 } 515 516 LOCKSTAT_ENTER(lsflag); 517 518 /* 519 * Adaptive mutex; spin trying to acquire the mutex. If we 520 * determine that the owner is not running on a processor, 521 * then we stop spinning, and sleep instead. 522 */ 523 KPREEMPT_DISABLE(curlwp); 524 for (owner = mtx->mtx_owner;;) { 525 if (!MUTEX_OWNED(owner)) { 526 /* 527 * Mutex owner clear could mean two things: 528 * 529 * * The mutex has been released. 530 * * The owner field hasn't been set yet. 531 * 532 * Try to acquire it again. If that fails, 533 * we'll just loop again. 534 */ 535 if (MUTEX_ACQUIRE(mtx, curthread)) 536 break; 537 owner = mtx->mtx_owner; 538 continue; 539 } 540 if (__predict_false(panicstr != NULL)) { 541 KPREEMPT_ENABLE(curlwp); 542 return; 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 mi_switch() posts a store fence before 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 if ((membar_consumer(), mutex_oncpu(owner)) || 677 (membar_consumer(), !MUTEX_HAS_WAITERS(mtx))) { 678 turnstile_exit(mtx); 679 owner = mtx->mtx_owner; 680 continue; 681 } 682 #endif /* MULTIPROCESSOR */ 683 684 LOCKSTAT_START_TIMER(lsflag, slptime); 685 686 turnstile_block(ts, TS_WRITER_Q, mtx, &mutex_syncobj); 687 688 LOCKSTAT_STOP_TIMER(lsflag, slptime); 689 LOCKSTAT_COUNT(slpcnt, 1); 690 691 owner = mtx->mtx_owner; 692 } 693 KPREEMPT_ENABLE(curlwp); 694 695 LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SLEEP1, 696 slpcnt, slptime); 697 LOCKSTAT_EVENT(lsflag, mtx, LB_ADAPTIVE_MUTEX | LB_SPIN, 698 spincnt, spintime); 699 LOCKSTAT_EXIT(lsflag); 700 701 MUTEX_DASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread); 702 MUTEX_LOCKED(mtx); 703 } 704 705 /* 706 * mutex_vector_exit: 707 * 708 * Support routine for mutex_exit() that handles all cases. 709 */ 710 void 711 mutex_vector_exit(kmutex_t *mtx) 712 { 713 turnstile_t *ts; 714 uintptr_t curthread; 715 716 if (MUTEX_SPIN_P(mtx)) { 717 #ifdef FULL 718 if (__predict_false(!MUTEX_SPINBIT_LOCKED_P(mtx))) { 719 if (panicstr != NULL) 720 return; 721 MUTEX_ABORT(mtx, "exiting unheld spin mutex"); 722 } 723 MUTEX_UNLOCKED(mtx); 724 MUTEX_SPINBIT_LOCK_UNLOCK(mtx); 725 #endif 726 MUTEX_SPIN_SPLRESTORE(mtx); 727 return; 728 } 729 730 if (__predict_false((uintptr_t)panicstr | cold)) { 731 MUTEX_UNLOCKED(mtx); 732 MUTEX_RELEASE(mtx); 733 return; 734 } 735 736 curthread = (uintptr_t)curlwp; 737 MUTEX_DASSERT(mtx, curthread != 0); 738 MUTEX_ASSERT(mtx, MUTEX_OWNER(mtx->mtx_owner) == curthread); 739 MUTEX_UNLOCKED(mtx); 740 #if !defined(LOCKDEBUG) 741 __USE(curthread); 742 #endif 743 744 #ifdef LOCKDEBUG 745 /* 746 * Avoid having to take the turnstile chain lock every time 747 * around. Raise the priority level to splhigh() in order 748 * to disable preemption and so make the following atomic. 749 */ 750 { 751 int s = splhigh(); 752 if (!MUTEX_HAS_WAITERS(mtx)) { 753 MUTEX_RELEASE(mtx); 754 splx(s); 755 return; 756 } 757 splx(s); 758 } 759 #endif 760 761 /* 762 * Get this lock's turnstile. This gets the interlock on 763 * the sleep queue. Once we have that, we can clear the 764 * lock. If there was no turnstile for the lock, there 765 * were no waiters remaining. 766 */ 767 ts = turnstile_lookup(mtx); 768 769 if (ts == NULL) { 770 MUTEX_RELEASE(mtx); 771 turnstile_exit(mtx); 772 } else { 773 MUTEX_RELEASE(mtx); 774 turnstile_wakeup(ts, TS_WRITER_Q, 775 TS_WAITERS(ts, TS_WRITER_Q), NULL); 776 } 777 } 778 779 #ifndef __HAVE_SIMPLE_MUTEXES 780 /* 781 * mutex_wakeup: 782 * 783 * Support routine for mutex_exit() that wakes up all waiters. 784 * We assume that the mutex has been released, but it need not 785 * be. 786 */ 787 void 788 mutex_wakeup(kmutex_t *mtx) 789 { 790 turnstile_t *ts; 791 792 ts = turnstile_lookup(mtx); 793 if (ts == NULL) { 794 turnstile_exit(mtx); 795 return; 796 } 797 MUTEX_CLEAR_WAITERS(mtx); 798 turnstile_wakeup(ts, TS_WRITER_Q, TS_WAITERS(ts, TS_WRITER_Q), NULL); 799 } 800 #endif /* !__HAVE_SIMPLE_MUTEXES */ 801 802 /* 803 * mutex_owned: 804 * 805 * Return true if the current LWP (adaptive) or CPU (spin) 806 * holds the mutex. 807 */ 808 int 809 mutex_owned(const kmutex_t *mtx) 810 { 811 812 if (mtx == NULL) 813 return 0; 814 if (MUTEX_ADAPTIVE_P(mtx)) 815 return MUTEX_OWNER(mtx->mtx_owner) == (uintptr_t)curlwp; 816 #ifdef FULL 817 return MUTEX_SPINBIT_LOCKED_P(mtx); 818 #else 819 return 1; 820 #endif 821 } 822 823 /* 824 * mutex_owner: 825 * 826 * Return the current owner of an adaptive mutex. Used for 827 * priority inheritance. 828 */ 829 lwp_t * 830 mutex_owner(const kmutex_t *mtx) 831 { 832 833 MUTEX_ASSERT(mtx, MUTEX_ADAPTIVE_P(mtx)); 834 return (struct lwp *)MUTEX_OWNER(mtx->mtx_owner); 835 } 836 837 /* 838 * mutex_ownable: 839 * 840 * When compiled with DEBUG and LOCKDEBUG defined, ensure that 841 * the mutex is available. We cannot use !mutex_owned() since 842 * that won't work correctly for spin mutexes. 843 */ 844 int 845 mutex_ownable(const kmutex_t *mtx) 846 { 847 848 #ifdef LOCKDEBUG 849 MUTEX_TESTLOCK(mtx); 850 #endif 851 return 1; 852 } 853 854 /* 855 * mutex_tryenter: 856 * 857 * Try to acquire the mutex; return non-zero if we did. 858 */ 859 int 860 mutex_tryenter(kmutex_t *mtx) 861 { 862 uintptr_t curthread; 863 864 /* 865 * Handle spin mutexes. 866 */ 867 if (MUTEX_SPIN_P(mtx)) { 868 MUTEX_SPIN_SPLRAISE(mtx); 869 #ifdef FULL 870 if (MUTEX_SPINBIT_LOCK_TRY(mtx)) { 871 MUTEX_WANTLOCK(mtx); 872 MUTEX_LOCKED(mtx); 873 return 1; 874 } 875 MUTEX_SPIN_SPLRESTORE(mtx); 876 #else 877 MUTEX_WANTLOCK(mtx); 878 MUTEX_LOCKED(mtx); 879 return 1; 880 #endif 881 } else { 882 curthread = (uintptr_t)curlwp; 883 MUTEX_ASSERT(mtx, curthread != 0); 884 if (MUTEX_ACQUIRE(mtx, curthread)) { 885 MUTEX_WANTLOCK(mtx); 886 MUTEX_LOCKED(mtx); 887 MUTEX_DASSERT(mtx, 888 MUTEX_OWNER(mtx->mtx_owner) == curthread); 889 return 1; 890 } 891 } 892 893 return 0; 894 } 895 896 #if defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) 897 /* 898 * mutex_spin_retry: 899 * 900 * Support routine for mutex_spin_enter(). Assumes that the caller 901 * has already raised the SPL, and adjusted counters. 902 */ 903 void 904 mutex_spin_retry(kmutex_t *mtx) 905 { 906 #ifdef MULTIPROCESSOR 907 u_int count; 908 LOCKSTAT_TIMER(spintime); 909 LOCKSTAT_FLAG(lsflag); 910 #ifdef LOCKDEBUG 911 u_int spins = 0; 912 #endif /* LOCKDEBUG */ 913 914 MUTEX_WANTLOCK(mtx); 915 916 LOCKSTAT_ENTER(lsflag); 917 LOCKSTAT_START_TIMER(lsflag, spintime); 918 count = SPINLOCK_BACKOFF_MIN; 919 920 /* 921 * Spin testing the lock word and do exponential backoff 922 * to reduce cache line ping-ponging between CPUs. 923 */ 924 do { 925 if (panicstr != NULL) 926 break; 927 while (MUTEX_SPINBIT_LOCKED_P(mtx)) { 928 SPINLOCK_BACKOFF(count); 929 #ifdef LOCKDEBUG 930 if (SPINLOCK_SPINOUT(spins)) 931 MUTEX_ABORT(mtx, "spinout"); 932 #endif /* LOCKDEBUG */ 933 } 934 } while (!MUTEX_SPINBIT_LOCK_TRY(mtx)); 935 936 LOCKSTAT_STOP_TIMER(lsflag, spintime); 937 LOCKSTAT_EVENT(lsflag, mtx, LB_SPIN_MUTEX | LB_SPIN, 1, spintime); 938 LOCKSTAT_EXIT(lsflag); 939 940 MUTEX_LOCKED(mtx); 941 #else /* MULTIPROCESSOR */ 942 MUTEX_ABORT(mtx, "locking against myself"); 943 #endif /* MULTIPROCESSOR */ 944 } 945 #endif /* defined(__HAVE_SPIN_MUTEX_STUBS) || defined(FULL) */ 946