Back to index

lightning-sunbird  0.9+nobinonly
nsRecyclingAllocator.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 2001, 2002
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *     Suresh Duddi <dp@netscape.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 /*
00040  * nsRecyclingAllocator
00041  */
00042 
00043 #include <stdlib.h>
00044 #include <string.h>
00045 #include <stdio.h>
00046 #include "nsRecyclingAllocator.h"
00047 #include "nsIMemory.h"
00048 #include "nsAutoLock.h"
00049 #include "prprf.h"
00050 #include "nsITimer.h"
00051 
00052 #define NS_SEC_TO_MS(s) ((s) * 1000)
00053 
00054 void
00055 nsRecyclingAllocator::nsRecycleTimerCallback(nsITimer *aTimer, void *aClosure)
00056 {
00057     nsRecyclingAllocator *obj = (nsRecyclingAllocator *) aClosure;
00058     if (!obj->mTouched)
00059     {
00060         if (obj->mFreeList)
00061             obj->FreeUnusedBuckets();
00062 
00063         // If we are holding no more memory, there is no need for the timer.
00064         // We will revive the timer on the next allocation.
00065         // XXX Unfortunately there is no way to Cancel and restart the same timer.
00066         // XXX So we pretty much kill it and create a new one later.
00067         if (!obj->mFreeList && obj->mRecycleTimer)
00068         {
00069             obj->mRecycleTimer->Cancel();
00070             NS_RELEASE(obj->mRecycleTimer);
00071         }
00072     }
00073     else
00074     {
00075         // Clear touched so the next time the timer fires we can test whether
00076         // the allocator was used or not.
00077         obj->Untouch();
00078     }
00079 }
00080 
00081 
00082 nsRecyclingAllocator::nsRecyclingAllocator(PRUint32 nbucket, PRUint32 recycleAfter, const char *id) :
00083     mMaxBlocks(nbucket), mBlocks(nsnull), mFreeList(nsnull), mNotUsedList(nsnull),
00084     mRecycleTimer(nsnull), mRecycleAfter(recycleAfter), mTouched(0), mId(id)
00085 #ifdef DEBUG
00086      ,mNAllocated(0)
00087 #endif
00088 {
00089     NS_ASSERTION(mMaxBlocks <= NS_MAX_BLOCKS, "Too many blocks. This will affect the allocator's performance.");
00090 
00091     mLock = PR_NewLock();
00092     NS_ASSERTION(mLock, "Recycling allocator cannot get lock");
00093 
00094     Init(nbucket, recycleAfter, id);
00095 }
00096 
00097 nsresult
00098 nsRecyclingAllocator::Init(PRUint32 nbucket, PRUint32 recycleAfter, const char *id)
00099 {
00100     nsAutoLock lock(mLock);
00101 
00102     // Free all memory held, if any
00103     while(mFreeList)
00104     {
00105         free(mFreeList->block);
00106         mFreeList = mFreeList->next;
00107     }
00108     mFreeList = nsnull;
00109     
00110     if (mBlocks)
00111         delete [] mBlocks;
00112 
00113     // Reinitialize everything
00114     mMaxBlocks = nbucket;
00115     if (nbucket)
00116     {
00117         // Create memory for our bookkeeping
00118         mBlocks = new BlockStoreNode[mMaxBlocks];
00119         if (!mBlocks)
00120             return NS_ERROR_OUT_OF_MEMORY;
00121         // Link them together
00122         mNotUsedList = mBlocks;
00123         for (PRUint32 i=0; i < mMaxBlocks-1; i++)
00124             mBlocks[i].next = &(mBlocks[i+1]);
00125     }
00126 
00127     mRecycleAfter = recycleAfter;
00128     mId = id;
00129 
00130     return NS_OK;
00131 }
00132 
00133 nsRecyclingAllocator::~nsRecyclingAllocator()
00134 {
00135     // Cancel and destroy recycle timer
00136     if (mRecycleTimer)
00137     {
00138         mRecycleTimer->Cancel();
00139         NS_RELEASE(mRecycleTimer);
00140     }
00141 
00142     // Free all memory held, if any
00143     while(mFreeList)
00144     {
00145         free(mFreeList->block);
00146         mFreeList = mFreeList->next;
00147     }
00148     mFreeList = nsnull;
00149     
00150     if (mBlocks)
00151         delete [] mBlocks;
00152 
00153     if (mLock)
00154     {
00155         PR_DestroyLock(mLock);
00156         mLock = nsnull;
00157     }
00158 }
00159 
00160 // Allocation and free routines
00161 void*
00162 nsRecyclingAllocator::Malloc(PRSize bytes, PRBool zeroit)
00163 {
00164     // Mark that we are using. This will prevent any
00165     // timer based release of unused memory.
00166     Touch();
00167   
00168     Block* freeBlock = FindFreeBlock(bytes);
00169     if (freeBlock)
00170     {
00171         void *data = DATA(freeBlock);
00172 
00173         if (zeroit)
00174             memset(data, 0, bytes);
00175         return data;
00176     }
00177      
00178     // We need to do an allocation
00179     // Add 4 bytes to what we allocate to hold the bucket index
00180     PRSize allocBytes = bytes + NS_ALLOCATOR_OVERHEAD_BYTES;
00181   
00182     // We dont have that memory already. Allocate.
00183     Block *ptr = (Block *) (zeroit ? calloc(1, allocBytes) : malloc(allocBytes));
00184     
00185     // Deal with no memory situation
00186     if (!ptr)
00187         return ptr;
00188   
00189     // This is the first allocation we are holding.
00190     // Setup timer for releasing memory
00191     // If this fails, then we wont have a timer to release unused
00192     // memory. We can live with that. Also, the next allocation
00193     // will try again to set the timer.
00194     if (mRecycleAfter && !mRecycleTimer)
00195     {
00196         // known only to stuff in xpcom.  
00197         extern nsresult NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosure,
00198                                     PRUint32 aDelay, PRUint32 aType);
00199 
00200         (void) NS_NewTimer(&mRecycleTimer, nsRecycleTimerCallback, this, 
00201                            NS_SEC_TO_MS(mRecycleAfter),
00202                            nsITimer::TYPE_REPEATING_SLACK);
00203         NS_ASSERTION(mRecycleTimer, "nsRecyclingAllocator: Creating timer failed.\n");
00204     }
00205  
00206 #ifdef DEBUG
00207     mNAllocated++;
00208 #endif
00209   
00210     // Store size and return data portion
00211     ptr->bytes = bytes;
00212     return DATA(ptr);
00213 }
00214 
00215 void
00216 nsRecyclingAllocator::Free(void *ptr)
00217 {
00218     // Mark that we are using the allocator. This will prevent any
00219     // timer based release of unused memory.
00220     Touch();
00221 
00222     Block* block = DATA_TO_BLOCK(ptr);
00223 
00224     if (!AddToFreeList(block))
00225     {
00226         // We are holding more than max. Failover to free
00227 #ifdef DEBUG_dp
00228         char buf[1024];
00229         // Warn if we are failing over to malloc/free and not storing it
00230         // This says we have a misdesigned memory pool. The intent was
00231         // once the pool was full, we would never fail over to calloc.
00232         PR_snprintf(buf, sizeof(buf), "nsRecyclingAllocator(%s) FAILOVER 0x%p (%d) - %d allocations, %d max\n",
00233                     mId, (char *)ptr, block->bytes, mNAllocated, mMaxBlocks);
00234         NS_WARNING(buf);
00235         mNAllocated--;
00236 #endif
00237         free(block);
00238     }
00239 }
00240 
00241 /* FreeUnusedBuckets
00242  *
00243  * Frees any bucket memory that isn't in use
00244  */
00245 
00246 void
00247 nsRecyclingAllocator::FreeUnusedBuckets()
00248 {
00249 #ifdef DEBUG_dp
00250     printf("DEBUG: nsRecyclingAllocator(%s) FreeUnusedBuckets: ", mId);
00251 #endif
00252     nsAutoLock lock(mLock);
00253 
00254     // We will run through the freelist and free all blocks
00255     BlockStoreNode* node = mFreeList;
00256     while (node)
00257     {
00258         // Free the allocated block
00259         free(node->block);
00260 
00261 #ifdef DEBUG_dp
00262         printf("%d ", node->bytes);
00263 #endif
00264         // Clear Node
00265         node->block = nsnull;
00266         node->bytes = 0;
00267         node = node->next;
00268     }
00269 
00270     // remake the lists
00271     mNotUsedList = mBlocks;
00272     for (PRUint32 i=0; i < mMaxBlocks-1; i++)
00273         mBlocks[i].next = &(mBlocks[i+1]);
00274     mBlocks[mMaxBlocks-1].next = nsnull;
00275     mFreeList = nsnull;
00276 
00277 #ifdef DEBUG        
00278     mNAllocated = 0;
00279 #endif
00280 #ifdef DEBUG_dp
00281     printf("\n");
00282 #endif
00283 }
00284 
00285 nsRecyclingAllocator::Block*
00286 nsRecyclingAllocator::FindFreeBlock(PRSize bytes)
00287 {
00288     // We dont enter lock for this check. This is intentional.
00289     // Here is my logic: we are checking if (!mFreeList). Doing this check
00290     // without locking can lead to unpredictable results. YES. But the effect
00291     // of the unpredictedness are ok. here is why:
00292     //
00293     // a) if the check returned NULL when there is stuff in freelist
00294     //    We would just end up reallocating.
00295     //
00296     // b) if the check returned nonNULL when our freelist is empty
00297     //    This is the more likely and dangerous case. The code for
00298     //    FindFreeBlock() will enter lock, while (null) and return null.
00299     //
00300     // The reason why I chose to not enter lock for this check was that when
00301     // the allocator is full, we dont want to impose any more overhead than
00302     // we already are for failing over to malloc/free.
00303 
00304     if (!mFreeList)
00305         return NULL;
00306 
00307     Block *block = nsnull;
00308 
00309     nsAutoLock lock(mLock);
00310     BlockStoreNode* freeNode = mFreeList;
00311     BlockStoreNode** prevp = &mFreeList;
00312 
00313     while (freeNode)
00314     {
00315         if (freeNode->bytes >= bytes)
00316         {
00317             // Found the best fit free block
00318             block = freeNode->block;
00319 
00320             // Clear the free node
00321             freeNode->block = nsnull;
00322             freeNode->bytes = 0;
00323 
00324             // Remove free node from free list
00325             *prevp = freeNode->next;
00326 
00327             // Add removed BlockStoreNode to not used list
00328             freeNode->next = mNotUsedList;
00329             mNotUsedList = freeNode;
00330 
00331             break;
00332         }
00333 
00334         prevp = &(freeNode->next);
00335         freeNode = freeNode->next;
00336     }
00337     return block;
00338 }
00339 
00340 PRInt32
00341 nsRecyclingAllocator::AddToFreeList(Block* block)
00342 {
00343     nsAutoLock lock(mLock);
00344 
00345     if (!mNotUsedList)
00346         return PR_FALSE;
00347 
00348     // Pick a node from the not used list
00349     BlockStoreNode *node = mNotUsedList;
00350     mNotUsedList = mNotUsedList->next;
00351 
00352     // Initialize the node
00353     node->bytes = block->bytes;
00354     node->block = block;
00355 
00356     // Find the right spot in the sorted list.
00357     BlockStoreNode* freeNode = mFreeList;
00358     BlockStoreNode** prevp = &mFreeList;
00359     while (freeNode)
00360     {
00361         if (freeNode->bytes >= block->bytes)
00362             break;
00363         prevp = &(freeNode->next);
00364         freeNode = freeNode->next;
00365     }
00366 
00367     // Needs to be inserted between *prevp and freeNode
00368     *prevp = node;
00369     node->next = freeNode;
00370 
00371     return PR_TRUE;
00372 }
00373 
00374 
00375 // ----------------------------------------------------------------------
00376 // Wrapping the recyling allocator with nsIMemory
00377 // ----------------------------------------------------------------------
00378 
00379 // nsIMemory methods
00380 NS_IMPL_THREADSAFE_ISUPPORTS2(nsRecyclingAllocatorImpl, nsIMemory, nsIRecyclingAllocator)
00381 
00382 NS_IMETHODIMP_(void *)
00383 nsRecyclingAllocatorImpl::Alloc(PRSize size)
00384 {
00385     return nsRecyclingAllocatorImpl::Malloc(size, PR_FALSE);
00386 }
00387 
00388 NS_IMETHODIMP_(void *)
00389 nsRecyclingAllocatorImpl::Realloc(void *ptr, PRSize size)
00390 {
00391     // XXX Not yet implemented
00392     return NULL;
00393 }
00394 
00395 NS_IMETHODIMP_(void)
00396 nsRecyclingAllocatorImpl::Free(void *ptr)
00397 {
00398     nsRecyclingAllocator::Free(ptr);
00399 }
00400 
00401 NS_IMETHODIMP
00402 nsRecyclingAllocatorImpl::Init(size_t nbuckets, size_t recycleAfter, const char *id)
00403 {
00404     return nsRecyclingAllocator::Init((PRUint32) nbuckets, (PRUint32) recycleAfter, id);
00405 }
00406 
00407 NS_IMETHODIMP
00408 nsRecyclingAllocatorImpl::HeapMinimize(PRBool immediate)
00409 {
00410     // XXX Not yet implemented
00411     return NS_ERROR_NOT_IMPLEMENTED;
00412 }
00413 
00414 NS_IMETHODIMP
00415 nsRecyclingAllocatorImpl::IsLowMemory(PRBool *lowmemoryb_ptr)
00416 {
00417     // XXX Not yet implemented
00418     return NS_ERROR_NOT_IMPLEMENTED;
00419 }
00420