andre@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
andre@0: /* This Source Code Form is subject to the terms of the Mozilla Public
andre@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
andre@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
andre@0: 
andre@0: /*
andre@0:  *  w95cv.c -- Windows 95 Machine-Dependent Code for Condition Variables
andre@0:  *
andre@0:  *  We implement our own condition variable wait queue.  Each thread
andre@0:  *  has a semaphore object (thread->md.blocked_sema) to block on while
andre@0:  *  waiting on a condition variable.
andre@0:  *
andre@0:  *  We use a deferred condition notify algorithm.  When PR_NotifyCondVar
andre@0:  *  or PR_NotifyAllCondVar is called, the condition notifies are simply
andre@0:  *  recorded in the _MDLock structure.  We defer the condition notifies
andre@0:  *  until right after we unlock the lock.  This way the awakened threads
andre@0:  *  have a better chance to reaquire the lock.
andre@0:  */
andre@0:  
andre@0: #include "primpl.h"
andre@0: 
andre@0: /*
andre@0:  * AddThreadToCVWaitQueueInternal --
andre@0:  *
andre@0:  * Add the thread to the end of the condition variable's wait queue.
andre@0:  * The CV's lock must be locked when this function is called.
andre@0:  */
andre@0: 
andre@0: static void
andre@0: AddThreadToCVWaitQueueInternal(PRThread *thred, struct _MDCVar *cv)
andre@0: {
andre@0:     PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL)
andre@0:             || (cv->waitTail == NULL && cv->waitHead == NULL));
andre@0:     cv->nwait += 1;
andre@0:     thred->md.inCVWaitQueue = PR_TRUE;
andre@0:     thred->md.next = NULL;
andre@0:     thred->md.prev = cv->waitTail;
andre@0:     if (cv->waitHead == NULL) {
andre@0:         cv->waitHead = thred;
andre@0:     } else {
andre@0:         cv->waitTail->md.next = thred;
andre@0:     }
andre@0:     cv->waitTail = thred;
andre@0: }
andre@0: 
andre@0: /*
andre@0:  * md_UnlockAndPostNotifies --
andre@0:  *
andre@0:  * Unlock the lock, and then do the deferred condition notifies.
andre@0:  * If waitThred and waitCV are not NULL, waitThred is added to
andre@0:  * the wait queue of waitCV before the lock is unlocked.
andre@0:  *
andre@0:  * This function is called by _PR_MD_WAIT_CV and _PR_MD_UNLOCK,
andre@0:  * the two places where a lock is unlocked.
andre@0:  */
andre@0: static void
andre@0: md_UnlockAndPostNotifies(
andre@0:     _MDLock *lock,
andre@0:     PRThread *waitThred,
andre@0:     _MDCVar *waitCV)
andre@0: {
andre@0:     PRIntn index;
andre@0:     _MDNotified post;
andre@0:     _MDNotified *notified, *prev = NULL;
andre@0: 
andre@0:     /*
andre@0:      * Time to actually notify any conditions that were affected
andre@0:      * while the lock was held.  Get a copy of the list that's in
andre@0:      * the lock structure and then zero the original.  If it's
andre@0:      * linked to other such structures, we own that storage.
andre@0:      */
andre@0:     post = lock->notified;  /* a safe copy; we own the lock */
andre@0: 
andre@0: #if defined(DEBUG)
andre@0:     ZeroMemory(&lock->notified, sizeof(_MDNotified));  /* reset */
andre@0: #else
andre@0:     lock->notified.length = 0;  /* these are really sufficient */
andre@0:     lock->notified.link = NULL;
andre@0: #endif
andre@0: 
andre@0:     /* 
andre@0:      * Figure out how many threads we need to wake up.
andre@0:      */
andre@0:     notified = &post;  /* this is where we start */
andre@0:     do {
andre@0:         for (index = 0; index < notified->length; ++index) {
andre@0:             _MDCVar *cv = notified->cv[index].cv;
andre@0:             PRThread *thred;
andre@0:             int i;
andre@0:             
andre@0:             /* Fast special case: no waiting threads */
andre@0:             if (cv->waitHead == NULL) {
andre@0:                 notified->cv[index].notifyHead = NULL;
andre@0:                 continue;
andre@0:             }
andre@0: 
andre@0:             /* General case */
andre@0:             if (-1 == notified->cv[index].times) {
andre@0:                 /* broadcast */
andre@0:                 thred = cv->waitHead;
andre@0:                 while (thred != NULL) {
andre@0:                     thred->md.inCVWaitQueue = PR_FALSE;
andre@0:                     thred = thred->md.next;
andre@0:                 }
andre@0:                 notified->cv[index].notifyHead = cv->waitHead;
andre@0:                 cv->waitHead = cv->waitTail = NULL;
andre@0:                 cv->nwait = 0;
andre@0:             } else {
andre@0:                 thred = cv->waitHead;
andre@0:                 i = notified->cv[index].times;
andre@0:                 while (thred != NULL && i > 0) {
andre@0:                     thred->md.inCVWaitQueue = PR_FALSE;
andre@0:                     thred = thred->md.next;
andre@0:                     i--;
andre@0:                 }
andre@0:                 notified->cv[index].notifyHead = cv->waitHead;
andre@0:                 cv->waitHead = thred;
andre@0:                 if (cv->waitHead == NULL) {
andre@0:                     cv->waitTail = NULL;
andre@0:                 } else {
andre@0:                     if (cv->waitHead->md.prev != NULL) {
andre@0:                         cv->waitHead->md.prev->md.next = NULL;
andre@0:                         cv->waitHead->md.prev = NULL;
andre@0:                     }
andre@0:                 }
andre@0:                 cv->nwait -= notified->cv[index].times - i;
andre@0:             }
andre@0:         }
andre@0:         notified = notified->link;
andre@0:     } while (NULL != notified);
andre@0: 
andre@0:     if (waitThred) {
andre@0:         AddThreadToCVWaitQueueInternal(waitThred, waitCV);
andre@0:     }
andre@0: 
andre@0:     /* Release the lock before notifying */
andre@0:         LeaveCriticalSection(&lock->mutex);
andre@0: 
andre@0:     notified = &post;  /* this is where we start */
andre@0:     do {
andre@0:         for (index = 0; index < notified->length; ++index) {
andre@0:             PRThread *thred;
andre@0:             PRThread *next;
andre@0: 
andre@0:             thred = notified->cv[index].notifyHead;
andre@0:             while (thred != NULL) {
andre@0:                 BOOL rv;
andre@0: 
andre@0:                 next = thred->md.next;
andre@0:                 thred->md.prev = thred->md.next = NULL;
andre@0: 
andre@0:                 rv = ReleaseSemaphore(thred->md.blocked_sema, 1, NULL);
andre@0:                 PR_ASSERT(rv != 0);
andre@0:                 thred = next;
andre@0:             }
andre@0:         }
andre@0:         prev = notified;
andre@0:         notified = notified->link;
andre@0:         if (&post != prev) PR_DELETE(prev);
andre@0:     } while (NULL != notified);
andre@0: }
andre@0: 
andre@0: /*
andre@0:  * Notifies just get posted to the protecting mutex.  The
andre@0:  * actual notification is done when the lock is released so that
andre@0:  * MP systems don't contend for a lock that they can't have.
andre@0:  */
andre@0: static void md_PostNotifyToCvar(_MDCVar *cvar, _MDLock *lock,
andre@0:         PRBool broadcast)
andre@0: {
andre@0:     PRIntn index = 0;
andre@0:     _MDNotified *notified = &lock->notified;
andre@0: 
andre@0:     while (1) {
andre@0:         for (index = 0; index < notified->length; ++index) {
andre@0:             if (notified->cv[index].cv == cvar) {
andre@0:                 if (broadcast) {
andre@0:                     notified->cv[index].times = -1;
andre@0:                 } else if (-1 != notified->cv[index].times) {
andre@0:                     notified->cv[index].times += 1;
andre@0:                 }
andre@0:                 return;
andre@0:             }
andre@0:         }
andre@0:         /* if not full, enter new CV in this array */
andre@0:         if (notified->length < _MD_CV_NOTIFIED_LENGTH) break;
andre@0: 
andre@0:         /* if there's no link, create an empty array and link it */
andre@0:         if (NULL == notified->link) {
andre@0:             notified->link = PR_NEWZAP(_MDNotified);
andre@0:         }
andre@0: 
andre@0:         notified = notified->link;
andre@0:     }
andre@0: 
andre@0:     /* A brand new entry in the array */
andre@0:     notified->cv[index].times = (broadcast) ? -1 : 1;
andre@0:     notified->cv[index].cv = cvar;
andre@0:     notified->length += 1;
andre@0: }
andre@0: 
andre@0: /*
andre@0:  * _PR_MD_NEW_CV() -- Creating new condition variable
andre@0:  * ... Solaris uses cond_init() in similar function.
andre@0:  *
andre@0:  * returns: -1 on failure
andre@0:  *          0 when it succeeds.
andre@0:  *
andre@0:  */
andre@0: PRInt32 
andre@0: _PR_MD_NEW_CV(_MDCVar *cv)
andre@0: {
andre@0:     cv->magic = _MD_MAGIC_CV;
andre@0:     /*
andre@0:      * The waitHead, waitTail, and nwait fields are zeroed
andre@0:      * when the PRCondVar structure is created.
andre@0:      */
andre@0:     return 0;
andre@0: } 
andre@0: 
andre@0: void _PR_MD_FREE_CV(_MDCVar *cv)
andre@0: {
andre@0:     cv->magic = (PRUint32)-1;
andre@0:     return;
andre@0: }
andre@0: 
andre@0: /*
andre@0:  *  _PR_MD_WAIT_CV() -- Wait on condition variable
andre@0:  */
andre@0: void _PR_MD_WAIT_CV(_MDCVar *cv, _MDLock *lock, PRIntervalTime timeout )
andre@0: {
andre@0:     PRThread *thred = _PR_MD_CURRENT_THREAD();
andre@0:     DWORD rv;
andre@0:     DWORD msecs = (timeout == PR_INTERVAL_NO_TIMEOUT) ?
andre@0:             INFINITE : PR_IntervalToMilliseconds(timeout);
andre@0: 
andre@0:     /*
andre@0:      * If we have pending notifies, post them now.
andre@0:      */
andre@0:     if (0 != lock->notified.length) {
andre@0:         md_UnlockAndPostNotifies(lock, thred, cv);
andre@0:     } else {
andre@0:         AddThreadToCVWaitQueueInternal(thred, cv);
andre@0:         LeaveCriticalSection(&lock->mutex);
andre@0:     }
andre@0: 
andre@0:     /* Wait for notification or timeout; don't really care which */
andre@0:     rv = WaitForSingleObject(thred->md.blocked_sema, msecs);
andre@0: 
andre@0:     EnterCriticalSection(&(lock->mutex));
andre@0: 
andre@0:     PR_ASSERT(rv != WAIT_ABANDONED);
andre@0:     PR_ASSERT(rv != WAIT_FAILED);
andre@0:     PR_ASSERT(rv != WAIT_OBJECT_0 || thred->md.inCVWaitQueue == PR_FALSE);
andre@0: 
andre@0:     if (rv == WAIT_TIMEOUT) {
andre@0:         if (thred->md.inCVWaitQueue) {
andre@0:             PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL)
andre@0:                     || (cv->waitTail == NULL && cv->waitHead == NULL));
andre@0:             cv->nwait -= 1;
andre@0:             thred->md.inCVWaitQueue = PR_FALSE;
andre@0:             if (cv->waitHead == thred) {
andre@0:                 cv->waitHead = thred->md.next;
andre@0:                 if (cv->waitHead == NULL) {
andre@0:                     cv->waitTail = NULL;
andre@0:                 } else {
andre@0:                     cv->waitHead->md.prev = NULL;
andre@0:                 }
andre@0:             } else {
andre@0:                 PR_ASSERT(thred->md.prev != NULL);
andre@0:                 thred->md.prev->md.next = thred->md.next;
andre@0:                 if (thred->md.next != NULL) {
andre@0:                     thred->md.next->md.prev = thred->md.prev;
andre@0:                 } else {
andre@0:                     PR_ASSERT(cv->waitTail == thred);
andre@0:                     cv->waitTail = thred->md.prev;
andre@0:                 }
andre@0:             }
andre@0:             thred->md.next = thred->md.prev = NULL;
andre@0:         } else {
andre@0:             /*
andre@0:              * This thread must have been notified, but the
andre@0:              * ReleaseSemaphore call happens after WaitForSingleObject
andre@0:              * times out.  Wait on the semaphore again to make it
andre@0:              * non-signaled.  We assume this wait won't take long.
andre@0:              */
andre@0:             rv = WaitForSingleObject(thred->md.blocked_sema, INFINITE);
andre@0:             PR_ASSERT(rv == WAIT_OBJECT_0);
andre@0:         }
andre@0:     }
andre@0:     PR_ASSERT(thred->md.inCVWaitQueue == PR_FALSE);
andre@0:     return;
andre@0: } /* --- end _PR_MD_WAIT_CV() --- */
andre@0: 
andre@0: void _PR_MD_NOTIFY_CV(_MDCVar *cv, _MDLock *lock)
andre@0: {
andre@0:     md_PostNotifyToCvar(cv, lock, PR_FALSE);
andre@0:     return;
andre@0: }
andre@0: 
andre@0: void _PR_MD_NOTIFYALL_CV(_MDCVar *cv, _MDLock *lock)
andre@0: {
andre@0:     md_PostNotifyToCvar(cv, lock, PR_TRUE);
andre@0:     return;
andre@0: }
andre@0: 
andre@0: typedef BOOL (WINAPI *INITIALIZECRITICALSECTIONEX)(
andre@0:     CRITICAL_SECTION *lpCriticalSection,
andre@0:     DWORD dwSpinCount,
andre@0:     DWORD Flags);
andre@0: 
andre@0: static INITIALIZECRITICALSECTIONEX sInitializeCriticalSectionEx;
andre@0: 
andre@0: void _PR_MD_INIT_LOCKS(void)
andre@0: {
andre@0:     /*
andre@0:      * Starting with Windows Vista, every CRITICAL_SECTION allocates an extra
andre@0:      * RTL_CRITICAL_SECTION_DEBUG object. Unfortunately, this debug object is
andre@0:      * not reclaimed by DeleteCriticalSection(), causing an apparent memory
andre@0:      * leak. This is a debugging "feature", not a bug. If we are running on
andre@0:      * Vista or later, use InitializeCriticalSectionEx() to allocate
andre@0:      * CRITICAL_SECTIONs without debug objects.
andre@0:      */
andre@0:     HMODULE hKernel32 = GetModuleHandle("kernel32.dll");
andre@0:     PR_ASSERT(hKernel32);
andre@0:     PR_ASSERT(!sInitializeCriticalSectionEx);
andre@0:     sInitializeCriticalSectionEx = (INITIALIZECRITICALSECTIONEX)
andre@0:             GetProcAddress(hKernel32, "InitializeCriticalSectionEx");
andre@0: }
andre@0: 
andre@0: /*
andre@0:  * By default, CRITICAL_SECTIONs are initialized with a spin count of 0.
andre@0:  * Joe Duffy's "Concurrent Programming on Windows" book suggests 1500 is
andre@0:  * a "reasonable starting point". On single-processor systems, the spin
andre@0:  * count is ignored and the critical section spin count is set to 0.
andre@0:  */
andre@0: #define LOCK_SPIN_COUNT 1500
andre@0: 
andre@0: PRStatus _PR_MD_NEW_LOCK(_MDLock *lock)
andre@0: {
andre@0:     CRITICAL_SECTION *cs = &lock->mutex;
andre@0:     BOOL ok;
andre@0: 
andre@0:     if (sInitializeCriticalSectionEx) {
andre@0:         ok = sInitializeCriticalSectionEx(cs, LOCK_SPIN_COUNT,
andre@0:                                           CRITICAL_SECTION_NO_DEBUG_INFO);
andre@0:     } else {
andre@0:         ok = InitializeCriticalSectionAndSpinCount(cs, LOCK_SPIN_COUNT);
andre@0:     }
andre@0:     if (!ok) {
andre@0:         _PR_MD_MAP_DEFAULT_ERROR(GetLastError());
andre@0:         return PR_FAILURE;
andre@0:     }
andre@0: 
andre@0:     lock->notified.length = 0;
andre@0:     lock->notified.link = NULL;
andre@0:     return PR_SUCCESS;
andre@0: }
andre@0: 
andre@0: void _PR_MD_UNLOCK(_MDLock *lock)
andre@0: {
andre@0:     if (0 != lock->notified.length) {
andre@0:         md_UnlockAndPostNotifies(lock, NULL, NULL);
andre@0:     } else {
andre@0:         LeaveCriticalSection(&lock->mutex);
andre@0:     }
andre@0: }