Annotation of embedaddon/bird/lib/mempool.c, revision 1.1
1.1 ! misho 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mempool.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib