src/surf/trace_mgr.c

   1 /* Copyright (c) 2004-2005, 2007, 2009-2014. 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
  38 /**
  39  * \brief Create a #tmgr_trace_t from probabilist generators
  40  *
  41  * This trace will generate an infinite set of events.
  42  * It needs two #probabilist_event_generator_t. The date when the event are
  43  * triggered is directed by date_generator, and will be interpreted as seconds.
  44  * The value of the event is set by value_generator. The value should be between
  45  * 0 and 1.
  46  *
  47  * \param id The name of the trace
  48  * \param date_generator The #probabilist_event_generator_t which generates the time
  49  *        between two events
  50  * \param generator2 The #probabilist_event_generator_t which generates the value
  51  *        of each events.
  52  * \return The new #tmgr_trace_t
  53  */
  54 tmgr_trace_t tmgr_trace_generator_value(const char *id,
  55                                   probabilist_event_generator_t date_generator,
  56                                   probabilist_event_generator_t value_generator)
  57 {
  58   tmgr_trace_t trace = NULL;
  59
  60   trace = xbt_new0(s_tmgr_trace_t, 1);
  61   trace->type = e_trace_probabilist;
  62
  63   trace->s_probabilist.event_generator[0] = date_generator;
  64   trace->s_probabilist.event_generator[1] = value_generator;
  65   trace->s_probabilist.is_state_trace = 0;
  66
  67   return trace;
  68 }
  69
  70 /**
  71  * \brief Create a #tmgr_trace_t from probabilist generators
  72  *
  73  * This trace will generate an infinite set of events. Value of the events
  74  * will be alternatively 0 and 1, so this should be used as a state trace.
  75  *
  76  * \param id The name of the trace
  77  * \param date_generator The #probabilist_event_generator_t which generates the time
  78  *        between two events
  79  * \param first_event_value Set the first event value
  80  * \return The new #tmgr_trace_t
  81  */
  82 tmgr_trace_t tmgr_trace_generator_state(const char *id,
  83                                   probabilist_event_generator_t date_generator,
  84                                   e_surf_resource_state_t first_event_value)
  85 {
  86   tmgr_trace_t trace = NULL;
  87
  88   trace = xbt_new0(s_tmgr_trace_t, 1);
  89   trace->type = e_trace_probabilist;
  90
  91   trace->s_probabilist.event_generator[0] = date_generator;
  92   trace->s_probabilist.event_generator[1] = date_generator;
  93   trace->s_probabilist.is_state_trace = 1;
  94   trace->s_probabilist.next_event = (first_event_value==SURF_RESOURCE_ON ? 1 : 0);
  95
  96   return trace;
  97 }
  98
  99 /**
 100  * \brief Create a #tmgr_trace_t from probabilist generators
 101  *
 102  * This trace will generate an infinite set of events. Value of the events
 103  * will be alternatively 0 and 1, so this should be used as a state trace.
 104  *
 105  * \param id The name of the trace
 106  * \param avail_duration_generator The #probabilist_event_generator_t which
 107  *        set the duration of the available state, (ie 1 value)
 108  * \param unavail_duration_generator The #probabilist_event_generator_t which
 109  *        set the duration of the unavailable state, (ie 0 value)
 110  * \param first_event_value Set the first event value
 111  * \return The new #tmgr_trace_t
 112  */
 113 tmgr_trace_t tmgr_trace_generator_avail_unavail(const char *id,
 114                                 probabilist_event_generator_t avail_duration_generator,
 115                                 probabilist_event_generator_t unavail_duration_generator,
 116                                 e_surf_resource_state_t first_event_value)
 117 {
 118   tmgr_trace_t trace = NULL;
 119
 120   trace = xbt_new0(s_tmgr_trace_t, 1);
 121   trace->type = e_trace_probabilist;
 122
 123   trace->s_probabilist.event_generator[0] = unavail_duration_generator;
 124   trace->s_probabilist.event_generator[1] = avail_duration_generator;
 125   trace->s_probabilist.is_state_trace = 1;
 126   trace->s_probabilist.next_event = (first_event_value==SURF_RESOURCE_ON ? 1 : 0);
 127
 128   return trace;
 129 }
 130
 131 /**
 132  * \brief Create a new #probabilist_event_generator_t following the uniform distribution
 133  *
 134  * This generator will generate uniformly distributed random values between min and max
 135  * The id is important : it controls the seed of the generator. So, generators with the
 136  * same id and the same parameters will generate the same values.
 137  *
 138  * \param id The name of the generator
 139  * \param min The minimal generated value
 140  * \param max The maximal generated value
 141  * \return a new #probabilist_event_generator_t
 142  */
 143 probabilist_event_generator_t tmgr_event_generator_new_uniform(const char* id,
 144                                                                double min,
 145                                                                double max)
 146 {
 147   probabilist_event_generator_t event_generator = NULL;
 148   RngStream rng_stream = NULL;
 149
 150   rng_stream = sg_platf_rng_stream_get(id);
 151
 152   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
 153   event_generator->type = e_generator_uniform;
 154   event_generator->s_uniform_parameters.min = min;
 155   event_generator->s_uniform_parameters.max = max;
 156   event_generator->rng_stream = rng_stream;
 157
 158   tmgr_event_generator_next_value(event_generator);
 159
 160   return event_generator;
 161 }
 162
 163
 164 /**
 165  * \brief Create a new #probabilist_event_generator_t following the exponential distribution
 166  *
 167  * This generator will generate random values following the exponential distribution.
 168  * The mean value is 1/rate .
 169  * The id is important : it controls the seed of the generator. So, generators with the
 170  * same id and the same parameters will generate the same values.
 171  *
 172  * \param id The name of the generator
 173  * \param rate The rate parameter
 174  * \return a new #probabilist_event_generator_t
 175  */
 176 probabilist_event_generator_t tmgr_event_generator_new_exponential(const char* id,
 177                                                                    double rate)
 178 {
 179   probabilist_event_generator_t event_generator = NULL;
 180   RngStream rng_stream = NULL;
 181
 182   rng_stream = sg_platf_rng_stream_get(id);
 183
 184   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
 185   event_generator->type = e_generator_exponential;
 186   event_generator->s_exponential_parameters.rate = rate;
 187   event_generator->rng_stream = rng_stream;
 188
 189   tmgr_event_generator_next_value(event_generator);
 190
 191   return event_generator;
 192 }
 193
 194 /**
 195  * \brief Create a new #probabilist_event_generator_t following the weibull distribution
 196  *
 197  * This generator will generate random values following the weibull distribution.
 198  * The id is important : it controls the seed of the generator. So, generators with the
 199  * same id and the same parameters will generate the same values.
 200  *
 201  * \param id The name of the generator
 202  * \param scale The scale parameter
 203  * \param shape The shape parameter
 204  * \return a new #probabilist_event_generator_t
 205  */
 206 probabilist_event_generator_t tmgr_event_generator_new_weibull(const char* id,
 207                                                                double scale,
 208                                                                double shape)
 209 {
 210   probabilist_event_generator_t event_generator = NULL;
 211   RngStream rng_stream = NULL;
 212
 213   rng_stream = sg_platf_rng_stream_get(id);
 214
 215   event_generator = xbt_new0(s_probabilist_event_generator_t, 1);
 216   event_generator->type = e_generator_weibull;
 217   event_generator->s_weibull_parameters.scale = scale;
 218   event_generator->s_weibull_parameters.shape = shape;
 219   event_generator->rng_stream = rng_stream;
 220
 221   tmgr_event_generator_next_value(event_generator);
 222
 223   return event_generator;
 224 }
 225 /**
 226  * \brief Get the next random value of a #probabilist_event_generator_t
 227  * \param generator The #probabilist_event_generator_t
 228  * \return the next random value
 229  */
 230 double tmgr_event_generator_next_value(probabilist_event_generator_t generator)
 231 {
 232
 233   switch(generator->type) {
 234     case e_generator_uniform:
 235       generator->next_value = (RngStream_RandU01(generator->rng_stream)
 236                   * (generator->s_uniform_parameters.max - generator->s_uniform_parameters.min))
 237                   + generator->s_uniform_parameters.min;
 238       break;
 239     case e_generator_exponential:
 240       generator->next_value = -log(RngStream_RandU01(generator->rng_stream))
 241                               / generator->s_exponential_parameters.rate;
 242       break;
 243     case e_generator_weibull:
 244       generator->next_value = generator->s_weibull_parameters.scale
 245                               * pow( -log(RngStream_RandU01(generator->rng_stream)),
 246                                     1.0 / generator->s_weibull_parameters.shape );
 247   }
 248
 249   return generator->next_value;
 250 }
 251
 252 tmgr_trace_t tmgr_trace_new_from_string(const char *id, const char *input,
 253                                         double periodicity)
 254 {
 255   tmgr_trace_t trace = NULL;
 256   int linecount = 0;
 257   s_tmgr_event_t event;
 258   tmgr_event_t last_event = NULL;
 259   xbt_dynar_t list;
 260   unsigned int cpt;
 261   char *val;
 262
 263   if (trace_list) {
 264     trace = xbt_dict_get_or_null(trace_list, id);
 265     if (trace) {
 266       XBT_WARN("Ignoring redefinition of trace %s", id);
 267       return trace;
 268     }
 269   }
 270
 271   xbt_assert(periodicity >= 0,
 272               "Invalid periodicity %g (must be positive)", periodicity);
 273
 274   trace = xbt_new0(s_tmgr_trace_t, 1);
 275   trace->type = e_trace_list;
 276   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
 277
 278   list = xbt_str_split(input, "\n\r");
 279
 280   xbt_dynar_foreach(list, cpt, val) {
 281     linecount++;
 282     xbt_str_trim(val, " \t\n\r\x0B");
 283     if (val[0] == '#' || val[0] == '\0' || val[0] == '%')
 284       continue;
 285
 286     if (sscanf(val, "PERIODICITY " "%lg" "\n", &periodicity) == 1)
 287       continue;
 288
 289     if (sscanf(val, "%lg" " " "%lg" "\n", &event.delta, &event.value) != 2)
 290       xbt_die("%s:%d: Syntax error in trace\n%s", id, linecount, input);
 291
 292     if (last_event) {
 293       if (last_event->delta > event.delta) {
 294         xbt_die("%s:%d: Invalid trace: Events must be sorted, "
 295                 "but time %g > time %g.\n%s",
 296                 id, linecount, last_event->delta, event.delta, input);
 297       }
 298       last_event->delta = event.delta - last_event->delta;
 299     } else {
 300       if(event.delta > 0.0){
 301         s_tmgr_event_t first_event;
 302         first_event.delta=event.delta;
 303         first_event.value=-1.0;
 304         xbt_dynar_push(trace->s_list.event_list, &first_event);
 305       }
 306     }
 307     xbt_dynar_push(trace->s_list.event_list, &event);
 308     last_event =
 309         xbt_dynar_get_ptr(trace->s_list.event_list,
 310                           xbt_dynar_length(trace->s_list.event_list) - 1);
 311   }
 312   if (last_event)
 313     last_event->delta = periodicity;
 314
 315   if (!trace_list)
 316     trace_list = xbt_dict_new_homogeneous((void (*)(void *)) tmgr_trace_free);
 317
 318   xbt_dict_set(trace_list, id, (void *) trace, NULL);
 319
 320   xbt_dynar_free(&list);
 321   return trace;
 322 }
 323
 324 tmgr_trace_t tmgr_trace_new_from_file(const char *filename)
 325 {
 326   char *tstr = NULL;
 327   FILE *f = NULL;
 328   tmgr_trace_t trace = NULL;
 329
 330   if ((!filename) || (strcmp(filename, "") == 0))
 331     return NULL;
 332
 333   if (trace_list) {
 334     trace = xbt_dict_get_or_null(trace_list, filename);
 335     if (trace) {
 336       XBT_WARN("Ignoring redefinition of trace %s", filename);
 337       return trace;
 338     }
 339   }
 340
 341   f = surf_fopen(filename, "r");
 342   if (f == NULL)
 343     xbt_die("Cannot open file '%s' (path=%s)", filename,
 344             xbt_str_join(surf_path, ":"));
 345
 346   tstr = xbt_str_from_file(f);
 347   fclose(f);
 348   trace = tmgr_trace_new_from_string(filename, tstr, 0.);
 349   xbt_free(tstr);
 350
 351   return trace;
 352 }
 353
 354 tmgr_trace_t tmgr_empty_trace_new(void)
 355 {
 356   tmgr_trace_t trace = NULL;
 357   s_tmgr_event_t event;
 358
 359   trace = xbt_new0(s_tmgr_trace_t, 1);
 360   trace->type = e_trace_list;
 361   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
 362
 363   event.delta = 0.0;
 364   event.value = 0.0;
 365   xbt_dynar_push(trace->s_list.event_list, &event);
 366
 367   return trace;
 368 }
 369
 370 XBT_INLINE void tmgr_trace_free(tmgr_trace_t trace)
 371 {
 372   if (!trace)
 373     return;
 374
 375   switch(trace->type) {
 376     case e_trace_list:
 377       xbt_dynar_free(&(trace->s_list.event_list));
 378       break;
 379     case e_trace_probabilist:
 380       THROW_UNIMPLEMENTED;
 381       break;
 382   }
 383   free(trace);
 384 }
 385
 386 tmgr_trace_event_t tmgr_history_add_trace(tmgr_history_t h,
 387                                           tmgr_trace_t trace,
 388                                           double start_time,
 389                                           unsigned int offset, void *model)
 390 {
 391   tmgr_trace_event_t trace_event = NULL;
 392
 393   trace_event = xbt_new0(s_tmgr_trace_event_t, 1);
 394   trace_event->trace = trace;
 395   trace_event->idx = offset;
 396   trace_event->model = model;
 397
 398   if(trace->type == e_trace_list) {
 399     xbt_assert((trace_event->idx < xbt_dynar_length(trace->s_list.event_list)),
 400               "You're referring to an event that does not exist!");
 401   }
 402
 403   xbt_heap_push(h->heap, trace_event, start_time);
 404
 405   return trace_event;
 406 }
 407
 408 XBT_INLINE double tmgr_history_next_date(tmgr_history_t h)
 409 {
 410   if (xbt_heap_size(h->heap))
 411     return (xbt_heap_maxkey(h->heap));
 412   else
 413     return -1.0;
 414 }
 415
 416 tmgr_trace_event_t tmgr_history_get_next_event_leq(tmgr_history_t h,
 417                                                    double date,
 418                                                    double *value,
 419                                                    void **model)
 420 {
 421   double event_date = tmgr_history_next_date(h);
 422   tmgr_trace_event_t trace_event = NULL;
 423   tmgr_event_t event = NULL;
 424   tmgr_trace_t trace = NULL;
 425   double event_delta;
 426
 427   if (event_date > date)
 428     return NULL;
 429
 430   if (!(trace_event = xbt_heap_pop(h->heap)))
 431     return NULL;
 432
 433   trace = trace_event->trace;
 434   *model = trace_event->model;
 435
 436   switch(trace->type) {
 437     case e_trace_list:
 438
 439       event = xbt_dynar_get_ptr(trace->s_list.event_list, trace_event->idx);
 440
 441       *value = event->value;
 442
 443       if (trace_event->idx < xbt_dynar_length(trace->s_list.event_list) - 1) {
 444         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
 445         trace_event->idx++;
 446       } else if (event->delta > 0) {        /* Last element, checking for periodicity */
 447         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
 448         trace_event->idx = 1; /* not 0 as the first event is a placeholder to handle when events really start */
 449       } else {                      /* We don't need this trace_event anymore */
 450         trace_event->free_me = 1;
 451       }
 452       break;
 453
 454     case e_trace_probabilist:
 455
 456       //FIXME : not tested yet
 457       if(trace->s_probabilist.is_state_trace) {
 458         *value = (double) trace->s_probabilist.next_event;
 459         if(trace->s_probabilist.next_event == 0) {
 460           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
 461           trace->s_probabilist.next_event = 1;
 462         } else {
 463           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
 464           trace->s_probabilist.next_event = 0;
 465         }
 466       } else {
 467         event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
 468         *value = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
 469       }
 470       xbt_heap_push(h->heap, trace_event, event_date + event_delta);
 471       XBT_DEBUG("Generating a new event at date %f, with value %f", event_date + event_delta, *value);
 472
 473       break;
 474   }
 475
 476   return trace_event;
 477 }
 478
 479 XBT_INLINE void tmgr_finalize(void)
 480 {
 481   xbt_dict_free(&trace_list);
 482 }
 483
 484 int tmgr_trace_event_free(tmgr_trace_event_t trace_event)
 485 {
 486   if (trace_event->free_me) {
 487     xbt_free(trace_event);
 488     return 1;
 489   }
 490   return 0;
 491 }