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

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