X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/0bd984429304da7c1c5509103e3dc04149028a95..6a418da9ec557fa94aac8b6e9ce51e6dbbd40e8b:/sub.c diff --git a/sub.c b/sub.c index b0d1895..45dcac4 100644 --- a/sub.c +++ b/sub.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sub.c,v 1.3 1999/05/06 19:51:35 mdw Exp $ + * $Id: sub.c,v 1.6 2000/06/17 10:35:51 mdw Exp $ * * Allocation of known-size blocks * @@ -30,6 +30,15 @@ /*----- Revision history --------------------------------------------------* * * $Log: sub.c,v $ + * Revision 1.6 2000/06/17 10:35:51 mdw + * Major overhaul for arena support. + * + * Revision 1.5 1999/05/19 20:27:11 mdw + * Change naming to match newer mLib conventions. + * + * Revision 1.4 1999/05/13 22:48:55 mdw + * Change `-ise' to `-ize' throughout. + * * Revision 1.3 1999/05/06 19:51:35 mdw * Reformatted the LGPL notice a little bit. * @@ -44,7 +53,7 @@ /*----- The big idea ------------------------------------------------------* * * This file provides an extra layer over @malloc@. It provides fast - * turnover for small blocks, and tries to minimise the per-block overhead. + * turnover for small blocks, and tries to minimize the per-block overhead. * * To do its job, @alloc@ must place an extra restriction on you: you must * know the size of a block when you free it. Usually you'll have this @@ -80,149 +89,191 @@ /* --- Local headers --- */ -#undef TRACK_ENABLE /* Can't track suballoc routines */ -#include "alloc.h" +#include "arena.h" +#include "exc.h" +#include "sub.h" -/*----- Configuration and tuning ------------------------------------------*/ +/*----- Static variables --------------------------------------------------*/ -/* --- The largest block I'll handle here --- * - * - * Anything larger will be handed on to @malloc@. - */ +static size_t sizes[SUB_BINS]; -#define SUB_MAXBIN 256 +/*----- Global variables --------------------------------------------------*/ -/* --- Preferred chunk size --- * - * - * When a bin is empty, I'll allocate a large chunk of approximately this - * size and divvy it up into small bin-sized blocks. - */ +subarena sub_global; -#define SUB_CHUNK 4096 - -/*----- Other useful macros -----------------------------------------------*/ +/*----- Main code ---------------------------------------------------------*/ -/* --- The granularity of bin buffers --- * +/* --- @subarena_create@ --- * * - * All blocks allocated by the binner are a multiple of this size. I've - * chosen @void *@ because I need to store @void *@ things in here. - */ - -#define SUB_GRANULE sizeof(void *) - -/* --- Finding the right bin for a given size --- * + * Arguments: @subarena *s@ = pointer to arena to initialize + * @arena *a@ = pointer to underlying arena block + * + * Returns: --- * - * This chooses the correct bin for an allocation. Input is the size of - * block wanted; result is the bin index. + * Use: Initialize a suballocation arena based on an underlying large + * blocks arena. */ -#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE) +void subarena_create(subarena *s, arena *a) +{ + size_t i; + if (!sizes[1]) + sub_init(); + for (i = 0; i < SUB_BINS; i++) + s->bin[i] = 0; + s->a = a; +} -/* --- Convert a bin back to the block size --- * +/* --- @subarena_destroy@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to destroy * - * This gives the size of block contained in a given bin. + * Returns: --- + * + * Use: Destroys a suballocation arena, freeing all of the memory it + * contains back to the underlying large blocks arena. */ -#define SUB_BINSZ(x) ((x) * SUB_GRANULE) - -/* --- Number of bins required --- */ - -#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1) - -/*----- Static variables --------------------------------------------------*/ - -static void *sub__bins[SUB_BINS]; -static size_t sub__sizes[SUB_BINS]; - -/*----- Main code ---------------------------------------------------------*/ +void subarena_destroy(subarena *s) +{ + size_t i; + for (i = 0; i < SUB_BINS; i++) { + void *p = s->bin[i]; + while (p) { + void *q = p; + p = *(void **)q; + A_FREE(s->a, q); + } + } +} -/* --- @sub_alloc@ --- * +/* --- @subarena_alloc@ --- * * - * Arguments: @size_t s@ = size of chunk wanted + * Arguments: @subarena *s@ = pointer to arena + * @size_t s@ = size of chunk wanted * * Returns: Pointer to a block at least as large as the one wanted. * - * Use: Allocates a small block of memory. If there is no more - * memory left, the exception @EXC_NOMEM@ is raised. + * Use: Allocates a small block of memory from the given pool. The + * exception @EXC_NOMEM@ is raised if the underlying arena is + * full. */ -void *sub_alloc(size_t s) +void *subarena_alloc(subarena *s, size_t sz) { - int bin = SUB_BIN(s); + int bin; void *p; + /* --- Ensure that everything is initialized --- */ + + if (!s->a) + subarena_create(s, arena_global); + bin = SUB_BIN(sz); + /* --- Handle oversize blocks --- */ - if (bin >= SUB_BINS) - return (xmalloc(s)); + if (bin >= SUB_BINS) { + void *p = A_ALLOC(s->a, sz); + if (!p) + THROW(EXC_NOMEM); + return (p); + } /* --- If the bin is empty, find some memory --- */ - if (!sub__bins[bin]) { + if (!s->bin[bin]) { char *p, *q; - p = xmalloc(sub__sizes[bin]); - q = p + sub__sizes[bin]; + p = A_ALLOC(s->a, sizes[bin]); + if (!p) + THROW(EXC_NOMEM); + q = p + sizes[bin]; - s = SUB_BINSZ(bin); + sz = SUB_BINSZ(bin); - q -= s; + q -= sz; *(void **)q = 0; while (q > p) { - q -= s; - *(void **)q = q + s; + q -= sz; + *(void **)q = q + sz; } - sub__bins[bin] = p; + s->bin[bin] = p; } /* --- Extract the first block in the list --- */ - p = sub__bins[bin]; - sub__bins[bin] = *(void **)p; + p = s->bin[bin]; + s->bin[bin] = *(void **)p; return (p); } -/* --- @sub_free@ --- * +/* --- @subarena_free@ --- * * - * Arguments: @void *p@ = address of block to free + * Arguments: @subarena *s@ = pointer to arena + * @void *p@ = address of block to free * @size_t s@ = size of block * * Returns: --- * - * Use: Frees a block allocated by @sub_alloc@. + * Use: Frees a block allocated by @subarena_alloc@. */ -void sub_free(void *p, size_t s) +void subarena_free(subarena *s, void *p, size_t sz) { - int bin = SUB_BIN(s); + int bin = SUB_BIN(sz); if (bin >= SUB_BINS) - free(p); + A_FREE(s->a, p); else { - *(void **)p = sub__bins[bin]; - sub__bins[bin] = p; + *(void **)p = s->bin[bin]; + s->bin[bin] = p; } } +/*----- Compatibility stuff -----------------------------------------------*/ + +/* --- @sub_alloc@ --- * + * + * Arguments: @size_t s@ = size of chunk wanted + * + * Returns: Pointer to a block at least as large as the one wanted. + * + * Use: Allocates a small block of memory from the @sub_global@ pool. + */ + +void *(sub_alloc)(size_t sz) { return sub_alloc(sz); } + +/* --- @sub_free@ --- * + * + * Arguments: @void *p@ = address of block to free + * @size_t s@ = size of block + * + * Returns: --- + * + * Use: Frees a block allocated by @sub_alloc@. + */ + +void (sub_free)(void *p, size_t sz) { sub_free(p, sz); } + /* --- @sub_init@ --- * * * Arguments: --- * * Returns: --- * - * Use: Initialises the magic allocator. + * Use: Initializes the magic allocator. */ void sub_init(void) { int i; - /* --- Initialise the sizes bins --- */ + /* --- Initialize the sizes bins --- */ for (i = 1; i < SUB_BINS; i++) { - sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) / + sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) / SUB_BINSZ(i) * SUB_BINSZ(i)); } }