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

   1 /* -*-c-*-
   2  *
   3  * $Id: sub.c,v 1.9 2004/04/08 01:36:13 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 /*----- The big idea ------------------------------------------------------*
  31  *
  32  * This file provides an extra layer over @malloc@.  It provides fast
  33  * turnover for small blocks, and tries to minimize the per-block overhead.
  34  *
  35  * To do its job, @alloc@ must place an extra restriction on you: you must
  36  * know the size of a block when you free it.  Usually you'll have this
  37  * information encoded in some way either in the block or in the thing that
  38  * referenced it, so this isn't a hardship.
  39  *
  40  * It works fairly simply.  If a request for a big block (as defined by the
  41  * constants below) comes in, it gets sent on to @malloc@ unmolested.  For
  42  * small blocks, it goes straight to a `bin' -- a list containing free blocks
  43  * of exactly that size, or the nearest bigger size we can manage.  If the
  44  * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
  45  * for lots of blocks of the requested size, so it ets split up and each
  46  * individual small block is added to the bin list.  The first block in the
  47  * bin list is then removed and given to the caller.  In this way, @malloc@
  48  * only stores its information once for lots of little blocks, so we save
  49  * memory.  Because I know where the correct bin is just from the block size,
  50  * and I don't need to do any searching at all in the usual case (because the
  51  * list isn't empty) I can get a speed advantage too.
  52  *
  53  * This code is almost certainly not ANSI conformant, although I'm not
  54  * actually sure.  If some kind soul would let me know how seriously I've
  55  * violated the standard, and whether this is easily fixable, I'd be
  56  * grateful.
  57  */
  58
  59 /*----- Header files ------------------------------------------------------*/
  60
  61 /* --- ANSI headers --- */
  62
  63 #include <assert.h>
  64 #include <stdio.h>
  65 #include <stdlib.h>
  66 #include <string.h>
  67
  68 /* --- Local headers --- */
  69
  70 #include "arena.h"
  71 #include "exc.h"
  72 #include "sub.h"
  73
  74 /*----- Configuration tweaks ----------------------------------------------*/
  75
  76 /* #define SUBARENA_TRIVIAL */
  77
  78 /*----- Static variables --------------------------------------------------*/
  79
  80 static size_t sizes[SUB_BINS];
  81
  82 /*----- Global variables --------------------------------------------------*/
  83
  84 subarena sub_global;
  85
  86 #ifdef SUBARENA_TRIVIAL
  87
  88 typedef struct sub_link {
  89   struct sub_link *next;
  90   void *p;
  91   size_t sz;
  92 } sub_link;
  93
  94 #endif
  95
  96 /*----- Main code ---------------------------------------------------------*/
  97
  98 /* --- @subarena_create@ --- *
  99  *
 100  * Arguments:   @subarena *s@ = pointer to arena to initialize
 101  *              @arena *a@ = pointer to underlying arena block
 102  *
 103  * Returns:     ---
 104  *
 105  * Use:         Initialize a suballocation arena based on an underlying large
 106  *              blocks arena.
 107  */
 108
 109 void subarena_create(subarena *s, arena *a)
 110 {
 111 #ifdef SUBARENA_TRIVIAL
 112   s->bin[0] = 0;
 113 #else
 114   size_t i;
 115   if (!sizes[1])
 116     sub_init();
 117   for (i = 0; i < SUB_BINS; i++)
 118     s->bin[i] = 0;
 119 #endif
 120   s->a = a;
 121 }
 122
 123 /* --- @subarena_destroy@ --- *
 124  *
 125  * Arguments:   @subarena *s@ = pointer to arena to destroy
 126  *
 127  * Returns:     ---
 128  *
 129  * Use:         Destroys a suballocation arena, freeing all of the memory it
 130  *              contains back to the underlying large blocks arena.
 131  */
 132
 133 void subarena_destroy(subarena *s)
 134 {
 135 #ifdef SUBARENA_TRIVIAL
 136
 137   sub_link *l, *ll;
 138
 139   for (l = s->bin[0]; l; l = ll) {
 140     ll = l;
 141     a_free(s->a, l->p);
 142     a_free(s->a, l);
 143   }
 144   s->bin[0] = 0;
 145
 146 #else
 147
 148   size_t i;
 149   for (i = 0; i < SUB_BINS; i++) {
 150     void *p = s->bin[i];
 151     while (p) {
 152       void *q = p;
 153       p = *(void **)q;
 154       A_FREE(s->a, q);
 155     }
 156     s->bin[i] = 0;
 157   }
 158
 159 #endif
 160 }
 161
 162 /* --- @subarena_alloc@ --- *
 163  *
 164  * Arguments:   @subarena *s@ = pointer to arena
 165  *              @size_t s@ = size of chunk wanted
 166  *
 167  * Returns:     Pointer to a block at least as large as the one wanted.
 168  *
 169  * Use:         Allocates a small block of memory from the given pool.  The
 170  *              exception @EXC_NOMEM@ is raised if the underlying arena is
 171  *              full.
 172  */
 173
 174 void *subarena_alloc(subarena *s, size_t sz)
 175 {
 176 #ifdef SUBARENA_TRIVIAL
 177
 178   sub_link *l;
 179   void *p;
 180
 181   if (!s->a)
 182     subarena_create(s, arena_global);
 183
 184   if ((l = a_alloc(s->a, sizeof(*l))) == 0)
 185     return (0);
 186   if ((p = a_alloc(s->a, sz)) == 0) {
 187     a_free(s->a, l);
 188     return (0);
 189   }
 190   l->p = p;
 191   l->sz = sz;
 192   l->next = s->bin[0];
 193   s->bin[0] = l;
 194   return (p);
 195
 196 #else
 197
 198   int bin;
 199   void *p;
 200
 201   /* --- Ensure that everything is initialized --- */
 202
 203   if (!s->a)
 204     subarena_create(s, arena_global);
 205
 206   /* --- Handle oversize blocks --- */
 207
 208   bin = SUB_BIN(sz);
 209   if (bin >= SUB_BINS) {
 210     void *p = A_ALLOC(s->a, sz);
 211     if (!p)
 212       THROW(EXC_NOMEM);
 213     return (p);
 214   }
 215
 216   /* --- If the bin is empty, find some memory --- */
 217
 218   if (!s->bin[bin]) {
 219     char *p, *q;
 220
 221     p = A_ALLOC(s->a, sizes[bin]);
 222     if (!p)
 223       THROW(EXC_NOMEM);
 224     q = p + sizes[bin];
 225
 226     sz = SUB_BINSZ(bin);
 227
 228     q -= sz;
 229     *(void **)q = 0;
 230
 231     while (q > p) {
 232       q -= sz;
 233       *(void **)q = q + sz;
 234     }
 235
 236     s->bin[bin] = p;
 237   }
 238
 239   /* --- Extract the first block in the list --- */
 240
 241   p = s->bin[bin];
 242   s->bin[bin] = *(void **)p;
 243   return (p);
 244
 245 #endif
 246 }
 247
 248 /* --- @subarena_free@ --- *
 249  *
 250  * Arguments:   @subarena *s@ = pointer to arena
 251  *              @void *p@ = address of block to free
 252  *              @size_t s@ = size of block
 253  *
 254  * Returns:     ---
 255  *
 256  * Use:         Frees a block allocated by @subarena_alloc@.
 257  */
 258
 259 void subarena_free(subarena *s, void *p, size_t sz)
 260 {
 261 #ifdef SUBARENA_TRIVIAL
 262
 263   sub_link *lh = s->bin[0], **l, *ll;
 264
 265   for (l = &lh; *l && (*l)->p != p; l = &(*l)->next)
 266     ;
 267   ll = *l;
 268   assert(ll);
 269   assert(ll->sz == sz);
 270   *l = ll->next;
 271   a_free(s->a, ll);
 272   a_free(s->a, p);
 273   s->bin[0] = lh;
 274
 275 #else
 276
 277   int bin = SUB_BIN(sz);
 278
 279   if (bin >= SUB_BINS)
 280     A_FREE(s->a, p);
 281   else {
 282     *(void **)p = s->bin[bin];
 283     s->bin[bin] = p;
 284   }
 285
 286 #endif
 287 }
 288
 289 /*----- Compatibility stuff -----------------------------------------------*/
 290
 291 /* --- @sub_alloc@ --- *
 292  *
 293  * Arguments:   @size_t s@ = size of chunk wanted
 294  *
 295  * Returns:     Pointer to a block at least as large as the one wanted.
 296  *
 297  * Use:         Allocates a small block of memory from the @sub_global@ pool.
 298  */
 299
 300 void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
 301
 302 /* --- @sub_free@ --- *
 303  *
 304  * Arguments:   @void *p@ = address of block to free
 305  *              @size_t s@ = size of block
 306  *
 307  * Returns:     ---
 308  *
 309  * Use:         Frees a block allocated by @sub_alloc@.
 310  */
 311
 312 void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
 313
 314 /* --- @sub_init@ --- *
 315  *
 316  * Arguments:   ---
 317  *
 318  * Returns:     ---
 319  *
 320  * Use:         Initializes the magic allocator.
 321  */
 322
 323 void sub_init(void)
 324 {
 325 #ifndef SUBARENA_TRIVIAL
 326   int i;
 327
 328   /* --- Initialize the sizes bins --- */
 329
 330   for (i = 1; i < SUB_BINS; i++) {
 331     sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
 332                      SUB_BINSZ(i) * SUB_BINSZ(i));
 333   }
 334 #endif
 335 }
 336
 337 /*----- Debugging code ----------------------------------------------------*/
 338
 339 #ifdef TEST_RIG
 340
 341 #define BLOCKS 1024
 342 #define SIZE_MAX 2048
 343 #define ITERATIONS 500000
 344
 345 int main(void)
 346 {
 347   static void *block[BLOCKS];
 348   static size_t size[BLOCKS];
 349   size_t allocced = 0;
 350   int i;
 351   long count;
 352
 353   sub_init();
 354
 355   for (count = 0; count < ITERATIONS; count++) {
 356     i = rand() % BLOCKS;
 357     if (block[i]) {
 358       sub_free(block[i], size[i]);
 359       block[i] = 0;
 360       allocced -= size[i];
 361     } else {
 362       block[i] = sub_alloc(size[i] =
 363                            rand() % (SUB_MAXBIN - 128) + 128);
 364       allocced += size[i];
 365       memset(block[i], 0, size[i]);    /* trample allocated storage */
 366     }
 367   }
 368
 369   return (0);
 370 }
 371
 372 #endif
 373
 374 /*----- That's all, folks -------------------------------------------------*/