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
, NetEvent
* const event
,
45 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
);
46 static void printMatchingStatsTCP(SyncState
* const syncState
);
47 static void writeMatchingGraphsPlotsTCP(FILE* stream
, SyncState
* const
48 syncState
, const unsigned int i
, const unsigned int j
);
49 static void writeMatchingGraphsOptionsTCP(FILE* stream
, SyncState
* const
50 syncState
, const unsigned int i
, const unsigned int j
);
52 // Functions specific to this module
53 static void registerMatchingTCP() __attribute__((constructor (101)));
55 static void matchEvents(SyncState
* const syncState
, NetEvent
* const event
,
56 GHashTable
* const unMatchedList
, GHashTable
* const
57 unMatchedOppositeList
, const size_t fieldOffset
, const size_t
59 static void partialDestroyMatchingTCP(SyncState
* const syncState
);
61 static bool isAck(const Packet
* const packet
);
62 static bool needsAck(const Packet
* const packet
);
63 static void buildReversedConnectionKey(ConnectionKey
* const
64 reversedConnectionKey
, const ConnectionKey
* const connectionKey
);
66 static void openGraphDataFiles(SyncState
* const syncState
);
67 static void closeGraphDataFiles(SyncState
* const syncState
);
68 static void writeMessagePoint(FILE* stream
, const Packet
* const packet
);
71 static MatchingModule matchingModuleTCP
= {
73 .initMatching
= &initMatchingTCP
,
74 .destroyMatching
= &destroyMatchingTCP
,
75 .matchEvent
= &matchEventTCP
,
76 .finalizeMatching
= &finalizeMatchingTCP
,
77 .printMatchingStats
= &printMatchingStatsTCP
,
78 .writeMatchingGraphsPlots
= &writeMatchingGraphsPlotsTCP
,
79 .writeMatchingGraphsOptions
= &writeMatchingGraphsOptionsTCP
,
84 * Matching module registering function
86 static void registerMatchingTCP()
88 g_queue_push_tail(&matchingModules
, &matchingModuleTCP
);
93 * Matching init function
95 * This function is called at the beginning of a synchronization run for a set
98 * Allocate the matching specific data structures
101 * syncState container for synchronization data.
102 * This function allocates these matchingData members:
108 static void initMatchingTCP(SyncState
* const syncState
)
110 MatchingDataTCP
* matchingData
;
112 matchingData
= malloc(sizeof(MatchingDataTCP
));
113 syncState
->matchingData
= matchingData
;
115 matchingData
->unMatchedInE
= g_hash_table_new_full(&ghfPacketKeyHash
,
116 &gefPacketKeyEqual
, NULL
, &gdnDestroyNetEvent
);
117 matchingData
->unMatchedOutE
= g_hash_table_new_full(&ghfPacketKeyHash
,
118 &gefPacketKeyEqual
, NULL
, &gdnDestroyNetEvent
);
119 matchingData
->unAcked
= g_hash_table_new_full(&ghfConnectionKeyHash
,
120 &gefConnectionKeyEqual
, &gdnConnectionKeyDestroy
,
121 &gdnPacketListDestroy
);
123 if (syncState
->stats
)
127 matchingData
->stats
= calloc(1, sizeof(MatchingStatsTCP
));
128 matchingData
->stats
->totMessageArray
= malloc(syncState
->traceNb
*
129 sizeof(unsigned int*));
130 for (i
= 0; i
< syncState
->traceNb
; i
++)
132 matchingData
->stats
->totMessageArray
[i
]=
133 calloc(syncState
->traceNb
, sizeof(unsigned int));
138 matchingData
->stats
= NULL
;
141 if (syncState
->graphs
)
143 openGraphDataFiles(syncState
);
147 matchingData
->messagePoints
= NULL
;
153 * Matching destroy function
155 * Free the matching specific data structures
158 * syncState container for synchronization data.
159 * This function deallocates these matchingData members:
162 static void destroyMatchingTCP(SyncState
* const syncState
)
164 MatchingDataTCP
* matchingData
;
166 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
168 if (matchingData
== NULL
)
173 partialDestroyMatchingTCP(syncState
);
175 if (syncState
->stats
)
179 for (i
= 0; i
< syncState
->traceNb
; i
++)
181 free(matchingData
->stats
->totMessageArray
[i
]);
183 free(matchingData
->stats
->totMessageArray
);
184 free(matchingData
->stats
);
187 free(syncState
->matchingData
);
188 syncState
->matchingData
= NULL
;
193 * Free some of the matching specific data structures
195 * This function can be called right after the events have been processed to
196 * free some data structures that are not needed for finalization.
199 * syncState container for synchronization data.
200 * This function deallocates these matchingData members:
205 static void partialDestroyMatchingTCP(SyncState
* const syncState
)
207 MatchingDataTCP
* matchingData
;
209 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
211 if (matchingData
== NULL
|| matchingData
->unMatchedInE
== NULL
)
216 g_hash_table_destroy(matchingData
->unMatchedInE
);
217 matchingData
->unMatchedInE
= NULL
;
218 g_hash_table_destroy(matchingData
->unMatchedOutE
);
219 g_hash_table_destroy(matchingData
->unAcked
);
221 if (syncState
->graphs
&& matchingData
->messagePoints
)
223 closeGraphDataFiles(syncState
);
229 * Try to match one event from a trace with the corresponding event from
233 * syncState container for synchronization data.
234 * event new event to match
235 * eventType type of event to match
237 static void matchEventTCP(SyncState
* const syncState
, NetEvent
* const event
, EventType eventType
)
239 MatchingDataTCP
* matchingData
;
241 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
245 matchEvents(syncState
, event
, matchingData
->unMatchedInE
,
246 matchingData
->unMatchedOutE
, offsetof(Packet
, inE
),
247 offsetof(Packet
, outE
));
251 matchEvents(syncState
, event
, matchingData
->unMatchedOutE
,
252 matchingData
->unMatchedInE
, offsetof(Packet
, outE
),
253 offsetof(Packet
, inE
));
259 * Call the partial matching destroyer and Obtain the factors from downstream
262 * syncState container for synchronization data.
265 * Factors[traceNb] synchronization factors for each trace
267 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
)
269 partialDestroyMatchingTCP(syncState
);
271 return syncState
->analysisModule
->finalizeAnalysis(syncState
);
276 * Print statistics related to matching and downstream modules. Must be
277 * called after finalizeMatching.
280 * syncState container for synchronization data.
282 static void printMatchingStatsTCP(SyncState
* const syncState
)
285 MatchingDataTCP
* matchingData
;
287 if (!syncState
->stats
)
292 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
294 printf("TCP matching stats:\n");
295 printf("\ttotal input and output events matched together to form a packet: %u\n",
296 matchingData
->stats
->totPacket
);
298 printf("\tMessage traffic:\n");
300 for (i
= 0; i
< syncState
->traceNb
; i
++)
302 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
304 printf("\t\t%3d - %-3d: sent %-10u received %-10u\n", i
, j
,
305 matchingData
->stats
->totMessageArray
[j
][i
],
306 matchingData
->stats
->totMessageArray
[i
][j
]);
310 if (syncState
->analysisModule
->analyzeExchange
!= NULL
)
312 printf("\ttotal packets identified needing an acknowledge: %u\n",
313 matchingData
->stats
->totPacketNeedAck
);
314 printf("\ttotal exchanges (four events matched together): %u\n",
315 matchingData
->stats
->totExchangeEffective
);
316 printf("\ttotal synchronization exchanges: %u\n",
317 matchingData
->stats
->totExchangeSync
);
320 if (syncState
->analysisModule
->printAnalysisStats
!= NULL
)
322 syncState
->analysisModule
->printAnalysisStats(syncState
);
328 * Implementation of a packet matching algorithm for TCP
331 * netEvent: new event to match
332 * unMatchedList: list of unmatched events of the same type (send or
333 * receive) as netEvent
334 * unMatchedOppositeList: list of unmatched events of the opposite type of
336 * fieldOffset: offset of the NetEvent field in the Packet struct for the
337 * field of the type of netEvent
338 * oppositeFieldOffset: offset of the NetEvent field in the Packet struct
339 * for the field of the opposite type of netEvent
341 static void matchEvents(SyncState
* const syncState
, NetEvent
* const event
,
342 GHashTable
* const unMatchedList
, GHashTable
* const unMatchedOppositeList
,
343 const size_t fieldOffset
, const size_t oppositeFieldOffset
)
345 NetEvent
* companionEvent
;
347 MatchingDataTCP
* matchingData
;
350 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
352 companionEvent
= g_hash_table_lookup(unMatchedOppositeList
, event
->packetKey
);
353 if (companionEvent
!= NULL
)
355 g_debug("Found matching companion event, ");
357 // If it's there, remove it and create a Packet
358 g_hash_table_steal(unMatchedOppositeList
, event
->packetKey
);
359 packet
= malloc(sizeof(Packet
));
360 *((NetEvent
**) ((void*) packet
+ fieldOffset
))= event
;
361 *((NetEvent
**) ((void*) packet
+ oppositeFieldOffset
))= companionEvent
;
362 // Both events can now share the same packetKey
363 free(packet
->outE
->packetKey
);
364 packet
->outE
->packetKey
= packet
->inE
->packetKey
;
367 if (syncState
->stats
)
369 matchingData
->stats
->totPacket
++;
370 matchingData
->stats
->totMessageArray
[packet
->inE
->traceNum
][packet
->outE
->traceNum
]++;
373 // Discard loopback traffic
374 if (packet
->inE
->traceNum
== packet
->outE
->traceNum
)
376 destroyPacket(packet
);
380 if (syncState
->graphs
)
382 writeMessagePoint(matchingData
->messagePoints
[packet
->inE
->traceNum
][packet
->outE
->traceNum
],
386 if (syncState
->analysisModule
->analyzePacket
!= NULL
)
388 syncState
->analysisModule
->analyzePacket(syncState
, packet
);
391 // We can skip the rest of the algorithm if the analysis module is not
392 // interested in exchanges
393 if (syncState
->analysisModule
->analyzeExchange
== NULL
)
395 destroyPacket(packet
);
399 // If this packet acknowleges some data ...
402 ConnectionKey oppositeConnectionKey
;
404 buildReversedConnectionKey(&oppositeConnectionKey
,
405 &event
->packetKey
->connectionKey
);
406 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
407 &oppositeConnectionKey
);
408 if (conUnAcked
!= NULL
)
413 result
= g_queue_find_custom(conUnAcked
, packet
, &gcfPacketAckCompare
);
415 while (result
!= NULL
)
417 // Remove the acknowledged packet from the unAcked list
418 // and keep it for later offset calculations
419 g_debug("Found matching unAcked packet, ");
421 ackedPacket
= (Packet
*) result
->data
;
422 g_queue_delete_link(conUnAcked
, result
);
424 if (syncState
->stats
)
426 matchingData
->stats
->totExchangeEffective
++;
429 if (packet
->acks
== NULL
)
431 packet
->acks
= g_queue_new();
434 g_queue_push_tail(packet
->acks
, ackedPacket
);
436 result
= g_queue_find_custom(conUnAcked
, packet
,
437 &gcfPacketAckCompare
);
440 // It might be possible to do an offset calculation
441 if (packet
->acks
!= NULL
)
443 ackedPacket
= g_queue_peek_tail(packet
->acks
);
444 if (ackedPacket
->outE
->traceNum
!= packet
->inE
->traceNum
445 || ackedPacket
->inE
->traceNum
!=
446 packet
->outE
->traceNum
|| packet
->inE
->traceNum
==
447 packet
->outE
->traceNum
)
449 printPacket(ackedPacket
);
451 g_error("Disorganized exchange encountered during "
456 if (syncState
->stats
)
458 matchingData
->stats
->totExchangeSync
++;
461 syncState
->analysisModule
->analyzeExchange(syncState
,
468 if (needsAck(packet
))
470 if (syncState
->stats
)
472 matchingData
->stats
->totPacketNeedAck
++;
475 // If this packet will generate an ack, add it to the unAcked list
476 g_debug("Adding to unAcked, ");
477 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
478 &event
->packetKey
->connectionKey
);
479 if (conUnAcked
== NULL
)
481 ConnectionKey
* connectionKey
;
483 connectionKey
= malloc(sizeof(ConnectionKey
));
484 memcpy(connectionKey
, &event
->packetKey
->connectionKey
,
485 sizeof(ConnectionKey
));
486 g_hash_table_insert(matchingData
->unAcked
, connectionKey
,
487 conUnAcked
= g_queue_new());
489 g_queue_push_tail(conUnAcked
, packet
);
493 destroyPacket(packet
);
498 // If there's no corresponding event, add the event to the unmatched
499 // list for this type of event
500 g_debug("Adding to unmatched event list, ");
501 g_hash_table_replace(unMatchedList
, event
->packetKey
, event
);
507 * Check if a packet is an acknowledge
513 static bool isAck(const Packet
* const packet
)
515 if (packet
->inE
->packetKey
->ack
== 1)
527 * Check if a packet will increment the sequence number, thus needing an
531 * true if the packet will need an acknowledge
534 static bool needsAck(const Packet
* const packet
)
536 if (packet
->inE
->packetKey
->syn
|| packet
->inE
->packetKey
->fin
||
537 packet
->inE
->packetKey
->tot_len
- packet
->inE
->packetKey
->ihl
* 4 -
538 packet
->inE
->packetKey
->doff
* 4 > 0)
550 * Populate a connection key structure for the opposite direction of a
554 * reversedConnectionKey the result, must be pre-allocated
555 * connectionKey the connection key to reverse
557 static void buildReversedConnectionKey(ConnectionKey
* const
558 reversedConnectionKey
, const ConnectionKey
* const connectionKey
)
560 reversedConnectionKey
->saddr
= connectionKey
->daddr
;
561 reversedConnectionKey
->daddr
= connectionKey
->saddr
;
562 reversedConnectionKey
->source
= connectionKey
->dest
;
563 reversedConnectionKey
->dest
= connectionKey
->source
;
568 * Create and open files used to store message points to genereate
569 * graphs. Allocate and populate array to store file pointers.
572 * syncState: container for synchronization data
574 static void openGraphDataFiles(SyncState
* const syncState
)
580 MatchingDataTCP
* matchingData
;
582 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
584 cwd
= changeToGraphDir(syncState
->graphs
);
586 matchingData
->messagePoints
= malloc(syncState
->traceNb
* sizeof(FILE**));
587 for (i
= 0; i
< syncState
->traceNb
; i
++)
589 matchingData
->messagePoints
[i
]= malloc(syncState
->traceNb
*
591 for (j
= 0; j
< syncState
->traceNb
; j
++)
595 retval
= snprintf(name
, sizeof(name
),
596 "matching_tcp-%03u_to_%03u.data", j
, i
);
597 if (retval
> sizeof(name
) - 1)
599 name
[sizeof(name
) - 1]= '\0';
601 if ((matchingData
->messagePoints
[i
][j
]= fopen(name
, "w")) ==
604 g_error(strerror(errno
));
613 g_error(strerror(errno
));
620 * Write a message point to a file used to generate graphs
623 * stream: FILE*, file pointer where to write the point
624 * packet: message for which to write the point
626 static void writeMessagePoint(FILE* stream
, const Packet
* const packet
)
630 if (packet
->inE
->traceNum
< packet
->outE
->traceNum
)
632 // CA is inE->traceNum
634 y
= packet
->outE
->tsc
;
638 // CA is outE->traceNum
639 x
= packet
->outE
->tsc
;
643 fprintf(stream
, "%20llu %20llu\n", x
, y
);
648 * Close files used to store convex hull points to genereate graphs.
649 * Deallocate array to store file pointers.
652 * syncState: container for synchronization data
654 static void closeGraphDataFiles(SyncState
* const syncState
)
657 MatchingDataTCP
* matchingData
;
660 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
662 if (matchingData
->messagePoints
== NULL
)
667 for (i
= 0; i
< syncState
->traceNb
; i
++)
669 for (j
= 0; j
< syncState
->traceNb
; j
++)
673 retval
= fclose(matchingData
->messagePoints
[i
][j
]);
676 g_error(strerror(errno
));
680 free(matchingData
->messagePoints
[i
]);
682 free(matchingData
->messagePoints
);
684 matchingData
->messagePoints
= NULL
;
689 * Write the matching-specific graph lines in the gnuplot script. Call the
690 * downstream module's graph function.
693 * stream: stream where to write the data
694 * syncState: container for synchronization data
695 * i: first trace number
696 * j: second trace number, garanteed to be larger than i
698 static void writeMatchingGraphsPlotsTCP(FILE* stream
, SyncState
* const
699 syncState
, const unsigned int i
, const unsigned int j
)
702 "\t\"matching_tcp-%1$03d_to_%2$03d.data\" "
703 "title \"Sent messages\" with points linetype 4 "
704 "linecolor rgb \"#98fc66\" pointtype 9 pointsize 2, \\\n"
705 "\t\"matching_tcp-%2$03d_to_%1$03d.data\" "
706 "title \"Received messages\" with points linetype 4 "
707 "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i
, j
);
709 if (syncState
->analysisModule
->writeAnalysisGraphsPlots
!= NULL
)
711 syncState
->analysisModule
->writeAnalysisGraphsPlots(stream
, syncState
,
718 * Write the matching-specific options in the gnuplot script (none). Call the
719 * downstream module's options function.
722 * stream: stream where to write the data
723 * syncState: container for synchronization data
724 * i: first trace number
725 * j: second trace number, garanteed to be larger than i
727 static void writeMatchingGraphsOptionsTCP(FILE* stream
, SyncState
* const
728 syncState
, const unsigned int i
, const unsigned int j
)
730 if (syncState
->analysisModule
->writeAnalysisGraphsOptions
!= NULL
)
732 syncState
->analysisModule
->writeAnalysisGraphsOptions(stream
,