projects / lttv.git / blob
? search:


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