projects / lttv.git / blob
? search:


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