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,
28 #include "event_analysis.h"
29 #include "sync_chain.h"
31 #include "event_matching_tcp.h"
35 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
39 // Functions common to all matching modules
40 static void initMatchingTCP(SyncState
* const syncState
);
41 static void destroyMatchingTCP(SyncState
* const syncState
);
43 static void matchEventTCP(SyncState
* const syncState
, Event
* const event
);
44 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
);
45 static void printMatchingStatsTCP(SyncState
* const syncState
);
46 static void writeMatchingGraphsPlotsTCP(FILE* stream
, SyncState
* const
47 syncState
, const unsigned int i
, const unsigned int j
);
48 static void writeMatchingGraphsOptionsTCP(FILE* stream
, SyncState
* const
49 syncState
, const unsigned int i
, const unsigned int j
);
51 // Functions specific to this module
52 static void registerMatchingTCP() __attribute__((constructor (101)));
54 static void matchEvents(SyncState
* const syncState
, Event
* const event
,
55 GHashTable
* const unMatchedList
, GHashTable
* const
56 unMatchedOppositeList
, const size_t fieldOffset
, const size_t
58 static void partialDestroyMatchingTCP(SyncState
* const syncState
);
60 static bool isAck(const Message
* const message
);
61 static bool needsAck(const Message
* const message
);
62 static void buildReversedConnectionKey(ConnectionKey
* const
63 reversedConnectionKey
, const ConnectionKey
* const connectionKey
);
65 static void openGraphDataFiles(SyncState
* const syncState
);
66 static void closeGraphDataFiles(SyncState
* const syncState
);
67 static void writeMessagePoint(FILE* stream
, const Message
* const message
);
70 static MatchingModule matchingModuleTCP
= {
73 .canMatch
[UDP
]= false,
74 .initMatching
= &initMatchingTCP
,
75 .destroyMatching
= &destroyMatchingTCP
,
76 .matchEvent
= &matchEventTCP
,
77 .finalizeMatching
= &finalizeMatchingTCP
,
78 .printMatchingStats
= &printMatchingStatsTCP
,
79 .writeMatchingGraphsPlots
= &writeMatchingGraphsPlotsTCP
,
80 .writeMatchingGraphsOptions
= &writeMatchingGraphsOptionsTCP
,
85 * Matching module registering function
87 static void registerMatchingTCP()
89 g_queue_push_tail(&matchingModules
, &matchingModuleTCP
);
94 * Matching init function
96 * This function is called at the beginning of a synchronization run for a set
99 * Allocate the matching specific data structures
102 * syncState container for synchronization data.
103 * This function allocates these matchingData members:
109 static void initMatchingTCP(SyncState
* const syncState
)
111 MatchingDataTCP
* matchingData
;
113 matchingData
= malloc(sizeof(MatchingDataTCP
));
114 syncState
->matchingData
= matchingData
;
116 matchingData
->unMatchedInE
= g_hash_table_new_full(&ghfSegmentKeyHash
,
117 &gefSegmentKeyEqual
, NULL
, &gdnDestroyEvent
);
118 matchingData
->unMatchedOutE
= g_hash_table_new_full(&ghfSegmentKeyHash
,
119 &gefSegmentKeyEqual
, NULL
, &gdnDestroyEvent
);
120 matchingData
->unAcked
= g_hash_table_new_full(&ghfConnectionKeyHash
,
121 &gefConnectionKeyEqual
, &gdnConnectionKeyDestroy
,
122 &gdnTCPSegmentListDestroy
);
124 if (syncState
->stats
)
128 matchingData
->stats
= calloc(1, sizeof(MatchingStatsTCP
));
129 matchingData
->stats
->totMessageArray
= malloc(syncState
->traceNb
*
130 sizeof(unsigned int*));
131 for (i
= 0; i
< syncState
->traceNb
; i
++)
133 matchingData
->stats
->totMessageArray
[i
]=
134 calloc(syncState
->traceNb
, sizeof(unsigned int));
139 matchingData
->stats
= NULL
;
142 if (syncState
->graphs
)
144 openGraphDataFiles(syncState
);
148 matchingData
->messagePoints
= NULL
;
154 * Matching destroy function
156 * Free the matching specific data structures
159 * syncState container for synchronization data.
160 * This function deallocates these matchingData members:
163 static void destroyMatchingTCP(SyncState
* const syncState
)
165 MatchingDataTCP
* matchingData
;
167 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
169 if (matchingData
== NULL
)
174 partialDestroyMatchingTCP(syncState
);
176 if (syncState
->stats
)
180 for (i
= 0; i
< syncState
->traceNb
; i
++)
182 free(matchingData
->stats
->totMessageArray
[i
]);
184 free(matchingData
->stats
->totMessageArray
);
185 free(matchingData
->stats
);
188 free(syncState
->matchingData
);
189 syncState
->matchingData
= NULL
;
194 * Free some of the matching specific data structures
196 * This function can be called right after the events have been processed to
197 * free some data structures that are not needed for finalization.
200 * syncState container for synchronization data.
201 * This function deallocates these matchingData members:
206 static void partialDestroyMatchingTCP(SyncState
* const syncState
)
208 MatchingDataTCP
* matchingData
;
210 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
212 if (matchingData
== NULL
|| matchingData
->unMatchedInE
== NULL
)
217 g_hash_table_destroy(matchingData
->unMatchedInE
);
218 matchingData
->unMatchedInE
= NULL
;
219 g_hash_table_destroy(matchingData
->unMatchedOutE
);
220 g_hash_table_destroy(matchingData
->unAcked
);
222 if (syncState
->graphs
&& matchingData
->messagePoints
)
224 closeGraphDataFiles(syncState
);
230 * Try to match one event from a trace with the corresponding event from
234 * syncState container for synchronization data.
235 * event new event to match
237 static void matchEventTCP(SyncState
* const syncState
, Event
* const event
)
239 MatchingDataTCP
* matchingData
;
241 g_assert(event
->type
== TCP
);
243 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
245 if (event
->event
.tcpEvent
->direction
== IN
)
247 matchEvents(syncState
, event
, matchingData
->unMatchedInE
,
248 matchingData
->unMatchedOutE
, offsetof(Message
, inE
),
249 offsetof(Message
, outE
));
253 matchEvents(syncState
, event
, matchingData
->unMatchedOutE
,
254 matchingData
->unMatchedInE
, offsetof(Message
, outE
),
255 offsetof(Message
, inE
));
261 * Call the partial matching destroyer and Obtain the factors from downstream
264 * syncState container for synchronization data.
267 * Factors[traceNb] synchronization factors for each trace
269 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
)
271 partialDestroyMatchingTCP(syncState
);
273 return syncState
->analysisModule
->finalizeAnalysis(syncState
);
278 * Print statistics related to matching and downstream modules. Must be
279 * called after finalizeMatching.
282 * syncState container for synchronization data.
284 static void printMatchingStatsTCP(SyncState
* const syncState
)
287 MatchingDataTCP
* matchingData
;
289 if (!syncState
->stats
)
294 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
296 printf("TCP matching stats:\n");
297 printf("\ttotal input and output events matched together to form a packet: %u\n",
298 matchingData
->stats
->totPacket
);
300 printf("\tMessage traffic:\n");
302 for (i
= 0; i
< syncState
->traceNb
; i
++)
304 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
306 printf("\t\t%3d - %-3d: sent %-10u received %-10u\n", i
, j
,
307 matchingData
->stats
->totMessageArray
[j
][i
],
308 matchingData
->stats
->totMessageArray
[i
][j
]);
312 if (syncState
->analysisModule
->analyzeExchange
!= NULL
)
314 printf("\ttotal packets identified needing an acknowledge: %u\n",
315 matchingData
->stats
->totPacketNeedAck
);
316 printf("\ttotal exchanges (four events matched together): %u\n",
317 matchingData
->stats
->totExchangeEffective
);
318 printf("\ttotal synchronization exchanges: %u\n",
319 matchingData
->stats
->totExchangeSync
);
322 if (syncState
->analysisModule
->printAnalysisStats
!= NULL
)
324 syncState
->analysisModule
->printAnalysisStats(syncState
);
330 * Implementation of a packet matching algorithm for TCP
333 * event: new event to match
334 * unMatchedList: list of unmatched events of the same type (send or
336 * unMatchedOppositeList: list of unmatched events of the opposite type of
338 * fieldOffset: offset of the Event field in the Message struct for the
339 * field of the type of event
340 * oppositeFieldOffset: offset of the Event field in the Message struct
341 * for the field of the opposite type of event
343 static void matchEvents(SyncState
* const syncState
, Event
* const event
,
344 GHashTable
* const unMatchedList
, GHashTable
* const unMatchedOppositeList
,
345 const size_t fieldOffset
, const size_t oppositeFieldOffset
)
347 Event
* companionEvent
;
349 MatchingDataTCP
* matchingData
;
352 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
354 companionEvent
= g_hash_table_lookup(unMatchedOppositeList
, event
->event
.tcpEvent
->segmentKey
);
355 if (companionEvent
!= NULL
)
357 g_debug("Found matching companion event, ");
359 // If it's there, remove it and create a Message
360 g_hash_table_steal(unMatchedOppositeList
, event
->event
.tcpEvent
->segmentKey
);
361 packet
= malloc(sizeof(Message
));
362 *((Event
**) ((void*) packet
+ fieldOffset
))= event
;
363 *((Event
**) ((void*) packet
+ oppositeFieldOffset
))= companionEvent
;
364 packet
->print
= &printTCPSegment
;
365 // Both events can now share the same segmentKey
366 free(packet
->outE
->event
.tcpEvent
->segmentKey
);
367 packet
->outE
->event
.tcpEvent
->segmentKey
= packet
->inE
->event
.tcpEvent
->segmentKey
;
369 if (syncState
->stats
)
371 matchingData
->stats
->totPacket
++;
372 matchingData
->stats
->totMessageArray
[packet
->inE
->traceNum
][packet
->outE
->traceNum
]++;
375 // Discard loopback traffic
376 if (packet
->inE
->traceNum
== packet
->outE
->traceNum
)
378 destroyTCPSegment(packet
);
382 if (syncState
->graphs
)
384 writeMessagePoint(matchingData
->messagePoints
[packet
->inE
->traceNum
][packet
->outE
->traceNum
],
388 if (syncState
->analysisModule
->analyzeMessage
!= NULL
)
390 syncState
->analysisModule
->analyzeMessage(syncState
, packet
);
393 // We can skip the rest of the algorithm if the analysis module is not
394 // interested in exchanges
395 if (syncState
->analysisModule
->analyzeExchange
== NULL
)
397 destroyTCPSegment(packet
);
401 // If this packet acknowleges some data ...
404 ConnectionKey oppositeConnectionKey
;
406 buildReversedConnectionKey(&oppositeConnectionKey
,
407 &event
->event
.tcpEvent
->segmentKey
->connectionKey
);
408 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
409 &oppositeConnectionKey
);
410 if (conUnAcked
!= NULL
)
412 Message
* ackedPacket
;
418 result
= g_queue_find_custom(conUnAcked
, packet
, &gcfTCPSegmentAckCompare
);
420 while (result
!= NULL
)
422 // Remove the acknowledged packet from the unAcked list
423 // and keep it for later offset calculations
424 g_debug("Found matching unAcked packet, ");
426 ackedPacket
= (Message
*) result
->data
;
427 g_queue_delete_link(conUnAcked
, result
);
429 if (syncState
->stats
)
431 matchingData
->stats
->totExchangeEffective
++;
434 if (exchange
== NULL
)
436 exchange
= malloc(sizeof(Exchange
));
437 exchange
->message
= packet
;
438 exchange
->acks
= g_queue_new();
441 g_queue_push_tail(exchange
->acks
, ackedPacket
);
443 result
= g_queue_find_custom(conUnAcked
, packet
,
444 &gcfTCPSegmentAckCompare
);
447 // It might be possible to do an offset calculation
448 if (exchange
!= NULL
)
450 ackedPacket
= g_queue_peek_tail(exchange
->acks
);
451 if (ackedPacket
->outE
->traceNum
!= packet
->inE
->traceNum
452 || ackedPacket
->inE
->traceNum
!=
453 packet
->outE
->traceNum
|| packet
->inE
->traceNum
==
454 packet
->outE
->traceNum
)
456 ackedPacket
->print(ackedPacket
);
457 packet
->print(packet
);
458 g_error("Disorganized exchange encountered during "
463 if (syncState
->stats
)
465 matchingData
->stats
->totExchangeSync
++;
468 syncState
->analysisModule
->analyzeExchange(syncState
,
472 exchange
->message
= NULL
;
473 destroyTCPExchange(exchange
);
478 if (needsAck(packet
))
480 if (syncState
->stats
)
482 matchingData
->stats
->totPacketNeedAck
++;
485 // If this packet will generate an ack, add it to the unAcked list
486 g_debug("Adding to unAcked, ");
487 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
488 &event
->event
.tcpEvent
->segmentKey
->connectionKey
);
489 if (conUnAcked
== NULL
)
491 ConnectionKey
* connectionKey
;
493 connectionKey
= malloc(sizeof(ConnectionKey
));
494 memcpy(connectionKey
, &event
->event
.tcpEvent
->segmentKey
->connectionKey
,
495 sizeof(ConnectionKey
));
496 g_hash_table_insert(matchingData
->unAcked
, connectionKey
,
497 conUnAcked
= g_queue_new());
499 g_queue_push_tail(conUnAcked
, packet
);
503 destroyTCPSegment(packet
);
508 // If there's no corresponding event, add the event to the unmatched
509 // list for this type of event
510 g_debug("Adding to unmatched event list, ");
511 g_hash_table_replace(unMatchedList
, event
->event
.tcpEvent
->segmentKey
, event
);
517 * Check if a packet is an acknowledge
526 static bool isAck(const Message
* const packet
)
528 if (packet
->inE
->event
.tcpEvent
->segmentKey
->ack
== 1)
540 * Check if a packet will increment the sequence number, thus needing an
547 * true if the packet will need an acknowledge
550 static bool needsAck(const Message
* const packet
)
552 if (packet
->inE
->event
.tcpEvent
->segmentKey
->syn
|| packet
->inE
->event
.tcpEvent
->segmentKey
->fin
||
553 packet
->inE
->event
.tcpEvent
->segmentKey
->tot_len
- packet
->inE
->event
.tcpEvent
->segmentKey
->ihl
* 4 -
554 packet
->inE
->event
.tcpEvent
->segmentKey
->doff
* 4 > 0)
566 * Populate a connection key structure for the opposite direction of a
570 * reversedConnectionKey the result, must be pre-allocated
571 * connectionKey the connection key to reverse
573 static void buildReversedConnectionKey(ConnectionKey
* const
574 reversedConnectionKey
, const ConnectionKey
* const connectionKey
)
576 reversedConnectionKey
->saddr
= connectionKey
->daddr
;
577 reversedConnectionKey
->daddr
= connectionKey
->saddr
;
578 reversedConnectionKey
->source
= connectionKey
->dest
;
579 reversedConnectionKey
->dest
= connectionKey
->source
;
584 * Create and open files used to store message points to genereate
585 * graphs. Allocate and populate array to store file pointers.
588 * syncState: container for synchronization data
590 static void openGraphDataFiles(SyncState
* const syncState
)
596 MatchingDataTCP
* matchingData
;
598 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
600 cwd
= changeToGraphDir(syncState
->graphs
);
602 matchingData
->messagePoints
= malloc(syncState
->traceNb
* sizeof(FILE**));
603 for (i
= 0; i
< syncState
->traceNb
; i
++)
605 matchingData
->messagePoints
[i
]= malloc(syncState
->traceNb
*
607 for (j
= 0; j
< syncState
->traceNb
; j
++)
611 retval
= snprintf(name
, sizeof(name
),
612 "matching_tcp-%03u_to_%03u.data", j
, i
);
613 if (retval
> sizeof(name
) - 1)
615 name
[sizeof(name
) - 1]= '\0';
617 if ((matchingData
->messagePoints
[i
][j
]= fopen(name
, "w")) ==
620 g_error(strerror(errno
));
629 g_error(strerror(errno
));
636 * Write a message point to a file used to generate graphs
639 * stream: FILE*, file pointer where to write the point
640 * message: message for which to write the point
642 static void writeMessagePoint(FILE* stream
, const Message
* const message
)
646 if (message
->inE
->traceNum
< message
->outE
->traceNum
)
648 // CA is inE->traceNum
649 x
= message
->inE
->time
;
650 y
= message
->outE
->time
;
654 // CA is outE->traceNum
655 x
= message
->outE
->time
;
656 y
= message
->inE
->time
;
659 fprintf(stream
, "%20llu %20llu\n", x
, y
);
664 * Close files used to store convex hull points to genereate graphs.
665 * Deallocate array to store file pointers.
668 * syncState: container for synchronization data
670 static void closeGraphDataFiles(SyncState
* const syncState
)
673 MatchingDataTCP
* matchingData
;
676 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
678 if (matchingData
->messagePoints
== NULL
)
683 for (i
= 0; i
< syncState
->traceNb
; i
++)
685 for (j
= 0; j
< syncState
->traceNb
; j
++)
689 retval
= fclose(matchingData
->messagePoints
[i
][j
]);
692 g_error(strerror(errno
));
696 free(matchingData
->messagePoints
[i
]);
698 free(matchingData
->messagePoints
);
700 matchingData
->messagePoints
= NULL
;
705 * Write the matching-specific graph lines in the gnuplot script. Call the
706 * downstream module's graph function.
709 * stream: stream where to write the data
710 * syncState: container for synchronization data
711 * i: first trace number
712 * j: second trace number, garanteed to be larger than i
714 static void writeMatchingGraphsPlotsTCP(FILE* stream
, SyncState
* const
715 syncState
, const unsigned int i
, const unsigned int j
)
718 "\t\"matching_tcp-%1$03d_to_%2$03d.data\" "
719 "title \"Sent messages\" with points linetype 4 "
720 "linecolor rgb \"#98fc66\" pointtype 9 pointsize 2, \\\n"
721 "\t\"matching_tcp-%2$03d_to_%1$03d.data\" "
722 "title \"Received messages\" with points linetype 4 "
723 "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i
, j
);
725 if (syncState
->analysisModule
->writeAnalysisGraphsPlots
!= NULL
)
727 syncState
->analysisModule
->writeAnalysisGraphsPlots(stream
, syncState
,
734 * Write the matching-specific options in the gnuplot script (none). Call the
735 * downstream module's options function.
738 * stream: stream where to write the data
739 * syncState: container for synchronization data
740 * i: first trace number
741 * j: second trace number, garanteed to be larger than i
743 static void writeMatchingGraphsOptionsTCP(FILE* stream
, SyncState
* const
744 syncState
, const unsigned int i
, const unsigned int j
)
746 if (syncState
->analysisModule
->writeAnalysisGraphsOptions
!= NULL
)
748 syncState
->analysisModule
->writeAnalysisGraphsOptions(stream
,