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

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