You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
334 lines
9.9 KiB
334 lines
9.9 KiB
/*
|
|
* Copyright (C) 1998-2000 Netscape Communications Corporation.
|
|
*
|
|
* Other contributors:
|
|
* Nick Blievers <nickb@adacel.com.au>
|
|
* Jeff Hostetler <jeff@nerdone.com>
|
|
* Tom Rini <trini@kernel.crashing.org>
|
|
* Raffaele Sena <raff@netwinder.org>
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Lesser General Public
|
|
* License as published by the Free Software Foundation; either
|
|
* version 2.1 of the License, or (at your option) any later version.
|
|
*
|
|
* This library is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
* Lesser General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Lesser General Public
|
|
* License along with this library; if not, write to the Free Software
|
|
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
|
|
*
|
|
* Alternatively, the contents of this file may be used under the terms
|
|
* of either the Mozilla Public License Version 1.1, found at
|
|
* http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public
|
|
* License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html
|
|
* (the "GPL"), in which case the provisions of the MPL or 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 one of those two
|
|
* licenses (the MPL or the GPL) and not to allow others to use your
|
|
* version of this file under the LGPL, indicate your decision by
|
|
* deletingthe provisions above and replace them with the notice and
|
|
* other provisions required by the MPL or the GPL, as the case may be.
|
|
* If you do not delete the provisions above, a recipient may use your
|
|
* version of this file under any of the LGPL, 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 <config.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <tdeglobal.h>
|
|
#include "arena.h"
|
|
|
|
#ifdef HAVE_GETPAGESIZE
|
|
#include <unistd.h>
|
|
#define POOL_SIZE kMax(8192u, 2*( unsigned ) getpagesize())
|
|
#else
|
|
#define POOL_SIZE 8192
|
|
#endif
|
|
|
|
//#define DEBUG_ARENA_MALLOC
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
#include <assert.h>
|
|
#include <stdio.h>
|
|
#endif
|
|
|
|
namespace tdehtml {
|
|
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
static int i = 0;
|
|
#endif
|
|
|
|
#define FREELIST_MAX 50
|
|
#define LARGE_ALLOCATION_CEIL(pool) (pool)->arenasize * 256
|
|
#define MAX_DISCRETE_ALLOCATION(pool) (pool)->arenasize * 32
|
|
static Arena *arena_freelist = 0;
|
|
static int freelist_count = 0;
|
|
|
|
#define ARENA_DEFAULT_ALIGN sizeof(double)
|
|
#define BIT(n) ((unsigned int)1 << (n))
|
|
#define BITMASK(n) (BIT(n) - 1)
|
|
#define CEILING_LOG2(_log2,_n) \
|
|
unsigned int j_ = (unsigned int)(_n); \
|
|
(_log2) = 0; \
|
|
if ((j_) & ((j_)-1)) \
|
|
(_log2) += 1; \
|
|
if ((j_) >> 16) \
|
|
(_log2) += 16, (j_) >>= 16; \
|
|
if ((j_) >> 8) \
|
|
(_log2) += 8, (j_) >>= 8; \
|
|
if ((j_) >> 4) \
|
|
(_log2) += 4, (j_) >>= 4; \
|
|
if ((j_) >> 2) \
|
|
(_log2) += 2, (j_) >>= 2; \
|
|
if ((j_) >> 1) \
|
|
(_log2) += 1;
|
|
|
|
int CeilingLog2(unsigned int i) {
|
|
int log2;
|
|
CEILING_LOG2(log2,i);
|
|
return log2;
|
|
}
|
|
|
|
void InitArenaPool(ArenaPool *pool, const char* /*name*/,
|
|
unsigned int /*size*/, unsigned int align)
|
|
{
|
|
unsigned int size = POOL_SIZE;
|
|
if (align == 0)
|
|
align = ARENA_DEFAULT_ALIGN;
|
|
pool->mask = BITMASK(CeilingLog2(align));
|
|
pool->first.next = NULL;
|
|
pool->first.base = pool->first.avail = pool->first.limit =
|
|
(uword)ARENA_ALIGN(pool, &pool->first + 1);
|
|
pool->current = &pool->first;
|
|
pool->arenasize = size;
|
|
pool->largealloc = LARGE_ALLOCATION_CEIL(pool);
|
|
pool->cumul = 0;
|
|
}
|
|
|
|
|
|
/*
|
|
** ArenaAllocate() -- allocate space from an arena pool
|
|
**
|
|
** Description: ArenaAllocate() allocates space from an arena
|
|
** pool.
|
|
**
|
|
** First try to satisfy the request from arenas starting at
|
|
** pool->current.
|
|
**
|
|
** If there is not enough space in the arena pool->current, try
|
|
** to claim an arena, on a first fit basis, from the global
|
|
** freelist (arena_freelist).
|
|
**
|
|
** If no arena in arena_freelist is suitable, then try to
|
|
** allocate a new arena from the heap.
|
|
**
|
|
** Returns: pointer to allocated space or NULL
|
|
**
|
|
*/
|
|
void* ArenaAllocate(ArenaPool *pool, unsigned int nb)
|
|
{
|
|
Arena *a;
|
|
char *rp; /* returned pointer */
|
|
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
assert((nb & pool->mask) == 0);
|
|
#endif
|
|
|
|
nb = (uword)ARENA_ALIGN(pool, nb); /* force alignment */
|
|
|
|
/* attempt to allocate from arenas at pool->current */
|
|
{
|
|
a = pool->current;
|
|
do {
|
|
if ( a->avail +nb <= a->limit ) {
|
|
pool->current = a;
|
|
rp = (char *)a->avail;
|
|
a->avail += nb;
|
|
VALGRIND_MEMPOOL_ALLOC(a->base, rp, nb);
|
|
return rp;
|
|
}
|
|
} while( NULL != (a = a->next) );
|
|
}
|
|
|
|
/* attempt to allocate from arena_freelist */
|
|
{
|
|
Arena *p; /* previous pointer, for unlinking from freelist */
|
|
|
|
for ( a = p = arena_freelist; a != NULL ; p = a, a = a->next ) {
|
|
if ( a->base +nb <= a->limit ) {
|
|
if ( p == arena_freelist )
|
|
arena_freelist = a->next;
|
|
else
|
|
p->next = a->next;
|
|
a->avail = a->base;
|
|
rp = (char *)a->avail;
|
|
a->avail += nb;
|
|
VALGRIND_MEMPOOL_ALLOC(a->base, rp, 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 ( 0 == pool->first.next )
|
|
pool->first.next = a;
|
|
freelist_count--;
|
|
return(rp);
|
|
}
|
|
}
|
|
}
|
|
|
|
/* attempt to allocate from the heap */
|
|
{
|
|
unsigned int sz;
|
|
#ifdef HAVE_MMAP
|
|
if (pool->cumul > pool->largealloc) {
|
|
// High memory pressure. Switch to a fractional allocation strategy
|
|
// so that malloc gets a chance to successfully trim us down when it's over.
|
|
sz = kMin(pool->cumul/25, MAX_DISCRETE_ALLOCATION(pool));
|
|
} else
|
|
#endif
|
|
sz = pool->arenasize > nb ? pool->arenasize : nb;
|
|
sz += sizeof *a + pool->mask; /* header and alignment slop */
|
|
pool->cumul += sz;
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
i++;
|
|
printf("Malloc: %d\n", i);
|
|
#endif
|
|
a = (Arena*)malloc(sz);
|
|
if (a) {
|
|
a->limit = (uword)a + sz;
|
|
a->base = a->avail = (uword)ARENA_ALIGN(pool, a + 1);
|
|
VALGRIND_CREATE_MEMPOOL(a->base, 0, 0);
|
|
rp = (char *)a->avail;
|
|
a->avail += nb;
|
|
VALGRIND_MEMPOOL_ALLOC(a->base, rp, 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 ( !pool->first.next )
|
|
pool->first.next = a;
|
|
return(rp);
|
|
}
|
|
}
|
|
|
|
/* we got to here, and there's no memory to allocate */
|
|
return(0);
|
|
} /* --- end ArenaAllocate() --- */
|
|
|
|
/*
|
|
* 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(ArenaPool *pool, Arena *head, bool reallyFree)
|
|
{
|
|
Arena **ap, *a;
|
|
|
|
ap = &head->next;
|
|
a = *ap;
|
|
if (!a)
|
|
return;
|
|
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
do {
|
|
assert(a->base <= a->avail && a->avail <= a->limit);
|
|
a->avail = a->base;
|
|
CLEAR_UNUSED(a);
|
|
} while ((a = a->next) != 0);
|
|
a = *ap;
|
|
#endif
|
|
|
|
if (freelist_count >= FREELIST_MAX)
|
|
reallyFree = true;
|
|
|
|
if (reallyFree) {
|
|
do {
|
|
*ap = a->next;
|
|
VALGRIND_DESTROY_MEMPOOL(a->base);
|
|
CLEAR_ARENA(a);
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
if (a) {
|
|
i--;
|
|
printf("Free: %d\n", i);
|
|
}
|
|
#endif
|
|
free(a); a = 0;
|
|
} while ((a = *ap) != 0);
|
|
} else {
|
|
/* Insert as much of the arena chain as we can hold at the front of the freelist. */
|
|
do {
|
|
ap = &(*ap)->next;
|
|
freelist_count++;
|
|
} while (*ap && freelist_count < FREELIST_MAX);
|
|
|
|
/* Get rid of excess */
|
|
if (*ap) {
|
|
Arena *xa, *n;
|
|
for (xa = *ap; xa; xa = n) {
|
|
VALGRIND_DESTROY_MEMPOOL(xa->base);
|
|
n = xa->next;
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
i--;
|
|
printf("Free: %d\n", i);
|
|
#endif
|
|
CLEAR_ARENA(xa);
|
|
free(xa);
|
|
}
|
|
}
|
|
*ap = arena_freelist;
|
|
arena_freelist = a;
|
|
head->next = 0;
|
|
}
|
|
pool->current = head;
|
|
}
|
|
|
|
void ArenaRelease(ArenaPool *pool, char *mark)
|
|
{
|
|
Arena *a;
|
|
|
|
for (a = pool->first.next; a; a = a->next) {
|
|
if (UPTRDIFF(mark, a->base) < UPTRDIFF(a->avail, a->base)) {
|
|
a->avail = (uword)ARENA_ALIGN(pool, mark);
|
|
FreeArenaList(pool, a, false);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
void FreeArenaPool(ArenaPool *pool)
|
|
{
|
|
FreeArenaList(pool, &pool->first, false);
|
|
}
|
|
|
|
void FinishArenaPool(ArenaPool *pool)
|
|
{
|
|
FreeArenaList(pool, &pool->first, true);
|
|
}
|
|
|
|
void ArenaFinish()
|
|
{
|
|
Arena *a, *next;
|
|
#ifdef DEBUG_ARENA_MALLOC
|
|
printf("releasing global Arena freelist\n");
|
|
#endif
|
|
for (a = arena_freelist; a; a = next) {
|
|
next = a->next;
|
|
free(a); a = 0;
|
|
}
|
|
freelist_count = 0;
|
|
arena_freelist = NULL;
|
|
}
|
|
|
|
} // namespace
|