[apple/security.git] / OSX / libsecurity_asn1 / lib / plarena.c

/*
 * Copyright (c) 2003-2006,2008,2010-2012 Apple Inc. All Rights Reserved.
 * 
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/* 
 * 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 the Netscape Portable Runtime (NSPR).
 * 
 * The Initial Developer of the Original Code is Netscape
 * Communications Corporation.  Portions created by Netscape are 
 * Copyright (C) 1998-2000 Netscape Communications Corporation.  All
 * Rights Reserved.
 * 
 * Contributor(s):
 * 
 * Alternatively, the contents of this file may be used under the
 * terms of the GNU General Public License Version 2 or later (the
 * "GPL"), in which case the provisions of the GPL are applicable 
 * instead of those above.  If you wish to allow use of your 
 * version of this file only under the terms of the GPL and not to
 * allow others to use your version of this file under the MPL,
 * indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by
 * the GPL.  If you do not delete the provisions above, a recipient
 * may use your version of this file under either the MPL or the
 * GPL.
 */

/*
 * Lifetime-based fast allocation, inspired by much prior art, including
 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
 */
#include <stdlib.h>
#include <string.h>
#include "plarena.h"
#include "prmem.h"
#include "prbit.h"
#include "prlog.h"
#include "prinit.h"

#ifdef PL_ARENAMETER
static PLArenaStats *arena_stats_list;

#define COUNT(pool,what)  (pool)->stats.what++
#else
#define COUNT(pool,what)  /* nothing */
#endif

#define PL_ARENA_DEFAULT_ALIGN  sizeof(double)

PR_IMPLEMENT(void) PL_InitArenaPool(
    PLArenaPool *pool, const char *name, PRUint32 size, PRUint32 align)
{
#if !defined (__GNUC__)
#pragma unused (name)
#endif

    if (align == 0)
        align = PL_ARENA_DEFAULT_ALIGN;
    pool->mask = PR_BITMASK(PR_CeilingLog2(align));
    pool->first.next = NULL;
    pool->first.base = pool->first.avail = pool->first.limit =
        (PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
    pool->current = &pool->first;
    pool->arenasize = size;                                  
#ifdef PL_ARENAMETER
    memset(&pool->stats, 0, sizeof pool->stats);
    pool->stats.name = strdup(name);
    pool->stats.next = arena_stats_list;
    arena_stats_list = &pool->stats;
#endif
}

#if __APPLE__
#define MAX_SIZE (PR_UINT32_MAX >> 1)
#endif

/*
** PL_ArenaAllocate() -- allocate space from an arena pool
** 
** Description: PL_ArenaAllocate() allocates space from an arena
** pool. 
**
** First, try to satisfy the request from arenas starting at
** pool->current. Then try to allocate a new arena from the heap.
**
** Returns: pointer to allocated space or NULL
** 
** Notes: The original implementation had some difficult to
** solve bugs; the code was difficult to read. Sometimes it's
** just easier to rewrite it. I did that. larryh.
**
** See also: bugzilla: 45343.
**
*/

PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
{
    PLArena *a;   
    char *rp;     /* returned pointer */
    PRUint32 nbOld;

    PR_ASSERT((nb & pool->mask) == 0);
    nbOld = nb;
#ifdef __APPLE__
    nb = PL_ARENA_ALIGN(pool, nb); /* force alignment, cast is useless/causes warning. */
#else
    nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
#endif
    /* ensure that alignment didn't cause overflow */
    if (nb < nbOld)
        return NULL;

    /* attempt to allocate from arenas at pool->current */
    {
        a = pool->current;
        do {
            if ( nb <= a->limit - a->avail )  {
                pool->current = a;
                rp = (char *)a->avail;
                a->avail += nb;
                return rp;
            }
        } while( NULL != (a = a->next) );
    }

    /* attempt to allocate from the heap */ 
    {  
        PRUint32 sz = PR_MAX(pool->arenasize, nb);
        if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
            a = NULL;
        } else {
            sz += sizeof *a + pool->mask;  /* header and alignment slop */
            a = (PLArena*)PR_MALLOC(sz);
        }
#ifdef __APPLE__
        // Check for integer overflow on a->avail += nb
        PRUword a_avail_tmp=(PRUword)PL_ARENA_ALIGN(pool, a + 1);
        if (a_avail_tmp + nb < a_avail_tmp)
        {
            PR_FREEIF(a); // Set a back to NULL
        }
#endif
        if ( NULL != a )  {
            a->limit = (PRUword)a + sz;
#ifdef __APPLE__
            a->base = a->avail = a_avail_tmp;
#else
            a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
#endif
            rp = (char *)a->avail;
            a->avail += nb;
            /* the newly allocated arena is linked after pool->current 
            *  and becomes pool->current */
            a->next = pool->current->next;
            pool->current->next = a;
            pool->current = a;
            if ( NULL == pool->first.next )
                pool->first.next = a;
            PL_COUNT_ARENA(pool,++);
            COUNT(pool, nmallocs);
            return(rp);
        }
    }

    /* we got to here, and there's no memory to allocate */
    return(NULL);
} /* --- end PL_ArenaAllocate() --- */

