kern_rwlock.c revision 167012
1154941Sjhb/*- 2154941Sjhb * Copyright (c) 2006 John Baldwin <jhb@FreeBSD.org> 3154941Sjhb * All rights reserved. 4154941Sjhb * 5154941Sjhb * Redistribution and use in source and binary forms, with or without 6154941Sjhb * modification, are permitted provided that the following conditions 7154941Sjhb * are met: 8154941Sjhb * 1. Redistributions of source code must retain the above copyright 9154941Sjhb * notice, this list of conditions and the following disclaimer. 10154941Sjhb * 2. Redistributions in binary form must reproduce the above copyright 11154941Sjhb * notice, this list of conditions and the following disclaimer in the 12154941Sjhb * documentation and/or other materials provided with the distribution. 13154941Sjhb * 3. Neither the name of the author nor the names of any co-contributors 14154941Sjhb * may be used to endorse or promote products derived from this software 15154941Sjhb * without specific prior written permission. 16154941Sjhb * 17154941Sjhb * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18154941Sjhb * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19154941Sjhb * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20154941Sjhb * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21154941Sjhb * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22154941Sjhb * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23154941Sjhb * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24154941Sjhb * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25154941Sjhb * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26154941Sjhb * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27154941Sjhb * SUCH DAMAGE. 28154941Sjhb */ 29154941Sjhb 30154941Sjhb/* 31154941Sjhb * Machine independent bits of reader/writer lock implementation. 32154941Sjhb */ 33154941Sjhb 34154941Sjhb#include <sys/cdefs.h> 35154941Sjhb__FBSDID("$FreeBSD: head/sys/kern/kern_rwlock.c 167012 2007-02-26 08:26:44Z kmacy $"); 36154941Sjhb 37154941Sjhb#include "opt_ddb.h" 38154941Sjhb 39154941Sjhb#include <sys/param.h> 40154941Sjhb#include <sys/ktr.h> 41154941Sjhb#include <sys/lock.h> 42154941Sjhb#include <sys/mutex.h> 43154941Sjhb#include <sys/proc.h> 44154941Sjhb#include <sys/rwlock.h> 45154941Sjhb#include <sys/systm.h> 46154941Sjhb#include <sys/turnstile.h> 47164159Skmacy#include <sys/lock_profile.h> 48154941Sjhb#include <machine/cpu.h> 49154941Sjhb 50154941Sjhb#ifdef DDB 51154941Sjhb#include <ddb/ddb.h> 52154941Sjhb 53154941Sjhbstatic void db_show_rwlock(struct lock_object *lock); 54154941Sjhb#endif 55154941Sjhb 56154941Sjhbstruct lock_class lock_class_rw = { 57154941Sjhb "rw", 58157882Sjhb LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE, 59154941Sjhb#ifdef DDB 60154941Sjhb db_show_rwlock 61154941Sjhb#endif 62154941Sjhb}; 63154941Sjhb 64157826Sjhb/* 65157826Sjhb * Return a pointer to the owning thread if the lock is write-locked or 66157826Sjhb * NULL if the lock is unlocked or read-locked. 67157826Sjhb */ 68157826Sjhb#define rw_wowner(rw) \ 69154941Sjhb ((rw)->rw_lock & RW_LOCK_READ ? NULL : \ 70154941Sjhb (struct thread *)RW_OWNER((rw)->rw_lock)) 71154941Sjhb 72157826Sjhb/* 73157826Sjhb * Return a pointer to the owning thread for this lock who should receive 74157826Sjhb * any priority lent by threads that block on this lock. Currently this 75157826Sjhb * is identical to rw_wowner(). 76157826Sjhb */ 77157826Sjhb#define rw_owner(rw) rw_wowner(rw) 78157826Sjhb 79154941Sjhb#ifndef INVARIANTS 80154941Sjhb#define _rw_assert(rw, what, file, line) 81154941Sjhb#endif 82154941Sjhb 83154941Sjhbvoid 84154941Sjhbrw_init(struct rwlock *rw, const char *name) 85154941Sjhb{ 86154941Sjhb 87154941Sjhb rw->rw_lock = RW_UNLOCKED; 88154941Sjhb 89164246Skmacy lock_profile_object_init(&rw->rw_object, &lock_class_rw, name); 90154941Sjhb lock_init(&rw->rw_object, &lock_class_rw, name, NULL, LO_WITNESS | 91157882Sjhb LO_RECURSABLE | LO_UPGRADABLE); 92154941Sjhb} 93154941Sjhb 94154941Sjhbvoid 95154941Sjhbrw_destroy(struct rwlock *rw) 96154941Sjhb{ 97154941Sjhb 98154941Sjhb KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock not unlocked")); 99164159Skmacy lock_profile_object_destroy(&rw->rw_object); 100154941Sjhb lock_destroy(&rw->rw_object); 101154941Sjhb} 102154941Sjhb 103154941Sjhbvoid 104154941Sjhbrw_sysinit(void *arg) 105154941Sjhb{ 106154941Sjhb struct rw_args *args = arg; 107154941Sjhb 108154941Sjhb rw_init(args->ra_rw, args->ra_desc); 109154941Sjhb} 110154941Sjhb 111154941Sjhbvoid 112154941Sjhb_rw_wlock(struct rwlock *rw, const char *file, int line) 113154941Sjhb{ 114154941Sjhb 115154941Sjhb MPASS(curthread != NULL); 116157826Sjhb KASSERT(rw_wowner(rw) != curthread, 117154941Sjhb ("%s (%s): wlock already held @ %s:%d", __func__, 118154941Sjhb rw->rw_object.lo_name, file, line)); 119154941Sjhb WITNESS_CHECKORDER(&rw->rw_object, LOP_NEWORDER | LOP_EXCLUSIVE, file, 120154941Sjhb line); 121154941Sjhb __rw_wlock(rw, curthread, file, line); 122154941Sjhb LOCK_LOG_LOCK("WLOCK", &rw->rw_object, 0, 0, file, line); 123154941Sjhb WITNESS_LOCK(&rw->rw_object, LOP_EXCLUSIVE, file, line); 124160771Sjhb curthread->td_locks++; 125154941Sjhb} 126154941Sjhb 127154941Sjhbvoid 128154941Sjhb_rw_wunlock(struct rwlock *rw, const char *file, int line) 129154941Sjhb{ 130154941Sjhb 131154941Sjhb MPASS(curthread != NULL); 132154941Sjhb _rw_assert(rw, RA_WLOCKED, file, line); 133160771Sjhb curthread->td_locks--; 134154941Sjhb WITNESS_UNLOCK(&rw->rw_object, LOP_EXCLUSIVE, file, line); 135154941Sjhb LOCK_LOG_LOCK("WUNLOCK", &rw->rw_object, 0, 0, file, line); 136164159Skmacy lock_profile_release_lock(&rw->rw_object); 137154941Sjhb __rw_wunlock(rw, curthread, file, line); 138154941Sjhb} 139154941Sjhb 140154941Sjhbvoid 141154941Sjhb_rw_rlock(struct rwlock *rw, const char *file, int line) 142154941Sjhb{ 143157851Swkoszek#ifdef SMP 144157846Sjhb volatile struct thread *owner; 145157851Swkoszek#endif 146164159Skmacy uint64_t waitstart; 147164159Skmacy int contested; 148154941Sjhb uintptr_t x; 149154941Sjhb 150157826Sjhb KASSERT(rw_wowner(rw) != curthread, 151154941Sjhb ("%s (%s): wlock already held @ %s:%d", __func__, 152154941Sjhb rw->rw_object.lo_name, file, line)); 153154941Sjhb WITNESS_CHECKORDER(&rw->rw_object, LOP_NEWORDER, file, line); 154154941Sjhb 155154941Sjhb /* 156154941Sjhb * Note that we don't make any attempt to try to block read 157154941Sjhb * locks once a writer has blocked on the lock. The reason is 158154941Sjhb * that we currently allow for read locks to recurse and we 159154941Sjhb * don't keep track of all the holders of read locks. Thus, if 160154941Sjhb * we were to block readers once a writer blocked and a reader 161154941Sjhb * tried to recurse on their reader lock after a writer had 162154941Sjhb * blocked we would end up in a deadlock since the reader would 163154941Sjhb * be blocked on the writer, and the writer would be blocked 164154941Sjhb * waiting for the reader to release its original read lock. 165154941Sjhb */ 166154941Sjhb for (;;) { 167154941Sjhb /* 168154941Sjhb * Handle the easy case. If no other thread has a write 169154941Sjhb * lock, then try to bump up the count of read locks. Note 170154941Sjhb * that we have to preserve the current state of the 171154941Sjhb * RW_LOCK_WRITE_WAITERS flag. If we fail to acquire a 172154941Sjhb * read lock, then rw_lock must have changed, so restart 173154941Sjhb * the loop. Note that this handles the case of a 174154941Sjhb * completely unlocked rwlock since such a lock is encoded 175154941Sjhb * as a read lock with no waiters. 176154941Sjhb */ 177154941Sjhb x = rw->rw_lock; 178154941Sjhb if (x & RW_LOCK_READ) { 179154941Sjhb 180154941Sjhb /* 181154941Sjhb * The RW_LOCK_READ_WAITERS flag should only be set 182154941Sjhb * if another thread currently holds a write lock, 183154941Sjhb * and in that case RW_LOCK_READ should be clear. 184154941Sjhb */ 185154941Sjhb MPASS((x & RW_LOCK_READ_WAITERS) == 0); 186154941Sjhb if (atomic_cmpset_acq_ptr(&rw->rw_lock, x, 187154941Sjhb x + RW_ONE_READER)) { 188167012Skmacy lock_profile_obtain_lock_success(&rw->rw_object, contested, waitstart, file, line); 189154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 190154941Sjhb CTR4(KTR_LOCK, 191154941Sjhb "%s: %p succeed %p -> %p", __func__, 192154941Sjhb rw, (void *)x, 193154941Sjhb (void *)(x + RW_ONE_READER)); 194154941Sjhb break; 195154941Sjhb } 196167012Skmacy lock_profile_obtain_lock_failed(&rw->rw_object, &contested, &waitstart); 197157846Sjhb cpu_spinwait(); 198154941Sjhb continue; 199154941Sjhb } 200154941Sjhb 201154941Sjhb /* 202154941Sjhb * Okay, now it's the hard case. Some other thread already 203154941Sjhb * has a write lock, so acquire the turnstile lock so we can 204154941Sjhb * begin the process of blocking. 205154941Sjhb */ 206154941Sjhb turnstile_lock(&rw->rw_object); 207154941Sjhb 208154941Sjhb /* 209154941Sjhb * The lock might have been released while we spun, so 210154941Sjhb * recheck its state and restart the loop if there is no 211154941Sjhb * longer a write lock. 212154941Sjhb */ 213154941Sjhb x = rw->rw_lock; 214154941Sjhb if (x & RW_LOCK_READ) { 215154941Sjhb turnstile_release(&rw->rw_object); 216157846Sjhb cpu_spinwait(); 217154941Sjhb continue; 218154941Sjhb } 219154941Sjhb 220154941Sjhb /* 221154941Sjhb * Ok, it's still a write lock. If the RW_LOCK_READ_WAITERS 222154941Sjhb * flag is already set, then we can go ahead and block. If 223154941Sjhb * it is not set then try to set it. If we fail to set it 224154941Sjhb * drop the turnstile lock and restart the loop. 225154941Sjhb */ 226157826Sjhb if (!(x & RW_LOCK_READ_WAITERS)) { 227157826Sjhb if (!atomic_cmpset_ptr(&rw->rw_lock, x, 228157826Sjhb x | RW_LOCK_READ_WAITERS)) { 229157826Sjhb turnstile_release(&rw->rw_object); 230157826Sjhb cpu_spinwait(); 231157826Sjhb continue; 232157826Sjhb } 233157826Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 234157826Sjhb CTR2(KTR_LOCK, "%s: %p set read waiters flag", 235157826Sjhb __func__, rw); 236154941Sjhb } 237154941Sjhb 238157846Sjhb#ifdef SMP 239154941Sjhb /* 240157846Sjhb * If the owner is running on another CPU, spin until 241157846Sjhb * the owner stops running or the state of the lock 242157846Sjhb * changes. 243157846Sjhb */ 244157846Sjhb owner = (struct thread *)RW_OWNER(x); 245157846Sjhb if (TD_IS_RUNNING(owner)) { 246167012Skmacy lock_profile_obtain_lock_failed(&rw->rw_object, &contested, &waitstart); 247157846Sjhb turnstile_release(&rw->rw_object); 248157846Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 249157846Sjhb CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 250157846Sjhb __func__, rw, owner); 251157846Sjhb while ((struct thread*)RW_OWNER(rw->rw_lock)== owner && 252157846Sjhb TD_IS_RUNNING(owner)) 253157846Sjhb cpu_spinwait(); 254157846Sjhb continue; 255157846Sjhb } 256157846Sjhb#endif 257157846Sjhb 258157846Sjhb /* 259154941Sjhb * We were unable to acquire the lock and the read waiters 260154941Sjhb * flag is set, so we must block on the turnstile. 261154941Sjhb */ 262154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 263154941Sjhb CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 264154941Sjhb rw); 265154941Sjhb turnstile_wait(&rw->rw_object, rw_owner(rw), TS_SHARED_QUEUE); 266154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 267154941Sjhb CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 268154941Sjhb __func__, rw); 269154941Sjhb } 270154941Sjhb 271154941Sjhb /* 272154941Sjhb * TODO: acquire "owner of record" here. Here be turnstile dragons 273154941Sjhb * however. turnstiles don't like owners changing between calls to 274154941Sjhb * turnstile_wait() currently. 275154941Sjhb */ 276154941Sjhb 277154941Sjhb LOCK_LOG_LOCK("RLOCK", &rw->rw_object, 0, 0, file, line); 278154941Sjhb WITNESS_LOCK(&rw->rw_object, 0, file, line); 279160771Sjhb curthread->td_locks++; 280154941Sjhb} 281154941Sjhb 282154941Sjhbvoid 283154941Sjhb_rw_runlock(struct rwlock *rw, const char *file, int line) 284154941Sjhb{ 285154941Sjhb struct turnstile *ts; 286154941Sjhb uintptr_t x; 287154941Sjhb 288154941Sjhb _rw_assert(rw, RA_RLOCKED, file, line); 289160771Sjhb curthread->td_locks--; 290154941Sjhb WITNESS_UNLOCK(&rw->rw_object, 0, file, line); 291154941Sjhb LOCK_LOG_LOCK("RUNLOCK", &rw->rw_object, 0, 0, file, line); 292154941Sjhb 293154941Sjhb /* TODO: drop "owner of record" here. */ 294154941Sjhb 295154941Sjhb for (;;) { 296154941Sjhb /* 297154941Sjhb * See if there is more than one read lock held. If so, 298154941Sjhb * just drop one and return. 299154941Sjhb */ 300154941Sjhb x = rw->rw_lock; 301154941Sjhb if (RW_READERS(x) > 1) { 302154941Sjhb if (atomic_cmpset_ptr(&rw->rw_lock, x, 303154941Sjhb x - RW_ONE_READER)) { 304154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 305154941Sjhb CTR4(KTR_LOCK, 306154941Sjhb "%s: %p succeeded %p -> %p", 307154941Sjhb __func__, rw, (void *)x, 308154941Sjhb (void *)(x - RW_ONE_READER)); 309154941Sjhb break; 310154941Sjhb } 311154941Sjhb continue; 312164159Skmacy } else 313164159Skmacy lock_profile_release_lock(&rw->rw_object); 314154941Sjhb 315164159Skmacy 316154941Sjhb /* 317154941Sjhb * We should never have read waiters while at least one 318154941Sjhb * thread holds a read lock. (See note above) 319154941Sjhb */ 320154941Sjhb KASSERT(!(x & RW_LOCK_READ_WAITERS), 321154941Sjhb ("%s: waiting readers", __func__)); 322154941Sjhb 323154941Sjhb /* 324154941Sjhb * If there aren't any waiters for a write lock, then try 325154941Sjhb * to drop it quickly. 326154941Sjhb */ 327154941Sjhb if (!(x & RW_LOCK_WRITE_WAITERS)) { 328154941Sjhb 329154941Sjhb /* 330154941Sjhb * There shouldn't be any flags set and we should 331154941Sjhb * be the only read lock. If we fail to release 332154941Sjhb * the single read lock, then another thread might 333154941Sjhb * have just acquired a read lock, so go back up 334154941Sjhb * to the multiple read locks case. 335154941Sjhb */ 336154941Sjhb MPASS(x == RW_READERS_LOCK(1)); 337154941Sjhb if (atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1), 338154941Sjhb RW_UNLOCKED)) { 339154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 340154941Sjhb CTR2(KTR_LOCK, "%s: %p last succeeded", 341154941Sjhb __func__, rw); 342154941Sjhb break; 343154941Sjhb } 344154941Sjhb continue; 345154941Sjhb } 346154941Sjhb 347154941Sjhb /* 348154941Sjhb * There should just be one reader with one or more 349154941Sjhb * writers waiting. 350154941Sjhb */ 351154941Sjhb MPASS(x == (RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS)); 352154941Sjhb 353154941Sjhb /* 354154941Sjhb * Ok, we know we have a waiting writer and we think we 355154941Sjhb * are the last reader, so grab the turnstile lock. 356154941Sjhb */ 357154941Sjhb turnstile_lock(&rw->rw_object); 358154941Sjhb 359154941Sjhb /* 360154941Sjhb * Try to drop our lock leaving the lock in a unlocked 361154941Sjhb * state. 362154941Sjhb * 363154941Sjhb * If you wanted to do explicit lock handoff you'd have to 364154941Sjhb * do it here. You'd also want to use turnstile_signal() 365154941Sjhb * and you'd have to handle the race where a higher 366154941Sjhb * priority thread blocks on the write lock before the 367154941Sjhb * thread you wakeup actually runs and have the new thread 368154941Sjhb * "steal" the lock. For now it's a lot simpler to just 369154941Sjhb * wakeup all of the waiters. 370154941Sjhb * 371154941Sjhb * As above, if we fail, then another thread might have 372154941Sjhb * acquired a read lock, so drop the turnstile lock and 373154941Sjhb * restart. 374154941Sjhb */ 375154941Sjhb if (!atomic_cmpset_ptr(&rw->rw_lock, 376154941Sjhb RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS, RW_UNLOCKED)) { 377154941Sjhb turnstile_release(&rw->rw_object); 378154941Sjhb continue; 379154941Sjhb } 380154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 381154941Sjhb CTR2(KTR_LOCK, "%s: %p last succeeded with waiters", 382154941Sjhb __func__, rw); 383154941Sjhb 384154941Sjhb /* 385154941Sjhb * Ok. The lock is released and all that's left is to 386154941Sjhb * wake up the waiters. Note that the lock might not be 387154941Sjhb * free anymore, but in that case the writers will just 388154941Sjhb * block again if they run before the new lock holder(s) 389154941Sjhb * release the lock. 390154941Sjhb */ 391154941Sjhb ts = turnstile_lookup(&rw->rw_object); 392157846Sjhb MPASS(ts != NULL); 393154941Sjhb turnstile_broadcast(ts, TS_EXCLUSIVE_QUEUE); 394154941Sjhb turnstile_unpend(ts, TS_SHARED_LOCK); 395154941Sjhb break; 396154941Sjhb } 397154941Sjhb} 398154941Sjhb 399154941Sjhb/* 400154941Sjhb * This function is called when we are unable to obtain a write lock on the 401154941Sjhb * first try. This means that at least one other thread holds either a 402154941Sjhb * read or write lock. 403154941Sjhb */ 404154941Sjhbvoid 405154941Sjhb_rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 406154941Sjhb{ 407157851Swkoszek#ifdef SMP 408157846Sjhb volatile struct thread *owner; 409157851Swkoszek#endif 410154941Sjhb uintptr_t v; 411154941Sjhb 412154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 413154941Sjhb CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__, 414154941Sjhb rw->rw_object.lo_name, (void *)rw->rw_lock, file, line); 415154941Sjhb 416154941Sjhb while (!_rw_write_lock(rw, tid)) { 417154941Sjhb turnstile_lock(&rw->rw_object); 418154941Sjhb v = rw->rw_lock; 419154941Sjhb 420154941Sjhb /* 421154941Sjhb * If the lock was released while spinning on the 422154941Sjhb * turnstile chain lock, try again. 423154941Sjhb */ 424154941Sjhb if (v == RW_UNLOCKED) { 425154941Sjhb turnstile_release(&rw->rw_object); 426154941Sjhb cpu_spinwait(); 427154941Sjhb continue; 428154941Sjhb } 429154941Sjhb 430154941Sjhb /* 431154941Sjhb * If the lock was released by a writer with both readers 432154941Sjhb * and writers waiting and a reader hasn't woken up and 433154941Sjhb * acquired the lock yet, rw_lock will be set to the 434154941Sjhb * value RW_UNLOCKED | RW_LOCK_WRITE_WAITERS. If we see 435154941Sjhb * that value, try to acquire it once. Note that we have 436154941Sjhb * to preserve the RW_LOCK_WRITE_WAITERS flag as there are 437154941Sjhb * other writers waiting still. If we fail, restart the 438154941Sjhb * loop. 439154941Sjhb */ 440154941Sjhb if (v == (RW_UNLOCKED | RW_LOCK_WRITE_WAITERS)) { 441154941Sjhb if (atomic_cmpset_acq_ptr(&rw->rw_lock, 442154941Sjhb RW_UNLOCKED | RW_LOCK_WRITE_WAITERS, 443154941Sjhb tid | RW_LOCK_WRITE_WAITERS)) { 444154941Sjhb turnstile_claim(&rw->rw_object); 445154941Sjhb CTR2(KTR_LOCK, "%s: %p claimed by new writer", 446154941Sjhb __func__, rw); 447154941Sjhb break; 448154941Sjhb } 449154941Sjhb turnstile_release(&rw->rw_object); 450154941Sjhb cpu_spinwait(); 451154941Sjhb continue; 452154941Sjhb } 453154941Sjhb 454154941Sjhb /* 455154941Sjhb * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to 456154941Sjhb * set it. If we fail to set it, then loop back and try 457154941Sjhb * again. 458154941Sjhb */ 459157826Sjhb if (!(v & RW_LOCK_WRITE_WAITERS)) { 460157826Sjhb if (!atomic_cmpset_ptr(&rw->rw_lock, v, 461157826Sjhb v | RW_LOCK_WRITE_WAITERS)) { 462157826Sjhb turnstile_release(&rw->rw_object); 463157826Sjhb cpu_spinwait(); 464157826Sjhb continue; 465157826Sjhb } 466157826Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 467157826Sjhb CTR2(KTR_LOCK, "%s: %p set write waiters flag", 468157826Sjhb __func__, rw); 469154941Sjhb } 470154941Sjhb 471157846Sjhb#ifdef SMP 472157846Sjhb /* 473157846Sjhb * If the lock is write locked and the owner is 474157846Sjhb * running on another CPU, spin until the owner stops 475157846Sjhb * running or the state of the lock changes. 476157846Sjhb */ 477157846Sjhb owner = (struct thread *)RW_OWNER(v); 478157846Sjhb if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) { 479157846Sjhb turnstile_release(&rw->rw_object); 480157846Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 481157846Sjhb CTR3(KTR_LOCK, "%s: spinning on %p held by %p", 482157846Sjhb __func__, rw, owner); 483157846Sjhb while ((struct thread*)RW_OWNER(rw->rw_lock)== owner && 484157846Sjhb TD_IS_RUNNING(owner)) 485157846Sjhb cpu_spinwait(); 486157846Sjhb continue; 487157846Sjhb } 488157846Sjhb#endif 489154941Sjhb 490154941Sjhb /* 491154941Sjhb * We were unable to acquire the lock and the write waiters 492154941Sjhb * flag is set, so we must block on the turnstile. 493154941Sjhb */ 494154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 495154941Sjhb CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__, 496154941Sjhb rw); 497154941Sjhb turnstile_wait(&rw->rw_object, rw_owner(rw), 498154941Sjhb TS_EXCLUSIVE_QUEUE); 499154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 500154941Sjhb CTR2(KTR_LOCK, "%s: %p resuming from turnstile", 501154941Sjhb __func__, rw); 502154941Sjhb } 503154941Sjhb} 504154941Sjhb 505154941Sjhb/* 506154941Sjhb * This function is called if the first try at releasing a write lock failed. 507154941Sjhb * This means that one of the 2 waiter bits must be set indicating that at 508154941Sjhb * least one thread is waiting on this lock. 509154941Sjhb */ 510154941Sjhbvoid 511154941Sjhb_rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line) 512154941Sjhb{ 513154941Sjhb struct turnstile *ts; 514154941Sjhb uintptr_t v; 515154941Sjhb int queue; 516154941Sjhb 517154941Sjhb KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS), 518154941Sjhb ("%s: neither of the waiter flags are set", __func__)); 519154941Sjhb 520154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 521154941Sjhb CTR2(KTR_LOCK, "%s: %p contested", __func__, rw); 522154941Sjhb 523154941Sjhb turnstile_lock(&rw->rw_object); 524154941Sjhb ts = turnstile_lookup(&rw->rw_object); 525154941Sjhb 526157846Sjhb#ifdef SMP 527157846Sjhb /* 528157846Sjhb * There might not be a turnstile for this lock if all of 529157846Sjhb * the waiters are adaptively spinning. In that case, just 530157846Sjhb * reset the lock to the unlocked state and return. 531157846Sjhb */ 532157846Sjhb if (ts == NULL) { 533157846Sjhb atomic_store_rel_ptr(&rw->rw_lock, RW_UNLOCKED); 534157846Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 535157846Sjhb CTR2(KTR_LOCK, "%s: %p no sleepers", __func__, rw); 536157846Sjhb turnstile_release(&rw->rw_object); 537157846Sjhb return; 538157846Sjhb } 539157846Sjhb#else 540154941Sjhb MPASS(ts != NULL); 541157846Sjhb#endif 542154941Sjhb 543154941Sjhb /* 544154941Sjhb * Use the same algo as sx locks for now. Prefer waking up shared 545154941Sjhb * waiters if we have any over writers. This is probably not ideal. 546154941Sjhb * 547154941Sjhb * 'v' is the value we are going to write back to rw_lock. If we 548154941Sjhb * have waiters on both queues, we need to preserve the state of 549154941Sjhb * the waiter flag for the queue we don't wake up. For now this is 550154941Sjhb * hardcoded for the algorithm mentioned above. 551154941Sjhb * 552154941Sjhb * In the case of both readers and writers waiting we wakeup the 553154941Sjhb * readers but leave the RW_LOCK_WRITE_WAITERS flag set. If a 554154941Sjhb * new writer comes in before a reader it will claim the lock up 555154941Sjhb * above. There is probably a potential priority inversion in 556154941Sjhb * there that could be worked around either by waking both queues 557154941Sjhb * of waiters or doing some complicated lock handoff gymnastics. 558157846Sjhb * 559157846Sjhb * Note that in the SMP case, if both flags are set, there might 560157846Sjhb * not be any actual writers on the turnstile as they might all 561157846Sjhb * be spinning. In that case, we don't want to preserve the 562157846Sjhb * RW_LOCK_WRITE_WAITERS flag as the turnstile is going to go 563157846Sjhb * away once we wakeup all the readers. 564154941Sjhb */ 565157846Sjhb v = RW_UNLOCKED; 566154941Sjhb if (rw->rw_lock & RW_LOCK_READ_WAITERS) { 567154941Sjhb queue = TS_SHARED_QUEUE; 568157846Sjhb#ifdef SMP 569157846Sjhb if (rw->rw_lock & RW_LOCK_WRITE_WAITERS && 570157846Sjhb !turnstile_empty(ts, TS_EXCLUSIVE_QUEUE)) 571157846Sjhb v |= RW_LOCK_WRITE_WAITERS; 572157846Sjhb#else 573157846Sjhb v |= (rw->rw_lock & RW_LOCK_WRITE_WAITERS); 574157846Sjhb#endif 575157846Sjhb } else 576154941Sjhb queue = TS_EXCLUSIVE_QUEUE; 577157846Sjhb 578157846Sjhb#ifdef SMP 579157846Sjhb /* 580157846Sjhb * We have to make sure that we actually have waiters to 581157846Sjhb * wakeup. If they are all spinning, then we just need to 582157846Sjhb * disown the turnstile and return. 583157846Sjhb */ 584157846Sjhb if (turnstile_empty(ts, queue)) { 585157846Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 586157846Sjhb CTR2(KTR_LOCK, "%s: %p no sleepers 2", __func__, rw); 587157846Sjhb atomic_store_rel_ptr(&rw->rw_lock, v); 588157846Sjhb turnstile_disown(ts); 589157846Sjhb return; 590154941Sjhb } 591157846Sjhb#endif 592157846Sjhb 593157846Sjhb /* Wake up all waiters for the specific queue. */ 594154941Sjhb if (LOCK_LOG_TEST(&rw->rw_object, 0)) 595154941Sjhb CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw, 596154941Sjhb queue == TS_SHARED_QUEUE ? "read" : "write"); 597154941Sjhb turnstile_broadcast(ts, queue); 598154941Sjhb atomic_store_rel_ptr(&rw->rw_lock, v); 599154941Sjhb turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 600154941Sjhb} 601154941Sjhb 602157882Sjhb/* 603157882Sjhb * Attempt to do a non-blocking upgrade from a read lock to a write 604157882Sjhb * lock. This will only succeed if this thread holds a single read 605157882Sjhb * lock. Returns true if the upgrade succeeded and false otherwise. 606157882Sjhb */ 607157882Sjhbint 608157882Sjhb_rw_try_upgrade(struct rwlock *rw, const char *file, int line) 609157882Sjhb{ 610157882Sjhb uintptr_t v, tid; 611157882Sjhb int success; 612157882Sjhb 613157882Sjhb _rw_assert(rw, RA_RLOCKED, file, line); 614157882Sjhb 615157882Sjhb /* 616157882Sjhb * Attempt to switch from one reader to a writer. If there 617157882Sjhb * are any write waiters, then we will have to lock the 618157882Sjhb * turnstile first to prevent races with another writer 619157882Sjhb * calling turnstile_wait() before we have claimed this 620157882Sjhb * turnstile. So, do the simple case of no waiters first. 621157882Sjhb */ 622157882Sjhb tid = (uintptr_t)curthread; 623157882Sjhb if (!(rw->rw_lock & RW_LOCK_WRITE_WAITERS)) { 624157882Sjhb success = atomic_cmpset_acq_ptr(&rw->rw_lock, 625157882Sjhb RW_READERS_LOCK(1), tid); 626157882Sjhb goto out; 627157882Sjhb } 628157882Sjhb 629157882Sjhb /* 630157882Sjhb * Ok, we think we have write waiters, so lock the 631157882Sjhb * turnstile. 632157882Sjhb */ 633157882Sjhb turnstile_lock(&rw->rw_object); 634157882Sjhb 635157882Sjhb /* 636157882Sjhb * Try to switch from one reader to a writer again. This time 637157882Sjhb * we honor the current state of the RW_LOCK_WRITE_WAITERS 638157882Sjhb * flag. If we obtain the lock with the flag set, then claim 639157882Sjhb * ownership of the turnstile. In the SMP case it is possible 640157882Sjhb * for there to not be an associated turnstile even though there 641157882Sjhb * are waiters if all of the waiters are spinning. 642157882Sjhb */ 643157882Sjhb v = rw->rw_lock & RW_LOCK_WRITE_WAITERS; 644157882Sjhb success = atomic_cmpset_acq_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v, 645157882Sjhb tid | v); 646157882Sjhb#ifdef SMP 647157882Sjhb if (success && v && turnstile_lookup(&rw->rw_object) != NULL) 648157882Sjhb#else 649157882Sjhb if (success && v) 650157882Sjhb#endif 651157882Sjhb turnstile_claim(&rw->rw_object); 652157882Sjhb else 653157882Sjhb turnstile_release(&rw->rw_object); 654157882Sjhbout: 655157882Sjhb LOCK_LOG_TRY("WUPGRADE", &rw->rw_object, 0, success, file, line); 656157882Sjhb if (success) 657157882Sjhb WITNESS_UPGRADE(&rw->rw_object, LOP_EXCLUSIVE | LOP_TRYLOCK, 658157882Sjhb file, line); 659157882Sjhb return (success); 660157882Sjhb} 661157882Sjhb 662157882Sjhb/* 663157882Sjhb * Downgrade a write lock into a single read lock. 664157882Sjhb */ 665157882Sjhbvoid 666157882Sjhb_rw_downgrade(struct rwlock *rw, const char *file, int line) 667157882Sjhb{ 668157882Sjhb struct turnstile *ts; 669157882Sjhb uintptr_t tid, v; 670157882Sjhb 671157882Sjhb _rw_assert(rw, RA_WLOCKED, file, line); 672157882Sjhb 673157882Sjhb WITNESS_DOWNGRADE(&rw->rw_object, 0, file, line); 674157882Sjhb 675157882Sjhb /* 676157882Sjhb * Convert from a writer to a single reader. First we handle 677157882Sjhb * the easy case with no waiters. If there are any waiters, we 678157882Sjhb * lock the turnstile, "disown" the lock, and awaken any read 679157882Sjhb * waiters. 680157882Sjhb */ 681157882Sjhb tid = (uintptr_t)curthread; 682157882Sjhb if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1))) 683157882Sjhb goto out; 684157882Sjhb 685157882Sjhb /* 686157882Sjhb * Ok, we think we have waiters, so lock the turnstile so we can 687157882Sjhb * read the waiter flags without any races. 688157882Sjhb */ 689157882Sjhb turnstile_lock(&rw->rw_object); 690157882Sjhb v = rw->rw_lock; 691157882Sjhb MPASS(v & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)); 692157882Sjhb 693157882Sjhb /* 694157882Sjhb * Downgrade from a write lock while preserving 695157882Sjhb * RW_LOCK_WRITE_WAITERS and give up ownership of the 696157882Sjhb * turnstile. If there are any read waiters, wake them up. 697157882Sjhb * 698157882Sjhb * For SMP, we have to allow for the fact that all of the 699157882Sjhb * read waiters might be spinning. In that case, act as if 700157882Sjhb * RW_LOCK_READ_WAITERS is not set. Also, only preserve 701157882Sjhb * the RW_LOCK_WRITE_WAITERS flag if at least one writer is 702157882Sjhb * blocked on the turnstile. 703157882Sjhb */ 704157882Sjhb ts = turnstile_lookup(&rw->rw_object); 705157882Sjhb#ifdef SMP 706157882Sjhb if (ts == NULL) 707157882Sjhb v &= ~(RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS); 708157882Sjhb else if (v & RW_LOCK_READ_WAITERS && 709157882Sjhb turnstile_empty(ts, TS_SHARED_QUEUE)) 710157882Sjhb v &= ~RW_LOCK_READ_WAITERS; 711157882Sjhb else if (v & RW_LOCK_WRITE_WAITERS && 712157882Sjhb turnstile_empty(ts, TS_EXCLUSIVE_QUEUE)) 713157882Sjhb v &= ~RW_LOCK_WRITE_WAITERS; 714157882Sjhb#else 715157882Sjhb MPASS(ts != NULL); 716157882Sjhb#endif 717157882Sjhb if (v & RW_LOCK_READ_WAITERS) 718157882Sjhb turnstile_broadcast(ts, TS_SHARED_QUEUE); 719157882Sjhb atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | 720157882Sjhb (v & RW_LOCK_WRITE_WAITERS)); 721157882Sjhb if (v & RW_LOCK_READ_WAITERS) 722157882Sjhb turnstile_unpend(ts, TS_EXCLUSIVE_LOCK); 723157882Sjhb#ifdef SMP 724157882Sjhb else if (ts == NULL) 725157882Sjhb turnstile_release(&rw->rw_object); 726157882Sjhb#endif 727157882Sjhb else 728157882Sjhb turnstile_disown(ts); 729157882Sjhbout: 730157882Sjhb LOCK_LOG_LOCK("WDOWNGRADE", &rw->rw_object, 0, 0, file, line); 731157882Sjhb} 732157882Sjhb 733154941Sjhb#ifdef INVARIANT_SUPPORT 734155162Sscottl#ifndef INVARIANTS 735154941Sjhb#undef _rw_assert 736154941Sjhb#endif 737154941Sjhb 738154941Sjhb/* 739154941Sjhb * In the non-WITNESS case, rw_assert() can only detect that at least 740154941Sjhb * *some* thread owns an rlock, but it cannot guarantee that *this* 741154941Sjhb * thread owns an rlock. 742154941Sjhb */ 743154941Sjhbvoid 744154941Sjhb_rw_assert(struct rwlock *rw, int what, const char *file, int line) 745154941Sjhb{ 746154941Sjhb 747154941Sjhb if (panicstr != NULL) 748154941Sjhb return; 749154941Sjhb switch (what) { 750154941Sjhb case RA_LOCKED: 751154941Sjhb case RA_RLOCKED: 752154941Sjhb#ifdef WITNESS 753154941Sjhb witness_assert(&rw->rw_object, what, file, line); 754154941Sjhb#else 755154941Sjhb /* 756154941Sjhb * If some other thread has a write lock or we have one 757154941Sjhb * and are asserting a read lock, fail. Also, if no one 758154941Sjhb * has a lock at all, fail. 759154941Sjhb */ 760155061Sscottl if (rw->rw_lock == RW_UNLOCKED || 761155061Sscottl (!(rw->rw_lock & RW_LOCK_READ) && (what == RA_RLOCKED || 762157826Sjhb rw_wowner(rw) != curthread))) 763154941Sjhb panic("Lock %s not %slocked @ %s:%d\n", 764155012Sscottl rw->rw_object.lo_name, (what == RA_RLOCKED) ? 765154941Sjhb "read " : "", file, line); 766154941Sjhb#endif 767154941Sjhb break; 768154941Sjhb case RA_WLOCKED: 769157826Sjhb if (rw_wowner(rw) != curthread) 770154941Sjhb panic("Lock %s not exclusively locked @ %s:%d\n", 771154941Sjhb rw->rw_object.lo_name, file, line); 772154941Sjhb break; 773154941Sjhb case RA_UNLOCKED: 774154941Sjhb#ifdef WITNESS 775154941Sjhb witness_assert(&rw->rw_object, what, file, line); 776154941Sjhb#else 777154941Sjhb /* 778154941Sjhb * If we hold a write lock fail. We can't reliably check 779154941Sjhb * to see if we hold a read lock or not. 780154941Sjhb */ 781157826Sjhb if (rw_wowner(rw) == curthread) 782154941Sjhb panic("Lock %s exclusively locked @ %s:%d\n", 783154941Sjhb rw->rw_object.lo_name, file, line); 784154941Sjhb#endif 785154941Sjhb break; 786154941Sjhb default: 787154941Sjhb panic("Unknown rw lock assertion: %d @ %s:%d", what, file, 788154941Sjhb line); 789154941Sjhb } 790154941Sjhb} 791154941Sjhb#endif /* INVARIANT_SUPPORT */ 792154941Sjhb 793154941Sjhb#ifdef DDB 794154941Sjhbvoid 795154941Sjhbdb_show_rwlock(struct lock_object *lock) 796154941Sjhb{ 797154941Sjhb struct rwlock *rw; 798154941Sjhb struct thread *td; 799154941Sjhb 800154941Sjhb rw = (struct rwlock *)lock; 801154941Sjhb 802154941Sjhb db_printf(" state: "); 803154941Sjhb if (rw->rw_lock == RW_UNLOCKED) 804154941Sjhb db_printf("UNLOCKED\n"); 805154941Sjhb else if (rw->rw_lock & RW_LOCK_READ) 806154973Smlaier db_printf("RLOCK: %jd locks\n", 807154973Smlaier (intmax_t)(RW_READERS(rw->rw_lock))); 808154941Sjhb else { 809157826Sjhb td = rw_wowner(rw); 810154941Sjhb db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td, 811154941Sjhb td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm); 812154941Sjhb } 813154941Sjhb db_printf(" waiters: "); 814154941Sjhb switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) { 815154941Sjhb case RW_LOCK_READ_WAITERS: 816154941Sjhb db_printf("readers\n"); 817154941Sjhb break; 818154941Sjhb case RW_LOCK_WRITE_WAITERS: 819154941Sjhb db_printf("writers\n"); 820154941Sjhb break; 821154941Sjhb case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS: 822154941Sjhb db_printf("readers and waiters\n"); 823154941Sjhb break; 824154941Sjhb default: 825154941Sjhb db_printf("none\n"); 826154941Sjhb break; 827154941Sjhb } 828154941Sjhb} 829154941Sjhb 830154941Sjhb#endif 831