trunk/js/jsarena.cpp

/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * 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 Mozilla Communicator client code, released
 * March 31, 1998.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1998
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

/*
 * 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 "jsstddef.h"
#include <stdlib.h>
#include <string.h>
#include "jstypes.h"
#include "jsbit.h"
#include "jsarena.h" /* Added by JSIFY */
#include "jsutil.h" /* Added by JSIFY */

#ifdef JS_ARENAMETER
static JSArenaStats *arena_stats_list;

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

#define JS_ARENA_DEFAULT_ALIGN  sizeof(double)

JS_PUBLIC_API(void)
JS_INIT_NAMED_ARENA_POOL(JSArenaPool *pool, const char *name, size_t size,
                         size_t align, size_t *quotap)
{
    if (align == 0)
        align = JS_ARENA_DEFAULT_ALIGN;
    pool->mask = JS_BITMASK(JS_CeilingLog2(align));
    pool->first.next = NULL;
    pool->first.base = pool->first.avail = pool->first.limit =
        JS_ARENA_ALIGN(pool, &pool->first + 1);
    pool->current = &pool->first;
    pool->arenasize = size;
    pool->quotap = quotap;
#ifdef JS_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
}

/*
 * An allocation that consumes more than pool->arenasize also has a header
 * pointing back to its previous arena's next member.  This header is not
 * included in [a->base, a->limit), so its space can't be wrongly claimed.
 *
 * As the header is a pointer, it must be well-aligned.  If pool->mask is
 * greater than or equal to POINTER_MASK, the header just preceding a->base
 * for an oversized arena a is well-aligned, because a->base is well-aligned.
 * However, we may need to add more space to pad the JSArena ** back-pointer
 * so that it lies just behind a->base, because a might not be aligned such
 * that (jsuword)(a + 1) is on a pointer boundary.
 *
 * By how much must we pad?  Let M be the alignment modulus for pool and P
 * the modulus for a pointer.  Given M >= P, the base of an oversized arena
 * that satisfies M is well-aligned for P.
 *
 * On the other hand, if M < P, we must include enough space in the header
 * size to align the back-pointer on a P boundary so that it can be found by
 * subtracting P from a->base.  This means a->base must be on a P boundary,
 * even though subsequent allocations from a may be aligned on a lesser (M)
 * boundary.  Given powers of two M and P as above, the extra space needed
 * when M < P is P-M or POINTER_MASK - pool->mask.
 *
 * The size of a header including padding is given by the HEADER_SIZE macro,
 * below, for any pool (for any value of M).
 *
 * The mask to align a->base for any pool is (pool->mask | POINTER_MASK), or
 * HEADER_BASE_MASK(pool).
 *
 * PTR_TO_HEADER computes the address of the back-pointer, given an oversized
 * allocation at p.  By definition, p must be a->base for the arena a that
 * contains p.  GET_HEADER and SET_HEADER operate on an oversized arena a, in
 * the case of SET_HEADER with back-pointer ap.
 */
#define POINTER_MASK            ((jsuword)(JS_ALIGN_OF_POINTER - 1))
#define HEADER_SIZE(pool)       (sizeof(JSArena **)                           \
                                 + (((pool)->mask < POINTER_MASK)             \
                                    ? POINTER_MASK - (pool)->mask             \
                                    : 0))
#define HEADER_BASE_MASK(pool)  ((pool)->mask | POINTER_MASK)
#define PTR_TO_HEADER(pool,p)   (JS_ASSERT(((jsuword)(p)                      \
                                            & HEADER_BASE_MASK(pool))         \
                                           == 0),                             \
                                 (JSArena ***)(p) - 1)
#define GET_HEADER(pool,a)      (*PTR_TO_HEADER(pool, (a)->base))
#define SET_HEADER(pool,a,ap)   (*PTR_TO_HEADER(pool, (a)->base) = (ap))

