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     unsigned int 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 appropriate 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 size;
  78     unsigned int i, newpos;
  79     unsigned char flag;
  80
  81     /*
  82      * Total size is the sum of the user's request
  83      * plus the overhead of a blknode_t data structure
  84     */
  85     size = blksize + sizeof *pnode;
  86
  87     DPRINTF(("\n\n=======================================================\n\n"));
  88     DPRINTF(("Searching for block of bytes: %u + %u = %u\n",
  89              blksize, sizeof *pnode, size));
  90
  91     /*
  92      * Find the most suitable 2^j bytes block for the requested size of bytes.
  93      * The condition 2^j >= size must be satisfied for the smallest possible value
  94      * of j and the block must be marked as available ofcourse.
  95     */
  96     pavailnode = NULL;
  97     for (i = 0; i < mpool->nblocks; i++) {
  98         DPRINTF(("Searcing block: %u\n", i));
  99         phead = &mpool->blktable[i];
 100         if ((pnode = LIST_FIRST(phead)) != NULL) {
 101             if ((unsigned)(1 << pnode->logsize) >= size) {
 102                 LIST_FOREACH(pnode, phead, next_chunk) {
 103                     /*if (pnode->flags & MP_NODE_AVAIL) {*/
 104                     if (MPOOL_IS_AVAIL(pnode)) {
 105                         pavailnode = pnode;
 106                         goto NEXT_CHUNK;
 107                     }
 108                 }
 109             }
 110         }
 111     NEXT_CHUNK:;
 112     }
 113
 114     /* Failure, no available block */
 115     if (pavailnode == NULL) {
 116         DPRINTF(("No available block found\n"));
 117         return NULL;
 118     }
 119     DPRINTF(("Found block of bytes %u\n", 1 << pavailnode->logsize));
 120
 121     /* Is a split required ? */
 122 AGAIN:;
 123     DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
 124              size,
 125              1 << pavailnode->logsize,
 126              1 << (pavailnode->logsize - 1)));
 127
 128     /*
 129      * We don't need to split the chunk we just found,
 130      * if one the following statements is true:
 131      *
 132      * - `size' bytes fit exactly in the chunk
 133      * - `size' bytes won't fit in the splitted chunk
 134      * - `minlogsize' constraint will be violated if we split
 135      *
 136      * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
 137      */
 138     if ((size == (unsigned)(1 << pavailnode->logsize))
 139         || (size > (unsigned)(1 << (pavailnode->logsize - 1)))
 140         || (mpool->minlogsize > (pavailnode->logsize - 1))) {
 141         DPRINTF(("No split required\n"));
 142         /*pavailnode->flags &= ~MP_NODE_AVAIL;     Mark as no longer available */
 143         MPOOL_MAKE_USED(pavailnode);
 144         mpool_printblks(mpool);
 145         return pavailnode->ptr;
 146     }
 147
 148     DPRINTF(("Splitting...\n"));
 149 #ifdef MP_STATS
 150     mpool->nsplits++;    /* FIXME: print a message if it overflows */
 151 #endif
 152
 153     /* Remove old block */
 154     DPRINTF(("Removing old chunk from list\n"));
 155     LIST_REMOVE(pavailnode, next_chunk);
 156     mpool_printblks(mpool);
 157
 158     pavailnode->logsize--;
 159     flag = pavailnode->flags;
 160     /*if (pavailnode->flags & MP_NODE_LR)*/
 161     if (MPOOL_IS_RIGHT(pavailnode))
 162         pavailnode->flags |= MP_NODE_PARENT;
 163     else
 164         pavailnode->flags &= ~MP_NODE_PARENT;
 165     /*pavailnode->flags &= ~MP_NODE_LR;     Mark as left buddy */
 166     MPOOL_MAKE_LEFT(pavailnode);
 167
 168     DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode->logsize));
 169
 170     newpos = mpool->maxlogsize - pavailnode->logsize;
 171     DPRINTF(("Moving old chunk to new position: %u\n", newpos));
 172
 173     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_chunk);
 174     mpool_printblks(mpool);
 175
 176     /* Split */
 177     DPRINTF(("Will add new item with bytes: %u (0x%x)\n", 1 << pavailnode->logsize, 1 << pavailnode->logsize));
 178     if ((unsigned) (1 << pavailnode->logsize) < sizeof *pnewnode)
 179         return NULL;
 180     pnewnode = (blknode_t *)((char *)pavailnode + (1 << pavailnode->logsize));
 181     pnewnode->ptr = (char *)pnewnode + sizeof *pnewnode;
 182     /*pnewnode->flags |= MP_NODE_AVAIL;*/
 183     MPOOL_MAKE_AVAIL(pnewnode);
 184     /*pnewnode->flags |= MP_NODE_LR;       Mark as right buddy */
 185     MPOOL_MAKE_RIGHT(pnewnode);
 186
 187     if (flag & MP_NODE_PARENT)
 188         pnewnode->flags |= MP_NODE_PARENT;
 189     else
 190         pnewnode->flags &= ~MP_NODE_PARENT;
 191
 192     pnewnode->logsize = pavailnode->logsize;
 193     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_chunk);
 194     mpool_printblks(mpool);
 195
 196     goto AGAIN;
 197     /* Never reached */
 198 }
 199
 200 void mpool_free(mpool_t *mpool, void *ptr)
 201 {
 202     blkhead_t *phead;
 203     blknode_t *pnode, *pbuddy;
 204     unsigned int i, newpos;
 205
 206     DPRINTF(("[ Freeing ptr: %p ]\n", ptr));
 207
 208     /* Search all nodes to find the one that points to ptr */
 209     pbuddy = NULL;
 210     for (i = 0; i < mpool->nblocks; i++) {
 211         DPRINTF(("Searching for ptr %p in block: %u\n", ptr, i));
 212         phead = &mpool->blktable[i];
 213         LIST_FOREACH(pnode, phead, next_chunk) {
 214             if (pnode->ptr == ptr) {
 215                 DPRINTF(("Found chunk at block: %u\tBlock has chunks with bytes: %u\n",
 216                          i, 1 << pnode->logsize));
 217                 goto CHUNK_FOUND;
 218             }
 219         }
 220     }
 221
 222     /*
 223      * Chunk isn't in our pool, this is probably bad.
 224      * Return immediately
 225      */
 226     DPRINTF(("Chunk %p was not found in the pool\n", ptr));
 227     return;
 228
 229  CHUNK_FOUND:;
 230     /* Are we top level ? */
 231     if (pnode->logsize == mpool->maxlogsize) {
 232         /*pnode->flags |= MP_NODE_AVAIL;*/
 233         MPOOL_MAKE_AVAIL(pnode);
 234         return;
 235     }
 236
 237     /* Calculate possible buddy of chunk */
 238     DPRINTF(("Searching for buddy of %p...\n", pnode->ptr));
 239
 240     /* `pnode' is a right buddy, so `pbuddy' is a left buddy */
 241     if (MPOOL_IS_RIGHT(pnode)) {
 242         /* if (pnode->flags & MP_NODE_LR) {*/
 243         pbuddy = (blknode_t *)((char *)pnode - (1 << pnode->logsize));
 244         if ((void *)pbuddy < (void *)mpool->mem) {
 245             DPRINTF(("buddy out of pool\n"));
 246             pbuddy = NULL;
 247         }
 248         if (pbuddy->logsize != pnode->logsize)
 249             pbuddy = NULL;
 250     }
 251     /* `pnode' is a left buddy, so `pbuddy' is a right buddy */
 252     else {
 253         pbuddy = (blknode_t *)((char *)pnode + (1 << pnode->logsize));
 254         if ((void *)pbuddy > (void *)((char *)mpool->mem + (1 << mpool->maxlogsize) - 1)) {
 255             DPRINTF(("buddy out of pool\n"));
 256             pbuddy = NULL;
 257         }
 258         if (pbuddy->logsize != pnode->logsize)
 259             pbuddy = NULL;
 260     }
 261
 262     /*
 263      * If there is no buddy of `pnode' or if there is, but it's unavailable,
 264      * just free `pnode' and we are done
 265      */
 266     /*if (pbuddy == NULL || (pbuddy != NULL && ((pbuddy->flags & MP_NODE_AVAIL) == 0))) {*/
 267     if (pbuddy == NULL || (pbuddy != NULL && MPOOL_IS_USED(pbuddy))) {
 268         DPRINTF(("Not found or found but unavailable\n"));
 269         DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode->ptr));
 270         /*pnode->flags |= MP_NODE_AVAIL;*/
 271         MPOOL_MAKE_AVAIL(pnode);
 272         mpool_printblks(mpool);
 273         return;
 274     }
 275     /*
 276      * There is a buddy, and it's available for sure. Coalesce.
 277      */
 278     else {
 279         DPRINTF(("Buddy %p exists and it's available. Coalesce\n", pbuddy->ptr));
 280 #ifdef MP_STATS
 281         mpool->nmerges++;
 282 #endif
 283         DPRINTF(("Removing chunk %p from old position %u\n",
 284                  pnode->ptr, mpool->maxlogsize - pnode->logsize));
 285         LIST_REMOVE(pnode, next_chunk);
 286         mpool_printblks(mpool);
 287
 288         /*
 289          * `pnode' is left buddy
 290          */
 291         /*if ((pnode->flags & MP_NODE_LR) == 0) {*/
 292         if (MPOOL_IS_LEFT(pnode)) {
 293             if (pnode->flags & MP_NODE_PARENT)
 294                 /*pnode->flags |= MP_NODE_LR;*/
 295                 MPOOL_MAKE_RIGHT(pnode);
 296             else
 297                 /*pnode->flags &= ~MP_NODE_LR;*/
 298                 MPOOL_MAKE_LEFT(pnode);
 299
 300             if (pbuddy->flags & MP_NODE_PARENT)
 301                 pnode->flags |= MP_NODE_PARENT;
 302             else
 303                 pnode->flags &= ~MP_NODE_PARENT;
 304
 305             pnode->logsize++;
 306             /*pnode->flags |= MP_NODE_AVAIL;*/
 307             MPOOL_MAKE_AVAIL(pnode);
 308
 309             /* Insert `pnode' to the appropriate position */
 310             newpos = mpool->maxlogsize - pnode->logsize;
 311             phead = &mpool->blktable[newpos];
 312             DPRINTF(("We will keep chunk %p, we will remove pbuddy %p\n",
 313                      pnode->ptr, pbuddy->ptr));
 314             DPRINTF(("Inserting chunk %p to new position = %u\n",
 315                      pnode->ptr, mpool->maxlogsize - pnode->logsize));
 316             LIST_INSERT_HEAD(phead, pnode, next_chunk);
 317
 318             /* Remove `pbuddy' from the block lists */
 319             DPRINTF(("Removing buddy %p\n", pbuddy->ptr));
 320             LIST_REMOVE(pbuddy, next_chunk);
 321         }
 322         /*
 323          * `pbuddy' is left buddy
 324          */
 325         /*else if ((pbuddy->flags & MP_NODE_LR) == 0) {*/
 326         else if (MPOOL_IS_LEFT(pbuddy)) {
 327             LIST_REMOVE(pbuddy, next_chunk);
 328             if (pbuddy->flags & MP_NODE_PARENT)
 329                 /*pbuddy->flags |= MP_NODE_LR;*/
 330                 MPOOL_MAKE_RIGHT(pbuddy);
 331             else
 332                 /*pbuddy->flags &= ~MP_NODE_LR;*/
 333                 MPOOL_MAKE_LEFT(pbuddy);
 334
 335             if (pnode->flags & MP_NODE_PARENT)
 336                 pbuddy->flags |= MP_NODE_PARENT;
 337             else
 338                 pbuddy->flags &= ~MP_NODE_PARENT;
 339
 340             pbuddy->logsize++;
 341             /*pbuddy->flags |= MP_NODE_AVAIL;*/
 342             MPOOL_MAKE_AVAIL(pbuddy);
 343
 344             /* Insert `pbuddy' to the appropriate position */
 345             newpos = mpool->maxlogsize - pbuddy->logsize;
 346             phead = &mpool->blktable[newpos];
 347             DPRINTF(("We will keep buddy %p, we will remove chunk %p\n",
 348                      pbuddy->ptr, pnode->ptr));
 349             DPRINTF(("Inserting buddy %p to new position = %u\n",
 350                      pbuddy->ptr, mpool->maxlogsize - pbuddy->logsize));
 351             LIST_INSERT_HEAD(phead, pbuddy, next_chunk);
 352
 353             pnode = pbuddy;
 354         }
 355         /* Error */
 356         else {
 357             DPRINTF(("Chunk %p and buddy %p have wrong LR relation",
 358                      pnode->ptr, pbuddy->ptr));
 359             return;
 360         }
 361         mpool_printblks(mpool);
 362
 363         goto CHUNK_FOUND;
 364     }
 365 }
 366
 367 void mpool_destroy(mpool_t *mpool)
 368 {
 369     free(mpool->blktable);
 370     free(mpool->mem);
 371     free(mpool);
 372 }
 373
 374 void mpool_printblks(const mpool_t *mpool)
 375 {
 376     const blkhead_t *phead;
 377     const blknode_t *pnode;
 378     unsigned int i;
 379
 380     for (i = 0; i < mpool->nblocks; i++) {
 381         DPRINTF(("Block: %u\t", i));
 382
 383         phead = &mpool->blktable[i];
 384         LIST_FOREACH(pnode, phead, next_chunk) {
 385             DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
 386                      pnode->ptr,
 387                      (unsigned) (1 << pnode->logsize),
 388                      /*pnode->flags & MP_NODE_AVAIL ? 1 : 0,*/
 389                      MPOOL_IS_AVAIL(pnode) ? 1 : 0,
 390                      /*pnode->flags & MP_NODE_LR ? 1 : 0,*/
 391                      MPOOL_IS_LEFT(pnode) ? 1 : 0,
 392                      pnode->flags & MP_NODE_PARENT ? 1 : 0));
 393         }
 394         DPRINTF(("\n"));
 395     }
 396 }
 397
 398 void mpool_stat_get_nodes(const mpool_t *mpool, size_t *avail, size_t *used)
 399 {
 400     const blkhead_t *phead;
 401     const blknode_t *pnode;
 402     unsigned int i;
 403
 404     *avail = 0;
 405     *used = 0;
 406     for (i = 0; i < mpool->nblocks; i++) {
 407         phead = &mpool->blktable[i];
 408         LIST_FOREACH(pnode, phead, next_chunk) {
 409             /*if (pnode->flags & MP_NODE_AVAIL)*/
 410             if (MPOOL_IS_AVAIL(pnode))
 411                 (*avail)++;
 412             else
 413                 (*used)++;
 414         }
 415     }
 416 }
 417
 418 void mpool_stat_get_bytes(const mpool_t *mpool, size_t *avail, size_t *used)
 419 {
 420     const blkhead_t *phead;
 421     const blknode_t *pnode;
 422     unsigned int i;
 423
 424     *avail = 0;
 425     *used = 0;
 426     for (i = 0; i < mpool->nblocks; i++) {
 427         phead = &mpool->blktable[i];
 428         LIST_FOREACH(pnode, phead, next_chunk) {
 429             /*if (pnode->flags & MP_NODE_AVAIL)*/
 430             if (MPOOL_IS_AVAIL(pnode))
 431                 *avail += 1 << pnode->logsize;
 432             else
 433                 *used += 1 << pnode->logsize;
 434         }
 435     }
 436 }
 437
 438 size_t mpool_stat_get_blocks(const mpool_t *mpool)
 439 {
 440     return mpool->nblocks;
 441 }
 442
 443 size_t mpool_stat_get_block_length(const mpool_t *mpool, size_t pos)
 444 {
 445     const blknode_t *pnode;
 446     size_t length;
 447
 448     if (pos >= mpool->nblocks)
 449         return 0;    /* FIXME: Better error handling */
 450
 451     length = 0;
 452     LIST_FOREACH(pnode, &mpool->blktable[pos], next_chunk)
 453         length++;
 454
 455     return length;
 456 }
 457
 458 #ifdef MP_STATS
 459 size_t mpool_stat_get_splits(const mpool_t *mpool)
 460 {
 461     return mpool->nsplits;
 462 }
 463
 464 size_t mpool_stat_get_merges(const mpool_t *mpool)
 465 {
 466     return mpool->nmerges;
 467 }
 468 #endif
 469