pthread_rwlock.cpp revision 39b644a0e270df453c53d6060cd364391bb1c512
1/* 2 * Copyright (C) 2010 The Android Open Source Project 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in 12 * the documentation and/or other materials provided with the 13 * distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29#include "pthread_internal.h" 30#include <errno.h> 31 32/* Technical note: 33 * 34 * Possible states of a read/write lock: 35 * 36 * - no readers and no writer (unlocked) 37 * - one or more readers sharing the lock at the same time (read-locked) 38 * - one writer holding the lock (write-lock) 39 * 40 * Additionally: 41 * - trying to get the write-lock while there are any readers blocks 42 * - trying to get the read-lock while there is a writer blocks 43 * - a single thread can acquire the lock multiple times in the same mode 44 * 45 * - Posix states that behavior is undefined it a thread tries to acquire 46 * the lock in two distinct modes (e.g. write after read, or read after write). 47 * 48 * - This implementation tries to avoid writer starvation by making the readers 49 * block as soon as there is a waiting writer on the lock. However, it cannot 50 * completely eliminate it: each time the lock is unlocked, all waiting threads 51 * are woken and battle for it, which one gets it depends on the kernel scheduler 52 * and is semi-random. 53 * 54 */ 55 56#define RWLOCKATTR_DEFAULT 0 57#define RWLOCKATTR_SHARED_MASK 0x0010 58 59extern pthread_internal_t* __get_thread(void); 60 61int pthread_rwlockattr_init(pthread_rwlockattr_t *attr) 62{ 63 *attr = PTHREAD_PROCESS_PRIVATE; 64 return 0; 65} 66 67int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) 68{ 69 *attr = -1; 70 return 0; 71} 72 73int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared) 74{ 75 switch (pshared) { 76 case PTHREAD_PROCESS_PRIVATE: 77 case PTHREAD_PROCESS_SHARED: 78 *attr = pshared; 79 return 0; 80 default: 81 return EINVAL; 82 } 83} 84 85int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) { 86 *pshared = *attr; 87 return 0; 88} 89 90int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr) 91{ 92 pthread_mutexattr_t* lock_attr = NULL; 93 pthread_condattr_t* cond_attr = NULL; 94 pthread_mutexattr_t lock_attr0; 95 pthread_condattr_t cond_attr0; 96 int ret; 97 98 if (attr && *attr == PTHREAD_PROCESS_SHARED) { 99 lock_attr = &lock_attr0; 100 pthread_mutexattr_init(lock_attr); 101 pthread_mutexattr_setpshared(lock_attr, PTHREAD_PROCESS_SHARED); 102 103 cond_attr = &cond_attr0; 104 pthread_condattr_init(cond_attr); 105 pthread_condattr_setpshared(cond_attr, PTHREAD_PROCESS_SHARED); 106 } 107 108 ret = pthread_mutex_init(&rwlock->lock, lock_attr); 109 if (ret != 0) 110 return ret; 111 112 ret = pthread_cond_init(&rwlock->cond, cond_attr); 113 if (ret != 0) { 114 pthread_mutex_destroy(&rwlock->lock); 115 return ret; 116 } 117 118 rwlock->numLocks = 0; 119 rwlock->pendingReaders = 0; 120 rwlock->pendingWriters = 0; 121 rwlock->writerThreadId = 0; 122 123 return 0; 124} 125 126int pthread_rwlock_destroy(pthread_rwlock_t *rwlock) 127{ 128 if (rwlock->numLocks > 0) 129 return EBUSY; 130 131 pthread_cond_destroy(&rwlock->cond); 132 pthread_mutex_destroy(&rwlock->lock); 133 return 0; 134} 135 136/* Returns TRUE iff we can acquire a read lock. */ 137static __inline__ int read_precondition(pthread_rwlock_t* rwlock, int tid) 138{ 139 /* We can't have the lock if any writer is waiting for it (writer bias). 140 * This tries to avoid starvation when there are multiple readers racing. 141 */ 142 if (rwlock->pendingWriters > 0) 143 return 0; 144 145 /* We can have the lock if there is no writer, or if we write-own it */ 146 /* The second test avoids a self-dead lock in case of buggy code. */ 147 if (rwlock->writerThreadId == 0 || rwlock->writerThreadId == tid) 148 return 1; 149 150 /* Otherwise, we can't have it */ 151 return 0; 152} 153 154/* returns TRUE iff we can acquire a write lock. */ 155static __inline__ int write_precondition(pthread_rwlock_t* rwlock, int tid) 156{ 157 /* We can get the lock if nobody has it */ 158 if (rwlock->numLocks == 0) 159 return 1; 160 161 /* Or if we already own it */ 162 if (rwlock->writerThreadId == tid) 163 return 1; 164 165 /* Otherwise, not */ 166 return 0; 167} 168 169/* This function is used to waken any waiting thread contending 170 * for the lock. One of them should be able to grab it after 171 * that. 172 */ 173static void _pthread_rwlock_pulse(pthread_rwlock_t *rwlock) 174{ 175 if (rwlock->pendingReaders > 0 || rwlock->pendingWriters > 0) 176 pthread_cond_broadcast(&rwlock->cond); 177} 178 179static int __pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 180 int ret = 0; 181 182 pthread_mutex_lock(&rwlock->lock); 183 int tid = __get_thread()->tid; 184 if (__predict_false(!read_precondition(rwlock, tid))) { 185 rwlock->pendingReaders += 1; 186 do { 187 ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); 188 } while (ret == 0 && !read_precondition(rwlock, tid)); 189 rwlock->pendingReaders -= 1; 190 if (ret != 0) { 191 goto EXIT; 192 } 193 } 194 ++rwlock->numLocks; 195EXIT: 196 pthread_mutex_unlock(&rwlock->lock); 197 return ret; 198} 199 200static int __pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 201 int ret = 0; 202 203 pthread_mutex_lock(&rwlock->lock); 204 int tid = __get_thread()->tid; 205 if (__predict_false(!write_precondition(rwlock, tid))) { 206 // If we can't read yet, wait until the rwlock is unlocked 207 // and try again. Increment pendingReaders to get the 208 // cond broadcast when that happens. 209 rwlock->pendingWriters += 1; 210 do { 211 ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); 212 } while (ret == 0 && !write_precondition(rwlock, tid)); 213 rwlock->pendingWriters -= 1; 214 if (ret != 0) { 215 goto EXIT; 216 } 217 } 218 ++rwlock->numLocks; 219 rwlock->writerThreadId = tid; 220EXIT: 221 pthread_mutex_unlock(&rwlock->lock); 222 return ret; 223} 224 225int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock) { 226 return __pthread_rwlock_timedrdlock(rwlock, NULL); 227} 228 229int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock) 230{ 231 int ret = 0; 232 233 pthread_mutex_lock(&rwlock->lock); 234 if (__predict_false(!read_precondition(rwlock, __get_thread()->tid))) 235 ret = EBUSY; 236 else 237 ++rwlock->numLocks; 238 pthread_mutex_unlock(&rwlock->lock); 239 240 return ret; 241} 242 243int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 244 return __pthread_rwlock_timedrdlock(rwlock, abs_timeout); 245} 246 247int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock) { 248 return __pthread_rwlock_timedwrlock(rwlock, NULL); 249} 250 251int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock) 252{ 253 int ret = 0; 254 255 pthread_mutex_lock(&rwlock->lock); 256 int tid = __get_thread()->tid; 257 if (__predict_false(!write_precondition(rwlock, tid))) { 258 ret = EBUSY; 259 } else { 260 ++rwlock->numLocks; 261 rwlock->writerThreadId = tid; 262 } 263 pthread_mutex_unlock(&rwlock->lock); 264 return ret; 265} 266 267int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 268 return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 269} 270 271int pthread_rwlock_unlock(pthread_rwlock_t *rwlock) 272{ 273 int ret = 0; 274 275 pthread_mutex_lock(&rwlock->lock); 276 277 /* The lock must be held */ 278 if (rwlock->numLocks == 0) { 279 ret = EPERM; 280 goto EXIT; 281 } 282 283 /* If it has only readers, writerThreadId is 0 */ 284 if (rwlock->writerThreadId == 0) { 285 if (--rwlock->numLocks == 0) 286 _pthread_rwlock_pulse(rwlock); 287 } 288 /* Otherwise, it has only a single writer, which 289 * must be ourselves. 290 */ 291 else { 292 if (rwlock->writerThreadId != __get_thread()->tid) { 293 ret = EPERM; 294 goto EXIT; 295 } 296 if (--rwlock->numLocks == 0) { 297 rwlock->writerThreadId = 0; 298 _pthread_rwlock_pulse(rwlock); 299 } 300 } 301EXIT: 302 pthread_mutex_unlock(&rwlock->lock); 303 return ret; 304} 305