From 0fd574c3198e0a08b7b27972f7931d0c7deb19fb Mon Sep 17 00:00:00 2001 Message-Id: <0fd574c3198e0a08b7b27972f7931d0c7deb19fb.1715536595.git.mdw@distorted.org.uk> From: Mark Wooding Date: Sat, 17 Jun 2000 10:35:51 +0000 Subject: [PATCH] Major overhaul for arena support. Organization: Straylight/Edgeware From: mdw --- alloc.c | 100 ++++++++++++++++++++++++++----- alloc.h | 85 ++++++++++++++++++++++++++- sub.c | 179 +++++++++++++++++++++++++++++++++++--------------------- sub.h | 168 ++++++++++++++++++++++++++++++++++++++++++++++------ 4 files changed, 431 insertions(+), 101 deletions(-) diff --git a/alloc.c b/alloc.c index 0c00888..d425e97 100644 --- a/alloc.c +++ b/alloc.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: alloc.c,v 1.3 1999/05/06 19:51:35 mdw Exp $ + * $Id: alloc.c,v 1.4 2000/06/17 10:35:51 mdw Exp $ * * Memory allocation functions * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: alloc.c,v $ + * Revision 1.4 2000/06/17 10:35:51 mdw + * Major overhaul for arena support. + * * Revision 1.3 1999/05/06 19:51:35 mdw * Reformatted the LGPL notice a little bit. * @@ -52,14 +55,15 @@ /* --- Local headers --- */ #include "alloc.h" +#include "arena.h" #include "exc.h" -#include "track.h" -/*----- Functions provided ------------------------------------------------*/ +/*----- Functions and macros ----------------------------------------------*/ -/* --- @xmalloc@ --- * +/* --- @x_alloc@ --- * * - * Arguments: @size_t sz@ = size of block to allocate + * Arguments: @arena *a@ = pointer to underlying arena + * @size_t sz@ = size of block to allocate * * Returns: Pointer to allocated block. * @@ -67,17 +71,18 @@ * exception @EXC_NOMEM@ is thrown. */ -void *xmalloc(size_t sz) +void *x_alloc(arena *a, size_t sz) { - void *p = malloc(sz); + void *p = A_ALLOC(a, sz); if (!p) THROW(EXC_NOMEM); return (p); } -/* --- @xstrdup@ --- * +/* --- @x_strdup@ --- * * - * Arguments: @const char *s@ = pointer to a string + * Arguments: @arena *a@ = pointer to underlying arena + * @const char *s@ = pointer to a string * * Returns: Pointer to a copy of the string. * @@ -86,17 +91,18 @@ void *xmalloc(size_t sz) * thrown. */ -char *xstrdup(const char *s) +char *x_strdup(arena *a, const char *s) { size_t sz = strlen(s) + 1; - char *p = xmalloc(sz); + char *p = x_alloc(a, sz); memcpy(p, s, sz); return (p); } -/* --- @xrealloc@ --- * +/* --- @x_realloc@ --- * * - * Arguments: @void *p@ = pointer to a block of memory + * Arguments: @arena *a@ = pointer to underlying arena + * @void *p@ = pointer to a block of memory * @size_t sz@ = new size desired for the block * * Returns: Pointer to the resized memory block (which is almost @@ -106,12 +112,76 @@ char *xstrdup(const char *s) * exception @EXC_NOMEM@ is thrown. */ -void *xrealloc(void *p, size_t sz) +void *x_realloc(arena *a, void *p, size_t sz) { - p = realloc(p, sz); + p = A_REALLOC(a, p, sz); if (!p) THROW(EXC_NOMEM); return (p); } +/* --- @x_free@ --- * + * + * Arguments: @arena *a@ = pointer to underlying arena + * @void *p@ = pointer to a block of memory. + * + * Returns: --- + * + * Use: Frees a block of memory. + */ + +void (x_free)(arena *a, void *p) { x_free(a, p); } + +/*----- Old functions for the standard arena ------------------------------*/ + +/* --- @xmalloc@ --- * + * + * Arguments: @size_t sz@ = size of block to allocate + * + * Returns: Pointer to allocated block. + * + * Use: Allocates memory. If there's not enough memory, the + * exception @EXC_NOMEM@ is thrown. + */ + +void *(xmalloc)(size_t sz) { return xmalloc(sz); } + +/* --- @xstrdup@ --- * + * + * Arguments: @const char *s@ = pointer to a string + * + * Returns: Pointer to a copy of the string. + * + * Use: Copies a string (like @strdup@ would, if it existed). If + * there's not enough memory, the exception @EXC_NOMEM@ is + * thrown. + */ + +char *(xstrdup)(const char *s) { return xstrdup(s); } + +/* --- @xrealloc@ --- * + * + * Arguments: @void *p@ = pointer to a block of memory + * @size_t sz@ = new size desired for the block + * + * Returns: Pointer to the resized memory block (which is almost + * certainly not in the same place any more). + * + * Use: Resizes a memory block. If there's not enough memory, the + * exception @EXC_NOMEM@ is thrown. + */ + +void *(xrealloc)(void *p, size_t sz) { return xrealloc(p, sz); } + +/* --- @xfree@ --- * + * + * Arguments: @void *p@ = pointer to a block of memory. + * + * Returns: --- + * + * Use: Frees a block of memory. + */ + +void (xfree)(void *p) { xfree(p); } + /*----- That's all, folks -------------------------------------------------*/ diff --git a/alloc.h b/alloc.h index 49e66d7..edf555a 100644 --- a/alloc.h +++ b/alloc.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: alloc.h,v 1.4 1999/12/10 23:42:04 mdw Exp $ + * $Id: alloc.h,v 1.5 2000/06/17 10:35:51 mdw Exp $ * * Memory allocation functions * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: alloc.h,v $ + * Revision 1.5 2000/06/17 10:35:51 mdw + * Major overhaul for arena support. + * * Revision 1.4 1999/12/10 23:42:04 mdw * Change header file guard names. * @@ -51,9 +54,72 @@ extern "C" { #endif +/*----- Required header files ---------------------------------------------*/ + #include -/*----- Functions provided ------------------------------------------------*/ +#ifndef MLIB_ARENA_H +# include "arena.h" +#endif + +/*----- Functions and macros ----------------------------------------------*/ + +/* --- @x_alloc@ --- * + * + * Arguments: @arena *a@ = pointer to underlying arena + * @size_t sz@ = size of block to allocate + * + * Returns: Pointer to allocated block. + * + * Use: Allocates memory. If there's not enough memory, the + * exception @EXC_NOMEM@ is thrown. + */ + +extern void *x_alloc(arena */*a*/, size_t /*sz*/); + +/* --- @x_strdup@ --- * + * + * Arguments: @arena *a@ = pointer to underlying arena + * @const char *s@ = pointer to a string + * + * Returns: Pointer to a copy of the string. + * + * Use: Copies a string (like @strdup@ would, if it existed). If + * there's not enough memory, the exception @EXC_NOMEM@ is + * thrown. + */ + +extern char *x_strdup(arena */*a*/, const char */*s*/); + +/* --- @x_realloc@ --- * + * + * Arguments: @arena *a@ = pointer to underlying arena + * @void *p@ = pointer to a block of memory + * @size_t sz@ = new size desired for the block + * + * Returns: Pointer to the resized memory block (which is almost + * certainly not in the same place any more). + * + * Use: Resizes a memory block. If there's not enough memory, the + * exception @EXC_NOMEM@ is thrown. + */ + +extern void *x_realloc(arena */*a*/, void */*p*/, size_t /*sz*/); + +/* --- @x_free@ --- * + * + * Arguments: @arena *a@ = pointer to underlying arena + * @void *p@ = pointer to a block of memory. + * + * Returns: --- + * + * Use: Frees a block of memory. + */ + +extern void x_free(arena */*a*/, void */*p*/); +#define x_free(a, p) A_FREE(a, p) + +/*----- Old functions for the standard arena ------------------------------*/ /* --- @xmalloc@ --- * * @@ -66,6 +132,7 @@ */ extern void *xmalloc(size_t /*sz*/); +#define xmalloc(sz) x_alloc(arena_global, (sz)) /* --- @xstrdup@ --- * * @@ -79,6 +146,7 @@ extern void *xmalloc(size_t /*sz*/); */ extern char *xstrdup(const char */*s*/); +#define xstrdup(p) x_strdup(arena_global, (p)) /* --- @xrealloc@ --- * * @@ -93,6 +161,19 @@ extern char *xstrdup(const char */*s*/); */ extern void *xrealloc(void */*p*/, size_t /*sz*/); +#define xrealloc(p, sz) x_realloc(arena_global, (p), (sz)) + +/* --- @xfree@ --- * + * + * Arguments: @void *p@ = pointer to a block of memory. + * + * Returns: --- + * + * Use: Frees a block of memory. + */ + +extern void xfree(void */*p*/); +#define xfree(p) x_free(arena_global, (p)) /*----- That's all, folks -------------------------------------------------*/ diff --git a/sub.c b/sub.c index 57ee194..45dcac4 100644 --- a/sub.c +++ b/sub.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sub.c,v 1.5 1999/05/19 20:27:11 mdw Exp $ + * $Id: sub.c,v 1.6 2000/06/17 10:35:51 mdw Exp $ * * Allocation of known-size blocks * @@ -30,6 +30,9 @@ /*----- 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. * @@ -86,132 +89,174 @@ /* --- Local headers --- */ -#undef TRACK_ENABLE /* Can't track suballoc routines */ -#include "alloc.h" - -/*----- Configuration and tuning ------------------------------------------*/ +#include "arena.h" +#include "exc.h" +#include "sub.h" -/* --- The largest block I'll handle here --- * - * - * Anything larger will be handed on to @malloc@. - */ +/*----- Static variables --------------------------------------------------*/ -#define SUB_MAXBIN 256 +static size_t sizes[SUB_BINS]; -/* --- 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. - */ +/*----- Global variables --------------------------------------------------*/ -#define SUB_CHUNK 4096 +subarena sub_global; -/*----- 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 * - * This chooses the correct bin for an allocation. Input is the size of - * block wanted; result is the bin index. + * Returns: --- + * + * 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@ --- * * - * This gives the size of block contained in a given bin. + * Arguments: @subarena *s@ = pointer to arena to destroy + * + * 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 *bins[SUB_BINS]; -static size_t 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 (!bins[bin]) { + if (!s->bin[bin]) { char *p, *q; - p = xmalloc(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; } - bins[bin] = p; + s->bin[bin] = p; } /* --- Extract the first block in the list --- */ - p = bins[bin]; - 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 = bins[bin]; - 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: --- diff --git a/sub.h b/sub.h index ffb708c..1b07703 100644 --- a/sub.h +++ b/sub.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sub.h,v 1.5 1999/12/10 23:42:04 mdw Exp $ + * $Id: sub.h,v 1.6 2000/06/17 10:35:51 mdw Exp $ * * Allocation of known-size blocks * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: sub.h,v $ + * Revision 1.6 2000/06/17 10:35:51 mdw + * Major overhaul for arena support. + * * Revision 1.5 1999/12/10 23:42:04 mdw * Change header file guard names. * @@ -58,27 +61,160 @@ #include -#ifndef MLIB_ALLOC_H -# include "alloc.h" +#ifndef MLIB_ARENA_H +# include "arena.h" #endif +/*----- Configuration and tuning ------------------------------------------*/ + +/* --- The largest block I'll handle here --- * + * + * Anything larger will be handed on to the underlying @alloc@. + */ + +#define SUB_MAXBIN 256 + +/* --- 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. + */ + +#define SUB_CHUNK 4096 + +/*----- Other useful macros -----------------------------------------------*/ + +/* --- 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. + */ + +#define SUB_GRANULE sizeof(void *) + +/* --- Finding the right bin for a given size --- * + * + * This chooses the correct bin for an allocation. Input is the size of + * block wanted; result is the bin index. + */ + +#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE) + +/* --- Convert a bin back to the block size --- * + * + * This gives the size of block contained in a given bin. + */ + +#define SUB_BINSZ(x) ((x) * SUB_GRANULE) + +/* --- Number of bins required --- */ + +#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1) + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct subarena { + arena *a; + void *bin[SUB_BINS]; +} subarena; + +/*----- Global variables --------------------------------------------------*/ + +extern subarena sub_global; + /*----- Functions provided ------------------------------------------------*/ +/* --- @subarena_create@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to initialize + * @arena *a@ = pointer to underlying arena block + * + * Returns: --- + * + * Use: Initialize a suballocation arena based on an underlying large + * blocks arena. + */ + +extern void subarena_create(subarena */*s*/, arena */*a*/); + +/* --- @subarena_destroy@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to destroy + * + * Returns: --- + * + * Use: Destroys a suballocation arena, freeing all of the memory it + * contains back to the underlying large blocks arena. + */ + +extern void subarena_destroy(subarena */*s*/); + +/* --- @subarena_alloc@ --- * + * + * 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 from the given pool. The + * exception @EXC_NOMEM@ is raised if the underlying arena is + * full. + */ + +extern void *subarena_alloc(subarena */*s*/, size_t /*sz*/); + +/* --- @subarena_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 @subarena_alloc@. + */ + +extern void subarena_free(subarena */*s*/, void */*p*/, size_t /*sz*/); + +/* --- @A_CREATE@ --- * + * + * Arguments: @subarena *s@ = pointer to arena + * @type@ = type of object required; must be passable to + * @sizeof@ + * + * Returns: Pointer to a block sufficiently big to hold an object of the + * named type. + * + * Use: Allocates a block of the required type. + */ + +#define A_CREATE(a, type) subarena_alloc((a), sizeof(type)) + +/* --- @A_DESTROY@ --- * + * + * Arguments: @subarena *s@ = pointer to arena + * @void *p@ = pointer to an object + * + * Returns: --- + * + * Use: Frees the thing pointed to by @p@. + */ + +#define A_DESTROY(a, p) subarena_free((a), (p), sizeof(*p)) + +/*----- Shortcuts for the global pool -------------------------------------*/ + /* --- @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. If there is no more - * memory left, the exception @EXC_NOMEM@ is raised. + * Use: Allocates a small block of memory from the @sub_global@ pool. */ -#ifdef TRACK_ENABLE -# define sub_alloc(s) xmalloc(s) -#else -void *sub_alloc(size_t s); -#endif +extern void *sub_alloc(size_t /*sz*/); +#define sub_alloc(sz) subarena_alloc(&sub_global, (sz)) /* --- @sub_free@ --- * * @@ -90,11 +226,8 @@ void *sub_alloc(size_t s); * Use: Frees a block allocated by @sub_alloc@. */ -#ifdef TRACK_ENABLE -# define sub_free(p, s) free(p) -#else -void sub_free(void *p, size_t s); -#endif +extern void sub_free(void */*p*/, size_t /*sz*/); +#define sub_free(p, sz) subarena_free(&sub_global, (p), (sz)) /* --- @CREATE@ --- * * @@ -126,10 +259,11 @@ void sub_free(void *p, size_t s); * * Returns: --- * - * Use: Initializes the magic allocator. + * Use: Initializes the magic allocator. This is no longer + * necessary. */ -void sub_init(void); +extern void sub_init(void); /*----- That's all, folks -------------------------------------------------*/ -- [mdw]