/*
 * Grow, a.k.a. realloc. The PL_ARENA_GROW macro has already handled
 * the possible grow-in-place action in which the current PLArena is the 
 * source of the incoming pointer, and there is room in that arena for 
 * the requested size. 
 */
PR_IMPLEMENT(void *) PL_ArenaGrow(
    PLArenaPool *pool, void *p, PRUint32 origSize, PRUint32 incr)
{
    void *newp;
	PLArena *thisArena;
	PLArena *lastArena;
	PRUint32 origAlignSize;		// bytes currently reserved for caller
	PRUint32 newSize;			// bytes actually mallocd here

    // Enforce maximal size before any potential implicit truncation
    if (origSize>=MAX_SIZE || incr>=MAX_SIZE) {
        return NULL;
    }
	origAlignSize = PL_ARENA_ALIGN(pool, origSize);
    if (origAlignSize>=MAX_SIZE) {
        return NULL;
    }

    /* expand at least by 2x */
    newSize = PR_MAX(origAlignSize+incr, 2*origAlignSize);
    newSize = PL_ARENA_ALIGN(pool, newSize);

    if (newSize>=MAX_SIZE) {
        return NULL;
    }

    PL_ARENA_ALLOCATE(newp, pool, newSize);
    if (newp == NULL) {
        return NULL;
    }
	/* 
	 * Trim back the memory we just allocated to the amount our caller really
	 * needs, leaving the remainder for grow-in-place on subsequent calls
	 * to PL_ARENA_GROW.
	 */
	PRUint32 newAlignSize = PL_ARENA_ALIGN(pool, origSize+incr);
	PR_ASSERT(pool->current->avail == ((PRUword)newp + newSize));
	pool->current->avail = (PRUword)newp + newAlignSize;
	PR_ASSERT(pool->current->avail <= pool->current->limit);
	
	/* "realloc" */
	memcpy(newp, p, origSize);

	/*
	 * Free old memory only if it's the entire outstanding allocated 
	 * memory associated with one of our known PLArenas. 
	 */
	lastArena = &pool->first;			/* pool->first always empty */
	thisArena = lastArena->next;		/* so, start here */
	
	PRUword origPtr = (PRUword)p;
	while(thisArena != NULL) {
		if(origPtr == thisArena->base) {
			if((origPtr + origAlignSize) == thisArena->avail) {
				/* unlink */
				lastArena->next = thisArena->next;
				
				/* and free */
				PL_CLEAR_ARENA(thisArena);
				PL_COUNT_ARENA(pool,--);
				PR_DELETE(thisArena);
				break;
			}
		}
		lastArena = thisArena;
		thisArena = thisArena->next;
	}
	/* 
	 * Note: inability to free is not an error; it just causes a temporary leak
	 * of the old buffer (until the arena pool is freed, of course).
	 */
    return newp;
}

static void ClearArenaList(PLArena *a, PRInt32 pattern)
{

    for (; a; a = a->next) {
        PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
        a->avail = a->base;
        PL_CLEAR_UNUSED_PATTERN(a, pattern);
    }
}

PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
{
    ClearArenaList(pool->first.next, pattern);
}

/*
 * Free tail arenas linked after head, which may not be the true list head.
 * Reset pool->current to point to head in case it pointed at a tail arena.
 */
