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

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