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 #include "config.h"
  60
  61 /* --- ANSI headers --- */
  62
  63 #include <assert.h>
  64
  65 /* --- External headers --- */
  66
  67 #ifdef HAVE_VALGRIND_VALGRIND_H
  68 #  include <valgrind/valgrind.h>
  69 #  include <valgrind/memcheck.h>
  70 #  define VG(x) x
  71 #else
  72 #  define VG(x)
  73 #endif
  74
  75 /* --- Local headers --- */
  76
  77 #include "arena.h"
  78 #include "exc.h"
  79 #include "sub.h"
  80
  81 /*----- Configuration tweaks ----------------------------------------------*/
  82
  83 /* #define SUBARENA_TRIVIAL */
  84
  85 #define REDZONE_SIZE (2*SUB_GRANULE)
  86
  87 /*----- Static variables --------------------------------------------------*/
  88
  89 static size_t sizes[SUB_BINS];
  90 VG( static unsigned flags; )
  91 #define SF_VALGRIND 1u
  92
  93 /*----- Global variables --------------------------------------------------*/
  94
  95 subarena sub_global;
  96
  97 #ifdef SUBARENA_TRIVIAL
  98
  99 typedef struct sub_link {
 100   struct sub_link *next;
 101   void *p;
 102   size_t sz;
 103 } sub_link;
 104
 105 #else
 106
 107 union sub_header {
 108   void *next;
 109   union align _a;
 110 };
 111
 112 #endif
 113
 114 /*----- Main code ---------------------------------------------------------*/
 115
 116 /* --- @subarena_create@ --- *
 117  *
 118  * Arguments:   @subarena *s@ = pointer to arena to initialize
 119  *              @arena *a@ = pointer to underlying arena block
 120  *
 121  * Returns:     ---
 122  *
 123  * Use:         Initialize a suballocation arena based on an underlying large
 124  *              blocks arena.
 125  */
 126
 127 void subarena_create(subarena *s, arena *a)
 128 {
 129 #ifdef SUBARENA_TRIVIAL
 130   s->bin[0] = 0;
 131 #else
 132   size_t i;
 133
 134   if (!sizes[1]) sub_init();
 135   for (i = 0; i < SUB_BINS; i++) s->bin[i] = 0;
 136   VG( VALGRIND_CREATE_MEMPOOL(s, REDZONE_SIZE, 0); )
 137 #endif
 138   s->a = a;
 139 }
 140
 141 /* --- @subarena_destroy@ --- *
 142  *
 143  * Arguments:   @subarena *s@ = pointer to arena to destroy
 144  *
 145  * Returns:     ---
 146  *
 147  * Use:         Destroys a suballocation arena, freeing all of the memory it
 148  *              contains back to the underlying large blocks arena.
 149  */
 150
 151 void subarena_destroy(subarena *s)
 152 {
 153 #ifdef SUBARENA_TRIVIAL
 154
 155   sub_link *l, *ll;
 156
 157   for (l = s->bin[0]; l; l = ll) {
 158     ll = l;
 159     a_free(s->a, l->p);
 160     a_free(s->a, l);
 161   }
 162   s->bin[0] = 0;
 163
 164 #else
 165
 166   union sub_header *p, *q;
 167
 168   for (p = s->bin[0]; p; p = q) { q = p->next; A_FREE(s->a, p); }
 169   VG( VALGRIND_DESTROY_MEMPOOL(s); )
 170
 171 #endif
 172 }
 173
 174 /* --- @subarena_alloc@ --- *
 175  *
 176  * Arguments:   @subarena *s@ = pointer to arena
 177  *              @size_t s@ = size of chunk wanted
 178  *
 179  * Returns:     Pointer to a block at least as large as the one wanted.
 180  *
 181  * Use:         Allocates a small block of memory from the given pool.  The
 182  *              exception @EXC_NOMEM@ is raised if the underlying arena is
 183  *              full.
 184  */
 185
 186 void *subarena_alloc(subarena *s, size_t sz)
 187 {
 188 #ifdef SUBARENA_TRIVIAL
 189
 190   sub_link *l;
 191   void *p;
 192
 193   if (!s->a) subarena_create(s, arena_global);
 194
 195   if ((l = a_alloc(s->a, sizeof(*l))) == 0) return (0);
 196   if ((p = a_alloc(s->a, sz)) == 0) { a_free(s->a, l); return (0); }
 197   l->p = p; l->sz = sz; l->next = s->bin[0]; s->bin[0] = l;
 198   return (p);
 199
 200 #else
 201
 202   unsigned char *p, *q;
 203   union sub_header *h;
 204   size_t bin, chsz, redsz;
 205
 206   /* --- Ensure that everything is initialized --- */
 207
 208   if (!s->a) subarena_create(s, arena_global);
 209
 210   /* --- Handle oversize blocks --- */
 211
 212   bin = SUB_BIN(sz);
 213   if (bin >= SUB_BINS) {
 214     p = A_ALLOC(s->a, sz); if (!p) THROW(EXC_NOMEM);
 215     return (p);
 216   }
 217
 218   /* --- If the bin is empty, find some memory --- */
 219
 220   if (!s->bin[bin]) {
 221     redsz = 0; VG( if (flags&SF_VALGRIND) redsz = REDZONE_SIZE; )
 222     chsz = SUB_BINSZ(bin) + redsz;
 223     h = A_ALLOC(s->a, sizes[bin]); if (!h) THROW(EXC_NOMEM);
 224     h->next = s->bin[0]; s->bin[0] = h;
 225     p = (unsigned char *)(h + 1);
 226     q = (unsigned char *)h + sizes[bin] - redsz - chsz; *(void **)q = 0;
 227     while (q > p) { q -= chsz; *(void **)q = q + chsz; }
 228     s->bin[bin] = q;
 229     VG( VALGRIND_MAKE_MEM_NOACCESS(p, sizes[bin]); )
 230   }
 231
 232   /* --- Extract the first block in the list --- */
 233
 234   p = s->bin[bin];
 235   VG( if (flags&SF_VALGRIND) {
 236         VALGRIND_MAKE_MEM_DEFINED(p, sizeof(void *));
 237         s->bin[bin] = *(void **)p;
 238         VALGRIND_MEMPOOL_ALLOC(s, p, sz);
 239       } else )
 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   ll = *l; assert(ll); assert(ll->sz == sz);
 265   *l = ll->next;
 266   a_free(s->a, ll); a_free(s->a, p); s->bin[0] = lh;
 267
 268 #else
 269
 270   size_t bin = SUB_BIN(sz);
 271
 272   if (bin >= SUB_BINS)
 273     A_FREE(s->a, p);
 274   else {
 275     *(void **)p = s->bin[bin]; s->bin[bin] = p;
 276     VG( if (flags&SF_VALGRIND) VALGRIND_MEMPOOL_FREE(s, p); )
 277   }
 278
 279 #endif
 280 }
 281
 282 /*----- Compatibility stuff -----------------------------------------------*/
 283
 284 /* --- @sub_alloc@ --- *
 285  *
 286  * Arguments:   @size_t s@ = size of chunk wanted
 287  *
 288  * Returns:     Pointer to a block at least as large as the one wanted.
 289  *
 290  * Use:         Allocates a small block of memory from the @sub_global@ pool.
 291  */
 292
 293 void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
 294
 295 /* --- @sub_free@ --- *
 296  *
 297  * Arguments:   @void *p@ = address of block to free
 298  *              @size_t s@ = size of block
 299  *
 300  * Returns:     ---
 301  *
 302  * Use:         Frees a block allocated by @sub_alloc@.
 303  */
 304
 305 void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
 306
 307 /* --- @sub_init@ --- *
 308  *
 309  * Arguments:   ---
 310  *
 311  * Returns:     ---
 312  *
 313  * Use:         Initializes the magic allocator.
 314  */
 315
 316 void sub_init(void)
 317 {
 318 #ifndef SUBARENA_TRIVIAL
 319   size_t n, sz;
 320   int i;
 321
 322   /* Find out if we're running under Valgrind --- */
 323
 324   VG( if (RUNNING_ON_VALGRIND) flags |= SF_VALGRIND; )
 325
 326   /* --- Initialize the sizes bins --- */
 327
 328   for (i = 1; i < SUB_BINS; i++) {
 329     sz = SUB_BINSZ(i);
 330     n = (SUB_CHUNK + sz - 1)/sz;
 331     sz = sizeof(union sub_header) + n*sz;
 332     VG( if (flags&SF_VALGRIND) sz += (n + 1)*REDZONE_SIZE; )
 333     sizes[i] = sz;
 334   }
 335 #endif
 336 }
 337
 338 /*----- Debugging code ----------------------------------------------------*/
 339
 340 #ifdef TEST_RIG
 341
 342 #define BLOCKS 1024
 343 #define SIZE_MAX 2048
 344 #define ITERATIONS 500000
 345
 346 int main(void)
 347 {
 348   static void *block[BLOCKS];
 349   static size_t size[BLOCKS];
 350   size_t allocced = 0;
 351   int i;
 352   long count;
 353
 354   sub_init();
 355
 356   for (count = 0; count < ITERATIONS; count++) {
 357     i = rand() % BLOCKS;
 358     if (block[i]) {
 359       sub_free(block[i], size[i]);
 360       block[i] = 0;
 361       allocced -= size[i];
 362     } else {
 363       block[i] = sub_alloc(size[i] =
 364                            rand() % (SUB_MAXBIN - 128) + 128);
 365       allocced += size[i];
 366       memset(block[i], 0, size[i]);    /* trample allocated storage */
 367     }
 368   }
 369
 370   return (0);
 371 }
 372
 373 #endif
 374
 375 /*----- That's all, folks -------------------------------------------------*/