Refugees from Catacomb: low-level buffer primitives.

[mLib] / sub.c

/* -*-c-*-
 *
 * $Id: sub.c,v 1.9 2004/04/08 01:36:13 mdw Exp $
 *
 * Allocation of known-size blocks
 *
 * (c) 1998 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * 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 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 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 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
 * information encoded in some way either in the block or in the thing that
 * referenced it, so this isn't a hardship.
 *
 * It works fairly simply.  If a request for a big block (as defined by the
 * constants below) comes in, it gets sent on to @malloc@ unmolested.  For
 * small blocks, it goes straight to a `bin' -- a list containing free blocks
 * of exactly that size, or the nearest bigger size we can manage.  If the
 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
 * for lots of blocks of the requested size, so it ets split up and each
 * individual small block is added to the bin list.  The first block in the
 * bin list is then removed and given to the caller.  In this way, @malloc@
 * only stores its information once for lots of little blocks, so we save
 * memory.  Because I know where the correct bin is just from the block size,
 * and I don't need to do any searching at all in the usual case (because the
 * list isn't empty) I can get a speed advantage too.
 *
 * This code is almost certainly not ANSI conformant, although I'm not
 * actually sure.  If some kind soul would let me know how seriously I've
 * violated the standard, and whether this is easily fixable, I'd be
 * grateful.
 */

/*----- Header files ------------------------------------------------------*/

/* --- ANSI headers --- */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* --- Local headers --- */

#include "arena.h"
#include "exc.h"
#include "sub.h"

/*----- Configuration tweaks ----------------------------------------------*/

/* #define SUBARENA_TRIVIAL */

/*----- Static variables --------------------------------------------------*/

static size_t sizes[SUB_BINS];

/*----- Global variables --------------------------------------------------*/

subarena sub_global;

#ifdef SUBARENA_TRIVIAL

typedef struct sub_link {
  struct sub_link *next;
  void *p;
  size_t sz;
} sub_link;

#endif

/*----- Main code ---------------------------------------------------------*/

/* --- @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.
 */

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;
}

/* --- @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.
 */

void subarena_destroy(subarena *s)
{
#ifdef SUBARENA_TRIVIAL

  sub_link *l, *ll;

  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;

#else

  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;
  }

#endif
}

/* --- @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.
 */

void *subarena_alloc(subarena *s, size_t sz)
{
#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 --- */

  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 (!s->bin[bin]) {
    char *p, *q;

    p = A_ALLOC(s->a, sizes[bin]);
    if (!p)
      THROW(EXC_NOMEM);
    q = p + sizes[bin];

    sz = SUB_BINSZ(bin);

    q -= sz;
    *(void **)q = 0;

    while (q > p) {
      q -= sz;
      *(void **)q = q + sz;
    }

    s->bin[bin] = p;
  }

  /* --- Extract the first block in the list --- */

  p = s->bin[bin];
  s->bin[bin] = *(void **)p;
  return (p);

#endif
}

/* --- @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@.
 */

void subarena_free(subarena *s, void *p, size_t sz)
{
#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)
    A_FREE(s->a, p);
  else {
    *(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:         Initializes the magic allocator.
 */

void sub_init(void)
{
#ifndef SUBARENA_TRIVIAL
  int i;

  /* --- Initialize the sizes bins --- */

  for (i = 1; i < SUB_BINS; i++) {
    sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
		     SUB_BINSZ(i) * SUB_BINSZ(i));
  }
#endif
}

/*----- Debugging code ----------------------------------------------------*/

#ifdef TEST_RIG

#define BLOCKS 1024
#define SIZE_MAX 2048
#define ITERATIONS 500000

int main(void)
{
  static void *block[BLOCKS];
  static size_t size[BLOCKS];
  size_t allocced = 0;
  int i;
  long count;

  sub_init();

  for (count = 0; count < ITERATIONS; count++) {
    i = rand() % BLOCKS;
    if (block[i]) {
      sub_free(block[i], size[i]);
      block[i] = 0;
      allocced -= size[i];
    } else {
      block[i] = sub_alloc(size[i] =
			   rand() % (SUB_MAXBIN - 128) + 128);
      allocced += size[i];
      memset(block[i], 0, size[i]);    /* trample allocated storage */
    }
  }

  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/