X-Git-Url: http://git.liburcu.org/?a=blobdiff_plain;f=lttv%2Flttv%2Fsync%2Fevent_analysis_eval.c;h=27d877d8a7c3b407d04a65ebe5a213b0304163f7;hb=0a87ec9a018cc9731ce3b04309eaa4dcc77df6d2;hp=29b1b4493009eabdb2552174a81d289689e1462b;hpb=1d597550379cb00832f73bd5402918fd6ed2e9df;p=lttv.git diff --git a/lttv/lttv/sync/event_analysis_eval.c b/lttv/lttv/sync/event_analysis_eval.c index 29b1b449..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 @@ -66,7 +65,7 @@ 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 writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, const unsigned int i, const unsigned int j); @@ -78,7 +77,6 @@ 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); @@ -111,6 +109,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, 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 @@ -118,10 +117,11 @@ 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* +static void calculateCompleteFactors(glp_prob* const lp, PairFactors* factors); -static FactorsCHull** createAllFactors(const unsigned int traceNb); 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 @@ -150,7 +150,6 @@ static AnalysisModule analysisModuleEval= { static ModuleOption optionEvalRttFile= { .longName= "eval-rtt-file", .hasArg= REQUIRED_ARG, - {.arg= NULL}, .optionHelp= "specify the file containing RTT information", .argHelp= "FILE", }; @@ -159,7 +158,7 @@ static ModuleOption optionEvalRttFile= { /* * Analysis module registering function */ -static void registerAnalysisEval() +void registerAnalysisEval() { binBase= exp10(6. / (BIN_NB - 3)); @@ -210,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*)); @@ -532,7 +532,7 @@ static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey, */ static void destroyAnalysisEval(SyncState* const syncState) { - unsigned int i, j; + unsigned int i; AnalysisDataEval* analysisData; analysisData= (AnalysisDataEval*) syncState->analysisData; @@ -557,8 +557,8 @@ static void destroyAnalysisEval(SyncState* const syncState) g_hash_table_destroy(stats->exchangeRtt); #ifdef HAVE_LIBGLPK - freeAllFactors(syncState->traceNb, stats->chFactorsArray); - freeAllFactors(syncState->traceNb, stats->lpFactorsArray); + freeAllFactors(stats->chFactorsArray); + freeAllFactors(stats->lpFactorsArray); #endif free(stats); @@ -582,10 +582,12 @@ static void destroyAnalysisEval(SyncState* const syncState) #ifdef HAVE_LIBGLPK for (i= 0; i < syncState->traceNb; i++) { + unsigned int j; + 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 + // loss (reachable) even if the problem is deleted glp_delete_prob(graphs->lps[i][j]); } free(graphs->lps[i]); @@ -594,7 +596,7 @@ static void destroyAnalysisEval(SyncState* const syncState) if (!syncState->stats) { - freeAllFactors(syncState->traceNb, graphs->lpFactorsArray); + freeAllFactors(graphs->lpFactorsArray); } #endif @@ -826,7 +828,40 @@ static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const g_queue_get_length(broadcast->events), 2.); if (y > 0) { - analysisData->stats->broadcastDiffSum+= sqrt(y); + 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; + } + + 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); } } @@ -860,19 +895,17 @@ static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const /* * Finalize the factor calculations. Since this module does not really - * calculate factors, identity factors are returned. Instead, histograms are + * 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->graphsStream && analysisData->graphs->histograms) @@ -886,19 +919,7 @@ static GArray* finalizeAnalysisEval(SyncState* const syncState) finalizeAnalysisEvalLP(syncState); - 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; - - e= &g_array_index(factors, Factors, i); - e->drift= 1.; - e->offset= 0.; - } - - return factors; + return createAllFactors(syncState->traceNb); } @@ -926,11 +947,27 @@ static void printAnalysisStatsEval(SyncState* const syncState) printf("Synchronization evaluation analysis stats:\n"); if (analysisData->stats->broadcastNb) { - printf("\tsum of broadcast differential delays: %g\n", - analysisData->stats->broadcastDiffSum); - printf("\taverage broadcast differential delay: %g\n", - analysisData->stats->broadcastDiffSum / + 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" @@ -954,13 +991,13 @@ static void printAnalysisStatsEval(SyncState* const syncState) &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2]; printf("\t\t%3d - %-3d ", loopValues[k].t1, loopValues[k].t2); - printf("%u (%u%%)%n", messageStats->inversionNb, (unsigned - int) ceil((double) messageStats->inversionNb / - messageStats->total * 100), &charNb); + printf("%u (%.2f%%)%n", messageStats->inversionNb, (double) + messageStats->inversionNb / messageStats->total * 100, + &charNb); printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " "); - printf("%u (%u%%)%n", messageStats->tooFastNb, (unsigned int) - ceil((double) messageStats->tooFastNb / - messageStats->total * 100), &charNb); + 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); @@ -973,11 +1010,11 @@ static void printAnalysisStatsEval(SyncState* const syncState) } printf("\t\t total "); - printf("%u (%u%%)%n", totInversion, (unsigned int) ceil((double) - totInversion / totTotal * 100), &charNb); + printf("%u (%.2f%%)%n", totInversion, (double) totInversion / totTotal * + 100, &charNb); printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " "); - printf("%u (%u%%)%n", totTooFast, (unsigned int) ceil((double) totTooFast - / totTotal * 100), &charNb); + printf("%u (%.2f%%)%n", totTooFast, (double) totTooFast / totTotal * 100, + &charNb); printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ", totNoInfo, totTotal); @@ -986,6 +1023,7 @@ static void printAnalysisStatsEval(SyncState* const syncState) 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" @@ -995,13 +1033,15 @@ static void printAnalysisStatsEval(SyncState* const syncState) { for (j= 0; j < i; j++) { - FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j]; - FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[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 == MIDDLE) + if (lpFactors->type == ACCURATE) { printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n", approxNames[lpFactors->type], @@ -1022,6 +1062,7 @@ static void printAnalysisStatsEval(SyncState* const syncState) } } } +#endif } @@ -1537,7 +1578,10 @@ static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const // Create the LP problem glp_term_out(GLP_OFF); - glp_add_rows(lp, hullPointNb); + if (hullPointNb > 0) + { + glp_add_rows(lp, hullPointNb); + } glp_add_cols(lp, 2); glp_set_col_name(lp, 1, "a0"); @@ -1664,18 +1708,18 @@ static Factors* calculateFactors(glp_prob* const lp, const int direction) * initialized. * * Returns: - * Please note that the approximation type may be MIDDLE, INCOMPLETE or + * 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, FactorsCHull* factors) +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= MIDDLE; + factors->type= ACCURATE; calculateFactorsMiddle(factors); } else if (factors->min || factors->max) @@ -1692,31 +1736,48 @@ static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors) /* - * Create and initialize an array like AnalysisStatsCHull.allFactors + * A GFunc for g_queue_foreach() * * Args: - * traceNb: number of traces + * 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: - * A new array, which can be freed with freeAllFactors() + * "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 FactorsCHull** createAllFactors(const unsigned int traceNb) +static gint gcfCompareDouble(gconstpointer a, gconstpointer b) { - FactorsCHull** factorsArray; - unsigned int i; - - factorsArray= malloc(traceNb * sizeof(FactorsCHull*)); - for (i= 0; i < traceNb; i++) + if (*(double*) a < *(double*) b) { - 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 -1; + } + else if (*(double*) a > *(double*) b) + { + return 1; + } + else + { + return 0; } - - return factorsArray; } #endif @@ -1725,37 +1786,36 @@ static FactorsCHull** createAllFactors(const unsigned int traceNb) * 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. + * 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 */ -#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; +#ifdef HAVE_LIBGLPK + unsigned int i, j; AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData; - FactorsCHull** lpFactorsArray= createAllFactors(syncState->traceNb); - FactorsCHull* lpFactors; + 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= @@ -1786,7 +1846,7 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) // Use the LP problem to find the correction factors for this pair of // traces - calculateCompleteFactors(lp, &lpFactorsArray[i][j]); + calculateCompleteFactors(lp, &lpFactorsArray->pairFactors[i][j]); if (syncState->graphsStream) { @@ -1795,15 +1855,13 @@ static void finalizeAnalysisEvalLP(SyncState* const syncState) else { glp_delete_prob(lp); - destroyFactorsCHull(lpFactors); } } } +#endif - g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS), - TRUE); + freeAllFactors(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS)); } -#endif /* @@ -1828,19 +1886,16 @@ static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, AnalysisGraphsEval* graphs= analysisData->graphs; GQueue*** hullArray= ((AnalysisDataCHull*) analysisData->chullSS->analysisData)->hullArray; - FactorsCHull* lpFactors= &graphs->lpFactorsArray[j][i]; + PairFactors* lpFactors= &graphs->lpFactorsArray->pairFactors[j][i]; glp_prob* lp= graphs->lps[j][i]; - if (lpFactors->type == MIDDLE) + if (lpFactors->type == ACCURATE) { int retval; char* cwd; char fileName[40]; FILE* fp; - double* xValues; - unsigned int xBegin, xEnd; - double interval; - const unsigned int graphPointNb= 1000; + GArray* xValues; // Open the data file snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j); @@ -1862,51 +1917,27 @@ static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, 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); + xValues= g_array_sized_new(FALSE, FALSE, sizeof(double), + g_queue_get_length(hullArray[i][j]) + + g_queue_get_length(hullArray[j][i])); - for (it= xBegin; it <= xEnd; it++) - { - xValues[it]= xValues[xBegin] + interval * (it - xBegin); - } + 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 < graphPointNb; it++) + 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, xValues[it]); + glp_set_obj_coef(lp, 2, g_array_index(xValues, double, it)); - fprintf(fp, "%25.9f %25.9f", xValues[it], lpFactors->approx->offset - + lpFactors->approx->drift * xValues[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; @@ -1921,7 +1952,7 @@ static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState, fprintf(fp, "\n"); } - free(xValues); + g_array_free(xValues, TRUE); fclose(fp); fprintf(syncState->graphsStream, @@ -1952,8 +1983,8 @@ static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState, { #ifdef HAVE_LIBGLPK if (((AnalysisDataEval*) - syncState->analysisData)->graphs->lpFactorsArray[j][i].type == - MIDDLE) + syncState->analysisData)->graphs->lpFactorsArray->pairFactors[j][i].type + == ACCURATE) { fprintf(syncState->graphsStream, "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "