mutex.c revision 843e19887f64dde75055cf8842fc4db2171eff45
/*
* 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 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Big Theory Statement for mutual exclusion locking primitives.
*
* A mutex serializes multiple threads so that only one thread
* (the "owner" of the mutex) is active at a time. See mutex(9F)
* for a full description of the interfaces and programming model.
* The rest of this comment describes the implementation.
*
* Mutexes come in two flavors: adaptive and spin. mutex_init(9F)
* determines the type based solely on the iblock cookie (PIL) argument.
* PIL > LOCK_LEVEL implies a spin lock; everything else is adaptive.
*
* Spin mutexes block interrupts and spin until the lock becomes available.
* A thread may not sleep, or call any function that might sleep, while
* holding a spin mutex. With few exceptions, spin mutexes should only
* be used to synchronize with interrupt handlers.
*
* Adaptive mutexes (the default type) spin if the owner is running on
* another CPU and block otherwise. This policy is based on the assumption
* that mutex hold times are typically short enough that the time spent
* spinning is less than the time it takes to block. If you need mutual
* exclusion semantics with long hold times, consider an rwlock(9F) as
* RW_WRITER. Better still, reconsider the algorithm: if it requires
* mutual exclusion for long periods of time, it's probably not scalable.
*
* Adaptive mutexes are overwhelmingly more common than spin mutexes,
* so mutex_enter() assumes that the lock is adaptive. We get away
* with this by structuring mutexes so that an attempt to acquire a
* spin mutex as adaptive always fails. When mutex_enter() fails
* it punts to mutex_vector_enter(), which does all the hard stuff.
*
* mutex_vector_enter() first checks the type. If it's spin mutex,
* we just call lock_set_spl() and return. If it's an adaptive mutex,
* we check to see what the owner is doing. If the owner is running,
* we spin until the lock becomes available; if not, we mark the lock
* as having waiters and block.
*
* Blocking on a mutex is surprisingly delicate dance because, for speed,
* mutex_exit() doesn't use an atomic instruction. Thus we have to work
* a little harder in the (rarely-executed) blocking path to make sure
* we don't block on a mutex that's just been released -- otherwise we
* might never be woken up.
*
* The logic for synchronizing mutex_vector_enter() with mutex_exit()
* in the face of preemption and relaxed memory ordering is as follows:
*
* (1) Preemption in the middle of mutex_exit() must cause mutex_exit()
* to restart. Each platform must enforce this by checking the
* interrupted PC in the interrupt handler (or on return from trap --
* whichever is more convenient for the platform). If the PC
* lies within the critical region of mutex_exit(), the interrupt
* handler must reset the PC back to the beginning of mutex_exit().
* The critical region consists of all instructions up to, but not
* including, the store that clears the lock (which, of course,
* must never be executed twice.)
*
* This ensures that the owner will always check for waiters after
* resuming from a previous preemption.
*
* (2) A thread resuming in mutex_exit() does (at least) the following:
*
* when resuming: set CPU_THREAD = owner
* membar #StoreLoad
*
* in mutex_exit: check waiters bit; do wakeup if set
* membar #LoadStore|#StoreStore
* clear owner
* (at this point, other threads may or may not grab
* the lock, and we may or may not reacquire it)
*
* when blocking: membar #StoreStore (due to disp_lock_enter())
* set CPU_THREAD = (possibly) someone else
*
* (3) A thread blocking in mutex_vector_enter() does the following:
*
* set waiters bit
* membar #StoreLoad (via membar_enter())
* check CPU_THREAD for each CPU; abort if owner running
* membar #LoadLoad (via membar_consumer())
* check owner and waiters bit; abort if either changed
* block
*
* Thus the global memory orderings for (2) and (3) are as follows:
*
* (2M) mutex_exit() memory order:
*
* STORE CPU_THREAD = owner
* LOAD waiters bit
* STORE owner = NULL
* STORE CPU_THREAD = (possibly) someone else
*
* (3M) mutex_vector_enter() memory order:
*
* STORE waiters bit = 1
* LOAD CPU_THREAD for each CPU
* LOAD owner and waiters bit
*
* It has been verified by exhaustive simulation that all possible global
* memory orderings of (2M) interleaved with (3M) result in correct
* behavior. Moreover, these ordering constraints are minimal: changing
* the ordering of anything in (2M) or (3M) breaks the algorithm, creating
* windows for missed wakeups. Note: the possibility that other threads
* may grab the lock after the owner drops it can be factored out of the
* memory ordering analysis because mutex_vector_enter() won't block
* if the lock isn't still owned by the same thread.
*
* The only requirements of code outside the mutex implementation are
* (1) mutex_exit() preemption fixup in interrupt handlers or trap return,
* and (2) a membar #StoreLoad after setting CPU_THREAD in resume().
* Note: idle threads cannot grab adaptive locks (since they cannot block),
* so the membar may be safely omitted when resuming an idle thread.
*
* When a mutex has waiters, mutex_vector_exit() has several options:
*
* (1) Choose a waiter and make that thread the owner before waking it;
* this is known as "direct handoff" of ownership.
*
* (2) Drop the lock and wake one waiter.
*
* (3) Drop the lock, clear the waiters bit, and wake all waiters.
*
* In many ways (1) is the cleanest solution, but if a lock is moderately
* contended it defeats the adaptive spin logic. If we make some other
* thread the owner, but he's not ONPROC yet, then all other threads on
* other cpus that try to get the lock will conclude that the owner is
* blocked, so they'll block too. And so on -- it escalates quickly,
* with every thread taking the blocking path rather than the spin path.
* Thus, direct handoff is *not* a good idea for adaptive mutexes.
*
* Option (2) is the next most natural-seeming option, but it has several
* annoying properties. If there's more than one waiter, we must preserve
* the waiters bit on an unheld lock. On cas-capable platforms, where
* the waiters bit is part of the lock word, this means that both 0x0
* and 0x1 represent unheld locks, so we have to cas against *both*.
* Priority inheritance also gets more complicated, because a lock can
* have waiters but no owner to whom priority can be willed. So while
* it is possible to make option (2) work, it's surprisingly vile.
*
* Option (3), the least-intuitive at first glance, is what we actually do.
* It has the advantage that because you always wake all waiters, you
* never have to preserve the waiters bit. Waking all waiters seems like
* begging for a thundering herd problem, but consider: under option (2),
* every thread that grabs and drops the lock will wake one waiter -- so
* if the lock is fairly active, all waiters will be awakened very quickly
* anyway. Moreover, this is how adaptive locks are *supposed* to work.
* The blocking case is rare; the more common case (by 3-4 orders of
* magnitude) is that one or more threads spin waiting to get the lock.
* Only direct handoff can prevent the thundering herd problem, but as
* mentioned earlier, that would tend to defeat the adaptive spin logic.
* In practice, option (3) works well because the blocking case is rare.
*/
/*
* delayed lock retry with exponential delay for spin locks
*
* It is noted above that for both the spin locks and the adaptive locks,
* spinning is the dominate mode of operation. So long as there is only
* one thread waiting on a lock, the naive spin loop works very well in
* cache based architectures. The lock data structure is pulled into the
* memory traffic is generated until the lock is released. Unfortunately,
* once two or more threads are waiting on a lock, the naive spin has
* the property of generating maximum memory traffic from each spinning
* thread as the spinning threads contend for the lock data structure.
*
* By executing a delay loop before retrying a lock, a waiting thread
* can reduce its memory traffic by a large factor, depending on the
* size of the delay loop. A large delay loop greatly reduced the memory
* traffic, but has the drawback of having a period of time when
* no thread is attempting to gain the lock even though several threads
* might be waiting. A small delay loop has the drawback of not
* much reduction in memory traffic, but reduces the potential idle time.
* The theory of the exponential delay code is to start with a short
* delay loop and double the waiting time on each iteration, up to
* a preselected maximum. The BACKOFF_BASE provides the equivalent
* of 2 to 3 memory references delay for US-III+ and US-IV architectures.
* The BACKOFF_CAP is the equivalent of 50 to 100 memory references of
* time (less than 12 microseconds for a 1000 MHz system).
*
* To determine appropriate BACKOFF_BASE and BACKOFF_CAP values,
* studies on US-III+ and US-IV systems using 1 to 66 threads were
* done. A range of possible values were studied.
* Performance differences below 10 threads were not large. For
* systems with more threads, substantial increases in total lock
* throughput was observed with the given values. For cases where
* more than 20 threads were waiting on the same lock, lock throughput
* increased by a factor of 5 or more using the backoff algorithm.
*
* Some platforms may provide their own platform specific delay code,
* using plat_lock_delay(backoff). If it is available, plat_lock_delay
* is executed instead of the default delay code.
*/
#pragma weak plat_lock_delay
#include <sys/turnstile.h>
#include <sys/mutex_impl.h>
#include <sys/lockstat.h>
#include <sys/archsystm.h>
#define BACKOFF_BASE 50
#define BACKOFF_CAP 1600
/*
* The sobj_ops vector exports a set of functions needed when a thread
* is asleep on a synchronization object of this type.
*/
static sobj_ops_t mutex_sobj_ops = {
};
/*
* If the system panics on a mutex, save the address of the offending
* mutex in panic_mutex_addr, and save the contents in panic_mutex.
*/
static mutex_impl_t panic_mutex;
static mutex_impl_t *panic_mutex_addr;
static void
{
if (panicstr)
return;
panic_mutex = *lp;
panic("%s, lp=%p owner=%p thread=%p",
}
/*
* mutex_vector_enter() is called from the assembly mutex_enter() routine
* if the lock is held or is not of type MUTEX_ADAPTIVE.
*/
void
{
int backoff; /* current backoff */
int backctr; /* ctr for backoff */
int sleep_count = 0;
if (MUTEX_TYPE_SPIN(lp)) {
return;
}
if (!MUTEX_TYPE_ADAPTIVE(lp)) {
return;
}
/*
* Adaptive mutexes must not be acquired from above LOCK_LEVEL.
* We can migrate after loading CPU but before checking CPU_ON_INTR,
* so we must verify by disabling preemption and loading CPU again.
*/
if (CPU_ON_INTR(CPU))
}
if (&plat_lock_delay) {
backoff = 0;
} else {
}
for (;;) {
spin:
spin_count++;
/*
* Add an exponential backoff delay before trying again
* to touch the mutex data structure.
* the spin_count test and call to nulldev are to prevent
* the compiler optimizer from eliminating the delay loop.
*/
if (&plat_lock_delay) {
} else {
if (!spin_count) (void) nulldev();
}; /* delay */
if (backoff > BACKOFF_CAP) {
}
SMT_PAUSE();
}
if (panicstr)
return;
if (mutex_adaptive_tryenter(lp))
break;
continue;
}
/*
* If lock is held but owner is not yet set, spin.
* (Only relevant for platforms that don't have cas.)
*/
if (owner == MUTEX_NO_OWNER)
continue;
/*
* When searching the other CPUs, start with the one where
* we last saw the owner thread. If owner is running, spin.
*
* We must disable preemption at this point to guarantee
* that the list doesn't change while we traverse it
* without the cpu_lock mutex. While preemption is
* disabled, we must revalidate our cached cpu pointer.
*/
do {
goto spin;
}
/*
* The owner appears not to be running, so block.
* See the Big Theory Statement for memory ordering issues.
*/
membar_enter();
/*
* Recheck whether owner is running after waiters bit hits
* global visibility (above). If owner is running, spin.
*
* Since we are at ipl DISP_LEVEL, kernel preemption is
* disabled, however we still need to revalidate our cached
* cpu pointer to make sure the cpu hasn't been deleted.
*/
do {
goto spin;
}
/*
* If owner and waiters bit are unchanged, block.
*/
sleep_time -= gethrtime();
sleep_time += gethrtime();
sleep_count++;
} else {
}
}
if (sleep_time != 0) {
/*
* Note, sleep time is the sum of all the sleeping we
* did.
*/
}
/*
* We do not count a sleep as a spin.
*/
if (spin_count > sleep_count)
}
/*
* mutex_vector_tryenter() is called from the assembly mutex_tryenter()
* routine if the lock is held or is not of type MUTEX_ADAPTIVE.
*/
int
{
int s;
if (MUTEX_TYPE_ADAPTIVE(lp))
return (0); /* we already tried in assembly */
if (!MUTEX_TYPE_SPIN(lp)) {
return (0);
}
return (1);
}
splx(s);
return (0);
}
/*
* mutex_vector_exit() is called from mutex_exit() if the lock is not
* adaptive, has waiters, or is not owned by the current thread (panic).
*/
void
{
if (MUTEX_TYPE_SPIN(lp)) {
return;
}
return;
}
else
}
int
{
if (panicstr)
return (1);
if (MUTEX_TYPE_ADAPTIVE(lp))
}
{
kthread_id_t t;
return (t);
return (NULL);
}
/*
* The iblock cookie 'ibc' is the spl level associated with the lock;
* this alone determines whether the lock will be ADAPTIVE or SPIN.
*
* Adaptive mutexes created in zeroed memory do not need to call
* mutex_init() as their allocation in this fashion guarantees
* their initialization.
* eg adaptive mutexes created as static within the BSS or allocated
* by kmem_zalloc().
*/
/* ARGSUSED */
void
{
} else {
}
}
void
{
} else if (MUTEX_TYPE_SPIN(lp)) {
} else if (MUTEX_TYPE_ADAPTIVE(lp)) {
if (MUTEX_HAS_WAITERS(lp)) {
}
} else {
}
}
/*
* Simple C support for the cases where spin locks miss on the first try.
*/
void
{
int spin_count = 1;
int backoff; /* current backoff */
int backctr; /* ctr for backoff */
if (panicstr)
return;
if (ncpus == 1)
if (&plat_lock_delay) {
backoff = 0;
} else {
}
if (panicstr)
return;
spin_count++;
/*
* Add an exponential backoff delay before trying again
* to touch the mutex data structure.
* the spin_count test and call to nulldev are to prevent
* the compiler optimizer from eliminating the delay loop.
*/
if (&plat_lock_delay) {
} else {
/* delay */
if (!spin_count) (void) nulldev();
}
if (backoff > BACKOFF_CAP) {
}
SMT_PAUSE();
}
}
if (spin_count) {
}
}
void
{
int spin_count = 1;
int backoff; /* current backoff */
int backctr; /* ctr for backoff */
if (panicstr)
return;
if (ncpus == 1)
if (&plat_lock_delay) {
backoff = 0;
} else {
}
do {
if (panicstr) {
return;
}
spin_count++;
/*
* Add an exponential backoff delay before trying again
* to touch the mutex data structure.
* spin_count test and call to nulldev are to prevent
* compiler optimizer from eliminating the delay loop.
*/
if (&plat_lock_delay) {
} else {
if (!spin_count) (void) nulldev();
}
if (backoff > BACKOFF_CAP) {
}
SMT_PAUSE();
}
}
} while (!lock_spin_try(lp));
if (spin_count) {
}
}