2 * This is an implementation of a buddy memory allocator.
3 * For a description of such a system, please refer to:
5 * The Art of Computer Programming Vol. I, by Donald E. Knuth
10 #include <limits.h> /* for CHAR_BIT */
14 /* Function prototypes */
15 static void mpool_printblks(const mpool_t
*mpool
);
17 mpret_t
mpool_init(mpool_t
**mpool
, size_t maxlogsize
, size_t minlogsize
)
23 if (maxlogsize
> sizeof(size_t) * CHAR_BIT
)
25 if (maxlogsize
< minlogsize
|| (size_t)(1 << minlogsize
) <= sizeof *pblknode
)
28 /* Allocate memory for memory pool data structure */
29 if ((*mpool
= malloc(sizeof **mpool
)) == NULL
)
32 /* Initialize mpool members */
33 (*mpool
)->maxlogsize
= maxlogsize
;
34 (*mpool
)->minlogsize
= minlogsize
;
35 (*mpool
)->nblocks
= maxlogsize
- minlogsize
+ 1;
37 (*mpool
)->nsplits
= 0;
38 (*mpool
)->nmerges
= 0;
41 /* Allocate the actual memory of the pool */
42 if (((*mpool
)->mem
= malloc((size_t)(1 << maxlogsize
))) == NULL
) {
46 DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n" \
47 "mpool->mem = %p\tsizeof(blknode) = 0x%x\n",
53 DPRINTF(("Allocated %u bytes for pool\n", 1 << maxlogsize
));
55 /* Allocate memory for block lists */
56 if (((*mpool
)->blktable
= malloc((*mpool
)->nblocks
*
57 sizeof *(*mpool
)->blktable
)) == NULL
) {
63 /* Initialize block lists */
64 for (i
= 0; i
< (*mpool
)->nblocks
; i
++)
65 LIST_INIT(&(*mpool
)->blktable
[i
]);
68 * Initially, before any storage has been requested, we have a single
69 * available block of length 2^maxlogsize in blktable[0].
71 MPOOL_BLOCK_INIT(pblknode
,
73 (char *)(*mpool
)->mem
+ sizeof *pblknode
,
75 MPOOL_BLOCK_LEFT
, /* irrelevant */
76 MPOOL_BLOCK_PARENT
, /* irrelevant */
79 /* Insert block to the first block list */
80 LIST_INSERT_HEAD(&(*mpool
)->blktable
[0], pblknode
, next_chunk
);
81 mpool_printblks(*mpool
);
86 void *mpool_alloc(mpool_t
*mpool
, size_t blksize
)
90 blknode_t
*pavailnode
;
92 size_t i
, newpos
, size
;
96 * Total size is the sum of the user's request plus the overhead of a
97 * blknode_t data structure. Be aware for the particular scenario, when
98 * requested size is of the form 2^j. The allocator will then return
99 * the next bigger memory chunk, leading to high internal fragmentation.
101 size
= blksize
+ sizeof *pnode
;
103 DPRINTF(("\n;--------------------------------------------------------------;\n"));
104 DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
105 blksize
, sizeof *pnode
, size
));
108 * Find the most suitable 2^j bytes block for the requested size of bytes.
109 * The condition 2^j >= size must be satisfied for the smallest possible
110 * value of j and the block must be marked as available ofcourse.
113 for (i
= 0; i
< mpool
->nblocks
; i
++) {
114 DPRINTF(("Searching block: %u\n", i
));
115 phead
= &mpool
->blktable
[i
];
116 if ((pnode
= LIST_FIRST(phead
)) != NULL
) {
117 if ((size_t)(1 << pnode
->logsize
) >= size
) {
118 LIST_FOREACH(pnode
, phead
, next_chunk
) {
119 if (MPOOL_IS_AVAIL(pnode
)) {
121 goto NEXT_BLOCK_LIST
;
129 /* Failure, no available block */
130 if (pavailnode
== NULL
) {
131 DPRINTF(("No available block found\n"));
134 DPRINTF(("Found block of bytes %u\n", 1 << pavailnode
->logsize
));
136 /* Is a split required ? */
138 DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
140 1 << pavailnode
->logsize
,
141 1 << (pavailnode
->logsize
- 1)));
144 * We don't need to split the chunk we just found,
145 * if one at least of the following statements is true:
147 * - `size' bytes fit exactly in the chunk
148 * - `size' bytes won't fit in the splitted chunk
149 * - `minlogsize' constraint will be violated if we split
151 * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
153 if ((size
== (size_t)(1 << pavailnode
->logsize
))
154 || (size
> (size_t)(1 << (pavailnode
->logsize
- 1)))
155 || (mpool
->minlogsize
> (pavailnode
->logsize
- 1))) {
156 DPRINTF(("No split required\n"));
157 MPOOL_MARK_USED(pavailnode
);
158 mpool_printblks(mpool
);
159 return pavailnode
->ptr
;
162 DPRINTF(("Splitting...\n"));
167 /* Remove old chunk */
168 DPRINTF(("Removing old chunk from list\n"));
169 LIST_REMOVE(pavailnode
, next_chunk
);
170 mpool_printblks(mpool
);
172 /* Calculate new size */
173 pavailnode
->logsize
--;
174 DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode
->logsize
));
177 flag
= pavailnode
->flags
;
178 if (MPOOL_IS_RIGHT(pavailnode
))
179 /*pavailnode->flags |= MPOOL_NODE_PARENT;*/
180 MPOOL_MARK_PARENT(pavailnode
);
182 /*pavailnode->flags &= ~MPOOL_NODE_PARENT;*/
183 MPOOL_MARK_NOTPARENT(pavailnode
);
184 MPOOL_MARK_LEFT(pavailnode
);
186 /* Calculate new position of chunk and insert it there */
187 newpos
= mpool
->maxlogsize
- pavailnode
->logsize
;
188 DPRINTF(("Moving old chunk to new position: %u\n", newpos
));
189 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pavailnode
, next_chunk
);
190 mpool_printblks(mpool
);
193 DPRINTF(("Will add new item with bytes: %u (0x%x)\n",
194 1 << pavailnode
->logsize
,
195 1 << pavailnode
->logsize
));
197 MPOOL_BLOCK_INIT(pnewnode
,
198 (blknode_t
*)((char *)pavailnode
+ (1 << pavailnode
->logsize
)),
199 (char *)pnewnode
+ sizeof *pnewnode
,
202 (flag
& MPOOL_NODE_PARENT
) ? MPOOL_BLOCK_PARENT
: -1,
203 pavailnode
->logsize
);
205 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pnewnode
, next_chunk
);
206 mpool_printblks(mpool
);
212 void mpool_free(mpool_t
*mpool
, void *ptr
)
215 blknode_t
*pnode
, *pbuddy
;
218 DPRINTF(("[ Freeing ptr: %p ]\n", ptr
));
220 #ifdef MPOOL_OPT_FOR_SECURITY
221 /* Search all nodes to find the one that points to ptr */
224 for (i
= 0; i
< mpool
->nblocks
; i
++) {
225 DPRINTF(("Searching for ptr %p in block: %u\n", ptr
, i
));
226 phead
= &mpool
->blktable
[i
];
227 LIST_FOREACH(pnode
, phead
, next_chunk
) {
228 if (pnode
->ptr
== ptr
) {
229 DPRINTF(("Found chunk at block: %u\t"
230 "Block has chunks with bytes: %u\n",
231 i
, 1 << pnode
->logsize
));
238 * Chunk isn't in our pool, this is probably bad.
240 * It means that either the user has provided an invalid pointer to free or
241 * the allocator exhibited buggy behaviour and corrupted itself. Either way,
242 * return immediately.
244 DPRINTF(("Chunk %p was not found in the pool\n", ptr
));
247 pnode
= (blknode_t
*)((char *)ptr
- sizeof *pnode
);
251 /* Are we top level ? */
252 if (pnode
->logsize
== mpool
->maxlogsize
) {
253 if (MPOOL_IS_AVAIL(pnode
) == 0)
254 MPOOL_MARK_AVAIL(pnode
);
258 /* Calculate possible buddy of chunk */
259 DPRINTF(("Searching for buddy of %p...\n", pnode
->ptr
));
261 /* `pnode' is a right buddy, so `pbuddy' is a left buddy */
262 if (MPOOL_IS_RIGHT(pnode
)) {
263 pbuddy
= MPOOL_GET_LEFT_BUDDY(pnode
);
264 if ((void *)pbuddy
< (void *)mpool
->mem
) {
265 DPRINTF(("buddy out of pool\n"));
269 /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
271 pbuddy
= MPOOL_GET_RIGHT_BUDDY(pnode
);
273 (void *)((char *)mpool
->mem
+ (1 << mpool
->maxlogsize
) - 1)) {
274 DPRINTF(("buddy out of pool\n"));
279 /* Buddies must be of the same size */
280 if (pbuddy
->logsize
!= pnode
->logsize
)
284 * If there is no buddy of `pnode' or if there is, but it's unavailable,
285 * just free `pnode' and we are done.
287 if (pbuddy
== NULL
|| (pbuddy
!= NULL
&& MPOOL_IS_USED(pbuddy
))) {
288 DPRINTF(("Not found or found but unavailable\n"));
289 DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode
->ptr
));
290 MPOOL_MARK_AVAIL(pnode
);
291 mpool_printblks(mpool
);
295 * There is a buddy, and it's available for sure. Coalesce.
298 DPRINTF(("Buddy %p exists and it's available. Coalesce.\n",
303 DPRINTF(("Removing chunk %p from old position %u\n",
304 pnode
->ptr
, mpool
->maxlogsize
- pnode
->logsize
));
305 LIST_REMOVE(pnode
, next_chunk
);
306 mpool_printblks(mpool
);
309 * `pnode' is left buddy
311 if (MPOOL_IS_LEFT(pnode
)) {
312 /*if (pnode->flags & MPOOL_NODE_PARENT)*/
313 if (MPOOL_IS_PARENT(pnode
))
314 MPOOL_MARK_RIGHT(pnode
);
316 MPOOL_MARK_LEFT(pnode
);
318 /*if (pbuddy->flags & MPOOL_NODE_PARENT)*/
319 if (MPOOL_IS_PARENT(pbuddy
))
320 /*pnode->flags |= MPOOL_NODE_PARENT;*/
321 MPOOL_MARK_PARENT(pnode
);
323 /*pnode->flags &= ~MPOOL_NODE_PARENT;*/
324 MPOOL_MARK_NOTPARENT(pnode
);
327 MPOOL_MARK_AVAIL(pnode
);
329 /* Insert `pnode' to the appropriate position */
330 newpos
= mpool
->maxlogsize
- pnode
->logsize
;
331 phead
= &mpool
->blktable
[newpos
];
332 DPRINTF(("We will keep chunk %p, we will remove pbuddy %p\n",
333 pnode
->ptr
, pbuddy
->ptr
));
334 DPRINTF(("Inserting chunk %p to new position = %u\n",
335 pnode
->ptr
, newpos
));
336 LIST_INSERT_HEAD(phead
, pnode
, next_chunk
);
338 /* Remove `pbuddy' from the block lists */
339 DPRINTF(("Removing buddy %p\n", pbuddy
->ptr
));
340 LIST_REMOVE(pbuddy
, next_chunk
);
343 * `pbuddy' is left buddy
345 else if (MPOOL_IS_LEFT(pbuddy
)) {
346 LIST_REMOVE(pbuddy
, next_chunk
);
347 /*if (pbuddy->flags & MPOOL_NODE_PARENT)*/
348 if (MPOOL_IS_PARENT(pbuddy
))
349 MPOOL_MARK_RIGHT(pbuddy
);
351 MPOOL_MARK_LEFT(pbuddy
);
353 /*if (pnode->flags & MPOOL_NODE_PARENT)*/
354 if (MPOOL_IS_PARENT(pnode
))
355 /*pbuddy->flags |= MPOOL_NODE_PARENT;*/
356 MPOOL_MARK_PARENT(pbuddy
);
358 /*pbuddy->flags &= ~MPOOL_NODE_PARENT;*/
359 MPOOL_MARK_NOTPARENT(pbuddy
);
362 MPOOL_MARK_AVAIL(pbuddy
);
364 /* Insert `pbuddy' to the appropriate position */
365 newpos
= mpool
->maxlogsize
- pbuddy
->logsize
;
366 phead
= &mpool
->blktable
[newpos
];
367 DPRINTF(("We will keep buddy %p, we will remove chunk %p\n",
368 pbuddy
->ptr
, pnode
->ptr
));
369 DPRINTF(("Inserting buddy %p to new position = %u\n",
370 pbuddy
->ptr
, mpool
->maxlogsize
- pbuddy
->logsize
));
371 LIST_INSERT_HEAD(phead
, pbuddy
, next_chunk
);
377 DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
378 pnode
->ptr
, pbuddy
->ptr
));
381 mpool_printblks(mpool
);
388 void mpool_destroy(mpool_t
*mpool
)
390 free(mpool
->blktable
);
395 static void mpool_printblks(const mpool_t
*mpool
)
397 const blkhead_t
*phead
;
398 const blknode_t
*pnode
;
401 for (i
= 0; i
< mpool
->nblocks
; i
++) {
402 DPRINTF(("Block (%p): %u\t", mpool
->blktable
[i
], i
));
403 phead
= &mpool
->blktable
[i
];
404 LIST_FOREACH(pnode
, phead
, next_chunk
) {
405 DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
407 (unsigned) (1 << pnode
->logsize
),
408 MPOOL_IS_AVAIL(pnode
) ? 1 : 0,
409 MPOOL_IS_RIGHT(pnode
) ? 1 : 0,
410 MPOOL_IS_PARENT(pnode
) ? 1 : 0));