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

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