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
13 /* Function prototypes */
14 static void mpool_printblks(const mpool_t
*mpool
);
16 mpret_t
mpool_init(mpool_t
**mpool
, size_t maxlogsize
, size_t minlogsize
)
22 if (maxlogsize
< minlogsize
|| (size_t)(1 << minlogsize
) <= sizeof *pblknode
)
25 /* Allocate memory for memory pool data structure */
26 if ((*mpool
= malloc(sizeof **mpool
)) == NULL
)
29 (*mpool
)->maxlogsize
= maxlogsize
;
30 (*mpool
)->minlogsize
= minlogsize
;
31 (*mpool
)->nblocks
= (*mpool
)->maxlogsize
- (*mpool
)->minlogsize
+ 1;
33 (*mpool
)->nsplits
= 0;
34 (*mpool
)->nmerges
= 0;
37 /* Allocate the actual memory of the pool */
38 if (((*mpool
)->mem
= malloc((size_t)(1 << maxlogsize
))) == NULL
) {
42 DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n" \
43 "mpool->mem = %p\tsizeof(blknode) = 0x%x\n",
49 DPRINTF(("Allocated %u bytes for pool\n", 1 << maxlogsize
));
51 /* Allocate memory for block lists */
52 if (((*mpool
)->blktable
= malloc((*mpool
)->nblocks
* sizeof *(*mpool
)->blktable
)) == NULL
) {
58 /* Initialize block lists */
59 for (i
= 0; i
< (*mpool
)->nblocks
; i
++)
60 LIST_INIT(&(*mpool
)->blktable
[i
]);
63 * Initially, before any storage has been requested,
64 * we have a single available block of length 2^maxlogsize
68 pblknode = (*mpool)->mem;
69 pblknode->ptr = (char *)(*mpool)->mem + sizeof *pblknode;
70 MPOOL_MARK_AVAIL(pblknode);
71 pblknode->logsize = maxlogsize;
73 MPOOL_BLOCK_INIT(pblknode
,
75 (char *)(*mpool
)->mem
+ sizeof(blknode_t
),
77 MPOOL_BLOCK_LEFT
, /* irrelevant */
78 MPOOL_BLOCK_PARENT
, /* irrelevant */
81 /* Insert block to the first block list */
82 LIST_INSERT_HEAD(&(*mpool
)->blktable
[0], pblknode
, next_chunk
);
84 mpool_printblks(*mpool
);
89 void *mpool_alloc(mpool_t
*mpool
, size_t blksize
)
93 blknode_t
*pavailnode
;
95 size_t i
, newpos
, size
;
99 * Total size is the sum of the user's request
100 * plus the overhead of a blknode_t data structure.
102 * Be aware for the particular scenario, when
103 * reqsize is 2^j. The allocator will return
104 * the next bigger memory chunk, leading to high
105 * internal fragmentation.
107 size
= blksize
+ sizeof *pnode
;
109 DPRINTF(("\n\n=======================================================\n\n"));
110 DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
111 blksize
, sizeof *pnode
, size
));
114 * Find the most suitable 2^j bytes block for the requested size of bytes.
115 * The condition 2^j >= size must be satisfied for the smallest possible
116 * value of j and the block must be marked as available ofcourse.
119 for (i
= 0; i
< mpool
->nblocks
; i
++) {
120 DPRINTF(("Searching block: %u\n", i
));
121 phead
= &mpool
->blktable
[i
];
122 if ((pnode
= LIST_FIRST(phead
)) != NULL
) {
123 if ((size_t)(1 << pnode
->logsize
) >= size
) {
124 LIST_FOREACH(pnode
, phead
, next_chunk
) {
125 if (MPOOL_IS_AVAIL(pnode
)) {
127 goto NEXT_BLOCK_LIST
;
135 /* Failure, no available block */
136 if (pavailnode
== NULL
) {
137 DPRINTF(("No available block found\n"));
140 DPRINTF(("Found block of bytes %u\n", 1 << pavailnode
->logsize
));
142 /* Is a split required ? */
144 DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
146 1 << pavailnode
->logsize
,
147 1 << (pavailnode
->logsize
- 1)));
150 * We don't need to split the chunk we just found,
151 * if one at least of the following statements is true:
153 * - `size' bytes fit exactly in the chunk
154 * - `size' bytes won't fit in the splitted chunk
155 * - `minlogsize' constraint will be violated if we split
157 * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
159 if ((size
== (size_t)(1 << pavailnode
->logsize
))
160 || (size
> (size_t)(1 << (pavailnode
->logsize
- 1)))
161 || (mpool
->minlogsize
> (pavailnode
->logsize
- 1))) {
162 DPRINTF(("No split required\n"));
163 MPOOL_MARK_USED(pavailnode
);
164 mpool_printblks(mpool
);
165 return pavailnode
->ptr
;
168 DPRINTF(("Splitting...\n"));
173 /* Remove old chunk */
174 DPRINTF(("Removing old chunk from list\n"));
175 LIST_REMOVE(pavailnode
, next_chunk
);
176 mpool_printblks(mpool
);
178 pavailnode
->logsize
--;
179 flag
= pavailnode
->flags
;
180 if (MPOOL_IS_RIGHT(pavailnode
))
181 pavailnode
->flags
|= MPOOL_NODE_PARENT
;
183 pavailnode
->flags
&= ~MPOOL_NODE_PARENT
;
184 MPOOL_MARK_LEFT(pavailnode
);
186 DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode
->logsize
));
188 newpos
= mpool
->maxlogsize
- pavailnode
->logsize
;
189 DPRINTF(("Moving old chunk to new position: %u\n", newpos
));
191 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pavailnode
, next_chunk
);
192 mpool_printblks(mpool
);
195 DPRINTF(("Will add new item with bytes: %u (0x%x)\n",
196 1 << pavailnode
->logsize
,
197 1 << pavailnode
->logsize
));
198 if ((size_t)(1 << pavailnode
->logsize
) < sizeof *pnewnode
)
201 pnewnode = (blknode_t *)((char *)pavailnode + (1 << pavailnode->logsize));
202 pnewnode->ptr = (char *)pnewnode + sizeof *pnewnode;
203 MPOOL_MARK_AVAIL(pnewnode);
204 MPOOL_MARK_RIGHT(pnewnode);
206 if (flag & MPOOL_NODE_PARENT)
207 pnewnode->flags |= MPOOL_NODE_PARENT;
209 pnewnode->flags &= ~MPOOL_NODE_PARENT;
210 pnewnode->logsize = pavailnode->logsize;
212 MPOOL_BLOCK_INIT(pnewnode
,
213 (blknode_t
*)((char *)pavailnode
+ (1 << pavailnode
->logsize
)),
214 (char *)pnewnode
+ sizeof *pnewnode
,
217 (flag
& MPOOL_NODE_PARENT
) ? MPOOL_BLOCK_PARENT
: -1,
218 pavailnode
->logsize
);
220 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pnewnode
, next_chunk
);
221 mpool_printblks(mpool
);
227 void mpool_free(mpool_t
*mpool
, void *ptr
)
230 blknode_t
*pnode
, *pbuddy
;
233 DPRINTF(("[ Freeing ptr: %p ]\n", ptr
));
235 /* Search all nodes to find the one that points to ptr */
237 for (i
= 0; i
< mpool
->nblocks
; i
++) {
238 DPRINTF(("Searching for ptr %p in block: %u\n", ptr
, i
));
239 phead
= &mpool
->blktable
[i
];
240 LIST_FOREACH(pnode
, phead
, next_chunk
) {
241 if (pnode
->ptr
== ptr
) {
242 DPRINTF(("Found chunk at block: %u\t"
243 "Block has chunks with bytes: %u\n",
244 i
, 1 << pnode
->logsize
));
251 * Chunk isn't in our pool, this is probably bad.
253 * It means that either the user has provided an invalid
254 * pointer to free or the allocator exhibited buggy
255 * behaviour and corrupted itself.
257 * Either way, return immediately.
259 DPRINTF(("Chunk %p was not found in the pool\n", ptr
));
263 /* Are we top level ? */
264 if (pnode
->logsize
== mpool
->maxlogsize
)
267 /* Calculate possible buddy of chunk */
268 DPRINTF(("Searching for buddy of %p...\n", pnode
->ptr
));
270 /* `pnode' is a right buddy, so `pbuddy' is a left buddy */
271 if (MPOOL_IS_RIGHT(pnode
)) {
272 pbuddy
= (blknode_t
*)((char *)pnode
- (1 << pnode
->logsize
));
273 if ((void *)pbuddy
< (void *)mpool
->mem
) {
274 DPRINTF(("buddy out of pool\n"));
277 if (pbuddy
->logsize
!= pnode
->logsize
)
280 /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
282 pbuddy
= (blknode_t
*)((char *)pnode
+ (1 << pnode
->logsize
));
283 if ((void *)pbuddy
> (void *)((char *)mpool
->mem
+ (1 << mpool
->maxlogsize
) - 1)) {
284 DPRINTF(("buddy out of pool\n"));
287 if (pbuddy
->logsize
!= pnode
->logsize
)
292 * If there is no buddy of `pnode' or if there is, but it's unavailable,
293 * just free `pnode' and we are done.
295 /*if (pbuddy == NULL || (pbuddy != NULL && ((pbuddy->flags & MPOOL_NODE_AVAIL) == 0))) {*/
296 if (pbuddy
== NULL
|| (pbuddy
!= NULL
&& MPOOL_IS_USED(pbuddy
))) {
297 DPRINTF(("Not found or found but unavailable\n"));
298 DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode
->ptr
));
299 MPOOL_MARK_AVAIL(pnode
);
300 mpool_printblks(mpool
);
304 * There is a buddy, and it's available for sure. Coalesce.
307 DPRINTF(("Buddy %p exists and it's available. Coalesce.\n",
312 DPRINTF(("Removing chunk %p from old position %u\n",
313 pnode
->ptr
, mpool
->maxlogsize
- pnode
->logsize
));
314 LIST_REMOVE(pnode
, next_chunk
);
315 mpool_printblks(mpool
);
318 * `pnode' is left buddy
320 if (MPOOL_IS_LEFT(pnode
)) {
321 if (pnode
->flags
& MPOOL_NODE_PARENT
)
322 MPOOL_MARK_RIGHT(pnode
);
324 MPOOL_MARK_LEFT(pnode
);
326 if (pbuddy
->flags
& MPOOL_NODE_PARENT
)
327 pnode
->flags
|= MPOOL_NODE_PARENT
;
329 pnode
->flags
&= ~MPOOL_NODE_PARENT
;
332 MPOOL_MARK_AVAIL(pnode
);
334 /* Insert `pnode' to the appropriate position */
335 newpos
= mpool
->maxlogsize
- pnode
->logsize
;
336 phead
= &mpool
->blktable
[newpos
];
337 DPRINTF(("We will keep chunk %p, we will remove pbuddy %p\n",
338 pnode
->ptr
, pbuddy
->ptr
));
339 DPRINTF(("Inserting chunk %p to new position = %u\n",
340 pnode
->ptr
, mpool
->maxlogsize
- pnode
->logsize
));
341 LIST_INSERT_HEAD(phead
, pnode
, next_chunk
);
343 /* Remove `pbuddy' from the block lists */
344 DPRINTF(("Removing buddy %p\n", pbuddy
->ptr
));
345 LIST_REMOVE(pbuddy
, next_chunk
);
348 * `pbuddy' is left buddy
350 else if (MPOOL_IS_LEFT(pbuddy
)) {
351 LIST_REMOVE(pbuddy
, next_chunk
);
352 if (pbuddy
->flags
& MPOOL_NODE_PARENT
)
353 MPOOL_MARK_RIGHT(pbuddy
);
355 MPOOL_MARK_LEFT(pbuddy
);
357 if (pnode
->flags
& MPOOL_NODE_PARENT
)
358 pbuddy
->flags
|= MPOOL_NODE_PARENT
;
360 pbuddy
->flags
&= ~MPOOL_NODE_PARENT
;
363 MPOOL_MARK_AVAIL(pbuddy
);
365 /* Insert `pbuddy' to the appropriate position */
366 newpos
= mpool
->maxlogsize
- pbuddy
->logsize
;
367 phead
= &mpool
->blktable
[newpos
];
368 DPRINTF(("We will keep buddy %p, we will remove chunk %p\n",
369 pbuddy
->ptr
, pnode
->ptr
));
370 DPRINTF(("Inserting buddy %p to new position = %u\n",
371 pbuddy
->ptr
, mpool
->maxlogsize
- pbuddy
->logsize
));
372 LIST_INSERT_HEAD(phead
, pbuddy
, next_chunk
);
378 DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
379 pnode
->ptr
, pbuddy
->ptr
));
382 mpool_printblks(mpool
);
389 void mpool_destroy(mpool_t
*mpool
)
391 free(mpool
->blktable
);
396 static void mpool_printblks(const mpool_t
*mpool
)
398 const blkhead_t
*phead
;
399 const blknode_t
*pnode
;
402 for (i
= 0; i
< mpool
->nblocks
; i
++) {
403 DPRINTF(("Block (%p): %u\t", mpool
->blktable
[i
], i
));
404 phead
= &mpool
->blktable
[i
];
405 LIST_FOREACH(pnode
, phead
, next_chunk
) {
406 DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
408 (unsigned) (1 << pnode
->logsize
),
409 MPOOL_IS_AVAIL(pnode
) ? 1 : 0,
410 MPOOL_IS_RIGHT(pnode
) ? 1 : 0,
411 pnode
->flags
& MPOOL_NODE_PARENT
? 1 : 0));