diff options
Diffstat (limited to 'libc/bionic/pthread.c')
| -rw-r--r-- | libc/bionic/pthread.c | 756 |
1 files changed, 519 insertions, 237 deletions
diff --git a/libc/bionic/pthread.c b/libc/bionic/pthread.c index c075d51..2e2c09d 100644 --- a/libc/bionic/pthread.c +++ b/libc/bionic/pthread.c @@ -52,6 +52,9 @@ #include "pthread_internal.h" #include "thread_private.h" +extern void pthread_debug_mutex_lock_check(pthread_mutex_t *mutex); +extern void pthread_debug_mutex_unlock_check(pthread_mutex_t *mutex); + extern int __pthread_clone(int (*fn)(void*), void *child_stack, int flags, void *arg); extern void _exit_with_stack_teardown(void * stackBase, int stackSize, int retCode); extern void _exit_thread(int retCode); @@ -84,9 +87,6 @@ static const int kPthreadInitFailed = 1; #define PTHREAD_ATTR_FLAG_USER_STACK 0x00000002 #define DEFAULT_STACKSIZE (1024 * 1024) -#define STACKBASE 0x10000000 - -static uint8_t * gStackBase = (uint8_t *)STACKBASE; static pthread_mutex_t mmap_lock = PTHREAD_MUTEX_INITIALIZER; @@ -129,7 +129,7 @@ _pthread_internal_remove( pthread_internal_t* thread ) pthread_mutex_unlock(&gThreadListLock); } -static void +__LIBC_ABI_PRIVATE__ void _pthread_internal_add( pthread_internal_t* thread ) { pthread_mutex_lock(&gThreadListLock); @@ -141,7 +141,7 @@ _pthread_internal_add( pthread_internal_t* thread ) pthread_mutex_unlock(&gThreadListLock); } -pthread_internal_t* +__LIBC_ABI_PRIVATE__ pthread_internal_t* __get_thread(void) { void** tls = (void**)__get_tls(); @@ -202,6 +202,7 @@ void __thread_entry(int (*func)(void*), void *arg, void **tls) pthread_exit((void*) result); } +__LIBC_ABI_PRIVATE__ int _init_thread(pthread_internal_t * thread, pid_t kernel_id, pthread_attr_t * attr, void * stack_base) { int error = 0; @@ -243,7 +244,7 @@ static void *mkstack(size_t size, size_t guard_size) int prot = PROT_READ | PROT_WRITE; int flags = MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE; - void* stack = mmap((void*) gStackBase, size, prot, flags, -1, 0); + void* stack = mmap(NULL, size, prot, flags, -1, 0); if (stack == MAP_FAILED) { stack = NULL; goto done; @@ -691,7 +692,7 @@ FoundIt: goto Exit; } } - while ( __atomic_cmpxchg( flags, flags | PTHREAD_ATTR_FLAG_DETACHED, + while ( __bionic_cmpxchg( flags, flags | PTHREAD_ATTR_FLAG_DETACHED, (volatile int*)&thread->attr.flags ) != 0 ); Exit: pthread_mutex_unlock(&gThreadListLock); @@ -740,12 +741,6 @@ int pthread_setschedparam(pthread_t thid, int policy, } -// mutex lock states -// -// 0: unlocked -// 1: locked, no waiters -// 2: locked, maybe waiters - /* a mutex is implemented as a 32-bit integer holding the following fields * * bits: name description @@ -756,18 +751,146 @@ int pthread_setschedparam(pthread_t thid, int policy, * 1-0 state lock state (0, 1 or 2) */ +/* Convenience macro, creates a mask of 'bits' bits that starts from + * the 'shift'-th least significant bit in a 32-bit word. + * + * Examples: FIELD_MASK(0,4) -> 0xf + * FIELD_MASK(16,9) -> 0x1ff0000 + */ +#define FIELD_MASK(shift,bits) (((1 << (bits))-1) << (shift)) + +/* This one is used to create a bit pattern from a given field value */ +#define FIELD_TO_BITS(val,shift,bits) (((val) & ((1 << (bits))-1)) << (shift)) + +/* And this one does the opposite, i.e. extract a field's value from a bit pattern */ +#define FIELD_FROM_BITS(val,shift,bits) (((val) >> (shift)) & ((1 << (bits))-1)) + +/* Mutex state: + * + * 0 for unlocked + * 1 for locked, no waiters + * 2 for locked, maybe waiters + */ +#define MUTEX_STATE_SHIFT 0 +#define MUTEX_STATE_LEN 2 + +#define MUTEX_STATE_MASK FIELD_MASK(MUTEX_STATE_SHIFT, MUTEX_STATE_LEN) +#define MUTEX_STATE_FROM_BITS(v) FIELD_FROM_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN) +#define MUTEX_STATE_TO_BITS(v) FIELD_TO_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN) + +#define MUTEX_STATE_UNLOCKED 0 /* must be 0 to match __PTHREAD_MUTEX_INIT_VALUE */ +#define MUTEX_STATE_LOCKED_UNCONTENDED 1 /* must be 1 due to atomic dec in unlock operation */ +#define MUTEX_STATE_LOCKED_CONTENDED 2 /* must be 1 + LOCKED_UNCONTENDED due to atomic dec */ + +#define MUTEX_STATE_FROM_BITS(v) FIELD_FROM_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN) +#define MUTEX_STATE_TO_BITS(v) FIELD_TO_BITS(v, MUTEX_STATE_SHIFT, MUTEX_STATE_LEN) + +#define MUTEX_STATE_BITS_UNLOCKED MUTEX_STATE_TO_BITS(MUTEX_STATE_UNLOCKED) +#define MUTEX_STATE_BITS_LOCKED_UNCONTENDED MUTEX_STATE_TO_BITS(MUTEX_STATE_LOCKED_UNCONTENDED) +#define MUTEX_STATE_BITS_LOCKED_CONTENDED MUTEX_STATE_TO_BITS(MUTEX_STATE_LOCKED_CONTENDED) + +/* return true iff the mutex if locked with no waiters */ +#define MUTEX_STATE_BITS_IS_LOCKED_UNCONTENDED(v) (((v) & MUTEX_STATE_MASK) == MUTEX_STATE_BITS_LOCKED_UNCONTENDED) + +/* return true iff the mutex if locked with maybe waiters */ +#define MUTEX_STATE_BITS_IS_LOCKED_CONTENDED(v) (((v) & MUTEX_STATE_MASK) == MUTEX_STATE_BITS_LOCKED_CONTENDED) + +/* used to flip from LOCKED_UNCONTENDED to LOCKED_CONTENDED */ +#define MUTEX_STATE_BITS_FLIP_CONTENTION(v) ((v) ^ (MUTEX_STATE_BITS_LOCKED_CONTENDED ^ MUTEX_STATE_BITS_LOCKED_UNCONTENDED)) + +/* Mutex counter: + * + * We need to check for overflow before incrementing, and we also need to + * detect when the counter is 0 + */ +#define MUTEX_COUNTER_SHIFT 2 +#define MUTEX_COUNTER_LEN 11 +#define MUTEX_COUNTER_MASK FIELD_MASK(MUTEX_COUNTER_SHIFT, MUTEX_COUNTER_LEN) + +#define MUTEX_COUNTER_BITS_WILL_OVERFLOW(v) (((v) & MUTEX_COUNTER_MASK) == MUTEX_COUNTER_MASK) +#define MUTEX_COUNTER_BITS_IS_ZERO(v) (((v) & MUTEX_COUNTER_MASK) == 0) + +/* Used to increment the counter directly after overflow has been checked */ +#define MUTEX_COUNTER_BITS_ONE FIELD_TO_BITS(1,MUTEX_COUNTER_SHIFT,MUTEX_COUNTER_LEN) + +/* Returns true iff the counter is 0 */ +#define MUTEX_COUNTER_BITS_ARE_ZERO(v) (((v) & MUTEX_COUNTER_MASK) == 0) + +/* Mutex shared bit flag + * + * This flag is set to indicate that the mutex is shared among processes. + * This changes the futex opcode we use for futex wait/wake operations + * (non-shared operations are much faster). + */ +#define MUTEX_SHARED_SHIFT 13 +#define MUTEX_SHARED_MASK FIELD_MASK(MUTEX_SHARED_SHIFT,1) + +/* Mutex type: + * + * We support normal, recursive and errorcheck mutexes. + * + * The constants defined here *cannot* be changed because they must match + * the C library ABI which defines the following initialization values in + * <pthread.h>: + * + * __PTHREAD_MUTEX_INIT_VALUE + * __PTHREAD_RECURSIVE_MUTEX_VALUE + * __PTHREAD_ERRORCHECK_MUTEX_INIT_VALUE + */ +#define MUTEX_TYPE_SHIFT 14 +#define MUTEX_TYPE_LEN 2 +#define MUTEX_TYPE_MASK FIELD_MASK(MUTEX_TYPE_SHIFT,MUTEX_TYPE_LEN) + +#define MUTEX_TYPE_NORMAL 0 /* Must be 0 to match __PTHREAD_MUTEX_INIT_VALUE */ +#define MUTEX_TYPE_RECURSIVE 1 +#define MUTEX_TYPE_ERRORCHECK 2 + +#define MUTEX_TYPE_TO_BITS(t) FIELD_TO_BITS(t, MUTEX_TYPE_SHIFT, MUTEX_TYPE_LEN) -#define MUTEX_OWNER(m) (((m)->value >> 16) & 0xffff) -#define MUTEX_COUNTER(m) (((m)->value >> 2) & 0xfff) +#define MUTEX_TYPE_BITS_NORMAL MUTEX_TYPE_TO_BITS(MUTEX_TYPE_NORMAL) +#define MUTEX_TYPE_BITS_RECURSIVE MUTEX_TYPE_TO_BITS(MUTEX_TYPE_RECURSIVE) +#define MUTEX_TYPE_BITS_ERRORCHECK MUTEX_TYPE_TO_BITS(MUTEX_TYPE_ERRORCHECK) + +/* Mutex owner field: + * + * This is only used for recursive and errorcheck mutexes. It holds the + * kernel TID of the owning thread. Note that this works because the Linux + * kernel _only_ uses 16-bit values for thread ids. + * + * More specifically, it will wrap to 10000 when it reaches over 32768 for + * application processes. You can check this by running the following inside + * an adb shell session: + * + OLDPID=$$; + while true; do + NEWPID=$(sh -c 'echo $$') + if [ "$NEWPID" -gt 32768 ]; then + echo "AARGH: new PID $NEWPID is too high!" + exit 1 + fi + if [ "$NEWPID" -lt "$OLDPID" ]; then + echo "****** Wrapping from PID $OLDPID to $NEWPID. *******" + else + echo -n "$NEWPID!" + fi + OLDPID=$NEWPID + done + + * Note that you can run the same example on a desktop Linux system, + * the wrapping will also happen at 32768, but will go back to 300 instead. + */ +#define MUTEX_OWNER_SHIFT 16 +#define MUTEX_OWNER_LEN 16 + +#define MUTEX_OWNER_FROM_BITS(v) FIELD_FROM_BITS(v,MUTEX_OWNER_SHIFT,MUTEX_OWNER_LEN) +#define MUTEX_OWNER_TO_BITS(v) FIELD_TO_BITS(v,MUTEX_OWNER_SHIFT,MUTEX_OWNER_LEN) + +/* Convenience macros. + * + * These are used to form or modify the bit pattern of a given mutex value + */ -#define MUTEX_TYPE_MASK 0xc000 -#define MUTEX_TYPE_NORMAL 0x0000 -#define MUTEX_TYPE_RECURSIVE 0x4000 -#define MUTEX_TYPE_ERRORCHECK 0x8000 -#define MUTEX_COUNTER_SHIFT 2 -#define MUTEX_COUNTER_MASK 0x1ffc -#define MUTEX_SHARED_MASK 0x2000 /* a mutex attribute holds the following fields * @@ -866,7 +989,7 @@ int pthread_mutex_init(pthread_mutex_t *mutex, return EINVAL; if (__likely(attr == NULL)) { - mutex->value = MUTEX_TYPE_NORMAL; + mutex->value = MUTEX_TYPE_BITS_NORMAL; return 0; } @@ -875,13 +998,13 @@ int pthread_mutex_init(pthread_mutex_t *mutex, switch (*attr & MUTEXATTR_TYPE_MASK) { case PTHREAD_MUTEX_NORMAL: - value |= MUTEX_TYPE_NORMAL; + value |= MUTEX_TYPE_BITS_NORMAL; break; case PTHREAD_MUTEX_RECURSIVE: - value |= MUTEX_TYPE_RECURSIVE; + value |= MUTEX_TYPE_BITS_RECURSIVE; break; case PTHREAD_MUTEX_ERRORCHECK: - value |= MUTEX_TYPE_ERRORCHECK; + value |= MUTEX_TYPE_BITS_ERRORCHECK; break; default: return EINVAL; @@ -891,20 +1014,6 @@ int pthread_mutex_init(pthread_mutex_t *mutex, return 0; } -int pthread_mutex_destroy(pthread_mutex_t *mutex) -{ - int ret; - - /* use trylock to ensure that the mutex value is - * valid and is not already locked. */ - ret = pthread_mutex_trylock(mutex); - if (ret != 0) - return ret; - - mutex->value = 0xdead10cc; - return 0; -} - /* * Lock a non-recursive mutex. @@ -919,23 +1028,25 @@ int pthread_mutex_destroy(pthread_mutex_t *mutex) * the lock state field. */ static __inline__ void -_normal_lock(pthread_mutex_t* mutex) +_normal_lock(pthread_mutex_t* mutex, int shared) { - /* We need to preserve the shared flag during operations */ - int shared = mutex->value & MUTEX_SHARED_MASK; + /* convenience shortcuts */ + const int unlocked = shared | MUTEX_STATE_BITS_UNLOCKED; + const int locked_uncontended = shared | MUTEX_STATE_BITS_LOCKED_UNCONTENDED; /* * The common case is an unlocked mutex, so we begin by trying to - * change the lock's state from 0 to 1. __atomic_cmpxchg() returns 0 - * if it made the swap successfully. If the result is nonzero, this - * lock is already held by another thread. + * change the lock's state from 0 (UNLOCKED) to 1 (LOCKED). + * __bionic_cmpxchg() returns 0 if it made the swap successfully. + * If the result is nonzero, this lock is already held by another thread. */ - if (__atomic_cmpxchg(shared|0, shared|1, &mutex->value ) != 0) { + if (__bionic_cmpxchg(unlocked, locked_uncontended, &mutex->value) != 0) { + const int locked_contended = shared | MUTEX_STATE_BITS_LOCKED_CONTENDED; /* * We want to go to sleep until the mutex is available, which - * requires promoting it to state 2. We need to swap in the new - * state value and then wait until somebody wakes us up. + * requires promoting it to state 2 (CONTENDED). We need to + * swap in the new state value and then wait until somebody wakes us up. * - * __atomic_swap() returns the previous value. We swap 2 in and + * __bionic_swap() returns the previous value. We swap 2 in and * see if we got zero back; if so, we have acquired the lock. If * not, another thread still holds the lock and we wait again. * @@ -946,8 +1057,8 @@ _normal_lock(pthread_mutex_t* mutex) * that the mutex is in state 2 when we go to sleep on it, which * guarantees a wake-up call. */ - while (__atomic_swap(shared|2, &mutex->value ) != (shared|0)) - __futex_wait_ex(&mutex->value, shared, shared|2, 0); + while (__bionic_swap(locked_contended, &mutex->value) != unlocked) + __futex_wait_ex(&mutex->value, shared, locked_contended, 0); } ANDROID_MEMBAR_FULL(); } @@ -957,19 +1068,16 @@ _normal_lock(pthread_mutex_t* mutex) * that we are in fact the owner of this lock. */ static __inline__ void -_normal_unlock(pthread_mutex_t* mutex) +_normal_unlock(pthread_mutex_t* mutex, int shared) { ANDROID_MEMBAR_FULL(); - /* We need to preserve the shared flag during operations */ - int shared = mutex->value & MUTEX_SHARED_MASK; - /* * The mutex state will be 1 or (rarely) 2. We use an atomic decrement - * to release the lock. __atomic_dec() returns the previous value; + * to release the lock. __bionic_atomic_dec() returns the previous value; * if it wasn't 1 we have to do some additional work. */ - if (__atomic_dec(&mutex->value) != (shared|1)) { + if (__bionic_atomic_dec(&mutex->value) != (shared|MUTEX_STATE_BITS_LOCKED_UNCONTENDED)) { /* * Start by releasing the lock. The decrement changed it from * "contended lock" to "uncontended lock", which means we still @@ -1011,153 +1119,232 @@ _normal_unlock(pthread_mutex_t* mutex) } } -static pthread_mutex_t __recursive_lock = PTHREAD_MUTEX_INITIALIZER; - -static void -_recursive_lock(void) +/* This common inlined function is used to increment the counter of an + * errorcheck or recursive mutex. + * + * For errorcheck mutexes, it will return EDEADLK + * If the counter overflows, it will return EAGAIN + * Otherwise, it atomically increments the counter and returns 0 + * after providing an acquire barrier. + * + * mtype is the current mutex type + * mvalue is the current mutex value (already loaded) + * mutex pointers to the mutex. + */ +static __inline__ __attribute__((always_inline)) int +_recursive_increment(pthread_mutex_t* mutex, int mvalue, int mtype) { - _normal_lock(&__recursive_lock); -} + if (mtype == MUTEX_TYPE_BITS_ERRORCHECK) { + /* trying to re-lock a mutex we already acquired */ + return EDEADLK; + } -static void -_recursive_unlock(void) -{ - _normal_unlock(&__recursive_lock ); + /* Detect recursive lock overflow and return EAGAIN. + * This is safe because only the owner thread can modify the + * counter bits in the mutex value. + */ + if (MUTEX_COUNTER_BITS_WILL_OVERFLOW(mvalue)) { + return EAGAIN; + } + + /* We own the mutex, but other threads are able to change + * the lower bits (e.g. promoting it to "contended"), so we + * need to use an atomic cmpxchg loop to update the counter. + */ + for (;;) { + /* increment counter, overflow was already checked */ + int newval = mvalue + MUTEX_COUNTER_BITS_ONE; + if (__likely(__bionic_cmpxchg(mvalue, newval, &mutex->value) == 0)) { + /* mutex is still locked, not need for a memory barrier */ + return 0; + } + /* the value was changed, this happens when another thread changes + * the lower state bits from 1 to 2 to indicate contention. This + * cannot change the counter, so simply reload and try again. + */ + mvalue = mutex->value; + } } -int pthread_mutex_lock(pthread_mutex_t *mutex) +__LIBC_HIDDEN__ +int pthread_mutex_lock_impl(pthread_mutex_t *mutex) { - int mtype, tid, new_lock_type, shared; + int mvalue, mtype, tid, new_lock_type, shared; if (__unlikely(mutex == NULL)) return EINVAL; - mtype = (mutex->value & MUTEX_TYPE_MASK); - shared = (mutex->value & MUTEX_SHARED_MASK); + mvalue = mutex->value; + mtype = (mvalue & MUTEX_TYPE_MASK); + shared = (mvalue & MUTEX_SHARED_MASK); /* Handle normal case first */ - if ( __likely(mtype == MUTEX_TYPE_NORMAL) ) { - _normal_lock(mutex); + if ( __likely(mtype == MUTEX_TYPE_BITS_NORMAL) ) { + _normal_lock(mutex, shared); return 0; } /* Do we already own this recursive or error-check mutex ? */ tid = __get_thread()->kernel_id; - if ( tid == MUTEX_OWNER(mutex) ) - { - int oldv, counter; + if ( tid == MUTEX_OWNER_FROM_BITS(mvalue) ) + return _recursive_increment(mutex, mvalue, mtype); + + /* Add in shared state to avoid extra 'or' operations below */ + mtype |= shared; - if (mtype == MUTEX_TYPE_ERRORCHECK) { - /* trying to re-lock a mutex we already acquired */ - return EDEADLK; + /* First, if the mutex is unlocked, try to quickly acquire it. + * In the optimistic case where this works, set the state to 1 to + * indicate locked with no contention */ + if (mvalue == mtype) { + int newval = MUTEX_OWNER_TO_BITS(tid) | mtype | MUTEX_STATE_BITS_LOCKED_UNCONTENDED; + if (__bionic_cmpxchg(mvalue, newval, &mutex->value) == 0) { + ANDROID_MEMBAR_FULL(); + return 0; } - /* - * We own the mutex, but other threads are able to change - * the contents (e.g. promoting it to "contended"), so we - * need to hold the global lock. - */ - _recursive_lock(); - oldv = mutex->value; - counter = (oldv + (1 << MUTEX_COUNTER_SHIFT)) & MUTEX_COUNTER_MASK; - mutex->value = (oldv & ~MUTEX_COUNTER_MASK) | counter; - _recursive_unlock(); - return 0; + /* argh, the value changed, reload before entering the loop */ + mvalue = mutex->value; } - /* We don't own the mutex, so try to get it. - * - * First, we try to change its state from 0 to 1, if this - * doesn't work, try to change it to state 2. - */ - new_lock_type = 1; - - /* compute futex wait opcode and restore shared flag in mtype */ - mtype |= shared; - for (;;) { - int oldv; - - _recursive_lock(); - oldv = mutex->value; - if (oldv == mtype) { /* uncontended released lock => 1 or 2 */ - mutex->value = ((tid << 16) | mtype | new_lock_type); - } else if ((oldv & 3) == 1) { /* locked state 1 => state 2 */ - oldv ^= 3; - mutex->value = oldv; + int newval; + + /* if the mutex is unlocked, its value should be 'mtype' and + * we try to acquire it by setting its owner and state atomically. + * NOTE: We put the state to 2 since we _know_ there is contention + * when we are in this loop. This ensures all waiters will be + * unlocked. + */ + if (mvalue == mtype) { + newval = MUTEX_OWNER_TO_BITS(tid) | mtype | MUTEX_STATE_BITS_LOCKED_CONTENDED; + /* TODO: Change this to __bionic_cmpxchg_acquire when we + * implement it to get rid of the explicit memory + * barrier below. + */ + if (__unlikely(__bionic_cmpxchg(mvalue, newval, &mutex->value) != 0)) { + mvalue = mutex->value; + continue; + } + ANDROID_MEMBAR_FULL(); + return 0; } - _recursive_unlock(); - if (oldv == mtype) - break; + /* the mutex is already locked by another thread, if its state is 1 + * we will change it to 2 to indicate contention. */ + if (MUTEX_STATE_BITS_IS_LOCKED_UNCONTENDED(mvalue)) { + newval = MUTEX_STATE_BITS_FLIP_CONTENTION(mvalue); /* locked state 1 => state 2 */ + if (__unlikely(__bionic_cmpxchg(mvalue, newval, &mutex->value) != 0)) { + mvalue = mutex->value; + continue; + } + mvalue = newval; + } - /* - * The lock was held, possibly contended by others. From - * now on, if we manage to acquire the lock, we have to - * assume that others are still contending for it so that - * we'll wake them when we unlock it. - */ - new_lock_type = 2; + /* wait until the mutex is unlocked */ + __futex_wait_ex(&mutex->value, shared, mvalue, NULL); - __futex_wait_ex(&mutex->value, shared, oldv, NULL); + mvalue = mutex->value; } - return 0; + /* NOTREACHED */ } +int pthread_mutex_lock(pthread_mutex_t *mutex) +{ + int err = pthread_mutex_lock_impl(mutex); +#ifdef PTHREAD_DEBUG + if (PTHREAD_DEBUG_ENABLED) { + if (!err) { + pthread_debug_mutex_lock_check(mutex); + } + } +#endif + return err; +} -int pthread_mutex_unlock(pthread_mutex_t *mutex) +__LIBC_HIDDEN__ +int pthread_mutex_unlock_impl(pthread_mutex_t *mutex) { - int mtype, tid, oldv, shared; + int mvalue, mtype, tid, oldv, shared; if (__unlikely(mutex == NULL)) return EINVAL; - mtype = (mutex->value & MUTEX_TYPE_MASK); - shared = (mutex->value & MUTEX_SHARED_MASK); + mvalue = mutex->value; + mtype = (mvalue & MUTEX_TYPE_MASK); + shared = (mvalue & MUTEX_SHARED_MASK); /* Handle common case first */ - if (__likely(mtype == MUTEX_TYPE_NORMAL)) { - _normal_unlock(mutex); + if (__likely(mtype == MUTEX_TYPE_BITS_NORMAL)) { + _normal_unlock(mutex, shared); return 0; } /* Do we already own this recursive or error-check mutex ? */ tid = __get_thread()->kernel_id; - if ( tid != MUTEX_OWNER(mutex) ) + if ( tid != MUTEX_OWNER_FROM_BITS(mvalue) ) return EPERM; - /* We do, decrement counter or release the mutex if it is 0 */ - _recursive_lock(); - oldv = mutex->value; - if (oldv & MUTEX_COUNTER_MASK) { - mutex->value = oldv - (1 << MUTEX_COUNTER_SHIFT); - oldv = 0; - } else { - mutex->value = shared | mtype; + /* If the counter is > 0, we can simply decrement it atomically. + * Since other threads can mutate the lower state bits (and only the + * lower state bits), use a cmpxchg to do it. + */ + if (!MUTEX_COUNTER_BITS_IS_ZERO(mvalue)) { + for (;;) { + int newval = mvalue - MUTEX_COUNTER_BITS_ONE; + if (__likely(__bionic_cmpxchg(mvalue, newval, &mutex->value) == 0)) { + /* success: we still own the mutex, so no memory barrier */ + return 0; + } + /* the value changed, so reload and loop */ + mvalue = mutex->value; + } } - _recursive_unlock(); + + /* the counter is 0, so we're going to unlock the mutex by resetting + * its value to 'unlocked'. We need to perform a swap in order + * to read the current state, which will be 2 if there are waiters + * to awake. + * + * TODO: Change this to __bionic_swap_release when we implement it + * to get rid of the explicit memory barrier below. + */ + ANDROID_MEMBAR_FULL(); /* RELEASE BARRIER */ + mvalue = __bionic_swap(mtype | shared | MUTEX_STATE_BITS_UNLOCKED, &mutex->value); /* Wake one waiting thread, if any */ - if ((oldv & 3) == 2) { + if (MUTEX_STATE_BITS_IS_LOCKED_CONTENDED(mvalue)) { __futex_wake_ex(&mutex->value, shared, 1); } return 0; } +int pthread_mutex_unlock(pthread_mutex_t *mutex) +{ +#ifdef PTHREAD_DEBUG + if (PTHREAD_DEBUG_ENABLED) { + pthread_debug_mutex_unlock_check(mutex); + } +#endif + return pthread_mutex_unlock_impl(mutex); +} -int pthread_mutex_trylock(pthread_mutex_t *mutex) +__LIBC_HIDDEN__ +int pthread_mutex_trylock_impl(pthread_mutex_t *mutex) { - int mtype, tid, oldv, shared; + int mvalue, mtype, tid, oldv, shared; if (__unlikely(mutex == NULL)) return EINVAL; - mtype = (mutex->value & MUTEX_TYPE_MASK); - shared = (mutex->value & MUTEX_SHARED_MASK); + mvalue = mutex->value; + mtype = (mvalue & MUTEX_TYPE_MASK); + shared = (mvalue & MUTEX_SHARED_MASK); /* Handle common case first */ - if ( __likely(mtype == MUTEX_TYPE_NORMAL) ) + if ( __likely(mtype == MUTEX_TYPE_BITS_NORMAL) ) { - if (__atomic_cmpxchg(shared|0, shared|1, &mutex->value) == 0) { + if (__bionic_cmpxchg(shared|MUTEX_STATE_BITS_UNLOCKED, + shared|MUTEX_STATE_BITS_LOCKED_UNCONTENDED, + &mutex->value) == 0) { ANDROID_MEMBAR_FULL(); return 0; } @@ -1167,39 +1354,36 @@ int pthread_mutex_trylock(pthread_mutex_t *mutex) /* Do we already own this recursive or error-check mutex ? */ tid = __get_thread()->kernel_id; - if ( tid == MUTEX_OWNER(mutex) ) - { - int counter; + if ( tid == MUTEX_OWNER_FROM_BITS(mvalue) ) + return _recursive_increment(mutex, mvalue, mtype); - if (mtype == MUTEX_TYPE_ERRORCHECK) { - /* already locked by ourselves */ - return EDEADLK; - } + /* Same as pthread_mutex_lock, except that we don't want to wait, and + * the only operation that can succeed is a single cmpxchg to acquire the + * lock if it is released / not owned by anyone. No need for a complex loop. + */ + mtype |= shared | MUTEX_STATE_BITS_UNLOCKED; + mvalue = MUTEX_OWNER_TO_BITS(tid) | mtype | MUTEX_STATE_BITS_LOCKED_UNCONTENDED; - _recursive_lock(); - oldv = mutex->value; - counter = (oldv + (1 << MUTEX_COUNTER_SHIFT)) & MUTEX_COUNTER_MASK; - mutex->value = (oldv & ~MUTEX_COUNTER_MASK) | counter; - _recursive_unlock(); + if (__likely(__bionic_cmpxchg(mtype, mvalue, &mutex->value) == 0)) { + ANDROID_MEMBAR_FULL(); return 0; } - /* Restore sharing bit in mtype */ - mtype |= shared; - - /* Try to lock it, just once. */ - _recursive_lock(); - oldv = mutex->value; - if (oldv == mtype) /* uncontended released lock => state 1 */ - mutex->value = ((tid << 16) | mtype | 1); - _recursive_unlock(); - - if (oldv != mtype) - return EBUSY; - - return 0; + return EBUSY; } +int pthread_mutex_trylock(pthread_mutex_t *mutex) +{ + int err = pthread_mutex_trylock_impl(mutex); +#ifdef PTHREAD_DEBUG + if (PTHREAD_DEBUG_ENABLED) { + if (!err) { + pthread_debug_mutex_lock_check(mutex); + } + } +#endif + return err; +} /* initialize 'ts' with the difference between 'abstime' and the current time * according to 'clock'. Returns -1 if abstime already expired, or 0 otherwise. @@ -1235,12 +1419,13 @@ __timespec_to_relative_msec(struct timespec* abstime, unsigned msecs, clockid_ } } -int pthread_mutex_lock_timeout_np(pthread_mutex_t *mutex, unsigned msecs) +__LIBC_HIDDEN__ +int pthread_mutex_lock_timeout_np_impl(pthread_mutex_t *mutex, unsigned msecs) { clockid_t clock = CLOCK_MONOTONIC; struct timespec abstime; struct timespec ts; - int mtype, tid, oldv, new_lock_type, shared; + int mvalue, mtype, tid, oldv, new_lock_type, shared; /* compute absolute expiration time */ __timespec_to_relative_msec(&abstime, msecs, clock); @@ -1248,24 +1433,29 @@ int pthread_mutex_lock_timeout_np(pthread_mutex_t *mutex, unsigned msecs) if (__unlikely(mutex == NULL)) return EINVAL; - mtype = (mutex->value & MUTEX_TYPE_MASK); - shared = (mutex->value & MUTEX_SHARED_MASK); + mvalue = mutex->value; + mtype = (mvalue & MUTEX_TYPE_MASK); + shared = (mvalue & MUTEX_SHARED_MASK); /* Handle common case first */ - if ( __likely(mtype == MUTEX_TYPE_NORMAL) ) + if ( __likely(mtype == MUTEX_TYPE_BITS_NORMAL) ) { - /* fast path for uncontended lock */ - if (__atomic_cmpxchg(shared|0, shared|1, &mutex->value) == 0) { + const int unlocked = shared | MUTEX_STATE_BITS_UNLOCKED; + const int locked_uncontended = shared | MUTEX_STATE_BITS_LOCKED_UNCONTENDED; + const int locked_contended = shared | MUTEX_STATE_BITS_LOCKED_CONTENDED; + + /* fast path for uncontended lock. Note: MUTEX_TYPE_BITS_NORMAL is 0 */ + if (__bionic_cmpxchg(unlocked, locked_uncontended, &mutex->value) == 0) { ANDROID_MEMBAR_FULL(); return 0; } /* loop while needed */ - while (__atomic_swap(shared|2, &mutex->value) != (shared|0)) { + while (__bionic_swap(locked_contended, &mutex->value) != unlocked) { if (__timespec_to_absolute(&ts, &abstime, clock) < 0) return EBUSY; - __futex_wait_ex(&mutex->value, shared, shared|2, &ts); + __futex_wait_ex(&mutex->value, shared, locked_contended, &ts); } ANDROID_MEMBAR_FULL(); return 0; @@ -1273,66 +1463,106 @@ int pthread_mutex_lock_timeout_np(pthread_mutex_t *mutex, unsigned msecs) /* Do we already own this recursive or error-check mutex ? */ tid = __get_thread()->kernel_id; - if ( tid == MUTEX_OWNER(mutex) ) - { - int oldv, counter; - - if (mtype == MUTEX_TYPE_ERRORCHECK) { - /* already locked by ourselves */ - return EDEADLK; - } + if ( tid == MUTEX_OWNER_FROM_BITS(mvalue) ) + return _recursive_increment(mutex, mvalue, mtype); - _recursive_lock(); - oldv = mutex->value; - counter = (oldv + (1 << MUTEX_COUNTER_SHIFT)) & MUTEX_COUNTER_MASK; - mutex->value = (oldv & ~MUTEX_COUNTER_MASK) | counter; - _recursive_unlock(); - return 0; - } - - /* We don't own the mutex, so try to get it. - * - * First, we try to change its state from 0 to 1, if this - * doesn't work, try to change it to state 2. + /* the following implements the same loop than pthread_mutex_lock_impl + * but adds checks to ensure that the operation never exceeds the + * absolute expiration time. */ - new_lock_type = 1; + mtype |= shared; - /* Compute wait op and restore sharing bit in mtype */ - mtype |= shared; + /* first try a quick lock */ + if (mvalue == mtype) { + mvalue = MUTEX_OWNER_TO_BITS(tid) | mtype | MUTEX_STATE_BITS_LOCKED_UNCONTENDED; + if (__likely(__bionic_cmpxchg(mtype, mvalue, &mutex->value) == 0)) { + ANDROID_MEMBAR_FULL(); + return 0; + } + mvalue = mutex->value; + } for (;;) { - int oldv; - struct timespec ts; - - _recursive_lock(); - oldv = mutex->value; - if (oldv == mtype) { /* uncontended released lock => 1 or 2 */ - mutex->value = ((tid << 16) | mtype | new_lock_type); - } else if ((oldv & 3) == 1) { /* locked state 1 => state 2 */ - oldv ^= 3; - mutex->value = oldv; - } - _recursive_unlock(); + struct timespec ts; + + /* if the value is 'unlocked', try to acquire it directly */ + /* NOTE: put state to 2 since we know there is contention */ + if (mvalue == mtype) /* unlocked */ { + mvalue = MUTEX_OWNER_TO_BITS(tid) | mtype | MUTEX_STATE_BITS_LOCKED_CONTENDED; + if (__bionic_cmpxchg(mtype, mvalue, &mutex->value) == 0) { + ANDROID_MEMBAR_FULL(); + return 0; + } + /* the value changed before we could lock it. We need to check + * the time to avoid livelocks, reload the value, then loop again. */ + if (__timespec_to_absolute(&ts, &abstime, clock) < 0) + return EBUSY; - if (oldv == mtype) - break; + mvalue = mutex->value; + continue; + } - /* - * The lock was held, possibly contended by others. From - * now on, if we manage to acquire the lock, we have to - * assume that others are still contending for it so that - * we'll wake them when we unlock it. - */ - new_lock_type = 2; + /* The value is locked. If 'uncontended', try to switch its state + * to 'contented' to ensure we get woken up later. */ + if (MUTEX_STATE_BITS_IS_LOCKED_UNCONTENDED(mvalue)) { + int newval = MUTEX_STATE_BITS_FLIP_CONTENTION(mvalue); + if (__bionic_cmpxchg(mvalue, newval, &mutex->value) != 0) { + /* this failed because the value changed, reload it */ + mvalue = mutex->value; + } else { + /* this succeeded, update mvalue */ + mvalue = newval; + } + } + /* check time and update 'ts' */ if (__timespec_to_absolute(&ts, &abstime, clock) < 0) return EBUSY; - __futex_wait_ex(&mutex->value, shared, oldv, &ts); + /* Only wait to be woken up if the state is '2', otherwise we'll + * simply loop right now. This can happen when the second cmpxchg + * in our loop failed because the mutex was unlocked by another + * thread. + */ + if (MUTEX_STATE_BITS_IS_LOCKED_CONTENDED(mvalue)) { + if (__futex_wait_ex(&mutex->value, shared, mvalue, &ts) == ETIMEDOUT) { + return EBUSY; + } + mvalue = mutex->value; + } + } + /* NOTREACHED */ +} + +int pthread_mutex_lock_timeout_np(pthread_mutex_t *mutex, unsigned msecs) +{ + int err = pthread_mutex_lock_timeout_np_impl(mutex, msecs); +#ifdef PTHREAD_DEBUG + if (PTHREAD_DEBUG_ENABLED) { + if (!err) { + pthread_debug_mutex_lock_check(mutex); + } } +#endif + return err; +} + +int pthread_mutex_destroy(pthread_mutex_t *mutex) +{ + int ret; + + /* use trylock to ensure that the mutex value is + * valid and is not already locked. */ + ret = pthread_mutex_trylock_impl(mutex); + if (ret != 0) + return ret; + + mutex->value = 0xdead10cc; return 0; } + + int pthread_condattr_init(pthread_condattr_t *attr) { if (attr == NULL) @@ -1430,7 +1660,7 @@ __pthread_cond_pulse(pthread_cond_t *cond, int counter) long oldval = cond->value; long newval = ((oldval - COND_COUNTER_INCREMENT) & COND_COUNTER_MASK) | flags; - if (__atomic_cmpxchg(oldval, newval, &cond->value) == 0) + if (__bionic_cmpxchg(oldval, newval, &cond->value) == 0) break; } @@ -1840,7 +2070,7 @@ static void pthread_key_clean_all(void) } // man says this should be in <linux/unistd.h>, but it isn't -extern int tkill(int tid, int sig); +extern int tgkill(int tgid, int tid, int sig); int pthread_kill(pthread_t tid, int sig) { @@ -1848,7 +2078,7 @@ int pthread_kill(pthread_t tid, int sig) int old_errno = errno; pthread_internal_t * thread = (pthread_internal_t *)tid; - ret = tkill(thread->kernel_id, sig); + ret = tgkill(getpid(), thread->kernel_id, sig); if (ret < 0) { ret = errno; errno = old_errno; @@ -1890,7 +2120,7 @@ int pthread_sigmask(int how, const sigset_t *set, sigset_t *oset) /* 'in_set_ptr' is the second parameter to __rt_sigprocmask. It must be NULL * if 'set' is NULL to ensure correct semantics (which in this case would * be to ignore 'how' and return the current signal set into 'oset'. - */ + */ if (set == NULL) { in_set_ptr = NULL; } else { @@ -1930,18 +2160,70 @@ int pthread_once( pthread_once_t* once_control, void (*init_routine)(void) ) { static pthread_mutex_t once_lock = PTHREAD_RECURSIVE_MUTEX_INITIALIZER; volatile pthread_once_t* ocptr = once_control; + pthread_once_t value; - pthread_once_t tmp = *ocptr; - ANDROID_MEMBAR_FULL(); - if (tmp == PTHREAD_ONCE_INIT) { - pthread_mutex_lock( &once_lock ); - if (*ocptr == PTHREAD_ONCE_INIT) { - (*init_routine)(); + /* PTHREAD_ONCE_INIT is 0, we use the following bit flags + * + * bit 0 set -> initialization is under way + * bit 1 set -> initialization is complete + */ +#define ONCE_INITIALIZING (1 << 0) +#define ONCE_COMPLETED (1 << 1) + + /* First check if the once is already initialized. This will be the common + * case and we want to make this as fast as possible. Note that this still + * requires a load_acquire operation here to ensure that all the + * stores performed by the initialization function are observable on + * this CPU after we exit. + */ + if (__likely((*ocptr & ONCE_COMPLETED) != 0)) { + ANDROID_MEMBAR_FULL(); + return 0; + } + + for (;;) { + /* Try to atomically set the INITIALIZING flag. + * This requires a cmpxchg loop, and we may need + * to exit prematurely if we detect that + * COMPLETED is now set. + */ + int32_t oldval, newval; + + do { + oldval = *ocptr; + if ((oldval & ONCE_COMPLETED) != 0) + break; + + newval = oldval | ONCE_INITIALIZING; + } while (__bionic_cmpxchg(oldval, newval, ocptr) != 0); + + if ((oldval & ONCE_COMPLETED) != 0) { + /* We detected that COMPLETED was set while in our loop */ ANDROID_MEMBAR_FULL(); - *ocptr = ~PTHREAD_ONCE_INIT; + return 0; + } + + if ((oldval & ONCE_INITIALIZING) == 0) { + /* We got there first, we can jump out of the loop to + * handle the initialization */ + break; } - pthread_mutex_unlock( &once_lock ); + + /* Another thread is running the initialization and hasn't completed + * yet, so wait for it, then try again. */ + __futex_wait_ex(ocptr, 0, oldval, NULL); } + + /* call the initialization function. */ + (*init_routine)(); + + /* Do a store_release indicating that initialization is complete */ + ANDROID_MEMBAR_FULL(); + *ocptr = ONCE_COMPLETED; + + /* Wake up any waiters, if any */ + __futex_wake_ex(ocptr, 0, INT_MAX); + return 0; } |