michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nssrwlk.h"
michael@0: #include "nspr.h"
michael@0: 
michael@0: PR_BEGIN_EXTERN_C
michael@0: 
michael@0: /*
michael@0:  * Reader-writer lock
michael@0:  */
michael@0: struct nssRWLockStr {
michael@0:     PZLock *        rw_lock;
michael@0:     char   *        rw_name;            /* lock name                    */
michael@0:     PRUint32        rw_rank;            /* rank of the lock             */
michael@0:     PRInt32         rw_writer_locks;    /* ==  0, if unlocked           */
michael@0:     PRInt32         rw_reader_locks;    /* ==  0, if unlocked           */
michael@0:                                         /* > 0  , # of read locks       */
michael@0:     PRUint32        rw_waiting_readers; /* number of waiting readers    */
michael@0:     PRUint32        rw_waiting_writers; /* number of waiting writers    */
michael@0:     PZCondVar *     rw_reader_waitq;    /* cvar for readers             */
michael@0:     PZCondVar *     rw_writer_waitq;    /* cvar for writers             */
michael@0:     PRThread  *     rw_owner;           /* lock owner for write-lock    */
michael@0:                                         /* Non-null if write lock held. */
michael@0: };
michael@0: 
michael@0: PR_END_EXTERN_C
michael@0: 
michael@0: #include <string.h>
michael@0: 
michael@0: #ifdef DEBUG_RANK_ORDER
michael@0: #define NSS_RWLOCK_RANK_ORDER_DEBUG /* enable deadlock detection using
michael@0:                                        rank-order for locks
michael@0:                                     */
michael@0: #endif
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0: 
michael@0: static PRUintn  nss_thread_rwlock_initialized;
michael@0: static PRUintn  nss_thread_rwlock;               /* TPD key for lock stack */
michael@0: static PRUintn  nss_thread_rwlock_alloc_failed;
michael@0: 
michael@0: #define _NSS_RWLOCK_RANK_ORDER_LIMIT 10
michael@0: 
michael@0: typedef struct thread_rwlock_stack {
michael@0:     PRInt32     trs_index;                                  /* top of stack */
michael@0:     NSSRWLock    *trs_stack[_NSS_RWLOCK_RANK_ORDER_LIMIT];  /* stack of lock
michael@0:                                                                pointers */
michael@0: } thread_rwlock_stack;
michael@0: 
michael@0: /* forward static declarations. */
michael@0: static PRUint32 nssRWLock_GetThreadRank(PRThread *me);
michael@0: static void     nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock);
michael@0: static void     nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock);
michael@0: static void     nssRWLock_ReleaseLockStack(void *lock_stack);
michael@0: 
michael@0: #endif
michael@0: 
michael@0: #define UNTIL(x) while(!(x))
michael@0: 
michael@0: /*
michael@0:  * Reader/Writer Locks
michael@0:  */
michael@0: 
michael@0: /*
michael@0:  * NSSRWLock_New
michael@0:  *      Create a reader-writer lock, with the given lock rank and lock name
michael@0:  *
michael@0:  */
michael@0: 
michael@0: NSSRWLock *
michael@0: NSSRWLock_New(PRUint32 lock_rank, const char *lock_name)
michael@0: {
michael@0:     NSSRWLock *rwlock;
michael@0: 
michael@0:     rwlock = PR_NEWZAP(NSSRWLock);
michael@0:     if (rwlock == NULL)
michael@0:         return NULL;
michael@0: 
michael@0:     rwlock->rw_lock = PZ_NewLock(nssILockRWLock);
michael@0:     if (rwlock->rw_lock == NULL) {
michael@0: 	goto loser;
michael@0:     }
michael@0:     rwlock->rw_reader_waitq = PZ_NewCondVar(rwlock->rw_lock);
michael@0:     if (rwlock->rw_reader_waitq == NULL) {
michael@0: 	goto loser;
michael@0:     }
michael@0:     rwlock->rw_writer_waitq = PZ_NewCondVar(rwlock->rw_lock);
michael@0:     if (rwlock->rw_writer_waitq == NULL) {
michael@0: 	goto loser;
michael@0:     }
michael@0:     if (lock_name != NULL) {
michael@0:         rwlock->rw_name = (char*) PR_Malloc(strlen(lock_name) + 1);
michael@0:         if (rwlock->rw_name == NULL) {
michael@0: 	    goto loser;
michael@0:         }
michael@0:         strcpy(rwlock->rw_name, lock_name);
michael@0:     } else {
michael@0:         rwlock->rw_name = NULL;
michael@0:     }
michael@0:     rwlock->rw_rank            = lock_rank;
michael@0:     rwlock->rw_waiting_readers = 0;
michael@0:     rwlock->rw_waiting_writers = 0;
michael@0:     rwlock->rw_reader_locks    = 0;
michael@0:     rwlock->rw_writer_locks    = 0;
michael@0: 
michael@0:     return rwlock;
michael@0: 
michael@0: loser:
michael@0:     NSSRWLock_Destroy(rwlock);
michael@0:     return(NULL);
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** Destroy the given RWLock "lock".
michael@0: */
michael@0: void
michael@0: NSSRWLock_Destroy(NSSRWLock *rwlock)
michael@0: {
michael@0:     PR_ASSERT(rwlock != NULL);
michael@0:     PR_ASSERT(rwlock->rw_waiting_readers == 0);
michael@0: 
michael@0:     /* XXX Shouldn't we lock the PZLock before destroying this?? */
michael@0: 
michael@0:     if (rwlock->rw_name)
michael@0:     	PR_Free(rwlock->rw_name);
michael@0:     if (rwlock->rw_reader_waitq)
michael@0:     	PZ_DestroyCondVar(rwlock->rw_reader_waitq);
michael@0:     if (rwlock->rw_writer_waitq)
michael@0: 	PZ_DestroyCondVar(rwlock->rw_writer_waitq);
michael@0:     if (rwlock->rw_lock)
michael@0: 	PZ_DestroyLock(rwlock->rw_lock);
michael@0:     PR_DELETE(rwlock);
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** Read-lock the RWLock.
michael@0: */
michael@0: void
michael@0: NSSRWLock_LockRead(NSSRWLock *rwlock)
michael@0: {
michael@0:     PRThread *me = PR_GetCurrentThread();
michael@0: 
michael@0:     PZ_Lock(rwlock->rw_lock);
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0: 
michael@0:     /*
michael@0:      * assert that rank ordering is not violated; the rank of 'rwlock' should
michael@0:      * be equal to or greater than the highest rank of all the locks held by
michael@0:      * the thread.
michael@0:      */
michael@0:     PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
michael@0:               (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
michael@0: #endif
michael@0:     /*
michael@0:      * wait if write-locked or if a writer is waiting; preference for writers
michael@0:      */
michael@0:     UNTIL ( (rwlock->rw_owner == me) ||		  /* I own it, or        */
michael@0: 	   ((rwlock->rw_owner == NULL) &&	  /* no-one owns it, and */
michael@0: 	    (rwlock->rw_waiting_writers == 0))) { /* no-one is waiting to own */
michael@0: 
michael@0: 	rwlock->rw_waiting_readers++;
michael@0: 	PZ_WaitCondVar(rwlock->rw_reader_waitq, PR_INTERVAL_NO_TIMEOUT);
michael@0: 	rwlock->rw_waiting_readers--;
michael@0:     }
michael@0:     rwlock->rw_reader_locks++; 		/* Increment read-lock count */
michael@0: 
michael@0:     PZ_Unlock(rwlock->rw_lock);
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0:     nssRWLock_SetThreadRank(me, rwlock);/* update thread's lock rank */
michael@0: #endif
michael@0: }
michael@0: 
michael@0: /* Unlock a Read lock held on this RW lock.
michael@0: */
michael@0: void
michael@0: NSSRWLock_UnlockRead(NSSRWLock *rwlock)
michael@0: {
michael@0:     PZ_Lock(rwlock->rw_lock);
michael@0: 
michael@0:     PR_ASSERT(rwlock->rw_reader_locks > 0); /* lock must be read locked */
michael@0: 
michael@0:     if ((  rwlock->rw_reader_locks  > 0)  &&	/* caller isn't screwey */
michael@0:         (--rwlock->rw_reader_locks == 0)  &&	/* not read locked any more */
michael@0: 	(  rwlock->rw_owner        == NULL) &&	/* not write locked */
michael@0: 	(  rwlock->rw_waiting_writers > 0)) {	/* someone's waiting. */
michael@0: 
michael@0: 	PZ_NotifyCondVar(rwlock->rw_writer_waitq); /* wake him up. */
michael@0:     }
michael@0: 
michael@0:     PZ_Unlock(rwlock->rw_lock);
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0:     /*
michael@0:      * update thread's lock rank
michael@0:      */
michael@0:     nssRWLock_UnsetThreadRank(me, rwlock);
michael@0: #endif
michael@0:     return;
michael@0: }
michael@0: 
michael@0: /*
michael@0: ** Write-lock the RWLock.
michael@0: */
michael@0: void
michael@0: NSSRWLock_LockWrite(NSSRWLock *rwlock)
michael@0: {
michael@0:     PRThread *me = PR_GetCurrentThread();
michael@0: 
michael@0:     PZ_Lock(rwlock->rw_lock);
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0:     /*
michael@0:      * assert that rank ordering is not violated; the rank of 'rwlock' should
michael@0:      * be equal to or greater than the highest rank of all the locks held by
michael@0:      * the thread.
michael@0:      */
michael@0:     PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
michael@0:                     (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
michael@0: #endif
michael@0:     /*
michael@0:      * wait if read locked or write locked.
michael@0:      */
michael@0:     PR_ASSERT(rwlock->rw_reader_locks >= 0);
michael@0:     PR_ASSERT(me != NULL);
michael@0: 
michael@0:     UNTIL ( (rwlock->rw_owner == me) ||           /* I own write lock, or */
michael@0: 	   ((rwlock->rw_owner == NULL) &&	  /* no writer   and */
michael@0: 	    (rwlock->rw_reader_locks == 0))) {    /* no readers, either. */
michael@0: 
michael@0:         rwlock->rw_waiting_writers++;
michael@0:         PZ_WaitCondVar(rwlock->rw_writer_waitq, PR_INTERVAL_NO_TIMEOUT);
michael@0:         rwlock->rw_waiting_writers--;
michael@0: 	PR_ASSERT(rwlock->rw_reader_locks >= 0);
michael@0:     }
michael@0: 
michael@0:     PR_ASSERT(rwlock->rw_reader_locks == 0);
michael@0:     /*
michael@0:      * apply write lock
michael@0:      */
michael@0:     rwlock->rw_owner = me;
michael@0:     rwlock->rw_writer_locks++; 		/* Increment write-lock count */
michael@0: 
michael@0:     PZ_Unlock(rwlock->rw_lock);
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0:     /*
michael@0:      * update thread's lock rank
michael@0:      */
michael@0:     nssRWLock_SetThreadRank(me,rwlock);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: /* Unlock a Read lock held on this RW lock.
michael@0: */
michael@0: void
michael@0: NSSRWLock_UnlockWrite(NSSRWLock *rwlock)
michael@0: {
michael@0:     PRThread *me = PR_GetCurrentThread();
michael@0: 
michael@0:     PZ_Lock(rwlock->rw_lock);
michael@0:     PR_ASSERT(rwlock->rw_owner == me); /* lock must be write-locked by me.  */
michael@0:     PR_ASSERT(rwlock->rw_writer_locks > 0); /* lock must be write locked */
michael@0: 
michael@0:     if (  rwlock->rw_owner        == me  &&	/* I own it, and            */
michael@0:           rwlock->rw_writer_locks  > 0   &&	/* I own it, and            */
michael@0:         --rwlock->rw_writer_locks == 0) {	/* I'm all done with it     */
michael@0: 
michael@0: 	rwlock->rw_owner = NULL;		/* I don't own it any more. */
michael@0: 
michael@0: 	/* Give preference to waiting writers. */
michael@0: 	if (rwlock->rw_waiting_writers > 0) {
michael@0: 	    if (rwlock->rw_reader_locks == 0)
michael@0: 		PZ_NotifyCondVar(rwlock->rw_writer_waitq);
michael@0: 	} else if (rwlock->rw_waiting_readers > 0) {
michael@0: 	    PZ_NotifyAllCondVar(rwlock->rw_reader_waitq);
michael@0: 	}
michael@0:     }
michael@0:     PZ_Unlock(rwlock->rw_lock);
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0:     /*
michael@0:      * update thread's lock rank
michael@0:      */
michael@0:     nssRWLock_UnsetThreadRank(me, rwlock);
michael@0: #endif
michael@0:     return;
michael@0: }
michael@0: 
michael@0: /* This is primarily for debugging, i.e. for inclusion in ASSERT calls. */
michael@0: PRBool
michael@0: NSSRWLock_HaveWriteLock(NSSRWLock *rwlock) {
michael@0:     PRBool ownWriteLock;
michael@0:     PRThread *me = PR_GetCurrentThread();
michael@0: 
michael@0:     /* This lock call isn't really necessary.
michael@0:     ** If this thread is the owner, that fact cannot change during this call,
michael@0:     ** because this thread is in this call.
michael@0:     ** If this thread is NOT the owner, the owner could change, but it 
michael@0:     ** could not become this thread.  
michael@0:     */
michael@0: #if UNNECESSARY
michael@0:     PZ_Lock(rwlock->rw_lock);	
michael@0: #endif
michael@0:     ownWriteLock = (PRBool)(me == rwlock->rw_owner);
michael@0: #if UNNECESSARY
michael@0:     PZ_Unlock(rwlock->rw_lock);
michael@0: #endif
michael@0:     return ownWriteLock;
michael@0: }
michael@0: 
michael@0: #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
michael@0: 
michael@0: /*
michael@0:  * nssRWLock_SetThreadRank
michael@0:  *      Set a thread's lock rank, which is the highest of the ranks of all
michael@0:  *      the locks held by the thread. Pointers to the locks are added to a
michael@0:  *      per-thread list, which is anchored off a thread-private data key.
michael@0:  */
michael@0: 
michael@0: static void
michael@0: nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock)
michael@0: {
michael@0:     thread_rwlock_stack *lock_stack;
michael@0:     PRStatus rv;
michael@0: 
michael@0:     /*
michael@0:      * allocated thread-private-data for rwlock list, if not already allocated
michael@0:      */
michael@0:     if (!nss_thread_rwlock_initialized) {
michael@0:         /*
michael@0:          * allocate tpd, only if not failed already
michael@0:          */
michael@0:         if (!nss_thread_rwlock_alloc_failed) {
michael@0:             if (PR_NewThreadPrivateIndex(&nss_thread_rwlock,
michael@0:                                         nssRWLock_ReleaseLockStack)
michael@0:                                                 == PR_FAILURE) {
michael@0:                 nss_thread_rwlock_alloc_failed = 1;
michael@0:                 return;
michael@0:             }
michael@0:         } else
michael@0:             return;
michael@0:     }
michael@0:     /*
michael@0:      * allocate a lock stack
michael@0:      */
michael@0:     if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL) {
michael@0:         lock_stack = (thread_rwlock_stack *)
michael@0:                         PR_CALLOC(1 * sizeof(thread_rwlock_stack));
michael@0:         if (lock_stack) {
michael@0:             rv = PR_SetThreadPrivate(nss_thread_rwlock, lock_stack);
michael@0:             if (rv == PR_FAILURE) {
michael@0:                 PR_DELETE(lock_stack);
michael@0:                 nss_thread_rwlock_alloc_failed = 1;
michael@0:                 return;
michael@0:             }
michael@0:         } else {
michael@0:             nss_thread_rwlock_alloc_failed = 1;
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0:     /*
michael@0:      * add rwlock to lock stack, if limit is not exceeded
michael@0:      */
michael@0:     if (lock_stack) {
michael@0:         if (lock_stack->trs_index < _NSS_RWLOCK_RANK_ORDER_LIMIT)
michael@0:             lock_stack->trs_stack[lock_stack->trs_index++] = rwlock;
michael@0:     }
michael@0:     nss_thread_rwlock_initialized = 1;
michael@0: }
michael@0: 
michael@0: static void
michael@0: nssRWLock_ReleaseLockStack(void *lock_stack)
michael@0: {
michael@0:     PR_ASSERT(lock_stack);
michael@0:     PR_DELETE(lock_stack);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * nssRWLock_GetThreadRank
michael@0:  *
michael@0:  *      return thread's lock rank. If thread-private-data for the lock
michael@0:  *      stack is not allocated, return NSS_RWLOCK_RANK_NONE.
michael@0:  */
michael@0: 
michael@0: static PRUint32
michael@0: nssRWLock_GetThreadRank(PRThread *me)
michael@0: {
michael@0:     thread_rwlock_stack *lock_stack;
michael@0: 
michael@0:     if (nss_thread_rwlock_initialized) {
michael@0:         if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL)
michael@0:             return (NSS_RWLOCK_RANK_NONE);
michael@0:         else
michael@0:             return(lock_stack->trs_stack[lock_stack->trs_index - 1]->rw_rank);
michael@0: 
michael@0:     } else
michael@0:             return (NSS_RWLOCK_RANK_NONE);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * nssRWLock_UnsetThreadRank
michael@0:  *
michael@0:  *      remove the rwlock from the lock stack. Since locks may not be
michael@0:  *      unlocked in a FIFO order, the entire lock stack is searched.
michael@0:  */
michael@0: 
michael@0: static void
michael@0: nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock)
michael@0: {
michael@0:     thread_rwlock_stack *lock_stack;
michael@0:     int new_index = 0, index, done = 0;
michael@0: 
michael@0:     if (!nss_thread_rwlock_initialized)
michael@0:         return;
michael@0: 
michael@0:     lock_stack = PR_GetThreadPrivate(nss_thread_rwlock);
michael@0: 
michael@0:     PR_ASSERT(lock_stack != NULL);
michael@0: 
michael@0:     index = lock_stack->trs_index - 1;
michael@0:     while (index-- >= 0) {
michael@0:         if ((lock_stack->trs_stack[index] == rwlock) && !done)  {
michael@0:             /*
michael@0:              * reset the slot for rwlock
michael@0:              */
michael@0:             lock_stack->trs_stack[index] = NULL;
michael@0:             done = 1;
michael@0:         }
michael@0:         /*
michael@0:          * search for the lowest-numbered empty slot, above which there are
michael@0:          * no non-empty slots
michael@0:          */
michael@0:         if ((lock_stack->trs_stack[index] != NULL) && !new_index)
michael@0:             new_index = index + 1;
michael@0:         if (done && new_index)
michael@0:             break;
michael@0:     }
michael@0:     /*
michael@0:      * set top of stack to highest numbered empty slot
michael@0:      */
michael@0:     lock_stack->trs_index = new_index;
michael@0: 
michael@0: }
michael@0: 
michael@0: #endif  /* NSS_RWLOCK_RANK_ORDER_DEBUG */