/*
* Copyright (C) 2010 The Android Open Source Project
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * 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 COPYRIGHT HOLDERS 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
* COPYRIGHT OWNER 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.
*/
#include <errno.h>
#include <stdatomic.h>
#include <string.h>
#include "pthread_internal.h"
#include "private/bionic_futex.h"
#include "private/bionic_lock.h"
#include "private/bionic_time_conversions.h"
/* Technical note:
*
* Possible states of a read/write lock:
*
* - no readers and no writer (unlocked)
* - one or more readers sharing the lock at the same time (read-locked)
* - one writer holding the lock (write-lock)
*
* Additionally:
* - trying to get the write-lock while there are any readers blocks
* - trying to get the read-lock while there is a writer blocks
* - a single thread can acquire the lock multiple times in read mode
*
* - Posix states that behavior is undefined (may deadlock) if a thread tries
* to acquire the lock
* - in write mode while already holding the lock (whether in read or write mode)
* - in read mode while already holding the lock in write mode.
* - This implementation will return EDEADLK in "write after write" and "read after
* write" cases and will deadlock in write after read case.
*
*/
// A rwlockattr is implemented as a 32-bit integer which has following fields:
// bits name description
// 1 rwlock_kind have rwlock preference like PTHREAD_RWLOCK_PREFER_READER_NP.
// 0 process_shared set to 1 if the rwlock is shared between processes.
#define RWLOCKATTR_PSHARED_SHIFT 0
#define RWLOCKATTR_KIND_SHIFT 1
#define RWLOCKATTR_PSHARED_MASK 1
#define RWLOCKATTR_KIND_MASK 2
#define RWLOCKATTR_RESERVED_MASK (~3)
static inline __always_inline __always_inline bool __rwlockattr_getpshared(const pthread_rwlockattr_t* attr) {
return (*attr & RWLOCKATTR_PSHARED_MASK) >> RWLOCKATTR_PSHARED_SHIFT;
}
static inline __always_inline __always_inline void __rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) {
*attr = (*attr & ~RWLOCKATTR_PSHARED_MASK) | (pshared << RWLOCKATTR_PSHARED_SHIFT);
}
static inline __always_inline int __rwlockattr_getkind(const pthread_rwlockattr_t* attr) {
return (*attr & RWLOCKATTR_KIND_MASK) >> RWLOCKATTR_KIND_SHIFT;
}
static inline __always_inline void __rwlockattr_setkind(pthread_rwlockattr_t* attr, int kind) {
*attr = (*attr & ~RWLOCKATTR_KIND_MASK) | (kind << RWLOCKATTR_KIND_SHIFT);
}
int pthread_rwlockattr_init(pthread_rwlockattr_t* attr) {
*attr = 0;
return 0;
}
int pthread_rwlockattr_destroy(pthread_rwlockattr_t* attr) {
*attr = -1;
return 0;
}
int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) {
if (__rwlockattr_getpshared(attr)) {
*pshared = PTHREAD_PROCESS_SHARED;
} else {
*pshared = PTHREAD_PROCESS_PRIVATE;
}
return 0;
}
int pthread_rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) {
switch (pshared) {
case PTHREAD_PROCESS_PRIVATE:
__rwlockattr_setpshared(attr, 0);
return 0;
case PTHREAD_PROCESS_SHARED:
__rwlockattr_setpshared(attr, 1);
return 0;
default:
return EINVAL;
}
}
int pthread_rwlockattr_getkind_np(const pthread_rwlockattr_t* attr, int* pref) {
*pref = __rwlockattr_getkind(attr);
return 0;
}
int pthread_rwlockattr_setkind_np(pthread_rwlockattr_t* attr, int pref) {
switch (pref) {
case PTHREAD_RWLOCK_PREFER_READER_NP: // Fall through.
case PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP:
__rwlockattr_setkind(attr, pref);
return 0;
default:
return EINVAL;
}
}
// A rwlock state is implemented as a 32-bit integer which has following rules:
// bits name description
// 31 owned_by_writer_flag set to 1 if the lock is owned by a writer now.
// 30-2 reader_count the count of readers holding the lock.
// 1 have_pending_writers set to 1 if having pending writers.
// 0 have_pending_readers set to 1 if having pending readers.
#define STATE_HAVE_PENDING_READERS_SHIFT 0
#define STATE_HAVE_PENDING_WRITERS_SHIFT 1
#define STATE_READER_COUNT_SHIFT 2
#define STATE_OWNED_BY_WRITER_SHIFT 31
#define STATE_HAVE_PENDING_READERS_FLAG (1 << STATE_HAVE_PENDING_READERS_SHIFT)
#define STATE_HAVE_PENDING_WRITERS_FLAG (1 << STATE_HAVE_PENDING_WRITERS_SHIFT)
#define STATE_READER_COUNT_CHANGE_STEP (1 << STATE_READER_COUNT_SHIFT)
#define STATE_OWNED_BY_WRITER_FLAG (1 << STATE_OWNED_BY_WRITER_SHIFT)
#define STATE_HAVE_PENDING_READERS_OR_WRITERS_FLAG \
(STATE_HAVE_PENDING_READERS_FLAG | STATE_HAVE_PENDING_WRITERS_FLAG)
struct pthread_rwlock_internal_t {
atomic_int state;
atomic_int writer_tid;
bool pshared;
bool writer_nonrecursive_preferred;
uint16_t __pad;
// When a reader thread plans to suspend on the rwlock, it will add STATE_HAVE_PENDING_READERS_FLAG
// in state, increase pending_reader_count, and wait on pending_reader_wakeup_serial. After woken
// up, the reader thread decreases pending_reader_count, and the last pending reader thread should
// remove STATE_HAVE_PENDING_READERS_FLAG in state. A pending writer thread works in a similar way,
// except that it uses flag and members for writer threads.
Lock pending_lock; // All pending members below are protected by pending_lock.
uint32_t pending_reader_count; // Count of pending reader threads.
uint32_t pending_writer_count; // Count of pending writer threads.
uint32_t pending_reader_wakeup_serial; // Pending reader threads wait on this address by futex_wait.
uint32_t pending_writer_wakeup_serial; // Pending writer threads wait on this address by futex_wait.
#if defined(__LP64__)
char __reserved[20];
#else
char __reserved[4];
#endif
};
static inline __always_inline bool __state_owned_by_writer(int state) {
return state < 0;
}
static inline __always_inline bool __state_owned_by_readers(int state) {
// If state >= 0, the owned_by_writer_flag is not set.
// And if state >= STATE_READER_COUNT_CHANGE_STEP, the reader_count field is not empty.
return state >= STATE_READER_COUNT_CHANGE_STEP;
}
static inline __always_inline bool __state_owned_by_readers_or_writer(int state) {
return state < 0 || state >= STATE_READER_COUNT_CHANGE_STEP;
}
static inline __always_inline int __state_add_writer_flag(int state) {
return state | STATE_OWNED_BY_WRITER_FLAG;
}
static inline __always_inline bool __state_is_last_reader(int state) {
return (state >> STATE_READER_COUNT_SHIFT) == 1;
}
static inline __always_inline bool __state_have_pending_writers(int state) {
return state & STATE_HAVE_PENDING_WRITERS_FLAG;
}
static inline __always_inline bool __state_have_pending_readers_or_writers(int state) {
return state & STATE_HAVE_PENDING_READERS_OR_WRITERS_FLAG;
}
static_assert(sizeof(pthread_rwlock_t) == sizeof(pthread_rwlock_internal_t),
"pthread_rwlock_t should actually be pthread_rwlock_internal_t in implementation.");
// For binary compatibility with old version of pthread_rwlock_t, we can't use more strict
// alignment than 4-byte alignment.
static_assert(alignof(pthread_rwlock_t) == 4,
"pthread_rwlock_t should fulfill the alignment requirement of pthread_rwlock_internal_t.");
static inline __always_inline pthread_rwlock_internal_t* __get_internal_rwlock(pthread_rwlock_t* rwlock_interface) {
return reinterpret_cast<pthread_rwlock_internal_t*>(rwlock_interface);
}
int pthread_rwlock_init(pthread_rwlock_t* rwlock_interface, const pthread_rwlockattr_t* attr) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
memset(rwlock, 0, sizeof(pthread_rwlock_internal_t));
if (__predict_false(attr != NULL)) {
rwlock->pshared = __rwlockattr_getpshared(attr);
int kind = __rwlockattr_getkind(attr);
switch (kind) {
case PTHREAD_RWLOCK_PREFER_READER_NP:
rwlock->writer_nonrecursive_preferred = false;
break;
case PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP:
rwlock->writer_nonrecursive_preferred = true;
break;
default:
return EINVAL;
}
if ((*attr & RWLOCKATTR_RESERVED_MASK) != 0) {
return EINVAL;
}
}
atomic_init(&rwlock->state, 0);
rwlock->pending_lock.init(rwlock->pshared);
return 0;
}
int pthread_rwlock_destroy(pthread_rwlock_t* rwlock_interface) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
if (atomic_load_explicit(&rwlock->state, memory_order_relaxed) != 0) {
return EBUSY;
}
return 0;
}
static inline __always_inline bool __can_acquire_read_lock(int old_state,
bool writer_nonrecursive_preferred) {
// If writer is preferred with nonrecursive reader, we prevent further readers from acquiring
// the lock when there are writers waiting for the lock.
bool cannot_apply = __state_owned_by_writer(old_state) ||
(writer_nonrecursive_preferred && __state_have_pending_writers(old_state));
return !cannot_apply;
}
static inline __always_inline int __pthread_rwlock_tryrdlock(pthread_rwlock_internal_t* rwlock) {
int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
while (__predict_true(__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred))) {
int new_state = old_state + STATE_READER_COUNT_CHANGE_STEP;
if (__predict_false(!__state_owned_by_readers(new_state))) { // Happens when reader count overflows.
return EAGAIN;
}
if (__predict_true(atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, new_state,
memory_order_acquire, memory_order_relaxed))) {
return 0;
}
}
return EBUSY;
}
static int __pthread_rwlock_timedrdlock(pthread_rwlock_internal_t* rwlock,
const timespec* abs_timeout_or_null) {
if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) == __get_thread()->tid) {
return EDEADLK;
}
while (true) {
int result = __pthread_rwlock_tryrdlock(rwlock);
if (result == 0 || result == EAGAIN) {
return result;
}
result = check_timespec(abs_timeout_or_null, true);
if (result != 0) {
return result;
}
int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
if (__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred)) {
continue;
}
rwlock->pending_lock.lock();
rwlock->pending_reader_count++;
// We rely on the fact that all atomic exchange operations on the same object (here it is
// rwlock->state) always appear to occur in a single total order. If the pending flag is added
// before unlocking, the unlocking thread will wakeup the waiter. Otherwise, we will see the
// state is unlocked and will not wait anymore.
old_state = atomic_fetch_or_explicit(&rwlock->state, STATE_HAVE_PENDING_READERS_FLAG,
memory_order_relaxed);
int old_serial = rwlock->pending_reader_wakeup_serial;
rwlock->pending_lock.unlock();
int futex_result = 0;
if (!__can_acquire_read_lock(old_state, rwlock->writer_nonrecursive_preferred)) {
futex_result = __futex_wait_ex(&rwlock->pending_reader_wakeup_serial, rwlock->pshared,
old_serial, true, abs_timeout_or_null);
}
rwlock->pending_lock.lock();
rwlock->pending_reader_count--;
if (rwlock->pending_reader_count == 0) {
atomic_fetch_and_explicit(&rwlock->state, ~STATE_HAVE_PENDING_READERS_FLAG,
memory_order_relaxed);
}
rwlock->pending_lock.unlock();
if (futex_result == -ETIMEDOUT) {
return ETIMEDOUT;
}
}
}
static inline __always_inline bool __can_acquire_write_lock(int old_state) {
return !__state_owned_by_readers_or_writer(old_state);
}
static inline __always_inline int __pthread_rwlock_trywrlock(pthread_rwlock_internal_t* rwlock) {
int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
while (__predict_true(__can_acquire_write_lock(old_state))) {
if (__predict_true(atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state,
__state_add_writer_flag(old_state), memory_order_acquire, memory_order_relaxed))) {
atomic_store_explicit(&rwlock->writer_tid, __get_thread()->tid, memory_order_relaxed);
return 0;
}
}
return EBUSY;
}
static int __pthread_rwlock_timedwrlock(pthread_rwlock_internal_t* rwlock,
const timespec* abs_timeout_or_null) {
if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) == __get_thread()->tid) {
return EDEADLK;
}
while (true) {
int result = __pthread_rwlock_trywrlock(rwlock);
if (result == 0) {
return result;
}
result = check_timespec(abs_timeout_or_null, true);
if (result != 0) {
return result;
}
int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
if (__can_acquire_write_lock(old_state)) {
continue;
}
rwlock->pending_lock.lock();
rwlock->pending_writer_count++;
old_state = atomic_fetch_or_explicit(&rwlock->state, STATE_HAVE_PENDING_WRITERS_FLAG,
memory_order_relaxed);
int old_serial = rwlock->pending_writer_wakeup_serial;
rwlock->pending_lock.unlock();
int futex_result = 0;
if (!__can_acquire_write_lock(old_state)) {
futex_result = __futex_wait_ex(&rwlock->pending_writer_wakeup_serial, rwlock->pshared,
old_serial, true, abs_timeout_or_null);
}
rwlock->pending_lock.lock();
rwlock->pending_writer_count--;
if (rwlock->pending_writer_count == 0) {
atomic_fetch_and_explicit(&rwlock->state, ~STATE_HAVE_PENDING_WRITERS_FLAG,
memory_order_relaxed);
}
rwlock->pending_lock.unlock();
if (futex_result == -ETIMEDOUT) {
return ETIMEDOUT;
}
}
}
int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock_interface) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
// Avoid slowing down fast path of rdlock.
if (__predict_true(__pthread_rwlock_tryrdlock(rwlock) == 0)) {
return 0;
}
return __pthread_rwlock_timedrdlock(rwlock, nullptr);
}
int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
return __pthread_rwlock_timedrdlock(rwlock, abs_timeout);
}
int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock_interface) {
return __pthread_rwlock_tryrdlock(__get_internal_rwlock(rwlock_interface));
}
int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock_interface) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
// Avoid slowing down fast path of wrlock.
if (__predict_true(__pthread_rwlock_trywrlock(rwlock) == 0)) {
return 0;
}
return __pthread_rwlock_timedwrlock(rwlock, nullptr);
}
int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
return __pthread_rwlock_timedwrlock(rwlock, abs_timeout);
}
int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock_interface) {
return __pthread_rwlock_trywrlock(__get_internal_rwlock(rwlock_interface));
}
int pthread_rwlock_unlock(pthread_rwlock_t* rwlock_interface) {
pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface);
int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed);
if (__state_owned_by_writer(old_state)) {
if (atomic_load_explicit(&rwlock->writer_tid, memory_order_relaxed) != __get_thread()->tid) {
return EPERM;
}
atomic_store_explicit(&rwlock->writer_tid, 0, memory_order_relaxed);
old_state = atomic_fetch_and_explicit(&rwlock->state, ~STATE_OWNED_BY_WRITER_FLAG,
memory_order_release);
if (!__state_have_pending_readers_or_writers(old_state)) {
return 0;
}
} else if (__state_owned_by_readers(old_state)) {
old_state = atomic_fetch_sub_explicit(&rwlock->state, STATE_READER_COUNT_CHANGE_STEP,
memory_order_release);
if (!__state_is_last_reader(old_state) || !__state_have_pending_readers_or_writers(old_state)) {
return 0;
}
} else {
return EPERM;
}
// Wake up pending readers or writers.
rwlock->pending_lock.lock();
if (rwlock->pending_writer_count != 0) {
rwlock->pending_writer_wakeup_serial++;
rwlock->pending_lock.unlock();
__futex_wake_ex(&rwlock->pending_writer_wakeup_serial, rwlock->pshared, 1);
} else if (rwlock->pending_reader_count != 0) {
rwlock->pending_reader_wakeup_serial++;
rwlock->pending_lock.unlock();
__futex_wake_ex(&rwlock->pending_reader_wakeup_serial, rwlock->pshared, INT_MAX);
} else {
// It happens when waiters are woken up by timeout.
rwlock->pending_lock.unlock();
}
return 0;
}