malloc/test4.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>  /* for memset() */
   4 #include <time.h>    /* for time() in srand() */
   5 #include <sys/queue.h>
   6
   7 #include "mpool.h"
   8 #include "mstat.h"
   9
  10 #define MAX_EPOCHS    20000   /* Maximum number of epochs of simulation */
  11 #define MAX_LIFETIME   1000   /* Maximum lifetime of a reserved block */
  12 #define MAX_LOGSIZE      5    /* Maximum logarithm of block's size */
  13 #define TI 5                  /* Every `TI' steps dump statistics */
  14
  15 typedef struct simnode {
  16     void *ptr;
  17     unsigned int lifetime;
  18     LIST_ENTRY(simnode) next_node;
  19 } simnode_t;
  20
  21 LIST_HEAD(simhead, simnode);
  22 typedef struct simhead simhead_t;
  23
  24 /* Function prototypes */
  25 void sim_add_to_list(simhead_t *simhead, simnode_t *simnode);
  26 void sim_free_from_list(mpool_t *mpool, simhead_t *simhead, unsigned int t);
  27 void sim_print_stats(const mpool_t *mpool, unsigned int t, FILE *fp);
  28
  29 int main(void)
  30 {
  31     simnode_t simnode[MAX_EPOCHS];
  32     mpool_t *mpool;
  33     mpret_t mpret;
  34     simhead_t simhead;
  35     size_t t, sz, lt;
  36
  37     /* Initialize memory pool */
  38     mpret = mpool_init(&mpool, 25, 5);
  39     if (mpret == MPOOL_ENOMEM) {
  40         fprintf(stderr, "mpool: not enough memory\n");
  41         exit(EXIT_FAILURE);
  42     }
  43     else if (mpret == MPOOL_EBADVAL) {
  44         fprintf(stderr, "mpool: bad value passed to mpool_init()\n");
  45         exit(EXIT_FAILURE);
  46     }
  47
  48     /* Initialize random number generator */
  49     srand(time(NULL));
  50
  51     /* Initialize simlist */
  52     LIST_INIT(&simhead);
  53
  54     /* Run simulation */
  55     for (t = 0; t < MAX_EPOCHS; t++) {
  56         /* Is it time to dump statistics ? */
  57         if (t % TI == 0)
  58             sim_print_stats(mpool, t, stdout);
  59
  60         /* Free all blocks that lived their life */
  61         sim_free_from_list(mpool, &simhead, t);
  62
  63         /*
  64          * Calculate a random size `sz' and a random lifetime `lt',
  65          * similar to the way Moirae defined peoples' lives in Greek Mythology
  66          * (One could use other distributions than the uniform we use here)
  67          */
  68         sz = 1 << rand() % (1 + MAX_LOGSIZE);
  69         if (t < (MAX_EPOCHS - MAX_LIFETIME))
  70             lt = 1 + rand() % MAX_LIFETIME;
  71         else
  72             lt = 1 + rand() % (MAX_EPOCHS - t);
  73         /*printf("t = %u\tsz = %u\tlt = %u\n", t, sz, lt);*/
  74
  75         /* Allocate a block of size `sz' and make it last `lt' time intervals */
  76         if ((simnode[t].ptr = mpool_alloc(mpool, sz)) == NULL) {
  77             fprintf(stderr, "mpool: no available block\n");
  78             mpool_destroy(mpool);
  79             exit(EXIT_FAILURE);
  80         }
  81         simnode[t].lifetime = t + lt;
  82
  83         /* Add block to list and let it find its correct position in it */
  84         sim_add_to_list(&simhead, &simnode[t]);
  85     }
  86
  87     /* Free the last of Mohicans */
  88     sim_free_from_list(mpool, &simhead, t);
  89
  90     /* Dump statistics */
  91     sim_print_stats(mpool, t, stdout);
  92
  93     /* Destroy memory pool and free all resources */
  94     mpool_destroy(mpool);
  95
  96     return EXIT_SUCCESS;
  97 }
  98
  99 void sim_add_to_list(simhead_t *simhead, simnode_t *simnode)
 100 {
 101     simnode_t *pnode;
 102
 103     /*
 104       LIST_FOREACH(pnode, simhead, next_node)
 105           printf("%u -> ", pnode->lifetime);
 106       printf("\n");
 107     */
 108
 109     LIST_FOREACH(pnode, simhead, next_node) {
 110         if (simnode->lifetime < pnode->lifetime) {
 111             LIST_INSERT_BEFORE(pnode, simnode, next_node);
 112             return;
 113         }
 114         else if (LIST_NEXT(pnode, next_node) == NULL) {
 115             LIST_INSERT_AFTER(pnode, simnode, next_node);
 116             return;
 117         }
 118    }
 119
 120     /* 1st element goes here -- this is called only when the list is empty */
 121     LIST_INSERT_HEAD(simhead, simnode, next_node);
 122 }
 123
 124 void sim_free_from_list(mpool_t *mpool, simhead_t *simhead, unsigned int t)
 125 {
 126     simnode_t *pnode;
 127
 128     /*
 129      * Blocks with the same lifetime are placed together,
 130      * e.g. ... -> 5 -> 5 -> 7 -> 7 -> 7 -> 7 -> 8 -> 8 -> 9 -> 9 -> ...
 131      * That said, if the continuity breaks in one node,
 132      * we are done and we should return
 133      */
 134     LIST_FOREACH(pnode, simhead, next_node) {
 135         if (t == pnode->lifetime) {
 136             /*printf("freeing %u\tptr = %p\n", t, pnode->ptr);*/
 137             mpool_free(mpool, pnode->ptr);
 138             LIST_REMOVE(pnode, next_node);
 139         }
 140         else
 141             return;
 142     }
 143 }
 144
 145 void sim_print_stats(const mpool_t *mpool, unsigned int t, FILE *fp)
 146 {
 147     size_t an, un;    /* nodes */
 148     size_t ab, ub;    /* blocks */
 149     size_t me = 1, sp = 1;    /* merges, splits */
 150     /*size_t i;*/
 151
 152     mpool_stat_get_nodes(mpool, &an, &un);
 153     mpool_stat_get_bytes(mpool, &ab, &ub);
 154     me = mpool_stat_get_merges(mpool);
 155     sp = mpool_stat_get_splits(mpool);
 156
 157     fprintf(fp, "%u\t%u\t%u\t%.2f\t%u\t%u\t%.2f\t%u\t%u\t%.2f\n",
 158             t, an, un, 100.0 * an / (an + un), ab, ub, 100.0 * ab / (ab + ub), sp, me, 1.0*sp/me);
 159
 160     /* Print length of every block
 161        for (i = 0; i < mpool_stat_get_blocks(mpool); i++)
 162        fprintf(fp, "%u\t", mpool_stat_get_block_length(mpool, i));
 163        fprintf(fp, "\n");
 164     */
 165 }