X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/0875b58fcccadd756e11487185c2ac1d3ed8ab4d..d4efbcd93c940ad522fcf8c601ec1829d2e0b10d:/sub.c diff --git a/sub.c b/sub.c index 2f0fed3..06570b6 100644 --- a/sub.c +++ b/sub.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sub.c,v 1.1 1998/06/17 23:44:42 mdw Exp $ + * $Id: sub.c,v 1.9 2004/04/08 01:36:13 mdw Exp $ * * Allocation of known-size blocks * @@ -12,32 +12,25 @@ * This file is part of the mLib utilities library. * * mLib is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. * * mLib 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with mLib; if not, write to the Free Software Foundation, - * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - */ - -/*----- Revision history --------------------------------------------------* - * - * $Log: sub.c,v $ - * Revision 1.1 1998/06/17 23:44:42 mdw - * Initial revision + * GNU Library General Public License for more details. * + * You should have received a copy of the GNU Library General Public + * License along with mLib; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. */ /*----- 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 @@ -67,157 +60,278 @@ /* --- ANSI headers --- */ +#include #include #include #include /* --- 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 ------------------------------------------*/ +/*----- Configuration tweaks ----------------------------------------------*/ -/* --- The largest block I'll handle here --- * - * - * Anything larger will be handed on to @malloc@. - */ +/* #define SUBARENA_TRIVIAL */ -#define SUB_MAXBIN 256 +/*----- Static 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. - */ +static size_t sizes[SUB_BINS]; -#define SUB_CHUNK 4096 +/*----- Global variables --------------------------------------------------*/ -/*----- Other useful macros -----------------------------------------------*/ +subarena sub_global; -/* --- The granularity of bin buffers --- * - * - * 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. - */ +#ifdef SUBARENA_TRIVIAL -#define SUB_GRANULE sizeof(void *) +typedef struct sub_link { + struct sub_link *next; + void *p; + size_t sz; +} sub_link; + +#endif -/* --- Finding the right bin for a given size --- * +/*----- Main code ---------------------------------------------------------*/ + +/* --- @subarena_create@ --- * + * + * 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) +{ +#ifdef SUBARENA_TRIVIAL + s->bin[0] = 0; +#else + size_t i; + if (!sizes[1]) + sub_init(); + for (i = 0; i < SUB_BINS; i++) + s->bin[i] = 0; +#endif + s->a = a; +} -/* --- Convert a bin back to the block size --- * +/* --- @subarena_destroy@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to destroy + * + * Returns: --- * - * This gives the size of block contained in a given bin. + * 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) +void subarena_destroy(subarena *s) +{ +#ifdef SUBARENA_TRIVIAL -/* --- Number of bins required --- */ + sub_link *l, *ll; -#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1) + for (l = s->bin[0]; l; l = ll) { + ll = l; + a_free(s->a, l->p); + a_free(s->a, l); + } + s->bin[0] = 0; -/*----- Static variables --------------------------------------------------*/ +#else -static void *sub__bins[SUB_BINS]; -static size_t sub__sizes[SUB_BINS]; + 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); + } + s->bin[i] = 0; + } -/*----- Main code ---------------------------------------------------------*/ +#endif +} -/* --- @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. + * 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); +#ifdef SUBARENA_TRIVIAL + + sub_link *l; void *p; + if (!s->a) + subarena_create(s, arena_global); + + if ((l = a_alloc(s->a, sizeof(*l))) == 0) + return (0); + if ((p = a_alloc(s->a, sz)) == 0) { + a_free(s->a, l); + return (0); + } + l->p = p; + l->sz = sz; + l->next = s->bin[0]; + s->bin[0] = l; + return (p); + +#else + + int bin; + void *p; + + /* --- Ensure that everything is initialized --- */ + + if (!s->a) + subarena_create(s, arena_global); + /* --- Handle oversize blocks --- */ - if (bin >= SUB_BINS) - return (xmalloc(s)); + bin = SUB_BIN(sz); + 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); + +#endif } -/* --- @sub_free@ --- * +/* --- @subarena_free@ --- * * - * Arguments: @void *p@ = address of block to free - * @size_t s@ = size of block + * Arguments: @subarena *s@ = pointer to arena + * @void *p@ = address of block to free + * @size_t s@ = size of block * - * Returns: --- + * 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); +#ifdef SUBARENA_TRIVIAL + + sub_link *lh = s->bin[0], **l, *ll; + + for (l = &lh; *l && (*l)->p != p; l = &(*l)->next) + ; + ll = *l; + assert(ll); + assert(ll->sz == sz); + *l = ll->next; + a_free(s->a, ll); + a_free(s->a, p); + s->bin[0] = lh; + +#else + + 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; } + +#endif } +/*----- 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: --- + * Arguments: --- * - * Returns: --- + * Returns: --- * - * Use: Initialises the magic allocator. + * Use: Initializes the magic allocator. */ void sub_init(void) { +#ifndef SUBARENA_TRIVIAL 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)); } +#endif } /*----- Debugging code ----------------------------------------------------*/