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