/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Copyright (c) 2013, Joyent, Inc. All rights reserved.
*/
#include <sys/turnstile.h>
#include <sys/rwlock_impl.h>
#include <sys/lockstat.h>
/*
*
* An rwlock provides exclusive access to a single thread ("writer") or
* concurrent access to multiple threads ("readers"). See rwlock(9F)
* for a full description of the interfaces and programming model.
* The rest of this comment describes the implementation.
*
* An rwlock is a single word with the following structure:
*
* ---------------------------------------------------------------------
* | OWNER (writer) or HOLD COUNT (readers) | WRLOCK | WRWANT | WAIT |
* ---------------------------------------------------------------------
* 63 / 31 .. 3 2 1 0
*
* The waiters bit (0) indicates whether any threads are blocked waiting
* for the lock. The write-wanted bit (1) indicates whether any threads
* are blocked waiting for write access. The write-locked bit (2) indicates
* whether the lock is held by a writer, which determines whether the upper
* bits (3..31 in ILP32, 3..63 in LP64) should be interpreted as the owner
* (thread pointer) or the hold count (number of readers).
*
* In the absence of any contention, a writer gets the lock by setting
* this word to (curthread | RW_WRITE_LOCKED); a reader gets the lock
* by incrementing the hold count (i.e. adding 8, aka RW_READ_LOCK).
*
* A writer will fail to acquire the lock if any other thread owns it.
* A reader will fail if the lock is either owned (in the RW_READER and
* RW_READER_STARVEWRITER cases) or wanted by a writer (in the RW_READER
* case). rw_tryenter() returns 0 in these cases; rw_enter() blocks until
* the lock becomes available.
*
* When a thread blocks it acquires the rwlock's hashed turnstile lock and
* attempts to set RW_HAS_WAITERS (and RW_WRITE_WANTED in the writer case)
* atomically *only if the lock still appears busy*. A thread must never
* accidentally block for an available lock since there would be no owner
* to awaken it. casip() provides the required atomicity. Once casip()
* succeeds, the decision to block becomes final and irreversible. The
* thread will not become runnable again until it has been granted ownership
* of the lock via direct handoff from a former owner as described below.
*
* In the absence of any waiters, rw_exit() just clears the lock (if it
* is write-locked) or decrements the hold count (if it is read-locked).
* Note that even if waiters are present, decrementing the hold count
* to a non-zero value requires no special action since the lock is still
* held by at least one other thread.
*
* On the "final exit" (transition to unheld state) of a lock with waiters,
* rw_exit_wakeup() grabs the turnstile lock and transfers ownership directly
* to the next writer or set of readers. There are several advantages to this
* approach: (1) it closes all windows for priority inversion (when a new
* writer has grabbed the lock but has not yet inherited from blocked readers);
* (2) it prevents starvation of equal-priority threads by granting the lock
* in FIFO order; (3) it eliminates the need for a write-wanted count -- a
* single bit suffices because the lock remains held until all waiting
* writers are gone; (4) when we awaken N readers we can perform a single
* "atomic_add(&x, N)" to set the total hold count rather than having all N
* threads fight for the cache to perform an "atomic_add(&x, 1)" upon wakeup.
*
* The most interesting policy decision in rw_exit_wakeup() is which thread
* to wake. Starvation is always possible with priority-based scheduling,
* but any sane wakeup policy should at least satisfy these requirements:
*
* (1) The highest-priority thread in the system should not starve.
* (2) The highest-priority writer should not starve.
* (3) No writer should starve due to lower-priority threads.
* (4) No reader should starve due to lower-priority writers.
* (5) If all threads have equal priority, none of them should starve.
*
* We used to employ a writers-always-win policy, which doesn't even
* satisfy (1): a steady stream of low-priority writers can starve out
* a real-time reader! This is clearly a broken policy -- it violates
* (1), (4), and (5) -- but it's how rwlocks always used to behave.
*
* A round-robin policy (exiting readers grant the lock to blocked writers
* and vice versa) satisfies all but (3): a single high-priority writer
* and many low-priority readers can starve out medium-priority writers.
*
* A strict priority policy (grant the lock to the highest priority blocked
* thread) satisfies everything but (2): a steady stream of high-priority
* readers can permanently starve the highest-priority writer.
*
* The reason we care about (2) is that it's important to process writers
* reasonably quickly -- even if they're low priority -- because their very
* presence causes all readers to take the slow (blocking) path through this
* code. There is also a general sense that writers deserve some degree of
* deference because they're updating the data upon which all readers act.
* Presumably this data should not be allowed to become arbitrarily stale
* due to writer starvation. Finally, it seems reasonable to level the
* playing field a bit to compensate for the fact that it's so much harder
* for a writer to get in when there are already many readers present.
*
* A hybrid of round-robin and strict priority can be made to satisfy
* all five criteria. In this "writer priority policy" exiting readers
* always grant the lock to waiting writers, but exiting writers only
* grant the lock to readers of the same or higher priority than the
* highest-priority blocked writer. Thus requirement (2) is satisfied,
* necessarily, by a willful act of priority inversion: an exiting reader
* will grant the lock to a blocked writer even if there are blocked
* readers of higher priority. The situation is mitigated by the fact
* that writers always inherit priority from blocked readers, and the
* writer will awaken those readers as soon as it exits the lock.
*
* Finally, note that this hybrid scheme -- and indeed, any scheme that
* satisfies requirement (2) -- has an important consequence: if a lock is
* held as reader and a writer subsequently becomes blocked, any further
* readers must be blocked to avoid writer starvation. This implementation
* detail has ramifications for the semantics of rwlocks, as it prohibits
* recursively acquiring an rwlock as reader: any writer that wishes to
* acquire the lock after the first but before the second acquisition as
* reader will block the second acquisition -- resulting in deadlock. This
* itself is not necessarily prohibitive, as it is often straightforward to
* prevent a single thread from recursively acquiring an rwlock as reader.
* However, a more subtle situation arises when both a traditional mutex and
* a reader lock are acquired by two different threads in opposite order.
* (That is, one thread first acquires the mutex and then the rwlock as
* reader; the other acquires the rwlock as reader and then the mutex.) As
* with the single threaded case, this is fine absent a blocked writer: the
* thread that acquires the mutex before acquiring the rwlock as reader will
* has the rwlock as reader and is blocked on the held mutex. However, if
* an unrelated writer (that is, a third thread) becomes blocked on the
* rwlock after the first thread acquires the rwlock as reader but before
* it's able to acquire the mutex, the second thread -- with the mutex held
* -- will not be able to acquire the rwlock as reader due to the waiting
* writer, deadlocking the three threads. Unlike the single-threaded
* (recursive) rwlock acquisition case, this case can be quite a bit
* thornier to fix, especially as there is nothing inherently wrong in the
* locking strategy: the deadlock is really induced by requirement (2), not
* the consumers of the rwlock. To permit such consumers, we allow rwlock
* acquirers to explicitly opt out of requirement (2) by specifying
* RW_READER_STARVEWRITER when acquiring the rwlock. This (obviously) means
* that inifinite readers can starve writers, but it also allows for
* multiple readers in the presence of other synchronization primitives
* without regard for lock-ordering. And while certainly odd (and perhaps
* unwise), RW_READER_STARVEWRITER can be safely used alongside RW_READER on
* the same lock -- RW_READER_STARVEWRITER describes only the act of lock
* acquisition with respect to waiting writers, not the lock itself.
*
* rw_downgrade() follows the same wakeup policy as an exiting writer.
*
* rw_tryupgrade() has the same failure mode as rw_tryenter() for a
* write lock. Both honor the WRITE_WANTED bit by specification.
*
* The following rules apply to manipulation of rwlock internal state:
*
* (1) The rwlock is only modified via the atomic primitives casip()
* and atomic_add_ip().
*
* (2) The waiters bit and write-wanted bit are only modified under
* turnstile_lookup(). This ensures that the turnstile is consistent
* with the rwlock.
*
* (3) Waiters receive the lock by direct handoff from the previous
* owner. Therefore, waiters *always* wake up holding the lock.
*/
/*
* The sobj_ops vector exports a set of functions needed when a thread
* is asleep on a synchronization object of a given type.
*/
};
/*
* If the system panics on an rwlock, save the address of the offending
* rwlock in panic_rwlock_addr, and save the contents in panic_rwlock.
*/
static void
{
if (panicstr)
return;
panic_rwlock = *lp;
panic("%s, lp=%p wwwh=%lx thread=%p",
}
/* ARGSUSED */
void
{
}
void
{
else
}
}
/*
* Verify that an rwlock is held correctly.
*/
static int
{
return (0);
}
/*
* Full-service implementation of rw_enter() to handle all the hard cases.
* Called from the assembly version if anything complicated is going on.
* The only semantic difference between calling rw_enter() and calling
* rw_enter_sleep() directly is that we assume the caller has already done
* a THREAD_KPRI_REQUEST() in the RW_READER cases.
*/
void
{
int loop_count = 0;
} else if (rw == RW_READER_STARVEWRITER) {
} else {
}
for (;;) {
if (rw_lock_delay != NULL) {
if (++loop_count == ncpus_online) {
backoff = 0;
loop_count = 0;
}
}
continue;
}
break;
}
if (panicstr)
return;
return;
}
return;
}
do {
break;
/*
* The lock appears free now; try the dance again
*/
continue;
}
/*
* We really are going to block. Bump the stats, and drop
* kpri if we're a reader.
*/
sleep_time = -gethrtime();
} else {
}
sleep_time += gethrtime();
old >> RW_HOLD_COUNT_SHIFT);
/*
* We wake up holding the lock (and having kpri if we're
* a reader) via direct handoff from the previous owner.
*/
break;
}
membar_enter();
}
/*
* Return the number of readers to wake, or zero if we should wake a writer.
* Called only by exiting/downgrading writers (readers don't wake readers).
*/
static int
{
int count = 0;
while (next_reader != NULL) {
break;
count++;
}
return (count);
}
/*
* Full-service implementation of rw_exit() to handle all the hard cases.
* Called from the assembly version if anything complicated is going on.
* There is no semantic difference between calling rw_exit() and calling
* rw_exit_wakeup() directly.
*/
void
{
int nreaders;
int loop_count = 0;
membar_exit();
if (old & RW_WRITE_LOCKED) {
return;
}
} else {
return;
}
}
for (;;) {
/*
* If this is *not* the final exit of a lock with waiters,
* just drop the lock -- there's nothing tricky going on.
*/
if (rw_lock_delay != NULL) {
if (++loop_count == ncpus_online) {
backoff = 0;
loop_count = 0;
}
}
continue;
}
break;
}
/*
* This appears to be the final exit of a lock with waiters.
* If we do not have the lock as writer (that is, if this is
* the last exit of a reader with waiting writers), we will
* grab the lock as writer to prevent additional readers.
* (This is required because a reader that is acquiring the
* lock via RW_READER_STARVEWRITER will not observe the
* RW_WRITE_WANTED bit -- and we could therefore be racing
* with such readers here.)
*/
if (!(old & RW_WRITE_LOCKED)) {
continue;
}
/*
* Perform the final exit of a lock that has waiters.
*/
if ((old & RW_WRITE_LOCKED) &&
/*
* Don't drop the lock -- just set the hold count
* such that we grant the lock to all readers at once.
*/
new |= RW_HAS_WAITERS;
if (next_writer)
new |= RW_WRITE_WANTED;
membar_enter();
} else {
/*
* Don't drop the lock -- just transfer ownership
* directly to next_writer. Note that there must
* be at least one waiting writer, because we get
* here only if (A) the lock is read-locked or
* (B) there are no waiting readers. In case (A),
* since the lock is read-locked there would be no
* reason for other readers to have blocked unless
* the RW_WRITE_WANTED bit was set. In case (B),
* since there are waiters but no waiting readers,
* they must all be waiting writers.
*/
new |= RW_HAS_WAITERS;
if (next_writer->t_link)
new |= RW_WRITE_WANTED;
membar_enter();
}
break;
}
if (lock_value == RW_READ_LOCK) {
} else {
}
}
int
{
int loop_count = 0;
for (;;) {
return (0);
}
break;
if (rw_lock_delay != NULL) {
if (++loop_count == ncpus_online) {
backoff = 0;
loop_count = 0;
}
}
}
} else {
return (0);
}
membar_enter();
return (1);
}
void
{
membar_exit();
return;
}
if (nreaders > 0) {
delta -= RW_HAS_WAITERS;
}
}
}
int
{
do {
return (0);
membar_enter();
return (1);
}
int
{
}
int
{
return (_RW_WRITE_HELD(rwlp));
}
int
{
return (_RW_LOCK_HELD(rwlp));
}
/*
* Like rw_read_held(), but ASSERTs that the lock is currently held
*/
int
{
}
/*
* Returns non-zero if the lock is either held or desired by a writer
*/
int
{
return (_RW_ISWRITER(rwlp));
}
{
}