lib/mempool.c

   1 /*
   2  *      BIRD Resource Manager -- Memory Pools
   3  *
   4  *      (c) 1998--2000 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 /**
  10  * DOC: Linear memory pools
  11  *
  12  * Linear memory pools are collections of memory blocks which
  13  * support very fast allocation of new blocks, but are able to free only
  14  * the whole collection at once.
  15  *
  16  * Example: Each configuration is described by a complex system of structures,
  17  * linked lists and function trees which are all allocated from a single linear
  18  * pool, thus they can be freed at once when the configuration is no longer used.
  19  */
  20
  21 #include <stdlib.h>
  22
  23 #include "nest/bird.h"
  24 #include "lib/resource.h"
  25 #include "lib/string.h"
  26
  27 struct lp_chunk {
  28   struct lp_chunk *next;
  29   unsigned int size;
  30   byte data[0];
  31 };
  32
  33 struct linpool {
  34   resource r;
  35   byte *ptr, *end;
  36   struct lp_chunk *first, *current, **plast;    /* Normal (reusable) chunks */
  37   struct lp_chunk *first_large;                 /* Large chunks */
  38   unsigned chunk_size, threshold, total, total_large;
  39 };
  40
  41 static void lp_free(resource *);
  42 static void lp_dump(resource *);
  43 static resource *lp_lookup(resource *, unsigned long);
  44
  45 static struct resclass lp_class = {
  46   "LinPool",
  47   sizeof(struct linpool),
  48   lp_free,
  49   lp_dump,
  50   lp_lookup
  51 };
  52
  53 /**
  54  * lp_new - create a new linear memory pool
  55  * @p: pool
  56  * @blk: block size
  57  *
  58  * lp_new() creates a new linear memory pool resource inside the pool @p.
  59  * The linear pool consists of a list of memory chunks of size at least
  60  * @blk.
  61  */
  62 linpool
  63 *lp_new(pool *p, unsigned blk)
  64 {
  65   linpool *m = ralloc(p, &lp_class);
  66   m->ptr = m->end = NULL;
  67   m->first = m->current = NULL;
  68   m->plast = &m->first;
  69   m->first_large = NULL;
  70   m->chunk_size = blk;
  71   m->threshold = 3*blk/4;
  72   m->total = m->total_large = 0;
  73   return m;
  74 }
  75
  76 /**
  77  * lp_alloc - allocate memory from a &linpool
  78  * @m: linear memory pool
  79  * @size: amount of memory
  80  *
  81  * lp_alloc() allocates @size bytes of memory from a &linpool @m
  82  * and it returns a pointer to the allocated memory.
  83  *
  84  * It works by trying to find free space in the last memory chunk
  85  * associated with the &linpool and creating a new chunk of the standard
  86  * size (as specified during lp_new()) if the free space is too small
  87  * to satisfy the allocation. If @size is too large to fit in a standard
  88  * size chunk, an "overflow" chunk is created for it instead.
  89  */
  90 void *
  91 lp_alloc(linpool *m, unsigned size)
  92 {
  93   byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
  94   byte *e = a + size;
  95
  96   if (e <= m->end)
  97     {
  98       m->ptr = e;
  99       return a;
 100     }
 101   else
 102     {
 103       struct lp_chunk *c;
 104       if (size >= m->threshold)
 105         {
 106           /* Too large => allocate large chunk */
 107           c = xmalloc(sizeof(struct lp_chunk) + size);
 108           m->total_large += size;
 109           c->next = m->first_large;
 110           m->first_large = c;
 111           c->size = size;
 112         }
 113       else
 114         {
 115           if (m->current)
 116             {
 117               /* Still have free chunks from previous incarnation (before lp_flush()) */
 118               c = m->current;
 119               m->current = c->next;
 120             }
 121           else
 122             {
 123               /* Need to allocate a new chunk */
 124               c = xmalloc(sizeof(struct lp_chunk) + m->chunk_size);
 125               m->total += m->chunk_size;
 126               *m->plast = c;
 127               m->plast = &c->next;
 128               c->next = NULL;
 129               c->size = m->chunk_size;
 130             }
 131           m->ptr = c->data + size;
 132           m->end = c->data + m->chunk_size;
 133         }
 134       return c->data;
 135     }
 136 }
 137
 138 /**
 139  * lp_allocu - allocate unaligned memory from a &linpool
 140  * @m: linear memory pool
 141  * @size: amount of memory
 142  *
 143  * lp_allocu() allocates @size bytes of memory from a &linpool @m
 144  * and it returns a pointer to the allocated memory. It doesn't
 145  * attempt to align the memory block, giving a very efficient way
 146  * how to allocate strings without any space overhead.
 147  */
 148 void *
 149 lp_allocu(linpool *m, unsigned size)
 150 {
 151   byte *a = m->ptr;
 152   byte *e = a + size;
 153
 154   if (e <= m->end)
 155     {
 156       m->ptr = e;
 157       return a;
 158     }
 159   return lp_alloc(m, size);
 160 }
 161
 162 /**
 163  * lp_allocz - allocate cleared memory from a &linpool
 164  * @m: linear memory pool
 165  * @size: amount of memory
 166  *
 167  * This function is identical to lp_alloc() except that it
 168  * clears the allocated memory block.
 169  */
 170 void *
 171 lp_allocz(linpool *m, unsigned size)
 172 {
 173   void *z = lp_alloc(m, size);
 174
 175   bzero(z, size);
 176   return z;
 177 }
 178
 179 /**
 180  * lp_flush - flush a linear memory pool
 181  * @m: linear memory pool
 182  *
 183  * This function frees the whole contents of the given &linpool @m,
 184  * but leaves the pool itself.
 185  */
 186 void
 187 lp_flush(linpool *m)
 188 {
 189   struct lp_chunk *c;
 190
 191   /* Relink all normal chunks to free list and free all large chunks */
 192   m->ptr = m->end = NULL;
 193   m->current = m->first;
 194   while (c = m->first_large)
 195     {
 196       m->first_large = c->next;
 197       xfree(c);
 198     }
 199   m->total_large = 0;
 200 }
 201
 202 static void
 203 lp_free(resource *r)
 204 {
 205   linpool *m = (linpool *) r;
 206   struct lp_chunk *c, *d;
 207
 208   for(d=m->first; d; d = c)
 209     {
 210       c = d->next;
 211       xfree(d);
 212     }
 213   for(d=m->first_large; d; d = c)
 214     {
 215       c = d->next;
 216       xfree(d);
 217     }
 218 }
 219
 220 static void
 221 lp_dump(resource *r)
 222 {
 223   linpool *m = (linpool *) r;
 224   struct lp_chunk *c;
 225   int cnt, cntl;
 226
 227   for(cnt=0, c=m->first; c; c=c->next, cnt++)
 228     ;
 229   for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
 230     ;
 231   debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
 232         m->chunk_size,
 233         m->threshold,
 234         cnt,
 235         cntl,
 236         m->total,
 237         m->total_large);
 238 }
 239
 240 static resource *
 241 lp_lookup(resource *r, unsigned long a)
 242 {
 243   linpool *m = (linpool *) r;
 244   struct lp_chunk *c;
 245
 246   for(c=m->first; c; c=c->next)
 247     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 248       return r;
 249   for(c=m->first_large; c; c=c->next)
 250     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 251       return r;
 252   return NULL;
 253 }