From 50304f2eefb4c79ceaf4605203f3825a35d831c0 Mon Sep 17 00:00:00 2001 From: Rich Felker Date: Wed, 3 Aug 2011 10:21:32 -0400 Subject: [PATCH] overhaul rwlocks to address several issues like mutexes and semaphores, rwlocks suffered from a race condition where the unlock operation could access the lock memory after another thread successfully obtained the lock (and possibly destroyed or unmapped the object). this has been fixed in the same way it was fixed for other lock types. in addition, the previous implementation favored writers over readers. in the absence of other considerations, that is the best behavior for rwlocks, and posix explicitly allows it. however posix also requires read locks to be recursive. if writers are favored, any attempt to obtain a read lock while a writer is waiting for the lock will fail, causing "recursive" read locks to deadlock. this can be avoided by keeping track of which threads already hold read locks, but doing so requires unbounded memory usage, and there must be a fallback case that favors readers in case memory allocation failed. and all of this must be synchronized. the cost, complexity, and risk of errors in getting it right is too great, so we simply favor readers. tracking of the owner of write locks has been removed, as it was not useful for anything. it could allow deadlock detection, but it's not clear to me that returning EDEADLK (which a buggy program is likely to ignore) is better than deadlocking; at least the latter behavior prevents further data corruption. a correct program cannot invoke this situation anyway. the reader count and write lock state, as well as the "last minute" waiter flag have all been combined into a single atomic lock. this means all state transitions for the lock are atomic compare-and-swap operations. this makes establishing correctness much easier and may improve performance. finally, some code duplication has been cleaned up. more is called for, especially the standard __timedwait idiom repeated in all locks. --- src/internal/pthread_impl.h | 6 ++---- src/thread/pthread_rwlock_rdlock.c | 4 +--- src/thread/pthread_rwlock_timedrdlock.c | 19 ++++++++++--------- src/thread/pthread_rwlock_timedwrlock.c | 21 ++++++++++----------- src/thread/pthread_rwlock_tryrdlock.c | 14 +++++++------- src/thread/pthread_rwlock_trywrlock.c | 8 +------- src/thread/pthread_rwlock_unlock.c | 23 ++++++++++++----------- src/thread/pthread_rwlock_wrlock.c | 9 +-------- 8 files changed, 44 insertions(+), 60 deletions(-) diff --git a/src/internal/pthread_impl.h b/src/internal/pthread_impl.h index c11840d6..c853af88 100644 --- a/src/internal/pthread_impl.h +++ b/src/internal/pthread_impl.h @@ -67,10 +67,8 @@ struct __timer { #define _m_count __u.__i[5] #define _c_block __u.__i[0] #define _c_clock __u.__i[1] -#define _rw_wrlock __u.__i[0] -#define _rw_readers __u.__i[1] -#define _rw_waiters __u.__i[2] -#define _rw_owner __u.__i[3] +#define _rw_lock __u.__i[0] +#define _rw_waiters __u.__i[1] #define _b_inst __u.__p[0] #define _b_limit __u.__i[2] #define _b_lock __u.__i[3] diff --git a/src/thread/pthread_rwlock_rdlock.c b/src/thread/pthread_rwlock_rdlock.c index 29863507..0800d21f 100644 --- a/src/thread/pthread_rwlock_rdlock.c +++ b/src/thread/pthread_rwlock_rdlock.c @@ -2,7 +2,5 @@ int pthread_rwlock_rdlock(pthread_rwlock_t *rw) { - while (pthread_rwlock_tryrdlock(rw)) - __wait(&rw->_rw_wrlock, &rw->_rw_waiters, 1, 0); - return 0; + return pthread_rwlock_timedrdlock(rw, 0); } diff --git a/src/thread/pthread_rwlock_timedrdlock.c b/src/thread/pthread_rwlock_timedrdlock.c index a6f61b05..b5cb404a 100644 --- a/src/thread/pthread_rwlock_timedrdlock.c +++ b/src/thread/pthread_rwlock_timedrdlock.c @@ -2,14 +2,15 @@ int pthread_rwlock_timedrdlock(pthread_rwlock_t *rw, const struct timespec *at) { - int w=0; - while (pthread_rwlock_tryrdlock(rw)) { - if (!w) a_inc(&rw->_rw_waiters), w++; - if (__timedwait(&rw->_rw_wrlock, 1, CLOCK_REALTIME, at, 0, 0, 0)==ETIMEDOUT) { - if (w) a_dec(&rw->_rw_waiters); - return ETIMEDOUT; - } + int r, t; + while ((r=pthread_rwlock_tryrdlock(rw))==EBUSY) { + if (!(r=rw->_rw_lock) || (r&0x7fffffff)!=0x7fffffff) continue; + t = r | 0x80000000; + a_inc(&rw->_rw_waiters); + a_cas(&rw->_rw_lock, r, t); + r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, 0); + a_dec(&rw->_rw_waiters); + if (r && r != EINTR) return r; } - if (w) a_dec(&rw->_rw_waiters); - return 0; + return r; } diff --git a/src/thread/pthread_rwlock_timedwrlock.c b/src/thread/pthread_rwlock_timedwrlock.c index 484808e8..aa2fd199 100644 --- a/src/thread/pthread_rwlock_timedwrlock.c +++ b/src/thread/pthread_rwlock_timedwrlock.c @@ -2,16 +2,15 @@ int pthread_rwlock_timedwrlock(pthread_rwlock_t *rw, const struct timespec *at) { - int nr, *p, w=0; - while (pthread_rwlock_trywrlock(rw)==EAGAIN) { - if (!w) a_inc(&rw->_rw_waiters), w++; - if ((nr=rw->_rw_readers)) p = &rw->_rw_readers; - else nr=1, p = &rw->_rw_wrlock; - if (__timedwait(p, nr, CLOCK_REALTIME, at, 0, 0, 0)==ETIMEDOUT) { - if (w) a_dec(&rw->_rw_waiters); - return ETIMEDOUT; - } + int r, t; + while ((r=pthread_rwlock_trywrlock(rw))==EBUSY) { + if (!(r=rw->_rw_lock)) continue; + t = r | 0x80000000; + a_inc(&rw->_rw_waiters); + a_cas(&rw->_rw_lock, r, t); + r = __timedwait(&rw->_rw_lock, t, CLOCK_REALTIME, at, 0, 0, 0); + a_dec(&rw->_rw_waiters); + if (r && r != EINTR) return r; } - if (w) a_dec(&rw->_rw_waiters); - return 0; + return r; } diff --git a/src/thread/pthread_rwlock_tryrdlock.c b/src/thread/pthread_rwlock_tryrdlock.c index f860ec71..fa271fcc 100644 --- a/src/thread/pthread_rwlock_tryrdlock.c +++ b/src/thread/pthread_rwlock_tryrdlock.c @@ -2,12 +2,12 @@ int pthread_rwlock_tryrdlock(pthread_rwlock_t *rw) { - a_inc(&rw->_rw_readers); - if (rw->_rw_wrlock) { - a_dec(&rw->_rw_readers); - if (rw->_rw_waiters && !rw->_rw_readers) - __wake(&rw->_rw_readers, 1, 0); - return EBUSY; - } + int val, cnt; + do { + val = rw->_rw_lock; + cnt = val & 0x7fffffff; + if (cnt == 0x7fffffff) return EBUSY; + if (cnt == 0x7ffffffe) return EAGAIN; + } while (a_cas(&rw->_rw_lock, val, val+1) != val); return 0; } diff --git a/src/thread/pthread_rwlock_trywrlock.c b/src/thread/pthread_rwlock_trywrlock.c index 202e256a..bb3d3a99 100644 --- a/src/thread/pthread_rwlock_trywrlock.c +++ b/src/thread/pthread_rwlock_trywrlock.c @@ -2,12 +2,6 @@ int pthread_rwlock_trywrlock(pthread_rwlock_t *rw) { - if (a_xchg(&rw->_rw_wrlock, 1)) - return EBUSY; - if (rw->_rw_readers) { - a_store(&rw->_rw_wrlock, 0); - return EBUSY; - } - rw->_rw_owner = pthread_self()->tid; + if (a_cas(&rw->_rw_lock, 0, 0x7fffffff)) return EBUSY; return 0; } diff --git a/src/thread/pthread_rwlock_unlock.c b/src/thread/pthread_rwlock_unlock.c index 060e3fe1..5edca634 100644 --- a/src/thread/pthread_rwlock_unlock.c +++ b/src/thread/pthread_rwlock_unlock.c @@ -2,16 +2,17 @@ int pthread_rwlock_unlock(pthread_rwlock_t *rw) { - struct pthread *self = pthread_self(); - if (rw->_rw_owner == self->tid) { - rw->_rw_owner = 0; - a_store(&rw->_rw_wrlock, 0); - if (rw->_rw_waiters) - __wake(&rw->_rw_wrlock, -1, 0); - return 0; - } - a_dec(&rw->_rw_readers); - if (rw->_rw_waiters && !rw->_rw_readers) - __wake(&rw->_rw_readers, 1, 0); + int val, cnt, waiters, new; + + do { + val = rw->_rw_lock; + cnt = val & 0x7fffffff; + waiters = rw->_rw_waiters; + new = (cnt == 0x7fffffff || cnt == 1) ? 0 : val-1; + } while (a_cas(&rw->_rw_lock, val, new) != val); + + if (!new && (waiters || val<0)) + __wake(&rw->_rw_lock, 1, 0); + return 0; } diff --git a/src/thread/pthread_rwlock_wrlock.c b/src/thread/pthread_rwlock_wrlock.c index 8fd9ad1d..7f33535c 100644 --- a/src/thread/pthread_rwlock_wrlock.c +++ b/src/thread/pthread_rwlock_wrlock.c @@ -2,12 +2,5 @@ int pthread_rwlock_wrlock(pthread_rwlock_t *rw) { - int nr; - while (pthread_rwlock_trywrlock(rw)==EAGAIN) { - if ((nr=rw->_rw_readers)) - __wait(&rw->_rw_readers, &rw->_rw_waiters, nr, 0); - else - __wait(&rw->_rw_wrlock, &rw->_rw_waiters, 1, 0); - } - return 0; + return pthread_rwlock_timedwrlock(rw, 0); } -- 2.25.1