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 * 3. Neither the name of the author nor the names of any co-contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER 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 27 * SUCH DAMAGE. 28 */ 29 30 /* 31 * Machine independent bits of reader/writer lock implementation. 32 */ 33 34 #include <sys/cdefs.h> 35 __FBSDID("$FreeBSD$"); 36 37 #include "opt_ddb.h" 38 #include "opt_no_adaptive_rwlocks.h" 39 40 #include <sys/param.h> 41 #include <sys/ktr.h> 42 #include <sys/lock.h> 43 #include <sys/mutex.h> 44 #include <sys/proc.h> 45 #include <sys/rwlock.h> 46 #include <sys/systm.h> 47 #include <sys/turnstile.h> 48 49 #include <machine/cpu.h> 50 51 CTASSERT((RW_RECURSE & LO_CLASSFLAGS) == RW_RECURSE); 52 53 #if defined(SMP) && !defined(NO_ADAPTIVE_RWLOCKS) 54 #define ADAPTIVE_RWLOCKS 55 #endif 56 57 #ifdef DDB 58 #include <ddb/ddb.h> 59 60 static void db_show_rwlock(struct lock_object *lock); 61 #endif 62 static void lock_rw(struct lock_object *lock, int how); 63 static int unlock_rw(struct lock_object *lock); 64 65 struct lock_class lock_class_rw = { 66 .lc_name = "rw", 67 .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE, 68 #ifdef DDB 69 .lc_ddb_show = db_show_rwlock, 70 #endif 71 .lc_lock = lock_rw, 72 .lc_unlock = unlock_rw, 73 }; 74 75 /* 76 * Return a pointer to the owning thread if the lock is write-locked or 77 * NULL if the lock is unlocked or read-locked. 78 */ 79 #define rw_wowner(rw) \ 80 ((rw)->rw_lock & RW_LOCK_READ ? NULL : \ 81 (struct thread *)RW_OWNER((rw)->rw_lock)) 82 83 /* 84 * Returns if a write owner is recursed. Write ownership is not assured 85 * here and should be previously checked. 86 */ 87 #define rw_recursed(rw) ((rw)->rw_recurse != 0) 88 89 /* 90 * Return true if curthread helds the lock. 91 */ 92 #define rw_wlocked(rw) (rw_wowner((rw)) == curthread) 93 94 /* 95 * Return a pointer to the owning thread for this lock who should receive 96 * any priority lent by threads that block on this lock. Currently this 97 * is identical to rw_wowner(). 98 */ 99 #define rw_owner(rw) rw_wowner(rw) 100 101 #ifndef INVARIANTS 102 #define _rw_assert(rw, what, file, line) 103 #endif 104 105 void 106 lock_rw(struct lock_object *lock, int how) 107 { 108 struct rwlock *rw; 109 110 rw = (struct rwlock *)lock; 111 if (how) 112 rw_wlock(rw); 113 else 114 rw_rlock(rw); 115 } 116 117 int 118 unlock_rw(struct lock_object *lock) 119 { 120 struct rwlock *rw; 121 122 rw = (struct rwlock *)lock; 123 rw_assert(rw, RA_LOCKED | LA_NOTRECURSED); 124 if (rw->rw_lock & RW_LOCK_READ) { 125 rw_runlock(rw); 126 return (0); 127 } else { 128 rw_wunlock(rw); 129 return (1); 130 } 131 } 132 133 void 134 rw_init_flags(struct rwlock *rw, const char *name, int opts) 135 { 136 int flags; 137 138 MPASS((opts & ~(RW_DUPOK | RW_NOPROFILE | RW_NOWITNESS | RW_QUIET | 139 RW_RECURSE)) == 0); 140 141 flags = LO_UPGRADABLE | LO_RECURSABLE; 142 if (opts & RW_DUPOK) 143 flags |= LO_DUPOK; 144 if (opts & RW_NOPROFILE) 145 flags |= LO_NOPROFILE; 146 if (!(opts & RW_NOWITNESS)) 147 flags |= LO_WITNESS; 148 if (opts & RW_QUIET) 149 flags |= LO_QUIET; 150 flags |= opts & RW_RECURSE; 151 152 rw->rw_lock = RW_UNLOCKED; 153 rw->rw_recurse = 0; 154 lock_init(&rw->lock_object, &lock_class_rw, name, NULL, flags); 155 } 156 157 void 158 rw_destroy(struct rwlock *rw) 159 { 160 161 KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock not unlocked")); 162 KASSERT(rw->rw_recurse == 0, ("rw lock still recursed")); 163 rw->rw_lock = RW_DESTROYED; 164 lock_destroy(&rw->lock_object); 165 } 166 167 void 168 rw_sysinit(void *arg) 169 { 170 struct rw_args *args = arg; 171 172 rw_init(args->ra_rw, args->ra_desc); 173 } 174 175 int 176 rw_wowned(struct rwlock *rw) 177 { 178 179 return (rw_wowner(rw) == curthread); 180 } 181 182 void 183 _rw_wlock(struct rwlock *rw, const char *file, int line) 184 { 185 186 MPASS(curthread != NULL); 187 KASSERT(rw->rw_lock != RW_DESTROYED, 188 ("rw_wlock() of destroyed rwlock @ %s:%d", file, line)); 189 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file, 190 line); 191 __rw_wlock(rw, curthread, file, line); 192 LOCK_LOG_LOCK("WLOCK", &rw->lock_object, 0, rw->rw_recurse, file, line); 193 WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 194 curthread->td_locks++; 195 } 196 197 int 198 _rw_try_wlock(struct rwlock *rw, const char *file, int line) 199 { 200 int rval; 201 202 KASSERT(rw->rw_lock != RW_DESTROYED, 203 ("rw_try_wlock() of destroyed rwlock @ %s:%d", file, line)); 204 205 if (rw_wlocked(rw) && (rw->lock_object.lo_flags & RW_RECURSE) != 0) { 206 rw->rw_recurse++; 207 rval = 1; 208 } else 209 rval = atomic_cmpset_acq_ptr(&rw->rw_lock, RW_UNLOCKED, 210 (uintptr_t)curthread); 211 212 LOCK_LOG_TRY("WLOCK", &rw->lock_object, 0, rval, file, line); 213 if (rval) { 214 WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 215 file, line); 216 curthread->td_locks++; 217 } 218 return (rval); 219 } 220 221 void 222 _rw_wunlock(struct rwlock *rw, const char *file, int line) 223 { 224 225 MPASS(curthread != NULL); 226 KASSERT(rw->rw_lock != RW_DESTROYED, 227 ("rw_wunlock() of destroyed rwlock @ %s:%d", file, line)); 228 _rw_assert(rw, RA_WLOCKED, file, line); 229 curthread->td_locks--; 230 WITNESS_UNLOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 231 LOCK_LOG_LOCK("WUNLOCK", &rw->lock_object, 0, rw->rw_recurse, file, 232 line); 233 if (!rw_recursed(rw)) 234 lock_profile_release_lock(&rw->lock_object); 235 __rw_wunlock(rw, curthread, file, line); 236 } 237 238 void 239 _rw_rlock(struct rwlock *rw, const char *file, int line) 240 { 241 struct turnstile *ts; 242 #ifdef ADAPTIVE_RWLOCKS 243 volatile struct thread *owner; 244 #endif 245 #ifdef LOCK_PROFILING_SHARED 246 uint64_t waittime = 0; 247 int contested = 0; 248 #endif 249 uintptr_t x; 250 251 KASSERT(rw->rw_lock != RW_DESTROYED, 252 ("rw_rlock() of destroyed rwlock @ %s:%d", file, line)); 253 KASSERT(rw_wowner(rw) != curthread, 254 ("%s (%s): wlock already held @ %s:%d", __func__, 255 rw->lock_object.lo_name, file, line)); 256 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER, file, line); 257 258 /* 259 * Note that we don't make any attempt to try to block read 260 * locks once a writer has blocked on the lock. The reason is 261 * that we currently allow for read locks to recurse and we 262 * don't keep track of all the holders of read locks. Thus, if 263 * we were to block readers once a writer blocked and a reader 264 * tried to recurse on their reader lock after a writer had 265 * blocked we would end up in a deadlock since the reader would 266 * be blocked on the writer, and the writer would be blocked 267 * waiting for the reader to release its original read lock. 268 */ 269 for (;;) { 270 /* 271 * Handle the easy case. If no other thread has a write 272 * lock, then try to bump up the count of read locks. Note 273 * that we have to preserve the current state of the 274 * RW_LOCK_WRITE_WAITERS flag. If we fail to acquire a 275 * read lock, then rw_lock must have changed, so restart 276 * the loop. Note that this handles the case of a 277 * completely unlocked rwlock since such a lock is encoded 278 * as a read lock with no waiters. 279 */ 280 x = rw->rw_lock; 281 if (x & RW_LOCK_READ) { 282 283 /* 284 * The RW_LOCK_READ_WAITERS flag should only be set 285 * if another thread currently holds a write lock, 286 * and in that case RW_LOCK_READ should be clear. 287 */ 288 MPASS((x & RW_LOCK_READ_WAITERS) == 0); 289 if (atomic_cmpset_acq_ptr(&rw->rw_lock, x, 290 x + RW_ONE_READER)) { 291 #ifdef LOCK_PROFILING_SHARED 292 if (RW_READERS(x) == 0) 293 lock_profile_obtain_lock_success( 294 &rw->lock_object, contested, 295 waittime, file, line); 296 #endif 297 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 298 CTR4(KTR_LOCK, 299 "%s: %p succeed %p -> %p", __func__, 300 rw, (void *)x, 301 (void *)(x + RW_ONE_READER)); 302 break; 303 } 304 cpu_spinwait(); 305 continue; 306 } 307 308 #ifdef ADAPTIVE_RWLOCKS 309 /* 310 * If the owner is running on another CPU, spin until 311 * the owner stops running or the state of the lock 312 * changes. 313 */ 314 owner = (struct thread *)RW_OWNER(x); 315 if (TD_IS_RUNNING(owner)) { 316 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 317 CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 318 __func__, rw, owner); 319 #ifdef LOCK_PROFILING_SHARED 320 lock_profile_obtain_lock_failed(&rw->lock_object, 321 &contested, &waittime); 322 #endif 323 while ((struct thread*)RW_OWNER(rw->rw_lock) == owner && 324 TD_IS_RUNNING(owner)) 325 cpu_spinwait(); 326 continue; 327 } 328 #endif 329 330 /* 331 * Okay, now it's the hard case. Some other thread already 332 * has a write lock, so acquire the turnstile lock so we can 333 * begin the process of blocking. 334 */ 335 ts = turnstile_trywait(&rw->lock_object); 336 337 /* 338 * The lock might have been released while we spun, so 339 * recheck its state and restart the loop if there is no 340 * longer a write lock. 341 */ 342 x = rw->rw_lock; 343 if (x & RW_LOCK_READ) { 344 turnstile_cancel(ts); 345 cpu_spinwait(); 346 continue; 347 } 348 349 #ifdef ADAPTIVE_RWLOCKS 350 /* 351 * If the current owner of the lock is executing on another 352 * CPU quit the hard path and try to spin. 353 */ 354 owner = (struct thread *)RW_OWNER(x); 355 if (TD_IS_RUNNING(owner)) { 356 turnstile_cancel(ts); 357 cpu_spinwait(); 358 continue; 359 } 360 #endif 361 362 /* 363 * Ok, it's still a write lock. If the RW_LOCK_READ_WAITERS 364 * flag is already set, then we can go ahead and block. If 365 * it is not set then try to set it. If we fail to set it 366 * drop the turnstile lock and restart the loop. 367 */ 368 if (!(x & RW_LOCK_READ_WAITERS)) { 369 if (!atomic_cmpset_ptr(&rw->rw_lock, x, 370 x | RW_LOCK_READ_WAITERS)) { 371 turnstile_cancel(ts); 372 cpu_spinwait(); 373 continue; 374 } 375 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 376 CTR2(KTR_LOCK, "%s: %p set read waiters flag", 377 __func__, rw); 378 } 379 380 /* 381 * We were unable to acquire the lock and the read waiters 382 * flag is set, so we must block on the turnstile. 383 */ 384 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 385 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 386 rw); 387 #ifdef LOCK_PROFILING_SHARED 388 lock_profile_obtain_lock_failed(&rw->lock_object, &contested, 389 &waittime); 390 #endif 391 turnstile_wait(ts, rw_owner(rw), TS_SHARED_QUEUE); 392 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 393 CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 394 __func__, rw); 395 } 396 397 /* 398 * TODO: acquire "owner of record" here. Here be turnstile dragons 399 * however. turnstiles don't like owners changing between calls to 400 * turnstile_wait() currently. 401 */ 402 403 LOCK_LOG_LOCK("RLOCK", &rw->lock_object, 0, 0, file, line); 404 WITNESS_LOCK(&rw->lock_object, 0, file, line); 405 curthread->td_locks++; 406 } 407 408 int 409 _rw_try_rlock(struct rwlock *rw, const char *file, int line) 410 { 411 uintptr_t x; 412 413 for (;;) { 414 x = rw->rw_lock; 415 KASSERT(rw->rw_lock != RW_DESTROYED, 416 ("rw_try_rlock() of destroyed rwlock @ %s:%d", file, line)); 417 if (!(x & RW_LOCK_READ)) 418 break; 419 if (atomic_cmpset_acq_ptr(&rw->rw_lock, x, x + RW_ONE_READER)) { 420 LOCK_LOG_TRY("RLOCK", &rw->lock_object, 0, 1, file, 421 line); 422 WITNESS_LOCK(&rw->lock_object, LOP_TRYLOCK, file, line); 423 curthread->td_locks++; 424 return (1); 425 } 426 } 427 428 LOCK_LOG_TRY("RLOCK", &rw->lock_object, 0, 0, file, line); 429 return (0); 430 } 431 432 void 433 _rw_runlock(struct rwlock *rw, const char *file, int line) 434 { 435 struct turnstile *ts; 436 uintptr_t x; 437 438 KASSERT(rw->rw_lock != RW_DESTROYED, 439 ("rw_runlock() of destroyed rwlock @ %s:%d", file, line)); 440 _rw_assert(rw, RA_RLOCKED, file, line); 441 curthread->td_locks--; 442 WITNESS_UNLOCK(&rw->lock_object, 0, file, line); 443 LOCK_LOG_LOCK("RUNLOCK", &rw->lock_object, 0, 0, file, line); 444 445 /* TODO: drop "owner of record" here. */ 446 447 for (;;) { 448 /* 449 * See if there is more than one read lock held. If so, 450 * just drop one and return. 451 */ 452 x = rw->rw_lock; 453 if (RW_READERS(x) > 1) { 454 if (atomic_cmpset_ptr(&rw->rw_lock, x, 455 x - RW_ONE_READER)) { 456 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 457 CTR4(KTR_LOCK, 458 "%s: %p succeeded %p -> %p", 459 __func__, rw, (void *)x, 460 (void *)(x - RW_ONE_READER)); 461 break; 462 } 463 continue; 464 } 465 466 467 /* 468 * We should never have read waiters while at least one 469 * thread holds a read lock. (See note above) 470 */ 471 KASSERT(!(x & RW_LOCK_READ_WAITERS), 472 ("%s: waiting readers", __func__)); 473 #ifdef LOCK_PROFILING_SHARED 474 lock_profile_release_lock(&rw->lock_object); 475 #endif 476 477 /* 478 * If there aren't any waiters for a write lock, then try 479 * to drop it quickly. 480 */ 481 if (!(x & RW_LOCK_WRITE_WAITERS)) { 482 483 /* 484 * There shouldn't be any flags set and we should 485 * be the only read lock. If we fail to release 486 * the single read lock, then another thread might 487 * have just acquired a read lock, so go back up 488 * to the multiple read locks case. 489 */ 490 MPASS(x == RW_READERS_LOCK(1)); 491 if (atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1), 492 RW_UNLOCKED)) { 493 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 494 CTR2(KTR_LOCK, "%s: %p last succeeded", 495 __func__, rw); 496 break; 497 } 498 continue; 499 } 500 501 /* 502 * There should just be one reader with one or more 503 * writers waiting. 504 */ 505 MPASS(x == (RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS)); 506 507 /* 508 * Ok, we know we have a waiting writer and we think we 509 * are the last reader, so grab the turnstile lock. 510 */ 511 turnstile_chain_lock(&rw->lock_object); 512 513 /* 514 * Try to drop our lock leaving the lock in a unlocked 515 * state. 516 * 517 * If you wanted to do explicit lock handoff you'd have to 518 * do it here. You'd also want to use turnstile_signal() 519 * and you'd have to handle the race where a higher 520 * priority thread blocks on the write lock before the 521 * thread you wakeup actually runs and have the new thread 522 * "steal" the lock. For now it's a lot simpler to just 523 * wakeup all of the waiters. 524 * 525 * As above, if we fail, then another thread might have 526 * acquired a read lock, so drop the turnstile lock and 527 * restart. 528 */ 529 if (!atomic_cmpset_ptr(&rw->rw_lock, 530 RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS, RW_UNLOCKED)) { 531 turnstile_chain_unlock(&rw->lock_object); 532 continue; 533 } 534 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 535 CTR2(KTR_LOCK, "%s: %p last succeeded with waiters", 536 __func__, rw); 537 538 /* 539 * Ok. The lock is released and all that's left is to 540 * wake up the waiters. Note that the lock might not be 541 * free anymore, but in that case the writers will just 542 * block again if they run before the new lock holder(s) 543 * release the lock. 544 */ 545 ts = turnstile_lookup(&rw->lock_object); 546 MPASS(ts != NULL); 547 turnstile_broadcast(ts, TS_EXCLUSIVE_QUEUE); 548 turnstile_unpend(ts, TS_SHARED_LOCK); 549 turnstile_chain_unlock(&rw->lock_object); 550 break; 551 } 552 } 553 554 /* 555 * This function is called when we are unable to obtain a write lock on the 556 * first try. This means that at least one other thread holds either a 557 * read or write lock. 558 */ 559 void 560 _rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 561 { 562 struct turnstile *ts; 563 #ifdef ADAPTIVE_RWLOCKS 564 volatile struct thread *owner; 565 #endif 566 uint64_t waittime = 0; 567 uintptr_t v; 568 int contested = 0; 569 570 if (rw_wlocked(rw)) { 571 KASSERT(rw->lock_object.lo_flags & RW_RECURSE, 572 ("%s: recursing but non-recursive rw %s @ %s:%d\n", 573 __func__, rw->lock_object.lo_name, file, line)); 574 rw->rw_recurse++; 575 atomic_set_ptr(&rw->rw_lock, RW_LOCK_RECURSED); 576 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 577 CTR2(KTR_LOCK, "%s: %p recursing", __func__, rw); 578 return; 579 } 580 581 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 582 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__, 583 rw->lock_object.lo_name, (void *)rw->rw_lock, file, line); 584 585 while (!_rw_write_lock(rw, tid)) { 586 #ifdef ADAPTIVE_RWLOCKS 587 /* 588 * If the lock is write locked and the owner is 589 * running on another CPU, spin until the owner stops 590 * running or the state of the lock changes. 591 */ 592 v = rw->rw_lock; 593 owner = (struct thread *)RW_OWNER(v); 594 if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) { 595 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 596 CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 597 __func__, rw, owner); 598 lock_profile_obtain_lock_failed(&rw->lock_object, 599 &contested, &waittime); 600 while ((struct thread*)RW_OWNER(rw->rw_lock) == owner && 601 TD_IS_RUNNING(owner)) 602 cpu_spinwait(); 603 continue; 604 } 605 #endif 606 607 ts = turnstile_trywait(&rw->lock_object); 608 v = rw->rw_lock; 609 610 /* 611 * If the lock was released while spinning on the 612 * turnstile chain lock, try again. 613 */ 614 if (v == RW_UNLOCKED) { 615 turnstile_cancel(ts); 616 cpu_spinwait(); 617 continue; 618 } 619 620 #ifdef ADAPTIVE_RWLOCKS 621 /* 622 * If the current owner of the lock is executing on another 623 * CPU quit the hard path and try to spin. 624 */ 625 if (!(v & RW_LOCK_READ)) { 626 owner = (struct thread *)RW_OWNER(v); 627 if (TD_IS_RUNNING(owner)) { 628 turnstile_cancel(ts); 629 cpu_spinwait(); 630 continue; 631 } 632 } 633 #endif 634 635 /* 636 * If the lock was released by a writer with both readers 637 * and writers waiting and a reader hasn't woken up and 638 * acquired the lock yet, rw_lock will be set to the 639 * value RW_UNLOCKED | RW_LOCK_WRITE_WAITERS. If we see 640 * that value, try to acquire it once. Note that we have 641 * to preserve the RW_LOCK_WRITE_WAITERS flag as there are 642 * other writers waiting still. If we fail, restart the 643 * loop. 644 */ 645 if (v == (RW_UNLOCKED | RW_LOCK_WRITE_WAITERS)) { 646 if (atomic_cmpset_acq_ptr(&rw->rw_lock, 647 RW_UNLOCKED | RW_LOCK_WRITE_WAITERS, 648 tid | RW_LOCK_WRITE_WAITERS)) { 649 turnstile_claim(ts); 650 CTR2(KTR_LOCK, "%s: %p claimed by new writer", 651 __func__, rw); 652 break; 653 } 654 turnstile_cancel(ts); 655 cpu_spinwait(); 656 continue; 657 } 658 659 /* 660 * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to 661 * set it. If we fail to set it, then loop back and try 662 * again. 663 */ 664 if (!(v & RW_LOCK_WRITE_WAITERS)) { 665 if (!atomic_cmpset_ptr(&rw->rw_lock, v, 666 v | RW_LOCK_WRITE_WAITERS)) { 667 turnstile_cancel(ts); 668 cpu_spinwait(); 669 continue; 670 } 671 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 672 CTR2(KTR_LOCK, "%s: %p set write waiters flag", 673 __func__, rw); 674 } 675 676 /* 677 * We were unable to acquire the lock and the write waiters 678 * flag is set, so we must block on the turnstile. 679 */ 680 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 681 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 682 rw); 683 lock_profile_obtain_lock_failed(&rw->lock_object, &contested, 684 &waittime); 685 turnstile_wait(ts, rw_owner(rw), TS_EXCLUSIVE_QUEUE); 686 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 687 CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 688 __func__, rw); 689 } 690 lock_profile_obtain_lock_success(&rw->lock_object, contested, waittime, 691 file, line); 692 } 693 694 /* 695 * This function is called if the first try at releasing a write lock failed. 696 * This means that one of the 2 waiter bits must be set indicating that at 697 * least one thread is waiting on this lock. 698 */ 699 void 700 _rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 701 { 702 struct turnstile *ts; 703 uintptr_t v; 704 int queue; 705 706 if (rw_wlocked(rw) && rw_recursed(rw)) { 707 if ((--rw->rw_recurse) == 0) 708 atomic_clear_ptr(&rw->rw_lock, RW_LOCK_RECURSED); 709 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 710 CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, rw); 711 return; 712 } 713 714 KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS), 715 ("%s: neither of the waiter flags are set", __func__)); 716 717 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 718 CTR2(KTR_LOCK, "%s: %p contested", __func__, rw); 719 720 turnstile_chain_lock(&rw->lock_object); 721 ts = turnstile_lookup(&rw->lock_object); 722 723 MPASS(ts != NULL); 724 725 /* 726 * Use the same algo as sx locks for now. Prefer waking up shared 727 * waiters if we have any over writers. This is probably not ideal. 728 * 729 * 'v' is the value we are going to write back to rw_lock. If we 730 * have waiters on both queues, we need to preserve the state of 731 * the waiter flag for the queue we don't wake up. For now this is 732 * hardcoded for the algorithm mentioned above. 733 * 734 * In the case of both readers and writers waiting we wakeup the 735 * readers but leave the RW_LOCK_WRITE_WAITERS flag set. If a 736 * new writer comes in before a reader it will claim the lock up 737 * above. There is probably a potential priority inversion in 738 * there that could be worked around either by waking both queues 739 * of waiters or doing some complicated lock handoff gymnastics. 740 */ 741 v = RW_UNLOCKED; 742 if (rw->rw_lock & RW_LOCK_READ_WAITERS) { 743 queue = TS_SHARED_QUEUE; 744 v |= (rw->rw_lock & RW_LOCK_WRITE_WAITERS); 745 } else 746 queue = TS_EXCLUSIVE_QUEUE; 747 748 /* Wake up all waiters for the specific queue. */ 749 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 750 CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw, 751 queue == TS_SHARED_QUEUE ? "read" : "write"); 752 turnstile_broadcast(ts, queue); 753 atomic_store_rel_ptr(&rw->rw_lock, v); 754 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 755 turnstile_chain_unlock(&rw->lock_object); 756 } 757 758 /* 759 * Attempt to do a non-blocking upgrade from a read lock to a write 760 * lock. This will only succeed if this thread holds a single read 761 * lock. Returns true if the upgrade succeeded and false otherwise. 762 */ 763 int 764 _rw_try_upgrade(struct rwlock *rw, const char *file, int line) 765 { 766 uintptr_t v, tid; 767 struct turnstile *ts; 768 int success; 769 770 KASSERT(rw->rw_lock != RW_DESTROYED, 771 ("rw_try_upgrade() of destroyed rwlock @ %s:%d", file, line)); 772 _rw_assert(rw, RA_RLOCKED, file, line); 773 774 /* 775 * Attempt to switch from one reader to a writer. If there 776 * are any write waiters, then we will have to lock the 777 * turnstile first to prevent races with another writer 778 * calling turnstile_wait() before we have claimed this 779 * turnstile. So, do the simple case of no waiters first. 780 */ 781 tid = (uintptr_t)curthread; 782 if (!(rw->rw_lock & RW_LOCK_WRITE_WAITERS)) { 783 success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1), 784 tid); 785 goto out; 786 } 787 788 /* 789 * Ok, we think we have write waiters, so lock the 790 * turnstile. 791 */ 792 ts = turnstile_trywait(&rw->lock_object); 793 794 /* 795 * Try to switch from one reader to a writer again. This time 796 * we honor the current state of the RW_LOCK_WRITE_WAITERS 797 * flag. If we obtain the lock with the flag set, then claim 798 * ownership of the turnstile. 799 */ 800 v = rw->rw_lock & RW_LOCK_WRITE_WAITERS; 801 success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v, 802 tid | v); 803 if (success && v) 804 turnstile_claim(ts); 805 else 806 turnstile_cancel(ts); 807 out: 808 LOCK_LOG_TRY("WUPGRADE", &rw->lock_object, 0, success, file, line); 809 if (success) 810 WITNESS_UPGRADE(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 811 file, line); 812 return (success); 813 } 814 815 /* 816 * Downgrade a write lock into a single read lock. 817 */ 818 void 819 _rw_downgrade(struct rwlock *rw, const char *file, int line) 820 { 821 struct turnstile *ts; 822 uintptr_t tid, v; 823 824 KASSERT(rw->rw_lock != RW_DESTROYED, 825 ("rw_downgrade() of destroyed rwlock @ %s:%d", file, line)); 826 _rw_assert(rw, RA_WLOCKED | RA_NOTRECURSED, file, line); 827 #ifndef INVARIANTS 828 if (rw_recursed(rw)) 829 panic("downgrade of a recursed lock"); 830 #endif 831 832 WITNESS_DOWNGRADE(&rw->lock_object, 0, file, line); 833 834 /* 835 * Convert from a writer to a single reader. First we handle 836 * the easy case with no waiters. If there are any waiters, we 837 * lock the turnstile, "disown" the lock, and awaken any read 838 * waiters. 839 */ 840 tid = (uintptr_t)curthread; 841 if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1))) 842 goto out; 843 844 /* 845 * Ok, we think we have waiters, so lock the turnstile so we can 846 * read the waiter flags without any races. 847 */ 848 turnstile_chain_lock(&rw->lock_object); 849 v = rw->rw_lock; 850 MPASS(v & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)); 851 852 /* 853 * Downgrade from a write lock while preserving 854 * RW_LOCK_WRITE_WAITERS and give up ownership of the 855 * turnstile. If there are any read waiters, wake them up. 856 */ 857 ts = turnstile_lookup(&rw->lock_object); 858 MPASS(ts != NULL); 859 if (v & RW_LOCK_READ_WAITERS) 860 turnstile_broadcast(ts, TS_SHARED_QUEUE); 861 atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | 862 (v & RW_LOCK_WRITE_WAITERS)); 863 if (v & RW_LOCK_READ_WAITERS) 864 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 865 else 866 turnstile_disown(ts); 867 turnstile_chain_unlock(&rw->lock_object); 868 out: 869 LOCK_LOG_LOCK("WDOWNGRADE", &rw->lock_object, 0, 0, file, line); 870 } 871 872 #ifdef INVARIANT_SUPPORT 873 #ifndef INVARIANTS 874 #undef _rw_assert 875 #endif 876 877 /* 878 * In the non-WITNESS case, rw_assert() can only detect that at least 879 * *some* thread owns an rlock, but it cannot guarantee that *this* 880 * thread owns an rlock. 881 */ 882 void 883 _rw_assert(struct rwlock *rw, int what, const char *file, int line) 884 { 885 886 if (panicstr != NULL) 887 return; 888 switch (what) { 889 case RA_LOCKED: 890 case RA_LOCKED | RA_RECURSED: 891 case RA_LOCKED | RA_NOTRECURSED: 892 case RA_RLOCKED: 893 #ifdef WITNESS 894 witness_assert(&rw->lock_object, what, file, line); 895 #else 896 /* 897 * If some other thread has a write lock or we have one 898 * and are asserting a read lock, fail. Also, if no one 899 * has a lock at all, fail. 900 */ 901 if (rw->rw_lock == RW_UNLOCKED || 902 (!(rw->rw_lock & RW_LOCK_READ) && (what == RA_RLOCKED || 903 rw_wowner(rw) != curthread))) 904 panic("Lock %s not %slocked @ %s:%d\n", 905 rw->lock_object.lo_name, (what == RA_RLOCKED) ? 906 "read " : "", file, line); 907 908 if (!(rw->rw_lock & RW_LOCK_READ)) { 909 if (rw_recursed(rw)) { 910 if (what & RA_NOTRECURSED) 911 panic("Lock %s recursed @ %s:%d\n", 912 rw->lock_object.lo_name, file, 913 line); 914 } else if (what & RA_RECURSED) 915 panic("Lock %s not recursed @ %s:%d\n", 916 rw->lock_object.lo_name, file, line); 917 } 918 #endif 919 break; 920 case RA_WLOCKED: 921 case RA_WLOCKED | RA_RECURSED: 922 case RA_WLOCKED | RA_NOTRECURSED: 923 if (rw_wowner(rw) != curthread) 924 panic("Lock %s not exclusively locked @ %s:%d\n", 925 rw->lock_object.lo_name, file, line); 926 if (rw_recursed(rw)) { 927 if (what & RA_NOTRECURSED) 928 panic("Lock %s recursed @ %s:%d\n", 929 rw->lock_object.lo_name, file, line); 930 } else if (what & RA_RECURSED) 931 panic("Lock %s not recursed @ %s:%d\n", 932 rw->lock_object.lo_name, file, line); 933 break; 934 case RA_UNLOCKED: 935 #ifdef WITNESS 936 witness_assert(&rw->lock_object, what, file, line); 937 #else 938 /* 939 * If we hold a write lock fail. We can't reliably check 940 * to see if we hold a read lock or not. 941 */ 942 if (rw_wowner(rw) == curthread) 943 panic("Lock %s exclusively locked @ %s:%d\n", 944 rw->lock_object.lo_name, file, line); 945 #endif 946 break; 947 default: 948 panic("Unknown rw lock assertion: %d @ %s:%d", what, file, 949 line); 950 } 951 } 952 #endif /* INVARIANT_SUPPORT */ 953 954 #ifdef DDB 955 void 956 db_show_rwlock(struct lock_object *lock) 957 { 958 struct rwlock *rw; 959 struct thread *td; 960 961 rw = (struct rwlock *)lock; 962 963 db_printf(" state: "); 964 if (rw->rw_lock == RW_UNLOCKED) 965 db_printf("UNLOCKED\n"); 966 else if (rw->rw_lock == RW_DESTROYED) { 967 db_printf("DESTROYED\n"); 968 return; 969 } else if (rw->rw_lock & RW_LOCK_READ) 970 db_printf("RLOCK: %ju locks\n", 971 (uintmax_t)(RW_READERS(rw->rw_lock))); 972 else { 973 td = rw_wowner(rw); 974 db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td, 975 td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm); 976 if (rw_recursed(rw)) 977 db_printf(" recursed: %u\n", rw->rw_recurse); 978 } 979 db_printf(" waiters: "); 980 switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) { 981 case RW_LOCK_READ_WAITERS: 982 db_printf("readers\n"); 983 break; 984 case RW_LOCK_WRITE_WAITERS: 985 db_printf("writers\n"); 986 break; 987 case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS: 988 db_printf("readers and writers\n"); 989 break; 990 default: 991 db_printf("none\n"); 992 break; 993 } 994 } 995 996 #endif
Cache object: b8093e68ddf45069dfd6a2f4db42c49b
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]