← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/virtualbox-ose/gutsy

« back to all changes in this revision

Viewing changes to src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Steve Kowalik
  • Date: 2007-09-08 16:44:58 UTC
  • Revision ID: james.westby@ubuntu.com-20070908164458-wao29470vqtr8ksy
Tags: upstream-1.5.0-dfsg2
Import upstream version 1.5.0-dfsg2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libs/xpcom18a4/xpcom/ds/nsRecyclingAllocator.cpp
 
1
/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
 
2
/* ***** BEGIN LICENSE BLOCK *****
 
3
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 
4
 *
 
5
 * The contents of this file are subject to the Mozilla Public License Version
 
6
 * 1.1 (the "License"); you may not use this file except in compliance with
 
7
 * the License. You may obtain a copy of the License at
 
8
 * http://www.mozilla.org/MPL/
 
9
 *
 
10
 * Software distributed under the License is distributed on an "AS IS" basis,
 
11
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 
12
 * for the specific language governing rights and limitations under the
 
13
 * License.
 
14
 *
 
15
 * The Original Code is mozilla.org code.
 
16
 *
 
17
 * The Initial Developer of the Original Code is
 
18
 * Netscape Communications Corporation.
 
19
 * Portions created by the Initial Developer are Copyright (C) 2001, 2002
 
20
 * the Initial Developer. All Rights Reserved.
 
21
 *
 
22
 * Contributor(s):
 
23
 *      Suresh Duddi <dp@netscape.com>
 
24
 *
 
25
 * Alternatively, the contents of this file may be used under the terms of
 
26
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 
27
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 
28
 * in which case the provisions of the GPL or the LGPL are applicable instead
 
29
 * of those above. If you wish to allow use of your version of this file only
 
30
 * under the terms of either the GPL or the LGPL, and not to allow others to
 
31
 * use your version of this file under the terms of the MPL, indicate your
 
32
 * decision by deleting the provisions above and replace them with the notice
 
33
 * and other provisions required by the GPL or the LGPL. If you do not delete
 
34
 * the provisions above, a recipient may use your version of this file under
 
35
 * the terms of any one of the MPL, the GPL or the LGPL.
 
36
 *
 
37
 * ***** END LICENSE BLOCK ***** */
 
38
 
 
39
/*
 
40
 * nsRecyclingAllocator
 
41
 */
 
42
 
 
43
#include <stdlib.h>
 
44
#include <string.h>
 
45
#include <stdio.h>
 
46
#include "nsRecyclingAllocator.h"
 
47
#include "nsIMemory.h"
 
48
#include "nsAutoLock.h"
 
49
#include "prprf.h"
 
50
#include "nsITimer.h"
 
51
 
 
52
#define NS_SEC_TO_MS(s) ((s) * 1000)
 
53
 
 
54
void
 
55
nsRecyclingAllocator::nsRecycleTimerCallback(nsITimer *aTimer, void *aClosure)
 
56
{
 
57
    nsRecyclingAllocator *obj = (nsRecyclingAllocator *) aClosure;
 
58
    if (!obj->mTouched)
 
59
    {
 
60
        if (obj->mFreeList)
 
61
            obj->FreeUnusedBuckets();
 
62
 
 
63
        // If we are holding no more memory, there is no need for the timer.
 
64
        // We will revive the timer on the next allocation.
 
65
        // XXX Unfortunately there is no way to Cancel and restart the same timer.
 
66
        // XXX So we pretty much kill it and create a new one later.
 
67
        if (!obj->mFreeList && obj->mRecycleTimer)
 
68
        {
 
69
            obj->mRecycleTimer->Cancel();
 
70
            NS_RELEASE(obj->mRecycleTimer);
 
71
        }
 
72
    }
 
73
    else
 
74
    {
 
75
        // Clear touched so the next time the timer fires we can test whether
 
76
        // the allocator was used or not.
 
77
        obj->Untouch();
 
78
    }
 
79
}
 
80
 
 
81
 
 
82
nsRecyclingAllocator::nsRecyclingAllocator(PRUint32 nbucket, PRUint32 recycleAfter, const char *id) :
 
83
    mMaxBlocks(nbucket), mBlocks(nsnull), mFreeList(nsnull), mNotUsedList(nsnull),
 
84
    mRecycleTimer(nsnull), mRecycleAfter(recycleAfter), mTouched(0), mId(id)
 
85
#ifdef DEBUG
 
86
     ,mNAllocated(0)
 
87
#endif
 
