1 /* This file is part of the Linux Trace Toolkit viewer
2 * Copyright (C) 2009 Benjamin Poirier <benjamin.poirier@polymtl.ca>
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;
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.
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,
20 #define _ISOC99_SOURCE
26 #include <arpa/inet.h>
29 #include <netinet/in.h>
34 #include <sys/socket.h>
37 #include "sync_chain.h"
39 #include "event_analysis_eval.h"
42 // Functions common to all analysis modules
43 static void initAnalysisEval(SyncState
* const syncState
);
44 static void destroyAnalysisEval(SyncState
* const syncState
);
46 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const
48 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const
50 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const
52 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
);
53 static void printAnalysisStatsEval(SyncState
* const syncState
);
55 // Functions specific to this module
56 static void registerAnalysisEval() __attribute__((constructor (102)));
57 static guint
ghfRttKeyHash(gconstpointer key
);
58 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
);
59 static void gdnDestroyRttKey(gpointer data
);
60 static void gdnDestroyDouble(gpointer data
);
61 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttFile
);
62 static void positionStream(FILE* stream
);
64 static void gfSum(gpointer data
, gpointer userData
);
65 static void gfSumSquares(gpointer data
, gpointer userData
);
66 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer user_data
);
69 static AnalysisModule analysisModuleEval
= {
71 .initAnalysis
= &initAnalysisEval
,
72 .destroyAnalysis
= &destroyAnalysisEval
,
73 .analyzeMessage
= &analyzeMessageEval
,
74 .analyzeExchange
= &analyzeExchangeEval
,
75 .analyzeBroadcast
= &analyzeBroadcastEval
,
76 .finalizeAnalysis
= &finalizeAnalysisEval
,
77 .printAnalysisStats
= &printAnalysisStatsEval
,
78 .writeAnalysisGraphsPlots
= NULL
,
79 .writeAnalysisGraphsOptions
= NULL
,
82 static ModuleOption optionEvalRttFile
= {
83 .longName
= "eval-rtt-file",
84 .hasArg
= REQUIRED_ARG
,
86 .optionHelp
= "specify the file containing rtt information",
92 * Analysis module registering function
94 static void registerAnalysisEval()
96 g_queue_push_tail(&analysisModules
, &analysisModuleEval
);
97 g_queue_push_tail(&moduleOptions
, &optionEvalRttFile
);
102 * Analysis init function
104 * This function is called at the beginning of a synchronization run for a set
108 * syncState container for synchronization data.
110 static void initAnalysisEval(SyncState
* const syncState
)
112 AnalysisDataEval
* analysisData
;
115 analysisData
= malloc(sizeof(AnalysisDataEval
));
116 syncState
->analysisData
= analysisData
;
118 analysisData
->rttInfo
= g_hash_table_new_full(&ghfRttKeyHash
,
119 &gefRttKeyEqual
, &gdnDestroyRttKey
, &gdnDestroyDouble
);
120 if (optionEvalRttFile
.arg
)
125 rttStream
= fopen(optionEvalRttFile
.arg
, "r");
126 if (rttStream
== NULL
)
128 g_error(strerror(errno
));
131 readRttInfo(analysisData
->rttInfo
, rttStream
);
133 retval
= fclose(rttStream
);
136 g_error(strerror(errno
));
140 if (syncState
->stats
)
142 analysisData
->stats
= calloc(1, sizeof(AnalysisStatsEval
));
143 analysisData
->stats
->broadcastDiffSum
= 0.;
145 analysisData
->stats
->messageStats
= malloc(syncState
->traceNb
*
146 sizeof(MessageStats
*));
147 for (i
= 0; i
< syncState
->traceNb
; i
++)
149 analysisData
->stats
->messageStats
[i
]= calloc(syncState
->traceNb
,
150 sizeof(MessageStats
));
153 analysisData
->stats
->exchangeRtt
=
154 g_hash_table_new_full(&ghfRttKeyHash
, &gefRttKeyEqual
,
155 &gdnDestroyRttKey
, &gdnDestroyDouble
);
161 * Analysis destroy function
163 * Free the analysis specific data structures
166 * syncState container for synchronization data.
168 static void destroyAnalysisEval(SyncState
* const syncState
)
171 AnalysisDataEval
* analysisData
;
173 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
175 if (analysisData
== NULL
|| analysisData
->rttInfo
== NULL
)
180 g_hash_table_destroy(analysisData
->rttInfo
);
181 analysisData
->rttInfo
= NULL
;
183 if (syncState
->stats
)
185 for (i
= 0; i
< syncState
->traceNb
; i
++)
187 free(analysisData
->stats
->messageStats
[i
]);
189 free(analysisData
->stats
->messageStats
);
191 g_hash_table_destroy(analysisData
->stats
->exchangeRtt
);
193 free(analysisData
->stats
);
196 free(syncState
->analysisData
);
197 syncState
->analysisData
= NULL
;
202 * Perform analysis on an event pair.
204 * Check if there is message inversion or messages that are too fast.
207 * syncState container for synchronization data
208 * message structure containing the events
210 static void analyzeMessageEval(SyncState
* const syncState
, Message
* const message
)
212 AnalysisDataEval
* analysisData
;
213 MessageStats
* messageStats
;
216 struct RttKey rttKey
;
218 if (!syncState
->stats
)
223 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
225 &analysisData
->stats
->messageStats
[message
->outE
->traceNum
][message
->inE
->traceNum
];
227 messageStats
->total
++;
229 tt
= wallTimeSub(&message
->inE
->wallTime
, &message
->outE
->wallTime
);
232 messageStats
->inversionNb
++;
235 g_assert(message
->inE
->type
== TCP
);
237 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
;
239 message
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
;
240 rtt
= g_hash_table_lookup(analysisData
->rttInfo
, &rttKey
);
241 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey
.saddr
,
242 rttKey
.daddr
, rtt
? *rtt
: NAN
);
246 g_debug("rttInfo, tt: %f rtt / 2: %f", tt
, *rtt
/ 2.);
249 messageStats
->tooFastNb
++;
254 messageStats
->noRTTInfoNb
++;
260 * Perform analysis on multiple messages
265 * syncState container for synchronization data
266 * exchange structure containing the messages
268 static void analyzeExchangeEval(SyncState
* const syncState
, Exchange
* const exchange
)
270 AnalysisDataEval
* analysisData
= syncState
->analysisData
;
271 Message
* m1
= g_queue_peek_tail(exchange
->acks
);
272 Message
* m2
= exchange
->message
;
273 struct RttKey
* rttKey
;
274 double* rtt
, * exchangeRtt
;
276 if (!syncState
->stats
)
281 // (T2 - T1) - (T3 - T4)
282 rtt
= malloc(sizeof(double));
283 *rtt
= wallTimeSub(&m1
->inE
->wallTime
, &m1
->outE
->wallTime
) -
284 wallTimeSub(&m2
->outE
->wallTime
, &m2
->inE
->wallTime
);
286 g_assert(m1
->inE
->type
== TCP
);
287 rttKey
= malloc(sizeof(struct RttKey
));
289 MIN(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
290 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
292 MAX(m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.saddr
,
293 m1
->inE
->event
.tcpEvent
->segmentKey
->connectionKey
.daddr
);
294 exchangeRtt
= g_hash_table_lookup(analysisData
->stats
->exchangeRtt
,
299 if (*rtt
< *exchangeRtt
)
301 g_hash_table_replace(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
306 g_hash_table_insert(analysisData
->stats
->exchangeRtt
, rttKey
, rtt
);
312 * Perform analysis on muliple events
314 * Sum the broadcast differential delays
317 * syncState container for synchronization data
318 * broadcast structure containing the events
320 static void analyzeBroadcastEval(SyncState
* const syncState
, Broadcast
* const broadcast
)
322 AnalysisDataEval
* analysisData
;
323 double sum
= 0, squaresSum
= 0;
326 if (!syncState
->stats
)
331 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
333 g_queue_foreach(broadcast
->events
, &gfSum
, &sum
);
334 g_queue_foreach(broadcast
->events
, &gfSumSquares
, &squaresSum
);
336 analysisData
->stats
->broadcastNb
++;
337 // Because of numerical errors, this can at times be < 0
338 y
= squaresSum
/ g_queue_get_length(broadcast
->events
) - pow(sum
/
339 g_queue_get_length(broadcast
->events
), 2.);
342 analysisData
->stats
->broadcastDiffSum
+= sqrt(y
);
348 * Finalize the factor calculations
350 * Since this module does not really calculate factors, identity factors are
354 * syncState container for synchronization data.
357 * Factors[traceNb] identity factors for each trace
359 static GArray
* finalizeAnalysisEval(SyncState
* const syncState
)
364 factors
= g_array_sized_new(FALSE
, FALSE
, sizeof(Factors
),
366 g_array_set_size(factors
, syncState
->traceNb
);
367 for (i
= 0; i
< syncState
->traceNb
; i
++)
371 e
= &g_array_index(factors
, Factors
, i
);
381 * Print statistics related to analysis. Must be called after
385 * syncState container for synchronization data.
387 static void printAnalysisStatsEval(SyncState
* const syncState
)
389 AnalysisDataEval
* analysisData
;
392 if (!syncState
->stats
)
397 analysisData
= (AnalysisDataEval
*) syncState
->analysisData
;
399 printf("Synchronization evaluation analysis stats:\n");
400 printf("\tsum of broadcast differential delays: %g\n",
401 analysisData
->stats
->broadcastDiffSum
);
402 printf("\taverage broadcast differential delays: %g\n",
403 analysisData
->stats
->broadcastDiffSum
/
404 analysisData
->stats
->broadcastNb
);
406 printf("\tIndividual evaluation:\n"
407 "\t\tTrace pair Inversions Too fast (No RTT info) Total\n");
409 for (i
= 0; i
< syncState
->traceNb
; i
++)
411 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
413 MessageStats
* messageStats
;
414 const char* format
= "\t\t%3d - %-3d %-10u %-10u %-10u %u\n";
416 messageStats
= &analysisData
->stats
->messageStats
[i
][j
];
418 printf(format
, i
, j
, messageStats
->inversionNb
, messageStats
->tooFastNb
,
419 messageStats
->noRTTInfoNb
, messageStats
->total
);
421 messageStats
= &analysisData
->stats
->messageStats
[j
][i
];
423 printf(format
, j
, i
, messageStats
->inversionNb
, messageStats
->tooFastNb
,
424 messageStats
->noRTTInfoNb
, messageStats
->total
);
428 printf("\tRound-trip times:\n"
429 "\t\tHost pair RTT from exchanges RTTs from file (ms)\n");
430 g_hash_table_foreach(analysisData
->stats
->exchangeRtt
,
431 &ghfPrintExchangeRtt
, analysisData
->rttInfo
);
436 * A GHFunc for g_hash_table_foreach()
439 * key: RttKey* where saddr < daddr
440 * value: double*, RTT estimated from exchanges
441 * user_data GHashTable* rttInfo
443 static void ghfPrintExchangeRtt(gpointer key
, gpointer value
, gpointer user_data
)
445 char addr1
[16], addr2
[16];
446 struct RttKey
* rttKey1
= key
;
447 struct RttKey rttKey2
= {rttKey1
->daddr
, rttKey1
->saddr
};
448 double* fileRtt1
, *fileRtt2
;
449 GHashTable
* rttInfo
= user_data
;
451 convertIP(addr1
, rttKey1
->saddr
);
452 convertIP(addr2
, rttKey1
->daddr
);
454 fileRtt1
= g_hash_table_lookup(rttInfo
, rttKey1
);
455 fileRtt2
= g_hash_table_lookup(rttInfo
, &rttKey2
);
457 printf("\t\t(%15s, %-15s) %-18.3f ", addr1
, addr2
, *(double*) value
* 1e3
);
459 if (fileRtt1
|| fileRtt2
)
463 printf("%.3f", *fileRtt1
* 1e3
);
465 if (fileRtt1
&& fileRtt2
)
471 printf("%.3f", *fileRtt2
* 1e3
);
483 * A GHashFunc for g_hash_table_new()
488 static guint
ghfRttKeyHash(gconstpointer key
)
490 struct RttKey
* rttKey
;
493 rttKey
= (struct RttKey
*) key
;
505 * A GDestroyNotify function for g_hash_table_new_full()
508 * data: struct RttKey*
510 static void gdnDestroyRttKey(gpointer data
)
517 * A GDestroyNotify function for g_hash_table_new_full()
522 static void gdnDestroyDouble(gpointer data
)
529 * A GEqualFunc for g_hash_table_new()
535 * TRUE if both values are equal
537 static gboolean
gefRttKeyEqual(gconstpointer a
, gconstpointer b
)
539 const struct RttKey
* rkA
, * rkB
;
541 rkA
= (struct RttKey
*) a
;
542 rkB
= (struct RttKey
*) b
;
544 if (rkA
->saddr
== rkB
->saddr
&& rkA
->daddr
== rkB
->daddr
)
556 * Read a file contain minimum round trip time values and fill an array with
557 * them. The file is formatted as such:
558 * <host1 IP> <host2 IP> <RTT in milliseconds>
559 * ip's should be in dotted quad format
562 * rttInfo: double* rttInfo[RttKey], empty table, will be filled
563 * rttStream: stream from which to read
565 static void readRttInfo(GHashTable
* rttInfo
, FILE* rttStream
)
571 positionStream(rttStream
);
572 retval
= getline(&line
, &len
, rttStream
);
573 while(!feof(rttStream
))
575 struct RttKey
* rttKey
;
576 char saddrDQ
[20], daddrDQ
[20];
585 {saddrDQ
, offsetof(struct RttKey
, saddr
)},
586 {daddrDQ
, offsetof(struct RttKey
, daddr
)}
589 if (retval
== -1 && !feof(rttStream
))
591 g_error(strerror(errno
));
594 if (line
[retval
- 1] == '\n')
596 line
[retval
- 1]= '\0';
599 rtt
= malloc(sizeof(double));
600 retval
= sscanf(line
, " %19s %19s %lf %c", saddrDQ
, daddrDQ
, rtt
,
604 g_error(strerror(errno
));
606 else if (retval
!= 3)
608 g_error("Error parsing RTT file, line was '%s'", line
);
611 rttKey
= malloc(sizeof(struct RttKey
));
612 for (i
= 0; i
< sizeof(loopValues
) / sizeof(*loopValues
); i
++)
614 retval
= inet_aton(loopValues
[i
].dq
, &addr
);
617 g_error("Error converting address '%s'", loopValues
[i
].dq
);
619 *(uint32_t*) ((void*) rttKey
+ loopValues
[i
].offset
)=
624 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey
->saddr
,
625 rttKey
->daddr
, *rtt
);
626 g_hash_table_insert(rttInfo
, rttKey
, rtt
);
628 positionStream(rttStream
);
629 retval
= getline(&line
, &len
, rttStream
);
640 * Advance stream over empty space, empty lines and lines that begin with '#'
643 * stream: stream, at exit, will be over the first non-empty character
644 * of a line of be at EOF
646 static void positionStream(FILE* stream
)
655 firstChar
= fgetc(stream
);
656 if (firstChar
== (int) '#')
658 retval
= getline(&line
, &len
, stream
);
667 g_error(strerror(errno
));
671 else if (firstChar
== (int) '\n' || firstChar
== (int) ' ' ||
672 firstChar
== (int) '\t')
674 else if (firstChar
== EOF
)
683 retval
= ungetc(firstChar
, stream
);
686 g_error("Error: ungetc()");
698 * A GFunc for g_queue_foreach()
701 * data Event*, a UDP broadcast event
702 * user_data double*, the running sum
705 * Adds the time of the event to the sum
707 static void gfSum(gpointer data
, gpointer userData
)
709 Event
* event
= (Event
*) data
;
711 *(double*) userData
+= event
->wallTime
.seconds
+ event
->wallTime
.nanosec
/
717 * A GFunc for g_queue_foreach()
720 * data Event*, a UDP broadcast event
721 * user_data double*, the running sum
724 * Adds the square of the time of the event to the sum
726 static void gfSumSquares(gpointer data
, gpointer userData
)
728 Event
* event
= (Event
*) data
;
730 *(double*) userData
+= pow(event
->wallTime
.seconds
+ event
->wallTime
.nanosec