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"
38 #include "event_analysis_chull.h"
40 #include "event_analysis_eval.h"
43 struct WriteHistogramInfo
54 GArray
* iArray
, * jArray
, * aArray
;
58 // Functions common to all analysis modules
59 static void initAnalysisEval(SyncState
* const syncState
);
60 static void destroyAnalysisEval(SyncState
* const syncState
);
62 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
64 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
66 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
68 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
);
69 static void printAnalysisStatsEval(SyncState
* const syncState
);
70 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
71 const unsigned int i
, const unsigned int j
);
72 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
73 const unsigned int i
, const unsigned int j
);
74 static void writeAnalysisTraceTraceBackPlotsEval(SyncState
* const syncState
,
75 const unsigned int i
, const unsigned int j
);
76 static void writeAnalysisTraceTraceForePlotsEval(SyncState
* const syncState
,
77 const unsigned int i
, const unsigned int j
);
79 // Functions specific to this module
80 static guint
ghfRttKeyHash(gconstpointer key
);
81 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
);
82 static void gdnDestroyRttKey(gpointer data
);
83 static void gdnDestroyDouble(gpointer data
);
84 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttFile
);
85 static void positionStream(FILE* stream
);
87 static void gfSum(gpointer data
, gpointer userData
);
88 static void gfSumSquares(gpointer data
, gpointer userData
);
89 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
92 static void hitBin(struct Bins
* const bins
, const double value
);
93 static unsigned int binNum(const double value
) __attribute__((pure
));
94 static double binStart(const unsigned int binNum
) __attribute__((pure
));
95 static double binEnd(const unsigned int binNum
) __attribute__((pure
));
96 static uint32_t normalTotal(struct Bins
* const bins
) __attribute__((const));
98 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
99 graphsDir
, const struct RttKey
* const rttKey
);
100 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
102 static void gdnDestroyAnalysisHistogramEval(gpointer data
);
103 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer
105 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
);
106 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
107 double* minRtt
, AnalysisHistogramEval
* const histogram
);
109 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
112 static void finalizeAnalysisEvalLP(SyncState
* const syncState
);
113 // The next group of functions is only needed when computing synchronization
116 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
118 static void gfLPAddRow(gpointer data
, gpointer user_data
);
119 static Factors
* calculateFactors(glp_prob
* const lp
, const int direction
);
120 static void calculateCompleteFactors(glp_prob
* const lp
, FactorsCHull
*
122 static FactorsCHull
** createAllFactors(const unsigned int traceNb
);
123 static inline void finalizeAnalysisEvalLP(SyncState
* const syncState
);
124 static void gfAddAbsiscaToArray(gpointer data
, gpointer user_data
);
125 static gint
gcfCompareDouble(gconstpointer a
, gconstpointer b
);
127 static void finalizeAnalysisEvalLP(SyncState
* const syncState
);
131 // initialized in registerAnalysisEval()
134 static AnalysisModule analysisModuleEval
= {
136 .initAnalysis
= &initAnalysisEval
,
137 .destroyAnalysis
= &destroyAnalysisEval
,
138 .analyzeMessage
= &analyzeMessageEval
,
139 .analyzeExchange
= &analyzeExchangeEval
,
140 .analyzeBroadcast
= &analyzeBroadcastEval
,
141 .finalizeAnalysis
= &finalizeAnalysisEval
,
142 .printAnalysisStats
= &printAnalysisStatsEval
,
144 .writeTraceTimeBackPlots
= &writeAnalysisTraceTimeBackPlotsEval
,
145 .writeTraceTimeForePlots
= &writeAnalysisTraceTimeForePlotsEval
,
146 .writeTraceTraceBackPlots
= &writeAnalysisTraceTraceBackPlotsEval
,
147 .writeTraceTraceForePlots
= &writeAnalysisTraceTraceForePlotsEval
,
151 static ModuleOption optionEvalRttFile
= {
152 .longName
= "eval-rtt-file",
153 .hasArg
= REQUIRED_ARG
,
154 .optionHelp
= "specify the file containing RTT information",
160 * Analysis module registering function
162 void registerAnalysisEval()
164 binBase
= exp10(6. / (BIN_NB
- 3));
166 g_queue_push_tail(&analysisModules
, &analysisModuleEval
);
167 g_queue_push_tail(&moduleOptions
, &optionEvalRttFile
);
172 * Analysis init function
174 * This function is called at the beginning of a synchronization run for a set
178 * syncState container for synchronization data.
180 static void initAnalysisEval(SyncState
* const syncState
)
182 AnalysisDataEval
* analysisData
;
185 analysisData
= malloc(sizeof(AnalysisDataEval
));
186 syncState
->analysisData
= analysisData
;
188 analysisData
->rttInfo
= g_hash_table_new_full(&ghfRttKeyHash
,
189 &gefRttKeyEqual
, &gdnDestroyRttKey
, &gdnDestroyDouble
);
190 if (optionEvalRttFile
.arg
)
195 rttStream
= fopen(optionEvalRttFile
.arg
, "r");
196 if (rttStream
== NULL
)
198 g_error(strerror(errno
));
201 readRttInfo(analysisData
->rttInfo
, rttStream
);
203 retval
= fclose(rttStream
);
206 g_error(strerror(errno
));
210 if (syncState
->stats
)
212 analysisData
->stats
= calloc(1, sizeof(AnalysisStatsEval
));
213 analysisData
->stats
->broadcastRangeMin
= INFINITY
;
214 analysisData
->stats
->broadcastRangeMax
= -INFINITY
;
216 analysisData
->stats
->messageStats
= malloc(syncState
->traceNb
*
217 sizeof(MessageStats
*));
218 for (i
= 0; i
< syncState
->traceNb
; i
++)
220 analysisData
->stats
->messageStats
[i
]= calloc(syncState
->traceNb
,
221 sizeof(MessageStats
));
224 analysisData
->stats
->exchangeRtt
=
225 g_hash_table_new_full(&ghfRttKeyHash
, &gefRttKeyEqual
,
226 &gdnDestroyRttKey
, &gdnDestroyDouble
);
229 analysisData
->stats
->chFactorsArray
= NULL
;
230 analysisData
->stats
->lpFactorsArray
= NULL
;
234 if (syncState
->graphsStream
)
236 AnalysisGraphsEval
* graphs
= malloc(sizeof(AnalysisGraphsEval
));
238 analysisData
->graphs
= graphs
;
240 graphs
->histograms
= g_hash_table_new_full(&ghfRttKeyHash
,
241 &gefRttKeyEqual
, &gdnDestroyRttKey
,
242 &gdnDestroyAnalysisHistogramEval
);
244 graphs
->bounds
= malloc(syncState
->traceNb
* sizeof(Bounds
*));
245 for (i
= 0; i
< syncState
->traceNb
; i
++)
247 graphs
->bounds
[i
]= malloc(i
* sizeof(Bounds
));
248 for (j
= 0; j
< i
; j
++)
250 graphs
->bounds
[i
][j
].min
= UINT64_MAX
;
251 graphs
->bounds
[i
][j
].max
= 0;
257 graphs
->lpFactorsArray
= NULL
;
261 if (syncState
->stats
|| syncState
->graphsStream
)
265 analysisData
->chullSS
= malloc(sizeof(SyncState
));
266 memcpy(analysisData
->chullSS
, syncState
, sizeof(SyncState
));
267 analysisData
->chullSS
->stats
= false;
268 analysisData
->chullSS
->analysisData
= NULL
;
269 result
= g_queue_find_custom(&analysisModules
, "chull",
270 &gcfCompareAnalysis
);
271 analysisData
->chullSS
->analysisModule
= (AnalysisModule
*) result
->data
;
272 analysisData
->chullSS
->analysisModule
->initAnalysis(analysisData
->chullSS
);
278 * Create and open files used to store histogram points to generate graphs.
279 * Create data structures to store histogram points during analysis.
282 * graphsDir: folder where to write files
283 * rttKey: host pair, make sure saddr < daddr
285 static AnalysisHistogramEval
* constructAnalysisHistogramEval(const char* const
286 graphsDir
, const struct RttKey
* const rttKey
)
291 char name
[60], saddr
[16], daddr
[16];
292 AnalysisHistogramEval
* histogram
= calloc(1, sizeof(*histogram
));
295 const char* fileName
;
296 const char* host1
, *host2
;
298 {offsetof(AnalysisHistogramEval
, ttSendPoints
),
299 "analysis_eval_tt-%s_to_%s.data", saddr
, daddr
},
300 {offsetof(AnalysisHistogramEval
, ttRecvPoints
),
301 "analysis_eval_tt-%s_to_%s.data", daddr
, saddr
},
302 {offsetof(AnalysisHistogramEval
, hrttPoints
),
303 "analysis_eval_hrtt-%s_and_%s.data", saddr
, daddr
},
306 histogram
->ttSendBins
.min
= BIN_NB
- 1;
307 histogram
->ttRecvBins
.min
= BIN_NB
- 1;
308 histogram
->hrttBins
.min
= BIN_NB
- 1;
310 convertIP(saddr
, rttKey
->saddr
);
311 convertIP(daddr
, rttKey
->daddr
);
313 cwd
= changeToGraphsDir(graphsDir
);
315 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
317 retval
= snprintf(name
, sizeof(name
), loopValues
[i
].fileName
,
318 loopValues
[i
].host1
, loopValues
[i
].host2
);
319 if (retval
> sizeof(name
) - 1)
321 name
[sizeof(name
) - 1]= '\0';
323 if ((*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
)=
324 fopen(name
, "w")) == NULL
)
326 g_error(strerror(errno
));
333 g_error(strerror(errno
));
342 * Close files used to store histogram points to generate graphs.
345 * graphsDir: folder where to write files
346 * rttKey: host pair, make sure saddr < daddr
348 static void destroyAnalysisHistogramEval(AnalysisHistogramEval
* const
356 {offsetof(AnalysisHistogramEval
, ttSendPoints
)},
357 {offsetof(AnalysisHistogramEval
, ttRecvPoints
)},
358 {offsetof(AnalysisHistogramEval
, hrttPoints
)},
361 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
363 retval
= fclose(*(FILE**)((void*) histogram
+ loopValues
[i
].pointsOffset
));
366 g_error(strerror(errno
));
375 * A GDestroyNotify function for g_hash_table_new_full()
378 * data: AnalysisHistogramEval*
380 static void gdnDestroyAnalysisHistogramEval(gpointer data
)
382 destroyAnalysisHistogramEval(data
);
387 * A GHFunc for g_hash_table_foreach()
390 * key: RttKey* where saddr < daddr
391 * value: AnalysisHistogramEval*
392 * user_data struct WriteHistogramInfo*
394 static void ghfWriteHistogram(gpointer key
, gpointer value
, gpointer user_data
)
396 double* rtt1
, * rtt2
;
397 struct RttKey
* rttKey
= key
;
398 struct RttKey oppositeRttKey
= {.saddr
= rttKey
->daddr
, .daddr
=
400 AnalysisHistogramEval
* histogram
= value
;
401 struct WriteHistogramInfo
* info
= user_data
;
403 rtt1
= g_hash_table_lookup(info
->rttInfo
, rttKey
);
404 rtt2
= g_hash_table_lookup(info
->rttInfo
, &oppositeRttKey
);
410 else if (rtt2
!= NULL
)
412 rtt1
= MIN(rtt1
, rtt2
);
415 dumpBinToFile(&histogram
->ttSendBins
, histogram
->ttSendPoints
);
416 dumpBinToFile(&histogram
->ttRecvBins
, histogram
->ttRecvPoints
);
417 dumpBinToFile(&histogram
->hrttBins
, histogram
->hrttPoints
);
418 writeHistogram(info
->graphsStream
, rttKey
, rtt1
, histogram
);
423 * Write the content of one bin in a histogram point file
426 * bin: array of values that make up a histogram
427 * file: FILE*, write to this file
429 static void dumpBinToFile(const struct Bins
* const bins
, FILE* const file
)
433 // The first and last bins are skipped, see struct Bins
434 for (i
= 1; i
< BIN_NB
- 1; i
++)
436 if (bins
->bin
[i
] > 0)
438 fprintf(file
, "%20.9f %20.9f %20.9f\n", (binStart(i
) + binEnd(i
))
439 / 2., (double) bins
->bin
[i
] / ((binEnd(i
) - binStart(i
)) *
440 bins
->total
), binEnd(i
) - binStart(i
));
447 * Write the analysis-specific plot in the gnuplot script.
450 * graphsStream: write to this file
451 * rttKey: must be sorted such that saddr < daddr
452 * minRtt: if available, else NULL
453 * histogram: struct that contains the bins for the pair of traces
454 * identified by rttKey
456 static void writeHistogram(FILE* graphsStream
, const struct RttKey
* rttKey
,
457 double* minRtt
, AnalysisHistogramEval
* const histogram
)
459 char saddr
[16], daddr
[16];
461 convertIP(saddr
, rttKey
->saddr
);
462 convertIP(daddr
, rttKey
->daddr
);
464 fprintf(graphsStream
,
466 "set output \"histogram-%s-%s.eps\"\n"
468 "set xlabel \"Message Latency (s)\"\n"
469 "set ylabel \"Proportion of messages per second\"\n", saddr
, daddr
);
473 fprintf(graphsStream
,
474 "set arrow from %.9f, 0 rto 0, graph 1 "
475 "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
479 if (normalTotal(&histogram
->ttSendBins
) ||
480 normalTotal(&histogram
->ttRecvBins
) ||
481 normalTotal(&histogram
->hrttBins
))
483 fprintf(graphsStream
, "plot \\\n");
485 if (normalTotal(&histogram
->hrttBins
))
487 fprintf(graphsStream
,
488 "\t\"analysis_eval_hrtt-%s_and_%s.data\" "
489 "title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
490 "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
494 if (normalTotal(&histogram
->ttSendBins
))
496 fprintf(graphsStream
,
497 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
498 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
499 "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
503 if (normalTotal(&histogram
->ttRecvBins
))
505 fprintf(graphsStream
,
506 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
507 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
508 "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
512 // Remove the ",\\\n" from the last graph plot line
513 if (ftruncate(fileno(graphsStream
), ftell(graphsStream
) - 3) == -1)
515 g_error(strerror(errno
));
517 if (fseek(graphsStream
, 0, SEEK_END
) == -1)
519 g_error(strerror(errno
));
521 fprintf(graphsStream
, "\n");
527 * Analysis destroy function
529 * Free the analysis specific data structures
532 * syncState container for synchronization data.
534 static void destroyAnalysisEval(SyncState
* const syncState
)
537 AnalysisDataEval
* analysisData
;
539 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
541 if (analysisData
== NULL
)
546 g_hash_table_destroy(analysisData
->rttInfo
);
548 if (syncState
->stats
)
550 AnalysisStatsEval
* stats
= analysisData
->stats
;
552 for (i
= 0; i
< syncState
->traceNb
; i
++)
554 free(stats
->messageStats
[i
]);
556 free(stats
->messageStats
);
558 g_hash_table_destroy(stats
->exchangeRtt
);
561 freeAllFactors(syncState
->traceNb
, stats
->chFactorsArray
);
562 freeAllFactors(syncState
->traceNb
, stats
->lpFactorsArray
);
568 if (syncState
->graphsStream
)
570 AnalysisGraphsEval
* graphs
= analysisData
->graphs
;
572 if (graphs
->histograms
)
574 g_hash_table_destroy(graphs
->histograms
);
577 for (i
= 0; i
< syncState
->traceNb
; i
++)
579 free(graphs
->bounds
[i
]);
581 free(graphs
->bounds
);
584 for (i
= 0; i
< syncState
->traceNb
; i
++)
588 for (j
= 0; j
< i
; j
++)
590 // There seems to be a memory leak in glpk, valgrind reports a
591 // loss (reachable) even if the problem is deleted
592 glp_delete_prob(graphs
->lps
[i
][j
]);
594 free(graphs
->lps
[i
]);
598 if (!syncState
->stats
)
600 freeAllFactors(syncState
->traceNb
, graphs
->lpFactorsArray
);
607 if (syncState
->stats
|| syncState
->graphsStream
)
609 analysisData
->chullSS
->analysisModule
->destroyAnalysis(analysisData
->chullSS
);
610 free(analysisData
->chullSS
);
613 free(syncState
->analysisData
);
614 syncState
->analysisData
= NULL
;
619 * Perform analysis on an event pair.
621 * Check if there is message inversion or messages that are too fast.
624 * syncState container for synchronization data
625 * message structure containing the events
627 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
630 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
631 MessageStats
* messageStats
;
634 struct RttKey rttKey
;
636 g_assert(message
->inE
->type
== TCP
);
638 if (syncState
->stats
)
641 &analysisData
->stats
->messageStats
[message
->outE
->traceNum
][message
->inE
->traceNum
];
642 messageStats
->total
++;
645 tt
= wallTimeSub(&message
->inE
->wallTime
, &message
->outE
->wallTime
);
648 if (syncState
->stats
)
650 messageStats
->inversionNb
++;
653 else if (syncState
->graphsStream
)
655 struct RttKey rttKey
= {
656 .saddr
=MIN(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
657 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
658 .daddr
=MAX(message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
659 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
),
661 AnalysisHistogramEval
* histogram
=
662 g_hash_table_lookup(analysisData
->graphs
->histograms
, &rttKey
);
664 if (histogram
== NULL
)
666 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
668 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
, &rttKey
);
669 memcpy(tableKey
, &rttKey
, sizeof(*tableKey
));
670 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
, histogram
);
673 if (message
->inE
->event
.udpEvent
->datagramKey
->saddr
<
674 message
->inE
->event
.udpEvent
->datagramKey
->daddr
)
676 hitBin(&histogram
->ttSendBins
, tt
);
680 hitBin(&histogram
->ttRecvBins
, tt
);
684 if (syncState
->stats
)
687 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
;
689 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
;
690 rtt
= g_hash_table_lookup(analysisData
->rttInfo
, &rttKey
);
691 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey
.saddr
,
692 rttKey
.daddr
, rtt
? *rtt
: NAN
);
696 g_debug("rttInfo, tt: %f rtt / 2: %f", tt
, *rtt
/ 2.);
699 messageStats
->tooFastNb
++;
704 messageStats
->noRTTInfoNb
++;
708 if (syncState
->graphsStream
)
710 updateBounds(analysisData
->graphs
->bounds
, message
->inE
,
714 if (syncState
->stats
|| syncState
->graphsStream
)
716 analysisData
->chullSS
->analysisModule
->analyzeMessage(analysisData
->chullSS
,
723 * Perform analysis on multiple messages
728 * syncState container for synchronization data
729 * exchange structure containing the messages
731 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
734 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
735 Message
* m1
= g_queue_peek_tail(exchange
->acks
);
736 Message
* m2
= exchange
->message
;
737 struct RttKey
* rttKey
;
738 double* rtt
, * exchangeRtt
;
740 g_assert(m1
->inE
->type
== TCP
);
742 // (T2 - T1) - (T3 - T4)
743 rtt
= malloc(sizeof(double));
744 *rtt
= wallTimeSub(&m1
->inE
->wallTime
, &m1
->outE
->wallTime
) -
745 wallTimeSub(&m2
->outE
->wallTime
, &m2
->inE
->wallTime
);
747 rttKey
= malloc(sizeof(struct RttKey
));
749 MIN(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
750 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
752 MAX(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
753 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
755 if (syncState
->graphsStream
)
757 AnalysisHistogramEval
* histogram
=
758 g_hash_table_lookup(analysisData
->graphs
->histograms
, rttKey
);
760 if (histogram
== NULL
)
762 struct RttKey
* tableKey
= malloc(sizeof(*tableKey
));
764 histogram
= constructAnalysisHistogramEval(syncState
->graphsDir
,
766 memcpy(tableKey
, rttKey
, sizeof(*tableKey
));
767 g_hash_table_insert(analysisData
->graphs
->histograms
, tableKey
,
771 hitBin(&histogram
->hrttBins
, *rtt
/ 2);
774 if (syncState
->stats
)
776 exchangeRtt
= g_hash_table_lookup(analysisData
->stats
->exchangeRtt
,
781 if (*rtt
< *exchangeRtt
)
783 g_hash_table_replace(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
793 g_hash_table_insert(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
805 * Perform analysis on muliple events
807 * Sum the broadcast differential delays
810 * syncState container for synchronization data
811 * broadcast structure containing the events
813 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
816 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
818 if (syncState
->stats
)
820 double sum
= 0, squaresSum
= 0;
823 g_queue_foreach(broadcast
->events
, &gfSum
, &sum
);
824 g_queue_foreach(broadcast
->events
, &gfSumSquares
, &squaresSum
);
826 analysisData
->stats
->broadcastNb
++;
827 // Because of numerical errors, this can at times be < 0
828 y
= squaresSum
/ g_queue_get_length(broadcast
->events
) - pow(sum
/
829 g_queue_get_length(broadcast
->events
), 2.);
832 analysisData
->stats
->broadcastStdevSum
+= sqrt(y
);
835 if (syncState
->traceNb
== 2 && g_queue_get_length(broadcast
->events
)
841 e0
= g_queue_peek_head(broadcast
->events
);
842 e1
= g_queue_peek_tail(broadcast
->events
);
843 if (e0
->traceNum
> e1
->traceNum
)
852 dd
= wallTimeSub(&e1
->wallTime
, &e0
->wallTime
);
854 analysisData
->stats
->broadcastPairNb
++;
855 if (dd
< analysisData
->stats
->broadcastRangeMin
)
857 analysisData
->stats
->broadcastRangeMin
= dd
;
859 if (dd
> analysisData
->stats
->broadcastRangeMax
)
861 analysisData
->stats
->broadcastRangeMax
= dd
;
864 analysisData
->stats
->broadcastSum
+= dd
;
865 analysisData
->stats
->broadcastSumSquares
+= pow(dd
, 2);
869 if (syncState
->graphsStream
)
873 unsigned int eventNb
= broadcast
->events
->length
;
875 events
= g_array_sized_new(FALSE
, FALSE
, sizeof(Event
*), eventNb
);
876 g_queue_foreach(broadcast
->events
, &gfAddEventToArray
, events
);
878 for (i
= 0; i
< eventNb
; i
++)
880 for (j
= 0; j
< eventNb
; j
++)
882 Event
* eventI
= g_array_index(events
, Event
*, i
), * eventJ
=
883 g_array_index(events
, Event
*, j
);
885 if (eventI
->traceNum
< eventJ
->traceNum
)
887 updateBounds(analysisData
->graphs
->bounds
, eventI
, eventJ
);
892 g_array_free(events
, TRUE
);
898 * Finalize the factor calculations. Since this module does not really
899 * calculate factors, identity factors are returned. Instead, histograms are
900 * written out and histogram structures are freed.
903 * syncState container for synchronization data.
906 * Factors[traceNb] identity factors for each trace
908 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
)
912 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
914 if (syncState
->graphsStream
&& analysisData
->graphs
->histograms
)
916 g_hash_table_foreach(analysisData
->graphs
->histograms
,
917 &ghfWriteHistogram
, &(struct WriteHistogramInfo
) {.rttInfo
=
918 analysisData
->rttInfo
, .graphsStream
= syncState
->graphsStream
});
919 g_hash_table_destroy(analysisData
->graphs
->histograms
);
920 analysisData
->graphs
->histograms
= NULL
;
923 finalizeAnalysisEvalLP(syncState
);
925 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
927 g_array_set_size(factors
, syncState
->traceNb
);
928 for (i
= 0; i
< syncState
->traceNb
; i
++)
932 e
= &g_array_index(factors
, Factors
, i
);
942 * Print statistics related to analysis. Must be called after
946 * syncState container for synchronization data.
948 static void printAnalysisStatsEval(SyncState
* const syncState
)
950 AnalysisDataEval
* analysisData
;
951 unsigned int i
, j
, k
;
952 unsigned int totInversion
= 0, totTooFast
= 0, totNoInfo
= 0, totTotal
= 0;
955 if (!syncState
->stats
)
960 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
962 printf("Synchronization evaluation analysis stats:\n");
963 if (analysisData
->stats
->broadcastNb
)
965 printf("\tBroadcast differential delay:\n");
966 printf("\t\tsum of standard deviations: %g\n",
967 analysisData
->stats
->broadcastStdevSum
);
968 printf("\t\taverage standard deviation: %g\n",
969 analysisData
->stats
->broadcastStdevSum
/
970 analysisData
->stats
->broadcastNb
);
972 if (syncState
->traceNb
== 2)
974 printf("\t\tdifferential delay range: [ %g .. %g ]\n",
975 analysisData
->stats
->broadcastRangeMin
,
976 analysisData
->stats
->broadcastRangeMax
);
977 printf("\t\tdifferential delay average: %g\n",
978 analysisData
->stats
->broadcastSum
/
979 analysisData
->stats
->broadcastPairNb
);
980 printf("\t\tdifferential delay standard deviation: %g\n",
981 sqrt(analysisData
->stats
->broadcastSumSquares
/
982 analysisData
->stats
->broadcastPairNb
-
983 pow(analysisData
->stats
->broadcastSum
/
984 analysisData
->stats
->broadcastPairNb
, 2)));
988 printf("\tIndividual evaluation:\n"
989 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
991 for (i
= 0; i
< syncState
->traceNb
; i
++)
993 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
995 MessageStats
* messageStats
;
1003 for (k
= 0; k
< sizeof(loopValues
) / sizeof(*loopValues
); k
++)
1006 &analysisData
->stats
->messageStats
[loopValues
[k
].t1
][loopValues
[k
].t2
];
1008 printf("\t\t%3d - %-3d ", loopValues
[k
].t1
, loopValues
[k
].t2
);
1009 printf("%u (%.2f%%)%n", messageStats
->inversionNb
, (double)
1010 messageStats
->inversionNb
/ messageStats
->total
* 100,
1012 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
1013 printf("%u (%.2f%%)%n", messageStats
->tooFastNb
, (double)
1014 messageStats
->tooFastNb
/ messageStats
->total
* 100,
1016 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1:
1017 1, " ", messageStats
->noRTTInfoNb
, messageStats
->total
);
1019 totInversion
+= messageStats
->inversionNb
;
1020 totTooFast
+= messageStats
->tooFastNb
;
1021 totNoInfo
+= messageStats
->noRTTInfoNb
;
1022 totTotal
+= messageStats
->total
;
1027 printf("\t\t total ");
1028 printf("%u (%.2f%%)%n", totInversion
, (double) totInversion
/ totTotal
*
1030 printf("%*s", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ");
1031 printf("%u (%.2f%%)%n", totTooFast
, (double) totTooFast
/ totTotal
* 100,
1033 printf("%*s%-10u %u\n", 17 - charNb
> 0 ? 17 - charNb
+ 1: 1, " ",
1034 totNoInfo
, totTotal
);
1036 printf("\tRound-trip times:\n"
1037 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
1038 g_hash_table_foreach(analysisData
->stats
->exchangeRtt
,
1039 &ghfPrintExchangeRtt
, analysisData
->rttInfo
);
1042 printf("\tConvex hull factors comparisons:\n"
1043 "\t\tTrace pair Factors type Differences (lp - chull)\n"
1045 "\t\t Min Max Min Max\n");
1047 for (i
= 0; i
< syncState
->traceNb
; i
++)
1049 for (j
= 0; j
< i
; j
++)
1051 FactorsCHull
* chFactors
= &analysisData
->stats
->chFactorsArray
[i
][j
];
1052 FactorsCHull
* lpFactors
= &analysisData
->stats
->lpFactorsArray
[i
][j
];
1054 printf("\t\t%3d - %-3d ", i
, j
);
1055 if (lpFactors
->type
== chFactors
->type
)
1057 if (lpFactors
->type
== MIDDLE
)
1059 printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
1060 approxNames
[lpFactors
->type
],
1061 lpFactors
->min
->offset
- chFactors
->min
->offset
,
1062 lpFactors
->max
->offset
- chFactors
->max
->offset
,
1063 lpFactors
->min
->drift
- chFactors
->min
->drift
,
1064 lpFactors
->max
->drift
- chFactors
->max
->drift
);
1066 else if (lpFactors
->type
== ABSENT
)
1068 printf("%s\n", approxNames
[lpFactors
->type
]);
1073 printf("Different! %s and %s\n", approxNames
[lpFactors
->type
],
1074 approxNames
[chFactors
->type
]);
1083 * A GHFunc for g_hash_table_foreach()
1086 * key: RttKey* where saddr < daddr
1087 * value: double*, RTT estimated from exchanges
1088 * user_data GHashTable* rttInfo
1090 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer
1093 char addr1
[16], addr2
[16];
1094 struct RttKey
* rttKey1
= key
;
1095 struct RttKey rttKey2
= {rttKey1
->daddr
, rttKey1
->saddr
};
1096 double* fileRtt1
, *fileRtt2
;
1097 GHashTable
* rttInfo
= user_data
;
1099 convertIP(addr1
, rttKey1
->saddr
);
1100 convertIP(addr2
, rttKey1
->daddr
);
1102 fileRtt1
= g_hash_table_lookup(rttInfo
, rttKey1
);
1103 fileRtt2
= g_hash_table_lookup(rttInfo
, &rttKey2
);
1105 printf("\t\t(%15s, %-15s) %-18.3f ", addr1
, addr2
, *(double*) value
* 1e3
);
1107 if (fileRtt1
|| fileRtt2
)
1111 printf("%.3f", *fileRtt1
* 1e3
);
1113 if (fileRtt1
&& fileRtt2
)
1119 printf("%.3f", *fileRtt2
* 1e3
);
1131 * A GHashFunc for g_hash_table_new()
1134 * key struct RttKey*
1136 static guint
ghfRttKeyHash(gconstpointer key
)
1138 struct RttKey
* rttKey
;
1141 rttKey
= (struct RttKey
*) key
;
1153 * A GDestroyNotify function for g_hash_table_new_full()
1156 * data: struct RttKey*
1158 static void gdnDestroyRttKey(gpointer data
)
1165 * A GDestroyNotify function for g_hash_table_new_full()
1170 static void gdnDestroyDouble(gpointer data
)
1177 * A GEqualFunc for g_hash_table_new()
1183 * TRUE if both values are equal
1185 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
)
1187 const struct RttKey
* rkA
, * rkB
;
1189 rkA
= (struct RttKey
*) a
;
1190 rkB
= (struct RttKey
*) b
;
1192 if (rkA
->saddr
== rkB
->saddr
&& rkA
->daddr
== rkB
->daddr
)
1204 * Read a file contain minimum round trip time values and fill an array with
1205 * them. The file is formatted as such:
1206 * <host1 IP> <host2 IP> <RTT in milliseconds>
1207 * ip's should be in dotted quad format
1210 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
1211 * rttStream: stream from which to read
1213 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttStream
)
1219 positionStream(rttStream
);
1220 retval
= getline(&line
, &len
, rttStream
);
1221 while(!feof(rttStream
))
1223 struct RttKey
* rttKey
;
1224 char saddrDQ
[20], daddrDQ
[20];
1227 struct in_addr addr
;
1233 {saddrDQ
, offsetof(struct RttKey
, saddr
)},
1234 {daddrDQ
, offsetof(struct RttKey
, daddr
)}
1237 if (retval
== -1 && !feof(rttStream
))
1239 g_error(strerror(errno
));
1242 if (line
[retval
- 1] == '\n')
1244 line
[retval
- 1]= '\0';
1247 rtt
= malloc(sizeof(double));
1248 retval
= sscanf(line
, " %19s %19s %lf %c", saddrDQ
, daddrDQ
, rtt
,
1252 g_error(strerror(errno
));
1254 else if (retval
!= 3)
1256 g_error("Error parsing RTT file, line was '%s'", line
);
1259 rttKey
= malloc(sizeof(struct RttKey
));
1260 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
1262 retval
= inet_aton(loopValues
[i
].dq
, &addr
);
1265 g_error("Error converting address '%s'", loopValues
[i
].dq
);
1267 *(uint32_t*) ((void*) rttKey
+ loopValues
[i
].offset
)=
1272 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey
->saddr
,
1273 rttKey
->daddr
, *rtt
);
1274 g_hash_table_insert(rttInfo
, rttKey
, rtt
);
1276 positionStream(rttStream
);
1277 retval
= getline(&line
, &len
, rttStream
);
1288 * Advance stream over empty space, empty lines and lines that begin with '#'
1291 * stream: stream, at exit, will be over the first non-empty character
1292 * of a line of be at EOF
1294 static void positionStream(FILE* stream
)
1303 firstChar
= fgetc(stream
);
1304 if (firstChar
== (int) '#')
1306 retval
= getline(&line
, &len
, stream
);
1315 g_error(strerror(errno
));
1319 else if (firstChar
== (int) '\n' || firstChar
== (int) ' ' ||
1320 firstChar
== (int) '\t')
1322 else if (firstChar
== EOF
)
1331 retval
= ungetc(firstChar
, stream
);
1334 g_error("Error: ungetc()");
1346 * A GFunc for g_queue_foreach()
1349 * data Event*, a UDP broadcast event
1350 * user_data double*, the running sum
1353 * Adds the time of the event to the sum
1355 static void gfSum(gpointer data
, gpointer userData
)
1357 Event
* event
= (Event
*) data
;
1359 *(double*) userData
+= event
->wallTime
.seconds
+ event
->wallTime
.nanosec
/
1365 * A GFunc for g_queue_foreach()
1368 * data Event*, a UDP broadcast event
1369 * user_data double*, the running sum
1372 * Adds the square of the time of the event to the sum
1374 static void gfSumSquares(gpointer data
, gpointer userData
)
1376 Event
* event
= (Event
*) data
;
1378 *(double*) userData
+= pow(event
->wallTime
.seconds
+ event
->wallTime
.nanosec
1384 * Update a struct Bins according to a new value
1387 * bins: the structure containing bins to build a histrogram
1388 * value: the new value
1390 static void hitBin(struct Bins
* const bins
, const double value
)
1392 unsigned int binN
= binNum(value
);
1394 if (binN
< bins
->min
)
1398 else if (binN
> bins
->max
)
1410 * Figure out the bin in a histogram to which a value belongs.
1412 * This uses exponentially sized bins that go from 0 to infinity.
1415 * value: in the range -INFINITY to INFINITY
1418 * The number of the bin in a struct Bins.bin
1420 static unsigned int binNum(const double value
)
1426 else if (value
< binEnd(1))
1430 else if (value
>= binStart(BIN_NB
- 1))
1436 return floor(log(value
) / log(binBase
)) + BIN_NB
+ 1;
1442 * Figure out the start of the interval of a bin in a histogram. See struct
1445 * This uses exponentially sized bins that go from 0 to infinity.
1448 * binNum: bin number
1451 * The start of the interval, this value is included in the interval (except
1452 * for -INFINITY, naturally)
1454 static double binStart(const unsigned int binNum
)
1456 g_assert_cmpuint(binNum
, <, BIN_NB
);
1462 else if (binNum
== 1)
1468 return pow(binBase
, (double) binNum
- BIN_NB
+ 1);
1474 * Figure out the end of the interval of a bin in a histogram. See struct
1477 * This uses exponentially sized bins that go from 0 to infinity.
1480 * binNum: bin number
1483 * The end of the interval, this value is not included in the interval
1485 static double binEnd(const unsigned int binNum
)
1487 g_assert_cmpuint(binNum
, <, BIN_NB
);
1493 else if (binNum
< BIN_NB
- 1)
1495 return pow(binBase
, (double) binNum
- BIN_NB
+ 2);
1505 * Return the total number of elements in the "normal" bins (not underflow or
1509 * bins: the structure containing bins to build a histrogram
1511 static uint32_t normalTotal(struct Bins
* const bins
)
1513 return bins
->total
- bins
->bin
[0] - bins
->bin
[BIN_NB
- 1];
1517 /* Update the bounds between two traces
1520 * bounds: the array containing all the trace-pair bounds
1521 * e1, e2: the two related events
1523 static void updateBounds(Bounds
** const bounds
, Event
* const e1
, Event
* const
1526 unsigned int traceI
, traceJ
;
1527 uint64_t messageTime
;
1530 if (e1
->traceNum
< e2
->traceNum
)
1532 traceI
= e2
->traceNum
;
1533 traceJ
= e1
->traceNum
;
1534 messageTime
= e1
->cpuTime
;
1538 traceI
= e1
->traceNum
;
1539 traceJ
= e2
->traceNum
;
1540 messageTime
= e2
->cpuTime
;
1542 tpBounds
= &bounds
[traceI
][traceJ
];
1544 if (messageTime
< tpBounds
->min
)
1546 tpBounds
->min
= messageTime
;
1548 if (messageTime
> tpBounds
->max
)
1550 tpBounds
->max
= messageTime
;
1557 * Create the linear programming problem containing the constraints defined by
1558 * two half-hulls. The objective function and optimization directions are not
1562 * syncState: container for synchronization data
1563 * i: first trace number
1564 * j: second trace number, garanteed to be larger than i
1566 * A new glp_prob*, this problem must be freed by the caller with
1569 static glp_prob
* lpCreateProblem(GQueue
* const lowerHull
, GQueue
* const
1574 const double zeroD
= 0.;
1575 glp_prob
* lp
= glp_create_prob();
1576 unsigned int hullPointNb
= g_queue_get_length(lowerHull
) +
1577 g_queue_get_length(upperHull
);
1578 GArray
* iArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1580 GArray
* jArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(int), hullPointNb
+
1582 GArray
* aArray
= g_array_sized_new(FALSE
, FALSE
, sizeof(double),
1586 struct LPAddRowInfo rowInfo
;
1588 {lowerHull
, {lp
, GLP_UP
, iArray
, jArray
, aArray
}},
1589 {upperHull
, {lp
, GLP_LO
, iArray
, jArray
, aArray
}},
1592 // Create the LP problem
1593 glp_term_out(GLP_OFF
);
1594 if (hullPointNb
> 0)
1596 glp_add_rows(lp
, hullPointNb
);
1598 glp_add_cols(lp
, 2);
1600 glp_set_col_name(lp
, 1, "a0");
1601 glp_set_col_bnds(lp
, 1, GLP_FR
, 0., 0.);
1602 glp_set_col_name(lp
, 2, "a1");
1603 glp_set_col_bnds(lp
, 2, GLP_LO
, 0., 0.);
1605 // Add row constraints
1606 g_array_append_val(iArray
, zero
);
1607 g_array_append_val(jArray
, zero
);
1608 g_array_append_val(aArray
, zeroD
);
1610 for (it
= 0; it
< sizeof(loopValues
) / sizeof(*loopValues
); it
++)
1612 g_queue_foreach(loopValues
[it
].hull
, &gfLPAddRow
,
1613 &loopValues
[it
].rowInfo
);
1616 g_assert_cmpuint(iArray
->len
, ==, jArray
->len
);
1617 g_assert_cmpuint(jArray
->len
, ==, aArray
->len
);
1618 g_assert_cmpuint(aArray
->len
- 1, ==, hullPointNb
* 2);
1620 glp_load_matrix(lp
, aArray
->len
- 1, &g_array_index(iArray
, int, 0),
1621 &g_array_index(jArray
, int, 0), &g_array_index(aArray
, double, 0));
1623 glp_scale_prob(lp
, GLP_SF_AUTO
);
1625 g_array_free(iArray
, TRUE
);
1626 g_array_free(jArray
, TRUE
);
1627 g_array_free(aArray
, TRUE
);
1634 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1637 * data Point*, synchronization point for which to add an LP row
1639 * user_data LPAddRowInfo*
1641 static void gfLPAddRow(gpointer data
, gpointer user_data
)
1644 struct LPAddRowInfo
* rowInfo
= user_data
;
1646 double constraints
[2];
1648 indexes
[0]= g_array_index(rowInfo
->iArray
, int, rowInfo
->iArray
->len
- 1) + 1;
1649 indexes
[1]= indexes
[0];
1651 if (rowInfo
->boundType
== GLP_UP
)
1653 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_UP
, 0., p
->y
);
1655 else if (rowInfo
->boundType
== GLP_LO
)
1657 glp_set_row_bnds(rowInfo
->lp
, indexes
[0], GLP_LO
, p
->y
, 0.);
1661 g_assert_not_reached();
1664 g_array_append_vals(rowInfo
->iArray
, indexes
, 2);
1667 g_array_append_vals(rowInfo
->jArray
, indexes
, 2);
1669 constraints
[1]= p
->x
;
1670 g_array_append_vals(rowInfo
->aArray
, constraints
, 2);
1675 * Calculate min or max correction factors (as possible) using an LP problem.
1678 * lp: A linear programming problem with constraints and bounds
1680 * direction: The type of factors desired. Use GLP_MAX for max
1681 * approximation factors (a1, the drift or slope is the
1682 * largest) and GLP_MIN in the other case.
1685 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1686 * The calculation will fail if the hull assumptions are not respected.
1688 static Factors
* calculateFactors(glp_prob
* const lp
, const int direction
)
1693 glp_set_obj_coef(lp
, 1, 0.);
1694 glp_set_obj_coef(lp
, 2, 1.);
1696 glp_set_obj_dir(lp
, direction
);
1697 retval
= glp_simplex(lp
, NULL
);
1698 status
= glp_get_status(lp
);
1700 if (retval
== 0 && status
== GLP_OPT
)
1702 factors
= malloc(sizeof(Factors
));
1703 factors
->offset
= glp_get_col_prim(lp
, 1);
1704 factors
->drift
= glp_get_col_prim(lp
, 2);
1716 * Calculate min, max and approx correction factors (as possible) using an LP
1720 * lp: A linear programming problem with constraints and bounds
1724 * Please note that the approximation type may be MIDDLE, INCOMPLETE or
1725 * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do
1726 * not respect assumptions.
1728 static void calculateCompleteFactors(glp_prob
* const lp
, FactorsCHull
* factors
)
1730 factors
->min
= calculateFactors(lp
, GLP_MIN
);
1731 factors
->max
= calculateFactors(lp
, GLP_MAX
);
1733 if (factors
->min
&& factors
->max
)
1735 factors
->type
= MIDDLE
;
1736 calculateFactorsMiddle(factors
);
1738 else if (factors
->min
|| factors
->max
)
1740 factors
->type
= INCOMPLETE
;
1741 factors
->approx
= NULL
;
1745 factors
->type
= ABSENT
;
1746 factors
->approx
= NULL
;
1752 * Create and initialize an array like AnalysisStatsCHull.allFactors
1755 * traceNb: number of traces
1758 * A new array, which can be freed with freeAllFactors()
1760 static FactorsCHull
** createAllFactors(const unsigned int traceNb
)
1762 FactorsCHull
** factorsArray
;
1765 factorsArray
= malloc(traceNb
* sizeof(FactorsCHull
*));
1766 for (i
= 0; i
< traceNb
; i
++)
1768 factorsArray
[i
]= calloc((i
+ 1), sizeof(FactorsCHull
));
1770 factorsArray
[i
][i
].type
= EXACT
;
1771 factorsArray
[i
][i
].approx
= malloc(sizeof(Factors
));
1772 factorsArray
[i
][i
].approx
->drift
= 1.;
1773 factorsArray
[i
][i
].approx
->offset
= 0.;
1776 return factorsArray
;
1781 * A GFunc for g_queue_foreach()
1784 * data Point*, a convex hull point
1785 * user_data GArray*, an array of convex hull point absisca values, as
1788 static void gfAddAbsiscaToArray(gpointer data
, gpointer user_data
)
1791 GArray
* a
= user_data
;
1794 g_array_append_val(a
, v
);
1799 * A GCompareFunc for g_array_sort()
1802 * a, b double*, absisca values
1805 * "returns less than zero for first arg is less than second arg, zero for
1806 * equal, greater zero if first arg is greater than second arg"
1807 * - the great glib documentation
1809 static gint
gcfCompareDouble(gconstpointer a
, gconstpointer b
)
1811 if (*(double*) a
< *(double*) b
)
1815 else if (*(double*) a
> *(double*) b
)
1828 * Compute synchronization factors using a linear programming approach.
1829 * Compute the factors using analysis_chull. Compare the two.
1831 * When the solver library, glpk, is not available at build time, only compute
1832 * the factors using analysis_chull. This is to make sure that module runs its
1833 * finalize function so that its graph functions can be called later.
1836 * syncState: container for synchronization data
1838 static void finalizeAnalysisEvalLP(SyncState
* const syncState
)
1840 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
1843 AnalysisDataCHull
* chAnalysisData
= analysisData
->chullSS
->analysisData
;
1844 FactorsCHull
** lpFactorsArray
;
1846 if (!syncState
->stats
&& !syncState
->graphsStream
)
1851 /* Because of matching_distributor, this analysis may be called twice.
1852 * Only run it once */
1853 if ((syncState
->graphsStream
&& analysisData
->graphs
->lps
!= NULL
) ||
1854 (syncState
->stats
&& analysisData
->stats
->chFactorsArray
!= NULL
))
1859 lpFactorsArray
= createAllFactors(syncState
->traceNb
);
1861 if (syncState
->stats
)
1863 analysisData
->stats
->chFactorsArray
=
1864 calculateAllFactors(analysisData
->chullSS
);
1865 analysisData
->stats
->lpFactorsArray
= lpFactorsArray
;
1868 if (syncState
->graphsStream
)
1870 analysisData
->graphs
->lps
= malloc(syncState
->traceNb
*
1871 sizeof(glp_prob
**));
1872 for (i
= 0; i
< syncState
->traceNb
; i
++)
1874 analysisData
->graphs
->lps
[i
]= malloc(i
* sizeof(glp_prob
*));
1876 analysisData
->graphs
->lpFactorsArray
= lpFactorsArray
;
1879 for (i
= 0; i
< syncState
->traceNb
; i
++)
1881 for (j
= 0; j
< i
; j
++)
1885 // Create the LP problem
1886 lp
= lpCreateProblem(chAnalysisData
->hullArray
[i
][j
],
1887 chAnalysisData
->hullArray
[j
][i
]);
1889 // Use the LP problem to find the correction factors for this pair of
1891 calculateCompleteFactors(lp
, &lpFactorsArray
[i
][j
]);
1893 if (syncState
->graphsStream
)
1895 analysisData
->graphs
->lps
[i
][j
]= lp
;
1899 glp_delete_prob(lp
);
1905 g_array_free(analysisData
->chullSS
->analysisModule
->finalizeAnalysis(analysisData
->chullSS
),
1911 * Compute synchronization accuracy information using a linear programming
1912 * approach. Write the neccessary data files and plot lines in the gnuplot
1915 * When the solver library, glpk, is not available at build time nothing is
1916 * actually produced.
1919 * syncState: container for synchronization data
1920 * i: first trace number
1921 * j: second trace number, garanteed to be larger than i
1923 static void writeAnalysisTraceTimeBackPlotsEval(SyncState
* const syncState
,
1924 const unsigned int i
, const unsigned int j
)
1928 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
1929 AnalysisGraphsEval
* graphs
= analysisData
->graphs
;
1930 GQueue
*** hullArray
= ((AnalysisDataCHull
*)
1931 analysisData
->chullSS
->analysisData
)->hullArray
;
1932 FactorsCHull
* lpFactors
= &graphs
->lpFactorsArray
[j
][i
];
1933 glp_prob
* lp
= graphs
->lps
[j
][i
];
1935 if (lpFactors
->type
== MIDDLE
)
1943 // Open the data file
1944 snprintf(fileName
, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i
, j
);
1945 fileName
[sizeof(fileName
) - 1]= '\0';
1947 cwd
= changeToGraphsDir(syncState
->graphsDir
);
1949 if ((fp
= fopen(fileName
, "w")) == NULL
)
1951 g_error(strerror(errno
));
1953 fprintf(fp
, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1958 g_error(strerror(errno
));
1962 // Build the list of absisca values for the points in the accuracy graph
1963 xValues
= g_array_sized_new(FALSE
, FALSE
, sizeof(double),
1964 g_queue_get_length(hullArray
[i
][j
]) +
1965 g_queue_get_length(hullArray
[j
][i
]));
1967 g_queue_foreach(hullArray
[i
][j
], &gfAddAbsiscaToArray
, xValues
);
1968 g_queue_foreach(hullArray
[j
][i
], &gfAddAbsiscaToArray
, xValues
);
1970 g_array_sort(xValues
, &gcfCompareDouble
);
1972 /* For each absisca value and each optimisation direction, solve the LP
1973 * and write a line in the data file */
1974 for (it
= 0; it
< xValues
->len
; it
++)
1977 int directions
[]= {GLP_MIN
, GLP_MAX
};
1978 glp_set_obj_coef(lp
, 1, 1.);
1979 glp_set_obj_coef(lp
, 2, g_array_index(xValues
, double, it
));
1981 fprintf(fp
, "%25.9f %25.9f", g_array_index(xValues
, double, it
),
1982 lpFactors
->approx
->offset
+ lpFactors
->approx
->drift
*
1983 g_array_index(xValues
, double, it
));
1984 for (it2
= 0; it2
< sizeof(directions
) / sizeof(*directions
); it2
++)
1988 glp_set_obj_dir(lp
, directions
[it2
]);
1989 retval
= glp_simplex(lp
, NULL
);
1990 status
= glp_get_status(lp
);
1992 g_assert(retval
== 0 && status
== GLP_OPT
);
1993 fprintf(fp
, " %25.9f", glp_get_obj_val(lp
));
1998 g_array_free(xValues
, TRUE
);
2001 fprintf(syncState
->graphsStream
,
2002 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
2003 "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
2004 "title \"Synchronization accuracy\" "
2005 "with filledcurves linewidth 2 linetype 1 "
2006 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
,
2014 * Write the analysis-specific graph lines in the gnuplot script.
2016 * When the solver library, glpk, is not available at build time nothing is
2017 * actually produced.
2020 * syncState: container for synchronization data
2021 * i: first trace number
2022 * j: second trace number, garanteed to be larger than i
2024 static void writeAnalysisTraceTimeForePlotsEval(SyncState
* const syncState
,
2025 const unsigned int i
, const unsigned int j
)
2028 if (((AnalysisDataEval
*)
2029 syncState
->analysisData
)->graphs
->lpFactorsArray
[j
][i
].type
==
2032 fprintf(syncState
->graphsStream
,
2033 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
2034 "using 1:(($3 - $2) / clock_freq_%2$u) notitle "
2035 "with lines linewidth 2 linetype 1 "
2036 "linecolor rgb \"gray60\", \\\n"
2037 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
2038 "using 1:(($4 - $2) / clock_freq_%2$u) notitle "
2039 "with lines linewidth 2 linetype 1 "
2040 "linecolor rgb \"gray60\", \\\n", i
, j
);
2047 * Write the analysis-specific graph lines in the gnuplot script.
2050 * syncState: container for synchronization data
2051 * i: first trace number
2052 * j: second trace number, garanteed to be larger than i
2054 static void writeAnalysisTraceTraceBackPlotsEval(SyncState
* const syncState
,
2055 const unsigned int i
, const unsigned int j
)
2058 fprintf(syncState
->graphsStream
,
2059 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
2061 "title \"Synchronization accuracy\" "
2062 "with filledcurves linewidth 2 linetype 1 "
2063 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i
, j
);
2069 * Write the analysis-specific graph lines in the gnuplot script.
2072 * syncState: container for synchronization data
2073 * i: first trace number
2074 * j: second trace number, garanteed to be larger than i
2076 static void writeAnalysisTraceTraceForePlotsEval(SyncState
* const syncState
,
2077 const unsigned int i
, const unsigned int j
)
2079 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
2081 analysisData
->chullSS
->analysisModule
->graphFunctions
.writeTraceTraceForePlots(analysisData
->chullSS
,