projects / lttv.git / blob
? search:


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