1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License Version 2 as
6 * published by the Free Software Foundation;
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20 #define _ISOC99_SOURCE
26 #include <arpa/inet.h>
29 #include <netinet/in.h>
34 #include <sys/socket.h>
38 #include "sync_chain.h"
39 #include "event_analysis_chull.h"
41 #include "event_analysis_eval.h"
44 struct WriteHistogramInfo
55 GArray
* iArray
, * jArray
, * aArray
;
59 // Functions common to all analysis modules
60 static void initAnalysisEval(SyncState
* const syncState
);
61 static void destroyAnalysisEval(SyncState
* const syncState
);
63 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
65 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
67 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
69 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
);
70 static void printAnalysisStatsEval(SyncState
* const syncState
);
71 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
72 const unsigned int i
, const unsigned int j
);
73 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
74 const unsigned int i
, const unsigned int j
);
75 static void writeAnalysisTraceTraceBackPlotsEval(SyncState
* const syncState
,
76 const unsigned int i
, const unsigned int j
);
77 static void writeAnalysisTraceTraceForePlotsEval(SyncState
* const syncState
,
78 const unsigned int i
, const unsigned int j
);
80 // Functions specific to this module
81 static void registerAnalysisEval() __attribute__((constructor (102)));
82 static guint
ghfRttKeyHash(gconstpointer key
);
83 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
);
84 static void gdnDestroyRttKey(gpointer data
);
85 static void gdnDestroyDouble(gpointer data
);
86 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttFile
);
87 static void positionStream(FILE* stream
);
89 static void gfSum(gpointer data
, gpointer userData
);
90 static void gfSumSquares(gpointer data
, gpointer userData
);
91 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
94 static void hitBin(struct Bins
* const bins
, const double value
);
95 static unsigned int binNum(const double value
) __attribute__((pure
));
96 static double binStart(const unsigned int binNum
) __attribute__((pure
));
97 static double binEnd(const unsigned int binNum
) __attribute__((pure
));
98 static uint32_t normalTotal(struct Bins
* const bins
) __attribute__((const));
100 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
101 graphsDir
, const struct RttKey
* const rttKey
);
102 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
104 static void gdnDestroyAnalysisHistogramEval(gpointer data
);
105 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer
107 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
);
108 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
109 double* minRtt
, AnalysisHistogramEval
* const histogram
);
111 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
114 // The next group of functions is only needed when computing synchronization
117 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
119 static void gfLPAddRow(gpointer data
, gpointer user_data
);
120 static Factors
* calculateFactors(glp_prob
* const lp
, const int direction
);
121 static void calculateCompleteFactors(glp_prob
* const lp
, FactorsCHull
*
123 static FactorsCHull
** createAllFactors(const unsigned int traceNb
);
124 static inline void finalizeAnalysisEvalLP(SyncState
* const syncState
);
126 static void finalizeAnalysisEvalLP(SyncState
* const syncState
);
130 // initialized in registerAnalysisEval()
133 static AnalysisModule analysisModuleEval
= {
135 .initAnalysis
= &initAnalysisEval
,
136 .destroyAnalysis
= &destroyAnalysisEval
,
137 .analyzeMessage
= &analyzeMessageEval
,
138 .analyzeExchange
= &analyzeExchangeEval
,
139 .analyzeBroadcast
= &analyzeBroadcastEval
,
140 .finalizeAnalysis
= &finalizeAnalysisEval
,
141 .printAnalysisStats
= &printAnalysisStatsEval
,
143 .writeTraceTimeBackPlots
= &writeAnalysisTraceTimeBackPlotsEval
,
144 .writeTraceTimeForePlots
= &writeAnalysisTraceTimeForePlotsEval
,
145 .writeTraceTraceBackPlots
= &writeAnalysisTraceTraceBackPlotsEval
,
146 .writeTraceTraceForePlots
= &writeAnalysisTraceTraceForePlotsEval
,
150 static ModuleOption optionEvalRttFile
= {
151 .longName
= "eval-rtt-file",
152 .hasArg
= REQUIRED_ARG
,
153 .optionHelp
= "specify the file containing RTT information",
159 * Analysis module registering function
161 static void registerAnalysisEval()
163 binBase
= exp10(6. / (BIN_NB
- 3));
165 g_queue_push_tail(&analysisModules
, &analysisModuleEval
);
166 g_queue_push_tail(&moduleOptions
, &optionEvalRttFile
);
171 * Analysis init function
173 * This function is called at the beginning of a synchronization run for a set
177 * syncState container for synchronization data.
179 static void initAnalysisEval(SyncState
* const syncState
)
181 AnalysisDataEval
* analysisData
;
184 analysisData
= malloc(sizeof(AnalysisDataEval
));
185 syncState
->analysisData
= analysisData
;
187 analysisData
->rttInfo
= g_hash_table_new_full(&ghfRttKeyHash
,
188 &gefRttKeyEqual
, &gdnDestroyRttKey
, &gdnDestroyDouble
);
189 if (optionEvalRttFile
.arg
)
194 rttStream
= fopen(optionEvalRttFile
.arg
, "r");
195 if (rttStream
== NULL
)
197 g_error(strerror(errno
));
200 readRttInfo(analysisData
->rttInfo
, rttStream
);
202 retval
= fclose(rttStream
);
205 g_error(strerror(errno
));
209 if (syncState
->stats
)
211 analysisData
->stats
= calloc(1, sizeof(AnalysisStatsEval
));
212 analysisData
->stats
->broadcastDiffSum
= 0.;
214 analysisData
->stats
->messageStats
= malloc(syncState
->traceNb
*
215 sizeof(MessageStats
*));
216 for (i
= 0; i
< syncState
->traceNb
; i
++)
218 analysisData
->stats
->messageStats
[i
]= calloc(syncState
->traceNb
,
219 sizeof(MessageStats
));
222 analysisData
->stats
->exchangeRtt
=
223 g_hash_table_new_full(&ghfRttKeyHash
, &gefRttKeyEqual
,
224 &gdnDestroyRttKey
, &gdnDestroyDouble
);
227 analysisData
->stats
->chFactorsArray
= NULL
;
228 analysisData
->stats
->lpFactorsArray
= NULL
;
232 if (syncState
->graphsStream
)
234 AnalysisGraphsEval
* graphs
= malloc(sizeof(AnalysisGraphsEval
));
236 analysisData
->graphs
= graphs
;
238 graphs
->histograms
= g_hash_table_new_full(&ghfRttKeyHash
,
239 &gefRttKeyEqual
, &gdnDestroyRttKey
,
240 &gdnDestroyAnalysisHistogramEval
);
242 graphs
->bounds
= malloc(syncState
->traceNb
* sizeof(Bounds
*));
243 for (i
= 0; i
< syncState
->traceNb
; i
++)
245 graphs
->bounds
[i
]= malloc(i
* sizeof(Bounds
));
246 for (j
= 0; j
< i
; j
++)
248 graphs
->bounds
[i
][j
].min
= UINT64_MAX
;
249 graphs
->bounds
[i
][j
].max
= 0;
255 graphs
->lpFactorsArray
= NULL
;
259 if (syncState
->stats
|| syncState
->graphsStream
)
263 analysisData
->chullSS
= malloc(sizeof(SyncState
));
264 memcpy(analysisData
->chullSS
, syncState
, sizeof(SyncState
));
265 analysisData
->chullSS
->stats
= false;
266 analysisData
->chullSS
->analysisData
= NULL
;
267 result
= g_queue_find_custom(&analysisModules
, "chull",
268 &gcfCompareAnalysis
);
269 analysisData
->chullSS
->analysisModule
= (AnalysisModule
*) result
->data
;
270 analysisData
->chullSS
->analysisModule
->initAnalysis(analysisData
->chullSS
);
276 * Create and open files used to store histogram points to generate graphs.
277 * Create data structures to store histogram points during analysis.
280 * graphsDir: folder where to write files
281 * rttKey: host pair, make sure saddr < daddr
283 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
284 graphsDir
, const struct RttKey
* const rttKey
)
289 char name
[60], saddr
[16], daddr
[16];
290 AnalysisHistogramEval
* histogram
= calloc(1, sizeof(*histogram
));
293 const char* fileName
;
294 const char* host1
, *host2
;
296 {offsetof(AnalysisHistogramEval
, ttSendPoints
),
297 "analysis_eval_tt-%s_to_%s.data", saddr
, daddr
},
298 {offsetof(AnalysisHistogramEval
, ttRecvPoints
),
299 "analysis_eval_tt-%s_to_%s.data", daddr
, saddr
},
300 {offsetof(AnalysisHistogramEval
, hrttPoints
),
301 "analysis_eval_hrtt-%s_and_%s.data", saddr
, daddr
},
304 histogram
->ttSendBins
.min
= BIN_NB
- 1;
305 histogram
->ttRecvBins
.min
= BIN_NB
- 1;
306 histogram
->hrttBins
.min
= BIN_NB
- 1;
308 convertIP(saddr
, rttKey
->saddr
);
309 convertIP(daddr
, rttKey
->daddr
);
311 cwd
= changeToGraphsDir(graphsDir
);
313 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
315 retval
= snprintf(name
, sizeof(name
), loopValues
[i
].fileName
,
316 loopValues
[i
].host1
, loopValues
[i
].host2
);
317 if (retval
> sizeof(name
) - 1)
319 name
[sizeof(name
) - 1]= '\0';
321 if ((*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
)=
322 fopen(name
, "w")) == NULL
)
324 g_error(strerror(errno
));
331 g_error(strerror(errno
));
340 * Close files used to store histogram points to generate graphs.
343 * graphsDir: folder where to write files
344 * rttKey: host pair, make sure saddr < daddr
346 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
354 {offsetof(AnalysisHistogramEval
, ttSendPoints
)},
355 {offsetof(AnalysisHistogramEval
, ttRecvPoints
)},
356 {offsetof(AnalysisHistogramEval
, hrttPoints
)},
359 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
361 retval
= fclose(*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
));
364 g_error(strerror(errno
));
373 * A GDestroyNotify function for g_hash_table_new_full()
376 * data: AnalysisHistogramEval*
378 static void gdnDestroyAnalysisHistogramEval(gpointer data
)
380 destroyAnalysisHistogramEval(data
);
385 * A GHFunc for g_hash_table_foreach()
388 * key: RttKey* where saddr < daddr
389 * value: AnalysisHistogramEval*
390 * user_data struct WriteHistogramInfo*
392 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer user_data
)
394 double* rtt1
, * rtt2
;
395 struct RttKey
* rttKey
= key
;
396 struct RttKey oppositeRttKey
= {.saddr
= rttKey
->daddr
, .daddr
=
398 AnalysisHistogramEval
* histogram
= value
;
399 struct WriteHistogramInfo
* info
= user_data
;
401 rtt1
= g_hash_table_lookup(info
->rttInfo
, rttKey
);
402 rtt2
= g_hash_table_lookup(info
->rttInfo
, &oppositeRttKey
);
408 else if (rtt2
!= NULL
)
410 rtt1
= MIN(rtt1
, rtt2
);
413 dumpBinToFile(&histogram
->ttSendBins
, histogram
->ttSendPoints
);
414 dumpBinToFile(&histogram
->ttRecvBins
, histogram
->ttRecvPoints
);
415 dumpBinToFile(&histogram
->hrttBins
, histogram
->hrttPoints
);
416 writeHistogram(info
->graphsStream
, rttKey
, rtt1
, histogram
);
421 * Write the content of one bin in a histogram point file
424 * bin: array of values that make up a histogram
425 * file: FILE*, write to this file
427 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
)
431 // The first and last bins are skipped, see struct Bins
432 for (i
= 1; i
< BIN_NB
- 1; i
++)
434 if (bins
->bin
[i
] > 0)
436 fprintf(file
, "%20.9f %20.9f %20.9f\n", (binStart(i
) + binEnd(i
))
437 / 2., (double) bins
->bin
[i
] / ((binEnd(i
) - binStart(i
)) *
438 bins
->total
), binEnd(i
) - binStart(i
));
445 * Write the analysis-specific plot in the gnuplot script.
448 * graphsStream: write to this file
449 * rttKey: must be sorted such that saddr < daddr
450 * minRtt: if available, else NULL
451 * histogram: struct that contains the bins for the pair of traces
452 * identified by rttKey
454 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
455 double* minRtt
, AnalysisHistogramEval
* const histogram
)
457 char saddr
[16], daddr
[16];
459 convertIP(saddr
, rttKey
->saddr
);
460 convertIP(daddr
, rttKey
->daddr
);
462 fprintf(graphsStream
,
464 "set output \"histogram-%s-%s.eps\"\n"
466 "set xlabel \"Message Latency (s)\"\n"
467 "set ylabel \"Proportion of messages per second\"\n", saddr
, daddr
);
471 fprintf(graphsStream
,
472 "set arrow from %.9f, 0 rto 0, graph 1 "
473 "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
477 if (normalTotal(&histogram
->ttSendBins
) ||
478 normalTotal(&histogram
->ttRecvBins
) ||
479 normalTotal(&histogram
->hrttBins
))
481 fprintf(graphsStream
, "plot \\\n");
483 if (normalTotal(&histogram
->hrttBins
))
485 fprintf(graphsStream
,
486 "\t\"analysis_eval_hrtt-%s_and_%s.data\" "
487 "title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
488 "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
492 if (normalTotal(&histogram
->ttSendBins
))
494 fprintf(graphsStream
,
495 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
496 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
497 "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
501 if (normalTotal(&histogram
->ttRecvBins
))
503 fprintf(graphsStream
,
504 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
505 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
506 "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
510 // Remove the ",\\\n" from the last graph plot line
511 if (ftruncate(fileno(graphsStream
), ftell(graphsStream
) - 3) == -1)
513 g_error(strerror(errno
));
515 if (fseek(graphsStream
, 0, SEEK_END
) == -1)
517 g_error(strerror(errno
));
519 fprintf(graphsStream
, "\n");
525 * Analysis destroy function
527 * Free the analysis specific data structures
530 * syncState container for synchronization data.
532 static void destroyAnalysisEval(SyncState
* const syncState
)
535 AnalysisDataEval
* analysisData
;
537 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
539 if (analysisData
== NULL
)
544 g_hash_table_destroy(analysisData
->rttInfo
);
546 if (syncState
->stats
)
548 AnalysisStatsEval
* stats
= analysisData
->stats
;
550 for (i
= 0; i
< syncState
->traceNb
; i
++)
552 free(stats
->messageStats
[i
]);
554 free(stats
->messageStats
);
556 g_hash_table_destroy(stats
->exchangeRtt
);
559 freeAllFactors(syncState
->traceNb
, stats
->chFactorsArray
);
560 freeAllFactors(syncState
->traceNb
, stats
->lpFactorsArray
);
566 if (syncState
->graphsStream
)
568 AnalysisGraphsEval
* graphs
= analysisData
->graphs
;
570 if (graphs
->histograms
)
572 g_hash_table_destroy(graphs
->histograms
);
575 for (i
= 0; i
< syncState
->traceNb
; i
++)
577 free(graphs
->bounds
[i
]);
579 free(graphs
->bounds
);
582 for (i
= 0; i
< syncState
->traceNb
; i
++)
584 for (j
= 0; j
< i
; j
++)
586 // There seems to be a memory leak in glpk, valgrind reports a
587 // loss even if the problem is deleted
588 glp_delete_prob(graphs
->lps
[i
][j
]);
590 free(graphs
->lps
[i
]);
594 if (!syncState
->stats
)
596 freeAllFactors(syncState
->traceNb
, graphs
->lpFactorsArray
);
603 if (syncState
->stats
|| syncState
->graphsStream
)
605 analysisData
->chullSS
->analysisModule
->destroyAnalysis(analysisData
->chullSS
);
606 free(analysisData
->chullSS
);
609 free(syncState
->analysisData
);
610 syncState
->analysisData
= NULL
;
615 * Perform analysis on an event pair.
617 * Check if there is message inversion or messages that are too fast.
620 * syncState container for synchronization data
621 * message structure containing the events
623 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
626 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
627 MessageStats
* messageStats
;
630 struct RttKey rttKey
;
632 g_assert(message
->inE
->type
== TCP
);
634 if (syncState
->stats
)
637 &analysisData
->stats
->messageStats
[message
->outE
->traceNum
][message
->inE
->traceNum
];
638 messageStats
->total
++;
641 tt
= wallTimeSub(&message
->inE
->wallTime
, &message
->outE
->wallTime
);
644 if (syncState
->stats
)
646 messageStats
->inversionNb
++;
649 else if (syncState
->graphsStream
)
651 struct RttKey rttKey
= {
652 .saddr
=MIN(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
653 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
654 .daddr
=MAX(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
655 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
657 AnalysisHistogramEval
* histogram
=
658 g_hash_table_lookup(analysisData
->graphs
->histograms
, &rttKey
);
660 if (histogram
== NULL
)
662 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
664 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
, &rttKey
);
665 memcpy(tableKey
, &rttKey
, sizeof(*tableKey
));
666 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
, histogram
);
669 if (message
->inE
->event
.udpEvent
->datagramKey
->saddr
<
670 message
->inE
->event
.udpEvent
->datagramKey
->daddr
)
672 hitBin(&histogram
->ttSendBins
, tt
);
676 hitBin(&histogram
->ttRecvBins
, tt
);
680 if (syncState
->stats
)
683 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
;
685 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
;
686 rtt
= g_hash_table_lookup(analysisData
->rttInfo
, &rttKey
);
687 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey
.saddr
,
688 rttKey
.daddr
, rtt
? *rtt
: NAN
);
692 g_debug("rttInfo, tt: %f rtt / 2: %f", tt
, *rtt
/ 2.);
695 messageStats
->tooFastNb
++;
700 messageStats
->noRTTInfoNb
++;
704 if (syncState
->graphsStream
)
706 updateBounds(analysisData
->graphs
->bounds
, message
->inE
,
710 if (syncState
->stats
|| syncState
->graphsStream
)
712 analysisData
->chullSS
->analysisModule
->analyzeMessage(analysisData
->chullSS
,
719 * Perform analysis on multiple messages
724 * syncState container for synchronization data
725 * exchange structure containing the messages
727 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
730 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
731 Message
* m1
= g_queue_peek_tail(exchange
->acks
);
732 Message
* m2
= exchange
->message
;
733 struct RttKey
* rttKey
;
734 double* rtt
, * exchangeRtt
;
736 g_assert(m1
->inE
->type
== TCP
);
738 // (T2 - T1) - (T3 - T4)
739 rtt
= malloc(sizeof(double));
740 *rtt
= wallTimeSub(&m1
->inE
->wallTime
, &m1
->outE
->wallTime
) -
741 wallTimeSub(&m2
->outE
->wallTime
, &m2
->inE
->wallTime
);
743 rttKey
= malloc(sizeof(struct RttKey
));
745 MIN(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
746 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
748 MAX(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
749 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
751 if (syncState
->graphsStream
)
753 AnalysisHistogramEval
* histogram
=
754 g_hash_table_lookup(analysisData
->graphs
->histograms
, rttKey
);
756 if (histogram
== NULL
)
758 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
760 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
,
762 memcpy(tableKey
, rttKey
, sizeof(*tableKey
));
763 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
,
767 hitBin(&histogram
->hrttBins
, *rtt
/ 2);
770 if (syncState
->stats
)
772 exchangeRtt
= g_hash_table_lookup(analysisData
->stats
->exchangeRtt
,
777 if (*rtt
< *exchangeRtt
)
779 g_hash_table_replace(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
789 g_hash_table_insert(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
801 * Perform analysis on muliple events
803 * Sum the broadcast differential delays
806 * syncState container for synchronization data
807 * broadcast structure containing the events
809 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
812 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
814 if (syncState
->stats
)
816 double sum
= 0, squaresSum
= 0;
819 g_queue_foreach(broadcast
->events
, &gfSum
, &sum
);
820 g_queue_foreach(broadcast
->events
, &gfSumSquares
, &squaresSum
);
822 analysisData
->stats
->broadcastNb
++;
823 // Because of numerical errors, this can at times be < 0
824 y
= squaresSum
/ g_queue_get_length(broadcast
->events
) - pow(sum
/
825 g_queue_get_length(broadcast
->events
), 2.);
828 analysisData
->stats
->broadcastDiffSum
+= sqrt(y
);
832 if (syncState
->graphsStream
)
836 unsigned int eventNb
= broadcast
->events
->length
;
838 events
= g_array_sized_new(FALSE
, FALSE
, sizeof(Event
*), eventNb
);
839 g_queue_foreach(broadcast
->events
, &gfAddEventToArray
, events
);
841 for (i
= 0; i
< eventNb
; i
++)
843 for (j
= 0; j
< eventNb
; j
++)
845 Event
* eventI
= g_array_index(events
, Event
*, i
), * eventJ
=
846 g_array_index(events
, Event
*, j
);
848 if (eventI
->traceNum
< eventJ
->traceNum
)
850 updateBounds(analysisData
->graphs
->bounds
, eventI
, eventJ
);
855 g_array_free(events
, TRUE
);
861 * Finalize the factor calculations. Since this module does not really
862 * calculate factors, identity factors are returned. Instead, histograms are
863 * written out and histogram structures are freed.
866 * syncState container for synchronization data.
869 * Factors[traceNb] identity factors for each trace
871 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
)
875 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
877 if (syncState
->graphsStream
&& analysisData
->graphs
->histograms
)
879 g_hash_table_foreach(analysisData
->graphs
->histograms
,
880 &ghfWriteHistogram
, &(struct WriteHistogramInfo
) {.rttInfo
=
881 analysisData
->rttInfo
, .graphsStream
= syncState
->graphsStream
});
882 g_hash_table_destroy(analysisData
->graphs
->histograms
);
883 analysisData
->graphs
->histograms
= NULL
;
886 finalizeAnalysisEvalLP(syncState
);
888 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
890 g_array_set_size(factors
, syncState
->traceNb
);
891 for (i
= 0; i
< syncState
->traceNb
; i
++)
895 e
= &g_array_index(factors
, Factors
, i
);
905 * Print statistics related to analysis. Must be called after
909 * syncState container for synchronization data.
911 static void printAnalysisStatsEval(SyncState
* const syncState
)
913 AnalysisDataEval
* analysisData
;
914 unsigned int i
, j
, k
;
915 unsigned int totInversion
= 0, totTooFast
= 0, totNoInfo
= 0, totTotal
= 0;
918 if (!syncState
->stats
)
923 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
925 printf("Synchronization evaluation analysis stats:\n");
926 if (analysisData
->stats
->broadcastNb
)
928 printf("\tsum of broadcast differential delays: %g\n",
929 analysisData
->stats
->broadcastDiffSum
);
930 printf("\taverage broadcast differential delay: %g\n",
931 analysisData
->stats
->broadcastDiffSum
/
932 analysisData
->stats
->broadcastNb
);
935 printf("\tIndividual evaluation:\n"
936 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
938 for (i
= 0; i
< syncState
->traceNb
; i
++)
940 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
942 MessageStats
* messageStats
;
950 for (k
= 0; k
< sizeof(loopValues
) / sizeof(*loopValues
); k
++)
953 &analysisData
->stats
->messageStats
[loopValues
[k
].t1
][loopValues
[k
].t2
];
955 printf("\t\t%3d - %-3d ", loopValues
[k
].t1
, loopValues
[k
].t2
);
956 printf("%u (%u%%)%n", messageStats
->inversionNb
, (unsigned
957 int) ceil((double) messageStats
->inversionNb
/
958 messageStats
->total
* 100), &charNb
);
959 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
960 printf("%u (%u%%)%n", messageStats
->tooFastNb
, (unsigned int)
961 ceil((double) messageStats
->tooFastNb
/
962 messageStats
->total
* 100), &charNb
);
963 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1:
964 1, " ", messageStats
->noRTTInfoNb
, messageStats
->total
);
966 totInversion
+= messageStats
->inversionNb
;
967 totTooFast
+= messageStats
->tooFastNb
;
968 totNoInfo
+= messageStats
->noRTTInfoNb
;
969 totTotal
+= messageStats
->total
;
974 printf("\t\t total ");
975 printf("%u (%u%%)%n", totInversion
, (unsigned int) ceil((double)
976 totInversion
/ totTotal
* 100), &charNb
);
977 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
978 printf("%u (%u%%)%n", totTooFast
, (unsigned int) ceil((double) totTooFast
979 / totTotal
* 100), &charNb
);
980 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ",
981 totNoInfo
, totTotal
);
983 printf("\tRound-trip times:\n"
984 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
985 g_hash_table_foreach(analysisData
->stats
->exchangeRtt
,
986 &ghfPrintExchangeRtt
, analysisData
->rttInfo
);
988 printf("\tConvex hull factors comparisons:\n"
989 "\t\tTrace pair Factors type Differences (lp - chull)\n"
991 "\t\t Min Max Min Max\n");
993 for (i
= 0; i
< syncState
->traceNb
; i
++)
995 for (j
= 0; j
< i
; j
++)
997 FactorsCHull
* chFactors
= &analysisData
->stats
->chFactorsArray
[i
][j
];
998 FactorsCHull
* lpFactors
= &analysisData
->stats
->lpFactorsArray
[i
][j
];
1000 printf("\t\t%3d - %-3d ", i
, j
);
1001 if (lpFactors
->type
== chFactors
->type
)
1003 if (lpFactors
->type
== MIDDLE
)
1005 printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
1006 approxNames
[lpFactors
->type
],
1007 lpFactors
->min
->offset
- chFactors
->min
->offset
,
1008 lpFactors
->max
->offset
- chFactors
->max
->offset
,
1009 lpFactors
->min
->drift
- chFactors
->min
->drift
,
1010 lpFactors
->max
->drift
- chFactors
->max
->drift
);
1012 else if (lpFactors
->type
== ABSENT
)
1014 printf("%s\n", approxNames
[lpFactors
->type
]);
1019 printf("Different! %s and %s\n", approxNames
[lpFactors
->type
],
1020 approxNames
[chFactors
->type
]);
1028 * A GHFunc for g_hash_table_foreach()
1031 * key: RttKey* where saddr < daddr
1032 * value: double*, RTT estimated from exchanges
1033 * user_data GHashTable* rttInfo
1035 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
1038 char addr1
[16], addr2
[16];
1039 struct RttKey
* rttKey1
= key
;
1040 struct RttKey rttKey2
= {rttKey1
->daddr
, rttKey1
->saddr
};
1041 double* fileRtt1
, *fileRtt2
;
1042 GHashTable
* rttInfo
= user_data
;
1044 convertIP(addr1
, rttKey1
->saddr
);
1045 convertIP(addr2
, rttKey1
->daddr
);
1047 fileRtt1
= g_hash_table_lookup(rttInfo
, rttKey1
);
1048 fileRtt2
= g_hash_table_lookup(rttInfo
, &rttKey2
);
1050 printf("\t\t(%15s, %-15s) %-18.3f ", addr1
, addr2
, *(double*) value
* 1e3
);
1052 if (fileRtt1
|| fileRtt2
)
1056 printf("%.3f", *fileRtt1
* 1e3
);
1058 if (fileRtt1
&& fileRtt2
)
1064 printf("%.3f", *fileRtt2
* 1e3
);
1076 * A GHashFunc for g_hash_table_new()
1079 * key struct RttKey*
1081 static guint
ghfRttKeyHash(gconstpointer key
)
1083 struct RttKey
* rttKey
;
1086 rttKey
= (struct RttKey
*) key
;
1098 * A GDestroyNotify function for g_hash_table_new_full()
1101 * data: struct RttKey*
1103 static void gdnDestroyRttKey(gpointer data
)
1110 * A GDestroyNotify function for g_hash_table_new_full()
1115 static void gdnDestroyDouble(gpointer data
)
1122 * A GEqualFunc for g_hash_table_new()
1128 * TRUE if both values are equal
1130 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
)
1132 const struct RttKey
* rkA
, * rkB
;
1134 rkA
= (struct RttKey
*) a
;
1135 rkB
= (struct RttKey
*) b
;
1137 if (rkA
->saddr
== rkB
->saddr
&& rkA
->daddr
== rkB
->daddr
)
1149 * Read a file contain minimum round trip time values and fill an array with
1150 * them. The file is formatted as such:
1151 * <host1 IP> <host2 IP> <RTT in milliseconds>
1152 * ip's should be in dotted quad format
1155 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
1156 * rttStream: stream from which to read
1158 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttStream
)
1164 positionStream(rttStream
);
1165 retval
= getline(&line
, &len
, rttStream
);
1166 while(!feof(rttStream
))
1168 struct RttKey
* rttKey
;
1169 char saddrDQ
[20], daddrDQ
[20];
1172 struct in_addr addr
;
1178 {saddrDQ
, offsetof(struct RttKey
, saddr
)},
1179 {daddrDQ
, offsetof(struct RttKey
, daddr
)}
1182 if (retval
== -1 && !feof(rttStream
))
1184 g_error(strerror(errno
));
1187 if (line
[retval
- 1] == '\n')
1189 line
[retval
- 1]= '\0';
1192 rtt
= malloc(sizeof(double));
1193 retval
= sscanf(line
, " %19s %19s %lf %c", saddrDQ
, daddrDQ
, rtt
,
1197 g_error(strerror(errno
));
1199 else if (retval
!= 3)
1201 g_error("Error parsing RTT file, line was '%s'", line
);
1204 rttKey
= malloc(sizeof(struct RttKey
));
1205 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
1207 retval
= inet_aton(loopValues
[i
].dq
, &addr
);
1210 g_error("Error converting address '%s'", loopValues
[i
].dq
);
1212 *(uint32_t*) ((void*) rttKey
+ loopValues
[i
].offset
)=
1217 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey
->saddr
,
1218 rttKey
->daddr
, *rtt
);
1219 g_hash_table_insert(rttInfo
, rttKey
, rtt
);
1221 positionStream(rttStream
);
1222 retval
= getline(&line
, &len
, rttStream
);
1233 * Advance stream over empty space, empty lines and lines that begin with '#'
1236 * stream: stream, at exit, will be over the first non-empty character
1237 * of a line of be at EOF
1239 static void positionStream(FILE* stream
)
1248 firstChar
= fgetc(stream
);
1249 if (firstChar
== (int) '#')
1251 retval
= getline(&line
, &len
, stream
);
1260 g_error(strerror(errno
));
1264 else if (firstChar
== (int) '\n' || firstChar
== (int) ' ' ||
1265 firstChar
== (int) '\t')
1267 else if (firstChar
== EOF
)
1276 retval
= ungetc(firstChar
, stream
);
1279 g_error("Error: ungetc()");
1291 * A GFunc for g_queue_foreach()
1294 * data Event*, a UDP broadcast event
1295 * user_data double*, the running sum
1298 * Adds the time of the event to the sum
1300 static void gfSum(gpointer data
, gpointer userData
)
1302 Event
* event
= (Event
*) data
;
1304 *(double*) userData
+= event
->wallTime
.seconds
+ event
->wallTime
.nanosec
/
1310 * A GFunc for g_queue_foreach()
1313 * data Event*, a UDP broadcast event
1314 * user_data double*, the running sum
1317 * Adds the square of the time of the event to the sum
1319 static void gfSumSquares(gpointer data
, gpointer userData
)
1321 Event
* event
= (Event
*) data
;
1323 *(double*) userData
+= pow(event
->wallTime
.seconds
+ event
->wallTime
.nanosec
1329 * Update a struct Bins according to a new value
1332 * bins: the structure containing bins to build a histrogram
1333 * value: the new value
1335 static void hitBin(struct Bins
* const bins
, const double value
)
1337 unsigned int binN
= binNum(value
);
1339 if (binN
< bins
->min
)
1343 else if (binN
> bins
->max
)
1355 * Figure out the bin in a histogram to which a value belongs.
1357 * This uses exponentially sized bins that go from 0 to infinity.
1360 * value: in the range -INFINITY to INFINITY
1363 * The number of the bin in a struct Bins.bin
1365 static unsigned int binNum(const double value
)
1371 else if (value
< binEnd(1))
1375 else if (value
>= binStart(BIN_NB
- 1))
1381 return floor(log(value
) / log(binBase
)) + BIN_NB
+ 1;
1387 * Figure out the start of the interval of a bin in a histogram. See struct
1390 * This uses exponentially sized bins that go from 0 to infinity.
1393 * binNum: bin number
1396 * The start of the interval, this value is included in the interval (except
1397 * for -INFINITY, naturally)
1399 static double binStart(const unsigned int binNum
)
1401 g_assert_cmpuint(binNum
, <, BIN_NB
);
1407 else if (binNum
== 1)
1413 return pow(binBase
, (double) binNum
- BIN_NB
+ 1);
1419 * Figure out the end of the interval of a bin in a histogram. See struct
1422 * This uses exponentially sized bins that go from 0 to infinity.
1425 * binNum: bin number
1428 * The end of the interval, this value is not included in the interval
1430 static double binEnd(const unsigned int binNum
)
1432 g_assert_cmpuint(binNum
, <, BIN_NB
);
1438 else if (binNum
< BIN_NB
- 1)
1440 return pow(binBase
, (double) binNum
- BIN_NB
+ 2);
1450 * Return the total number of elements in the "normal" bins (not underflow or
1454 * bins: the structure containing bins to build a histrogram
1456 static uint32_t normalTotal(struct Bins
* const bins
)
1458 return bins
->total
- bins
->bin
[0] - bins
->bin
[BIN_NB
- 1];
1462 /* Update the bounds between two traces
1465 * bounds: the array containing all the trace-pair bounds
1466 * e1, e2: the two related events
1468 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
1471 unsigned int traceI
, traceJ
;
1472 uint64_t messageTime
;
1475 if (e1
->traceNum
< e2
->traceNum
)
1477 traceI
= e2
->traceNum
;
1478 traceJ
= e1
->traceNum
;
1479 messageTime
= e1
->cpuTime
;
1483 traceI
= e1
->traceNum
;
1484 traceJ
= e2
->traceNum
;
1485 messageTime
= e2
->cpuTime
;
1487 tpBounds
= &bounds
[traceI
][traceJ
];
1489 if (messageTime
< tpBounds
->min
)
1491 tpBounds
->min
= messageTime
;
1493 if (messageTime
> tpBounds
->max
)
1495 tpBounds
->max
= messageTime
;
1502 * Create the linear programming problem containing the constraints defined by
1503 * two half-hulls. The objective function and optimization directions are not
1507 * syncState: container for synchronization data
1508 * i: first trace number
1509 * j: second trace number, garanteed to be larger than i
1511 * A new glp_prob*, this problem must be freed by the caller with
1514 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
1519 const double zeroD
= 0.;
1520 glp_prob
* lp
= glp_create_prob();
1521 unsigned int hullPointNb
= g_queue_get_length(lowerHull
) +
1522 g_queue_get_length(upperHull
);
1523 GArray
* iArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1525 GArray
* jArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1527 GArray
* aArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(double),
1531 struct LPAddRowInfo rowInfo
;
1533 {lowerHull
, {lp
, GLP_UP
, iArray
, jArray
, aArray
}},
1534 {upperHull
, {lp
, GLP_LO
, iArray
, jArray
, aArray
}},
1537 // Create the LP problem
1538 glp_term_out(GLP_OFF
);
1539 glp_add_rows(lp
, hullPointNb
);
1540 glp_add_cols(lp
, 2);
1542 glp_set_col_name(lp
, 1, "a0");
1543 glp_set_col_bnds(lp
, 1, GLP_FR
, 0., 0.);
1544 glp_set_col_name(lp
, 2, "a1");
1545 glp_set_col_bnds(lp
, 2, GLP_LO
, 0., 0.);
1547 // Add row constraints
1548 g_array_append_val(iArray
, zero
);
1549 g_array_append_val(jArray
, zero
);
1550 g_array_append_val(aArray
, zeroD
);
1552 for (it
= 0; it
< sizeof(loopValues
) / sizeof(*loopValues
); it
++)
1554 g_queue_foreach(loopValues
[it
].hull
, &gfLPAddRow
,
1555 &loopValues
[it
].rowInfo
);
1558 g_assert_cmpuint(iArray
->len
, ==, jArray
->len
);
1559 g_assert_cmpuint(jArray
->len
, ==, aArray
->len
);
1560 g_assert_cmpuint(aArray
->len
- 1, ==, hullPointNb
* 2);
1562 glp_load_matrix(lp
, aArray
->len
- 1, &g_array_index(iArray
, int, 0),
1563 &g_array_index(jArray
, int, 0), &g_array_index(aArray
, double, 0));
1565 glp_scale_prob(lp
, GLP_SF_AUTO
);
1567 g_array_free(iArray
, TRUE
);
1568 g_array_free(jArray
, TRUE
);
1569 g_array_free(aArray
, TRUE
);
1576 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1579 * data Point*, synchronization point for which to add an LP row
1581 * user_data LPAddRowInfo*
1583 static void gfLPAddRow(gpointer data
, gpointer user_data
)
1586 struct LPAddRowInfo
* rowInfo
= user_data
;
1588 double constraints
[2];
1590 indexes
[0]= g_array_index(rowInfo
->iArray
, int, rowInfo
->iArray
->len
- 1) + 1;
1591 indexes
[1]= indexes
[0];
1593 if (rowInfo
->boundType
== GLP_UP
)
1595 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_UP
, 0., p
->y
);
1597 else if (rowInfo
->boundType
== GLP_LO
)
1599 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_LO
, p
->y
, 0.);
1603 g_assert_not_reached();
1606 g_array_append_vals(rowInfo
->iArray
, indexes
, 2);
1609 g_array_append_vals(rowInfo
->jArray
, indexes
, 2);
1611 constraints
[1]= p
->x
;
1612 g_array_append_vals(rowInfo
->aArray
, constraints
, 2);
1617 * Calculate min or max correction factors (as possible) using an LP problem.
1620 * lp: A linear programming problem with constraints and bounds
1622 * direction: The type of factors desired. Use GLP_MAX for max
1623 * approximation factors (a1, the drift or slope is the
1624 * largest) and GLP_MIN in the other case.
1627 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1628 * The calculation will fail if the hull assumptions are not respected.
1630 static Factors
* calculateFactors(glp_prob
* const lp
, const int direction
)
1635 glp_set_obj_coef(lp
, 1, 0.);
1636 glp_set_obj_coef(lp
, 2, 1.);
1638 glp_set_obj_dir(lp
, direction
);
1639 retval
= glp_simplex(lp
, NULL
);
1640 status
= glp_get_status(lp
);
1642 if (retval
== 0 && status
== GLP_OPT
)
1644 factors
= malloc(sizeof(Factors
));
1645 factors
->offset
= glp_get_col_prim(lp
, 1);
1646 factors
->drift
= glp_get_col_prim(lp
, 2);
1658 * Calculate min, max and approx correction factors (as possible) using an LP
1662 * lp: A linear programming problem with constraints and bounds
1666 * Please note that the approximation type may be MIDDLE, INCOMPLETE or
1667 * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do
1668 * not respect assumptions.
1670 static void calculateCompleteFactors(glp_prob
* const lp
, FactorsCHull
* factors
)
1672 factors
->min
= calculateFactors(lp
, GLP_MIN
);
1673 factors
->max
= calculateFactors(lp
, GLP_MAX
);
1675 if (factors
->min
&& factors
->max
)
1677 factors
->type
= MIDDLE
;
1678 calculateFactorsMiddle(factors
);
1680 else if (factors
->min
|| factors
->max
)
1682 factors
->type
= INCOMPLETE
;
1683 factors
->approx
= NULL
;
1687 factors
->type
= ABSENT
;
1688 factors
->approx
= NULL
;
1694 * Create and initialize an array like AnalysisStatsCHull.allFactors
1697 * traceNb: number of traces
1700 * A new array, which can be freed with freeAllFactors()
1702 static FactorsCHull
** createAllFactors(const unsigned int traceNb
)
1704 FactorsCHull
** factorsArray
;
1707 factorsArray
= malloc(traceNb
* sizeof(FactorsCHull
*));
1708 for (i
= 0; i
< traceNb
; i
++)
1710 factorsArray
[i
]= calloc((i
+ 1), sizeof(FactorsCHull
));
1712 factorsArray
[i
][i
].type
= EXACT
;
1713 factorsArray
[i
][i
].approx
= malloc(sizeof(Factors
));
1714 factorsArray
[i
][i
].approx
->drift
= 1.;
1715 factorsArray
[i
][i
].approx
->offset
= 0.;
1718 return factorsArray
;
1724 * Compute synchronization factors using a linear programming approach.
1725 * Compute the factors using analysis_chull. Compare the two.
1727 * There are two definitions of this function. The empty one is used when the
1728 * solver library, glpk, is not available at build time. In that case, nothing
1729 * is actually produced.
1732 * syncState: container for synchronization data
1734 #ifndef HAVE_LIBGLPK
1735 static inline void finalizeAnalysisEvalLP(SyncState
* const syncState
)
1739 static void finalizeAnalysisEvalLP(SyncState
* const syncState
)
1742 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
1743 AnalysisDataCHull
* chAnalysisData
= analysisData
->chullSS
->analysisData
;
1744 FactorsCHull
** lpFactorsArray
= createAllFactors(syncState
->traceNb
);
1745 FactorsCHull
* lpFactors
;
1747 if (!syncState
->stats
&& !syncState
->graphsStream
)
1752 if ((syncState
->graphsStream
&& analysisData
->graphs
->lps
!= NULL
) ||
1753 (syncState
->stats
&& analysisData
->stats
->chFactorsArray
!= NULL
))
1758 if (syncState
->stats
)
1760 analysisData
->stats
->chFactorsArray
=
1761 calculateAllFactors(analysisData
->chullSS
);
1762 analysisData
->stats
->lpFactorsArray
= lpFactorsArray
;
1765 if (syncState
->graphsStream
)
1767 analysisData
->graphs
->lps
= malloc(syncState
->traceNb
*
1768 sizeof(glp_prob
**));
1769 for (i
= 0; i
< syncState
->traceNb
; i
++)
1771 analysisData
->graphs
->lps
[i
]= malloc(i
* sizeof(glp_prob
*));
1773 analysisData
->graphs
->lpFactorsArray
= lpFactorsArray
;
1776 for (i
= 0; i
< syncState
->traceNb
; i
++)
1778 for (j
= 0; j
< i
; j
++)
1782 // Create the LP problem
1783 lp
= lpCreateProblem(chAnalysisData
->hullArray
[i
][j
],
1784 chAnalysisData
->hullArray
[j
][i
]);
1786 // Use the LP problem to find the correction factors for this pair of
1788 calculateCompleteFactors(lp
, &lpFactorsArray
[i
][j
]);
1790 if (syncState
->graphsStream
)
1792 analysisData
->graphs
->lps
[i
][j
]= lp
;
1796 glp_delete_prob(lp
);
1797 destroyFactorsCHull(lpFactors
);
1802 g_array_free(analysisData
->chullSS
->analysisModule
->finalizeAnalysis(analysisData
->chullSS
),
1809 * Compute synchronization accuracy information using a linear programming
1810 * approach. Write the neccessary data files and plot lines in the gnuplot
1813 * When the solver library, glpk, is not available at build time nothing is
1814 * actually produced.
1817 * syncState: container for synchronization data
1818 * i: first trace number
1819 * j: second trace number, garanteed to be larger than i
1821 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
1822 const unsigned int i
, const unsigned int j
)
1826 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
1827 AnalysisGraphsEval
* graphs
= analysisData
->graphs
;
1828 GQueue
*** hullArray
= ((AnalysisDataCHull
*)
1829 analysisData
->chullSS
->analysisData
)->hullArray
;
1830 FactorsCHull
* lpFactors
= &graphs
->lpFactorsArray
[j
][i
];
1831 glp_prob
* lp
= graphs
->lps
[j
][i
];
1833 if (lpFactors
->type
== MIDDLE
)
1840 unsigned int xBegin
, xEnd
;
1842 const unsigned int graphPointNb
= 1000;
1844 // Open the data file
1845 snprintf(fileName
, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i
, j
);
1846 fileName
[sizeof(fileName
) - 1]= '\0';
1848 cwd
= changeToGraphsDir(syncState
->graphsDir
);
1850 if ((fp
= fopen(fileName
, "w")) == NULL
)
1852 g_error(strerror(errno
));
1854 fprintf(fp
, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1859 g_error(strerror(errno
));
1863 // Build the list of absisca values for the points in the accuracy graph
1864 g_assert_cmpuint(graphPointNb
, >=, 4);
1865 xValues
= malloc(graphPointNb
* sizeof(double));
1866 xValues
[0]= graphs
->bounds
[j
][i
].min
;
1867 xValues
[graphPointNb
- 1]= graphs
->bounds
[j
][i
].max
;
1868 xValues
[1]= MIN(((Point
*) g_queue_peek_head(hullArray
[i
][j
]))->x
,
1869 ((Point
*) g_queue_peek_head(hullArray
[j
][i
]))->x
);
1870 xValues
[graphPointNb
- 2]= MAX(((Point
*)
1871 g_queue_peek_tail(hullArray
[i
][j
]))->x
, ((Point
*)
1872 g_queue_peek_tail(hullArray
[j
][i
]))->x
);
1874 if (xValues
[0] == xValues
[1])
1882 if (xValues
[graphPointNb
- 2] == xValues
[graphPointNb
- 1])
1884 xEnd
= graphPointNb
- 1;
1888 xEnd
= graphPointNb
- 2;
1890 interval
= (xValues
[xEnd
] - xValues
[xBegin
]) / (graphPointNb
- 1);
1892 for (it
= xBegin
; it
<= xEnd
; it
++)
1894 xValues
[it
]= xValues
[xBegin
] + interval
* (it
- xBegin
);
1897 /* For each absisca value and each optimisation direction, solve the LP
1898 * and write a line in the data file */
1899 for (it
= 0; it
< graphPointNb
; it
++)
1902 int directions
[]= {GLP_MIN
, GLP_MAX
};
1904 glp_set_obj_coef(lp
, 1, 1.);
1905 glp_set_obj_coef(lp
, 2, xValues
[it
]);
1907 fprintf(fp
, "%25.9f %25.9f", xValues
[it
], lpFactors
->approx
->offset
1908 + lpFactors
->approx
->drift
* xValues
[it
]);
1909 for (it2
= 0; it2
< sizeof(directions
) / sizeof(*directions
); it2
++)
1913 glp_set_obj_dir(lp
, directions
[it2
]);
1914 retval
= glp_simplex(lp
, NULL
);
1915 status
= glp_get_status(lp
);
1917 g_assert(retval
== 0 && status
== GLP_OPT
);
1918 fprintf(fp
, " %25.9f", glp_get_obj_val(lp
));
1926 fprintf(syncState
->graphsStream
,
1927 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1928 "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
1929 "title \"Synchronization accuracy\" "
1930 "with filledcurves linewidth 2 linetype 1 "
1931 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
,
1939 * Write the analysis-specific graph lines in the gnuplot script.
1941 * When the solver library, glpk, is not available at build time nothing is
1942 * actually produced.
1945 * syncState: container for synchronization data
1946 * i: first trace number
1947 * j: second trace number, garanteed to be larger than i
1949 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
1950 const unsigned int i
, const unsigned int j
)
1953 if (((AnalysisDataEval
*)
1954 syncState
->analysisData
)->graphs
->lpFactorsArray
[j
][i
].type
==
1957 fprintf(syncState
->graphsStream
,
1958 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1959 "using 1:(($3 - $2) / clock_freq_%2$u) notitle "
1960 "with lines linewidth 2 linetype 1 "
1961 "linecolor rgb \"gray60\", \\\n"
1962 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1963 "using 1:(($4 - $2) / clock_freq_%2$u) notitle "
1964 "with lines linewidth 2 linetype 1 "
1965 "linecolor rgb \"gray60\", \\\n", i
, j
);
1972 * Write the analysis-specific graph lines in the gnuplot script.
1975 * syncState: container for synchronization data
1976 * i: first trace number
1977 * j: second trace number, garanteed to be larger than i
1979 static void writeAnalysisTraceTraceBackPlotsEval(SyncState
* const syncState
,
1980 const unsigned int i
, const unsigned int j
)
1983 fprintf(syncState
->graphsStream
,
1984 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1986 "title \"Synchronization accuracy\" "
1987 "with filledcurves linewidth 2 linetype 1 "
1988 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
, j
);
1994 * Write the analysis-specific graph lines in the gnuplot script.
1997 * syncState: container for synchronization data
1998 * i: first trace number
1999 * j: second trace number, garanteed to be larger than i
2001 static void writeAnalysisTraceTraceForePlotsEval(SyncState
* const syncState
,
2002 const unsigned int i
, const unsigned int j
)
2004 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
2006 analysisData
->chullSS
->analysisModule
->graphFunctions
.writeTraceTraceForePlots(analysisData
->chullSS
,