]>
Commit | Line | Data |
---|---|---|
18c8241a MM |
1 | /* |
2 | * BIRD Resource Manager -- Memory Pools | |
3 | * | |
5cc1e1f8 | 4 | * (c) 1998--2000 Martin Mares <mj@ucw.cz> |
18c8241a MM |
5 | * |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
5cc1e1f8 MM |
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 | ||
18c8241a | 21 | #include <stdlib.h> |
46eb80d5 | 22 | #include <stdint.h> |
18c8241a MM |
23 | |
24 | #include "nest/bird.h" | |
25 | #include "lib/resource.h" | |
221135d6 | 26 | #include "lib/string.h" |
18c8241a | 27 | |
b35d72ac MM |
28 | struct lp_chunk { |
29 | struct lp_chunk *next; | |
c9763428 | 30 | unsigned int size; |
d1abbeac | 31 | uintptr_t data_align[0]; |
18c8241a MM |
32 | byte data[0]; |
33 | }; | |
34 | ||
b35d72ac | 35 | struct linpool { |
18c8241a MM |
36 | resource r; |
37 | byte *ptr, *end; | |
f5c687f7 MM |
38 | struct lp_chunk *first, *current, **plast; /* Normal (reusable) chunks */ |
39 | struct lp_chunk *first_large; /* Large chunks */ | |
40 | unsigned chunk_size, threshold, total, total_large; | |
18c8241a MM |
41 | }; |
42 | ||
c9763428 MM |
43 | static void lp_free(resource *); |
44 | static void lp_dump(resource *); | |
45 | static resource *lp_lookup(resource *, unsigned long); | |
acb60628 | 46 | static size_t lp_memsize(resource *r); |
18c8241a | 47 | |
b35d72ac MM |
48 | static struct resclass lp_class = { |
49 | "LinPool", | |
50 | sizeof(struct linpool), | |
51 | lp_free, | |
c9763428 | 52 | lp_dump, |
acb60628 OZ |
53 | lp_lookup, |
54 | lp_memsize | |
18c8241a MM |
55 | }; |
56 | ||
5cc1e1f8 MM |
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 | */ | |
b35d72ac MM |
66 | linpool |
67 | *lp_new(pool *p, unsigned blk) | |
18c8241a | 68 | { |
b35d72ac | 69 | linpool *m = ralloc(p, &lp_class); |
18c8241a MM |
70 | m->plast = &m->first; |
71 | m->chunk_size = blk; | |
72 | m->threshold = 3*blk/4; | |
18c8241a MM |
73 | return m; |
74 | } | |
75 | ||
5cc1e1f8 MM |
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 | */ | |
18c8241a | 90 | void * |
b35d72ac | 91 | lp_alloc(linpool *m, unsigned size) |
18c8241a | 92 | { |
7fdd338c | 93 | byte *a = (byte *) BIRD_ALIGN((unsigned long) m->ptr, CPU_STRUCT_ALIGN); |
18c8241a MM |
94 | byte *e = a + size; |
95 | ||
96 | if (e <= m->end) | |
97 | { | |
98 | m->ptr = e; | |
99 | return a; | |
100 | } | |
101 | else | |
102 | { | |
b35d72ac | 103 | struct lp_chunk *c; |
18c8241a MM |
104 | if (size >= m->threshold) |
105 | { | |
f5c687f7 | 106 | /* Too large => allocate large chunk */ |
b35d72ac | 107 | c = xmalloc(sizeof(struct lp_chunk) + size); |
f5c687f7 MM |
108 | m->total_large += size; |
109 | c->next = m->first_large; | |
0766e962 | 110 | m->first_large = c; |
c9763428 | 111 | c->size = size; |
18c8241a MM |
112 | } |
113 | else | |
114 | { | |
92af6f30 MM |
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 | } | |
f5c687f7 MM |
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; | |
c9763428 | 129 | c->size = m->chunk_size; |
f5c687f7 | 130 | } |
18c8241a MM |
131 | m->ptr = c->data + size; |
132 | m->end = c->data + m->chunk_size; | |
18c8241a | 133 | } |
18c8241a MM |
134 | return c->data; |
135 | } | |
136 | } | |
137 | ||
5cc1e1f8 MM |
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 | */ | |
18c8241a | 148 | void * |
b35d72ac | 149 | lp_allocu(linpool *m, unsigned size) |
18c8241a MM |
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 | } | |
b35d72ac | 159 | return lp_alloc(m, size); |
18c8241a MM |
160 | } |
161 | ||
5cc1e1f8 MM |
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 | */ | |
18c8241a | 170 | void * |
b35d72ac | 171 | lp_allocz(linpool *m, unsigned size) |
18c8241a | 172 | { |
b35d72ac | 173 | void *z = lp_alloc(m, size); |
18c8241a MM |
174 | |
175 | bzero(z, size); | |
176 | return z; | |
177 | } | |
178 | ||
5cc1e1f8 MM |
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 | */ | |
f5c687f7 MM |
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 | ||
c9763428 | 202 | static void |
b35d72ac | 203 | lp_free(resource *r) |
18c8241a | 204 | { |
b35d72ac MM |
205 | linpool *m = (linpool *) r; |
206 | struct lp_chunk *c, *d; | |
18c8241a MM |
207 | |
208 | for(d=m->first; d; d = c) | |
209 | { | |
210 | c = d->next; | |
211 | xfree(d); | |
212 | } | |
507cb9e5 MM |
213 | for(d=m->first_large; d; d = c) |
214 | { | |
215 | c = d->next; | |
216 | xfree(d); | |
217 | } | |
18c8241a MM |
218 | } |
219 | ||
c9763428 | 220 | static void |
b35d72ac | 221 | lp_dump(resource *r) |
18c8241a | 222 | { |
b35d72ac MM |
223 | linpool *m = (linpool *) r; |
224 | struct lp_chunk *c; | |
5bc512aa | 225 | int cnt, cntl; |
18c8241a MM |
226 | |
227 | for(cnt=0, c=m->first; c; c=c->next, cnt++) | |
228 | ; | |
5bc512aa MM |
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", | |
18c8241a MM |
232 | m->chunk_size, |
233 | m->threshold, | |
234 | cnt, | |
5bc512aa MM |
235 | cntl, |
236 | m->total, | |
237 | m->total_large); | |
18c8241a | 238 | } |
c9763428 | 239 | |
acb60628 OZ |
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(sizeof(struct lp_chunk))) + | |
254 | m->total + m->total_large; | |
255 | } | |
256 | ||
257 | ||
c9763428 MM |
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 | } |