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 #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, **plast;    /* 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->plast = &m->first;
  73   m->chunk_size = blk;
  74   m->threshold = 3*blk/4;
  75   return m;
  76 }
  77
  78 /**
  79  * lp_alloc - allocate memory from a &linpool
  80  * @m: linear memory pool
  81  * @size: amount of memory
  82  *
  83  * lp_alloc() allocates @size bytes of memory from a &linpool @m
  84  * and it returns a pointer to the allocated memory.
  85  *
  86  * It works by trying to find free space in the last memory chunk
  87  * associated with the &linpool and creating a new chunk of the standard
  88  * size (as specified during lp_new()) if the free space is too small
  89  * to satisfy the allocation. If @size is too large to fit in a standard
  90  * size chunk, an "overflow" chunk is created for it instead.
  91  */
  92 void *
  93 lp_alloc(linpool *m, uint size)
  94 {
  95   byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN);
  96   byte *e = a + size;
  97
  98   if (e <= m->end)
  99     {
 100       m->ptr = e;
 101       return a;
 102     }
 103   else
 104     {
 105       struct lp_chunk *c;
 106       if (size >= m->threshold)
 107         {
 108           /* Too large => allocate large chunk */
 109           c = xmalloc(sizeof(struct lp_chunk) + size);
 110           m->total_large += size;
 111           c->next = m->first_large;
 112           m->first_large = c;
 113           c->size = size;
 114         }
 115       else
 116         {
 117           if (m->current)
 118             {
 119               /* Still have free chunks from previous incarnation (before lp_flush()) */
 120               c = m->current;
 121               m->current = c->next;
 122             }
 123           else
 124             {
 125               /* Need to allocate a new chunk */
 126               c = xmalloc(sizeof(struct lp_chunk) + m->chunk_size);
 127               m->total += m->chunk_size;
 128               *m->plast = c;
 129               m->plast = &c->next;
 130               c->next = NULL;
 131               c->size = m->chunk_size;
 132             }
 133           m->ptr = c->data + size;
 134           m->end = c->data + m->chunk_size;
 135         }
 136       return c->data;
 137     }
 138 }
 139
 140 /**
 141  * lp_allocu - allocate unaligned memory from a &linpool
 142  * @m: linear memory pool
 143  * @size: amount of memory
 144  *
 145  * lp_allocu() allocates @size bytes of memory from a &linpool @m
 146  * and it returns a pointer to the allocated memory. It doesn't
 147  * attempt to align the memory block, giving a very efficient way
 148  * how to allocate strings without any space overhead.
 149  */
 150 void *
 151 lp_allocu(linpool *m, uint size)
 152 {
 153   byte *a = m->ptr;
 154   byte *e = a + size;
 155
 156   if (e <= m->end)
 157     {
 158       m->ptr = e;
 159       return a;
 160     }
 161   return lp_alloc(m, size);
 162 }
 163
 164 /**
 165  * lp_allocz - allocate cleared memory from a &linpool
 166  * @m: linear memory pool
 167  * @size: amount of memory
 168  *
 169  * This function is identical to lp_alloc() except that it
 170  * clears the allocated memory block.
 171  */
 172 void *
 173 lp_allocz(linpool *m, uint size)
 174 {
 175   void *z = lp_alloc(m, size);
 176
 177   bzero(z, size);
 178   return z;
 179 }
 180
 181 /**
 182  * lp_flush - flush a linear memory pool
 183  * @m: linear memory pool
 184  *
 185  * This function frees the whole contents of the given &linpool @m,
 186  * but leaves the pool itself.
 187  */
 188 void
 189 lp_flush(linpool *m)
 190 {
 191   struct lp_chunk *c;
 192
 193   /* Relink all normal chunks to free list and free all large chunks */
 194   m->ptr = m->end = NULL;
 195   m->current = m->first;
 196   while (c = m->first_large)
 197     {
 198       m->first_large = c->next;
 199       xfree(c);
 200     }
 201   m->total_large = 0;
 202 }
 203
 204 static void
 205 lp_free(resource *r)
 206 {
 207   linpool *m = (linpool *) r;
 208   struct lp_chunk *c, *d;
 209
 210   for(d=m->first; d; d = c)
 211     {
 212       c = d->next;
 213       xfree(d);
 214     }
 215   for(d=m->first_large; d; d = c)
 216     {
 217       c = d->next;
 218       xfree(d);
 219     }
 220 }
 221
 222 static void
 223 lp_dump(resource *r)
 224 {
 225   linpool *m = (linpool *) r;
 226   struct lp_chunk *c;
 227   int cnt, cntl;
 228
 229   for(cnt=0, c=m->first; c; c=c->next, cnt++)
 230     ;
 231   for(cntl=0, c=m->first_large; c; c=c->next, cntl++)
 232     ;
 233   debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
 234         m->chunk_size,
 235         m->threshold,
 236         cnt,
 237         cntl,
 238         m->total,
 239         m->total_large);
 240 }
 241
 242 static size_t
 243 lp_memsize(resource *r)
 244 {
 245   linpool *m = (linpool *) r;
 246   struct lp_chunk *c;
 247   int cnt = 0;
 248
 249   for(c=m->first; c; c=c->next)
 250     cnt++;
 251   for(c=m->first_large; c; c=c->next)
 252     cnt++;
 253
 254   return ALLOC_OVERHEAD + sizeof(struct linpool) +
 255     cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
 256     m->total + m->total_large;
 257 }
 258
 259
 260 static resource *
 261 lp_lookup(resource *r, unsigned long a)
 262 {
 263   linpool *m = (linpool *) r;
 264   struct lp_chunk *c;
 265
 266   for(c=m->first; c; c=c->next)
 267     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 268       return r;
 269   for(c=m->first_large; c; c=c->next)
 270     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
 271       return r;
 272   return NULL;
 273 }