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