turnstile.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (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 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Big Theory Statement for turnstiles.
*
* Turnstiles provide blocking and wakeup support, including priority
* inheritance, for synchronization primitives (e.g. mutexes and rwlocks).
* Typical usage is as follows:
*
* To block on lock 'lp' for read access in foo_enter():
*
* ts = turnstile_lookup(lp);
* [ If the lock is still held, set the waiters bit
* turnstile_block(ts, TS_READER_Q, lp, &foo_sobj_ops);
*
* To wake threads waiting for write access to lock 'lp' in foo_exit():
*
* ts = turnstile_lookup(lp);
* [ Either drop the lock (change owner to NULL) or perform a direct
* [ handoff (change owner to one of the threads we're about to wake).
* [ If we're going to wake the last waiter, clear the waiters bit.
* turnstile_wakeup(ts, TS_WRITER_Q, nwaiters, new_owner or NULL);
*
* turnstile_lookup() returns holding the turnstile hash chain lock for lp.
* Both turnstile_block() and turnstile_wakeup() drop the turnstile lock.
* To abort a turnstile operation, the client must call turnstile_exit().
*
* Requirements of the client:
*
* (1) The lock's waiters indicator may be manipulated *only* while
* holding the turnstile hash chain lock (i.e. under turnstile_lookup()).
*
* (2) Once the lock is marked as having waiters, the owner may be
* changed *only* while holding the turnstile hash chain lock.
*
* (3) The caller must never block on an unheld lock.
*
* Consequences of these assumptions include the following:
*
* (a) It is impossible for a lock to be unheld but have waiters.
*
* (b) The priority inheritance code can safely assume that an active
* turnstile's ts_inheritor never changes until the inheritor calls
* turnstile_pi_waive().
*
* These assumptions simplify the implementation of both turnstiles and
* their clients.
*
* Background on priority inheritance:
*
* Priority inheritance allows a thread to "will" its dispatch priority
* to all the threads blocking it, directly or indirectly. This prevents
* situations called priority inversions in which a high-priority thread
* needs a lock held by a low-priority thread, which cannot run because
* of medium-priority threads. Without PI, the medium-priority threads
* can starve out the high-priority thread indefinitely. With PI, the
* low-priority thread becomes high-priority until it releases whatever
* synchronization object the real high-priority thread is waiting for.
*
* How turnstiles work:
*
* All active turnstiles reside in a global hash table, turnstile_table[].
* The address of a synchronization object determines its hash index.
* Each hash chain is protected by its own dispatcher lock, acquired
* by turnstile_lookup(). This lock protects the hash chain linkage, the
* contents of all turnstiles on the hash chain, and the waiters bits of
* every synchronization object in the system that hashes to the same chain.
* Giving the lock such broad scope simplifies the interactions between
* the turnstile code and its clients considerably. The blocking path
* is rare enough that this has no impact on scalability. (If it ever
* does, it's almost surely a second-order effect -- the real problem
* is that some synchronization object is *very* heavily contended.)
*
* Each thread has an attached turnstile in case it needs to block.
* A thread cannot block on more than one lock at a time, so one
* turnstile per thread is the most we ever need. The first thread
* to block on a lock donates its attached turnstile and adds it to
* the appropriate hash chain in turnstile_table[]. This becomes the
* "active turnstile" for the lock. Each subsequent thread that blocks
* on the same lock discovers that the lock already has an active
* turnstile, so it stashes its own turnstile on the active turnstile's
* freelist. As threads wake up, the process is reversed.
*
* turnstile_block() puts the current thread to sleep on the active
* turnstile for the desired lock, walks the blocking chain to apply
* priority inheritance to everyone in its way, and yields the CPU.
*
* turnstile_wakeup() waives any priority the owner may have inherited
* and wakes the specified number of waiting threads. If the caller is
* doing direct handoff of ownership (rather than just dropping the lock),
* the new owner automatically inherits priority from any existing waiters.
*/
#include <sys/turnstile.h>
#include <sys/sysmacros.h>
#include <sys/lockstat.h>
#include <sys/lwp_upimutex_impl.h>
#include <sys/schedctl.h>
/*
* The turnstile hash table is partitioned into two halves: the lower half
* is used for upimutextab[] locks, the upper half for everything else.
* The reason for the distinction is that SOBJ_USER_PI locks present a
* unique problem: the upimutextab[] lock passed to turnstile_block()
* cannot be dropped until the calling thread has blocked on its
* SOBJ_USER_PI lock and willed its priority down the blocking chain.
* At that point, the caller's t_lockp will be one of the turnstile locks.
* If mutex_exit() discovers that the upimutextab[] lock has waiters, it
* must wake them, which forces a lock ordering on us: the turnstile lock
* for the upimutextab[] lock will be acquired in mutex_vector_exit(),
* which will eventually call into turnstile_pi_waive(), which will then
* acquire the caller's thread lock, which in this case is the turnstile
* lock for the SOBJ_USER_PI lock. In general, when two turnstile locks
* must be held at the same time, the lock order must be the address order.
* Therefore, to prevent deadlock in turnstile_pi_waive(), we must ensure
* that upimutextab[] locks *always* hash to lower addresses than any
* other locks. You think this is cheesy? Let's see you do better.
*/
#define TURNSTILE_SOBJ_HASH(sobj) \
#define TURNSTILE_SOBJ_BUCKET(sobj) \
typedef struct turnstile_chain {
static lock_t turnstile_loser_lock;
/*
* Make 'inheritor' inherit priority from this turnstile.
*/
static void
{
return;
} else {
/*
* 'inheritor' is already inheriting from this turnstile,
* so just adjust its priority.
*/
}
}
/*
* If turnstile is non-NULL, remove it from inheritor's t_prioinv list.
* Compute new inherited priority, and return it.
*/
static pri_t
{
else
}
return (new_epri);
}
/*
* Remove turnstile from inheritor's t_prioinv list, compute
* new priority, and change the inheritor's effective priority if
* necessary. Keep in synch with turnstile_pi_recalc().
*/
static void
{
if (DISP_MUST_SURRENDER(inheritor))
}
/*
* Compute caller's new inherited priority, and change its effective
* priority if necessary. Necessary only for SOBJ_USER_PI, because of
* its interruptibility characteristic.
*/
void
turnstile_pi_recalc(void)
{
if (DISP_MUST_SURRENDER(inheritor))
}
/*
* Grab the lock protecting the hash chain for sobj
* and return the active turnstile for sobj, if any.
*/
turnstile_lookup(void *sobj)
{
break;
return (ts);
}
/*
* Drop the lock protecting the hash chain for sobj.
*/
void
turnstile_exit(void *sobj)
{
}
/*
* When we apply priority inheritance, we must grab the owner's thread lock
* while already holding the waiter's thread lock. If both thread locks are
* turnstile locks, this can lead to deadlock: while we hold L1 and try to
* grab L2, some unrelated thread may be applying priority inheritance to
* some other blocking chain, holding L2 and trying to grab L1. The most
* obvious solution -- do a lock_try() for the owner lock -- isn't quite
* sufficient because it can cause livelock: each thread may hold one lock,
* try to grab the other, fail, bail out, and try again, looping forever.
* To prevent livelock we must define a winner, i.e. define an arbitrary
* lock ordering on the turnstile locks. For simplicity we declare that
* virtual address order defines lock order, i.e. if L1 < L2, then the
* correct lock ordering is L1, L2. Thus the thread that holds L1 and
* wants L2 should spin until L2 is available, but the thread that holds
* L2 and can't get L1 on the first try must drop L2 and return failure.
* Moreover, the losing thread must not reacquire L2 until the winning
* thread has had a chance to grab it; to ensure this, the losing thread
* must grab L1 after dropping L2, thus spinning until the winner is done.
* Complicating matters further, note that the owner's thread lock pointer
* can change (i.e. be pointed at a different lock) while we're trying to
* grab it. If that happens, we must unwind our state and try again.
*
* On success, returns 1 with both locks held.
* On failure, returns 0 with neither lock held.
*/
static int
{
for (;;) {
/*
* If the locks are identical, there's nothing to do.
*/
return (1);
/*
* If 'olp' is still the right lock, return success.
* Otherwise, drop 'olp' and try the dance again.
*/
return (1);
} else {
/*
* If we're grabbing the locks out of order, we lose.
* Drop the waiter's lock, and then grab and release
* the owner's lock to ensure that we won't retry
* until the winner is done (as described above).
*/
return (0);
}
/*
* We're grabbing the locks in the right order,
* so spin until the owner's lock either becomes
* available or spontaneously changes.
*/
if (panicstr)
return (1);
spin_count++;
SMT_PAUSE();
}
olp, spin_count);
}
}
}
/*
* Block the current thread on a synchronization object.
*
* Turnstiles implement both kernel and user-level priority inheritance.
* To avoid missed wakeups in the user-level case, lwp_upimutex_lock() calls
* turnstile_block() holding the appropriate lock in the upimutextab (see
* the block comment in lwp_upimutex_lock() for details). The held lock is
* passed to turnstile_block() as the "mp" parameter, and will be dropped
* after priority has been willed, but before the thread actually sleeps
* (this locking behavior leads to some subtle ordering issues; see the
* block comment on turnstile hashing for details). This _must_ be the only
* lock held when calling turnstile_block() with a SOBJ_USER_PI sobj; holding
* other locks can result in panics due to cycles in the blocking chain.
*
* turnstile_block() always succeeds for kernel synchronization objects.
* For SOBJ_USER_PI locks the possible errors are EINTR for signals, and
* EDEADLK for cycles in the blocking chain. A return code of zero indicates
* *either* that the lock is now held, or that this is a spurious wake-up, or
* that the lock can never be held due to an ENOTRECOVERABLE error.
* It is up to lwp_upimutex_lock() to sort this all out.
*/
int
{
int error = 0;
int loser = 0;
thread_lock_high(t);
/*
* This is the first thread to block on this sobj.
* Take its attached turnstile and add it to the hash chain.
*/
} else {
/*
* Another thread has already donated its turnstile
* to block on this sobj, so ours isn't needed.
* Stash it on the active turnstile's freelist.
*/
}
/*
* Put the thread to sleep.
*/
}
CL_SLEEP(t); /* assign kernel priority */
t->t_sobj_ops = sobj_ops;
(void) new_mstate(t, LMS_SLEEP);
lwp->lwp_sysabort = 0;
/*
* make wchan0 non-zero to conform to the rule that
* threads blocking for user-level objects have a
* non-zero wchan0: this prevents spurious wake-ups
* by, for example, /proc.
*/
}
}
ts->ts_waiters++;
/*
* Follow the blocking chain to its end, willing our priority to
* everyone who's in our way.
*/
while (t->t_sobj_ops != NULL &&
panic("Deadlock: cycle in blocking chain");
}
/*
* If the cycle we've encountered ends in mp,
* then we know it isn't a 'real' cycle because
* we're going to drop mp before we go to sleep.
* Moreover, since we've come full circle we know
* that we must have willed priority to everyone
* in our way. Therefore, we can break out now.
*/
break;
if (loser)
/*
* For SOBJ_USER_PI, a cycle is an application
* deadlock which needs to be communicated
* back to the application.
*/
/*
* We enqueued a timeout, we are
* holding curthread->t_delay_lock.
* Drop it and dequeue the timeout.
*/
(void) lwp_timer_dequeue(lwptp);
}
mutex_exit(mp);
swtch(); /* necessary to transition state */
setallwatch();
lwp->lwp_asleep = 0;
lwp->lwp_sysabort = 0;
return (EDEADLK);
}
/*
* If we failed to grab the owner's thread lock,
* turnstile_interlock() will have dropped t's
* thread lock, so at this point we don't even know
* that 't' exists anymore. The simplest solution
* is to restart the entire priority inheritance dance
* from the beginning of the blocking chain, since
* we *do* know that 'curthread' still exists.
* Application of priority inheritance is idempotent,
* so it's OK that we're doing it more than once.
* Note also that since we've dropped our thread lock,
* we may already have been woken up; if so, our
* t_sobj_ops will be NULL, the loop will terminate,
* and the call to swtch() will be a no-op. Phew.
*
* There is one further complication: if two (or more)
* threads keep trying to grab the turnstile locks out
* of order and keep losing the race to another thread,
* these "dueling losers" can livelock the system.
* Therefore, once we get into this rare situation,
* we serialize all the losers.
*/
if (loser == 0) {
loser = 1;
}
t = curthread;
thread_lock_high(t);
continue;
}
/*
* We now have the owner's thread lock. If we are traversing
* from non-SOBJ_USER_PI ops to SOBJ_USER_PI ops, then we know
* that we have caught the thread while in the TS_SLEEP state,
* but holding mp. We know that this situation is transient
* (mp will be dropped before the holder actually sleeps on
* the SOBJ_USER_PI sobj), so we will spin waiting for mp to
* be dropped. Then, as in the turnstile_interlock() failure
* case, we will restart the priority inheritance dance.
*/
if (loser)
SMT_PAUSE();
continue;
}
if (loser)
t = curthread;
thread_lock_high(t);
continue;
}
t = owner;
}
if (loser)
/*
* Note: 't' and 'curthread' were synonymous before the loop above,
* but now they may be different. ('t' is now the last thread in
* the blocking chain.)
*/
int timedwait = 0;
/*
* We enqueued a timeout and we are
* holding curthread->t_delay_lock.
*/
timedwait = 1;
}
mutex_exit(mp);
splx(s);
swtch();
if (timedwait)
setallwatch();
MUSTRETURN(p, curthread))
lwp->lwp_sysabort = 0;
lwp->lwp_asleep = 0;
} else {
swtch();
}
return (error);
}
/*
* Remove thread from specified turnstile sleep queue; retrieve its
* free turnstile; if it is the last waiter, delete the turnstile
* from the turnstile chain and if there is an inheritor, delete it
* from the inheritor's t_prioinv chain.
*/
static void
{
} else {
/*
* The active turnstile's freelist is empty, so this
* must be the last waiter. Remove the turnstile
* from the hash chain and leave the now-inactive
* turnstile attached to the thread we're waking.
* Note that the ts_inheritor for the turnstile
* may be NULL. If one exists, its t_prioinv
* chain has to be updated.
*/
/*
* If we ever do a "disinherit" or "unboost", we need
* to do it only if "t" is a thread at the head of the
* sleep queue. Since the sleep queue is prioritized,
* the disinherit is necessary only if the interrupted
* thread is the highest priority thread.
* Otherwise, there is a higher priority thread blocked
* on the turnstile, whose inheritance cannot be
* disinherited. However, disinheriting is explicitly
* not done here, since it would require holding the
* inheritor's thread lock (see turnstile_unsleep()).
*/
}
}
ts->ts_waiters--;
sleepq_dequeue(t);
t->t_sobj_ops = NULL;
}
/*
* Wake threads that are blocked in a turnstile.
*/
void
{
/*
* Waive any priority we may have inherited from this turnstile.
*/
}
while (nthreads-- > 0) {
CL_WAKEUP(t); /* previous thread lock, tc_lock, not dropped */
/*
* If the caller did direct handoff of ownership,
* make the new owner inherit from this turnstile.
*/
if (t == owner) {
}
thread_unlock_high(t); /* drop run queue lock */
}
}
/*
* Change priority of a thread sleeping in a turnstile.
*/
void
{
sleepq_dequeue(t);
sleepq_insert(sqp, t);
}
/*
* We don't allow spurious wakeups of threads blocked in turnstiles
* for synch objects whose sobj_ops vector is initialized with the
* following routine (e.g. kernel synchronization objects).
* This is vital to the correctness of direct-handoff logic in some
* synchronization primitives, and it also simplifies the PI logic.
*/
/* ARGSUSED */
void
{
}
/*
* Wake up a thread blocked in a turnstile. Used to enable interruptibility
* of threads blocked on a SOBJ_USER_PI sobj.
*
* The implications of this interface are:
*
* 1. turnstile_block() may return with an EINTR.
* 2. When the owner of an sobj releases it, but no turnstile is found (i.e.
* no waiters), the (prior) owner must call turnstile_pi_recalc() to
* waive any priority inherited from interrupted waiters.
*
* When a waiter is interrupted, disinheriting its willed priority from the
* inheritor would require holding the inheritor's thread lock, while also
* holding the waiter's thread lock which is a turnstile lock. If the
* inheritor's thread lock is not free, and is also a turnstile lock that
* is out of lock order, the waiter's thread lock would have to be dropped.
* This leads to complications for the caller of turnstile_unsleep(), since
* the caller holds the waiter's thread lock. So, instead of disinheriting
* on waiter interruption, the owner is required to follow rule 2 above.
*
* Avoiding disinherit on waiter interruption seems acceptable because
* the owner runs at an unnecessarily high priority only while sobj is held,
* which it would have done in any case, if the waiter had not been interrupted.
*/
void
{
CL_SETRUN(t);
}