malloc/mpool.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <sys/queue.h>
   5
   6 typedef struct blknode {
   7     int avail;
   8     size_t logsize;
   9     void *ptr;
  10     LIST_ENTRY(blknode) next_block;
  11 } blknode_t;
  12
  13 typedef struct mpool {
  14     void *mem;
  15     size_t logsize;    /* logarithm of size with base 2  */
  16     LIST_HEAD(blkhead, blknode) *blktable;
  17 } mpool_t;
  18
  19 typedef struct blkhead blkhead_t;
  20
  21 typedef enum {
  22     MP_OK,
  23     MP_ENOMEM
  24 } mpret_t;
  25
  26 /* Function prototypes */
  27 mpret_t mpool_init(mpool_t **mpool, size_t logsize);
  28 void *mpool_alloc(mpool_t *mpool, size_t size);
  29 void mpool_free(void *ptr, size_t size);
  30 void mpool_destroy(mpool_t *mpool);
  31
  32 void mpool_printblks(const mpool_t *mpool);
  33
  34 mpret_t mpool_init(mpool_t **mpool, size_t logsize)
  35 {
  36     blknode_t *pblknode;
  37     unsigned int i;
  38
  39     /* Allocate memory for memory pool data structure */
  40     if ((*mpool = malloc(sizeof **mpool)) == NULL)
  41         return MP_ENOMEM;
  42
  43     /* Allocate the actual memory of the pool */
  44     printf("Allocating %u bytes for pool\n", 2 << logsize);
  45     if (((*mpool)->mem = malloc(2 << logsize)) == NULL) {
  46         free(*mpool);
  47         return MP_ENOMEM;
  48     }
  49
  50     /* Allocate memory for block lists */
  51     if (((*mpool)->blktable = malloc(logsize * sizeof *(*mpool)->blktable)) == NULL) {
  52         free((*mpool)->blktable);
  53         free(*mpool);
  54         return MP_ENOMEM;
  55     }
  56
  57     /* Initialize block lists */
  58     for (i = 0; i < logsize; i++)
  59         LIST_INIT(&(*mpool)->blktable[i]);
  60
  61     (*mpool)->logsize = logsize;
  62
  63     /* Initially, before any storage has been requested,
  64        we have a single available block of length 2 << logsize
  65        in blktable[0].
  66      */
  67     if ((pblknode = malloc(sizeof *pblknode)) == NULL) {
  68         free((*mpool)->blktable);
  69         free(*mpool);
  70         return MP_ENOMEM;
  71     }
  72     pblknode->ptr = (*mpool)->mem;
  73     pblknode->avail = 1;
  74     pblknode->logsize = logsize;
  75
  76     LIST_INSERT_HEAD(&(*mpool)->blktable[0], pblknode, next_block);
  77
  78     mpool_printblks(*mpool);
  79
  80     return MP_OK;
  81 }
  82
  83 void *mpool_alloc(mpool_t *mpool, size_t size)
  84 {
  85     blkhead_t *phead;
  86     blknode_t *pnode;
  87     blknode_t *pavailnode;
  88     blknode_t *pnewnode;
  89     unsigned int i, newpos;
  90
  91     printf("\n\n=======================================================\n\n");
  92     printf("Searching for block of bytes: %u\n", size);
  93
  94     /* Find the most suitable 2^j bytes block for the requested size of k bytes.
  95        The block must satisfy the condition: 2^j >= size and must also be available.
  96      */
  97     pavailnode = NULL;
  98     for (i = 0; i < mpool->logsize; i++) {
  99         printf("Searcing block: %u\n", i);
 100         phead = &mpool->blktable[i];
 101         if ((pnode = LIST_FIRST(phead)) != NULL) {
 102             if ((unsigned)(2 << pnode->logsize) >= size) {
 103                 LIST_FOREACH(pnode, &mpool->blktable[i], next_block) {
 104                     if (pnode->avail != 0) {
 105                         pavailnode = pnode;
 106                         goto NEXT_BLOCK;
 107                     }
 108                 }
 109             }
 110         }
 111     NEXT_BLOCK:;
 112     }
 113
 114     /* Failure, no available block */
 115     if (pavailnode == NULL) {
 116         printf("No available block found\n");
 117         return NULL;
 118     }
 119     printf("Found block of bytes %u\n", 2 << pavailnode->logsize);
 120
 121     /* Split required ? */
 122 AGAIN:;
 123     printf("size = %u\tp = %u\tp-1=%u\n",
 124            size,
 125            2 << pavailnode->logsize,
 126            2 << (pavailnode->logsize - 1));
 127
 128     if (size == (unsigned)(2 << pavailnode->logsize)
 129         || (size > (unsigned)(2 << (pavailnode->logsize - 1)))) {
 130         printf("No split required\n");
 131         pavailnode->avail = 0;    /* Mars as no longer available */
 132         mpool_printblks(mpool);
 133         return pavailnode->ptr;
 134     }
 135
 136     printf("Splitting...\n");
 137
 138     /* Removing old block */
 139     printf("Removing old chunk from list\n");
 140     LIST_REMOVE(pavailnode, next_block);
 141     mpool_printblks(mpool);
 142     pavailnode->logsize--;
 143
 144     printf("New size is now: %u bytes\n", 2 << pavailnode->logsize);
 145     printf("Moving old chunk to new position\n");
 146     newpos = mpool->logsize - pavailnode->logsize;
 147     LIST_INSERT_HEAD(&mpool->blktable[newpos], pavailnode, next_block);
 148     mpool_printblks(mpool);
 149
 150     /* Split */
 151     printf("Will add new item with bytes: %u\n", 2 << pavailnode->logsize);
 152     if ((pnewnode = malloc(sizeof *pnewnode)) == NULL)
 153         return NULL;    /* ? */
 154     pnewnode->ptr = pavailnode->ptr + (2 << pavailnode->logsize);
 155     pnewnode->avail = 1;
 156     pnewnode->logsize = pavailnode->logsize;
 157     LIST_INSERT_HEAD(&mpool->blktable[newpos], pnewnode, next_block);
 158     mpool_printblks(mpool);
 159
 160     goto AGAIN;
 161     /* Never reached */
 162 }
 163
 164 void mpool_free(void *ptr, size_t size)
 165 {
 166     size = 0;
 167     ptr = NULL;
 168 }
 169
 170 void mpool_destroy(mpool_t *mpool)
 171 {
 172     const blkhead_t *phead;
 173     blknode_t *pnode;
 174     unsigned int i;
 175
 176     /* Free all nodes in all block lists */
 177     for (i = 0; i < mpool->logsize; i++) {
 178         phead = &mpool->blktable[i];
 179         while ((pnode = LIST_FIRST(phead)) != NULL) {
 180             LIST_REMOVE(pnode, next_block);
 181             free(pnode);
 182         }
 183     }
 184
 185     free(mpool->blktable);
 186     free(mpool->mem);
 187     free(mpool);
 188 }
 189
 190 void mpool_printblks(const mpool_t *mpool)
 191 {
 192     const blkhead_t *phead;
 193     const blknode_t *pnode;
 194     unsigned int i;
 195
 196     for (i = 0; i < mpool->logsize; i++) {
 197         printf("Block: %u\t", i);
 198
 199         phead = &mpool->blktable[i];
 200         LIST_FOREACH(pnode, phead, next_block) {
 201             printf("chunk(addr = %p, bytes = %u, av = %d)\t",
 202                    pnode->ptr,
 203                    (unsigned) (2 << pnode->logsize),
 204                    pnode->avail);
 205         }
 206
 207         printf("\n");
 208     }
 209 }
 210
 211 int main(void)
 212 {
 213     mpool_t *mpool;
 214     /*char *p, *p2, *p3;*/
 215     char *p[10000];
 216     unsigned int i;
 217
 218     if (mpool_init(&mpool, 25) == MP_ENOMEM) {
 219         fprintf(stderr, "Not enought memory\n");
 220         exit(EXIT_FAILURE);
 221     }
 222
 223     /*
 224     p = mpool_alloc(mpool, 70);
 225     p2 = mpool_alloc(mpool, 35);
 226     p3 = mpool_alloc(mpool, 80);
 227
 228     strcpy(p, "Hello flyfly");
 229     strcpy(p2, "H");
 230     strcpy(p3, "Hello all");
 231
 232     printf("Address: %p\tContent: %s\n", p, p);
 233     printf("Address: %p\tContent: %s\n", p2, p2);
 234     printf("Address: %p\tContent: %s\n", p3, p3);
 235     */
 236
 237     for (i = 0; i < 3000; i++)
 238         if ((p[i] = mpool_alloc(mpool, 2 << (1 + (rand() % 10)))) == NULL)
 239             break;
 240
 241     mpool_destroy(mpool);
 242     return EXIT_SUCCESS;
 243 }