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,
29 #include "event_analysis.h"
30 #include "sync_chain.h"
32 #include "event_matching_tcp.h"
35 // Functions common to all matching modules
36 static void initMatchingTCP(SyncState
* const syncState
);
37 static void destroyMatchingTCP(SyncState
* const syncState
);
39 static void matchEventTCP(SyncState
* const syncState
, Event
* const event
);
40 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
);
41 static void printMatchingStatsTCP(SyncState
* const syncState
);
42 static void writeMatchingGraphsPlotsTCPMessages(SyncState
* const syncState
,
43 const unsigned int i
, const unsigned int j
);
45 // Functions specific to this module
46 static void registerMatchingTCP() __attribute__((constructor (101)));
48 static void matchEvents(SyncState
* const syncState
, Event
* const event
,
49 GHashTable
* const unMatchedList
, GHashTable
* const
50 unMatchedOppositeList
, const size_t fieldOffset
, const size_t
52 static void partialDestroyMatchingTCP(SyncState
* const syncState
);
54 static bool isAck(const Message
* const message
);
55 static bool needsAck(const Message
* const message
);
56 static void buildReversedConnectionKey(ConnectionKey
* const
57 reversedConnectionKey
, const ConnectionKey
* const connectionKey
);
59 static void openGraphDataFiles(SyncState
* const syncState
);
60 static void closeGraphDataFiles(SyncState
* const syncState
);
61 static void writeMessagePoint(FILE* stream
, const Message
* const message
);
64 static MatchingModule matchingModuleTCP
= {
67 .canMatch
[UDP
]= false,
68 .initMatching
= &initMatchingTCP
,
69 .destroyMatching
= &destroyMatchingTCP
,
70 .matchEvent
= &matchEventTCP
,
71 .finalizeMatching
= &finalizeMatchingTCP
,
72 .printMatchingStats
= &printMatchingStatsTCP
,
74 .writeTraceTraceForePlots
= &writeMatchingGraphsPlotsTCPMessages
,
80 * Matching module registering function
82 static void registerMatchingTCP()
84 g_queue_push_tail(&matchingModules
, &matchingModuleTCP
);
89 * Matching init function
91 * This function is called at the beginning of a synchronization run for a set
94 * Allocate the matching specific data structures
97 * syncState container for synchronization data.
98 * This function allocates these matchingData members:
104 static void initMatchingTCP(SyncState
* const syncState
)
106 MatchingDataTCP
* matchingData
;
108 matchingData
= malloc(sizeof(MatchingDataTCP
));
109 syncState
->matchingData
= matchingData
;
111 matchingData
->unMatchedInE
= g_hash_table_new_full(&ghfSegmentKeyHash
,
112 &gefSegmentKeyEqual
, NULL
, &gdnDestroyEvent
);
113 matchingData
->unMatchedOutE
= g_hash_table_new_full(&ghfSegmentKeyHash
,
114 &gefSegmentKeyEqual
, NULL
, &gdnDestroyEvent
);
115 matchingData
->unAcked
= g_hash_table_new_full(&ghfConnectionKeyHash
,
116 &gefConnectionKeyEqual
, &gdnConnectionKeyDestroy
,
117 &gdnTCPSegmentListDestroy
);
119 if (syncState
->stats
)
123 matchingData
->stats
= calloc(1, sizeof(MatchingStatsTCP
));
124 matchingData
->stats
->totMessageArray
= malloc(syncState
->traceNb
*
125 sizeof(unsigned int*));
126 for (i
= 0; i
< syncState
->traceNb
; i
++)
128 matchingData
->stats
->totMessageArray
[i
]=
129 calloc(syncState
->traceNb
, sizeof(unsigned int));
134 matchingData
->stats
= NULL
;
137 if (syncState
->graphsStream
)
139 openGraphDataFiles(syncState
);
143 matchingData
->messagePoints
= NULL
;
149 * Matching destroy function
151 * Free the matching specific data structures
154 * syncState container for synchronization data.
155 * This function deallocates these matchingData members:
158 static void destroyMatchingTCP(SyncState
* const syncState
)
160 MatchingDataTCP
* matchingData
;
162 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
164 if (matchingData
== NULL
)
169 partialDestroyMatchingTCP(syncState
);
171 if (syncState
->stats
)
175 for (i
= 0; i
< syncState
->traceNb
; i
++)
177 free(matchingData
->stats
->totMessageArray
[i
]);
179 free(matchingData
->stats
->totMessageArray
);
180 free(matchingData
->stats
);
183 free(syncState
->matchingData
);
184 syncState
->matchingData
= NULL
;
189 * Free some of the matching specific data structures
191 * This function can be called right after the events have been processed to
192 * free some data structures that are not needed for finalization.
195 * syncState container for synchronization data.
196 * This function deallocates these matchingData members:
201 static void partialDestroyMatchingTCP(SyncState
* const syncState
)
203 MatchingDataTCP
* matchingData
;
205 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
207 if (matchingData
== NULL
|| matchingData
->unMatchedInE
== NULL
)
212 g_hash_table_destroy(matchingData
->unMatchedInE
);
213 matchingData
->unMatchedInE
= NULL
;
214 g_hash_table_destroy(matchingData
->unMatchedOutE
);
215 g_hash_table_destroy(matchingData
->unAcked
);
217 if (syncState
->graphsStream
&& matchingData
->messagePoints
)
219 closeGraphDataFiles(syncState
);
225 * Try to match one event from a trace with the corresponding event from
229 * syncState container for synchronization data.
230 * event new event to match
232 static void matchEventTCP(SyncState
* const syncState
, Event
* const event
)
234 MatchingDataTCP
* matchingData
;
236 g_assert(event
->type
== TCP
);
238 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
240 if (event
->event
.tcpEvent
->direction
== IN
)
242 matchEvents(syncState
, event
, matchingData
->unMatchedInE
,
243 matchingData
->unMatchedOutE
, offsetof(Message
, inE
),
244 offsetof(Message
, outE
));
248 matchEvents(syncState
, event
, matchingData
->unMatchedOutE
,
249 matchingData
->unMatchedInE
, offsetof(Message
, outE
),
250 offsetof(Message
, inE
));
256 * Call the partial matching destroyer and Obtain the factors from downstream
259 * syncState container for synchronization data.
262 * Factors[traceNb] synchronization factors for each trace
264 static GArray
* finalizeMatchingTCP(SyncState
* const syncState
)
266 partialDestroyMatchingTCP(syncState
);
268 return syncState
->analysisModule
->finalizeAnalysis(syncState
);
273 * Print statistics related to matching. Must be called after
277 * syncState container for synchronization data.
279 static void printMatchingStatsTCP(SyncState
* const syncState
)
282 MatchingDataTCP
* matchingData
;
284 if (!syncState
->stats
)
289 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
291 printf("TCP matching stats:\n");
292 printf("\ttotal input and output events matched together to form a packet: %u\n",
293 matchingData
->stats
->totPacket
);
295 printf("\tMessage traffic:\n");
297 for (i
= 0; i
< syncState
->traceNb
; i
++)
299 for (j
= i
+ 1; j
< syncState
->traceNb
; j
++)
301 printf("\t\t%3d - %-3d: sent %-10u received %-10u\n", i
, j
,
302 matchingData
->stats
->totMessageArray
[j
][i
],
303 matchingData
->stats
->totMessageArray
[i
][j
]);
307 if (syncState
->analysisModule
->analyzeExchange
!= NULL
)
309 printf("\ttotal packets identified needing an acknowledge: %u\n",
310 matchingData
->stats
->totPacketNeedAck
);
311 printf("\ttotal exchanges (four events matched together): %u\n",
312 matchingData
->stats
->totExchangeEffective
);
313 printf("\ttotal synchronization exchanges: %u\n",
314 matchingData
->stats
->totExchangeSync
);
320 * Implementation of a packet matching algorithm for TCP
323 * event: new event to match
324 * unMatchedList: list of unmatched events of the same type (send or
326 * unMatchedOppositeList: list of unmatched events of the opposite type of
328 * fieldOffset: offset of the Event field in the Message struct for the
329 * field of the type of event
330 * oppositeFieldOffset: offset of the Event field in the Message struct
331 * for the field of the opposite type of event
333 static void matchEvents(SyncState
* const syncState
, Event
* const event
,
334 GHashTable
* const unMatchedList
, GHashTable
* const unMatchedOppositeList
,
335 const size_t fieldOffset
, const size_t oppositeFieldOffset
)
337 Event
* companionEvent
;
339 MatchingDataTCP
* matchingData
;
342 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
344 companionEvent
= g_hash_table_lookup(unMatchedOppositeList
, event
->event
.tcpEvent
->segmentKey
);
345 if (companionEvent
!= NULL
)
347 g_debug("Found matching companion event, ");
349 // If it's there, remove it and create a Message
350 g_hash_table_steal(unMatchedOppositeList
, event
->event
.tcpEvent
->segmentKey
);
351 packet
= malloc(sizeof(Message
));
352 *((Event
**) ((void*) packet
+ fieldOffset
))= event
;
353 *((Event
**) ((void*) packet
+ oppositeFieldOffset
))= companionEvent
;
354 packet
->print
= &printTCPSegment
;
355 // Both events can now share the same segmentKey
356 free(packet
->outE
->event
.tcpEvent
->segmentKey
);
357 packet
->outE
->event
.tcpEvent
->segmentKey
= packet
->inE
->event
.tcpEvent
->segmentKey
;
359 if (syncState
->stats
)
361 matchingData
->stats
->totPacket
++;
362 matchingData
->stats
->totMessageArray
[packet
->inE
->traceNum
][packet
->outE
->traceNum
]++;
365 // Discard loopback traffic
366 if (packet
->inE
->traceNum
== packet
->outE
->traceNum
)
368 destroyTCPSegment(packet
);
372 if (syncState
->graphsStream
)
374 writeMessagePoint(matchingData
->messagePoints
[packet
->inE
->traceNum
][packet
->outE
->traceNum
],
378 if (syncState
->analysisModule
->analyzeMessage
!= NULL
)
380 syncState
->analysisModule
->analyzeMessage(syncState
, packet
);
383 // We can skip the rest of the algorithm if the analysis module is not
384 // interested in exchanges
385 if (syncState
->analysisModule
->analyzeExchange
== NULL
)
387 destroyTCPSegment(packet
);
391 // If this packet acknowleges some data ...
394 ConnectionKey oppositeConnectionKey
;
396 buildReversedConnectionKey(&oppositeConnectionKey
,
397 &event
->event
.tcpEvent
->segmentKey
->connectionKey
);
398 conUnAcked
= g_hash_table_lookup(matchingData
->unAcked
,
399 &oppositeConnectionKey
);
400 if (conUnAcked
!= NULL
)
402 Message
* ackedPacket
;
408 result
= g_queue_find_custom(conUnAcked
, packet
, &gcfTCPSegmentAckCompare
);
410 while (result
!= NULL
)
412 // Remove the acknowledged packet from the unAcked list
413 // and keep it for later offset calculations
414 g_debug("Found matching unAcked packet, ");
416 ackedPacket
= (Message
*) result
->data
;
417 g_queue_delete_link(conUnAcked
, result
);
419 if (syncState
->stats
)
421 matchingData
->stats
->totExchangeEffective
++;
424 if (exchange
== NULL
)
426 exchange
= malloc(sizeof(Exchange
));
427 exchange
->message
= packet
;
428 exchange
->acks
= g_queue_new();
431 g_queue_push_tail(exchange
->acks
, ackedPacket
);
433 result
= g_queue_find_custom(conUnAcked
, packet
,
434 &gcfTCPSegmentAckCompare
);
437 // It might be possible to do an offset calculation
438 if (exchange
!= NULL
)
440 ackedPacket
= g_queue_peek_tail(exchange
->acks
);
441 if (ackedPacket
->outE
->traceNum
!= packet
->inE
->traceNum
442 || ackedPacket
->inE
->traceNum
!=
443 packet
->outE
->traceNum
|| packet
->inE
->traceNum
==
444 packet
->outE
->traceNum
)
446 ackedPacket
->print(ackedPacket
);
447 packet
->print(packet
);
448 g_error("Disorganized exchange encountered during "
453 if (syncState
->stats
)
455 matchingData
->stats
->totExchangeSync
++;
458 syncState
->analysisModule
->analyzeExchange(syncState
,
462 exchange
->message
= NULL
;
463 destroyTCPExchange(exchange
);
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
->event
.tcpEvent
->segmentKey
->connectionKey
);
479 if (conUnAcked
== NULL
)
481 ConnectionKey
* connectionKey
;
483 connectionKey
= malloc(sizeof(ConnectionKey
));
484 memcpy(connectionKey
, &event
->event
.tcpEvent
->segmentKey
->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 destroyTCPSegment(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
->event
.tcpEvent
->segmentKey
, event
);
507 * Check if a packet is an acknowledge
516 static bool isAck(const Message
* const packet
)
518 if (packet
->inE
->event
.tcpEvent
->segmentKey
->ack
== 1)
530 * Check if a packet will increment the sequence number, thus needing an
537 * true if the packet will need an acknowledge
540 static bool needsAck(const Message
* const packet
)
542 if (packet
->inE
->event
.tcpEvent
->segmentKey
->syn
|| packet
->inE
->event
.tcpEvent
->segmentKey
->fin
||
543 packet
->inE
->event
.tcpEvent
->segmentKey
->tot_len
- packet
->inE
->event
.tcpEvent
->segmentKey
->ihl
* 4 -
544 packet
->inE
->event
.tcpEvent
->segmentKey
->doff
* 4 > 0)
556 * Populate a connection key structure for the opposite direction of a
560 * reversedConnectionKey the result, must be pre-allocated
561 * connectionKey the connection key to reverse
563 static void buildReversedConnectionKey(ConnectionKey
* const
564 reversedConnectionKey
, const ConnectionKey
* const connectionKey
)
566 reversedConnectionKey
->saddr
= connectionKey
->daddr
;
567 reversedConnectionKey
->daddr
= connectionKey
->saddr
;
568 reversedConnectionKey
->source
= connectionKey
->dest
;
569 reversedConnectionKey
->dest
= connectionKey
->source
;
574 * Create and open files used to store message points to genereate
575 * graphs. Allocate and populate array to store file pointers.
578 * syncState: container for synchronization data
580 static void openGraphDataFiles(SyncState
* const syncState
)
586 MatchingDataTCP
* matchingData
;
588 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
590 cwd
= changeToGraphsDir(syncState
->graphsDir
);
592 matchingData
->messagePoints
= malloc(syncState
->traceNb
* sizeof(FILE**));
593 for (i
= 0; i
< syncState
->traceNb
; i
++)
595 matchingData
->messagePoints
[i
]= malloc(syncState
->traceNb
*
597 for (j
= 0; j
< syncState
->traceNb
; j
++)
601 retval
= snprintf(name
, sizeof(name
),
602 "matching_tcp-%03u_to_%03u.data", j
, i
);
603 if (retval
> sizeof(name
) - 1)
605 name
[sizeof(name
) - 1]= '\0';
607 if ((matchingData
->messagePoints
[i
][j
]= fopen(name
, "w")) ==
610 g_error(strerror(errno
));
619 g_error(strerror(errno
));
626 * Write a message point to a file used to generate graphs
629 * stream: FILE*, file pointer where to write the point
630 * message: message for which to write the point
632 static void writeMessagePoint(FILE* stream
, const Message
* const message
)
636 if (message
->inE
->traceNum
< message
->outE
->traceNum
)
638 // CA is inE->traceNum
639 x
= message
->inE
->cpuTime
;
640 y
= message
->outE
->cpuTime
;
644 // CA is outE->traceNum
645 x
= message
->outE
->cpuTime
;
646 y
= message
->inE
->cpuTime
;
649 fprintf(stream
, "%20" PRIu64
" %20" PRIu64
"\n", x
, y
);
654 * Close files used to store convex hull points to genereate graphs.
655 * Deallocate array to store file pointers.
658 * syncState: container for synchronization data
660 static void closeGraphDataFiles(SyncState
* const syncState
)
663 MatchingDataTCP
* matchingData
;
666 matchingData
= (MatchingDataTCP
*) syncState
->matchingData
;
668 if (matchingData
->messagePoints
== NULL
)
673 for (i
= 0; i
< syncState
->traceNb
; i
++)
675 for (j
= 0; j
< syncState
->traceNb
; j
++)
679 retval
= fclose(matchingData
->messagePoints
[i
][j
]);
682 g_error(strerror(errno
));
686 free(matchingData
->messagePoints
[i
]);
688 free(matchingData
->messagePoints
);
690 matchingData
->messagePoints
= NULL
;
695 * Write the matching-specific graph lines in the gnuplot script.
698 * syncState: container for synchronization data
699 * i: first trace number
700 * j: second trace number, garanteed to be larger than i
702 static void writeMatchingGraphsPlotsTCPMessages(SyncState
* const syncState
,
703 const unsigned int i
, const unsigned int j
)
705 fprintf(syncState
->graphsStream
,
706 "\t\"matching_tcp-%1$03d_to_%2$03d.data\" "
707 "title \"Sent messages\" with points linetype 4 "
708 "linecolor rgb \"#98fc66\" pointtype 9 pointsize 2, \\\n"
709 "\t\"matching_tcp-%2$03d_to_%1$03d.data\" "
710 "title \"Received messages\" with points linetype 4 "
711 "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i
, j
);