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 (or in stack order).
  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 #include <stdint.h>
  23
  24 #include "nest/bird.h"
  25 #include "lib/resource.h"
  26 #include "lib/string.h"
  27
  28 struct lp_chunk {
  29   struct lp_chunk *next;
  30   uint size;
  31   uintptr_t data_align[0];
  32   byte data[0];
  33 };
  34
  35 const int lp_chunk_size = sizeof(struct lp_chunk);
  36
  37 struct linpool {
  38   resource r;
  39   byte *ptr, *end;
  40   struct lp_chunk *first, *current;             /* Normal (reusable) chunks */
  41   struct lp_chunk *first_large;                 /* Large chunks */
  42   uint chunk_size, threshold, total, total_large;
  43 };
  44
  45 static void lp_free(resource *);
  46 static void lp_dump(resource *);
  47 static resource *lp_lookup(resource *, unsigned long);
  48 static size_t lp_memsize(resource *r);
  49
  50 static struct resclass lp_class = {
  51   "LinPool",
  52   sizeof(struct linpool),
  53   lp_free,
  54   lp_dump,
  55   lp_lookup,
  56   lp_memsize
  57 };
  58
  59 /**
  60  * lp_new - create a new linear memory pool
  61  * @p: pool
  62  * @blk: block size
  63  *
  64  * lp_new() creates a new linear memory pool resource inside the pool @p.
  65  * The linear pool consists of a list of memory chunks of size at least
  66  * @blk.
  67  */
  68 linpool
  69 *lp_new(pool *p, uint blk)
  70 {
  71   linpool *m = ralloc(p, &lp_class);
  72   m->chunk_size = blk;
  73   m->threshold = 3*blk/4;
  74   return m;
  75 }
  76
  77 /**
  78  * lp_alloc - allocate memory from a &linpool
  79  * @m: linear memory pool
  80  * @size: amount of memory
  81  *
  82  * lp_alloc() allocates @size bytes of memory from a &linpool @m
  83  * and it returns a pointer to the allocated memory.
  84  *
  85  * It works by trying to find free space in the last memory chunk
  86  * associated with the &linpool and creating a new chunk of the standard
  87  * size (as specified during lp_new()) if the free space is too small
  88  * to satisfy the allocation. If @size is too large to fit in a standard
  89  * size chunk, an "overflow" chunk is created for it instead.
  90  */
  91 void *
  92 lp_alloc(linpool *m, uint size)
  93 {
  94   byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
  95   byte *e = a + size;
  96
  97   if (e <= m->end)
  98     {
  99       m->ptr = e;
 100       return a;
 101     }
 102   else
 103     {
 104       struct lp_chunk *c;
 105       if (size >= m->threshold)
 106         {
 107           /* Too large => allocate large chunk */
 108           c = xmalloc(sizeof(struct lp_chunk) + size);
 109           m->total_large += size;
 110           c->next = m->first_large;
 111           m->first_large = c;
 112           c->size = size;
 113         }
 114       else
 115         {
 116           if (m->current && m->current->next)
 117             {
 118               /* Still have free chunks from previous incarnation (before lp_flush()) */
 119               c = m->current->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               c->next = NULL;
 127               c->size = m->chunk_size;
 128
 129               if (m->current)
 130                 m->current->next = c;
 131               else
 132                 m->first = c;
 133             }
 134           m->current = c;
 135           m->ptr = c->data + size;
 136           m->end = c->data + m->chunk_size;
 137         }
 138       return c->data;
 139     }
 140 }
 141
 142 /**
 143  * lp_allocu - allocate unaligned memory from a &linpool
 144  * @m: linear memory pool
 145  * @size: amount of memory
 146  *
 147  * lp_allocu() allocates @size bytes of memory from a &linpool @m
 148  * and it returns a pointer to the allocated memory. It doesn't
 149  * attempt to align the memory block, giving a very efficient way
 150  * how to allocate strings without any space overhead.
 151  */
 152 void *
 153 lp_allocu(linpool *m, uint size)
 154 {
 155   byte *a = m->ptr;
 156   byte *e = a + size;
 157
 158   if (e <= m->end)
 159     {
 160       m->ptr = e;
 161       return a;
 162     }
 163   return lp_alloc(m, size);
 164 }
 165
 166 /**
 167  * lp_allocz - allocate cleared memory from a &linpool
 168  * @m: linear memory pool
 169  * @size: amount of memory
 170  *
 171  * This function is identical to lp_alloc() except that it
 172  * clears the allocated memory block.
 173  */
 174 void *
 175 lp_allocz(linpool *m, uint size)
 176 {
 177   void *z = lp_alloc(m, size);
 178
 179   bzero(z, size);
 180   return z;
 181 }
 182
 183 /**
 184  * lp_flush - flush a linear memory pool
 185  * @m: linear memory pool
 186  *
 187  * This function frees the whole contents of the given &linpool @m,
 188  * but leaves the pool itself.
 189  */
 190 void
 191 lp_flush(linpool *m)
 192 {
 193   struct lp_chunk *c;
 194
 195   /* Move ptr to the first chunk and free all large chunks */
 196   m->current = c = m->first;
 197   m->ptr = c ? c->data : NULL;
 198   m->end = c ? c->data + m->chunk_size : NULL;
 199
 200   while (c = m->first_large)
 201     {
 202       m->first_large = c->next;
 203       xfree(c);
 204     }
 205   m->total_large = 0;
 206 }
 207
 208 /**
 209  * lp_save - save the state of a linear memory pool
 210  * @m: linear memory pool
 211  * @p: state buffer
 212  *
 213  * This function saves the state of a linear memory pool. Saved state can be
 214  * used later to restore the pool (to free memory allocated since).
 215  */
 216 void
 217 lp_save(linpool *m, lp_state *p)
 218 {
 219   p->current = m->current;
 220   p->large = m->first_large;
 221   p->ptr = m->ptr;
 222 }
 223
 224 /**
 225  * lp_restore - restore the state of a linear memory pool
 226  * @m: linear memory pool
 227  * @p: saved state
 228  *
 229  * This function restores the state of a linear memory pool, freeing all memory
 230  * allocated since the state was saved. Note that the function cannot un-free
 231  * the memory, therefore the function also invalidates other states that were
 232  * saved between (on the same pool).
 233  */
 234 void
 235 lp_restore(linpool *m, lp_state *p)
 236 {
 237   struct lp_chunk *c;
 238
 239   /* Move ptr to the saved pos and free all newer large chunks */
 240   m->current = c = p->current;
 241   m->ptr = p->ptr;
 242   m->end = c ? c->data + m->chunk_size : NULL;
 243
 244   while ((c = m->first_large) && (c != p->large))
 245     {
 246       m->first_large = c->next;
 247       m->total_large -= c->size;
 248       xfree(c);
 249     }
 250 }
 251
 252 static void
 253 lp_free(resource *r)
 254 {
 255   linpool *m = (linpool *) r;
 256   struct lp_chunk *c, *d;
 257
 258   for(d=m->first; d; d = c)
 259     {
 260       c = d->next;
 261       xfree(d);
 262     }
 263   for(d=m->first_large; d; d = c)
 264     {
 265       c = d->next;
 266       xfree(d);
 267     }
 268 }
 269
 270 static void
 271 lp_dump(resource *r)
 272 {
 273   linpool *m = (linpool *) r;
 274   struct lp_chunk *c;
 275   int cnt, cntl;
 276
 277   for(cnt=0, c=m->first; c; c=c->next, cnt++)
 278     ;
 279   for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
 280     ;
 281   debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
 282         m->chunk_size,
 283         m->threshold,
 284         cnt,
 285         cntl,
 286         m->total,
 287         m->total_large);
 288 }
 289
 290 static size_t
 291 lp_memsize(resource *r)
 292 {
 293   linpool *m = (linpool *) r;
 294   struct lp_chunk *c;
 295   int cnt = 0;
 296
 297   for(c=m->first; c; c=c->next)
 298     cnt++;
 299   for(c=m->first_large; c; c=c->next)
 300     cnt++;
 301
 302   return ALLOC_OVERHEAD + sizeof(struct linpool) +
 303     cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
 304     m->total + m->total_large;
 305 }
 306
 307
 308 static resource *
 309 lp_lookup(resource *r, unsigned long a)
 310 {
 311   linpool *m = (linpool *) r;
 312   struct lp_chunk *c;
 313
 314   for(c=m->first; c; c=c->next)
 315     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 316       return r;
 317   for(c=m->first_large; c; c=c->next)
 318     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 319       return r;
 320   return NULL;
 321 }