static void FreeArenaList(PLArenaPool *pool, PLArena *head, PRBool reallyFree)
{
    PLArena **ap, *a;

    ap = &head->next;
    a = *ap;
    if (!a)
        return;

	do {
		*ap = a->next;
		PL_CLEAR_ARENA(a);
		PL_COUNT_ARENA(pool,--);
		PR_DELETE(a);
	} while ((a = *ap) != 0);

    pool->current = head;
}

PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool *pool, char *mark)
{
	#if ARENA_MARK_ENABLE
    PLArena *a;

    for (a = pool->first.next; a; a = a->next) {
        if (PR_UPTRDIFF(mark, a->base) < PR_UPTRDIFF(a->avail, a->base)) {
            a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
            FreeArenaList(pool, a, PR_FALSE);
            return;
        }
    }
	#endif	/* ARENA_MARK_ENABLE */
}

PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
{
    FreeArenaList(pool, &pool->first, PR_FALSE);
    COUNT(pool, ndeallocs);
}

PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
{
    FreeArenaList(pool, &pool->first, PR_TRUE);
#ifdef PL_ARENAMETER
    {
        PLArenaStats *stats, **statsp;

        if (pool->stats.name)
            PR_DELETE(pool->stats.name);
        for (statsp = &arena_stats_list; (stats = *statsp) != 0;
             statsp = &stats->next) {
            if (stats == &pool->stats) {
                *statsp = stats->next;
                return;
            }
        }
    }
#endif
}

PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
{
}

PR_IMPLEMENT(void) PL_ArenaFinish(void)
{
}

#ifdef PL_ARENAMETER
PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
{
    pool->stats.nallocs++;
    pool->stats.nbytes += nb;
    if (nb > pool->stats.maxalloc)
        pool->stats.maxalloc = nb;
    pool->stats.variance += nb * nb;
}

PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
    PLArenaPool *pool, PRUint32 size, PRUint32 incr)
{
    pool->stats.ninplace++;
}

PR_IMPLEMENT(void) PL_ArenaCountGrowth(
    PLArenaPool *pool, PRUint32 size, PRUint32 incr)
{
    pool->stats.ngrows++;
    pool->stats.nbytes += incr;
    pool->stats.variance -= size * size;
    size += incr;
    if (size > pool->stats.maxalloc)
        pool->stats.maxalloc = size;
    pool->stats.variance += size * size;
}

PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool *pool, char *mark)
{
    pool->stats.nreleases++;
}

PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool *pool, char *mark)
{
    pool->stats.nfastrels++;
}

#include <math.h>
#include <stdio.h>

PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
{
    PLArenaStats *stats;
    double mean, variance;

    for (stats = arena_stats_list; stats; stats = stats->next) {
        if (stats->nallocs != 0) {
            mean = (double)stats->nbytes / stats->nallocs;
            variance = fabs(stats->variance / stats->nallocs - mean * mean);
        } else {
            mean = variance = 0;
        }

        fprintf(fp, "\n%s allocation statistics:\n", stats->name);
        fprintf(fp, "              number of arenas: %u\n", stats->narenas);
        fprintf(fp, "         number of allocations: %u\n", stats->nallocs);
        fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
        fprintf(fp, "        number of malloc calls: %u\n", stats->nmallocs);
        fprintf(fp, "       number of deallocations: %u\n", stats->ndeallocs);
        fprintf(fp, "  number of allocation growths: %u\n", stats->ngrows);
        fprintf(fp, "    number of in-place growths: %u\n", stats->ninplace);
        fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
        fprintf(fp, "       number of fast releases: %u\n", stats->nfastrels);
        fprintf(fp, "         total bytes allocated: %u\n", stats->nbytes);
        fprintf(fp, "          mean allocation size: %g\n", mean);
        fprintf(fp, "            standard deviation: %g\n", sqrt(variance));
        fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
    }
}
#endif /* PL_ARENAMETER */
Commit	Line	Data
b1ab9ed8	1	/*
d8f41ccd	2	* Copyright (c) 2003-2006,2008,2010-2012 Apple Inc. All Rights Reserved.
b1ab9ed8 A	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. Please obtain a copy of the License at
	10	* http://www.opensource.apple.com/apsl/ and read it before using this
	11	* file.
	12	*
	13	* The Original Code and all software distributed under the License are
	14	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	15	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	16	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	17	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	18	* Please see the License for the specific language governing rights and
	19	* limitations under the License.
	20	*
	21	* @APPLE_LICENSE_HEADER_END@
	22	*/
	23	/*
	24	* The contents of this file are subject to the Mozilla Public
	25	* License Version 1.1 (the "License"); you may not use this file
	26	* except in compliance with the License. You may obtain a copy of
	27	* the License at http://www.mozilla.org/MPL/
	28	*
	29	* Software distributed under the License is distributed on an "AS
	30	* IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
	31	* implied. See the License for the specific language governing
	32	* rights and limitations under the License.
	33	*
	34	* The Original Code is the Netscape Portable Runtime (NSPR).
	35	*
	36	* The Initial Developer of the Original Code is Netscape
	37	* Communications Corporation. Portions created by Netscape are
	38	* Copyright (C) 1998-2000 Netscape Communications Corporation. All
	39	* Rights Reserved.
	40	*
	41	* Contributor(s):
	42	*
	43	* Alternatively, the contents of this file may be used under the
	44	* terms of the GNU General Public License Version 2 or later (the
	45	* "GPL"), in which case the provisions of the GPL are applicable
	46	* instead of those above. If you wish to allow use of your
	47	* version of this file only under the terms of the GPL and not to
	48	* allow others to use your version of this file under the MPL,
	49	* indicate your decision by deleting the provisions above and
	50	* replace them with the notice and other provisions required by
	51	* the GPL. If you do not delete the provisions above, a recipient
	52	* may use your version of this file under either the MPL or the
	53	* GPL.
	54	*/
	55
	56	/*
	57	* Lifetime-based fast allocation, inspired by much prior art, including
	58	* "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
	59	* David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
	60	*/
	61	#include <stdlib.h>
	62	#include <string.h>
	63	#include "plarena.h"
	64	#include "prmem.h"
	65	#include "prbit.h"
	66	#include "prlog.h"
67	#include "prinit.h"
68
69	#ifdef PL_ARENAMETER
70	static PLArenaStats *arena_stats_list;
71
72	#define COUNT(pool,what) (pool)->stats.what++
73	#else
74	#define COUNT(pool,what) /* nothing */
75	#endif
76
77	#define PL_ARENA_DEFAULT_ALIGN sizeof(double)
78
79	PR_IMPLEMENT(void) PL_InitArenaPool(
80	PLArenaPool pool, const char name, PRUint32 size, PRUint32 align)
81	{
82	#if !defined (__GNUC__)
83	#pragma unused (name)
84	#endif
85
86	if (align == 0)
87	align = PL_ARENA_DEFAULT_ALIGN;
88	pool->mask = PR_BITMASK(PR_CeilingLog2(align));
89	pool->first.next = NULL;
90	pool->first.base = pool->first.avail = pool->first.limit =
91	(PRUword)PL_ARENA_ALIGN(pool, &pool->first + 1);
92	pool->current = &pool->first;
93	pool->arenasize = size;
94	#ifdef PL_ARENAMETER
95	memset(&pool->stats, 0, sizeof pool->stats);
96	pool->stats.name = strdup(name);
97	pool->stats.next = arena_stats_list;
98	arena_stats_list = &pool->stats;
99	#endif
100	}
101
60c433a9 A	102	#if __APPLE__
	103	#define MAX_SIZE (PR_UINT32_MAX >> 1)
	104	#endif
