From 66eaf2eba602c331d08677dbb59ec3f9e40f0ccc Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Tue, 17 Nov 2009 14:35:48 -0500 Subject: [PATCH] Generate graphs of synchronization accuracy This depends on libglpk. Automatically enabled if present at configure time. Signed-off-by: Benjamin Poirier --- configure.ac | 33 +- lttv/lttv/Makefile.am | 2 +- lttv/lttv/sync/data_structures.c | 13 + lttv/lttv/sync/data_structures.h | 1 + lttv/lttv/sync/event_analysis_chull.c | 95 +- lttv/lttv/sync/event_analysis_chull.h | 30 +- lttv/lttv/sync/event_analysis_eval.c | 1010 ++++++++++++++--- lttv/lttv/sync/event_analysis_eval.h | 67 +- lttv/lttv/sync/event_matching_broadcast.c | 16 +- .../sync/event_processing_lttng_standard.c | 36 +- lttv/lttv/sync/graph_functions.c | 37 +- lttv/lttv/sync/graph_functions.h | 3 + lttv/lttv/sync/sync_chain_lttv.c | 2 +- lttv/modules/text/sync_chain_batch.c | 2 +- 14 files changed, 1121 insertions(+), 226 deletions(-) diff --git a/configure.ac b/configure.ac index c7dba3c2..c3a0b508 100644 --- a/configure.ac +++ b/configure.ac @@ -64,12 +64,33 @@ AC_SYS_LARGEFILE AC_PROG_CC # Checks for libraries. -AC_CHECK_LIB([popt], [poptGetNextOpt], POPT_LIBS="-lpopt",AC_MSG_ERROR([libpopt is required in order to compile LinuxTraceToolkit]) ) -AC_CHECK_LIB([m], [round], M_LIBS="-lm",AC_MSG_ERROR([Mathematical libraries are missing.]) ) - -AC_CHECK_LIB([util], [forkpty], UTIL_LIBS="-lutil", AC_MSG_ERROR([ -libutil is required in order to compile LinuxTraceToolkit])) - +AC_CHECK_LIB([popt], [poptGetNextOpt], POPT_LIBS="-lpopt", + AC_MSG_ERROR([libpopt is required in order to compile LinuxTraceToolkit])) +AC_CHECK_LIB([m], [round], M_LIBS="-lm", + AC_MSG_ERROR([Mathematical libraries are missing.])) +AC_CHECK_LIB([util], [forkpty], UTIL_LIBS="-lutil", + AC_MSG_ERROR([libutil is required in order to compile LinuxTraceToolkit])) + +AC_ARG_WITH([glpk], + [AS_HELP_STRING([--with-glpk@<:@=DIR@:>@], + [support trace synchronization accuracy calculation (needs glpk) + @<:@default=check@:>@])], + [], + [with_glpk=check]) + +GLPK_LIBS= + AS_IF([test "x$with_glpk" != xno], + [if test "x$with_glpk" != xyes -a -d "$with_glpk"; then + LDFLAGS="$LDFLAGS -L$with_glpk" + fi + AC_CHECK_LIB([glpk], [glp_create_prob], + [AC_SUBST([GLPK_LIBS], ["-lglpk"]) + AC_DEFINE([HAVE_LIBGLPK], [1], [Define if you have libglpk])], + [if test "x$with_glpk" != xcheck; then + AC_MSG_FAILURE( + [--with-glpk was given, but test for glpk failed]) + fi], + -lm)]) # pthread for gdb with dlopen(). AC_CHECK_LIB(pthread, pthread_join, [], AC_MSG_ERROR([LinuxThreads is required in order to make sure gdb works fine with lttv-gui])) diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index 10729886..d468e7ed 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -1,7 +1,7 @@ SUBDIRS= sync AM_CFLAGS= $(PACKAGE_CFLAGS) -LDADD = $(POPT_LIBS) $(M_LIBS) ${top_builddir}/ltt/liblttvtraceread.la +LDADD = $(POPT_LIBS) $(M_LIBS) $(GLPK_LIBS) ${top_builddir}/ltt/liblttvtraceread.la bin_PROGRAMS = lttv.real diff --git a/lttv/lttv/sync/data_structures.c b/lttv/lttv/sync/data_structures.c index c4d4d966..5983eaf6 100644 --- a/lttv/lttv/sync/data_structures.c +++ b/lttv/lttv/sync/data_structures.c @@ -640,3 +640,16 @@ void copyUDPEvent(const Event* const event, Event** const newEvent) memcpy((*newEvent)->event.udpEvent->datagramKey, event->event.udpEvent->datagramKey, sizeof(DatagramKey)); } + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Event*, event to add + * user_data GArray*, array to add to + */ +void gfAddEventToArray(gpointer data, gpointer user_data) +{ + g_array_append_val((GArray*) user_data, data); +} diff --git a/lttv/lttv/sync/data_structures.h b/lttv/lttv/sync/data_structures.h index 014b7da1..0eab5393 100644 --- a/lttv/lttv/sync/data_structures.h +++ b/lttv/lttv/sync/data_structures.h @@ -160,6 +160,7 @@ void destroyTCPEvent(Event* const event); void destroyUDPEvent(Event* const event); void gfDestroyEvent(gpointer data, gpointer user_data); double wallTimeSub(const WallTime const* tA, const WallTime const* tB); +void gfAddEventToArray(gpointer data, gpointer user_data); // Message-related functions void printTCPSegment(const Message* const segment); diff --git a/lttv/lttv/sync/event_analysis_chull.c b/lttv/lttv/sync/event_analysis_chull.c index 25736018..50bb7ab5 100644 --- a/lttv/lttv/sync/event_analysis_chull.c +++ b/lttv/lttv/sync/event_analysis_chull.c @@ -77,10 +77,8 @@ static int jointCmp(const Point* const p1, const Point* const p2, const Point* const p3) __attribute__((pure)); static double crossProductK(const Point const* p1, const Point const* p2, const Point const* p3, const Point const* p4) __attribute__((pure)); -static FactorsCHull** calculateAllFactors(SyncState* const syncState); static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const LineType lineType) __attribute__((pure)); -static void calculateFactorsMiddle(FactorsCHull* factors); static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, FactorsCHull* const result); static double slope(const Point* const p1, const Point* const p2) @@ -89,8 +87,6 @@ static double intercept(const Point* const p1, const Point* const p2) __attribute__((pure)); static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** allFactors); -static void freeAllFactors(const SyncState* const syncState, FactorsCHull** - const allFactors); static double verticalDistance(Point* p1, Point* p2, Point* const point) __attribute__((pure)); static void floydWarshall(SyncState* const syncState, FactorsCHull** const @@ -115,6 +111,14 @@ static AnalysisModule analysisModuleCHull= { } }; +const char* const approxNames[]= { + [EXACT]= "Exact", + [MIDDLE]= "Middle", + [FALLBACK]= "Fallback", + [INCOMPLETE]= "Incomplete", + [ABSENT]= "Absent", + [SCREWED]= "Screwed", +}; /* * Analysis module registering function @@ -350,7 +354,7 @@ static void destroyAnalysisCHull(SyncState* const syncState) { if (analysisData->stats->allFactors != NULL) { - freeAllFactors(syncState, analysisData->stats->allFactors); + freeAllFactors(syncState->traceNb, analysisData->stats->allFactors); } free(analysisData->stats); @@ -365,7 +369,7 @@ static void destroyAnalysisCHull(SyncState* const syncState) if (!syncState->stats && analysisData->graphsData->allFactors != NULL) { - freeAllFactors(syncState, analysisData->graphsData->allFactors); + freeAllFactors(syncState->traceNb, analysisData->graphsData->allFactors); } free(analysisData->graphsData); @@ -533,7 +537,7 @@ static GArray* finalizeAnalysisCHull(SyncState* const syncState) } else { - freeAllFactors(syncState, allFactors); + freeAllFactors(syncState->traceNb, allFactors); } return factors; @@ -741,44 +745,19 @@ static double crossProductK(const Point const* p1, const Point const* p2, * Free a container of FactorsCHull * * Args: - * syncState: container for synchronization data. - * allFactors: container of Factors + * traceNb: number of traces + * allFactors: container of FactorsCHull */ -static void freeAllFactors(const SyncState* const syncState, FactorsCHull** - const allFactors) +void freeAllFactors(const unsigned int traceNb, FactorsCHull** const + allFactors) { unsigned int i, j; - for (i= 0; i < syncState->traceNb; i++) + for (i= 0; i < traceNb; i++) { for (j= 0; j <= i; j++) { - FactorsCHull* factorsCHull; - - factorsCHull= &allFactors[i][j]; - if (factorsCHull->type == MIDDLE || factorsCHull->type == - INCOMPLETE || factorsCHull->type == ABSENT) - { - free(factorsCHull->min); - free(factorsCHull->max); - } - else if (factorsCHull->type == SCREWED) - { - if (factorsCHull->min != NULL) - { - free(factorsCHull->min); - } - if (factorsCHull->max != NULL) - { - free(factorsCHull->max); - } - } - - if (factorsCHull->type == EXACT || factorsCHull->type == MIDDLE || - factorsCHull->type == FALLBACK) - { - free(factorsCHull->approx); - } + destroyFactorsCHull(&allFactors[i][j]); } free(allFactors[i]); } @@ -786,6 +765,40 @@ static void freeAllFactors(const SyncState* const syncState, FactorsCHull** } +/* + * Free a FactorsCHull + * + * Args: + * factorsCHull: container of Factors + */ +void destroyFactorsCHull(FactorsCHull* factorsCHull) +{ + if (factorsCHull->type == MIDDLE || factorsCHull->type == + INCOMPLETE || factorsCHull->type == ABSENT) + { + free(factorsCHull->min); + free(factorsCHull->max); + } + else if (factorsCHull->type == SCREWED) + { + if (factorsCHull->min != NULL) + { + free(factorsCHull->min); + } + if (factorsCHull->max != NULL) + { + free(factorsCHull->max); + } + } + + if (factorsCHull->type == EXACT || factorsCHull->type == MIDDLE || + factorsCHull->type == FALLBACK) + { + free(factorsCHull->approx); + } +} + + /* * Analyze the convex hulls to determine the synchronization factors between * each pair of trace. @@ -797,7 +810,7 @@ static void freeAllFactors(const SyncState* const syncState, FactorsCHull** * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the * member allFactors of AnalysisStatsCHull. */ -static FactorsCHull** calculateAllFactors(SyncState* const syncState) +FactorsCHull** calculateAllFactors(SyncState* const syncState) { unsigned int traceNumA, traceNumB; FactorsCHull** allFactors; @@ -907,7 +920,7 @@ static FactorsCHull** calculateAllFactors(SyncState* const syncState) * Args: * factors: contains the min and max limits, used to store the result */ -static void calculateFactorsMiddle(FactorsCHull* factors) +void calculateFactorsMiddle(FactorsCHull* const factors) { double amin, amax, bmin, bmax, bhat; @@ -1566,7 +1579,7 @@ void writeAnalysisGraphsPlotsCHull(SyncState* const syncState, const unsigned fprintf(syncState->graphsStream, "\t%.2f + %.10f * x " "title \"Middle conversion\" with lines " - "linecolor rgb \"gray60\" linetype 1, \\\n", + "linecolor rgb \"black\" linetype 1, \\\n", factorsCHull->approx->offset, factorsCHull->approx->drift); } else if (factorsCHull->type == FALLBACK) diff --git a/lttv/lttv/sync/event_analysis_chull.h b/lttv/lttv/sync/event_analysis_chull.h index c9e82457..b82596b9 100644 --- a/lttv/lttv/sync/event_analysis_chull.h +++ b/lttv/lttv/sync/event_analysis_chull.h @@ -32,36 +32,44 @@ typedef struct typedef enum { + EXACT, /* Used for identity factors (a0= 0, a1= 1) that map a trace to itself. In * this case, min, max and accuracy are not initialized. */ - EXACT, + + MIDDLE, /* The approximation is the middle of the min and max limits, all fields * are initialized. */ - MIDDLE, + + FALLBACK, /* min and max are not available because the hulls do not respect * assumptions (hulls should not intersect and the upper half-hull should * be below the lower half-hull). The approximation is a "best effort". * All fields are initialized but min and max are NULL. */ - FALLBACK, + + INCOMPLETE, /* min or max is available but not both. The hulls respected assumptions * but all receives took place after all sends or vice versa. approx and * accuracy are not initialized. */ - INCOMPLETE, + + ABSENT, /* The pair of trace did not have communications in both directions (maybe * even no communication at all). approx and accuracy are not initialized. */ - ABSENT, + + SCREWED, /* min and max are not available because the algorithms are screwed. One * of min or max (but not both) is NULL. The other is initialized. Approx * is not initialized. */ - SCREWED, + + APPROX_NB, // This must be the last member } ApproxType; +extern const char* const approxNames[APPROX_NB]; typedef struct { @@ -116,7 +124,7 @@ typedef struct typedef struct { - /* Point hullArray[traceNb][traceNb][] + /* Point* hullArray[traceNb][traceNb][] * * A message comes from two traces. The lowest numbered trace is * considered to be the reference clock, CA. The other is CB. The @@ -161,4 +169,12 @@ typedef struct AnalysisGraphsDataCHull* graphsData; } AnalysisDataCHull; + +FactorsCHull** calculateAllFactors(struct _SyncState* const syncState); +void freeAllFactors(const unsigned int traceNb, FactorsCHull** const + allFactors); + +void calculateFactorsMiddle(FactorsCHull* const factors); +void destroyFactorsCHull(FactorsCHull* factorsCHull); + #endif diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c index 223a75b8..ab4cffbe 100644 --- a/lttv/lttv/sync/event_analysis_eval.c +++ b/lttv/lttv/sync/event_analysis_eval.c @@ -36,16 +36,25 @@ #include "lookup3.h" #include "sync_chain.h" +#include "event_analysis_chull.h" #include "event_analysis_eval.h" -struct WriteGraphInfo +struct WriteHistogramInfo { GHashTable* rttInfo; FILE* graphsStream; }; +#ifdef HAVE_LIBGLPK +struct LPAddRowInfo +{ + glp_prob* lp; + int boundType; + GArray* iArray, * jArray, * aArray; +}; +#endif // Functions common to all analysis modules static void initAnalysisEval(SyncState* const syncState); @@ -59,6 +68,10 @@ static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast); static GArray* finalizeAnalysisEval(SyncState* const syncState); static void printAnalysisStatsEval(SyncState* const syncState); +static void writeAnalysisTraceTimePlotsEval(SyncState* const syncState, const + unsigned int i, const unsigned int j); +static void writeAnalysisTraceTracePlotsEval(SyncState* const syncState, const + unsigned int i, const unsigned int j); // Functions specific to this module static void registerAnalysisEval() __attribute__((constructor (102))); @@ -71,7 +84,8 @@ static void positionStream(FILE* stream); static void gfSum(gpointer data, gpointer userData); static void gfSumSquares(gpointer data, gpointer userData); -static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data); +static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer + user_data); static void hitBin(struct Bins* const bins, const double value); static unsigned int binNum(const double value) __attribute__((pure)); @@ -79,16 +93,34 @@ static double binStart(const unsigned int binNum) __attribute__((pure)); static double binEnd(const unsigned int binNum) __attribute__((pure)); static uint32_t normalTotal(struct Bins* const bins) __attribute__((const)); -static AnalysisGraphEval* constructAnalysisGraphEval(const char* const +static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const graphsDir, const struct RttKey* const rttKey); -static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph); -static void gdnDestroyAnalysisGraphEval(gpointer data); -static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data); +static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const + histogram); +static void gdnDestroyAnalysisHistogramEval(gpointer data); +static void ghfWriteHistogram(gpointer key, gpointer value, gpointer + user_data); static void dumpBinToFile(const struct Bins* const bins, FILE* const file); static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, - double* minRtt, AnalysisGraphEval* const graph); + double* minRtt, AnalysisHistogramEval* const histogram); + +static void updateBounds(Bounds** const bounds, Event* const e1, Event* const e2); + +// The next group of functions is only needed when computing synchronization +// accuracy. +#ifdef HAVE_LIBGLPK +static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const upperHull); +static void gfLPAddRow(gpointer data, gpointer user_data); +static Factors* calculateFactors(glp_prob* const lp, const int direction); +static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors); +static FactorsCHull** createAllFactors(const unsigned int traceNb); +static inline void finalizeAnalysisEvalLP(SyncState* const syncState); +#else +static void finalizeAnalysisEvalLP(SyncState* const syncState); +#endif +// initialized in registerAnalysisEval() double binBase; static AnalysisModule analysisModuleEval= { @@ -100,6 +132,10 @@ static AnalysisModule analysisModuleEval= { .analyzeBroadcast= &analyzeBroadcastEval, .finalizeAnalysis= &finalizeAnalysisEval, .printAnalysisStats= &printAnalysisStatsEval, + .graphFunctions= { + .writeTraceTimePlots= &writeAnalysisTraceTimePlotsEval, + .writeTraceTracePlots= &writeAnalysisTraceTracePlotsEval, + } }; static ModuleOption optionEvalRttFile= { @@ -116,6 +152,8 @@ static ModuleOption optionEvalRttFile= { */ static void registerAnalysisEval() { + binBase= exp10(6. / (BIN_NB - 3)); + g_queue_push_tail(&analysisModules, &analysisModuleEval); g_queue_push_tail(&moduleOptions, &optionEvalRttFile); } @@ -133,7 +171,7 @@ static void registerAnalysisEval() static void initAnalysisEval(SyncState* const syncState) { AnalysisDataEval* analysisData; - unsigned int i; + unsigned int i, j; analysisData= malloc(sizeof(AnalysisDataEval)); syncState->analysisData= analysisData; @@ -176,13 +214,52 @@ static void initAnalysisEval(SyncState* const syncState) analysisData->stats->exchangeRtt= g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble); + +#ifdef HAVE_LIBGLPK + analysisData->stats->chFactorsArray= NULL; + analysisData->stats->lpFactorsArray= NULL; +#endif } if (syncState->graphsStream) { - binBase= exp10(6. / (BIN_NB - 3)); - analysisData->graphs= g_hash_table_new_full(&ghfRttKeyHash, - &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyAnalysisGraphEval); + AnalysisGraphsEval* graphs= malloc(sizeof(AnalysisGraphsEval)); + + analysisData->graphs= graphs; + + graphs->histograms= g_hash_table_new_full(&ghfRttKeyHash, + &gefRttKeyEqual, &gdnDestroyRttKey, + &gdnDestroyAnalysisHistogramEval); + + graphs->bounds= malloc(syncState->traceNb * sizeof(Bounds*)); + for (i= 0; i < syncState->traceNb; i++) + { + graphs->bounds[i]= malloc(i * sizeof(Bounds)); + for (j= 0; j < i; j++) + { + graphs->bounds[i][j].min= UINT64_MAX; + graphs->bounds[i][j].max= 0; + } + } + +#ifdef HAVE_LIBGLPK + graphs->lps= NULL; + graphs->lpFactorsArray= NULL; +#endif + } + + if (syncState->stats || syncState->graphsStream) + { + GList* result; + + analysisData->chullSS= malloc(sizeof(SyncState)); + memcpy(analysisData->chullSS, syncState, sizeof(SyncState)); + analysisData->chullSS->stats= false; + analysisData->chullSS->analysisData= NULL; + result= g_queue_find_custom(&analysisModules, "chull", + &gcfCompareAnalysis); + analysisData->chullSS->analysisModule= (AnalysisModule*) result->data; + analysisData->chullSS->analysisModule->initAnalysis(analysisData->chullSS); } } @@ -195,30 +272,30 @@ static void initAnalysisEval(SyncState* const syncState) * graphsDir: folder where to write files * rttKey: host pair, make sure saddr < daddr */ -static AnalysisGraphEval* constructAnalysisGraphEval(const char* const +static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const graphsDir, const struct RttKey* const rttKey) { int retval; unsigned int i; char* cwd; char name[60], saddr[16], daddr[16]; - AnalysisGraphEval* graph= calloc(1, sizeof(*graph)); + AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram)); const struct { size_t pointsOffset; const char* fileName; const char* host1, *host2; } loopValues[]= { - {offsetof(AnalysisGraphEval, ttSendPoints), "analysis_eval_tt-%s_to_%s.data", - saddr, daddr}, - {offsetof(AnalysisGraphEval, ttRecvPoints), "analysis_eval_tt-%s_to_%s.data", - daddr, saddr}, - {offsetof(AnalysisGraphEval, hrttPoints), "analysis_eval_hrtt-%s_and_%s.data", - saddr, daddr}, + {offsetof(AnalysisHistogramEval, ttSendPoints), + "analysis_eval_tt-%s_to_%s.data", saddr, daddr}, + {offsetof(AnalysisHistogramEval, ttRecvPoints), + "analysis_eval_tt-%s_to_%s.data", daddr, saddr}, + {offsetof(AnalysisHistogramEval, hrttPoints), + "analysis_eval_hrtt-%s_and_%s.data", saddr, daddr}, }; - graph->ttSendBins.max= BIN_NB - 1; - graph->ttRecvBins.max= BIN_NB - 1; - graph->hrttBins.max= BIN_NB - 1; + histogram->ttSendBins.min= BIN_NB - 1; + histogram->ttRecvBins.min= BIN_NB - 1; + histogram->hrttBins.min= BIN_NB - 1; convertIP(saddr, rttKey->saddr); convertIP(daddr, rttKey->daddr); @@ -233,7 +310,7 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const { name[sizeof(name) - 1]= '\0'; } - if ((*(FILE**)((void*) graph + loopValues[i].pointsOffset)= + if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)= fopen(name, "w")) == NULL) { g_error(strerror(errno)); @@ -247,7 +324,7 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const } free(cwd); - return graph; + return histogram; } @@ -258,26 +335,29 @@ static AnalysisGraphEval* constructAnalysisGraphEval(const char* const * graphsDir: folder where to write files * rttKey: host pair, make sure saddr < daddr */ -static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph) +static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const + histogram) { unsigned int i; int retval; const struct { size_t pointsOffset; } loopValues[]= { - {offsetof(AnalysisGraphEval, ttSendPoints)}, - {offsetof(AnalysisGraphEval, ttRecvPoints)}, - {offsetof(AnalysisGraphEval, hrttPoints)}, + {offsetof(AnalysisHistogramEval, ttSendPoints)}, + {offsetof(AnalysisHistogramEval, ttRecvPoints)}, + {offsetof(AnalysisHistogramEval, hrttPoints)}, }; for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) { - retval= fclose(*(FILE**)((void*) graph + loopValues[i].pointsOffset)); + retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset)); if (retval != 0) { g_error(strerror(errno)); } } + + free(histogram); } @@ -285,11 +365,11 @@ static void destroyAnalysisGraphEval(AnalysisGraphEval* const graph) * A GDestroyNotify function for g_hash_table_new_full() * * Args: - * data: AnalysisGraphEval* + * data: AnalysisHistogramEval* */ -static void gdnDestroyAnalysisGraphEval(gpointer data) +static void gdnDestroyAnalysisHistogramEval(gpointer data) { - destroyAnalysisGraphEval(data); + destroyAnalysisHistogramEval(data); } @@ -298,17 +378,17 @@ static void gdnDestroyAnalysisGraphEval(gpointer data) * * Args: * key: RttKey* where saddr < daddr - * value: AnalysisGraphEval* - * user_data struct WriteGraphInfo* + * value: AnalysisHistogramEval* + * user_data struct WriteHistogramInfo* */ -static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data) +static void ghfWriteHistogram(gpointer key, gpointer value, gpointer user_data) { double* rtt1, * rtt2; struct RttKey* rttKey= key; struct RttKey oppositeRttKey= {.saddr= rttKey->daddr, .daddr= rttKey->saddr}; - AnalysisGraphEval* graph= value; - struct WriteGraphInfo* info= user_data; + AnalysisHistogramEval* histogram= value; + struct WriteHistogramInfo* info= user_data; rtt1= g_hash_table_lookup(info->rttInfo, rttKey); rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey); @@ -322,10 +402,10 @@ static void ghfWriteGraph(gpointer key, gpointer value, gpointer user_data) rtt1= MIN(rtt1, rtt2); } - dumpBinToFile(&graph->ttSendBins, graph->ttSendPoints); - dumpBinToFile(&graph->ttRecvBins, graph->ttRecvPoints); - dumpBinToFile(&graph->hrttBins, graph->hrttPoints); - writeHistogram(info->graphsStream, rttKey, rtt1, graph); + dumpBinToFile(&histogram->ttSendBins, histogram->ttSendPoints); + dumpBinToFile(&histogram->ttRecvBins, histogram->ttRecvPoints); + dumpBinToFile(&histogram->hrttBins, histogram->hrttPoints); + writeHistogram(info->graphsStream, rttKey, rtt1, histogram); } @@ -360,11 +440,11 @@ static void dumpBinToFile(const struct Bins* const bins, FILE* const file) * graphsStream: write to this file * rttKey: must be sorted such that saddr < daddr * minRtt: if available, else NULL - * graph: struct that contains the bins for the pair of traces + * histogram: struct that contains the bins for the pair of traces * identified by rttKey */ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, - double* minRtt, AnalysisGraphEval* const graph) + double* minRtt, AnalysisHistogramEval* const histogram) { char saddr[16], daddr[16]; @@ -372,7 +452,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, convertIP(daddr, rttKey->daddr); fprintf(graphsStream, - "reset\n" + "\nreset\n" "set output \"histogram-%s-%s.eps\"\n" "set title \"\"\n" "set xlabel \"Message Latency (s)\"\n" @@ -386,12 +466,13 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, / 2); } - if (normalTotal(&graph->ttSendBins) || normalTotal(&graph->ttRecvBins) || - normalTotal(&graph->hrttBins)) + if (normalTotal(&histogram->ttSendBins) || + normalTotal(&histogram->ttRecvBins) || + normalTotal(&histogram->hrttBins)) { fprintf(graphsStream, "plot \\\n"); - if (normalTotal(&graph->hrttBins)) + if (normalTotal(&histogram->hrttBins)) { fprintf(graphsStream, "\t\"analysis_eval_hrtt-%s_and_%s.data\" " @@ -400,7 +481,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, saddr, daddr); } - if (normalTotal(&graph->ttSendBins)) + if (normalTotal(&histogram->ttSendBins)) { fprintf(graphsStream, "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" " @@ -409,7 +490,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, saddr, daddr); } - if (normalTotal(&graph->ttRecvBins)) + if (normalTotal(&histogram->ttRecvBins)) { fprintf(graphsStream, "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" " @@ -442,35 +523,79 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, */ static void destroyAnalysisEval(SyncState* const syncState) { - unsigned int i; + unsigned int i, j; AnalysisDataEval* analysisData; analysisData= (AnalysisDataEval*) syncState->analysisData; - if (analysisData == NULL || analysisData->rttInfo == NULL) + if (analysisData == NULL) { return; } g_hash_table_destroy(analysisData->rttInfo); - analysisData->rttInfo= NULL; if (syncState->stats) { + AnalysisStatsEval* stats= analysisData->stats; + + for (i= 0; i < syncState->traceNb; i++) + { + free(stats->messageStats[i]); + } + free(stats->messageStats); + + g_hash_table_destroy(stats->exchangeRtt); + +#ifdef HAVE_LIBGLPK + freeAllFactors(syncState->traceNb, stats->chFactorsArray); + freeAllFactors(syncState->traceNb, stats->lpFactorsArray); +#endif + + free(stats); + } + + if (syncState->graphsStream) + { + AnalysisGraphsEval* graphs= analysisData->graphs; + + if (graphs->histograms) + { + g_hash_table_destroy(graphs->histograms); + } + for (i= 0; i < syncState->traceNb; i++) { - free(analysisData->stats->messageStats[i]); + free(graphs->bounds[i]); + } + free(graphs->bounds); + +#ifdef HAVE_LIBGLPK + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < i; j++) + { + // There seems to be a memory leak in glpk, valgrind reports a + // loss even if the problem is deleted + glp_delete_prob(graphs->lps[i][j]); + } + free(graphs->lps[i]); } - free(analysisData->stats->messageStats); + free(graphs->lps); - g_hash_table_destroy(analysisData->stats->exchangeRtt); + if (!syncState->stats) + { + freeAllFactors(syncState->traceNb, graphs->lpFactorsArray); + } +#endif - free(analysisData->stats); + free(graphs); } - if (syncState->graphsStream && analysisData->graphs) + if (syncState->stats || syncState->graphsStream) { - g_hash_table_destroy(analysisData->graphs); + analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS); + free(analysisData->chullSS); } free(syncState->analysisData); @@ -487,28 +612,30 @@ static void destroyAnalysisEval(SyncState* const syncState) * syncState container for synchronization data * message structure containing the events */ -static void analyzeMessageEval(SyncState* const syncState, Message* const message) +static void analyzeMessageEval(SyncState* const syncState, Message* const + message) { AnalysisDataEval* analysisData= syncState->analysisData; MessageStats* messageStats= - &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];; + &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum]; double* rtt; double tt; struct RttKey rttKey; - if (!syncState->stats) - { - return; - } - g_assert(message->inE->type == TCP); - messageStats->total++; + if (syncState->stats) + { + messageStats->total++; + } tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime); if (tt <= 0) { - messageStats->inversionNb++; + if (syncState->stats) + { + messageStats->inversionNb++; + } } else if (syncState->graphsStream) { @@ -518,48 +645,63 @@ static void analyzeMessageEval(SyncState* const syncState, Message* const messag .daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr, message->inE->event.tcpEvent->segmentKey->connectionKey.daddr), }; - AnalysisGraphEval* graph= g_hash_table_lookup(analysisData->graphs, - &rttKey); + AnalysisHistogramEval* histogram= + g_hash_table_lookup(analysisData->graphs->histograms, &rttKey); - if (graph == NULL) + if (histogram == NULL) { struct RttKey* tableKey= malloc(sizeof(*tableKey)); - graph= constructAnalysisGraphEval(syncState->graphsDir, &rttKey); + histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey); memcpy(tableKey, &rttKey, sizeof(*tableKey)); - g_hash_table_insert(analysisData->graphs, tableKey, graph); + g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram); } if (message->inE->event.udpEvent->datagramKey->saddr < message->inE->event.udpEvent->datagramKey->daddr) { - hitBin(&graph->ttSendBins, tt); + hitBin(&histogram->ttSendBins, tt); } else { - hitBin(&graph->ttRecvBins, tt); + hitBin(&histogram->ttRecvBins, tt); } } - rttKey.saddr= - message->inE->event.tcpEvent->segmentKey->connectionKey.saddr; - rttKey.daddr= - message->inE->event.tcpEvent->segmentKey->connectionKey.daddr; - rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey); - g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr, - rttKey.daddr, rtt ? *rtt : NAN); - - if (rtt) + if (syncState->stats) { - g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.); - if (tt < *rtt / 2.) + rttKey.saddr= + message->inE->event.tcpEvent->segmentKey->connectionKey.saddr; + rttKey.daddr= + message->inE->event.tcpEvent->segmentKey->connectionKey.daddr; + rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey); + g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr, + rttKey.daddr, rtt ? *rtt : NAN); + + if (rtt) { - messageStats->tooFastNb++; + g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.); + if (tt < *rtt / 2.) + { + messageStats->tooFastNb++; + } + } + else + { + messageStats->noRTTInfoNb++; } } - else + + if (syncState->graphsStream) + { + updateBounds(analysisData->graphs->bounds, message->inE, + message->outE); + } + + if (syncState->stats || syncState->graphsStream) { - messageStats->noRTTInfoNb++; + analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS, + message); } } @@ -573,7 +715,8 @@ static void analyzeMessageEval(SyncState* const syncState, Message* const messag * syncState container for synchronization data * exchange structure containing the messages */ -static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exchange) +static void analyzeExchangeEval(SyncState* const syncState, Exchange* const + exchange) { AnalysisDataEval* analysisData= syncState->analysisData; Message* m1= g_queue_peek_tail(exchange->acks); @@ -581,11 +724,6 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch struct RttKey* rttKey; double* rtt, * exchangeRtt; - if (!syncState->stats) - { - return; - } - g_assert(m1->inE->type == TCP); // (T2 - T1) - (T3 - T4) @@ -603,34 +741,49 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch if (syncState->graphsStream) { - AnalysisGraphEval* graph= g_hash_table_lookup(analysisData->graphs, - rttKey); + AnalysisHistogramEval* histogram= + g_hash_table_lookup(analysisData->graphs->histograms, rttKey); - if (graph == NULL) + if (histogram == NULL) { struct RttKey* tableKey= malloc(sizeof(*tableKey)); - graph= constructAnalysisGraphEval(syncState->graphsDir, rttKey); + histogram= constructAnalysisHistogramEval(syncState->graphsDir, + rttKey); memcpy(tableKey, rttKey, sizeof(*tableKey)); - g_hash_table_insert(analysisData->graphs, tableKey, graph); + g_hash_table_insert(analysisData->graphs->histograms, tableKey, + histogram); } - hitBin(&graph->hrttBins, *rtt / 2); + hitBin(&histogram->hrttBins, *rtt / 2); } - exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt, - rttKey); - - if (exchangeRtt) + if (syncState->stats) { - if (*rtt < *exchangeRtt) + exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt, + rttKey); + + if (exchangeRtt) { - g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt); + if (*rtt < *exchangeRtt) + { + g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt); + } + else + { + free(rttKey); + free(rtt); + } + } + else + { + g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt); } } else { - g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt); + free(rttKey); + free(rtt); } } @@ -644,38 +797,61 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch * syncState container for synchronization data * broadcast structure containing the events */ -static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast) +static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const + broadcast) { - AnalysisDataEval* analysisData; - double sum= 0, squaresSum= 0; - double y; + AnalysisDataEval* analysisData= syncState->analysisData; - if (!syncState->stats) + if (syncState->stats) { - return; - } + double sum= 0, squaresSum= 0; + double y; - analysisData= (AnalysisDataEval*) syncState->analysisData; + g_queue_foreach(broadcast->events, &gfSum, &sum); + g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum); - g_queue_foreach(broadcast->events, &gfSum, &sum); - g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum); + analysisData->stats->broadcastNb++; + // Because of numerical errors, this can at times be < 0 + y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum / + g_queue_get_length(broadcast->events), 2.); + if (y > 0) + { + analysisData->stats->broadcastDiffSum+= sqrt(y); + } + } - analysisData->stats->broadcastNb++; - // Because of numerical errors, this can at times be < 0 - y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum / - g_queue_get_length(broadcast->events), 2.); - if (y > 0) + if (syncState->graphsStream) { - analysisData->stats->broadcastDiffSum+= sqrt(y); + unsigned int i, j; + GArray* events; + unsigned int eventNb= broadcast->events->length; + + events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb); + g_queue_foreach(broadcast->events, &gfAddEventToArray, events); + + for (i= 0; i < eventNb; i++) + { + for (j= 0; j < eventNb; j++) + { + Event* eventI= g_array_index(events, Event*, i), * eventJ= + g_array_index(events, Event*, j); + + if (eventI->traceNum < eventJ->traceNum) + { + updateBounds(analysisData->graphs->bounds, eventI, eventJ); + } + } + } + + g_array_free(events, TRUE); } } /* - * Finalize the factor calculations - * - * Since this module does not really calculate factors, identity factors are - * returned. + * Finalize the factor calculations. Since this module does not really + * calculate factors, identity factors are returned. Instead, histograms are + * written out and histogram structures are freed. * * Args: * syncState container for synchronization data. @@ -689,15 +865,17 @@ static GArray* finalizeAnalysisEval(SyncState* const syncState) unsigned int i; AnalysisDataEval* analysisData= syncState->analysisData; - if (syncState->graphsStream && analysisData->graphs) + if (syncState->graphsStream && analysisData->graphs->histograms) { - g_hash_table_foreach(analysisData->graphs, &ghfWriteGraph, &(struct - WriteGraphInfo) {.rttInfo= analysisData->rttInfo, - .graphsStream= syncState->graphsStream}); - g_hash_table_destroy(analysisData->graphs); - analysisData->graphs= NULL; + g_hash_table_foreach(analysisData->graphs->histograms, + &ghfWriteHistogram, &(struct WriteHistogramInfo) {.rttInfo= + analysisData->rttInfo, .graphsStream= syncState->graphsStream}); + g_hash_table_destroy(analysisData->graphs->histograms); + analysisData->graphs->histograms= NULL; } + finalizeAnalysisEvalLP(syncState); + factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), syncState->traceNb); g_array_set_size(factors, syncState->traceNb); @@ -797,6 +975,43 @@ static void printAnalysisStatsEval(SyncState* const syncState) "\t\tHost pair RTT from exchanges RTTs from file (ms)\n"); g_hash_table_foreach(analysisData->stats->exchangeRtt, &ghfPrintExchangeRtt, analysisData->rttInfo); + + printf("\tConvex hull factors comparisons:\n" + "\t\tTrace pair Factors type Differences (lp - chull)\n" + "\t\t a0 a1\n" + "\t\t Min Max Min Max\n"); + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < i; j++) + { + FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j]; + FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[i][j]; + + printf("\t\t%3d - %-3d ", i, j); + if (lpFactors->type == chFactors->type) + { + if (lpFactors->type == MIDDLE) + { + printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n", + approxNames[lpFactors->type], + lpFactors->min->offset - chFactors->min->offset, + lpFactors->max->offset - chFactors->max->offset, + lpFactors->min->drift - chFactors->min->drift, + lpFactors->max->drift - chFactors->max->drift); + } + else if (lpFactors->type == ABSENT) + { + printf("%s\n", approxNames[lpFactors->type]); + } + } + else + { + printf("Different! %s and %s\n", approxNames[lpFactors->type], + approxNames[chFactors->type]); + } + } + } } @@ -808,7 +1023,8 @@ static void printAnalysisStatsEval(SyncState* const syncState) * value: double*, RTT estimated from exchanges * user_data GHashTable* rttInfo */ -static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data) +static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer + user_data) { char addr1[16], addr2[16]; struct RttKey* rttKey1= key; @@ -1232,3 +1448,529 @@ static uint32_t normalTotal(struct Bins* const bins) { return bins->total - bins->bin[0] - bins->bin[BIN_NB - 1]; } + + +/* Update the bounds between two traces + * + * Args: + * bounds: the array containing all the trace-pair bounds + * e1, e2: the two related events + */ +static void updateBounds(Bounds** const bounds, Event* const e1, Event* const e2) +{ + unsigned int traceI, traceJ; + uint64_t messageTime; + Bounds* tpBounds; + + if (e1->traceNum < e2->traceNum) + { + traceI= e2->traceNum; + traceJ= e1->traceNum; + messageTime= e1->cpuTime; + } + else + { + traceI= e1->traceNum; + traceJ= e2->traceNum; + messageTime= e2->cpuTime; + } + tpBounds= &bounds[traceI][traceJ]; + + if (messageTime < tpBounds->min) + { + tpBounds->min= messageTime; + } + if (messageTime > tpBounds->max) + { + tpBounds->max= messageTime; + } +} + + +#ifdef HAVE_LIBGLPK +/* + * Create the linear programming problem containing the constraints defined by + * two half-hulls. The objective function and optimization directions are not + * written. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + * Returns: + * A new glp_prob*, this problem must be freed by the caller with + * glp_delete_prob() + */ +static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const upperHull) +{ + unsigned int it; + const int zero= 0; + const double zeroD= 0.; + glp_prob* lp= glp_create_prob(); + unsigned int hullPointNb= g_queue_get_length(lowerHull) + + g_queue_get_length(upperHull); + GArray* iArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + + 1); + GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb + + 1); + GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double), + hullPointNb + 1); + struct { + GQueue* hull; + struct LPAddRowInfo rowInfo; + } loopValues[2]= { + {lowerHull, {lp, GLP_UP, iArray, jArray, aArray}}, + {upperHull, {lp, GLP_LO, iArray, jArray, aArray}}, + }; + + // Create the LP problem + glp_term_out(GLP_OFF); + glp_add_rows(lp, hullPointNb); + glp_add_cols(lp, 2); + + glp_set_col_name(lp, 1, "a0"); + glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.); + glp_set_col_name(lp, 2, "a1"); + glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.); + + // Add row constraints + g_array_append_val(iArray, zero); + g_array_append_val(jArray, zero); + g_array_append_val(aArray, zeroD); + + for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++) + { + g_queue_foreach(loopValues[it].hull, &gfLPAddRow, + &loopValues[it].rowInfo); + } + + g_assert_cmpuint(iArray->len, ==, jArray->len); + g_assert_cmpuint(jArray->len, ==, aArray->len); + g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2); + + glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0), + &g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0)); + + glp_scale_prob(lp, GLP_SF_AUTO); + + g_array_free(iArray, TRUE); + g_array_free(jArray, TRUE); + g_array_free(aArray, TRUE); + + return lp; +} + + +/* + * A GFunc for g_queue_foreach(). Add constraints and bounds for one row. + * + * Args: + * data Point*, synchronization point for which to add an LP row + * (a constraint) + * user_data LPAddRowInfo* + */ +static void gfLPAddRow(gpointer data, gpointer user_data) +{ + Point* p= data; + struct LPAddRowInfo* rowInfo= user_data; + int indexes[2]; + double constraints[2]; + + indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1; + indexes[1]= indexes[0]; + + if (rowInfo->boundType == GLP_UP) + { + glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y); + } + else if (rowInfo->boundType == GLP_LO) + { + glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.); + } + else + { + g_assert_not_reached(); + } + + g_array_append_vals(rowInfo->iArray, indexes, 2); + indexes[0]= 1; + indexes[1]= 2; + g_array_append_vals(rowInfo->jArray, indexes, 2); + constraints[0]= 1.; + constraints[1]= p->x; + g_array_append_vals(rowInfo->aArray, constraints, 2); +} + + +/* + * Calculate min or max correction factors (as possible) using an LP problem. + * + * Args: + * lp: A linear programming problem with constraints and bounds + * initialized. + * direction: The type of factors desired. Use GLP_MAX for max + * approximation factors (a1, the drift or slope is the + * largest) and GLP_MIN in the other case. + * + * Returns: + * If the calculation was successful, a new Factors struct. Otherwise, NULL. + * The calculation will fail if the hull assumptions are not respected. + */ +static Factors* calculateFactors(glp_prob* const lp, const int direction) +{ + int retval, status; + Factors* factors; + + glp_set_obj_coef(lp, 1, 0.); + glp_set_obj_coef(lp, 2, 1.); + + glp_set_obj_dir(lp, direction); + retval= glp_simplex(lp, NULL); + status= glp_get_status(lp); + + if (retval == 0 && status == GLP_OPT) + { + factors= malloc(sizeof(Factors)); + factors->offset= glp_get_col_prim(lp, 1); + factors->drift= glp_get_col_prim(lp, 2); + } + else + { + factors= NULL; + } + + return factors; +} + + +/* + * Calculate min, max and approx correction factors (as possible) using an LP + * problem. + * + * Args: + * lp: A linear programming problem with constraints and bounds + * initialized. + * + * Returns: + * Please note that the approximation type may be MIDDLE, INCOMPLETE or + * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do + * not respect assumptions. + */ +static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors) +{ + factors->min= calculateFactors(lp, GLP_MIN); + factors->max= calculateFactors(lp, GLP_MAX); + + if (factors->min && factors->max) + { + factors->type= MIDDLE; + calculateFactorsMiddle(factors); + } + else if (factors->min || factors->max) + { + factors->type= INCOMPLETE; + factors->approx= NULL; + } + else + { + factors->type= ABSENT; + factors->approx= NULL; + } +} + + +/* + * Create and initialize an array like AnalysisStatsCHull.allFactors + * + * Args: + * traceNb: number of traces + * + * Returns: + * A new array, which can be freed with freeAllFactors() + */ +static FactorsCHull** createAllFactors(const unsigned int traceNb) +{ + FactorsCHull** factorsArray; + unsigned int i; + + factorsArray= malloc(traceNb * sizeof(FactorsCHull*)); + for (i= 0; i < traceNb; i++) + { + factorsArray[i]= calloc((i + 1), sizeof(FactorsCHull)); + + factorsArray[i][i].type= EXACT; + factorsArray[i][i].approx= malloc(sizeof(Factors)); + factorsArray[i][i].approx->drift= 1.; + factorsArray[i][i].approx->offset= 0.; + } + + return factorsArray; +} +#endif + + +/* + * Compute synchronization factors using a linear programming approach. + * Compute the factors using analysis_chull. Compare the two. + * + * There are two definitions of this function. The empty one is used when the + * solver library, glpk, is not available at build time. In that case, nothing + * is actually produced. + * + * Args: + * syncState: container for synchronization data + */ +#ifndef HAVE_LIBGLPK +static inline void finalizeAnalysisEvalLP(SyncState* const syncState) +{ +} +#else +static void finalizeAnalysisEvalLP(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataEval* analysisData= syncState->analysisData; + AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData; + FactorsCHull** lpFactorsArray= createAllFactors(syncState->traceNb); + FactorsCHull* lpFactors; + + if (!syncState->stats && !syncState->graphsStream) + { + return; + } + + if ((syncState->graphsStream && analysisData->graphs->lps != NULL) || + (syncState->stats && analysisData->stats->chFactorsArray != NULL)) + { + return; + } + + if (syncState->stats) + { + analysisData->stats->chFactorsArray= + calculateAllFactors(analysisData->chullSS); + analysisData->stats->lpFactorsArray= lpFactorsArray; + } + + if (syncState->graphsStream) + { + analysisData->graphs->lps= malloc(syncState->traceNb * + sizeof(glp_prob**)); + for (i= 0; i < syncState->traceNb; i++) + { + analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*)); + } + analysisData->graphs->lpFactorsArray= lpFactorsArray; + } + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < i; j++) + { + glp_prob* lp; + + // Create the LP problem + lp= lpCreateProblem(chAnalysisData->hullArray[i][j], + chAnalysisData->hullArray[j][i]); + + // Use the LP problem to find the correction factors for this pair of + // traces + calculateCompleteFactors(lp, &lpFactorsArray[i][j]); + + if (syncState->graphsStream) + { + analysisData->graphs->lps[i][j]= lp; + } + else + { + glp_delete_prob(lp); + destroyFactorsCHull(lpFactors); + } + } + } + + g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS), + TRUE); +} +#endif + + +/* + * Compute synchronization accuracy information using a linear programming + * approach. Write the neccessary data files and plot lines in the gnuplot + * script. + * + * There are two definitions of this function. The empty one is used when the + * solver library, glpk, is not available at build time. In that case, nothing + * is actually produced. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +#ifndef HAVE_LIBGLPK +static inline void writeAccuracyGraphs(SyncState* const syncState, const unsigned int + i, const unsigned int j) +{ +} +#else +static void writeAccuracyGraphs(SyncState* const syncState, const unsigned int + i, const unsigned int j) +{ + unsigned int it; + AnalysisDataEval* analysisData= syncState->analysisData; + AnalysisGraphsEval* graphs= analysisData->graphs; + GQueue*** hullArray= ((AnalysisDataCHull*) + analysisData->chullSS->analysisData)->hullArray; + FactorsCHull* lpFactors= &graphs->lpFactorsArray[j][i]; + glp_prob* lp= graphs->lps[j][i]; + + if (lpFactors->type == MIDDLE) + { + int retval; + char* cwd; + char fileName[40]; + FILE* fp; + double* xValues; + unsigned int xBegin, xEnd; + double interval; + const unsigned int graphPointNb= 1000; + + // Open the data file + snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j); + fileName[sizeof(fileName) - 1]= '\0'; + + cwd= changeToGraphDir(syncState->graphsDir); + + if ((fp= fopen(fileName, "w")) == NULL) + { + g_error(strerror(errno)); + } + fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max"); + + retval= chdir(cwd); + if (retval == -1) + { + g_error(strerror(errno)); + } + free(cwd); + + // Build the list of absisca values for the points in the accuracy graph + g_assert_cmpuint(graphPointNb, >=, 4); + xValues= malloc(graphPointNb * sizeof(double)); + xValues[0]= graphs->bounds[j][i].min; + xValues[graphPointNb - 1]= graphs->bounds[j][i].max; + xValues[1]= MIN(((Point*) g_queue_peek_head(hullArray[i][j]))->x, + ((Point*) g_queue_peek_head(hullArray[j][i]))->x); + xValues[graphPointNb - 2]= MAX(((Point*) + g_queue_peek_tail(hullArray[i][j]))->x, ((Point*) + g_queue_peek_tail(hullArray[j][i]))->x); + + if (xValues[0] == xValues[1]) + { + xBegin= 0; + } + else + { + xBegin= 1; + } + if (xValues[graphPointNb - 2] == xValues[graphPointNb - 1]) + { + xEnd= graphPointNb - 1; + } + else + { + xEnd= graphPointNb - 2; + } + interval= (xValues[xEnd] - xValues[xBegin]) / (graphPointNb - 1); + + for (it= xBegin; it <= xEnd; it++) + { + xValues[it]= xValues[xBegin] + interval * (it - xBegin); + } + + /* For each absisca value and each optimisation direction, solve the LP + * and write a line in the data file */ + for (it= 0; it < graphPointNb; it++) + { + unsigned int it2; + int directions[]= {GLP_MIN, GLP_MAX}; + + glp_set_obj_coef(lp, 1, 1.); + glp_set_obj_coef(lp, 2, xValues[it]); + + fprintf(fp, "%25.9f %25.9f", xValues[it], lpFactors->approx->offset + + lpFactors->approx->drift * xValues[it]); + for (it2= 0; it2 < sizeof(directions) / sizeof(*directions); it2++) + { + int status; + + glp_set_obj_dir(lp, directions[it2]); + retval= glp_simplex(lp, NULL); + status= glp_get_status(lp); + + g_assert(retval == 0 && status == GLP_OPT); + fprintf(fp, " %25.9f", glp_get_obj_val(lp)); + } + fprintf(fp, "\n"); + } + + free(xValues); + fclose(fp); + + fprintf(syncState->graphsStream, + "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) " + "title \"Synchronization accuracy\" " + "with filledcurves linewidth 2 linetype 1 " + "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, + j); + } +} +#endif + + +/* + * Write the analysis-specific graph lines in the gnuplot script. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTimePlotsEval(SyncState* const syncState, const + unsigned int i, const unsigned int j) +{ + AnalysisDataEval* analysisData= syncState->analysisData; + AnalysisGraphsEval* graphs= analysisData->graphs; + GQueue*** hullArray= ((AnalysisDataCHull*) + analysisData->chullSS->analysisData)->hullArray; + + printf("Between %u and %u:\n", i, j); + printf("\tbounds min %llu max %llu\n", graphs->bounds[j][i].min, + graphs->bounds[j][i].max); + printf("\tnumber of points in lower half-hull %u upper half-hull %u\n", + g_queue_get_length(hullArray[j][i]), + g_queue_get_length(hullArray[i][j])); + + writeAccuracyGraphs(syncState, i, j); +} + + +static void writeAnalysisTraceTracePlotsEval(SyncState* const syncState, const + unsigned int i, const unsigned int j) +{ + AnalysisDataEval* analysisData= syncState->analysisData; + +#ifdef HAVE_LIBGLPK + fprintf(syncState->graphsStream, + "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:3:4 " + "title \"Synchronization accuracy\" " + "with filledcurves linewidth 2 linetype 1 " + "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j); +#endif + + analysisData->chullSS->analysisModule->graphFunctions.writeTraceTracePlots(analysisData->chullSS, + i, j); +} diff --git a/lttv/lttv/sync/event_analysis_eval.h b/lttv/lttv/sync/event_analysis_eval.h index b02c7721..c0b02d0d 100644 --- a/lttv/lttv/sync/event_analysis_eval.h +++ b/lttv/lttv/sync/event_analysis_eval.h @@ -19,7 +19,14 @@ #ifndef EVENT_ANALYSIS_EVAL_H #define EVENT_ANALYSIS_EVAL_H +#ifdef HAVE_CONFIG_H +#include +#endif + #include +#ifdef HAVE_LIBGLPK +#include +#endif #include "data_structures.h" @@ -49,8 +56,17 @@ typedef struct * For this table, saddr and daddr are swapped as necessary such that * saddr < daddr */ GHashTable* exchangeRtt; -} AnalysisStatsEval; +#ifdef HAVE_LIBGLPK + /* FactorsCHull** chFactorsArray[traceNum][traceNum] + * FactorsCHull** lpFactorsArray[traceNum][traceNum] + * + * As usual, only the lower triangular part of theses matrixes is + * allocated */ + FactorsCHull** chFactorsArray; + FactorsCHull** lpFactorsArray; +#endif +} AnalysisStatsEval; #define BIN_NB 1001 struct Bins @@ -66,7 +82,6 @@ struct Bins uint32_t bin[BIN_NB]; }; - typedef struct { /* File pointers to files where "trip times" (message latency) histogram @@ -86,18 +101,56 @@ typedef struct FILE* hrttPoints; struct Bins hrttBins; -} AnalysisGraphEval; +} AnalysisHistogramEval; + +typedef struct +{ + // These are the cpu times of the first and last interactions (message or + // broadcast) between two traces. The times are from the trace with the + // lowest traceNum. + uint64_t min, max; +} Bounds; + +typedef struct +{ + /* AnalysisHistogramEval* graphs[RttKey]; + * For this table, saddr and daddr are swapped as necessary such that + * saddr < daddr */ + GHashTable* histograms; + + /* Bounds bounds[traceNum][traceNum] + * + * Only the lower triangular part of the matrix is allocated, that is + * bounds[i][j] where i > j */ + Bounds** bounds; + +#ifdef HAVE_LIBGLPK + /* glp_prob* lps[traceNum][traceNum] + * + * Only the lower triangular part of the matrix is allocated, that is + * lps[i][j] where i > j */ + glp_prob*** lps; + + /* Factors lpFactors[traceNum][traceNum] + * + * Only the lower triangular part of the matrix is allocated, that is + * lpFactorsArray[i][j] where i > j */ + FactorsCHull** lpFactorsArray; +#endif +} AnalysisGraphsEval; typedef struct { // double* rttInfo[RttKey] GHashTable* rttInfo; + /* The convex hull analysis is encapsulated and messages are passed to it + * so that it builds the convex hulls. These are reused in the linear + * program. */ + struct _SyncState* chullSS; + AnalysisStatsEval* stats; - /* AnalysisGraphsEval* graphs[RttKey]; - * For this table, saddr and daddr are swapped as necessary such that - * saddr < daddr */ - GHashTable* graphs; + AnalysisGraphsEval* graphs; } AnalysisDataEval; #endif diff --git a/lttv/lttv/sync/event_matching_broadcast.c b/lttv/lttv/sync/event_matching_broadcast.c index 3006f404..7579a4ac 100644 --- a/lttv/lttv/sync/event_matching_broadcast.c +++ b/lttv/lttv/sync/event_matching_broadcast.c @@ -54,7 +54,6 @@ static void partialDestroyMatchingBroadcast(SyncState* const syncState); static void openGraphDataFiles(SyncState* const syncState); static void writeAccuracyPoints(MatchingGraphsBroadcast* graphs, const Broadcast* const broadcast); -void gfAddToArray(gpointer data, gpointer user_data); static void closeGraphDataFiles(SyncState* const syncState); @@ -419,7 +418,7 @@ static void writeAccuracyPoints(MatchingGraphsBroadcast* graphs, const unsigned int eventNb= broadcast->events->length; events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb); - g_queue_foreach(broadcast->events, &gfAddToArray, events); + g_queue_foreach(broadcast->events, &gfAddEventToArray, events); for (i= 0; i < eventNb; i++) { @@ -437,19 +436,8 @@ static void writeAccuracyPoints(MatchingGraphsBroadcast* graphs, const } } } -} - -/* - * A GFunc for g_queue_foreach() - * - * Args: - * data Event*, event to add - * user_data GArray*, array to add to - */ -void gfAddToArray(gpointer data, gpointer user_data) -{ - g_array_append_val((GArray*) user_data, data); + g_array_free(events, TRUE); } diff --git a/lttv/lttv/sync/event_processing_lttng_standard.c b/lttv/lttv/sync/event_processing_lttng_standard.c index cc9ada28..733c4081 100644 --- a/lttv/lttv/sync/event_processing_lttng_standard.c +++ b/lttv/lttv/sync/event_processing_lttng_standard.c @@ -47,6 +47,8 @@ static void destroyProcessingLTTVStandard(SyncState* const syncState); static void finalizeProcessingLTTVStandard(SyncState* const syncState); static void printProcessingStatsLTTVStandard(SyncState* const syncState); +static void writeProcessingGraphVariablesLTTVStandard(SyncState* const + syncState, const unsigned int i); static void writeProcessingTraceTraceOptionsLTTVStandard(SyncState* const syncState, const unsigned int i, const unsigned int j); static void writeProcessingTraceTimeOptionsLTTVStandard(SyncState* const @@ -65,6 +67,7 @@ static ProcessingModule processingModuleLTTVStandard = { .finalizeProcessing= &finalizeProcessingLTTVStandard, .printProcessingStats= &printProcessingStatsLTTVStandard, .graphFunctions= { + .writeVariables= &writeProcessingGraphVariablesLTTVStandard, .writeTraceTraceOptions= &writeProcessingTraceTraceOptionsLTTVStandard, .writeTraceTimeOptions= &writeProcessingTraceTimeOptionsLTTVStandard, }, @@ -674,6 +677,24 @@ static gboolean processEventLTTVStandard(void* hookData, void* callData) } +/* + * Write the processing-specific variables in the gnuplot script. + * + * Args: + * syncState: container for synchronization data + * i: trace number + */ +static void writeProcessingGraphVariablesLTTVStandard(SyncState* const + syncState, const unsigned int i) +{ + ProcessingDataLTTVStandard* processingData= syncState->processingData; + ProcessingGraphsLTTVStandard* traceI= &processingData->graphs[i]; + + fprintf(syncState->graphsStream, "clock_freq_%u= %.3f\n", i, (double) + traceI->startFreq / traceI->freqScale); +} + + /* * Write the processing-specific options in the gnuplot script. * @@ -697,15 +718,14 @@ static void writeProcessingTraceTraceOptionsLTTVStandard(SyncState* const "set key inside right bottom\n" "set xlabel \"Clock %1$u\"\n" "set xtics nomirror\n" - "set ylabel \"Clock %3$u\"\n" + "set ylabel \"Clock %2$u\"\n" "set ytics nomirror\n" "set x2label \"Clock %1$d (s)\"\n" - "set x2range [GPVAL_X_MIN / %2$.1f : GPVAL_X_MAX / %2$.1f]\n" + "set x2range [GPVAL_X_MIN / clock_freq_%1$u : GPVAL_X_MAX / clock_freq_%1$u]\n" "set x2tics\n" - "set y2label \"Clock %3$d (s)\"\n" - "set y2range [GPVAL_Y_MIN / %4$.1f : GPVAL_Y_MAX / %4$.1f]\n" - "set y2tics\n", i, (double) traceI->startFreq / traceI->freqScale, j, - (double) traceJ->startFreq / traceJ->freqScale); + "set y2label \"Clock %2$d (s)\"\n" + "set y2range [GPVAL_Y_MIN / clock_freq_%2$u : GPVAL_Y_MAX / clock_freq_%2$u]\n" + "set y2tics\n", i, j); } @@ -735,6 +755,6 @@ static void writeProcessingTraceTimeOptionsLTTVStandard(SyncState* const "set ylabel \"time (s)\"\n" "set ytics nomirror\n" "set x2label \"Clock %1$d (s)\"\n" - "set x2range [GPVAL_X_MIN / %2$.1f : GPVAL_X_MAX / %2$.1f]\n" - "set x2tics\n", i, (double) traceI->startFreq / traceI->freqScale); + "set x2range [GPVAL_X_MIN / clock_freq_%1$u : GPVAL_X_MAX / clock_freq_%1$u]\n" + "set x2tics\n", i); } diff --git a/lttv/lttv/sync/graph_functions.c b/lttv/lttv/sync/graph_functions.c index 9b61e120..ca5be5ea 100644 --- a/lttv/lttv/sync/graph_functions.c +++ b/lttv/lttv/sync/graph_functions.c @@ -31,6 +31,12 @@ void writeGraphsScript(SyncState* const syncState) { unsigned int i, j, k, l; + long pos1, pos2; + const GraphFunctions* moduleGraphFunctions[]= { + &syncState->processingModule->graphFunctions, + &syncState->matchingModule->graphFunctions, + &syncState->analysisModule->graphFunctions, + }; const struct { size_t plotsOffset, optionsOffset; @@ -42,6 +48,30 @@ void writeGraphsScript(SyncState* const syncState) offsetof(GraphFunctions, writeTraceTimeOptions), "TraceTime"}, }; + fprintf(syncState->graphsStream, "\n"); + pos1= ftell(syncState->graphsStream); + for (i= 0; i < syncState->traceNb; i++) + { + for (k= 0; k < sizeof(moduleGraphFunctions) / + sizeof(*moduleGraphFunctions); k++) + { + GraphVariableFunction** writeVariables= (void*) + moduleGraphFunctions[k] + offsetof(GraphFunctions, + writeVariables); + + if (*writeVariables) + { + (*writeVariables)(syncState, i); + } + } + } + fflush(syncState->graphsStream); + pos2= ftell(syncState->graphsStream); + if (pos1 != pos2) + { + fprintf(syncState->graphsStream, "\n"); + } + for (l= 0; l < sizeof(funcTypes) / sizeof(*funcTypes); l++) { // Cover the upper triangular matrix, i is the reference node. @@ -49,12 +79,7 @@ void writeGraphsScript(SyncState* const syncState) { for (j= i + 1; j < syncState->traceNb; j++) { - long pos1, pos2, trunc; - const GraphFunctions* moduleGraphFunctions[]= { - &syncState->processingModule->graphFunctions, - &syncState->matchingModule->graphFunctions, - &syncState->analysisModule->graphFunctions, - }; + long trunc; fprintf(syncState->graphsStream, "reset\n" diff --git a/lttv/lttv/sync/graph_functions.h b/lttv/lttv/sync/graph_functions.h index 85e53a7a..d0b76948 100644 --- a/lttv/lttv/sync/graph_functions.h +++ b/lttv/lttv/sync/graph_functions.h @@ -21,11 +21,14 @@ struct _SyncState; +typedef void (GraphVariableFunction)(struct _SyncState* const syncState, const + unsigned int i); typedef void (GraphFunction)(struct _SyncState* const syncState, const unsigned int i, const unsigned int j); typedef struct { + GraphVariableFunction* writeVariables; /* This is for graphs where the data on both axis is in the range of * timestamps */ GraphFunction* writeTraceTracePlots; diff --git a/lttv/lttv/sync/sync_chain_lttv.c b/lttv/lttv/sync/sync_chain_lttv.c index ae41ff67..43963798 100644 --- a/lttv/lttv/sync/sync_chain_lttv.c +++ b/lttv/lttv/sync/sync_chain_lttv.c @@ -220,7 +220,7 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) fprintf(syncState->graphsStream, "#!/usr/bin/gnuplot\n\n" - "set terminal postscript eps color size 8in,6in\n\n"); + "set terminal postscript eps color size 8in,6in\n"); retval= chdir(cwd); if (retval == -1) diff --git a/lttv/modules/text/sync_chain_batch.c b/lttv/modules/text/sync_chain_batch.c index 2b2990ff..55ec9105 100644 --- a/lttv/modules/text/sync_chain_batch.c +++ b/lttv/modules/text/sync_chain_batch.c @@ -316,7 +316,7 @@ void setupSyncChain(LttvTracesetContext* const traceSetContext) fprintf(syncState->graphsStream, "#!/usr/bin/gnuplot\n\n" - "set terminal postscript eps color size 8in,6in\n\n"); + "set terminal postscript eps color size 8in,6in\n"); retval= chdir(cwd); if (retval == -1) -- 2.34.1