malloc/mpool.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "mpool.h"
   5
   6 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize)
   7 {
   8     blknode_t *pblknode;
   9     size_t i;
  10
  11     /* Validate input */
  12     if (maxlogsize < minlogsize || (1  << minlogsize) <= sizeof *pblknode)
  13         return MPOOL_EBADVAL;
  14
  15     /* Allocate memory for memory pool data structure */
  16     if ((*mpool = malloc(sizeof **mpool)) == NULL)
  17         return MPOOL_ENOMEM;
  18
  19     (*mpool)->maxlogsize = maxlogsize;
  20     (*mpool)->minlogsize = minlogsize;
  21     (*mpool)->nblocks = (*mpool)->maxlogsize - (*mpool)->minlogsize + 1;
  22 #ifdef MP_STATS
  23     (*mpool)->nsplits = 0;
  24     (*mpool)->nmerges = 0;
  25 #endif
  26
  27     /* Allocate the actual memory of the pool */
  28     if (((*mpool)->mem = malloc(1 << maxlogsize)) == NULL) {
  29         free(*mpool);
  30         return MPOOL_ENOMEM;
  31     }
  32     DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n" \
  33              "mpool->mem = %p\tsizeof(blknode) = 0x%x\n",
  34              (*mpool)->maxlogsize,
  35              (*mpool)->minlogsize,
  36              (*mpool)->nblocks,
  37              (*mpool)->mem,
  38              sizeof *pblknode));
  39     DPRINTF(("Allocated %u bytes for pool\n", 1 << maxlogsize));
  40
  41     /* Allocate memory for block lists */
  42     if (((*mpool)->blktable = malloc((*mpool)->nblocks * sizeof *(*mpool)->blktable)) == NULL) {
  43         free((*mpool)->mem);
  44         free(*mpool);
  45         return MPOOL_ENOMEM;
  46     }
  47
  48     /* Initialize block lists */
  49     for (i = 0; i < (*mpool)->nblocks; i++)
  50         LIST_INIT(&(*mpool)->blktable[i]);
  51
  52     /*
  53      * Initially, before any storage has been requested,
  54      * we have a single available block of length 2^maxlogsize
  55      * in blktable[0].
  56      */
  57     pblknode = (*mpool)->mem;
  58     pblknode->ptr = (char *)(*mpool)->mem + sizeof *pblknode;
  59     /*pblknode->flags |= MP_NODE_AVAIL;*/
  60     MPOOL_MAKE_AVAIL(pblknode);
  61     pblknode->logsize = maxlogsize;
  62
  63     /* Insert block to the first block list */
  64     LIST_INSERT_HEAD(&(*mpool)->blktable[0], pblknode, next_chunk);
  65
  66     mpool_printblks(*mpool);
  67
  68     return MPOOL_OK;
  69 }
  70
  71 void *mpool_alloc(mpool_t *mpool, size_t blksize)
  72 {
  73     blkhead_t *phead;
  74     blknode_t *pnode;
  75     blknode_t *pavailnode;
  76     blknode_t *pnewnode;
  77     size_t i, newpos, size;
  78     unsigned char flag;
  79
  80     /*
  81      * Total size is the sum of the user's request
  82      * plus the overhead of a blknode_t data structure.
  83      *
  84      * Be aware for the particular scenario, when
  85      * reqsize is 2^j. The allocator will return
  86      * the next bigger memory chunk, leading to high
  87      * internal fragmentation.
  88     */
  89     size = blksize + sizeof *pnode;
  90
  91     DPRINTF(("\n\n=======================================================\n\n"));
  92     DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
  93              blksize, sizeof *pnode, size));
  94
  95     /*
  96      * Find the most suitable 2^j bytes block for the requested size of bytes.
  97      * The condition 2^j >= size must be satisfied for the smallest possible value
  98      * of j and the block must be marked as available ofcourse.
  99     */
 100     pavailnode = NULL;
 101     for (i = 0; i < mpool->nblocks; i++) {
 102         DPRINTF(("Searching block: %u\n", i));
 103         phead = &mpool->blktable[i];
 104         if ((pnode = LIST_FIRST(phead)) != NULL) {
 105             if ((unsigned)(1 << pnode->logsize) >= size) {
 106                 LIST_FOREACH(pnode, phead, next_chunk) {
 107                     /*if (pnode->flags & MP_NODE_AVAIL) {*/
 108                     if (MPOOL_IS_AVAIL(pnode)) {
 109                         pavailnode = pnode;
 110                         goto NEXT_BLOCK_LIST;
 111                     }
 112                 }
 113             }
 114         }
 115     NEXT_BLOCK_LIST:;
 116     }
 117
 118     /* Failure, no available block */
 119     if (pavailnode == NULL) {
 120         DPRINTF(("No available block found\n"));
 121         return NULL;
 122     }
 123     DPRINTF(("Found block of bytes %u\n", 1 << pavailnode->logsize));
 124
 125     /* Is a split required ? */
 126 AGAIN:;
 127     DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
 128              size,
 129              1 << pavailnode->logsize,
 130              1 << (pavailnode->logsize - 1)));
 131
 132     /*
 133      * We don't need to split the chunk we just found,
 134      * if one at least of the following statements is true:
 135      *
 136      * - `size' bytes fit exactly in the chunk
 137      * - `size' bytes won't fit in the splitted chunk
 138      * - `minlogsize' constraint will be violated if we split
 139      *
 140      * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
 141      */
 142     if ((size == (unsigned)(1 << pavailnode->logsize))
 143         || (size > (unsigned)(1 << (pavailnode->logsize - 1)))
 144         || (mpool->minlogsize > (pavailnode->logsize - 1))) {
 145         DPRINTF(("No split required\n"));
 146         /*pavailnode->flags &= ~MP_NODE_AVAIL;     Mark as no longer available */
 147         MPOOL_MAKE_USED(pavailnode);
 148         mpool_printblks(mpool);
 149         return pavailnode->ptr;
 150     }
 151
 152     DPRINTF(("Splitting...\n"));
 153 #ifdef MP_STATS
 154     mpool->nsplits++;
 155 #endif
 156
 157     /* Remove old chunk */
 158     DPRINTF(("Removing old chunk from list\n"));
 159     LIST_REMOVE(pavailnode, next_chunk);
 160     mpool_printblks(mpool);
 161
 162     pavailnode->logsize--;
 163     flag = pavailnode->flags;
 164     /*if (pavailnode->flags & MP_NODE_LR)*/
 165     if (MPOOL_IS_RIGHT(pavailnode))
 166         pavailnode->flags |= MP_NODE_PARENT;
 167     else
 168         pavailnode->flags &= ~MP_NODE_PARENT;
 169     /*pavailnode->flags &= ~MP_NODE_LR;     Mark as left buddy */
 170     MPOOL_MAKE_LEFT(pavailnode);
 171
 172     DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode->logsize));
 173
 174     newpos = mpool->maxlogsize - pavailnode->logsize;
 175     DPRINTF(("Moving old chunk to new position: %u\n", newpos));
 176
 177     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_chunk);
 178     mpool_printblks(mpool);
 179
 180     /* Split */
 181     DPRINTF(("Will add new item with bytes: %u (0x%x)\n",
 182              1 << pavailnode->logsize,
 183              1 << pavailnode->logsize));
 184     if ((unsigned) (1 << pavailnode->logsize) < sizeof *pnewnode)
 185         return NULL;
 186     pnewnode = (blknode_t *)((char *)pavailnode + (1 << pavailnode->logsize));
 187     pnewnode->ptr = (char *)pnewnode + sizeof *pnewnode;
 188     /*pnewnode->flags |= MP_NODE_AVAIL;*/
 189     MPOOL_MAKE_AVAIL(pnewnode);
 190     /*pnewnode->flags |= MP_NODE_LR;       Mark as right buddy */
 191     MPOOL_MAKE_RIGHT(pnewnode);
 192
 193     if (flag & MP_NODE_PARENT)
 194         pnewnode->flags |= MP_NODE_PARENT;
 195     else
 196         pnewnode->flags &= ~MP_NODE_PARENT;
 197
 198     pnewnode->logsize = pavailnode->logsize;
 199     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_chunk);
 200     mpool_printblks(mpool);
 201
 202     goto AGAIN;
 203     /* Never reached */
 204 }
 205
 206 void mpool_free(mpool_t *mpool, void *ptr)
 207 {
 208     blkhead_t *phead;
 209     blknode_t *pnode, *pbuddy;
 210     size_t i, newpos;
 211
 212     DPRINTF(("[ Freeing ptr: %p ]\n", ptr));
 213
 214     /* Search all nodes to find the one that points to ptr */
 215     pbuddy = NULL;
 216     for (i = 0; i < mpool->nblocks; i++) {
 217         DPRINTF(("Searching for ptr %p in block: %u\n", ptr, i));
 218         phead = &mpool->blktable[i];
 219         LIST_FOREACH(pnode, phead, next_chunk) {
 220             if (pnode->ptr == ptr) {
 221                 DPRINTF(("Found chunk at block: %u\tBlock has chunks with bytes: %u\n",
 222                          i, 1 << pnode->logsize));
 223                 goto CHUNK_FOUND;
 224             }
 225         }
 226     }
 227
 228     /*
 229      * Chunk isn't in our pool, this is probably bad.
 230      *
 231      * It means that either the user has provided an invalid
 232      * pointer to free or the allocator exhibited buggy
 233      * behaviour and corrupted itself.
 234      *
 235      * Either way, return immediately.
 236      */
 237     DPRINTF(("Chunk %p was not found in the pool\n", ptr));
 238     return;
 239
 240  CHUNK_FOUND:;
 241     /* Are we top level ? */
 242     if (pnode->logsize == mpool->maxlogsize)
 243         return;
 244
 245     /* Calculate possible buddy of chunk */
 246     DPRINTF(("Searching for buddy of %p...\n", pnode->ptr));
 247
 248     /* `pnode' is a right buddy, so `pbuddy' is a left buddy */
 249     if (MPOOL_IS_RIGHT(pnode)) {
 250         /* if (pnode->flags & MP_NODE_LR) {*/
 251         pbuddy = (blknode_t *)((char *)pnode - (1 << pnode->logsize));
 252         if ((void *)pbuddy < (void *)mpool->mem) {
 253             DPRINTF(("buddy out of pool\n"));
 254             pbuddy = NULL;
 255         }
 256         if (pbuddy->logsize != pnode->logsize)
 257             pbuddy = NULL;
 258     }
 259     /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
 260     else {
 261         pbuddy = (blknode_t *)((char *)pnode + (1 << pnode->logsize));
 262         if ((void *)pbuddy > (void *)((char *)mpool->mem + (1 << mpool->maxlogsize) - 1)) {
 263             DPRINTF(("buddy out of pool\n"));
 264             pbuddy = NULL;
 265         }
 266         if (pbuddy->logsize != pnode->logsize)
 267             pbuddy = NULL;
 268     }
 269
 270     /*
 271      * If there is no buddy of `pnode' or if there is, but it's unavailable,
 272      * just free `pnode' and we are done
 273      */
 274     /*if (pbuddy == NULL || (pbuddy != NULL && ((pbuddy->flags & MP_NODE_AVAIL) == 0))) {*/
 275     if (pbuddy == NULL || (pbuddy != NULL && MPOOL_IS_USED(pbuddy))) {
 276         DPRINTF(("Not found or found but unavailable\n"));
 277         DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode->ptr));
 278         /*pnode->flags |= MP_NODE_AVAIL;*/
 279         MPOOL_MAKE_AVAIL(pnode);
 280         mpool_printblks(mpool);
 281         return;
 282     }
 283     /*
 284      * There is a buddy, and it's available for sure. Coalesce.
 285      */
 286     else {
 287         DPRINTF(("Buddy %p exists and it's available. Coalesce\n", pbuddy->ptr));
 288 #ifdef MP_STATS
 289         mpool->nmerges++;
 290 #endif
 291         DPRINTF(("Removing chunk %p from old position %u\n",
 292                  pnode->ptr, mpool->maxlogsize - pnode->logsize));
 293         LIST_REMOVE(pnode, next_chunk);
 294         mpool_printblks(mpool);
 295
 296         /*
 297          * `pnode' is left buddy
 298          */
 299         /*if ((pnode->flags & MP_NODE_LR) == 0) {*/
 300         if (MPOOL_IS_LEFT(pnode)) {
 301             if (pnode->flags & MP_NODE_PARENT)
 302                 /*pnode->flags |= MP_NODE_LR;*/
 303                 MPOOL_MAKE_RIGHT(pnode);
 304             else
 305                 /*pnode->flags &= ~MP_NODE_LR;*/
 306                 MPOOL_MAKE_LEFT(pnode);
 307
 308             if (pbuddy->flags & MP_NODE_PARENT)
 309                 pnode->flags |= MP_NODE_PARENT;
 310             else
 311                 pnode->flags &= ~MP_NODE_PARENT;
 312
 313             pnode->logsize++;
 314             /*pnode->flags |= MP_NODE_AVAIL;*/
 315             MPOOL_MAKE_AVAIL(pnode);
 316
 317             /* Insert `pnode' to the appropriate position */
 318             newpos = mpool->maxlogsize - pnode->logsize;
 319             phead = &mpool->blktable[newpos];
 320             DPRINTF(("We will keep chunk %p, we will remove pbuddy %p\n",
 321                      pnode->ptr, pbuddy->ptr));
 322             DPRINTF(("Inserting chunk %p to new position = %u\n",
 323                      pnode->ptr, mpool->maxlogsize - pnode->logsize));
 324             LIST_INSERT_HEAD(phead, pnode, next_chunk);
 325
 326             /* Remove `pbuddy' from the block lists */
 327             DPRINTF(("Removing buddy %p\n", pbuddy->ptr));
 328             LIST_REMOVE(pbuddy, next_chunk);
 329         }
 330         /*
 331          * `pbuddy' is left buddy
 332          */
 333         /*else if ((pbuddy->flags & MP_NODE_LR) == 0) {*/
 334         else if (MPOOL_IS_LEFT(pbuddy)) {
 335             LIST_REMOVE(pbuddy, next_chunk);
 336             if (pbuddy->flags & MP_NODE_PARENT)
 337                 /*pbuddy->flags |= MP_NODE_LR;*/
 338                 MPOOL_MAKE_RIGHT(pbuddy);
 339             else
 340                 /*pbuddy->flags &= ~MP_NODE_LR;*/
 341                 MPOOL_MAKE_LEFT(pbuddy);
 342
 343             if (pnode->flags & MP_NODE_PARENT)
 344                 pbuddy->flags |= MP_NODE_PARENT;
 345             else
 346                 pbuddy->flags &= ~MP_NODE_PARENT;
 347
 348             pbuddy->logsize++;
 349             /*pbuddy->flags |= MP_NODE_AVAIL;*/
 350             MPOOL_MAKE_AVAIL(pbuddy);
 351
 352             /* Insert `pbuddy' to the appropriate position */
 353             newpos = mpool->maxlogsize - pbuddy->logsize;
 354             phead = &mpool->blktable[newpos];
 355             DPRINTF(("We will keep buddy %p, we will remove chunk %p\n",
 356                      pbuddy->ptr, pnode->ptr));
 357             DPRINTF(("Inserting buddy %p to new position = %u\n",
 358                      pbuddy->ptr, mpool->maxlogsize - pbuddy->logsize));
 359             LIST_INSERT_HEAD(phead, pbuddy, next_chunk);
 360
 361             pnode = pbuddy;
 362         }
 363         /* Error */
 364         else {
 365             DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
 366                      pnode->ptr, pbuddy->ptr));
 367             return;
 368         }
 369         mpool_printblks(mpool);
 370
 371         goto CHUNK_FOUND;
 372         /* Never reached */
 373     }
 374 }
 375
 376 void mpool_destroy(mpool_t *mpool)
 377 {
 378     free(mpool->blktable);
 379     free(mpool->mem);
 380     free(mpool);
 381 }
 382
 383 void mpool_printblks(const mpool_t *mpool)
 384 {
 385     const blkhead_t *phead;
 386     const blknode_t *pnode;
 387     size_t i;
 388
 389     for (i = 0; i < mpool->nblocks; i++) {
 390         DPRINTF(("Block: %u\t", i));
 391
 392         phead = &mpool->blktable[i];
 393         LIST_FOREACH(pnode, phead, next_chunk) {
 394             DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
 395                      pnode->ptr,
 396                      (unsigned) (1 << pnode->logsize),
 397                      /*pnode->flags & MP_NODE_AVAIL ? 1 : 0,*/
 398                      MPOOL_IS_AVAIL(pnode) ? 1 : 0,
 399                      /*pnode->flags & MP_NODE_LR ? 1 : 0,*/
 400                      MPOOL_IS_LEFT(pnode) ? 1 : 0,
 401                      pnode->flags & MP_NODE_PARENT ? 1 : 0));
 402         }
 403         DPRINTF(("\n"));
 404     }
 405 }
 406