Back to index

lightning-sunbird  0.9+nobinonly
nssrwlk.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 #include "nssrwlk.h"
00038 #include "nspr.h"
00039 
00040 PR_BEGIN_EXTERN_C
00041 
00042 /*
00043  * Reader-writer lock
00044  */
00045 struct nssRWLockStr {
00046     PZLock *        rw_lock;
00047     char   *        rw_name;            /* lock name                    */
00048     PRUint32        rw_rank;            /* rank of the lock             */
00049     PRInt32         rw_writer_locks;    /* ==  0, if unlocked           */
00050     PRInt32         rw_reader_locks;    /* ==  0, if unlocked           */
00051                                         /* > 0  , # of read locks       */
00052     PRUint32        rw_waiting_readers; /* number of waiting readers    */
00053     PRUint32        rw_waiting_writers; /* number of waiting writers    */
00054     PZCondVar *     rw_reader_waitq;    /* cvar for readers             */
00055     PZCondVar *     rw_writer_waitq;    /* cvar for writers             */
00056     PRThread  *     rw_owner;           /* lock owner for write-lock    */
00057                                         /* Non-null if write lock held. */
00058 };
00059 
00060 PR_END_EXTERN_C
00061 
00062 #include <string.h>
00063 
00064 #ifdef DEBUG_RANK_ORDER
00065 #define NSS_RWLOCK_RANK_ORDER_DEBUG /* enable deadlock detection using
00066                                        rank-order for locks
00067                                     */
00068 #endif
00069 
00070 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00071 
00072 static PRUintn  nss_thread_rwlock_initialized;
00073 static PRUintn  nss_thread_rwlock;               /* TPD key for lock stack */
00074 static PRUintn  nss_thread_rwlock_alloc_failed;
00075 
00076 #define _NSS_RWLOCK_RANK_ORDER_LIMIT 10
00077 
00078 typedef struct thread_rwlock_stack {
00079     PRInt32     trs_index;                                  /* top of stack */
00080     NSSRWLock    *trs_stack[_NSS_RWLOCK_RANK_ORDER_LIMIT];  /* stack of lock
00081                                                                pointers */
00082 } thread_rwlock_stack;
00083 
00084 /* forward static declarations. */
00085 static PRUint32 nssRWLock_GetThreadRank(PRThread *me);
00086 static void     nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock);
00087 static void     nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock);
00088 static void     nssRWLock_ReleaseLockStack(void *lock_stack);
00089 
00090 #endif
00091 
00092 #define UNTIL(x) while(!(x))
00093 
00094 /*
00095  * Reader/Writer Locks
00096  */
00097 
00098 /*
00099  * NSSRWLock_New
00100  *      Create a reader-writer lock, with the given lock rank and lock name
00101  *
00102  */
00103 
00104 PR_IMPLEMENT(NSSRWLock *)
00105 NSSRWLock_New(PRUint32 lock_rank, const char *lock_name)
00106 {
00107     NSSRWLock *rwlock;
00108 
00109     rwlock = PR_NEWZAP(NSSRWLock);
00110     if (rwlock == NULL)
00111         return NULL;
00112 
00113     rwlock->rw_lock = PZ_NewLock(nssILockRWLock);
00114     if (rwlock->rw_lock == NULL) {
00115        goto loser;
00116     }
00117     rwlock->rw_reader_waitq = PZ_NewCondVar(rwlock->rw_lock);
00118     if (rwlock->rw_reader_waitq == NULL) {
00119        goto loser;
00120     }
00121     rwlock->rw_writer_waitq = PZ_NewCondVar(rwlock->rw_lock);
00122     if (rwlock->rw_writer_waitq == NULL) {
00123        goto loser;
00124     }
00125     if (lock_name != NULL) {
00126         rwlock->rw_name = (char*) PR_Malloc(strlen(lock_name) + 1);
00127         if (rwlock->rw_name == NULL) {
00128            goto loser;
00129         }
00130         strcpy(rwlock->rw_name, lock_name);
00131     } else {
00132         rwlock->rw_name = NULL;
00133     }
00134     rwlock->rw_rank            = lock_rank;
00135     rwlock->rw_waiting_readers = 0;
00136     rwlock->rw_waiting_writers = 0;
00137     rwlock->rw_reader_locks    = 0;
00138     rwlock->rw_writer_locks    = 0;
00139 
00140     return rwlock;
00141 
00142 loser:
00143     NSSRWLock_Destroy(rwlock);
00144     return(NULL);
00145 }
00146 
00147 /*
00148 ** Destroy the given RWLock "lock".
00149 */
00150 PR_IMPLEMENT(void)
00151 NSSRWLock_Destroy(NSSRWLock *rwlock)
00152 {
00153     PR_ASSERT(rwlock != NULL);
00154     PR_ASSERT(rwlock->rw_waiting_readers == 0);
00155 
00156     /* XXX Shouldn't we lock the PZLock before destroying this?? */
00157 
00158     if (rwlock->rw_name)
00159        PR_Free(rwlock->rw_name);
00160     if (rwlock->rw_reader_waitq)
00161        PZ_DestroyCondVar(rwlock->rw_reader_waitq);
00162     if (rwlock->rw_writer_waitq)
00163        PZ_DestroyCondVar(rwlock->rw_writer_waitq);
00164     if (rwlock->rw_lock)
00165        PZ_DestroyLock(rwlock->rw_lock);
00166     PR_DELETE(rwlock);
00167 }
00168 
00169 /***********************************************************************
00170 **  Given the address of a NULL pointer to a NSSRWLock, 
00171 **  atomically initializes that pointer to a newly created NSSRWLock.
00172 **  Returns the value placed into that pointer, or NULL.
00173 **   If the lock cannot be created because of resource constraints, 
00174 **   the pointer will be left NULL.
00175 **  
00176 ***********************************************************************/
00177 PR_IMPLEMENT(NSSRWLock *)
00178 nssRWLock_AtomicCreate( NSSRWLock  ** prwlock, 
00179                      PRUint32      lock_rank, 
00180                      const char *  lock_name)
00181 {
00182     NSSRWLock  *    rwlock;
00183     static PRInt32  initializers;
00184 
00185     PR_ASSERT(prwlock != NULL);
00186 
00187     /* atomically initialize the lock */
00188     while (NULL == (rwlock = *prwlock)) {
00189         PRInt32 myAttempt = PR_AtomicIncrement(&initializers);
00190         if (myAttempt == 1) {
00191             if (NULL == (rwlock = *prwlock)) {
00192                 *prwlock = rwlock = NSSRWLock_New(lock_rank, lock_name);
00193             }
00194             (void) PR_AtomicDecrement(&initializers);
00195             break;
00196         }
00197         PR_Sleep(PR_INTERVAL_NO_WAIT);          /* PR_Yield() */
00198         (void) PR_AtomicDecrement(&initializers);
00199     }
00200 
00201     return rwlock;
00202 }
00203 
00204 /*
00205 ** Read-lock the RWLock.
00206 */
00207 PR_IMPLEMENT(void)
00208 NSSRWLock_LockRead(NSSRWLock *rwlock)
00209 {
00210     PRThread *me = PR_GetCurrentThread();
00211 
00212     PZ_Lock(rwlock->rw_lock);
00213 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00214 
00215     /*
00216      * assert that rank ordering is not violated; the rank of 'rwlock' should
00217      * be equal to or greater than the highest rank of all the locks held by
00218      * the thread.
00219      */
00220     PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
00221               (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
00222 #endif
00223     /*
00224      * wait if write-locked or if a writer is waiting; preference for writers
00225      */
00226     UNTIL ( (rwlock->rw_owner == me) ||            /* I own it, or        */
00227           ((rwlock->rw_owner == NULL) &&    /* no-one owns it, and */
00228            (rwlock->rw_waiting_writers == 0))) { /* no-one is waiting to own */
00229 
00230        rwlock->rw_waiting_readers++;
00231        PZ_WaitCondVar(rwlock->rw_reader_waitq, PR_INTERVAL_NO_TIMEOUT);
00232        rwlock->rw_waiting_readers--;
00233     }
00234     rwlock->rw_reader_locks++;            /* Increment read-lock count */
00235 
00236     PZ_Unlock(rwlock->rw_lock);
00237 
00238 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00239     nssRWLock_SetThreadRank(me, rwlock);/* update thread's lock rank */
00240 #endif
00241 }
00242 
00243 /* Unlock a Read lock held on this RW lock.
00244 */
00245 PR_IMPLEMENT(void)
00246 NSSRWLock_UnlockRead(NSSRWLock *rwlock)
00247 {
00248     PZ_Lock(rwlock->rw_lock);
00249 
00250     PR_ASSERT(rwlock->rw_reader_locks > 0); /* lock must be read locked */
00251 
00252     if ((  rwlock->rw_reader_locks  > 0)  &&     /* caller isn't screwey */
00253         (--rwlock->rw_reader_locks == 0)  &&     /* not read locked any more */
00254        (  rwlock->rw_owner        == NULL) &&    /* not write locked */
00255        (  rwlock->rw_waiting_writers > 0)) {     /* someone's waiting. */
00256 
00257        PZ_NotifyCondVar(rwlock->rw_writer_waitq); /* wake him up. */
00258     }
00259 
00260     PZ_Unlock(rwlock->rw_lock);
00261 
00262 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00263     /*
00264      * update thread's lock rank
00265      */
00266     nssRWLock_UnsetThreadRank(me, rwlock);
00267 #endif
00268     return;
00269 }
00270 
00271 /*
00272 ** Write-lock the RWLock.
00273 */
00274 PR_IMPLEMENT(void)
00275 NSSRWLock_LockWrite(NSSRWLock *rwlock)
00276 {
00277     PRThread *me = PR_GetCurrentThread();
00278 
00279     PZ_Lock(rwlock->rw_lock);
00280 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00281     /*
00282      * assert that rank ordering is not violated; the rank of 'rwlock' should
00283      * be equal to or greater than the highest rank of all the locks held by
00284      * the thread.
00285      */
00286     PR_ASSERT((rwlock->rw_rank == NSS_RWLOCK_RANK_NONE) ||
00287                     (rwlock->rw_rank >= nssRWLock_GetThreadRank(me)));
00288 #endif
00289     /*
00290      * wait if read locked or write locked.
00291      */
00292     PR_ASSERT(rwlock->rw_reader_locks >= 0);
00293     PR_ASSERT(me != NULL);
00294 
00295     UNTIL ( (rwlock->rw_owner == me) ||           /* I own write lock, or */
00296           ((rwlock->rw_owner == NULL) &&    /* no writer   and */
00297            (rwlock->rw_reader_locks == 0))) {    /* no readers, either. */
00298 
00299         rwlock->rw_waiting_writers++;
00300         PZ_WaitCondVar(rwlock->rw_writer_waitq, PR_INTERVAL_NO_TIMEOUT);
00301         rwlock->rw_waiting_writers--;
00302        PR_ASSERT(rwlock->rw_reader_locks >= 0);
00303     }
00304 
00305     PR_ASSERT(rwlock->rw_reader_locks == 0);
00306     /*
00307      * apply write lock
00308      */
00309     rwlock->rw_owner = me;
00310     rwlock->rw_writer_locks++;            /* Increment write-lock count */
00311 
00312     PZ_Unlock(rwlock->rw_lock);
00313 
00314 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00315     /*
00316      * update thread's lock rank
00317      */
00318     nssRWLock_SetThreadRank(me,rwlock);
00319 #endif
00320 }
00321 
00322 /* Unlock a Read lock held on this RW lock.
00323 */
00324 PR_IMPLEMENT(void)
00325 NSSRWLock_UnlockWrite(NSSRWLock *rwlock)
00326 {
00327     PRThread *me = PR_GetCurrentThread();
00328 
00329     PZ_Lock(rwlock->rw_lock);
00330     PR_ASSERT(rwlock->rw_owner == me); /* lock must be write-locked by me.  */
00331     PR_ASSERT(rwlock->rw_writer_locks > 0); /* lock must be write locked */
00332 
00333     if (  rwlock->rw_owner        == me  &&      /* I own it, and            */
00334           rwlock->rw_writer_locks  > 0   &&      /* I own it, and            */
00335         --rwlock->rw_writer_locks == 0) { /* I'm all done with it     */
00336 
00337        rwlock->rw_owner = NULL;           /* I don't own it any more. */
00338 
00339        /* Give preference to waiting writers. */
00340        if (rwlock->rw_waiting_writers > 0) {
00341            if (rwlock->rw_reader_locks == 0)
00342               PZ_NotifyCondVar(rwlock->rw_writer_waitq);
00343        } else if (rwlock->rw_waiting_readers > 0) {
00344            PZ_NotifyAllCondVar(rwlock->rw_reader_waitq);
00345        }
00346     }
00347     PZ_Unlock(rwlock->rw_lock);
00348 
00349 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00350     /*
00351      * update thread's lock rank
00352      */
00353     nssRWLock_UnsetThreadRank(me, rwlock);
00354 #endif
00355     return;
00356 }
00357 
00358 /* This is primarily for debugging, i.e. for inclusion in ASSERT calls. */
00359 PR_IMPLEMENT(PRBool)
00360 NSSRWLock_HaveWriteLock(NSSRWLock *rwlock) {
00361     PRBool ownWriteLock;
00362     PRThread *me = PR_GetCurrentThread();
00363 
00364     /* This lock call isn't really necessary.
00365     ** If this thread is the owner, that fact cannot change during this call,
00366     ** because this thread is in this call.
00367     ** If this thread is NOT the owner, the owner could change, but it 
00368     ** could not become this thread.  
00369     */
00370 #if UNNECESSARY
00371     PZ_Lock(rwlock->rw_lock);      
00372 #endif
00373     ownWriteLock = (PRBool)(me == rwlock->rw_owner);
00374 #if UNNECESSARY
00375     PZ_Unlock(rwlock->rw_lock);
00376 #endif
00377     return ownWriteLock;
00378 }
00379 
00380 #ifdef NSS_RWLOCK_RANK_ORDER_DEBUG
00381 
00382 /*
00383  * nssRWLock_SetThreadRank
00384  *      Set a thread's lock rank, which is the highest of the ranks of all
00385  *      the locks held by the thread. Pointers to the locks are added to a
00386  *      per-thread list, which is anchored off a thread-private data key.
00387  */
00388 
00389 static void
00390 nssRWLock_SetThreadRank(PRThread *me, NSSRWLock *rwlock)
00391 {
00392     thread_rwlock_stack *lock_stack;
00393     PRStatus rv;
00394 
00395     /*
00396      * allocated thread-private-data for rwlock list, if not already allocated
00397      */
00398     if (!nss_thread_rwlock_initialized) {
00399         /*
00400          * allocate tpd, only if not failed already
00401          */
00402         if (!nss_thread_rwlock_alloc_failed) {
00403             if (PR_NewThreadPrivateIndex(&nss_thread_rwlock,
00404                                         nssRWLock_ReleaseLockStack)
00405                                                 == PR_FAILURE) {
00406                 nss_thread_rwlock_alloc_failed = 1;
00407                 return;
00408             }
00409         } else
00410             return;
00411     }
00412     /*
00413      * allocate a lock stack
00414      */
00415     if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL) {
00416         lock_stack = (thread_rwlock_stack *)
00417                         PR_CALLOC(1 * sizeof(thread_rwlock_stack));
00418         if (lock_stack) {
00419             rv = PR_SetThreadPrivate(nss_thread_rwlock, lock_stack);
00420             if (rv == PR_FAILURE) {
00421                 PR_DELETE(lock_stack);
00422                 nss_thread_rwlock_alloc_failed = 1;
00423                 return;
00424             }
00425         } else {
00426             nss_thread_rwlock_alloc_failed = 1;
00427             return;
00428         }
00429     }
00430     /*
00431      * add rwlock to lock stack, if limit is not exceeded
00432      */
00433     if (lock_stack) {
00434         if (lock_stack->trs_index < _NSS_RWLOCK_RANK_ORDER_LIMIT)
00435             lock_stack->trs_stack[lock_stack->trs_index++] = rwlock;
00436     }
00437     nss_thread_rwlock_initialized = 1;
00438 }
00439 
00440 static void
00441 nssRWLock_ReleaseLockStack(void *lock_stack)
00442 {
00443     PR_ASSERT(lock_stack);
00444     PR_DELETE(lock_stack);
00445 }
00446 
00447 /*
00448  * nssRWLock_GetThreadRank
00449  *
00450  *      return thread's lock rank. If thread-private-data for the lock
00451  *      stack is not allocated, return NSS_RWLOCK_RANK_NONE.
00452  */
00453 
00454 static PRUint32
00455 nssRWLock_GetThreadRank(PRThread *me)
00456 {
00457     thread_rwlock_stack *lock_stack;
00458 
00459     if (nss_thread_rwlock_initialized) {
00460         if ((lock_stack = PR_GetThreadPrivate(nss_thread_rwlock)) == NULL)
00461             return (NSS_RWLOCK_RANK_NONE);
00462         else
00463             return(lock_stack->trs_stack[lock_stack->trs_index - 1]->rw_rank);
00464 
00465     } else
00466             return (NSS_RWLOCK_RANK_NONE);
00467 }
00468 
00469 /*
00470  * nssRWLock_UnsetThreadRank
00471  *
00472  *      remove the rwlock from the lock stack. Since locks may not be
00473  *      unlocked in a FIFO order, the entire lock stack is searched.
00474  */
00475 
00476 static void
00477 nssRWLock_UnsetThreadRank(PRThread *me, NSSRWLock *rwlock)
00478 {
00479     thread_rwlock_stack *lock_stack;
00480     int new_index = 0, index, done = 0;
00481 
00482     if (!nss_thread_rwlock_initialized)
00483         return;
00484 
00485     lock_stack = PR_GetThreadPrivate(nss_thread_rwlock);
00486 
00487     PR_ASSERT(lock_stack != NULL);
00488 
00489     index = lock_stack->trs_index - 1;
00490     while (index-- >= 0) {
00491         if ((lock_stack->trs_stack[index] == rwlock) && !done)  {
00492             /*
00493              * reset the slot for rwlock
00494              */
00495             lock_stack->trs_stack[index] = NULL;
00496             done = 1;
00497         }
00498         /*
00499          * search for the lowest-numbered empty slot, above which there are
00500          * no non-empty slots
00501          */
00502         if ((lock_stack->trs_stack[index] != NULL) && !new_index)
00503             new_index = index + 1;
00504         if (done && new_index)
00505             break;
00506     }
00507     /*
00508      * set top of stack to highest numbered empty slot
00509      */
00510     lock_stack->trs_index = new_index;
00511 
00512 }
00513 
00514 #endif  /* NSS_RWLOCK_RANK_ORDER_DEBUG */