Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Bug fix in trace management.
[simgrid.git] / 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. 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 %lg (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 %lg > time %lg.\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   xbt_assert(f != NULL, "Cannot open file '%s' (path=%s)", filename,
343               xbt_str_join(surf_path, ":"));
344
345   tstr = xbt_str_from_file(f);
346   fclose(f);
347   trace = tmgr_trace_new_from_string(filename, tstr, 0.);
348   xbt_free(tstr);
349
350   return trace;
351 }
352
353 tmgr_trace_t tmgr_empty_trace_new(void)
354 {
355   tmgr_trace_t trace = NULL;
356   s_tmgr_event_t event;
357
358   trace = xbt_new0(s_tmgr_trace_t, 1);
359   trace->type = e_trace_list;
360   trace->s_list.event_list = xbt_dynar_new(sizeof(s_tmgr_event_t), NULL);
361
362   event.delta = 0.0;
363   event.value = 0.0;
364   xbt_dynar_push(trace->s_list.event_list, &event);
365
366   return trace;
367 }
368
369 XBT_INLINE void tmgr_trace_free(tmgr_trace_t trace)
370 {
371   if (!trace)
372     return;
373
374   switch(trace->type) {
375     case e_trace_list:
376       xbt_dynar_free(&(trace->s_list.event_list));
377       break;
378     case e_trace_probabilist:
379       THROW_UNIMPLEMENTED;
380       break;
381   }
382   free(trace);
383 }
384
385 tmgr_trace_event_t tmgr_history_add_trace(tmgr_history_t h,
386                                           tmgr_trace_t trace,
387                                           double start_time,
388                                           unsigned int offset, void *model)
389 {
390   tmgr_trace_event_t trace_event = NULL;
391
392   trace_event = xbt_new0(s_tmgr_trace_event_t, 1);
393   trace_event->trace = trace;
394   trace_event->idx = offset;
395   trace_event->model = model;
396
397   if(trace->type == e_trace_list) {
398     xbt_assert((trace_event->idx < xbt_dynar_length(trace->s_list.event_list)),
399               "You're referring to an event that does not exist!");
400   }
401
402   xbt_heap_push(h->heap, trace_event, start_time);
403
404   return trace_event;
405 }
406
407 XBT_INLINE double tmgr_history_next_date(tmgr_history_t h)
408 {
409   if (xbt_heap_size(h->heap))
410     return (xbt_heap_maxkey(h->heap));
411   else
412     return -1.0;
413 }
414
415 tmgr_trace_event_t tmgr_history_get_next_event_leq(tmgr_history_t h,
416                                                    double date,
417                                                    double *value,
418                                                    void **model)
419 {
420   double event_date = tmgr_history_next_date(h);
421   tmgr_trace_event_t trace_event = NULL;
422   tmgr_event_t event = NULL;
423   tmgr_trace_t trace = NULL;
424   double event_delta;
425
426   if (event_date > date)
427     return NULL;
428
429   if (!(trace_event = xbt_heap_pop(h->heap)))
430     return NULL;
431
432   trace = trace_event->trace;
433   *model = trace_event->model;
434
435   switch(trace->type) {
436     case e_trace_list:
437
438       event = xbt_dynar_get_ptr(trace->s_list.event_list, trace_event->idx);
439
440       *value = event->value;
441
442       if (trace_event->idx < xbt_dynar_length(trace->s_list.event_list) - 1) {
443         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
444         trace_event->idx++;
445       } else if (event->delta > 0) {        /* Last element, checking for periodicity */
446         xbt_heap_push(h->heap, trace_event, event_date + event->delta);
447         trace_event->idx = 1; /* not 0 as the first event is a placeholder to handle when events really start */
448       } else {                      /* We don't need this trace_event anymore */
449         trace_event->free_me = 1;
450       }
451       break;
452
453     case e_trace_probabilist:
454
455       //FIXME : not tested yet
456       if(trace->s_probabilist.is_state_trace) {
457         *value = (double) trace->s_probabilist.next_event;
458         if(trace->s_probabilist.next_event == 0) {
459           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
460           trace->s_probabilist.next_event = 1;
461         } else {
462           event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
463           trace->s_probabilist.next_event = 0;
464         }
465       } else {
466         event_delta = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[0]);
467         *value = tmgr_event_generator_next_value(trace->s_probabilist.event_generator[1]);
468       }
469       xbt_heap_push(h->heap, trace_event, event_date + event_delta);
470       XBT_DEBUG("Generating a new event at date %f, with value %f", event_date + event_delta, *value);
471
472       break;
473   }
474
475   return trace_event;
476 }
477
478 XBT_INLINE void tmgr_finalize(void)
479 {
480   xbt_dict_free(&trace_list);
481 }
482
483 int tmgr_trace_event_free(tmgr_trace_event_t trace_event)
484 {
485   if (trace_event->free_me) {
486     xbt_free(trace_event);
487     return 1;
488   }
489   return 0;
490 }