tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

w95cv.c (10796B)

      1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
      2 /* This Source Code Form is subject to the terms of the Mozilla Public
      3 * License, v. 2.0. If a copy of the MPL was not distributed with this
      4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      5 
      6 /*
      7 *  w95cv.c -- Windows 95 Machine-Dependent Code for Condition Variables
      8 *
      9 *  We implement our own condition variable wait queue.  Each thread
     10 *  has a semaphore object (thread->md.blocked_sema) to block on while
     11 *  waiting on a condition variable.
     12 *
     13 *  We use a deferred condition notify algorithm.  When PR_NotifyCondVar
     14 *  or PR_NotifyAllCondVar is called, the condition notifies are simply
     15 *  recorded in the _MDLock structure.  We defer the condition notifies
     16 *  until right after we unlock the lock.  This way the awakened threads
     17 *  have a better chance to reaquire the lock.
     18 */
     19 
     20 #include "primpl.h"
     21 
     22 /*
     23 * AddThreadToCVWaitQueueInternal --
     24 *
     25 * Add the thread to the end of the condition variable's wait queue.
     26 * The CV's lock must be locked when this function is called.
     27 */
     28 
     29 static void AddThreadToCVWaitQueueInternal(PRThread* thred,
     30                                           struct _MDCVar* cv) {
     31  PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL) ||
     32            (cv->waitTail == NULL && cv->waitHead == NULL));
     33  cv->nwait += 1;
     34  thred->md.inCVWaitQueue = PR_TRUE;
     35  thred->md.next = NULL;
     36  thred->md.prev = cv->waitTail;
     37  if (cv->waitHead == NULL) {
     38    cv->waitHead = thred;
     39  } else {
     40    cv->waitTail->md.next = thred;
     41  }
     42  cv->waitTail = thred;
     43 }
     44 
     45 /*
     46 * md_UnlockAndPostNotifies --
     47 *
     48 * Unlock the lock, and then do the deferred condition notifies.
     49 * If waitThred and waitCV are not NULL, waitThred is added to
     50 * the wait queue of waitCV before the lock is unlocked.
     51 *
     52 * This function is called by _PR_MD_WAIT_CV and _PR_MD_UNLOCK,
     53 * the two places where a lock is unlocked.
     54 */
     55 static void md_UnlockAndPostNotifies(_MDLock* lock, PRThread* waitThred,
     56                                     _MDCVar* waitCV) {
     57  PRIntn index;
     58  _MDNotified post;
     59  _MDNotified *notified, *prev = NULL;
     60 
     61  /*
     62   * Time to actually notify any conditions that were affected
     63   * while the lock was held.  Get a copy of the list that's in
     64   * the lock structure and then zero the original.  If it's
     65   * linked to other such structures, we own that storage.
     66   */
     67  post = lock->notified; /* a safe copy; we own the lock */
     68 
     69 #if defined(DEBUG)
     70  ZeroMemory(&lock->notified, sizeof(_MDNotified)); /* reset */
     71 #else
     72  lock->notified.length = 0; /* these are really sufficient */
     73  lock->notified.link = NULL;
     74 #endif
     75 
     76  /*
     77   * Figure out how many threads we need to wake up.
     78   */
     79  notified = &post; /* this is where we start */
     80  do {
     81    for (index = 0; index < notified->length; ++index) {
     82      _MDCVar* cv = notified->cv[index].cv;
     83      PRThread* thred;
     84      int i;
     85 
     86      /* Fast special case: no waiting threads */
     87      if (cv->waitHead == NULL) {
     88        notified->cv[index].notifyHead = NULL;
     89        continue;
     90      }
     91 
     92      /* General case */
     93      if (-1 == notified->cv[index].times) {
     94        /* broadcast */
     95        thred = cv->waitHead;
     96        while (thred != NULL) {
     97          thred->md.inCVWaitQueue = PR_FALSE;
     98          thred = thred->md.next;
     99        }
    100        notified->cv[index].notifyHead = cv->waitHead;
    101        cv->waitHead = cv->waitTail = NULL;
    102        cv->nwait = 0;
    103      } else {
    104        thred = cv->waitHead;
    105        i = notified->cv[index].times;
    106        while (thred != NULL && i > 0) {
    107          thred->md.inCVWaitQueue = PR_FALSE;
    108          thred = thred->md.next;
    109          i--;
    110        }
    111        notified->cv[index].notifyHead = cv->waitHead;
    112        cv->waitHead = thred;
    113        if (cv->waitHead == NULL) {
    114          cv->waitTail = NULL;
    115        } else {
    116          if (cv->waitHead->md.prev != NULL) {
    117            cv->waitHead->md.prev->md.next = NULL;
    118            cv->waitHead->md.prev = NULL;
    119          }
    120        }
    121        cv->nwait -= notified->cv[index].times - i;
    122      }
    123    }
    124    notified = notified->link;
    125  } while (NULL != notified);
    126 
    127  if (waitThred) {
    128    AddThreadToCVWaitQueueInternal(waitThred, waitCV);
    129  }
    130 
    131  /* Release the lock before notifying */
    132  LeaveCriticalSection(&lock->mutex);
    133 
    134  notified = &post; /* this is where we start */
    135  do {
    136    for (index = 0; index < notified->length; ++index) {
    137      PRThread* thred;
    138      PRThread* next;
    139 
    140      thred = notified->cv[index].notifyHead;
    141      while (thred != NULL) {
    142        BOOL rv;
    143 
    144        next = thred->md.next;
    145        thred->md.prev = thred->md.next = NULL;
    146 
    147        rv = ReleaseSemaphore(thred->md.blocked_sema, 1, NULL);
    148        PR_ASSERT(rv != 0);
    149        thred = next;
    150      }
    151    }
    152    prev = notified;
    153    notified = notified->link;
    154    if (&post != prev) {
    155      PR_DELETE(prev);
    156    }
    157  } while (NULL != notified);
    158 }
    159 
    160 /*
    161 * Notifies just get posted to the protecting mutex.  The
    162 * actual notification is done when the lock is released so that
    163 * MP systems don't contend for a lock that they can't have.
    164 */
    165 static void md_PostNotifyToCvar(_MDCVar* cvar, _MDLock* lock,
    166                                PRBool broadcast) {
    167  PRIntn index = 0;
    168  _MDNotified* notified = &lock->notified;
    169 
    170  while (1) {
    171    for (index = 0; index < notified->length; ++index) {
    172      if (notified->cv[index].cv == cvar) {
    173        if (broadcast) {
    174          notified->cv[index].times = -1;
    175        } else if (-1 != notified->cv[index].times) {
    176          notified->cv[index].times += 1;
    177        }
    178        return;
    179      }
    180    }
    181    /* if not full, enter new CV in this array */
    182    if (notified->length < _MD_CV_NOTIFIED_LENGTH) {
    183      break;
    184    }
    185 
    186    /* if there's no link, create an empty array and link it */
    187    if (NULL == notified->link) {
    188      notified->link = PR_NEWZAP(_MDNotified);
    189    }
    190 
    191    notified = notified->link;
    192  }
    193 
    194  /* A brand new entry in the array */
    195  notified->cv[index].times = (broadcast) ? -1 : 1;
    196  notified->cv[index].cv = cvar;
    197  notified->length += 1;
    198 }
    199 
    200 /*
    201 * _PR_MD_NEW_CV() -- Creating new condition variable
    202 * ... Solaris uses cond_init() in similar function.
    203 *
    204 * returns: -1 on failure
    205 *          0 when it succeeds.
    206 *
    207 */
    208 PRInt32 _PR_MD_NEW_CV(_MDCVar* cv) {
    209  cv->magic = _MD_MAGIC_CV;
    210  /*
    211   * The waitHead, waitTail, and nwait fields are zeroed
    212   * when the PRCondVar structure is created.
    213   */
    214  return 0;
    215 }
    216 
    217 void _PR_MD_FREE_CV(_MDCVar* cv) {
    218  cv->magic = (PRUint32)-1;
    219  return;
    220 }
    221 
    222 /*
    223 *  _PR_MD_WAIT_CV() -- Wait on condition variable
    224 */
    225 void _PR_MD_WAIT_CV(_MDCVar* cv, _MDLock* lock, PRIntervalTime timeout) {
    226  PRThread* thred = _PR_MD_CURRENT_THREAD();
    227  DWORD rv;
    228  DWORD msecs = (timeout == PR_INTERVAL_NO_TIMEOUT)
    229                    ? INFINITE
    230                    : PR_IntervalToMilliseconds(timeout);
    231 
    232  /*
    233   * If we have pending notifies, post them now.
    234   */
    235  if (0 != lock->notified.length) {
    236    md_UnlockAndPostNotifies(lock, thred, cv);
    237  } else {
    238    AddThreadToCVWaitQueueInternal(thred, cv);
    239    LeaveCriticalSection(&lock->mutex);
    240  }
    241 
    242  /* Wait for notification or timeout; don't really care which */
    243  rv = WaitForSingleObject(thred->md.blocked_sema, msecs);
    244 
    245  EnterCriticalSection(&(lock->mutex));
    246 
    247  PR_ASSERT(rv != WAIT_ABANDONED);
    248  PR_ASSERT(rv != WAIT_FAILED);
    249  PR_ASSERT(rv != WAIT_OBJECT_0 || thred->md.inCVWaitQueue == PR_FALSE);
    250 
    251  if (rv == WAIT_TIMEOUT) {
    252    if (thred->md.inCVWaitQueue) {
    253      PR_ASSERT((cv->waitTail != NULL && cv->waitHead != NULL) ||
    254                (cv->waitTail == NULL && cv->waitHead == NULL));
    255      cv->nwait -= 1;
    256      thred->md.inCVWaitQueue = PR_FALSE;
    257      if (cv->waitHead == thred) {
    258        cv->waitHead = thred->md.next;
    259        if (cv->waitHead == NULL) {
    260          cv->waitTail = NULL;
    261        } else {
    262          cv->waitHead->md.prev = NULL;
    263        }
    264      } else {
    265        PR_ASSERT(thred->md.prev != NULL);
    266        thred->md.prev->md.next = thred->md.next;
    267        if (thred->md.next != NULL) {
    268          thred->md.next->md.prev = thred->md.prev;
    269        } else {
    270          PR_ASSERT(cv->waitTail == thred);
    271          cv->waitTail = thred->md.prev;
    272        }
    273      }
    274      thred->md.next = thred->md.prev = NULL;
    275    } else {
    276      /*
    277       * This thread must have been notified, but the
    278       * ReleaseSemaphore call happens after WaitForSingleObject
    279       * times out.  Wait on the semaphore again to make it
    280       * non-signaled.  We assume this wait won't take long.
    281       */
    282      rv = WaitForSingleObject(thred->md.blocked_sema, INFINITE);
    283      PR_ASSERT(rv == WAIT_OBJECT_0);
    284    }
    285  }
    286  PR_ASSERT(thred->md.inCVWaitQueue == PR_FALSE);
    287  return;
    288 } /* --- end _PR_MD_WAIT_CV() --- */
    289 
    290 void _PR_MD_NOTIFY_CV(_MDCVar* cv, _MDLock* lock) {
    291  md_PostNotifyToCvar(cv, lock, PR_FALSE);
    292  return;
    293 }
    294 
    295 void _PR_MD_NOTIFYALL_CV(_MDCVar* cv, _MDLock* lock) {
    296  md_PostNotifyToCvar(cv, lock, PR_TRUE);
    297  return;
    298 }
    299 
    300 typedef BOOL(WINAPI* INITIALIZECRITICALSECTIONEX)(
    301    CRITICAL_SECTION* lpCriticalSection, DWORD dwSpinCount, DWORD Flags);
    302 
    303 static INITIALIZECRITICALSECTIONEX sInitializeCriticalSectionEx;
    304 
    305 void _PR_MD_INIT_LOCKS(void) {
    306  /*
    307   * Starting with Windows Vista, every CRITICAL_SECTION allocates an extra
    308   * RTL_CRITICAL_SECTION_DEBUG object. Unfortunately, this debug object is
    309   * not reclaimed by DeleteCriticalSection(), causing an apparent memory
    310   * leak. This is a debugging "feature", not a bug. If we are running on
    311   * Vista or later, use InitializeCriticalSectionEx() to allocate
    312   * CRITICAL_SECTIONs without debug objects.
    313   */
    314  HMODULE hKernel32 = GetModuleHandle("kernel32.dll");
    315  PR_ASSERT(hKernel32);
    316  PR_ASSERT(!sInitializeCriticalSectionEx);
    317  sInitializeCriticalSectionEx = (INITIALIZECRITICALSECTIONEX)GetProcAddress(
    318      hKernel32, "InitializeCriticalSectionEx");
    319 }
    320 
    321 /*
    322 * By default, CRITICAL_SECTIONs are initialized with a spin count of 0.
    323 * Joe Duffy's "Concurrent Programming on Windows" book suggests 1500 is
    324 * a "reasonable starting point". On single-processor systems, the spin
    325 * count is ignored and the critical section spin count is set to 0.
    326 */
    327 #define LOCK_SPIN_COUNT 1500
    328 
    329 PRStatus _PR_MD_NEW_LOCK(_MDLock* lock) {
    330  CRITICAL_SECTION* cs = &lock->mutex;
    331  BOOL ok;
    332 
    333  if (sInitializeCriticalSectionEx) {
    334    ok = sInitializeCriticalSectionEx(cs, LOCK_SPIN_COUNT,
    335                                      CRITICAL_SECTION_NO_DEBUG_INFO);
    336  } else {
    337    ok = InitializeCriticalSectionAndSpinCount(cs, LOCK_SPIN_COUNT);
    338  }
    339  if (!ok) {
    340    _PR_MD_MAP_DEFAULT_ERROR(GetLastError());
    341    return PR_FAILURE;
    342  }
    343 
    344  lock->notified.length = 0;
    345  lock->notified.link = NULL;
    346  return PR_SUCCESS;
    347 }
    348 
    349 void _PR_MD_UNLOCK(_MDLock* lock) {
    350  if (0 != lock->notified.length) {
    351    md_UnlockAndPostNotifies(lock, NULL, NULL);
    352  } else {
    353    LeaveCriticalSection(&lock->mutex);
    354  }
    355 }