[mLib] / mem / sub.c

/* -*-c-*-
 *
 * 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 ------------------------------------------------------*/

#include "config.h"

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

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

/* --- External headers --- */

#ifdef HAVE_VALGRIND_VALGRIND_H
#  include <valgrind/valgrind.h>
#  include <valgrind/memcheck.h>
#  define VG(x) x
#else
#  define VG(x)
#endif

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

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

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

/* #define SUBARENA_TRIVIAL */

#define REDZONE_SIZE (2*SUB_GRANULE)

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

static size_t sizes[SUB_BINS];
VG( static unsigned flags; )
#define SF_VALGRIND 1u

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

subarena sub_global;

#ifdef SUBARENA_TRIVIAL

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

#else

union sub_header {
  void *next;
  union align _a;
};

#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;
  VG( VALGRIND_CREATE_MEMPOOL(s, REDZONE_SIZE, 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

  union sub_header *p, *q;

  for (p = s->bin[0]; p; p = q) { q = p->next; A_FREE(s->a, p); }
  VG( VALGRIND_DESTROY_MEMPOOL(s); )

#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

  unsigned char *p, *q;
  union sub_header *h;
  size_t bin, chsz, redsz;

  /* --- Ensure that everything is initialized --- */

  if (!s->a) subarena_create(s, arena_global);

  /* --- Handle oversize blocks --- */

  bin = SUB_BIN(sz);
  if (bin >= SUB_BINS) {
    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]) {
    redsz = 0; VG( if (flags&SF_VALGRIND) redsz = REDZONE_SIZE; )
    chsz = SUB_BINSZ(bin) + redsz;
    h = A_ALLOC(s->a, sizes[bin]); if (!h) THROW(EXC_NOMEM);
    h->next = s->bin[0]; s->bin[0] = h;
    p = (unsigned char *)(h + 1);
    q = (unsigned char *)h + sizes[bin] - redsz - chsz; *(void **)q = 0;
    while (q > p) { q -= chsz; *(void **)q = q + chsz; }
    s->bin[bin] = q;
    VG( VALGRIND_MAKE_MEM_NOACCESS(p, sizes[bin]); )
  }

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

  p = s->bin[bin];
  VG( if (flags&SF_VALGRIND) {
        VALGRIND_MAKE_MEM_DEFINED(p, sizeof(void *));
        s->bin[bin] = *(void **)p;
        VALGRIND_MEMPOOL_ALLOC(s, p, sz);
      } else )
  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

  size_t bin = SUB_BIN(sz);

  if (bin >= SUB_BINS)
    A_FREE(s->a, p);
  else {
    *(void **)p = s->bin[bin]; s->bin[bin] = p;
    VG( if (flags&SF_VALGRIND) VALGRIND_MEMPOOL_FREE(s, 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
  size_t n, sz;
  int i;

  /* Find out if we're running under Valgrind --- */

  VG( if (RUNNING_ON_VALGRIND) flags |= SF_VALGRIND; )

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

  for (i = 1; i < SUB_BINS; i++) {
    sz = SUB_BINSZ(i);
    n = (SUB_CHUNK + sz - 1)/sz;
    sz = sizeof(union sub_header) + n*sz;
    VG( if (flags&SF_VALGRIND) sz += (n + 1)*REDZONE_SIZE; )
    sizes[i] = sz;
  }
#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 -------------------------------------------------*/