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         MPOOL_MARK_PARENT(pavailnode);
 180     else
 181         MPOOL_MARK_NOTPARENT(pavailnode);
 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                      MPOOL_GET_RIGHT_BUDDY_OF(pavailnode),
 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_OF(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_OF(pnode);
 270         if ((void *)pbuddy >
 271             (void *)((char *)mpool->mem + (1 << mpool->maxlogsize) - 1)) {
 272             DPRINTF(("buddy out of pool\n"));
 273             return;
 274         }
 275     }
 276
 277     /* Buddies must be of the same size */
 278     if (pbuddy->logsize != pnode->logsize)
 279         pbuddy = NULL;
 280
 281     /*
 282      * If there is no buddy of `pnode' or if there is, but it's unavailable,
 283      * just free `pnode' and we are done.
 284      */
 285     if (pbuddy == NULL || (pbuddy != NULL && MPOOL_IS_USED(pbuddy))) {
 286         DPRINTF(("Not found or found but unavailable\n"));
 287         DPRINTF(("Freeing chunk %p (marking it as available)\n", pnode->ptr));
 288         MPOOL_MARK_AVAIL(pnode);
 289         mpool_printblks(mpool);
 290         return;
 291     }
 292     /*
 293      * There is a buddy, and it's available for sure. Coalesce.
 294      */
 295     else {
 296         DPRINTF(("Buddy %p exists and it's available. Coalesce.\n",
 297                  pbuddy->ptr));
 298 #ifdef MPOOL_STATS
 299         mpool->nmerges++;
 300 #endif
 301         /* Remove `pnode' and `pbuddy' from block lists */
 302         DPRINTF(("Removing chunk %p and buddy %p from old position %u\n",
 303                  pnode->ptr, pbuddy->ptr, mpool->maxlogsize - pnode->logsize));
 304         LIST_REMOVE(pnode, next_chunk);
 305         LIST_REMOVE(pbuddy, next_chunk);
 306         mpool_printblks(mpool);
 307
 308         /* Update flags */
 309         if (MPOOL_IS_LEFT(pnode)) {
 310             if (MPOOL_IS_PARENT(pnode))
 311                 MPOOL_MARK_RIGHT(pnode);
 312             else
 313                 MPOOL_MARK_LEFT(pnode);
 314
 315             if (MPOOL_IS_PARENT(pbuddy))
 316                 MPOOL_MARK_PARENT(pnode);
 317             else
 318                 MPOOL_MARK_NOTPARENT(pnode);
 319         }
 320         else if (MPOOL_IS_LEFT(pbuddy)) {
 321             if (MPOOL_IS_PARENT(pbuddy))
 322                 MPOOL_MARK_RIGHT(pbuddy);
 323             else
 324                 MPOOL_MARK_LEFT(pbuddy);
 325
 326             if (MPOOL_IS_PARENT(pnode))
 327                 MPOOL_MARK_PARENT(pbuddy);
 328             else
 329                 MPOOL_MARK_NOTPARENT(pbuddy);
 330
 331             pnode = pbuddy;
 332         }
 333         else {
 334             DPRINTF(("Wrong LR relationship\n"));
 335             return;
 336         }
 337
 338         /* Calculate new size */
 339         pnode->logsize++;
 340
 341         /* Mark node as available */
 342         MPOOL_MARK_AVAIL(pnode);
 343
 344         /* Insert `pnode' to the appropriate position */
 345         newpos = mpool->maxlogsize - pnode->logsize;
 346         phead = &mpool->blktable[newpos];
 347         LIST_INSERT_HEAD(phead, pnode, next_chunk);
 348         mpool_printblks(mpool);
 349
 350         goto CHUNK_FOUND;
 351         /* Never reached */
 352     }
 353 }
 354
 355 void mpool_destroy(mpool_t *mpool)
 356 {
 357     free(mpool->blktable);
 358     free(mpool->mem);
 359     free(mpool);
 360 }
 361
 362 static void mpool_printblks(const mpool_t *mpool)
 363 {
 364     const blkhead_t *phead;
 365     const blknode_t *pnode;
 366     size_t i;
 367
 368     for (i = 0; i < mpool->nblocks; i++) {
 369         DPRINTF(("Block (%p): %u\t", mpool->blktable[i], i));
 370         phead = &mpool->blktable[i];
 371         LIST_FOREACH(pnode, phead, next_chunk) {
 372             DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
 373                      pnode->ptr,
 374                      (unsigned) (1 << pnode->logsize),
 375                      MPOOL_IS_AVAIL(pnode) ? 1 : 0,
 376                      MPOOL_IS_RIGHT(pnode) ? 1 : 0,
 377                      MPOOL_IS_PARENT(pnode) ? 1 : 0));
 378         }
 379         DPRINTF(("\n"));
 380     }
 381 }