1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/util/nssrwlk.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,447 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "nssrwlk.h"
1.9 +#include "nspr.h"
1.10 +
1.11 +PR_BEGIN_EXTERN_C
1.12 +
1.13 +/*
1.14 + * Reader-writer lock
1.15 + */
1.16 +struct nssRWLockStr {
1.17 + PZLock * rw_lock;
1.18 + char * rw_name; /* lock name */
1.19 + PRUint32 rw_rank; /* rank of the lock */
1.20 + PRInt32 rw_writer_locks; /* == 0, if unlocked */
1.21 + PRInt32 rw_reader_locks; /* == 0, if unlocked */
1.22 + /* > 0 , # of read locks */
1.23 + PRUint32 rw_waiting_readers; /* number of waiting readers */
1.24 + PRUint32 rw_waiting_writers; /* number of waiting writers */
1.25 + PZCondVar * rw_reader_waitq; /* cvar for readers */
1.26 + PZCondVar * rw_writer_waitq; /* cvar for writers */
1.27 + PRThread * rw_owner; /* lock owner for write-lock */
1.28 + /* Non-null if write lock held. */
1.29 +};
1.30 +
1.31 +PR_END_EXTERN_C
1.32 +
1.33 +#include <string.h>
1.34 +
1.35 +#ifdef DEBUG_RANK_ORDER
1.36 +#define NSS_RWLOCK_RANK_ORDER_DEBUG /* enable deadlock detection using
1.37 + rank-order for locks
1.38 + */
1.39 +#endif
1.40 +
1.41 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.42 +
1.43 +static PRUintn nss_thread_rwlock_initialized;
1.44 +static PRUintn nss_thread_rwlock; /* TPD key for lock stack */
1.45 +static PRUintn nss_thread_rwlock_alloc_failed;
1.46 +
1.47 +#define _NSS_RWLOCK_RANK_ORDER_LIMIT 10
1.48 +
1.49 +typedef struct thread_rwlock_stack {
1.50 + PRInt32 trs_index; /* top of stack */
1.51 + NSSRWLock *trs_stack[_NSS_RWLOCK_RANK_ORDER_LIMIT]; /* stack of lock
1.52 + pointers */
1.53 +} thread_rwlock_stack;
1.54 +
1.55 +/* forward static declarations. */
1.56 +static PRUint32 nssRWLock_GetThreadRank(PRThread *me);
1.57 +static void nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock);
1.58 +static void nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock);
1.59 +static void nssRWLock_ReleaseLockStack(void *lock_stack);
1.60 +
1.61 +#endif
1.62 +
1.63 +#define UNTIL(x) while(!(x))
1.64 +
1.65 +/*
1.66 + * Reader/Writer Locks
1.67 + */
1.68 +
1.69 +/*
1.70 + * NSSRWLock_New
1.71 + * Create a reader-writer lock, with the given lock rank and lock name
1.72 + *
1.73 + */
1.74 +
1.75 +NSSRWLock *
1.76 +NSSRWLock_New(PRUint32 lock_rank, const char *lock_name)
1.77 +{
1.78 + NSSRWLock *rwlock;
1.79 +
1.80 + rwlock = PR_NEWZAP(NSSRWLock);
1.81 + if (rwlock == NULL)
1.82 + return NULL;
1.83 +
1.84 + rwlock->rw_lock = PZ_NewLock(nssILockRWLock);
1.85 + if (rwlock->rw_lock == NULL) {
1.86 + goto loser;
1.87 + }
1.88 + rwlock->rw_reader_waitq = PZ_NewCondVar(rwlock->rw_lock);
1.89 + if (rwlock->rw_reader_waitq == NULL) {
1.90 + goto loser;
1.91 + }
1.92 + rwlock->rw_writer_waitq = PZ_NewCondVar(rwlock->rw_lock);
1.93 + if (rwlock->rw_writer_waitq == NULL) {
1.94 + goto loser;
1.95 + }
1.96 + if (lock_name != NULL) {
1.97 + rwlock->rw_name = (char*) PR_Malloc(strlen(lock_name) + 1);
1.98 + if (rwlock->rw_name == NULL) {
1.99 + goto loser;
1.100 + }
1.101 + strcpy(rwlock->rw_name, lock_name);
1.102 + } else {
1.103 + rwlock->rw_name = NULL;
1.104 + }
1.105 + rwlock->rw_rank = lock_rank;
1.106 + rwlock->rw_waiting_readers = 0;
1.107 + rwlock->rw_waiting_writers = 0;
1.108 + rwlock->rw_reader_locks = 0;
1.109 + rwlock->rw_writer_locks = 0;
1.110 +
1.111 + return rwlock;
1.112 +
1.113 +loser:
1.114 + NSSRWLock_Destroy(rwlock);
1.115 + return(NULL);
1.116 +}
1.117 +
1.118 +/*
1.119 +** Destroy the given RWLock "lock".
1.120 +*/
1.121 +void
1.122 +NSSRWLock_Destroy(NSSRWLock *rwlock)
1.123 +{
1.124 + PR_ASSERT(rwlock != NULL);
1.125 + PR_ASSERT(rwlock->rw_waiting_readers == 0);
1.126 +
1.127 + /* XXX Shouldn't we lock the PZLock before destroying this?? */
1.128 +
1.129 + if (rwlock->rw_name)
1.130 + PR_Free(rwlock->rw_name);
1.131 + if (rwlock->rw_reader_waitq)
1.132 + PZ_DestroyCondVar(rwlock->rw_reader_waitq);
1.133 + if (rwlock->rw_writer_waitq)
1.134 + PZ_DestroyCondVar(rwlock->rw_writer_waitq);
1.135 + if (rwlock->rw_lock)
1.136 + PZ_DestroyLock(rwlock->rw_lock);
1.137 + PR_DELETE(rwlock);
1.138 +}
1.139 +
1.140 +/*
1.141 +** Read-lock the RWLock.
1.142 +*/
1.143 +void
1.144 +NSSRWLock_LockRead(NSSRWLock *rwlock)
1.145 +{
1.146 + PRThread *me = PR_GetCurrentThread();
1.147 +
1.148 + PZ_Lock(rwlock->rw_lock);
1.149 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.150 +
1.151 + /*
1.152 + * assert that rank ordering is not violated; the rank of 'rwlock' should
1.153 + * be equal to or greater than the highest rank of all the locks held by
1.154 + * the thread.
1.155 + */
1.156 + PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
1.157 + (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
1.158 +#endif
1.159 + /*
1.160 + * wait if write-locked or if a writer is waiting; preference for writers
1.161 + */
1.162 + UNTIL ( (rwlock->rw_owner == me) || /* I own it, or */
1.163 + ((rwlock->rw_owner == NULL) && /* no-one owns it, and */
1.164 + (rwlock->rw_waiting_writers == 0))) { /* no-one is waiting to own */
1.165 +
1.166 + rwlock->rw_waiting_readers++;
1.167 + PZ_WaitCondVar(rwlock->rw_reader_waitq, PR_INTERVAL_NO_TIMEOUT);
1.168 + rwlock->rw_waiting_readers--;
1.169 + }
1.170 + rwlock->rw_reader_locks++; /* Increment read-lock count */
1.171 +
1.172 + PZ_Unlock(rwlock->rw_lock);
1.173 +
1.174 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.175 + nssRWLock_SetThreadRank(me, rwlock);/* update thread's lock rank */
1.176 +#endif
1.177 +}
1.178 +
1.179 +/* Unlock a Read lock held on this RW lock.
1.180 +*/
1.181 +void
1.182 +NSSRWLock_UnlockRead(NSSRWLock *rwlock)
1.183 +{
1.184 + PZ_Lock(rwlock->rw_lock);
1.185 +
1.186 + PR_ASSERT(rwlock->rw_reader_locks > 0); /* lock must be read locked */
1.187 +
1.188 + if (( rwlock->rw_reader_locks > 0) && /* caller isn't screwey */
1.189 + (--rwlock->rw_reader_locks == 0) && /* not read locked any more */
1.190 + ( rwlock->rw_owner == NULL) && /* not write locked */
1.191 + ( rwlock->rw_waiting_writers > 0)) { /* someone's waiting. */
1.192 +
1.193 + PZ_NotifyCondVar(rwlock->rw_writer_waitq); /* wake him up. */
1.194 + }
1.195 +
1.196 + PZ_Unlock(rwlock->rw_lock);
1.197 +
1.198 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.199 + /*
1.200 + * update thread's lock rank
1.201 + */
1.202 + nssRWLock_UnsetThreadRank(me, rwlock);
1.203 +#endif
1.204 + return;
1.205 +}
1.206 +
1.207 +/*
1.208 +** Write-lock the RWLock.
1.209 +*/
1.210 +void
1.211 +NSSRWLock_LockWrite(NSSRWLock *rwlock)
1.212 +{
1.213 + PRThread *me = PR_GetCurrentThread();
1.214 +
1.215 + PZ_Lock(rwlock->rw_lock);
1.216 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.217 + /*
1.218 + * assert that rank ordering is not violated; the rank of 'rwlock' should
1.219 + * be equal to or greater than the highest rank of all the locks held by
1.220 + * the thread.
1.221 + */
1.222 + PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
1.223 + (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
1.224 +#endif
1.225 + /*
1.226 + * wait if read locked or write locked.
1.227 + */
1.228 + PR_ASSERT(rwlock->rw_reader_locks >= 0);
1.229 + PR_ASSERT(me != NULL);
1.230 +
1.231 + UNTIL ( (rwlock->rw_owner == me) || /* I own write lock, or */
1.232 + ((rwlock->rw_owner == NULL) && /* no writer and */
1.233 + (rwlock->rw_reader_locks == 0))) { /* no readers, either. */
1.234 +
1.235 + rwlock->rw_waiting_writers++;
1.236 + PZ_WaitCondVar(rwlock->rw_writer_waitq, PR_INTERVAL_NO_TIMEOUT);
1.237 + rwlock->rw_waiting_writers--;
1.238 + PR_ASSERT(rwlock->rw_reader_locks >= 0);
1.239 + }
1.240 +
1.241 + PR_ASSERT(rwlock->rw_reader_locks == 0);
1.242 + /*
1.243 + * apply write lock
1.244 + */
1.245 + rwlock->rw_owner = me;
1.246 + rwlock->rw_writer_locks++; /* Increment write-lock count */
1.247 +
1.248 + PZ_Unlock(rwlock->rw_lock);
1.249 +
1.250 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.251 + /*
1.252 + * update thread's lock rank
1.253 + */
1.254 + nssRWLock_SetThreadRank(me,rwlock);
1.255 +#endif
1.256 +}
1.257 +
1.258 +/* Unlock a Read lock held on this RW lock.
1.259 +*/
1.260 +void
1.261 +NSSRWLock_UnlockWrite(NSSRWLock *rwlock)
1.262 +{
1.263 + PRThread *me = PR_GetCurrentThread();
1.264 +
1.265 + PZ_Lock(rwlock->rw_lock);
1.266 + PR_ASSERT(rwlock->rw_owner == me); /* lock must be write-locked by me. */
1.267 + PR_ASSERT(rwlock->rw_writer_locks > 0); /* lock must be write locked */
1.268 +
1.269 + if ( rwlock->rw_owner == me && /* I own it, and */
1.270 + rwlock->rw_writer_locks > 0 && /* I own it, and */
1.271 + --rwlock->rw_writer_locks == 0) { /* I'm all done with it */
1.272 +
1.273 + rwlock->rw_owner = NULL; /* I don't own it any more. */
1.274 +
1.275 + /* Give preference to waiting writers. */
1.276 + if (rwlock->rw_waiting_writers > 0) {
1.277 + if (rwlock->rw_reader_locks == 0)
1.278 + PZ_NotifyCondVar(rwlock->rw_writer_waitq);
1.279 + } else if (rwlock->rw_waiting_readers > 0) {
1.280 + PZ_NotifyAllCondVar(rwlock->rw_reader_waitq);
1.281 + }
1.282 + }
1.283 + PZ_Unlock(rwlock->rw_lock);
1.284 +
1.285 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.286 + /*
1.287 + * update thread's lock rank
1.288 + */
1.289 + nssRWLock_UnsetThreadRank(me, rwlock);
1.290 +#endif
1.291 + return;
1.292 +}
1.293 +
1.294 +/* This is primarily for debugging, i.e. for inclusion in ASSERT calls. */
1.295 +PRBool
1.296 +NSSRWLock_HaveWriteLock(NSSRWLock *rwlock) {
1.297 + PRBool ownWriteLock;
1.298 + PRThread *me = PR_GetCurrentThread();
1.299 +
1.300 + /* This lock call isn't really necessary.
1.301 + ** If this thread is the owner, that fact cannot change during this call,
1.302 + ** because this thread is in this call.
1.303 + ** If this thread is NOT the owner, the owner could change, but it
1.304 + ** could not become this thread.
1.305 + */
1.306 +#if UNNECESSARY
1.307 + PZ_Lock(rwlock->rw_lock);
1.308 +#endif
1.309 + ownWriteLock = (PRBool)(me == rwlock->rw_owner);
1.310 +#if UNNECESSARY
1.311 + PZ_Unlock(rwlock->rw_lock);
1.312 +#endif
1.313 + return ownWriteLock;
1.314 +}
1.315 +
1.316 +#ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
1.317 +
1.318 +/*
1.319 + * nssRWLock_SetThreadRank
1.320 + * Set a thread's lock rank, which is the highest of the ranks of all
1.321 + * the locks held by the thread. Pointers to the locks are added to a
1.322 + * per-thread list, which is anchored off a thread-private data key.
1.323 + */
1.324 +
1.325 +static void
1.326 +nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock)
1.327 +{
1.328 + thread_rwlock_stack *lock_stack;
1.329 + PRStatus rv;
1.330 +
1.331 + /*
1.332 + * allocated thread-private-data for rwlock list, if not already allocated
1.333 + */
1.334 + if (!nss_thread_rwlock_initialized) {
1.335 + /*
1.336 + * allocate tpd, only if not failed already
1.337 + */
1.338 + if (!nss_thread_rwlock_alloc_failed) {
1.339 + if (PR_NewThreadPrivateIndex(&nss_thread_rwlock,
1.340 + nssRWLock_ReleaseLockStack)
1.341 + == PR_FAILURE) {
1.342 + nss_thread_rwlock_alloc_failed = 1;
1.343 + return;
1.344 + }
1.345 + } else
1.346 + return;
1.347 + }
1.348 + /*
1.349 + * allocate a lock stack
1.350 + */
1.351 + if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL) {
1.352 + lock_stack = (thread_rwlock_stack *)
1.353 + PR_CALLOC(1 * sizeof(thread_rwlock_stack));
1.354 + if (lock_stack) {
1.355 + rv = PR_SetThreadPrivate(nss_thread_rwlock, lock_stack);
1.356 + if (rv == PR_FAILURE) {
1.357 + PR_DELETE(lock_stack);
1.358 + nss_thread_rwlock_alloc_failed = 1;
1.359 + return;
1.360 + }
1.361 + } else {
1.362 + nss_thread_rwlock_alloc_failed = 1;
1.363 + return;
1.364 + }
1.365 + }
1.366 + /*
1.367 + * add rwlock to lock stack, if limit is not exceeded
1.368 + */
1.369 + if (lock_stack) {
1.370 + if (lock_stack->trs_index < _NSS_RWLOCK_RANK_ORDER_LIMIT)
1.371 + lock_stack->trs_stack[lock_stack->trs_index++] = rwlock;
1.372 + }
1.373 + nss_thread_rwlock_initialized = 1;
1.374 +}
1.375 +
1.376 +static void
1.377 +nssRWLock_ReleaseLockStack(void *lock_stack)
1.378 +{
1.379 + PR_ASSERT(lock_stack);
1.380 + PR_DELETE(lock_stack);
1.381 +}
1.382 +
1.383 +/*
1.384 + * nssRWLock_GetThreadRank
1.385 + *
1.386 + * return thread's lock rank. If thread-private-data for the lock
1.387 + * stack is not allocated, return NSS_RWLOCK_RANK_NONE.
1.388 + */
1.389 +
1.390 +static PRUint32
1.391 +nssRWLock_GetThreadRank(PRThread *me)
1.392 +{
1.393 + thread_rwlock_stack *lock_stack;
1.394 +
1.395 + if (nss_thread_rwlock_initialized) {
1.396 + if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL)
1.397 + return (NSS_RWLOCK_RANK_NONE);
1.398 + else
1.399 + return(lock_stack->trs_stack[lock_stack->trs_index - 1]->rw_rank);
1.400 +
1.401 + } else
1.402 + return (NSS_RWLOCK_RANK_NONE);
1.403 +}
1.404 +
1.405 +/*
1.406 + * nssRWLock_UnsetThreadRank
1.407 + *
1.408 + * remove the rwlock from the lock stack. Since locks may not be
1.409 + * unlocked in a FIFO order, the entire lock stack is searched.
1.410 + */
1.411 +
1.412 +static void
1.413 +nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock)
1.414 +{
1.415 + thread_rwlock_stack *lock_stack;
1.416 + int new_index = 0, index, done = 0;
1.417 +
1.418 + if (!nss_thread_rwlock_initialized)
1.419 + return;
1.420 +
1.421 + lock_stack = PR_GetThreadPrivate(nss_thread_rwlock);
1.422 +
1.423 + PR_ASSERT(lock_stack != NULL);
1.424 +
1.425 + index = lock_stack->trs_index - 1;
1.426 + while (index-- >= 0) {
1.427 + if ((lock_stack->trs_stack[index] == rwlock) && !done) {
1.428 + /*
1.429 + * reset the slot for rwlock
1.430 + */
1.431 + lock_stack->trs_stack[index] = NULL;
1.432 + done = 1;
1.433 + }
1.434 + /*
1.435 + * search for the lowest-numbered empty slot, above which there are
1.436 + * no non-empty slots
1.437 + */
1.438 + if ((lock_stack->trs_stack[index] != NULL) && !new_index)
1.439 + new_index = index + 1;
1.440 + if (done && new_index)
1.441 + break;
1.442 + }
1.443 + /*
1.444 + * set top of stack to highest numbered empty slot
1.445 + */
1.446 + lock_stack->trs_index = new_index;
1.447 +
1.448 +}
1.449 +
1.450 +#endif /* NSS_RWLOCK_RANK_ORDER_DEBUG */
