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