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