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,
26 #include "event_analysis.h"
27 #include "sync_chain.h"
29 #include "event_matching_tcp.h"
33 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
37 // Functions common to all matching modules
38 static void initMatchingTCP(SyncState
* const syncState
);
39 static void destroyMatchingTCP(SyncState
* const syncState
);
41 static void matchEventTCP(SyncState
* const syncState
, NetEvent
* const event
,
43 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
);
44 static void printMatchingStatsTCP(SyncState
* const syncState
);
46 // Functions specific to this module
47 static void registerMatchingTCP() __attribute__((constructor (101)));
49 static void matchEvents(SyncState
* const syncState
, NetEvent
* const event
,
50 GHashTable
* const unMatchedList
, GHashTable
* const
51 unMatchedOppositeList
, const size_t fieldOffset
, const size_t
53 static void partialDestroyMatchingTCP(SyncState
* const syncState
);
55 static bool isAck(const Packet
* const packet
);
56 static bool needsAck(const Packet
* const packet
);
57 static void buildReversedConnectionKey(ConnectionKey
* const
58 reversedConnectionKey
, const ConnectionKey
* const connectionKey
);
61 static MatchingModule matchingModuleTCP
= {
63 .initMatching
= &initMatchingTCP
,
64 .destroyMatching
= &destroyMatchingTCP
,
65 .matchEvent
= &matchEventTCP
,
66 .finalizeMatching
= &finalizeMatchingTCP
,
67 .printMatchingStats
= &printMatchingStatsTCP
,
72 * Matching module registering function
74 static void registerMatchingTCP()
76 g_queue_push_tail(&matchingModules
, &matchingModuleTCP
);
81 * Matching init function
83 * This function is called at the beginning of a synchronization run for a set
86 * Allocate the matching specific data structures
89 * syncState container for synchronization data.
90 * This function allocates these matchingData members:
96 static void initMatchingTCP(SyncState
* const syncState
)
98 MatchingDataTCP
* matchingData
;
100 matchingData
= malloc(sizeof(MatchingDataTCP
));
101 syncState
->matchingData
= matchingData
;
103 matchingData
->unMatchedInE
= g_hash_table_new_full(&ghfPacketKeyHash
,
104 &gefPacketKeyEqual
, NULL
, &gdnDestroyNetEvent
);
105 matchingData
->unMatchedOutE
= g_hash_table_new_full(&ghfPacketKeyHash
,
106 &gefPacketKeyEqual
, NULL
, &gdnDestroyNetEvent
);
107 matchingData
->unAcked
= g_hash_table_new_full(&ghfConnectionKeyHash
,
108 &gefConnectionKeyEqual
, &gdnConnectionKeyDestroy
,
109 &gdnPacketListDestroy
);
111 if (syncState
->stats
)
113 matchingData
->stats
= calloc(1, sizeof(MatchingStatsTCP
));
117 matchingData
->stats
= NULL
;
123 * Matching destroy function
125 * Free the matching specific data structures
128 * syncState container for synchronization data.
129 * This function deallocates these matchingData members:
132 static void destroyMatchingTCP(SyncState
* const syncState
)
134 MatchingDataTCP
* matchingData
;
136 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
138 if (matchingData
== NULL
)
143 partialDestroyMatchingTCP(syncState
);
145 if (syncState
->stats
)
147 free(matchingData
->stats
);
150 free(syncState
->matchingData
);
151 syncState
->matchingData
= NULL
;
156 * Free some of the matching specific data structures
158 * This function can be called right after the events have been processed to
159 * free some data structures that are not needed for finalization.
162 * syncState container for synchronization data.
163 * This function deallocates these matchingData members:
168 static void partialDestroyMatchingTCP(SyncState
* const syncState
)
170 MatchingDataTCP
* matchingData
;
172 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
174 if (matchingData
== NULL
|| matchingData
->unMatchedInE
== NULL
)
179 g_debug("Cleaning up unMatchedInE list\n");
180 g_hash_table_destroy(matchingData
->unMatchedInE
);
181 matchingData
->unMatchedInE
= NULL
;
182 g_debug("Cleaning up unMatchedOutE list\n");
183 g_hash_table_destroy(matchingData
->unMatchedOutE
);
184 g_debug("Cleaning up unAcked list\n");
185 g_hash_table_destroy(matchingData
->unAcked
);
190 * Try to match one event from a trace with the corresponding event from
194 * syncState container for synchronization data.
195 * event new event to match
196 * eventType type of event to match
198 static void matchEventTCP(SyncState
* const syncState
, NetEvent
* const event
, EventType eventType
)
200 MatchingDataTCP
* matchingData
;
202 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
206 matchEvents(syncState
, event
, matchingData
->unMatchedInE
,
207 matchingData
->unMatchedOutE
, offsetof(Packet
, inE
),
208 offsetof(Packet
, outE
));
212 matchEvents(syncState
, event
, matchingData
->unMatchedOutE
,
213 matchingData
->unMatchedInE
, offsetof(Packet
, outE
),
214 offsetof(Packet
, inE
));
220 * Call the partial matching destroyer and Obtain the factors from downstream
223 * syncState container for synchronization data.
226 * Factors[traceNb] synchronization factors for each trace
228 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
)
230 partialDestroyMatchingTCP(syncState
);
232 return syncState
->analysisModule
->finalizeAnalysis(syncState
);
237 * Print statistics related to matching and downstream modules. Must be
238 * called after finalizeMatching.
241 * syncState container for synchronization data.
243 static void printMatchingStatsTCP(SyncState
* const syncState
)
245 MatchingDataTCP
* matchingData
;
247 if (!syncState
->stats
)
252 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
254 printf("TCP matching stats:\n");
255 printf("\ttotal input and output events matched together to form a packet: %d\n",
256 matchingData
->stats
->totPacket
);
257 printf("\ttotal packets identified needing an acknowledge: %d\n",
258 matchingData
->stats
->totPacketNeedAck
);
259 printf("\ttotal exchanges (four events matched together): %d\n",
260 matchingData
->stats
->totExchangeEffective
);
261 printf("\ttotal synchronization exchanges: %d\n",
262 matchingData
->stats
->totExchangeSync
);
264 if (syncState
->analysisModule
->printAnalysisStats
!= NULL
)
266 syncState
->analysisModule
->printAnalysisStats(syncState
);
272 * Implementation of a packet matching algorithm for TCP
275 * netEvent: new event to match
276 * unMatchedList: list of unmatched events of the same type (send or
277 * receive) as netEvent
278 * unMatchedOppositeList: list of unmatched events of the opposite type of
280 * fieldOffset: offset of the NetEvent field in the Packet struct for the
281 * field of the type of netEvent
282 * oppositeFieldOffset: offset of the NetEvent field in the Packet struct
283 * for the field of the opposite type of netEvent
285 static void matchEvents(SyncState
* const syncState
, NetEvent
* const event
,
286 GHashTable
* const unMatchedList
, GHashTable
* const unMatchedOppositeList
,
287 const size_t fieldOffset
, const size_t oppositeFieldOffset
)
289 NetEvent
* companionEvent
;
291 MatchingDataTCP
* matchingData
;
294 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
296 companionEvent
= g_hash_table_lookup(unMatchedOppositeList
, event
->packetKey
);
297 if (companionEvent
!= NULL
)
299 g_debug("Found matching companion event, ");
301 if (syncState
->stats
)
303 matchingData
->stats
->totPacket
++;
306 // If it's there, remove it and create a Packet
307 g_hash_table_steal(unMatchedOppositeList
, event
->packetKey
);
308 packet
= malloc(sizeof(Packet
));
309 *((NetEvent
**) ((void*) packet
+ fieldOffset
))= event
;
310 *((NetEvent
**) ((void*) packet
+ oppositeFieldOffset
))= companionEvent
;
311 // Both events can now share the same packetKey
312 free(packet
->outE
->packetKey
);
313 packet
->outE
->packetKey
= packet
->inE
->packetKey
;
316 // Discard loopback traffic
317 if (packet
->inE
->traceNum
== packet
->outE
->traceNum
)
319 destroyPacket(packet
);
323 if (syncState
->analysisModule
->analyzePacket
)
325 syncState
->analysisModule
->analyzePacket(syncState
, packet
);
328 // We can skip the rest of the algorithm if the analysis module is not
329 // interested in exchanges
330 if (!syncState
->analysisModule
->analyzeExchange
)
332 destroyPacket(packet
);
336 // If this packet acknowleges some data ...
339 ConnectionKey oppositeConnectionKey
;
341 buildReversedConnectionKey(&oppositeConnectionKey
,
342 &event
->packetKey
->connectionKey
);
343 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
344 &oppositeConnectionKey
);
345 if (conUnAcked
!= NULL
)
350 result
= g_queue_find_custom(conUnAcked
, packet
, &gcfPacketAckCompare
);
352 while (result
!= NULL
)
354 // Remove the acknowledged packet from the unAcked list
355 // and keep it for later offset calculations
356 g_debug("Found matching unAcked packet, ");
358 ackedPacket
= (Packet
*) result
->data
;
359 g_queue_delete_link(conUnAcked
, result
);
361 if (syncState
->stats
)
363 matchingData
->stats
->totExchangeEffective
++;
366 if (packet
->acks
== NULL
)
368 packet
->acks
= g_queue_new();
371 g_queue_push_tail(packet
->acks
, ackedPacket
);
373 result
= g_queue_find_custom(conUnAcked
, packet
,
374 &gcfPacketAckCompare
);
377 // It might be possible to do an offset calculation
378 if (packet
->acks
!= NULL
)
380 ackedPacket
= g_queue_peek_tail(packet
->acks
);
381 if (ackedPacket
->outE
->traceNum
!= packet
->inE
->traceNum
382 || ackedPacket
->inE
->traceNum
!=
383 packet
->outE
->traceNum
|| packet
->inE
->traceNum
==
384 packet
->outE
->traceNum
)
386 printPacket(ackedPacket
);
388 g_error("Disorganized exchange encountered during "
393 if (syncState
->stats
)
395 matchingData
->stats
->totExchangeSync
++;
398 syncState
->analysisModule
->analyzeExchange(syncState
,
405 if (needsAck(packet
))
407 if (syncState
->stats
)
409 matchingData
->stats
->totPacketNeedAck
++;
412 // If this packet will generate an ack, add it to the unAcked list
413 g_debug("Adding to unAcked, ");
414 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
415 &event
->packetKey
->connectionKey
);
416 if (conUnAcked
== NULL
)
418 ConnectionKey
* connectionKey
;
420 connectionKey
= malloc(sizeof(ConnectionKey
));
421 memcpy(connectionKey
, &event
->packetKey
->connectionKey
,
422 sizeof(ConnectionKey
));
423 g_hash_table_insert(matchingData
->unAcked
, connectionKey
,
424 conUnAcked
= g_queue_new());
426 g_queue_push_tail(conUnAcked
, packet
);
430 destroyPacket(packet
);
435 // If there's no corresponding event, add the event to the unmatched
436 // list for this type of event
437 g_debug("Adding to unmatched event list, ");
438 g_hash_table_replace(unMatchedList
, event
->packetKey
, event
);
444 * Check if a packet is an acknowledge
450 static bool isAck(const Packet
* const packet
)
452 if (packet
->inE
->packetKey
->ack
== 1)
464 * Check if a packet will increment the sequence number, thus needing an
468 * true if the packet will need an acknowledge
471 static bool needsAck(const Packet
* const packet
)
473 if (packet
->inE
->packetKey
->syn
|| packet
->inE
->packetKey
->fin
||
474 packet
->inE
->packetKey
->tot_len
- packet
->inE
->packetKey
->ihl
* 4 -
475 packet
->inE
->packetKey
->doff
* 4 > 0)
487 * Populate a connection key structure for the opposite direction of a
491 * reversedConnectionKey the result, must be pre-allocated
492 * connectionKey the connection key to reverse
494 static void buildReversedConnectionKey(ConnectionKey
* const
495 reversedConnectionKey
, const ConnectionKey
* const connectionKey
)
497 reversedConnectionKey
->saddr
= connectionKey
->daddr
;
498 reversedConnectionKey
->daddr
= connectionKey
->saddr
;
499 reversedConnectionKey
->source
= connectionKey
->dest
;
500 reversedConnectionKey
->dest
= connectionKey
->source
;