malloc/mpool.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "mpool.h"
   5
   6 /* Function prototypes */
   7 static void mpool_printblks(const mpool_t *mpool);
   8
   9 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize)
  10 {
  11     blknode_t *pblknode;
  12     size_t i;
  13
  14     /* Validate input */
  15     if (maxlogsize < minlogsize || (unsigned)(1  << minlogsize) <= sizeof *pblknode)
  16         return MPOOL_EBADVAL;
  17
  18     /* Allocate memory for memory pool data structure */
  19     if ((*mpool = malloc(sizeof **mpool)) == NULL)
  20         return MPOOL_ENOMEM;
  21
  22     (*mpool)->maxlogsize = maxlogsize;
  23     (*mpool)->minlogsize = minlogsize;
  24     (*mpool)->nblocks = (*mpool)->maxlogsize - (*mpool)->minlogsize + 1;
  25 #ifdef MP_STATS
  26     (*mpool)->nsplits = 0;
  27     (*mpool)->nmerges = 0;
  28 #endif
  29
  30     /* Allocate the actual memory of the pool */
  31     if (((*mpool)->mem = malloc(1 << maxlogsize)) == NULL) {
  32         free(*mpool);
  33         return MPOOL_ENOMEM;
  34     }
  35     DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n" \
  36              "mpool->mem = %p\tsizeof(blknode) = 0x%x\n",
  37              (*mpool)->maxlogsize,
  38              (*mpool)->minlogsize,
  39              (*mpool)->nblocks,
  40              (*mpool)->mem,
  41              sizeof *pblknode));
  42     DPRINTF(("Allocated %u bytes for pool\n", 1 << maxlogsize));
  43
  44     /* Allocate memory for block lists */
  45     if (((*mpool)->blktable = malloc((*mpool)->nblocks * sizeof *(*mpool)->blktable)) == NULL) {
  46         free((*mpool)->mem);
  47         free(*mpool);
  48         return MPOOL_ENOMEM;
  49     }
  50
  51     /* Initialize block lists */
  52     for (i = 0; i < (*mpool)->nblocks; i++)
  53         LIST_INIT(&(*mpool)->blktable[i]);
  54
  55     /*
  56      * Initially, before any storage has been requested,
  57      * we have a single available block of length 2^maxlogsize
  58      * in blktable[0].
  59      */
  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;
  65
  66     /* Insert block to the first block list */
  67     LIST_INSERT_HEAD(&(*mpool)->blktable[0], pblknode, next_chunk);
  68
  69     mpool_printblks(*mpool);
  70
  71     return MPOOL_OK;
  72 }
  73
  74 void *mpool_alloc(mpool_t *mpool, size_t blksize)
  75 {
  76     blkhead_t *phead;
  77     blknode_t *pnode;
  78     blknode_t *pavailnode;
  79     blknode_t *pnewnode;
  80     size_t i, newpos, size;
  81     unsigned char flag;
  82
  83     /*
  84      * Total size is the sum of the user's request
  85      * plus the overhead of a blknode_t data structure.
  86      *
  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.
  91     */
  92     size = blksize + sizeof *pnode;
  93
  94     DPRINTF(("\n\n=======================================================\n\n"));
  95     DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
  96              blksize, sizeof *pnode, size));
  97
  98     /*
  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.
 102     */
 103     pavailnode = NULL;
 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 ((unsigned)(1 << pnode->logsize) >= size) {
 109                 LIST_FOREACH(pnode, phead, next_chunk) {
 110                     /*if (pnode->flags & MP_NODE_AVAIL) {*/
 111                     if (MPOOL_IS_AVAIL(pnode)) {
 112                         pavailnode = pnode;
 113                         goto NEXT_BLOCK_LIST;
 114                     }
 115                 }
 116             }
 117         }
 118     NEXT_BLOCK_LIST:;
 119     }
 120
 121     /* Failure, no available block */
 122     if (pavailnode == NULL) {
 123         DPRINTF(("No available block found\n"));
 124         return NULL;
 125     }
 126     DPRINTF(("Found block of bytes %u\n", 1 << pavailnode->logsize));
 127
 128     /* Is a split required ? */
 129 AGAIN:;
 130     DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
 131              size,
 132              1 << pavailnode->logsize,
 133              1 << (pavailnode->logsize - 1)));
 134
 135     /*
 136      * We don't need to split the chunk we just found,
 137      * if one at least of the following statements is true:
 138      *
 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
 142      *
 143      * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
 144      */
 145     if ((size == (unsigned)(1 << pavailnode->logsize))
 146         || (size > (unsigned)(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;
 153     }
 154
 155     DPRINTF(("Splitting...\n"));
 156 #ifdef MP_STATS
 157     mpool->nsplits++;
 158 #endif
 159
 160     /* Remove old chunk */
 161     DPRINTF(("Removing old chunk from list\n"));
 162     LIST_REMOVE(pavailnode, next_chunk);
 163     mpool_printblks(mpool);
 164
 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;
 170     else
 171         pavailnode->flags &= ~MP_NODE_PARENT;
 172     /*pavailnode->flags &= ~MP_NODE_LR;     Mark as left buddy */
 173     MPOOL_MAKE_LEFT(pavailnode);
 174
 175     DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode->logsize));
 176
 177     newpos = mpool->maxlogsize - pavailnode->logsize;
 178     DPRINTF(("Moving old chunk to new position: %u\n", newpos));
 179
 180     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_chunk);
 181     mpool_printblks(mpool);
 182
 183     /* Split */
 184     DPRINTF(("Will add new item with bytes: %u (0x%x)\n",
 185              1 << pavailnode->logsize,
 186              1 << pavailnode->logsize));
 187     if ((unsigned) (1 << pavailnode->logsize) < sizeof *pnewnode)
 188         return NULL;
 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);
 195
 196     if (flag & MP_NODE_PARENT)
 197         pnewnode->flags |= MP_NODE_PARENT;
 198     else
 199         pnewnode->flags &= ~MP_NODE_PARENT;
 200
 201     pnewnode->logsize = pavailnode->logsize;
 202     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_chunk);
 203     mpool_printblks(mpool);
 204
 205     goto AGAIN;
 206     /* Never reached */
 207 }
 208
 209 void mpool_free(mpool_t *mpool, void *ptr)
 210 {
 211     blkhead_t *phead;
 212     blknode_t *pnode, *pbuddy;
 213     size_t i, newpos;
 214
 215     DPRINTF(("[ Freeing ptr: %p ]\n", ptr));
 216
 217     /* Search all nodes to find the one that points to ptr */
 218     pbuddy = NULL;
 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));
 226                 goto CHUNK_FOUND;
 227             }
 228         }
 229     }
 230
 231     /*
 232      * Chunk isn't in our pool, this is probably bad.
 233      *
 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.
 237      *
 238      * Either way, return immediately.
 239      */
 240     DPRINTF(("Chunk %p was not found in the pool\n", ptr));
 241     return;
 242
 243  CHUNK_FOUND:;
 244     /* Are we top level ? */
 245     if (pnode->logsize == mpool->maxlogsize)
 246         return;
 247
 248     /* Calculate possible buddy of chunk */
 249     DPRINTF(("Searching for buddy of %p...\n", pnode->ptr));
 250
 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"));
 257             return;
 258         }
 259         if (pbuddy->logsize != pnode->logsize)
 260             pbuddy = NULL;
 261     }
 262     /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
 263     else {
 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"));
 267             return;
 268         }
 269         if (pbuddy->logsize != pnode->logsize)
 270             pbuddy = NULL;
 271     }
 272
 273     /*
 274      * If there is no buddy of `pnode' or if there is, but it's unavailable,
 275      * just free `pnode' and we are done
 276      */
 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);
 284         return;
 285     }
 286     /*
 287      * There is a buddy, and it's available for sure. Coalesce.
 288      */
 289     else {
 290         DPRINTF(("Buddy %p exists and it's available. Coalesce\n", pbuddy->ptr));
 291 #ifdef MP_STATS
 292         mpool->nmerges++;
 293 #endif
 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);
 298
 299         /*
 300          * `pnode' is left buddy
 301          */
 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);
 307             else
 308                 /*pnode->flags &= ~MP_NODE_LR;*/
 309                 MPOOL_MAKE_LEFT(pnode);
 310
 311             if (pbuddy->flags & MP_NODE_PARENT)
 312                 pnode->flags |= MP_NODE_PARENT;
 313             else
 314                 pnode->flags &= ~MP_NODE_PARENT;
 315
 316             pnode->logsize++;
 317             /*pnode->flags |= MP_NODE_AVAIL;*/
 318             MPOOL_MAKE_AVAIL(pnode);
 319
 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);
 328
 329             /* Remove `pbuddy' from the block lists */
 330             DPRINTF(("Removing buddy %p\n", pbuddy->ptr));
 331             LIST_REMOVE(pbuddy, next_chunk);
 332         }
 333         /*
 334          * `pbuddy' is left buddy
 335          */
 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);
 342             else
 343                 /*pbuddy->flags &= ~MP_NODE_LR;*/
 344                 MPOOL_MAKE_LEFT(pbuddy);
 345
 346             if (pnode->flags & MP_NODE_PARENT)
 347                 pbuddy->flags |= MP_NODE_PARENT;
 348             else
 349                 pbuddy->flags &= ~MP_NODE_PARENT;
 350
 351             pbuddy->logsize++;
 352             /*pbuddy->flags |= MP_NODE_AVAIL;*/
 353             MPOOL_MAKE_AVAIL(pbuddy);
 354
 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);
 363
 364             pnode = pbuddy;
 365         }
 366         /* Error */
 367         else {
 368             DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
 369                      pnode->ptr, pbuddy->ptr));
 370             return;
 371         }
 372         mpool_printblks(mpool);
 373
 374         goto CHUNK_FOUND;
 375         /* Never reached */
 376     }
 377 }
 378
 379 void mpool_destroy(mpool_t *mpool)
 380 {
 381     free(mpool->blktable);
 382     free(mpool->mem);
 383     free(mpool);
 384 }
 385
 386 static void mpool_printblks(const mpool_t *mpool)
 387 {
 388     const blkhead_t *phead;
 389     const blknode_t *pnode;
 390     size_t i;
 391
 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",
 397                      pnode->ptr,
 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));
 404         }
 405         DPRINTF(("\n"));
 406     }
 407 }
 408