malloc/mpool.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "mpool.h"
   5
   6 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize)
   7 {
   8     blknode_t *pblknode;
   9     unsigned int i;
  10
  11     /* Validate input */
  12     if (maxlogsize < minlogsize)
  13         return MP_EBADVAL;
  14
  15     /* Allocate memory for memory pool data structure */
  16     if ((*mpool = malloc(sizeof **mpool)) == NULL)
  17         return MP_ENOMEM;
  18
  19     (*mpool)->maxlogsize = maxlogsize;
  20     (*mpool)->minlogsize = minlogsize;
  21     (*mpool)->nblocks = (*mpool)->maxlogsize - (*mpool)->minlogsize + 1;
  22
  23     /* Allocate the actual memory of the pool */
  24     printf("Allocating %u bytes for pool\n", 1 << maxlogsize);
  25     printf("maxlogsize = %u\tminlogsize = %u\tnblocks = %u\n",
  26            (*mpool)->maxlogsize,
  27            (*mpool)->minlogsize,
  28            (*mpool)->nblocks);
  29     if (((*mpool)->mem = malloc(1 << maxlogsize)) == NULL) {
  30         free(*mpool);
  31         return MP_ENOMEM;
  32     }
  33
  34     /* Allocate memory for block lists */
  35     if (((*mpool)->blktable = malloc((*mpool)->nblocks * sizeof *(*mpool)->blktable)) == NULL) {
  36         free((*mpool)->mem);
  37         free(*mpool);
  38         return MP_ENOMEM;
  39     }
  40
  41     /* Initialize block lists */
  42     for (i = 0; i < (*mpool)->nblocks; i++)
  43         LIST_INIT(&(*mpool)->blktable[i]);
  44
  45     /*
  46      * Initially, before any storage has been requested,
  47      * we have a single available block of length 2^maxlogsize
  48      * in blktable[0].
  49      */
  50     if ((pblknode = malloc(sizeof *pblknode)) == NULL) {
  51         free((*mpool)->blktable);
  52         free((*mpool)->mem);
  53         free(*mpool);
  54         return MP_ENOMEM;
  55     }
  56     pblknode->ptr = (*mpool)->mem;
  57     pblknode->avail = 1;
  58     pblknode->logsize = maxlogsize;
  59
  60     LIST_INSERT_HEAD(&(*mpool)->blktable[0], pblknode, next_block);
  61
  62     mpool_printblks(*mpool);
  63
  64     return MP_OK;
  65 }
  66
  67 void *mpool_alloc(mpool_t *mpool, size_t size)
  68 {
  69     blkhead_t *phead;
  70     blknode_t *pnode;
  71     blknode_t *pavailnode;
  72     blknode_t *pnewnode;
  73     unsigned int i, newpos;
  74
  75     printf("\n\n=======================================================\n\n");
  76     printf("Searching for block of bytes: %u\n", size);
  77
  78     /*
  79      * Find the most suitable 2^j bytes block for the requested size of bytes.
  80      * The condition 2^j >= size must be satisfied for the smallest possible value
  81      * of j and the block must be marked as available ofcourse.
  82     */
  83     pavailnode = NULL;
  84     for (i = 0; i < mpool->nblocks; i++) {
  85         printf("Searcing block: %u\n", i);
  86         phead = &mpool->blktable[i];
  87         if ((pnode = LIST_FIRST(phead)) != NULL) {
  88             if ((unsigned)(1 << pnode->logsize) >= size) {
  89                 LIST_FOREACH(pnode, phead, next_block) {
  90                     if (pnode->avail != 0) {
  91                         pavailnode = pnode;
  92                         goto NEXT_BLOCK;
  93                     }
  94                 }
  95             }
  96         }
  97     NEXT_BLOCK:;
  98     }
  99
 100     /* Failure, no available block */
 101     if (pavailnode == NULL) {
 102         printf("No available block found\n");
 103         return NULL;
 104     }
 105     printf("Found block of bytes %u\n", 1 << pavailnode->logsize);
 106
 107     /* Is a split required ? */
 108 AGAIN:;
 109     printf("size = %u\tp = %u\tp-1 = %u\n",
 110            size,
 111            1 << pavailnode->logsize,
 112            1 << (pavailnode->logsize - 1));
 113
 114     /*
 115      * We don't need to split the chunk we just found,
 116      * if one the following statements is true:
 117      *
 118      * - `size' bytes fit exactly in the chunk
 119      * - `size' bytes won't fit in the divided chunk
 120      * - `minlogsize' constraint will be violated if we split
 121      *
 122      * NOTE: log2(size/2) = log2(size) - log2(2) = log2(size) - 1
 123      */
 124     if ((size == (unsigned)(1 << pavailnode->logsize))
 125         || (size > (unsigned)(1 << (pavailnode->logsize - 1)))
 126         || (mpool->minlogsize > (pavailnode->logsize - 1))) {
 127         printf("No split required\n");
 128         pavailnode->avail = 0;    /* Mark as no longer available */
 129         mpool_printblks(mpool);
 130         return pavailnode->ptr;
 131     }
 132
 133     printf("Splitting...\n");
 134
 135     /* Remove old block */
 136     printf("Removing old chunk from list\n");
 137     LIST_REMOVE(pavailnode, next_block);
 138     mpool_printblks(mpool);
 139     pavailnode->logsize--;
 140
 141     printf("New size is now: %u bytes\n", 1 << pavailnode->logsize);
 142     printf("Moving old chunk to new position\n");
 143     newpos = mpool->nblocks - pavailnode->logsize - 1;
 144     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_block);
 145     mpool_printblks(mpool);
 146
 147     /* Split */
 148     printf("Will add new item with bytes: %u\n", 1 << pavailnode->logsize);
 149     if ((pnewnode = malloc(sizeof *pnewnode)) == NULL)
 150         return NULL;    /* ? */
 151     pnewnode->ptr = (char *)pavailnode->ptr + (1 << pavailnode->logsize);
 152     pnewnode->avail = 1;
 153     pnewnode->logsize = pavailnode->logsize;
 154     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_block);
 155     mpool_printblks(mpool);
 156
 157     goto AGAIN;
 158     /* Never reached */
 159 }
 160
 161 void mpool_free(mpool_t *mpool, void *ptr)
 162 {
 163     const blkhead_t *phead;
 164     blknode_t *pnode;
 165     unsigned int i;
 166
 167     printf("Freeing ptr: %p\n", ptr);
 168
 169     /* Coalesce has not been implemented yet */
 170     for (i = 0; i < mpool->nblocks; i++) {
 171         printf("Block: %u\n", i);
 172         phead = &mpool->blktable[i];
 173         LIST_FOREACH(pnode, phead, next_block) {
 174             if (pnode->ptr == ptr) {
 175                 printf("Found\n");
 176                 LIST_REMOVE(pnode, next_block);
 177                 free(pnode);
 178                 goto DONE;
 179             }
 180         }
 181     }
 182  DONE:;
 183 }
 184
 185 void mpool_destroy(mpool_t *mpool)
 186 {
 187     const blkhead_t *phead;
 188     blknode_t *pnode;
 189     unsigned int i;
 190
 191     /* Free all nodes in all block lists */
 192     for (i = 0; i < mpool->nblocks; i++) {
 193         phead = &mpool->blktable[i];
 194         while ((pnode = LIST_FIRST(phead)) != NULL) {
 195             LIST_REMOVE(pnode, next_block);
 196             free(pnode);
 197         }
 198     }
 199
 200     free(mpool->blktable);
 201     free(mpool->mem);
 202     free(mpool);
 203 }
 204
 205 void mpool_printblks(const mpool_t *mpool)
 206 {
 207     const blkhead_t *phead;
 208     const blknode_t *pnode;
 209     unsigned int i;
 210
 211     for (i = 0; i < mpool->nblocks; i++) {
 212         printf("Block: %u\t", i);
 213
 214         phead = &mpool->blktable[i];
 215         LIST_FOREACH(pnode, phead, next_block) {
 216             printf("chunk(addr = %p, bytes = %u, av = %d)\t",
 217                    pnode->ptr,
 218                    (unsigned) (1 << pnode->logsize),
 219                    pnode->avail);
 220         }
 221
 222         printf("\n");
 223     }
 224 }
 225
 226 void mpool_stat_get_nodes(const mpool_t *mpool, size_t *avail, size_t *used)
 227 {
 228     const blkhead_t *phead;
 229     const blknode_t *pnode;
 230     unsigned int i;
 231
 232     *avail = 0;
 233     *used = 0;
 234     for (i = 0; i < mpool->nblocks; i++) {
 235         phead = &mpool->blktable[i];
 236         LIST_FOREACH(pnode, phead, next_block) {
 237             if (pnode->avail == 1)
 238                 (*avail)++;
 239             else
 240                 (*used)++;
 241         }
 242     }
 243 }
 244
 245 void mpool_stat_get_bytes(const mpool_t *mpool, size_t *avail, size_t *used)
 246 {
 247     const blkhead_t *phead;
 248     const blknode_t *pnode;
 249     unsigned int i;
 250
 251     for (i = 0; i < mpool->nblocks; i++) {
 252         phead = &mpool->blktable[i];
 253         LIST_FOREACH(pnode, phead, next_block) {
 254             if (pnode->avail == 1)
 255                 *avail += 1 << pnode->logsize;
 256             else
 257                 *used += 1 << pnode->logsize;
 258         }
 259     }
 260 }
 261
 262 int main(void)
 263 {
 264     mpool_t *mpool;
 265     char *p[1000];
 266     size_t an = 1, un = 0, ab = 1, ub = 0;
 267     unsigned int i;
 268
 269     if (mpool_init(&mpool, 15, 1) == MP_ENOMEM) {
 270         fprintf(stderr, "Not enough memory\n");
 271         exit(EXIT_FAILURE);
 272     }
 273
 274     for (i = 0; i < 10; i++) {
 275         if ((p[i] = mpool_alloc(mpool, 1 << ((rand() % 10)))) == NULL)
 276             break;
 277         else
 278             mpool_free(mpool, p[i]);
 279     }
 280
 281     mpool_stat_get_nodes(mpool, &an, &un);
 282     mpool_stat_get_bytes(mpool, &ab, &ub);
 283     printf("avail nodes = %u\tused nodes = %u\tfree(%%) = %f\n", an, un, (float)an / (an + un));
 284     printf("avail bytes  = %u\tused bytes = %u\tfree(%%) = %f\n", ab, ub, (float)ab / (ab + ub));
 285
 286     mpool_destroy(mpool);
 287
 288     return EXIT_SUCCESS;
 289 }