88
{
 
89
    NS_ASSERTION(mMaxBlocks <= NS_MAX_BLOCKS, "Too many blocks. This will affect the allocator's performance.");
 
90
 
 
91
    mLock = PR_NewLock();
 
92
    NS_ASSERTION(mLock, "Recycling allocator cannot get lock");
 
93
 
 
94
    Init(nbucket, recycleAfter, id);
 
95
}
 
96
 
 
97
nsresult
 
98
nsRecyclingAllocator::Init(PRUint32 nbucket, PRUint32 recycleAfter, const char *id)
 
99
{
 
100
    nsAutoLock lock(mLock);
 
101
 
 
102
    // Free all memory held, if any
 
103
    while(mFreeList)
 
104
    {
 
105
        free(mFreeList->block);
 
106
        mFreeList = mFreeList->next;
 
107
    }
 
108
    mFreeList = nsnull;
 
109
    
 
110
    if (mBlocks)
 
111
        delete [] mBlocks;
 
112
 
 
113
    // Reinitialize everything
 
114
    mMaxBlocks = nbucket;
 
115
    if (nbucket)
 
116
    {
 
117
        // Create memory for our bookkeeping
 
118
        mBlocks = new BlockStoreNode[mMaxBlocks];
 
119
        if (!mBlocks)
 
120
            return NS_ERROR_OUT_OF_MEMORY;
 
121
        // Link them together
 
122
        mNotUsedList = mBlocks;
 
123
        for (PRUint32 i=0; i < mMaxBlocks-1; i++)
 
124
            mBlocks[i].next = &(mBlocks[i+1]);
 
125
    }
 
126
 
 
127
    mRecycleAfter = recycleAfter;
 
128
    mId = id;
 
129
 
 
130
    return NS_OK;
 
131
}
 
132
 
 
133
nsRecyclingAllocator::~nsRecyclingAllocator()
 
134
{
 
135
    // Cancel and destroy recycle timer
 
136
    if (mRecycleTimer)
 
137
    {
 
138
        mRecycleTimer->Cancel();
 
139
        NS_RELEASE(mRecycleTimer);
 
140
    }
 
141
 
 
142
    // Free all memory held, if any
 
143
    while(mFreeList)
 
144
    {
 
145
        free(mFreeList->block);
 
146
        mFreeList = mFreeList->next;
 
147
    }
 
148
    mFreeList = nsnull;
 
149
    
 
150
    if (mBlocks)
 
151
        delete [] mBlocks;
 
152
 
 
153
    if (mLock)
 
154
    {
 
155
        PR_DestroyLock(mLock);
 
156
        mLock = nsnull;
 
157
    }
 
158
}
 
159
 
 
160
// Allocation and free routines
 
161
void*
 
162
nsRecyclingAllocator::Malloc(PRSize bytes, PRBool zeroit)
 
163
{
 
164
    // Mark that we are using. This will prevent any
 
165
    // timer based release of unused memory.
 
166
    Touch();
 
167
  
 
168
    Block* freeBlock = FindFreeBlock(bytes);
 
169
    if (freeBlock)
 
170
    {
 
171
        void *data = DATA(freeBlock);
 
172
 
 
173
        if (zeroit)
 
174
            memset(data, 0, bytes);
 
175
        return data;
 
176
    }
 
177
     
 
178
    // We need to do an allocation
 
179
    // Add 4 bytes to what we allocate to hold the bucket index
 
180
    PRSize allocBytes = bytes + NS_ALLOCATOR_OVERHEAD_BYTES;
 
181
  
 
182
    // We dont have that memory already. Allocate.
 
183
    Block *ptr = (Block *) (zeroit ? calloc(1, allocBytes) : malloc(allocBytes));
 
184
    
 
185
    // Deal with no memory situation
 
186
    if (!ptr)
 
187
        return ptr;
 
188
  
 
189
    // This is the first allocation we are holding.
 
190
    // Setup timer for releasing memory
 
191
    // If this fails, then we wont have a timer to release unused
 
192
    // memory. We can live with that. Also, the next allocation
 
193
    // will try again to set the timer.
 
194
    if (mRecycleAfter && !mRecycleTimer)
 
195
    {
 
196
        // known only to stuff in xpcom.  
 
197
        extern nsresult NS_NewTimer(nsITimer* *aResult, nsTimerCallbackFunc aCallback, void *aClosure,
 
198
                                    PRUint32 aDelay, PRUint32 aType);
 
199
 
 
200
        (void) NS_NewTimer(&mRecycleTimer, nsRecycleTimerCallback, this, 
 
201
                           NS_SEC_TO_MS(mRecycleAfter),
 
202
                           nsITimer::TYPE_REPEATING_SLACK);
 
203
        NS_ASSERTION(mRecycleTimer, "nsRecyclingAllocator: Creating timer failed.\n");
 
204
    }
 
205
 
 
206
#ifdef DEBUG
 
207
    mNAllocated++;
 
208
#endif
 
209
  
 
210
    // Store size and return data portion
 
211
    ptr->bytes = bytes;
 
212
    return DATA(ptr);
 
213
}
 