JS_PUBLIC_API(void *)
JS_ArenaAllocate(JSArenaPool *pool, size_t nb)
{
    JSArena **ap, *a, *b;
    jsuword extra, hdrsz, gross;
    void *p;

    /*
     * Search pool from current forward till we find or make enough space.
     *
     * NB: subtract nb from a->limit in the loop condition, instead of adding
     * nb to a->avail, to avoid overflowing a 32-bit address space (possible
     * when running a 32-bit program on a 64-bit system where the kernel maps
     * the heap up against the top of the 32-bit address space).
     *
     * Thanks to Juergen Kreileder <jk@blackdown.de>, who brought this up in
     * https://bugzilla.mozilla.org/show_bug.cgi?id=279273.
     */
    JS_ASSERT((nb & pool->mask) == 0);
    for (a = pool->current; nb > a->limit || a->avail > a->limit - nb;
         pool->current = a) {
        ap = &a->next;
        if (!*ap) {
            /* Not enough space in pool, so we must malloc. */
            extra = (nb > pool->arenasize) ? HEADER_SIZE(pool) : 0;
            hdrsz = sizeof *a + extra + pool->mask;
            gross = hdrsz + JS_MAX(nb, pool->arenasize);
            if (gross < nb)
                return NULL;
            if (pool->quotap) {
                if (gross > *pool->quotap)
                    return NULL;
                b = (JSArena *) malloc(gross);
                if (!b)
                    return NULL;
                *pool->quotap -= gross;
            } else {
                b = (JSArena *) malloc(gross);
                if (!b)
                    return NULL;
            }

            b->next = NULL;
            b->limit = (jsuword)b + gross;
            JS_COUNT_ARENA(pool,++);
            COUNT(pool, nmallocs);

            /* If oversized, store ap in the header, just before a->base. */
            *ap = a = b;
            JS_ASSERT(gross <= JS_UPTRDIFF(a->limit, a));
            if (extra) {
                a->base = a->avail =
                    ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
                SET_HEADER(pool, a, ap);
            } else {
                a->base = a->avail = JS_ARENA_ALIGN(pool, a + 1);
            }
            continue;
        }
        a = *ap;                                /* move to next arena */
    }

    p = (void *)a->avail;
    a->avail += nb;
    JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
    return p;
}

JS_PUBLIC_API(void *)
JS_ArenaRealloc(JSArenaPool *pool, void *p, size_t size, size_t incr)
{
    JSArena **ap, *a, *b;
    jsuword boff, aoff, extra, hdrsz, gross, growth;

    /*
     * Use the oversized-single-allocation header to avoid searching for ap.
     * See JS_ArenaAllocate, the SET_HEADER call.
     */
    if (size > pool->arenasize) {
        ap = *PTR_TO_HEADER(pool, p);
        a = *ap;
    } else {
        ap = &pool->first.next;
        while ((a = *ap) != pool->current)
            ap = &a->next;
    }

    JS_ASSERT(a->base == (jsuword)p);
    boff = JS_UPTRDIFF(a->base, a);
    aoff = JS_ARENA_ALIGN(pool, size + incr);
    JS_ASSERT(aoff > pool->arenasize);
    extra = HEADER_SIZE(pool);                  /* oversized header holds ap */
    hdrsz = sizeof *a + extra + pool->mask;     /* header and alignment slop */
    gross = hdrsz + aoff;
    JS_ASSERT(gross > aoff);
    if (pool->quotap) {
        growth = gross - (a->limit - (jsuword) a);
        if (growth > *pool->quotap)
            return NULL;
        a = (JSArena *) realloc(a, gross);
        if (!a)
            return NULL;
        *pool->quotap -= growth;
    } else {
        a = (JSArena *) realloc(a, gross);
        if (!a)
            return NULL;
    }
#ifdef JS_ARENAMETER
    pool->stats.nreallocs++;
#endif

    if (a != *ap) {
        /* Oops, realloc moved the allocation: update other pointers to a. */
        if (pool->current == *ap)
            pool->current = a;
        b = a->next;
        if (b && b->avail - b->base > pool->arenasize) {
            JS_ASSERT(GET_HEADER(pool, b) == &(*ap)->next);
            SET_HEADER(pool, b, &a->next);
        }

        /* Now update *ap, the next link of the arena before a. */
        *ap = a;
    }

    a->base = ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
    a->limit = (jsuword)a + gross;
    a->avail = a->base + aoff;
    JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);

    /* Check whether realloc aligned differently, and copy if necessary. */
    if (boff != JS_UPTRDIFF(a->base, a))
        memmove((void *)a->base, (char *)a + boff, size);

    /* Store ap in the oversized-load arena header. */
    SET_HEADER(pool, a, ap);
    return (void *)a->base;
}

