jsarena.c

来自「一个基于alice开发的机器人」· C语言 代码 · 共 566 行 · 第 1/2 页

/* -*- 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 */
#include "jslock.h"

static JSArena *arena_freelist;

#ifdef JS_THREADSAFE
static JSLock *arena_freelist_lock;
#endif

#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_InitArenaPool(JSArenaPool *pool, const char *name, size_t size, size_t align)
{
#ifdef JS_THREADSAFE
    /* Must come through here once in primordial thread to init safely! */
    if (!arena_freelist_lock) {
        arena_freelist_lock = JS_NEW_LOCK();
        JS_ASSERT(arena_freelist_lock);
    }
#endif
    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;
#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 greatest distance between a
 * pointer aligned on an M boundary and one aligned on a P boundary is M-P.
 * If M and P are powers of two, then M-P = (pool->mask - POINTER_MASK).
 *
 * How much extra padding might spill over unused into the remainder of the
 * allocation, in the worst case (where M > P)?
 *
 * If we add M-P to the nominal back-pointer address and then round down to
 * align on a P boundary, we will use at most M-P bytes of padding, and at
 * least P (M > P => M >= 2P; M == 2P gives the least padding, P).  So if we
 * use P bytes of padding, then we will overallocate a by P+M-1 bytes, as we
 * also add M-1 to the estimated size in case malloc returns an odd pointer.
 * a->limit must include this overestimation to satisfy a->avail in [a->base,
 * a->limit].
 *
 * Similarly, if pool->mask is less than POINTER_MASK, 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 P > M 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             \
                                    : (pool)->mask - POINTER_MASK))
#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, **bp, *a, *b;
    jsuword extra, hdrsz, gross, sz;
    void *p;

    /* Search pool from current forward till we find or make enough space. */
    JS_ASSERT((nb & pool->mask) == 0);
    for (a = pool->current; a->avail + nb > a->limit; pool->current = a) {
        ap = &a->next;
        if (!*ap) {
            /* Not enough space in pool -- try to reclaim a free arena. */
            extra = (nb > pool->arenasize) ? HEADER_SIZE(pool) : 0;
            hdrsz = sizeof *a + extra + pool->mask;
            gross = hdrsz + JS_MAX(nb, pool->arenasize);
            bp = &arena_freelist;
            JS_ACQUIRE_LOCK(arena_freelist_lock);
            while ((b = *bp) != NULL) {
                /*
                 * Insist on exact arenasize match if nb is not greater than
                 * arenasize.  Otherwise take any arena big enough, but not by
                 * more than gross + arenasize.
                 */
                sz = JS_UPTRDIFF(b->limit, b);
                if (extra
                    ? sz >= gross && sz <= gross + pool->arenasize
                    : sz == gross) {
                    *bp = b->next;
                    JS_RELEASE_LOCK(arena_freelist_lock);
                    b->next = NULL;
                    COUNT(pool, nreclaims);
                    goto claim;
                }
                bp = &b->next;
            }

            /* Nothing big enough on the freelist, so we must malloc. */
            JS_RELEASE_LOCK(arena_freelist_lock);
            b = (JSArena *) malloc(gross);
            if (!b)
                return 0;
            b->next = NULL;
            b->limit = (jsuword)b + gross;
            JS_COUNT_ARENA(pool,++);
            COUNT(pool, nmallocs);

        claim:
            /* 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;

    /*
     * 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 = 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;
    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 = JS_ARENA_ALIGN(pool, 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;
}