malloc/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     LIST_FOREACH(pnode, simhead, next_node) {
 115         if (simnode->lifetime < pnode->lifetime) {
 116             LIST_INSERT_BEFORE(pnode, simnode, next_node);
 117             return;
 118         }
 119         else if (LIST_NEXT(pnode, next_node) == NULL) {
 120             LIST_INSERT_AFTER(pnode, simnode, next_node);
 121             return;
 122         }
 123    }
 124
 125     /* 1st element goes here -- this is called only when the list is empty */
 126     LIST_INSERT_HEAD(simhead, simnode, next_node);
 127 }
 128
 129 void sim_free_from_list(mpool_t *mpool, simhead_t *simhead, unsigned int t)
 130 {
 131     simnode_t *pnode;
 132
 133     /*
 134      * Blocks with the same lifetime are placed together,
 135      * e.g. ... -> 5 -> 5 -> 7 -> 7 -> 7 -> 7 -> 8 -> 8 -> 9 -> 9 -> ...
 136      * That said, if the continuity breaks in one node,
 137      * we are done and we should return
 138      */
 139     LIST_FOREACH(pnode, simhead, next_node) {
 140         if (t == pnode->lifetime) {
 141             /*printf("freeing %u\tptr = %p\n", t, pnode->ptr);*/
 142             mpool_free(mpool, pnode->ptr);
 143             LIST_REMOVE(pnode, next_node);
 144         }
 145         else
 146             return;
 147     }
 148 }
 149
 150 void sim_print_stats(const mpool_t *mpool, unsigned int t, FILE *fp)
 151 {
 152     size_t an, un;    /* nodes */
 153     size_t ab, ub;    /* blocks */
 154     size_t me = 1, sp = 1;    /* merges, splits */
 155     /*size_t i;*/
 156
 157     mpool_stat_get_nodes(mpool, &an, &un);
 158     mpool_stat_get_bytes(mpool, &ab, &ub);
 159     me = mpool_stat_get_merges(mpool);
 160     sp = mpool_stat_get_splits(mpool);
 161
 162     fprintf(fp, "%u\t%u\t%u\t%.2f\t%u\t%u\t%.2f\t%u\t%u\t%.2f\n",
 163             t, an, un, 100.0 * an / (an + un), ab, ub, 100.0 * ab / (ab + ub), sp, me, 1.0*sp/me);
 164
 165     /* Print length of every block
 166        for (i = 0; i < mpool_stat_get_blocks(mpool); i++)
 167        fprintf(fp, "%u\t", mpool_stat_get_block_length(mpool, i));
 168        fprintf(fp, "\n");
 169     */
 170 }