Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
f3cf2effc36720ae3eacf33242eb8a9d9b83cf6d
[simgrid.git] / src / surf / trace_mgr.cpp
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 "src/surf/trace_mgr.hpp"
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 tmgr_fes_t tmgr_history_new(void)
21 {
22   tmgr_fes_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 void tmgr_history_free(tmgr_fes_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                                   int first_event_hostIsOn)
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_hostIsOn;
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                                 int first_event_hostIsOn)
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_hostIsOn;
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 = (tmgr_trace_t)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 = (tmgr_event_t)xbt_dynar_get_ptr(trace->s_list.event_list, xbt_dynar_length(trace->s_list.event_list) - 1);
309   }
310   if (last_event)
311     last_event->delta = periodicity;
312
313   if (!trace_list)
314     trace_list = xbt_dict_new_homogeneous((void (*)(void *)) tmgr_trace_free);
315
316   xbt_dict_set(trace_list, id, (void *) trace, NULL);
317
318   xbt_dynar_free(&list);
319   return trace;
320 }
321
322 tmgr_trace_t tmgr_trace_new_from_file(const char *filename)
323 {
324   char *tstr = NULL;
325   FILE *f = NULL;
326   tmgr_trace_t trace = NULL;
327
328   if ((!filename) || (strcmp(filename, "") == 0))
329     return NULL;
330
331   if (trace_list) {
332     trace = (tmgr_trace_t)xbt_dict_get_or_null(trace_list, filename);
333     if (trace) {
334       XBT_WARN("Ignoring redefinition of trace %s", filename);
335       return trace;
336     }
337   }
338
339   f = surf_fopen(filename, "r");
340   if (f == NULL)
341     xbt_die("Cannot open file '%s' (path=%s)", filename,
342             xbt_str_join(surf_path, ":"));
343
344   tstr = xbt_str_from_file(f);
345   fclose(f);
346   trace = tmgr_trace_new_from_string(filename, tstr, 0.);
347   xbt_free(tstr);
348
349   return trace;
350 }
351
352 tmgr_trace_t tmgr_empty_trace_new(void)
353 {
354   tmgr_trace_t trace = NULL;
355   s_tmgr_event_t event;
356
357   trace = xbt_new0(s_tmgr_trace_t, 1);
358   trace->type = e_trace_list;
359   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
360
361   event.delta = 0.0;
362   event.value = 0.0;
363   xbt_dynar_push(trace->s_list.event_list, &event);
364
365   return trace;
366 }
367
368 void tmgr_trace_free(tmgr_trace_t trace)
369 {
370   if (!trace)
371     return;
372
373   switch(trace->type) {
374     case e_trace_list:
375       xbt_dynar_free(&(trace->s_list.event_list));
376       break;
377     case e_trace_probabilist:
378       THROW_UNIMPLEMENTED;
379       break;
380   }
381   free(trace);
382 }
383
384 tmgr_trace_iterator_t tmgr_history_add_trace(tmgr_fes_t h,
385                                           tmgr_trace_t trace,
386                                           double start_time,
387                                           unsigned int offset, void *resource)
388 {
389   tmgr_trace_iterator_t trace_iterator = NULL;
390
391   trace_iterator = xbt_new0(s_tmgr_trace_event_t, 1);
392   trace_iterator->trace = trace;
393   trace_iterator->idx = offset;
394   trace_iterator->resource = resource;
395
396   if(trace->type == e_trace_list) {
397     xbt_assert((trace_iterator->idx < xbt_dynar_length(trace->s_list.event_list)),
398               "You're referring to an event that does not exist!");
399   }
400
401   xbt_heap_push(h->heap, trace_iterator, start_time);
402
403   return trace_iterator;
404 }
405
406 double tmgr_history_next_date(tmgr_fes_t h)
407 {
408   if (xbt_heap_size(h->heap))
409     return (xbt_heap_maxkey(h->heap));
410   else
411     return -1.0;
412 }
413
414 tmgr_trace_iterator_t tmgr_history_get_next_event_leq(tmgr_fes_t h,
415                                                    double date,
416                                                    double *value,
417                                                    void** resource)
418 {
419   double event_date = tmgr_history_next_date(h);
420   tmgr_trace_iterator_t trace_iterator = NULL;
421   tmgr_event_t event = NULL;
422   tmgr_trace_t trace = NULL;
423   double event_delta;
424
425   if (event_date > date)
426     return NULL;
427
428   if (!(trace_iterator = (tmgr_trace_iterator_t)xbt_heap_pop(h->heap)))
429     return NULL;
430
431   trace = trace_iterator->trace;
432   *resource = trace_iterator->resource;
433
434   switch(trace->type) {
435     case e_trace_list:
436
437       event = (tmgr_event_t)xbt_dynar_get_ptr(trace->s_list.event_list, trace_iterator->idx);
438
439       *value = event->value;
440
441       if (trace_iterator->idx < xbt_dynar_length(trace->s_list.event_list) - 1) {
442         xbt_heap_push(h->heap, trace_iterator, event_date + event->delta);
443         trace_iterator->idx++;
444       } else if (event->delta > 0) {        /* Last element, checking for periodicity */
445         xbt_heap_push(h->heap, trace_iterator, event_date + event->delta);
446         trace_iterator->idx = 1; /* not 0 as the first event is a placeholder to handle when events really start */
447       } else {                      /* We don't need this trace_event anymore */
448         trace_iterator->free_me = 1;
449       }
450       break;
451
452     case e_trace_probabilist:
453
454       //FIXME : not tested yet
455       if(trace->s_probabilist.is_state_trace) {
456         *value = (double) trace->s_probabilist.next_event;
457         if(trace->s_probabilist.next_event == 0) {
458           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
459           trace->s_probabilist.next_event = 1;
460         } else {
461           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
462           trace->s_probabilist.next_event = 0;
463         }
464       } else {
465         event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
466         *value = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
467       }
468       xbt_heap_push(h->heap, trace_iterator, event_date + event_delta);
469       XBT_DEBUG("Generating a new event at date %f, with value %f", event_date + event_delta, *value);
470
471       break;
472   }
473
474   return trace_iterator;
475 }
476
477 void tmgr_finalize(void)
478 {
479   xbt_dict_free(&trace_list);
480 }
481
482 int tmgr_trace_event_free(tmgr_trace_iterator_t trace_event)
483 {
484   if (trace_event->free_me) {
485     xbt_free(trace_event);
486     return 1;
487   }
488   return 0;
489 }