JS_PUBLIC_API(void *)
JS_ArenaGrow(JSArenaPool *pool, void *p, size_t size, size_t incr)
{
    void *newp;

    /*
     * If p points to an oversized allocation, it owns an entire arena, so we
     * can simply realloc the arena.
     */
    if (size > pool->arenasize)
        return JS_ArenaRealloc(pool, p, size, incr);

    JS_ARENA_ALLOCATE(newp, pool, size + incr);
    if (newp)
        memcpy(newp, p, size);
    return newp;
}

/*
 * 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(JSArenaPool *pool, JSArena *head)
{
    JSArena **ap, *a;

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

#ifdef DEBUG
    do {
        JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
        a->avail = a->base;
        JS_CLEAR_UNUSED(a);
    } while ((a = a->next) != NULL);
    a = *ap;
#endif

    do {
        *ap = a->next;
        if (pool->quotap)
            *pool->quotap += a->limit - (jsuword) a;
        JS_CLEAR_ARENA(a);
        JS_COUNT_ARENA(pool,--);
        free(a);
    } while ((a = *ap) != NULL);

    pool->current = head;
}

JS_PUBLIC_API(void)
JS_ArenaRelease(JSArenaPool *pool, char *mark)
{
    JSArena *a;

    for (a = &pool->first; a; a = a->next) {
        JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);

        if (JS_ARENA_MARK_MATCH(a, mark)) {
            a->avail = JS_ARENA_ALIGN(pool, mark);
            JS_ASSERT(a->avail <= a->limit);
            FreeArenaList(pool, a);
            return;
        }
    }
}

JS_PUBLIC_API(void)
JS_FreeArenaPool(JSArenaPool *pool)
{
    FreeArenaList(pool, &pool->first);
    COUNT(pool, ndeallocs);
}

JS_PUBLIC_API(void)
JS_FinishArenaPool(JSArenaPool *pool)
{
    FreeArenaList(pool, &pool->first);
#ifdef JS_ARENAMETER
    {
        JSArenaStats *stats, **statsp;

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

JS_PUBLIC_API(void)
JS_ArenaFinish()
{
}

JS_PUBLIC_API(void)
JS_ArenaShutDown(void)
{
}

#ifdef JS_ARENAMETER
JS_PUBLIC_API(void)
JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb)
{
    pool->stats.nallocs++;
    pool->stats.nbytes += nb;
    if (nb > pool->stats.maxalloc)
        pool->stats.maxalloc = nb;
    pool->stats.variance += nb * nb;
}

JS_PUBLIC_API(void)
JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr)
{
    pool->stats.ninplace++;
}

JS_PUBLIC_API(void)
JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t 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;
}

JS_PUBLIC_API(void)
JS_ArenaCountRelease(JSArenaPool *pool, char *mark)
{
    pool->stats.nreleases++;
}

JS_PUBLIC_API(void)
JS_ArenaCountRetract(JSArenaPool *pool, char *mark)
{
    pool->stats.nfastrels++;
}

#include <stdio.h>

JS_PUBLIC_API(void)
JS_DumpArenaStats(FILE *fp)
{
    JSArenaStats *stats;
    double mean, sigma;

    for (stats = arena_stats_list; stats; stats = stats->next) {
        mean = JS_MeanAndStdDev(stats->nallocs, stats->nbytes, stats->variance,
                                &sigma);

        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 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 realloc'ing growths: %u\n", stats->nreallocs);
        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", sigma);
        fprintf(fp, "       maximum allocation size: %u\n", stats->maxalloc);
    }
}
#endif /* JS_ARENAMETER */
1	/* -- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
2	*
3	* *** BEGIN LICENSE BLOCK ***
4	* Version: MPL 1.1/GPL 2.0/LGPL 2.1
5	*
6	* The contents of this file are subject to the Mozilla Public License Version
7	* 1.1 (the "License"); you may not use this file except in compliance with
8	* the License. You may obtain a copy of the License at
9	* http://www.mozilla.org/MPL/
10	*
11	* Software distributed under the License is distributed on an "AS IS" basis,
12	* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13	* for the specific language governing rights and limitations under the
14	* License.
15	*
16	* The Original Code is Mozilla Communicator client code, released
17	* March 31, 1998.
18	*
19	* The Initial Developer of the Original Code is
20	* Netscape Communications Corporation.
21	* Portions created by the Initial Developer are Copyright (C) 1998
22	* the Initial Developer. All Rights Reserved.
23	*
24	* Contributor(s):
25	*
26	* Alternatively, the contents of this file may be used under the terms of
27	* either of the GNU General Public License Version 2 or later (the "GPL"),
28	* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29	* in which case the provisions of the GPL or the LGPL are applicable instead
30	* of those above. If you wish to allow use of your version of this file only
31	* under the terms of either the GPL or the LGPL, and not to allow others to
32	* use your version of this file under the terms of the MPL, indicate your
33	* decision by deleting the provisions above and replace them with the notice
34	* and other provisions required by the GPL or the LGPL. If you do not delete
35	* the provisions above, a recipient may use your version of this file under
36	* the terms of any one of the MPL, the GPL or the LGPL.
37	*
38	* *** END LICENSE BLOCK *** */
39
40	/*
41	* Lifetime-based fast allocation, inspired by much prior art, including
42	* "Fast Allocation and Deallocation of Memory Based on Object Lifetimes"
43	* David R. Hanson, Software -- Practice and Experience, Vol. 20(1).
44	*/
45	#include "jsstddef.h"
46	#include <stdlib.h>
47	#include <string.h>
48	#include "jstypes.h"
49	#include "jsbit.h"
50	#include "jsarena.h" /* Added by JSIFY */
51	#include "jsutil.h" /* Added by JSIFY */
52
53	#ifdef JS_ARENAMETER
54	static JSArenaStats *arena_stats_list;
55
56	#define COUNT(pool,what) (pool)->stats.what++
57	#else
58	#define COUNT(pool,what) /* nothing */
59	#endif
60
61	#define JS_ARENA_DEFAULT_ALIGN sizeof(double)
62
63	JS_PUBLIC_API(void)
64	JS_INIT_NAMED_ARENA_POOL(JSArenaPool pool, const char name, size_t size,
65	size_t align, size_t *quotap)
66	{
67	if (align == 0)
68	align = JS_ARENA_DEFAULT_ALIGN;
69	pool->mask = JS_BITMASK(JS_CeilingLog2(align));
70	pool->first.next = NULL;
71	pool->first.base = pool->first.avail = pool->first.limit =
72	JS_ARENA_ALIGN(pool, &pool->first + 1);
73	pool->current = &pool->first;
74	pool->arenasize = size;
75	pool->quotap = quotap;
76	#ifdef JS_ARENAMETER
77	memset(&pool->stats, 0, sizeof pool->stats);
78	pool->stats.name = strdup(name);
79	pool->stats.next = arena_stats_list;
80	arena_stats_list = &pool->stats;
81	#endif
82	}
83
84	/*
85	* An allocation that consumes more than pool->arenasize also has a header
86	* pointing back to its previous arena's next member. This header is not
87	* included in [a->base, a->limit), so its space can't be wrongly claimed.
88	*
89	* As the header is a pointer, it must be well-aligned. If pool->mask is
90	* greater than or equal to POINTER_MASK, the header just preceding a->base
91	* for an oversized arena a is well-aligned, because a->base is well-aligned.
92	* However, we may need to add more space to pad the JSArena ** back-pointer
93	* so that it lies just behind a->base, because a might not be aligned such
94	* that (jsuword)(a + 1) is on a pointer boundary.
95	*
96	* By how much must we pad? Let M be the alignment modulus for pool and P
97	* the modulus for a pointer. Given M >= P, the base of an oversized arena
98	* that satisfies M is well-aligned for P.
99	*
100	* On the other hand, if M < P, we must include enough space in the header
101	* size to align the back-pointer on a P boundary so that it can be found by
102	* subtracting P from a->base. This means a->base must be on a P boundary,
103	* even though subsequent allocations from a may be aligned on a lesser (M)
104	* boundary. Given powers of two M and P as above, the extra space needed
105	* when M < P is P-M or POINTER_MASK - pool->mask.
106	*
107	* The size of a header including padding is given by the HEADER_SIZE macro,
108	* below, for any pool (for any value of M).
109	*
110	* The mask to align a->base for any pool is (pool->mask \| POINTER_MASK), or
111	* HEADER_BASE_MASK(pool).
112	*
113	* PTR_TO_HEADER computes the address of the back-pointer, given an oversized
114	* allocation at p. By definition, p must be a->base for the arena a that
115	* contains p. GET_HEADER and SET_HEADER operate on an oversized arena a, in
116	* the case of SET_HEADER with back-pointer ap.
117	*/
118	#define POINTER_MASK ((jsuword)(JS_ALIGN_OF_POINTER - 1))
119	#define HEADER_SIZE(pool) (sizeof(JSArena **) \
120	+ (((pool)->mask < POINTER_MASK) \
121	? POINTER_MASK - (pool)->mask \
122	: 0))
123	#define HEADER_BASE_MASK(pool) ((pool)->mask \| POINTER_MASK)
124	#define PTR_TO_HEADER(pool,p) (JS_ASSERT(((jsuword)(p) \
125	& HEADER_BASE_MASK(pool)) \
126	== 0), \
127	(JSArena ***)(p) - 1)
128	#define GET_HEADER(pool,a) (*PTR_TO_HEADER(pool, (a)->base))
129	#define SET_HEADER(pool,a,ap) (*PTR_TO_HEADER(pool, (a)->base) = (ap))
130
131	JS_PUBLIC_API(void *)
132	JS_ArenaAllocate(JSArenaPool *pool, size_t nb)
133	{
134	JSArena *ap, a, *b;
135	jsuword extra, hdrsz, gross;
136	void *p;
137
138	/*
139	* Search pool from current forward till we find or make enough space.
140	*
141	* NB: subtract nb from a->limit in the loop condition, instead of adding
142	* nb to a->avail, to avoid overflowing a 32-bit address space (possible
143	* when running a 32-bit program on a 64-bit system where the kernel maps
144	* the heap up against the top of the 32-bit address space).
145	*
146	* Thanks to Juergen Kreileder <jk@blackdown.de>, who brought this up in
147	* https://bugzilla.mozilla.org/show_bug.cgi?id=279273.
148	*/
149	JS_ASSERT((nb & pool->mask) == 0);
150	for (a = pool->current; nb > a->limit \|\| a->avail > a->limit - nb;
151	pool->current = a) {
152	ap = &a->next;
153	if (!*ap) {
154	/* Not enough space in pool, so we must malloc. */
155	extra = (nb > pool->arenasize) ? HEADER_SIZE(pool) : 0;
156	hdrsz = sizeof *a + extra + pool->mask;
157	gross = hdrsz + JS_MAX(nb, pool->arenasize);
158	if (gross < nb)
159	return NULL;
160	if (pool->quotap) {
161	if (gross > *pool->quotap)
162	return NULL;
163	b = (JSArena *) malloc(gross);
164	if (!b)
165	return NULL;
166	*pool->quotap -= gross;
167	} else {
168	b = (JSArena *) malloc(gross);
169	if (!b)
170	return NULL;
171	}
172
173	b->next = NULL;
174	b->limit = (jsuword)b + gross;
175	JS_COUNT_ARENA(pool,++);
176	COUNT(pool, nmallocs);
177
178	/* If oversized, store ap in the header, just before a->base. */
179	*ap = a = b;
180	JS_ASSERT(gross <= JS_UPTRDIFF(a->limit, a));
181	if (extra) {
182	a->base = a->avail =
183	((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
184	SET_HEADER(pool, a, ap);
185	} else {
186	a->base = a->avail = JS_ARENA_ALIGN(pool, a + 1);
187	}
188	continue;
189	}
190	a = ap; / move to next arena */
191	}
192
193	p = (void *)a->avail;
194	a->avail += nb;
195	JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
196	return p;
197	}
198
199	JS_PUBLIC_API(void *)
200	JS_ArenaRealloc(JSArenaPool pool, void p, size_t size, size_t incr)
201	{
202	JSArena *ap, a, *b;
203	jsuword boff, aoff, extra, hdrsz, gross, growth;
204
205	/*
206	* Use the oversized-single-allocation header to avoid searching for ap.
207	* See JS_ArenaAllocate, the SET_HEADER call.
208	*/
209	if (size > pool->arenasize) {
210	ap = *PTR_TO_HEADER(pool, p);
211	a = *ap;
212	} else {
213	ap = &pool->first.next;
214	while ((a = *ap) != pool->current)
215	ap = &a->next;
216	}
217
218	JS_ASSERT(a->base == (jsuword)p);
219	boff = JS_UPTRDIFF(a->base, a);
220	aoff = JS_ARENA_ALIGN(pool, size + incr);
221	JS_ASSERT(aoff > pool->arenasize);
222	extra = HEADER_SIZE(pool); /* oversized header holds ap */
223	hdrsz = sizeof a + extra + pool->mask; / header and alignment slop */
224	gross = hdrsz + aoff;
225	JS_ASSERT(gross > aoff);
226	if (pool->quotap) {
227	growth = gross - (a->limit - (jsuword) a);
228	if (growth > *pool->quotap)
229	return NULL;
230	a = (JSArena *) realloc(a, gross);
231	if (!a)
232	return NULL;
233	*pool->quotap -= growth;
234	} else {
235	a = (JSArena *) realloc(a, gross);
236	if (!a)
237	return NULL;
238	}
239	#ifdef JS_ARENAMETER
240	pool->stats.nreallocs++;
241	#endif
242
243	if (a != *ap) {
244	/* Oops, realloc moved the allocation: update other pointers to a. */
245	if (pool->current == *ap)
246	pool->current = a;
247	b = a->next;
248	if (b && b->avail - b->base > pool->arenasize) {
249	JS_ASSERT(GET_HEADER(pool, b) == &(*ap)->next);
250	SET_HEADER(pool, b, &a->next);
251	}
252
253	/* Now update ap, the next link of the arena before a. /
254	*ap = a;
255	}
256
257	a->base = ((jsuword)a + hdrsz) & ~HEADER_BASE_MASK(pool);
258	a->limit = (jsuword)a + gross;
259	a->avail = a->base + aoff;
260	JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
261
262	/* Check whether realloc aligned differently, and copy if necessary. */
263	if (boff != JS_UPTRDIFF(a->base, a))
264	memmove((void )a->base, (char )a + boff, size);
265
266	/* Store ap in the oversized-load arena header. */
267	SET_HEADER(pool, a, ap);
268	return (void *)a->base;
269	}
270
271	JS_PUBLIC_API(void *)
272	JS_ArenaGrow(JSArenaPool pool, void p, size_t size, size_t incr)
273	{
274	void *newp;
275
276	/*
277	* If p points to an oversized allocation, it owns an entire arena, so we
278	* can simply realloc the arena.
279	*/
280	if (size > pool->arenasize)
281	return JS_ArenaRealloc(pool, p, size, incr);
282
283	JS_ARENA_ALLOCATE(newp, pool, size + incr);
284	if (newp)
285	memcpy(newp, p, size);
286	return newp;
287	}
288
289	/*
290	* Free tail arenas linked after head, which may not be the true list head.
291	* Reset pool->current to point to head in case it pointed at a tail arena.
292	*/
293	static void
294	FreeArenaList(JSArenaPool pool, JSArena head)
295	{
296	JSArena *ap, a;
297
298	ap = &head->next;
299	a = *ap;
300	if (!a)
301	return;
302
303	#ifdef DEBUG
304	do {
305	JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
306	a->avail = a->base;
307	JS_CLEAR_UNUSED(a);
308	} while ((a = a->next) != NULL);
309	a = *ap;
310	#endif
311
312	do {
313	*ap = a->next;
314	if (pool->quotap)
315	*pool->quotap += a->limit - (jsuword) a;
316	JS_CLEAR_ARENA(a);
317	JS_COUNT_ARENA(pool,--);
318	free(a);
319	} while ((a = *ap) != NULL);
320
321	pool->current = head;
322	}
323
324	JS_PUBLIC_API(void)
325	JS_ArenaRelease(JSArenaPool pool, char mark)
326	{
327	JSArena *a;
328
329	for (a = &pool->first; a; a = a->next) {
330	JS_ASSERT(a->base <= a->avail && a->avail <= a->limit);
331
332	if (JS_ARENA_MARK_MATCH(a, mark)) {
333	a->avail = JS_ARENA_ALIGN(pool, mark);
334	JS_ASSERT(a->avail <= a->limit);
335	FreeArenaList(pool, a);
336	return;
337	}
338	}
339	}
340
341	JS_PUBLIC_API(void)
342	JS_FreeArenaPool(JSArenaPool *pool)
343	{
344	FreeArenaList(pool, &pool->first);
345	COUNT(pool, ndeallocs);
346	}
347
348	JS_PUBLIC_API(void)
349	JS_FinishArenaPool(JSArenaPool *pool)
350	{
351	FreeArenaList(pool, &pool->first);
352	#ifdef JS_ARENAMETER
353	{
354	JSArenaStats stats, *statsp;
355
356	if (pool->stats.name) {
357	free(pool->stats.name);
358	pool->stats.name = NULL;
359	}
360	for (statsp = &arena_stats_list; (stats = *statsp) != 0;
361	statsp = &stats->next) {
362	if (stats == &pool->stats) {
363	*statsp = stats->next;
364	return;
365	}
366	}
367	}
368	#endif
369	}
370
371	JS_PUBLIC_API(void)
372	JS_ArenaFinish()
373	{
374	}
375
376	JS_PUBLIC_API(void)
377	JS_ArenaShutDown(void)
378	{
379	}
380
381	#ifdef JS_ARENAMETER
382	JS_PUBLIC_API(void)
383	JS_ArenaCountAllocation(JSArenaPool *pool, size_t nb)
384	{
385	pool->stats.nallocs++;
386	pool->stats.nbytes += nb;
387	if (nb > pool->stats.maxalloc)
388	pool->stats.maxalloc = nb;
389	pool->stats.variance += nb * nb;
390	}
391
392	JS_PUBLIC_API(void)
393	JS_ArenaCountInplaceGrowth(JSArenaPool *pool, size_t size, size_t incr)
394	{
395	pool->stats.ninplace++;
396	}
397
398	JS_PUBLIC_API(void)
399	JS_ArenaCountGrowth(JSArenaPool *pool, size_t size, size_t incr)
400	{
401	pool->stats.ngrows++;
402	pool->stats.nbytes += incr;
403	pool->stats.variance -= size * size;
404	size += incr;
405	if (size > pool->stats.maxalloc)
406	pool->stats.maxalloc = size;
407	pool->stats.variance += size * size;
408	}
409
410	JS_PUBLIC_API(void)
411	JS_ArenaCountRelease(JSArenaPool pool, char mark)
412	{
413	pool->stats.nreleases++;
414	}
415
416	JS_PUBLIC_API(void)
417	JS_ArenaCountRetract(JSArenaPool pool, char mark)
418	{
419	pool->stats.nfastrels++;
420	}
421
422	#include <stdio.h>
423
424	JS_PUBLIC_API(void)
425	JS_DumpArenaStats(FILE *fp)
426	{
427	JSArenaStats *stats;
428	double mean, sigma;
429
430	for (stats = arena_stats_list; stats; stats = stats->next) {
431	mean = JS_MeanAndStdDev(stats->nallocs, stats->nbytes, stats->variance,
432	&sigma);
433
434	fprintf(fp, "\n%s allocation statistics:\n", stats->name);
435	fprintf(fp, " number of arenas: %u\n", stats->narenas);
436	fprintf(fp, " number of allocations: %u\n", stats->nallocs);
437	fprintf(fp, " number of malloc calls: %u\n", stats->nmallocs);
438	fprintf(fp, " number of deallocations: %u\n", stats->ndeallocs);
439	fprintf(fp, " number of allocation growths: %u\n", stats->ngrows);
440	fprintf(fp, " number of in-place growths: %u\n", stats->ninplace);
441	fprintf(fp, " number of realloc'ing growths: %u\n", stats->nreallocs);
442	fprintf(fp, "number of released allocations: %u\n", stats->nreleases);
443	fprintf(fp, " number of fast releases: %u\n", stats->nfastrels);
444	fprintf(fp, " total bytes allocated: %u\n", stats->nbytes);
445	fprintf(fp, " mean allocation size: %g\n", mean);
446	fprintf(fp, " standard deviation: %g\n", sigma);
447	fprintf(fp, " maximum allocation size: %u\n", stats->maxalloc);
448	}
449	}
450	#endif /* JS_ARENAMETER */