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