Annotation of embedaddon/bird/lib/mempool.c, revision 1.1.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