Back to index

lightning-sunbird  0.9+nobinonly
plarena.c
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
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 the Netscape Portable Runtime (NSPR).
00016  * 
00017  * The Initial Developer of the Original Code is Netscape
00018  * Communications Corporation.  Portions created by Netscape are 
00019  * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
00020  * Rights Reserved.
00021  * 
00022  * Contributor(s):
00023  * 
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK *****
00037  */
00038 
00039 /*
00040  * Lifetime-based fast allocation, inspired by much prior art, including
00041  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
00042  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
00043  */
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #include "plarena.h"
00047 #include "prmem.h"
00048 #include "prbit.h"
00049 #include "prlog.h"
00050 #include "prlock.h"
00051 #include "prinit.h"
00052 
00053 static PLArena *arena_freelist;
00054 
00055 #ifdef PL_ARENAMETER
00056 static PLArenaStats *arena_stats_list;
00057 
00058 #define COUNT(pool,what)  (pool)->stats.what++
00059 #else
00060 #define COUNT(pool,what)  /* nothing */
00061 #endif
00062 
00063 #define PL_ARENA_DEFAULT_ALIGN  sizeof(double)
00064 
00065 static PRLock    *arenaLock;
00066 static PRCallOnceType once;
00067 
00068 /*
00069 ** InitializeArenas() -- Initialize arena operations.
00070 **
00071 ** InitializeArenas() is called exactly once and only once from 
00072 ** LockArena(). This function creates the arena protection 
00073 ** lock: arenaLock.
00074 **
00075 ** Note: If the arenaLock cannot be created, InitializeArenas()
00076 ** fails quietly, returning only PR_FAILURE. This percolates up
00077 ** to the application using the Arena API. He gets no arena
00078 ** from PL_ArenaAllocate(). It's up to him to fail gracefully
00079 ** or recover.
00080 **
00081 */
00082 static PRStatus InitializeArenas( void )
00083 {
00084     PR_ASSERT( arenaLock == NULL );
00085     arenaLock = PR_NewLock();
00086     if ( arenaLock == NULL )
00087         return PR_FAILURE;
00088     else
00089         return PR_SUCCESS;
00090 } /* end ArenaInitialize() */
00091 
00092 static PRStatus LockArena( void )
00093 {
00094     PRStatus rc = PR_CallOnce( &once, InitializeArenas );
00095 
00096     if ( PR_FAILURE != rc )
00097         PR_Lock( arenaLock );
00098     return(rc);
00099 } /* end LockArena() */
00100 
00101 static void UnlockArena( void )
00102 {
00103     PR_Unlock( arenaLock );
00104     return;
00105 } /* end UnlockArena() */
00106 
00107 PR_IMPLEMENT(void) PL_InitArenaPool(
00108     PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
00109 {
00110 #if defined(XP_MAC)
00111 #pragma unused (name)
00112 #endif
00113 
00114     if (align == 0)
00115         align = PL_ARENA_DEFAULT_ALIGN;
00116     pool->mask = PR_BITMASK(PR_CeilingLog2(align));
00117     pool->first.next = NULL;
00118     pool->first.base = pool->first.avail = pool->first.limit =
00119         (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
00120     pool->current = &pool->first;
00121     pool->arenasize = size;                                  
00122 #ifdef PL_ARENAMETER
00123     memset(&pool->stats, 0, sizeof pool->stats);
00124     pool->stats.name = strdup(name);
00125     pool->stats.next = arena_stats_list;
00126     arena_stats_list = &pool->stats;
00127 #endif
00128 }
00129 
00130 
00131 /*
00132 ** PL_ArenaAllocate() -- allocate space from an arena pool
00133 ** 
00134 ** Description: PL_ArenaAllocate() allocates space from an arena
00135 ** pool. 
00136 **
00137 ** First, try to satisfy the request from arenas starting at
00138 ** pool->current.
00139 **
00140 ** If there is not enough space in the arena pool->current, try
00141 ** to claim an arena, on a first fit basis, from the global
00142 ** freelist (arena_freelist).
00143 ** 
00144 ** If no arena in arena_freelist is suitable, then try to
00145 ** allocate a new arena from the heap.
00146 **
00147 ** Returns: pointer to allocated space or NULL
00148 ** 
00149 ** Notes: The original implementation had some difficult to
00150 ** solve bugs; the code was difficult to read. Sometimes it's
00151 ** just easier to rewrite it. I did that. larryh.
00152 **
00153 ** See also: bugzilla: 45343.
00154 **
00155 */
00156 
00157 PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
00158 {
00159     PLArena *a;   
00160     char *rp;     /* returned pointer */
00161 
00162     PR_ASSERT((nb & pool->mask) == 0);
00163     
00164     nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
00165 
00166     /* attempt to allocate from arenas at pool->current */
00167     {
00168         a = pool->current;
00169         do {
00170             if ( a->avail +nb <= a->limit )  {
00171                 pool->current = a;
00172                 rp = (char *)a->avail;
00173                 a->avail += nb;
00174                 return rp;
00175             }
00176         } while( NULL != (a = a->next) );
00177     }
00178 
00179     /* attempt to allocate from arena_freelist */
00180     {
00181         PLArena *p; /* previous pointer, for unlinking from freelist */
00182 
00183         /* lock the arena_freelist. Make access to the freelist MT-Safe */
00184         if ( PR_FAILURE == LockArena())
00185             return(0);
00186 
00187         for ( a = arena_freelist, p = NULL; a != NULL ; p = a, a = a->next ) {
00188             if ( a->base +nb <= a->limit )  {
00189                 if ( p == NULL )
00190                     arena_freelist = a->next;
00191                 else
00192                     p->next = a->next;
00193                 UnlockArena();
00194                 a->avail = a->base;
00195                 rp = (char *)a->avail;
00196                 a->avail += nb;
00197                 /* the newly allocated arena is linked after pool->current 
00198                 *  and becomes pool->current */
00199                 a->next = pool->current->next;
00200                 pool->current->next = a;
00201                 pool->current = a;
00202                 if ( NULL == pool->first.next )
00203                     pool->first.next = a;
00204                 return(rp);
00205             }
00206         }
00207         UnlockArena();
00208     }
00209 
00210     /* attempt to allocate from the heap */ 
00211     {  
00212         PRUint32 sz = PR_MAX(pool->arenasize, nb);
00213         sz += sizeof *a + pool->mask;  /* header and alignment slop */
00214         a = (PLArena*)PR_MALLOC(sz);
00215         if ( NULL != a )  {
00216             a->limit = (PRUword)a + sz;
00217             a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
00218             rp = (char *)a->avail;
00219             a->avail += nb;
00220             /* the newly allocated arena is linked after pool->current 
00221             *  and becomes pool->current */
00222             a->next = pool->current->next;
00223             pool->current->next = a;
00224             pool->current = a;
00225             if ( NULL == pool->first.next )
00226                 pool->first.next = a;
00227             PL_COUNT_ARENA(pool,++);
00228             COUNT(pool, nmallocs);
00229             return(rp);
00230         }
00231     }
00232 
00233     /* we got to here, and there's no memory to allocate */
00234     return(NULL);
00235 } /* --- end PL_ArenaAllocate() --- */
00236 
00237 PR_IMPLEMENT(void *) PL_ArenaGrow(
00238     PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr)
00239 {
00240     void *newp;
00241 
00242     PL_ARENA_ALLOCATE(newp, pool, size + incr);
00243     if (newp)
00244         memcpy(newp, p, size);
00245     return newp;
00246 }
00247 
00248 /*
00249  * Free tail arenas linked after head, which may not be the true list head.
00250  * Reset pool->current to point to head in case it pointed at a tail arena.
00251  */
00252 static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
00253 {
00254     PLArena **ap, *a;
00255 
00256     ap = &head->next;
00257     a = *ap;
00258     if (!a)
00259         return;
00260 
00261 #ifdef DEBUG
00262     do {
00263         PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
00264         a->avail = a->base;
00265         PL_CLEAR_UNUSED(a);
00266     } while ((a = a->next) != 0);
00267     a = *ap;
00268 #endif
00269 
00270     if (reallyFree) {
00271         do {
00272             *ap = a->next;
00273             PL_CLEAR_ARENA(a);
00274             PL_COUNT_ARENA(pool,--);
00275             PR_DELETE(a);
00276         } while ((a = *ap) != 0);
00277     } else {
00278         /* Insert the whole arena chain at the front of the freelist. */
00279         do {
00280             ap = &(*ap)->next;
00281         } while (*ap);
00282         LockArena();
00283         *ap = arena_freelist;
00284         arena_freelist = a;
00285         head->next = 0;
00286         UnlockArena();
00287     }
00288 
00289     pool->current = head;
00290 }
00291 
00292 PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
00293 {
00294     PLArena *a;
00295 
00296     for (a = pool->first.next; a; a = a->next) {
00297         if (PR_UPTRDIFF(mark, a->base) < PR_UPTRDIFF(a->avail, a->base)) {
00298             a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
00299             FreeArenaList(pool, a, PR_FALSE);
00300             return;
00301         }
00302     }
00303 }
00304 
00305 PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
00306 {
00307     FreeArenaList(pool, &pool->first, PR_FALSE);
00308     COUNT(pool, ndeallocs);
00309 }
00310 
00311 PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
00312 {
00313     FreeArenaList(pool, &pool->first, PR_TRUE);
00314 #ifdef PL_ARENAMETER
00315     {
00316         PLArenaStats *stats, **statsp;
00317 
00318         if (pool->stats.name)
00319             PR_DELETE(pool->stats.name);
00320         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
00321              statsp = &stats->next) {
00322             if (stats == &pool->stats) {
00323                 *statsp = stats->next;
00324                 return;
00325             }
00326         }
00327     }
00328 #endif
00329 }
00330 
00331 PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
00332 {
00333 #if XP_MAC
00334 #pragma unused (ap)
00335 #if 0
00336     PRArena *curr = &(ap->first);
00337     while (curr) {
00338         reallocSmaller(curr, curr->avail - (uprword_t)curr);
00339         curr->limit = curr->avail;
00340         curr = curr->next;
00341     }
00342 #endif
00343 #endif
00344 }
00345 
00346 PR_IMPLEMENT(void) PL_ArenaFinish(void)
00347 {
00348     PLArena *a, *next;
00349 
00350     for (a = arena_freelist; a; a = next) {
00351         next = a->next;
00352         PR_DELETE(a);
00353     }
00354     arena_freelist = NULL;
00355 
00356     if (arenaLock) {
00357         PR_DestroyLock(arenaLock);
00358         arenaLock = NULL;
00359     }
00360 }
00361 
00362 #ifdef PL_ARENAMETER
00363 PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
00364 {
00365     pool->stats.nallocs++;
00366     pool->stats.nbytes += nb;
00367     if (nb > pool->stats.maxalloc)
00368         pool->stats.maxalloc = nb;
00369     pool->stats.variance += nb * nb;
00370 }
00371 
00372 PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
00373     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
00374 {
00375     pool->stats.ninplace++;
00376 }
00377 
00378 PR_IMPLEMENT(void) PL_ArenaCountGrowth(
00379     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
00380 {
00381     pool->stats.ngrows++;
00382     pool->stats.nbytes += incr;
00383     pool->stats.variance -= size * size;
00384     size += incr;
00385     if (size > pool->stats.maxalloc)
00386         pool->stats.maxalloc = size;
00387     pool->stats.variance += size * size;
00388 }
00389 
00390 PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
00391 {
00392     pool->stats.nreleases++;
00393 }
00394 
00395 PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
00396 {
00397     pool->stats.nfastrels++;
00398 }
00399 
00400 #include <math.h>
00401 #include <stdio.h>
00402 
00403 PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
00404 {
00405     PLArenaStats *stats;
00406     double mean, variance;
00407 
00408     for (stats = arena_stats_list; stats; stats = stats->next) {
00409         if (stats->nallocs != 0) {
00410             mean = (double)stats->nbytes / stats->nallocs;
00411             variance = fabs(stats->variance / stats->nallocs - mean * mean);
00412         } else {
00413             mean = variance = 0;
00414         }
00415 
00416         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
00417         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
00418         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
00419         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
00420         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
00421         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
00422         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
00423         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
00424         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
00425         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
00426         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
00427         fprintf(fp, "          mean allocation size: %g\n", mean);
00428         fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
00429         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
00430     }
00431 }
00432 #endif /* PL_ARENAMETER */