214
 
 
215
void
 
216
nsRecyclingAllocator::Free(void *ptr)
 
217
{
 
218
    // Mark that we are using the allocator. This will prevent any
 
219
    // timer based release of unused memory.
 
220
    Touch();
 
221
 
 
222
    Block* block = DATA_TO_BLOCK(ptr);
 
223
 
 
224
    if (!AddToFreeList(block))
 
225
    {
 
226
        // We are holding more than max. Failover to free
 
227
#ifdef DEBUG_dp
 
228
        char buf[1024];
 
229
        // Warn if we are failing over to malloc/free and not storing it
 
230
        // This says we have a misdesigned memory pool. The intent was
 
231
        // once the pool was full, we would never fail over to calloc.
 
232
        PR_snprintf(buf, sizeof(buf), "nsRecyclingAllocator(%s) FAILOVER 0x%p (%d) - %d allocations, %d max\n",
 
233
                    mId, (char *)ptr, block->bytes, mNAllocated, mMaxBlocks);
 
234
        NS_WARNING(buf);
 
235
        mNAllocated--;
 
236
#endif
 
237
        free(block);
 
238
    }
 
239
}
 
240
 
 
241
/* FreeUnusedBuckets
 
242
 *
 
243
 * Frees any bucket memory that isn't in use
 
244
 */
 
245
 
 
246
void
 
247
nsRecyclingAllocator::FreeUnusedBuckets()
 
248
{
 
249
#ifdef DEBUG_dp
 
250
    printf("DEBUG: nsRecyclingAllocator(%s) FreeUnusedBuckets: ", mId);
 
251
#endif
 
252
    nsAutoLock lock(mLock);
 
253
 
 
254
    // We will run through the freelist and free all blocks
 
255
    BlockStoreNode* node = mFreeList;
 
256
    while (node)
 
257
    {
 
258
        // Free the allocated block
 
259
        free(node->block);
 
260
 
 
261
#ifdef DEBUG_dp
 
262
        printf("%d ", node->bytes);
 
263
#endif
 
264
        // Clear Node
 
265
        node->block = nsnull;
 
266
        node->bytes = 0;
 
267
        node = node->next;
 
268
    }
 
269
 
 
270
    // remake the lists
 
271
    mNotUsedList = mBlocks;
 
272
    for (PRUint32 i=0; i < mMaxBlocks-1; i++)
 
273
        mBlocks[i].next = &(mBlocks[i+1]);
 
274
    mBlocks[mMaxBlocks-1].next = nsnull;
 
275
    mFreeList = nsnull;
 
276
 
 
277
#ifdef DEBUG        
 
278
    mNAllocated = 0;
 
279
#endif
 
280
#ifdef DEBUG_dp
 
281
    printf("\n");
 
282
#endif
 
283
}
 
284
 
 
285
nsRecyclingAllocator::Block*
 
286
nsRecyclingAllocator::FindFreeBlock(PRSize bytes)
 
