pthread_rwlock.cpp revision 2fabea47ac9475bcc52aff0715819d18aa5bdf1d
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 <stdatomic.h> 31 32#include "pthread_internal.h" 33#include "private/bionic_futex.h" 34#include "private/bionic_time_conversions.h" 35 36/* Technical note: 37 * 38 * Possible states of a read/write lock: 39 * 40 * - no readers and no writer (unlocked) 41 * - one or more readers sharing the lock at the same time (read-locked) 42 * - one writer holding the lock (write-lock) 43 * 44 * Additionally: 45 * - trying to get the write-lock while there are any readers blocks 46 * - trying to get the read-lock while there is a writer blocks 47 * - a single thread can acquire the lock multiple times in read mode 48 * 49 * - Posix states that behavior is undefined (may deadlock) if a thread tries 50 * to acquire the lock 51 * - in write mode while already holding the lock (whether in read or write mode) 52 * - in read mode while already holding the lock in write mode. 53 * - This implementation will return EDEADLK in "write after write" and "read after 54 * write" cases and will deadlock in write after read case. 55 * 56 * TODO: As it stands now, pending_readers and pending_writers could be merged into a 57 * a single waiters variable. Keeping them separate adds a bit of clarity and keeps 58 * the door open for a writer-biased implementation. 59 * 60 */ 61 62#define RWLOCKATTR_DEFAULT 0 63#define RWLOCKATTR_SHARED_MASK 0x0010 64 65 66int pthread_rwlockattr_init(pthread_rwlockattr_t* attr) { 67 *attr = PTHREAD_PROCESS_PRIVATE; 68 return 0; 69} 70 71int pthread_rwlockattr_destroy(pthread_rwlockattr_t* attr) { 72 *attr = -1; 73 return 0; 74} 75 76int pthread_rwlockattr_setpshared(pthread_rwlockattr_t* attr, int pshared) { 77 switch (pshared) { 78 case PTHREAD_PROCESS_PRIVATE: 79 case PTHREAD_PROCESS_SHARED: 80 *attr = pshared; 81 return 0; 82 default: 83 return EINVAL; 84 } 85} 86 87int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t* attr, int* pshared) { 88 *pshared = *attr; 89 return 0; 90} 91 92struct pthread_rwlock_internal_t { 93 atomic_int state; // 0=unlock, -1=writer lock, +n=reader lock 94 atomic_int writer_thread_id; 95 atomic_uint pending_readers; 96 atomic_uint pending_writers; 97 int32_t attr; 98 99 bool process_shared() const { 100 return attr == PTHREAD_PROCESS_SHARED; 101 } 102 103#if defined(__LP64__) 104 char __reserved[36]; 105#else 106 char __reserved[20]; 107#endif 108}; 109 110static inline pthread_rwlock_internal_t* __get_internal_rwlock(pthread_rwlock_t* rwlock_interface) { 111 static_assert(sizeof(pthread_rwlock_t) == sizeof(pthread_rwlock_internal_t), 112 "pthread_rwlock_t should actually be pthread_rwlock_internal_t in implementation."); 113 return reinterpret_cast<pthread_rwlock_internal_t*>(rwlock_interface); 114} 115 116int pthread_rwlock_init(pthread_rwlock_t* rwlock_interface, const pthread_rwlockattr_t* attr) { 117 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 118 119 if (__predict_true(attr == NULL)) { 120 rwlock->attr = 0; 121 } else { 122 switch (*attr) { 123 case PTHREAD_PROCESS_SHARED: 124 case PTHREAD_PROCESS_PRIVATE: 125 rwlock->attr= *attr; 126 break; 127 default: 128 return EINVAL; 129 } 130 } 131 132 atomic_init(&rwlock->state, 0); 133 atomic_init(&rwlock->writer_thread_id, 0); 134 atomic_init(&rwlock->pending_readers, 0); 135 atomic_init(&rwlock->pending_writers, 0); 136 137 return 0; 138} 139 140int pthread_rwlock_destroy(pthread_rwlock_t* rwlock_interface) { 141 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 142 143 if (atomic_load_explicit(&rwlock->state, memory_order_relaxed) != 0) { 144 return EBUSY; 145 } 146 return 0; 147} 148 149static int __pthread_rwlock_timedrdlock(pthread_rwlock_internal_t* rwlock, 150 const timespec* abs_timeout_or_null) { 151 152 if (__predict_false(__get_thread()->tid == atomic_load_explicit(&rwlock->writer_thread_id, 153 memory_order_relaxed))) { 154 return EDEADLK; 155 } 156 157 while (true) { 158 int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed); 159 if (__predict_true(old_state >= 0)) { 160 if (atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, old_state + 1, 161 memory_order_acquire, memory_order_relaxed)) { 162 return 0; 163 } 164 } else { 165 timespec ts; 166 timespec* rel_timeout = NULL; 167 168 if (abs_timeout_or_null != NULL) { 169 rel_timeout = &ts; 170 if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, CLOCK_REALTIME)) { 171 return ETIMEDOUT; 172 } 173 } 174 175 // To avoid losing wake ups, the pending_readers increment should be observed before 176 // futex_wait by all threads. A seq_cst fence instead of a seq_cst operation is used 177 // here. Because only a seq_cst fence can ensure sequential consistency for non-atomic 178 // operations in futex_wait. 179 atomic_fetch_add_explicit(&rwlock->pending_readers, 1, memory_order_relaxed); 180 181 atomic_thread_fence(memory_order_seq_cst); 182 183 int ret = __futex_wait_ex(&rwlock->state, rwlock->process_shared(), old_state, 184 rel_timeout); 185 186 atomic_fetch_sub_explicit(&rwlock->pending_readers, 1, memory_order_relaxed); 187 188 if (ret == -ETIMEDOUT) { 189 return ETIMEDOUT; 190 } 191 } 192 } 193} 194 195static int __pthread_rwlock_timedwrlock(pthread_rwlock_internal_t* rwlock, 196 const timespec* abs_timeout_or_null) { 197 198 if (__predict_false(__get_thread()->tid == atomic_load_explicit(&rwlock->writer_thread_id, 199 memory_order_relaxed))) { 200 return EDEADLK; 201 } 202 203 while (true) { 204 int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed); 205 if (__predict_true(old_state == 0)) { 206 if (atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, -1, 207 memory_order_acquire, memory_order_relaxed)) { 208 // writer_thread_id is protected by rwlock and can only be modified in rwlock write 209 // owner thread. Other threads may read it for EDEADLK error checking, atomic operation 210 // is safe enough for it. 211 atomic_store_explicit(&rwlock->writer_thread_id, __get_thread()->tid, memory_order_relaxed); 212 return 0; 213 } 214 } else { 215 timespec ts; 216 timespec* rel_timeout = NULL; 217 218 if (abs_timeout_or_null != NULL) { 219 rel_timeout = &ts; 220 if (!timespec_from_absolute_timespec(*rel_timeout, *abs_timeout_or_null, CLOCK_REALTIME)) { 221 return ETIMEDOUT; 222 } 223 } 224 225 // To avoid losing wake ups, the pending_writers increment should be observed before 226 // futex_wait by all threads. A seq_cst fence instead of a seq_cst operation is used 227 // here. Because only a seq_cst fence can ensure sequential consistency for non-atomic 228 // operations in futex_wait. 229 atomic_fetch_add_explicit(&rwlock->pending_writers, 1, memory_order_relaxed); 230 231 atomic_thread_fence(memory_order_seq_cst); 232 233 int ret = __futex_wait_ex(&rwlock->state, rwlock->process_shared(), old_state, 234 rel_timeout); 235 236 atomic_fetch_sub_explicit(&rwlock->pending_writers, 1, memory_order_relaxed); 237 238 if (ret == -ETIMEDOUT) { 239 return ETIMEDOUT; 240 } 241 } 242 } 243} 244 245int pthread_rwlock_rdlock(pthread_rwlock_t* rwlock_interface) { 246 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 247 248 return __pthread_rwlock_timedrdlock(rwlock, NULL); 249} 250 251int pthread_rwlock_timedrdlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) { 252 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 253 254 return __pthread_rwlock_timedrdlock(rwlock, abs_timeout); 255} 256 257int pthread_rwlock_tryrdlock(pthread_rwlock_t* rwlock_interface) { 258 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 259 260 int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed); 261 262 while (old_state >= 0 && !atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, 263 old_state + 1, memory_order_acquire, memory_order_relaxed)) { 264 } 265 return (old_state >= 0) ? 0 : EBUSY; 266} 267 268int pthread_rwlock_wrlock(pthread_rwlock_t* rwlock_interface) { 269 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 270 271 return __pthread_rwlock_timedwrlock(rwlock, NULL); 272} 273 274int pthread_rwlock_timedwrlock(pthread_rwlock_t* rwlock_interface, const timespec* abs_timeout) { 275 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 276 277 return __pthread_rwlock_timedwrlock(rwlock, abs_timeout); 278} 279 280int pthread_rwlock_trywrlock(pthread_rwlock_t* rwlock_interface) { 281 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 282 283 int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed); 284 285 while (old_state == 0 && !atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, -1, 286 memory_order_acquire, memory_order_relaxed)) { 287 } 288 if (old_state == 0) { 289 atomic_store_explicit(&rwlock->writer_thread_id, __get_thread()->tid, memory_order_relaxed); 290 return 0; 291 } 292 return EBUSY; 293} 294 295 296int pthread_rwlock_unlock(pthread_rwlock_t* rwlock_interface) { 297 pthread_rwlock_internal_t* rwlock = __get_internal_rwlock(rwlock_interface); 298 299 int old_state = atomic_load_explicit(&rwlock->state, memory_order_relaxed); 300 if (__predict_false(old_state == 0)) { 301 return EPERM; 302 } else if (old_state == -1) { 303 if (atomic_load_explicit(&rwlock->writer_thread_id, memory_order_relaxed) != __get_thread()->tid) { 304 return EPERM; 305 } 306 // We're no longer the owner. 307 atomic_store_explicit(&rwlock->writer_thread_id, 0, memory_order_relaxed); 308 // Change state from -1 to 0. 309 atomic_store_explicit(&rwlock->state, 0, memory_order_release); 310 311 } else { // old_state > 0 312 // Reduce state by 1. 313 while (old_state > 0 && !atomic_compare_exchange_weak_explicit(&rwlock->state, &old_state, 314 old_state - 1, memory_order_release, memory_order_relaxed)) { 315 } 316 317 if (old_state <= 0) { 318 return EPERM; 319 } else if (old_state > 1) { 320 return 0; 321 } 322 // old_state = 1, which means the last reader calling unlock. It has to wake up waiters. 323 } 324 325 // If having waiters, wake up them. 326 // To avoid losing wake ups, the update of state should be observed before reading 327 // pending_readers/pending_writers by all threads. Use read locking as an example: 328 // read locking thread unlocking thread 329 // pending_readers++; state = 0; 330 // seq_cst fence seq_cst fence 331 // read state for futex_wait read pending_readers for futex_wake 332 // 333 // So when locking and unlocking threads are running in parallel, we will not get 334 // in a situation that the locking thread reads state as negative and needs to wait, 335 // while the unlocking thread reads pending_readers as zero and doesn't need to wake up waiters. 336 atomic_thread_fence(memory_order_seq_cst); 337 if (__predict_false(atomic_load_explicit(&rwlock->pending_readers, memory_order_relaxed) > 0 || 338 atomic_load_explicit(&rwlock->pending_writers, memory_order_relaxed) > 0)) { 339 __futex_wake_ex(&rwlock->state, rwlock->process_shared(), INT_MAX); 340 } 341 return 0; 342} 343