1 /*- 2 * Copyright (c) 2007 Attilio Rao <attilio@freebsd.org> 3 * Copyright (c) 2001 Jason Evans <jasone@freebsd.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice(s), this list of conditions and the following disclaimer as 11 * the first lines of this file unmodified other than the possible 12 * addition of one or more copyright notices. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice(s), this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY 18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 20 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY 21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 24 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 27 * DAMAGE. 28 */ 29 30 /* 31 * Shared/exclusive locks. This implementation attempts to ensure 32 * deterministic lock granting behavior, so that slocks and xlocks are 33 * interleaved. 34 * 35 * Priority propagation will not generally raise the priority of lock holders, 36 * so should not be relied upon in combination with sx locks. 37 */ 38 39 #include "opt_adaptive_sx.h" 40 #include "opt_ddb.h" 41 42 #include <sys/cdefs.h> 43 __FBSDID("$FreeBSD$"); 44 45 #include <sys/param.h> 46 #include <sys/ktr.h> 47 #include <sys/lock.h> 48 #include <sys/mutex.h> 49 #include <sys/proc.h> 50 #include <sys/sleepqueue.h> 51 #include <sys/sx.h> 52 #include <sys/systm.h> 53 54 #ifdef ADAPTIVE_SX 55 #include <machine/cpu.h> 56 #endif 57 58 #ifdef DDB 59 #include <ddb/ddb.h> 60 #endif 61 62 #if !defined(SMP) && defined(ADAPTIVE_SX) 63 #error "You must have SMP to enable the ADAPTIVE_SX option" 64 #endif 65 66 CTASSERT(((SX_ADAPTIVESPIN | SX_RECURSE) & LO_CLASSFLAGS) == 67 (SX_ADAPTIVESPIN | SX_RECURSE)); 68 69 /* Handy macros for sleep queues. */ 70 #define SQ_EXCLUSIVE_QUEUE 0 71 #define SQ_SHARED_QUEUE 1 72 73 /* 74 * Variations on DROP_GIANT()/PICKUP_GIANT() for use in this file. We 75 * drop Giant anytime we have to sleep or if we adaptively spin. 76 */ 77 #define GIANT_DECLARE \ 78 int _giantcnt = 0; \ 79 WITNESS_SAVE_DECL(Giant) \ 80 81 #define GIANT_SAVE() do { \ 82 if (mtx_owned(&Giant)) { \ 83 WITNESS_SAVE(&Giant.lock_object, Giant); \ 84 while (mtx_owned(&Giant)) { \ 85 _giantcnt++; \ 86 mtx_unlock(&Giant); \ 87 } \ 88 } \ 89 } while (0) 90 91 #define GIANT_RESTORE() do { \ 92 if (_giantcnt > 0) { \ 93 mtx_assert(&Giant, MA_NOTOWNED); \ 94 while (_giantcnt--) \ 95 mtx_lock(&Giant); \ 96 WITNESS_RESTORE(&Giant.lock_object, Giant); \ 97 } \ 98 } while (0) 99 100 /* 101 * Returns true if an exclusive lock is recursed. It assumes 102 * curthread currently has an exclusive lock. 103 */ 104 #define sx_recurse lock_object.lo_data 105 #define sx_recursed(sx) ((sx)->sx_recurse != 0) 106 107 static void assert_sx(struct lock_object *lock, int what); 108 #ifdef DDB 109 static void db_show_sx(struct lock_object *lock); 110 #endif 111 static void lock_sx(struct lock_object *lock, int how); 112 static int unlock_sx(struct lock_object *lock); 113 114 struct lock_class lock_class_sx = { 115 .lc_name = "sx", 116 .lc_flags = LC_SLEEPLOCK | LC_SLEEPABLE | LC_RECURSABLE | LC_UPGRADABLE, 117 .lc_assert = assert_sx, 118 #ifdef DDB 119 .lc_ddb_show = db_show_sx, 120 #endif 121 .lc_lock = lock_sx, 122 .lc_unlock = unlock_sx, 123 }; 124 125 #ifndef INVARIANTS 126 #define _sx_assert(sx, what, file, line) 127 #endif 128 129 void 130 assert_sx(struct lock_object *lock, int what) 131 { 132 133 sx_assert((struct sx *)lock, what); 134 } 135 136 void 137 lock_sx(struct lock_object *lock, int how) 138 { 139 struct sx *sx; 140 141 sx = (struct sx *)lock; 142 if (how) 143 sx_xlock(sx); 144 else 145 sx_slock(sx); 146 } 147 148 int 149 unlock_sx(struct lock_object *lock) 150 { 151 struct sx *sx; 152 153 sx = (struct sx *)lock; 154 sx_assert(sx, SA_LOCKED | SA_NOTRECURSED); 155 if (sx_xlocked(sx)) { 156 sx_xunlock(sx); 157 return (1); 158 } else { 159 sx_sunlock(sx); 160 return (0); 161 } 162 } 163 164 void 165 sx_sysinit(void *arg) 166 { 167 struct sx_args *sargs = arg; 168 169 sx_init(sargs->sa_sx, sargs->sa_desc); 170 } 171 172 void 173 sx_init_flags(struct sx *sx, const char *description, int opts) 174 { 175 int flags; 176 177 MPASS((opts & ~(SX_QUIET | SX_RECURSE | SX_NOWITNESS | SX_DUPOK | 178 SX_NOPROFILE | SX_ADAPTIVESPIN)) == 0); 179 180 flags = LO_RECURSABLE | LO_SLEEPABLE | LO_UPGRADABLE; 181 if (opts & SX_DUPOK) 182 flags |= LO_DUPOK; 183 if (opts & SX_NOPROFILE) 184 flags |= LO_NOPROFILE; 185 if (!(opts & SX_NOWITNESS)) 186 flags |= LO_WITNESS; 187 if (opts & SX_QUIET) 188 flags |= LO_QUIET; 189 190 flags |= opts & (SX_ADAPTIVESPIN | SX_RECURSE); 191 sx->sx_lock = SX_LOCK_UNLOCKED; 192 sx->sx_recurse = 0; 193 lock_init(&sx->lock_object, &lock_class_sx, description, NULL, flags); 194 } 195 196 void 197 sx_destroy(struct sx *sx) 198 { 199 200 KASSERT(sx->sx_lock == SX_LOCK_UNLOCKED, ("sx lock still held")); 201 KASSERT(sx->sx_recurse == 0, ("sx lock still recursed")); 202 sx->sx_lock = SX_LOCK_DESTROYED; 203 lock_destroy(&sx->lock_object); 204 } 205 206 int 207 _sx_slock(struct sx *sx, int opts, const char *file, int line) 208 { 209 int error = 0; 210 211 MPASS(curthread != NULL); 212 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 213 ("sx_slock() of destroyed sx @ %s:%d", file, line)); 214 WITNESS_CHECKORDER(&sx->lock_object, LOP_NEWORDER, file, line, NULL); 215 error = __sx_slock(sx, opts, file, line); 216 if (!error) { 217 LOCK_LOG_LOCK("SLOCK", &sx->lock_object, 0, 0, file, line); 218 WITNESS_LOCK(&sx->lock_object, 0, file, line); 219 curthread->td_locks++; 220 } 221 222 return (error); 223 } 224 225 int 226 _sx_try_slock(struct sx *sx, const char *file, int line) 227 { 228 uintptr_t x; 229 230 for (;;) { 231 x = sx->sx_lock; 232 KASSERT(x != SX_LOCK_DESTROYED, 233 ("sx_try_slock() of destroyed sx @ %s:%d", file, line)); 234 if (!(x & SX_LOCK_SHARED)) 235 break; 236 if (atomic_cmpset_acq_ptr(&sx->sx_lock, x, x + SX_ONE_SHARER)) { 237 LOCK_LOG_TRY("SLOCK", &sx->lock_object, 0, 1, file, line); 238 WITNESS_LOCK(&sx->lock_object, LOP_TRYLOCK, file, line); 239 curthread->td_locks++; 240 return (1); 241 } 242 } 243 244 LOCK_LOG_TRY("SLOCK", &sx->lock_object, 0, 0, file, line); 245 return (0); 246 } 247 248 int 249 _sx_xlock(struct sx *sx, int opts, const char *file, int line) 250 { 251 int error = 0; 252 253 MPASS(curthread != NULL); 254 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 255 ("sx_xlock() of destroyed sx @ %s:%d", file, line)); 256 WITNESS_CHECKORDER(&sx->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file, 257 line, NULL); 258 error = __sx_xlock(sx, curthread, opts, file, line); 259 if (!error) { 260 LOCK_LOG_LOCK("XLOCK", &sx->lock_object, 0, sx->sx_recurse, 261 file, line); 262 WITNESS_LOCK(&sx->lock_object, LOP_EXCLUSIVE, file, line); 263 curthread->td_locks++; 264 } 265 266 return (error); 267 } 268 269 int 270 _sx_try_xlock(struct sx *sx, const char *file, int line) 271 { 272 int rval; 273 274 MPASS(curthread != NULL); 275 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 276 ("sx_try_xlock() of destroyed sx @ %s:%d", file, line)); 277 278 if (sx_xlocked(sx) && (sx->lock_object.lo_flags & SX_RECURSE) != 0) { 279 sx->sx_recurse++; 280 atomic_set_ptr(&sx->sx_lock, SX_LOCK_RECURSED); 281 rval = 1; 282 } else 283 rval = atomic_cmpset_acq_ptr(&sx->sx_lock, SX_LOCK_UNLOCKED, 284 (uintptr_t)curthread); 285 LOCK_LOG_TRY("XLOCK", &sx->lock_object, 0, rval, file, line); 286 if (rval) { 287 WITNESS_LOCK(&sx->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 288 file, line); 289 curthread->td_locks++; 290 } 291 292 return (rval); 293 } 294 295 void 296 _sx_sunlock(struct sx *sx, const char *file, int line) 297 { 298 299 MPASS(curthread != NULL); 300 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 301 ("sx_sunlock() of destroyed sx @ %s:%d", file, line)); 302 _sx_assert(sx, SA_SLOCKED, file, line); 303 curthread->td_locks--; 304 WITNESS_UNLOCK(&sx->lock_object, 0, file, line); 305 LOCK_LOG_LOCK("SUNLOCK", &sx->lock_object, 0, 0, file, line); 306 __sx_sunlock(sx, file, line); 307 lock_profile_release_lock(&sx->lock_object); 308 } 309 310 void 311 _sx_xunlock(struct sx *sx, const char *file, int line) 312 { 313 314 MPASS(curthread != NULL); 315 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 316 ("sx_xunlock() of destroyed sx @ %s:%d", file, line)); 317 _sx_assert(sx, SA_XLOCKED, file, line); 318 curthread->td_locks--; 319 WITNESS_UNLOCK(&sx->lock_object, LOP_EXCLUSIVE, file, line); 320 LOCK_LOG_LOCK("XUNLOCK", &sx->lock_object, 0, sx->sx_recurse, file, 321 line); 322 if (!sx_recursed(sx)) 323 lock_profile_release_lock(&sx->lock_object); 324 __sx_xunlock(sx, curthread, file, line); 325 } 326 327 /* 328 * Try to do a non-blocking upgrade from a shared lock to an exclusive lock. 329 * This will only succeed if this thread holds a single shared lock. 330 * Return 1 if if the upgrade succeed, 0 otherwise. 331 */ 332 int 333 _sx_try_upgrade(struct sx *sx, const char *file, int line) 334 { 335 uintptr_t x; 336 int success; 337 338 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 339 ("sx_try_upgrade() of destroyed sx @ %s:%d", file, line)); 340 _sx_assert(sx, SA_SLOCKED, file, line); 341 342 /* 343 * Try to switch from one shared lock to an exclusive lock. We need 344 * to maintain the SX_LOCK_EXCLUSIVE_WAITERS flag if set so that 345 * we will wake up the exclusive waiters when we drop the lock. 346 */ 347 x = sx->sx_lock & SX_LOCK_EXCLUSIVE_WAITERS; 348 success = atomic_cmpset_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1) | x, 349 (uintptr_t)curthread | x); 350 LOCK_LOG_TRY("XUPGRADE", &sx->lock_object, 0, success, file, line); 351 if (success) 352 WITNESS_UPGRADE(&sx->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 353 file, line); 354 return (success); 355 } 356 357 /* 358 * Downgrade an unrecursed exclusive lock into a single shared lock. 359 */ 360 void 361 _sx_downgrade(struct sx *sx, const char *file, int line) 362 { 363 uintptr_t x; 364 int wakeup_swapper; 365 366 KASSERT(sx->sx_lock != SX_LOCK_DESTROYED, 367 ("sx_downgrade() of destroyed sx @ %s:%d", file, line)); 368 _sx_assert(sx, SA_XLOCKED | SA_NOTRECURSED, file, line); 369 #ifndef INVARIANTS 370 if (sx_recursed(sx)) 371 panic("downgrade of a recursed lock"); 372 #endif 373 374 WITNESS_DOWNGRADE(&sx->lock_object, 0, file, line); 375 376 /* 377 * Try to switch from an exclusive lock with no shared waiters 378 * to one sharer with no shared waiters. If there are 379 * exclusive waiters, we don't need to lock the sleep queue so 380 * long as we preserve the flag. We do one quick try and if 381 * that fails we grab the sleepq lock to keep the flags from 382 * changing and do it the slow way. 383 * 384 * We have to lock the sleep queue if there are shared waiters 385 * so we can wake them up. 386 */ 387 x = sx->sx_lock; 388 if (!(x & SX_LOCK_SHARED_WAITERS) && 389 atomic_cmpset_rel_ptr(&sx->sx_lock, x, SX_SHARERS_LOCK(1) | 390 (x & SX_LOCK_EXCLUSIVE_WAITERS))) { 391 LOCK_LOG_LOCK("XDOWNGRADE", &sx->lock_object, 0, 0, file, line); 392 return; 393 } 394 395 /* 396 * Lock the sleep queue so we can read the waiters bits 397 * without any races and wakeup any shared waiters. 398 */ 399 sleepq_lock(&sx->lock_object); 400 401 /* 402 * Preserve SX_LOCK_EXCLUSIVE_WAITERS while downgraded to a single 403 * shared lock. If there are any shared waiters, wake them up. 404 */ 405 wakeup_swapper = 0; 406 x = sx->sx_lock; 407 atomic_store_rel_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1) | 408 (x & SX_LOCK_EXCLUSIVE_WAITERS)); 409 if (x & SX_LOCK_SHARED_WAITERS) 410 wakeup_swapper = sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, 411 0, SQ_SHARED_QUEUE); 412 sleepq_release(&sx->lock_object); 413 414 LOCK_LOG_LOCK("XDOWNGRADE", &sx->lock_object, 0, 0, file, line); 415 416 if (wakeup_swapper) 417 kick_proc0(); 418 } 419 420 /* 421 * This function represents the so-called 'hard case' for sx_xlock 422 * operation. All 'easy case' failures are redirected to this. Note 423 * that ideally this would be a static function, but it needs to be 424 * accessible from at least sx.h. 425 */ 426 int 427 _sx_xlock_hard(struct sx *sx, uintptr_t tid, int opts, const char *file, 428 int line) 429 { 430 GIANT_DECLARE; 431 #ifdef ADAPTIVE_SX 432 volatile struct thread *owner; 433 #endif 434 uint64_t waittime = 0; 435 uintptr_t x; 436 int contested = 0, error = 0; 437 438 /* If we already hold an exclusive lock, then recurse. */ 439 if (sx_xlocked(sx)) { 440 KASSERT((sx->lock_object.lo_flags & SX_RECURSE) != 0, 441 ("_sx_xlock_hard: recursed on non-recursive sx %s @ %s:%d\n", 442 sx->lock_object.lo_name, file, line)); 443 sx->sx_recurse++; 444 atomic_set_ptr(&sx->sx_lock, SX_LOCK_RECURSED); 445 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 446 CTR2(KTR_LOCK, "%s: %p recursing", __func__, sx); 447 return (0); 448 } 449 450 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 451 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__, 452 sx->lock_object.lo_name, (void *)sx->sx_lock, file, line); 453 454 while (!atomic_cmpset_acq_ptr(&sx->sx_lock, SX_LOCK_UNLOCKED, tid)) { 455 lock_profile_obtain_lock_failed(&sx->lock_object, &contested, 456 &waittime); 457 #ifdef ADAPTIVE_SX 458 /* 459 * If the lock is write locked and the owner is 460 * running on another CPU, spin until the owner stops 461 * running or the state of the lock changes. 462 */ 463 x = sx->sx_lock; 464 if (!(x & SX_LOCK_SHARED) && 465 (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) { 466 x = SX_OWNER(x); 467 owner = (struct thread *)x; 468 if (TD_IS_RUNNING(owner)) { 469 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 470 CTR3(KTR_LOCK, 471 "%s: spinning on %p held by %p", 472 __func__, sx, owner); 473 GIANT_SAVE(); 474 while (SX_OWNER(sx->sx_lock) == x && 475 TD_IS_RUNNING(owner)) 476 cpu_spinwait(); 477 continue; 478 } 479 } 480 #endif 481 482 sleepq_lock(&sx->lock_object); 483 x = sx->sx_lock; 484 485 /* 486 * If the lock was released while spinning on the 487 * sleep queue chain lock, try again. 488 */ 489 if (x == SX_LOCK_UNLOCKED) { 490 sleepq_release(&sx->lock_object); 491 continue; 492 } 493 494 #ifdef ADAPTIVE_SX 495 /* 496 * The current lock owner might have started executing 497 * on another CPU (or the lock could have changed 498 * owners) while we were waiting on the sleep queue 499 * chain lock. If so, drop the sleep queue lock and try 500 * again. 501 */ 502 if (!(x & SX_LOCK_SHARED) && 503 (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) { 504 owner = (struct thread *)SX_OWNER(x); 505 if (TD_IS_RUNNING(owner)) { 506 sleepq_release(&sx->lock_object); 507 continue; 508 } 509 } 510 #endif 511 512 /* 513 * If an exclusive lock was released with both shared 514 * and exclusive waiters and a shared waiter hasn't 515 * woken up and acquired the lock yet, sx_lock will be 516 * set to SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS. 517 * If we see that value, try to acquire it once. Note 518 * that we have to preserve SX_LOCK_EXCLUSIVE_WAITERS 519 * as there are other exclusive waiters still. If we 520 * fail, restart the loop. 521 */ 522 if (x == (SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS)) { 523 if (atomic_cmpset_acq_ptr(&sx->sx_lock, 524 SX_LOCK_UNLOCKED | SX_LOCK_EXCLUSIVE_WAITERS, 525 tid | SX_LOCK_EXCLUSIVE_WAITERS)) { 526 sleepq_release(&sx->lock_object); 527 CTR2(KTR_LOCK, "%s: %p claimed by new writer", 528 __func__, sx); 529 break; 530 } 531 sleepq_release(&sx->lock_object); 532 continue; 533 } 534 535 /* 536 * Try to set the SX_LOCK_EXCLUSIVE_WAITERS. If we fail, 537 * than loop back and retry. 538 */ 539 if (!(x & SX_LOCK_EXCLUSIVE_WAITERS)) { 540 if (!atomic_cmpset_ptr(&sx->sx_lock, x, 541 x | SX_LOCK_EXCLUSIVE_WAITERS)) { 542 sleepq_release(&sx->lock_object); 543 continue; 544 } 545 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 546 CTR2(KTR_LOCK, "%s: %p set excl waiters flag", 547 __func__, sx); 548 } 549 550 /* 551 * Since we have been unable to acquire the exclusive 552 * lock and the exclusive waiters flag is set, we have 553 * to sleep. 554 */ 555 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 556 CTR2(KTR_LOCK, "%s: %p blocking on sleep queue", 557 __func__, sx); 558 559 GIANT_SAVE(); 560 sleepq_add(&sx->lock_object, NULL, sx->lock_object.lo_name, 561 SLEEPQ_SX | ((opts & SX_INTERRUPTIBLE) ? 562 SLEEPQ_INTERRUPTIBLE : 0), SQ_EXCLUSIVE_QUEUE); 563 if (!(opts & SX_INTERRUPTIBLE)) 564 sleepq_wait(&sx->lock_object, 0); 565 else 566 error = sleepq_wait_sig(&sx->lock_object, 0); 567 568 if (error) { 569 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 570 CTR2(KTR_LOCK, 571 "%s: interruptible sleep by %p suspended by signal", 572 __func__, sx); 573 break; 574 } 575 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 576 CTR2(KTR_LOCK, "%s: %p resuming from sleep queue", 577 __func__, sx); 578 } 579 580 GIANT_RESTORE(); 581 if (!error) 582 lock_profile_obtain_lock_success(&sx->lock_object, contested, 583 waittime, file, line); 584 return (error); 585 } 586 587 /* 588 * This function represents the so-called 'hard case' for sx_xunlock 589 * operation. All 'easy case' failures are redirected to this. Note 590 * that ideally this would be a static function, but it needs to be 591 * accessible from at least sx.h. 592 */ 593 void 594 _sx_xunlock_hard(struct sx *sx, uintptr_t tid, const char *file, int line) 595 { 596 uintptr_t x; 597 int queue, wakeup_swapper; 598 599 MPASS(!(sx->sx_lock & SX_LOCK_SHARED)); 600 601 /* If the lock is recursed, then unrecurse one level. */ 602 if (sx_xlocked(sx) && sx_recursed(sx)) { 603 if ((--sx->sx_recurse) == 0) 604 atomic_clear_ptr(&sx->sx_lock, SX_LOCK_RECURSED); 605 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 606 CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, sx); 607 return; 608 } 609 MPASS(sx->sx_lock & (SX_LOCK_SHARED_WAITERS | 610 SX_LOCK_EXCLUSIVE_WAITERS)); 611 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 612 CTR2(KTR_LOCK, "%s: %p contested", __func__, sx); 613 614 sleepq_lock(&sx->lock_object); 615 x = SX_LOCK_UNLOCKED; 616 617 /* 618 * The wake up algorithm here is quite simple and probably not 619 * ideal. It gives precedence to shared waiters if they are 620 * present. For this condition, we have to preserve the 621 * state of the exclusive waiters flag. 622 */ 623 if (sx->sx_lock & SX_LOCK_SHARED_WAITERS) { 624 queue = SQ_SHARED_QUEUE; 625 x |= (sx->sx_lock & SX_LOCK_EXCLUSIVE_WAITERS); 626 } else 627 queue = SQ_EXCLUSIVE_QUEUE; 628 629 /* Wake up all the waiters for the specific queue. */ 630 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 631 CTR3(KTR_LOCK, "%s: %p waking up all threads on %s queue", 632 __func__, sx, queue == SQ_SHARED_QUEUE ? "shared" : 633 "exclusive"); 634 atomic_store_rel_ptr(&sx->sx_lock, x); 635 wakeup_swapper = sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, 0, 636 queue); 637 sleepq_release(&sx->lock_object); 638 if (wakeup_swapper) 639 kick_proc0(); 640 } 641 642 /* 643 * This function represents the so-called 'hard case' for sx_slock 644 * operation. All 'easy case' failures are redirected to this. Note 645 * that ideally this would be a static function, but it needs to be 646 * accessible from at least sx.h. 647 */ 648 int 649 _sx_slock_hard(struct sx *sx, int opts, const char *file, int line) 650 { 651 GIANT_DECLARE; 652 #ifdef ADAPTIVE_SX 653 volatile struct thread *owner; 654 #endif 655 uint64_t waittime = 0; 656 int contested = 0; 657 uintptr_t x; 658 int error = 0; 659 660 /* 661 * As with rwlocks, we don't make any attempt to try to block 662 * shared locks once there is an exclusive waiter. 663 */ 664 for (;;) { 665 x = sx->sx_lock; 666 667 /* 668 * If no other thread has an exclusive lock then try to bump up 669 * the count of sharers. Since we have to preserve the state 670 * of SX_LOCK_EXCLUSIVE_WAITERS, if we fail to acquire the 671 * shared lock loop back and retry. 672 */ 673 if (x & SX_LOCK_SHARED) { 674 MPASS(!(x & SX_LOCK_SHARED_WAITERS)); 675 if (atomic_cmpset_acq_ptr(&sx->sx_lock, x, 676 x + SX_ONE_SHARER)) { 677 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 678 CTR4(KTR_LOCK, 679 "%s: %p succeed %p -> %p", __func__, 680 sx, (void *)x, 681 (void *)(x + SX_ONE_SHARER)); 682 break; 683 } 684 continue; 685 } 686 lock_profile_obtain_lock_failed(&sx->lock_object, &contested, 687 &waittime); 688 689 #ifdef ADAPTIVE_SX 690 /* 691 * If the owner is running on another CPU, spin until 692 * the owner stops running or the state of the lock 693 * changes. 694 */ 695 if (sx->lock_object.lo_flags & SX_ADAPTIVESPIN) { 696 x = SX_OWNER(x); 697 owner = (struct thread *)x; 698 if (TD_IS_RUNNING(owner)) { 699 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 700 CTR3(KTR_LOCK, 701 "%s: spinning on %p held by %p", 702 __func__, sx, owner); 703 GIANT_SAVE(); 704 while (SX_OWNER(sx->sx_lock) == x && 705 TD_IS_RUNNING(owner)) 706 cpu_spinwait(); 707 continue; 708 } 709 } 710 #endif 711 712 /* 713 * Some other thread already has an exclusive lock, so 714 * start the process of blocking. 715 */ 716 sleepq_lock(&sx->lock_object); 717 x = sx->sx_lock; 718 719 /* 720 * The lock could have been released while we spun. 721 * In this case loop back and retry. 722 */ 723 if (x & SX_LOCK_SHARED) { 724 sleepq_release(&sx->lock_object); 725 continue; 726 } 727 728 #ifdef ADAPTIVE_SX 729 /* 730 * If the owner is running on another CPU, spin until 731 * the owner stops running or the state of the lock 732 * changes. 733 */ 734 if (!(x & SX_LOCK_SHARED) && 735 (sx->lock_object.lo_flags & SX_ADAPTIVESPIN)) { 736 owner = (struct thread *)SX_OWNER(x); 737 if (TD_IS_RUNNING(owner)) { 738 sleepq_release(&sx->lock_object); 739 continue; 740 } 741 } 742 #endif 743 744 /* 745 * Try to set the SX_LOCK_SHARED_WAITERS flag. If we 746 * fail to set it drop the sleep queue lock and loop 747 * back. 748 */ 749 if (!(x & SX_LOCK_SHARED_WAITERS)) { 750 if (!atomic_cmpset_ptr(&sx->sx_lock, x, 751 x | SX_LOCK_SHARED_WAITERS)) { 752 sleepq_release(&sx->lock_object); 753 continue; 754 } 755 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 756 CTR2(KTR_LOCK, "%s: %p set shared waiters flag", 757 __func__, sx); 758 } 759 760 /* 761 * Since we have been unable to acquire the shared lock, 762 * we have to sleep. 763 */ 764 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 765 CTR2(KTR_LOCK, "%s: %p blocking on sleep queue", 766 __func__, sx); 767 768 GIANT_SAVE(); 769 sleepq_add(&sx->lock_object, NULL, sx->lock_object.lo_name, 770 SLEEPQ_SX | ((opts & SX_INTERRUPTIBLE) ? 771 SLEEPQ_INTERRUPTIBLE : 0), SQ_SHARED_QUEUE); 772 if (!(opts & SX_INTERRUPTIBLE)) 773 sleepq_wait(&sx->lock_object, 0); 774 else 775 error = sleepq_wait_sig(&sx->lock_object, 0); 776 777 if (error) { 778 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 779 CTR2(KTR_LOCK, 780 "%s: interruptible sleep by %p suspended by signal", 781 __func__, sx); 782 break; 783 } 784 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 785 CTR2(KTR_LOCK, "%s: %p resuming from sleep queue", 786 __func__, sx); 787 } 788 if (error == 0) 789 lock_profile_obtain_lock_success(&sx->lock_object, contested, 790 waittime, file, line); 791 792 GIANT_RESTORE(); 793 return (error); 794 } 795 796 /* 797 * This function represents the so-called 'hard case' for sx_sunlock 798 * operation. All 'easy case' failures are redirected to this. Note 799 * that ideally this would be a static function, but it needs to be 800 * accessible from at least sx.h. 801 */ 802 void 803 _sx_sunlock_hard(struct sx *sx, const char *file, int line) 804 { 805 uintptr_t x; 806 int wakeup_swapper; 807 808 for (;;) { 809 x = sx->sx_lock; 810 811 /* 812 * We should never have sharers while at least one thread 813 * holds a shared lock. 814 */ 815 KASSERT(!(x & SX_LOCK_SHARED_WAITERS), 816 ("%s: waiting sharers", __func__)); 817 818 /* 819 * See if there is more than one shared lock held. If 820 * so, just drop one and return. 821 */ 822 if (SX_SHARERS(x) > 1) { 823 if (atomic_cmpset_ptr(&sx->sx_lock, x, 824 x - SX_ONE_SHARER)) { 825 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 826 CTR4(KTR_LOCK, 827 "%s: %p succeeded %p -> %p", 828 __func__, sx, (void *)x, 829 (void *)(x - SX_ONE_SHARER)); 830 break; 831 } 832 continue; 833 } 834 835 /* 836 * If there aren't any waiters for an exclusive lock, 837 * then try to drop it quickly. 838 */ 839 if (!(x & SX_LOCK_EXCLUSIVE_WAITERS)) { 840 MPASS(x == SX_SHARERS_LOCK(1)); 841 if (atomic_cmpset_ptr(&sx->sx_lock, SX_SHARERS_LOCK(1), 842 SX_LOCK_UNLOCKED)) { 843 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 844 CTR2(KTR_LOCK, "%s: %p last succeeded", 845 __func__, sx); 846 break; 847 } 848 continue; 849 } 850 851 /* 852 * At this point, there should just be one sharer with 853 * exclusive waiters. 854 */ 855 MPASS(x == (SX_SHARERS_LOCK(1) | SX_LOCK_EXCLUSIVE_WAITERS)); 856 857 sleepq_lock(&sx->lock_object); 858 859 /* 860 * Wake up semantic here is quite simple: 861 * Just wake up all the exclusive waiters. 862 * Note that the state of the lock could have changed, 863 * so if it fails loop back and retry. 864 */ 865 if (!atomic_cmpset_ptr(&sx->sx_lock, 866 SX_SHARERS_LOCK(1) | SX_LOCK_EXCLUSIVE_WAITERS, 867 SX_LOCK_UNLOCKED)) { 868 sleepq_release(&sx->lock_object); 869 continue; 870 } 871 if (LOCK_LOG_TEST(&sx->lock_object, 0)) 872 CTR2(KTR_LOCK, "%s: %p waking up all thread on" 873 "exclusive queue", __func__, sx); 874 wakeup_swapper = sleepq_broadcast(&sx->lock_object, SLEEPQ_SX, 875 0, SQ_EXCLUSIVE_QUEUE); 876 sleepq_release(&sx->lock_object); 877 if (wakeup_swapper) 878 kick_proc0(); 879 break; 880 } 881 } 882 883 #ifdef INVARIANT_SUPPORT 884 #ifndef INVARIANTS 885 #undef _sx_assert 886 #endif 887 888 /* 889 * In the non-WITNESS case, sx_assert() can only detect that at least 890 * *some* thread owns an slock, but it cannot guarantee that *this* 891 * thread owns an slock. 892 */ 893 void 894 _sx_assert(struct sx *sx, int what, const char *file, int line) 895 { 896 #ifndef WITNESS 897 int slocked = 0; 898 #endif 899 900 if (panicstr != NULL) 901 return; 902 switch (what) { 903 case SA_SLOCKED: 904 case SA_SLOCKED | SA_NOTRECURSED: 905 case SA_SLOCKED | SA_RECURSED: 906 #ifndef WITNESS 907 slocked = 1; 908 /* FALLTHROUGH */ 909 #endif 910 case SA_LOCKED: 911 case SA_LOCKED | SA_NOTRECURSED: 912 case SA_LOCKED | SA_RECURSED: 913 #ifdef WITNESS 914 witness_assert(&sx->lock_object, what, file, line); 915 #else 916 /* 917 * If some other thread has an exclusive lock or we 918 * have one and are asserting a shared lock, fail. 919 * Also, if no one has a lock at all, fail. 920 */ 921 if (sx->sx_lock == SX_LOCK_UNLOCKED || 922 (!(sx->sx_lock & SX_LOCK_SHARED) && (slocked || 923 sx_xholder(sx) != curthread))) 924 panic("Lock %s not %slocked @ %s:%d\n", 925 sx->lock_object.lo_name, slocked ? "share " : "", 926 file, line); 927 928 if (!(sx->sx_lock & SX_LOCK_SHARED)) { 929 if (sx_recursed(sx)) { 930 if (what & SA_NOTRECURSED) 931 panic("Lock %s recursed @ %s:%d\n", 932 sx->lock_object.lo_name, file, 933 line); 934 } else if (what & SA_RECURSED) 935 panic("Lock %s not recursed @ %s:%d\n", 936 sx->lock_object.lo_name, file, line); 937 } 938 #endif 939 break; 940 case SA_XLOCKED: 941 case SA_XLOCKED | SA_NOTRECURSED: 942 case SA_XLOCKED | SA_RECURSED: 943 if (sx_xholder(sx) != curthread) 944 panic("Lock %s not exclusively locked @ %s:%d\n", 945 sx->lock_object.lo_name, file, line); 946 if (sx_recursed(sx)) { 947 if (what & SA_NOTRECURSED) 948 panic("Lock %s recursed @ %s:%d\n", 949 sx->lock_object.lo_name, file, line); 950 } else if (what & SA_RECURSED) 951 panic("Lock %s not recursed @ %s:%d\n", 952 sx->lock_object.lo_name, file, line); 953 break; 954 case SA_UNLOCKED: 955 #ifdef WITNESS 956 witness_assert(&sx->lock_object, what, file, line); 957 #else 958 /* 959 * If we hold an exclusve lock fail. We can't 960 * reliably check to see if we hold a shared lock or 961 * not. 962 */ 963 if (sx_xholder(sx) == curthread) 964 panic("Lock %s exclusively locked @ %s:%d\n", 965 sx->lock_object.lo_name, file, line); 966 #endif 967 break; 968 default: 969 panic("Unknown sx lock assertion: %d @ %s:%d", what, file, 970 line); 971 } 972 } 973 #endif /* INVARIANT_SUPPORT */ 974 975 #ifdef DDB 976 static void 977 db_show_sx(struct lock_object *lock) 978 { 979 struct thread *td; 980 struct sx *sx; 981 982 sx = (struct sx *)lock; 983 984 db_printf(" state: "); 985 if (sx->sx_lock == SX_LOCK_UNLOCKED) 986 db_printf("UNLOCKED\n"); 987 else if (sx->sx_lock == SX_LOCK_DESTROYED) { 988 db_printf("DESTROYED\n"); 989 return; 990 } else if (sx->sx_lock & SX_LOCK_SHARED) 991 db_printf("SLOCK: %ju\n", (uintmax_t)SX_SHARERS(sx->sx_lock)); 992 else { 993 td = sx_xholder(sx); 994 db_printf("XLOCK: %p (tid %d, pid %d, \"%s\")\n", td, 995 td->td_tid, td->td_proc->p_pid, td->td_name); 996 if (sx_recursed(sx)) 997 db_printf(" recursed: %d\n", sx->sx_recurse); 998 } 999 1000 db_printf(" waiters: "); 1001 switch(sx->sx_lock & 1002 (SX_LOCK_SHARED_WAITERS | SX_LOCK_EXCLUSIVE_WAITERS)) { 1003 case SX_LOCK_SHARED_WAITERS: 1004 db_printf("shared\n"); 1005 break; 1006 case SX_LOCK_EXCLUSIVE_WAITERS: 1007 db_printf("exclusive\n"); 1008 break; 1009 case SX_LOCK_SHARED_WAITERS | SX_LOCK_EXCLUSIVE_WAITERS: 1010 db_printf("exclusive and shared\n"); 1011 break; 1012 default: 1013 db_printf("none\n"); 1014 } 1015 } 1016 1017 /* 1018 * Check to see if a thread that is blocked on a sleep queue is actually 1019 * blocked on an sx lock. If so, output some details and return true. 1020 * If the lock has an exclusive owner, return that in *ownerp. 1021 */ 1022 int 1023 sx_chain(struct thread *td, struct thread **ownerp) 1024 { 1025 struct sx *sx; 1026 1027 /* 1028 * Check to see if this thread is blocked on an sx lock. 1029 * First, we check the lock class. If that is ok, then we 1030 * compare the lock name against the wait message. 1031 */ 1032 sx = td->td_wchan; 1033 if (LOCK_CLASS(&sx->lock_object) != &lock_class_sx || 1034 sx->lock_object.lo_name != td->td_wmesg) 1035 return (0); 1036 1037 /* We think we have an sx lock, so output some details. */ 1038 db_printf("blocked on sx \"%s\" ", td->td_wmesg); 1039 *ownerp = sx_xholder(sx); 1040 if (sx->sx_lock & SX_LOCK_SHARED) 1041 db_printf("SLOCK (count %ju)\n", 1042 (uintmax_t)SX_SHARERS(sx->sx_lock)); 1043 else 1044 db_printf("XLOCK\n"); 1045 return (1); 1046 } 1047 #endif 1048