6 /* Function prototypes */
7 static void mpool_printblks(const mpool_t
*mpool
);
9 mpret_t
mpool_init(mpool_t
**mpool
, size_t maxlogsize
, size_t minlogsize
)
15 if (maxlogsize
< minlogsize
|| (size_t)(1 << minlogsize
) <= sizeof *pblknode
)
18 /* Allocate memory for memory pool data structure */
19 if ((*mpool
= malloc(sizeof **mpool
)) == NULL
)
22 (*mpool
)->maxlogsize
= maxlogsize
;
23 (*mpool
)->minlogsize
= minlogsize
;
24 (*mpool
)->nblocks
= (*mpool
)->maxlogsize
- (*mpool
)->minlogsize
+ 1;
26 (*mpool
)->nsplits
= 0;
27 (*mpool
)->nmerges
= 0;
30 /* Allocate the actual memory of the pool */
31 if (((*mpool
)->mem
= malloc((size_t)(1 << maxlogsize
))) == NULL
) {
35 DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n" \
36 "mpool->mem = %p\tsizeof(blknode) = 0x%x\n",
42 DPRINTF(("Allocated %u bytes for pool\n", 1 << maxlogsize
));
44 /* Allocate memory for block lists */
45 if (((*mpool
)->blktable
= malloc((*mpool
)->nblocks
* sizeof *(*mpool
)->blktable
)) == NULL
) {
51 /* Initialize block lists */
52 for (i
= 0; i
< (*mpool
)->nblocks
; i
++)
53 LIST_INIT(&(*mpool
)->blktable
[i
]);
56 * Initially, before any storage has been requested,
57 * we have a single available block of length 2^maxlogsize
60 pblknode
= (*mpool
)->mem
;
61 pblknode
->ptr
= (char *)(*mpool
)->mem
+ sizeof *pblknode
;
62 /*pblknode->flags |= MP_NODE_AVAIL;*/
63 MPOOL_MAKE_AVAIL(pblknode
);
64 pblknode
->logsize
= maxlogsize
;
66 /* Insert block to the first block list */
67 LIST_INSERT_HEAD(&(*mpool
)->blktable
[0], pblknode
, next_chunk
);
69 mpool_printblks(*mpool
);
74 void *mpool_alloc(mpool_t
*mpool
, size_t blksize
)
78 blknode_t
*pavailnode
;
80 size_t i
, newpos
, size
;
84 * Total size is the sum of the user's request
85 * plus the overhead of a blknode_t data structure.
87 * Be aware for the particular scenario, when
88 * reqsize is 2^j. The allocator will return
89 * the next bigger memory chunk, leading to high
90 * internal fragmentation.
92 size
= blksize
+ sizeof *pnode
;
94 DPRINTF(("\n\n=======================================================\n\n"));
95 DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
96 blksize
, sizeof *pnode
, size
));
99 * Find the most suitable 2^j bytes block for the requested size of bytes.
100 * The condition 2^j >= size must be satisfied for the smallest possible value
101 * of j and the block must be marked as available ofcourse.
104 for (i
= 0; i
< mpool
->nblocks
; i
++) {
105 DPRINTF(("Searching block: %u\n", i
));
106 phead
= &mpool
->blktable
[i
];
107 if ((pnode
= LIST_FIRST(phead
)) != NULL
) {
108 if ((size_t)(1 << pnode
->logsize
) >= size
) {
109 LIST_FOREACH(pnode
, phead
, next_chunk
) {
110 /*if (pnode->flags & MP_NODE_AVAIL) {*/
111 if (MPOOL_IS_AVAIL(pnode
)) {
113 goto NEXT_BLOCK_LIST
;
121 /* Failure, no available block */
122 if (pavailnode
== NULL
) {
123 DPRINTF(("No available block found\n"));
126 DPRINTF(("Found block of bytes %u\n", 1 << pavailnode
->logsize
));
128 /* Is a split required ? */
130 DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
132 1 << pavailnode
->logsize
,
133 1 << (pavailnode
->logsize
- 1)));
136 * We don't need to split the chunk we just found,
137 * if one at least of the following statements is true:
139 * - `size' bytes fit exactly in the chunk
140 * - `size' bytes won't fit in the splitted chunk
141 * - `minlogsize' constraint will be violated if we split
143 * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
145 if ((size
== (size_t)(1 << pavailnode
->logsize
))
146 || (size
> (size_t)(1 << (pavailnode
->logsize
- 1)))
147 || (mpool
->minlogsize
> (pavailnode
->logsize
- 1))) {
148 DPRINTF(("No split required\n"));
149 /*pavailnode->flags &= ~MP_NODE_AVAIL; Mark as no longer available */
150 MPOOL_MAKE_USED(pavailnode
);
151 mpool_printblks(mpool
);
152 return pavailnode
->ptr
;
155 DPRINTF(("Splitting...\n"));
160 /* Remove old chunk */
161 DPRINTF(("Removing old chunk from list\n"));
162 LIST_REMOVE(pavailnode
, next_chunk
);
163 mpool_printblks(mpool
);
165 pavailnode
->logsize
--;
166 flag
= pavailnode
->flags
;
167 /*if (pavailnode->flags & MP_NODE_LR)*/
168 if (MPOOL_IS_RIGHT(pavailnode
))
169 pavailnode
->flags
|= MP_NODE_PARENT
;
171 pavailnode
->flags
&= ~MP_NODE_PARENT
;
172 /*pavailnode->flags &= ~MP_NODE_LR; Mark as left buddy */
173 MPOOL_MAKE_LEFT(pavailnode
);
175 DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode
->logsize
));
177 newpos
= mpool
->maxlogsize
- pavailnode
->logsize
;
178 DPRINTF(("Moving old chunk to new position: %u\n", newpos
));
180 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pavailnode
, next_chunk
);
181 mpool_printblks(mpool
);
184 DPRINTF(("Will add new item with bytes: %u (0x%x)\n",
185 1 << pavailnode
->logsize
,
186 1 << pavailnode
->logsize
));
187 if ((size_t)(1 << pavailnode
->logsize
) < sizeof *pnewnode
)
189 pnewnode
= (blknode_t
*)((char *)pavailnode
+ (1 << pavailnode
->logsize
));
190 pnewnode
->ptr
= (char *)pnewnode
+ sizeof *pnewnode
;
191 /*pnewnode->flags |= MP_NODE_AVAIL;*/
192 MPOOL_MAKE_AVAIL(pnewnode
);
193 /*pnewnode->flags |= MP_NODE_LR; Mark as right buddy */
194 MPOOL_MAKE_RIGHT(pnewnode
);
196 if (flag
& MP_NODE_PARENT
)
197 pnewnode
->flags
|= MP_NODE_PARENT
;
199 pnewnode
->flags
&= ~MP_NODE_PARENT
;
201 pnewnode
->logsize
= pavailnode
->logsize
;
202 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pnewnode
, next_chunk
);
203 mpool_printblks(mpool
);
209 void mpool_free(mpool_t
*mpool
, void *ptr
)
212 blknode_t
*pnode
, *pbuddy
;
215 DPRINTF(("[ Freeing ptr: %p ]\n", ptr
));
217 /* Search all nodes to find the one that points to ptr */
219 for (i
= 0; i
< mpool
->nblocks
; i
++) {
220 DPRINTF(("Searching for ptr %p in block: %u\n", ptr
, i
));
221 phead
= &mpool
->blktable
[i
];
222 LIST_FOREACH(pnode
, phead
, next_chunk
) {
223 if (pnode
->ptr
== ptr
) {
224 DPRINTF(("Found chunk at block: %u\tBlock has chunks with bytes: %u\n",
225 i
, 1 << pnode
->logsize
));
232 * Chunk isn't in our pool, this is probably bad.
234 * It means that either the user has provided an invalid
235 * pointer to free or the allocator exhibited buggy
236 * behaviour and corrupted itself.
238 * Either way, return immediately.
240 DPRINTF(("Chunk %p was not found in the pool\n", ptr
));
244 /* Are we top level ? */
245 if (pnode
->logsize
== mpool
->maxlogsize
)
248 /* Calculate possible buddy of chunk */
249 DPRINTF(("Searching for buddy of %p...\n", pnode
->ptr
));
251 /* `pnode' is a right buddy, so `pbuddy' is a left buddy */
252 if (MPOOL_IS_RIGHT(pnode
)) {
253 /* if (pnode->flags & MP_NODE_LR) {*/
254 pbuddy
= (blknode_t
*)((char *)pnode
- (1 << pnode
->logsize
));
255 if ((void *)pbuddy
< (void *)mpool
->mem
) {
256 DPRINTF(("buddy out of pool\n"));
259 if (pbuddy
->logsize
!= pnode
->logsize
)
262 /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
264 pbuddy
= (blknode_t
*)((char *)pnode
+ (1 << pnode
->logsize
));
265 if ((void *)pbuddy
> (void *)((char *)mpool
->mem
+ (1 << mpool
->maxlogsize
) - 1)) {
266 DPRINTF(("buddy out of pool\n"));
269 if (pbuddy
->logsize
!= pnode
->logsize
)
274 * If there is no buddy of `pnode' or if there is, but it's unavailable,
275 * just free `pnode' and we are done
277 /*if (pbuddy == NULL || (pbuddy != NULL && ((pbuddy->flags & MP_NODE_AVAIL) == 0))) {*/
278 if (pbuddy
== NULL
|| (pbuddy
!= NULL
&& MPOOL_IS_USED(pbuddy
))) {
279 DPRINTF(("Not found or found but unavailable\n"));
280 DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode
->ptr
));
281 /*pnode->flags |= MP_NODE_AVAIL;*/
282 MPOOL_MAKE_AVAIL(pnode
);
283 mpool_printblks(mpool
);
287 * There is a buddy, and it's available for sure. Coalesce.
290 DPRINTF(("Buddy %p exists and it's available. Coalesce\n", pbuddy
->ptr
));
294 DPRINTF(("Removing chunk %p from old position %u\n",
295 pnode
->ptr
, mpool
->maxlogsize
- pnode
->logsize
));
296 LIST_REMOVE(pnode
, next_chunk
);
297 mpool_printblks(mpool
);
300 * `pnode' is left buddy
302 /*if ((pnode->flags & MP_NODE_LR) == 0) {*/
303 if (MPOOL_IS_LEFT(pnode
)) {
304 if (pnode
->flags
& MP_NODE_PARENT
)
305 /*pnode->flags |= MP_NODE_LR;*/
306 MPOOL_MAKE_RIGHT(pnode
);
308 /*pnode->flags &= ~MP_NODE_LR;*/
309 MPOOL_MAKE_LEFT(pnode
);
311 if (pbuddy
->flags
& MP_NODE_PARENT
)
312 pnode
->flags
|= MP_NODE_PARENT
;
314 pnode
->flags
&= ~MP_NODE_PARENT
;
317 /*pnode->flags |= MP_NODE_AVAIL;*/
318 MPOOL_MAKE_AVAIL(pnode
);
320 /* Insert `pnode' to the appropriate position */
321 newpos
= mpool
->maxlogsize
- pnode
->logsize
;
322 phead
= &mpool
->blktable
[newpos
];
323 DPRINTF(("We will keep chunk %p, we will remove pbuddy %p\n",
324 pnode
->ptr
, pbuddy
->ptr
));
325 DPRINTF(("Inserting chunk %p to new position = %u\n",
326 pnode
->ptr
, mpool
->maxlogsize
- pnode
->logsize
));
327 LIST_INSERT_HEAD(phead
, pnode
, next_chunk
);
329 /* Remove `pbuddy' from the block lists */
330 DPRINTF(("Removing buddy %p\n", pbuddy
->ptr
));
331 LIST_REMOVE(pbuddy
, next_chunk
);
334 * `pbuddy' is left buddy
336 /*else if ((pbuddy->flags & MP_NODE_LR) == 0) {*/
337 else if (MPOOL_IS_LEFT(pbuddy
)) {
338 LIST_REMOVE(pbuddy
, next_chunk
);
339 if (pbuddy
->flags
& MP_NODE_PARENT
)
340 /*pbuddy->flags |= MP_NODE_LR;*/
341 MPOOL_MAKE_RIGHT(pbuddy
);
343 /*pbuddy->flags &= ~MP_NODE_LR;*/
344 MPOOL_MAKE_LEFT(pbuddy
);
346 if (pnode
->flags
& MP_NODE_PARENT
)
347 pbuddy
->flags
|= MP_NODE_PARENT
;
349 pbuddy
->flags
&= ~MP_NODE_PARENT
;
352 /*pbuddy->flags |= MP_NODE_AVAIL;*/
353 MPOOL_MAKE_AVAIL(pbuddy
);
355 /* Insert `pbuddy' to the appropriate position */
356 newpos
= mpool
->maxlogsize
- pbuddy
->logsize
;
357 phead
= &mpool
->blktable
[newpos
];
358 DPRINTF(("We will keep buddy %p, we will remove chunk %p\n",
359 pbuddy
->ptr
, pnode
->ptr
));
360 DPRINTF(("Inserting buddy %p to new position = %u\n",
361 pbuddy
->ptr
, mpool
->maxlogsize
- pbuddy
->logsize
));
362 LIST_INSERT_HEAD(phead
, pbuddy
, next_chunk
);
368 DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
369 pnode
->ptr
, pbuddy
->ptr
));
372 mpool_printblks(mpool
);
379 void mpool_destroy(mpool_t
*mpool
)
381 free(mpool
->blktable
);
386 static void mpool_printblks(const mpool_t
*mpool
)
388 const blkhead_t
*phead
;
389 const blknode_t
*pnode
;
392 for (i
= 0; i
< mpool
->nblocks
; i
++) {
393 DPRINTF(("Block (%p): %u\t", mpool
->blktable
[i
], i
));
394 phead
= &mpool
->blktable
[i
];
395 LIST_FOREACH(pnode
, phead
, next_chunk
) {
396 DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
398 (unsigned) (1 << pnode
->logsize
),
399 /*pnode->flags & MP_NODE_AVAIL ? 1 : 0,*/
400 MPOOL_IS_AVAIL(pnode
) ? 1 : 0,
401 /*pnode->flags & MP_NODE_LR ? 1 : 0,*/
402 MPOOL_IS_RIGHT(pnode
) ? 1 : 0,
403 pnode
->flags
& MP_NODE_PARENT
? 1 : 0));