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