From 08365995afd45ea5f6f62f5d8fbc90961de5eacf Mon Sep 17 00:00:00 2001 From: Benjamin Poirier Date: Fri, 14 Aug 2009 15:54:45 -0400 Subject: [PATCH] Add convex hull algorithm-based synchronization This analysis module implements an algorithm that provides a garantee that the synchronization will not result in inverted messages. It is now the default algorithm, over linear regression. Signed-off-by: Benjamin Poirier --- lttv/lttv/Makefile.am | 3 +- lttv/lttv/sync/data_structures_tcp.c | 3 +- lttv/lttv/sync/event_analysis.h | 11 +- lttv/lttv/sync/event_analysis_chull.c | 1627 +++++++++++++++++ lttv/lttv/sync/event_analysis_chull.h | 164 ++ lttv/lttv/sync/event_analysis_linreg.c | 32 +- lttv/lttv/sync/event_matching.h | 4 + lttv/lttv/sync/event_matching_tcp.c | 268 ++- lttv/lttv/sync/event_matching_tcp.h | 18 +- lttv/lttv/sync/event_processing.h | 11 + lttv/lttv/sync/event_processing_lttv_common.c | 95 +- lttv/lttv/sync/event_processing_lttv_common.h | 8 +- lttv/lttv/sync/event_processing_lttv_null.c | 8 +- .../sync/event_processing_lttv_standard.c | 71 +- lttv/lttv/sync/sync_chain.c | 175 +- lttv/lttv/sync/sync_chain.h | 3 + 16 files changed, 2415 insertions(+), 86 deletions(-) create mode 100644 lttv/lttv/sync/event_analysis_chull.c create mode 100644 lttv/lttv/sync/event_analysis_chull.h diff --git a/lttv/lttv/Makefile.am b/lttv/lttv/Makefile.am index de0a170f..a89b55ba 100644 --- a/lttv/lttv/Makefile.am +++ b/lttv/lttv/Makefile.am @@ -59,7 +59,8 @@ lttv_real_SOURCES = \ sync/event_processing_lttv_standard.c\ sync/event_processing_lttv_null.c\ sync/event_matching_tcp.c\ - sync/event_analysis_linreg.c + sync/event_analysis_linreg.c\ + sync/event_analysis_chull.c lttvinclude_HEADERS = \ attribute.h\ diff --git a/lttv/lttv/sync/data_structures_tcp.c b/lttv/lttv/sync/data_structures_tcp.c index 0861f341..4db03098 100644 --- a/lttv/lttv/sync/data_structures_tcp.c +++ b/lttv/lttv/sync/data_structures_tcp.c @@ -27,6 +27,8 @@ #include #include +#include + #include "lookup3.h" #include "data_structures_tcp.h" @@ -382,4 +384,3 @@ void gdnConnectionKeyDestroy(gpointer data) { free((ConnectionKey*) data); } - diff --git a/lttv/lttv/sync/event_analysis.h b/lttv/lttv/sync/event_analysis.h index 3b3cacd5..76658b4e 100644 --- a/lttv/lttv/sync/event_analysis.h +++ b/lttv/lttv/sync/event_analysis.h @@ -20,6 +20,7 @@ #define EVENT_ANALYSIS_H #include +#include #include "data_structures_tcp.h" @@ -33,10 +34,16 @@ typedef struct void (*initAnalysis)(struct _SyncState* const syncState); void (*destroyAnalysis)(struct _SyncState* const syncState); - void (*analyzePacket)(struct _SyncState* const syncState, Packet* const packet); - void (*analyzeExchange)(struct _SyncState* const syncState, Packet* const packet); + void (*analyzePacket)(struct _SyncState* const syncState, Packet* const + packet); + void (*analyzeExchange)(struct _SyncState* const syncState, Packet* const + packet); GArray* (*finalizeAnalysis)(struct _SyncState* const syncState); void (*printAnalysisStats)(struct _SyncState* const syncState); + void (*writeAnalysisGraphsPlots)(FILE* stream, struct _SyncState* const + syncState, const unsigned int i, const unsigned int j); + void (*writeAnalysisGraphsOptions)(FILE* stream, struct _SyncState* const + syncState, const unsigned int i, const unsigned int j); } AnalysisModule; #endif diff --git a/lttv/lttv/sync/event_analysis_chull.c b/lttv/lttv/sync/event_analysis_chull.c new file mode 100644 index 00000000..367b97cf --- /dev/null +++ b/lttv/lttv/sync/event_analysis_chull.c @@ -0,0 +1,1627 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 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 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. + * + * 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. + */ +#define _ISOC99_SOURCE + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include +#include +#include +#include + +#include "sync_chain.h" + +#include "event_analysis_chull.h" + + +#ifndef g_info +#define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) +#endif + + +typedef enum +{ + LOWER, + UPPER +} HullType; + + +typedef enum +{ + MINIMUM, + MAXIMUM +} LineType; + + +// Functions common to all analysis modules +static void initAnalysisCHull(SyncState* const syncState); +static void destroyAnalysisCHull(SyncState* const syncState); + +static void analyzePacketCHull(SyncState* const syncState, Packet* const packet); +static GArray* finalizeAnalysisCHull(SyncState* const syncState); +static void printAnalysisStatsCHull(SyncState* const syncState); +static void writeAnalysisGraphsPlotsCHull(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j); + +// Functions specific to this module +static void registerAnalysisCHull() __attribute__((constructor (101))); + +static void openGraphFiles(SyncState* const syncState); +static void closeGraphFiles(SyncState* const syncState); +static void writeGraphFiles(SyncState* const syncState); +static void gfDumpHullToFile(gpointer data, gpointer userData); + +static void grahamScan(GQueue* const hull, Point* const newPoint, const + HullType type); +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) + __attribute__((pure)); +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 + allFactors, double*** const distances, unsigned int*** const + predecessors); +static void getFactors(FactorsCHull** const allFactors, unsigned int** const + predecessors, unsigned int* const references, const unsigned int traceNum, + Factors* const factors); + +static void gfPointDestroy(gpointer data, gpointer userData); + + +static AnalysisModule analysisModuleCHull= { + .name= "chull", + .initAnalysis= &initAnalysisCHull, + .destroyAnalysis= &destroyAnalysisCHull, + .analyzePacket= &analyzePacketCHull, + .analyzeExchange= NULL, + .finalizeAnalysis= &finalizeAnalysisCHull, + .printAnalysisStats= &printAnalysisStatsCHull, + .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsCHull, + .writeAnalysisGraphsOptions= NULL, +}; + + +/* + * Analysis module registering function + */ +static void registerAnalysisCHull() +{ + g_queue_push_tail(&analysisModules, &analysisModuleCHull); +} + + +/* + * Analysis init function + * + * This function is called at the beginning of a synchronization run for a set + * of traces. + * + * Allocate some of the analysis specific data structures + * + * Args: + * syncState container for synchronization data. + * This function allocates or initializes these analysisData + * members: + * hullArray + * dropped + */ +static void initAnalysisCHull(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataCHull* analysisData; + + analysisData= malloc(sizeof(AnalysisDataCHull)); + syncState->analysisData= analysisData; + + analysisData->hullArray= malloc(syncState->traceNb * sizeof(GQueue**)); + for (i= 0; i < syncState->traceNb; i++) + { + analysisData->hullArray[i]= malloc(syncState->traceNb * sizeof(GQueue*)); + + for (j= 0; j < syncState->traceNb; j++) + { + analysisData->hullArray[i][j]= g_queue_new(); + } + } + + if (syncState->stats) + { + analysisData->stats= malloc(sizeof(AnalysisStatsCHull)); + analysisData->stats->dropped= 0; + analysisData->stats->allFactors= NULL; + } + + if (syncState->graphs) + { + analysisData->graphsData= malloc(sizeof(AnalysisGraphsDataCHull)); + openGraphFiles(syncState); + analysisData->graphsData->allFactors= NULL; + } +} + + +/* + * Create and open files used to store convex hull points to genereate + * graphs. Allocate and populate array to store file pointers. + * + * Args: + * syncState: container for synchronization data + */ +static void openGraphFiles(SyncState* const syncState) +{ + unsigned int i, j; + int retval; + char* cwd; + char name[31]; + AnalysisDataCHull* analysisData; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + cwd= changeToGraphDir(syncState->graphs); + + analysisData->graphsData->hullPoints= malloc(syncState->traceNb * + sizeof(FILE**)); + for (i= 0; i < syncState->traceNb; i++) + { + analysisData->graphsData->hullPoints[i]= malloc(syncState->traceNb * + sizeof(FILE*)); + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + retval= snprintf(name, sizeof(name), + "analysis_chull-%03u_to_%03u.data", j, i); + if (retval > sizeof(name) - 1) + { + name[sizeof(name) - 1]= '\0'; + } + if ((analysisData->graphsData->hullPoints[i][j]= fopen(name, "w")) == + NULL) + { + g_error(strerror(errno)); + } + } + } + } + + retval= chdir(cwd); + if (retval == -1) + { + g_error(strerror(errno)); + } + free(cwd); +} + + +/* + * Write hull points to files to generate graphs. + * + * Args: + * syncState: container for synchronization data + */ +static void writeGraphFiles(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataCHull* analysisData; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + g_queue_foreach(analysisData->hullArray[i][j], + &gfDumpHullToFile, + analysisData->graphsData->hullPoints[i][j]); + } + } + } +} + + +/* + * A GFunc for g_queue_foreach. Write a hull point to a file used to generate + * graphs + * + * Args: + * data: Point*, point to write to the file + * userData: FILE*, file pointer where to write the point + */ +static void gfDumpHullToFile(gpointer data, gpointer userData) +{ + Point* point; + + point= (Point*) data; + fprintf((FILE*) userData, "%20llu %20llu\n", point->x, point->y); +} + + +/* + * Close files used to store convex hull points to generate graphs. + * Deallocate array to store file pointers. + * + * Args: + * syncState: container for synchronization data + */ +static void closeGraphFiles(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataCHull* analysisData; + int retval; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + if (analysisData->graphsData->hullPoints == NULL) + { + return; + } + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + retval= fclose(analysisData->graphsData->hullPoints[i][j]); + if (retval != 0) + { + g_error(strerror(errno)); + } + } + } + free(analysisData->graphsData->hullPoints[i]); + } + free(analysisData->graphsData->hullPoints); + analysisData->graphsData->hullPoints= NULL; +} + + +/* + * Analysis destroy function + * + * Free the analysis specific data structures + * + * Args: + * syncState container for synchronization data. + * This function deallocates these analysisData members: + * hullArray + * stDev + */ +static void destroyAnalysisCHull(SyncState* const syncState) +{ + unsigned int i, j; + AnalysisDataCHull* analysisData; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + if (analysisData == NULL) + { + return; + } + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + g_queue_foreach(analysisData->hullArray[i][j], gfPointDestroy, NULL); + } + free(analysisData->hullArray[i]); + } + free(analysisData->hullArray); + + if (syncState->stats) + { + if (analysisData->stats->allFactors != NULL) + { + freeAllFactors(syncState, analysisData->stats->allFactors); + } + + free(analysisData->stats); + } + + if (syncState->graphs) + { + if (analysisData->graphsData->hullPoints != NULL) + { + closeGraphFiles(syncState); + } + + if (!syncState->stats && analysisData->graphsData->allFactors != NULL) + { + freeAllFactors(syncState, analysisData->graphsData->allFactors); + } + + free(analysisData->graphsData); + } + + free(syncState->analysisData); + syncState->analysisData= NULL; +} + + +/* + * Perform analysis on an event pair. + * + * Args: + * syncState container for synchronization data + * packet structure containing the events + */ +static void analyzePacketCHull(SyncState* const syncState, Packet* const packet) +{ + AnalysisDataCHull* analysisData; + Point* newPoint; + HullType hullType; + GQueue* hull; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + newPoint= malloc(sizeof(Point)); + if (packet->inE->traceNum < packet->outE->traceNum) + { + // CA is inE->traceNum + newPoint->x= packet->inE->tsc; + newPoint->y= packet->outE->tsc; + hullType= UPPER; + g_debug("Reception point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu", + packet->inE->traceNum, packet->outE->traceNum, newPoint->x, + newPoint->y); + } + else + { + // CA is outE->traceNum + newPoint->x= packet->outE->tsc; + newPoint->y= packet->inE->tsc; + hullType= LOWER; + g_debug("Send point hullArray[%lu][%lu] x= inE->tsc= %llu y= outE->tsc= %llu", + packet->inE->traceNum, packet->outE->traceNum, newPoint->x, + newPoint->y); + } + + hull= + analysisData->hullArray[packet->inE->traceNum][packet->outE->traceNum]; + + if (hull->length >= 1 && newPoint->x < ((Point*) + g_queue_peek_tail(hull))->x) + { + if (syncState->stats) + { + analysisData->stats->dropped++; + } + + free(newPoint); + } + else + { + grahamScan(hull, newPoint, hullType); + } +} + + +/* + * Construct one half of a convex hull from abscissa-sorted points + * + * Args: + * hull: the points already in the hull + * newPoint: a new point to consider + * type: which half of the hull to construct + */ +static void grahamScan(GQueue* const hull, Point* const newPoint, const + HullType type) +{ + int inversionFactor; + + g_debug("grahamScan(hull (length: %u), newPoint, %s)", hull->length, type + == LOWER ? "LOWER" : "UPPER"); + + if (type == LOWER) + { + inversionFactor= 1; + } + else + { + inversionFactor= -1; + } + + if (hull->length >= 2) + { + g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d", + hull->length - 2, + hull->length - 1, + jointCmp(g_queue_peek_nth(hull, hull->length - 2), + g_queue_peek_tail(hull), newPoint), + inversionFactor, + jointCmp(g_queue_peek_nth(hull, hull->length - 2), + g_queue_peek_tail(hull), newPoint) * inversionFactor); + } + while (hull->length >= 2 && jointCmp(g_queue_peek_nth(hull, hull->length - + 2), g_queue_peek_tail(hull), newPoint) * inversionFactor <= 0) + { + g_debug("Removing hull[%u]", hull->length); + free((Point*) g_queue_pop_tail(hull)); + + if (hull->length >= 2) + { + g_debug("jointCmp(hull[%u], hull[%u], newPoint) * inversionFactor = %d * %d = %d", + hull->length - 2, + hull->length - 1, + jointCmp(g_queue_peek_nth(hull, hull->length - 2), + g_queue_peek_tail(hull), newPoint), + inversionFactor, + jointCmp(g_queue_peek_nth(hull, hull->length - 2), + g_queue_peek_tail(hull), newPoint) * inversionFactor); + } + } + g_queue_push_tail(hull, newPoint); +} + + +/* + * Finalize the factor calculations + * + * Args: + * syncState container for synchronization data. + * + * Returns: + * Factors[traceNb] synchronization factors for each trace + */ +static GArray* finalizeAnalysisCHull(SyncState* const syncState) +{ + AnalysisDataCHull* analysisData; + GArray* factors; + FactorsCHull** allFactors; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + if (syncState->graphs) + { + writeGraphFiles(syncState); + closeGraphFiles(syncState); + } + + allFactors= calculateAllFactors(syncState); + + factors= reduceFactors(syncState, allFactors); + + if (syncState->stats || syncState->graphs) + { + if (syncState->stats) + { + analysisData->stats->allFactors= allFactors; + } + + if (syncState->graphs) + { + analysisData->graphsData->allFactors= allFactors; + } + } + else + { + freeAllFactors(syncState, allFactors); + } + + return factors; +} + + +/* + * Print statistics related to analysis. Must be called after + * finalizeAnalysis. + * + * Args: + * syncState container for synchronization data. + */ +static void printAnalysisStatsCHull(SyncState* const syncState) +{ + AnalysisDataCHull* analysisData; + unsigned int i, j; + + if (!syncState->stats) + { + return; + } + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + printf("Convex hull analysis stats:\n"); + printf("\tout of order packets dropped from analysis: %u\n", + analysisData->stats->dropped); + + printf("\tNumber of points in convex hulls:\n"); + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= i + 1; j < syncState->traceNb; j++) + { + printf("\t\t%3d - %-3d: lower half-hull %-5u upper half-hull %-5u\n", + i, j, analysisData->hullArray[j][i]->length, + analysisData->hullArray[i][j]->length); + } + } + + printf("\tIndividual synchronization factors:\n"); + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= i + 1; j < syncState->traceNb; j++) + { + FactorsCHull* factorsCHull; + + factorsCHull= &analysisData->stats->allFactors[j][i]; + printf("\t\t%3d - %-3d: ", i, j); + + if (factorsCHull->type == EXACT) + { + printf("Exact a0= % 7g a1= 1 %c %7g\n", + factorsCHull->approx->offset, + factorsCHull->approx->drift < 0. ? '-' : '+', + fabs(factorsCHull->approx->drift)); + } + else if (factorsCHull->type == MIDDLE) + { + printf("Middle a0= % 7g a1= 1 %c %7g accuracy %7g\n", + factorsCHull->approx->offset, factorsCHull->approx->drift + - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift - + 1.), factorsCHull->accuracy); + printf("\t\t a0: % 7g to % 7g (delta= %7g)\n", + factorsCHull->max->offset, factorsCHull->min->offset, + factorsCHull->min->offset - factorsCHull->max->offset); + printf("\t\t a1: 1 %+7g to %+7g (delta= %7g)\n", + factorsCHull->min->drift - 1., factorsCHull->max->drift - + 1., factorsCHull->max->drift - factorsCHull->min->drift); + } + else if (factorsCHull->type == FALLBACK) + { + printf("Fallback a0= % 7g a1= 1 %c %7g error= %7g\n", + factorsCHull->approx->offset, factorsCHull->approx->drift + - 1. < 0. ? '-' : '+', fabs(factorsCHull->approx->drift - + 1.), factorsCHull->accuracy); + } + else if (factorsCHull->type == INCOMPLETE) + { + printf("Incomplete\n"); + + if (factorsCHull->min->drift != -INFINITY) + { + printf("\t\t min: a0: % 7g a1: 1 %c %7g\n", + factorsCHull->min->offset, factorsCHull->min->drift - + 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift - + 1.)); + } + if (factorsCHull->max->drift != INFINITY) + { + printf("\t\t max: a0: % 7g a1: 1 %c %7g\n", + factorsCHull->max->offset, factorsCHull->max->drift - + 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift - + 1.)); + } + } + else if (factorsCHull->type == SCREWED) + { + printf("Screwed\n"); + + if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY) + { + printf("\t\t min: a0: % 7g a1: 1 %c %7g\n", + factorsCHull->min->offset, factorsCHull->min->drift - + 1. < 0 ? '-' : '+', fabs(factorsCHull->min->drift - + 1.)); + } + if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY) + { + printf("\t\t max: a0: % 7g a1: 1 %c %7g\n", + factorsCHull->max->offset, factorsCHull->max->drift - + 1. < 0 ? '-' : '+', fabs(factorsCHull->max->drift - + 1.)); + } + } + else if (factorsCHull->type == ABSENT) + { + printf("Absent\n"); + } + else + { + g_assert_not_reached(); + } + } + } +} + + +/* + * A GFunc for g_queue_foreach() + * + * Args: + * data Point*, point to destroy + * user_data NULL + */ +static void gfPointDestroy(gpointer data, gpointer userData) +{ + Point* point; + + point= (Point*) data; + free(point); +} + + +/* + * Find out if a sequence of three points constitutes a "left turn" or a + * "right turn". + * + * Args: + * p1, p2, p3: The three points. + * + * Returns: + * < 0 right turn + * 0 colinear (unlikely result since this uses floating point + * arithmetic) + * > 0 left turn + */ +static int jointCmp(const Point const* p1, const Point const* p2, const + Point const* p3) +{ + double result; + const double fuzzFactor= 0.; + + result= crossProductK(p1, p2, p1, p3); + g_debug("crossProductK(p1= (%llu, %llu), p2= (%llu, %llu), p1= (%llu, %llu), p3= (%llu, %llu))= %g", + p1->x, p1->y, p2->x, p2->y, p1->x, p1->y, p3->x, p3->y, result); + if (result < fuzzFactor) + { + return -1; + } + else if (result > fuzzFactor) + { + return 1; + } + else + { + return 0; + } +} + + +/* + * Calculate the k component of the cross product of two vectors. + * + * Args: + * p1, p2: start and end points of the first vector + * p3, p4: start and end points of the second vector + * + * Returns: + * the k component of the cross product when considering the two vectors to + * be in the i-j plane. The direction (sign) of the result can be useful to + * determine the relative orientation of the two vectors. + */ +static double crossProductK(const Point const* p1, const Point const* p2, + const Point const* p3, const Point const* p4) +{ + return ((double) p2->x - p1->x) * ((double) p4->y - p3->y) - ((double) + p2->y - p1->y) * ((double) p4->x - p3->x); +} + + +/* + * Free a container of FactorsCHull + * + * Args: + * syncState: container for synchronization data. + * allFactors: container of Factors + */ +static void freeAllFactors(const SyncState* const syncState, FactorsCHull** + const allFactors) +{ + unsigned int i, j; + + for (i= 0; i < syncState->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); + } + } + free(allFactors[i]); + } + free(allFactors); +} + + +/* + * Analyze the convex hulls to determine the synchronization factors between + * each pair of trace. + * + * Args: + * syncState container for synchronization data. + * + * Returns: + * FactorsCHull*[TraceNum][TraceNum] array. See the documentation for the + * member allFactors of AnalysisStatsCHull. + */ +static FactorsCHull** calculateAllFactors(SyncState* const syncState) +{ + unsigned int traceNumA, traceNumB; + FactorsCHull** allFactors; + AnalysisDataCHull* analysisData; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + // Allocate allFactors and calculate min and max + allFactors= malloc(syncState->traceNb * sizeof(FactorsCHull*)); + for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++) + { + allFactors[traceNumA]= malloc((traceNumA + 1) * sizeof(FactorsCHull)); + + allFactors[traceNumA][traceNumA].type= EXACT; + allFactors[traceNumA][traceNumA].approx= malloc(sizeof(Factors)); + allFactors[traceNumA][traceNumA].approx->drift= 1.; + allFactors[traceNumA][traceNumA].approx->offset= 0.; + + for (traceNumB= 0; traceNumB < traceNumA; traceNumB++) + { + unsigned int i; + GQueue* cs, * cr; + const struct + { + LineType lineType; + size_t factorsOffset; + } loopValues[]= { + {MINIMUM, offsetof(FactorsCHull, min)}, + {MAXIMUM, offsetof(FactorsCHull, max)} + }; + + cr= analysisData->hullArray[traceNumB][traceNumA]; + cs= analysisData->hullArray[traceNumA][traceNumB]; + + for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++) + { + g_debug("allFactors[%u][%u].%s = calculateFactorsExact(cr= hullArray[%u][%u], cs= hullArray[%u][%u], %s)", + traceNumA, traceNumB, loopValues[i].factorsOffset == + offsetof(FactorsCHull, min) ? "min" : "max", traceNumB, + traceNumA, traceNumA, traceNumB, loopValues[i].lineType == + MINIMUM ? "MINIMUM" : "MAXIMUM"); + *((Factors**) ((void*) &allFactors[traceNumA][traceNumB] + + loopValues[i].factorsOffset))= + calculateFactorsExact(cr, cs, loopValues[i].lineType); + } + } + } + + // Calculate approx when possible + for (traceNumA= 0; traceNumA < syncState->traceNb; traceNumA++) + { + for (traceNumB= 0; traceNumB < traceNumA; traceNumB++) + { + FactorsCHull* factorsCHull; + + factorsCHull= &allFactors[traceNumA][traceNumB]; + if (factorsCHull->min == NULL && factorsCHull->max == NULL) + { + factorsCHull->type= FALLBACK; + calculateFactorsFallback(analysisData->hullArray[traceNumB][traceNumA], + analysisData->hullArray[traceNumA][traceNumB], + &allFactors[traceNumA][traceNumB]); + } + else if (factorsCHull->min != NULL && factorsCHull->max != NULL) + { + if (factorsCHull->min->drift != -INFINITY && + factorsCHull->max->drift != INFINITY) + { + factorsCHull->type= MIDDLE; + calculateFactorsMiddle(factorsCHull); + } + else if (factorsCHull->min->drift != -INFINITY || + factorsCHull->max->drift != INFINITY) + { + factorsCHull->type= INCOMPLETE; + } + else + { + factorsCHull->type= ABSENT; + } + } + else + { + //g_assert_not_reached(); + factorsCHull->type= SCREWED; + } + } + } + + return allFactors; +} + + +/* Calculate approximative factors based on minimum and maximum limits. The + * best approximation to make is the interior bissector of the angle formed by + * the minimum and maximum lines. + * + * The formulae used come from [Haddad, Yoram: Performance dans les systèmes + * répartis: des outils pour les mesures, Université de Paris-Sud, Centre + * d'Orsay, September 1988] Section 6.1 p.44 + * + * The reasoning for choosing this estimator comes from [Duda, A., Harrus, G., + * Haddad, Y., and Bernard, G.: Estimating global time in distributed systems, + * Proc. 7th Int. Conf. on Distributed Computing Systems, Berlin, volume 18, + * 1987] p.303 + * + * Args: + * factors: contains the min and max limits, used to store the result + */ +static void calculateFactorsMiddle(FactorsCHull* factors) +{ + double amin, amax, bmin, bmax, bhat; + + amin= factors->max->offset; + amax= factors->min->offset; + bmin= factors->min->drift; + bmax= factors->max->drift; + + g_assert_cmpfloat(bmax, >, bmin); + + factors->approx= malloc(sizeof(Factors)); + bhat= (bmax * bmin - 1. + sqrt(1. + pow(bmax, 2.) * pow(bmin, 2.) + + pow(bmax, 2.) + pow(bmin, 2.))) / (bmax + bmin); + factors->approx->offset= amax - (amax - amin) / 2. * (pow(bhat, 2.) + 1.) + / (1. + bhat * bmax); + factors->approx->drift= bhat; + factors->accuracy= bmax - bmin; +} + + +/* + * Analyze the convex hulls to determine the minimum or maximum + * synchronization factors between one pair of trace. + * + * This implements and improves upon the algorithm in [Haddad, Yoram: + * Performance dans les systèmes répartis: des outils pour les mesures, + * Université de Paris-Sud, Centre d'Orsay, September 1988] Section 6.2 p.47 + * + * Some degenerate cases are possible: + * 1) the result is unbounded. In that case, when searching for the maximum + * factors, result->drift= INFINITY; result->offset= -INFINITY. When + * searching for the minimum factors, it is the opposite. It is not + * possible to improve the situation with this data. + * 2) no line can be above the upper hull and below the lower hull. This is + * because the hulls intersect each other or are reversed. This means that + * an assertion was false. Most probably, the clocks are not linear. It is + * possible to repeat the search with another algorithm that will find a + * "best effort" approximation. See calculateFactorsApprox(). + * + * Args: + * cu: the upper half-convex hull, the line must pass above this + * and touch it in one point + * cl: the lower half-convex hull, the line must pass below this + * and touch it in one point + * lineType: search for minimum or maximum factors + * + * Returns: + * If a result is found, a struct Factors is allocated, filed with the + * result and returned + * NULL otherwise, degenerate case 2 is in effect + */ +static Factors* calculateFactorsExact(GQueue* const cu, GQueue* const cl, const + LineType lineType) +{ + GQueue* c1, * c2; + unsigned int i1, i2; + Point* p1, * p2; + double inversionFactor; + Factors* result; + + g_debug("calculateFactorsExact(cu= %p, cl= %p, %s)", cu, cl, lineType == + MINIMUM ? "MINIMUM" : "MAXIMUM"); + + if (lineType == MINIMUM) + { + c1= cl; + c2= cu; + inversionFactor= -1.; + } + else + { + c1= cu; + c2= cl; + inversionFactor= 1.; + } + + i1= 0; + i2= c2->length - 1; + + // Check for degenerate case 1 + if (c1->length == 0 || c2->length == 0 || ((Point*) g_queue_peek_nth(c1, + i1))->x >= ((Point*) g_queue_peek_nth(c2, i2))->x) + { + result= malloc(sizeof(Factors)); + if (lineType == MINIMUM) + { + result->drift= -INFINITY; + result->offset= INFINITY; + } + else + { + result->drift= INFINITY; + result->offset= -INFINITY; + } + + return result; + } + + do + { + while + ( + (int) i2 - 1 > 0 + && crossProductK( + g_queue_peek_nth(c1, i1), + g_queue_peek_nth(c2, i2), + g_queue_peek_nth(c1, i1), + g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0. + ) + { + if (((Point*) g_queue_peek_nth(c1, i1))->x + < ((Point*) g_queue_peek_nth(c2, i2 - 1))->x) + { + i2--; + } + else + { + // Degenerate case 2 + return NULL; + } + } + while + ( + i1 + 1 < c1->length - 1 + && crossProductK( + g_queue_peek_nth(c1, i1), + g_queue_peek_nth(c2, i2), + g_queue_peek_nth(c1, i1 + 1), + g_queue_peek_nth(c2, i2)) * inversionFactor < 0. + ) + { + if (((Point*) g_queue_peek_nth(c1, i1 + 1))->x + < ((Point*) g_queue_peek_nth(c2, i2))->x) + { + i1++; + } + else + { + // Degenerate case 2 + return NULL; + } + } + } while + ( + (int) i2 - 1 > 0 + && crossProductK( + g_queue_peek_nth(c1, i1), + g_queue_peek_nth(c2, i2), + g_queue_peek_nth(c1, i1), + g_queue_peek_nth(c2, i2 - 1)) * inversionFactor < 0. + ); + + p1= g_queue_peek_nth(c1, i1); + p2= g_queue_peek_nth(c2, i2); + + g_debug("Resulting points are: c1[i1]: x= %llu y= %llu c2[i2]: x= %llu y= %llu", + p1->x, p1->y, p2->x, p2->y); + + result= malloc(sizeof(Factors)); + result->drift= slope(p1, p2); + result->offset= intercept(p1, p2); + + g_debug("Resulting factors are: drift= %g offset= %g", result->drift, result->offset); + + return result; +} + + +/* + * Analyze the convex hulls to determine approximate synchronization factors + * between one pair of trace when there is no line that can fit in the + * corridor separating them. + * + * This implements the algorithm in [Ashton, P.: Algorithms for Off-line Clock + * Synchronisation, University of Canterbury, December 1995, 26] Section 4.2.2 + * p.7 + * + * For each point p1 in cr + * For each point p2 in cs + * errorMin= 0 + * Calculate the line paramaters + * For each point p3 in each convex hull + * If p3 is on the wrong side of the line + * error+= distance + * If error < errorMin + * Update results + * + * Args: + * cr: the upper half-convex hull + * cs: the lower half-convex hull + * result: a pointer to the pre-allocated struct where the results + * will be stored + */ +static void calculateFactorsFallback(GQueue* const cr, GQueue* const cs, + FactorsCHull* const result) +{ + unsigned int i, j, k; + double errorMin; + Factors* approx; + + errorMin= INFINITY; + approx= malloc(sizeof(Factors)); + + for (i= 0; i < cs->length; i++) + { + for (j= 0; j < cr->length; j++) + { + double error; + Point p1, p2; + + error= 0.; + + if (((Point*) g_queue_peek_nth(cs, i))->x < ((Point*)g_queue_peek_nth(cr, j))->x) + { + p1= *(Point*)g_queue_peek_nth(cs, i); + p2= *(Point*)g_queue_peek_nth(cr, j); + } + else + { + p1= *(Point*)g_queue_peek_nth(cr, j); + p2= *(Point*)g_queue_peek_nth(cs, i); + } + + // The lower hull should be above the point + for (k= 0; k < cs->length; k++) + { + if (jointCmp(&p1, &p2, g_queue_peek_nth(cs, k)) < 0.) + { + error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cs, k)); + } + } + + // The upper hull should be below the point + for (k= 0; k < cr->length; k++) + { + if (jointCmp(&p1, &p2, g_queue_peek_nth(cr, k)) > 0.) + { + error+= verticalDistance(&p1, &p2, g_queue_peek_nth(cr, k)); + } + } + + if (error < errorMin) + { + g_debug("Fallback: i= %u j= %u is a better match (error= %g)", i, j, error); + approx->drift= slope(&p1, &p2); + approx->offset= intercept(&p1, &p2); + errorMin= error; + } + } + } + + result->approx= approx; + result->accuracy= errorMin; +} + + +/* + * Calculate the vertical distance between a line and a point + * + * Args: + * p1, p2: Two points defining the line + * point: a point + * + * Return: + * the vertical distance + */ +static double verticalDistance(Point* p1, Point* p2, Point* const point) +{ + return fabs(slope(p1, p2) * point->x + intercept(p1, p2) - point->y); +} + + +/* + * Calculate the slope between two points + * + * Args: + * p1, p2 the two points + * + * Returns: + * the slope + */ +static double slope(const Point* const p1, const Point* const p2) +{ + return ((double) p2->y - p1->y) / (p2->x - p1->x); +} + + +/* Calculate the y-intercept of a line that passes by two points + * + * Args: + * p1, p2 the two points + * + * Returns: + * the y-intercept + */ +static double intercept(const Point* const p1, const Point* const p2) +{ + return ((double) p2->y * p1->x - (double) p1->y * p2->x) / ((double) p1->x - p2->x); +} + + +/* + * Calculate a resulting offset and drift for each trace. + * + * Traces are assembled in groups. A group is an "island" of nodes/traces that + * exchanged messages. A reference is determined for each group by using a + * shortest path search based on the accuracy of the approximation. This also + * forms a tree of the best way to relate each node's clock to the reference's + * based on the accuracy. Sometimes it may be necessary or advantageous to + * propagate the factors through intermediary clocks. Resulting factors for + * each trace are determined based on this tree. + * + * This part was not the focus of my research. The algorithm used here is + * inexact in some ways: + * 1) The reference used may not actually be the best one to use. This is + * because the accuracy is not corrected based on the drift during the + * shortest path search. + * 2) The min and max factors are not propagated and are no longer valid. + * 3) Approximations of different types (MIDDLE and FALLBACK) are compared + * together. The "accuracy" parameters of these have different meanings and + * are not readily comparable. + * + * Nevertheless, the result is satisfactory. You just can't tell "how much" it + * is. + * + * Two alternative (and subtly different) ways of propagating factors to + * preserve min and max bondaries have been proposed, see: + * [Duda, A., Harrus, G., Haddad, Y., and Bernard, G.: Estimating global time + * in distributed systems, Proc. 7th Int. Conf. on Distributed Computing + * Systems, Berlin, volume 18, 1987] p.304 + * + * [Jezequel, J.M., and Jard, C.: Building a global clock for observing + * computations in distributed memory parallel computers, Concurrency: + * Practice and Experience 8(1), volume 8, John Wiley & Sons, Ltd Chichester, + * 1996, 32] Section 5; which is mostly the same as + * [Jezequel, J.M.: Building a global time on parallel machines, Proceedings + * of the 3rd International Workshop on Distributed Algorithms, LNCS, volume + * 392, 136–147, 1989] Section 5 + * + * Args: + * syncState: container for synchronization data. + * allFactors: offset and drift between each pair of traces + * + * Returns: + * Factors[traceNb] synchronization factors for each trace + */ +static GArray* reduceFactors(SyncState* const syncState, FactorsCHull** const + allFactors) +{ + GArray* factors; + double** distances; + unsigned int** predecessors; + double* distanceSums; + unsigned int* references; + unsigned int i, j; + + // Solve the all-pairs shortest path problem using the Floyd-Warshall + // algorithm + floydWarshall(syncState, allFactors, &distances, &predecessors); + + /* Find the reference for each node + * + * First calculate, for each node, the sum of the distances to each other + * node it can reach. + * + * Then, go through each "island" of traces to find the trace that has the + * lowest distance sum. Assign this trace as the reference to each trace + * of the island. + */ + distanceSums= malloc(syncState->traceNb * sizeof(double)); + for (i= 0; i < syncState->traceNb; i++) + { + distanceSums[i]= 0.; + for (j= 0; j < syncState->traceNb; j++) + { + distanceSums[i]+= distances[i][j]; + } + } + + references= malloc(syncState->traceNb * sizeof(unsigned int)); + for (i= 0; i < syncState->traceNb; i++) + { + references[i]= UINT_MAX; + } + for (i= 0; i < syncState->traceNb; i++) + { + if (references[i] == UINT_MAX) + { + unsigned int reference; + double distanceSumMin; + + // A node is its own reference by default + reference= i; + distanceSumMin= INFINITY; + for (j= 0; j < syncState->traceNb; j++) + { + if (distances[i][j] != INFINITY && distanceSums[j] < + distanceSumMin) + { + reference= j; + distanceSumMin= distanceSums[j]; + } + } + for (j= 0; j < syncState->traceNb; j++) + { + if (distances[i][j] != INFINITY) + { + references[j]= reference; + } + } + } + } + + for (i= 0; i < syncState->traceNb; i++) + { + free(distances[i]); + } + free(distances); + free(distanceSums); + + /* For each trace, calculate the factors based on their corresponding + * tree. The tree is rooted at the reference and the shortest path to each + * other nodes are the branches. + */ + 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++) + { + getFactors(allFactors, predecessors, references, i, &g_array_index(factors, + Factors, i)); + } + + for (i= 0; i < syncState->traceNb; i++) + { + free(predecessors[i]); + } + free(predecessors); + free(references); + + return factors; +} + + +/* + * Perform an all-source shortest path search using the Floyd-Warshall + * algorithm. + * + * The algorithm is implemented accoding to the description here: + * http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html + * + * Args: + * syncState: container for synchronization data. + * allFactors: offset and drift between each pair of traces + * distances: resulting matrix of the length of the shortest path between + * two nodes. If there is no path between two nodes, the + * length is INFINITY + * predecessors: resulting matrix of each node's predecessor on the shortest + * path between two nodes + */ +static void floydWarshall(SyncState* const syncState, FactorsCHull** const + allFactors, double*** const distances, unsigned int*** const + predecessors) +{ + unsigned int i, j, k; + + // Setup initial conditions + *distances= malloc(syncState->traceNb * sizeof(double*)); + *predecessors= malloc(syncState->traceNb * sizeof(unsigned int*)); + for (i= 0; i < syncState->traceNb; i++) + { + (*distances)[i]= malloc(syncState->traceNb * sizeof(double)); + for (j= 0; j < syncState->traceNb; j++) + { + if (i == j) + { + g_assert(allFactors[i][j].type == EXACT); + + (*distances)[i][j]= 0.; + } + else + { + unsigned int row, col; + + if (i > j) + { + row= i; + col= j; + } + else if (i < j) + { + row= j; + col= i; + } + + if (allFactors[row][col].type == MIDDLE || + allFactors[row][col].type == FALLBACK) + { + (*distances)[i][j]= allFactors[row][col].accuracy; + } + else if (allFactors[row][col].type == INCOMPLETE || + allFactors[row][col].type == SCREWED || + allFactors[row][col].type == ABSENT) + { + (*distances)[i][j]= INFINITY; + } + else + { + g_assert_not_reached(); + } + } + } + + (*predecessors)[i]= malloc(syncState->traceNb * sizeof(unsigned int)); + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + (*predecessors)[i][j]= i; + } + else + { + (*predecessors)[i][j]= UINT_MAX; + } + } + } + + // Run the iterations + for (k= 0; k < syncState->traceNb; k++) + { + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + double distanceMin; + + distanceMin= MIN((*distances)[i][j], (*distances)[i][k] + + (*distances)[k][j]); + + if (distanceMin != (*distances)[i][j]) + { + (*predecessors)[i][j]= (*predecessors)[k][j]; + } + + (*distances)[i][j]= distanceMin; + } + } + } +} + + +/* + * Cummulate the time correction factors to convert a node's time to its + * reference's time. + * This function recursively calls itself until it reaches the reference node. + * + * Args: + * allFactors: offset and drift between each pair of traces + * predecessors: matrix of each node's predecessor on the shortest + * path between two nodes + * references: reference node for each node + * traceNum: node for which to find the factors + * factors: resulting factors + */ +static void getFactors(FactorsCHull** const allFactors, unsigned int** const + predecessors, unsigned int* const references, const unsigned int traceNum, + Factors* const factors) +{ + unsigned int reference; + + reference= references[traceNum]; + + if (reference == traceNum) + { + factors->offset= 0.; + factors->drift= 1.; + } + else + { + Factors previousVertexFactors; + + getFactors(allFactors, predecessors, references, + predecessors[reference][traceNum], &previousVertexFactors); + + // convertir de traceNum à reference + + // allFactors convertit de col à row + + if (reference > traceNum) + { + factors->offset= previousVertexFactors.drift * + allFactors[reference][traceNum].approx->offset + + previousVertexFactors.offset; + factors->drift= previousVertexFactors.drift * + allFactors[reference][traceNum].approx->drift; + } + else + { + factors->offset= previousVertexFactors.drift * (-1. * + allFactors[traceNum][reference].approx->offset / + allFactors[traceNum][reference].approx->drift) + + previousVertexFactors.offset; + factors->drift= previousVertexFactors.drift * (1. / + allFactors[traceNum][reference].approx->drift); + } + } +} + + +/* + * 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 + */ +void writeAnalysisGraphsPlotsCHull(FILE* stream, SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ + AnalysisDataCHull* analysisData; + FactorsCHull* factorsCHull; + + analysisData= (AnalysisDataCHull*) syncState->analysisData; + + fprintf(stream, + "\t\"analysis_chull-%1$03d_to_%2$03d.data\" " + "title \"Lower half-hull\" with linespoints " + "linecolor rgb \"#015a01\" linetype 4 pointtype 8 pointsize 0.8, \\\n" + "\t\"analysis_chull-%2$03d_to_%1$03d.data\" " + "title \"Upper half-hull\" with linespoints " + "linecolor rgb \"#003366\" linetype 4 pointtype 10 pointsize 0.8, \\\n", + i, j); + + factorsCHull= &analysisData->graphsData->allFactors[j][i]; + if (factorsCHull->type == EXACT) + { + fprintf(stream, + "\t%7g + %7g * x " + "title \"Exact conversion\" with lines " + "linecolor rgb \"black\" linetype 1, \\\n", + factorsCHull->approx->offset, factorsCHull->approx->drift); + } + else if (factorsCHull->type == MIDDLE) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Min conversion\" with lines " + "linecolor rgb \"black\" linetype 5, \\\n", + factorsCHull->min->offset, factorsCHull->min->drift); + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Max conversion\" with lines " + "linecolor rgb \"black\" linetype 8, \\\n", + factorsCHull->max->offset, factorsCHull->max->drift); + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Middle conversion\" with lines " + "linecolor rgb \"gray60\" linetype 1, \\\n", + factorsCHull->approx->offset, factorsCHull->approx->drift); + } + else if (factorsCHull->type == FALLBACK) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Fallback conversion\" with lines " + "linecolor rgb \"gray60\" linetype 1, \\\n", + factorsCHull->approx->offset, factorsCHull->approx->drift); + } + else if (factorsCHull->type == INCOMPLETE) + { + if (factorsCHull->min->drift != -INFINITY) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Min conversion\" with lines " + "linecolor rgb \"black\" linetype 5, \\\n", + factorsCHull->min->offset, factorsCHull->min->drift); + } + + if (factorsCHull->max->drift != INFINITY) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Max conversion\" with lines " + "linecolor rgb \"black\" linetype 8, \\\n", + factorsCHull->max->offset, factorsCHull->max->drift); + } + } + else if (factorsCHull->type == SCREWED) + { + if (factorsCHull->min != NULL && factorsCHull->min->drift != -INFINITY) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Min conversion\" with lines " + "linecolor rgb \"black\" linetype 5, \\\n", + factorsCHull->min->offset, factorsCHull->min->drift); + } + + if (factorsCHull->max != NULL && factorsCHull->max->drift != INFINITY) + { + fprintf(stream, + "\t%.2f + %.10f * x " + "title \"Max conversion\" with lines " + "linecolor rgb \"black\" linetype 8, \\\n", + factorsCHull->max->offset, factorsCHull->max->drift); + } + } + else if (factorsCHull->type == ABSENT) + { + } + else + { + g_assert_not_reached(); + } +} diff --git a/lttv/lttv/sync/event_analysis_chull.h b/lttv/lttv/sync/event_analysis_chull.h new file mode 100644 index 00000000..ed4284d8 --- /dev/null +++ b/lttv/lttv/sync/event_analysis_chull.h @@ -0,0 +1,164 @@ +/* This file is part of the Linux Trace Toolkit viewer + * Copyright (C) 2009 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 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. + * + * 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. + */ + +#ifndef EVENT_ANALYSIS_CHULL_H +#define EVENT_ANALYSIS_CHULL_H + +#include + +#include "data_structures_tcp.h" + + +typedef struct +{ + LttCycleCount x, y; +} Point; + + +typedef enum +{ + /* 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, + /* The approximation is the middle of the min and max limits, all fields + * are initialized. + */ + MIDDLE, + /* 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, + /* 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, + /* The pair of trace did not have communications in both directions (maybe + * even no communication at all). approx and accuracy are not initialized. + */ + ABSENT, + /* 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, +} ApproxType; + + +typedef struct +{ + Factors* min, * max, * approx; + ApproxType type; + double accuracy; +} FactorsCHull; + + +typedef struct +{ + unsigned int dropped; + + /* FactorsCHull allFactors[traceNb][traceNb] + * + * allFactors is divided into three parts depending on the position of an + * element allFactors[i][j]: + * Lower triangular part of the matrix + * i > j + * This contains the factors between nodes i and j. These factors + * convert the time values of j to time values of i. + * Diagonal part of the matrix + * i = j + * This contains identity factors (a0= 0, a1= 1). + * Upper triangular part of the matrix + * i < j + * This area is not allocated. + */ + FactorsCHull** allFactors; +} AnalysisStatsCHull; + + +typedef struct +{ + /* This array contains file pointers to files where hull points x-y data + * is outputed. Each trace-pair has two files, one for each message + * direction. The structure of the array is the same as for hullArray, + * hullPoints[row][col] where: + * row= inE->traceNum + * col= outE->traceNum + * + * The elements on the diagonal are not initialized. + */ + FILE*** hullPoints; + + /* FactorsCHull allFactors[traceNb][traceNb] + * This is the same array as AnalysisStatsCHull.allFactors. + */ + FactorsCHull** allFactors; +} AnalysisGraphsDataCHull; + + +typedef struct +{ + /* 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 + * direction of messages (sent or received) is relative to CA. Points are + * formed such that their abscissa comes from CA and their ordinate from + * CB. + * + * hullArray is divided into three parts depending on the position of an + * element hullArray[i][j]: + * Lower triangular part of the matrix + * i > j + * This contains the points that form lower hulls, therefore that + * represent "sent" messages. + * Upper triangular part of the matrix + * i < j + * This contains the points that form upper hulls, therefore that + * represent "received" messages. + * Diagonal part of the matrix + * i = j + * This contains empty lists + * + * When a message is such that: + * inE->traceNum < outE->traceNum + * CA is inE->traceNum, therefore the message was received and may + * generate a point in the upper hull. Upper hulls are such that i < + * j, therefore, i= inE->traceNum and j= outE->traceNum. + * inE->traceNum > outE->traceNum + * CA is outE->traceNum, therefore the message was sent and may + * generate a point in the lower hull. Lower hulls are such that i > + * j, therefore, i= inE->traceNum and j= outE->traceNum. Hence, we + * always have: + * i= inE->traceNum + * j= outE->traceNum + * + * Do not let yourself get confused! Always remember that the "lower hull" + * is in fact the "lower half" of a hull. When assumptions are respected, + * the lower half is above the upper half. + */ + GQueue*** hullArray; + + AnalysisStatsCHull* stats; + AnalysisGraphsDataCHull* graphsData; +} AnalysisDataCHull; + +#endif diff --git a/lttv/lttv/sync/event_analysis_linreg.c b/lttv/lttv/sync/event_analysis_linreg.c index 8a7bd227..41a32aeb 100644 --- a/lttv/lttv/sync/event_analysis_linreg.c +++ b/lttv/lttv/sync/event_analysis_linreg.c @@ -44,9 +44,11 @@ static void destroyAnalysisLinReg(SyncState* const syncState); static void analyzeExchangeLinReg(SyncState* const syncState, Packet* const packet); static GArray* finalizeAnalysisLinReg(SyncState* const syncState); static void printAnalysisStatsLinReg(SyncState* const syncState); +static void writeAnalysisGraphsPlotsLinReg(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j); // Functions specific to this module -static void registerAnalysisLinReg() __attribute__((constructor (101))); +static void registerAnalysisLinReg() __attribute__((constructor (102))); static void finalizeLSA(SyncState* const syncState); static void doGraphProcessing(SyncState* const syncState); @@ -73,6 +75,8 @@ static AnalysisModule analysisModuleLinReg= { .analyzeExchange= &analyzeExchangeLinReg, .finalizeAnalysis= &finalizeAnalysisLinReg, .printAnalysisStats= &printAnalysisStatsLinReg, + .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsLinReg, + .writeAnalysisGraphsOptions= NULL, }; @@ -483,6 +487,7 @@ static GArray* calculateFactors(SyncState* const syncState) analysisData= (AnalysisDataLinReg*) syncState->analysisData; factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors), syncState->traceNb); + g_array_set_size(factors, syncState->traceNb); // Calculate the resulting offset and drift between each trace and its // reference @@ -743,3 +748,28 @@ static gint gcfGraphTraceCompare(gconstpointer a, gconstpointer b) } } + +/* + * 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, on the x axis + * j: second trace number, garanteed to be larger than i + */ +void writeAnalysisGraphsPlotsLinReg(FILE* stream, SyncState* const syncState, + const unsigned int i, const unsigned int j) +{ + AnalysisDataLinReg* analysisData; + Fit* fit; + + analysisData= (AnalysisDataLinReg*) syncState->analysisData; + fit= &analysisData->fitArray[j][i]; + + fprintf(stream, + "\t%7g + %7g * x " + "title \"Linreg conversion\" with lines " + "linecolor rgb \"gray60\" linetype 1, \\\n", + fit->d0, 1. + fit->x); +} diff --git a/lttv/lttv/sync/event_matching.h b/lttv/lttv/sync/event_matching.h index f8b4a109..0c3fe2d1 100644 --- a/lttv/lttv/sync/event_matching.h +++ b/lttv/lttv/sync/event_matching.h @@ -37,6 +37,10 @@ typedef struct EventType eventType); GArray* (*finalizeMatching)(struct _SyncState* const syncState); void (*printMatchingStats)(struct _SyncState* const syncState); + void (*writeMatchingGraphsPlots)(FILE* stream, struct _SyncState* const + syncState, const unsigned int i, const unsigned int j); + void (*writeMatchingGraphsOptions)(FILE* stream, struct _SyncState* const + syncState, const unsigned int i, const unsigned int j); } MatchingModule; #endif diff --git a/lttv/lttv/sync/event_matching_tcp.c b/lttv/lttv/sync/event_matching_tcp.c index 892dc7af..5c0e3b69 100644 --- a/lttv/lttv/sync/event_matching_tcp.c +++ b/lttv/lttv/sync/event_matching_tcp.c @@ -20,8 +20,10 @@ #include #endif +#include #include #include +#include #include "event_analysis.h" #include "sync_chain.h" @@ -42,6 +44,10 @@ static void matchEventTCP(SyncState* const syncState, NetEvent* const event, EventType eventType); static GArray* finalizeMatchingTCP(SyncState* const syncState); static void printMatchingStatsTCP(SyncState* const syncState); +static void writeMatchingGraphsPlotsTCP(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j); +static void writeMatchingGraphsOptionsTCP(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j); // Functions specific to this module static void registerMatchingTCP() __attribute__((constructor (101))); @@ -57,6 +63,10 @@ static bool needsAck(const Packet* const packet); static void buildReversedConnectionKey(ConnectionKey* const reversedConnectionKey, const ConnectionKey* const connectionKey); +static void openGraphDataFiles(SyncState* const syncState); +static void closeGraphDataFiles(SyncState* const syncState); +static void writeMessagePoint(FILE* stream, const Packet* const packet); + static MatchingModule matchingModuleTCP = { .name= "TCP", @@ -65,6 +75,8 @@ static MatchingModule matchingModuleTCP = { .matchEvent= &matchEventTCP, .finalizeMatching= &finalizeMatchingTCP, .printMatchingStats= &printMatchingStatsTCP, + .writeMatchingGraphsPlots= &writeMatchingGraphsPlotsTCP, + .writeMatchingGraphsOptions= &writeMatchingGraphsOptionsTCP, }; @@ -110,12 +122,30 @@ static void initMatchingTCP(SyncState* const syncState) if (syncState->stats) { + unsigned int i; + matchingData->stats= calloc(1, sizeof(MatchingStatsTCP)); + matchingData->stats->totMessageArray= malloc(syncState->traceNb * + sizeof(unsigned int*)); + for (i= 0; i < syncState->traceNb; i++) + { + matchingData->stats->totMessageArray[i]= + calloc(syncState->traceNb, sizeof(unsigned int)); + } } else { matchingData->stats= NULL; } + + if (syncState->graphs) + { + openGraphDataFiles(syncState); + } + else + { + matchingData->messagePoints= NULL; + } } @@ -144,6 +174,13 @@ static void destroyMatchingTCP(SyncState* const syncState) if (syncState->stats) { + unsigned int i; + + for (i= 0; i < syncState->traceNb; i++) + { + free(matchingData->stats->totMessageArray[i]); + } + free(matchingData->stats->totMessageArray); free(matchingData->stats); } @@ -176,13 +213,15 @@ static void partialDestroyMatchingTCP(SyncState* const syncState) return; } - g_debug("Cleaning up unMatchedInE list\n"); g_hash_table_destroy(matchingData->unMatchedInE); matchingData->unMatchedInE= NULL; - g_debug("Cleaning up unMatchedOutE list\n"); g_hash_table_destroy(matchingData->unMatchedOutE); - g_debug("Cleaning up unAcked list\n"); g_hash_table_destroy(matchingData->unAcked); + + if (syncState->graphs && matchingData->messagePoints) + { + closeGraphDataFiles(syncState); + } } @@ -242,6 +281,7 @@ static GArray* finalizeMatchingTCP(SyncState* const syncState) */ static void printMatchingStatsTCP(SyncState* const syncState) { + unsigned int i, j; MatchingDataTCP* matchingData; if (!syncState->stats) @@ -252,14 +292,30 @@ static void printMatchingStatsTCP(SyncState* const syncState) matchingData= (MatchingDataTCP*) syncState->matchingData; printf("TCP matching stats:\n"); - printf("\ttotal input and output events matched together to form a packet: %d\n", + printf("\ttotal input and output events matched together to form a packet: %u\n", matchingData->stats->totPacket); - printf("\ttotal packets identified needing an acknowledge: %d\n", - matchingData->stats->totPacketNeedAck); - printf("\ttotal exchanges (four events matched together): %d\n", - matchingData->stats->totExchangeEffective); - printf("\ttotal synchronization exchanges: %d\n", - matchingData->stats->totExchangeSync); + + printf("\tMessage traffic:\n"); + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= i + 1; j < syncState->traceNb; j++) + { + printf("\t\t%3d - %-3d: sent %-10u received %-10u\n", i, j, + matchingData->stats->totMessageArray[j][i], + matchingData->stats->totMessageArray[i][j]); + } + } + + if (syncState->analysisModule->analyzeExchange != NULL) + { + printf("\ttotal packets identified needing an acknowledge: %u\n", + matchingData->stats->totPacketNeedAck); + printf("\ttotal exchanges (four events matched together): %u\n", + matchingData->stats->totExchangeEffective); + printf("\ttotal synchronization exchanges: %u\n", + matchingData->stats->totExchangeSync); + } if (syncState->analysisModule->printAnalysisStats != NULL) { @@ -298,11 +354,6 @@ static void matchEvents(SyncState* const syncState, NetEvent* const event, { g_debug("Found matching companion event, "); - if (syncState->stats) - { - matchingData->stats->totPacket++; - } - // If it's there, remove it and create a Packet g_hash_table_steal(unMatchedOppositeList, event->packetKey); packet= malloc(sizeof(Packet)); @@ -313,6 +364,12 @@ static void matchEvents(SyncState* const syncState, NetEvent* const event, packet->outE->packetKey= packet->inE->packetKey; packet->acks= NULL; + if (syncState->stats) + { + matchingData->stats->totPacket++; + matchingData->stats->totMessageArray[packet->inE->traceNum][packet->outE->traceNum]++; + } + // Discard loopback traffic if (packet->inE->traceNum == packet->outE->traceNum) { @@ -320,14 +377,20 @@ static void matchEvents(SyncState* const syncState, NetEvent* const event, return; } - if (syncState->analysisModule->analyzePacket) + if (syncState->graphs) + { + writeMessagePoint(matchingData->messagePoints[packet->inE->traceNum][packet->outE->traceNum], + packet); + } + + if (syncState->analysisModule->analyzePacket != NULL) { syncState->analysisModule->analyzePacket(syncState, packet); } // We can skip the rest of the algorithm if the analysis module is not // interested in exchanges - if (!syncState->analysisModule->analyzeExchange) + if (syncState->analysisModule->analyzeExchange == NULL) { destroyPacket(packet); return; @@ -499,3 +562,174 @@ static void buildReversedConnectionKey(ConnectionKey* const reversedConnectionKey->source= connectionKey->dest; reversedConnectionKey->dest= connectionKey->source; } + + +/* + * Create and open files used to store message points to genereate + * graphs. Allocate and populate array to store file pointers. + * + * Args: + * syncState: container for synchronization data + */ +static void openGraphDataFiles(SyncState* const syncState) +{ + unsigned int i, j; + int retval; + char* cwd; + char name[29]; + MatchingDataTCP* matchingData; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + cwd= changeToGraphDir(syncState->graphs); + + matchingData->messagePoints= malloc(syncState->traceNb * sizeof(FILE**)); + for (i= 0; i < syncState->traceNb; i++) + { + matchingData->messagePoints[i]= malloc(syncState->traceNb * + sizeof(FILE*)); + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + retval= snprintf(name, sizeof(name), + "matching_tcp-%03u_to_%03u.data", j, i); + if (retval > sizeof(name) - 1) + { + name[sizeof(name) - 1]= '\0'; + } + if ((matchingData->messagePoints[i][j]= fopen(name, "w")) == + NULL) + { + g_error(strerror(errno)); + } + } + } + } + + retval= chdir(cwd); + if (retval == -1) + { + g_error(strerror(errno)); + } + free(cwd); +} + + +/* + * Write a message point to a file used to generate graphs + * + * Args: + * stream: FILE*, file pointer where to write the point + * packet: message for which to write the point + */ +static void writeMessagePoint(FILE* stream, const Packet* const packet) +{ + LttCycleCount x, y; + + if (packet->inE->traceNum < packet->outE->traceNum) + { + // CA is inE->traceNum + x= packet->inE->tsc; + y= packet->outE->tsc; + } + else + { + // CA is outE->traceNum + x= packet->outE->tsc; + y= packet->inE->tsc; + } + + fprintf(stream, "%20llu %20llu\n", x, y); +} + + +/* + * Close files used to store convex hull points to genereate graphs. + * Deallocate array to store file pointers. + * + * Args: + * syncState: container for synchronization data + */ +static void closeGraphDataFiles(SyncState* const syncState) +{ + unsigned int i, j; + MatchingDataTCP* matchingData; + int retval; + + matchingData= (MatchingDataTCP*) syncState->matchingData; + + if (matchingData->messagePoints == NULL) + { + return; + } + + for (i= 0; i < syncState->traceNb; i++) + { + for (j= 0; j < syncState->traceNb; j++) + { + if (i != j) + { + retval= fclose(matchingData->messagePoints[i][j]); + if (retval != 0) + { + g_error(strerror(errno)); + } + } + } + free(matchingData->messagePoints[i]); + } + free(matchingData->messagePoints); + + matchingData->messagePoints= NULL; +} + + +/* + * Write the matching-specific graph lines in the gnuplot script. Call the + * downstream module's graph function. + * + * 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 writeMatchingGraphsPlotsTCP(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j) +{ + fprintf(stream, + "\t\"matching_tcp-%1$03d_to_%2$03d.data\" " + "title \"Sent messages\" with points linetype 4 " + "linecolor rgb \"#98fc66\" pointtype 9 pointsize 2, \\\n" + "\t\"matching_tcp-%2$03d_to_%1$03d.data\" " + "title \"Received messages\" with points linetype 4 " + "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i, j); + + if (syncState->analysisModule->writeAnalysisGraphsPlots != NULL) + { + syncState->analysisModule->writeAnalysisGraphsPlots(stream, syncState, + i, j); + } +} + + +/* + * Write the matching-specific options in the gnuplot script (none). Call the + * downstream module's options function. + * + * 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 writeMatchingGraphsOptionsTCP(FILE* stream, SyncState* const + syncState, const unsigned int i, const unsigned int j) +{ + if (syncState->analysisModule->writeAnalysisGraphsOptions != NULL) + { + syncState->analysisModule->writeAnalysisGraphsOptions(stream, + syncState, i, j); + } +} diff --git a/lttv/lttv/sync/event_matching_tcp.h b/lttv/lttv/sync/event_matching_tcp.h index 19da807a..f0ce6225 100644 --- a/lttv/lttv/sync/event_matching_tcp.h +++ b/lttv/lttv/sync/event_matching_tcp.h @@ -26,10 +26,16 @@ typedef struct { - int totPacket, + unsigned int totPacket, totPacketNeedAck, totExchangeEffective, totExchangeSync; + /* The structure of the array is the same as for hullArray in + * analysis_chull, messagePoints[row][col] where: + * row= inE->traceNum + * col= outE->traceNum + */ + unsigned int** totMessageArray; } MatchingStatsTCP; typedef struct @@ -42,6 +48,16 @@ typedef struct GHashTable* unAcked; MatchingStatsTCP* stats; + /* This array is used for graphs. It contains file pointers to files where + * messages x-y points are outputed. Each trace-pair has two files, one + * for each message direction. The structure of the array is the same as + * for hullArray in analysis_chull, messagePoints[row][col] where: + * row= inE->traceNum + * col= outE->traceNum + * + * The elements on the diagonal are not initialized. + */ + FILE*** messagePoints; } MatchingDataTCP; #endif diff --git a/lttv/lttv/sync/event_processing.h b/lttv/lttv/sync/event_processing.h index bbaae74c..6e8c3799 100644 --- a/lttv/lttv/sync/event_processing.h +++ b/lttv/lttv/sync/event_processing.h @@ -20,6 +20,7 @@ #define EVENT_PROCESSING_H #include +#include #include @@ -37,7 +38,17 @@ typedef struct void (*destroyProcessing)(struct _SyncState* const syncState); void (*finalizeProcessing)(struct _SyncState* const syncState); + void (*printProcessingStats)(struct _SyncState* const syncState); + + /* The processing module must provide the next function if it wishes + * graphs to be created at all. If it provides the next function, it must + * also provide the second next function. + */ + void (*writeProcessingGraphsPlots)(FILE* stream, struct _SyncState* const + syncState, const unsigned int i, const unsigned int j); + void (*writeProcessingGraphsOptions)(FILE* stream, struct _SyncState* + const syncState, const unsigned int i, const unsigned int j); } ProcessingModule; #endif diff --git a/lttv/lttv/sync/event_processing_lttv_common.c b/lttv/lttv/sync/event_processing_lttv_common.c index e225db71..b0d26c9e 100644 --- a/lttv/lttv/sync/event_processing_lttv_common.c +++ b/lttv/lttv/sync/event_processing_lttv_common.c @@ -23,52 +23,11 @@ #include "event_processing_lttv_common.h" -/* This compound literal is #define'd in order to be able to "assign" it and - * 'sizeof()' it - */ -#define EVENT_HOOK_INFO_LIST ((EventHookInfo[]) {\ - {\ - .channelName= LTT_CHANNEL_NET,\ - .eventName= LTT_EVENT_DEV_XMIT,\ - .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_NETWORK_PROTOCOL,\ - LTT_FIELD_TRANSPORT_PROTOCOL, LTT_FIELD_SADDR,\ - LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL,\ - LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ,\ - LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK,\ - LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN),\ - }, {\ - .channelName= LTT_CHANNEL_NET,\ - .eventName= LTT_EVENT_DEV_RECEIVE,\ - .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_PROTOCOL),\ - }, {\ - .channelName= LTT_CHANNEL_NET,\ - .eventName= LTT_EVENT_TCPV4_RCV,\ - .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR,\ - LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL,\ - LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ,\ - LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK,\ - LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN),\ - }, {\ - .channelName= LTT_CHANNEL_NETIF_STATE,\ - .eventName= LTT_EVENT_NETWORK_IPV4_INTERFACE,\ - .fields= FIELD_ARRAY(LTT_FIELD_NAME, LTT_FIELD_ADDRESS,\ - LTT_FIELD_UP),\ - }\ -}) - #ifndef g_info #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) #endif -typedef struct -{ - GQuark channelName; - GQuark eventName; - GQuark* fields; -} EventHookInfo; - - /* * Initialize the GQuarks needed to register the event hooks for * synchronization @@ -115,17 +74,51 @@ void createQuarks() * r328) * * Args: + * hookListList: LttvTraceHook hookListList[traceNum][hookNum] + * traceSetContext: LTTV traceset + * hookFunction: call back function when event is encountered + * hookData: data that will be made accessible to hookFunction in + * arg0->hook_data */ void registerHooks(GArray* hookListList, LttvTracesetContext* const - traceSetContext, unsigned int traceNb, LttvHook hookFunction, gpointer - hookData) + traceSetContext, LttvHook hookFunction, gpointer hookData) { unsigned int i, j, k; - unsigned int hookNb; - EventHookInfo* eventHookInfoList; - - eventHookInfoList= EVENT_HOOK_INFO_LIST; - hookNb= sizeof(EVENT_HOOK_INFO_LIST) / sizeof(EventHookInfo); + unsigned int traceNb= lttv_traceset_number(traceSetContext->ts); + struct { + GQuark channelName; + GQuark eventName; + GQuark* fields; + } eventHookInfoList[] = { + { + .channelName= LTT_CHANNEL_NET, + .eventName= LTT_EVENT_DEV_XMIT, + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_NETWORK_PROTOCOL, + LTT_FIELD_TRANSPORT_PROTOCOL, LTT_FIELD_SADDR, + LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL, + LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ, + LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK, + LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN), + }, { + .channelName= LTT_CHANNEL_NET, + .eventName= LTT_EVENT_DEV_RECEIVE, + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_PROTOCOL), + }, { + .channelName= LTT_CHANNEL_NET, + .eventName= LTT_EVENT_TCPV4_RCV, + .fields= FIELD_ARRAY(LTT_FIELD_SKB, LTT_FIELD_SADDR, + LTT_FIELD_DADDR, LTT_FIELD_TOT_LEN, LTT_FIELD_IHL, + LTT_FIELD_SOURCE, LTT_FIELD_DEST, LTT_FIELD_SEQ, + LTT_FIELD_ACK_SEQ, LTT_FIELD_DOFF, LTT_FIELD_ACK, + LTT_FIELD_RST, LTT_FIELD_SYN, LTT_FIELD_FIN), + }, { + .channelName= LTT_CHANNEL_NETIF_STATE, + .eventName= LTT_EVENT_NETWORK_IPV4_INTERFACE, + .fields= FIELD_ARRAY(LTT_FIELD_NAME, LTT_FIELD_ADDRESS, + LTT_FIELD_UP), + } + }; // This is called a compound literal + unsigned int hookNb= sizeof(eventHookInfoList) / sizeof(*eventHookInfoList); for(i= 0; i < traceNb; i++) { @@ -177,7 +170,7 @@ void registerHooks(GArray* hookListList, LttvTracesetContext* const } if (traceHook->mdata == tfc->tf->mdata) { - lttv_hooks_add(lttv_hooks_by_id_find( tfc->event_by_id, + lttv_hooks_add(lttv_hooks_by_id_find(tfc->event_by_id, traceHook->id), traceHook->h, traceHook, LTTV_PRIO_DEFAULT); } @@ -192,12 +185,12 @@ void registerHooks(GArray* hookListList, LttvTracesetContext* const * Args: * hookListList: LttvTraceHook hookListList[traceNum][hookNum] * traceSetContext: LTTV traceset - * traceNb: number of traces in the traceset */ void unregisterHooks(GArray* hookListList, LttvTracesetContext* const - traceSetContext, unsigned int traceNb) + traceSetContext) { unsigned int i, j, k; + unsigned int traceNb= lttv_traceset_number(traceSetContext->ts); for(i= 0; i < traceNb; i++) { diff --git a/lttv/lttv/sync/event_processing_lttv_common.h b/lttv/lttv/sync/event_processing_lttv_common.h index 31c2a649..aa34cfcc 100644 --- a/lttv/lttv/sync/event_processing_lttv_common.h +++ b/lttv/lttv/sync/event_processing_lttv_common.h @@ -16,8 +16,8 @@ * MA 02111-1307, USA. */ -#ifndef EVENT_PROCESSING_LTTV_COMMON_H -#define EVENT_PROCESSING_LTTV_COMMON_H +#ifndef EVENT_PROCESSING_LTTNG_COMMON_H +#define EVENT_PROCESSING_LTTNG_COMMON_H #include @@ -59,9 +59,9 @@ GQuark void createQuarks(); void registerHooks(GArray* hookListList, LttvTracesetContext* const - traceSetContext, unsigned int traceNb, LttvHook hookFunction, gpointer + traceSetContext, LttvHook hookFunction, gpointer hookData); void unregisterHooks(GArray* hookListList, LttvTracesetContext* const - traceSetContext, unsigned int traceNb); + traceSetContext); #endif diff --git a/lttv/lttv/sync/event_processing_lttv_null.c b/lttv/lttv/sync/event_processing_lttv_null.c index 2229bc10..678e3c34 100644 --- a/lttv/lttv/sync/event_processing_lttv_null.c +++ b/lttv/lttv/sync/event_processing_lttv_null.c @@ -33,7 +33,7 @@ #endif -// Functions common to all matching modules +// Functions common to all processing modules static void initProcessingLTTVNull(SyncState* const syncState, LttvTracesetContext* const traceSetContext); static void destroyProcessingLTTVNull(SyncState* const syncState); @@ -51,6 +51,8 @@ static ProcessingModule processingModuleLTTVNull = { .destroyProcessing= &destroyProcessingLTTVNull, .finalizeProcessing= &finalizeProcessingLTTVNull, .printProcessingStats= NULL, + .writeProcessingGraphsPlots= NULL, + .writeProcessingGraphsOptions= NULL, }; @@ -89,7 +91,7 @@ static void initProcessingLTTVNull(SyncState* const syncState, sizeof(GArray*), syncState->traceNb); registerHooks(processingData->hookListList, traceSetContext, - syncState->traceNb, &processEventLTTVNull, syncState); + &processEventLTTVNull, syncState); } @@ -125,7 +127,7 @@ static void destroyProcessingLTTVNull(SyncState* const syncState) } unregisterHooks(processingData->hookListList, - processingData->traceSetContext, syncState->traceNb); + processingData->traceSetContext); free(syncState->processingData); syncState->processingData= NULL; diff --git a/lttv/lttv/sync/event_processing_lttv_standard.c b/lttv/lttv/sync/event_processing_lttv_standard.c index f67ab107..b981d3a8 100644 --- a/lttv/lttv/sync/event_processing_lttv_standard.c +++ b/lttv/lttv/sync/event_processing_lttv_standard.c @@ -39,13 +39,17 @@ #endif -// Functions common to all matching modules +// Functions common to all processing modules static void initProcessingLTTVStandard(SyncState* const syncState, LttvTracesetContext* const traceSetContext); static void destroyProcessingLTTVStandard(SyncState* const syncState); static void finalizeProcessingLTTVStandard(SyncState* const syncState); static void printProcessingStatsLTTVStandard(SyncState* const syncState); +static void writeProcessingGraphsPlotsLTTVStandard(FILE* stream, SyncState* + const syncState, const unsigned int i, const unsigned int j); +static void writeProcessingGraphsOptionsLTTVStandard(FILE* stream, SyncState* + const syncState, const unsigned int i, const unsigned int j); // Functions specific to this module static void registerProcessingLTTVStandard() __attribute__((constructor (102))); @@ -59,6 +63,8 @@ static ProcessingModule processingModuleLTTVStandard = { .destroyProcessing= &destroyProcessingLTTVStandard, .finalizeProcessing= &finalizeProcessingLTTVStandard, .printProcessingStats= &printProcessingStatsLTTVStandard, + .writeProcessingGraphsPlots= &writeProcessingGraphsPlotsLTTVStandard, + .writeProcessingGraphsOptions= &writeProcessingGraphsOptionsLTTVStandard, }; @@ -125,7 +131,7 @@ static void initProcessingLTTVStandard(SyncState* const syncState, LttvTracesetC } registerHooks(processingData->hookListList, traceSetContext, - syncState->traceNb, &processEventLTTVStandard, syncState); + &processEventLTTVStandard, syncState); } @@ -333,7 +339,7 @@ static void partialDestroyProcessingLTTVStandard(SyncState* const syncState) free(processingData->pendingRecv); unregisterHooks(processingData->hookListList, - processingData->traceSetContext, syncState->traceNb); + processingData->traceSetContext); } @@ -559,3 +565,62 @@ static gboolean processEventLTTVStandard(void* hookData, void* callData) return FALSE; } + + +/* + * Write the processing-specific graph lines in the gnuplot script (none at + * the moment). Call the downstream module's graph function. + * + * 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 writeProcessingGraphsPlotsLTTVStandard(FILE* stream, SyncState* + const syncState, const unsigned int i, const unsigned int j) +{ + if (syncState->matchingModule->writeMatchingGraphsPlots != NULL) + { + syncState->matchingModule->writeMatchingGraphsPlots(stream, syncState, + i, j); + } +} + + +/* + * Write the processing-specific options in the gnuplot script. Call the + * downstream module's options function. + * + * 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 writeProcessingGraphsOptionsLTTVStandard(FILE* stream, SyncState* + const syncState, const unsigned int i, const unsigned int j) +{ + ProcessingDataLTTVStandard* processingData; + LttTrace* traceI, * traceJ; + + processingData= (ProcessingDataLTTVStandard*) syncState->processingData; + + traceI= processingData->traceSetContext->traces[i]->t; + traceJ= processingData->traceSetContext->traces[j]->t; + + fprintf(stream, + "set x2label \"Clock %1$d (s)\"\n" + "set x2range [GPVAL_X_MIN / %2$.1f : GPVAL_X_MAX / %2$.1f]\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->start_freq / traceI->freq_scale, + j, (double) traceJ->start_freq / traceJ->freq_scale); + + if (syncState->matchingModule->writeMatchingGraphsOptions != NULL) + { + syncState->matchingModule->writeMatchingGraphsOptions(stream, + syncState, i, j); + } +} diff --git a/lttv/lttv/sync/sync_chain.c b/lttv/lttv/sync/sync_chain.c index 210be504..52e0bb9d 100644 --- a/lttv/lttv/sync/sync_chain.c +++ b/lttv/lttv/sync/sync_chain.c @@ -20,9 +20,16 @@ #include #endif +#include +#include +#include #include -#include #include +#include +#include +#include +#include +#include #include #include @@ -39,6 +46,7 @@ static void init(); static void destroy(); static void timeDiff(struct timeval* const end, const struct timeval* const start); + static gint gcfCompareAnalysis(gconstpointer a, gconstpointer b); static gint gcfCompareProcessing(gconstpointer a, gconstpointer b); static void gfAppendAnalysisName(gpointer data, gpointer user_data); @@ -47,6 +55,9 @@ static gboolean optionSync; static gboolean optionSyncStats; static gboolean optionSyncNull; static char* optionSyncAnalysis; +static gboolean optionSyncGraphs; +static char* optionSyncGraphsDir; +static char graphsDir[20]; GQueue processingModules= G_QUEUE_INIT; GQueue matchingModules= G_QUEUE_INIT; @@ -67,6 +78,7 @@ GQueue analysisModules= G_QUEUE_INIT; static void init() { GString* analysisModulesNames; + int retval; g_debug("\t\t\tXXXX sync init\n"); @@ -95,6 +107,21 @@ static void init() "event analysis" , analysisModulesNames->str, LTTV_OPT_STRING, &optionSyncAnalysis, NULL, NULL); g_string_free(analysisModulesNames, TRUE); + + optionSyncGraphs= FALSE; + lttv_option_add("sync-graphs", '\0', "output gnuplot graph showing " + "synchronization points", "none", LTTV_OPT_NONE, &optionSyncGraphs, + NULL, NULL); + + retval= snprintf(graphsDir, sizeof(graphsDir), "graphs-%d", getpid()); + if (retval > sizeof(graphsDir) - 1) + { + graphsDir[sizeof(graphsDir) - 1]= '\0'; + } + optionSyncGraphsDir= graphsDir; + lttv_option_add("sync-graphs-dir", '\0', "specify the directory where to" + " store the graphs", graphsDir, LTTV_OPT_STRING, &optionSyncGraphsDir, + NULL, NULL); } @@ -109,6 +136,8 @@ static void destroy() lttv_option_remove("sync-stats"); lttv_option_remove("sync-null"); lttv_option_remove("sync-analysis"); + lttv_option_remove("sync-graphs"); + lttv_option_remove("sync-graphs-dir"); } @@ -126,6 +155,9 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) struct timeval startTime, endTime; struct rusage startUsage, endUsage; GList* result; + char* cwd; + FILE* graphsStream; + int graphsFp; int retval; if (optionSync == FALSE) @@ -153,6 +185,16 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) syncState->stats= false; } + if (optionSyncGraphs) + { + syncState->graphs= optionSyncGraphsDir; + } + else + { + syncState->graphs= NULL; + } + + // Identify and initialize processing module syncState->processingData= NULL; if (optionSyncNull) { @@ -166,8 +208,39 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) } g_assert(result != NULL); syncState->processingModule= (ProcessingModule*) result->data; + + graphsStream= NULL; + if (syncState->graphs) + { + // Create the graph directory right away in case the module initialization + // functions have something to write in it. + cwd= changeToGraphDir(syncState->graphs); + + if (syncState->processingModule->writeProcessingGraphsPlots != NULL) + { + if ((graphsFp= open("graphs.gnu", O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | + S_IWUSR | S_IXUSR | S_IRGRP | S_IWGRP | S_IXGRP | S_IROTH + | S_IWOTH | S_IXOTH)) == -1) + { + g_error(strerror(errno)); + } + if ((graphsStream= fdopen(graphsFp, "w")) == NULL) + { + g_error(strerror(errno)); + } + } + + retval= chdir(cwd); + if (retval == -1) + { + g_error(strerror(errno)); + } + free(cwd); + } + syncState->processingModule->initProcessing(syncState, traceSetContext); + // Identify and initialize matching and analysis modules syncState->matchingData= NULL; syncState->analysisData= NULL; if (optionSyncNull) @@ -203,6 +276,64 @@ void syncTraceset(LttvTracesetContext* const traceSetContext) syncState->processingModule->finalizeProcessing(syncState); + // Write graphs file + if (graphsStream != NULL) + { + unsigned int i, j; + + fprintf(graphsStream, + "#!/usr/bin/gnuplot\n\n" + "set terminal postscript eps color size 8in,6in\n"); + + // Cover the upper triangular matrix, i is the reference node. + for (i= 0; i < syncState->traceNb; i++) + { + for (j= i + 1; j < syncState->traceNb; j++) + { + long pos; + + fprintf(graphsStream, + "\nset output \"%03d-%03d.eps\"\n" + "plot \\\n", i, j); + + syncState->processingModule->writeProcessingGraphsPlots(graphsStream, + syncState, i, j); + + // Remove the ", \\\n" from the last graph plot line + fflush(graphsStream); + pos= ftell(graphsStream); + if (ftruncate(fileno(graphsStream), pos - 4) == -1) + { + g_error(strerror(errno)); + } + if (fseek(graphsStream, 0, SEEK_END) == -1) + { + g_error(strerror(errno)); + } + + fprintf(graphsStream, + "\nset output \"%1$03d-%2$03d.eps\"\n" + "set key inside right bottom\n" + "set title \"\"\n" + "set xlabel \"Clock %1$u\"\n" + "set xtics nomirror\n" + "set ylabel \"Clock %2$u\"\n" + "set ytics nomirror\n", i, j); + + syncState->processingModule->writeProcessingGraphsOptions(graphsStream, + syncState, i, j); + + fprintf(graphsStream, + "replot\n"); + } + } + + if (fclose(graphsStream) != 0) + { + g_error(strerror(errno)); + } + } + if (syncState->processingModule->printProcessingStats != NULL) { syncState->processingModule->printProcessingStats(syncState); @@ -323,7 +454,47 @@ static void gfAppendAnalysisName(gpointer data, gpointer user_data) } +/* + * Change to the directory used to hold graphs. Create it if necessary. + * + * Args: + * graph: name of directory + * + * Returns: + * The current working directory before the execution of the function. The + * string must be free'd by the caller. + */ +char* changeToGraphDir(char* const graphs) +{ + int retval; + char* cwd; + + cwd= getcwd(NULL, 0); + if (cwd == NULL) + { + g_error(strerror(errno)); + } + while ((retval= chdir(graphs)) != 0) + { + if (errno == ENOENT) + { + retval= mkdir(graphs, S_IRUSR | S_IWUSR | S_IXUSR | S_IRGRP | + S_IWGRP | S_IXGRP | S_IROTH | S_IWOTH | S_IXOTH); + if (retval != 0) + { + g_error(strerror(errno)); + } + } + else + { + g_error(strerror(errno)); + } + } + + return cwd; +} + + LTTV_MODULE("sync", "Synchronize traces", \ "Synchronizes a traceset based on the correspondance of network events", \ init, destroy, "option") - diff --git a/lttv/lttv/sync/sync_chain.h b/lttv/lttv/sync/sync_chain.h index 9515c6e5..152d1321 100644 --- a/lttv/lttv/sync/sync_chain.h +++ b/lttv/lttv/sync/sync_chain.h @@ -29,6 +29,7 @@ typedef struct _SyncState { unsigned int traceNb; bool stats; + char* graphs; const ProcessingModule* processingModule; void* processingData; @@ -45,4 +46,6 @@ extern GQueue analysisModules; void syncTraceset(LttvTracesetContext* const traceSetContext); +char* changeToGraphDir(char* const graphs); + #endif -- 2.34.1