buddy/test4.c

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