Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_rwlock.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /*- 2 * Copyright (c) 2006 John Baldwin <jhb@FreeBSD.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 /* 28 * Machine independent bits of reader/writer lock implementation. 29 */ 30 31 #include <sys/cdefs.h> 32 __FBSDID("$FreeBSD$"); 33 34 #include "opt_ddb.h" 35 #include "opt_hwpmc_hooks.h" 36 #include "opt_kdtrace.h" 37 #include "opt_no_adaptive_rwlocks.h" 38 39 #include <sys/param.h> 40 #include <sys/kdb.h> 41 #include <sys/ktr.h> 42 #include <sys/kernel.h> 43 #include <sys/lock.h> 44 #include <sys/mutex.h> 45 #include <sys/proc.h> 46 #include <sys/rwlock.h> 47 #include <sys/sysctl.h> 48 #include <sys/systm.h> 49 #include <sys/turnstile.h> 50 51 #include <machine/cpu.h> 52 53 #if defined(SMP) && !defined(NO_ADAPTIVE_RWLOCKS) 54 #define ADAPTIVE_RWLOCKS 55 #endif 56 57 #ifdef HWPMC_HOOKS 58 #include <sys/pmckern.h> 59 PMC_SOFT_DECLARE( , , lock, failed); 60 #endif 61 62 #ifdef ADAPTIVE_RWLOCKS 63 #define ROWNER_RETRIES 10 64 #define ROWNER_LOOPS 10000 65 #endif 66 67 #ifdef DDB 68 #include <ddb/ddb.h> 69 70 static void db_show_rwlock(struct lock_object *lock); 71 #endif 72 static void assert_rw(struct lock_object *lock, int what); 73 static void lock_rw(struct lock_object *lock, int how); 74 #ifdef KDTRACE_HOOKS 75 static int owner_rw(struct lock_object *lock, struct thread **owner); 76 #endif 77 static int unlock_rw(struct lock_object *lock); 78 79 struct lock_class lock_class_rw = { 80 .lc_name = "rw", 81 .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE, 82 .lc_assert = assert_rw, 83 #ifdef DDB 84 .lc_ddb_show = db_show_rwlock, 85 #endif 86 .lc_lock = lock_rw, 87 .lc_unlock = unlock_rw, 88 #ifdef KDTRACE_HOOKS 89 .lc_owner = owner_rw, 90 #endif 91 }; 92 93 /* 94 * Return a pointer to the owning thread if the lock is write-locked or 95 * NULL if the lock is unlocked or read-locked. 96 */ 97 #define rw_wowner(rw) \ 98 ((rw)->rw_lock & RW_LOCK_READ ? NULL : \ 99 (struct thread *)RW_OWNER((rw)->rw_lock)) 100 101 /* 102 * Returns if a write owner is recursed. Write ownership is not assured 103 * here and should be previously checked. 104 */ 105 #define rw_recursed(rw) ((rw)->rw_recurse != 0) 106 107 /* 108 * Return true if curthread helds the lock. 109 */ 110 #define rw_wlocked(rw) (rw_wowner((rw)) == curthread) 111 112 /* 113 * Return a pointer to the owning thread for this lock who should receive 114 * any priority lent by threads that block on this lock. Currently this 115 * is identical to rw_wowner(). 116 */ 117 #define rw_owner(rw) rw_wowner(rw) 118 119 #ifndef INVARIANTS 120 #define _rw_assert(rw, what, file, line) 121 #endif 122 123 void 124 assert_rw(struct lock_object *lock, int what) 125 { 126 127 rw_assert((struct rwlock *)lock, what); 128 } 129 130 void 131 lock_rw(struct lock_object *lock, int how) 132 { 133 struct rwlock *rw; 134 135 rw = (struct rwlock *)lock; 136 if (how) 137 rw_wlock(rw); 138 else 139 rw_rlock(rw); 140 } 141 142 int 143 unlock_rw(struct lock_object *lock) 144 { 145 struct rwlock *rw; 146 147 rw = (struct rwlock *)lock; 148 rw_assert(rw, RA_LOCKED | LA_NOTRECURSED); 149 if (rw->rw_lock & RW_LOCK_READ) { 150 rw_runlock(rw); 151 return (0); 152 } else { 153 rw_wunlock(rw); 154 return (1); 155 } 156 } 157 158 #ifdef KDTRACE_HOOKS 159 int 160 owner_rw(struct lock_object *lock, struct thread **owner) 161 { 162 struct rwlock *rw = (struct rwlock *)lock; 163 uintptr_t x = rw->rw_lock; 164 165 *owner = rw_wowner(rw); 166 return ((x & RW_LOCK_READ) != 0 ? (RW_READERS(x) != 0) : 167 (*owner != NULL)); 168 } 169 #endif 170 171 void 172 rw_init_flags(struct rwlock *rw, const char *name, int opts) 173 { 174 int flags; 175 176 MPASS((opts & ~(RW_DUPOK | RW_NOPROFILE | RW_NOWITNESS | RW_QUIET | 177 RW_RECURSE)) == 0); 178 ASSERT_ATOMIC_LOAD_PTR(rw->rw_lock, 179 ("%s: rw_lock not aligned for %s: %p", __func__, name, 180 &rw->rw_lock)); 181 182 flags = LO_UPGRADABLE; 183 if (opts & RW_DUPOK) 184 flags |= LO_DUPOK; 185 if (opts & RW_NOPROFILE) 186 flags |= LO_NOPROFILE; 187 if (!(opts & RW_NOWITNESS)) 188 flags |= LO_WITNESS; 189 if (opts & RW_RECURSE) 190 flags |= LO_RECURSABLE; 191 if (opts & RW_QUIET) 192 flags |= LO_QUIET; 193 194 rw->rw_lock = RW_UNLOCKED; 195 rw->rw_recurse = 0; 196 lock_init(&rw->lock_object, &lock_class_rw, name, NULL, flags); 197 } 198 199 void 200 rw_destroy(struct rwlock *rw) 201 { 202 203 KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock %p not unlocked", rw)); 204 KASSERT(rw->rw_recurse == 0, ("rw lock %p still recursed", rw)); 205 rw->rw_lock = RW_DESTROYED; 206 lock_destroy(&rw->lock_object); 207 } 208 209 void 210 rw_sysinit(void *arg) 211 { 212 struct rw_args *args = arg; 213 214 rw_init(args->ra_rw, args->ra_desc); 215 } 216 217 void 218 rw_sysinit_flags(void *arg) 219 { 220 struct rw_args_flags *args = arg; 221 222 rw_init_flags(args->ra_rw, args->ra_desc, args->ra_flags); 223 } 224 225 int 226 rw_wowned(struct rwlock *rw) 227 { 228 229 return (rw_wowner(rw) == curthread); 230 } 231 232 void 233 _rw_wlock(struct rwlock *rw, const char *file, int line) 234 { 235 236 if (SCHEDULER_STOPPED()) 237 return; 238 KASSERT(kdb_active != 0 || !TD_IS_IDLETHREAD(curthread), 239 ("rw_wlock() by idle thread %p on rwlock %s @ %s:%d", 240 curthread, rw->lock_object.lo_name, file, line)); 241 KASSERT(rw->rw_lock != RW_DESTROYED, 242 ("rw_wlock() of destroyed rwlock @ %s:%d", file, line)); 243 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file, 244 line, NULL); 245 __rw_wlock(rw, curthread, file, line); 246 LOCK_LOG_LOCK("WLOCK", &rw->lock_object, 0, rw->rw_recurse, file, line); 247 WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 248 curthread->td_locks++; 249 } 250 251 int 252 _rw_try_wlock(struct rwlock *rw, const char *file, int line) 253 { 254 int rval; 255 256 if (SCHEDULER_STOPPED()) 257 return (1); 258 259 KASSERT(kdb_active != 0 || !TD_IS_IDLETHREAD(curthread), 260 ("rw_try_wlock() by idle thread %p on rwlock %s @ %s:%d", 261 curthread, rw->lock_object.lo_name, file, line)); 262 KASSERT(rw->rw_lock != RW_DESTROYED, 263 ("rw_try_wlock() of destroyed rwlock @ %s:%d", file, line)); 264 265 if (rw_wlocked(rw) && 266 (rw->lock_object.lo_flags & LO_RECURSABLE) != 0) { 267 rw->rw_recurse++; 268 rval = 1; 269 } else 270 rval = atomic_cmpset_acq_ptr(&rw->rw_lock, RW_UNLOCKED, 271 (uintptr_t)curthread); 272 273 LOCK_LOG_TRY("WLOCK", &rw->lock_object, 0, rval, file, line); 274 if (rval) { 275 WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 276 file, line); 277 if (!rw_recursed(rw)) 278 LOCKSTAT_PROFILE_OBTAIN_LOCK_SUCCESS(LS_RW_WLOCK_ACQUIRE, 279 rw, 0, 0, file, line); 280 curthread->td_locks++; 281 } 282 return (rval); 283 } 284 285 void 286 _rw_wunlock(struct rwlock *rw, const char *file, int line) 287 { 288 289 if (SCHEDULER_STOPPED()) 290 return; 291 KASSERT(rw->rw_lock != RW_DESTROYED, 292 ("rw_wunlock() of destroyed rwlock @ %s:%d", file, line)); 293 _rw_assert(rw, RA_WLOCKED, file, line); 294 curthread->td_locks--; 295 WITNESS_UNLOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 296 LOCK_LOG_LOCK("WUNLOCK", &rw->lock_object, 0, rw->rw_recurse, file, 297 line); 298 if (!rw_recursed(rw)) 299 LOCKSTAT_PROFILE_RELEASE_LOCK(LS_RW_WUNLOCK_RELEASE, rw); 300 __rw_wunlock(rw, curthread, file, line); 301 } 302 /* 303 * Determines whether a new reader can acquire a lock. Succeeds if the 304 * reader already owns a read lock and the lock is locked for read to 305 * prevent deadlock from reader recursion. Also succeeds if the lock 306 * is unlocked and has no writer waiters or spinners. Failing otherwise 307 * prioritizes writers before readers. 308 */ 309 #define RW_CAN_READ(_rw) \ 310 ((curthread->td_rw_rlocks && (_rw) & RW_LOCK_READ) || ((_rw) & \ 311 (RW_LOCK_READ | RW_LOCK_WRITE_WAITERS | RW_LOCK_WRITE_SPINNER)) == \ 312 RW_LOCK_READ) 313 314 void 315 _rw_rlock(struct rwlock *rw, const char *file, int line) 316 { 317 struct turnstile *ts; 318 #ifdef ADAPTIVE_RWLOCKS 319 volatile struct thread *owner; 320 int spintries = 0; 321 int i; 322 #endif 323 #ifdef LOCK_PROFILING 324 uint64_t waittime = 0; 325 int contested = 0; 326 #endif 327 uintptr_t v; 328 #ifdef KDTRACE_HOOKS 329 uintptr_t state; 330 uint64_t spin_cnt = 0; 331 uint64_t sleep_cnt = 0; 332 int64_t sleep_time = 0; 333 int64_t all_time = 0; 334 #endif 335 336 if (SCHEDULER_STOPPED()) 337 return; 338 339 KASSERT(kdb_active != 0 || !TD_IS_IDLETHREAD(curthread), 340 ("rw_rlock() by idle thread %p on rwlock %s @ %s:%d", 341 curthread, rw->lock_object.lo_name, file, line)); 342 KASSERT(rw->rw_lock != RW_DESTROYED, 343 ("rw_rlock() of destroyed rwlock @ %s:%d", file, line)); 344 KASSERT(rw_wowner(rw) != curthread, 345 ("rw_rlock: wlock already held for %s @ %s:%d", 346 rw->lock_object.lo_name, file, line)); 347 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER, file, line, NULL); 348 349 #ifdef KDTRACE_HOOKS 350 all_time -= lockstat_nsecs(&rw->lock_object); 351 state = rw->rw_lock; 352 #endif 353 for (;;) { 354 #ifdef KDTRACE_HOOKS 355 spin_cnt++; 356 #endif 357 /* 358 * Handle the easy case. If no other thread has a write 359 * lock, then try to bump up the count of read locks. Note 360 * that we have to preserve the current state of the 361 * RW_LOCK_WRITE_WAITERS flag. If we fail to acquire a 362 * read lock, then rw_lock must have changed, so restart 363 * the loop. Note that this handles the case of a 364 * completely unlocked rwlock since such a lock is encoded 365 * as a read lock with no waiters. 366 */ 367 v = rw->rw_lock; 368 if (RW_CAN_READ(v)) { 369 /* 370 * The RW_LOCK_READ_WAITERS flag should only be set 371 * if the lock has been unlocked and write waiters 372 * were present. 373 */ 374 if (atomic_cmpset_acq_ptr(&rw->rw_lock, v, 375 v + RW_ONE_READER)) { 376 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 377 CTR4(KTR_LOCK, 378 "%s: %p succeed %p -> %p", __func__, 379 rw, (void *)v, 380 (void *)(v + RW_ONE_READER)); 381 break; 382 } 383 continue; 384 } 385 #ifdef HWPMC_HOOKS 386 PMC_SOFT_CALL( , , lock, failed); 387 #endif 388 lock_profile_obtain_lock_failed(&rw->lock_object, 389 &contested, &waittime); 390 391 #ifdef ADAPTIVE_RWLOCKS 392 /* 393 * If the owner is running on another CPU, spin until 394 * the owner stops running or the state of the lock 395 * changes. 396 */ 397 if ((v & RW_LOCK_READ) == 0) { 398 owner = (struct thread *)RW_OWNER(v); 399 if (TD_IS_RUNNING(owner)) { 400 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 401 CTR3(KTR_LOCK, 402 "%s: spinning on %p held by %p", 403 __func__, rw, owner); 404 while ((struct thread*)RW_OWNER(rw->rw_lock) == 405 owner && TD_IS_RUNNING(owner)) { 406 cpu_spinwait(); 407 #ifdef KDTRACE_HOOKS 408 spin_cnt++; 409 #endif 410 } 411 continue; 412 } 413 } else if (spintries < ROWNER_RETRIES) { 414 spintries++; 415 for (i = 0; i < ROWNER_LOOPS; i++) { 416 v = rw->rw_lock; 417 if ((v & RW_LOCK_READ) == 0 || RW_CAN_READ(v)) 418 break; 419 cpu_spinwait(); 420 } 421 if (i != ROWNER_LOOPS) 422 continue; 423 } 424 #endif 425 426 /* 427 * Okay, now it's the hard case. Some other thread already 428 * has a write lock or there are write waiters present, 429 * acquire the turnstile lock so we can begin the process 430 * of blocking. 431 */ 432 ts = turnstile_trywait(&rw->lock_object); 433 434 /* 435 * The lock might have been released while we spun, so 436 * recheck its state and restart the loop if needed. 437 */ 438 v = rw->rw_lock; 439 if (RW_CAN_READ(v)) { 440 turnstile_cancel(ts); 441 continue; 442 } 443 444 #ifdef ADAPTIVE_RWLOCKS 445 /* 446 * The current lock owner might have started executing 447 * on another CPU (or the lock could have changed 448 * owners) while we were waiting on the turnstile 449 * chain lock. If so, drop the turnstile lock and try 450 * again. 451 */ 452 if ((v & RW_LOCK_READ) == 0) { 453 owner = (struct thread *)RW_OWNER(v); 454 if (TD_IS_RUNNING(owner)) { 455 turnstile_cancel(ts); 456 continue; 457 } 458 } 459 #endif 460 461 /* 462 * The lock is held in write mode or it already has waiters. 463 */ 464 MPASS(!RW_CAN_READ(v)); 465 466 /* 467 * If the RW_LOCK_READ_WAITERS flag is already set, then 468 * we can go ahead and block. If it is not set then try 469 * to set it. If we fail to set it drop the turnstile 470 * lock and restart the loop. 471 */ 472 if (!(v & RW_LOCK_READ_WAITERS)) { 473 if (!atomic_cmpset_ptr(&rw->rw_lock, v, 474 v | RW_LOCK_READ_WAITERS)) { 475 turnstile_cancel(ts); 476 continue; 477 } 478 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 479 CTR2(KTR_LOCK, "%s: %p set read waiters flag", 480 __func__, rw); 481 } 482 483 /* 484 * We were unable to acquire the lock and the read waiters 485 * flag is set, so we must block on the turnstile. 486 */ 487 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 488 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 489 rw); 490 #ifdef KDTRACE_HOOKS 491 sleep_time -= lockstat_nsecs(&rw->lock_object); 492 #endif 493 turnstile_wait(ts, rw_owner(rw), TS_SHARED_QUEUE); 494 #ifdef KDTRACE_HOOKS 495 sleep_time += lockstat_nsecs(&rw->lock_object); 496 sleep_cnt++; 497 #endif 498 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 499 CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 500 __func__, rw); 501 } 502 #ifdef KDTRACE_HOOKS 503 all_time += lockstat_nsecs(&rw->lock_object); 504 if (sleep_time) 505 LOCKSTAT_RECORD4(LS_RW_RLOCK_BLOCK, rw, sleep_time, 506 LOCKSTAT_READER, (state & RW_LOCK_READ) == 0, 507 (state & RW_LOCK_READ) == 0 ? 0 : RW_READERS(state)); 508 509 /* Record only the loops spinning and not sleeping. */ 510 if (spin_cnt > sleep_cnt) 511 LOCKSTAT_RECORD4(LS_RW_RLOCK_SPIN, rw, all_time - sleep_time, 512 LOCKSTAT_READER, (state & RW_LOCK_READ) == 0, 513 (state & RW_LOCK_READ) == 0 ? 0 : RW_READERS(state)); 514 #endif 515 /* 516 * TODO: acquire "owner of record" here. Here be turnstile dragons 517 * however. turnstiles don't like owners changing between calls to 518 * turnstile_wait() currently. 519 */ 520 LOCKSTAT_PROFILE_OBTAIN_LOCK_SUCCESS(LS_RW_RLOCK_ACQUIRE, rw, contested, 521 waittime, file, line); 522 LOCK_LOG_LOCK("RLOCK", &rw->lock_object, 0, 0, file, line); 523 WITNESS_LOCK(&rw->lock_object, 0, file, line); 524 curthread->td_locks++; 525 curthread->td_rw_rlocks++; 526 } 527 528 int 529 _rw_try_rlock(struct rwlock *rw, const char *file, int line) 530 { 531 uintptr_t x; 532 533 if (SCHEDULER_STOPPED()) 534 return (1); 535 536 KASSERT(kdb_active != 0 || !TD_IS_IDLETHREAD(curthread), 537 ("rw_try_rlock() by idle thread %p on rwlock %s @ %s:%d", 538 curthread, rw->lock_object.lo_name, file, line)); 539 540 for (;;) { 541 x = rw->rw_lock; 542 KASSERT(rw->rw_lock != RW_DESTROYED, 543 ("rw_try_rlock() of destroyed rwlock @ %s:%d", file, line)); 544 if (!(x & RW_LOCK_READ)) 545 break; 546 if (atomic_cmpset_acq_ptr(&rw->rw_lock, x, x + RW_ONE_READER)) { 547 LOCK_LOG_TRY("RLOCK", &rw->lock_object, 0, 1, file, 548 line); 549 WITNESS_LOCK(&rw->lock_object, LOP_TRYLOCK, file, line); 550 LOCKSTAT_PROFILE_OBTAIN_LOCK_SUCCESS(LS_RW_RLOCK_ACQUIRE, 551 rw, 0, 0, file, line); 552 curthread->td_locks++; 553 curthread->td_rw_rlocks++; 554 return (1); 555 } 556 } 557 558 LOCK_LOG_TRY("RLOCK", &rw->lock_object, 0, 0, file, line); 559 return (0); 560 } 561 562 void 563 _rw_runlock(struct rwlock *rw, const char *file, int line) 564 { 565 struct turnstile *ts; 566 uintptr_t x, v, queue; 567 568 if (SCHEDULER_STOPPED()) 569 return; 570 571 KASSERT(rw->rw_lock != RW_DESTROYED, 572 ("rw_runlock() of destroyed rwlock @ %s:%d", file, line)); 573 _rw_assert(rw, RA_RLOCKED, file, line); 574 curthread->td_locks--; 575 curthread->td_rw_rlocks--; 576 WITNESS_UNLOCK(&rw->lock_object, 0, file, line); 577 LOCK_LOG_LOCK("RUNLOCK", &rw->lock_object, 0, 0, file, line); 578 579 /* TODO: drop "owner of record" here. */ 580 581 for (;;) { 582 /* 583 * See if there is more than one read lock held. If so, 584 * just drop one and return. 585 */ 586 x = rw->rw_lock; 587 if (RW_READERS(x) > 1) { 588 if (atomic_cmpset_rel_ptr(&rw->rw_lock, x, 589 x - RW_ONE_READER)) { 590 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 591 CTR4(KTR_LOCK, 592 "%s: %p succeeded %p -> %p", 593 __func__, rw, (void *)x, 594 (void *)(x - RW_ONE_READER)); 595 break; 596 } 597 continue; 598 } 599 /* 600 * If there aren't any waiters for a write lock, then try 601 * to drop it quickly. 602 */ 603 if (!(x & RW_LOCK_WAITERS)) { 604 MPASS((x & ~RW_LOCK_WRITE_SPINNER) == 605 RW_READERS_LOCK(1)); 606 if (atomic_cmpset_rel_ptr(&rw->rw_lock, x, 607 RW_UNLOCKED)) { 608 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 609 CTR2(KTR_LOCK, "%s: %p last succeeded", 610 __func__, rw); 611 break; 612 } 613 continue; 614 } 615 /* 616 * Ok, we know we have waiters and we think we are the 617 * last reader, so grab the turnstile lock. 618 */ 619 turnstile_chain_lock(&rw->lock_object); 620 v = rw->rw_lock & (RW_LOCK_WAITERS | RW_LOCK_WRITE_SPINNER); 621 MPASS(v & RW_LOCK_WAITERS); 622 623 /* 624 * Try to drop our lock leaving the lock in a unlocked 625 * state. 626 * 627 * If you wanted to do explicit lock handoff you'd have to 628 * do it here. You'd also want to use turnstile_signal() 629 * and you'd have to handle the race where a higher 630 * priority thread blocks on the write lock before the 631 * thread you wakeup actually runs and have the new thread 632 * "steal" the lock. For now it's a lot simpler to just 633 * wakeup all of the waiters. 634 * 635 * As above, if we fail, then another thread might have 636 * acquired a read lock, so drop the turnstile lock and 637 * restart. 638 */ 639 x = RW_UNLOCKED; 640 if (v & RW_LOCK_WRITE_WAITERS) { 641 queue = TS_EXCLUSIVE_QUEUE; 642 x |= (v & RW_LOCK_READ_WAITERS); 643 } else 644 queue = TS_SHARED_QUEUE; 645 if (!atomic_cmpset_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v, 646 x)) { 647 turnstile_chain_unlock(&rw->lock_object); 648 continue; 649 } 650 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 651 CTR2(KTR_LOCK, "%s: %p last succeeded with waiters", 652 __func__, rw); 653 654 /* 655 * Ok. The lock is released and all that's left is to 656 * wake up the waiters. Note that the lock might not be 657 * free anymore, but in that case the writers will just 658 * block again if they run before the new lock holder(s) 659 * release the lock. 660 */ 661 ts = turnstile_lookup(&rw->lock_object); 662 MPASS(ts != NULL); 663 turnstile_broadcast(ts, queue); 664 turnstile_unpend(ts, TS_SHARED_LOCK); 665 turnstile_chain_unlock(&rw->lock_object); 666 break; 667 } 668 LOCKSTAT_PROFILE_RELEASE_LOCK(LS_RW_RUNLOCK_RELEASE, rw); 669 } 670 671 /* 672 * This function is called when we are unable to obtain a write lock on the 673 * first try. This means that at least one other thread holds either a 674 * read or write lock. 675 */ 676 void 677 _rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 678 { 679 struct turnstile *ts; 680 #ifdef ADAPTIVE_RWLOCKS 681 volatile struct thread *owner; 682 int spintries = 0; 683 int i; 684 #endif 685 uintptr_t v, x; 686 #ifdef LOCK_PROFILING 687 uint64_t waittime = 0; 688 int contested = 0; 689 #endif 690 #ifdef KDTRACE_HOOKS 691 uintptr_t state; 692 uint64_t spin_cnt = 0; 693 uint64_t sleep_cnt = 0; 694 int64_t sleep_time = 0; 695 int64_t all_time = 0; 696 #endif 697 698 if (SCHEDULER_STOPPED()) 699 return; 700 701 if (rw_wlocked(rw)) { 702 KASSERT(rw->lock_object.lo_flags & LO_RECURSABLE, 703 ("%s: recursing but non-recursive rw %s @ %s:%d\n", 704 __func__, rw->lock_object.lo_name, file, line)); 705 rw->rw_recurse++; 706 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 707 CTR2(KTR_LOCK, "%s: %p recursing", __func__, rw); 708 return; 709 } 710 711 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 712 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__, 713 rw->lock_object.lo_name, (void *)rw->rw_lock, file, line); 714 715 #ifdef KDTRACE_HOOKS 716 all_time -= lockstat_nsecs(&rw->lock_object); 717 state = rw->rw_lock; 718 #endif 719 while (!_rw_write_lock(rw, tid)) { 720 #ifdef KDTRACE_HOOKS 721 spin_cnt++; 722 #endif 723 #ifdef HWPMC_HOOKS 724 PMC_SOFT_CALL( , , lock, failed); 725 #endif 726 lock_profile_obtain_lock_failed(&rw->lock_object, 727 &contested, &waittime); 728 #ifdef ADAPTIVE_RWLOCKS 729 /* 730 * If the lock is write locked and the owner is 731 * running on another CPU, spin until the owner stops 732 * running or the state of the lock changes. 733 */ 734 v = rw->rw_lock; 735 owner = (struct thread *)RW_OWNER(v); 736 if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) { 737 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 738 CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 739 __func__, rw, owner); 740 while ((struct thread*)RW_OWNER(rw->rw_lock) == owner && 741 TD_IS_RUNNING(owner)) { 742 cpu_spinwait(); 743 #ifdef KDTRACE_HOOKS 744 spin_cnt++; 745 #endif 746 } 747 continue; 748 } 749 if ((v & RW_LOCK_READ) && RW_READERS(v) && 750 spintries < ROWNER_RETRIES) { 751 if (!(v & RW_LOCK_WRITE_SPINNER)) { 752 if (!atomic_cmpset_ptr(&rw->rw_lock, v, 753 v | RW_LOCK_WRITE_SPINNER)) { 754 continue; 755 } 756 } 757 spintries++; 758 for (i = 0; i < ROWNER_LOOPS; i++) { 759 if ((rw->rw_lock & RW_LOCK_WRITE_SPINNER) == 0) 760 break; 761 cpu_spinwait(); 762 } 763 #ifdef KDTRACE_HOOKS 764 spin_cnt += ROWNER_LOOPS - i; 765 #endif 766 if (i != ROWNER_LOOPS) 767 continue; 768 } 769 #endif 770 ts = turnstile_trywait(&rw->lock_object); 771 v = rw->rw_lock; 772 773 #ifdef ADAPTIVE_RWLOCKS 774 /* 775 * The current lock owner might have started executing 776 * on another CPU (or the lock could have changed 777 * owners) while we were waiting on the turnstile 778 * chain lock. If so, drop the turnstile lock and try 779 * again. 780 */ 781 if (!(v & RW_LOCK_READ)) { 782 owner = (struct thread *)RW_OWNER(v); 783 if (TD_IS_RUNNING(owner)) { 784 turnstile_cancel(ts); 785 continue; 786 } 787 } 788 #endif 789 /* 790 * Check for the waiters flags about this rwlock. 791 * If the lock was released, without maintain any pending 792 * waiters queue, simply try to acquire it. 793 * If a pending waiters queue is present, claim the lock 794 * ownership and maintain the pending queue. 795 */ 796 x = v & (RW_LOCK_WAITERS | RW_LOCK_WRITE_SPINNER); 797 if ((v & ~x) == RW_UNLOCKED) { 798 x &= ~RW_LOCK_WRITE_SPINNER; 799 if (atomic_cmpset_acq_ptr(&rw->rw_lock, v, tid | x)) { 800 if (x) 801 turnstile_claim(ts); 802 else 803 turnstile_cancel(ts); 804 break; 805 } 806 turnstile_cancel(ts); 807 continue; 808 } 809 /* 810 * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to 811 * set it. If we fail to set it, then loop back and try 812 * again. 813 */ 814 if (!(v & RW_LOCK_WRITE_WAITERS)) { 815 if (!atomic_cmpset_ptr(&rw->rw_lock, v, 816 v | RW_LOCK_WRITE_WAITERS)) { 817 turnstile_cancel(ts); 818 continue; 819 } 820 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 821 CTR2(KTR_LOCK, "%s: %p set write waiters flag", 822 __func__, rw); 823 } 824 /* 825 * We were unable to acquire the lock and the write waiters 826 * flag is set, so we must block on the turnstile. 827 */ 828 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 829 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 830 rw); 831 #ifdef KDTRACE_HOOKS 832 sleep_time -= lockstat_nsecs(&rw->lock_object); 833 #endif 834 turnstile_wait(ts, rw_owner(rw), TS_EXCLUSIVE_QUEUE); 835 #ifdef KDTRACE_HOOKS 836 sleep_time += lockstat_nsecs(&rw->lock_object); 837 sleep_cnt++; 838 #endif 839 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 840 CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 841 __func__, rw); 842 #ifdef ADAPTIVE_RWLOCKS 843 spintries = 0; 844 #endif 845 } 846 #ifdef KDTRACE_HOOKS 847 all_time += lockstat_nsecs(&rw->lock_object); 848 if (sleep_time) 849 LOCKSTAT_RECORD4(LS_RW_WLOCK_BLOCK, rw, sleep_time, 850 LOCKSTAT_WRITER, (state & RW_LOCK_READ) == 0, 851 (state & RW_LOCK_READ) == 0 ? 0 : RW_READERS(state)); 852 853 /* Record only the loops spinning and not sleeping. */ 854 if (spin_cnt > sleep_cnt) 855 LOCKSTAT_RECORD4(LS_RW_WLOCK_SPIN, rw, all_time - sleep_time, 856 LOCKSTAT_READER, (state & RW_LOCK_READ) == 0, 857 (state & RW_LOCK_READ) == 0 ? 0 : RW_READERS(state)); 858 #endif 859 LOCKSTAT_PROFILE_OBTAIN_LOCK_SUCCESS(LS_RW_WLOCK_ACQUIRE, rw, contested, 860 waittime, file, line); 861 } 862 863 /* 864 * This function is called if the first try at releasing a write lock failed. 865 * This means that one of the 2 waiter bits must be set indicating that at 866 * least one thread is waiting on this lock. 867 */ 868 void 869 _rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 870 { 871 struct turnstile *ts; 872 uintptr_t v; 873 int queue; 874 875 if (SCHEDULER_STOPPED()) 876 return; 877 878 if (rw_wlocked(rw) && rw_recursed(rw)) { 879 rw->rw_recurse--; 880 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 881 CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, rw); 882 return; 883 } 884 885 KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS), 886 ("%s: neither of the waiter flags are set", __func__)); 887 888 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 889 CTR2(KTR_LOCK, "%s: %p contested", __func__, rw); 890 891 turnstile_chain_lock(&rw->lock_object); 892 ts = turnstile_lookup(&rw->lock_object); 893 MPASS(ts != NULL); 894 895 /* 896 * Use the same algo as sx locks for now. Prefer waking up shared 897 * waiters if we have any over writers. This is probably not ideal. 898 * 899 * 'v' is the value we are going to write back to rw_lock. If we 900 * have waiters on both queues, we need to preserve the state of 901 * the waiter flag for the queue we don't wake up. For now this is 902 * hardcoded for the algorithm mentioned above. 903 * 904 * In the case of both readers and writers waiting we wakeup the 905 * readers but leave the RW_LOCK_WRITE_WAITERS flag set. If a 906 * new writer comes in before a reader it will claim the lock up 907 * above. There is probably a potential priority inversion in 908 * there that could be worked around either by waking both queues 909 * of waiters or doing some complicated lock handoff gymnastics. 910 */ 911 v = RW_UNLOCKED; 912 if (rw->rw_lock & RW_LOCK_WRITE_WAITERS) { 913 queue = TS_EXCLUSIVE_QUEUE; 914 v |= (rw->rw_lock & RW_LOCK_READ_WAITERS); 915 } else 916 queue = TS_SHARED_QUEUE; 917 918 /* Wake up all waiters for the specific queue. */ 919 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 920 CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw, 921 queue == TS_SHARED_QUEUE ? "read" : "write"); 922 turnstile_broadcast(ts, queue); 923 atomic_store_rel_ptr(&rw->rw_lock, v); 924 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 925 turnstile_chain_unlock(&rw->lock_object); 926 } 927 928 /* 929 * Attempt to do a non-blocking upgrade from a read lock to a write 930 * lock. This will only succeed if this thread holds a single read 931 * lock. Returns true if the upgrade succeeded and false otherwise. 932 */ 933 int 934 _rw_try_upgrade(struct rwlock *rw, const char *file, int line) 935 { 936 uintptr_t v, x, tid; 937 struct turnstile *ts; 938 int success; 939 940 if (SCHEDULER_STOPPED()) 941 return (1); 942 943 KASSERT(rw->rw_lock != RW_DESTROYED, 944 ("rw_try_upgrade() of destroyed rwlock @ %s:%d", file, line)); 945 _rw_assert(rw, RA_RLOCKED, file, line); 946 947 /* 948 * Attempt to switch from one reader to a writer. If there 949 * are any write waiters, then we will have to lock the 950 * turnstile first to prevent races with another writer 951 * calling turnstile_wait() before we have claimed this 952 * turnstile. So, do the simple case of no waiters first. 953 */ 954 tid = (uintptr_t)curthread; 955 success = 0; 956 for (;;) { 957 v = rw->rw_lock; 958 if (RW_READERS(v) > 1) 959 break; 960 if (!(v & RW_LOCK_WAITERS)) { 961 success = atomic_cmpset_ptr(&rw->rw_lock, v, tid); 962 if (!success) 963 continue; 964 break; 965 } 966 967 /* 968 * Ok, we think we have waiters, so lock the turnstile. 969 */ 970 ts = turnstile_trywait(&rw->lock_object); 971 v = rw->rw_lock; 972 if (RW_READERS(v) > 1) { 973 turnstile_cancel(ts); 974 break; 975 } 976 /* 977 * Try to switch from one reader to a writer again. This time 978 * we honor the current state of the waiters flags. 979 * If we obtain the lock with the flags set, then claim 980 * ownership of the turnstile. 981 */ 982 x = rw->rw_lock & RW_LOCK_WAITERS; 983 success = atomic_cmpset_ptr(&rw->rw_lock, v, tid | x); 984 if (success) { 985 if (x) 986 turnstile_claim(ts); 987 else 988 turnstile_cancel(ts); 989 break; 990 } 991 turnstile_cancel(ts); 992 } 993 LOCK_LOG_TRY("WUPGRADE", &rw->lock_object, 0, success, file, line); 994 if (success) { 995 curthread->td_rw_rlocks--; 996 WITNESS_UPGRADE(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 997 file, line); 998 LOCKSTAT_RECORD0(LS_RW_TRYUPGRADE_UPGRADE, rw); 999 } 1000 return (success); 1001 } 1002 1003 /* 1004 * Downgrade a write lock into a single read lock. 1005 */ 1006 void 1007 _rw_downgrade(struct rwlock *rw, const char *file, int line) 1008 { 1009 struct turnstile *ts; 1010 uintptr_t tid, v; 1011 int rwait, wwait; 1012 1013 if (SCHEDULER_STOPPED()) 1014 return; 1015 1016 KASSERT(rw->rw_lock != RW_DESTROYED, 1017 ("rw_downgrade() of destroyed rwlock @ %s:%d", file, line)); 1018 _rw_assert(rw, RA_WLOCKED | RA_NOTRECURSED, file, line); 1019 #ifndef INVARIANTS 1020 if (rw_recursed(rw)) 1021 panic("downgrade of a recursed lock"); 1022 #endif 1023 1024 WITNESS_DOWNGRADE(&rw->lock_object, 0, file, line); 1025 1026 /* 1027 * Convert from a writer to a single reader. First we handle 1028 * the easy case with no waiters. If there are any waiters, we 1029 * lock the turnstile and "disown" the lock. 1030 */ 1031 tid = (uintptr_t)curthread; 1032 if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1))) 1033 goto out; 1034 1035 /* 1036 * Ok, we think we have waiters, so lock the turnstile so we can 1037 * read the waiter flags without any races. 1038 */ 1039 turnstile_chain_lock(&rw->lock_object); 1040 v = rw->rw_lock & RW_LOCK_WAITERS; 1041 rwait = v & RW_LOCK_READ_WAITERS; 1042 wwait = v & RW_LOCK_WRITE_WAITERS; 1043 MPASS(rwait | wwait); 1044 1045 /* 1046 * Downgrade from a write lock while preserving waiters flag 1047 * and give up ownership of the turnstile. 1048 */ 1049 ts = turnstile_lookup(&rw->lock_object); 1050 MPASS(ts != NULL); 1051 if (!wwait) 1052 v &= ~RW_LOCK_READ_WAITERS; 1053 atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v); 1054 /* 1055 * Wake other readers if there are no writers pending. Otherwise they 1056 * won't be able to acquire the lock anyway. 1057 */ 1058 if (rwait && !wwait) { 1059 turnstile_broadcast(ts, TS_SHARED_QUEUE); 1060 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 1061 } else 1062 turnstile_disown(ts); 1063 turnstile_chain_unlock(&rw->lock_object); 1064 out: 1065 curthread->td_rw_rlocks++; 1066 LOCK_LOG_LOCK("WDOWNGRADE", &rw->lock_object, 0, 0, file, line); 1067 LOCKSTAT_RECORD0(LS_RW_DOWNGRADE_DOWNGRADE, rw); 1068 } 1069 1070 #ifdef INVARIANT_SUPPORT 1071 #ifndef INVARIANTS 1072 #undef _rw_assert 1073 #endif 1074 1075 /* 1076 * In the non-WITNESS case, rw_assert() can only detect that at least 1077 * *some* thread owns an rlock, but it cannot guarantee that *this* 1078 * thread owns an rlock. 1079 */ 1080 void 1081 _rw_assert(struct rwlock *rw, int what, const char *file, int line) 1082 { 1083 1084 if (panicstr != NULL) 1085 return; 1086 switch (what) { 1087 case RA_LOCKED: 1088 case RA_LOCKED | RA_RECURSED: 1089 case RA_LOCKED | RA_NOTRECURSED: 1090 case RA_RLOCKED: 1091 case RA_RLOCKED | RA_RECURSED: 1092 case RA_RLOCKED | RA_NOTRECURSED: 1093 #ifdef WITNESS 1094 witness_assert(&rw->lock_object, what, file, line); 1095 #else 1096 /* 1097 * If some other thread has a write lock or we have one 1098 * and are asserting a read lock, fail. Also, if no one 1099 * has a lock at all, fail. 1100 */ 1101 if (rw->rw_lock == RW_UNLOCKED || 1102 (!(rw->rw_lock & RW_LOCK_READ) && (what & RA_RLOCKED || 1103 rw_wowner(rw) != curthread))) 1104 panic("Lock %s not %slocked @ %s:%d\n", 1105 rw->lock_object.lo_name, (what & RA_RLOCKED) ? 1106 "read " : "", file, line); 1107 1108 if (!(rw->rw_lock & RW_LOCK_READ) && !(what & RA_RLOCKED)) { 1109 if (rw_recursed(rw)) { 1110 if (what & RA_NOTRECURSED) 1111 panic("Lock %s recursed @ %s:%d\n", 1112 rw->lock_object.lo_name, file, 1113 line); 1114 } else if (what & RA_RECURSED) 1115 panic("Lock %s not recursed @ %s:%d\n", 1116 rw->lock_object.lo_name, file, line); 1117 } 1118 #endif 1119 break; 1120 case RA_WLOCKED: 1121 case RA_WLOCKED | RA_RECURSED: 1122 case RA_WLOCKED | RA_NOTRECURSED: 1123 if (rw_wowner(rw) != curthread) 1124 panic("Lock %s not exclusively locked @ %s:%d\n", 1125 rw->lock_object.lo_name, file, line); 1126 if (rw_recursed(rw)) { 1127 if (what & RA_NOTRECURSED) 1128 panic("Lock %s recursed @ %s:%d\n", 1129 rw->lock_object.lo_name, file, line); 1130 } else if (what & RA_RECURSED) 1131 panic("Lock %s not recursed @ %s:%d\n", 1132 rw->lock_object.lo_name, file, line); 1133 break; 1134 case RA_UNLOCKED: 1135 #ifdef WITNESS 1136 witness_assert(&rw->lock_object, what, file, line); 1137 #else 1138 /* 1139 * If we hold a write lock fail. We can't reliably check 1140 * to see if we hold a read lock or not. 1141 */ 1142 if (rw_wowner(rw) == curthread) 1143 panic("Lock %s exclusively locked @ %s:%d\n", 1144 rw->lock_object.lo_name, file, line); 1145 #endif 1146 break; 1147 default: 1148 panic("Unknown rw lock assertion: %d @ %s:%d", what, file, 1149 line); 1150 } 1151 } 1152 #endif /* INVARIANT_SUPPORT */ 1153 1154 #ifdef DDB 1155 void 1156 db_show_rwlock(struct lock_object *lock) 1157 { 1158 struct rwlock *rw; 1159 struct thread *td; 1160 1161 rw = (struct rwlock *)lock; 1162 1163 db_printf(" state: "); 1164 if (rw->rw_lock == RW_UNLOCKED) 1165 db_printf("UNLOCKED\n"); 1166 else if (rw->rw_lock == RW_DESTROYED) { 1167 db_printf("DESTROYED\n"); 1168 return; 1169 } else if (rw->rw_lock & RW_LOCK_READ) 1170 db_printf("RLOCK: %ju locks\n", 1171 (uintmax_t)(RW_READERS(rw->rw_lock))); 1172 else { 1173 td = rw_wowner(rw); 1174 db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td, 1175 td->td_tid, td->td_proc->p_pid, td->td_name); 1176 if (rw_recursed(rw)) 1177 db_printf(" recursed: %u\n", rw->rw_recurse); 1178 } 1179 db_printf(" waiters: "); 1180 switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) { 1181 case RW_LOCK_READ_WAITERS: 1182 db_printf("readers\n"); 1183 break; 1184 case RW_LOCK_WRITE_WAITERS: 1185 db_printf("writers\n"); 1186 break; 1187 case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS: 1188 db_printf("readers and writers\n"); 1189 break; 1190 default: 1191 db_printf("none\n"); 1192 break; 1193 } 1194 } 1195 1196 #endif
Cache object: 30e686dbc5688a40580fc84333468072
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]