From 509304ee1435b62cd49eb9071995fab468f68f58 Mon Sep 17 00:00:00 2001 From: alegrand Date: Mon, 15 Nov 2004 22:20:08 +0000 Subject: [PATCH] Add the trace library and fixed a few source of potential bugs in heap. git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@511 48e7efb5-ca39-0410-a469-dd3cf9ba447f --- include/Makefile.am | 1 + include/xbt/dict.h | 2 + include/xbt/dynar.h | 4 - include/xbt/heap.h | 7 +- include/xbt/misc.h | 4 + include/xbt/swag.h | 5 +- src/Makefile.am | 2 + src/include/surf/maxmin.h | 4 + src/include/surf/trace_mgr.h | 34 +++++++ src/surf/maxmin_private.h | 6 +- src/surf/trace_mgr.c | 182 +++++++++++++++++++++++++++++++++++ src/surf/trace_mgr_private.h | 32 ++++++ src/xbt/heap.c | 22 ++++- testsuite/Makefile.am | 9 +- testsuite/surf/trace_A.txt | 4 + testsuite/surf/trace_B.txt | 4 + testsuite/surf/trace_usage.c | 47 +++++++++ 17 files changed, 354 insertions(+), 15 deletions(-) create mode 100644 src/include/surf/trace_mgr.h create mode 100644 src/surf/trace_mgr.c create mode 100644 src/surf/trace_mgr_private.h create mode 100644 testsuite/surf/trace_A.txt create mode 100644 testsuite/surf/trace_B.txt create mode 100644 testsuite/surf/trace_usage.c diff --git a/include/Makefile.am b/include/Makefile.am index 0a14706b9f..ab8858fc34 100644 --- a/include/Makefile.am +++ b/include/Makefile.am @@ -11,6 +11,7 @@ nobase_include_HEADERS = \ xbt/config.h \ \ surf/maxmin.h \ + surf/trace_mgr.h \ \ gras/core.h \ gras/datadesc.h gras/transport.h \ diff --git a/include/xbt/dict.h b/include/xbt/dict.h index 8b866bb54e..1837700c75 100644 --- a/include/xbt/dict.h +++ b/include/xbt/dict.h @@ -12,6 +12,8 @@ #ifndef _XBT_DICT_H #define _XBT_DICT_H +#include "xbt/misc.h" /* BEGIN_DECL */ + #ifdef __cplusplus extern "C" #endif diff --git a/include/xbt/dynar.h b/include/xbt/dynar.h index c95e61920c..d793aacb1c 100644 --- a/include/xbt/dynar.h +++ b/include/xbt/dynar.h @@ -17,10 +17,6 @@ BEGIN_DECL typedef struct xbt_dynar_s *xbt_dynar_t; -/* pointer to a function freeing something */ -typedef void (void_f_ppvoid_t)(void**); -typedef void (void_f_pvoid_t) (void*); - xbt_dynar_t xbt_dynar_new(unsigned long elm_size, void_f_pvoid_t *free_func); void xbt_dynar_free(xbt_dynar_t *dynar); diff --git a/include/xbt/heap.h b/include/xbt/heap.h index 85b8c4fb52..249f24bee6 100644 --- a/include/xbt/heap.h +++ b/include/xbt/heap.h @@ -6,6 +6,8 @@ #ifndef _XBT_HEAP_H #define _XBT_HEAP_H +#include "xbt/dynar.h" + typedef struct xbt_heap *xbt_heap_t; /* The following two definitions concern the type of the keys used for @@ -13,11 +15,12 @@ typedef struct xbt_heap *xbt_heap_t; typedef long double xbt_heap_float_t; #define XBT_HEAP_FLOAT_T "%Lg" /* for printing purposes */ -/* pointer to a function freeing something (should be common to all .h : FIXME) */ -typedef void (void_f_pvoid_t) (void *); +/* /\* pointer to a function freeing something (should be common to all .h : FIXME) *\/ */ +/* typedef void (void_f_pvoid_t) (void *); */ xbt_heap_t xbt_heap_new(int num, void_f_pvoid_t free_func); void xbt_heap_free(xbt_heap_t H); +int xbt_heap_size(xbt_heap_t H); void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key); void *xbt_heap_pop(xbt_heap_t H); diff --git a/include/xbt/misc.h b/include/xbt/misc.h index be295b5b2f..f4f2d36c53 100644 --- a/include/xbt/misc.h +++ b/include/xbt/misc.h @@ -44,6 +44,10 @@ typedef struct { int port; } xbt_host_t; +/* pointer to a function freeing something */ +typedef void (void_f_ppvoid_t)(void**); +typedef void (void_f_pvoid_t) (void*); + END_DECL #endif /* XBT_MISC_H */ diff --git a/include/xbt/swag.h b/include/xbt/swag.h index a834d74f7c..c23538778a 100644 --- a/include/xbt/swag.h +++ b/include/xbt/swag.h @@ -8,7 +8,8 @@ what you are doing. */ /* This type should be added to a type that is to be used in such a swag */ -/* Whenever a new object with this struct is created, all fields have to be swag to NULL */ +/* Whenever a new object with this struct is created, all fields have + to be set to NULL */ typedef struct xbt_swag_hookup { void *next; @@ -40,6 +41,6 @@ static __inline__ void *xbt_swag_getFirst(xbt_swag_t swag) #define xbt_swag_offset(var,field) ((char *)&( (var).field ) - (char *)&(var)) #define xbt_swag_foreach(obj,swag) \ - for((obj)=xbt_swag_getFirst((swag)); \ + for((obj)=xbt_swag_getFirst((swag)); \ (obj)!=NULL; \ (obj)=xbt_swag_getNext((obj),(swag)->offset)) diff --git a/src/Makefile.am b/src/Makefile.am index f2bfa9f605..7e681b1ed1 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -22,6 +22,7 @@ EXTRA_DIST= \ xbt/fifo_private.h \ \ surf/maxmin_private.h \ + surf/trace_mgr_private.h \ \ gras/Transport/transport_interface.h \ gras/Virtu/virtu_interface.h \ @@ -92,6 +93,7 @@ COMMON_S=\ xbt/config.c \ \ surf/maxmin.c \ + surf/trace_mgr.c \ \ gras/Transport/transport.c gras/Transport/transport_private.h gras/Transport/transport_plugin_buf.c \ \ diff --git a/src/include/surf/maxmin.h b/src/include/surf/maxmin.h index eab59570a5..1d76633441 100644 --- a/src/include/surf/maxmin.h +++ b/src/include/surf/maxmin.h @@ -3,6 +3,9 @@ /* This program is free software; you can redistribute it and/or modify it under the terms of the license (GNU LGPL) which comes with this package. */ +#ifndef _SURF_MAXMIN_H +#define _SURF_MAXMIN_H + typedef long double xbt_maxmin_float_t; #define XBT_MAXMIN_FLOAT_T "%Lg" /* for printing purposes */ @@ -38,3 +41,4 @@ void lmm_update_constraint_bound(lmm_constraint_t cnst, xbt_maxmin_float_t bound); void lmm_solve(lmm_system_t sys); +#endif /* _SURF_MAXMIN_H */ diff --git a/src/include/surf/trace_mgr.h b/src/include/surf/trace_mgr.h new file mode 100644 index 0000000000..9773846590 --- /dev/null +++ b/src/include/surf/trace_mgr.h @@ -0,0 +1,34 @@ +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef _SURF_TMGR_H +#define _SURF_TMGR_H + +#include "xbt/heap.h" +#include "xbt/dynar.h" +#include "surf/maxmin.h" + +typedef struct tmgr_history *tmgr_history_t; +typedef struct tmgr_trace *tmgr_trace_t; + +/* Creation functions */ +tmgr_history_t tmgr_history_new(void); +void tmgr_history_free(tmgr_history_t history); + +tmgr_trace_t tmgr_trace_new(const char *filename); +void tmgr_trace_free(tmgr_trace_t trace); + +void tmgr_history_add_trace(tmgr_history_t history, tmgr_trace_t trace, + xbt_heap_float_t start_time, int offset, + void *resource); + +/* Access functions */ +xbt_heap_float_t tmgr_history_next_date(tmgr_history_t history); +int tmgr_history_get_next_event_leq(tmgr_history_t history, + xbt_heap_float_t date, + xbt_maxmin_float_t *value, + void **resource); + +#endif /* _SURF_TMGR_H */ diff --git a/src/surf/maxmin_private.h b/src/surf/maxmin_private.h index 0ace8c0032..04047843f2 100644 --- a/src/surf/maxmin_private.h +++ b/src/surf/maxmin_private.h @@ -3,6 +3,9 @@ /* This program is free software; you can redistribute it and/or modify it under the terms of the license (GNU LGPL) which comes with this package. */ +#ifndef _SURF_MAXMIN_PRIVATE_H +#define _SURF_MAXMIN_PRIVATE_H + #include "surf/maxmin.h" #include "xbt/swag.h" @@ -72,5 +75,4 @@ typedef struct lmm_system { static void lmm_var_free(lmm_system_t sys, lmm_variable_t var); static void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst); -/* #define UNDEFINED_VALUE -1.0 */ -#define UNUSED_CONSTRAINT -2.0 +#endif /* _SURF_MAXMIN_PRIVATE_H */ diff --git a/src/surf/trace_mgr.c b/src/surf/trace_mgr.c new file mode 100644 index 0000000000..c9ac6a96e0 --- /dev/null +++ b/src/surf/trace_mgr.c @@ -0,0 +1,182 @@ +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "xbt/sysdep.h" +#include "xbt/error.h" +#include "xbt/dict.h" +#include "trace_mgr_private.h" +#include + +static xbt_dict_t trace_list = NULL; +static void _tmgr_trace_free(void *trace) +{ + tmgr_trace_free(trace); +} + +tmgr_history_t tmgr_history_new(void) +{ + tmgr_history_t history; + + history = xbt_new0(s_tmgr_history_t,1); + + history->heap = xbt_heap_new(8,NULL); /* Why 8 ? Well, why not... */ + + return history; +} + +void tmgr_history_free(tmgr_history_t history) +{ + xbt_heap_free(history->heap); + xbt_free(history); +} + +tmgr_trace_t tmgr_trace_new(const char *filename) +{ + tmgr_trace_t trace = NULL; + FILE *f = NULL; + int linecount = 0; + char line[256]; + xbt_heap_float_t current_time=0.0, previous_time = 0.0; + xbt_maxmin_float_t value=-1.0; + xbt_heap_float_t periodicity = -1.0; /* No periodicity by default */ + s_tmgr_event_t event; + tmgr_event_t last_event = NULL; + + if(trace_list) { + xbt_dict_get(trace_list, filename, (void **) &trace); + if(trace) return trace; + } + + /* Parsing et création de la trace */ + + if ((f = fopen(filename, "r")) == NULL) { + fprintf(stderr, "Cannot open file '%s'\n", filename); + return NULL; + } + + trace = xbt_new0(s_tmgr_trace_t,1); + trace->event_list = xbt_dynar_new(sizeof(s_tmgr_event_t),NULL); + + while (fgets(line, 256, f)) { + linecount++; + if ((line[0] == '#') || (line[0] == '\n') || (line[0] == '%')) + continue; + + if (sscanf(line, "PERIODICITY " XBT_HEAP_FLOAT_T "\n", &(periodicity)) == 1){ + if(periodicity<=0) { + fprintf(stderr, "%s,%d: Syntax error. Periodicity has to be positive\n", + filename, linecount); + abort(); +/* xbt_dynar_free(&(trace->event_list)); */ +/* xbt_free(trace); */ +/* return NULL; */ + } + continue; + } + + if (sscanf(line, XBT_HEAP_FLOAT_T " " XBT_MAXMIN_FLOAT_T "\n", &event.delta, &event.value) != 2){ + fprintf(stderr, "%s,%d: Syntax error\n", filename, linecount); + abort(); +/* xbt_dynar_free(&(trace->event_list)); */ +/* xbt_free(trace); */ +/* return NULL; */ + } + + if(last_event) { + if((last_event->delta=event.delta-last_event->delta) <=0) { + fprintf(stderr, "%s,%d: Invalid trace value, events have to be sorted\n", + filename, linecount); + abort(); + } + } + xbt_dynar_push(trace->event_list, &event); + last_event = xbt_dynar_get_ptr(trace->event_list, + xbt_dynar_length(trace->event_list)-1); + printf(XBT_HEAP_FLOAT_T " " XBT_MAXMIN_FLOAT_T "\n", + event.delta, event.value); + } + + if(periodicity>0) { + if(last_event) + last_event->delta=periodicity; + } + + if(!trace_list) trace_list = xbt_dict_new(); + + xbt_dict_set(trace_list, filename, (void *) trace, _tmgr_trace_free); + + return trace; +} + + +void tmgr_trace_free(tmgr_trace_t trace) +{ + if(!trace) return; + xbt_dynar_free(&(trace->event_list)); + xbt_free(trace); +} + +void tmgr_history_add_trace(tmgr_history_t history, tmgr_trace_t trace, + xbt_heap_float_t start_time, int offset, + void *resource) +{ + tmgr_trace_event_t trace_event = NULL; + + + trace_event = xbt_new0(s_tmgr_trace_event_t,1); + trace_event->trace=trace; + trace_event->idx=offset; + trace_event->resource=resource; + + if(trace_event->idx>= xbt_dynar_length(trace->event_list)) + abort(); + + xbt_heap_push(history->heap, trace_event, start_time); +} + +xbt_heap_float_t tmgr_history_next_date(tmgr_history_t history) +{ + if(xbt_heap_size(history->heap)) return(xbt_heap_maxkey(history->heap)); + else return -1.0; +} + +int tmgr_history_get_next_event_leq(tmgr_history_t history, + xbt_heap_float_t date, + xbt_maxmin_float_t *value, + void **resource) +{ + xbt_heap_float_t event_date = xbt_heap_maxkey(history->heap); + tmgr_trace_event_t trace_event = NULL; + tmgr_event_t event = NULL; + tmgr_trace_t trace = NULL; + + if(event_date > date) + return 0; + + if(!(trace_event = xbt_heap_pop(history->heap))) + return 0; + + trace=trace_event->trace; + event=xbt_dynar_get_ptr(trace->event_list, + trace_event->idx); + + + *value=event->value; + *resource = trace_event->resource; + + if(trace_event->idxevent_list)-1) { + xbt_heap_push(history->heap, trace_event, event_date + + event->delta); + trace_event->idx++; + } else if(event->delta > 0) { /* Last element, checking for periodicity */ + xbt_heap_push(history->heap, trace_event, event_date + + event->delta); + trace_event->idx=0; + } else { /* We don't need this trace_event anymore */ + xbt_free(trace_event); + } + + return 1; +} diff --git a/src/surf/trace_mgr_private.h b/src/surf/trace_mgr_private.h new file mode 100644 index 0000000000..bcea7f354b --- /dev/null +++ b/src/surf/trace_mgr_private.h @@ -0,0 +1,32 @@ +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef _SURF_TMGR_PRIVATE_H +#define _SURF_TMGR_PRIVATE_H + +#include "xbt/swag.h" +#include "xbt/heap.h" +#include "surf/trace_mgr.h" + +typedef struct tmgr_event { + xbt_heap_float_t delta; + xbt_maxmin_float_t value; +} s_tmgr_event_t, *tmgr_event_t; + +typedef struct tmgr_trace { + xbt_dynar_t event_list; +} s_tmgr_trace_t; + +typedef struct tmgr_trace_event { + tmgr_trace_t trace; + int idx; + void *resource; +} s_tmgr_trace_event_t, *tmgr_trace_event_t; + +typedef struct tmgr_history { + xbt_heap_t heap; +} s_tmgr_history_t; + +#endif /* _SURF_TMGR_PRIVATE_H */ diff --git a/src/xbt/heap.c b/src/xbt/heap.c index dae1a1207c..394056d779 100644 --- a/src/xbt/heap.c +++ b/src/xbt/heap.c @@ -36,13 +36,24 @@ void xbt_heap_free(xbt_heap_t H) { int i; if (H->free) - for (i = 0; i < H->size; i++) + for (i = 0; i < H->count; i++) H->free(H->items[i].content); xbt_free(H->items); xbt_free(H); return; } +/** + * xbt_heap_size: + * @H: the heap we're working on + * + * returns the number of elements in the heap + */ +int xbt_heap_size(xbt_heap_t H) +{ + return (H->count); +} + /** * xbt_heap_push: * @H: the heap we're working on @@ -80,7 +91,12 @@ void xbt_heap_push(xbt_heap_t H, void *content, xbt_heap_float_t key) */ void *xbt_heap_pop(xbt_heap_t H) { - void *max = CONTENT(H, 0); + void *max ; + + if(H->count==0) return NULL; + + max = CONTENT(H, 0); + H->items[0] = H->items[(H->count) - 1]; (H->count)--; xbt_heap_maxHeapify(H); @@ -101,6 +117,7 @@ void *xbt_heap_pop(xbt_heap_t H) */ xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H) { + if(H->count==0) abort(); return KEY(H, 0); } @@ -113,6 +130,7 @@ xbt_heap_float_t xbt_heap_maxkey(xbt_heap_t H) */ void *xbt_heap_maxcontent(xbt_heap_t H) { + if(H->count==0) abort(); return CONTENT(H, 0); } diff --git a/testsuite/Makefile.am b/testsuite/Makefile.am index b53d51f78d..cf25ec85ee 100644 --- a/testsuite/Makefile.am +++ b/testsuite/Makefile.am @@ -7,7 +7,9 @@ MAINTAINERCLEANFILES=Makefile.in EXTRA_DIST=run_tests.in \ gras/datadesc.little32 gras/datadesc.little64 gras/datadesc.big32 gras/datadesc.big64 \ gras/datadesc.aix \ - gras/mk_datadesc_structs.pl + gras/mk_datadesc_structs.pl \ + surf/trace_A.txt surf/trace_B.txt + # Test stuff @@ -27,7 +29,7 @@ RL_tests = \ gras/datadesc_usage SG_tests = \ - surf/maxmin_usage + surf/maxmin_usage surf/trace_usage check_PROGRAMS = $(xbt_tests) $(RL_tests) $(SG_tests) check_SCRIPTS = run_tests gras/trp_tcp_usage @@ -59,7 +61,8 @@ xbt_config_usage_LDADD= $(LDADD_UTILS) xbt_heap_bench_LDADD= $(LDADD_UTILS) -surf_maxmin_usage_LDADD= $(LDADD_UTILS) +surf_maxmin_usage_LDADD= $(LDADD_UTILS) +surf_trace_usage_LDADD= $(LDADD_UTILS) gras_trp_tcp_client_LDADD= $(LDADD_RL) gras_trp_tcp_server_LDADD= $(LDADD_RL) diff --git a/testsuite/surf/trace_A.txt b/testsuite/surf/trace_A.txt new file mode 100644 index 0000000000..3fcb2ac1af --- /dev/null +++ b/testsuite/surf/trace_A.txt @@ -0,0 +1,4 @@ +PERIODICITY 100.01 +1.1 100.0 +15.2 20.0 +20.4 80.24 diff --git a/testsuite/surf/trace_B.txt b/testsuite/surf/trace_B.txt new file mode 100644 index 0000000000..3061526e01 --- /dev/null +++ b/testsuite/surf/trace_B.txt @@ -0,0 +1,4 @@ +PERIODICITY 10.00 +1.0 10.0 +15.0 2.0 +20.0 8.024 diff --git a/testsuite/surf/trace_usage.c b/testsuite/surf/trace_usage.c new file mode 100644 index 0000000000..c203163c6c --- /dev/null +++ b/testsuite/surf/trace_usage.c @@ -0,0 +1,47 @@ +/* A few tests for the trace library */ + +/* Authors: Arnaud Legrand */ + +/* This program is free software; you can redistribute it and/or modify it + under the terms of the license (GNU LGPL) which comes with this package. */ + +#include +#include +#include +#include "surf/trace_mgr.h" + +void test(void); +void test(void) +{ + tmgr_history_t history = tmgr_history_new(); + tmgr_trace_t trace_A= tmgr_trace_new("trace_A.txt"); + tmgr_trace_t trace_B= tmgr_trace_new("trace_B.txt"); + xbt_heap_float_t next_event_date=-1.0; + xbt_maxmin_float_t value = -1.0; + char *resource = NULL; + char *host_A = strdup("Host A"); + char *host_B = strdup("Host B"); + + tmgr_history_add_trace(history, trace_A, 1.0, 2, host_A); + tmgr_history_add_trace(history, trace_B, 0.0, 0, host_B); + + while((next_event_date=tmgr_history_next_date(history))!=-1.0) { + printf(XBT_HEAP_FLOAT_T " : \n",next_event_date); + while(tmgr_history_get_next_event_leq(history, next_event_date, + &value, (void**) &resource)){ + printf("\t %s : " XBT_MAXMIN_FLOAT_T "\n",resource,value); + } + if(next_event_date>1000) break; + } + + tmgr_trace_free(trace_A); + tmgr_trace_free(trace_B); + tmgr_history_free(history); +} + + +int main(int argc, char **argv) +{ + test(); + return 0; +} -- 2.20.1