src/surf/trace_mgr.c

   1 /* Copyright (c) 2004, 2005, 2007, 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include "xbt/sysdep.h"
   8 #include "xbt/log.h"
   9 #include "xbt/str.h"
  10 #include "xbt/dict.h"
  11 #include "trace_mgr_private.h"
  12 #include "surf_private.h"
  13 #include "xbt/RngStream.h"
  14 #include <math.h>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_trace, surf, "Surf trace management");
  17
  18 static xbt_dict_t trace_list = NULL;
  19
  20 // a unique RngStream structure for everyone
  21 // FIXME : has to be created by someone
  22 static RngStream common_rng_stream = NULL;
  23
  24 XBT_INLINE tmgr_history_t tmgr_history_new(void)
  25 {
  26   tmgr_history_t h;
  27
  28   h = xbt_new0(s_tmgr_history_t, 1);
  29
  30   h->heap = xbt_heap_new(8, xbt_free_f);        /* Why 8 ? Well, why not... */
  31
  32   return h;
  33 }
  34
  35 XBT_INLINE void tmgr_history_free(tmgr_history_t h)
  36 {
  37   xbt_heap_free(h->heap);
  38   free(h);
  39 }
  40
  41 tmgr_trace_t tmgr_trace_new_from_generator(const char *id,
  42                                           probabilist_event_generator_t generator1,
  43                                           probabilist_event_generator_t generator2)
  44 {
  45   tmgr_trace_t trace = NULL;
  46   unsigned int id_hash;
  47   RngStream rng_stream = NULL;
  48
  49   rng_stream = RngStream_CopyStream(common_rng_stream);
  50   id_hash = xbt_dict_hash(id);
  51   RngStream_AdvanceState(rng_stream, 0, id_hash);
  52
  53   trace = xbt_new0(s_tmgr_trace_t, 1);
  54   trace->type = e_trace_probabilist;
  55
  56   trace->s_probabilist.event_generator[0] = generator1;
  57   trace->s_probabilist.event_generator[0]->rng_stream = rng_stream;
  58   tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
  59
  60   //FIXME : may also be a parameter
  61   trace->s_probabilist.next_event = 0;
  62
  63   if(generator2 == NULL) {
  64     trace->s_probabilist.event_generator[0] = generator1;
  65   } else {
  66     trace->s_probabilist.event_generator[1] = generator2;
  67     trace->s_probabilist.event_generator[1]->rng_stream = rng_stream;
  68     tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
  69   }
  70
  71   return trace;
  72 }
  73
  74 probabilist_event_generator_t tmgr_event_generator_new_uniform(double alpha,
  75                                                                double beta)
  76 {
  77   probabilist_event_generator_t event_generator = NULL;
  78
  79   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
  80   event_generator->type = e_generator_uniform;
  81   event_generator->s_uniform_parameters.alpha = alpha;
  82   event_generator->s_uniform_parameters.beta = beta;
  83
  84   tmgr_event_generator_next_value(event_generator);
  85
  86   return event_generator;
  87 }
  88
  89 probabilist_event_generator_t tmgr_event_generator_new_exponential(double lambda)
  90 {
  91   probabilist_event_generator_t event_generator = NULL;
  92
  93   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
  94   event_generator->type = e_generator_exponential;
  95   event_generator->s_exponential_parameters.lambda = lambda;
  96
  97   return event_generator;
  98 }
  99
 100 probabilist_event_generator_t tmgr_event_generator_new_weibull(double lambda,
 101                                                                double k)
 102 {
 103   probabilist_event_generator_t event_generator = NULL;
 104
 105   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
 106   event_generator->type = e_generator_weibull;
 107   event_generator->s_weibull_parameters.lambda = lambda;
 108   event_generator->s_weibull_parameters.k = k;
 109
 110   tmgr_event_generator_next_value(event_generator);
 111
 112   return event_generator;
 113 }
 114
 115 double tmgr_event_generator_next_value(probabilist_event_generator_t generator)
 116 {
 117
 118   switch(generator->type) {
 119     case e_generator_uniform:
 120       generator->next_value = (RngStream_RandU01(generator->rng_stream)
 121                   * (generator->s_uniform_parameters.beta - generator->s_uniform_parameters.alpha))
 122                   + generator->s_uniform_parameters.alpha;
 123       break;
 124     case e_generator_exponential:
 125       generator->next_value = -log(RngStream_RandU01(generator->rng_stream))
 126                               / generator->s_exponential_parameters.lambda;
 127       break;
 128     case e_generator_weibull:
 129       generator->next_value = - generator->s_weibull_parameters.lambda
 130                               * pow( log(RngStream_RandU01(generator->rng_stream)),
 131                                     1.0 / generator->s_weibull_parameters.k );
 132   }
 133
 134   return generator->next_value;
 135 }
 136
 137 tmgr_trace_t tmgr_trace_new_from_string(const char *id, const char *input,
 138                                         double periodicity)
 139 {
 140   tmgr_trace_t trace = NULL;
 141   int linecount = 0;
 142   s_tmgr_event_t event;
 143   tmgr_event_t last_event = NULL;
 144   xbt_dynar_t list;
 145   unsigned int cpt;
 146   char *val;
 147
 148   if (trace_list) {
 149     trace = xbt_dict_get_or_null(trace_list, id);
 150     if (trace) {
 151       XBT_WARN("Ignoring redefinition of trace %s", id);
 152       return trace;
 153     }
 154   }
 155
 156   xbt_assert(periodicity >= 0,
 157               "Invalid periodicity %lg (must be positive)", periodicity);
 158
 159   trace = xbt_new0(s_tmgr_trace_t, 1);
 160   trace->type = e_trace_list;
 161   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
 162
 163   list = xbt_str_split(input, "\n\r");
 164
 165   xbt_dynar_foreach(list, cpt, val) {
 166     linecount++;
 167     xbt_str_trim(val, " \t\n\r\x0B");
 168     if (val[0] == '#' || val[0] == '\0' || val[0] == '%')
 169       continue;
 170
 171     if (sscanf(val, "PERIODICITY " "%lg" "\n", &periodicity) == 1)
 172       continue;
 173
 174     if (sscanf(val, "%lg" " " "%lg" "\n", &event.delta, &event.value) != 2)
 175       xbt_die("%s:%d: Syntax error in trace\n%s", id, linecount, input);
 176
 177     if (last_event) {
 178       if (last_event->delta > event.delta) {
 179         xbt_die("%s:%d: Invalid trace: Events must be sorted, "
 180                 "but time %lg > time %lg.\n%s",
 181                 id, linecount, last_event->delta, event.delta, input);
 182       }
 183       last_event->delta = event.delta - last_event->delta;
 184     }
 185     xbt_dynar_push(trace->s_list.event_list, &event);
 186     last_event =
 187         xbt_dynar_get_ptr(trace->s_list.event_list,
 188                           xbt_dynar_length(trace->s_list.event_list) - 1);
 189   }
 190   if (last_event)
 191     last_event->delta = periodicity;
 192
 193   if (!trace_list)
 194     trace_list = xbt_dict_new_homogeneous((void (*)(void *)) tmgr_trace_free);
 195
 196   xbt_dict_set(trace_list, id, (void *) trace, NULL);
 197
 198   xbt_dynar_free(&list);
 199   return trace;
 200 }
 201
 202 tmgr_trace_t tmgr_trace_new_from_file(const char *filename)
 203 {
 204   char *tstr = NULL;
 205   FILE *f = NULL;
 206   tmgr_trace_t trace = NULL;
 207
 208   if ((!filename) || (strcmp(filename, "") == 0))
 209     return NULL;
 210
 211   if (trace_list) {
 212     trace = xbt_dict_get_or_null(trace_list, filename);
 213     if (trace) {
 214       XBT_WARN("Ignoring redefinition of trace %s", filename);
 215       return trace;
 216     }
 217   }
 218
 219   f = surf_fopen(filename, "r");
 220   xbt_assert(f != NULL, "Cannot open file '%s' (path=%s)", filename,
 221               xbt_str_join(surf_path, ":"));
 222
 223   tstr = xbt_str_from_file(f);
 224   fclose(f);
 225   trace = tmgr_trace_new_from_string(filename, tstr, 0.);
 226   xbt_free(tstr);
 227
 228   return trace;
 229 }
 230
 231 tmgr_trace_t tmgr_empty_trace_new(void)
 232 {
 233   tmgr_trace_t trace = NULL;
 234   s_tmgr_event_t event;
 235
 236   trace = xbt_new0(s_tmgr_trace_t, 1);
 237   trace->type = e_trace_list;
 238   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
 239
 240   event.delta = 0.0;
 241   event.value = 0.0;
 242   xbt_dynar_push(trace->s_list.event_list, &event);
 243
 244   return trace;
 245 }
 246
 247 XBT_INLINE void tmgr_trace_free(tmgr_trace_t trace)
 248 {
 249   if (!trace)
 250     return;
 251
 252   switch(trace->type) {
 253     case e_trace_list:
 254       xbt_dynar_free(&(trace->s_list.event_list));
 255       break;
 256     case e_trace_probabilist:
 257       THROW_UNIMPLEMENTED;
 258       break;
 259   }
 260   free(trace);
 261 }
 262
 263 tmgr_trace_event_t tmgr_history_add_trace(tmgr_history_t h,
 264                                           tmgr_trace_t trace,
 265                                           double start_time,
 266                                           unsigned int offset, void *model)
 267 {
 268   tmgr_trace_event_t trace_event = NULL;
 269
 270   trace_event = xbt_new0(s_tmgr_trace_event_t, 1);
 271   trace_event->trace = trace;
 272   trace_event->idx = offset;
 273   trace_event->model = model;
 274
 275   if(trace->type == e_trace_list) {
 276     xbt_assert((trace_event->idx < xbt_dynar_length(trace->s_list.event_list)),
 277               "You're referring to an event that does not exist!");
 278   }
 279
 280   xbt_heap_push(h->heap, trace_event, start_time);
 281
 282   return trace_event;
 283 }
 284
 285 XBT_INLINE double tmgr_history_next_date(tmgr_history_t h)
 286 {
 287   if (xbt_heap_size(h->heap))
 288     return (xbt_heap_maxkey(h->heap));
 289   else
 290     return -1.0;
 291 }
 292
 293 tmgr_trace_event_t tmgr_history_get_next_event_leq(tmgr_history_t h,
 294                                                    double date,
 295                                                    double *value,
 296                                                    void **model)
 297 {
 298   double event_date = tmgr_history_next_date(h);
 299   tmgr_trace_event_t trace_event = NULL;
 300   tmgr_event_t event = NULL;
 301   tmgr_trace_t trace = NULL;
 302
 303   if (event_date > date)
 304     return NULL;
 305
 306   if (!(trace_event = xbt_heap_pop(h->heap)))
 307     return NULL;
 308
 309   trace = trace_event->trace;
 310
 311   switch(trace->type) {
 312     case e_trace_list:
 313
 314       event = xbt_dynar_get_ptr(trace->s_list.event_list, trace_event->idx);
 315
 316       *value = event->value;
 317       *model = trace_event->model;
 318
 319       if (trace_event->idx < xbt_dynar_length(trace->s_list.event_list) - 1) {
 320         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
 321         trace_event->idx++;
 322       } else if (event->delta > 0) {        /* Last element, checking for periodicity */
 323         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
 324         trace_event->idx = 0;
 325       } else {                      /* We don't need this trace_event anymore */
 326         trace_event->free_me = 1;
 327       }
 328       break;
 329
 330     case e_trace_probabilist:
 331       THROW_UNIMPLEMENTED;
 332       break;
 333   }
 334
 335   return trace_event;
 336 }
 337
 338 XBT_INLINE void tmgr_finalize(void)
 339 {
 340   xbt_dict_free(&trace_list);
 341 }
 342
 343 int tmgr_trace_event_free(tmgr_trace_event_t trace_event)
 344 {
 345   if (trace_event->free_me) {
 346     xbt_free(trace_event);
 347     return 1;
 348   }
 349   return 0;
 350 }