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: #include "primpl.h"
andre@0: 
andre@0: #include <stdlib.h>
andre@0: #include <stddef.h>
andre@0: 
andre@0: /* Lock used to lock the monitor cache */
andre@0: #ifdef _PR_NO_PREEMPT
andre@0: #define _PR_NEW_LOCK_MCACHE()
andre@0: #define _PR_DESTROY_LOCK_MCACHE()
andre@0: #define _PR_LOCK_MCACHE()
andre@0: #define _PR_UNLOCK_MCACHE()
andre@0: #else
andre@0: #ifdef _PR_LOCAL_THREADS_ONLY
andre@0: #define _PR_NEW_LOCK_MCACHE()
andre@0: #define _PR_DESTROY_LOCK_MCACHE()
andre@0: #define _PR_LOCK_MCACHE() { PRIntn _is; _PR_INTSOFF(_is)
andre@0: #define _PR_UNLOCK_MCACHE() _PR_INTSON(_is); }
andre@0: #else
andre@0: PRLock *_pr_mcacheLock;
andre@0: #define _PR_NEW_LOCK_MCACHE() (_pr_mcacheLock = PR_NewLock())
andre@0: #define _PR_DESTROY_LOCK_MCACHE()               \
andre@0:     PR_BEGIN_MACRO                              \
andre@0:         if (_pr_mcacheLock) {                   \
andre@0:             PR_DestroyLock(_pr_mcacheLock);     \
andre@0:             _pr_mcacheLock = NULL;              \
andre@0:         }                                       \
andre@0:     PR_END_MACRO
andre@0: #define _PR_LOCK_MCACHE() PR_Lock(_pr_mcacheLock)
andre@0: #define _PR_UNLOCK_MCACHE() PR_Unlock(_pr_mcacheLock)
andre@0: #endif
andre@0: #endif
andre@0: 
andre@0: /************************************************************************/
andre@0: 
andre@0: typedef struct MonitorCacheEntryStr MonitorCacheEntry;
andre@0: 
andre@0: struct MonitorCacheEntryStr {
andre@0:     MonitorCacheEntry*  next;
andre@0:     void*               address;
andre@0:     PRMonitor*          mon;
andre@0:     long                cacheEntryCount;
andre@0: };
andre@0: 
andre@0: /*
andre@0: ** An array of MonitorCacheEntry's, plus a pointer to link these
andre@0: ** arrays together.
andre@0: */
andre@0: 
andre@0: typedef struct MonitorCacheEntryBlockStr MonitorCacheEntryBlock;
andre@0: 
andre@0: struct MonitorCacheEntryBlockStr {
andre@0:     MonitorCacheEntryBlock* next;
andre@0:     MonitorCacheEntry entries[1];
andre@0: };
andre@0: 
andre@0: static PRUint32 hash_mask;
andre@0: static PRUintn num_hash_buckets;
andre@0: static PRUintn num_hash_buckets_log2;
andre@0: static MonitorCacheEntry **hash_buckets;
andre@0: static MonitorCacheEntry *free_entries;
andre@0: static PRUintn num_free_entries;
andre@0: static PRBool expanding;
andre@0: static MonitorCacheEntryBlock *mcache_blocks;
andre@0: 
andre@0: static void (*OnMonitorRecycle)(void *address);
andre@0: 
andre@0: #define HASH(address)                               \
andre@0:     ((PRUint32) ( ((PRUptrdiff)(address) >> 2) ^    \
andre@0:                   ((PRUptrdiff)(address) >> 10) )   \
andre@0:      & hash_mask)
andre@0: 
andre@0: /*
andre@0: ** Expand the monitor cache. This grows the hash buckets and allocates a
andre@0: ** new chunk of cache entries and throws them on the free list. We keep
andre@0: ** as many hash buckets as there are entries.
andre@0: **
andre@0: ** Because we call malloc and malloc may need the monitor cache, we must
andre@0: ** ensure that there are several free monitor cache entries available for
andre@0: ** malloc to get. FREE_THRESHOLD is used to prevent monitor cache
andre@0: ** starvation during monitor cache expansion.
andre@0: */
andre@0: 
andre@0: #define FREE_THRESHOLD  5
andre@0: 
andre@0: static PRStatus ExpandMonitorCache(PRUintn new_size_log2)
andre@0: {
andre@0:     MonitorCacheEntry **old_hash_buckets, *p;
andre@0:     PRUintn i, entries, old_num_hash_buckets, added;
andre@0:     MonitorCacheEntry **new_hash_buckets;
andre@0:     MonitorCacheEntryBlock *new_block;
andre@0: 
andre@0:     entries = 1L << new_size_log2;
andre@0: 
andre@0:     /*
andre@0:     ** Expand the monitor-cache-entry free list
andre@0:     */
andre@0:     new_block = (MonitorCacheEntryBlock*)
andre@0:         PR_CALLOC(sizeof(MonitorCacheEntryBlock)
andre@0:         + (entries - 1) * sizeof(MonitorCacheEntry));
andre@0:     if (NULL == new_block) return PR_FAILURE;
andre@0: 
andre@0:     /*
andre@0:     ** Allocate system monitors for the new monitor cache entries. If we
andre@0:     ** run out of system monitors, break out of the loop.
andre@0:     */
andre@0:     for (i = 0, p = new_block->entries; i < entries; i++, p++) {
andre@0:         p->mon = PR_NewMonitor();
andre@0:         if (!p->mon)
andre@0:             break;
andre@0:     }
andre@0:     added = i;
andre@0:     if (added != entries) {
andre@0:         MonitorCacheEntryBlock *realloc_block;
andre@0: 
andre@0:         if (added == 0) {
andre@0:             /* Totally out of system monitors. Lossage abounds */
andre@0:             PR_DELETE(new_block);
andre@0:             return PR_FAILURE;
andre@0:         }
andre@0: 
andre@0:         /*
andre@0:         ** We were able to allocate some of the system monitors. Use
andre@0:         ** realloc to shrink down the new_block memory. If that fails,
andre@0:         ** carry on with the too-large new_block.
andre@0:         */
andre@0:         realloc_block = (MonitorCacheEntryBlock*)
andre@0:             PR_REALLOC(new_block, sizeof(MonitorCacheEntryBlock)
andre@0:             + (added - 1) * sizeof(MonitorCacheEntry));
andre@0:         if (realloc_block)
andre@0:             new_block = realloc_block;
andre@0:     }
andre@0: 
andre@0:     /*
andre@0:     ** Now that we have allocated all of the system monitors, build up
andre@0:     ** the new free list. We can just update the free_list because we own
andre@0:     ** the mcache-lock and we aren't calling anyone who might want to use
andre@0:     ** it.
andre@0:     */
andre@0:     for (i = 0, p = new_block->entries; i < added - 1; i++, p++)
andre@0:         p->next = p + 1;
andre@0:     p->next = free_entries;
andre@0:     free_entries = new_block->entries;
andre@0:     num_free_entries += added;
andre@0:     new_block->next = mcache_blocks;
andre@0:     mcache_blocks = new_block;
andre@0: 
andre@0:     /* Try to expand the hash table */
andre@0:     new_hash_buckets = (MonitorCacheEntry**)
andre@0:         PR_CALLOC(entries * sizeof(MonitorCacheEntry*));
andre@0:     if (NULL == new_hash_buckets) {
andre@0:         /*
andre@0:         ** Partial lossage. In this situation we don't get any more hash
andre@0:         ** buckets, which just means that the table lookups will take
andre@0:         ** longer. This is bad, but not fatal
andre@0:         */
andre@0:         PR_LOG(_pr_cmon_lm, PR_LOG_WARNING,
andre@0:                ("unable to grow monitor cache hash buckets"));
andre@0:         return PR_SUCCESS;
andre@0:     }
andre@0: 
andre@0:     /*
andre@0:     ** Compute new hash mask value. This value is used to mask an address
andre@0:     ** until it's bits are in the right spot for indexing into the hash
andre@0:     ** table.
andre@0:     */
andre@0:     hash_mask = entries - 1;
andre@0: 
andre@0:     /*
andre@0:     ** Expand the hash table. We have to rehash everything in the old
andre@0:     ** table into the new table.
andre@0:     */
andre@0:     old_hash_buckets = hash_buckets;
andre@0:     old_num_hash_buckets = num_hash_buckets;
andre@0:     for (i = 0; i < old_num_hash_buckets; i++) {
andre@0:         p = old_hash_buckets[i];
andre@0:         while (p) {
andre@0:             MonitorCacheEntry *next = p->next;
andre@0: 
andre@0:             /* Hash based on new table size, and then put p in the new table */
andre@0:             PRUintn hash = HASH(p->address);
andre@0:             p->next = new_hash_buckets[hash];
andre@0:             new_hash_buckets[hash] = p;
andre@0: 
andre@0:             p = next;
andre@0:         }
andre@0:     }
andre@0: 
andre@0:     /*
andre@0:     ** Switch over to new hash table and THEN call free of the old
andre@0:     ** table. Since free might re-enter _pr_mcache_lock, things would
andre@0:     ** break terribly if it used the old hash table.
andre@0:     */
andre@0:     hash_buckets = new_hash_buckets;
andre@0:     num_hash_buckets = entries;
andre@0:     num_hash_buckets_log2 = new_size_log2;
andre@0:     PR_DELETE(old_hash_buckets);
andre@0: 
andre@0:     PR_LOG(_pr_cmon_lm, PR_LOG_NOTICE,
andre@0:            ("expanded monitor cache to %d (buckets %d)",
andre@0:             num_free_entries, entries));
andre@0: 
andre@0:     return PR_SUCCESS;
andre@0: }  /* ExpandMonitorCache */
andre@0: 
andre@0: /*
andre@0: ** Lookup a monitor cache entry by address. Return a pointer to the
andre@0: ** pointer to the monitor cache entry on success, null on failure.
andre@0: */
andre@0: static MonitorCacheEntry **LookupMonitorCacheEntry(void *address)
andre@0: {
andre@0:     PRUintn hash;
andre@0:     MonitorCacheEntry **pp, *p;
andre@0: 
andre@0:     hash = HASH(address);
andre@0:     pp = hash_buckets + hash;
andre@0:     while ((p = *pp) != 0) {
andre@0:         if (p->address == address) {
andre@0:             if (p->cacheEntryCount > 0)
andre@0:                 return pp;
andre@0:             return NULL;
andre@0:         }
andre@0:         pp = &p->next;
andre@0:     }
andre@0:     return NULL;
andre@0: }
andre@0: 
andre@0: /*
andre@0: ** Try to create a new cached monitor. If it's already in the cache,
andre@0: ** great - return it. Otherwise get a new free cache entry and set it
andre@0: ** up. If the cache free space is getting low, expand the cache.
andre@0: */
andre@0: static PRMonitor *CreateMonitor(void *address)
andre@0: {
andre@0:     PRUintn hash;
andre@0:     MonitorCacheEntry **pp, *p;
andre@0: 
andre@0:     hash = HASH(address);
andre@0:     pp = hash_buckets + hash;
andre@0:     while ((p = *pp) != 0) {
andre@0:         if (p->address == address) goto gotit;
andre@0: 
andre@0:         pp = &p->next;
andre@0:     }
andre@0: 
andre@0:     /* Expand the monitor cache if we have run out of free slots in the table */
andre@0:     if (num_free_entries < FREE_THRESHOLD) {
andre@0:         /* Expand monitor cache */
andre@0: 
andre@0:         /*
andre@0:         ** This function is called with the lock held. So what's the 'expanding'
andre@0:         ** boolean all about? Seems a bit redundant.
andre@0:         */
andre@0:         if (!expanding) {
andre@0:             PRStatus rv;
andre@0: 
andre@0:             expanding = PR_TRUE;
andre@0:             rv = ExpandMonitorCache(num_hash_buckets_log2 + 1);
andre@0:             expanding = PR_FALSE;
andre@0:             if (PR_FAILURE == rv)  return NULL;
andre@0: 
andre@0:             /* redo the hash because it'll be different now */
andre@0:             hash = HASH(address);
andre@0:         } else {
andre@0:             /*
andre@0:             ** We are in process of expanding and we need a cache
andre@0:             ** monitor.  Make sure we have enough!
andre@0:             */
andre@0:             PR_ASSERT(num_free_entries > 0);
andre@0:         }
andre@0:     }
andre@0: 
andre@0:     /* Make a new monitor */
andre@0:     p = free_entries;
andre@0:     free_entries = p->next;
andre@0:     num_free_entries--;
andre@0:     if (OnMonitorRecycle && p->address)
andre@0:         OnMonitorRecycle(p->address);
andre@0:     p->address = address;
andre@0:     p->next = hash_buckets[hash];
andre@0:     hash_buckets[hash] = p;
andre@0:     PR_ASSERT(p->cacheEntryCount == 0);
andre@0: 
andre@0:   gotit:
andre@0:     p->cacheEntryCount++;
andre@0:     return p->mon;
andre@0: }
andre@0: 
andre@0: /*
andre@0: ** Initialize the monitor cache
andre@0: */
andre@0: void _PR_InitCMon(void)
andre@0: {
andre@0:     _PR_NEW_LOCK_MCACHE();
andre@0:     ExpandMonitorCache(3);
andre@0: }
andre@0: 
andre@0: /*
andre@0: ** Destroy the monitor cache
andre@0: */
andre@0: void _PR_CleanupCMon(void)
andre@0: {
andre@0:     _PR_DESTROY_LOCK_MCACHE();
andre@0: 
andre@0:     while (free_entries) {
andre@0:         PR_DestroyMonitor(free_entries->mon);
andre@0:         free_entries = free_entries->next;
andre@0:     }
andre@0:     num_free_entries = 0;
andre@0: 
andre@0:     while (mcache_blocks) {
andre@0:         MonitorCacheEntryBlock *block;
andre@0: 
andre@0:         block = mcache_blocks;
andre@0:         mcache_blocks = block->next;
andre@0:         PR_DELETE(block);
andre@0:     }
andre@0: 
andre@0:     PR_DELETE(hash_buckets);
andre@0:     hash_mask = 0;
andre@0:     num_hash_buckets = 0;
andre@0:     num_hash_buckets_log2 = 0;
andre@0: 
andre@0:     expanding = PR_FALSE;
andre@0:     OnMonitorRecycle = NULL;
andre@0: }
andre@0: 
andre@0: /*
andre@0: ** Create monitor for address. Don't enter the monitor while we have the
andre@0: ** mcache locked because we might block!
andre@0: */
andre@0: PR_IMPLEMENT(PRMonitor*) PR_CEnterMonitor(void *address)
andre@0: {
andre@0:     PRMonitor *mon;
andre@0: 
andre@0:     if (!_pr_initialized) _PR_ImplicitInitialization();
andre@0: 
andre@0:     _PR_LOCK_MCACHE();
andre@0:     mon = CreateMonitor(address);
andre@0:     _PR_UNLOCK_MCACHE();
andre@0: 
andre@0:     if (!mon) return NULL;
andre@0: 
andre@0:     PR_EnterMonitor(mon);
andre@0:     return mon;
andre@0: }
andre@0: 
andre@0: PR_IMPLEMENT(PRStatus) PR_CExitMonitor(void *address)
andre@0: {
andre@0:     MonitorCacheEntry **pp, *p;
andre@0:     PRStatus status = PR_SUCCESS;
andre@0: 
andre@0:     _PR_LOCK_MCACHE();
andre@0:     pp = LookupMonitorCacheEntry(address);
andre@0:     if (pp != NULL) {
andre@0:         p = *pp;
andre@0:         if (--p->cacheEntryCount == 0) {
andre@0:             /*
andre@0:             ** Nobody is using the system monitor. Put it on the cached free
andre@0:             ** list. We are safe from somebody trying to use it because we
andre@0:             ** have the mcache locked.
andre@0:             */
andre@0:             p->address = 0;             /* defensive move */
andre@0:             *pp = p->next;              /* unlink from hash_buckets */
andre@0:             p->next = free_entries;     /* link into free list */
andre@0:             free_entries = p;
andre@0:             num_free_entries++;         /* count it as free */
andre@0:         }
andre@0:         status = PR_ExitMonitor(p->mon);
andre@0:     } else {
andre@0:         status = PR_FAILURE;
andre@0:     }
andre@0:     _PR_UNLOCK_MCACHE();
andre@0: 
andre@0:     return status;
andre@0: }
andre@0: 
andre@0: PR_IMPLEMENT(PRStatus) PR_CWait(void *address, PRIntervalTime ticks)
andre@0: {
andre@0:     MonitorCacheEntry **pp;
andre@0:     PRMonitor *mon;
andre@0: 
andre@0:     _PR_LOCK_MCACHE();
andre@0:     pp = LookupMonitorCacheEntry(address);
andre@0:     mon = pp ? ((*pp)->mon) : NULL;
andre@0:     _PR_UNLOCK_MCACHE();
andre@0: 
andre@0:     if (mon == NULL)
andre@0:         return PR_FAILURE;
andre@0:     return PR_Wait(mon, ticks);
andre@0: }
andre@0: 
andre@0: PR_IMPLEMENT(PRStatus) PR_CNotify(void *address)
andre@0: {
andre@0:     MonitorCacheEntry **pp;
andre@0:     PRMonitor *mon;
andre@0: 
andre@0:     _PR_LOCK_MCACHE();
andre@0:     pp = LookupMonitorCacheEntry(address);
andre@0:     mon = pp ? ((*pp)->mon) : NULL;
andre@0:     _PR_UNLOCK_MCACHE();
andre@0: 
andre@0:     if (mon == NULL)
andre@0:         return PR_FAILURE;
andre@0:     return PR_Notify(mon);
andre@0: }
andre@0: 
andre@0: PR_IMPLEMENT(PRStatus) PR_CNotifyAll(void *address)
andre@0: {
andre@0:     MonitorCacheEntry **pp;
andre@0:     PRMonitor *mon;
andre@0: 
andre@0:     _PR_LOCK_MCACHE();
andre@0:     pp = LookupMonitorCacheEntry(address);
andre@0:     mon = pp ? ((*pp)->mon) : NULL;
andre@0:     _PR_UNLOCK_MCACHE();
andre@0: 
andre@0:     if (mon == NULL)
andre@0:         return PR_FAILURE;
andre@0:     return PR_NotifyAll(mon);
andre@0: }
andre@0: 
andre@0: PR_IMPLEMENT(void)
andre@0: PR_CSetOnMonitorRecycle(void (*callback)(void *address))
andre@0: {
andre@0:     OnMonitorRecycle = callback;
andre@0: }