X-Git-Url: http://git.lttng.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fevent_analysis_eval.c;h=27d877d8a7c3b407d04a65ebe5a213b0304163f7;hb=0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2;hp=b63fa54f91b49ab12fc761d4e906a9250103a33d;hpb=4ee223e50270f894ec866b07c00ad49dff666173;p=lttv.git diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c index b63fa54f..27d877d8 100644 --- a/lttv/lttv/sync/event_analysis_eval.c +++ b/lttv/lttv/sync/event_analysis_eval.c @@ -1,19 +1,18 @@ /* This file is part of the Linux Trace Toolkit viewer - * Copyright (C) 2009 Benjamin Poirier + * Copyright (C) 2009, 2010 Benjamin Poirier * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License Version 2 as - * published by the Free Software Foundation; + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation, either version 2.1 of the License, or (at + * your option) any later version. * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public + * License for more details. * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place - Suite 330, Boston, - * MA 02111-1307, USA. + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see . */ #define _GNU_SOURCE @@ -36,10 +35,26 @@ #include "lookup3.h" #include "sync_chain.h" +#include "event_analysis_chull.h" #include "event_analysis_eval.h" +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); static void destroyAnalysisEval(SyncState* const syncState); @@ -50,15 +65,18 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exchange); static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast); -static GArray* finalizeAnalysisEval(SyncState* const syncState); +static AllFactors* finalizeAnalysisEval(SyncState* const syncState); static void printAnalysisStatsEval(SyncState* const syncState); -static void writeAnalysisGraphsPlotsEval(FILE* stream, SyncState* const - syncState, const unsigned int i, const unsigned int j); -static void writeAnalysisGraphsOptionsEval(FILE* stream, SyncState* - const syncState, const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j); +static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j); // Functions specific to this module -static void registerAnalysisEval() __attribute__((constructor (102))); static guint ghfRttKeyHash(gconstpointer key); static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b); static void gdnDestroyRttKey(gpointer data); @@ -68,19 +86,48 @@ 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 initGraphs(SyncState* const syncState); -static void writeGraphFiles(SyncState* const syncState); -static void dumpBinToFile(const uint32_t* const bin, const uint32_t total, - FILE* const file); -static void destroyGraphs(SyncState* const syncState); +static void hitBin(struct Bins* const bins, const double value); static unsigned int binNum(const double value) __attribute__((pure)); 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 AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const + graphsDir, const struct RttKey* const rttKey); +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, AnalysisHistogramEval* const histogram); + +static void updateBounds(Bounds** const bounds, Event* const e1, Event* const + e2); + +static void finalizeAnalysisEvalLP(SyncState* const syncState); +// 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, PairFactors* + factors); +static inline void finalizeAnalysisEvalLP(SyncState* const syncState); +static void gfAddAbsiscaToArray(gpointer data, gpointer user_data); +static gint gcfCompareDouble(gconstpointer a, gconstpointer b); +#else +static void finalizeAnalysisEvalLP(SyncState* const syncState); +#endif -const unsigned int binNb= 10000; +// initialized in registerAnalysisEval() double binBase; static AnalysisModule analysisModuleEval= { @@ -92,14 +139,17 @@ static AnalysisModule analysisModuleEval= { .analyzeBroadcast= &analyzeBroadcastEval, .finalizeAnalysis= &finalizeAnalysisEval, .printAnalysisStats= &printAnalysisStatsEval, - .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsEval, - .writeAnalysisGraphsOptions= &writeAnalysisGraphsOptionsEval, + .graphFunctions= { + .writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsEval, + .writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsEval, + .writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsEval, + .writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsEval, + } }; static ModuleOption optionEvalRttFile= { .longName= "eval-rtt-file", .hasArg= REQUIRED_ARG, - {.arg= NULL}, .optionHelp= "specify the file containing RTT information", .argHelp= "FILE", }; @@ -108,8 +158,10 @@ static ModuleOption optionEvalRttFile= { /* * Analysis module registering function */ -static void registerAnalysisEval() +void registerAnalysisEval() { + binBase= exp10(6. / (BIN_NB - 3)); + g_queue_push_tail(&analysisModules, &analysisModuleEval); g_queue_push_tail(&moduleOptions, &optionEvalRttFile); } @@ -127,7 +179,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; @@ -157,7 +209,8 @@ static void initAnalysisEval(SyncState* const syncState) if (syncState->stats) { analysisData->stats= calloc(1, sizeof(AnalysisStatsEval)); - analysisData->stats->broadcastDiffSum= 0.; + analysisData->stats->broadcastRangeMin= INFINITY; + analysisData->stats->broadcastRangeMax= -INFINITY; analysisData->stats->messageStats= malloc(syncState->traceNb * sizeof(MessageStats*)); @@ -170,99 +223,106 @@ 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) + { + 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->graphs) + if (syncState->stats || syncState->graphsStream) { - binBase= exp10(6. / (binNb - 2)); - analysisData->graphs= malloc(sizeof(AnalysisGraphsEval)); - initGraphs(syncState); + 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); } } /* - * Create and open files used to store histogram points to genereate - * graphs. Allocate and populate array to store file pointers. - * - * Also create data structures to store histogram points during analysis. + * Create and open files used to store histogram points to generate graphs. + * Create data structures to store histogram points during analysis. * * Args: - * syncState: container for synchronization data + * graphsDir: folder where to write files + * rttKey: host pair, make sure saddr < daddr */ -static void initGraphs(SyncState* const syncState) +static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const + graphsDir, const struct RttKey* const rttKey) { - unsigned int i, j; int retval; + unsigned int i; char* cwd; - char name[36]; - AnalysisDataEval* analysisData= syncState->analysisData; - - cwd= changeToGraphDir(syncState->graphs); - - analysisData->graphs->ttPoints= malloc(syncState->traceNb * - sizeof(FILE**)); - analysisData->graphs->ttBinsArray= malloc(syncState->traceNb * - sizeof(uint32_t**)); - analysisData->graphs->ttBinsTotal= malloc(syncState->traceNb * - sizeof(uint32_t*)); - for (i= 0; i < syncState->traceNb; i++) + char name[60], saddr[16], daddr[16]; + AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram)); + const struct { + size_t pointsOffset; + const char* fileName; + const char* host1, *host2; + } loopValues[]= { + {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}, + }; + + 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); + + cwd= changeToGraphsDir(graphsDir); + + for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) { - analysisData->graphs->ttPoints[i]= malloc(syncState->traceNb * - sizeof(FILE*)); - analysisData->graphs->ttBinsArray[i]= malloc(syncState->traceNb * - sizeof(uint32_t*)); - analysisData->graphs->ttBinsTotal[i]= calloc(syncState->traceNb, - sizeof(uint32_t)); - for (j= 0; j < syncState->traceNb; j++) + retval= snprintf(name, sizeof(name), loopValues[i].fileName, + loopValues[i].host1, loopValues[i].host2); + if (retval > sizeof(name) - 1) { - if (i != j) - { - retval= snprintf(name, sizeof(name), - "analysis_eval_tt-%03u_to_%03u.data", i, j); - if (retval > sizeof(name) - 1) - { - name[sizeof(name) - 1]= '\0'; - } - if ((analysisData->graphs->ttPoints[i][j]= fopen(name, "w")) == - NULL) - { - g_error(strerror(errno)); - } - - analysisData->graphs->ttBinsArray[i][j]= calloc(binNb, - sizeof(uint32_t)); - } + name[sizeof(name) - 1]= '\0'; } - } - - analysisData->graphs->hrttPoints= malloc(syncState->traceNb * - sizeof(FILE**)); - analysisData->graphs->hrttBinsArray= malloc(syncState->traceNb * - sizeof(uint32_t**)); - analysisData->graphs->hrttBinsTotal= malloc(syncState->traceNb * - sizeof(uint32_t*)); - for (i= 0; i < syncState->traceNb; i++) - { - analysisData->graphs->hrttPoints[i]= malloc(i * sizeof(FILE*)); - analysisData->graphs->hrttBinsArray[i]= malloc(i * sizeof(uint32_t*)); - analysisData->graphs->hrttBinsTotal[i]= calloc(i, sizeof(uint32_t)); - for (j= 0; j < i; j++) + if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)= + fopen(name, "w")) == NULL) { - retval= snprintf(name, sizeof(name), - "analysis_eval_hrtt-%03u_and_%03u.data", i, j); - if (retval > sizeof(name) - 1) - { - name[sizeof(name) - 1]= '\0'; - } - if ((analysisData->graphs->hrttPoints[i][j]= fopen(name, "w")) == - NULL) - { - g_error(strerror(errno)); - } - - analysisData->graphs->hrttBinsArray[i][j]= calloc(binNb, - sizeof(uint32_t)); + g_error(strerror(errno)); } } @@ -272,41 +332,89 @@ static void initGraphs(SyncState* const syncState) g_error(strerror(errno)); } free(cwd); + + return histogram; } /* - * Write histogram points to all files to generate graphs. + * Close files used to store histogram points to generate graphs. * * Args: - * syncState: container for synchronization data + * graphsDir: folder where to write files + * rttKey: host pair, make sure saddr < daddr */ -static void writeGraphFiles(SyncState* const syncState) +static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const + histogram) { - unsigned int i, j; - AnalysisDataEval* analysisData= syncState->analysisData; - - for (i= 0; i < syncState->traceNb; i++) + unsigned int i; + int retval; + const struct { + size_t pointsOffset; + } loopValues[]= { + {offsetof(AnalysisHistogramEval, ttSendPoints)}, + {offsetof(AnalysisHistogramEval, ttRecvPoints)}, + {offsetof(AnalysisHistogramEval, hrttPoints)}, + }; + + for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) { - for (j= 0; j < syncState->traceNb; j++) + retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset)); + if (retval != 0) { - if (i != j) - { - dumpBinToFile(analysisData->graphs->ttBinsArray[i][j], - analysisData->graphs->ttBinsTotal[i][j] - - analysisData->graphs->ttBinsArray[i][j][binNb - 1], - analysisData->graphs->ttPoints[i][j]); - } - - if (i > j) - { - dumpBinToFile(analysisData->graphs->hrttBinsArray[i][j], - analysisData->graphs->hrttBinsTotal[i][j] - - analysisData->graphs->hrttBinsArray[i][j][binNb - 1], - analysisData->graphs->hrttPoints[i][j]); - } + g_error(strerror(errno)); } } + + free(histogram); +} + + +/* + * A GDestroyNotify function for g_hash_table_new_full() + * + * Args: + * data: AnalysisHistogramEval* + */ +static void gdnDestroyAnalysisHistogramEval(gpointer data) +{ + destroyAnalysisHistogramEval(data); +} + + +/* + * A GHFunc for g_hash_table_foreach() + * + * Args: + * key: RttKey* where saddr < daddr + * value: AnalysisHistogramEval* + * user_data struct WriteHistogramInfo* + */ +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}; + AnalysisHistogramEval* histogram= value; + struct WriteHistogramInfo* info= user_data; + + rtt1= g_hash_table_lookup(info->rttInfo, rttKey); + rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey); + + if (rtt1 == NULL) + { + rtt1= rtt2; + } + else if (rtt2 != NULL) + { + rtt1= MIN(rtt1, rtt2); + } + + dumpBinToFile(&histogram->ttSendBins, histogram->ttSendPoints); + dumpBinToFile(&histogram->ttRecvBins, histogram->ttRecvPoints); + dumpBinToFile(&histogram->hrttBins, histogram->hrttPoints); + writeHistogram(info->graphsStream, rttKey, rtt1, histogram); } @@ -315,90 +423,102 @@ static void writeGraphFiles(SyncState* const syncState) * * Args: * bin: array of values that make up a histogram - * total: total number of messages in bins 0 to binNb - 2 - * file: FILE* + * file: FILE*, write to this file */ -static void dumpBinToFile(const uint32_t* const bin, const uint32_t total, - FILE* const file) +static void dumpBinToFile(const struct Bins* const bins, FILE* const file) { unsigned int i; - // Last bin is skipped because is continues till infinity - for (i= 0; i < binNb - 1; i++) + // The first and last bins are skipped, see struct Bins + for (i= 1; i < BIN_NB - 1; i++) { - if (bin[i] > 0) + if (bins->bin[i] > 0) { - fprintf(file, "%20.9f %20.9f %20.9f\n", (binStart(i) + binEnd(i)) / 2, (double) bin[i] - / ((binEnd(i) - binStart(i)) * total), binEnd(i) - binStart(i)); + fprintf(file, "%20.9f %20.9f %20.9f\n", (binStart(i) + binEnd(i)) + / 2., (double) bins->bin[i] / ((binEnd(i) - binStart(i)) * + bins->total), binEnd(i) - binStart(i)); } } } /* - * Close files used to store histogram points to generate graphs. Deallocate - * arrays of file pointers and arrays used to store histogram points during - * analysis. + * Write the analysis-specific plot in the gnuplot script. * * Args: - * syncState: container for synchronization data + * graphsStream: write to this file + * rttKey: must be sorted such that saddr < daddr + * minRtt: if available, else NULL + * histogram: struct that contains the bins for the pair of traces + * identified by rttKey */ -static void destroyGraphs(SyncState* const syncState) +static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, + double* minRtt, AnalysisHistogramEval* const histogram) { - unsigned int i, j; - AnalysisDataEval* analysisData= syncState->analysisData; - int retval; + char saddr[16], daddr[16]; + + convertIP(saddr, rttKey->saddr); + convertIP(daddr, rttKey->daddr); - if (analysisData->graphs == NULL || analysisData->graphs->ttPoints == - NULL) + fprintf(graphsStream, + "\nreset\n" + "set output \"histogram-%s-%s.eps\"\n" + "set title \"\"\n" + "set xlabel \"Message Latency (s)\"\n" + "set ylabel \"Proportion of messages per second\"\n", saddr, daddr); + + if (minRtt != NULL) { - return; + fprintf(graphsStream, + "set arrow from %.9f, 0 rto 0, graph 1 " + "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt + / 2); } - for (i= 0; i < syncState->traceNb; i++) + if (normalTotal(&histogram->ttSendBins) || + normalTotal(&histogram->ttRecvBins) || + normalTotal(&histogram->hrttBins)) { - for (j= 0; j < syncState->traceNb; j++) + fprintf(graphsStream, "plot \\\n"); + + if (normalTotal(&histogram->hrttBins)) { - if (i != j) - { - retval= fclose(analysisData->graphs->ttPoints[i][j]); - if (retval != 0) - { - g_error(strerror(errno)); - } + fprintf(graphsStream, + "\t\"analysis_eval_hrtt-%s_and_%s.data\" " + "title \"RTT/2\" with linespoints linetype 1 linewidth 2 " + "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n", + saddr, daddr); + } - free(analysisData->graphs->ttBinsArray[i][j]); - } + if (normalTotal(&histogram->ttSendBins)) + { + fprintf(graphsStream, + "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" " + "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 " + "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n", + saddr, daddr); } - free(analysisData->graphs->ttPoints[i]); - free(analysisData->graphs->ttBinsArray[i]); - free(analysisData->graphs->ttBinsTotal[i]); - } - free(analysisData->graphs->ttPoints); - free(analysisData->graphs->ttBinsArray); - free(analysisData->graphs->ttBinsTotal); - for (i= 0; i < syncState->traceNb; i++) - { - for (j= 0; j < i; j++) + if (normalTotal(&histogram->ttRecvBins)) { - retval= fclose(analysisData->graphs->hrttPoints[i][j]); - if (retval != 0) - { - g_error(strerror(errno)); - } + fprintf(graphsStream, + "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" " + "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 " + "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n", + daddr, saddr); + } - free(analysisData->graphs->hrttBinsArray[i][j]); + // Remove the ",\\\n" from the last graph plot line + if (ftruncate(fileno(graphsStream), ftell(graphsStream) - 3) == -1) + { + g_error(strerror(errno)); + } + if (fseek(graphsStream, 0, SEEK_END) == -1) + { + g_error(strerror(errno)); } - free(analysisData->graphs->hrttPoints[i]); - free(analysisData->graphs->hrttBinsArray[i]); - free(analysisData->graphs->hrttBinsTotal[i]); + fprintf(graphsStream, "\n"); } - free(analysisData->graphs->hrttPoints); - free(analysisData->graphs->hrttBinsArray); - free(analysisData->graphs->hrttBinsTotal); - - analysisData->graphs->ttPoints= NULL; } @@ -417,31 +537,76 @@ static void destroyAnalysisEval(SyncState* const syncState) 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(stats->chFactorsArray); + freeAllFactors(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(graphs->bounds[i]); + } + free(graphs->bounds); + +#ifdef HAVE_LIBGLPK for (i= 0; i < syncState->traceNb; i++) { - free(analysisData->stats->messageStats[i]); + unsigned int j; + + for (j= 0; j < i; j++) + { + // There seems to be a memory leak in glpk, valgrind reports a + // loss (reachable) 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(graphs->lpFactorsArray); + } +#endif - free(analysisData->stats); + free(graphs); } - if (syncState->graphs && analysisData->graphs) + if (syncState->stats || syncState->graphsStream) { - destroyGraphs(syncState); - free(analysisData->graphs); + analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS); + free(analysisData->chullSS); } free(syncState->analysisData); @@ -458,56 +623,97 @@ 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; + AnalysisDataEval* analysisData= syncState->analysisData; MessageStats* messageStats; double* rtt; double tt; struct RttKey rttKey; - if (!syncState->stats) + g_assert(message->inE->type == TCP); + + if (syncState->stats) { - return; + messageStats= + &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum]; + messageStats->total++; } - analysisData= (AnalysisDataEval*) syncState->analysisData; - messageStats= - &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum]; - - messageStats->total++; - tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime); if (tt <= 0) { - messageStats->inversionNb++; + if (syncState->stats) + { + messageStats->inversionNb++; + } } - else if (syncState->graphs) + else if (syncState->graphsStream) { - analysisData->graphs->ttBinsArray[message->outE->traceNum][message->inE->traceNum][binNum(tt)]++; - analysisData->graphs->ttBinsTotal[message->outE->traceNum][message->inE->traceNum]++; + struct RttKey rttKey= { + .saddr=MIN(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr, + message->inE->event.tcpEvent->segmentKey->connectionKey.daddr), + .daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr, + message->inE->event.tcpEvent->segmentKey->connectionKey.daddr), + }; + AnalysisHistogramEval* histogram= + g_hash_table_lookup(analysisData->graphs->histograms, &rttKey); + + if (histogram == NULL) + { + struct RttKey* tableKey= malloc(sizeof(*tableKey)); + + histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey); + memcpy(tableKey, &rttKey, sizeof(*tableKey)); + g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram); + } + + if (message->inE->event.udpEvent->datagramKey->saddr < + message->inE->event.udpEvent->datagramKey->daddr) + { + hitBin(&histogram->ttSendBins, tt); + } + else + { + hitBin(&histogram->ttRecvBins, tt); + } } - g_assert(message->inE->type == TCP); - 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) - { - g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.); - if (tt < *rtt / 2.) + if (syncState->stats) + { + 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) + { + g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.); + if (tt < *rtt / 2.) + { + messageStats->tooFastNb++; + } + } + else { - messageStats->tooFastNb++; + messageStats->noRTTInfoNb++; } } - else + + if (syncState->graphsStream) { - messageStats->noRTTInfoNb++; + updateBounds(analysisData->graphs->bounds, message->inE, + message->outE); + } + + if (syncState->stats || syncState->graphsStream) + { + analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS, + message); } } @@ -521,7 +727,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); @@ -529,26 +736,13 @@ 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) rtt= malloc(sizeof(double)); *rtt= wallTimeSub(&m1->inE->wallTime, &m1->outE->wallTime) - wallTimeSub(&m2->outE->wallTime, &m2->inE->wallTime); - if (syncState->graphs) - { - unsigned int row= MAX(m1->inE->traceNum, m1->outE->traceNum); - unsigned int col= MIN(m1->inE->traceNum, m1->outE->traceNum); - - analysisData->graphs->hrttBinsArray[row][col][binNum(*rtt / 2.)]++; - analysisData->graphs->hrttBinsTotal[row][col]++; - } - - g_assert(m1->inE->type == TCP); rttKey= malloc(sizeof(struct RttKey)); rttKey->saddr= MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr, @@ -556,19 +750,52 @@ static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exch rttKey->daddr= MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr, m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr); - exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt, - rttKey); - if (exchangeRtt) + if (syncState->graphsStream) + { + AnalysisHistogramEval* histogram= + g_hash_table_lookup(analysisData->graphs->histograms, rttKey); + + if (histogram == NULL) + { + struct RttKey* tableKey= malloc(sizeof(*tableKey)); + + histogram= constructAnalysisHistogramEval(syncState->graphsDir, + rttKey); + memcpy(tableKey, rttKey, sizeof(*tableKey)); + g_hash_table_insert(analysisData->graphs->histograms, tableKey, + histogram); + } + + hitBin(&histogram->hrttBins, *rtt / 2); + } + + 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); } } @@ -582,72 +809,118 @@ 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); + + 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->broadcastStdevSum+= sqrt(y); + } + + if (syncState->traceNb == 2 && g_queue_get_length(broadcast->events) + == 2) + { + Event* e0, * e1; + double dd; + + e0= g_queue_peek_head(broadcast->events); + e1= g_queue_peek_tail(broadcast->events); + if (e0->traceNum > e1->traceNum) + { + Event* tmp; + + tmp= e0; + e0= e1; + e1= tmp; + } - g_queue_foreach(broadcast->events, &gfSum, &sum); - g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum); + dd= wallTimeSub(&e1->wallTime, &e0->wallTime); + + analysisData->stats->broadcastPairNb++; + if (dd < analysisData->stats->broadcastRangeMin) + { + analysisData->stats->broadcastRangeMin= dd; + } + if (dd > analysisData->stats->broadcastRangeMax) + { + analysisData->stats->broadcastRangeMax= dd; + } + + analysisData->stats->broadcastSum+= dd; + analysisData->stats->broadcastSumSquares+= pow(dd, 2); + } + } - 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, absent factors are returned. Instead, histograms are + * written out and histogram structures are freed. * * Args: * syncState container for synchronization data. * * Returns: - * Factors[traceNb] identity factors for each trace + * AllFactors* synchronization factors for each trace pair */ -static GArray* finalizeAnalysisEval(SyncState* const syncState) +static AllFactors* finalizeAnalysisEval(SyncState* const syncState) { - GArray* factors; - unsigned int i; AnalysisDataEval* analysisData= syncState->analysisData; - if (syncState->graphs && analysisData->graphs) + if (syncState->graphsStream && analysisData->graphs->histograms) { - writeGraphFiles(syncState); - destroyGraphs(syncState); - 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; } - factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), - syncState->traceNb); - g_array_set_size(factors, syncState->traceNb); - for (i= 0; i < syncState->traceNb; i++) - { - Factors* e; + finalizeAnalysisEvalLP(syncState); - e= &g_array_index(factors, Factors, i); - e->drift= 1.; - e->offset= 0.; - } - - return factors; -} + return createAllFactors(syncState->traceNb); +} /* @@ -660,7 +933,9 @@ static GArray* finalizeAnalysisEval(SyncState* const syncState) static void printAnalysisStatsEval(SyncState* const syncState) { AnalysisDataEval* analysisData; - unsigned int i, j; + unsigned int i, j, k; + unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0; + int charNb; if (!syncState->stats) { @@ -670,38 +945,124 @@ static void printAnalysisStatsEval(SyncState* const syncState) analysisData= (AnalysisDataEval*) syncState->analysisData; printf("Synchronization evaluation analysis stats:\n"); - printf("\tsum of broadcast differential delays: %g\n", - analysisData->stats->broadcastDiffSum); - printf("\taverage broadcast differential delays: %g\n", - analysisData->stats->broadcastDiffSum / - analysisData->stats->broadcastNb); + if (analysisData->stats->broadcastNb) + { + printf("\tBroadcast differential delay:\n"); + printf("\t\tsum of standard deviations: %g\n", + analysisData->stats->broadcastStdevSum); + printf("\t\taverage standard deviation: %g\n", + analysisData->stats->broadcastStdevSum / + analysisData->stats->broadcastNb); + + if (syncState->traceNb == 2) + { + printf("\t\tdifferential delay range: [ %g .. %g ]\n", + analysisData->stats->broadcastRangeMin, + analysisData->stats->broadcastRangeMax); + printf("\t\tdifferential delay average: %g\n", + analysisData->stats->broadcastSum / + analysisData->stats->broadcastPairNb); + printf("\t\tdifferential delay standard deviation: %g\n", + sqrt(analysisData->stats->broadcastSumSquares / + analysisData->stats->broadcastPairNb - + pow(analysisData->stats->broadcastSum / + analysisData->stats->broadcastPairNb, 2))); + } + } printf("\tIndividual evaluation:\n" - "\t\tTrace pair Inversions Too fast (No RTT info) Total\n"); + "\t\tTrace pair Inversions Too fast No RTT info Total\n"); for (i= 0; i < syncState->traceNb; i++) { for (j= i + 1; j < syncState->traceNb; j++) { MessageStats* messageStats; - const char* format= "\t\t%3d - %-3d %-10u %-10u %-10u %u\n"; - - messageStats= &analysisData->stats->messageStats[i][j]; - - printf(format, i, j, messageStats->inversionNb, messageStats->tooFastNb, - messageStats->noRTTInfoNb, messageStats->total); - - messageStats= &analysisData->stats->messageStats[j][i]; - - printf(format, j, i, messageStats->inversionNb, messageStats->tooFastNb, - messageStats->noRTTInfoNb, messageStats->total); + struct { + unsigned int t1, t2; + } loopValues[]= { + {i, j}, + {j, i} + }; + + for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++) + { + messageStats= + &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2]; + + printf("\t\t%3d - %-3d ", loopValues[k].t1, loopValues[k].t2); + printf("%u (%.2f%%)%n", messageStats->inversionNb, (double) + messageStats->inversionNb / messageStats->total * 100, + &charNb); + printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " "); + printf("%u (%.2f%%)%n", messageStats->tooFastNb, (double) + messageStats->tooFastNb / messageStats->total * 100, + &charNb); + printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: + 1, " ", messageStats->noRTTInfoNb, messageStats->total); + + totInversion+= messageStats->inversionNb; + totTooFast+= messageStats->tooFastNb; + totNoInfo+= messageStats->noRTTInfoNb; + totTotal+= messageStats->total; + } } } + printf("\t\t total "); + printf("%u (%.2f%%)%n", totInversion, (double) totInversion / totTotal * + 100, &charNb); + printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " "); + printf("%u (%.2f%%)%n", totTooFast, (double) totTooFast / totTotal * 100, + &charNb); + printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ", + totNoInfo, totTotal); + printf("\tRound-trip times:\n" "\t\tHost pair RTT from exchanges RTTs from file (ms)\n"); g_hash_table_foreach(analysisData->stats->exchangeRtt, &ghfPrintExchangeRtt, analysisData->rttInfo); + +#ifdef HAVE_LIBGLPK + 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++) + { + PairFactors* chFactors= + &analysisData->stats->chFactorsArray->pairFactors[i][j]; + PairFactors* lpFactors= + &analysisData->stats->lpFactorsArray->pairFactors[i][j]; + + printf("\t\t%3d - %-3d ", i, j); + if (lpFactors->type == chFactors->type) + { + if (lpFactors->type == ACCURATE) + { + 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]); + } + } + } +#endif } @@ -713,7 +1074,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; @@ -1005,77 +1367,119 @@ static void gfSumSquares(gpointer data, gpointer userData) } +/* + * Update a struct Bins according to a new value + * + * Args: + * bins: the structure containing bins to build a histrogram + * value: the new value + */ +static void hitBin(struct Bins* const bins, const double value) +{ + unsigned int binN= binNum(value); + + if (binN < bins->min) + { + bins->min= binN; + } + else if (binN > bins->max) + { + bins->max= binN; + } + + bins->total++; + + bins->bin[binN]++; +} + + /* * Figure out the bin in a histogram to which a value belongs. * * This uses exponentially sized bins that go from 0 to infinity. * * Args: - * value: the value, must be >=0, or else expect the unexpected - * (floating point exception) + * value: in the range -INFINITY to INFINITY + * + * Returns: + * The number of the bin in a struct Bins.bin */ static unsigned int binNum(const double value) { - if (value == 0) + if (value <= 0) { return 0; } + else if (value < binEnd(1)) + { + return 1; + } + else if (value >= binStart(BIN_NB - 1)) + { + return BIN_NB - 1; + } else { - double result= floor(log(value) / log(binBase)) + (binNb - 1); - - if (result < 0.) - { - return 0.; - } - else - { - return result; - } + return floor(log(value) / log(binBase)) + BIN_NB + 1; } } /* - * Figure out the start of the interval of a bin in a histogram. The starting - * value is included in the interval. + * Figure out the start of the interval of a bin in a histogram. See struct + * Bins. * * This uses exponentially sized bins that go from 0 to infinity. * * Args: * binNum: bin number + * + * Return: + * The start of the interval, this value is included in the interval (except + * for -INFINITY, naturally) */ static double binStart(const unsigned int binNum) { - g_assert(binNum < binNb); + g_assert_cmpuint(binNum, <, BIN_NB); if (binNum == 0) { - return 0; + return -INFINITY; + } + else if (binNum == 1) + { + return 0.; } else { - return pow(binBase, (double) binNum - (binNb - 1)); + return pow(binBase, (double) binNum - BIN_NB + 1); } } /* - * Figure out the end of the interval of a bin in a histogram. The end value - * is not included in the interval. + * Figure out the end of the interval of a bin in a histogram. See struct + * Bins. * * This uses exponentially sized bins that go from 0 to infinity. * * Args: * binNum: bin number + * + * Return: + * The end of the interval, this value is not included in the interval */ static double binEnd(const unsigned int binNum) { - g_assert(binNum < binNb); + g_assert_cmpuint(binNum, <, BIN_NB); - if (binNum < binNb) + if (binNum == 0) { - return pow(binBase, (double) binNum - (binNb - 2)); + return 0.; + } + else if (binNum < BIN_NB - 1) + { + return pow(binBase, (double) binNum - BIN_NB + 2); } else { @@ -1084,57 +1488,553 @@ static double binEnd(const unsigned int binNum) } +/* + * Return the total number of elements in the "normal" bins (not underflow or + * overflow) + * + * Args: + * bins: the structure containing bins to build a histrogram + */ +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); + if (hullPointNb > 0) + { + 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 ACCURATE, 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, PairFactors* factors) +{ + factors->min= calculateFactors(lp, GLP_MIN); + factors->max= calculateFactors(lp, GLP_MAX); + + if (factors->min && factors->max) + { + factors->type= ACCURATE; + calculateFactorsMiddle(factors); + } + else if (factors->min || factors->max) + { + factors->type= INCOMPLETE; + factors->approx= NULL; + } + else + { + factors->type= ABSENT; + factors->approx= NULL; + } +} + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Point*, a convex hull point + * user_data GArray*, an array of convex hull point absisca values, as + * double + */ +static void gfAddAbsiscaToArray(gpointer data, gpointer user_data) +{ + Point* p= data; + GArray* a= user_data; + double v= p->x; + + g_array_append_val(a, v); +} + + +/* + * A GCompareFunc for g_array_sort() + * + * Args: + * a, b double*, absisca values + * + * Returns: + * "returns less than zero for first arg is less than second arg, zero for + * equal, greater zero if first arg is greater than second arg" + * - the great glib documentation + */ +static gint gcfCompareDouble(gconstpointer a, gconstpointer b) +{ + if (*(double*) a < *(double*) b) + { + return -1; + } + else if (*(double*) a > *(double*) b) + { + return 1; + } + else + { + return 0; + } +} +#endif + + +/* + * Compute synchronization factors using a linear programming approach. + * Compute the factors using analysis_chull. Compare the two. + * + * When the solver library, glpk, is not available at build time, only compute + * the factors using analysis_chull. This is to make sure that module runs its + * finalize function so that its graph functions can be called later. + * + * Args: + * syncState: container for synchronization data + */ +static void finalizeAnalysisEvalLP(SyncState* const syncState) +{ + AnalysisDataEval* analysisData= syncState->analysisData; +#ifdef HAVE_LIBGLPK + unsigned int i, j; + AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData; + AllFactors* lpFactorsArray; + + if (!syncState->stats && !syncState->graphsStream) + { + return; + } + + /* Because of matching_distributor, this analysis may be called twice. + * Only run it once */ + if ((syncState->graphsStream && analysisData->graphs->lps != NULL) || + (syncState->stats && analysisData->stats->chFactorsArray != NULL)) + { + return; + } + + lpFactorsArray= createAllFactors(syncState->traceNb); + + 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->pairFactors[i][j]); + + if (syncState->graphsStream) + { + analysisData->graphs->lps[i][j]= lp; + } + else + { + glp_delete_prob(lp); + } + } + } +#endif + + freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS)); +} + + +/* + * Compute synchronization accuracy information using a linear programming + * approach. Write the neccessary data files and plot lines in the gnuplot + * script. + * + * When the solver library, glpk, is not available at build time nothing is + * actually produced. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ +#ifdef HAVE_LIBGLPK + unsigned int it; + AnalysisDataEval* analysisData= syncState->analysisData; + AnalysisGraphsEval* graphs= analysisData->graphs; + GQueue*** hullArray= ((AnalysisDataCHull*) + analysisData->chullSS->analysisData)->hullArray; + PairFactors* lpFactors= &graphs->lpFactorsArray->pairFactors[j][i]; + glp_prob* lp= graphs->lps[j][i]; + + if (lpFactors->type == ACCURATE) + { + int retval; + char* cwd; + char fileName[40]; + FILE* fp; + GArray* xValues; + + // Open the data file + snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j); + fileName[sizeof(fileName) - 1]= '\0'; + + cwd= changeToGraphsDir(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 + xValues= g_array_sized_new(FALSE, FALSE, sizeof(double), + g_queue_get_length(hullArray[i][j]) + + g_queue_get_length(hullArray[j][i])); + + g_queue_foreach(hullArray[i][j], &gfAddAbsiscaToArray, xValues); + g_queue_foreach(hullArray[j][i], &gfAddAbsiscaToArray, xValues); + + g_array_sort(xValues, &gcfCompareDouble); + + /* For each absisca value and each optimisation direction, solve the LP + * and write a line in the data file */ + for (it= 0; it < xValues->len; it++) + { + unsigned int it2; + int directions[]= {GLP_MIN, GLP_MAX}; + glp_set_obj_coef(lp, 1, 1.); + glp_set_obj_coef(lp, 2, g_array_index(xValues, double, it)); + + fprintf(fp, "%25.9f %25.9f", g_array_index(xValues, double, it), + lpFactors->approx->offset + lpFactors->approx->drift * + g_array_index(xValues, double, 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"); + } + + g_array_free(xValues, TRUE); + 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. + * + * When the solver library, glpk, is not available at build time nothing is + * actually produced. + * + * Args: + * syncState: container for synchronization data + * i: first trace number + * j: second trace number, garanteed to be larger than i + */ +static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ +#ifdef HAVE_LIBGLPK + if (((AnalysisDataEval*) + syncState->analysisData)->graphs->lpFactorsArray->pairFactors[j][i].type + == ACCURATE) + { + fprintf(syncState->graphsStream, + "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($3 - $2) / clock_freq_%2$u) notitle " + "with lines linewidth 2 linetype 1 " + "linecolor rgb \"gray60\", \\\n" + "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" " + "using 1:(($4 - $2) / clock_freq_%2$u) notitle " + "with lines linewidth 2 linetype 1 " + "linecolor rgb \"gray60\", \\\n", i, j); + } +#endif +} + + /* * Write the analysis-specific graph lines in the gnuplot script. * * Args: - * stream: stream where to write the data * syncState: container for synchronization data * i: first trace number * j: second trace number, garanteed to be larger than i */ -static void writeAnalysisGraphsPlotsEval(FILE* stream, SyncState* const - syncState, const unsigned int i, const unsigned int j) +static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j) { - fprintf(stream, - "\t\"analysis_eval_hrtt-%2$03d_and_%1$03d.data\" " - "title \"RTT/2\" with boxes linetype 1 linewidth 3 " - "linecolor rgb \"black\" fill transparent solid 0.75, \\\n" - /*"\t\"analysis_eval_tt-%1$03d_to_%2$03d.data\" " - "title \"%1$u to %2$u\" with boxes linetype 1 linewidth 3 " - "linecolor rgb \"black\" fill transparent solid 0.5, \\\n" - "\t\"analysis_eval_tt-%2$03d_to_%1$03d.data\" " - "title \"%2$u to %1$u\" with boxes linetype 1 linewidth 3 " - "linecolor rgb \"black\" fill transparent solid 0.25, \\\n"*/ - , i, j); - /* - fprintf(stream, - "\t\"analysis_eval_hrtt-%2$03d_and_%1$03d.data\" " - "title \"RTT/2\" with linespoints linetype 1 linewidth 3 " - "linecolor rgb \"black\", \\\n" - "\t\"analysis_eval_tt-%1$03d_to_%2$03d.data\" " - "title \"%1$u to %2$u\" with linespoints linetype 1 linewidth 3 " - "linecolor rgb \"gray70\", \\\n" - "\t\"analysis_eval_tt-%2$03d_to_%1$03d.data\" " - "title \"%2$u to %1$u\" with linespoints linetype 1 linewidth 3 " - "linecolor rgb \"gray40\", \\\n", i, j); -*/ +#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 } /* - * Write the analysis-specific options in the gnuplot script. + * Write the analysis-specific graph lines in the gnuplot script. * * Args: - * stream: stream where to write the data * syncState: container for synchronization data * i: first trace number * j: second trace number, garanteed to be larger than i */ -static void writeAnalysisGraphsOptionsEval(FILE* stream, SyncState* - const syncState, const unsigned int i, const unsigned int j) +static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState, + const unsigned int i, const unsigned int j) { - fprintf(stream, - "set xlabel \"Message Latency (s)\"\n" - "set ylabel \"Proportion of messages per second\"\n"); + AnalysisDataEval* analysisData= syncState->analysisData; + + analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS, + i, j); }