michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Lifetime-based fast allocation, inspired by much prior art, including
michael@0:  * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
michael@0:  * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
michael@0:  */
michael@0: #include <stdlib.h>
michael@0: #include <string.h>
michael@0: #include "plarena.h"
michael@0: #include "prmem.h"
michael@0: #include "prbit.h"
michael@0: #include "prlog.h"
michael@0: #include "prlock.h"
michael@0: #include "prinit.h"
michael@0: 
michael@0: static PLArena *arena_freelist;
michael@0: 
michael@0: #ifdef PL_ARENAMETER
michael@0: static PLArenaStats *arena_stats_list;
michael@0: 
michael@0: #define COUNT(pool,what)  (pool)->stats.what++
michael@0: #else
michael@0: #define COUNT(pool,what)  /* nothing */
michael@0: #endif
michael@0: 
michael@0: #define PL_ARENA_DEFAULT_ALIGN  sizeof(double)
michael@0: 
michael@0: static PRLock    *arenaLock;
michael@0: static PRCallOnceType once;
michael@0: static const PRCallOnceType pristineCallOnce;
michael@0: 
michael@0: /*
michael@0: ** InitializeArenas() -- Initialize arena operations.
michael@0: **
michael@0: ** InitializeArenas() is called exactly once and only once from 
michael@0: ** LockArena(). This function creates the arena protection 
michael@0: ** lock: arenaLock.
michael@0: **
michael@0: ** Note: If the arenaLock cannot be created, InitializeArenas()
michael@0: ** fails quietly, returning only PR_FAILURE. This percolates up
michael@0: ** to the application using the Arena API. He gets no arena
michael@0: ** from PL_ArenaAllocate(). It's up to him to fail gracefully
michael@0: ** or recover.
michael@0: **
michael@0: */
michael@0: static PRStatus InitializeArenas( void )
michael@0: {
michael@0:     PR_ASSERT( arenaLock == NULL );
michael@0:     arenaLock = PR_NewLock();
michael@0:     if ( arenaLock == NULL )
michael@0:         return PR_FAILURE;
michael@0:     else
michael@0:         return PR_SUCCESS;
michael@0: } /* end ArenaInitialize() */
michael@0: 
michael@0: static PRStatus LockArena( void )
michael@0: {
michael@0:     PRStatus rc = PR_CallOnce( &once, InitializeArenas );
michael@0: 
michael@0:     if ( PR_FAILURE != rc )
michael@0:         PR_Lock( arenaLock );
michael@0:     return(rc);
michael@0: } /* end LockArena() */
michael@0: 
michael@0: static void UnlockArena( void )
michael@0: {
michael@0:     PR_Unlock( arenaLock );
michael@0:     return;
michael@0: } /* end UnlockArena() */
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_InitArenaPool(
michael@0:     PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
michael@0: {
michael@0:     /*
michael@0:      * Look-up table of PR_BITMASK(PR_CeilingLog2(align)) values for
michael@0:      * align = 1 to 32.
michael@0:      */
michael@0:     static const PRUint8 pmasks[33] = {
michael@0:          0,                                               /*  not used */
michael@0:          0, 1, 3, 3, 7, 7, 7, 7,15,15,15,15,15,15,15,15,  /*  1 ... 16 */
michael@0:         31,31,31,31,31,31,31,31,31,31,31,31,31,31,31,31}; /* 17 ... 32 */
michael@0: 
michael@0:     if (align == 0)
michael@0:         align = PL_ARENA_DEFAULT_ALIGN;
michael@0: 
michael@0:     if (align < sizeof(pmasks)/sizeof(pmasks[0]))
michael@0:         pool->mask = pmasks[align];
michael@0:     else
michael@0:         pool->mask = PR_BITMASK(PR_CeilingLog2(align));
michael@0: 
michael@0:     pool->first.next = NULL;
michael@0:     pool->first.base = pool->first.avail = pool->first.limit =
michael@0:         (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
michael@0:     pool->current = &pool->first;
michael@0:     /*
michael@0:      * Compute the net size so that each arena's gross size is |size|.
michael@0:      * sizeof(PLArena) + pool->mask is the header and alignment slop
michael@0:      * that PL_ArenaAllocate adds to the net size.
michael@0:      */
michael@0:     if (size > sizeof(PLArena) + pool->mask)
michael@0:         pool->arenasize = size - (sizeof(PLArena) + pool->mask);
michael@0:     else
michael@0:         pool->arenasize = size;
michael@0: #ifdef PL_ARENAMETER
michael@0:     memset(&pool->stats, 0, sizeof pool->stats);
michael@0:     pool->stats.name = strdup(name);
michael@0:     pool->stats.next = arena_stats_list;
michael@0:     arena_stats_list = &pool->stats;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: 
michael@0: /*
michael@0: ** PL_ArenaAllocate() -- allocate space from an arena pool
michael@0: ** 
michael@0: ** Description: PL_ArenaAllocate() allocates space from an arena
michael@0: ** pool. 
michael@0: **
michael@0: ** First, try to satisfy the request from arenas starting at
michael@0: ** pool->current.
michael@0: **
michael@0: ** If there is not enough space in the arena pool->current, try
michael@0: ** to claim an arena, on a first fit basis, from the global
michael@0: ** freelist (arena_freelist).
michael@0: ** 
michael@0: ** If no arena in arena_freelist is suitable, then try to
michael@0: ** allocate a new arena from the heap.
michael@0: **
michael@0: ** Returns: pointer to allocated space or NULL
michael@0: ** 
michael@0: ** Notes: The original implementation had some difficult to
michael@0: ** solve bugs; the code was difficult to read. Sometimes it's
michael@0: ** just easier to rewrite it. I did that. larryh.
michael@0: **
michael@0: ** See also: bugzilla: 45343.
michael@0: **
michael@0: */
michael@0: 
michael@0: PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
michael@0: {
michael@0:     PLArena *a;   
michael@0:     char *rp;     /* returned pointer */
michael@0: 
michael@0:     PR_ASSERT((nb & pool->mask) == 0);
michael@0:     
michael@0:     nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
michael@0: 
michael@0:     /* attempt to allocate from arenas at pool->current */
michael@0:     {
michael@0:         a = pool->current;
michael@0:         do {
michael@0:             if ( nb <= a->limit - a->avail )  {
michael@0:                 pool->current = a;
michael@0:                 rp = (char *)a->avail;
michael@0:                 a->avail += nb;
michael@0:                 return rp;
michael@0:             }
michael@0:         } while( NULL != (a = a->next) );
michael@0:     }
michael@0: 
michael@0:     /* attempt to allocate from arena_freelist */
michael@0:     {
michael@0:         PLArena *p; /* previous pointer, for unlinking from freelist */
michael@0: 
michael@0:         /* lock the arena_freelist. Make access to the freelist MT-Safe */
michael@0:         if ( PR_FAILURE == LockArena())
michael@0:             return(0);
michael@0: 
michael@0:         for ( a = arena_freelist, p = NULL; a != NULL ; p = a, a = a->next ) {
michael@0:             if ( nb <= a->limit - a->base )  {
michael@0:                 if ( p == NULL )
michael@0:                     arena_freelist = a->next;
michael@0:                 else
michael@0:                     p->next = a->next;
michael@0:                 UnlockArena();
michael@0:                 a->avail = a->base;
michael@0:                 rp = (char *)a->avail;
michael@0:                 a->avail += nb;
michael@0:                 /* the newly allocated arena is linked after pool->current 
michael@0:                 *  and becomes pool->current */
michael@0:                 a->next = pool->current->next;
michael@0:                 pool->current->next = a;
michael@0:                 pool->current = a;
michael@0:                 if ( NULL == pool->first.next )
michael@0:                     pool->first.next = a;
michael@0:                 return(rp);
michael@0:             }
michael@0:         }
michael@0:         UnlockArena();
michael@0:     }
michael@0: 
michael@0:     /* attempt to allocate from the heap */ 
michael@0:     {  
michael@0:         PRUint32 sz = PR_MAX(pool->arenasize, nb);
michael@0:         if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
michael@0:             a = NULL;
michael@0:         } else {
michael@0:             sz += sizeof *a + pool->mask;  /* header and alignment slop */
michael@0:             a = (PLArena*)PR_MALLOC(sz);
michael@0:         }
michael@0:         if ( NULL != a )  {
michael@0:             a->limit = (PRUword)a + sz;
michael@0:             a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
michael@0:             PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
michael@0:             rp = (char *)a->avail;
michael@0:             a->avail += nb;
michael@0:             /* the newly allocated arena is linked after pool->current 
michael@0:             *  and becomes pool->current */
michael@0:             a->next = pool->current->next;
michael@0:             pool->current->next = a;
michael@0:             pool->current = a;
michael@0:             if ( NULL == pool->first.next )
michael@0:                 pool->first.next = a;
michael@0:             PL_COUNT_ARENA(pool,++);
michael@0:             COUNT(pool, nmallocs);
michael@0:             return(rp);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* we got to here, and there's no memory to allocate */
michael@0:     return(NULL);
michael@0: } /* --- end PL_ArenaAllocate() --- */
michael@0: 
michael@0: PR_IMPLEMENT(void *) PL_ArenaGrow(
michael@0:     PLArenaPool *pool, void *p, PRUint32 size, PRUint32 incr)
michael@0: {
michael@0:     void *newp;
michael@0: 
michael@0:     PL_ARENA_ALLOCATE(newp, pool, size + incr);
michael@0:     if (newp)
michael@0:         memcpy(newp, p, size);
michael@0:     return newp;
michael@0: }
michael@0: 
michael@0: static void ClearArenaList(PLArena *a, PRInt32 pattern)
michael@0: {
michael@0: 
michael@0:     for (; a; a = a->next) {
michael@0:         PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
michael@0:         a->avail = a->base;
michael@0:         PL_CLEAR_UNUSED_PATTERN(a, pattern);
michael@0:         PL_MAKE_MEM_NOACCESS((void*)a->avail, a->limit - a->avail);
michael@0:     }
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
michael@0: {
michael@0:     ClearArenaList(pool->first.next, pattern);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Free tail arenas linked after head, which may not be the true list head.
michael@0:  * Reset pool->current to point to head in case it pointed at a tail arena.
michael@0:  */
michael@0: static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
michael@0: {
michael@0:     PLArena **ap, *a;
michael@0: 
michael@0:     ap = &head->next;
michael@0:     a = *ap;
michael@0:     if (!a)
michael@0:         return;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     ClearArenaList(a, PL_FREE_PATTERN);
michael@0: #endif
michael@0: 
michael@0:     if (reallyFree) {
michael@0:         do {
michael@0:             *ap = a->next;
michael@0:             PL_CLEAR_ARENA(a);
michael@0:             PL_COUNT_ARENA(pool,--);
michael@0:             PR_DELETE(a);
michael@0:         } while ((a = *ap) != 0);
michael@0:     } else {
michael@0:         /* Insert the whole arena chain at the front of the freelist. */
michael@0:         do {
michael@0:             PL_MAKE_MEM_NOACCESS((void*)(*ap)->base,
michael@0:                                  (*ap)->limit - (*ap)->base);
michael@0:             ap = &(*ap)->next;
michael@0:         } while (*ap);
michael@0:         LockArena();
michael@0:         *ap = arena_freelist;
michael@0:         arena_freelist = a;
michael@0:         head->next = 0;
michael@0:         UnlockArena();
michael@0:     }
michael@0: 
michael@0:     pool->current = head;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
michael@0: {
michael@0:     PLArena *a;
michael@0: 
michael@0:     for (a = &pool->first; a; a = a->next) {
michael@0:         if (PR_UPTRDIFF(mark, a->base) <= PR_UPTRDIFF(a->avail, a->base)) {
michael@0:             a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
michael@0:             FreeArenaList(pool, a, PR_FALSE);
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
michael@0: {
michael@0:     FreeArenaList(pool, &pool->first, PR_FALSE);
michael@0:     COUNT(pool, ndeallocs);
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
michael@0: {
michael@0:     FreeArenaList(pool, &pool->first, PR_TRUE);
michael@0: #ifdef PL_ARENAMETER
michael@0:     {
michael@0:         PLArenaStats *stats, **statsp;
michael@0: 
michael@0:         if (pool->stats.name)
michael@0:             PR_DELETE(pool->stats.name);
michael@0:         for (statsp = &arena_stats_list; (stats = *statsp) != 0;
michael@0:              statsp = &stats->next) {
michael@0:             if (stats == &pool->stats) {
michael@0:                 *statsp = stats->next;
michael@0:                 return;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: #endif
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
michael@0: {
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaFinish(void)
michael@0: {
michael@0:     PLArena *a, *next;
michael@0: 
michael@0:     for (a = arena_freelist; a; a = next) {
michael@0:         next = a->next;
michael@0:         PR_DELETE(a);
michael@0:     }
michael@0:     arena_freelist = NULL;
michael@0: 
michael@0:     if (arenaLock) {
michael@0:         PR_DestroyLock(arenaLock);
michael@0:         arenaLock = NULL;
michael@0:     }
michael@0:     once = pristineCallOnce;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(size_t) PL_SizeOfArenaPoolExcludingPool(
michael@0:     const PLArenaPool *pool, PLMallocSizeFn mallocSizeOf)
michael@0: {
michael@0:     /*
michael@0:      * The first PLArena is within |pool|, so don't measure it.  Subsequent
michael@0:      * PLArenas are separate and must be measured.
michael@0:      */
michael@0:     size_t size = 0;
michael@0:     const PLArena *arena = pool->first.next;
michael@0:     while (arena) {
michael@0:         size += mallocSizeOf(arena);
michael@0:         arena = arena->next;
michael@0:     }
michael@0:     return size;
michael@0: }
michael@0: 
michael@0: #ifdef PL_ARENAMETER
michael@0: PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
michael@0: {
michael@0:     pool->stats.nallocs++;
michael@0:     pool->stats.nbytes += nb;
michael@0:     if (nb > pool->stats.maxalloc)
michael@0:         pool->stats.maxalloc = nb;
michael@0:     pool->stats.variance += nb * nb;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
michael@0:     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
michael@0: {
michael@0:     pool->stats.ninplace++;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaCountGrowth(
michael@0:     PLArenaPool *pool, PRUint32 size, PRUint32 incr)
michael@0: {
michael@0:     pool->stats.ngrows++;
michael@0:     pool->stats.nbytes += incr;
michael@0:     pool->stats.variance -= size * size;
michael@0:     size += incr;
michael@0:     if (size > pool->stats.maxalloc)
michael@0:         pool->stats.maxalloc = size;
michael@0:     pool->stats.variance += size * size;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
michael@0: {
michael@0:     pool->stats.nreleases++;
michael@0: }
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
michael@0: {
michael@0:     pool->stats.nfastrels++;
michael@0: }
michael@0: 
michael@0: #include <math.h>
michael@0: #include <stdio.h>
michael@0: 
michael@0: PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
michael@0: {
michael@0:     PLArenaStats *stats;
michael@0:     double mean, variance;
michael@0: 
michael@0:     for (stats = arena_stats_list; stats; stats = stats->next) {
michael@0:         if (stats->nallocs != 0) {
michael@0:             mean = (double)stats->nbytes / stats->nallocs;
michael@0:             variance = fabs(stats->variance / stats->nallocs - mean * mean);
michael@0:         } else {
michael@0:             mean = variance = 0;
michael@0:         }
michael@0: 
michael@0:         fprintf(fp, "\n%s allocation statistics:\n", stats->name);
michael@0:         fprintf(fp, "              number of arenas: %u\n", stats->narenas);
michael@0:         fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
michael@0:         fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
michael@0:         fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
michael@0:         fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
michael@0:         fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
michael@0:         fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
michael@0:         fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
michael@0:         fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
michael@0:         fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
michael@0:         fprintf(fp, "          mean allocation size: %g\n", mean);
michael@0:         fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
michael@0:         fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
michael@0:     }
michael@0: }
michael@0: #endif /* PL_ARENAMETER */