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