Commit | Line | Data |
---|---|---|
70407e86 BP |
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 | #ifdef HAVE_CONFIG_H | |
20 | #include <config.h> | |
21 | #endif | |
22 | ||
23 | #include <stdlib.h> | |
24 | #include <string.h> | |
25 | ||
26 | #include "event_analysis.h" | |
27 | #include "sync_chain.h" | |
28 | ||
29 | #include "event_matching_tcp.h" | |
30 | ||
31 | ||
32 | #ifndef g_info | |
33 | #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format) | |
34 | #endif | |
35 | ||
36 | ||
37 | // Functions common to all matching modules | |
38 | static void initMatchingTCP(SyncState* const syncState); | |
39 | static void destroyMatchingTCP(SyncState* const syncState); | |
40 | ||
41 | static void matchEventTCP(SyncState* const syncState, NetEvent* const event, | |
42 | EventType eventType); | |
43 | static GArray* finalizeMatchingTCP(SyncState* const syncState); | |
44 | static void printMatchingStatsTCP(SyncState* const syncState); | |
45 | ||
46 | // Functions specific to this module | |
47 | static void registerMatchingTCP() __attribute__((constructor (101))); | |
48 | ||
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 | |
52 | oppositeFieldOffset); | |
53 | static void partialDestroyMatchingTCP(SyncState* const syncState); | |
54 | ||
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); | |
59 | ||
60 | ||
61 | static MatchingModule matchingModuleTCP = { | |
62 | .name= "TCP", | |
63 | .initMatching= &initMatchingTCP, | |
64 | .destroyMatching= &destroyMatchingTCP, | |
65 | .matchEvent= &matchEventTCP, | |
66 | .finalizeMatching= &finalizeMatchingTCP, | |
67 | .printMatchingStats= &printMatchingStatsTCP, | |
68 | }; | |
69 | ||
70 | ||
71 | /* | |
72 | * Matching module registering function | |
73 | */ | |
74 | static void registerMatchingTCP() | |
75 | { | |
76 | g_queue_push_tail(&matchingModules, &matchingModuleTCP); | |
77 | } | |
78 | ||
79 | ||
80 | /* | |
81 | * Matching init function | |
82 | * | |
83 | * This function is called at the beginning of a synchronization run for a set | |
84 | * of traces. | |
85 | * | |
86 | * Allocate the matching specific data structures | |
87 | * | |
88 | * Args: | |
89 | * syncState container for synchronization data. | |
90 | * This function allocates these matchingData members: | |
91 | * unMatchedInE | |
92 | * unMatchedOutE | |
93 | * unAcked | |
94 | * stats | |
95 | */ | |
96 | static void initMatchingTCP(SyncState* const syncState) | |
97 | { | |
98 | MatchingDataTCP* matchingData; | |
99 | ||
100 | matchingData= malloc(sizeof(MatchingDataTCP)); | |
101 | syncState->matchingData= matchingData; | |
102 | ||
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); | |
110 | ||
111 | if (syncState->stats) | |
112 | { | |
113 | matchingData->stats= calloc(1, sizeof(MatchingStatsTCP)); | |
114 | } | |
115 | else | |
116 | { | |
117 | matchingData->stats= NULL; | |
118 | } | |
119 | } | |
120 | ||
121 | ||
122 | /* | |
123 | * Matching destroy function | |
124 | * | |
125 | * Free the matching specific data structures | |
126 | * | |
127 | * Args: | |
128 | * syncState container for synchronization data. | |
129 | * This function deallocates these matchingData members: | |
130 | * stats | |
131 | */ | |
132 | static void destroyMatchingTCP(SyncState* const syncState) | |
133 | { | |
134 | MatchingDataTCP* matchingData; | |
135 | ||
136 | matchingData= (MatchingDataTCP*) syncState->matchingData; | |
137 | ||
138 | if (matchingData == NULL) | |
139 | { | |
140 | return; | |
141 | } | |
142 | ||
143 | partialDestroyMatchingTCP(syncState); | |
144 | ||
145 | if (syncState->stats) | |
146 | { | |
147 | free(matchingData->stats); | |
148 | } | |
149 | ||
150 | free(syncState->matchingData); | |
151 | syncState->matchingData= NULL; | |
152 | } | |
153 | ||
154 | ||
155 | /* | |
156 | * Free some of the matching specific data structures | |
157 | * | |
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. | |
160 | * | |
161 | * Args: | |
162 | * syncState container for synchronization data. | |
163 | * This function deallocates these matchingData members: | |
164 | * unMatchedInE | |
165 | * unMatchedOut | |
166 | * unAcked | |
167 | */ | |
168 | static void partialDestroyMatchingTCP(SyncState* const syncState) | |
169 | { | |
170 | MatchingDataTCP* matchingData; | |
171 | ||
172 | matchingData= (MatchingDataTCP*) syncState->matchingData; | |
173 | ||
174 | if (matchingData == NULL || matchingData->unMatchedInE == NULL) | |
175 | { | |
176 | return; | |
177 | } | |
178 | ||
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); | |
186 | } | |
187 | ||
188 | ||
189 | /* | |
190 | * Try to match one event from a trace with the corresponding event from | |
191 | * another trace. | |
192 | * | |
193 | * Args: | |
194 | * syncState container for synchronization data. | |
195 | * event new event to match | |
196 | * eventType type of event to match | |
197 | */ | |
198 | static void matchEventTCP(SyncState* const syncState, NetEvent* const event, EventType eventType) | |
199 | { | |
200 | MatchingDataTCP* matchingData; | |
201 | ||
202 | matchingData= (MatchingDataTCP*) syncState->matchingData; | |
203 | ||
204 | if (eventType == IN) | |
205 | { | |
206 | matchEvents(syncState, event, matchingData->unMatchedInE, | |
207 | matchingData->unMatchedOutE, offsetof(Packet, inE), | |
208 | offsetof(Packet, outE)); | |
209 | } | |
210 | else | |
211 | { | |
212 | matchEvents(syncState, event, matchingData->unMatchedOutE, | |
213 | matchingData->unMatchedInE, offsetof(Packet, outE), | |
214 | offsetof(Packet, inE)); | |
215 | } | |
216 | } | |
217 | ||
218 | ||
219 | /* | |
220 | * Call the partial matching destroyer and Obtain the factors from downstream | |
221 | * | |
222 | * Args: | |
223 | * syncState container for synchronization data. | |
224 | * | |
225 | * Returns: | |
226 | * Factors[traceNb] synchronization factors for each trace | |
227 | */ | |
228 | static GArray* finalizeMatchingTCP(SyncState* const syncState) | |
229 | { | |
230 | partialDestroyMatchingTCP(syncState); | |
231 | ||
232 | return syncState->analysisModule->finalizeAnalysis(syncState); | |
233 | } | |
234 | ||
235 | ||
236 | /* | |
237 | * Print statistics related to matching and downstream modules. Must be | |
238 | * called after finalizeMatching. | |
239 | * | |
240 | * Args: | |
241 | * syncState container for synchronization data. | |
242 | */ | |
243 | static void printMatchingStatsTCP(SyncState* const syncState) | |
244 | { | |
245 | MatchingDataTCP* matchingData; | |
246 | ||
247 | if (!syncState->stats) | |
248 | { | |
249 | return; | |
250 | } | |
251 | ||
252 | matchingData= (MatchingDataTCP*) syncState->matchingData; | |
253 | ||
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); | |
263 | ||
264 | if (syncState->analysisModule->printAnalysisStats != NULL) | |
265 | { | |
266 | syncState->analysisModule->printAnalysisStats(syncState); | |
267 | } | |
268 | } | |
269 | ||
270 | ||
271 | /* | |
272 | * Implementation of a packet matching algorithm for TCP | |
273 | * | |
274 | * Args: | |
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 | |
279 | * netEvent | |
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 | |
284 | */ | |
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) | |
288 | { | |
289 | NetEvent* companionEvent; | |
290 | Packet* packet; | |
291 | MatchingDataTCP* matchingData; | |
292 | GQueue* conUnAcked; | |
293 | ||
294 | matchingData= (MatchingDataTCP*) syncState->matchingData; | |
295 | ||
296 | companionEvent= g_hash_table_lookup(unMatchedOppositeList, event->packetKey); | |
297 | if (companionEvent != NULL) | |
298 | { | |
299 | g_debug("Found matching companion event, "); | |
300 | ||
301 | if (syncState->stats) | |
302 | { | |
303 | matchingData->stats->totPacket++; | |
304 | } | |
305 | ||
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; | |
314 | packet->acks= NULL; | |
315 | ||
316 | // Discard loopback traffic | |
317 | if (packet->inE->traceNum == packet->outE->traceNum) | |
318 | { | |
319 | destroyPacket(packet); | |
320 | return; | |
321 | } | |
322 | ||
323 | if (syncState->analysisModule->analyzePacket) | |
324 | { | |
325 | syncState->analysisModule->analyzePacket(syncState, packet); | |
326 | } | |
327 | ||
328 | // We can skip the rest of the algorithm if the analysis module is not | |
329 | // interested in exchanges | |
330 | if (!syncState->analysisModule->analyzeExchange) | |
331 | { | |
332 | destroyPacket(packet); | |
333 | return; | |
334 | } | |
335 | ||
336 | // If this packet acknowleges some data ... | |
337 | if (isAck(packet)) | |
338 | { | |
339 | ConnectionKey oppositeConnectionKey; | |
340 | ||
341 | buildReversedConnectionKey(&oppositeConnectionKey, | |
342 | &event->packetKey->connectionKey); | |
343 | conUnAcked= g_hash_table_lookup(matchingData->unAcked, | |
344 | &oppositeConnectionKey); | |
345 | if (conUnAcked != NULL) | |
346 | { | |
347 | Packet* ackedPacket; | |
348 | GList* result; | |
349 | ||
350 | result= g_queue_find_custom(conUnAcked, packet, &gcfPacketAckCompare); | |
351 | ||
352 | while (result != NULL) | |
353 | { | |
354 | // Remove the acknowledged packet from the unAcked list | |
355 | // and keep it for later offset calculations | |
356 | g_debug("Found matching unAcked packet, "); | |
357 | ||
358 | ackedPacket= (Packet*) result->data; | |
359 | g_queue_delete_link(conUnAcked, result); | |
360 | ||
361 | if (syncState->stats) | |
362 | { | |
363 | matchingData->stats->totExchangeEffective++; | |
364 | } | |
365 | ||
366 | if (packet->acks == NULL) | |
367 | { | |
368 | packet->acks= g_queue_new(); | |
369 | } | |
370 | ||
371 | g_queue_push_tail(packet->acks, ackedPacket); | |
372 | ||
373 | result= g_queue_find_custom(conUnAcked, packet, | |
374 | &gcfPacketAckCompare); | |
375 | } | |
376 | ||
377 | // It might be possible to do an offset calculation | |
378 | if (packet->acks != NULL) | |
379 | { | |
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) | |
385 | { | |
386 | printPacket(ackedPacket); | |
387 | printPacket(packet); | |
388 | g_error("Disorganized exchange encountered during " | |
389 | "synchronization"); | |
390 | } | |
391 | else | |
392 | { | |
393 | if (syncState->stats) | |
394 | { | |
395 | matchingData->stats->totExchangeSync++; | |
396 | } | |
397 | ||
398 | syncState->analysisModule->analyzeExchange(syncState, | |
399 | packet); | |
400 | } | |
401 | } | |
402 | } | |
403 | } | |
404 | ||
405 | if (needsAck(packet)) | |
406 | { | |
407 | if (syncState->stats) | |
408 | { | |
409 | matchingData->stats->totPacketNeedAck++; | |
410 | } | |
411 | ||
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) | |
417 | { | |
418 | ConnectionKey* connectionKey; | |
419 | ||
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()); | |
425 | } | |
426 | g_queue_push_tail(conUnAcked, packet); | |
427 | } | |
428 | else | |
429 | { | |
430 | destroyPacket(packet); | |
431 | } | |
432 | } | |
433 | else | |
434 | { | |
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); | |
439 | } | |
440 | } | |
441 | ||
442 | ||
443 | /* | |
444 | * Check if a packet is an acknowledge | |
445 | * | |
446 | * Returns: | |
447 | * true if it is, | |
448 | * false otherwise | |
449 | */ | |
450 | static bool isAck(const Packet* const packet) | |
451 | { | |
452 | if (packet->inE->packetKey->ack == 1) | |
453 | { | |
454 | return true; | |
455 | } | |
456 | else | |
457 | { | |
458 | return false; | |
459 | } | |
460 | } | |
461 | ||
462 | ||
463 | /* | |
464 | * Check if a packet will increment the sequence number, thus needing an | |
465 | * acknowledge | |
466 | * | |
467 | * Returns: | |
468 | * true if the packet will need an acknowledge | |
469 | * false otherwise | |
470 | */ | |
471 | static bool needsAck(const Packet* const packet) | |
472 | { | |
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) | |
476 | { | |
477 | return true; | |
478 | } | |
479 | else | |
480 | { | |
481 | return false; | |
482 | } | |
483 | } | |
484 | ||
485 | ||
486 | /* | |
487 | * Populate a connection key structure for the opposite direction of a | |
488 | * connection | |
489 | * | |
490 | * Args: | |
491 | * reversedConnectionKey the result, must be pre-allocated | |
492 | * connectionKey the connection key to reverse | |
493 | */ | |
494 | static void buildReversedConnectionKey(ConnectionKey* const | |
495 | reversedConnectionKey, const ConnectionKey* const connectionKey) | |
496 | { | |
497 | reversedConnectionKey->saddr= connectionKey->daddr; | |
498 | reversedConnectionKey->daddr= connectionKey->saddr; | |
499 | reversedConnectionKey->source= connectionKey->dest; | |
500 | reversedConnectionKey->dest= connectionKey->source; | |
501 | } |