4 #include <time.h> /* for time() in srand() */
8 mpret_t
mpool_init(mpool_t
**mpool
, size_t maxlogsize
, size_t minlogsize
)
14 if (maxlogsize
< minlogsize
)
17 /* Allocate memory for memory pool data structure */
18 if ((*mpool
= malloc(sizeof **mpool
)) == NULL
)
21 (*mpool
)->maxlogsize
= maxlogsize
;
22 (*mpool
)->minlogsize
= minlogsize
;
23 (*mpool
)->nblocks
= (*mpool
)->maxlogsize
- (*mpool
)->minlogsize
+ 1;
25 (*mpool
)->nsplits
= 0;
26 (*mpool
)->nmerges
= 0;
29 /* Allocate the actual memory of the pool */
30 DPRINTF(("Allocating %u bytes for pool\n", 1 << maxlogsize
));
31 DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n",
35 if (((*mpool
)->mem
= malloc(1 << maxlogsize
)) == NULL
) {
40 /* Allocate memory for block lists */
41 if (((*mpool
)->blktable
= malloc((*mpool
)->nblocks
* sizeof *(*mpool
)->blktable
)) == NULL
) {
47 /* Initialize block lists */
48 for (i
= 0; i
< (*mpool
)->nblocks
; i
++)
49 LIST_INIT(&(*mpool
)->blktable
[i
]);
52 * Initially, before any storage has been requested,
53 * we have a single available block of length 2^maxlogsize
56 if ((pblknode
= malloc(sizeof *pblknode
)) == NULL
) {
57 free((*mpool
)->blktable
);
62 pblknode
->ptr
= (*mpool
)->mem
;
63 pblknode
->flags
|= MP_NODE_AVAIL
; /* Mark as available */
64 pblknode
->logsize
= maxlogsize
;
66 LIST_INSERT_HEAD(&(*mpool
)->blktable
[0], pblknode
, next_block
);
68 mpool_printblks(*mpool
);
73 void *mpool_alloc(mpool_t
*mpool
, size_t size
)
77 blknode_t
*pavailnode
;
79 unsigned int i
, newpos
;
82 DPRINTF(("\n\n=======================================================\n\n"));
83 DPRINTF(("Searching for block of bytes: %u\n", size
));
86 * Find the most suitable 2^j bytes block for the requested size of bytes.
87 * The condition 2^j >= size must be satisfied for the smallest possible value
88 * of j and the block must be marked as available ofcourse.
91 for (i
= 0; i
< mpool
->nblocks
; i
++) {
92 DPRINTF(("Searcing block: %u\n", i
));
93 phead
= &mpool
->blktable
[i
];
94 if ((pnode
= LIST_FIRST(phead
)) != NULL
) {
95 if ((unsigned)(1 << pnode
->logsize
) >= size
) {
96 LIST_FOREACH(pnode
, phead
, next_block
) {
97 if (pnode
->flags
& MP_NODE_AVAIL
) {
107 /* Failure, no available block */
108 if (pavailnode
== NULL
) {
109 DPRINTF(("No available block found\n"));
112 DPRINTF(("Found block of bytes %u\n", 1 << pavailnode
->logsize
));
114 /* Is a split required ? */
116 DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
118 1 << pavailnode
->logsize
,
119 1 << (pavailnode
->logsize
- 1)));
122 * We don't need to split the chunk we just found,
123 * if one the following statements is true:
125 * - `size' bytes fit exactly in the chunk
126 * - `size' bytes won't fit in the divided chunk
127 * - `minlogsize' constraint will be violated if we split
129 * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
131 if ((size
== (unsigned)(1 << pavailnode
->logsize
))
132 || (size
> (unsigned)(1 << (pavailnode
->logsize
- 1)))
133 || (mpool
->minlogsize
> (pavailnode
->logsize
- 1))) {
134 DPRINTF(("No split required\n"));
135 pavailnode
->flags
&= ~MP_NODE_AVAIL
; /* Mark as no longer available */
136 mpool_printblks(mpool
);
137 return pavailnode
->ptr
;
140 DPRINTF(("Splitting...\n"));
142 mpool
->nsplits
++; /* FIXME: print a message if it overflows */
145 /* Remove old block */
146 DPRINTF(("Removing old chunk from list\n"));
147 LIST_REMOVE(pavailnode
, next_block
);
148 mpool_printblks(mpool
);
149 pavailnode
->logsize
--;
150 flag
= pavailnode
->flags
;
151 if (pavailnode
->flags
& MP_NODE_LR
)
152 pavailnode
->flags
|= MP_NODE_PARENT
;
154 pavailnode
->flags
&= ~MP_NODE_PARENT
;
155 pavailnode
->flags
&= ~MP_NODE_LR
; /* Mark as left buddy */
157 DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode
->logsize
));
158 DPRINTF(("Moving old chunk to new position\n"));
159 newpos
= mpool
->nblocks
- pavailnode
->logsize
;
160 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pavailnode
, next_block
);
161 mpool_printblks(mpool
);
164 DPRINTF(("Will add new item with bytes: %u\n", 1 << pavailnode
->logsize
));
165 if ((pnewnode
= malloc(sizeof *pnewnode
)) == NULL
)
167 pnewnode
->ptr
= (char *)pavailnode
->ptr
+ (1 << pavailnode
->logsize
);
168 pnewnode
->flags
|= MP_NODE_AVAIL
; /* Mark as available */
169 pnewnode
->flags
|= MP_NODE_LR
; /* Mark as right buddy */
171 if (flag
& MP_NODE_PARENT
)
172 pnewnode
->flags
|= MP_NODE_PARENT
;
174 pnewnode
->flags
&= ~MP_NODE_PARENT
;
176 pnewnode
->logsize
= pavailnode
->logsize
;
177 LIST_INSERT_HEAD(&mpool
->blktable
[newpos
], pnewnode
, next_block
);
178 mpool_printblks(mpool
);
184 void mpool_free(mpool_t
*mpool
, void *ptr
)
187 blknode_t
*pnode
, *pbuddy
;
188 unsigned int i
, newpos
;
191 DPRINTF(("Freeing ptr: %p\n", ptr
));
193 /* Search all nodes to find the one that points to ptr */
194 for (i
= 0; i
< mpool
->nblocks
; i
++) {
195 DPRINTF(("Searching for ptr %p in block: %u\n", ptr
, i
));
196 phead
= &mpool
->blktable
[i
];
197 LIST_FOREACH(pnode
, phead
, next_block
) {
198 if (pnode
->ptr
== ptr
) {
199 DPRINTF(("Found chunk at block: %u\tBlock has chunks with bytes: %u\n",
200 i
, 1 << pnode
->logsize
));
207 if (pnode
->logsize
== mpool
->maxlogsize
) {
208 pnode
->flags
|= MP_NODE_AVAIL
;
212 /* Calculate possible buddy of chunk */
213 if (pnode
->flags
& MP_NODE_LR
)
214 buddyptr
= (char *)pnode
->ptr
- (1 << pnode
->logsize
);
216 buddyptr
= (char *)pnode
->ptr
+ (1 << pnode
->logsize
);
219 * Search buddy node with address `buddyptr'.
220 * If there is indeed a buddy of `pnode', it will be in
221 * the same linked list with the latter.
223 * NOTE: nodes that belong to the same linked list,
224 * point to memory chunks with the same size.
226 DPRINTF(("Chunk: %p\tPossible buddy at: %p\n", pnode
->ptr
, buddyptr
));
227 DPRINTF(("Searching for node with address: %p\n", buddyptr
));
229 LIST_FOREACH(pbuddy
, phead
, next_block
) {
230 if (pbuddy
->ptr
== buddyptr
) {
231 DPRINTF(("Buddy found\n"));
237 * If there is no buddy of `pnode' or if there is, but it's unavailable,
238 * just free `pnode' and we are done
240 if (pbuddy
== NULL
|| (pbuddy
!= NULL
&& ((pbuddy
->flags
& MP_NODE_AVAIL
) == 0))) {
241 DPRINTF(("Not found or found but unavailable\n"));
242 DPRINTF(("Freeing chunk (marking it as available)\n"));
243 pnode
->flags
|= MP_NODE_AVAIL
;
244 mpool_printblks(mpool
);
248 * There is a buddy, and it's available for sure. Coalesce.
250 * So now we have the chunk we were told to free (`pnode'), and
251 * it's buddy (`pbuddy').
253 * pnode will become the parent, by updating its member structures,
254 * such as logsize and flags (availability, LR buddiness, and inheritance)
255 * and pbuddy will be free'd() for real.
259 DPRINTF(("Buddy exists and it's available. Coalesce\n"));
263 DPRINTF(("Removing chunk from old position (so as to reposition it)\n"));
264 LIST_REMOVE(pnode
, next_block
);
265 mpool_printblks(mpool
);
267 pnode
->flags
|= MP_NODE_AVAIL
; /* Mark as available */
269 /* `pnode' is left buddy */
270 if ((pnode
->flags
& MP_NODE_LR
) == 0) {
271 if (pnode
->flags
& MP_NODE_PARENT
)
272 pnode
->flags
|= MP_NODE_LR
;
274 pnode
->flags
&= ~MP_NODE_LR
;
276 if (pbuddy
->flags
& MP_NODE_PARENT
)
277 pnode
->flags
|= MP_NODE_PARENT
;
279 pnode
->flags
&= ~MP_NODE_PARENT
;
282 /* `pbuddy' is left buddy */
283 if ((pbuddy
->flags
& MP_NODE_LR
) == 0) {
284 if (pbuddy
->flags
& MP_NODE_PARENT
)
285 pnode
->flags
|= MP_NODE_LR
;
287 pnode
->flags
&= ~MP_NODE_LR
;
289 DPRINTF(("Adjusting... pnode->ptr = pbuddy->ptr\n"));
290 pnode
->ptr
= pbuddy
->ptr
;
293 newpos
= mpool
->nblocks
- pnode
->logsize
;
294 phead
= &mpool
->blktable
[newpos
];
296 DPRINTF(("Inserting chunk to new position\n"));
297 LIST_INSERT_HEAD(phead
, pnode
, next_block
);
298 mpool_printblks(mpool
);
300 DPRINTF(("Removing buddy\n"));
301 LIST_REMOVE(pbuddy
, next_block
);
303 mpool_printblks(mpool
);
308 void mpool_destroy(mpool_t
*mpool
)
310 const blkhead_t
*phead
;
314 /* Free all nodes in all block lists */
315 for (i
= 0; i
< mpool
->nblocks
; i
++) {
316 phead
= &mpool
->blktable
[i
];
317 while ((pnode
= LIST_FIRST(phead
)) != NULL
) {
318 LIST_REMOVE(pnode
, next_block
);
323 free(mpool
->blktable
);
328 void mpool_printblks(const mpool_t
*mpool
)
330 const blkhead_t
*phead
;
331 const blknode_t
*pnode
;
334 for (i
= 0; i
< mpool
->nblocks
; i
++) {
335 DPRINTF(("Block: %u\t", i
));
337 phead
= &mpool
->blktable
[i
];
338 LIST_FOREACH(pnode
, phead
, next_block
) {
339 DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
341 (unsigned) (1 << pnode
->logsize
),
342 pnode
->flags
& MP_NODE_AVAIL
? 1 : 0,
343 pnode
->flags
& MP_NODE_LR
? 1 : 0,
344 pnode
->flags
& MP_NODE_PARENT
? 1 : 0));
351 void mpool_stat_get_nodes(const mpool_t
*mpool
, size_t *avail
, size_t *used
)
353 const blkhead_t
*phead
;
354 const blknode_t
*pnode
;
359 for (i
= 0; i
< mpool
->nblocks
; i
++) {
360 phead
= &mpool
->blktable
[i
];
361 LIST_FOREACH(pnode
, phead
, next_block
) {
362 if (pnode
->flags
& MP_NODE_AVAIL
)
370 void mpool_stat_get_bytes(const mpool_t
*mpool
, size_t *avail
, size_t *used
)
372 const blkhead_t
*phead
;
373 const blknode_t
*pnode
;
378 for (i
= 0; i
< mpool
->nblocks
; i
++) {
379 phead
= &mpool
->blktable
[i
];
380 LIST_FOREACH(pnode
, phead
, next_block
) {
381 if (pnode
->flags
& MP_NODE_AVAIL
)
382 *avail
+= 1 << pnode
->logsize
;
384 *used
+= 1 << pnode
->logsize
;
390 size_t mpool_stat_get_splits(const mpool_t
*mpool
)
392 return mpool
->nsplits
;
395 size_t mpool_stat_get_merges(const mpool_t
*mpool
)
397 return mpool
->nmerges
;
405 size_t an
= 0, un
= 0, ab
= 0, ub
= 0, me
= 0, sp
= 0;
406 unsigned int i
, j
, S
;
410 if (mpool_init(&mpool
, 12, 1) == MP_ENOMEM
) {
411 fprintf(stderr
, "Not enough memory\n");
415 for (i
= 0; i
< 1000; i
++) {
416 if ((p
[i
] = mpool_alloc(mpool
, S
= (1 << ((rand() % 5))))) == NULL
)
419 /*memset(p[i], 0, S);*/;
423 for (j
= 0; j
< i
; j
++) {
424 mpool_free(mpool
, p
[j
]);
427 mpool_stat_get_nodes(mpool
, &an
, &un
);
428 mpool_stat_get_bytes(mpool
, &ab
, &ub
);
429 me
= mpool_stat_get_merges(mpool
);
430 sp
= mpool_stat_get_splits(mpool
);
431 DPRINTF(("avail nodes = %u\tused nodes = %u\tfree(%%) = %f\n", an
, un
, 100.0 * an
/ (an
+ un
)));
432 DPRINTF(("avail bytes = %u\tused bytes = %u\tfree(%%) = %f\n", ab
, ub
, 100.0 * ab
/ (ab
+ ub
)));
433 DPRINTF(("splits = %u\tmerges = %u\n", sp
, me
));
435 mpool_destroy(mpool
);