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