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