tor-browser

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

prcmon.c (11480B)

      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 #include "primpl.h"
      7 
      8 #include <stdlib.h>
      9 #include <stddef.h>
     10 
     11 /* Lock used to lock the monitor cache */
     12 #ifdef _PR_NO_PREEMPT
     13 #  define _PR_NEW_LOCK_MCACHE()
     14 #  define _PR_DESTROY_LOCK_MCACHE()
     15 #  define _PR_LOCK_MCACHE()
     16 #  define _PR_UNLOCK_MCACHE()
     17 #else
     18 #  ifdef _PR_LOCAL_THREADS_ONLY
     19 #    define _PR_NEW_LOCK_MCACHE()
     20 #    define _PR_DESTROY_LOCK_MCACHE()
     21 #    define _PR_LOCK_MCACHE() \
     22      {                       \
     23        PRIntn _is;           \
     24        _PR_INTSOFF(_is)
     25 #    define _PR_UNLOCK_MCACHE() \
     26      _PR_INTSON(_is);          \
     27      }
     28 #  else
     29 PRLock* _pr_mcacheLock;
     30 #    define _PR_NEW_LOCK_MCACHE() (_pr_mcacheLock = PR_NewLock())
     31 #    define _PR_DESTROY_LOCK_MCACHE()   \
     32      PR_BEGIN_MACRO                    \
     33      if (_pr_mcacheLock) {             \
     34        PR_DestroyLock(_pr_mcacheLock); \
     35        _pr_mcacheLock = NULL;          \
     36      }                                 \
     37      PR_END_MACRO
     38 #    define _PR_LOCK_MCACHE() PR_Lock(_pr_mcacheLock)
     39 #    define _PR_UNLOCK_MCACHE() PR_Unlock(_pr_mcacheLock)
     40 #  endif
     41 #endif
     42 
     43 /************************************************************************/
     44 
     45 typedef struct MonitorCacheEntryStr MonitorCacheEntry;
     46 
     47 struct MonitorCacheEntryStr {
     48  MonitorCacheEntry* next;
     49  void* address;
     50  PRMonitor* mon;
     51  long cacheEntryCount;
     52 };
     53 
     54 /*
     55 ** An array of MonitorCacheEntry's, plus a pointer to link these
     56 ** arrays together.
     57 */
     58 
     59 typedef struct MonitorCacheEntryBlockStr MonitorCacheEntryBlock;
     60 
     61 struct MonitorCacheEntryBlockStr {
     62  MonitorCacheEntryBlock* next;
     63  MonitorCacheEntry entries[1];
     64 };
     65 
     66 static PRUint32 hash_mask;
     67 static PRUintn num_hash_buckets;
     68 static PRUintn num_hash_buckets_log2;
     69 static MonitorCacheEntry** hash_buckets;
     70 static MonitorCacheEntry* free_entries;
     71 static PRUintn num_free_entries;
     72 static PRBool expanding;
     73 static MonitorCacheEntryBlock* mcache_blocks;
     74 
     75 static void (*OnMonitorRecycle)(void* address);
     76 
     77 #define HASH(address)                                                         \
     78  ((PRUint32)(((PRUptrdiff)(address) >> 2) ^ ((PRUptrdiff)(address) >> 10)) & \
     79   hash_mask)
     80 
     81 /*
     82 ** Expand the monitor cache. This grows the hash buckets and allocates a
     83 ** new chunk of cache entries and throws them on the free list. We keep
     84 ** as many hash buckets as there are entries.
     85 **
     86 ** Because we call malloc and malloc may need the monitor cache, we must
     87 ** ensure that there are several free monitor cache entries available for
     88 ** malloc to get. FREE_THRESHOLD is used to prevent monitor cache
     89 ** starvation during monitor cache expansion.
     90 */
     91 
     92 #define FREE_THRESHOLD 5
     93 
     94 static PRStatus ExpandMonitorCache(PRUintn new_size_log2) {
     95  MonitorCacheEntry **old_hash_buckets, *p;
     96  PRUintn i, entries, old_num_hash_buckets, added;
     97  MonitorCacheEntry** new_hash_buckets;
     98  MonitorCacheEntryBlock* new_block;
     99 
    100  entries = 1L << new_size_log2;
    101 
    102  /*
    103  ** Expand the monitor-cache-entry free list
    104  */
    105  new_block = (MonitorCacheEntryBlock*)PR_CALLOC(
    106      sizeof(MonitorCacheEntryBlock) +
    107      (entries - 1) * sizeof(MonitorCacheEntry));
    108  if (NULL == new_block) {
    109    return PR_FAILURE;
    110  }
    111 
    112  /*
    113  ** Allocate system monitors for the new monitor cache entries. If we
    114  ** run out of system monitors, break out of the loop.
    115  */
    116  for (i = 0, p = new_block->entries; i < entries; i++, p++) {
    117    p->mon = PR_NewMonitor();
    118    if (!p->mon) {
    119      break;
    120    }
    121  }
    122  added = i;
    123  if (added != entries) {
    124    MonitorCacheEntryBlock* realloc_block;
    125 
    126    if (added == 0) {
    127      /* Totally out of system monitors. Lossage abounds */
    128      PR_DELETE(new_block);
    129      return PR_FAILURE;
    130    }
    131 
    132    /*
    133    ** We were able to allocate some of the system monitors. Use
    134    ** realloc to shrink down the new_block memory. If that fails,
    135    ** carry on with the too-large new_block.
    136    */
    137    realloc_block = (MonitorCacheEntryBlock*)PR_REALLOC(
    138        new_block, sizeof(MonitorCacheEntryBlock) +
    139                       (added - 1) * sizeof(MonitorCacheEntry));
    140    if (realloc_block) {
    141      new_block = realloc_block;
    142    }
    143  }
    144 
    145  /*
    146  ** Now that we have allocated all of the system monitors, build up
    147  ** the new free list. We can just update the free_list because we own
    148  ** the mcache-lock and we aren't calling anyone who might want to use
    149  ** it.
    150  */
    151  for (i = 0, p = new_block->entries; i < added - 1; i++, p++) {
    152    p->next = p + 1;
    153  }
    154  p->next = free_entries;
    155  free_entries = new_block->entries;
    156  num_free_entries += added;
    157  new_block->next = mcache_blocks;
    158  mcache_blocks = new_block;
    159 
    160  /* Try to expand the hash table */
    161  new_hash_buckets =
    162      (MonitorCacheEntry**)PR_CALLOC(entries * sizeof(MonitorCacheEntry*));
    163  if (NULL == new_hash_buckets) {
    164    /*
    165    ** Partial lossage. In this situation we don't get any more hash
    166    ** buckets, which just means that the table lookups will take
    167    ** longer. This is bad, but not fatal
    168    */
    169    PR_LOG(_pr_cmon_lm, PR_LOG_WARNING,
    170           ("unable to grow monitor cache hash buckets"));
    171    return PR_SUCCESS;
    172  }
    173 
    174  /*
    175  ** Compute new hash mask value. This value is used to mask an address
    176  ** until it's bits are in the right spot for indexing into the hash
    177  ** table.
    178  */
    179  hash_mask = entries - 1;
    180 
    181  /*
    182  ** Expand the hash table. We have to rehash everything in the old
    183  ** table into the new table.
    184  */
    185  old_hash_buckets = hash_buckets;
    186  old_num_hash_buckets = num_hash_buckets;
    187  for (i = 0; i < old_num_hash_buckets; i++) {
    188    p = old_hash_buckets[i];
    189    while (p) {
    190      MonitorCacheEntry* next = p->next;
    191 
    192      /* Hash based on new table size, and then put p in the new table */
    193      PRUintn hash = HASH(p->address);
    194      p->next = new_hash_buckets[hash];
    195      new_hash_buckets[hash] = p;
    196 
    197      p = next;
    198    }
    199  }
    200 
    201  /*
    202  ** Switch over to new hash table and THEN call free of the old
    203  ** table. Since free might re-enter _pr_mcache_lock, things would
    204  ** break terribly if it used the old hash table.
    205  */
    206  hash_buckets = new_hash_buckets;
    207  num_hash_buckets = entries;
    208  num_hash_buckets_log2 = new_size_log2;
    209  PR_DELETE(old_hash_buckets);
    210 
    211  PR_LOG(
    212      _pr_cmon_lm, PR_LOG_NOTICE,
    213      ("expanded monitor cache to %d (buckets %d)", num_free_entries, entries));
    214 
    215  return PR_SUCCESS;
    216 } /* ExpandMonitorCache */
    217 
    218 /*
    219 ** Lookup a monitor cache entry by address. Return a pointer to the
    220 ** pointer to the monitor cache entry on success, null on failure.
    221 */
    222 static MonitorCacheEntry** LookupMonitorCacheEntry(void* address) {
    223  PRUintn hash;
    224  MonitorCacheEntry **pp, *p;
    225 
    226  hash = HASH(address);
    227  pp = hash_buckets + hash;
    228  while ((p = *pp) != 0) {
    229    if (p->address == address) {
    230      if (p->cacheEntryCount > 0) {
    231        return pp;
    232      }
    233      return NULL;
    234    }
    235    pp = &p->next;
    236  }
    237  return NULL;
    238 }
    239 
    240 /*
    241 ** Try to create a new cached monitor. If it's already in the cache,
    242 ** great - return it. Otherwise get a new free cache entry and set it
    243 ** up. If the cache free space is getting low, expand the cache.
    244 */
    245 static PRMonitor* CreateMonitor(void* address) {
    246  PRUintn hash;
    247  MonitorCacheEntry **pp, *p;
    248 
    249  hash = HASH(address);
    250  pp = hash_buckets + hash;
    251  while ((p = *pp) != 0) {
    252    if (p->address == address) {
    253      goto gotit;
    254    }
    255 
    256    pp = &p->next;
    257  }
    258 
    259  /* Expand the monitor cache if we have run out of free slots in the table */
    260  if (num_free_entries < FREE_THRESHOLD) {
    261    /* Expand monitor cache */
    262 
    263    /*
    264    ** This function is called with the lock held. So what's the 'expanding'
    265    ** boolean all about? Seems a bit redundant.
    266    */
    267    if (!expanding) {
    268      PRStatus rv;
    269 
    270      expanding = PR_TRUE;
    271      rv = ExpandMonitorCache(num_hash_buckets_log2 + 1);
    272      expanding = PR_FALSE;
    273      if (PR_FAILURE == rv) {
    274        return NULL;
    275      }
    276 
    277      /* redo the hash because it'll be different now */
    278      hash = HASH(address);
    279    } else {
    280      /*
    281      ** We are in process of expanding and we need a cache
    282      ** monitor.  Make sure we have enough!
    283      */
    284      PR_ASSERT(num_free_entries > 0);
    285    }
    286  }
    287 
    288  /* Make a new monitor */
    289  p = free_entries;
    290  free_entries = p->next;
    291  num_free_entries--;
    292  if (OnMonitorRecycle && p->address) {
    293    OnMonitorRecycle(p->address);
    294  }
    295  p->address = address;
    296  p->next = hash_buckets[hash];
    297  hash_buckets[hash] = p;
    298  PR_ASSERT(p->cacheEntryCount == 0);
    299 
    300 gotit:
    301  p->cacheEntryCount++;
    302  return p->mon;
    303 }
    304 
    305 /*
    306 ** Initialize the monitor cache
    307 */
    308 void _PR_InitCMon(void) {
    309  _PR_NEW_LOCK_MCACHE();
    310  ExpandMonitorCache(3);
    311 }
    312 
    313 /*
    314 ** Destroy the monitor cache
    315 */
    316 void _PR_CleanupCMon(void) {
    317  _PR_DESTROY_LOCK_MCACHE();
    318 
    319  while (free_entries) {
    320    PR_DestroyMonitor(free_entries->mon);
    321    free_entries = free_entries->next;
    322  }
    323  num_free_entries = 0;
    324 
    325  while (mcache_blocks) {
    326    MonitorCacheEntryBlock* block;
    327 
    328    block = mcache_blocks;
    329    mcache_blocks = block->next;
    330    PR_DELETE(block);
    331  }
    332 
    333  PR_DELETE(hash_buckets);
    334  hash_mask = 0;
    335  num_hash_buckets = 0;
    336  num_hash_buckets_log2 = 0;
    337 
    338  expanding = PR_FALSE;
    339  OnMonitorRecycle = NULL;
    340 }
    341 
    342 /*
    343 ** Create monitor for address. Don't enter the monitor while we have the
    344 ** mcache locked because we might block!
    345 */
    346 PR_IMPLEMENT(PRMonitor*) PR_CEnterMonitor(void* address) {
    347  PRMonitor* mon;
    348 
    349  if (!_pr_initialized) {
    350    _PR_ImplicitInitialization();
    351  }
    352 
    353  _PR_LOCK_MCACHE();
    354  mon = CreateMonitor(address);
    355  _PR_UNLOCK_MCACHE();
    356 
    357  if (!mon) {
    358    return NULL;
    359  }
    360 
    361  PR_EnterMonitor(mon);
    362  return mon;
    363 }
    364 
    365 PR_IMPLEMENT(PRStatus) PR_CExitMonitor(void* address) {
    366  MonitorCacheEntry **pp, *p;
    367  PRStatus status = PR_SUCCESS;
    368 
    369  _PR_LOCK_MCACHE();
    370  pp = LookupMonitorCacheEntry(address);
    371  if (pp != NULL) {
    372    p = *pp;
    373    if (--p->cacheEntryCount == 0) {
    374      /*
    375      ** Nobody is using the system monitor. Put it on the cached free
    376      ** list. We are safe from somebody trying to use it because we
    377      ** have the mcache locked.
    378      */
    379      p->address = 0;         /* defensive move */
    380      *pp = p->next;          /* unlink from hash_buckets */
    381      p->next = free_entries; /* link into free list */
    382      free_entries = p;
    383      num_free_entries++; /* count it as free */
    384    }
    385    status = PR_ExitMonitor(p->mon);
    386  } else {
    387    status = PR_FAILURE;
    388  }
    389  _PR_UNLOCK_MCACHE();
    390 
    391  return status;
    392 }
    393 
    394 PR_IMPLEMENT(PRStatus) PR_CWait(void* address, PRIntervalTime ticks) {
    395  MonitorCacheEntry** pp;
    396  PRMonitor* mon;
    397 
    398  _PR_LOCK_MCACHE();
    399  pp = LookupMonitorCacheEntry(address);
    400  mon = pp ? ((*pp)->mon) : NULL;
    401  _PR_UNLOCK_MCACHE();
    402 
    403  if (mon == NULL) {
    404    return PR_FAILURE;
    405  }
    406  return PR_Wait(mon, ticks);
    407 }
    408 
    409 PR_IMPLEMENT(PRStatus) PR_CNotify(void* address) {
    410  MonitorCacheEntry** pp;
    411  PRMonitor* mon;
    412 
    413  _PR_LOCK_MCACHE();
    414  pp = LookupMonitorCacheEntry(address);
    415  mon = pp ? ((*pp)->mon) : NULL;
    416  _PR_UNLOCK_MCACHE();
    417 
    418  if (mon == NULL) {
    419    return PR_FAILURE;
    420  }
    421  return PR_Notify(mon);
    422 }
    423 
    424 PR_IMPLEMENT(PRStatus) PR_CNotifyAll(void* address) {
    425  MonitorCacheEntry** pp;
    426  PRMonitor* mon;
    427 
    428  _PR_LOCK_MCACHE();
    429  pp = LookupMonitorCacheEntry(address);
    430  mon = pp ? ((*pp)->mon) : NULL;
    431  _PR_UNLOCK_MCACHE();
    432 
    433  if (mon == NULL) {
    434    return PR_FAILURE;
    435  }
    436  return PR_NotifyAll(mon);
    437 }
    438 
    439 PR_IMPLEMENT(void)
    440 PR_CSetOnMonitorRecycle(void (*callback)(void* address)) {
    441  OnMonitorRecycle = callback;
    442 }