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