projects / lttv.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Make the accuracy area easier to see on the broadcast graphs
[lttv.git] / lttv / lttv / sync / event_analysis_eval.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License Version 2 as
6 * published by the Free Software Foundation;
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
16 * MA 02111-1307, USA.
17 */
18
19 #define _GNU_SOURCE
20 #define _ISOC99_SOURCE
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <arpa/inet.h>
27 #include <errno.h>
28 #include <math.h>
29 #include <netinet/in.h>
30 #include <stddef.h>
31 #include <stdlib.h>
32 #include <stdio.h>
33 #include <string.h>
34 #include <sys/socket.h>
35 #include <unistd.h>
36
37 #include "lookup3.h"
38 #include "sync_chain.h"
39 #include "event_analysis_chull.h"
40
41 #include "event_analysis_eval.h"
42
43
44 struct WriteHistogramInfo
45 {
46 GHashTable* rttInfo;
47 FILE* graphsStream;
48 };
49
50 #ifdef HAVE_LIBGLPK
51 struct LPAddRowInfo
52 {
53 glp_prob* lp;
54 int boundType;
55 GArray* iArray, * jArray, * aArray;
56 };
57 #endif
58
59 // Functions common to all analysis modules
60 static void initAnalysisEval(SyncState* const syncState);
61 static void destroyAnalysisEval(SyncState* const syncState);
62
63 static void analyzeMessageEval(SyncState* const syncState, Message* const
64 message);
65 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
66 exchange);
67 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
68 broadcast);
69 static GArray* finalizeAnalysisEval(SyncState* const syncState);
70 static void printAnalysisStatsEval(SyncState* const syncState);
71 static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
72 const unsigned int i, const unsigned int j);
73 static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
74 const unsigned int i, const unsigned int j);
75 static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
76 const unsigned int i, const unsigned int j);
77 static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
78 const unsigned int i, const unsigned int j);
79
80 // Functions specific to this module
81 static void registerAnalysisEval() __attribute__((constructor (102)));
82 static guint ghfRttKeyHash(gconstpointer key);
83 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b);
84 static void gdnDestroyRttKey(gpointer data);
85 static void gdnDestroyDouble(gpointer data);
86 static void readRttInfo(GHashTable* rttInfo, FILE* rttFile);
87 static void positionStream(FILE* stream);
88
89 static void gfSum(gpointer data, gpointer userData);
90 static void gfSumSquares(gpointer data, gpointer userData);
91 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
92 user_data);
93
94 static void hitBin(struct Bins* const bins, const double value);
95 static unsigned int binNum(const double value) __attribute__((pure));
96 static double binStart(const unsigned int binNum) __attribute__((pure));
97 static double binEnd(const unsigned int binNum) __attribute__((pure));
98 static uint32_t normalTotal(struct Bins* const bins) __attribute__((const));
99
100 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
101 graphsDir, const struct RttKey* const rttKey);
102 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
103 histogram);
104 static void gdnDestroyAnalysisHistogramEval(gpointer data);
105 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer
106 user_data);
107 static void dumpBinToFile(const struct Bins* const bins, FILE* const file);
108 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
109 double* minRtt, AnalysisHistogramEval* const histogram);
110
111 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
112 e2);
113
114 // The next group of functions is only needed when computing synchronization
115 // accuracy.
116 #ifdef HAVE_LIBGLPK
117 static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
118 upperHull);
119 static void gfLPAddRow(gpointer data, gpointer user_data);
120 static Factors* calculateFactors(glp_prob* const lp, const int direction);
121 static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull*
122 factors);
123 static FactorsCHull** createAllFactors(const unsigned int traceNb);
124 static inline void finalizeAnalysisEvalLP(SyncState* const syncState);
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 {.arg= NULL},
154 .optionHelp= "specify the file containing RTT information",
155 .argHelp= "FILE",
156 };
157
158
159 /*
160 * Analysis module registering function
161 */
162 static 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->broadcastDiffSum= 0.;
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= changeToGraphDir(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, j;
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(syncState->traceNb, stats->chFactorsArray);
561 freeAllFactors(syncState->traceNb, 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 for (j= 0; j < i; j++)
586 {
587 // There seems to be a memory leak in glpk, valgrind reports a
588 // loss even if the problem is deleted
589 glp_delete_prob(graphs->lps[i][j]);
590 }
591 free(graphs->lps[i]);
592 }
593 free(graphs->lps);
594
595 if (!syncState->stats)
596 {
597 freeAllFactors(syncState->traceNb, graphs->lpFactorsArray);
598 }
599 #endif
600
601 free(graphs);
602 }
603
604 if (syncState->stats || syncState->graphsStream)
605 {
606 analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS);
607 free(analysisData->chullSS);
608 }
609
610 free(syncState->analysisData);
611 syncState->analysisData= NULL;
612 }
613
614
615 /*
616 * Perform analysis on an event pair.
617 *
618 * Check if there is message inversion or messages that are too fast.
619 *
620 * Args:
621 * syncState container for synchronization data
622 * message structure containing the events
623 */
624 static void analyzeMessageEval(SyncState* const syncState, Message* const
625 message)
626 {
627 AnalysisDataEval* analysisData= syncState->analysisData;
628 MessageStats* messageStats=
629 &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
630 double* rtt;
631 double tt;
632 struct RttKey rttKey;
633
634 g_assert(message->inE->type == TCP);
635
636 if (syncState->stats)
637 {
638 messageStats->total++;
639 }
640
641 tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
642 if (tt <= 0)
643 {
644 if (syncState->stats)
645 {
646 messageStats->inversionNb++;
647 }
648 }
649 else if (syncState->graphsStream)
650 {
651 struct RttKey rttKey= {
652 .saddr=MIN(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
653 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
654 .daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
655 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
656 };
657 AnalysisHistogramEval* histogram=
658 g_hash_table_lookup(analysisData->graphs->histograms, &rttKey);
659
660 if (histogram == NULL)
661 {
662 struct RttKey* tableKey= malloc(sizeof(*tableKey));
663
664 histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey);
665 memcpy(tableKey, &rttKey, sizeof(*tableKey));
666 g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram);
667 }
668
669 if (message->inE->event.udpEvent->datagramKey->saddr <
670 message->inE->event.udpEvent->datagramKey->daddr)
671 {
672 hitBin(&histogram->ttSendBins, tt);
673 }
674 else
675 {
676 hitBin(&histogram->ttRecvBins, tt);
677 }
678 }
679
680 if (syncState->stats)
681 {
682 rttKey.saddr=
683 message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
684 rttKey.daddr=
685 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
686 rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
687 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
688 rttKey.daddr, rtt ? *rtt : NAN);
689
690 if (rtt)
691 {
692 g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
693 if (tt < *rtt / 2.)
694 {
695 messageStats->tooFastNb++;
696 }
697 }
698 else
699 {
700 messageStats->noRTTInfoNb++;
701 }
702 }
703
704 if (syncState->graphsStream)
705 {
706 updateBounds(analysisData->graphs->bounds, message->inE,
707 message->outE);
708 }
709
710 if (syncState->stats || syncState->graphsStream)
711 {
712 analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS,
713 message);
714 }
715 }
716
717
718 /*
719 * Perform analysis on multiple messages
720 *
721 * Measure the RTT
722 *
723 * Args:
724 * syncState container for synchronization data
725 * exchange structure containing the messages
726 */
727 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
728 exchange)
729 {
730 AnalysisDataEval* analysisData= syncState->analysisData;
731 Message* m1= g_queue_peek_tail(exchange->acks);
732 Message* m2= exchange->message;
733 struct RttKey* rttKey;
734 double* rtt, * exchangeRtt;
735
736 g_assert(m1->inE->type == TCP);
737
738 // (T2 - T1) - (T3 - T4)
739 rtt= malloc(sizeof(double));
740 *rtt= wallTimeSub(&m1->inE->wallTime, &m1->outE->wallTime) -
741 wallTimeSub(&m2->outE->wallTime, &m2->inE->wallTime);
742
743 rttKey= malloc(sizeof(struct RttKey));
744 rttKey->saddr=
745 MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
746 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
747 rttKey->daddr=
748 MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
749 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
750
751 if (syncState->graphsStream)
752 {
753 AnalysisHistogramEval* histogram=
754 g_hash_table_lookup(analysisData->graphs->histograms, rttKey);
755
756 if (histogram == NULL)
757 {
758 struct RttKey* tableKey= malloc(sizeof(*tableKey));
759
760 histogram= constructAnalysisHistogramEval(syncState->graphsDir,
761 rttKey);
762 memcpy(tableKey, rttKey, sizeof(*tableKey));
763 g_hash_table_insert(analysisData->graphs->histograms, tableKey,
764 histogram);
765 }
766
767 hitBin(&histogram->hrttBins, *rtt / 2);
768 }
769
770 if (syncState->stats)
771 {
772 exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
773 rttKey);
774
775 if (exchangeRtt)
776 {
777 if (*rtt < *exchangeRtt)
778 {
779 g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
780 }
781 else
782 {
783 free(rttKey);
784 free(rtt);
785 }
786 }
787 else
788 {
789 g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
790 }
791 }
792 else
793 {
794 free(rttKey);
795 free(rtt);
796 }
797 }
798
799
800 /*
801 * Perform analysis on muliple events
802 *
803 * Sum the broadcast differential delays
804 *
805 * Args:
806 * syncState container for synchronization data
807 * broadcast structure containing the events
808 */
809 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
810 broadcast)
811 {
812 AnalysisDataEval* analysisData= syncState->analysisData;
813
814 if (syncState->stats)
815 {
816 double sum= 0, squaresSum= 0;
817 double y;
818
819 g_queue_foreach(broadcast->events, &gfSum, &sum);
820 g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
821
822 analysisData->stats->broadcastNb++;
823 // Because of numerical errors, this can at times be < 0
824 y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
825 g_queue_get_length(broadcast->events), 2.);
826 if (y > 0)
827 {
828 analysisData->stats->broadcastDiffSum+= sqrt(y);
829 }
830 }
831
832 if (syncState->graphsStream)
833 {
834 unsigned int i, j;
835 GArray* events;
836 unsigned int eventNb= broadcast->events->length;
837
838 events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb);
839 g_queue_foreach(broadcast->events, &gfAddEventToArray, events);
840
841 for (i= 0; i < eventNb; i++)
842 {
843 for (j= 0; j < eventNb; j++)
844 {
845 Event* eventI= g_array_index(events, Event*, i), * eventJ=
846 g_array_index(events, Event*, j);
847
848 if (eventI->traceNum < eventJ->traceNum)
849 {
850 updateBounds(analysisData->graphs->bounds, eventI, eventJ);
851 }
852 }
853 }
854
855 g_array_free(events, TRUE);
856 }
857 }
858
859
860 /*
861 * Finalize the factor calculations. Since this module does not really
862 * calculate factors, identity factors are returned. Instead, histograms are
863 * written out and histogram structures are freed.
864 *
865 * Args:
866 * syncState container for synchronization data.
867 *
868 * Returns:
869 * Factors[traceNb] identity factors for each trace
870 */
871 static GArray* finalizeAnalysisEval(SyncState* const syncState)
872 {
873 GArray* factors;
874 unsigned int i;
875 AnalysisDataEval* analysisData= syncState->analysisData;
876
877 if (syncState->graphsStream && analysisData->graphs->histograms)
878 {
879 g_hash_table_foreach(analysisData->graphs->histograms,
880 &ghfWriteHistogram, &(struct WriteHistogramInfo) {.rttInfo=
881 analysisData->rttInfo, .graphsStream= syncState->graphsStream});
882 g_hash_table_destroy(analysisData->graphs->histograms);
883 analysisData->graphs->histograms= NULL;
884 }
885
886 finalizeAnalysisEvalLP(syncState);
887
888 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
889 syncState->traceNb);
890 g_array_set_size(factors, syncState->traceNb);
891 for (i= 0; i < syncState->traceNb; i++)
892 {
893 Factors* e;
894
895 e= &g_array_index(factors, Factors, i);
896 e->drift= 1.;
897 e->offset= 0.;
898 }
899
900 return factors;
901 }
902
903
904 /*
905 * Print statistics related to analysis. Must be called after
906 * finalizeAnalysis.
907 *
908 * Args:
909 * syncState container for synchronization data.
910 */
911 static void printAnalysisStatsEval(SyncState* const syncState)
912 {
913 AnalysisDataEval* analysisData;
914 unsigned int i, j, k;
915 unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0;
916 int charNb;
917
918 if (!syncState->stats)
919 {
920 return;
921 }
922
923 analysisData= (AnalysisDataEval*) syncState->analysisData;
924
925 printf("Synchronization evaluation analysis stats:\n");
926 if (analysisData->stats->broadcastNb)
927 {
928 printf("\tsum of broadcast differential delays: %g\n",
929 analysisData->stats->broadcastDiffSum);
930 printf("\taverage broadcast differential delay: %g\n",
931 analysisData->stats->broadcastDiffSum /
932 analysisData->stats->broadcastNb);
933 }
934
935 printf("\tIndividual evaluation:\n"
936 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
937
938 for (i= 0; i < syncState->traceNb; i++)
939 {
940 for (j= i + 1; j < syncState->traceNb; j++)
941 {
942 MessageStats* messageStats;
943 struct {
944 unsigned int t1, t2;
945 } loopValues[]= {
946 {i, j},
947 {j, i}
948 };
949
950 for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++)
951 {
952 messageStats=
953 &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
954
955 printf("\t\t%3d - %-3d ", loopValues[k].t1, loopValues[k].t2);
956 printf("%u (%u%%)%n", messageStats->inversionNb, (unsigned
957 int) ceil((double) messageStats->inversionNb /
958 messageStats->total * 100), &charNb);
959 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
960 printf("%u (%u%%)%n", messageStats->tooFastNb, (unsigned int)
961 ceil((double) messageStats->tooFastNb /
962 messageStats->total * 100), &charNb);
963 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
964 1, " ", messageStats->noRTTInfoNb, messageStats->total);
965
966 totInversion+= messageStats->inversionNb;
967 totTooFast+= messageStats->tooFastNb;
968 totNoInfo+= messageStats->noRTTInfoNb;
969 totTotal+= messageStats->total;
970 }
971 }
972 }
973
974 printf("\t\t total ");
975 printf("%u (%u%%)%n", totInversion, (unsigned int) ceil((double)
976 totInversion / totTotal * 100), &charNb);
977 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
978 printf("%u (%u%%)%n", totTooFast, (unsigned int) ceil((double) totTooFast
979 / totTotal * 100), &charNb);
980 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
981 totNoInfo, totTotal);
982
983 printf("\tRound-trip times:\n"
984 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
985 g_hash_table_foreach(analysisData->stats->exchangeRtt,
986 &ghfPrintExchangeRtt, analysisData->rttInfo);
987
988 printf("\tConvex hull factors comparisons:\n"
989 "\t\tTrace pair Factors type Differences (lp - chull)\n"
990 "\t\t a0 a1\n"
991 "\t\t Min Max Min Max\n");
992
993 for (i= 0; i < syncState->traceNb; i++)
994 {
995 for (j= 0; j < i; j++)
996 {
997 FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j];
998 FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[i][j];
999
1000 printf("\t\t%3d - %-3d ", i, j);
1001 if (lpFactors->type == chFactors->type)
1002 {
1003 if (lpFactors->type == MIDDLE)
1004 {
1005 printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
1006 approxNames[lpFactors->type],
1007 lpFactors->min->offset - chFactors->min->offset,
1008 lpFactors->max->offset - chFactors->max->offset,
1009 lpFactors->min->drift - chFactors->min->drift,
1010 lpFactors->max->drift - chFactors->max->drift);
1011 }
1012 else if (lpFactors->type == ABSENT)
1013 {
1014 printf("%s\n", approxNames[lpFactors->type]);
1015 }
1016 }
1017 else
1018 {
1019 printf("Different! %s and %s\n", approxNames[lpFactors->type],
1020 approxNames[chFactors->type]);
1021 }
1022 }
1023 }
1024 }
1025
1026
1027 /*
1028 * A GHFunc for g_hash_table_foreach()
1029 *
1030 * Args:
1031 * key: RttKey* where saddr < daddr
1032 * value: double*, RTT estimated from exchanges
1033 * user_data GHashTable* rttInfo
1034 */
1035 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
1036 user_data)
1037 {
1038 char addr1[16], addr2[16];
1039 struct RttKey* rttKey1= key;
1040 struct RttKey rttKey2= {rttKey1->daddr, rttKey1->saddr};
1041 double* fileRtt1, *fileRtt2;
1042 GHashTable* rttInfo= user_data;
1043
1044 convertIP(addr1, rttKey1->saddr);
1045 convertIP(addr2, rttKey1->daddr);
1046
1047 fileRtt1= g_hash_table_lookup(rttInfo, rttKey1);
1048 fileRtt2= g_hash_table_lookup(rttInfo, &rttKey2);
1049
1050 printf("\t\t(%15s, %-15s) %-18.3f ", addr1, addr2, *(double*) value * 1e3);
1051
1052 if (fileRtt1 || fileRtt2)
1053 {
1054 if (fileRtt1)
1055 {
1056 printf("%.3f", *fileRtt1 * 1e3);
1057 }
1058 if (fileRtt1 && fileRtt2)
1059 {
1060 printf(", ");
1061 }
1062 if (fileRtt2)
1063 {
1064 printf("%.3f", *fileRtt2 * 1e3);
1065 }
1066 }
1067 else
1068 {
1069 printf("-");
1070 }
1071 printf("\n");
1072 }
1073
1074
1075 /*
1076 * A GHashFunc for g_hash_table_new()
1077 *
1078 * Args:
1079 * key struct RttKey*
1080 */
1081 static guint ghfRttKeyHash(gconstpointer key)
1082 {
1083 struct RttKey* rttKey;
1084 uint32_t a, b, c;
1085
1086 rttKey= (struct RttKey*) key;
1087
1088 a= rttKey->saddr;
1089 b= rttKey->daddr;
1090 c= 0;
1091 final(a, b, c);
1092
1093 return c;
1094 }
1095
1096
1097 /*
1098 * A GDestroyNotify function for g_hash_table_new_full()
1099 *
1100 * Args:
1101 * data: struct RttKey*
1102 */
1103 static void gdnDestroyRttKey(gpointer data)
1104 {
1105 free(data);
1106 }
1107
1108
1109 /*
1110 * A GDestroyNotify function for g_hash_table_new_full()
1111 *
1112 * Args:
1113 * data: double*
1114 */
1115 static void gdnDestroyDouble(gpointer data)
1116 {
1117 free(data);
1118 }
1119
1120
1121 /*
1122 * A GEqualFunc for g_hash_table_new()
1123 *
1124 * Args:
1125 * a, b RttKey*
1126 *
1127 * Returns:
1128 * TRUE if both values are equal
1129 */
1130 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b)
1131 {
1132 const struct RttKey* rkA, * rkB;
1133
1134 rkA= (struct RttKey*) a;
1135 rkB= (struct RttKey*) b;
1136
1137 if (rkA->saddr == rkB->saddr && rkA->daddr == rkB->daddr)
1138 {
1139 return TRUE;
1140 }
1141 else
1142 {
1143 return FALSE;
1144 }
1145 }
1146
1147
1148 /*
1149 * Read a file contain minimum round trip time values and fill an array with
1150 * them. The file is formatted as such:
1151 * <host1 IP> <host2 IP> <RTT in milliseconds>
1152 * ip's should be in dotted quad format
1153 *
1154 * Args:
1155 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
1156 * rttStream: stream from which to read
1157 */
1158 static void readRttInfo(GHashTable* rttInfo, FILE* rttStream)
1159 {
1160 char* line= NULL;
1161 size_t len;
1162 int retval;
1163
1164 positionStream(rttStream);
1165 retval= getline(&line, &len, rttStream);
1166 while(!feof(rttStream))
1167 {
1168 struct RttKey* rttKey;
1169 char saddrDQ[20], daddrDQ[20];
1170 double* rtt;
1171 char tmp;
1172 struct in_addr addr;
1173 unsigned int i;
1174 struct {
1175 char* dq;
1176 size_t offset;
1177 } loopValues[] = {
1178 {saddrDQ, offsetof(struct RttKey, saddr)},
1179 {daddrDQ, offsetof(struct RttKey, daddr)}
1180 };
1181
1182 if (retval == -1 && !feof(rttStream))
1183 {
1184 g_error(strerror(errno));
1185 }
1186
1187 if (line[retval - 1] == '\n')
1188 {
1189 line[retval - 1]= '\0';
1190 }
1191
1192 rtt= malloc(sizeof(double));
1193 retval= sscanf(line, " %19s %19s %lf %c", saddrDQ, daddrDQ, rtt,
1194 &tmp);
1195 if (retval == EOF)
1196 {
1197 g_error(strerror(errno));
1198 }
1199 else if (retval != 3)
1200 {
1201 g_error("Error parsing RTT file, line was '%s'", line);
1202 }
1203
1204 rttKey= malloc(sizeof(struct RttKey));
1205 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
1206 {
1207 retval= inet_aton(loopValues[i].dq, &addr);
1208 if (retval == 0)
1209 {
1210 g_error("Error converting address '%s'", loopValues[i].dq);
1211 }
1212 *(uint32_t*) ((void*) rttKey + loopValues[i].offset)=
1213 addr.s_addr;
1214 }
1215
1216 *rtt/= 1e3;
1217 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey->saddr,
1218 rttKey->daddr, *rtt);
1219 g_hash_table_insert(rttInfo, rttKey, rtt);
1220
1221 positionStream(rttStream);
1222 retval= getline(&line, &len, rttStream);
1223 }
1224
1225 if (line)
1226 {
1227 free(line);
1228 }
1229 }
1230
1231
1232 /*
1233 * Advance stream over empty space, empty lines and lines that begin with '#'
1234 *
1235 * Args:
1236 * stream: stream, at exit, will be over the first non-empty character
1237 * of a line of be at EOF
1238 */
1239 static void positionStream(FILE* stream)
1240 {
1241 int firstChar;
1242 ssize_t retval;
1243 char* line= NULL;
1244 size_t len;
1245
1246 do
1247 {
1248 firstChar= fgetc(stream);
1249 if (firstChar == (int) '#')
1250 {
1251 retval= getline(&line, &len, stream);
1252 if (retval == -1)
1253 {
1254 if (feof(stream))
1255 {
1256 goto outEof;
1257 }
1258 else
1259 {
1260 g_error(strerror(errno));
1261 }
1262 }
1263 }
1264 else if (firstChar == (int) '\n' || firstChar == (int) ' ' ||
1265 firstChar == (int) '\t')
1266 {}
1267 else if (firstChar == EOF)
1268 {
1269 goto outEof;
1270 }
1271 else
1272 {
1273 break;
1274 }
1275 } while (true);
1276 retval= ungetc(firstChar, stream);
1277 if (retval == EOF)
1278 {
1279 g_error("Error: ungetc()");
1280 }
1281
1282 outEof:
1283 if (line)
1284 {
1285 free(line);
1286 }
1287 }
1288
1289
1290 /*
1291 * A GFunc for g_queue_foreach()
1292 *
1293 * Args:
1294 * data Event*, a UDP broadcast event
1295 * user_data double*, the running sum
1296 *
1297 * Returns:
1298 * Adds the time of the event to the sum
1299 */
1300 static void gfSum(gpointer data, gpointer userData)
1301 {
1302 Event* event= (Event*) data;
1303
1304 *(double*) userData+= event->wallTime.seconds + event->wallTime.nanosec /
1305 1e9;
1306 }
1307
1308
1309 /*
1310 * A GFunc for g_queue_foreach()
1311 *
1312 * Args:
1313 * data Event*, a UDP broadcast event
1314 * user_data double*, the running sum
1315 *
1316 * Returns:
1317 * Adds the square of the time of the event to the sum
1318 */
1319 static void gfSumSquares(gpointer data, gpointer userData)
1320 {
1321 Event* event= (Event*) data;
1322
1323 *(double*) userData+= pow(event->wallTime.seconds + event->wallTime.nanosec
1324 / 1e9, 2.);
1325 }
1326
1327
1328 /*
1329 * Update a struct Bins according to a new value
1330 *
1331 * Args:
1332 * bins: the structure containing bins to build a histrogram
1333 * value: the new value
1334 */
1335 static void hitBin(struct Bins* const bins, const double value)
1336 {
1337 unsigned int binN= binNum(value);
1338
1339 if (binN < bins->min)
1340 {
1341 bins->min= binN;
1342 }
1343 else if (binN > bins->max)
1344 {
1345 bins->max= binN;
1346 }
1347
1348 bins->total++;
1349
1350 bins->bin[binN]++;
1351 }
1352
1353
1354 /*
1355 * Figure out the bin in a histogram to which a value belongs.
1356 *
1357 * This uses exponentially sized bins that go from 0 to infinity.
1358 *
1359 * Args:
1360 * value: in the range -INFINITY to INFINITY
1361 *
1362 * Returns:
1363 * The number of the bin in a struct Bins.bin
1364 */
1365 static unsigned int binNum(const double value)
1366 {
1367 if (value <= 0)
1368 {
1369 return 0;
1370 }
1371 else if (value < binEnd(1))
1372 {
1373 return 1;
1374 }
1375 else if (value >= binStart(BIN_NB - 1))
1376 {
1377 return BIN_NB - 1;
1378 }
1379 else
1380 {
1381 return floor(log(value) / log(binBase)) + BIN_NB + 1;
1382 }
1383 }
1384
1385
1386 /*
1387 * Figure out the start of the interval of a bin in a histogram. See struct
1388 * Bins.
1389 *
1390 * This uses exponentially sized bins that go from 0 to infinity.
1391 *
1392 * Args:
1393 * binNum: bin number
1394 *
1395 * Return:
1396 * The start of the interval, this value is included in the interval (except
1397 * for -INFINITY, naturally)
1398 */
1399 static double binStart(const unsigned int binNum)
1400 {
1401 g_assert_cmpuint(binNum, <, BIN_NB);
1402
1403 if (binNum == 0)
1404 {
1405 return -INFINITY;
1406 }
1407 else if (binNum == 1)
1408 {
1409 return 0.;
1410 }
1411 else
1412 {
1413 return pow(binBase, (double) binNum - BIN_NB + 1);
1414 }
1415 }
1416
1417
1418 /*
1419 * Figure out the end of the interval of a bin in a histogram. See struct
1420 * Bins.
1421 *
1422 * This uses exponentially sized bins that go from 0 to infinity.
1423 *
1424 * Args:
1425 * binNum: bin number
1426 *
1427 * Return:
1428 * The end of the interval, this value is not included in the interval
1429 */
1430 static double binEnd(const unsigned int binNum)
1431 {
1432 g_assert_cmpuint(binNum, <, BIN_NB);
1433
1434 if (binNum == 0)
1435 {
1436 return 0.;
1437 }
1438 else if (binNum < BIN_NB - 1)
1439 {
1440 return pow(binBase, (double) binNum - BIN_NB + 2);
1441 }
1442 else
1443 {
1444 return INFINITY;
1445 }
1446 }
1447
1448
1449 /*
1450 * Return the total number of elements in the "normal" bins (not underflow or
1451 * overflow)
1452 *
1453 * Args:
1454 * bins: the structure containing bins to build a histrogram
1455 */
1456 static uint32_t normalTotal(struct Bins* const bins)
1457 {
1458 return bins->total - bins->bin[0] - bins->bin[BIN_NB - 1];
1459 }
1460
1461
1462 /* Update the bounds between two traces
1463 *
1464 * Args:
1465 * bounds: the array containing all the trace-pair bounds
1466 * e1, e2: the two related events
1467 */
1468 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
1469 e2)
1470 {
1471 unsigned int traceI, traceJ;
1472 uint64_t messageTime;
1473 Bounds* tpBounds;
1474
1475 if (e1->traceNum < e2->traceNum)
1476 {
1477 traceI= e2->traceNum;
1478 traceJ= e1->traceNum;
1479 messageTime= e1->cpuTime;
1480 }
1481 else
1482 {
1483 traceI= e1->traceNum;
1484 traceJ= e2->traceNum;
1485 messageTime= e2->cpuTime;
1486 }
1487 tpBounds= &bounds[traceI][traceJ];
1488
1489 if (messageTime < tpBounds->min)
1490 {
1491 tpBounds->min= messageTime;
1492 }
1493 if (messageTime > tpBounds->max)
1494 {
1495 tpBounds->max= messageTime;
1496 }
1497 }
1498
1499
1500 #ifdef HAVE_LIBGLPK
1501 /*
1502 * Create the linear programming problem containing the constraints defined by
1503 * two half-hulls. The objective function and optimization directions are not
1504 * written.
1505 *
1506 * Args:
1507 * syncState: container for synchronization data
1508 * i: first trace number
1509 * j: second trace number, garanteed to be larger than i
1510 * Returns:
1511 * A new glp_prob*, this problem must be freed by the caller with
1512 * glp_delete_prob()
1513 */
1514 static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
1515 upperHull)
1516 {
1517 unsigned int it;
1518 const int zero= 0;
1519 const double zeroD= 0.;
1520 glp_prob* lp= glp_create_prob();
1521 unsigned int hullPointNb= g_queue_get_length(lowerHull) +
1522 g_queue_get_length(upperHull);
1523 GArray* iArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb +
1524 1);
1525 GArray* jArray= g_array_sized_new(FALSE, FALSE, sizeof(int), hullPointNb +
1526 1);
1527 GArray* aArray= g_array_sized_new(FALSE, FALSE, sizeof(double),
1528 hullPointNb + 1);
1529 struct {
1530 GQueue* hull;
1531 struct LPAddRowInfo rowInfo;
1532 } loopValues[2]= {
1533 {lowerHull, {lp, GLP_UP, iArray, jArray, aArray}},
1534 {upperHull, {lp, GLP_LO, iArray, jArray, aArray}},
1535 };
1536
1537 // Create the LP problem
1538 glp_term_out(GLP_OFF);
1539 glp_add_rows(lp, hullPointNb);
1540 glp_add_cols(lp, 2);
1541
1542 glp_set_col_name(lp, 1, "a0");
1543 glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.);
1544 glp_set_col_name(lp, 2, "a1");
1545 glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.);
1546
1547 // Add row constraints
1548 g_array_append_val(iArray, zero);
1549 g_array_append_val(jArray, zero);
1550 g_array_append_val(aArray, zeroD);
1551
1552 for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++)
1553 {
1554 g_queue_foreach(loopValues[it].hull, &gfLPAddRow,
1555 &loopValues[it].rowInfo);
1556 }
1557
1558 g_assert_cmpuint(iArray->len, ==, jArray->len);
1559 g_assert_cmpuint(jArray->len, ==, aArray->len);
1560 g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2);
1561
1562 glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0),
1563 &g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0));
1564
1565 glp_scale_prob(lp, GLP_SF_AUTO);
1566
1567 g_array_free(iArray, TRUE);
1568 g_array_free(jArray, TRUE);
1569 g_array_free(aArray, TRUE);
1570
1571 return lp;
1572 }
1573
1574
1575 /*
1576 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1577 *
1578 * Args:
1579 * data Point*, synchronization point for which to add an LP row
1580 * (a constraint)
1581 * user_data LPAddRowInfo*
1582 */
1583 static void gfLPAddRow(gpointer data, gpointer user_data)
1584 {
1585 Point* p= data;
1586 struct LPAddRowInfo* rowInfo= user_data;
1587 int indexes[2];
1588 double constraints[2];
1589
1590 indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1;
1591 indexes[1]= indexes[0];
1592
1593 if (rowInfo->boundType == GLP_UP)
1594 {
1595 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y);
1596 }
1597 else if (rowInfo->boundType == GLP_LO)
1598 {
1599 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.);
1600 }
1601 else
1602 {
1603 g_assert_not_reached();
1604 }
1605
1606 g_array_append_vals(rowInfo->iArray, indexes, 2);
1607 indexes[0]= 1;
1608 indexes[1]= 2;
1609 g_array_append_vals(rowInfo->jArray, indexes, 2);
1610 constraints[0]= 1.;
1611 constraints[1]= p->x;
1612 g_array_append_vals(rowInfo->aArray, constraints, 2);
1613 }
1614
1615
1616 /*
1617 * Calculate min or max correction factors (as possible) using an LP problem.
1618 *
1619 * Args:
1620 * lp: A linear programming problem with constraints and bounds
1621 * initialized.
1622 * direction: The type of factors desired. Use GLP_MAX for max
1623 * approximation factors (a1, the drift or slope is the
1624 * largest) and GLP_MIN in the other case.
1625 *
1626 * Returns:
1627 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1628 * The calculation will fail if the hull assumptions are not respected.
1629 */
1630 static Factors* calculateFactors(glp_prob* const lp, const int direction)
1631 {
1632 int retval, status;
1633 Factors* factors;
1634
1635 glp_set_obj_coef(lp, 1, 0.);
1636 glp_set_obj_coef(lp, 2, 1.);
1637
1638 glp_set_obj_dir(lp, direction);
1639 retval= glp_simplex(lp, NULL);
1640 status= glp_get_status(lp);
1641
1642 if (retval == 0 && status == GLP_OPT)
1643 {
1644 factors= malloc(sizeof(Factors));
1645 factors->offset= glp_get_col_prim(lp, 1);
1646 factors->drift= glp_get_col_prim(lp, 2);
1647 }
1648 else
1649 {
1650 factors= NULL;
1651 }
1652
1653 return factors;
1654 }
1655
1656
1657 /*
1658 * Calculate min, max and approx correction factors (as possible) using an LP
1659 * problem.
1660 *
1661 * Args:
1662 * lp: A linear programming problem with constraints and bounds
1663 * initialized.
1664 *
1665 * Returns:
1666 * Please note that the approximation type may be MIDDLE, INCOMPLETE or
1667 * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do
1668 * not respect assumptions.
1669 */
1670 static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors)
1671 {
1672 factors->min= calculateFactors(lp, GLP_MIN);
1673 factors->max= calculateFactors(lp, GLP_MAX);
1674
1675 if (factors->min && factors->max)
1676 {
1677 factors->type= MIDDLE;
1678 calculateFactorsMiddle(factors);
1679 }
1680 else if (factors->min || factors->max)
1681 {
1682 factors->type= INCOMPLETE;
1683 factors->approx= NULL;
1684 }
1685 else
1686 {
1687 factors->type= ABSENT;
1688 factors->approx= NULL;
1689 }
1690 }
1691
1692
1693 /*
1694 * Create and initialize an array like AnalysisStatsCHull.allFactors
1695 *
1696 * Args:
1697 * traceNb: number of traces
1698 *
1699 * Returns:
1700 * A new array, which can be freed with freeAllFactors()
1701 */
1702 static FactorsCHull** createAllFactors(const unsigned int traceNb)
1703 {
1704 FactorsCHull** factorsArray;
1705 unsigned int i;
1706
1707 factorsArray= malloc(traceNb * sizeof(FactorsCHull*));
1708 for (i= 0; i < traceNb; i++)
1709 {
1710 factorsArray[i]= calloc((i + 1), sizeof(FactorsCHull));
1711
1712 factorsArray[i][i].type= EXACT;
1713 factorsArray[i][i].approx= malloc(sizeof(Factors));
1714 factorsArray[i][i].approx->drift= 1.;
1715 factorsArray[i][i].approx->offset= 0.;
1716 }
1717
1718 return factorsArray;
1719 }
1720 #endif
1721
1722
1723 /*
1724 * Compute synchronization factors using a linear programming approach.
1725 * Compute the factors using analysis_chull. Compare the two.
1726 *
1727 * There are two definitions of this function. The empty one is used when the
1728 * solver library, glpk, is not available at build time. In that case, nothing
1729 * is actually produced.
1730 *
1731 * Args:
1732 * syncState: container for synchronization data
1733 */
1734 #ifndef HAVE_LIBGLPK
1735 static inline void finalizeAnalysisEvalLP(SyncState* const syncState)
1736 {
1737 }
1738 #else
1739 static void finalizeAnalysisEvalLP(SyncState* const syncState)
1740 {
1741 unsigned int i, j;
1742 AnalysisDataEval* analysisData= syncState->analysisData;
1743 AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData;
1744 FactorsCHull** lpFactorsArray= createAllFactors(syncState->traceNb);
1745 FactorsCHull* lpFactors;
1746
1747 if (!syncState->stats && !syncState->graphsStream)
1748 {
1749 return;
1750 }
1751
1752 if ((syncState->graphsStream && analysisData->graphs->lps != NULL) ||
1753 (syncState->stats && analysisData->stats->chFactorsArray != NULL))
1754 {
1755 return;
1756 }
1757
1758 if (syncState->stats)
1759 {
1760 analysisData->stats->chFactorsArray=
1761 calculateAllFactors(analysisData->chullSS);
1762 analysisData->stats->lpFactorsArray= lpFactorsArray;
1763 }
1764
1765 if (syncState->graphsStream)
1766 {
1767 analysisData->graphs->lps= malloc(syncState->traceNb *
1768 sizeof(glp_prob**));
1769 for (i= 0; i < syncState->traceNb; i++)
1770 {
1771 analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*));
1772 }
1773 analysisData->graphs->lpFactorsArray= lpFactorsArray;
1774 }
1775
1776 for (i= 0; i < syncState->traceNb; i++)
1777 {
1778 for (j= 0; j < i; j++)
1779 {
1780 glp_prob* lp;
1781
1782 // Create the LP problem
1783 lp= lpCreateProblem(chAnalysisData->hullArray[i][j],
1784 chAnalysisData->hullArray[j][i]);
1785
1786 // Use the LP problem to find the correction factors for this pair of
1787 // traces
1788 calculateCompleteFactors(lp, &lpFactorsArray[i][j]);
1789
1790 if (syncState->graphsStream)
1791 {
1792 analysisData->graphs->lps[i][j]= lp;
1793 }
1794 else
1795 {
1796 glp_delete_prob(lp);
1797 destroyFactorsCHull(lpFactors);
1798 }
1799 }
1800 }
1801
1802 g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS),
1803 TRUE);
1804 }
1805 #endif
1806
1807
1808 /*
1809 * Compute synchronization accuracy information using a linear programming
1810 * approach. Write the neccessary data files and plot lines in the gnuplot
1811 * script.
1812 *
1813 * When the solver library, glpk, is not available at build time nothing is
1814 * actually produced.
1815 *
1816 * Args:
1817 * syncState: container for synchronization data
1818 * i: first trace number
1819 * j: second trace number, garanteed to be larger than i
1820 */
1821 static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
1822 const unsigned int i, const unsigned int j)
1823 {
1824 #ifdef HAVE_LIBGLPK
1825 unsigned int it;
1826 AnalysisDataEval* analysisData= syncState->analysisData;
1827 AnalysisGraphsEval* graphs= analysisData->graphs;
1828 GQueue*** hullArray= ((AnalysisDataCHull*)
1829 analysisData->chullSS->analysisData)->hullArray;
1830 FactorsCHull* lpFactors= &graphs->lpFactorsArray[j][i];
1831 glp_prob* lp= graphs->lps[j][i];
1832
1833 if (lpFactors->type == MIDDLE)
1834 {
1835 int retval;
1836 char* cwd;
1837 char fileName[40];
1838 FILE* fp;
1839 double* xValues;
1840 unsigned int xBegin, xEnd;
1841 double interval;
1842 const unsigned int graphPointNb= 1000;
1843
1844 // Open the data file
1845 snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j);
1846 fileName[sizeof(fileName) - 1]= '\0';
1847
1848 cwd= changeToGraphDir(syncState->graphsDir);
1849
1850 if ((fp= fopen(fileName, "w")) == NULL)
1851 {
1852 g_error(strerror(errno));
1853 }
1854 fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1855
1856 retval= chdir(cwd);
1857 if (retval == -1)
1858 {
1859 g_error(strerror(errno));
1860 }
1861 free(cwd);
1862
1863 // Build the list of absisca values for the points in the accuracy graph
1864 g_assert_cmpuint(graphPointNb, >=, 4);
1865 xValues= malloc(graphPointNb * sizeof(double));
1866 xValues[0]= graphs->bounds[j][i].min;
1867 xValues[graphPointNb - 1]= graphs->bounds[j][i].max;
1868 xValues[1]= MIN(((Point*) g_queue_peek_head(hullArray[i][j]))->x,
1869 ((Point*) g_queue_peek_head(hullArray[j][i]))->x);
1870 xValues[graphPointNb - 2]= MAX(((Point*)
1871 g_queue_peek_tail(hullArray[i][j]))->x, ((Point*)
1872 g_queue_peek_tail(hullArray[j][i]))->x);
1873
1874 if (xValues[0] == xValues[1])
1875 {
1876 xBegin= 0;
1877 }
1878 else
1879 {
1880 xBegin= 1;
1881 }
1882 if (xValues[graphPointNb - 2] == xValues[graphPointNb - 1])
1883 {
1884 xEnd= graphPointNb - 1;
1885 }
1886 else
1887 {
1888 xEnd= graphPointNb - 2;
1889 }
1890 interval= (xValues[xEnd] - xValues[xBegin]) / (graphPointNb - 1);
1891
1892 for (it= xBegin; it <= xEnd; it++)
1893 {
1894 xValues[it]= xValues[xBegin] + interval * (it - xBegin);
1895 }
1896
1897 /* For each absisca value and each optimisation direction, solve the LP
1898 * and write a line in the data file */
1899 for (it= 0; it < graphPointNb; it++)
1900 {
1901 unsigned int it2;
1902 int directions[]= {GLP_MIN, GLP_MAX};
1903
1904 glp_set_obj_coef(lp, 1, 1.);
1905 glp_set_obj_coef(lp, 2, xValues[it]);
1906
1907 fprintf(fp, "%25.9f %25.9f", xValues[it], lpFactors->approx->offset
1908 + lpFactors->approx->drift * xValues[it]);
1909 for (it2= 0; it2 < sizeof(directions) / sizeof(*directions); it2++)
1910 {
1911 int status;
1912
1913 glp_set_obj_dir(lp, directions[it2]);
1914 retval= glp_simplex(lp, NULL);
1915 status= glp_get_status(lp);
1916
1917 g_assert(retval == 0 && status == GLP_OPT);
1918 fprintf(fp, " %25.9f", glp_get_obj_val(lp));
1919 }
1920 fprintf(fp, "\n");
1921 }
1922
1923 free(xValues);
1924 fclose(fp);
1925
1926 fprintf(syncState->graphsStream,
1927 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1928 "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
1929 "title \"Synchronization accuracy\" "
1930 "with filledcurves linewidth 2 linetype 1 "
1931 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i,
1932 j);
1933 }
1934 #endif
1935 }
1936
1937
1938 /*
1939 * Write the analysis-specific graph lines in the gnuplot script.
1940 *
1941 * When the solver library, glpk, is not available at build time nothing is
1942 * actually produced.
1943 *
1944 * Args:
1945 * syncState: container for synchronization data
1946 * i: first trace number
1947 * j: second trace number, garanteed to be larger than i
1948 */
1949 static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
1950 const unsigned int i, const unsigned int j)
1951 {
1952 #ifdef HAVE_LIBGLPK
1953 if (((AnalysisDataEval*)
1954 syncState->analysisData)->graphs->lpFactorsArray[j][i].type ==
1955 MIDDLE)
1956 {
1957 fprintf(syncState->graphsStream,
1958 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1959 "using 1:(($3 - $2) / clock_freq_%2$u) notitle "
1960 "with lines linewidth 2 linetype 1 "
1961 "linecolor rgb \"gray60\", \\\n"
1962 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1963 "using 1:(($4 - $2) / clock_freq_%2$u) notitle "
1964 "with lines linewidth 2 linetype 1 "
1965 "linecolor rgb \"gray60\", \\\n", i, j);
1966 }
1967 #endif
1968 }
1969
1970
1971 /*
1972 * Write the analysis-specific graph lines in the gnuplot script.
1973 *
1974 * Args:
1975 * syncState: container for synchronization data
1976 * i: first trace number
1977 * j: second trace number, garanteed to be larger than i
1978 */
1979 static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
1980 const unsigned int i, const unsigned int j)
1981 {
1982 #ifdef HAVE_LIBGLPK
1983 fprintf(syncState->graphsStream,
1984 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1985 "using 1:3:4 "
1986 "title \"Synchronization accuracy\" "
1987 "with filledcurves linewidth 2 linetype 1 "
1988 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j);
1989 #endif
1990 }
1991
1992
1993 /*
1994 * Write the analysis-specific graph lines in the gnuplot script.
1995 *
1996 * Args:
1997 * syncState: container for synchronization data
1998 * i: first trace number
1999 * j: second trace number, garanteed to be larger than i
2000 */
2001 static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
2002 const unsigned int i, const unsigned int j)
2003 {
2004 AnalysisDataEval* analysisData= syncState->analysisData;
2005
2006 analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS,
2007 i, j);
2008 }
LTTng 2.x Viewer (LTTV)
This page took 0.106562 seconds and 4 git commands to generate.