projects / lttv.git / blob
? search:


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