nsprpub/pr/src/threads/prcmon.c

   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 }