malloc/mpool.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <time.h>    /* for time() in srand() */
   5
   6 #include "mpool.h"
   7
   8 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize)
   9 {
  10     blknode_t *pblknode;
  11     unsigned int i;
  12
  13     /* Validate input */
  14     if (maxlogsize < minlogsize)
  15         return MP_EBADVAL;
  16
  17     /* Allocate memory for memory pool data structure */
  18     if ((*mpool = malloc(sizeof **mpool)) == NULL)
  19         return MP_ENOMEM;
  20
  21     (*mpool)->maxlogsize = maxlogsize;
  22     (*mpool)->minlogsize = minlogsize;
  23     (*mpool)->nblocks = (*mpool)->maxlogsize - (*mpool)->minlogsize + 1;
  24 #ifdef MP_STATS
  25     (*mpool)->nsplits = 0;
  26     (*mpool)->nmerges = 0;
  27 #endif
  28
  29     /* Allocate the actual memory of the pool */
  30     DPRINTF(("Allocating %u bytes for pool\n", 1 << maxlogsize));
  31     DPRINTF(("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n",
  32              (*mpool)->maxlogsize,
  33              (*mpool)->minlogsize,
  34              (*mpool)->nblocks));
  35     if (((*mpool)->mem = malloc(1 << maxlogsize)) == NULL) {
  36         free(*mpool);
  37         return MP_ENOMEM;
  38     }
  39
  40     /* Allocate memory for block lists */
  41     if (((*mpool)->blktable = malloc((*mpool)->nblocks * sizeof *(*mpool)->blktable)) == NULL) {
  42         free((*mpool)->mem);
  43         free(*mpool);
  44         return MP_ENOMEM;
  45     }
  46
  47     /* Initialize block lists */
  48     for (i = 0; i < (*mpool)->nblocks; i++)
  49         LIST_INIT(&(*mpool)->blktable[i]);
  50
  51     /*
  52      * Initially, before any storage has been requested,
  53      * we have a single available block of length 2^maxlogsize
  54      * in blktable[0].
  55      */
  56     if ((pblknode = malloc(sizeof *pblknode)) == NULL) {
  57         free((*mpool)->blktable);
  58         free((*mpool)->mem);
  59         free(*mpool);
  60         return MP_ENOMEM;
  61     }
  62     pblknode->ptr = (*mpool)->mem;
  63     pblknode->flags |= MP_NODE_AVAIL;    /* Mark as available */
  64     pblknode->logsize = maxlogsize;
  65
  66     LIST_INSERT_HEAD(&(*mpool)->blktable[0], pblknode, next_block);
  67
  68     mpool_printblks(*mpool);
  69
  70     return MP_OK;
  71 }
  72
  73 void *mpool_alloc(mpool_t *mpool, size_t size)
  74 {
  75     blkhead_t *phead;
  76     blknode_t *pnode;
  77     blknode_t *pavailnode;
  78     blknode_t *pnewnode;
  79     unsigned int i, newpos;
  80     unsigned char flag;
  81
  82     DPRINTF(("\n\n=======================================================\n\n"));
  83     DPRINTF(("Searching for block of bytes: %u\n", size));
  84
  85     /*
  86      * Find the most suitable 2^j bytes block for the requested size of bytes.
  87      * The condition 2^j >= size must be satisfied for the smallest possible value
  88      * of j and the block must be marked as available ofcourse.
  89     */
  90     pavailnode = NULL;
  91     for (i = 0; i < mpool->nblocks; i++) {
  92         DPRINTF(("Searcing block: %u\n", i));
  93         phead = &mpool->blktable[i];
  94         if ((pnode = LIST_FIRST(phead)) != NULL) {
  95             if ((unsigned)(1 << pnode->logsize) >= size) {
  96                 LIST_FOREACH(pnode, phead, next_block) {
  97                     if (pnode->flags & MP_NODE_AVAIL) {
  98                         pavailnode = pnode;
  99                         goto NEXT_BLOCK;
 100                     }
 101                 }
 102             }
 103         }
 104     NEXT_BLOCK:;
 105     }
 106
 107     /* Failure, no available block */
 108     if (pavailnode == NULL) {
 109         DPRINTF(("No available block found\n"));
 110         return NULL;
 111     }
 112     DPRINTF(("Found block of bytes %u\n", 1 << pavailnode->logsize));
 113
 114     /* Is a split required ? */
 115 AGAIN:;
 116     DPRINTF(("size = %u\tp = %u\tp-1 = %u\n",
 117              size,
 118              1 << pavailnode->logsize,
 119              1 << (pavailnode->logsize - 1)));
 120
 121     /*
 122      * We don't need to split the chunk we just found,
 123      * if one the following statements is true:
 124      *
 125      * - `size' bytes fit exactly in the chunk
 126      * - `size' bytes won't fit in the divided chunk
 127      * - `minlogsize' constraint will be violated if we split
 128      *
 129      * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
 130      */
 131     if ((size == (unsigned)(1 << pavailnode->logsize))
 132         || (size > (unsigned)(1 << (pavailnode->logsize - 1)))
 133         || (mpool->minlogsize > (pavailnode->logsize - 1))) {
 134         DPRINTF(("No split required\n"));
 135         pavailnode->flags &= ~MP_NODE_AVAIL;    /* Mark as no longer available */
 136         mpool_printblks(mpool);
 137         return pavailnode->ptr;
 138     }
 139
 140     DPRINTF(("Splitting...\n"));
 141 #ifdef MP_STATS
 142     mpool->nsplits++;    /* FIXME: print a message if it overflows */
 143 #endif
 144
 145     /* Remove old block */
 146     DPRINTF(("Removing old chunk from list\n"));
 147     LIST_REMOVE(pavailnode, next_block);
 148     mpool_printblks(mpool);
 149     pavailnode->logsize--;
 150     flag = pavailnode->flags;
 151     if (pavailnode->flags & MP_NODE_LR)
 152         pavailnode->flags |= MP_NODE_PARENT;
 153     else
 154         pavailnode->flags &= ~MP_NODE_PARENT;
 155     pavailnode->flags &= ~MP_NODE_LR;    /* Mark as left buddy */
 156
 157     DPRINTF(("New size is now: %u bytes\n", 1 << pavailnode->logsize));
 158     DPRINTF(("Moving old chunk to new position\n"));
 159     newpos = mpool->nblocks - pavailnode->logsize;
 160     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_block);
 161     mpool_printblks(mpool);
 162
 163     /* Split */
 164     DPRINTF(("Will add new item with bytes: %u\n", 1 << pavailnode->logsize));
 165     if ((pnewnode = malloc(sizeof *pnewnode)) == NULL)
 166         return NULL;    /* ? */
 167     pnewnode->ptr = (char *)pavailnode->ptr + (1 << pavailnode->logsize);
 168     pnewnode->flags |= MP_NODE_AVAIL;    /* Mark as available */
 169     pnewnode->flags |= MP_NODE_LR;       /* Mark as right buddy */
 170
 171     if (flag & MP_NODE_PARENT)
 172         pnewnode->flags |= MP_NODE_PARENT;
 173     else
 174         pnewnode->flags &= ~MP_NODE_PARENT;
 175
 176     pnewnode->logsize = pavailnode->logsize;
 177     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_block);
 178     mpool_printblks(mpool);
 179
 180     goto AGAIN;
 181     /* Never reached */
 182 }
 183
 184 void mpool_free(mpool_t *mpool, void *ptr)
 185 {
 186     blkhead_t *phead;
 187     blknode_t *pnode, *pbuddy;
 188     unsigned int i, newpos;
 189     void *buddyptr;
 190
 191     DPRINTF(("Freeing ptr: %p\n", ptr));
 192
 193     /* Search all nodes to find the one that points to ptr */
 194     for (i = 0; i < mpool->nblocks; i++) {
 195         DPRINTF(("Searching for ptr %p in block: %u\n", ptr, i));
 196         phead = &mpool->blktable[i];
 197         LIST_FOREACH(pnode, phead, next_block) {
 198             if (pnode->ptr == ptr) {
 199                 DPRINTF(("Found chunk at block: %u\tBlock has chunks with bytes: %u\n",
 200                          i, 1 << pnode->logsize));
 201                 goto CHUNK_FOUND;
 202             }
 203         }
 204     }
 205
 206  CHUNK_FOUND:;
 207     if (pnode->logsize == mpool->maxlogsize) {
 208         pnode->flags |= MP_NODE_AVAIL;
 209         return;
 210     }
 211
 212     /* Calculate possible buddy of chunk */
 213     if (pnode->flags & MP_NODE_LR)
 214         buddyptr = (char *)pnode->ptr - (1 << pnode->logsize);
 215     else
 216         buddyptr = (char *)pnode->ptr + (1 << pnode->logsize);
 217
 218     /*
 219      * Search buddy node with address `buddyptr'.
 220      * If there is indeed a buddy of `pnode', it will be in
 221      * the same linked list with the latter.
 222      *
 223      * NOTE: nodes that belong to the same linked list,
 224      * point to memory chunks with the same size.
 225      */
 226     DPRINTF(("Chunk: %p\tPossible buddy at: %p\n", pnode->ptr, buddyptr));
 227     DPRINTF(("Searching for node with address: %p\n", buddyptr));
 228     pbuddy = NULL;
 229     LIST_FOREACH(pbuddy, phead, next_block) {
 230         if (pbuddy->ptr == buddyptr) {
 231             DPRINTF(("Buddy found\n"));
 232             break;
 233         }
 234     }
 235
 236     /*
 237      * If there is no buddy of `pnode' or if there is, but it's unavailable,
 238      * just free `pnode' and we are done
 239      */
 240     if (pbuddy == NULL || (pbuddy != NULL && ((pbuddy->flags & MP_NODE_AVAIL) == 0))) {
 241         DPRINTF(("Not found or found but unavailable\n"));
 242         DPRINTF(("Freeing chunk (marking it as available)\n"));
 243         pnode->flags |= MP_NODE_AVAIL;
 244         mpool_printblks(mpool);
 245         return;
 246     }
 247     /*
 248      * There is a buddy, and it's available for sure. Coalesce.
 249      *
 250      * So now we have the chunk we were told to free (`pnode'), and
 251      * it's buddy (`pbuddy').
 252      *
 253      * pnode will become the parent, by updating its member structures,
 254      * such as logsize and flags (availability, LR buddiness, and inheritance)
 255      * and pbuddy will be free'd() for real.
 256      *
 257      * */
 258     else {
 259         DPRINTF(("Buddy exists and it's available. Coalesce\n"));
 260 #ifdef MP_STATS
 261         mpool->nmerges++;
 262 #endif
 263         DPRINTF(("Removing chunk from old position (so as to reposition it)\n"));
 264         LIST_REMOVE(pnode, next_block);
 265         mpool_printblks(mpool);
 266         pnode->logsize++;
 267         pnode->flags |= MP_NODE_AVAIL;    /* Mark as available */
 268
 269         /* `pnode' is left buddy */
 270         if ((pnode->flags & MP_NODE_LR) == 0) {
 271             if (pnode->flags & MP_NODE_PARENT)
 272                 pnode->flags |= MP_NODE_LR;
 273             else
 274                 pnode->flags &= ~MP_NODE_LR;
 275
 276             if (pbuddy->flags & MP_NODE_PARENT)
 277                 pnode->flags |= MP_NODE_PARENT;
 278             else
 279                 pnode->flags &= ~MP_NODE_PARENT;
 280         }
 281
 282         /* `pbuddy' is left buddy */
 283         if ((pbuddy->flags & MP_NODE_LR) == 0) {
 284             if (pbuddy->flags & MP_NODE_PARENT)
 285                 pnode->flags |= MP_NODE_LR;
 286             else
 287                 pnode->flags &= ~MP_NODE_LR;
 288
 289             DPRINTF(("Adjusting... pnode->ptr = pbuddy->ptr\n"));
 290             pnode->ptr = pbuddy->ptr;
 291         }
 292
 293         newpos = mpool->nblocks - pnode->logsize;
 294         phead = &mpool->blktable[newpos];
 295
 296         DPRINTF(("Inserting chunk to new position\n"));
 297         LIST_INSERT_HEAD(phead, pnode, next_block);
 298         mpool_printblks(mpool);
 299
 300         DPRINTF(("Removing buddy\n"));
 301         LIST_REMOVE(pbuddy, next_block);
 302         free(pbuddy);
 303         mpool_printblks(mpool);
 304         goto CHUNK_FOUND;
 305     }
 306 }
 307
 308 void mpool_destroy(mpool_t *mpool)
 309 {
 310     const blkhead_t *phead;
 311     blknode_t *pnode;
 312     unsigned int i;
 313
 314     /* Free all nodes in all block lists */
 315     for (i = 0; i < mpool->nblocks; i++) {
 316         phead = &mpool->blktable[i];
 317         while ((pnode = LIST_FIRST(phead)) != NULL) {
 318             LIST_REMOVE(pnode, next_block);
 319             free(pnode);
 320         }
 321     }
 322
 323     free(mpool->blktable);
 324     free(mpool->mem);
 325     free(mpool);
 326 }
 327
 328 void mpool_printblks(const mpool_t *mpool)
 329 {
 330     const blkhead_t *phead;
 331     const blknode_t *pnode;
 332     unsigned int i;
 333
 334     for (i = 0; i < mpool->nblocks; i++) {
 335         DPRINTF(("Block: %u\t", i));
 336
 337         phead = &mpool->blktable[i];
 338         LIST_FOREACH(pnode, phead, next_block) {
 339             DPRINTF(("ch(ad = %p, by = %u, av = %d, lr = %d, pa = %d)\t",
 340                      pnode->ptr,
 341                      (unsigned) (1 << pnode->logsize),
 342                      pnode->flags & MP_NODE_AVAIL ? 1 : 0,
 343                      pnode->flags & MP_NODE_LR ? 1 : 0,
 344                      pnode->flags & MP_NODE_PARENT ? 1 : 0));
 345         }
 346
 347         DPRINTF(("\n"));
 348     }
 349 }
 350
 351 void mpool_stat_get_nodes(const mpool_t *mpool, size_t *avail, size_t *used)
 352 {
 353     const blkhead_t *phead;
 354     const blknode_t *pnode;
 355     unsigned int i;
 356
 357     *avail = 0;
 358     *used = 0;
 359     for (i = 0; i < mpool->nblocks; i++) {
 360         phead = &mpool->blktable[i];
 361         LIST_FOREACH(pnode, phead, next_block) {
 362             if (pnode->flags & MP_NODE_AVAIL)
 363                 (*avail)++;
 364             else
 365                 (*used)++;
 366         }
 367     }
 368 }
 369
 370 void mpool_stat_get_bytes(const mpool_t *mpool, size_t *avail, size_t *used)
 371 {
 372     const blkhead_t *phead;
 373     const blknode_t *pnode;
 374     unsigned int i;
 375
 376     *avail = 0;
 377     *used = 0;
 378     for (i = 0; i < mpool->nblocks; i++) {
 379         phead = &mpool->blktable[i];
 380         LIST_FOREACH(pnode, phead, next_block) {
 381             if (pnode->flags & MP_NODE_AVAIL)
 382                 *avail += 1 << pnode->logsize;
 383             else
 384                 *used += 1 << pnode->logsize;
 385         }
 386     }
 387 }
 388
 389 #ifdef MP_STATS
 390 size_t mpool_stat_get_splits(const mpool_t *mpool)
 391 {
 392     return mpool->nsplits;
 393 }
 394
 395 size_t mpool_stat_get_merges(const mpool_t *mpool)
 396 {
 397     return mpool->nmerges;
 398 }
 399 #endif
 400
 401 int main(void)
 402 {
 403     mpool_t *mpool;
 404     char *p[1000];
 405     size_t an = 0, un = 0, ab = 0, ub = 0, me = 0, sp = 0;
 406     unsigned int i, j, S;
 407
 408     srand(time(NULL));
 409
 410     if (mpool_init(&mpool, 12, 1) == MP_ENOMEM) {
 411         fprintf(stderr, "Not enough memory\n");
 412         exit(EXIT_FAILURE);
 413     }
 414
 415     for (i = 0; i < 1000; i++) {
 416         if ((p[i] = mpool_alloc(mpool, S = (1 << ((rand() % 5))))) == NULL)
 417             break;
 418         else {
 419             /*memset(p[i], 0, S);*/;
 420         }
 421     }
 422
 423     for (j = 0; j < i; j++) {
 424         mpool_free(mpool, p[j]);
 425     }
 426
 427     mpool_stat_get_nodes(mpool, &an, &un);
 428     mpool_stat_get_bytes(mpool, &ab, &ub);
 429     me = mpool_stat_get_merges(mpool);
 430     sp = mpool_stat_get_splits(mpool);
 431     DPRINTF(("avail nodes = %u\tused nodes = %u\tfree(%%) = %f\n", an, un, 100.0 * an / (an + un)));
 432     DPRINTF(("avail bytes  = %u\tused bytes = %u\tfree(%%) = %f\n", ab, ub, 100.0 * ab / (ab + ub)));
 433     DPRINTF(("splits = %u\tmerges = %u\n", sp, me));
 434
 435     mpool_destroy(mpool);
 436
 437     return EXIT_SUCCESS;
 438 }