/* -*-c-*-
*
- * $Id: sub.c,v 1.3 1999/05/06 19:51:35 mdw Exp $
+ * $Id: sub.c,v 1.8 2003/10/12 14:44:46 mdw Exp $
*
* Allocation of known-size blocks
*
/*----- Revision history --------------------------------------------------*
*
* $Log: sub.c,v $
+ * Revision 1.8 2003/10/12 14:44:46 mdw
+ * Various fixes.
+ *
+ * Revision 1.7 2003/05/18 15:10:20 mdw
+ * Add debugging mode which just uses the underlying arena.
+ *
+ * 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.
*
/*----- 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
/* --- ANSI headers --- */
+#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* --- 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
+
+typedef struct sub_link {
+ struct sub_link *next;
+ void *p;
+ size_t sz;
+} sub_link;
+
+#endif
-#define SUB_GRANULE sizeof(void *)
+/*----- Main code ---------------------------------------------------------*/
-/* --- Finding the right bin for a given size --- *
+/* --- @subarena_create@ --- *
+ *
+ * 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)
+{
+#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
*
- * 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)
+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.
*
- * 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
+ * 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);
+#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: ---
*
* 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 ----------------------------------------------------*/
~mdw / mLib / blobdiff