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