malloc/mpool.c

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