pthread_rwlock.cpp revision 04303f5a8ab9a992f3671d46b6ee2171582cbd61
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 <errno.h> 30 31#include "pthread_internal.h" 32#include "private/bionic_futex.h" 33#include "private/bionic_time_conversions.h" 34 35/* Technical note: 36 * 37 * Possible states of a read/write lock: 38 * 39 * - no readers and no writer (unlocked) 40 * - one or more readers sharing the lock at the same time (read-locked) 41 * - one writer holding the lock (write-lock) 42 * 43 * Additionally: 44 * - trying to get the write-lock while there are any readers blocks 45 * - trying to get the read-lock while there is a writer blocks 46 * - a single thread can acquire the lock multiple times in read mode 47 * 48 * - Posix states that behavior is undefined (may deadlock) if a thread tries 49 * to acquire the lock 50 * - in write mode while already holding the lock (whether in read or write mode) 51 * - in read mode while already holding the lock in write mode. 52 * - This implementation will return EDEADLK in "write after write" and "read after 53 * write" cases and will deadlock in write after read case. 54 * 55 * TODO: VERY CAREFULLY convert this to use C++11 atomics when possible. All volatile 56 * members of pthread_rwlock_t should be converted to atomics<> and __sync_bool_compare_and_swap 57 * should be changed to compare_exchange_strong accompanied by the proper ordering 58 * constraints (comments have been added with the intending ordering across the code). 59 * 60 * TODO: As it stands now, pending_readers and pending_writers could be merged into a 61 * a single waiters variable. Keeping them separate adds a bit of clarity and keeps 62 * the door open for a writer-biased implementation. 63 * 64 */ 65 66#define RWLOCKATTR_DEFAULT 0 67#define RWLOCKATTR_SHARED_MASK 0x0010 68 69static inline bool rwlock_is_shared(const pthread_rwlock_t* rwlock) { 70 return rwlock->attr == PTHREAD_PROCESS_SHARED; 71} 72 73static bool timespec_from_absolute(timespec* rel_timeout, const timespec* abs_timeout) { 74 if (abs_timeout != NULL) { 75 if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout, CLOCK_REALTIME)) { 76 return false; 77 } 78 } 79 return true; 80} 81 82int pthread_rwlockattr_init(pthread_rwlockattr_t* attr) { 83 *attr = PTHREAD_PROCESS_PRIVATE; 84 return 0; 85} 86 87int pthread_rwlockattr_destroy(pthread_rwlockattr_t* attr) { 88 *attr = -1; 89 return 0; 90} 91 92int pthread_rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) { 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(const pthread_rwlockattr_t* attr, int* pshared) { 104 *pshared = *attr; 105 return 0; 106} 107 108int pthread_rwlock_init(pthread_rwlock_t* rwlock, const pthread_rwlockattr_t* attr) { 109 if (attr != NULL) { 110 switch (*attr) { 111 case PTHREAD_PROCESS_SHARED: 112 case PTHREAD_PROCESS_PRIVATE: 113 rwlock->attr= *attr; 114 break; 115 default: 116 return EINVAL; 117 } 118 } 119 120 rwlock->state = 0; 121 rwlock->pending_readers = 0; 122 rwlock->pending_writers = 0; 123 rwlock->writer_thread_id = 0; 124 125 return 0; 126} 127 128int pthread_rwlock_destroy(pthread_rwlock_t* rwlock) { 129 if (rwlock->state != 0) { 130 return EBUSY; 131 } 132 return 0; 133} 134 135static int __pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 136 if (__predict_false(__get_thread()->tid == rwlock->writer_thread_id)) { 137 return EDEADLK; 138 } 139 140 timespec ts; 141 timespec* rel_timeout = (abs_timeout == NULL) ? NULL : &ts; 142 bool done = false; 143 do { 144 // This is actually a race read as there's nothing that guarantees the atomicity of integer 145 // reads / writes. However, in practice this "never" happens so until we switch to C++11 this 146 // should work fine. The same applies in the other places this idiom is used. 147 int32_t cur_state = rwlock->state; // C++11 relaxed atomic read 148 if (__predict_true(cur_state >= 0)) { 149 // Add as an extra reader. 150 done = __sync_bool_compare_and_swap(&rwlock->state, cur_state, cur_state + 1); // C++11 memory_order_aquire 151 } else { 152 if (!timespec_from_absolute(rel_timeout, abs_timeout)) { 153 return ETIMEDOUT; 154 } 155 // Owner holds it in write mode, hang up. 156 // To avoid losing wake ups the pending_readers update and the state read should be 157 // sequentially consistent. (currently enforced by __sync_fetch_and_add which creates a full barrier) 158 __sync_fetch_and_add(&rwlock->pending_readers, 1); // C++11 memory_order_relaxed (if the futex_wait ensures the ordering) 159 int ret = __futex_wait_ex(&rwlock->state, rwlock_is_shared(rwlock), cur_state, rel_timeout); 160 __sync_fetch_and_sub(&rwlock->pending_readers, 1); // C++11 memory_order_relaxed 161 if (ret == -ETIMEDOUT) { 162 return ETIMEDOUT; 163 } 164 } 165 } while (!done); 166 167 return 0; 168} 169 170static int __pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 171 int tid = __get_thread()->tid; 172 if (__predict_false(tid == rwlock->writer_thread_id)) { 173 return EDEADLK; 174 } 175 176 timespec ts; 177 timespec* rel_timeout = (abs_timeout == NULL) ? NULL : &ts; 178 bool done = false; 179 do { 180 int32_t cur_state = rwlock->state; 181 if (__predict_true(cur_state == 0)) { 182 // Change state from 0 to -1. 183 done = __sync_bool_compare_and_swap(&rwlock->state, 0 /* cur state */, -1 /* new state */); // C++11 memory_order_aquire 184 } else { 185 if (!timespec_from_absolute(rel_timeout, abs_timeout)) { 186 return ETIMEDOUT; 187 } 188 // Failed to acquire, hang up. 189 // To avoid losing wake ups the pending_writers update and the state read should be 190 // sequentially consistent. (currently enforced by __sync_fetch_and_add which creates a full barrier) 191 __sync_fetch_and_add(&rwlock->pending_writers, 1); // C++11 memory_order_relaxed (if the futex_wait ensures the ordering) 192 int ret = __futex_wait_ex(&rwlock->state, rwlock_is_shared(rwlock), cur_state, rel_timeout); 193 __sync_fetch_and_sub(&rwlock->pending_writers, 1); // C++11 memory_order_relaxed 194 if (ret == -ETIMEDOUT) { 195 return ETIMEDOUT; 196 } 197 } 198 } while (!done); 199 200 rwlock->writer_thread_id = tid; 201 return 0; 202} 203 204int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock) { 205 return __pthread_rwlock_timedrdlock(rwlock, NULL); 206} 207 208int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 209 return __pthread_rwlock_timedrdlock(rwlock, abs_timeout); 210} 211 212int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock) { 213 int32_t cur_state = rwlock->state; 214 if ((cur_state >= 0) && 215 __sync_bool_compare_and_swap(&rwlock->state, cur_state, cur_state + 1)) { // C++11 memory_order_acquire 216 return 0; 217 } 218 return EBUSY; 219} 220 221int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock) { 222 return __pthread_rwlock_timedwrlock(rwlock, NULL); 223} 224 225int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 226 return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 227} 228 229int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock) { 230 int tid = __get_thread()->tid; 231 int32_t cur_state = rwlock->state; 232 if ((cur_state == 0) && 233 __sync_bool_compare_and_swap(&rwlock->state, 0 /* cur state */, -1 /* new state */)) { // C++11 memory_order_acquire 234 rwlock->writer_thread_id = tid; 235 return 0; 236 } 237 return EBUSY; 238} 239 240 241int pthread_rwlock_unlock(pthread_rwlock_t* rwlock) { 242 int tid = __get_thread()->tid; 243 bool done = false; 244 do { 245 int32_t cur_state = rwlock->state; 246 if (cur_state == 0) { 247 return EPERM; 248 } 249 if (cur_state == -1) { 250 if (rwlock->writer_thread_id != tid) { 251 return EPERM; 252 } 253 // We're no longer the owner. 254 rwlock->writer_thread_id = 0; 255 // Change state from -1 to 0. 256 // We use __sync_bool_compare_and_swap to achieve sequential consistency of the state store and 257 // the following pendingX loads. A simple store with memory_order_release semantics 258 // is not enough to guarantee that the pendingX loads are not reordered before the 259 // store (which may lead to a lost wakeup). 260 __sync_bool_compare_and_swap( &rwlock->state, -1 /* cur state*/, 0 /* new state */); // C++11 maybe memory_order_seq_cst? 261 262 // Wake any waiters. 263 if (__predict_false(rwlock->pending_readers > 0 || rwlock->pending_writers > 0)) { 264 __futex_wake_ex(&rwlock->state, rwlock_is_shared(rwlock), INT_MAX); 265 } 266 done = true; 267 } else { // cur_state > 0 268 // Reduce state by 1. 269 // See the comment above on why we need __sync_bool_compare_and_swap. 270 done = __sync_bool_compare_and_swap(&rwlock->state, cur_state, cur_state - 1); // C++11 maybe memory_order_seq_cst? 271 if (done && (cur_state - 1) == 0) { 272 // There are no more readers, wake any waiters. 273 if (__predict_false(rwlock->pending_readers > 0 || rwlock->pending_writers > 0)) { 274 __futex_wake_ex(&rwlock->state, rwlock_is_shared(rwlock), INT_MAX); 275 } 276 } 277 } 278 } while (!done); 279 280 return 0; 281} 282