projects / lttv.git / blob
? search:


0872eb6dd8aa7c7762e7606e87963009320de1eb
[lttv.git] / lttv / lttv / sync / event_analysis_eval.c
1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
3 *
4 * This program is free software: you can redistribute it and/or modify it
5 * under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or (at
7 * your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
12 * License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #define _GNU_SOURCE
19 #define _ISOC99_SOURCE
20
21 #ifdef HAVE_CONFIG_H
22 #include <config.h>
23 #endif
24
25 #include <arpa/inet.h>
26 #include <errno.h>
27 #include <math.h>
28 #include <netinet/in.h>
29 #include <stddef.h>
30 #include <stdlib.h>
31 #include <stdio.h>
32 #include <string.h>
33 #include <sys/socket.h>
34 #include <unistd.h>
35
36 #include "lookup3.h"
37 #include "sync_chain.h"
38 #include "event_analysis_chull.h"
39
40 #include "event_analysis_eval.h"
41
42
43 struct WriteHistogramInfo
44 {
45 GHashTable* rttInfo;
46 FILE* graphsStream;
47 };
48
49 #ifdef HAVE_LIBGLPK
50 struct LPAddRowInfo
51 {
52 glp_prob* lp;
53 int boundType;
54 GArray* iArray, * jArray, * aArray;
55 };
56 #endif
57
58 // Functions common to all analysis modules
59 static void initAnalysisEval(SyncState* const syncState);
60 static void destroyAnalysisEval(SyncState* const syncState);
61
62 static void analyzeMessageEval(SyncState* const syncState, Message* const
63 message);
64 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
65 exchange);
66 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
67 broadcast);
68 static GArray* finalizeAnalysisEval(SyncState* const syncState);
69 static void printAnalysisStatsEval(SyncState* const syncState);
70 static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
71 const unsigned int i, const unsigned int j);
72 static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
73 const unsigned int i, const unsigned int j);
74 static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
75 const unsigned int i, const unsigned int j);
76 static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
77 const unsigned int i, const unsigned int j);
78
79 // Functions specific to this module
80 static guint ghfRttKeyHash(gconstpointer key);
81 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b);
82 static void gdnDestroyRttKey(gpointer data);
83 static void gdnDestroyDouble(gpointer data);
84 static void readRttInfo(GHashTable* rttInfo, FILE* rttFile);
85 static void positionStream(FILE* stream);
86
87 static void gfSum(gpointer data, gpointer userData);
88 static void gfSumSquares(gpointer data, gpointer userData);
89 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
90 user_data);
91
92 static void hitBin(struct Bins* const bins, const double value);
93 static unsigned int binNum(const double value) __attribute__((pure));
94 static double binStart(const unsigned int binNum) __attribute__((pure));
95 static double binEnd(const unsigned int binNum) __attribute__((pure));
96 static uint32_t normalTotal(struct Bins* const bins) __attribute__((const));
97
98 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
99 graphsDir, const struct RttKey* const rttKey);
100 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
101 histogram);
102 static void gdnDestroyAnalysisHistogramEval(gpointer data);
103 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer
104 user_data);
105 static void dumpBinToFile(const struct Bins* const bins, FILE* const file);
106 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
107 double* minRtt, AnalysisHistogramEval* const histogram);
108
109 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
110 e2);
111
112 static void finalizeAnalysisEvalLP(SyncState* const syncState);
113 // The next group of functions is only needed when computing synchronization
114 // accuracy.
115 #ifdef HAVE_LIBGLPK
116 static glp_prob* lpCreateProblem(GQueue* const lowerHull, GQueue* const
117 upperHull);
118 static void gfLPAddRow(gpointer data, gpointer user_data);
119 static Factors* calculateFactors(glp_prob* const lp, const int direction);
120 static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull*
121 factors);
122 static FactorsCHull** createAllFactors(const unsigned int traceNb);
123 #endif
124
125
126 // initialized in registerAnalysisEval()
127 double binBase;
128
129 static AnalysisModule analysisModuleEval= {
130 .name= "eval",
131 .initAnalysis= &initAnalysisEval,
132 .destroyAnalysis= &destroyAnalysisEval,
133 .analyzeMessage= &analyzeMessageEval,
134 .analyzeExchange= &analyzeExchangeEval,
135 .analyzeBroadcast= &analyzeBroadcastEval,
136 .finalizeAnalysis= &finalizeAnalysisEval,
137 .printAnalysisStats= &printAnalysisStatsEval,
138 .graphFunctions= {
139 .writeTraceTimeBackPlots= &writeAnalysisTraceTimeBackPlotsEval,
140 .writeTraceTimeForePlots= &writeAnalysisTraceTimeForePlotsEval,
141 .writeTraceTraceBackPlots= &writeAnalysisTraceTraceBackPlotsEval,
142 .writeTraceTraceForePlots= &writeAnalysisTraceTraceForePlotsEval,
143 }
144 };
145
146 static ModuleOption optionEvalRttFile= {
147 .longName= "eval-rtt-file",
148 .hasArg= REQUIRED_ARG,
149 .optionHelp= "specify the file containing RTT information",
150 .argHelp= "FILE",
151 };
152
153
154 /*
155 * Analysis module registering function
156 */
157 void registerAnalysisEval()
158 {
159 binBase= exp10(6. / (BIN_NB - 3));
160
161 g_queue_push_tail(&analysisModules, &analysisModuleEval);
162 g_queue_push_tail(&moduleOptions, &optionEvalRttFile);
163 }
164
165
166 /*
167 * Analysis init function
168 *
169 * This function is called at the beginning of a synchronization run for a set
170 * of traces.
171 *
172 * Args:
173 * syncState container for synchronization data.
174 */
175 static void initAnalysisEval(SyncState* const syncState)
176 {
177 AnalysisDataEval* analysisData;
178 unsigned int i, j;
179
180 analysisData= malloc(sizeof(AnalysisDataEval));
181 syncState->analysisData= analysisData;
182
183 analysisData->rttInfo= g_hash_table_new_full(&ghfRttKeyHash,
184 &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble);
185 if (optionEvalRttFile.arg)
186 {
187 FILE* rttStream;
188 int retval;
189
190 rttStream= fopen(optionEvalRttFile.arg, "r");
191 if (rttStream == NULL)
192 {
193 g_error(strerror(errno));
194 }
195
196 readRttInfo(analysisData->rttInfo, rttStream);
197
198 retval= fclose(rttStream);
199 if (retval == EOF)
200 {
201 g_error(strerror(errno));
202 }
203 }
204
205 if (syncState->stats)
206 {
207 analysisData->stats= calloc(1, sizeof(AnalysisStatsEval));
208 analysisData->stats->broadcastDiffSum= 0.;
209
210 analysisData->stats->messageStats= malloc(syncState->traceNb *
211 sizeof(MessageStats*));
212 for (i= 0; i < syncState->traceNb; i++)
213 {
214 analysisData->stats->messageStats[i]= calloc(syncState->traceNb,
215 sizeof(MessageStats));
216 }
217
218 analysisData->stats->exchangeRtt=
219 g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual,
220 &gdnDestroyRttKey, &gdnDestroyDouble);
221
222 #ifdef HAVE_LIBGLPK
223 analysisData->stats->chFactorsArray= NULL;
224 analysisData->stats->lpFactorsArray= NULL;
225 #endif
226 }
227
228 if (syncState->graphsStream)
229 {
230 AnalysisGraphsEval* graphs= malloc(sizeof(AnalysisGraphsEval));
231
232 analysisData->graphs= graphs;
233
234 graphs->histograms= g_hash_table_new_full(&ghfRttKeyHash,
235 &gefRttKeyEqual, &gdnDestroyRttKey,
236 &gdnDestroyAnalysisHistogramEval);
237
238 graphs->bounds= malloc(syncState->traceNb * sizeof(Bounds*));
239 for (i= 0; i < syncState->traceNb; i++)
240 {
241 graphs->bounds[i]= malloc(i * sizeof(Bounds));
242 for (j= 0; j < i; j++)
243 {
244 graphs->bounds[i][j].min= UINT64_MAX;
245 graphs->bounds[i][j].max= 0;
246 }
247 }
248
249 #ifdef HAVE_LIBGLPK
250 graphs->lps= NULL;
251 graphs->lpFactorsArray= NULL;
252 #endif
253 }
254
255 if (syncState->stats || syncState->graphsStream)
256 {
257 GList* result;
258
259 analysisData->chullSS= malloc(sizeof(SyncState));
260 memcpy(analysisData->chullSS, syncState, sizeof(SyncState));
261 analysisData->chullSS->stats= false;
262 analysisData->chullSS->analysisData= NULL;
263 result= g_queue_find_custom(&analysisModules, "chull",
264 &gcfCompareAnalysis);
265 analysisData->chullSS->analysisModule= (AnalysisModule*) result->data;
266 analysisData->chullSS->analysisModule->initAnalysis(analysisData->chullSS);
267 }
268 }
269
270
271 /*
272 * Create and open files used to store histogram points to generate graphs.
273 * Create data structures to store histogram points during analysis.
274 *
275 * Args:
276 * graphsDir: folder where to write files
277 * rttKey: host pair, make sure saddr < daddr
278 */
279 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
280 graphsDir, const struct RttKey* const rttKey)
281 {
282 int retval;
283 unsigned int i;
284 char* cwd;
285 char name[60], saddr[16], daddr[16];
286 AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram));
287 const struct {
288 size_t pointsOffset;
289 const char* fileName;
290 const char* host1, *host2;
291 } loopValues[]= {
292 {offsetof(AnalysisHistogramEval, ttSendPoints),
293 "analysis_eval_tt-%s_to_%s.data", saddr, daddr},
294 {offsetof(AnalysisHistogramEval, ttRecvPoints),
295 "analysis_eval_tt-%s_to_%s.data", daddr, saddr},
296 {offsetof(AnalysisHistogramEval, hrttPoints),
297 "analysis_eval_hrtt-%s_and_%s.data", saddr, daddr},
298 };
299
300 histogram->ttSendBins.min= BIN_NB - 1;
301 histogram->ttRecvBins.min= BIN_NB - 1;
302 histogram->hrttBins.min= BIN_NB - 1;
303
304 convertIP(saddr, rttKey->saddr);
305 convertIP(daddr, rttKey->daddr);
306
307 cwd= changeToGraphsDir(graphsDir);
308
309 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
310 {
311 retval= snprintf(name, sizeof(name), loopValues[i].fileName,
312 loopValues[i].host1, loopValues[i].host2);
313 if (retval > sizeof(name) - 1)
314 {
315 name[sizeof(name) - 1]= '\0';
316 }
317 if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)=
318 fopen(name, "w")) == NULL)
319 {
320 g_error(strerror(errno));
321 }
322 }
323
324 retval= chdir(cwd);
325 if (retval == -1)
326 {
327 g_error(strerror(errno));
328 }
329 free(cwd);
330
331 return histogram;
332 }
333
334
335 /*
336 * Close files used to store histogram points to generate graphs.
337 *
338 * Args:
339 * graphsDir: folder where to write files
340 * rttKey: host pair, make sure saddr < daddr
341 */
342 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
343 histogram)
344 {
345 unsigned int i;
346 int retval;
347 const struct {
348 size_t pointsOffset;
349 } loopValues[]= {
350 {offsetof(AnalysisHistogramEval, ttSendPoints)},
351 {offsetof(AnalysisHistogramEval, ttRecvPoints)},
352 {offsetof(AnalysisHistogramEval, hrttPoints)},
353 };
354
355 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
356 {
357 retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset));
358 if (retval != 0)
359 {
360 g_error(strerror(errno));
361 }
362 }
363
364 free(histogram);
365 }
366
367
368 /*
369 * A GDestroyNotify function for g_hash_table_new_full()
370 *
371 * Args:
372 * data: AnalysisHistogramEval*
373 */
374 static void gdnDestroyAnalysisHistogramEval(gpointer data)
375 {
376 destroyAnalysisHistogramEval(data);
377 }
378
379
380 /*
381 * A GHFunc for g_hash_table_foreach()
382 *
383 * Args:
384 * key: RttKey* where saddr < daddr
385 * value: AnalysisHistogramEval*
386 * user_data struct WriteHistogramInfo*
387 */
388 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer user_data)
389 {
390 double* rtt1, * rtt2;
391 struct RttKey* rttKey= key;
392 struct RttKey oppositeRttKey= {.saddr= rttKey->daddr, .daddr=
393 rttKey->saddr};
394 AnalysisHistogramEval* histogram= value;
395 struct WriteHistogramInfo* info= user_data;
396
397 rtt1= g_hash_table_lookup(info->rttInfo, rttKey);
398 rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey);
399
400 if (rtt1 == NULL)
401 {
402 rtt1= rtt2;
403 }
404 else if (rtt2 != NULL)
405 {
406 rtt1= MIN(rtt1, rtt2);
407 }
408
409 dumpBinToFile(&histogram->ttSendBins, histogram->ttSendPoints);
410 dumpBinToFile(&histogram->ttRecvBins, histogram->ttRecvPoints);
411 dumpBinToFile(&histogram->hrttBins, histogram->hrttPoints);
412 writeHistogram(info->graphsStream, rttKey, rtt1, histogram);
413 }
414
415
416 /*
417 * Write the content of one bin in a histogram point file
418 *
419 * Args:
420 * bin: array of values that make up a histogram
421 * file: FILE*, write to this file
422 */
423 static void dumpBinToFile(const struct Bins* const bins, FILE* const file)
424 {
425 unsigned int i;
426
427 // The first and last bins are skipped, see struct Bins
428 for (i= 1; i < BIN_NB - 1; i++)
429 {
430 if (bins->bin[i] > 0)
431 {
432 fprintf(file, "%20.9f %20.9f %20.9f\n", (binStart(i) + binEnd(i))
433 / 2., (double) bins->bin[i] / ((binEnd(i) - binStart(i)) *
434 bins->total), binEnd(i) - binStart(i));
435 }
436 }
437 }
438
439
440 /*
441 * Write the analysis-specific plot in the gnuplot script.
442 *
443 * Args:
444 * graphsStream: write to this file
445 * rttKey: must be sorted such that saddr < daddr
446 * minRtt: if available, else NULL
447 * histogram: struct that contains the bins for the pair of traces
448 * identified by rttKey
449 */
450 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
451 double* minRtt, AnalysisHistogramEval* const histogram)
452 {
453 char saddr[16], daddr[16];
454
455 convertIP(saddr, rttKey->saddr);
456 convertIP(daddr, rttKey->daddr);
457
458 fprintf(graphsStream,
459 "\nreset\n"
460 "set output \"histogram-%s-%s.eps\"\n"
461 "set title \"\"\n"
462 "set xlabel \"Message Latency (s)\"\n"
463 "set ylabel \"Proportion of messages per second\"\n", saddr, daddr);
464
465 if (minRtt != NULL)
466 {
467 fprintf(graphsStream,
468 "set arrow from %.9f, 0 rto 0, graph 1 "
469 "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
470 / 2);
471 }
472
473 if (normalTotal(&histogram->ttSendBins) ||
474 normalTotal(&histogram->ttRecvBins) ||
475 normalTotal(&histogram->hrttBins))
476 {
477 fprintf(graphsStream, "plot \\\n");
478
479 if (normalTotal(&histogram->hrttBins))
480 {
481 fprintf(graphsStream,
482 "\t\"analysis_eval_hrtt-%s_and_%s.data\" "
483 "title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
484 "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
485 saddr, daddr);
486 }
487
488 if (normalTotal(&histogram->ttSendBins))
489 {
490 fprintf(graphsStream,
491 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
492 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
493 "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
494 saddr, daddr);
495 }
496
497 if (normalTotal(&histogram->ttRecvBins))
498 {
499 fprintf(graphsStream,
500 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
501 "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
502 "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
503 daddr, saddr);
504 }
505
506 // Remove the ",\\\n" from the last graph plot line
507 if (ftruncate(fileno(graphsStream), ftell(graphsStream) - 3) == -1)
508 {
509 g_error(strerror(errno));
510 }
511 if (fseek(graphsStream, 0, SEEK_END) == -1)
512 {
513 g_error(strerror(errno));
514 }
515 fprintf(graphsStream, "\n");
516 }
517 }
518
519
520 /*
521 * Analysis destroy function
522 *
523 * Free the analysis specific data structures
524 *
525 * Args:
526 * syncState container for synchronization data.
527 */
528 static void destroyAnalysisEval(SyncState* const syncState)
529 {
530 unsigned int i;
531 AnalysisDataEval* analysisData;
532
533 analysisData= (AnalysisDataEval*) syncState->analysisData;
534
535 if (analysisData == NULL)
536 {
537 return;
538 }
539
540 g_hash_table_destroy(analysisData->rttInfo);
541
542 if (syncState->stats)
543 {
544 AnalysisStatsEval* stats= analysisData->stats;
545
546 for (i= 0; i < syncState->traceNb; i++)
547 {
548 free(stats->messageStats[i]);
549 }
550 free(stats->messageStats);
551
552 g_hash_table_destroy(stats->exchangeRtt);
553
554 #ifdef HAVE_LIBGLPK
555 freeAllFactors(syncState->traceNb, stats->chFactorsArray);
556 freeAllFactors(syncState->traceNb, stats->lpFactorsArray);
557 #endif
558
559 free(stats);
560 }
561
562 if (syncState->graphsStream)
563 {
564 AnalysisGraphsEval* graphs= analysisData->graphs;
565
566 if (graphs->histograms)
567 {
568 g_hash_table_destroy(graphs->histograms);
569 }
570
571 for (i= 0; i < syncState->traceNb; i++)
572 {
573 free(graphs->bounds[i]);
574 }
575 free(graphs->bounds);
576
577 #ifdef HAVE_LIBGLPK
578 for (i= 0; i < syncState->traceNb; i++)
579 {
580 unsigned int j;
581
582 for (j= 0; j < i; j++)
583 {
584 // There seems to be a memory leak in glpk, valgrind reports a
585 // loss (reachable) even if the problem is deleted
586 glp_delete_prob(graphs->lps[i][j]);
587 }
588 free(graphs->lps[i]);
589 }
590 free(graphs->lps);
591
592 if (!syncState->stats)
593 {
594 freeAllFactors(syncState->traceNb, graphs->lpFactorsArray);
595 }
596 #endif
597
598 free(graphs);
599 }
600
601 if (syncState->stats || syncState->graphsStream)
602 {
603 analysisData->chullSS->analysisModule->destroyAnalysis(analysisData->chullSS);
604 free(analysisData->chullSS);
605 }
606
607 free(syncState->analysisData);
608 syncState->analysisData= NULL;
609 }
610
611
612 /*
613 * Perform analysis on an event pair.
614 *
615 * Check if there is message inversion or messages that are too fast.
616 *
617 * Args:
618 * syncState container for synchronization data
619 * message structure containing the events
620 */
621 static void analyzeMessageEval(SyncState* const syncState, Message* const
622 message)
623 {
624 AnalysisDataEval* analysisData= syncState->analysisData;
625 MessageStats* messageStats;
626 double* rtt;
627 double tt;
628 struct RttKey rttKey;
629
630 g_assert(message->inE->type == TCP);
631
632 if (syncState->stats)
633 {
634 messageStats=
635 &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
636 messageStats->total++;
637 }
638
639 tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
640 if (tt <= 0)
641 {
642 if (syncState->stats)
643 {
644 messageStats->inversionNb++;
645 }
646 }
647 else if (syncState->graphsStream)
648 {
649 struct RttKey rttKey= {
650 .saddr=MIN(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
651 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
652 .daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
653 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
654 };
655 AnalysisHistogramEval* histogram=
656 g_hash_table_lookup(analysisData->graphs->histograms, &rttKey);
657
658 if (histogram == NULL)
659 {
660 struct RttKey* tableKey= malloc(sizeof(*tableKey));
661
662 histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey);
663 memcpy(tableKey, &rttKey, sizeof(*tableKey));
664 g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram);
665 }
666
667 if (message->inE->event.udpEvent->datagramKey->saddr <
668 message->inE->event.udpEvent->datagramKey->daddr)
669 {
670 hitBin(&histogram->ttSendBins, tt);
671 }
672 else
673 {
674 hitBin(&histogram->ttRecvBins, tt);
675 }
676 }
677
678 if (syncState->stats)
679 {
680 rttKey.saddr=
681 message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
682 rttKey.daddr=
683 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
684 rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
685 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
686 rttKey.daddr, rtt ? *rtt : NAN);
687
688 if (rtt)
689 {
690 g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
691 if (tt < *rtt / 2.)
692 {
693 messageStats->tooFastNb++;
694 }
695 }
696 else
697 {
698 messageStats->noRTTInfoNb++;
699 }
700 }
701
702 if (syncState->graphsStream)
703 {
704 updateBounds(analysisData->graphs->bounds, message->inE,
705 message->outE);
706 }
707
708 if (syncState->stats || syncState->graphsStream)
709 {
710 analysisData->chullSS->analysisModule->analyzeMessage(analysisData->chullSS,
711 message);
712 }
713 }
714
715
716 /*
717 * Perform analysis on multiple messages
718 *
719 * Measure the RTT
720 *
721 * Args:
722 * syncState container for synchronization data
723 * exchange structure containing the messages
724 */
725 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
726 exchange)
727 {
728 AnalysisDataEval* analysisData= syncState->analysisData;
729 Message* m1= g_queue_peek_tail(exchange->acks);
730 Message* m2= exchange->message;
731 struct RttKey* rttKey;
732 double* rtt, * exchangeRtt;
733
734 g_assert(m1->inE->type == TCP);
735
736 // (T2 - T1) - (T3 - T4)
737 rtt= malloc(sizeof(double));
738 *rtt= wallTimeSub(&m1->inE->wallTime, &m1->outE->wallTime) -
739 wallTimeSub(&m2->outE->wallTime, &m2->inE->wallTime);
740
741 rttKey= malloc(sizeof(struct RttKey));
742 rttKey->saddr=
743 MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
744 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
745 rttKey->daddr=
746 MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
747 m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
748
749 if (syncState->graphsStream)
750 {
751 AnalysisHistogramEval* histogram=
752 g_hash_table_lookup(analysisData->graphs->histograms, rttKey);
753
754 if (histogram == NULL)
755 {
756 struct RttKey* tableKey= malloc(sizeof(*tableKey));
757
758 histogram= constructAnalysisHistogramEval(syncState->graphsDir,
759 rttKey);
760 memcpy(tableKey, rttKey, sizeof(*tableKey));
761 g_hash_table_insert(analysisData->graphs->histograms, tableKey,
762 histogram);
763 }
764
765 hitBin(&histogram->hrttBins, *rtt / 2);
766 }
767
768 if (syncState->stats)
769 {
770 exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
771 rttKey);
772
773 if (exchangeRtt)
774 {
775 if (*rtt < *exchangeRtt)
776 {
777 g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
778 }
779 else
780 {
781 free(rttKey);
782 free(rtt);
783 }
784 }
785 else
786 {
787 g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
788 }
789 }
790 else
791 {
792 free(rttKey);
793 free(rtt);
794 }
795 }
796
797
798 /*
799 * Perform analysis on muliple events
800 *
801 * Sum the broadcast differential delays
802 *
803 * Args:
804 * syncState container for synchronization data
805 * broadcast structure containing the events
806 */
807 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
808 broadcast)
809 {
810 AnalysisDataEval* analysisData= syncState->analysisData;
811
812 if (syncState->stats)
813 {
814 double sum= 0, squaresSum= 0;
815 double y;
816
817 g_queue_foreach(broadcast->events, &gfSum, &sum);
818 g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
819
820 analysisData->stats->broadcastNb++;
821 // Because of numerical errors, this can at times be < 0
822 y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
823 g_queue_get_length(broadcast->events), 2.);
824 if (y > 0)
825 {
826 analysisData->stats->broadcastDiffSum+= sqrt(y);
827 }
828 }
829
830 if (syncState->graphsStream)
831 {
832 unsigned int i, j;
833 GArray* events;
834 unsigned int eventNb= broadcast->events->length;
835
836 events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb);
837 g_queue_foreach(broadcast->events, &gfAddEventToArray, events);
838
839 for (i= 0; i < eventNb; i++)
840 {
841 for (j= 0; j < eventNb; j++)
842 {
843 Event* eventI= g_array_index(events, Event*, i), * eventJ=
844 g_array_index(events, Event*, j);
845
846 if (eventI->traceNum < eventJ->traceNum)
847 {
848 updateBounds(analysisData->graphs->bounds, eventI, eventJ);
849 }
850 }
851 }
852
853 g_array_free(events, TRUE);
854 }
855 }
856
857
858 /*
859 * Finalize the factor calculations. Since this module does not really
860 * calculate factors, identity factors are returned. Instead, histograms are
861 * written out and histogram structures are freed.
862 *
863 * Args:
864 * syncState container for synchronization data.
865 *
866 * Returns:
867 * Factors[traceNb] identity factors for each trace
868 */
869 static GArray* finalizeAnalysisEval(SyncState* const syncState)
870 {
871 GArray* factors;
872 unsigned int i;
873 AnalysisDataEval* analysisData= syncState->analysisData;
874
875 if (syncState->graphsStream && analysisData->graphs->histograms)
876 {
877 g_hash_table_foreach(analysisData->graphs->histograms,
878 &ghfWriteHistogram, &(struct WriteHistogramInfo) {.rttInfo=
879 analysisData->rttInfo, .graphsStream= syncState->graphsStream});
880 g_hash_table_destroy(analysisData->graphs->histograms);
881 analysisData->graphs->histograms= NULL;
882 }
883
884 finalizeAnalysisEvalLP(syncState);
885
886 factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
887 syncState->traceNb);
888 g_array_set_size(factors, syncState->traceNb);
889 for (i= 0; i < syncState->traceNb; i++)
890 {
891 Factors* e;
892
893 e= &g_array_index(factors, Factors, i);
894 e->drift= 1.;
895 e->offset= 0.;
896 }
897
898 return factors;
899 }
900
901
902 /*
903 * Print statistics related to analysis. Must be called after
904 * finalizeAnalysis.
905 *
906 * Args:
907 * syncState container for synchronization data.
908 */
909 static void printAnalysisStatsEval(SyncState* const syncState)
910 {
911 AnalysisDataEval* analysisData;
912 unsigned int i, j, k;
913 unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0;
914 int charNb;
915
916 if (!syncState->stats)
917 {
918 return;
919 }
920
921 analysisData= (AnalysisDataEval*) syncState->analysisData;
922
923 printf("Synchronization evaluation analysis stats:\n");
924 if (analysisData->stats->broadcastNb)
925 {
926 printf("\tsum of broadcast differential delays: %g\n",
927 analysisData->stats->broadcastDiffSum);
928 printf("\taverage broadcast differential delay: %g\n",
929 analysisData->stats->broadcastDiffSum /
930 analysisData->stats->broadcastNb);
931 }
932
933 printf("\tIndividual evaluation:\n"
934 "\t\tTrace pair Inversions Too fast No RTT info Total\n");
935
936 for (i= 0; i < syncState->traceNb; i++)
937 {
938 for (j= i + 1; j < syncState->traceNb; j++)
939 {
940 MessageStats* messageStats;
941 struct {
942 unsigned int t1, t2;
943 } loopValues[]= {
944 {i, j},
945 {j, i}
946 };
947
948 for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++)
949 {
950 messageStats=
951 &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
952
953 printf("\t\t%3d - %-3d ", loopValues[k].t1, loopValues[k].t2);
954 printf("%u (%u%%)%n", messageStats->inversionNb, (unsigned
955 int) ceil((double) messageStats->inversionNb /
956 messageStats->total * 100), &charNb);
957 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
958 printf("%u (%u%%)%n", messageStats->tooFastNb, (unsigned int)
959 ceil((double) messageStats->tooFastNb /
960 messageStats->total * 100), &charNb);
961 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
962 1, " ", messageStats->noRTTInfoNb, messageStats->total);
963
964 totInversion+= messageStats->inversionNb;
965 totTooFast+= messageStats->tooFastNb;
966 totNoInfo+= messageStats->noRTTInfoNb;
967 totTotal+= messageStats->total;
968 }
969 }
970 }
971
972 printf("\t\t total ");
973 printf("%u (%u%%)%n", totInversion, (unsigned int) ceil((double)
974 totInversion / totTotal * 100), &charNb);
975 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
976 printf("%u (%u%%)%n", totTooFast, (unsigned int) ceil((double) totTooFast
977 / totTotal * 100), &charNb);
978 printf("%*s%-10u %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
979 totNoInfo, totTotal);
980
981 printf("\tRound-trip times:\n"
982 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
983 g_hash_table_foreach(analysisData->stats->exchangeRtt,
984 &ghfPrintExchangeRtt, analysisData->rttInfo);
985
986 #ifdef HAVE_LIBGLPK
987 printf("\tConvex hull factors comparisons:\n"
988 "\t\tTrace pair Factors type Differences (lp - chull)\n"
989 "\t\t a0 a1\n"
990 "\t\t Min Max Min Max\n");
991
992 for (i= 0; i < syncState->traceNb; i++)
993 {
994 for (j= 0; j < i; j++)
995 {
996 FactorsCHull* chFactors= &analysisData->stats->chFactorsArray[i][j];
997 FactorsCHull* lpFactors= &analysisData->stats->lpFactorsArray[i][j];
998
999 printf("\t\t%3d - %-3d ", i, j);
1000 if (lpFactors->type == chFactors->type)
1001 {
1002 if (lpFactors->type == MIDDLE)
1003 {
1004 printf("%-13s %-10.4g %-10.4g %-10.4g %.4g\n",
1005 approxNames[lpFactors->type],
1006 lpFactors->min->offset - chFactors->min->offset,
1007 lpFactors->max->offset - chFactors->max->offset,
1008 lpFactors->min->drift - chFactors->min->drift,
1009 lpFactors->max->drift - chFactors->max->drift);
1010 }
1011 else if (lpFactors->type == ABSENT)
1012 {
1013 printf("%s\n", approxNames[lpFactors->type]);
1014 }
1015 }
1016 else
1017 {
1018 printf("Different! %s and %s\n", approxNames[lpFactors->type],
1019 approxNames[chFactors->type]);
1020 }
1021 }
1022 }
1023 #endif
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 if (hullPointNb > 0)
1540 {
1541 glp_add_rows(lp, hullPointNb);
1542 }
1543 glp_add_cols(lp, 2);
1544
1545 glp_set_col_name(lp, 1, "a0");
1546 glp_set_col_bnds(lp, 1, GLP_FR, 0., 0.);
1547 glp_set_col_name(lp, 2, "a1");
1548 glp_set_col_bnds(lp, 2, GLP_LO, 0., 0.);
1549
1550 // Add row constraints
1551 g_array_append_val(iArray, zero);
1552 g_array_append_val(jArray, zero);
1553 g_array_append_val(aArray, zeroD);
1554
1555 for (it= 0; it < sizeof(loopValues) / sizeof(*loopValues); it++)
1556 {
1557 g_queue_foreach(loopValues[it].hull, &gfLPAddRow,
1558 &loopValues[it].rowInfo);
1559 }
1560
1561 g_assert_cmpuint(iArray->len, ==, jArray->len);
1562 g_assert_cmpuint(jArray->len, ==, aArray->len);
1563 g_assert_cmpuint(aArray->len - 1, ==, hullPointNb * 2);
1564
1565 glp_load_matrix(lp, aArray->len - 1, &g_array_index(iArray, int, 0),
1566 &g_array_index(jArray, int, 0), &g_array_index(aArray, double, 0));
1567
1568 glp_scale_prob(lp, GLP_SF_AUTO);
1569
1570 g_array_free(iArray, TRUE);
1571 g_array_free(jArray, TRUE);
1572 g_array_free(aArray, TRUE);
1573
1574 return lp;
1575 }
1576
1577
1578 /*
1579 * A GFunc for g_queue_foreach(). Add constraints and bounds for one row.
1580 *
1581 * Args:
1582 * data Point*, synchronization point for which to add an LP row
1583 * (a constraint)
1584 * user_data LPAddRowInfo*
1585 */
1586 static void gfLPAddRow(gpointer data, gpointer user_data)
1587 {
1588 Point* p= data;
1589 struct LPAddRowInfo* rowInfo= user_data;
1590 int indexes[2];
1591 double constraints[2];
1592
1593 indexes[0]= g_array_index(rowInfo->iArray, int, rowInfo->iArray->len - 1) + 1;
1594 indexes[1]= indexes[0];
1595
1596 if (rowInfo->boundType == GLP_UP)
1597 {
1598 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_UP, 0., p->y);
1599 }
1600 else if (rowInfo->boundType == GLP_LO)
1601 {
1602 glp_set_row_bnds(rowInfo->lp, indexes[0], GLP_LO, p->y, 0.);
1603 }
1604 else
1605 {
1606 g_assert_not_reached();
1607 }
1608
1609 g_array_append_vals(rowInfo->iArray, indexes, 2);
1610 indexes[0]= 1;
1611 indexes[1]= 2;
1612 g_array_append_vals(rowInfo->jArray, indexes, 2);
1613 constraints[0]= 1.;
1614 constraints[1]= p->x;
1615 g_array_append_vals(rowInfo->aArray, constraints, 2);
1616 }
1617
1618
1619 /*
1620 * Calculate min or max correction factors (as possible) using an LP problem.
1621 *
1622 * Args:
1623 * lp: A linear programming problem with constraints and bounds
1624 * initialized.
1625 * direction: The type of factors desired. Use GLP_MAX for max
1626 * approximation factors (a1, the drift or slope is the
1627 * largest) and GLP_MIN in the other case.
1628 *
1629 * Returns:
1630 * If the calculation was successful, a new Factors struct. Otherwise, NULL.
1631 * The calculation will fail if the hull assumptions are not respected.
1632 */
1633 static Factors* calculateFactors(glp_prob* const lp, const int direction)
1634 {
1635 int retval, status;
1636 Factors* factors;
1637
1638 glp_set_obj_coef(lp, 1, 0.);
1639 glp_set_obj_coef(lp, 2, 1.);
1640
1641 glp_set_obj_dir(lp, direction);
1642 retval= glp_simplex(lp, NULL);
1643 status= glp_get_status(lp);
1644
1645 if (retval == 0 && status == GLP_OPT)
1646 {
1647 factors= malloc(sizeof(Factors));
1648 factors->offset= glp_get_col_prim(lp, 1);
1649 factors->drift= glp_get_col_prim(lp, 2);
1650 }
1651 else
1652 {
1653 factors= NULL;
1654 }
1655
1656 return factors;
1657 }
1658
1659
1660 /*
1661 * Calculate min, max and approx correction factors (as possible) using an LP
1662 * problem.
1663 *
1664 * Args:
1665 * lp: A linear programming problem with constraints and bounds
1666 * initialized.
1667 *
1668 * Returns:
1669 * Please note that the approximation type may be MIDDLE, INCOMPLETE or
1670 * ABSENT. Unlike in analysis_chull, ABSENT is also used when the hulls do
1671 * not respect assumptions.
1672 */
1673 static void calculateCompleteFactors(glp_prob* const lp, FactorsCHull* factors)
1674 {
1675 factors->min= calculateFactors(lp, GLP_MIN);
1676 factors->max= calculateFactors(lp, GLP_MAX);
1677
1678 if (factors->min && factors->max)
1679 {
1680 factors->type= MIDDLE;
1681 calculateFactorsMiddle(factors);
1682 }
1683 else if (factors->min || factors->max)
1684 {
1685 factors->type= INCOMPLETE;
1686 factors->approx= NULL;
1687 }
1688 else
1689 {
1690 factors->type= ABSENT;
1691 factors->approx= NULL;
1692 }
1693 }
1694
1695
1696 /*
1697 * Create and initialize an array like AnalysisStatsCHull.allFactors
1698 *
1699 * Args:
1700 * traceNb: number of traces
1701 *
1702 * Returns:
1703 * A new array, which can be freed with freeAllFactors()
1704 */
1705 static FactorsCHull** createAllFactors(const unsigned int traceNb)
1706 {
1707 FactorsCHull** factorsArray;
1708 unsigned int i;
1709
1710 factorsArray= malloc(traceNb * sizeof(FactorsCHull*));
1711 for (i= 0; i < traceNb; i++)
1712 {
1713 factorsArray[i]= calloc((i + 1), sizeof(FactorsCHull));
1714
1715 factorsArray[i][i].type= EXACT;
1716 factorsArray[i][i].approx= malloc(sizeof(Factors));
1717 factorsArray[i][i].approx->drift= 1.;
1718 factorsArray[i][i].approx->offset= 0.;
1719 }
1720
1721 return factorsArray;
1722 }
1723 #endif
1724
1725
1726 /*
1727 * Compute synchronization factors using a linear programming approach.
1728 * Compute the factors using analysis_chull. Compare the two.
1729 *
1730 * When the solver library, glpk, is not available at build time, only compute
1731 * the factors using analysis_chull. This is to make sure that module runs its
1732 * finalize function so that its graph functions can be called later.
1733 *
1734 * Args:
1735 * syncState: container for synchronization data
1736 */
1737 static void finalizeAnalysisEvalLP(SyncState* const syncState)
1738 {
1739 AnalysisDataEval* analysisData= syncState->analysisData;
1740 #ifdef HAVE_LIBGLPK
1741 unsigned int i, j;
1742 AnalysisDataCHull* chAnalysisData= analysisData->chullSS->analysisData;
1743 FactorsCHull** lpFactorsArray;
1744
1745 if (!syncState->stats && !syncState->graphsStream)
1746 {
1747 return;
1748 }
1749
1750 /* Because of matching_distributor, this analysis may be called twice.
1751 * Only run it once */
1752 if ((syncState->graphsStream && analysisData->graphs->lps != NULL) ||
1753 (syncState->stats && analysisData->stats->chFactorsArray != NULL))
1754 {
1755 return;
1756 }
1757
1758 lpFactorsArray= createAllFactors(syncState->traceNb);
1759
1760 if (syncState->stats)
1761 {
1762 analysisData->stats->chFactorsArray=
1763 calculateAllFactors(analysisData->chullSS);
1764 analysisData->stats->lpFactorsArray= lpFactorsArray;
1765 }
1766
1767 if (syncState->graphsStream)
1768 {
1769 analysisData->graphs->lps= malloc(syncState->traceNb *
1770 sizeof(glp_prob**));
1771 for (i= 0; i < syncState->traceNb; i++)
1772 {
1773 analysisData->graphs->lps[i]= malloc(i * sizeof(glp_prob*));
1774 }
1775 analysisData->graphs->lpFactorsArray= lpFactorsArray;
1776 }
1777
1778 for (i= 0; i < syncState->traceNb; i++)
1779 {
1780 for (j= 0; j < i; j++)
1781 {
1782 glp_prob* lp;
1783
1784 // Create the LP problem
1785 lp= lpCreateProblem(chAnalysisData->hullArray[i][j],
1786 chAnalysisData->hullArray[j][i]);
1787
1788 // Use the LP problem to find the correction factors for this pair of
1789 // traces
1790 calculateCompleteFactors(lp, &lpFactorsArray[i][j]);
1791
1792 if (syncState->graphsStream)
1793 {
1794 analysisData->graphs->lps[i][j]= lp;
1795 }
1796 else
1797 {
1798 glp_delete_prob(lp);
1799 }
1800 }
1801 }
1802 #endif
1803
1804 g_array_free(analysisData->chullSS->analysisModule->finalizeAnalysis(analysisData->chullSS),
1805 TRUE);
1806 }
1807
1808
1809 /*
1810 * Compute synchronization accuracy information using a linear programming
1811 * approach. Write the neccessary data files and plot lines in the gnuplot
1812 * script.
1813 *
1814 * When the solver library, glpk, is not available at build time nothing is
1815 * actually produced.
1816 *
1817 * Args:
1818 * syncState: container for synchronization data
1819 * i: first trace number
1820 * j: second trace number, garanteed to be larger than i
1821 */
1822 static void writeAnalysisTraceTimeBackPlotsEval(SyncState* const syncState,
1823 const unsigned int i, const unsigned int j)
1824 {
1825 #ifdef HAVE_LIBGLPK
1826 unsigned int it;
1827 AnalysisDataEval* analysisData= syncState->analysisData;
1828 AnalysisGraphsEval* graphs= analysisData->graphs;
1829 GQueue*** hullArray= ((AnalysisDataCHull*)
1830 analysisData->chullSS->analysisData)->hullArray;
1831 FactorsCHull* lpFactors= &graphs->lpFactorsArray[j][i];
1832 glp_prob* lp= graphs->lps[j][i];
1833
1834 if (lpFactors->type == MIDDLE)
1835 {
1836 int retval;
1837 char* cwd;
1838 char fileName[40];
1839 FILE* fp;
1840 double* xValues;
1841 unsigned int xBegin, xEnd;
1842 double interval;
1843 const unsigned int graphPointNb= 1000;
1844
1845 // Open the data file
1846 snprintf(fileName, 40, "analysis_eval_accuracy-%03u_and_%03u.data", i, j);
1847 fileName[sizeof(fileName) - 1]= '\0';
1848
1849 cwd= changeToGraphsDir(syncState->graphsDir);
1850
1851 if ((fp= fopen(fileName, "w")) == NULL)
1852 {
1853 g_error(strerror(errno));
1854 }
1855 fprintf(fp, "#%-24s %-25s %-25s %-25s\n", "x", "middle", "min", "max");
1856
1857 retval= chdir(cwd);
1858 if (retval == -1)
1859 {
1860 g_error(strerror(errno));
1861 }
1862 free(cwd);
1863
1864 // Build the list of absisca values for the points in the accuracy graph
1865 g_assert_cmpuint(graphPointNb, >=, 4);
1866 xValues= malloc(graphPointNb * sizeof(double));
1867 xValues[0]= graphs->bounds[j][i].min;
1868 xValues[graphPointNb - 1]= graphs->bounds[j][i].max;
1869 xValues[1]= MIN(((Point*) g_queue_peek_head(hullArray[i][j]))->x,
1870 ((Point*) g_queue_peek_head(hullArray[j][i]))->x);
1871 xValues[graphPointNb - 2]= MAX(((Point*)
1872 g_queue_peek_tail(hullArray[i][j]))->x, ((Point*)
1873 g_queue_peek_tail(hullArray[j][i]))->x);
1874
1875 if (xValues[0] == xValues[1])
1876 {
1877 xBegin= 0;
1878 }
1879 else
1880 {
1881 xBegin= 1;
1882 }
1883 if (xValues[graphPointNb - 2] == xValues[graphPointNb - 1])
1884 {
1885 xEnd= graphPointNb - 1;
1886 }
1887 else
1888 {
1889 xEnd= graphPointNb - 2;
1890 }
1891 interval= (xValues[xEnd] - xValues[xBegin]) / (graphPointNb - 1);
1892
1893 for (it= xBegin; it <= xEnd; it++)
1894 {
1895 xValues[it]= xValues[xBegin] + interval * (it - xBegin);
1896 }
1897
1898 /* For each absisca value and each optimisation direction, solve the LP
1899 * and write a line in the data file */
1900 for (it= 0; it < graphPointNb; it++)
1901 {
1902 unsigned int it2;
1903 int directions[]= {GLP_MIN, GLP_MAX};
1904
1905 glp_set_obj_coef(lp, 1, 1.);
1906 glp_set_obj_coef(lp, 2, xValues[it]);
1907
1908 fprintf(fp, "%25.9f %25.9f", xValues[it], lpFactors->approx->offset
1909 + lpFactors->approx->drift * xValues[it]);
1910 for (it2= 0; it2 < sizeof(directions) / sizeof(*directions); it2++)
1911 {
1912 int status;
1913
1914 glp_set_obj_dir(lp, directions[it2]);
1915 retval= glp_simplex(lp, NULL);
1916 status= glp_get_status(lp);
1917
1918 g_assert(retval == 0 && status == GLP_OPT);
1919 fprintf(fp, " %25.9f", glp_get_obj_val(lp));
1920 }
1921 fprintf(fp, "\n");
1922 }
1923
1924 free(xValues);
1925 fclose(fp);
1926
1927 fprintf(syncState->graphsStream,
1928 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1929 "using 1:(($3 - $2) / clock_freq_%2$u):(($4 - $2) / clock_freq_%2$u) "
1930 "title \"Synchronization accuracy\" "
1931 "with filledcurves linewidth 2 linetype 1 "
1932 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i,
1933 j);
1934 }
1935 #endif
1936 }
1937
1938
1939 /*
1940 * Write the analysis-specific graph lines in the gnuplot script.
1941 *
1942 * When the solver library, glpk, is not available at build time nothing is
1943 * actually produced.
1944 *
1945 * Args:
1946 * syncState: container for synchronization data
1947 * i: first trace number
1948 * j: second trace number, garanteed to be larger than i
1949 */
1950 static void writeAnalysisTraceTimeForePlotsEval(SyncState* const syncState,
1951 const unsigned int i, const unsigned int j)
1952 {
1953 #ifdef HAVE_LIBGLPK
1954 if (((AnalysisDataEval*)
1955 syncState->analysisData)->graphs->lpFactorsArray[j][i].type ==
1956 MIDDLE)
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) notitle "
1961 "with lines linewidth 2 linetype 1 "
1962 "linecolor rgb \"gray60\", \\\n"
1963 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1964 "using 1:(($4 - $2) / clock_freq_%2$u) notitle "
1965 "with lines linewidth 2 linetype 1 "
1966 "linecolor rgb \"gray60\", \\\n", i, j);
1967 }
1968 #endif
1969 }
1970
1971
1972 /*
1973 * Write the analysis-specific graph lines in the gnuplot script.
1974 *
1975 * Args:
1976 * syncState: container for synchronization data
1977 * i: first trace number
1978 * j: second trace number, garanteed to be larger than i
1979 */
1980 static void writeAnalysisTraceTraceBackPlotsEval(SyncState* const syncState,
1981 const unsigned int i, const unsigned int j)
1982 {
1983 #ifdef HAVE_LIBGLPK
1984 fprintf(syncState->graphsStream,
1985 "\t\"analysis_eval_accuracy-%1$03u_and_%2$03u.data\" "
1986 "using 1:3:4 "
1987 "title \"Synchronization accuracy\" "
1988 "with filledcurves linewidth 2 linetype 1 "
1989 "linecolor rgb \"black\" fill solid 0.25 noborder, \\\n", i, j);
1990 #endif
1991 }
1992
1993
1994 /*
1995 * Write the analysis-specific graph lines in the gnuplot script.
1996 *
1997 * Args:
1998 * syncState: container for synchronization data
1999 * i: first trace number
2000 * j: second trace number, garanteed to be larger than i
2001 */
2002 static void writeAnalysisTraceTraceForePlotsEval(SyncState* const syncState,
2003 const unsigned int i, const unsigned int j)
2004 {
2005 AnalysisDataEval* analysisData= syncState->analysisData;
2006
2007 analysisData->chullSS->analysisModule->graphFunctions.writeTraceTraceForePlots(analysisData->chullSS,
2008 i, j);
2009 }
LTTng 2.x Viewer (LTTV)
This page took 0.06767 seconds and 3 git commands to generate.