OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright 2015 The Native Client Authors. All rights reserved. |
| 3 * Use of this source code is governed by a BSD-style license that can be |
| 4 * found in the LICENSE file. |
| 5 */ |
| 6 |
| 7 /* |
| 8 * Native Client rwlock implementation |
| 9 * |
| 10 * This implementation is a 'write-preferring' reader-writer lock which |
| 11 * avoids writer starvation by preventing readers from acquiring the lock |
| 12 * while there are waiting writers (with an exception to prevent deadlocks |
| 13 * in the case of recursive read lock (see read_lock_available)). See: |
| 14 * http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock |
| 15 * |
| 16 * The thundering herd problem is avoided (at least for waiting writers) |
| 17 * by only waking a single writer at a time. |
| 18 */ |
| 19 |
| 20 #include <errno.h> |
| 21 |
| 22 #include "native_client/src/untrusted/pthread/pthread.h" |
| 23 #include "native_client/src/untrusted/pthread/pthread_internal.h" |
| 24 #include "native_client/src/untrusted/pthread/pthread_types.h" |
| 25 |
| 26 int pthread_rwlockattr_init(pthread_rwlockattr_t *attr) { |
| 27 attr->type = PTHREAD_PROCESS_PRIVATE; |
| 28 return 0; |
| 29 } |
| 30 |
| 31 int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr) { |
| 32 return 0; |
| 33 } |
| 34 |
| 35 int pthread_rwlockattr_getpshared(const pthread_rwlockattr_t *attr, |
| 36 int *pshared) { |
| 37 *pshared = attr->type; |
| 38 return 0; |
| 39 } |
| 40 |
| 41 int pthread_rwlockattr_setpshared(pthread_rwlockattr_t *attr, int pshared) { |
| 42 if (pshared != PTHREAD_PROCESS_PRIVATE && pshared != PTHREAD_PROCESS_SHARED) |
| 43 return EINVAL; |
| 44 attr->type = pshared; |
| 45 return 0; |
| 46 } |
| 47 |
| 48 int pthread_rwlock_init(pthread_rwlock_t *rwlock, |
| 49 const pthread_rwlockattr_t *attr) { |
| 50 if (attr != NULL && attr->type != PTHREAD_PROCESS_PRIVATE) |
| 51 return EINVAL; |
| 52 rwlock->writer_thread_id = NACL_PTHREAD_ILLEGAL_THREAD_ID; |
| 53 rwlock->writers_waiting = 0; |
| 54 rwlock->reader_count = 0; |
| 55 int rc = pthread_mutex_init(&rwlock->mutex, NULL); |
| 56 if (rc != 0) |
| 57 return rc; |
| 58 rc = pthread_cond_init(&rwlock->write_possible, NULL); |
| 59 if (rc != 0) |
| 60 return rc; |
| 61 return pthread_cond_init(&rwlock->read_possible, NULL); |
| 62 } |
| 63 |
| 64 /* |
| 65 * Helper function used by waiting writers to determine if they can take |
| 66 * the lock. The rwlock->mutex must be held when calling this function. |
| 67 * Returns 1 if the write lock can be taken, 0 if it can't. |
| 68 */ |
| 69 static inline int write_lock_available(pthread_rwlock_t *rwlock) { |
| 70 /* |
| 71 * Write lock is available if there is no current writer and no current |
| 72 * readers. |
| 73 */ |
| 74 if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) |
| 75 return 0; |
| 76 if (rwlock->reader_count > 0) |
| 77 return 0; |
| 78 return 1; |
| 79 } |
| 80 |
| 81 /* |
| 82 * Helper function used by waiting readers to determine if they can take |
| 83 * the lock. The rwlock->mutex must be held when calling this function. |
| 84 * Returns 1 if the write lock can be taken, 0 if it can't. |
| 85 */ |
| 86 static inline int read_lock_available(pthread_rwlock_t *rwlock) { |
| 87 /* |
| 88 * Read lock is unavailable if there is a current writer. |
| 89 */ |
| 90 if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) |
| 91 return 0; |
| 92 |
| 93 /* |
| 94 * Attempt to reduce writer starvation by blocking readers when there |
| 95 * is a waiting writer. However don't do this if the current thread |
| 96 * already holds one or more rdlocks in order to allow for recursive |
| 97 * rdlocks. See: http://stackoverflow.com/questions/2190090/ |
| 98 * how-to-prevent-writer-starvation-in-a-read-write-lock-in-pthreads |
| 99 */ |
| 100 if (rwlock->writers_waiting > 0 && __nc_get_tdb()->rdlock_count == 0) |
| 101 return 0; |
| 102 return 1; |
| 103 } |
| 104 |
| 105 /* |
| 106 * Internal function used to acquire the read lock. |
| 107 * This operates in three different ways in order to implement the three public |
| 108 * functions: |
| 109 * pthread_rwlock_rdlock |
| 110 * pthread_rwlock_tryrdlock |
| 111 * pthread_rwlock_timedrdlock |
| 112 */ |
| 113 static int rdlock_internal(pthread_rwlock_t *rwlock, |
| 114 const struct timespec *abs_timeout, |
| 115 int try_only) { |
| 116 int rc2; |
| 117 int rc = pthread_mutex_lock(&rwlock->mutex); |
| 118 if (rc != 0) |
| 119 return rc; |
| 120 |
| 121 /* |
| 122 * Wait repeatedly until the write preconditions are met. |
| 123 * In theory this loop should only execute once because the preconditions |
| 124 * should always be true when the condition is signaled. |
| 125 */ |
| 126 while (!read_lock_available(rwlock)) { |
| 127 if (try_only) { |
| 128 rc = EBUSY; |
| 129 } else if (abs_timeout != NULL) { |
| 130 rc = pthread_cond_timedwait(&rwlock->read_possible, |
| 131 &rwlock->mutex, |
| 132 abs_timeout); |
| 133 } else { |
| 134 rc = pthread_cond_wait(&rwlock->read_possible, &rwlock->mutex); |
| 135 } |
| 136 if (rc != 0) |
| 137 goto done; |
| 138 } |
| 139 |
| 140 /* Acquire the read lock. */ |
| 141 rwlock->reader_count++; |
| 142 __nc_get_tdb()->rdlock_count++; |
| 143 done: |
| 144 rc2 = pthread_mutex_unlock(&rwlock->mutex); |
| 145 return rc == 0 ? rc2 : rc; |
| 146 } |
| 147 |
| 148 /* |
| 149 * Internal function used to acquire the write lock. |
| 150 * This operates in three different ways in order to implement the three public |
| 151 * functions: |
| 152 * pthread_rwlock_wrlock |
| 153 * pthread_rwlock_trywrlock |
| 154 * pthread_rwlock_timedwrlock |
| 155 */ |
| 156 static int rwlock_internal(pthread_rwlock_t *rwlock, |
| 157 const struct timespec *abs_timeout, |
| 158 int try_only) { |
| 159 int rc2; |
| 160 int rc = pthread_mutex_lock(&rwlock->mutex); |
| 161 if (rc != 0) |
| 162 return rc; |
| 163 |
| 164 /* Wait repeatedly until the write preconditions are met */ |
| 165 while (!write_lock_available(rwlock)) { |
| 166 if (try_only) { |
| 167 rc = EBUSY; |
| 168 } else { |
| 169 /* |
| 170 * Before waiting (and releasing the lock) we increment the |
| 171 * waiting_writers count so the unlocking code knows to wake |
| 172 * a writer first (before any waiting readers). |
| 173 */ |
| 174 rwlock->writers_waiting++; |
| 175 if (abs_timeout != NULL) { |
| 176 rc = pthread_cond_timedwait(&rwlock->write_possible, |
| 177 &rwlock->mutex, |
| 178 abs_timeout); |
| 179 } else { |
| 180 rc = pthread_cond_wait(&rwlock->write_possible, |
| 181 &rwlock->mutex); |
| 182 } |
| 183 rwlock->writers_waiting--; |
| 184 } |
| 185 if (rc != 0) |
| 186 goto done; |
| 187 } |
| 188 |
| 189 /* Acquire the write lock. */ |
| 190 rwlock->writer_thread_id = pthread_self(); |
| 191 done: |
| 192 rc2 = pthread_mutex_unlock(&rwlock->mutex); |
| 193 return rc == 0 ? rc2 : rc; |
| 194 } |
| 195 |
| 196 int pthread_rwlock_timedrdlock(pthread_rwlock_t *rwlock, |
| 197 const struct timespec *abs_timeout) { |
| 198 return rdlock_internal(rwlock, abs_timeout, 0); |
| 199 } |
| 200 |
| 201 int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock) { |
| 202 return rdlock_internal(rwlock, NULL, 0); |
| 203 } |
| 204 |
| 205 int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock) { |
| 206 return rdlock_internal(rwlock, NULL, 1); |
| 207 } |
| 208 |
| 209 int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock) { |
| 210 return rwlock_internal(rwlock, NULL, 0); |
| 211 } |
| 212 |
| 213 int pthread_rwlock_timedwrlock(pthread_rwlock_t *rwlock, |
| 214 const struct timespec *abs_timeout) { |
| 215 return rwlock_internal(rwlock, abs_timeout, 0); |
| 216 } |
| 217 |
| 218 int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock) { |
| 219 return rwlock_internal(rwlock, NULL, 1); |
| 220 } |
| 221 |
| 222 int pthread_rwlock_unlock(pthread_rwlock_t *rwlock) { |
| 223 int rc2; |
| 224 int rc = pthread_mutex_lock(&rwlock->mutex); |
| 225 if (rc != 0) |
| 226 return rc; |
| 227 |
| 228 if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) { |
| 229 /* The write lock is held. Ensure it's the current thread that holds it. */ |
| 230 if (rwlock->writer_thread_id != pthread_self()) { |
| 231 rc = EPERM; |
| 232 goto done; |
| 233 } |
| 234 |
| 235 /* Release write lock. */ |
| 236 rwlock->writer_thread_id = NACL_PTHREAD_ILLEGAL_THREAD_ID; |
| 237 if (rwlock->writers_waiting > 0) { |
| 238 /* Wake a waiting writer if there is one. */ |
| 239 rc = pthread_cond_signal(&rwlock->write_possible); |
| 240 } else { |
| 241 /* |
| 242 * Otherwise wake all waiting readers. All of them should be able |
| 243 * to make progress now that the write lock is no longer held. |
| 244 */ |
| 245 rc = pthread_cond_broadcast(&rwlock->read_possible); |
| 246 } |
| 247 } else { |
| 248 if (rwlock->reader_count == 0) { |
| 249 rc = EPERM; |
| 250 goto done; |
| 251 } |
| 252 |
| 253 /* Release read lock. */ |
| 254 rwlock->reader_count--; |
| 255 __nc_get_tdb()->rdlock_count--; |
| 256 if (rwlock->reader_count == 0 && rwlock->writers_waiting > 0) { |
| 257 /* Wake a waiting writer. */ |
| 258 rc = pthread_cond_signal(&rwlock->write_possible); |
| 259 } |
| 260 } |
| 261 |
| 262 done: |
| 263 rc2 = pthread_mutex_unlock(&rwlock->mutex); |
| 264 return rc == 0 ? rc2 : rc; |
| 265 } |
| 266 |
| 267 int pthread_rwlock_destroy(pthread_rwlock_t *rwlock) { |
| 268 /* Return EBUSY if another thread holds the mutex. */ |
| 269 int rc = pthread_mutex_trylock(&rwlock->mutex); |
| 270 if (rc != 0) { |
| 271 return rc; |
| 272 } |
| 273 |
| 274 /* Return EBUSY if there are active readers or an active writer. */ |
| 275 if (rwlock->reader_count != 0) { |
| 276 pthread_mutex_unlock(&rwlock->mutex); |
| 277 return EBUSY; |
| 278 } |
| 279 if (rwlock->writer_thread_id != NACL_PTHREAD_ILLEGAL_THREAD_ID) { |
| 280 pthread_mutex_unlock(&rwlock->mutex); |
| 281 return EBUSY; |
| 282 } |
| 283 |
| 284 int rc1 = pthread_cond_destroy(&rwlock->write_possible); |
| 285 int rc2 = pthread_cond_destroy(&rwlock->read_possible); |
| 286 |
| 287 /* Finally unlock the mutex and destroy it. */ |
| 288 pthread_mutex_unlock(&rwlock->mutex); |
| 289 int rc3 = pthread_mutex_destroy(&rwlock->mutex); |
| 290 if (rc1 != 0) |
| 291 return rc1; |
| 292 if (rc2 != 0) |
| 293 return rc2; |
| 294 return rc3; |
| 295 } |
OLD | NEW |