chiark - git - mdw - mLib/blob - sub.c

   1 /* -*-c-*-
   2  *
   3  * $Id: sub.c,v 1.1 1998/06/17 23:44:42 mdw Exp $
   4  *
   5  * Allocation of known-size blocks
   6  *
   7  * (c) 1998 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of the mLib utilities library.
  13  *
  14  * mLib is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * mLib is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with mLib; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: sub.c,v $
  32  * Revision 1.1  1998/06/17 23:44:42  mdw
  33  * Initial revision
  34  *
  35  */
  36
  37 /*----- The big idea ------------------------------------------------------*
  38  *
  39  * This file provides an extra layer over @malloc@.  It provides fast
  40  * turnover for small blocks, and tries to minimise the per-block overhead.
  41  *
  42  * To do its job, @alloc@ must place an extra restriction on you: you must
  43  * know the size of a block when you free it.  Usually you'll have this
  44  * information encoded in some way either in the block or in the thing that
  45  * referenced it, so this isn't a hardship.
  46  *
  47  * It works fairly simply.  If a request for a big block (as defined by the
  48  * constants below) comes in, it gets sent on to @malloc@ unmolested.  For
  49  * small blocks, it goes straight to a `bin' -- a list containing free blocks
  50  * of exactly that size, or the nearest bigger size we can manage.  If the
  51  * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
  52  * for lots of blocks of the requested size, so it ets split up and each
  53  * individual small block is added to the bin list.  The first block in the
  54  * bin list is then removed and given to the caller.  In this way, @malloc@
  55  * only stores its information once for lots of little blocks, so we save
  56  * memory.  Because I know where the correct bin is just from the block size,
  57  * and I don't need to do any searching at all in the usual case (because the
  58  * list isn't empty) I can get a speed advantage too.
  59  *
  60  * This code is almost certainly not ANSI conformant, although I'm not
  61  * actually sure.  If some kind soul would let me know how seriously I've
  62  * violated the standard, and whether this is easily fixable, I'd be
  63  * grateful.
  64  */
  65
  66 /*----- Header files ------------------------------------------------------*/
  67
  68 /* --- ANSI headers --- */
  69
  70 #include <stdio.h>
  71 #include <stdlib.h>
  72 #include <string.h>
  73
  74 /* --- Local headers --- */
  75
  76 #undef TRACK_ENABLE                     /* Can't track suballoc routines */
  77 #include "alloc.h"
  78
  79 /*----- Configuration and tuning ------------------------------------------*/
  80
  81 /* --- The largest block I'll handle here --- *
  82  *
  83  * Anything larger will be handed on to @malloc@.
  84  */
  85
  86 #define SUB_MAXBIN 256
  87
  88 /* --- Preferred chunk size --- *
  89  *
  90  * When a bin is empty, I'll allocate a large chunk of approximately this
  91  * size and divvy it up into small bin-sized blocks.
  92  */
  93
  94 #define SUB_CHUNK 4096
  95
  96 /*----- Other useful macros -----------------------------------------------*/
  97
  98 /* --- The granularity of bin buffers --- *
  99  *
 100  * All blocks allocated by the binner are a multiple of this size.  I've
 101  * chosen @void *@ because I need to store @void *@ things in here.
 102  */
 103
 104 #define SUB_GRANULE sizeof(void *)
 105
 106 /* --- Finding the right bin for a given size --- *
 107  *
 108  * This chooses the correct bin for an allocation.  Input is the size of
 109  * block wanted; result is the bin index.
 110  */
 111
 112 #define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)
 113
 114 /* --- Convert a bin back to the block size --- *
 115  *
 116  * This gives the size of block contained in a given bin.
 117  */
 118
 119 #define SUB_BINSZ(x) ((x) * SUB_GRANULE)
 120
 121 /* --- Number of bins required --- */
 122
 123 #define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)
 124
 125 /*----- Static variables --------------------------------------------------*/
 126
 127 static void *sub__bins[SUB_BINS];
 128 static size_t sub__sizes[SUB_BINS];
 129
 130 /*----- Main code ---------------------------------------------------------*/
 131
 132 /* --- @sub_alloc@ --- *
 133  *
 134  * Arguments:   @size_t s@ = size of chunk wanted
 135  *
 136  * Returns:     Pointer to a block at least as large as the one wanted.
 137  *
 138  * Use:         Allocates a small block of memory.  If there is no more
 139  *              memory left, the exception @EXC_NOMEM@ is raised.
 140  */
 141
 142 void *sub_alloc(size_t s)
 143 {
 144   int bin = SUB_BIN(s);
 145   void *p;
 146
 147   /* --- Handle oversize blocks --- */
 148
 149   if (bin >= SUB_BINS)
 150     return (xmalloc(s));
 151
 152   /* --- If the bin is empty, find some memory --- */
 153
 154   if (!sub__bins[bin]) {
 155     char *p, *q;
 156
 157     p = xmalloc(sub__sizes[bin]);
 158     q = p + sub__sizes[bin];
 159
 160     s = SUB_BINSZ(bin);
 161
 162     q -= s;
 163     *(void **)q = 0;
 164
 165     while (q > p) {
 166       q -= s;
 167       *(void **)q = q + s;
 168     }
 169
 170     sub__bins[bin] = p;
 171   }
 172
 173   /* --- Extract the first block in the list --- */
 174
 175   p = sub__bins[bin];
 176   sub__bins[bin] = *(void **)p;
 177   return (p);
 178 }
 179
 180 /* --- @sub_free@ --- *
 181  *
 182  * Arguments:   @void *p@ = address of block to free
 183  *              @size_t s@ = size of block
 184  *
 185  * Returns:     ---
 186  *
 187  * Use:         Frees a block allocated by @sub_alloc@.
 188  */
 189
 190 void sub_free(void *p, size_t s)
 191 {
 192   int bin = SUB_BIN(s);
 193
 194   if (bin >= SUB_BINS)
 195     free(p);
 196   else {
 197     *(void **)p = sub__bins[bin];
 198     sub__bins[bin] = p;
 199   }
 200 }
 201
 202 /* --- @sub_init@ --- *
 203  *
 204  * Arguments:   ---
 205  *
 206  * Returns:     ---
 207  *
 208  * Use:         Initialises the magic allocator.
 209  */
 210
 211 void sub_init(void)
 212 {
 213   int i;
 214
 215   /* --- Initialise the sizes bins --- */
 216
 217   for (i = 1; i < SUB_BINS; i++) {
 218     sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
 219                      SUB_BINSZ(i) * SUB_BINSZ(i));
 220   }
 221 }
 222
 223 /*----- Debugging code ----------------------------------------------------*/
 224
 225 #ifdef TEST_RIG
 226
 227 #define BLOCKS 1024
 228 #define SIZE_MAX 2048
 229 #define ITERATIONS 500000
 230
 231 int main(void)
 232 {
 233   static void *block[BLOCKS];
 234   static size_t size[BLOCKS];
 235   size_t allocced = 0;
 236   int i;
 237   long count;
 238
 239   sub_init();
 240
 241   for (count = 0; count < ITERATIONS; count++) {
 242     i = rand() % BLOCKS;
 243     if (block[i]) {
 244       sub_free(block[i], size[i]);
 245       block[i] = 0;
 246       allocced -= size[i];
 247     } else {
 248       block[i] = sub_alloc(size[i] =
 249                            rand() % (SUB_MAXBIN - 128) + 128);
 250       allocced += size[i];
 251       memset(block[i], 0, size[i]);    /* trample allocated storage */
 252     }
 253   }
 254
 255   return (0);
 256 }
 257
 258 #endif
 259
 260 /*----- That's all, folks -------------------------------------------------*/