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