Return to mempool.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

bird 1.6.3

    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: 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:   uint 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: static size_t lp_memsize(resource *r);
   47: 
   48: static struct resclass lp_class = {
   49:   "LinPool",
   50:   sizeof(struct linpool),
   51:   lp_free,
   52:   lp_dump,
   53:   lp_lookup,
   54:   lp_memsize
   55: };
   56: 
   57: /**
   58:  * lp_new - create a new linear memory pool
   59:  * @p: pool
   60:  * @blk: block size
   61:  *
   62:  * lp_new() creates a new linear memory pool resource inside the pool @p.
   63:  * The linear pool consists of a list of memory chunks of size at least
   64:  * @blk.
   65:  */
   66: linpool
   67: *lp_new(pool *p, uint blk)
   68: {
   69:   linpool *m = ralloc(p, &lp_class);
   70:   m->plast = &m->first;
   71:   m->chunk_size = blk;
   72:   m->threshold = 3*blk/4;
   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, uint 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, uint 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, uint 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 size_t
  241: lp_memsize(resource *r)
  242: {
  243:   linpool *m = (linpool *) r;
  244:   struct lp_chunk *c;
  245:   int cnt = 0;
  246: 
  247:   for(c=m->first; c; c=c->next)
  248:     cnt++;
  249:   for(c=m->first_large; c; c=c->next)
  250:     cnt++;
  251: 
  252:   return ALLOC_OVERHEAD + sizeof(struct linpool) +
  253:     cnt * (ALLOC_OVERHEAD + sizeof(struct lp_chunk)) +
  254:     m->total + m->total_large;
  255: }
  256: 
  257: 
  258: static resource *
  259: lp_lookup(resource *r, unsigned long a)
  260: {
  261:   linpool *m = (linpool *) r;
  262:   struct lp_chunk *c;
  263: 
  264:   for(c=m->first; c; c=c->next)
  265:     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
  266:       return r;
  267:   for(c=m->first_large; c; c=c->next)
  268:     if ((unsigned long) c->data <= a && (unsigned long) c->data + c->size > a)
  269:       return r;
  270:   return NULL;
  271: }