buddy/mpool.c

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