pthread_rwlock.cpp revision c3f114037dbf028896310609fd28cf2b3da99c4d
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 if (!attr) 64 return EINVAL; 65 66 *attr = PTHREAD_PROCESS_PRIVATE; 67 return 0; 68} 69 70int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) 71{ 72 if (!attr) 73 return EINVAL; 74 75 *attr = -1; 76 return 0; 77} 78 79int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared) 80{ 81 if (!attr) 82 return EINVAL; 83 84 switch (pshared) { 85 case PTHREAD_PROCESS_PRIVATE: 86 case PTHREAD_PROCESS_SHARED: 87 *attr = pshared; 88 return 0; 89 default: 90 return EINVAL; 91 } 92} 93 94int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) { 95 if (!attr || !pshared) 96 return EINVAL; 97 98 *pshared = *attr; 99 return 0; 100} 101 102int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr) 103{ 104 pthread_mutexattr_t* lock_attr = NULL; 105 pthread_condattr_t* cond_attr = NULL; 106 pthread_mutexattr_t lock_attr0; 107 pthread_condattr_t cond_attr0; 108 int ret; 109 110 if (rwlock == NULL) 111 return EINVAL; 112 113 if (attr && *attr == PTHREAD_PROCESS_SHARED) { 114 lock_attr = &lock_attr0; 115 pthread_mutexattr_init(lock_attr); 116 pthread_mutexattr_setpshared(lock_attr, PTHREAD_PROCESS_SHARED); 117 118 cond_attr = &cond_attr0; 119 pthread_condattr_init(cond_attr); 120 pthread_condattr_setpshared(cond_attr, PTHREAD_PROCESS_SHARED); 121 } 122 123 ret = pthread_mutex_init(&rwlock->lock, lock_attr); 124 if (ret != 0) 125 return ret; 126 127 ret = pthread_cond_init(&rwlock->cond, cond_attr); 128 if (ret != 0) { 129 pthread_mutex_destroy(&rwlock->lock); 130 return ret; 131 } 132 133 rwlock->numLocks = 0; 134 rwlock->pendingReaders = 0; 135 rwlock->pendingWriters = 0; 136 rwlock->writerThreadId = 0; 137 138 return 0; 139} 140 141int pthread_rwlock_destroy(pthread_rwlock_t *rwlock) 142{ 143 if (rwlock == NULL) 144 return EINVAL; 145 146 if (rwlock->numLocks > 0) 147 return EBUSY; 148 149 pthread_cond_destroy(&rwlock->cond); 150 pthread_mutex_destroy(&rwlock->lock); 151 return 0; 152} 153 154/* Returns TRUE iff we can acquire a read lock. */ 155static __inline__ int read_precondition(pthread_rwlock_t* rwlock, int tid) 156{ 157 /* We can't have the lock if any writer is waiting for it (writer bias). 158 * This tries to avoid starvation when there are multiple readers racing. 159 */ 160 if (rwlock->pendingWriters > 0) 161 return 0; 162 163 /* We can have the lock if there is no writer, or if we write-own it */ 164 /* The second test avoids a self-dead lock in case of buggy code. */ 165 if (rwlock->writerThreadId == 0 || rwlock->writerThreadId == tid) 166 return 1; 167 168 /* Otherwise, we can't have it */ 169 return 0; 170} 171 172/* returns TRUE iff we can acquire a write lock. */ 173static __inline__ int write_precondition(pthread_rwlock_t* rwlock, int tid) 174{ 175 /* We can get the lock if nobody has it */ 176 if (rwlock->numLocks == 0) 177 return 1; 178 179 /* Or if we already own it */ 180 if (rwlock->writerThreadId == tid) 181 return 1; 182 183 /* Otherwise, not */ 184 return 0; 185} 186 187/* This function is used to waken any waiting thread contending 188 * for the lock. One of them should be able to grab it after 189 * that. 190 */ 191static void _pthread_rwlock_pulse(pthread_rwlock_t *rwlock) 192{ 193 if (rwlock->pendingReaders > 0 || rwlock->pendingWriters > 0) 194 pthread_cond_broadcast(&rwlock->cond); 195} 196 197static int __pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 198 int ret = 0; 199 200 if (rwlock == NULL) { 201 return EINVAL; 202 } 203 204 pthread_mutex_lock(&rwlock->lock); 205 int tid = __get_thread()->tid; 206 if (__predict_false(!read_precondition(rwlock, tid))) { 207 rwlock->pendingReaders += 1; 208 do { 209 ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); 210 } while (ret == 0 && !read_precondition(rwlock, tid)); 211 rwlock->pendingReaders -= 1; 212 if (ret != 0) { 213 goto EXIT; 214 } 215 } 216 ++rwlock->numLocks; 217EXIT: 218 pthread_mutex_unlock(&rwlock->lock); 219 return ret; 220} 221 222static int __pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 223 int ret = 0; 224 225 if (rwlock == NULL) { 226 return EINVAL; 227 } 228 229 pthread_mutex_lock(&rwlock->lock); 230 int tid = __get_thread()->tid; 231 if (__predict_false(!write_precondition(rwlock, tid))) { 232 // If we can't read yet, wait until the rwlock is unlocked 233 // and try again. Increment pendingReaders to get the 234 // cond broadcast when that happens. 235 rwlock->pendingWriters += 1; 236 do { 237 ret = pthread_cond_timedwait(&rwlock->cond, &rwlock->lock, abs_timeout); 238 } while (ret == 0 && !write_precondition(rwlock, tid)); 239 rwlock->pendingWriters -= 1; 240 if (ret != 0) { 241 goto EXIT; 242 } 243 } 244 ++rwlock->numLocks; 245 rwlock->writerThreadId = tid; 246EXIT: 247 pthread_mutex_unlock(&rwlock->lock); 248 return ret; 249} 250 251int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock) { 252 return __pthread_rwlock_timedrdlock(rwlock, NULL); 253} 254 255int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock) 256{ 257 int ret = 0; 258 259 if (rwlock == NULL) 260 return EINVAL; 261 262 pthread_mutex_lock(&rwlock->lock); 263 if (__predict_false(!read_precondition(rwlock, __get_thread()->tid))) 264 ret = EBUSY; 265 else 266 ++rwlock->numLocks; 267 pthread_mutex_unlock(&rwlock->lock); 268 269 return ret; 270} 271 272int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 273 return __pthread_rwlock_timedrdlock(rwlock, abs_timeout); 274} 275 276int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock) { 277 return __pthread_rwlock_timedwrlock(rwlock, NULL); 278} 279 280int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock) 281{ 282 int ret = 0; 283 284 if (rwlock == NULL) 285 return EINVAL; 286 287 pthread_mutex_lock(&rwlock->lock); 288 int tid = __get_thread()->tid; 289 if (__predict_false(!write_precondition(rwlock, tid))) { 290 ret = EBUSY; 291 } else { 292 ++rwlock->numLocks; 293 rwlock->writerThreadId = tid; 294 } 295 pthread_mutex_unlock(&rwlock->lock); 296 return ret; 297} 298 299int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 300 return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 301} 302 303int pthread_rwlock_unlock(pthread_rwlock_t *rwlock) 304{ 305 int ret = 0; 306 307 if (rwlock == NULL) 308 return EINVAL; 309 310 pthread_mutex_lock(&rwlock->lock); 311 312 /* The lock must be held */ 313 if (rwlock->numLocks == 0) { 314 ret = EPERM; 315 goto EXIT; 316 } 317 318 /* If it has only readers, writerThreadId is 0 */ 319 if (rwlock->writerThreadId == 0) { 320 if (--rwlock->numLocks == 0) 321 _pthread_rwlock_pulse(rwlock); 322 } 323 /* Otherwise, it has only a single writer, which 324 * must be ourselves. 325 */ 326 else { 327 if (rwlock->writerThreadId != __get_thread()->tid) { 328 ret = EPERM; 329 goto EXIT; 330 } 331 if (--rwlock->numLocks == 0) { 332 rwlock->writerThreadId = 0; 333 _pthread_rwlock_pulse(rwlock); 334 } 335 } 336EXIT: 337 pthread_mutex_unlock(&rwlock->lock); 338 return ret; 339} 340