1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
4 * This program is free software: you can redistribute it and/or modify it
5 * under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or (at
7 * your option) any later version.
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
12 * License for more details.
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
19 #define _ISOC99_SOURCE
25 #include <arpa/inet.h>
28 #include <netinet/in.h>
33 #include <sys/socket.h>
37 #include "sync_chain.h"
39 #include "event_analysis_eval.h"
42 struct WriteHistogramInfo
48 // Functions common to all analysis modules
49 static void initAnalysisEval(SyncState
* const syncState
);
50 static void destroyAnalysisEval(SyncState
* const syncState
);
52 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
54 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
56 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
58 static AllFactors
* finalizeAnalysisEval(SyncState
* const syncState
);
59 static void printAnalysisStatsEval(SyncState
* const syncState
);
60 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
61 const unsigned int i
, const unsigned int j
);
62 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
63 const unsigned int i
, const unsigned int j
);
65 // Functions specific to this module
66 static guint
ghfRttKeyHash(gconstpointer key
);
67 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
);
68 static void gdnDestroyRttKey(gpointer data
);
69 static void gdnDestroyDouble(gpointer data
);
70 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttFile
);
71 static void positionStream(FILE* stream
);
73 static void gfSum(gpointer data
, gpointer userData
);
74 static void gfSumSquares(gpointer data
, gpointer userData
);
75 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
78 static void hitBin(struct Bins
* const bins
, const double value
);
79 static unsigned int binNum(const double value
) __attribute__((pure
));
80 static double binStart(const unsigned int binNum
) __attribute__((pure
));
81 static double binEnd(const unsigned int binNum
) __attribute__((pure
));
82 static uint32_t normalTotal(struct Bins
* const bins
) __attribute__((const));
84 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
85 graphsDir
, const struct RttKey
* const rttKey
);
86 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
88 static void gdnDestroyAnalysisHistogramEval(gpointer data
);
89 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer
91 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
);
92 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
93 double* minRtt
, AnalysisHistogramEval
* const histogram
);
95 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
99 // initialized in registerAnalysisEval()
102 static AnalysisModule analysisModuleEval
= {
104 .initAnalysis
= &initAnalysisEval
,
105 .destroyAnalysis
= &destroyAnalysisEval
,
106 .analyzeMessage
= &analyzeMessageEval
,
107 .analyzeExchange
= &analyzeExchangeEval
,
108 .analyzeBroadcast
= &analyzeBroadcastEval
,
109 .finalizeAnalysis
= &finalizeAnalysisEval
,
110 .printAnalysisStats
= &printAnalysisStatsEval
,
112 .writeTraceTimeBackPlots
= &writeAnalysisTraceTimeBackPlotsEval
,
113 .writeTraceTimeForePlots
= &writeAnalysisTraceTimeForePlotsEval
,
117 static ModuleOption optionEvalRttFile
= {
118 .longName
= "eval-rtt-file",
119 .hasArg
= REQUIRED_ARG
,
120 .optionHelp
= "specify the file containing RTT information",
126 * Analysis module registering function
128 void registerAnalysisEval()
130 binBase
= exp10(6. / (BIN_NB
- 3));
132 g_queue_push_tail(&analysisModules
, &analysisModuleEval
);
133 g_queue_push_tail(&moduleOptions
, &optionEvalRttFile
);
138 * Analysis init function
140 * This function is called at the beginning of a synchronization run for a set
144 * syncState container for synchronization data.
146 static void initAnalysisEval(SyncState
* const syncState
)
148 AnalysisDataEval
* analysisData
;
151 analysisData
= malloc(sizeof(AnalysisDataEval
));
152 syncState
->analysisData
= analysisData
;
154 analysisData
->rttInfo
= g_hash_table_new_full(&ghfRttKeyHash
,
155 &gefRttKeyEqual
, &gdnDestroyRttKey
, &gdnDestroyDouble
);
156 if (optionEvalRttFile
.arg
)
161 rttStream
= fopen(optionEvalRttFile
.arg
, "r");
162 if (rttStream
== NULL
)
164 g_error(strerror(errno
));
167 readRttInfo(analysisData
->rttInfo
, rttStream
);
169 retval
= fclose(rttStream
);
172 g_error(strerror(errno
));
176 if (syncState
->stats
)
178 analysisData
->stats
= calloc(1, sizeof(AnalysisStatsEval
));
179 analysisData
->stats
->broadcastRangeMin
= INFINITY
;
180 analysisData
->stats
->broadcastRangeMax
= -INFINITY
;
182 analysisData
->stats
->messageStats
= malloc(syncState
->traceNb
*
183 sizeof(MessageStats
*));
184 for (i
= 0; i
< syncState
->traceNb
; i
++)
186 analysisData
->stats
->messageStats
[i
]= calloc(syncState
->traceNb
,
187 sizeof(MessageStats
));
190 analysisData
->stats
->exchangeRtt
=
191 g_hash_table_new_full(&ghfRttKeyHash
, &gefRttKeyEqual
,
192 &gdnDestroyRttKey
, &gdnDestroyDouble
);
195 if (syncState
->graphsStream
)
197 AnalysisGraphsEval
* graphs
= malloc(sizeof(AnalysisGraphsEval
));
200 analysisData
->graphs
= graphs
;
202 graphs
->histograms
= g_hash_table_new_full(&ghfRttKeyHash
,
203 &gefRttKeyEqual
, &gdnDestroyRttKey
,
204 &gdnDestroyAnalysisHistogramEval
);
206 graphs
->bounds
= malloc(syncState
->traceNb
* sizeof(Bounds
*));
207 for (i
= 0; i
< syncState
->traceNb
; i
++)
209 graphs
->bounds
[i
]= malloc(i
* sizeof(Bounds
));
210 for (j
= 0; j
< i
; j
++)
212 graphs
->bounds
[i
][j
].min
= UINT64_MAX
;
213 graphs
->bounds
[i
][j
].max
= 0;
217 graphs
->chullSS
= (SyncState
*) malloc(sizeof(SyncState
));
218 memcpy(graphs
->chullSS
, syncState
, sizeof(SyncState
));
219 graphs
->chullSS
->analysisData
= NULL
;
220 result
= g_queue_find_custom(&analysisModules
, "chull", &gcfCompareAnalysis
);
221 g_assert(result
!= NULL
);
222 graphs
->chullSS
->analysisModule
= (AnalysisModule
*) result
->data
;
223 graphs
->chullSS
->analysisModule
->initAnalysis(graphs
->chullSS
);
229 * Create and open files used to store histogram points to generate graphs.
230 * Create data structures to store histogram points during analysis.
233 * graphsDir: folder where to write files
234 * rttKey: host pair, make sure saddr < daddr
236 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
237 graphsDir
, const struct RttKey
* const rttKey
)
242 char name
[60], saddr
[16], daddr
[16];
243 AnalysisHistogramEval
* histogram
= calloc(1, sizeof(*histogram
));
246 const char* fileName
;
247 const char* host1
, *host2
;
249 {offsetof(AnalysisHistogramEval
, ttSendPoints
),
250 "analysis_eval_tt-%s_to_%s.data", saddr
, daddr
},
251 {offsetof(AnalysisHistogramEval
, ttRecvPoints
),
252 "analysis_eval_tt-%s_to_%s.data", daddr
, saddr
},
253 {offsetof(AnalysisHistogramEval
, hrttPoints
),
254 "analysis_eval_hrtt-%s_and_%s.data", saddr
, daddr
},
257 histogram
->ttSendBins
.min
= BIN_NB
- 1;
258 histogram
->ttRecvBins
.min
= BIN_NB
- 1;
259 histogram
->hrttBins
.min
= BIN_NB
- 1;
261 convertIP(saddr
, rttKey
->saddr
);
262 convertIP(daddr
, rttKey
->daddr
);
264 cwd
= changeToGraphsDir(graphsDir
);
266 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
268 retval
= snprintf(name
, sizeof(name
), loopValues
[i
].fileName
,
269 loopValues
[i
].host1
, loopValues
[i
].host2
);
270 if (retval
> sizeof(name
) - 1)
272 name
[sizeof(name
) - 1]= '\0';
274 if ((*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
)=
275 fopen(name
, "w")) == NULL
)
277 g_error(strerror(errno
));
284 g_error(strerror(errno
));
293 * Close files used to store histogram points to generate graphs.
296 * graphsDir: folder where to write files
297 * rttKey: host pair, make sure saddr < daddr
299 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
307 {offsetof(AnalysisHistogramEval
, ttSendPoints
)},
308 {offsetof(AnalysisHistogramEval
, ttRecvPoints
)},
309 {offsetof(AnalysisHistogramEval
, hrttPoints
)},
312 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
314 retval
= fclose(*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
));
317 g_error(strerror(errno
));
326 * A GDestroyNotify function for g_hash_table_new_full()
329 * data: AnalysisHistogramEval*
331 static void gdnDestroyAnalysisHistogramEval(gpointer data
)
333 destroyAnalysisHistogramEval(data
);
338 * A GHFunc for g_hash_table_foreach()
341 * key: RttKey* where saddr < daddr
342 * value: AnalysisHistogramEval*
343 * user_data struct WriteHistogramInfo*
345 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer user_data
)
347 double* rtt1
, * rtt2
;
348 struct RttKey
* rttKey
= key
;
349 struct RttKey oppositeRttKey
= {.saddr
= rttKey
->daddr
, .daddr
=
351 AnalysisHistogramEval
* histogram
= value
;
352 struct WriteHistogramInfo
* info
= user_data
;
354 rtt1
= g_hash_table_lookup(info
->rttInfo
, rttKey
);
355 rtt2
= g_hash_table_lookup(info
->rttInfo
, &oppositeRttKey
);
361 else if (rtt2
!= NULL
)
363 rtt1
= MIN(rtt1
, rtt2
);
366 dumpBinToFile(&histogram
->ttSendBins
, histogram
->ttSendPoints
);
367 dumpBinToFile(&histogram
->ttRecvBins
, histogram
->ttRecvPoints
);
368 dumpBinToFile(&histogram
->hrttBins
, histogram
->hrttPoints
);
369 writeHistogram(info
->graphsStream
, rttKey
, rtt1
, histogram
);
374 * Write the content of one bin in a histogram point file
377 * bin: array of values that make up a histogram
378 * file: FILE*, write to this file
380 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
)
384 // The first and last bins are skipped, see struct Bins
385 for (i
= 1; i
< BIN_NB
- 1; i
++)
387 if (bins
->bin
[i
] > 0)
389 fprintf(file
, "%20.9f %20.9f %20.9f\n", (binStart(i
) + binEnd(i
))
390 / 2., (double) bins
->bin
[i
] / ((binEnd(i
) - binStart(i
)) *
391 bins
->total
), binEnd(i
) - binStart(i
));
398 * Write the analysis-specific plot in the gnuplot script.
401 * graphsStream: write to this file
402 * rttKey: must be sorted such that saddr < daddr
403 * minRtt: if available, else NULL
404 * histogram: struct that contains the bins for the pair of traces
405 * identified by rttKey
407 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
408 double* minRtt
, AnalysisHistogramEval
* const histogram
)
410 char saddr
[16], daddr
[16];
412 convertIP(saddr
, rttKey
->saddr
);
413 convertIP(daddr
, rttKey
->daddr
);
415 fprintf(graphsStream
,
417 "set output \"histogram-%s-%s.eps\"\n"
419 "set xlabel \"Message Latency (s)\"\n"
420 "set ylabel \"Proportion of messages per second\"\n", saddr
, daddr
);
424 fprintf(graphsStream
,
425 "set arrow from %.9f, 0 rto 0, graph 1 "
426 "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
430 if (normalTotal(&histogram
->ttSendBins
) ||
431 normalTotal(&histogram
->ttRecvBins
) ||
432 normalTotal(&histogram
->hrttBins
))
434 fprintf(graphsStream
, "plot \\\n");
436 if (normalTotal(&histogram
->hrttBins
))
438 fprintf(graphsStream
,
439 "\t\"analysis_eval_hrtt-%s_and_%s.data\" "
440 "title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
441 "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
445 if (normalTotal(&histogram
->ttSendBins
))
447 fprintf(graphsStream
,
448 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
449 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
450 "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
454 if (normalTotal(&histogram
->ttRecvBins
))
456 fprintf(graphsStream
,
457 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
458 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
459 "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
463 // Remove the ",\\\n" from the last graph plot line
464 if (ftruncate(fileno(graphsStream
), ftell(graphsStream
) - 3) == -1)
466 g_error(strerror(errno
));
468 if (fseek(graphsStream
, 0, SEEK_END
) == -1)
470 g_error(strerror(errno
));
472 fprintf(graphsStream
, "\n");
478 * Analysis destroy function
480 * Free the analysis specific data structures
483 * syncState container for synchronization data.
485 static void destroyAnalysisEval(SyncState
* const syncState
)
488 AnalysisDataEval
* analysisData
;
490 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
492 if (analysisData
== NULL
)
497 g_hash_table_destroy(analysisData
->rttInfo
);
499 if (syncState
->stats
)
501 AnalysisStatsEval
* stats
= analysisData
->stats
;
503 for (i
= 0; i
< syncState
->traceNb
; i
++)
505 free(stats
->messageStats
[i
]);
507 free(stats
->messageStats
);
509 g_hash_table_destroy(stats
->exchangeRtt
);
514 if (syncState
->graphsStream
)
516 AnalysisGraphsEval
* graphs
= analysisData
->graphs
;
518 if (graphs
->histograms
)
520 g_hash_table_destroy(graphs
->histograms
);
523 for (i
= 0; i
< syncState
->traceNb
; i
++)
525 free(graphs
->bounds
[i
]);
527 free(graphs
->bounds
);
529 graphs
->chullSS
->analysisModule
->destroyAnalysis(graphs
->chullSS
);
530 free(graphs
->chullSS
);
535 free(syncState
->analysisData
);
536 syncState
->analysisData
= NULL
;
541 * Perform analysis on an event pair.
543 * Check if there is message inversion or messages that are too fast.
546 * syncState container for synchronization data
547 * message structure containing the events
549 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
552 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
553 MessageStats
* messageStats
;
556 struct RttKey rttKey
;
558 g_assert(message
->inE
->type
== TCP
);
560 if (syncState
->stats
)
563 &analysisData
->stats
->messageStats
[message
->outE
->traceNum
][message
->inE
->traceNum
];
564 messageStats
->total
++;
567 tt
= wallTimeSub(&message
->inE
->wallTime
, &message
->outE
->wallTime
);
570 if (syncState
->stats
)
572 messageStats
->inversionNb
++;
575 else if (syncState
->graphsStream
)
577 struct RttKey rttKey
= {
578 .saddr
=MIN(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
579 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
580 .daddr
=MAX(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
581 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
583 AnalysisHistogramEval
* histogram
=
584 g_hash_table_lookup(analysisData
->graphs
->histograms
, &rttKey
);
586 if (histogram
== NULL
)
588 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
590 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
, &rttKey
);
591 memcpy(tableKey
, &rttKey
, sizeof(*tableKey
));
592 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
, histogram
);
595 if (message
->inE
->event
.udpEvent
->datagramKey
->saddr
<
596 message
->inE
->event
.udpEvent
->datagramKey
->daddr
)
598 hitBin(&histogram
->ttSendBins
, tt
);
602 hitBin(&histogram
->ttRecvBins
, tt
);
606 if (syncState
->stats
)
609 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
;
611 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
;
612 rtt
= g_hash_table_lookup(analysisData
->rttInfo
, &rttKey
);
613 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey
.saddr
,
614 rttKey
.daddr
, rtt
? *rtt
: NAN
);
618 g_debug("rttInfo, tt: %f rtt / 2: %f", tt
, *rtt
/ 2.);
621 messageStats
->tooFastNb
++;
626 messageStats
->noRTTInfoNb
++;
630 if (syncState
->graphsStream
)
632 updateBounds(analysisData
->graphs
->bounds
, message
->inE
,
635 analysisData
->graphs
->chullSS
->analysisModule
->analyzeMessage(analysisData
->graphs
->chullSS
,
642 * Perform analysis on multiple messages
647 * syncState container for synchronization data
648 * exchange structure containing the messages
650 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
653 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
654 Message
* m1
= g_queue_peek_tail(exchange
->acks
);
655 Message
* m2
= exchange
->message
;
656 struct RttKey
* rttKey
;
657 double* rtt
, * exchangeRtt
;
659 g_assert(m1
->inE
->type
== TCP
);
661 // (T2 - T1) - (T3 - T4)
662 rtt
= malloc(sizeof(double));
663 *rtt
= wallTimeSub(&m1
->inE
->wallTime
, &m1
->outE
->wallTime
) -
664 wallTimeSub(&m2
->outE
->wallTime
, &m2
->inE
->wallTime
);
666 rttKey
= malloc(sizeof(struct RttKey
));
668 MIN(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
669 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
671 MAX(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
672 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
674 if (syncState
->graphsStream
)
676 AnalysisHistogramEval
* histogram
=
677 g_hash_table_lookup(analysisData
->graphs
->histograms
, rttKey
);
679 if (histogram
== NULL
)
681 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
683 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
,
685 memcpy(tableKey
, rttKey
, sizeof(*tableKey
));
686 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
,
690 hitBin(&histogram
->hrttBins
, *rtt
/ 2);
693 if (syncState
->stats
)
695 exchangeRtt
= g_hash_table_lookup(analysisData
->stats
->exchangeRtt
,
700 if (*rtt
< *exchangeRtt
)
702 g_hash_table_replace(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
712 g_hash_table_insert(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
724 * Perform analysis on muliple events
726 * Sum the broadcast differential delays
729 * syncState container for synchronization data
730 * broadcast structure containing the events
732 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
735 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
737 if (syncState
->stats
)
739 double sum
= 0, squaresSum
= 0;
742 g_queue_foreach(broadcast
->events
, &gfSum
, &sum
);
743 g_queue_foreach(broadcast
->events
, &gfSumSquares
, &squaresSum
);
745 analysisData
->stats
->broadcastNb
++;
746 // Because of numerical errors, this can at times be < 0
747 y
= squaresSum
/ g_queue_get_length(broadcast
->events
) - pow(sum
/
748 g_queue_get_length(broadcast
->events
), 2.);
751 analysisData
->stats
->broadcastStdevSum
+= sqrt(y
);
754 if (syncState
->traceNb
== 2 && g_queue_get_length(broadcast
->events
)
760 e0
= g_queue_peek_head(broadcast
->events
);
761 e1
= g_queue_peek_tail(broadcast
->events
);
762 if (e0
->traceNum
> e1
->traceNum
)
771 dd
= wallTimeSub(&e1
->wallTime
, &e0
->wallTime
);
773 analysisData
->stats
->broadcastPairNb
++;
774 if (dd
< analysisData
->stats
->broadcastRangeMin
)
776 analysisData
->stats
->broadcastRangeMin
= dd
;
778 if (dd
> analysisData
->stats
->broadcastRangeMax
)
780 analysisData
->stats
->broadcastRangeMax
= dd
;
783 analysisData
->stats
->broadcastSum
+= dd
;
784 analysisData
->stats
->broadcastSumSquares
+= pow(dd
, 2);
788 if (syncState
->graphsStream
)
792 unsigned int eventNb
= broadcast
->events
->length
;
794 events
= g_array_sized_new(FALSE
, FALSE
, sizeof(Event
*), eventNb
);
795 g_queue_foreach(broadcast
->events
, &gfAddEventToArray
, events
);
797 for (i
= 0; i
< eventNb
; i
++)
799 for (j
= 0; j
< eventNb
; j
++)
801 Event
* eventI
= g_array_index(events
, Event
*, i
), * eventJ
=
802 g_array_index(events
, Event
*, j
);
804 if (eventI
->traceNum
< eventJ
->traceNum
)
806 updateBounds(analysisData
->graphs
->bounds
, eventI
, eventJ
);
811 g_array_free(events
, TRUE
);
817 * Finalize the factor calculations. Since this module does not really
818 * calculate factors, absent factors are returned. Instead, histograms are
819 * written out and histogram structures are freed.
822 * syncState container for synchronization data.
825 * AllFactors* synchronization factors for each trace pair
827 static AllFactors
* finalizeAnalysisEval(SyncState
* const syncState
)
829 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
831 /* This function may be run twice because of matching_distributor. This
832 * check is there to make sure the next block is run only once.
834 if (syncState
->graphsStream
&& analysisData
->graphs
->histograms
)
836 g_hash_table_foreach(analysisData
->graphs
->histograms
,
837 &ghfWriteHistogram
, &(struct WriteHistogramInfo
) {.rttInfo
=
838 analysisData
->rttInfo
, .graphsStream
= syncState
->graphsStream
});
839 g_hash_table_destroy(analysisData
->graphs
->histograms
);
840 analysisData
->graphs
->histograms
= NULL
;
842 if (syncState
->graphsStream
)
844 SyncState
* chullSS
= analysisData
->graphs
->chullSS
;
846 freeAllFactors(chullSS
->analysisModule
->finalizeAnalysis(chullSS
),
851 return createAllFactors(syncState
->traceNb
);
856 * Print statistics related to analysis. Must be called after
860 * syncState container for synchronization data.
862 static void printAnalysisStatsEval(SyncState
* const syncState
)
864 AnalysisDataEval
* analysisData
;
865 unsigned int i
, j
, k
;
866 unsigned int totInversion
= 0, totTooFast
= 0, totNoInfo
= 0, totTotal
= 0;
869 if (!syncState
->stats
)
874 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
876 printf("Synchronization evaluation analysis stats:\n");
877 if (analysisData
->stats
->broadcastNb
)
879 printf("\tBroadcast differential delay:\n");
880 printf("\t\tsum of standard deviations: %g\n",
881 analysisData
->stats
->broadcastStdevSum
);
882 printf("\t\taverage standard deviation: %g\n",
883 analysisData
->stats
->broadcastStdevSum
/
884 analysisData
->stats
->broadcastNb
);
886 if (syncState
->traceNb
== 2)
888 printf("\t\tdifferential delay range: [ %g .. %g ]\n",
889 analysisData
->stats
->broadcastRangeMin
,
890 analysisData
->stats
->broadcastRangeMax
);
891 printf("\t\tdifferential delay average: %g\n",
892 analysisData
->stats
->broadcastSum
/
893 analysisData
->stats
->broadcastPairNb
);
894 printf("\t\tdifferential delay standard deviation: %g\n",
895 sqrt(analysisData
->stats
->broadcastSumSquares
/
896 analysisData
->stats
->broadcastPairNb
-
897 pow(analysisData
->stats
->broadcastSum
/
898 analysisData
->stats
->broadcastPairNb
, 2)));
902 printf("\tIndividual evaluation:\n"
903 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
905 for (i
= 0; i
< syncState
->traceNb
; i
++)
907 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
909 MessageStats
* messageStats
;
917 for (k
= 0; k
< sizeof(loopValues
) / sizeof(*loopValues
); k
++)
920 &analysisData
->stats
->messageStats
[loopValues
[k
].t1
][loopValues
[k
].t2
];
922 printf("\t\t%3d - %-3d ", loopValues
[k
].t1
, loopValues
[k
].t2
);
923 printf("%u (%.2f%%)%n", messageStats
->inversionNb
, (double)
924 messageStats
->inversionNb
/ messageStats
->total
* 100,
926 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
927 printf("%u (%.2f%%)%n", messageStats
->tooFastNb
, (double)
928 messageStats
->tooFastNb
/ messageStats
->total
* 100,
930 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1:
931 1, " ", messageStats
->noRTTInfoNb
, messageStats
->total
);
933 totInversion
+= messageStats
->inversionNb
;
934 totTooFast
+= messageStats
->tooFastNb
;
935 totNoInfo
+= messageStats
->noRTTInfoNb
;
936 totTotal
+= messageStats
->total
;
941 printf("\t\t total ");
942 printf("%u (%.2f%%)%n", totInversion
, (double) totInversion
/ totTotal
*
944 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
945 printf("%u (%.2f%%)%n", totTooFast
, (double) totTooFast
/ totTotal
* 100,
947 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ",
948 totNoInfo
, totTotal
);
950 printf("\tRound-trip times:\n"
951 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
952 g_hash_table_foreach(analysisData
->stats
->exchangeRtt
,
953 &ghfPrintExchangeRtt
, analysisData
->rttInfo
);
958 * A GHFunc for g_hash_table_foreach()
961 * key: RttKey* where saddr < daddr
962 * value: double*, RTT estimated from exchanges
963 * user_data GHashTable* rttInfo
965 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
968 char addr1
[16], addr2
[16];
969 struct RttKey
* rttKey1
= key
;
970 struct RttKey rttKey2
= {rttKey1
->daddr
, rttKey1
->saddr
};
971 double* fileRtt1
, *fileRtt2
;
972 GHashTable
* rttInfo
= user_data
;
974 convertIP(addr1
, rttKey1
->saddr
);
975 convertIP(addr2
, rttKey1
->daddr
);
977 fileRtt1
= g_hash_table_lookup(rttInfo
, rttKey1
);
978 fileRtt2
= g_hash_table_lookup(rttInfo
, &rttKey2
);
980 printf("\t\t(%15s, %-15s) %-18.3f ", addr1
, addr2
, *(double*) value
* 1e3
);
982 if (fileRtt1
|| fileRtt2
)
986 printf("%.3f", *fileRtt1
* 1e3
);
988 if (fileRtt1
&& fileRtt2
)
994 printf("%.3f", *fileRtt2
* 1e3
);
1006 * A GHashFunc for g_hash_table_new()
1009 * key struct RttKey*
1011 static guint
ghfRttKeyHash(gconstpointer key
)
1013 struct RttKey
* rttKey
;
1016 rttKey
= (struct RttKey
*) key
;
1028 * A GDestroyNotify function for g_hash_table_new_full()
1031 * data: struct RttKey*
1033 static void gdnDestroyRttKey(gpointer data
)
1040 * A GDestroyNotify function for g_hash_table_new_full()
1045 static void gdnDestroyDouble(gpointer data
)
1052 * A GEqualFunc for g_hash_table_new()
1058 * TRUE if both values are equal
1060 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
)
1062 const struct RttKey
* rkA
, * rkB
;
1064 rkA
= (struct RttKey
*) a
;
1065 rkB
= (struct RttKey
*) b
;
1067 if (rkA
->saddr
== rkB
->saddr
&& rkA
->daddr
== rkB
->daddr
)
1079 * Read a file contain minimum round trip time values and fill an array with
1080 * them. The file is formatted as such:
1081 * <host1 IP> <host2 IP> <RTT in milliseconds>
1082 * ip's should be in dotted quad format
1085 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
1086 * rttStream: stream from which to read
1088 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttStream
)
1094 positionStream(rttStream
);
1095 retval
= getline(&line
, &len
, rttStream
);
1096 while(!feof(rttStream
))
1098 struct RttKey
* rttKey
;
1099 char saddrDQ
[20], daddrDQ
[20];
1102 struct in_addr addr
;
1108 {saddrDQ
, offsetof(struct RttKey
, saddr
)},
1109 {daddrDQ
, offsetof(struct RttKey
, daddr
)}
1112 if (retval
== -1 && !feof(rttStream
))
1114 g_error(strerror(errno
));
1117 if (line
[retval
- 1] == '\n')
1119 line
[retval
- 1]= '\0';
1122 rtt
= malloc(sizeof(double));
1123 retval
= sscanf(line
, " %19s %19s %lf %c", saddrDQ
, daddrDQ
, rtt
,
1127 g_error(strerror(errno
));
1129 else if (retval
!= 3)
1131 g_error("Error parsing RTT file, line was '%s'", line
);
1134 rttKey
= malloc(sizeof(struct RttKey
));
1135 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
1137 retval
= inet_aton(loopValues
[i
].dq
, &addr
);
1140 g_error("Error converting address '%s'", loopValues
[i
].dq
);
1142 *(uint32_t*) ((void*) rttKey
+ loopValues
[i
].offset
)=
1147 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey
->saddr
,
1148 rttKey
->daddr
, *rtt
);
1149 g_hash_table_insert(rttInfo
, rttKey
, rtt
);
1151 positionStream(rttStream
);
1152 retval
= getline(&line
, &len
, rttStream
);
1163 * Advance stream over empty space, empty lines and lines that begin with '#'
1166 * stream: stream, at exit, will be over the first non-empty character
1167 * of a line of be at EOF
1169 static void positionStream(FILE* stream
)
1178 firstChar
= fgetc(stream
);
1179 if (firstChar
== (int) '#')
1181 retval
= getline(&line
, &len
, stream
);
1190 g_error(strerror(errno
));
1194 else if (firstChar
== (int) '\n' || firstChar
== (int) ' ' ||
1195 firstChar
== (int) '\t')
1197 else if (firstChar
== EOF
)
1206 retval
= ungetc(firstChar
, stream
);
1209 g_error("Error: ungetc()");
1221 * A GFunc for g_queue_foreach()
1224 * data Event*, a UDP broadcast event
1225 * user_data double*, the running sum
1228 * Adds the time of the event to the sum
1230 static void gfSum(gpointer data
, gpointer userData
)
1232 Event
* event
= (Event
*) data
;
1234 *(double*) userData
+= event
->wallTime
.seconds
+ event
->wallTime
.nanosec
/
1240 * A GFunc for g_queue_foreach()
1243 * data Event*, a UDP broadcast event
1244 * user_data double*, the running sum
1247 * Adds the square of the time of the event to the sum
1249 static void gfSumSquares(gpointer data
, gpointer userData
)
1251 Event
* event
= (Event
*) data
;
1253 *(double*) userData
+= pow(event
->wallTime
.seconds
+ event
->wallTime
.nanosec
1259 * Update a struct Bins according to a new value
1262 * bins: the structure containing bins to build a histrogram
1263 * value: the new value
1265 static void hitBin(struct Bins
* const bins
, const double value
)
1267 unsigned int binN
= binNum(value
);
1269 if (binN
< bins
->min
)
1273 else if (binN
> bins
->max
)
1285 * Figure out the bin in a histogram to which a value belongs.
1287 * This uses exponentially sized bins that go from 0 to infinity.
1290 * value: in the range -INFINITY to INFINITY
1293 * The number of the bin in a struct Bins.bin
1295 static unsigned int binNum(const double value
)
1301 else if (value
< binEnd(1))
1305 else if (value
>= binStart(BIN_NB
- 1))
1311 return floor(log(value
) / log(binBase
)) + BIN_NB
+ 1;
1317 * Figure out the start of the interval of a bin in a histogram. See struct
1320 * This uses exponentially sized bins that go from 0 to infinity.
1323 * binNum: bin number
1326 * The start of the interval, this value is included in the interval (except
1327 * for -INFINITY, naturally)
1329 static double binStart(const unsigned int binNum
)
1331 g_assert_cmpuint(binNum
, <, BIN_NB
);
1337 else if (binNum
== 1)
1343 return pow(binBase
, (double) binNum
- BIN_NB
+ 1);
1349 * Figure out the end of the interval of a bin in a histogram. See struct
1352 * This uses exponentially sized bins that go from 0 to infinity.
1355 * binNum: bin number
1358 * The end of the interval, this value is not included in the interval
1360 static double binEnd(const unsigned int binNum
)
1362 g_assert_cmpuint(binNum
, <, BIN_NB
);
1368 else if (binNum
< BIN_NB
- 1)
1370 return pow(binBase
, (double) binNum
- BIN_NB
+ 2);
1380 * Return the total number of elements in the "normal" bins (not underflow or
1384 * bins: the structure containing bins to build a histrogram
1386 static uint32_t normalTotal(struct Bins
* const bins
)
1388 return bins
->total
- bins
->bin
[0] - bins
->bin
[BIN_NB
- 1];
1392 /* Update the bounds between two traces
1395 * bounds: the array containing all the trace-pair bounds
1396 * e1, e2: the two related events
1398 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
1401 unsigned int traceI
, traceJ
;
1402 uint64_t messageTime
;
1405 if (e1
->traceNum
< e2
->traceNum
)
1407 traceI
= e2
->traceNum
;
1408 traceJ
= e1
->traceNum
;
1409 messageTime
= e1
->cpuTime
;
1413 traceI
= e1
->traceNum
;
1414 traceJ
= e2
->traceNum
;
1415 messageTime
= e2
->cpuTime
;
1417 tpBounds
= &bounds
[traceI
][traceJ
];
1419 if (messageTime
< tpBounds
->min
)
1421 tpBounds
->min
= messageTime
;
1423 if (messageTime
> tpBounds
->max
)
1425 tpBounds
->max
= messageTime
;
1431 * Write the analysis-specific graph lines in the gnuplot script.
1434 * syncState: container for synchronization data
1435 * i: first trace number
1436 * j: second trace number, garanteed to be larger than i
1438 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
1439 const unsigned int i
, const unsigned int j
)
1441 SyncState
* chullSS
= ((AnalysisDataEval
*)
1442 syncState
->analysisData
)->graphs
->chullSS
;
1443 const GraphFunctions
* graphFunctions
=
1444 &chullSS
->analysisModule
->graphFunctions
;
1446 if (graphFunctions
->writeTraceTimeBackPlots
!= NULL
)
1448 graphFunctions
->writeTraceTimeBackPlots(chullSS
, i
, j
);
1454 * Write the analysis-specific graph lines in the gnuplot script.
1457 * syncState: container for synchronization data
1458 * i: first trace number
1459 * j: second trace number, garanteed to be larger than i
1461 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
1462 const unsigned int i
, const unsigned int j
)
1464 SyncState
* chullSS
= ((AnalysisDataEval
*)
1465 syncState
->analysisData
)->graphs
->chullSS
;
1466 const GraphFunctions
* graphFunctions
=
1467 &chullSS
->analysisModule
->graphFunctions
;
1469 if (graphFunctions
->writeTraceTimeForePlots
!= NULL
)
1471 graphFunctions
->writeTraceTimeForePlots(chullSS
, i
, j
);