kern_rwlock.c revision 167801
1171169Smlaier/*- 2171169Smlaier * Copyright (c) 2006 John Baldwin <jhb@FreeBSD.org> 3171169Smlaier * All rights reserved. 4171169Smlaier * 5171169Smlaier * Redistribution and use in source and binary forms, with or without 6171169Smlaier * modification, are permitted provided that the following conditions 7171169Smlaier * are met: 8171169Smlaier * 1. Redistributions of source code must retain the above copyright 9171169Smlaier * notice, this list of conditions and the following disclaimer. 10171169Smlaier * 2. Redistributions in binary form must reproduce the above copyright 11171169Smlaier * notice, this list of conditions and the following disclaimer in the 12171169Smlaier * documentation and/or other materials provided with the distribution. 13171169Smlaier * 3. Neither the name of the author nor the names of any co-contributors 14171169Smlaier * may be used to endorse or promote products derived from this software 15171169Smlaier * without specific prior written permission. 16171169Smlaier * 17171169Smlaier * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18171169Smlaier * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19171169Smlaier * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20171169Smlaier * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21171169Smlaier * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22171169Smlaier * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23171169Smlaier * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24171169Smlaier * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25171169Smlaier * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26171169Smlaier * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27171169Smlaier * SUCH DAMAGE. 28171169Smlaier */ 29171169Smlaier 30171169Smlaier/* 31171169Smlaier * Machine independent bits of reader/writer lock implementation. 32171169Smlaier */ 33171169Smlaier 34171169Smlaier#include <sys/cdefs.h> 35171169Smlaier__FBSDID("$FreeBSD: head/sys/kern/kern_rwlock.c 167801 2007-03-22 16:09:23Z jhb $"); 36171169Smlaier 37171169Smlaier#include "opt_ddb.h" 38171169Smlaier#include "opt_no_adaptive_rwlocks.h" 39171169Smlaier 40171169Smlaier#include <sys/param.h> 41171169Smlaier#include <sys/ktr.h> 42171169Smlaier#include <sys/lock.h> 43171169Smlaier#include <sys/mutex.h> 44171169Smlaier#include <sys/proc.h> 45171169Smlaier#include <sys/rwlock.h> 46171169Smlaier#include <sys/systm.h> 47171169Smlaier#include <sys/turnstile.h> 48171169Smlaier#include <sys/lock_profile.h> 49171169Smlaier#include <machine/cpu.h> 50171169Smlaier 51171169Smlaier#if defined(SMP) && !defined(NO_ADAPTIVE_RWLOCKS) 52171169Smlaier#define ADAPTIVE_RWLOCKS 53171169Smlaier#endif 54171169Smlaier 55171169Smlaier#ifdef DDB 56171169Smlaier#include <ddb/ddb.h> 57171169Smlaier 58171169Smlaierstatic void db_show_rwlock(struct lock_object *lock); 59171169Smlaier#endif 60171169Smlaierstatic void lock_rw(struct lock_object *lock, int how); 61171169Smlaierstatic int unlock_rw(struct lock_object *lock); 62171169Smlaier 63171169Smlaierstruct lock_class lock_class_rw = { 64171169Smlaier .lc_name = "rw", 65171169Smlaier .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE, 66171169Smlaier#ifdef DDB 67171169Smlaier .lc_ddb_show = db_show_rwlock, 68171169Smlaier#endif 69171169Smlaier .lc_lock = lock_rw, 70171169Smlaier .lc_unlock = unlock_rw, 71171169Smlaier}; 72171169Smlaier 73171169Smlaier/* 74171169Smlaier * Return a pointer to the owning thread if the lock is write-locked or 75171169Smlaier * NULL if the lock is unlocked or read-locked. 76171169Smlaier */ 77171169Smlaier#define rw_wowner(rw) \ 78171169Smlaier ((rw)->rw_lock & RW_LOCK_READ ? NULL : \ 79171169Smlaier (struct thread *)RW_OWNER((rw)->rw_lock)) 80171169Smlaier 81171169Smlaier/* 82171169Smlaier * Return a pointer to the owning thread for this lock who should receive 83171169Smlaier * any priority lent by threads that block on this lock. Currently this 84171169Smlaier * is identical to rw_wowner(). 85171169Smlaier */ 86171169Smlaier#define rw_owner(rw) rw_wowner(rw) 87171169Smlaier 88171169Smlaier#ifndef INVARIANTS 89171169Smlaier#define _rw_assert(rw, what, file, line) 90171169Smlaier#endif 91171169Smlaier 92171169Smlaiervoid 93171169Smlaierlock_rw(struct lock_object *lock, int how) 94171169Smlaier{ 95171169Smlaier struct rwlock *rw; 96171169Smlaier 97171169Smlaier rw = (struct rwlock *)lock; 98171169Smlaier if (how) 99171169Smlaier rw_wlock(rw); 100171169Smlaier else 101171169Smlaier rw_rlock(rw); 102171169Smlaier} 103171169Smlaier 104171169Smlaierint 105171169Smlaierunlock_rw(struct lock_object *lock) 106171169Smlaier{ 107171169Smlaier struct rwlock *rw; 108171169Smlaier 109171169Smlaier rw = (struct rwlock *)lock; 110171169Smlaier rw_assert(rw, RA_LOCKED | LA_NOTRECURSED); 111171169Smlaier if (rw->rw_lock & RW_LOCK_READ) { 112171169Smlaier rw_runlock(rw); 113171169Smlaier return (0); 114171169Smlaier } else { 115171169Smlaier rw_wunlock(rw); 116171169Smlaier return (1); 117171169Smlaier } 118171169Smlaier} 119171169Smlaier 120171169Smlaiervoid 121171169Smlaierrw_init(struct rwlock *rw, const char *name) 122171169Smlaier{ 123171169Smlaier 124171169Smlaier rw->rw_lock = RW_UNLOCKED; 125171169Smlaier 126171169Smlaier lock_profile_object_init(&rw->lock_object, &lock_class_rw, name); 127171169Smlaier lock_init(&rw->lock_object, &lock_class_rw, name, NULL, LO_WITNESS | 128171169Smlaier LO_RECURSABLE | LO_UPGRADABLE); 129171169Smlaier} 130171169Smlaier 131171169Smlaiervoid 132171169Smlaierrw_destroy(struct rwlock *rw) 133171169Smlaier{ 134171169Smlaier 135171169Smlaier KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock not unlocked")); 136171169Smlaier lock_profile_object_destroy(&rw->lock_object); 137171169Smlaier lock_destroy(&rw->lock_object); 138171169Smlaier} 139171169Smlaier 140171169Smlaiervoid 141171169Smlaierrw_sysinit(void *arg) 142171169Smlaier{ 143171169Smlaier struct rw_args *args = arg; 144171169Smlaier 145171169Smlaier rw_init(args->ra_rw, args->ra_desc); 146171169Smlaier} 147171169Smlaier 148171169Smlaierint 149171169Smlaierrw_wowned(struct rwlock *rw) 150171169Smlaier{ 151171169Smlaier 152171169Smlaier return (rw_wowner(rw) == curthread); 153171169Smlaier} 154171169Smlaier 155171169Smlaiervoid 156171169Smlaier_rw_wlock(struct rwlock *rw, const char *file, int line) 157171169Smlaier{ 158171169Smlaier 159171169Smlaier MPASS(curthread != NULL); 160171169Smlaier KASSERT(rw_wowner(rw) != curthread, 161171169Smlaier ("%s (%s): wlock already held @ %s:%d", __func__, 162171169Smlaier rw->lock_object.lo_name, file, line)); 163171169Smlaier WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file, 164171169Smlaier line); 165171169Smlaier __rw_wlock(rw, curthread, file, line); 166171169Smlaier LOCK_LOG_LOCK("WLOCK", &rw->lock_object, 0, 0, file, line); 167171169Smlaier WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 168171169Smlaier curthread->td_locks++; 169171169Smlaier} 170171169Smlaier 171171169Smlaiervoid 172171169Smlaier_rw_wunlock(struct rwlock *rw, const char *file, int line) 173171169Smlaier{ 174171169Smlaier 175171169Smlaier MPASS(curthread != NULL); 176171169Smlaier _rw_assert(rw, RA_WLOCKED, file, line); 177171169Smlaier curthread->td_locks--; 178171169Smlaier WITNESS_UNLOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line); 179171169Smlaier LOCK_LOG_LOCK("WUNLOCK", &rw->lock_object, 0, 0, file, line); 180171169Smlaier lock_profile_release_lock(&rw->lock_object); 181171169Smlaier __rw_wunlock(rw, curthread, file, line); 182171169Smlaier} 183171169Smlaier 184171169Smlaiervoid 185171169Smlaier_rw_rlock(struct rwlock *rw, const char *file, int line) 186171169Smlaier{ 187171169Smlaier#ifdef ADAPTIVE_RWLOCKS 188171169Smlaier volatile struct thread *owner; 189171169Smlaier#endif 190171169Smlaier uint64_t waittime = 0; 191171169Smlaier int contested = 0; 192171169Smlaier uintptr_t x; 193171169Smlaier 194171169Smlaier KASSERT(rw_wowner(rw) != curthread, 195171169Smlaier ("%s (%s): wlock already held @ %s:%d", __func__, 196171169Smlaier rw->lock_object.lo_name, file, line)); 197171169Smlaier WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER, file, line); 198171169Smlaier 199171169Smlaier /* 200171169Smlaier * Note that we don't make any attempt to try to block read 201171169Smlaier * locks once a writer has blocked on the lock. The reason is 202171169Smlaier * that we currently allow for read locks to recurse and we 203171169Smlaier * don't keep track of all the holders of read locks. Thus, if 204171169Smlaier * we were to block readers once a writer blocked and a reader 205171169Smlaier * tried to recurse on their reader lock after a writer had 206171169Smlaier * blocked we would end up in a deadlock since the reader would 207171169Smlaier * be blocked on the writer, and the writer would be blocked 208171169Smlaier * waiting for the reader to release its original read lock. 209171169Smlaier */ 210171169Smlaier for (;;) { 211171169Smlaier /* 212171169Smlaier * Handle the easy case. If no other thread has a write 213171169Smlaier * lock, then try to bump up the count of read locks. Note 214171169Smlaier * that we have to preserve the current state of the 215171169Smlaier * RW_LOCK_WRITE_WAITERS flag. If we fail to acquire a 216171169Smlaier * read lock, then rw_lock must have changed, so restart 217171169Smlaier * the loop. Note that this handles the case of a 218171169Smlaier * completely unlocked rwlock since such a lock is encoded 219171169Smlaier * as a read lock with no waiters. 220171169Smlaier */ 221171169Smlaier x = rw->rw_lock; 222171169Smlaier if (x & RW_LOCK_READ) { 223171169Smlaier 224171169Smlaier /* 225171169Smlaier * The RW_LOCK_READ_WAITERS flag should only be set 226171169Smlaier * if another thread currently holds a write lock, 227171169Smlaier * and in that case RW_LOCK_READ should be clear. 228171169Smlaier */ 229171169Smlaier MPASS((x & RW_LOCK_READ_WAITERS) == 0); 230171169Smlaier if (atomic_cmpset_acq_ptr(&rw->rw_lock, x, 231171169Smlaier x + RW_ONE_READER)) { 232171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 233171169Smlaier CTR4(KTR_LOCK, 234171169Smlaier "%s: %p succeed %p -> %p", __func__, 235171169Smlaier rw, (void *)x, 236171169Smlaier (void *)(x + RW_ONE_READER)); 237171169Smlaier if (RW_READERS(x) == 0) 238171169Smlaier lock_profile_obtain_lock_success( 239171169Smlaier &rw->lock_object, contested, waittime, 240171169Smlaier file, line); 241171169Smlaier break; 242171169Smlaier } 243171169Smlaier cpu_spinwait(); 244171169Smlaier continue; 245171169Smlaier } 246171169Smlaier lock_profile_obtain_lock_failed(&rw->lock_object, &contested, 247171169Smlaier &waittime); 248171169Smlaier 249171169Smlaier /* 250171169Smlaier * Okay, now it's the hard case. Some other thread already 251171169Smlaier * has a write lock, so acquire the turnstile lock so we can 252171169Smlaier * begin the process of blocking. 253171169Smlaier */ 254171169Smlaier turnstile_lock(&rw->lock_object); 255171169Smlaier 256171169Smlaier /* 257171169Smlaier * The lock might have been released while we spun, so 258171169Smlaier * recheck its state and restart the loop if there is no 259171169Smlaier * longer a write lock. 260171169Smlaier */ 261171169Smlaier x = rw->rw_lock; 262171169Smlaier if (x & RW_LOCK_READ) { 263171169Smlaier turnstile_release(&rw->lock_object); 264171169Smlaier cpu_spinwait(); 265171169Smlaier continue; 266171169Smlaier } 267171169Smlaier 268171169Smlaier /* 269171169Smlaier * Ok, it's still a write lock. If the RW_LOCK_READ_WAITERS 270171169Smlaier * flag is already set, then we can go ahead and block. If 271171169Smlaier * it is not set then try to set it. If we fail to set it 272171169Smlaier * drop the turnstile lock and restart the loop. 273171169Smlaier */ 274171169Smlaier if (!(x & RW_LOCK_READ_WAITERS)) { 275171169Smlaier if (!atomic_cmpset_ptr(&rw->rw_lock, x, 276171169Smlaier x | RW_LOCK_READ_WAITERS)) { 277171169Smlaier turnstile_release(&rw->lock_object); 278171169Smlaier cpu_spinwait(); 279171169Smlaier continue; 280171169Smlaier } 281171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 282171169Smlaier CTR2(KTR_LOCK, "%s: %p set read waiters flag", 283171169Smlaier __func__, rw); 284171169Smlaier } 285171169Smlaier 286171169Smlaier#ifdef ADAPTIVE_RWLOCKS 287171169Smlaier /* 288171169Smlaier * If the owner is running on another CPU, spin until 289171169Smlaier * the owner stops running or the state of the lock 290171169Smlaier * changes. 291171169Smlaier */ 292171169Smlaier owner = (struct thread *)RW_OWNER(x); 293171169Smlaier if (TD_IS_RUNNING(owner)) { 294171169Smlaier turnstile_release(&rw->lock_object); 295171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 296171169Smlaier CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 297171169Smlaier __func__, rw, owner); 298171169Smlaier while ((struct thread*)RW_OWNER(rw->rw_lock)== owner && 299171169Smlaier TD_IS_RUNNING(owner)) 300171169Smlaier cpu_spinwait(); 301171169Smlaier continue; 302171169Smlaier } 303171169Smlaier#endif 304171169Smlaier 305171169Smlaier /* 306171169Smlaier * We were unable to acquire the lock and the read waiters 307171169Smlaier * flag is set, so we must block on the turnstile. 308171169Smlaier */ 309171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 310171169Smlaier CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 311171169Smlaier rw); 312171169Smlaier turnstile_wait(&rw->lock_object, rw_owner(rw), TS_SHARED_QUEUE); 313171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 314171169Smlaier CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 315171169Smlaier __func__, rw); 316171169Smlaier } 317171169Smlaier 318171169Smlaier /* 319171169Smlaier * TODO: acquire "owner of record" here. Here be turnstile dragons 320171169Smlaier * however. turnstiles don't like owners changing between calls to 321171169Smlaier * turnstile_wait() currently. 322171169Smlaier */ 323171169Smlaier 324171169Smlaier LOCK_LOG_LOCK("RLOCK", &rw->lock_object, 0, 0, file, line); 325171169Smlaier WITNESS_LOCK(&rw->lock_object, 0, file, line); 326171169Smlaier curthread->td_locks++; 327171169Smlaier} 328171169Smlaier 329171169Smlaiervoid 330171169Smlaier_rw_runlock(struct rwlock *rw, const char *file, int line) 331171169Smlaier{ 332171169Smlaier struct turnstile *ts; 333171169Smlaier uintptr_t x; 334171169Smlaier 335171169Smlaier _rw_assert(rw, RA_RLOCKED, file, line); 336171169Smlaier curthread->td_locks--; 337171169Smlaier WITNESS_UNLOCK(&rw->lock_object, 0, file, line); 338171169Smlaier LOCK_LOG_LOCK("RUNLOCK", &rw->lock_object, 0, 0, file, line); 339171169Smlaier 340171169Smlaier /* TODO: drop "owner of record" here. */ 341171169Smlaier 342171169Smlaier for (;;) { 343171169Smlaier /* 344171169Smlaier * See if there is more than one read lock held. If so, 345171169Smlaier * just drop one and return. 346171169Smlaier */ 347171169Smlaier x = rw->rw_lock; 348171169Smlaier if (RW_READERS(x) > 1) { 349171169Smlaier if (atomic_cmpset_ptr(&rw->rw_lock, x, 350171169Smlaier x - RW_ONE_READER)) { 351171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 352171169Smlaier CTR4(KTR_LOCK, 353171169Smlaier "%s: %p succeeded %p -> %p", 354171169Smlaier __func__, rw, (void *)x, 355171169Smlaier (void *)(x - RW_ONE_READER)); 356171169Smlaier break; 357171169Smlaier } 358171169Smlaier continue; 359171169Smlaier } 360171169Smlaier 361171169Smlaier 362171169Smlaier /* 363171169Smlaier * We should never have read waiters while at least one 364171169Smlaier * thread holds a read lock. (See note above) 365171169Smlaier */ 366171169Smlaier KASSERT(!(x & RW_LOCK_READ_WAITERS), 367171169Smlaier ("%s: waiting readers", __func__)); 368171169Smlaier 369171169Smlaier /* 370171169Smlaier * If there aren't any waiters for a write lock, then try 371171169Smlaier * to drop it quickly. 372171169Smlaier */ 373171169Smlaier if (!(x & RW_LOCK_WRITE_WAITERS)) { 374171169Smlaier 375171169Smlaier /* 376171169Smlaier * There shouldn't be any flags set and we should 377171169Smlaier * be the only read lock. If we fail to release 378171169Smlaier * the single read lock, then another thread might 379171169Smlaier * have just acquired a read lock, so go back up 380171169Smlaier * to the multiple read locks case. 381171169Smlaier */ 382171169Smlaier MPASS(x == RW_READERS_LOCK(1)); 383171169Smlaier if (atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1), 384171169Smlaier RW_UNLOCKED)) { 385171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 386171169Smlaier CTR2(KTR_LOCK, "%s: %p last succeeded", 387171169Smlaier __func__, rw); 388171169Smlaier break; 389171169Smlaier } 390171169Smlaier continue; 391171169Smlaier } 392171169Smlaier 393171169Smlaier /* 394171169Smlaier * There should just be one reader with one or more 395171169Smlaier * writers waiting. 396171169Smlaier */ 397171169Smlaier MPASS(x == (RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS)); 398171169Smlaier 399171169Smlaier /* 400171169Smlaier * Ok, we know we have a waiting writer and we think we 401171169Smlaier * are the last reader, so grab the turnstile lock. 402171169Smlaier */ 403171169Smlaier turnstile_lock(&rw->lock_object); 404171169Smlaier 405171169Smlaier /* 406171169Smlaier * Try to drop our lock leaving the lock in a unlocked 407171169Smlaier * state. 408171169Smlaier * 409171169Smlaier * If you wanted to do explicit lock handoff you'd have to 410171169Smlaier * do it here. You'd also want to use turnstile_signal() 411171169Smlaier * and you'd have to handle the race where a higher 412171169Smlaier * priority thread blocks on the write lock before the 413171169Smlaier * thread you wakeup actually runs and have the new thread 414171169Smlaier * "steal" the lock. For now it's a lot simpler to just 415171169Smlaier * wakeup all of the waiters. 416171169Smlaier * 417171169Smlaier * As above, if we fail, then another thread might have 418171169Smlaier * acquired a read lock, so drop the turnstile lock and 419171169Smlaier * restart. 420171169Smlaier */ 421171169Smlaier if (!atomic_cmpset_ptr(&rw->rw_lock, 422171169Smlaier RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS, RW_UNLOCKED)) { 423171169Smlaier turnstile_release(&rw->lock_object); 424171169Smlaier continue; 425171169Smlaier } 426171169Smlaier if (LOCK_LOG_TEST(&rw->lock_object, 0)) 427171169Smlaier CTR2(KTR_LOCK, "%s: %p last succeeded with waiters", 428171169Smlaier __func__, rw); 429171169Smlaier 430171169Smlaier /* 431171169Smlaier * Ok. The lock is released and all that's left is to 432171169Smlaier * wake up the waiters. Note that the lock might not be 433171169Smlaier * free anymore, but in that case the writers will just 434171169Smlaier * block again if they run before the new lock holder(s) 435171169Smlaier * release the lock. 436171169Smlaier */ 437171169Smlaier ts = turnstile_lookup(&rw->lock_object); 438171169Smlaier MPASS(ts != NULL); 439171169Smlaier turnstile_broadcast(ts, TS_EXCLUSIVE_QUEUE); 440171169Smlaier turnstile_unpend(ts, TS_SHARED_LOCK); 441171169Smlaier break; 442171169Smlaier } 443171169Smlaier lock_profile_release_lock(&rw->lock_object); 444171169Smlaier} 445171169Smlaier 446171169Smlaier/* 447171169Smlaier * This function is called when we are unable to obtain a write lock on the 448171169Smlaier * first try. This means that at least one other thread holds either a 449171169Smlaier * read or write lock. 450171169Smlaier */ 451171169Smlaiervoid 452171169Smlaier_rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 453171169Smlaier{ 454171169Smlaier#ifdef ADAPTIVE_RWLOCKS 455171169Smlaier volatile struct thread *owner; 456171169Smlaier#endif 457 uintptr_t v; 458 459 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 460 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__, 461 rw->lock_object.lo_name, (void *)rw->rw_lock, file, line); 462 463 while (!_rw_write_lock(rw, tid)) { 464 turnstile_lock(&rw->lock_object); 465 v = rw->rw_lock; 466 467 /* 468 * If the lock was released while spinning on the 469 * turnstile chain lock, try again. 470 */ 471 if (v == RW_UNLOCKED) { 472 turnstile_release(&rw->lock_object); 473 cpu_spinwait(); 474 continue; 475 } 476 477 /* 478 * If the lock was released by a writer with both readers 479 * and writers waiting and a reader hasn't woken up and 480 * acquired the lock yet, rw_lock will be set to the 481 * value RW_UNLOCKED | RW_LOCK_WRITE_WAITERS. If we see 482 * that value, try to acquire it once. Note that we have 483 * to preserve the RW_LOCK_WRITE_WAITERS flag as there are 484 * other writers waiting still. If we fail, restart the 485 * loop. 486 */ 487 if (v == (RW_UNLOCKED | RW_LOCK_WRITE_WAITERS)) { 488 if (atomic_cmpset_acq_ptr(&rw->rw_lock, 489 RW_UNLOCKED | RW_LOCK_WRITE_WAITERS, 490 tid | RW_LOCK_WRITE_WAITERS)) { 491 turnstile_claim(&rw->lock_object); 492 CTR2(KTR_LOCK, "%s: %p claimed by new writer", 493 __func__, rw); 494 break; 495 } 496 turnstile_release(&rw->lock_object); 497 cpu_spinwait(); 498 continue; 499 } 500 501 /* 502 * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to 503 * set it. If we fail to set it, then loop back and try 504 * again. 505 */ 506 if (!(v & RW_LOCK_WRITE_WAITERS)) { 507 if (!atomic_cmpset_ptr(&rw->rw_lock, v, 508 v | RW_LOCK_WRITE_WAITERS)) { 509 turnstile_release(&rw->lock_object); 510 cpu_spinwait(); 511 continue; 512 } 513 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 514 CTR2(KTR_LOCK, "%s: %p set write waiters flag", 515 __func__, rw); 516 } 517 518#ifdef ADAPTIVE_RWLOCKS 519 /* 520 * If the lock is write locked and the owner is 521 * running on another CPU, spin until the owner stops 522 * running or the state of the lock changes. 523 */ 524 owner = (struct thread *)RW_OWNER(v); 525 if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) { 526 turnstile_release(&rw->lock_object); 527 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 528 CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 529 __func__, rw, owner); 530 while ((struct thread*)RW_OWNER(rw->rw_lock)== owner && 531 TD_IS_RUNNING(owner)) 532 cpu_spinwait(); 533 continue; 534 } 535#endif 536 537 /* 538 * We were unable to acquire the lock and the write waiters 539 * flag is set, so we must block on the turnstile. 540 */ 541 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 542 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 543 rw); 544 turnstile_wait(&rw->lock_object, rw_owner(rw), 545 TS_EXCLUSIVE_QUEUE); 546 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 547 CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 548 __func__, rw); 549 } 550} 551 552/* 553 * This function is called if the first try at releasing a write lock failed. 554 * This means that one of the 2 waiter bits must be set indicating that at 555 * least one thread is waiting on this lock. 556 */ 557void 558_rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 559{ 560 struct turnstile *ts; 561 uintptr_t v; 562 int queue; 563 564 KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS), 565 ("%s: neither of the waiter flags are set", __func__)); 566 567 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 568 CTR2(KTR_LOCK, "%s: %p contested", __func__, rw); 569 570 turnstile_lock(&rw->lock_object); 571 ts = turnstile_lookup(&rw->lock_object); 572 573#ifdef ADAPTIVE_RWLOCKS 574 /* 575 * There might not be a turnstile for this lock if all of 576 * the waiters are adaptively spinning. In that case, just 577 * reset the lock to the unlocked state and return. 578 */ 579 if (ts == NULL) { 580 atomic_store_rel_ptr(&rw->rw_lock, RW_UNLOCKED); 581 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 582 CTR2(KTR_LOCK, "%s: %p no sleepers", __func__, rw); 583 turnstile_release(&rw->lock_object); 584 return; 585 } 586#else 587 MPASS(ts != NULL); 588#endif 589 590 /* 591 * Use the same algo as sx locks for now. Prefer waking up shared 592 * waiters if we have any over writers. This is probably not ideal. 593 * 594 * 'v' is the value we are going to write back to rw_lock. If we 595 * have waiters on both queues, we need to preserve the state of 596 * the waiter flag for the queue we don't wake up. For now this is 597 * hardcoded for the algorithm mentioned above. 598 * 599 * In the case of both readers and writers waiting we wakeup the 600 * readers but leave the RW_LOCK_WRITE_WAITERS flag set. If a 601 * new writer comes in before a reader it will claim the lock up 602 * above. There is probably a potential priority inversion in 603 * there that could be worked around either by waking both queues 604 * of waiters or doing some complicated lock handoff gymnastics. 605 * 606 * Note that in the ADAPTIVE_RWLOCKS case, if both flags are 607 * set, there might not be any actual writers on the turnstile 608 * as they might all be spinning. In that case, we don't want 609 * to preserve the RW_LOCK_WRITE_WAITERS flag as the turnstile 610 * is going to go away once we wakeup all the readers. 611 */ 612 v = RW_UNLOCKED; 613 if (rw->rw_lock & RW_LOCK_READ_WAITERS) { 614 queue = TS_SHARED_QUEUE; 615#ifdef ADAPTIVE_RWLOCKS 616 if (rw->rw_lock & RW_LOCK_WRITE_WAITERS && 617 !turnstile_empty(ts, TS_EXCLUSIVE_QUEUE)) 618 v |= RW_LOCK_WRITE_WAITERS; 619#else 620 v |= (rw->rw_lock & RW_LOCK_WRITE_WAITERS); 621#endif 622 } else 623 queue = TS_EXCLUSIVE_QUEUE; 624 625#ifdef ADAPTIVE_RWLOCKS 626 /* 627 * We have to make sure that we actually have waiters to 628 * wakeup. If they are all spinning, then we just need to 629 * disown the turnstile and return. 630 */ 631 if (turnstile_empty(ts, queue)) { 632 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 633 CTR2(KTR_LOCK, "%s: %p no sleepers 2", __func__, rw); 634 atomic_store_rel_ptr(&rw->rw_lock, v); 635 turnstile_disown(ts); 636 return; 637 } 638#endif 639 640 /* Wake up all waiters for the specific queue. */ 641 if (LOCK_LOG_TEST(&rw->lock_object, 0)) 642 CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw, 643 queue == TS_SHARED_QUEUE ? "read" : "write"); 644 turnstile_broadcast(ts, queue); 645 atomic_store_rel_ptr(&rw->rw_lock, v); 646 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 647} 648 649/* 650 * Attempt to do a non-blocking upgrade from a read lock to a write 651 * lock. This will only succeed if this thread holds a single read 652 * lock. Returns true if the upgrade succeeded and false otherwise. 653 */ 654int 655_rw_try_upgrade(struct rwlock *rw, const char *file, int line) 656{ 657 uintptr_t v, tid; 658 int success; 659 660 _rw_assert(rw, RA_RLOCKED, file, line); 661 662 /* 663 * Attempt to switch from one reader to a writer. If there 664 * are any write waiters, then we will have to lock the 665 * turnstile first to prevent races with another writer 666 * calling turnstile_wait() before we have claimed this 667 * turnstile. So, do the simple case of no waiters first. 668 */ 669 tid = (uintptr_t)curthread; 670 if (!(rw->rw_lock & RW_LOCK_WRITE_WAITERS)) { 671 success = atomic_cmpset_acq_ptr(&rw->rw_lock, 672 RW_READERS_LOCK(1), tid); 673 goto out; 674 } 675 676 /* 677 * Ok, we think we have write waiters, so lock the 678 * turnstile. 679 */ 680 turnstile_lock(&rw->lock_object); 681 682 /* 683 * Try to switch from one reader to a writer again. This time 684 * we honor the current state of the RW_LOCK_WRITE_WAITERS 685 * flag. If we obtain the lock with the flag set, then claim 686 * ownership of the turnstile. In the ADAPTIVE_RWLOCKS case 687 * it is possible for there to not be an associated turnstile 688 * even though there are waiters if all of the waiters are 689 * spinning. 690 */ 691 v = rw->rw_lock & RW_LOCK_WRITE_WAITERS; 692 success = atomic_cmpset_acq_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v, 693 tid | v); 694#ifdef ADAPTIVE_RWLOCKS 695 if (success && v && turnstile_lookup(&rw->lock_object) != NULL) 696#else 697 if (success && v) 698#endif 699 turnstile_claim(&rw->lock_object); 700 else 701 turnstile_release(&rw->lock_object); 702out: 703 LOCK_LOG_TRY("WUPGRADE", &rw->lock_object, 0, success, file, line); 704 if (success) 705 WITNESS_UPGRADE(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 706 file, line); 707 return (success); 708} 709 710/* 711 * Downgrade a write lock into a single read lock. 712 */ 713void 714_rw_downgrade(struct rwlock *rw, const char *file, int line) 715{ 716 struct turnstile *ts; 717 uintptr_t tid, v; 718 719 _rw_assert(rw, RA_WLOCKED, file, line); 720 721 WITNESS_DOWNGRADE(&rw->lock_object, 0, file, line); 722 723 /* 724 * Convert from a writer to a single reader. First we handle 725 * the easy case with no waiters. If there are any waiters, we 726 * lock the turnstile, "disown" the lock, and awaken any read 727 * waiters. 728 */ 729 tid = (uintptr_t)curthread; 730 if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1))) 731 goto out; 732 733 /* 734 * Ok, we think we have waiters, so lock the turnstile so we can 735 * read the waiter flags without any races. 736 */ 737 turnstile_lock(&rw->lock_object); 738 v = rw->rw_lock; 739 MPASS(v & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)); 740 741 /* 742 * Downgrade from a write lock while preserving 743 * RW_LOCK_WRITE_WAITERS and give up ownership of the 744 * turnstile. If there are any read waiters, wake them up. 745 * 746 * For ADAPTIVE_RWLOCKS, we have to allow for the fact that 747 * all of the read waiters might be spinning. In that case, 748 * act as if RW_LOCK_READ_WAITERS is not set. Also, only 749 * preserve the RW_LOCK_WRITE_WAITERS flag if at least one 750 * writer is blocked on the turnstile. 751 */ 752 ts = turnstile_lookup(&rw->lock_object); 753#ifdef ADAPTIVE_RWLOCKS 754 if (ts == NULL) 755 v &= ~(RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS); 756 else if (v & RW_LOCK_READ_WAITERS && 757 turnstile_empty(ts, TS_SHARED_QUEUE)) 758 v &= ~RW_LOCK_READ_WAITERS; 759 else if (v & RW_LOCK_WRITE_WAITERS && 760 turnstile_empty(ts, TS_EXCLUSIVE_QUEUE)) 761 v &= ~RW_LOCK_WRITE_WAITERS; 762#else 763 MPASS(ts != NULL); 764#endif 765 if (v & RW_LOCK_READ_WAITERS) 766 turnstile_broadcast(ts, TS_SHARED_QUEUE); 767 atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | 768 (v & RW_LOCK_WRITE_WAITERS)); 769 if (v & RW_LOCK_READ_WAITERS) 770 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 771#ifdef ADAPTIVE_RWLOCKS 772 else if (ts == NULL) 773 turnstile_release(&rw->lock_object); 774#endif 775 else 776 turnstile_disown(ts); 777out: 778 LOCK_LOG_LOCK("WDOWNGRADE", &rw->lock_object, 0, 0, file, line); 779} 780 781#ifdef INVARIANT_SUPPORT 782#ifndef INVARIANTS 783#undef _rw_assert 784#endif 785 786/* 787 * In the non-WITNESS case, rw_assert() can only detect that at least 788 * *some* thread owns an rlock, but it cannot guarantee that *this* 789 * thread owns an rlock. 790 */ 791void 792_rw_assert(struct rwlock *rw, int what, const char *file, int line) 793{ 794 795 if (panicstr != NULL) 796 return; 797 switch (what) { 798 case RA_LOCKED: 799 case RA_LOCKED | LA_NOTRECURSED: 800 case RA_RLOCKED: 801#ifdef WITNESS 802 witness_assert(&rw->lock_object, what, file, line); 803#else 804 /* 805 * If some other thread has a write lock or we have one 806 * and are asserting a read lock, fail. Also, if no one 807 * has a lock at all, fail. 808 */ 809 if (rw->rw_lock == RW_UNLOCKED || 810 (!(rw->rw_lock & RW_LOCK_READ) && (what == RA_RLOCKED || 811 rw_wowner(rw) != curthread))) 812 panic("Lock %s not %slocked @ %s:%d\n", 813 rw->lock_object.lo_name, (what == RA_RLOCKED) ? 814 "read " : "", file, line); 815#endif 816 break; 817 case RA_WLOCKED: 818 if (rw_wowner(rw) != curthread) 819 panic("Lock %s not exclusively locked @ %s:%d\n", 820 rw->lock_object.lo_name, file, line); 821 break; 822 case RA_UNLOCKED: 823#ifdef WITNESS 824 witness_assert(&rw->lock_object, what, file, line); 825#else 826 /* 827 * If we hold a write lock fail. We can't reliably check 828 * to see if we hold a read lock or not. 829 */ 830 if (rw_wowner(rw) == curthread) 831 panic("Lock %s exclusively locked @ %s:%d\n", 832 rw->lock_object.lo_name, file, line); 833#endif 834 break; 835 default: 836 panic("Unknown rw lock assertion: %d @ %s:%d", what, file, 837 line); 838 } 839} 840#endif /* INVARIANT_SUPPORT */ 841 842#ifdef DDB 843void 844db_show_rwlock(struct lock_object *lock) 845{ 846 struct rwlock *rw; 847 struct thread *td; 848 849 rw = (struct rwlock *)lock; 850 851 db_printf(" state: "); 852 if (rw->rw_lock == RW_UNLOCKED) 853 db_printf("UNLOCKED\n"); 854 else if (rw->rw_lock & RW_LOCK_READ) 855 db_printf("RLOCK: %ju locks\n", 856 (uintmax_t)(RW_READERS(rw->rw_lock))); 857 else { 858 td = rw_wowner(rw); 859 db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td, 860 td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm); 861 } 862 db_printf(" waiters: "); 863 switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) { 864 case RW_LOCK_READ_WAITERS: 865 db_printf("readers\n"); 866 break; 867 case RW_LOCK_WRITE_WAITERS: 868 db_printf("writers\n"); 869 break; 870 case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS: 871 db_printf("readers and writers\n"); 872 break; 873 default: 874 db_printf("none\n"); 875 break; 876 } 877} 878 879#endif 880