NetBSD-5.0.2/lib/libpthread/pthread_mutex.c
/* $NetBSD: pthread_mutex.c,v 1.51 2008/08/02 19:46:30 matt Exp $ */
/*-
* Copyright (c) 2001, 2003, 2006, 2007, 2008 The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
* by Nathan J. Williams, by Jason R. Thorpe, and by Andrew Doran.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/*
* To track threads waiting for mutexes to be released, we use lockless
* lists built on atomic operations and memory barriers.
*
* A simple spinlock would be faster and make the code easier to
* follow, but spinlocks are problematic in userspace. If a thread is
* preempted by the kernel while holding a spinlock, any other thread
* attempting to acquire that spinlock will needlessly busy wait.
*
* There is no good way to know that the holding thread is no longer
* running, nor to request a wake-up once it has begun running again.
* Of more concern, threads in the SCHED_FIFO class do not have a
* limited time quantum and so could spin forever, preventing the
* thread holding the spinlock from getting CPU time: it would never
* be released.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: pthread_mutex.c,v 1.51 2008/08/02 19:46:30 matt Exp $");
#include <sys/types.h>
#include <sys/lwpctl.h>
#include <sys/lock.h>
#include <errno.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "pthread.h"
#include "pthread_int.h"
#define MUTEX_WAITERS_BIT ((uintptr_t)0x01)
#define MUTEX_RECURSIVE_BIT ((uintptr_t)0x02)
#define MUTEX_DEFERRED_BIT ((uintptr_t)0x04)
#define MUTEX_THREAD ((uintptr_t)-16L)
#define MUTEX_HAS_WAITERS(x) ((uintptr_t)(x) & MUTEX_WAITERS_BIT)
#define MUTEX_RECURSIVE(x) ((uintptr_t)(x) & MUTEX_RECURSIVE_BIT)
#define MUTEX_OWNER(x) ((uintptr_t)(x) & MUTEX_THREAD)
#if __GNUC_PREREQ__(3, 0)
#define NOINLINE __attribute ((noinline))
#else
#define NOINLINE /* nothing */
#endif
static void pthread__mutex_wakeup(pthread_t, pthread_mutex_t *);
static int pthread__mutex_lock_slow(pthread_mutex_t *);
static int pthread__mutex_unlock_slow(pthread_mutex_t *);
static void pthread__mutex_pause(void);
int _pthread_mutex_held_np(pthread_mutex_t *);
pthread_t _pthread_mutex_owner_np(pthread_mutex_t *);
__weak_alias(pthread_mutex_held_np,_pthread_mutex_held_np)
__weak_alias(pthread_mutex_owner_np,_pthread_mutex_owner_np)
__strong_alias(__libc_mutex_init,pthread_mutex_init)
__strong_alias(__libc_mutex_lock,pthread_mutex_lock)
__strong_alias(__libc_mutex_trylock,pthread_mutex_trylock)
__strong_alias(__libc_mutex_unlock,pthread_mutex_unlock)
__strong_alias(__libc_mutex_destroy,pthread_mutex_destroy)
__strong_alias(__libc_mutexattr_init,pthread_mutexattr_init)
__strong_alias(__libc_mutexattr_destroy,pthread_mutexattr_destroy)
__strong_alias(__libc_mutexattr_settype,pthread_mutexattr_settype)
__strong_alias(__libc_thr_once,pthread_once)
int
pthread_mutex_init(pthread_mutex_t *ptm, const pthread_mutexattr_t *attr)
{
intptr_t type;
if (attr == NULL)
type = PTHREAD_MUTEX_NORMAL;
else
type = (intptr_t)attr->ptma_private;
switch (type) {
case PTHREAD_MUTEX_ERRORCHECK:
__cpu_simple_lock_set(&ptm->ptm_errorcheck);
ptm->ptm_owner = NULL;
break;
case PTHREAD_MUTEX_RECURSIVE:
__cpu_simple_lock_clear(&ptm->ptm_errorcheck);
ptm->ptm_owner = (void *)MUTEX_RECURSIVE_BIT;
break;
default:
__cpu_simple_lock_clear(&ptm->ptm_errorcheck);
ptm->ptm_owner = NULL;
break;
}
ptm->ptm_magic = _PT_MUTEX_MAGIC;
ptm->ptm_waiters = NULL;
ptm->ptm_recursed = 0;
return 0;
}
int
pthread_mutex_destroy(pthread_mutex_t *ptm)
{
pthread__error(EINVAL, "Invalid mutex",
ptm->ptm_magic == _PT_MUTEX_MAGIC);
pthread__error(EBUSY, "Destroying locked mutex",
MUTEX_OWNER(ptm->ptm_owner) == 0);
ptm->ptm_magic = _PT_MUTEX_DEAD;
return 0;
}
int
pthread_mutex_lock(pthread_mutex_t *ptm)
{
pthread_t self;
void *val;
self = pthread__self();
val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self);
if (__predict_true(val == NULL)) {
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
return pthread__mutex_lock_slow(ptm);
}
/* We want function call overhead. */
NOINLINE static void
pthread__mutex_pause(void)
{
pthread__smt_pause();
}
/*
* Spin while the holder is running. 'lwpctl' gives us the true
* status of the thread. pt_blocking is set by libpthread in order
* to cut out system call and kernel spinlock overhead on remote CPUs
* (could represent many thousands of clock cycles). pt_blocking also
* makes this thread yield if the target is calling sched_yield().
*/
NOINLINE static void *
pthread__mutex_spin(pthread_mutex_t *ptm, pthread_t owner)
{
pthread_t thread;
unsigned int count, i;
for (count = 2;; owner = ptm->ptm_owner) {
thread = (pthread_t)MUTEX_OWNER(owner);
if (thread == NULL)
break;
if (thread->pt_lwpctl->lc_curcpu == LWPCTL_CPU_NONE ||
thread->pt_blocking)
break;
if (count < 128)
count += count;
for (i = count; i != 0; i--)
pthread__mutex_pause();
}
return owner;
}
NOINLINE static int
pthread__mutex_lock_slow(pthread_mutex_t *ptm)
{
void *waiters, *new, *owner, *next;
pthread_t self;
pthread__error(EINVAL, "Invalid mutex",
ptm->ptm_magic == _PT_MUTEX_MAGIC);
owner = ptm->ptm_owner;
self = pthread__self();
/* Recursive or errorcheck? */
if (MUTEX_OWNER(owner) == (uintptr_t)self) {
if (MUTEX_RECURSIVE(owner)) {
if (ptm->ptm_recursed == INT_MAX)
return EAGAIN;
ptm->ptm_recursed++;
return 0;
}
if (__SIMPLELOCK_LOCKED_P(&ptm->ptm_errorcheck))
return EDEADLK;
}
for (;; owner = ptm->ptm_owner) {
/* Spin while the owner is running. */
owner = pthread__mutex_spin(ptm, owner);
/* If it has become free, try to acquire it again. */
if (MUTEX_OWNER(owner) == 0) {
do {
new = (void *)
((uintptr_t)self | (uintptr_t)owner);
next = atomic_cas_ptr(&ptm->ptm_owner, owner,
new);
if (next == owner) {
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
owner = next;
} while (MUTEX_OWNER(owner) == 0);
/*
* We have lost the race to acquire the mutex.
* The new owner could be running on another
* CPU, in which case we should spin and avoid
* the overhead of blocking.
*/
continue;
}
/*
* Nope, still held. Add thread to the list of waiters.
* Issue a memory barrier to ensure mutexwait/mutexnext
* are visible before we enter the waiters list.
*/
self->pt_mutexwait = 1;
for (waiters = ptm->ptm_waiters;; waiters = next) {
self->pt_mutexnext = waiters;
membar_producer();
next = atomic_cas_ptr(&ptm->ptm_waiters, waiters, self);
if (next == waiters)
break;
}
/*
* Set the waiters bit and block.
*
* Note that the mutex can become unlocked before we set
* the waiters bit. If that happens it's not safe to sleep
* as we may never be awoken: we must remove the current
* thread from the waiters list and try again.
*
* Because we are doing this atomically, we can't remove
* one waiter: we must remove all waiters and awken them,
* then sleep in _lwp_park() until we have been awoken.
*
* Issue a memory barrier to ensure that we are reading
* the value of ptm_owner/pt_mutexwait after we have entered
* the waiters list (the CAS itself must be atomic).
*/
membar_consumer();
for (owner = ptm->ptm_owner;; owner = next) {
if (MUTEX_HAS_WAITERS(owner))
break;
if (MUTEX_OWNER(owner) == 0) {
pthread__mutex_wakeup(self, ptm);
break;
}
new = (void *)((uintptr_t)owner | MUTEX_WAITERS_BIT);
next = atomic_cas_ptr(&ptm->ptm_owner, owner, new);
if (next == owner) {
/*
* pthread_mutex_unlock() can do a
* non-interlocked CAS. We cannot
* know if our attempt to set the
* waiters bit has succeeded while
* the holding thread is running.
* There are many assumptions; see
* sys/kern/kern_mutex.c for details.
* In short, we must spin if we see
* that the holder is running again.
*/
membar_sync();
next = pthread__mutex_spin(ptm, owner);
}
}
/*
* We may have been awoken by the current thread above,
* or will be awoken by the current holder of the mutex.
* The key requirement is that we must not proceed until
* told that we are no longer waiting (via pt_mutexwait
* being set to zero). Otherwise it is unsafe to re-enter
* the thread onto the waiters list.
*/
while (self->pt_mutexwait) {
self->pt_blocking++;
(void)_lwp_park(NULL, self->pt_unpark,
__UNVOLATILE(&ptm->ptm_waiters),
__UNVOLATILE(&ptm->ptm_waiters));
self->pt_unpark = 0;
self->pt_blocking--;
membar_sync();
}
}
}
int
pthread_mutex_trylock(pthread_mutex_t *ptm)
{
pthread_t self;
void *val, *new, *next;
self = pthread__self();
val = atomic_cas_ptr(&ptm->ptm_owner, NULL, self);
if (__predict_true(val == NULL)) {
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
if (MUTEX_RECURSIVE(val)) {
if (MUTEX_OWNER(val) == 0) {
new = (void *)((uintptr_t)self | (uintptr_t)val);
next = atomic_cas_ptr(&ptm->ptm_owner, val, new);
if (__predict_true(next == val)) {
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
}
if (MUTEX_OWNER(val) == (uintptr_t)self) {
if (ptm->ptm_recursed == INT_MAX)
return EAGAIN;
ptm->ptm_recursed++;
return 0;
}
}
return EBUSY;
}
int
pthread_mutex_unlock(pthread_mutex_t *ptm)
{
pthread_t self;
void *value;
/*
* Note this may be a non-interlocked CAS. See lock_slow()
* above and sys/kern/kern_mutex.c for details.
*/
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_exit();
#endif
self = pthread__self();
value = atomic_cas_ptr_ni(&ptm->ptm_owner, self, NULL);
if (__predict_true(value == self))
return 0;
return pthread__mutex_unlock_slow(ptm);
}
NOINLINE static int
pthread__mutex_unlock_slow(pthread_mutex_t *ptm)
{
pthread_t self, owner, new;
int weown, error, deferred;
pthread__error(EINVAL, "Invalid mutex",
ptm->ptm_magic == _PT_MUTEX_MAGIC);
self = pthread__self();
owner = ptm->ptm_owner;
weown = (MUTEX_OWNER(owner) == (uintptr_t)self);
deferred = (int)((uintptr_t)owner & MUTEX_DEFERRED_BIT);
error = 0;
if (__SIMPLELOCK_LOCKED_P(&ptm->ptm_errorcheck)) {
if (!weown) {
error = EPERM;
new = owner;
} else {
new = NULL;
}
} else if (MUTEX_RECURSIVE(owner)) {
if (!weown) {
error = EPERM;
new = owner;
} else if (ptm->ptm_recursed) {
ptm->ptm_recursed--;
new = owner;
} else {
new = (pthread_t)MUTEX_RECURSIVE_BIT;
}
} else {
pthread__error(EPERM,
"Unlocking unlocked mutex", (owner != NULL));
pthread__error(EPERM,
"Unlocking mutex owned by another thread", weown);
new = NULL;
}
/*
* Release the mutex. If there appear to be waiters, then
* wake them up.
*/
if (new != owner) {
owner = atomic_swap_ptr(&ptm->ptm_owner, new);
if (MUTEX_HAS_WAITERS(owner) != 0) {
pthread__mutex_wakeup(self, ptm);
return 0;
}
}
/*
* There were no waiters, but we may have deferred waking
* other threads until mutex unlock - we must wake them now.
*/
if (!deferred)
return error;
if (self->pt_nwaiters == 1) {
/*
* If the calling thread is about to block, defer
* unparking the target until _lwp_park() is called.
*/
if (self->pt_willpark && self->pt_unpark == 0) {
self->pt_unpark = self->pt_waiters[0];
} else {
(void)_lwp_unpark(self->pt_waiters[0],
__UNVOLATILE(&ptm->ptm_waiters));
}
} else {
(void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters,
__UNVOLATILE(&ptm->ptm_waiters));
}
self->pt_nwaiters = 0;
return error;
}
static void
pthread__mutex_wakeup(pthread_t self, pthread_mutex_t *ptm)
{
pthread_t thread, next;
ssize_t n, rv;
/*
* Take ownership of the current set of waiters. No
* need for a memory barrier following this, all loads
* are dependent upon 'thread'.
*/
thread = atomic_swap_ptr(&ptm->ptm_waiters, NULL);
for (;;) {
/*
* Pull waiters from the queue and add to our list.
* Use a memory barrier to ensure that we safely
* read the value of pt_mutexnext before 'thread'
* sees pt_mutexwait being cleared.
*/
for (n = self->pt_nwaiters, self->pt_nwaiters = 0;
n < pthread__unpark_max && thread != NULL;
thread = next) {
next = thread->pt_mutexnext;
if (thread != self) {
self->pt_waiters[n++] = thread->pt_lid;
membar_sync();
}
thread->pt_mutexwait = 0;
/* No longer safe to touch 'thread' */
}
switch (n) {
case 0:
return;
case 1:
/*
* If the calling thread is about to block,
* defer unparking the target until _lwp_park()
* is called.
*/
if (self->pt_willpark && self->pt_unpark == 0) {
self->pt_unpark = self->pt_waiters[0];
return;
}
rv = (ssize_t)_lwp_unpark(self->pt_waiters[0],
__UNVOLATILE(&ptm->ptm_waiters));
if (rv != 0 && errno != EALREADY && errno != EINTR &&
errno != ESRCH) {
pthread__errorfunc(__FILE__, __LINE__,
__func__, "_lwp_unpark failed");
}
return;
default:
rv = _lwp_unpark_all(self->pt_waiters, (size_t)n,
__UNVOLATILE(&ptm->ptm_waiters));
if (rv != 0 && errno != EINTR) {
pthread__errorfunc(__FILE__, __LINE__,
__func__, "_lwp_unpark_all failed");
}
break;
}
}
}
int
pthread_mutexattr_init(pthread_mutexattr_t *attr)
{
attr->ptma_magic = _PT_MUTEXATTR_MAGIC;
attr->ptma_private = (void *)PTHREAD_MUTEX_DEFAULT;
return 0;
}
int
pthread_mutexattr_destroy(pthread_mutexattr_t *attr)
{
pthread__error(EINVAL, "Invalid mutex attribute",
attr->ptma_magic == _PT_MUTEXATTR_MAGIC);
return 0;
}
int
pthread_mutexattr_gettype(const pthread_mutexattr_t *attr, int *typep)
{
pthread__error(EINVAL, "Invalid mutex attribute",
attr->ptma_magic == _PT_MUTEXATTR_MAGIC);
*typep = (int)(intptr_t)attr->ptma_private;
return 0;
}
int
pthread_mutexattr_settype(pthread_mutexattr_t *attr, int type)
{
pthread__error(EINVAL, "Invalid mutex attribute",
attr->ptma_magic == _PT_MUTEXATTR_MAGIC);
switch (type) {
case PTHREAD_MUTEX_NORMAL:
case PTHREAD_MUTEX_ERRORCHECK:
case PTHREAD_MUTEX_RECURSIVE:
attr->ptma_private = (void *)(intptr_t)type;
return 0;
default:
return EINVAL;
}
}
static void
once_cleanup(void *closure)
{
pthread_mutex_unlock((pthread_mutex_t *)closure);
}
int
pthread_once(pthread_once_t *once_control, void (*routine)(void))
{
if (once_control->pto_done == 0) {
pthread_mutex_lock(&once_control->pto_mutex);
pthread_cleanup_push(&once_cleanup, &once_control->pto_mutex);
if (once_control->pto_done == 0) {
routine();
once_control->pto_done = 1;
}
pthread_cleanup_pop(1);
}
return 0;
}
void
pthread__mutex_deferwake(pthread_t self, pthread_mutex_t *ptm)
{
if (__predict_false(ptm == NULL ||
MUTEX_OWNER(ptm->ptm_owner) != (uintptr_t)self)) {
(void)_lwp_unpark_all(self->pt_waiters, self->pt_nwaiters,
__UNVOLATILE(&ptm->ptm_waiters));
self->pt_nwaiters = 0;
} else {
atomic_or_ulong((volatile unsigned long *)
(uintptr_t)&ptm->ptm_owner,
(unsigned long)MUTEX_DEFERRED_BIT);
}
}
int
_pthread_mutex_held_np(pthread_mutex_t *ptm)
{
return MUTEX_OWNER(ptm->ptm_owner) == (uintptr_t)pthread__self();
}
pthread_t
_pthread_mutex_owner_np(pthread_mutex_t *ptm)
{
return (pthread_t)MUTEX_OWNER(ptm->ptm_owner);
}