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