projects / lttv.git / blob
? search:


45bad57c57ba3d907d48151929312e97c00c0c77
[lttv.git] / lttv / lttv / sync / event_analysis_eval.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 *
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.
8 *
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.
13 *
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/>.
16 */
17
18 #define _GNU_SOURCE
19 #define _ISOC99_SOURCE
20
21 #ifdef HAVE_CONFIG_H
22 #include <config.h>
23 #endif
24
25 #include <arpa/inet.h>
26 #include <errno.h>
27 #include <math.h>
28 #include <netinet/in.h>
29 #include <stddef.h>
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33 #include <sys/socket.h>
34 #include <unistd.h>
35
36 #include "lookup3.h"
37 #include "sync_chain.h"
38 #include "event_analysis_chull.h"
39
40 #include "event_analysis_eval.h"
41
42
43 struct WriteHistogramInfo
44 {
45 GHashTable* rttInfo;
46 FILE* graphsStream;
47 };
48
49 #ifdef HAVE_LIBGLPK
50 struct LPAddRowInfo
51 {
52 glp_prob* lp;
53 int boundType;
54 GArray* iArray, * jArray, * aArray;
55 };
56 #endif
57
58 // Functions common to all analysis modules
59 static void initAnalysisEval(SyncState* const syncState);
60 static void destroyAnalysisEval(SyncState* const syncState);
61
62 static void analyzeMessageEval(SyncState* const syncState, Message* const
63 message);
64 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
65 exchange);
66 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
67 broadcast);
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);
78
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);
86
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
90 user_data);
91
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));
97
98 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
99 graphsDir, const struct RttKey* const rttKey);
100 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
101 histogram);
102 static void gdnDestroyAnalysisHistogramEval(gpointer data);
103 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer
104 user_data);
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);
108
109 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
110 e2);
111
112 static void finalizeAnalysisEvalLP(SyncState* const syncState);
113 // The next group of functions is only needed when computing synchronization
114 // accuracy.
115 #ifdef HAVE_LIBGLPK
116 static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
117 upperHull);
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*
121 factors);
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);
126 #else
127 static void finalizeAnalysisEvalLP(SyncState* const syncState);
128 #endif
129
130
131 // initialized in registerAnalysisEval()
132 double binBase;
133
134 static AnalysisModule analysisModuleEval= {
135 .name= "eval",
136 .initAnalysis= &initAnalysisEval,
137 .destroyAnalysis= &destroyAnalysisEval,
138 .analyzeMessage= &analyzeMessageEval,
139 .analyzeExchange= &analyzeExchangeEval,
140 .analyzeBroadcast= &analyzeBroadcastEval,
141 .finalizeAnalysis= &finalizeAnalysisEval,
142 .printAnalysisStats= &printAnalysisStatsEval,
143 .graphFunctions= {
144 .writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsEval,
145 .writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsEval,
146 .writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsEval,
147 .writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsEval,
148 }
149 };
150
151 static ModuleOption optionEvalRttFile= {
152 .longName= "eval-rtt-file",
153 .hasArg= REQUIRED_ARG,
154 .optionHelp= "specify the file containing RTT information",
155 .argHelp= "FILE",
156 };
157
158
159 /*
160 * Analysis module registering function
161 */
162 void registerAnalysisEval()
163 {
164 binBase= exp10(6. / (BIN_NB - 3));
165
166 g_queue_push_tail(&analysisModules, &analysisModuleEval);
167 g_queue_push_tail(&moduleOptions, &optionEvalRttFile);
168 }
169
170
171 /*
172 * Analysis init function
173 *
174 * This function is called at the beginning of a synchronization run for a set
175 * of traces.
176 *
177 * Args:
178 * syncState container for synchronization data.
179 */
180 static void initAnalysisEval(SyncState* const syncState)
181 {
182 AnalysisDataEval* analysisData;
183 unsigned int i, j;
184
185 analysisData= malloc(sizeof(AnalysisDataEval));
186 syncState->analysisData= analysisData;
187
188 analysisData->rttInfo= g_hash_table_new_full(&ghfRttKeyHash,
189 &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble);
190 if (optionEvalRttFile.arg)
191 {
192 FILE* rttStream;
193 int retval;
194
195 rttStream= fopen(optionEvalRttFile.arg, "r");
196 if (rttStream == NULL)
197 {
198 g_error(strerror(errno));
199 }
200
201 readRttInfo(analysisData->rttInfo, rttStream);
202
203 retval= fclose(rttStream);
204 if (retval == EOF)
205 {
206 g_error(strerror(errno));
207 }
208 }
209
210 if (syncState->stats)
211 {
212 analysisData->stats= calloc(1, sizeof(AnalysisStatsEval));
213 analysisData->stats->broadcastRangeMin= INFINITY;
214 analysisData->stats->broadcastRangeMax= -INFINITY;
215
216 analysisData->stats->messageStats= malloc(syncState->traceNb *
217 sizeof(MessageStats*));
218 for (i= 0; i < syncState->traceNb; i++)
219 {
220 analysisData->stats->messageStats[i]= calloc(syncState->traceNb,
221 sizeof(MessageStats));
222 }
223
224 analysisData->stats->exchangeRtt=
225 g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual,
226 &gdnDestroyRttKey, &gdnDestroyDouble);
227
228 #ifdef HAVE_LIBGLPK
229 analysisData->stats->chFactorsArray= NULL;
230 analysisData->stats->lpFactorsArray= NULL;
231 #endif
232 }
233
234 if (syncState->graphsStream)
235 {
236 AnalysisGraphsEval* graphs= malloc(sizeof(AnalysisGraphsEval));
237
238 analysisData->graphs= graphs;
239
240 graphs->histograms= g_hash_table_new_full(&ghfRttKeyHash,
241 &gefRttKeyEqual, &gdnDestroyRttKey,
242 &gdnDestroyAnalysisHistogramEval);
243
244 graphs->bounds= malloc(syncState->traceNb * sizeof(Bounds*));
245 for (i= 0; i < syncState->traceNb; i++)
246 {
247 graphs->bounds[i]= malloc(i * sizeof(Bounds));
248 for (j= 0; j < i; j++)
249 {
250 graphs->bounds[i][j].min= UINT64_MAX;
251 graphs->bounds[i][j].max= 0;
252 }
253 }
254
255 #ifdef HAVE_LIBGLPK
256 graphs->lps= NULL;
257 graphs->lpFactorsArray= NULL;
258 #endif
259 }
260
261 if (syncState->stats || syncState->graphsStream)
262 {
263 GList* result;
264
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);
273 }
274 }
275
276
277 /*
278 * Create and open files used to store histogram points to generate graphs.
279 * Create data structures to store histogram points during analysis.
280 *
281 * Args:
282 * graphsDir: folder where to write files
283 * rttKey: host pair, make sure saddr < daddr
284 */
285 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
286 graphsDir, const struct RttKey* const rttKey)
287 {
288 int retval;
289 unsigned int i;
290 char* cwd;
291 char name[60], saddr[16], daddr[16];
292 AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram));
293 const struct {
294 size_t pointsOffset;
295 const char* fileName;
296 const char* host1, *host2;
297 } loopValues[]= {
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},
304 };
305
306 histogram->ttSendBins.min= BIN_NB - 1;
307 histogram->ttRecvBins.min= BIN_NB - 1;
308 histogram->hrttBins.min= BIN_NB - 1;
309
310 convertIP(saddr, rttKey->saddr);
311 convertIP(daddr, rttKey->daddr);
312
313 cwd= changeToGraphsDir(graphsDir);
314
315 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
316 {
317 retval= snprintf(name, sizeof(name), loopValues[i].fileName,
318 loopValues[i].host1, loopValues[i].host2);
319 if (retval > sizeof(name) - 1)
320 {
321 name[sizeof(name) - 1]= '\0';
322 }
323 if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)=
324 fopen(name, "w")) == NULL)
325 {
326 g_error(strerror(errno));
327 }
328 }
329
330 retval= chdir(cwd);
331 if (retval == -1)
332 {
333 g_error(strerror(errno));
334 }
335 free(cwd);
336
337 return histogram;
338 }
339
340
341 /*
342 * Close files used to store histogram points to generate graphs.
343 *
344 * Args:
345 * graphsDir: folder where to write files
346 * rttKey: host pair, make sure saddr < daddr
347 */
348 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
349 histogram)
350 {
351 unsigned int i;
352 int retval;
353 const struct {
354 size_t pointsOffset;
355 } loopValues[]= {
356 {offsetof(AnalysisHistogramEval, ttSendPoints)},
357 {offsetof(AnalysisHistogramEval, ttRecvPoints)},
358 {offsetof(AnalysisHistogramEval, hrttPoints)},
359 };
360
361 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
362 {
363 retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset));
364 if (retval != 0)
365 {
366 g_error(strerror(errno));
367 }
368 }
369
370 free(histogram);
371 }
372
373
374 /*
375 * A GDestroyNotify function for g_hash_table_new_full()
376 *
377 * Args:
378 * data: AnalysisHistogramEval*
379 */
380 static void gdnDestroyAnalysisHistogramEval(gpointer data)
381 {
382 destroyAnalysisHistogramEval(data);
383 }
384
385
386 /*
387 * A GHFunc for g_hash_table_foreach()
388 *
389 * Args:
390 * key: RttKey* where saddr < daddr
391 * value: AnalysisHistogramEval*
392 * user_data struct WriteHistogramInfo*
393 */
394 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer user_data)
395 {
396 double* rtt1, * rtt2;
397 struct RttKey* rttKey= key;
398 struct RttKey oppositeRttKey= {.saddr= rttKey->daddr, .daddr=
399 rttKey->saddr};
400 AnalysisHistogramEval* histogram= value;
401 struct WriteHistogramInfo* info= user_data;
402
403 rtt1= g_hash_table_lookup(info->rttInfo, rttKey);
404 rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey);
405
406 if (rtt1 == NULL)
407 {
408 rtt1= rtt2;
409 }
410 else if (rtt2 != NULL)
411 {
412 rtt1= MIN(rtt1, rtt2);
413 }
414
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);
419 }
420
421
422 /*
423 * Write the content of one bin in a histogram point file
424 *
425 * Args:
426 * bin: array of values that make up a histogram
427 * file: FILE*, write to this file
428 */
429 static void dumpBinToFile(const struct Bins* const bins, FILE* const file)
430 {
431 unsigned int i;
432
433 // The first and last bins are skipped, see struct Bins
434 for (i= 1; i < BIN_NB - 1; i++)
435 {
436 if (bins->bin[i] > 0)
437 {
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));
441 }
442 }
443 }
444
445
446 /*
447 * Write the analysis-specific plot in the gnuplot script.
448 *
449 * Args:
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
455 */
456 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
457 double* minRtt, AnalysisHistogramEval* const histogram)
458 {
459 char saddr[16], daddr[16];
460
461 convertIP(saddr, rttKey->saddr);
462 convertIP(daddr, rttKey->daddr);
463
464 fprintf(graphsStream,
465 "\nreset\n"
466 "set output \"histogram-%s-%s.eps\"\n"
467 "set title \"\"\n"
468 "set xlabel \"Message Latency (s)\"\n"
469 "set ylabel \"Proportion of messages per second\"\n", saddr, daddr);
470
471 if (minRtt != NULL)
472 {
473 fprintf(graphsStream,
474 "set arrow from %.9f, 0 rto 0, graph 1 "
475 "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
476 / 2);
477 }
478
479 if (normalTotal(&histogram->ttSendBins) ||
480 normalTotal(&histogram->ttRecvBins) ||
481 normalTotal(&histogram->hrttBins))
482 {
483 fprintf(graphsStream, "plot \\\n");
484
485 if (normalTotal(&histogram->hrttBins))
486 {
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",
491 saddr, daddr);
492 }
493
494 if (normalTotal(&histogram->ttSendBins))
495 {
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",
500 saddr, daddr);
501 }
502
503 if (normalTotal(&histogram->ttRecvBins))
504 {
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",
509 daddr, saddr);
510 }
511
512 // Remove the ",\\\n" from the last graph plot line
513 if (ftruncate(fileno(graphsStream), ftell(graphsStream) - 3) == -1)
514 {
515 g_error(strerror(errno));
516 }
517 if (fseek(graphsStream, 0, SEEK_END) == -1)
518 {
519 g_error(strerror(errno));
520 }
521 fprintf(graphsStream, "\n");
522 }
523 }
524
525
526 /*
527 * Analysis destroy function
528 *
529 * Free the analysis specific data structures
530 *
531 * Args:
532 * syncState container for synchronization data.
533 */
534 static void destroyAnalysisEval(SyncState* const syncState)
535 {
536 unsigned int i;
537 AnalysisDataEval* analysisData;
538
539 analysisData= (AnalysisDataEval*) syncState->analysisData;
540
541 if (analysisData == NULL)
542 {
543 return;
544 }
545
546 g_hash_table_destroy(analysisData->rttInfo);
547
548 if (syncState->stats)
549 {
550 AnalysisStatsEval* stats= analysisData->stats;
551
552 for (i= 0; i < syncState->traceNb; i++)
553 {
554 free(stats->messageStats[i]);
555 }
556 free(stats->messageStats);
557
558 g_hash_table_destroy(stats->exchangeRtt);
559
560 #ifdef HAVE_LIBGLPK
561 freeAllFactors(syncState->traceNb, stats->chFactorsArray);
562 freeAllFactors(syncState->traceNb, stats->lpFactorsArray);
563 #endif
564
565 free(stats);
566 }
567
568 if (syncState->graphsStream)
569 {
570 AnalysisGraphsEval* graphs= analysisData->graphs;
571
572 if (graphs->histograms)
573 {
574 g_hash_table_destroy(graphs->histograms);
575 }
576
577 for (i= 0; i < syncState->traceNb; i++)
578 {
579 free(graphs->bounds[i]);
580 }
581 free(graphs->bounds);
582
583 #ifdef HAVE_LIBGLPK
584 for (i= 0; i < syncState->traceNb; i++)
585 {
586 unsigned int j;
587
588 for (j= 0; j < i; j++)
589 {
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]);
593 }
594 free(graphs->lps[i]);
595 }
596 free(graphs->lps);
597
598 if (!syncState->stats)
599 {
600 freeAllFactors(syncState->traceNb, graphs->lpFactorsArray);
601 }
602 #endif
603
604 free(graphs);
605 }
606
607 if (syncState->stats || syncState->graphsStream)
608 {
609 analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS);
610 free(analysisData->chullSS);
611 }
612
613 free(syncState->analysisData);
614 syncState->analysisData= NULL;
615 }
616
617
618 /*
619 * Perform analysis on an event pair.
620 *
621 * Check if there is message inversion or messages that are too fast.
622 *
623 * Args:
624 * syncState container for synchronization data
625 * message structure containing the events
626 */
627 static void analyzeMessageEval(SyncState* const syncState, Message* const
628 message)
629 {
630 AnalysisDataEval* analysisData= syncState->analysisData;
631 MessageStats* messageStats;
632 double* rtt;
633 double tt;
634 struct RttKey rttKey;
635
636 g_assert(message->inE->type == TCP);
637
638 if (syncState->stats)
639 {
640 messageStats=
641 &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
642 messageStats->total++;
643 }
644
645 tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
646 if (tt <= 0)
647 {
648 if (syncState->stats)
649 {
650 messageStats->inversionNb++;
651 }
652 }
653 else if (syncState->graphsStream)
654 {
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),
660 };
661 AnalysisHistogramEval* histogram=
662 g_hash_table_lookup(analysisData->graphs->histograms, &rttKey);
663
664 if (histogram == NULL)
665 {
666 struct RttKey* tableKey= malloc(sizeof(*tableKey));
667
668 histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey);
669 memcpy(tableKey, &rttKey, sizeof(*tableKey));
670 g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram);
671 }
672
673 if (message->inE->event.udpEvent->datagramKey->saddr <
674 message->inE->event.udpEvent->datagramKey->daddr)
675 {
676 hitBin(&histogram->ttSendBins, tt);
677 }
678 else
679 {
680 hitBin(&histogram->ttRecvBins, tt);
681 }
682 }
683
684 if (syncState->stats)
685 {
686 rttKey.saddr=
687 message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
688 rttKey.daddr=
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);
693
694 if (rtt)
695 {
696 g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
697 if (tt < *rtt / 2.)
698 {
699 messageStats->tooFastNb++;
700 }
701 }
702 else
703 {
704 messageStats->noRTTInfoNb++;
705 }
706 }
707
708 if (syncState->graphsStream)
709 {
710 updateBounds(analysisData->graphs->bounds, message->inE,
711 message->outE);
712 }
713
714 if (syncState->stats || syncState->graphsStream)
715 {
716 analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS,
717 message);
718 }
719 }
720
721
722 /*
723 * Perform analysis on multiple messages
724 *
725 * Measure the RTT
726 *
727 * Args:
728 * syncState container for synchronization data
729 * exchange structure containing the messages
730 */
731 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
732 exchange)
733 {
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;
739
740 g_assert(m1->inE->type == TCP);
741
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);
746
747 rttKey= malloc(sizeof(struct RttKey));
748 rttKey->saddr=
749 MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
750 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
751 rttKey->daddr=
752 MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
753 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
754
755 if (syncState->graphsStream)
756 {
757 AnalysisHistogramEval* histogram=
758 g_hash_table_lookup(analysisData->graphs->histograms, rttKey);
759
760 if (histogram == NULL)
761 {
762 struct RttKey* tableKey= malloc(sizeof(*tableKey));
763
764 histogram= constructAnalysisHistogramEval(syncState->graphsDir,
765 rttKey);
766 memcpy(tableKey, rttKey, sizeof(*tableKey));
767 g_hash_table_insert(analysisData->graphs->histograms, tableKey,
768 histogram);
769 }
770
771 hitBin(&histogram->hrttBins, *rtt / 2);
772 }
773
774 if (syncState->stats)
775 {
776 exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
777 rttKey);
778
779 if (exchangeRtt)
780 {
781 if (*rtt < *exchangeRtt)
782 {
783 g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
784 }
785 else
786 {
787 free(rttKey);
788 free(rtt);
789 }
790 }
791 else
792 {
793 g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
794 }
795 }
796 else
797 {
798 free(rttKey);
799 free(rtt);
800 }
801 }
802
803
804 /*
805 * Perform analysis on muliple events
806 *
807 * Sum the broadcast differential delays
808 *
809 * Args:
810 * syncState container for synchronization data
811 * broadcast structure containing the events
812 */
813 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
814 broadcast)
815 {
816 AnalysisDataEval* analysisData= syncState->analysisData;
817
818 if (syncState->stats)
819 {
820 double sum= 0, squaresSum= 0;
821 double y;
822
823 g_queue_foreach(broadcast->events, &gfSum, &sum);
824 g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
825
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.);
830 if (y > 0)
831 {
832 analysisData->stats->broadcastStdevSum+= sqrt(y);
833 }
834
835 if (syncState->traceNb == 2 && g_queue_get_length(broadcast->events)
836 == 2)
837 {
838 Event* e0, * e1;
839 double dd;
840
841 e0= g_queue_peek_head(broadcast->events);
842 e1= g_queue_peek_tail(broadcast->events);
843 if (e0->traceNum > e1->traceNum)
844 {
845 Event* tmp;
846
847 tmp= e0;
848 e0= e1;
849 e1= tmp;
850 }
851
852 dd= wallTimeSub(&e1->wallTime, &e0->wallTime);
853
854 analysisData->stats->broadcastPairNb++;
855 if (dd < analysisData->stats->broadcastRangeMin)
856 {
857 analysisData->stats->broadcastRangeMin= dd;
858 }
859 if (dd > analysisData->stats->broadcastRangeMax)
860 {
861 analysisData->stats->broadcastRangeMax= dd;
862 }
863
864 analysisData->stats->broadcastSum+= dd;
865 analysisData->stats->broadcastSumSquares+= pow(dd, 2);
866 }
867 }
868
869 if (syncState->graphsStream)
870 {
871 unsigned int i, j;
872 GArray* events;
873 unsigned int eventNb= broadcast->events->length;
874
875 events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb);
876 g_queue_foreach(broadcast->events, &gfAddEventToArray, events);
877
878 for (i= 0; i < eventNb; i++)
879 {
880 for (j= 0; j < eventNb; j++)
881 {
882 Event* eventI= g_array_index(events, Event*, i), * eventJ=
883 g_array_index(events, Event*, j);
884
885 if (eventI->traceNum < eventJ->traceNum)
886 {
887 updateBounds(analysisData->graphs->bounds, eventI, eventJ);
888 }
889 }
890 }
891
892 g_array_free(events, TRUE);
893 }
894 }
895
896
897 /*
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.
901 *
902 * Args:
903 * syncState container for synchronization data.
904 *
905 * Returns:
906 * Factors[traceNb] identity factors for each trace
907 */
908 static GArray* finalizeAnalysisEval(SyncState* const syncState)
909 {
910 GArray* factors;
911 unsigned int i;
912 AnalysisDataEval* analysisData= syncState->analysisData;
913
914 if (syncState->graphsStream && analysisData->graphs->histograms)
915 {
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;
921 }
922
923 finalizeAnalysisEvalLP(syncState);
924
925 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
926 syncState->traceNb);
927 g_array_set_size(factors, syncState->traceNb);
928 for (i= 0; i < syncState->traceNb; i++)
929 {
930 Factors* e;
931
932 e= &g_array_index(factors, Factors, i);
933 e->drift= 1.;
934 e->offset= 0.;
935 }
936
937 return factors;
938 }
939
940
941 /*
942 * Print statistics related to analysis. Must be called after
943 * finalizeAnalysis.
944 *
945 * Args:
946 * syncState container for synchronization data.
947 */
948 static void printAnalysisStatsEval(SyncState* const syncState)
949 {
950 AnalysisDataEval* analysisData;
951 unsigned int i, j, k;
952 unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0;
953 int charNb;
954
955 if (!syncState->stats)
956 {
957 return;
958 }
959
960 analysisData= (AnalysisDataEval*) syncState->analysisData;
961
962 printf("Synchronization evaluation analysis stats:\n");
963 if (analysisData->stats->broadcastNb)
964 {
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);
971
972 if (syncState->traceNb == 2)
973 {
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)));
985 }
986 }
987
988 printf("\tIndividual evaluation:\n"
989 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
990
991 for (i= 0; i < syncState->traceNb; i++)
992 {
993 for (j= i + 1; j < syncState->traceNb; j++)
994 {
995 MessageStats* messageStats;
996 struct {
997 unsigned int t1, t2;
998 } loopValues[]= {
999 {i, j},
1000 {j, i}
1001 };
1002
1003 for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++)
1004 {
1005 messageStats=
1006 &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
1007
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,
1011 &charNb);
1012 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
1013 printf("%u (%.2f%%)%n", messageStats->tooFastNb, (double)
1014 messageStats->tooFastNb / messageStats->total * 100,
1015 &charNb);
1016 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
1017 1, " ", messageStats->noRTTInfoNb, messageStats->total);
1018
1019 totInversion+= messageStats->inversionNb;
1020 totTooFast+= messageStats->tooFastNb;
1021 totNoInfo+= messageStats->noRTTInfoNb;
1022 totTotal+= messageStats->total;
1023 }
1024 }
1025 }
1026
1027 printf("\t\t total ");
1028 printf("%u (%.2f%%)%n", totInversion, (double) totInversion / totTotal *
1029 100, &charNb);
1030 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
1031 printf("%u (%.2f%%)%n", totTooFast, (double) totTooFast / totTotal * 100,
1032 &charNb);
1033 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
1034 totNoInfo, totTotal);
1035
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);
1040
1041 #ifdef HAVE_LIBGLPK
1042 printf("\tConvex hull factors comparisons:\n"
1043 "\t\tTrace pair Factors type Differences (lp - chull)\n"
1044 "\t\t a0 a1\n"
1045 "\t\t Min Max Min Max\n");
1046
1047 for (i= 0; i < syncState->traceNb; i++)
1048 {
1049 for (j= 0; j < i; j++)
1050 {
1051 FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j];
1052 FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[i][j];
1053
1054 printf("\t\t%3d - %-3d ", i, j);
1055 if (lpFactors->type == chFactors->type)
1056 {
1057 if (lpFactors->type == MIDDLE)
1058 {
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);
1065 }
1066 else if (lpFactors->type == ABSENT)
1067 {
1068 printf("%s\n", approxNames[lpFactors->type]);
1069 }
1070 }
1071 else
1072 {
1073 printf("Different! %s and %s\n", approxNames[lpFactors->type],
1074 approxNames[chFactors->type]);
1075 }
1076 }
1077 }
1078 #endif
1079 }
1080
1081
1082 /*
1083 * A GHFunc for g_hash_table_foreach()
1084 *
1085 * Args:
1086 * key: RttKey* where saddr < daddr
1087 * value: double*, RTT estimated from exchanges
1088 * user_data GHashTable* rttInfo
1089 */
1090 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
1091 user_data)
1092 {
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;
1098
1099 convertIP(addr1, rttKey1->saddr);
1100 convertIP(addr2, rttKey1->daddr);
1101
1102 fileRtt1= g_hash_table_lookup(rttInfo, rttKey1);
1103 fileRtt2= g_hash_table_lookup(rttInfo, &rttKey2);
1104
1105 printf("\t\t(%15s, %-15s) %-18.3f ", addr1, addr2, *(double*) value * 1e3);
1106
1107 if (fileRtt1 || fileRtt2)
1108 {
1109 if (fileRtt1)
1110 {
1111 printf("%.3f", *fileRtt1 * 1e3);
1112 }
1113 if (fileRtt1 && fileRtt2)
1114 {
1115 printf(", ");
1116 }
1117 if (fileRtt2)
1118 {
1119 printf("%.3f", *fileRtt2 * 1e3);
1120 }
1121 }
1122 else
1123 {
1124 printf("-");
1125 }
1126 printf("\n");
1127 }
1128
1129
1130 /*
1131 * A GHashFunc for g_hash_table_new()
1132 *
1133 * Args:
1134 * key struct RttKey*
1135 */
1136 static guint ghfRttKeyHash(gconstpointer key)
1137 {
1138 struct RttKey* rttKey;
1139 uint32_t a, b, c;
1140
1141 rttKey= (struct RttKey*) key;
1142
1143 a= rttKey->saddr;
1144 b= rttKey->daddr;
1145 c= 0;
1146 final(a, b, c);
1147
1148 return c;
1149 }
1150
1151
1152 /*
1153 * A GDestroyNotify function for g_hash_table_new_full()
1154 *
1155 * Args:
1156 * data: struct RttKey*
1157 */
1158 static void gdnDestroyRttKey(gpointer data)
1159 {
1160 free(data);
1161 }
1162
1163
1164 /*
1165 * A GDestroyNotify function for g_hash_table_new_full()
1166 *
1167 * Args:
1168 * data: double*
1169 */
1170 static void gdnDestroyDouble(gpointer data)
1171 {
1172 free(data);
1173 }
1174
1175
1176 /*
1177 * A GEqualFunc for g_hash_table_new()
1178 *
1179 * Args:
1180 * a, b RttKey*
1181 *
1182 * Returns:
1183 * TRUE if both values are equal
1184 */
1185 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b)
1186 {
1187 const struct RttKey* rkA, * rkB;
1188
1189 rkA= (struct RttKey*) a;
1190 rkB= (struct RttKey*) b;
1191
1192 if (rkA->saddr == rkB->saddr && rkA->daddr == rkB->daddr)
1193 {
1194 return TRUE;
1195 }
1196 else
1197 {
1198 return FALSE;
1199 }
1200 }
1201
1202
1203 /*
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
1208 *
1209 * Args:
1210 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
1211 * rttStream: stream from which to read
1212 */
1213 static void readRttInfo(GHashTable* rttInfo, FILE* rttStream)
1214 {
1215 char* line= NULL;
1216 size_t len;
1217 int retval;
1218
1219 positionStream(rttStream);
1220 retval= getline(&line, &len, rttStream);
1221 while(!feof(rttStream))
1222 {
1223 struct RttKey* rttKey;
1224 char saddrDQ[20], daddrDQ[20];
1225 double* rtt;
1226 char tmp;
1227 struct in_addr addr;
1228 unsigned int i;
1229 struct {
1230 char* dq;
1231 size_t offset;
1232 } loopValues[] = {
1233 {saddrDQ, offsetof(struct RttKey, saddr)},
1234 {daddrDQ, offsetof(struct RttKey, daddr)}
1235 };
1236
1237 if (retval == -1 && !feof(rttStream))
1238 {
1239 g_error(strerror(errno));
1240 }
1241
1242 if (line[retval - 1] == '\n')
1243 {
1244 line[retval - 1]= '\0';
1245 }
1246
1247 rtt= malloc(sizeof(double));
1248 retval= sscanf(line, " %19s %19s %lf %c", saddrDQ, daddrDQ, rtt,
1249 &tmp);
1250 if (retval == EOF)
1251 {
1252 g_error(strerror(errno));
1253 }
1254 else if (retval != 3)
1255 {
1256 g_error("Error parsing RTT file, line was '%s'", line);
1257 }
1258
1259 rttKey= malloc(sizeof(struct RttKey));
1260 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
1261 {
1262 retval= inet_aton(loopValues[i].dq, &addr);
1263 if (retval == 0)
1264 {
1265 g_error("Error converting address '%s'", loopValues[i].dq);
1266 }
1267 *(uint32_t*) ((void*) rttKey + loopValues[i].offset)=
1268 addr.s_addr;
1269 }
1270
1271 *rtt/= 1e3;
1272 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey->saddr,
1273 rttKey->daddr, *rtt);
1274 g_hash_table_insert(rttInfo, rttKey, rtt);
1275
1276 positionStream(rttStream);
1277 retval= getline(&line, &len, rttStream);
1278 }
1279
1280 if (line)
1281 {
1282 free(line);
1283 }
1284 }
1285
1286
1287 /*
1288 * Advance stream over empty space, empty lines and lines that begin with '#'
1289 *
1290 * Args:
1291 * stream: stream, at exit, will be over the first non-empty character
1292 * of a line of be at EOF
1293 */
1294 static void positionStream(FILE* stream)
1295 {
1296 int firstChar;
1297 ssize_t retval;
1298 char* line= NULL;
1299 size_t len;
1300
1301 do
1302 {
1303 firstChar= fgetc(stream);
1304 if (firstChar == (int) '#')
1305 {
1306 retval= getline(&line, &len, stream);
1307 if (retval == -1)
1308 {
1309 if (feof(stream))
1310 {
1311 goto outEof;
1312 }
1313 else
1314 {
1315 g_error(strerror(errno));
1316 }
1317 }
1318 }
1319 else if (firstChar == (int) '\n' || firstChar == (int) ' ' ||
1320 firstChar == (int) '\t')
1321 {}
1322 else if (firstChar == EOF)
1323 {
1324 goto outEof;
1325 }
1326 else
1327 {
1328 break;
1329 }
1330 } while (true);
1331 retval= ungetc(firstChar, stream);
1332 if (retval == EOF)
1333 {
1334 g_error("Error: ungetc()");
1335 }
1336
1337 outEof:
1338 if (line)
1339 {
1340 free(line);
1341 }
1342 }
1343
1344
1345 /*
1346 * A GFunc for g_queue_foreach()
1347 *
1348 * Args:
1349 * data Event*, a UDP broadcast event
1350 * user_data double*, the running sum
1351 *
1352 * Returns:
1353 * Adds the time of the event to the sum
1354 */
1355 static void gfSum(gpointer data, gpointer userData)
1356 {
1357 Event* event= (Event*) data;
1358
1359 *(double*) userData+= event->wallTime.seconds + event->wallTime.nanosec /
1360 1e9;
1361 }
1362
1363
1364 /*
1365 * A GFunc for g_queue_foreach()
1366 *
1367 * Args:
1368 * data Event*, a UDP broadcast event
1369 * user_data double*, the running sum
1370 *
1371 * Returns:
1372 * Adds the square of the time of the event to the sum
1373 */
1374 static void gfSumSquares(gpointer data, gpointer userData)
1375 {
1376 Event* event= (Event*) data;
1377
1378 *(double*) userData+= pow(event->wallTime.seconds + event->wallTime.nanosec
1379 / 1e9, 2.);
1380 }
1381
1382
1383 /*
1384 * Update a struct Bins according to a new value
1385 *
1386 * Args:
1387 * bins: the structure containing bins to build a histrogram
1388 * value: the new value
1389 */
1390 static void hitBin(struct Bins* const bins, const double value)
1391 {
1392 unsigned int binN= binNum(value);
1393
1394 if (binN < bins->min)
1395 {
1396 bins->min= binN;
1397 }
1398 else if (binN > bins->max)
1399 {
1400 bins->max= binN;
1401 }
1402
1403 bins->total++;
1404
1405 bins->bin[binN]++;
1406 }
1407
1408
1409 /*
1410 * Figure out the bin in a histogram to which a value belongs.
1411 *
1412 * This uses exponentially sized bins that go from 0 to infinity.
1413 *
1414 * Args:
1415 * value: in the range -INFINITY to INFINITY
1416 *
1417 * Returns:
1418 * The number of the bin in a struct Bins.bin
1419 */
1420 static unsigned int binNum(const double value)
1421 {
1422 if (value <= 0)
1423 {
1424 return 0;
1425 }
1426 else if (value < binEnd(1))
1427 {
1428 return 1;
1429 }
1430 else if (value >= binStart(BIN_NB - 1))
1431 {
1432 return BIN_NB - 1;
1433 }
1434 else
1435 {
1436 return floor(log(value) / log(binBase)) + BIN_NB + 1;
1437 }
1438 }
1439
1440
1441 /*
1442 * Figure out the start of the interval of a bin in a histogram. See struct
1443 * Bins.
1444 *
1445 * This uses exponentially sized bins that go from 0 to infinity.
1446 *
1447 * Args:
1448 * binNum: bin number
1449 *
1450 * Return:
1451 * The start of the interval, this value is included in the interval (except
1452 * for -INFINITY, naturally)
1453 */
1454 static double binStart(const unsigned int binNum)
1455 {
1456 g_assert_cmpuint(binNum, <, BIN_NB);
1457
1458 if (binNum == 0)
1459 {
1460 return -INFINITY;
1461 }
1462 else if (binNum == 1)
1463 {
1464 return 0.;
1465 }
1466 else
1467 {
1468 return pow(binBase, (double) binNum - BIN_NB + 1);
1469 }
1470 }
1471
1472
1473 /*
1474 * Figure out the end of the interval of a bin in a histogram. See struct
1475 * Bins.
1476 *
1477 * This uses exponentially sized bins that go from 0 to infinity.
1478 *
1479 * Args:
1480 * binNum: bin number
1481 *
1482 * Return:
1483 * The end of the interval, this value is not included in the interval
1484 */
1485 static double binEnd(const unsigned int binNum)
1486 {
1487 g_assert_cmpuint(binNum, <, BIN_NB);
1488
1489 if (binNum == 0)
1490 {
1491 return 0.;
1492 }
1493 else if (binNum < BIN_NB - 1)
1494 {
1495 return pow(binBase, (double) binNum - BIN_NB + 2);
1496 }
1497 else
1498 {
1499 return INFINITY;
1500 }
1501 }
1502
1503
1504 /*
1505 * Return the total number of elements in the "normal" bins (not underflow or
1506 * overflow)
1507 *
1508 * Args:
1509 * bins: the structure containing bins to build a histrogram
1510 */
1511 static uint32_t normalTotal(struct Bins* const bins)
1512 {
1513 return bins->total - bins->bin[0] - bins->bin[BIN_NB - 1];
1514 }
1515
1516
1517 /* Update the bounds between two traces
1518 *
1519 * Args:
1520 * bounds: the array containing all the trace-pair bounds
1521 * e1, e2: the two related events
1522 */
1523 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
1524 e2)
1525 {
1526 unsigned int traceI, traceJ;
1527 uint64_t messageTime;
1528 Bounds* tpBounds;
1529
1530 if (e1->traceNum < e2->traceNum)
1531 {
1532 traceI= e2->traceNum;
1533 traceJ= e1->traceNum;
1534 messageTime= e1->cpuTime;
1535 }
1536 else
1537 {
1538 traceI= e1->traceNum;
1539 traceJ= e2->traceNum;
1540 messageTime= e2->cpuTime;
1541 }
1542 tpBounds= &bounds[traceI][traceJ];
1543
1544 if (messageTime < tpBounds->min)
1545 {
1546 tpBounds->min= messageTime;
1547 }
1548 if (messageTime > tpBounds->max)
1549 {
1550 tpBounds->max= messageTime;
1551 }
1552 }
1553
1554
1555 #ifdef HAVE_LIBGLPK
1556 /*
1557 * Create the linear programming problem containing the constraints defined by
1558 * two half-hulls. The objective function and optimization directions are not
1559 * written.
1560 *
1561 * Args:
1562 * syncState: container for synchronization data
1563 * i: first trace number
1564 * j: second trace number, garanteed to be larger than i
1565 * Returns:
1566 * A new glp_prob*, this problem must be freed by the caller with
1567 * glp_delete_prob()
1568 */
1569 static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
1570 upperHull)
1571 {
1572 unsigned int it;
1573 const int zero= 0;
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 +
1579 1);
1580 GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb +
1581 1);
1582 GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double),
1583 hullPointNb + 1);
1584 struct {
1585 GQueue* hull;
1586 struct LPAddRowInfo rowInfo;
1587 } loopValues[2]= {
1588 {lowerHull, {lp, GLP_UP, iArray, jArray, aArray}},
1589 {upperHull, {lp, GLP_LO, iArray, jArray, aArray}},
1590 };
1591
1592 // Create the LP problem
1593 glp_term_out(GLP_OFF);
1594 if (hullPointNb > 0)
1595 {
1596 glp_add_rows(lp, hullPointNb);
1597 }
1598 glp_add_cols(lp, 2);
1599
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.);
1604
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);
1609
1610 for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++)
1611 {
1612 g_queue_foreach(loopValues[it].hull, &gfLPAddRow,
1613 &loopValues[it].rowInfo);
1614 }
1615
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);
1619
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));
1622
1623 glp_scale_prob(lp, GLP_SF_AUTO);
1624
1625 g_array_free(iArray, TRUE);
1626 g_array_free(jArray, TRUE);
1627 g_array_free(aArray, TRUE);
1628
1629 return lp;
1630 }
1631
1632
1633 /*
1634 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1635 *
1636 * Args:
1637 * data Point*, synchronization point for which to add an LP row
1638 * (a constraint)
1639 * user_data LPAddRowInfo*
1640 */
1641 static void gfLPAddRow(gpointer data, gpointer user_data)
1642 {
1643 Point* p= data;
1644 struct LPAddRowInfo* rowInfo= user_data;
1645 int indexes[2];
1646 double constraints[2];
1647
1648 indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1;
1649 indexes[1]= indexes[0];
1650
1651 if (rowInfo->boundType == GLP_UP)
1652 {
1653 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y);
1654 }
1655 else if (rowInfo->boundType == GLP_LO)
1656 {
1657 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.);
1658 }
1659 else
1660 {
1661 g_assert_not_reached();
1662 }
1663
1664 g_array_append_vals(rowInfo->iArray, indexes, 2);
1665 indexes[0]= 1;
1666 indexes[1]= 2;
1667 g_array_append_vals(rowInfo->jArray, indexes, 2);
1668 constraints[0]= 1.;
1669 constraints[1]= p->x;
1670 g_array_append_vals(rowInfo->aArray, constraints, 2);
1671 }
1672
1673
1674 /*
1675 * Calculate min or max correction factors (as possible) using an LP problem.
1676 *
1677 * Args:
1678 * lp: A linear programming problem with constraints and bounds
1679 * initialized.
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.
1683 *
1684 * Returns:
1685 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1686 * The calculation will fail if the hull assumptions are not respected.
1687 */
1688 static Factors* calculateFactors(glp_prob* const lp, const int direction)
1689 {
1690 int retval, status;
1691 Factors* factors;
1692
1693 glp_set_obj_coef(lp, 1, 0.);
1694 glp_set_obj_coef(lp, 2, 1.);
1695
1696 glp_set_obj_dir(lp, direction);
1697 retval= glp_simplex(lp, NULL);
1698 status= glp_get_status(lp);
1699
1700 if (retval == 0 && status == GLP_OPT)
1701 {
1702 factors= malloc(sizeof(Factors));
1703 factors->offset= glp_get_col_prim(lp, 1);
1704 factors->drift= glp_get_col_prim(lp, 2);
1705 }
1706 else
1707 {
1708 factors= NULL;
1709 }
1710
1711 return factors;
1712 }
1713
1714
1715 /*
1716 * Calculate min, max and approx correction factors (as possible) using an LP
1717 * problem.
1718 *
1719 * Args:
1720 * lp: A linear programming problem with constraints and bounds
1721 * initialized.
1722 *
1723 * Returns:
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.
1727 */
1728 static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors)
1729 {
1730 factors->min= calculateFactors(lp, GLP_MIN);
1731 factors->max= calculateFactors(lp, GLP_MAX);
1732
1733 if (factors->min && factors->max)
1734 {
1735 factors->type= MIDDLE;
1736 calculateFactorsMiddle(factors);
1737 }
1738 else if (factors->min || factors->max)
1739 {
1740 factors->type= INCOMPLETE;
1741 factors->approx= NULL;
1742 }
1743 else
1744 {
1745 factors->type= ABSENT;
1746 factors->approx= NULL;
1747 }
1748 }
1749
1750
1751 /*
1752 * Create and initialize an array like AnalysisStatsCHull.allFactors
1753 *
1754 * Args:
1755 * traceNb: number of traces
1756 *
1757 * Returns:
1758 * A new array, which can be freed with freeAllFactors()
1759 */
1760 static FactorsCHull** createAllFactors(const unsigned int traceNb)
1761 {
1762 FactorsCHull** factorsArray;
1763 unsigned int i;
1764
1765 factorsArray= malloc(traceNb * sizeof(FactorsCHull*));
1766 for (i= 0; i < traceNb; i++)
1767 {
1768 factorsArray[i]= calloc((i + 1), sizeof(FactorsCHull));
1769
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.;
1774 }
1775
1776 return factorsArray;
1777 }
1778
1779
1780 /*
1781 * A GFunc for g_queue_foreach()
1782 *
1783 * Args:
1784 * data Point*, a convex hull point
1785 * user_data GArray*, an array of convex hull point absisca values, as
1786 * double
1787 */
1788 static void gfAddAbsiscaToArray(gpointer data, gpointer user_data)
1789 {
1790 Point* p= data;
1791 GArray* a= user_data;
1792 double v= p->x;
1793
1794 g_array_append_val(a, v);
1795 }
1796
1797
1798 /*
1799 * A GCompareFunc for g_array_sort()
1800 *
1801 * Args:
1802 * a, b double*, absisca values
1803 *
1804 * Returns:
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
1808 */
1809 static gint gcfCompareDouble(gconstpointer a, gconstpointer b)
1810 {
1811 if (*(double*) a < *(double*) b)
1812 {
1813 return -1;
1814 }
1815 else if (*(double*) a > *(double*) b)
1816 {
1817 return 1;
1818 }
1819 else
1820 {
1821 return 0;
1822 }
1823 }
1824 #endif
1825
1826
1827 /*
1828 * Compute synchronization factors using a linear programming approach.
1829 * Compute the factors using analysis_chull. Compare the two.
1830 *
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.
1834 *
1835 * Args:
1836 * syncState: container for synchronization data
1837 */
1838 static void finalizeAnalysisEvalLP(SyncState* const syncState)
1839 {
1840 AnalysisDataEval* analysisData= syncState->analysisData;
1841 #ifdef HAVE_LIBGLPK
1842 unsigned int i, j;
1843 AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData;
1844 FactorsCHull** lpFactorsArray;
1845
1846 if (!syncState->stats && !syncState->graphsStream)
1847 {
1848 return;
1849 }
1850
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))
1855 {
1856 return;
1857 }
1858
1859 lpFactorsArray= createAllFactors(syncState->traceNb);
1860
1861 if (syncState->stats)
1862 {
1863 analysisData->stats->chFactorsArray=
1864 calculateAllFactors(analysisData->chullSS);
1865 analysisData->stats->lpFactorsArray= lpFactorsArray;
1866 }
1867
1868 if (syncState->graphsStream)
1869 {
1870 analysisData->graphs->lps= malloc(syncState->traceNb *
1871 sizeof(glp_prob**));
1872 for (i= 0; i < syncState->traceNb; i++)
1873 {
1874 analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*));
1875 }
1876 analysisData->graphs->lpFactorsArray= lpFactorsArray;
1877 }
1878
1879 for (i= 0; i < syncState->traceNb; i++)
1880 {
1881 for (j= 0; j < i; j++)
1882 {
1883 glp_prob* lp;
1884
1885 // Create the LP problem
1886 lp= lpCreateProblem(chAnalysisData->hullArray[i][j],
1887 chAnalysisData->hullArray[j][i]);
1888
1889 // Use the LP problem to find the correction factors for this pair of
1890 // traces
1891 calculateCompleteFactors(lp, &lpFactorsArray[i][j]);
1892
1893 if (syncState->graphsStream)
1894 {
1895 analysisData->graphs->lps[i][j]= lp;
1896 }
1897 else
1898 {
1899 glp_delete_prob(lp);
1900 }
1901 }
1902 }
1903 #endif
1904
1905 g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS),
1906 TRUE);
1907 }
1908
1909
1910 /*
1911 * Compute synchronization accuracy information using a linear programming
1912 * approach. Write the neccessary data files and plot lines in the gnuplot
1913 * script.
1914 *
1915 * When the solver library, glpk, is not available at build time nothing is
1916 * actually produced.
1917 *
1918 * Args:
1919 * syncState: container for synchronization data
1920 * i: first trace number
1921 * j: second trace number, garanteed to be larger than i
1922 */
1923 static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
1924 const unsigned int i, const unsigned int j)
1925 {
1926 #ifdef HAVE_LIBGLPK
1927 unsigned int it;
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];
1934
1935 if (lpFactors->type == MIDDLE)
1936 {
1937 int retval;
1938 char* cwd;
1939 char fileName[40];
1940 FILE* fp;
1941 GArray* xValues;
1942
1943 // Open the data file
1944 snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j);
1945 fileName[sizeof(fileName) - 1]= '\0';
1946
1947 cwd= changeToGraphsDir(syncState->graphsDir);
1948
1949 if ((fp= fopen(fileName, "w")) == NULL)
1950 {
1951 g_error(strerror(errno));
1952 }
1953 fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1954
1955 retval= chdir(cwd);
1956 if (retval == -1)
1957 {
1958 g_error(strerror(errno));
1959 }
1960 free(cwd);
1961
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]));
1966
1967 g_queue_foreach(hullArray[i][j], &gfAddAbsiscaToArray, xValues);
1968 g_queue_foreach(hullArray[j][i], &gfAddAbsiscaToArray, xValues);
1969
1970 g_array_sort(xValues, &gcfCompareDouble);
1971
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++)
1975 {
1976 unsigned int it2;
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));
1980
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++)
1985 {
1986 int status;
1987
1988 glp_set_obj_dir(lp, directions[it2]);
1989 retval= glp_simplex(lp, NULL);
1990 status= glp_get_status(lp);
1991
1992 g_assert(retval == 0 && status == GLP_OPT);
1993 fprintf(fp, " %25.9f", glp_get_obj_val(lp));
1994 }
1995 fprintf(fp, "\n");
1996 }
1997
1998 g_array_free(xValues, TRUE);
1999 fclose(fp);
2000
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,
2007 j);
2008 }
2009 #endif
2010 }
2011
2012
2013 /*
2014 * Write the analysis-specific graph lines in the gnuplot script.
2015 *
2016 * When the solver library, glpk, is not available at build time nothing is
2017 * actually produced.
2018 *
2019 * Args:
2020 * syncState: container for synchronization data
2021 * i: first trace number
2022 * j: second trace number, garanteed to be larger than i
2023 */
2024 static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
2025 const unsigned int i, const unsigned int j)
2026 {
2027 #ifdef HAVE_LIBGLPK
2028 if (((AnalysisDataEval*)
2029 syncState->analysisData)->graphs->lpFactorsArray[j][i].type ==
2030 MIDDLE)
2031 {
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);
2041 }
2042 #endif
2043 }
2044
2045
2046 /*
2047 * Write the analysis-specific graph lines in the gnuplot script.
2048 *
2049 * Args:
2050 * syncState: container for synchronization data
2051 * i: first trace number
2052 * j: second trace number, garanteed to be larger than i
2053 */
2054 static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
2055 const unsigned int i, const unsigned int j)
2056 {
2057 #ifdef HAVE_LIBGLPK
2058 fprintf(syncState->graphsStream,
2059 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
2060 "using 1:3:4 "
2061 "title \"Synchronization accuracy\" "
2062 "with filledcurves linewidth 2 linetype 1 "
2063 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j);
2064 #endif
2065 }
2066
2067
2068 /*
2069 * Write the analysis-specific graph lines in the gnuplot script.
2070 *
2071 * Args:
2072 * syncState: container for synchronization data
2073 * i: first trace number
2074 * j: second trace number, garanteed to be larger than i
2075 */
2076 static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
2077 const unsigned int i, const unsigned int j)
2078 {
2079 AnalysisDataEval* analysisData= syncState->analysisData;
2080
2081 analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS,
2082 i, j);
2083 }
LTTng 2.x Viewer (LTTV)
This page took 0.112713 seconds and 3 git commands to generate.