pthread_rwlock.cpp revision 92687e41bcf108957944dafa80a9bfda219bfb0f
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#include <sys/atomics.h> 31 32#include "pthread_internal.h" 33#include "private/bionic_futex.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 __atomic_cmpxchg 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(rel_timeout, abs_timeout, CLOCK_REALTIME) < 0) { 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 = __atomic_cmpxchg(cur_state, cur_state + 1, &rwlock->state) == 0; // 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 __atomic_inc which creates a full barrier) 158 __atomic_inc(&rwlock->pending_readers); // 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 __atomic_dec(&rwlock->pending_readers); // 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 = __atomic_cmpxchg(0 /* cur_state */, -1 /* new state */, &rwlock->state) == 0; // 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 __atomic_inc which creates a full barrier) 191 __atomic_inc(&rwlock->pending_writers); // 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 __atomic_dec(&rwlock->pending_writers); // 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 if(__atomic_cmpxchg(cur_state, cur_state + 1, &rwlock->state) != 0) { // C++11 memory_order_acquire 216 return EBUSY; 217 } 218 } else { 219 return EBUSY; 220 } 221 return 0; 222} 223 224int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock) { 225 return __pthread_rwlock_timedwrlock(rwlock, NULL); 226} 227 228int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock, const timespec* abs_timeout) { 229 return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 230} 231 232int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock) { 233 int tid = __get_thread()->tid; 234 int32_t cur_state = rwlock->state; 235 if (cur_state == 0) { 236 if(__atomic_cmpxchg(0, -1, &rwlock->state) != 0) { // C++11 memory_order_acquire 237 return EBUSY; 238 } 239 } else { 240 return EBUSY; 241 } 242 243 rwlock->writer_thread_id = tid; 244 return 0; 245} 246 247 248int pthread_rwlock_unlock(pthread_rwlock_t* rwlock) { 249 int tid = __get_thread()->tid; 250 bool done = false; 251 do { 252 int32_t cur_state = rwlock->state; 253 if (cur_state == 0) { 254 return EPERM; 255 } 256 if (cur_state == -1) { 257 if (rwlock->writer_thread_id != tid) { 258 return EPERM; 259 } 260 // We're no longer the owner. 261 rwlock->writer_thread_id = 0; 262 // Change state from -1 to 0. 263 // We use __atomic_cmpxchg to achieve sequential consistency of the state store and 264 // the following pendingX loads. A simple store with memory_order_release semantics 265 // is not enough to guarantee that the pendingX loads are not reordered before the 266 // store (which may lead to a lost wakeup). 267 __atomic_cmpxchg(-1 /* cur_state*/, 0 /* new state */, &rwlock->state); // C++11 maybe memory_order_seq_cst? 268 269 // Wake any waiters. 270 if (__predict_false(rwlock->pending_readers > 0 || rwlock->pending_writers > 0)) { 271 __futex_wake_ex(&rwlock->state, rwlock_is_shared(rwlock), INT_MAX); 272 } 273 done = true; 274 } else { // cur_state > 0 275 // Reduce state by 1. 276 // See the above comment on why we need __atomic_cmpxchg. 277 done = __atomic_cmpxchg(cur_state, cur_state - 1, &rwlock->state) == 0; // C++11 maybe memory_order_seq_cst? 278 if (done && (cur_state - 1) == 0) { 279 // There are no more readers, wake any waiters. 280 if (__predict_false(rwlock->pending_readers > 0 || rwlock->pending_writers > 0)) { 281 __futex_wake_ex(&rwlock->state, rwlock_is_shared(rwlock), INT_MAX); 282 } 283 } 284 } 285 } while (!done); 286 287 return 0; 288} 289