287
{
 
288
    // We dont enter lock for this check. This is intentional.
 
289
    // Here is my logic: we are checking if (!mFreeList). Doing this check
 
290
    // without locking can lead to unpredictable results. YES. But the effect
 
291
    // of the unpredictedness are ok. here is why:
 
292
    //
 
293
    // a) if the check returned NULL when there is stuff in freelist
 
294
    //    We would just end up reallocating.
 
295
    //
 
296
    // b) if the check returned nonNULL when our freelist is empty
 
297
    //    This is the more likely and dangerous case. The code for
 
298
    //    FindFreeBlock() will enter lock, while (null) and return null.
 
299
    //
 
300
    // The reason why I chose to not enter lock for this check was that when
 
301
    // the allocator is full, we dont want to impose any more overhead than
 
302
    // we already are for failing over to malloc/free.
 
303
 
 
304
    if (!mFreeList)
 
305
        return NULL;
 
306
 
 
307
    Block *block = nsnull;
 
308
 
 
309
    nsAutoLock lock(mLock);
 
310
    BlockStoreNode* freeNode = mFreeList;
 
311
    BlockStoreNode** prevp = &mFreeList;
 
312
 
 
313
    while (freeNode)
 
314
    {
 
315
        if (freeNode->bytes >= bytes)
 
316
        {
 
317
            // Found the best fit free block
 
318
            block = freeNode->block;
 
319
 
 
320
            // Clear the free node
 
321
            freeNode->block = nsnull;
 
322
            freeNode->bytes = 0;
 
323
 
 
324
            // Remove free node from free list
 
325
            *prevp = freeNode->next;
 
326
 
 
327
            // Add removed BlockStoreNode to not used list
 
328
            freeNode->next = mNotUsedList;
 
329
            mNotUsedList = freeNode;
 
330
 
 
331
            break;
 
332
        }
 
333
 
 
334
        prevp = &(freeNode->next);
 
335
        freeNode = freeNode->next;
 
336
    }
 
337
    return block;
 
338
}
 
339
 
 
340
PRInt32
 
341
nsRecyclingAllocator::AddToFreeList(Block* block)
 
342
{
 
343
    nsAutoLock lock(mLock);
 
344
 
 
345
    if (!mNotUsedList)
 
346
        return PR_FALSE;
 
347
 
 
348
    // Pick a node from the not used list
 
349
    BlockStoreNode *node = mNotUsedList;
 
350
    mNotUsedList = mNotUsedList->next;
 
351
 
 
352
    // Initialize the node
 
353
    node->bytes = block->bytes;
 
354
    node->block = block;
 
355
 
 
356
    // Find the right spot in the sorted list.
 
357
    BlockStoreNode* freeNode = mFreeList;
 
358
    BlockStoreNode** prevp = &mFreeList;
 
359
    while (freeNode)
 
360
    {
 
361
        if (freeNode->bytes >= block->bytes)
 
362
            break;
 
363
        prevp = &(freeNode->next);
 
364
        freeNode = freeNode->next;
 
365
    }
 
366
 
 
367
    // Needs to be inserted between *prevp and freeNode
 
368
    *prevp = node;
 
369
    node->next = freeNode;
 
370
 
 
371
    return PR_TRUE;
 
372
}
 
373
 
 
374
 
 
375
// ----------------------------------------------------------------------
 
376
// Wrapping the recyling allocator with nsIMemory
 
377
// ----------------------------------------------------------------------
 
378
 
 
379
// nsIMemory methods
 
380
NS_IMPL_THREADSAFE_ISUPPORTS2(nsRecyclingAllocatorImpl, nsIMemory, nsIRecyclingAllocator)
 
381
 
 
382
NS_IMETHODIMP_(void *)
 
383
nsRecyclingAllocatorImpl::Alloc(PRSize size)
 
384
{
 
385
    return nsRecyclingAllocatorImpl::Malloc(size, PR_FALSE);
 
386
}
 
387
 
 
388
NS_IMETHODIMP_(void *)
 
389
nsRecyclingAllocatorImpl::Realloc(void *ptr, PRSize size)
 
390
{
 
391
    // XXX Not yet implemented
 
392
    return NULL;
 
393
}
 
394
 
 
395
NS_IMETHODIMP_(void)
 
396
nsRecyclingAllocatorImpl::Free(void *ptr)
 
397
{
 
398
    nsRecyclingAllocator::Free(ptr);
 
399
}
 
400
 
 
401
NS_IMETHODIMP
 
402
nsRecyclingAllocatorImpl::Init(size_t nbuckets, size_t recycleAfter, const char *id)
 
403
{
 
404
    return nsRecyclingAllocator::Init((PRUint32) nbuckets, (PRUint32) recycleAfter, id);
 
405
}
 
406
 
 
407
NS_IMETHODIMP
 
408
nsRecyclingAllocatorImpl::HeapMinimize(PRBool immediate)
 
409
{
 
410
    // XXX Not yet implemented
 
411
    return NS_ERROR_NOT_IMPLEMENTED;
 
412
}
 
413
 
 
414
NS_IMETHODIMP
 
415
nsRecyclingAllocatorImpl::IsLowMemory(PRBool *lowmemoryb_ptr)
 
416
{
 
417
    // XXX Not yet implemented
 
418
    return NS_ERROR_NOT_IMPLEMENTED;
 
419
}
 
420