/* $NetBSD: pthread_rwlock.c,v 1.44 2022/02/12 14:59:32 riastradh Exp $ */
/*-
* Copyright (c) 2002, 2006, 2007, 2008, 2020 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.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: pthread_rwlock.c,v 1.44 2022/02/12 14:59:32 riastradh Exp $");
/* Need to use libc-private names for atomic operations. */
#include "../../common/lib/libc/atomic/atomic_op_namespace.h"
#include <sys/types.h>
#include <sys/lwpctl.h>
#include <assert.h>
#include <time.h>
#include <errno.h>
#include <stddef.h>
#include "pthread.h"
#include "pthread_int.h"
#include "reentrant.h"
#define _RW_LOCKED 0
#define _RW_WANT_WRITE 1
#define _RW_WANT_READ 2
#if __GNUC_PREREQ__(3, 0)
#define NOINLINE __attribute ((noinline))
#else
#define NOINLINE /* nothing */
#endif
static int pthread__rwlock_wrlock(pthread_rwlock_t *, const struct timespec *);
static int pthread__rwlock_rdlock(pthread_rwlock_t *, const struct timespec *);
static void pthread__rwlock_early(pthread_t, pthread_rwlock_t *,
pthread_mutex_t *);
int _pthread_rwlock_held_np(pthread_rwlock_t *);
int _pthread_rwlock_rdheld_np(pthread_rwlock_t *);
int _pthread_rwlock_wrheld_np(pthread_rwlock_t *);
#ifndef lint
__weak_alias(pthread_rwlock_held_np,_pthread_rwlock_held_np)
__weak_alias(pthread_rwlock_rdheld_np,_pthread_rwlock_rdheld_np)
__weak_alias(pthread_rwlock_wrheld_np,_pthread_rwlock_wrheld_np)
#endif
__strong_alias(__libc_rwlock_init,pthread_rwlock_init)
__strong_alias(__libc_rwlock_rdlock,pthread_rwlock_rdlock)
__strong_alias(__libc_rwlock_wrlock,pthread_rwlock_wrlock)
__strong_alias(__libc_rwlock_tryrdlock,pthread_rwlock_tryrdlock)
__strong_alias(__libc_rwlock_trywrlock,pthread_rwlock_trywrlock)
__strong_alias(__libc_rwlock_unlock,pthread_rwlock_unlock)
__strong_alias(__libc_rwlock_destroy,pthread_rwlock_destroy)
static inline uintptr_t
rw_cas(pthread_rwlock_t *ptr, uintptr_t o, uintptr_t n)
{
return (uintptr_t)atomic_cas_ptr(&ptr->ptr_owner, (void *)o,
(void *)n);
}
int
pthread_rwlock_init(pthread_rwlock_t *ptr,
const pthread_rwlockattr_t *attr)
{
if (__predict_false(__uselibcstub))
return __libc_rwlock_init_stub(ptr, attr);
pthread__error(EINVAL, "Invalid rwlock attribute",
attr == NULL || attr->ptra_magic == _PT_RWLOCKATTR_MAGIC);
ptr->ptr_magic = _PT_RWLOCK_MAGIC;
PTQ_INIT(&ptr->ptr_rblocked);
PTQ_INIT(&ptr->ptr_wblocked);
ptr->ptr_nreaders = 0;
ptr->ptr_owner = NULL;
return 0;
}
int
pthread_rwlock_destroy(pthread_rwlock_t *ptr)
{
if (__predict_false(__uselibcstub))
return __libc_rwlock_destroy_stub(ptr);
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
if ((!PTQ_EMPTY(&ptr->ptr_rblocked)) ||
(!PTQ_EMPTY(&ptr->ptr_wblocked)) ||
(ptr->ptr_nreaders != 0) ||
(ptr->ptr_owner != NULL))
return EINVAL;
ptr->ptr_magic = _PT_RWLOCK_DEAD;
return 0;
}
/* We want function call overhead. */
NOINLINE static void
pthread__rwlock_pause(void)
{
pthread__smt_pause();
}
NOINLINE static int
pthread__rwlock_spin(uintptr_t owner)
{
pthread_t thread;
unsigned int i;
if ((owner & ~RW_THREAD) != RW_WRITE_LOCKED)
return 0;
thread = (pthread_t)(owner & RW_THREAD);
if (__predict_false(thread == NULL) ||
thread->pt_lwpctl->lc_curcpu == LWPCTL_CPU_NONE)
return 0;
for (i = 128; i != 0; i--)
pthread__rwlock_pause();
return 1;
}
static int
pthread__rwlock_rdlock(pthread_rwlock_t *ptr, const struct timespec *ts)
{
uintptr_t owner, next;
pthread_mutex_t *interlock;
pthread_t self;
int error;
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) {
/*
* Read the lock owner field. If the need-to-wait
* indicator is clear, then try to acquire the lock.
*/
if ((owner & (RW_WRITE_LOCKED | RW_WRITE_WANTED)) == 0) {
next = rw_cas(ptr, owner, owner + RW_READ_INCR);
if (owner == next) {
/* Got it! */
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
/*
* Didn't get it -- spin around again (we'll
* probably sleep on the next iteration).
*/
continue;
}
self = pthread__self();
if ((owner & RW_THREAD) == (uintptr_t)self)
return EDEADLK;
/* If held write locked and no waiters, spin. */
if (pthread__rwlock_spin(owner)) {
while (pthread__rwlock_spin(owner)) {
owner = (uintptr_t)ptr->ptr_owner;
}
next = owner;
continue;
}
/*
* Grab the interlock. Once we have that, we
* can adjust the waiter bits and sleep queue.
*/
interlock = pthread__hashlock(ptr);
pthread_mutex_lock(interlock);
/*
* Mark the rwlock as having waiters. If the set fails,
* then we may not need to sleep and should spin again.
*/
next = rw_cas(ptr, owner, owner | RW_HAS_WAITERS);
if (owner != next) {
pthread_mutex_unlock(interlock);
continue;
}
/* The waiters bit is set - it's safe to sleep. */
PTQ_INSERT_HEAD(&ptr->ptr_rblocked, self, pt_sleep);
ptr->ptr_nreaders++;
self->pt_rwlocked = _RW_WANT_READ;
self->pt_sleepobj = &ptr->ptr_rblocked;
error = pthread__park(self, interlock, &ptr->ptr_rblocked,
ts, 0);
if (self->pt_sleepobj != NULL) {
pthread__rwlock_early(self, ptr, interlock);
}
/* Did we get the lock? */
if (self->pt_rwlocked == _RW_LOCKED) {
membar_enter();
return 0;
}
if (error != 0)
return error;
pthread__errorfunc(__FILE__, __LINE__, __func__,
"direct handoff failure");
}
}
int
pthread_rwlock_tryrdlock(pthread_rwlock_t *ptr)
{
uintptr_t owner, next;
if (__predict_false(__uselibcstub))
return __libc_rwlock_tryrdlock_stub(ptr);
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
/*
* Don't get a readlock if there is a writer or if there are waiting
* writers; i.e. prefer writers to readers. This strategy is dictated
* by SUSv3.
*/
for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) {
if ((owner & (RW_WRITE_LOCKED | RW_WRITE_WANTED)) != 0)
return EBUSY;
next = rw_cas(ptr, owner, owner + RW_READ_INCR);
if (owner == next) {
/* Got it! */
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
}
}
static int
pthread__rwlock_wrlock(pthread_rwlock_t *ptr, const struct timespec *ts)
{
uintptr_t owner, next;
pthread_mutex_t *interlock;
pthread_t self;
int error;
self = pthread__self();
_DIAGASSERT(((uintptr_t)self & RW_FLAGMASK) == 0);
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) {
/*
* Read the lock owner field. If the need-to-wait
* indicator is clear, then try to acquire the lock.
*/
if ((owner & RW_THREAD) == 0) {
next = rw_cas(ptr, owner,
(uintptr_t)self | RW_WRITE_LOCKED);
if (owner == next) {
/* Got it! */
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
/*
* Didn't get it -- spin around again (we'll
* probably sleep on the next iteration).
*/
continue;
}
if ((owner & RW_THREAD) == (uintptr_t)self)
return EDEADLK;
/* If held write locked and no waiters, spin. */
if (pthread__rwlock_spin(owner)) {
while (pthread__rwlock_spin(owner)) {
owner = (uintptr_t)ptr->ptr_owner;
}
next = owner;
continue;
}
/*
* Grab the interlock. Once we have that, we
* can adjust the waiter bits and sleep queue.
*/
interlock = pthread__hashlock(ptr);
pthread_mutex_lock(interlock);
/*
* Mark the rwlock as having waiters. If the set fails,
* then we may not need to sleep and should spin again.
*/
next = rw_cas(ptr, owner,
owner | RW_HAS_WAITERS | RW_WRITE_WANTED);
if (owner != next) {
pthread_mutex_unlock(interlock);
continue;
}
/* The waiters bit is set - it's safe to sleep. */
PTQ_INSERT_TAIL(&ptr->ptr_wblocked, self, pt_sleep);
self->pt_rwlocked = _RW_WANT_WRITE;
self->pt_sleepobj = &ptr->ptr_wblocked;
error = pthread__park(self, interlock, &ptr->ptr_wblocked,
ts, 0);
if (self->pt_sleepobj != NULL) {
pthread__rwlock_early(self, ptr, interlock);
}
/* Did we get the lock? */
if (self->pt_rwlocked == _RW_LOCKED) {
membar_enter();
return 0;
}
if (error != 0)
return error;
pthread__errorfunc(__FILE__, __LINE__, __func__,
"direct handoff failure: %d", errno);
}
}
int
pthread_rwlock_trywrlock(pthread_rwlock_t *ptr)
{
uintptr_t owner, next;
pthread_t self;
if (__predict_false(__uselibcstub))
return __libc_rwlock_trywrlock_stub(ptr);
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
self = pthread__self();
_DIAGASSERT(((uintptr_t)self & RW_FLAGMASK) == 0);
for (owner = (uintptr_t)ptr->ptr_owner;; owner = next) {
if (owner != 0)
return EBUSY;
next = rw_cas(ptr, owner, (uintptr_t)self | RW_WRITE_LOCKED);
if (owner == next) {
/* Got it! */
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_enter();
#endif
return 0;
}
}
}
int
pthread_rwlock_rdlock(pthread_rwlock_t *ptr)
{
if (__predict_false(__uselibcstub))
return __libc_rwlock_rdlock_stub(ptr);
return pthread__rwlock_rdlock(ptr, NULL);
}
int
pthread_rwlock_timedrdlock(pthread_rwlock_t *ptr,
const struct timespec *abs_timeout)
{
if (abs_timeout == NULL)
return EINVAL;
if ((abs_timeout->tv_nsec >= 1000000000) ||
(abs_timeout->tv_nsec < 0) ||
(abs_timeout->tv_sec < 0))
return EINVAL;
return pthread__rwlock_rdlock(ptr, abs_timeout);
}
int
pthread_rwlock_wrlock(pthread_rwlock_t *ptr)
{
if (__predict_false(__uselibcstub))
return __libc_rwlock_wrlock_stub(ptr);
return pthread__rwlock_wrlock(ptr, NULL);
}
int
pthread_rwlock_timedwrlock(pthread_rwlock_t *ptr,
const struct timespec *abs_timeout)
{
if (abs_timeout == NULL)
return EINVAL;
if ((abs_timeout->tv_nsec >= 1000000000) ||
(abs_timeout->tv_nsec < 0) ||
(abs_timeout->tv_sec < 0))
return EINVAL;
return pthread__rwlock_wrlock(ptr, abs_timeout);
}
int
pthread_rwlock_unlock(pthread_rwlock_t *ptr)
{
uintptr_t owner, decr, new, next;
pthread_mutex_t *interlock;
pthread_t self, thread;
if (__predict_false(__uselibcstub))
return __libc_rwlock_unlock_stub(ptr);
pthread__error(EINVAL, "Invalid rwlock",
ptr->ptr_magic == _PT_RWLOCK_MAGIC);
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_exit();
#endif
/*
* Since we used an add operation to set the required lock
* bits, we can use a subtract to clear them, which makes
* the read-release and write-release path similar.
*/
owner = (uintptr_t)ptr->ptr_owner;
if ((owner & RW_WRITE_LOCKED) != 0) {
self = pthread__self();
decr = (uintptr_t)self | RW_WRITE_LOCKED;
if ((owner & RW_THREAD) != (uintptr_t)self) {
return EPERM;
}
} else {
decr = RW_READ_INCR;
if (owner == 0) {
return EPERM;
}
}
for (;; owner = next) {
/*
* Compute what we expect the new value of the lock to be.
* Only proceed to do direct handoff if there are waiters,
* and if the lock would become unowned.
*/
new = (owner - decr);
if ((new & (RW_THREAD | RW_HAS_WAITERS)) != RW_HAS_WAITERS) {
next = rw_cas(ptr, owner, new);
if (owner == next) {
/* Released! */
return 0;
}
continue;
}
/*
* Grab the interlock. Once we have that, we can adjust
* the waiter bits. We must check to see if there are
* still waiters before proceeding.
*/
interlock = pthread__hashlock(ptr);
pthread_mutex_lock(interlock);
owner = (uintptr_t)ptr->ptr_owner;
if ((owner & RW_HAS_WAITERS) == 0) {
pthread_mutex_unlock(interlock);
next = owner;
continue;
}
/*
* Give the lock away. SUSv3 dictates that we must give
* preference to writers.
*/
self = pthread__self();
if ((thread = PTQ_FIRST(&ptr->ptr_wblocked)) != NULL) {
_DIAGASSERT(((uintptr_t)thread & RW_FLAGMASK) == 0);
new = (uintptr_t)thread | RW_WRITE_LOCKED;
if (PTQ_NEXT(thread, pt_sleep) != NULL)
new |= RW_HAS_WAITERS | RW_WRITE_WANTED;
else if (ptr->ptr_nreaders != 0)
new |= RW_HAS_WAITERS;
/*
* Set in the new value. The lock becomes owned
* by the writer that we are about to wake.
*/
(void)atomic_swap_ptr(&ptr->ptr_owner, (void *)new);
#ifndef PTHREAD__ATOMIC_IS_MEMBAR
membar_exit();
#endif
/* Wake the writer. */
thread->pt_rwlocked = _RW_LOCKED;
pthread__unpark(&ptr->ptr_wblocked, self,
interlock);
} else {
new = 0;
PTQ_FOREACH(thread, &ptr->ptr_rblocked, pt_sleep) {
/*
* May have already been handed the lock,
* since pthread__unpark_all() can release
* our interlock before awakening all
* threads.
*/
if (thread->pt_sleepobj == NULL)
continue;
new += RW_READ_INCR;
membar_exit();
thread->pt_rwlocked = _RW_LOCKED;
}
/*
* Set in the new value. The lock becomes owned
* by the readers that we are about to wake.
*/
(void)atomic_swap_ptr(&ptr->ptr_owner, (void *)new);
/* Wake up all sleeping readers. */
ptr->ptr_nreaders = 0;
pthread__unpark_all(&ptr->ptr_rblocked, self,
interlock);
}
pthread_mutex_unlock(interlock);
return 0;
}
}
/*
* Called when a timedlock awakens early to adjust the waiter bits.
* The rwlock's interlock is held on entry, and the caller has been
* removed from the waiters lists.
*/
static void
pthread__rwlock_early(pthread_t self, pthread_rwlock_t *ptr,
pthread_mutex_t *interlock)
{
uintptr_t owner, set, newval, next;
pthread_queue_t *queue;
pthread_mutex_lock(interlock);
if ((queue = self->pt_sleepobj) == NULL) {
pthread_mutex_unlock(interlock);
return;
}
PTQ_REMOVE(queue, self, pt_sleep);
self->pt_sleepobj = NULL;
owner = (uintptr_t)ptr->ptr_owner;
if ((owner & RW_THREAD) == 0) {
pthread__errorfunc(__FILE__, __LINE__, __func__,
"lock not held");
}
if (!PTQ_EMPTY(&ptr->ptr_wblocked))
set = RW_HAS_WAITERS | RW_WRITE_WANTED;
else if (ptr->ptr_nreaders != 0)
set = RW_HAS_WAITERS;
else
set = 0;
for (;; owner = next) {
newval = (owner & ~(RW_HAS_WAITERS | RW_WRITE_WANTED)) | set;
next = rw_cas(ptr, owner, newval);
if (owner == next)
break;
}
pthread_mutex_unlock(interlock);
}
int
_pthread_rwlock_held_np(pthread_rwlock_t *ptr)
{
uintptr_t owner = (uintptr_t)ptr->ptr_owner;
if ((owner & RW_WRITE_LOCKED) != 0)
return (owner & RW_THREAD) == (uintptr_t)pthread__self();
return (owner & RW_THREAD) != 0;
}
int
_pthread_rwlock_rdheld_np(pthread_rwlock_t *ptr)
{
uintptr_t owner = (uintptr_t)ptr->ptr_owner;
return (owner & RW_THREAD) != 0 && (owner & RW_WRITE_LOCKED) == 0;
}
int
_pthread_rwlock_wrheld_np(pthread_rwlock_t *ptr)
{
uintptr_t owner = (uintptr_t)ptr->ptr_owner;
return (owner & (RW_THREAD | RW_WRITE_LOCKED)) ==
((uintptr_t)pthread__self() | RW_WRITE_LOCKED);
}
#ifdef _PTHREAD_PSHARED
int
pthread_rwlockattr_getpshared(const pthread_rwlockattr_t * __restrict attr,
int * __restrict pshared)
{
pthread__error(EINVAL, "Invalid rwlock attribute",
ptr->ptra_magic == _PT_RWLOCKATTR_MAGIC);
*pshared = PTHREAD_PROCESS_PRIVATE;
return 0;
}
int
pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared)
{
pthread__error(EINVAL, "Invalid rwlock attribute",
ptr->ptra_magic == _PT_RWLOCKATTR_MAGIC);
switch(pshared) {
case PTHREAD_PROCESS_PRIVATE:
return 0;
case PTHREAD_PROCESS_SHARED:
return ENOSYS;
}
return EINVAL;
}
#endif
int
pthread_rwlockattr_init(pthread_rwlockattr_t *attr)
{
if (attr == NULL)
return EINVAL;
attr->ptra_magic = _PT_RWLOCKATTR_MAGIC;
return 0;
}
int
pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr)
{
pthread__error(EINVAL, "Invalid rwlock attribute",
attr->ptra_magic == _PT_RWLOCKATTR_MAGIC);
attr->ptra_magic = _PT_RWLOCKATTR_DEAD;
return 0;
}