summaryrefslogtreecommitdiffstats
path: root/src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp')
-rw-r--r--src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp443
1 files changed, 443 insertions, 0 deletions
diff --git a/src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp b/src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp
new file mode 100644
index 00000000..241f795c
--- /dev/null
+++ b/src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp
@@ -0,0 +1,443 @@
+/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2001, 2002
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ * Suresh Duddi <dp@netscape.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+/*
+ * nsRecyclingAllocator
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include "nsRecyclingAllocator.h"
+#include "nsIMemory.h"
+#include "nsAutoLock.h"
+#include "prprf.h"
+#include "nsITimer.h"
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+# include <iprt/mem.h>
+#endif
+
+#define NS_SEC_TO_MS(s) ((s) * 1000)
+
+void
+nsRecyclingAllocator::nsRecycleTimerCallback(nsITimer *aTimer, void *aClosure)
+{
+ nsRecyclingAllocator *obj = (nsRecyclingAllocator *) aClosure;
+ if (!obj->mTouched)
+ {
+ if (obj->mFreeList)
+ obj->FreeUnusedBuckets();
+
+ // If we are holding no more memory, there is no need for the timer.
+ // We will revive the timer on the next allocation.
+ // XXX Unfortunately there is no way to Cancel and restart the same timer.
+ // XXX So we pretty much kill it and create a new one later.
+ if (!obj->mFreeList && obj->mRecycleTimer)
+ {
+ obj->mRecycleTimer->Cancel();
+ NS_RELEASE(obj->mRecycleTimer);
+ }
+ }
+ else
+ {
+ // Clear touched so the next time the timer fires we can test whether
+ // the allocator was used or not.
+ obj->Untouch();
+ }
+}
+
+
+nsRecyclingAllocator::nsRecyclingAllocator(PRUint32 nbucket, PRUint32 recycleAfter, const char *id) :
+ mMaxBlocks(nbucket), mBlocks(nsnull), mFreeList(nsnull), mNotUsedList(nsnull),
+ mRecycleTimer(nsnull), mRecycleAfter(recycleAfter), mTouched(0), mId(id)
+#ifdef DEBUG
+ ,mNAllocated(0)
+#endif
+{
+ NS_ASSERTION(mMaxBlocks <= NS_MAX_BLOCKS, "Too many blocks. This will affect the allocator's performance.");
+
+ mLock = PR_NewLock();
+ NS_ASSERTION(mLock, "Recycling allocator cannot get lock");
+
+ Init(nbucket, recycleAfter, id);
+}
+
+nsresult
+nsRecyclingAllocator::Init(PRUint32 nbucket, PRUint32 recycleAfter, const char *id)
+{
+ nsAutoLock lock(mLock);
+
+ // Free all memory held, if any
+ while(mFreeList)
+ {
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+ RTMemFree(mFreeList->block);
+#else
+ free(mFreeList->block);
+#endif
+ mFreeList = mFreeList->next;
+ }
+ mFreeList = nsnull;
+
+ if (mBlocks)
+ delete [] mBlocks;
+
+ // Reinitialize everything
+ mMaxBlocks = nbucket;
+ if (nbucket)
+ {
+ // Create memory for our bookkeeping
+ mBlocks = new BlockStoreNode[mMaxBlocks];
+ if (!mBlocks)
+ return NS_ERROR_OUT_OF_MEMORY;
+ // Link them together
+ mNotUsedList = mBlocks;
+ for (PRUint32 i=0; i < mMaxBlocks-1; i++)
+ mBlocks[i].next = &(mBlocks[i+1]);
+ }
+
+ mRecycleAfter = recycleAfter;
+ mId = id;
+
+ return NS_OK;
+}
+
+nsRecyclingAllocator::~nsRecyclingAllocator()
+{
+ // Cancel and destroy recycle timer
+ if (mRecycleTimer)
+ {
+ mRecycleTimer->Cancel();
+ NS_RELEASE(mRecycleTimer);
+ }
+
+ // Free all memory held, if any
+ while(mFreeList)
+ {
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+ RTMemFree(mFreeList->block);
+#else
+ free(mFreeList->block);
+#endif
+ mFreeList = mFreeList->next;
+ }
+ mFreeList = nsnull;
+
+ if (mBlocks)
+ delete [] mBlocks;
+
+ if (mLock)
+ {
+ PR_DestroyLock(mLock);
+ mLock = nsnull;
+ }
+}
+
+// Allocation and free routines
+void*
+nsRecyclingAllocator::Malloc(PRSize bytes, PRBool zeroit)
+{
+ // Mark that we are using. This will prevent any
+ // timer based release of unused memory.
+ Touch();
+
+ Block* freeBlock = FindFreeBlock(bytes);
+ if (freeBlock)
+ {
+ void *data = DATA(freeBlock);
+
+ if (zeroit)
+ memset(data, 0, bytes);
+ return data;
+ }
+
+ // We need to do an allocation
+ // Add 4 bytes to what we allocate to hold the bucket index
+ PRSize allocBytes = bytes + NS_ALLOCATOR_OVERHEAD_BYTES;
+
+ // We dont have that memory already. Allocate.
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+ Block *ptr = (Block *) (zeroit ? RTMemAllocZ(allocBytes) : RTMemAlloc(allocBytes));
+#else
+ Block *ptr = (Block *) (zeroit ? calloc(1, allocBytes) : malloc(allocBytes));
+#endif
+
+ // Deal with no memory situation
+ if (!ptr)
+ return ptr;
+
+ // This is the first allocation we are holding.
+ // Setup timer for releasing memory
+ // If this fails, then we wont have a timer to release unused
+ // memory. We can live with that. Also, the next allocation
+ // will try again to set the timer.
+ if (mRecycleAfter && !mRecycleTimer)
+ {
+ // known only to stuff in xpcom.
+ extern nsresult NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosure,
+ PRUint32 aDelay, PRUint32 aType);
+
+ (void) NS_NewTimer(&mRecycleTimer, nsRecycleTimerCallback, this,
+ NS_SEC_TO_MS(mRecycleAfter),
+ nsITimer::TYPE_REPEATING_SLACK);
+ NS_ASSERTION(mRecycleTimer, "nsRecyclingAllocator: Creating timer failed.\n");
+ }
+
+#ifdef DEBUG
+ mNAllocated++;
+#endif
+
+ // Store size and return data portion
+ ptr->bytes = bytes;
+ return DATA(ptr);
+}
+
+void
+nsRecyclingAllocator::Free(void *ptr)
+{
+ // Mark that we are using the allocator. This will prevent any
+ // timer based release of unused memory.
+ Touch();
+
+ Block* block = DATA_TO_BLOCK(ptr);
+
+ if (!AddToFreeList(block))
+ {
+ // We are holding more than max. Failover to free
+#ifdef DEBUG_dp
+ char buf[1024];
+ // Warn if we are failing over to malloc/free and not storing it
+ // This says we have a misdesigned memory pool. The intent was
+ // once the pool was full, we would never fail over to calloc.
+ PR_snprintf(buf, sizeof(buf), "nsRecyclingAllocator(%s) FAILOVER 0x%p (%d) - %d allocations, %d max\n",
+ mId, (char *)ptr, block->bytes, mNAllocated, mMaxBlocks);
+ NS_WARNING(buf);
+ mNAllocated--;
+#endif
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+ RTMemFree(block);
+#else
+ free(block);
+#endif
+ }
+}
+
+/* FreeUnusedBuckets
+ *
+ * Frees any bucket memory that isn't in use
+ */
+
+void
+nsRecyclingAllocator::FreeUnusedBuckets()
+{
+#ifdef DEBUG_dp
+ printf("DEBUG: nsRecyclingAllocator(%s) FreeUnusedBuckets: ", mId);
+#endif
+ nsAutoLock lock(mLock);
+
+ // We will run through the freelist and free all blocks
+ BlockStoreNode* node = mFreeList;
+ while (node)
+ {
+ // Free the allocated block
+#ifdef VBOX_USE_IPRT_IN_XPCOM
+ RTMemFree(node->block);
+#else
+ free(node->block);
+#endif
+
+#ifdef DEBUG_dp
+ printf("%d ", node->bytes);
+#endif
+ // Clear Node
+ node->block = nsnull;
+ node->bytes = 0;
+ node = node->next;
+ }
+
+ // remake the lists
+ mNotUsedList = mBlocks;
+ for (PRUint32 i=0; i < mMaxBlocks-1; i++)
+ mBlocks[i].next = &(mBlocks[i+1]);
+ mBlocks[mMaxBlocks-1].next = nsnull;
+ mFreeList = nsnull;
+
+#ifdef DEBUG
+ mNAllocated = 0;
+#endif
+#ifdef DEBUG_dp
+ printf("\n");
+#endif
+}
+
+nsRecyclingAllocator::Block*
+nsRecyclingAllocator::FindFreeBlock(PRSize bytes)
+{
+ // We dont enter lock for this check. This is intentional.
+ // Here is my logic: we are checking if (!mFreeList). Doing this check
+ // without locking can lead to unpredictable results. YES. But the effect
+ // of the unpredictedness are ok. here is why:
+ //
+ // a) if the check returned NULL when there is stuff in freelist
+ // We would just end up reallocating.
+ //
+ // b) if the check returned nonNULL when our freelist is empty
+ // This is the more likely and dangerous case. The code for
+ // FindFreeBlock() will enter lock, while (null) and return null.
+ //
+ // The reason why I chose to not enter lock for this check was that when
+ // the allocator is full, we dont want to impose any more overhead than
+ // we already are for failing over to malloc/free.
+
+ if (!mFreeList)
+ return NULL;
+
+ Block *block = nsnull;
+
+ nsAutoLock lock(mLock);
+ BlockStoreNode* freeNode = mFreeList;
+ BlockStoreNode** prevp = &mFreeList;
+
+ while (freeNode)
+ {
+ if (freeNode->bytes >= bytes)
+ {
+ // Found the best fit free block
+ block = freeNode->block;
+
+ // Clear the free node
+ freeNode->block = nsnull;
+ freeNode->bytes = 0;
+
+ // Remove free node from free list
+ *prevp = freeNode->next;
+
+ // Add removed BlockStoreNode to not used list
+ freeNode->next = mNotUsedList;
+ mNotUsedList = freeNode;
+
+ break;
+ }
+
+ prevp = &(freeNode->next);
+ freeNode = freeNode->next;
+ }
+ return block;
+}
+
+PRInt32
+nsRecyclingAllocator::AddToFreeList(Block* block)
+{
+ nsAutoLock lock(mLock);
+
+ if (!mNotUsedList)
+ return PR_FALSE;
+
+ // Pick a node from the not used list
+ BlockStoreNode *node = mNotUsedList;
+ mNotUsedList = mNotUsedList->next;
+
+ // Initialize the node
+ node->bytes = block->bytes;
+ node->block = block;
+
+ // Find the right spot in the sorted list.
+ BlockStoreNode* freeNode = mFreeList;
+ BlockStoreNode** prevp = &mFreeList;
+ while (freeNode)
+ {
+ if (freeNode->bytes >= block->bytes)
+ break;
+ prevp = &(freeNode->next);
+ freeNode = freeNode->next;
+ }
+
+ // Needs to be inserted between *prevp and freeNode
+ *prevp = node;
+ node->next = freeNode;
+
+ return PR_TRUE;
+}
+
+
+// ----------------------------------------------------------------------
+// Wrapping the recyling allocator with nsIMemory
+// ----------------------------------------------------------------------
+
+// nsIMemory methods
+NS_IMPL_THREADSAFE_ISUPPORTS2(nsRecyclingAllocatorImpl, nsIMemory, nsIRecyclingAllocator)
+
+NS_IMETHODIMP_(void *)
+nsRecyclingAllocatorImpl::Alloc(PRSize size)
+{
+ return nsRecyclingAllocatorImpl::Malloc(size, PR_FALSE);
+}
+
+NS_IMETHODIMP_(void *)
+nsRecyclingAllocatorImpl::Realloc(void *ptr, PRSize size)
+{
+ // XXX Not yet implemented
+ return NULL;
+}
+
+NS_IMETHODIMP_(void)
+nsRecyclingAllocatorImpl::Free(void *ptr)
+{
+ nsRecyclingAllocator::Free(ptr);
+}
+
+NS_IMETHODIMP
+nsRecyclingAllocatorImpl::Init(size_t nbuckets, size_t recycleAfter, const char *id)
+{
+ return nsRecyclingAllocator::Init((PRUint32) nbuckets, (PRUint32) recycleAfter, id);
+}
+
+NS_IMETHODIMP
+nsRecyclingAllocatorImpl::HeapMinimize(PRBool immediate)
+{
+ // XXX Not yet implemented
+ return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+NS_IMETHODIMP
+nsRecyclingAllocatorImpl::IsLowMemory(PRBool *lowmemoryb_ptr)
+{
+ // XXX Not yet implemented
+ return NS_ERROR_NOT_IMPLEMENTED;
+}
+