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

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