b1ab9ed8 A	105
	106	/*
	107	** PL_ArenaAllocate() -- allocate space from an arena pool
	108	**
	109	** Description: PL_ArenaAllocate() allocates space from an arena
	110	** pool.
	111	**
	112	** First, try to satisfy the request from arenas starting at
	113	** pool->current. Then try to allocate a new arena from the heap.
	114	**
	115	** Returns: pointer to allocated space or NULL
	116	**
	117	** Notes: The original implementation had some difficult to
	118	** solve bugs; the code was difficult to read. Sometimes it's
	119	** just easier to rewrite it. I did that. larryh.
	120	**
	121	** See also: bugzilla: 45343.
	122	**
	123	*/
	124
	125	PR_IMPLEMENT(void ) PL_ArenaAllocate(PLArenaPool pool, PRUint32 nb)
	126	{
	127	PLArena *a;
	128	char rp; / returned pointer */
e0e0d90e	129	PRUint32 nbOld;
b1ab9ed8 A	130
b1ab9ed8 A	131	PR_ASSERT((nb & pool->mask) == 0);
e0e0d90e	132	nbOld = nb;
60c433a9 A	133	#ifdef __APPLE__
	134	nb = PL_ARENA_ALIGN(pool, nb); /* force alignment, cast is useless/causes warning. */
	135	#else
	136	nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */
	137	#endif
e0e0d90e A	138	/* ensure that alignment didn't cause overflow */
	139	if (nb < nbOld)
	140	return NULL;
b1ab9ed8 A	141
	142	/* attempt to allocate from arenas at pool->current */
	143	{
	144	a = pool->current;
	145	do {
60c433a9	146	if ( nb <= a->limit - a->avail ) {
b1ab9ed8 A	147	pool->current = a;
	148	rp = (char *)a->avail;
	149	a->avail += nb;
	150	return rp;
	151	}
	152	} while( NULL != (a = a->next) );
	153	}
	154
	155	/* attempt to allocate from the heap */
	156	{
60c433a9 A	157	PRUint32 sz = PR_MAX(pool->arenasize, nb);
	158	if (PR_UINT32_MAX - sz < sizeof *a + pool->mask) {
	159	a = NULL;
	160	} else {
	161	sz += sizeof a + pool->mask; / header and alignment slop */
	162	a = (PLArena*)PR_MALLOC(sz);
	163	}
	164	#ifdef __APPLE__
	165	// Check for integer overflow on a->avail += nb
	166	PRUword a_avail_tmp=(PRUword)PL_ARENA_ALIGN(pool, a + 1);
	167	if (a_avail_tmp + nb < a_avail_tmp)
	168	{
	169	PR_FREEIF(a); // Set a back to NULL
	170	}
	171	#endif
b1ab9ed8 A	172	if ( NULL != a ) {
b1ab9ed8 A	173	a->limit = (PRUword)a + sz;
60c433a9 A	174	#ifdef __APPLE__
	175	a->base = a->avail = a_avail_tmp;
	176	#else
b1ab9ed8	177	a->base = a->avail = (PRUword)PL_ARENA_ALIGN(pool, a + 1);
60c433a9	178	#endif
b1ab9ed8 A	179	rp = (char *)a->avail;
	180	a->avail += nb;
	181	/* the newly allocated arena is linked after pool->current
	182	* and becomes pool->current */
	183	a->next = pool->current->next;
	184	pool->current->next = a;
	185	pool->current = a;
	186	if ( NULL == pool->first.next )
	187	pool->first.next = a;
	188	PL_COUNT_ARENA(pool,++);
	189	COUNT(pool, nmallocs);
	190	return(rp);
	191	}
	192	}
	193
	194	/* we got to here, and there's no memory to allocate */
	195	return(NULL);
	196	} /* --- end PL_ArenaAllocate() --- */
	197
	198	/*
	199	* Grow, a.k.a. realloc. The PL_ARENA_GROW macro has already handled
	200	* the possible grow-in-place action in which the current PLArena is the
	201	* source of the incoming pointer, and there is room in that arena for
	202	* the requested size.
	203	*/
	204	PR_IMPLEMENT(void *) PL_ArenaGrow(
	205	PLArenaPool pool, void p, PRUint32 origSize, PRUint32 incr)
	206	{
	207	void *newp;
	208	PLArena *thisArena;
	209	PLArena *lastArena;
	210	PRUint32 origAlignSize; // bytes currently reserved for caller
	211	PRUint32 newSize; // bytes actually mallocd here
e0e0d90e A	212
	213	// Enforce maximal size before any potential implicit truncation
	214	if (origSize>=MAX_SIZE \|\| incr>=MAX_SIZE) {
	215	return NULL;
	216	}
60c433a9	217	origAlignSize = PL_ARENA_ALIGN(pool, origSize);
e0e0d90e A	218	if (origAlignSize>=MAX_SIZE) {
	219	return NULL;
	220	}
	221
	222	/* expand at least by 2x */
60c433a9 A	223	newSize = PR_MAX(origAlignSize+incr, 2*origAlignSize);
60c433a9 A	224	newSize = PL_ARENA_ALIGN(pool, newSize);
e0e0d90e A	225
e0e0d90e A	226	if (newSize>=MAX_SIZE) {
60c433a9 A	227	return NULL;
60c433a9 A	228	}
e0e0d90e	229
b1ab9ed8 A	230	PL_ARENA_ALLOCATE(newp, pool, newSize);
b1ab9ed8 A	231	if (newp == NULL) {
60c433a9 A	232	return NULL;
60c433a9 A	233	}
b1ab9ed8 A	234	/*
	235	* Trim back the memory we just allocated to the amount our caller really
	236	* needs, leaving the remainder for grow-in-place on subsequent calls
	237	* to PL_ARENA_GROW.
	238	*/
	239	PRUint32 newAlignSize = PL_ARENA_ALIGN(pool, origSize+incr);
	240	PR_ASSERT(pool->current->avail == ((PRUword)newp + newSize));
	241	pool->current->avail = (PRUword)newp + newAlignSize;
	242	PR_ASSERT(pool->current->avail <= pool->current->limit);
	243
	244	/* "realloc" */
	245	memcpy(newp, p, origSize);
	246
	247	/*
	248	* Free old memory only if it's the entire outstanding allocated
	249	* memory associated with one of our known PLArenas.
	250	*/
	251	lastArena = &pool->first; /* pool->first always empty */
	252	thisArena = lastArena->next; /* so, start here */
	253
	254	PRUword origPtr = (PRUword)p;
	255	while(thisArena != NULL) {
	256	if(origPtr == thisArena->base) {
	257	if((origPtr + origAlignSize) == thisArena->avail) {
	258	/* unlink */
	259	lastArena->next = thisArena->next;
	260
	261	/* and free */
	262	PL_CLEAR_ARENA(thisArena);
	263	PL_COUNT_ARENA(pool,--);
	264	PR_DELETE(thisArena);
	265	break;
	266	}
	267	}
	268	lastArena = thisArena;
	269	thisArena = thisArena->next;
	270	}
	271	/*
	272	* Note: inability to free is not an error; it just causes a temporary leak
	273	* of the old buffer (until the arena pool is freed, of course).
	274	*/
	275	return newp;
60c433a9 A	276	}
	277
	278	static void ClearArenaList(PLArena *a, PRInt32 pattern)
	279	{
	280
	281	for (; a; a = a->next) {
	282	PR_ASSERT(a->base <= a->avail && a->avail <= a->limit);
	283	a->avail = a->base;
	284	PL_CLEAR_UNUSED_PATTERN(a, pattern);
	285	}
	286	}
	287
	288	PR_IMPLEMENT(void) PL_ClearArenaPool(PLArenaPool *pool, PRInt32 pattern)
	289	{
	290	ClearArenaList(pool->first.next, pattern);
b1ab9ed8 A	291	}
	292
	293	/*
	294	* Free tail arenas linked after head, which may not be the true list head.
	295	* Reset pool->current to point to head in case it pointed at a tail arena.
	296	*/
	297	static void FreeArenaList(PLArenaPool pool, PLArena head, PRBool reallyFree)
	298	{
	299	PLArena *ap, a;
	300
	301	ap = &head->next;
	302	a = *ap;
	303	if (!a)
	304	return;
	305
	306	do {
	307	*ap = a->next;
	308	PL_CLEAR_ARENA(a);
	309	PL_COUNT_ARENA(pool,--);
	310	PR_DELETE(a);
	311	} while ((a = *ap) != 0);
	312
	313	pool->current = head;
	314	}
	315
	316	PR_IMPLEMENT(void) PL_ArenaRelease(PLArenaPool pool, char mark)
	317	{
	318	#if ARENA_MARK_ENABLE
	319	PLArena *a;
	320
	321	for (a = pool->first.next; a; a = a->next) {
	322	if (PR_UPTRDIFF(mark, a->base) < PR_UPTRDIFF(a->avail, a->base)) {
	323	a->avail = (PRUword)PL_ARENA_ALIGN(pool, mark);
	324	FreeArenaList(pool, a, PR_FALSE);
	325	return;
	326	}
	327	}
	328	#endif /* ARENA_MARK_ENABLE */
	329	}
	330
	331	PR_IMPLEMENT(void) PL_FreeArenaPool(PLArenaPool *pool)
	332	{
	333	FreeArenaList(pool, &pool->first, PR_FALSE);
	334	COUNT(pool, ndeallocs);
	335	}
	336
	337	PR_IMPLEMENT(void) PL_FinishArenaPool(PLArenaPool *pool)
	338	{
	339	FreeArenaList(pool, &pool->first, PR_TRUE);
	340	#ifdef PL_ARENAMETER
	341	{
	342	PLArenaStats stats, *statsp;
	343
	344	if (pool->stats.name)
	345	PR_DELETE(pool->stats.name);
	346	for (statsp = &arena_stats_list; (stats = *statsp) != 0;
	347	statsp = &stats->next) {
	348	if (stats == &pool->stats) {
	349	*statsp = stats->next;
	350	return;
	351	}
	352	}
	353	}
	354	#endif
355	}
356
357	PR_IMPLEMENT(void) PL_CompactArenaPool(PLArenaPool *ap)
358	{
359	}
360
361	PR_IMPLEMENT(void) PL_ArenaFinish(void)
362	{
363	}
364
365	#ifdef PL_ARENAMETER
366	PR_IMPLEMENT(void) PL_ArenaCountAllocation(PLArenaPool *pool, PRUint32 nb)
367	{
368	pool->stats.nallocs++;
369	pool->stats.nbytes += nb;
370	if (nb > pool->stats.maxalloc)
371	pool->stats.maxalloc = nb;
372	pool->stats.variance += nb * nb;
373	}
374
375	PR_IMPLEMENT(void) PL_ArenaCountInplaceGrowth(
376	PLArenaPool *pool, PRUint32 size, PRUint32 incr)
377	{
378	pool->stats.ninplace++;
379	}
380
381	PR_IMPLEMENT(void) PL_ArenaCountGrowth(
382	PLArenaPool *pool, PRUint32 size, PRUint32 incr)
383	{
384	pool->stats.ngrows++;
385	pool->stats.nbytes += incr;
386	pool->stats.variance -= size * size;
387	size += incr;
388	if (size > pool->stats.maxalloc)
389	pool->stats.maxalloc = size;
390	pool->stats.variance += size * size;
391	}
392
393	PR_IMPLEMENT(void) PL_ArenaCountRelease(PLArenaPool pool, char mark)
394	{
395	pool->stats.nreleases++;
396	}
397
398	PR_IMPLEMENT(void) PL_ArenaCountRetract(PLArenaPool pool, char mark)
399	{
400	pool->stats.nfastrels++;
401	}
402
403	#include <math.h>
404	#include <stdio.h>
405
406	PR_IMPLEMENT(void) PL_DumpArenaStats(FILE *fp)
407	{
408	PLArenaStats *stats;
409	double mean, variance;
410
411	for (stats = arena_stats_list; stats; stats = stats->next) {
412	if (stats->nallocs != 0) {
413	mean = (double)stats->nbytes / stats->nallocs;
414	variance = fabs(stats->variance / stats->nallocs - mean * mean);
415	} else {
416	mean = variance = 0;
417	}
418
419	fprintf(fp, "\n%s allocation statistics:\n", stats->name);
420	fprintf(fp, " number of arenas: %u\n", stats->narenas);
421	fprintf(fp, " number of allocations: %u\n", stats->nallocs);
422	fprintf(fp, " number of free arena reclaims: %u\n", stats->nreclaims);
423	fprintf(fp, " number of malloc calls: %u\n", stats->nmallocs);
424	fprintf(fp, " number of deallocations: %u\n", stats->ndeallocs);
425	fprintf(fp, " number of allocation growths: %u\n", stats->ngrows);
426	fprintf(fp, " number of in-place growths: %u\n", stats->ninplace);
427	fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
428	fprintf(fp, " number of fast releases: %u\n", stats->nfastrels);
429	fprintf(fp, " total bytes allocated: %u\n", stats->nbytes);
430	fprintf(fp, " mean allocation size: %g\n", mean);
431	fprintf(fp, " standard deviation: %g\n", sqrt(variance));
432	fprintf(fp, " maximum allocation size: %u\n", stats->maxalloc);
433	}
434	}
435	#endif /* PL_ARENAMETER */