]>
git.ipfire.org Git - thirdparty/bird.git/blob - lib/mempool.c
2 * BIRD Resource Manager -- Memory Pools
4 * (c) 1998--2000 Martin Mares <mj@ucw.cz>
6 * Can be freely distributed and used under the terms of the GNU GPL.
10 * DOC: Linear memory pools
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.
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.
24 #include "nest/bird.h"
25 #include "lib/resource.h"
26 #include "lib/string.h"
29 struct lp_chunk
*next
;
31 uintptr_t data_align
[0];
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
;
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
);
48 static struct resclass lp_class
= {
50 sizeof(struct linpool
),
58 * lp_new - create a new linear memory pool
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
67 *lp_new(pool
*p
, unsigned blk
)
69 linpool
*m
= ralloc(p
, &lp_class
);
72 m
->threshold
= 3*blk
/4;
77 * lp_alloc - allocate memory from a &linpool
78 * @m: linear memory pool
79 * @size: amount of memory
81 * lp_alloc() allocates @size bytes of memory from a &linpool @m
82 * and it returns a pointer to the allocated memory.
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.
91 lp_alloc(linpool
*m
, unsigned size
)
93 byte
*a
= (byte
*) BIRD_ALIGN((unsigned long) m
->ptr
, CPU_STRUCT_ALIGN
);
104 if (size
>= m
->threshold
)
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
;
117 /* Still have free chunks from previous incarnation (before lp_flush()) */
119 m
->current
= c
->next
;
123 /* Need to allocate a new chunk */
124 c
= xmalloc(sizeof(struct lp_chunk
) + m
->chunk_size
);
125 m
->total
+= m
->chunk_size
;
129 c
->size
= m
->chunk_size
;
131 m
->ptr
= c
->data
+ size
;
132 m
->end
= c
->data
+ m
->chunk_size
;
139 * lp_allocu - allocate unaligned memory from a &linpool
140 * @m: linear memory pool
141 * @size: amount of memory
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.
149 lp_allocu(linpool
*m
, unsigned size
)
159 return lp_alloc(m
, size
);
163 * lp_allocz - allocate cleared memory from a &linpool
164 * @m: linear memory pool
165 * @size: amount of memory
167 * This function is identical to lp_alloc() except that it
168 * clears the allocated memory block.
171 lp_allocz(linpool
*m
, unsigned size
)
173 void *z
= lp_alloc(m
, size
);
180 * lp_flush - flush a linear memory pool
181 * @m: linear memory pool
183 * This function frees the whole contents of the given &linpool @m,
184 * but leaves the pool itself.
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
)
196 m
->first_large
= c
->next
;
205 linpool
*m
= (linpool
*) r
;
206 struct lp_chunk
*c
, *d
;
208 for(d
=m
->first
; d
; d
= c
)
213 for(d
=m
->first_large
; d
; d
= c
)
223 linpool
*m
= (linpool
*) r
;
227 for(cnt
=0, c
=m
->first
; c
; c
=c
->next
, cnt
++)
229 for(cntl
=0, c
=m
->first_large
; c
; c
=c
->next
, cntl
++)
231 debug("(chunk=%d threshold=%d count=%d+%d total=%d+%d)\n",
241 lp_memsize(resource
*r
)
243 linpool
*m
= (linpool
*) r
;
247 for(c
=m
->first
; c
; c
=c
->next
)
249 for(c
=m
->first_large
; c
; c
=c
->next
)
252 return ALLOC_OVERHEAD
+ sizeof(struct linpool
) +
253 cnt
* (ALLOC_OVERHEAD
+ sizeof(sizeof(struct lp_chunk
))) +
254 m
->total
+ m
->total_large
;
259 lp_lookup(resource
*r
, unsigned long a
)
261 linpool
*m
= (linpool
*) r
;
264 for(c
=m
->first
; c
; c
=c
->next
)
265 if ((unsigned long) c
->data
<= a
&& (unsigned long) c
->data
+ c
->size
> a
)
267 for(c
=m
->first_large
; c
; c
=c
->next
)
268 if ((unsigned long) c
->data
<= a
&& (unsigned long) c
->data
+ c
->size
> a
)