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