Annotation of embedaddon/bird2/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 (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