25e39858fb8b36c76c19c11bcd0efe5d64a5ba09
[lttv.git] / lttv / lttv / sync / event_matching_tcp.c
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 <errno.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <unistd.h>
27
28 #include "event_analysis.h"
29 #include "sync_chain_lttv.h"
30
31 #include "event_matching_tcp.h"
32
33
34 #ifndef g_info
35 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
36 #endif
37
38
39 // Functions common to all matching modules
40 static void initMatchingTCP(SyncState* const syncState);
41 static void destroyMatchingTCP(SyncState* const syncState);
42
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);
50
51 // Functions specific to this module
52 static void registerMatchingTCP() __attribute__((constructor (101)));
53
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
57 oppositeFieldOffset);
58 static void partialDestroyMatchingTCP(SyncState* const syncState);
59
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);
64
65 static void openGraphDataFiles(SyncState* const syncState);
66 static void closeGraphDataFiles(SyncState* const syncState);
67 static void writeMessagePoint(FILE* stream, const Message* const message);
68
69
70 static MatchingModule matchingModuleTCP = {
71 .name= "TCP",
72 .initMatching= &initMatchingTCP,
73 .destroyMatching= &destroyMatchingTCP,
74 .matchEvent= &matchEventTCP,
75 .finalizeMatching= &finalizeMatchingTCP,
76 .printMatchingStats= &printMatchingStatsTCP,
77 .writeMatchingGraphsPlots= &writeMatchingGraphsPlotsTCP,
78 .writeMatchingGraphsOptions= &writeMatchingGraphsOptionsTCP,
79 };
80
81
82 /*
83 * Matching module registering function
84 */
85 static void registerMatchingTCP()
86 {
87 g_queue_push_tail(&matchingModules, &matchingModuleTCP);
88 }
89
90
91 /*
92 * Matching init function
93 *
94 * This function is called at the beginning of a synchronization run for a set
95 * of traces.
96 *
97 * Allocate the matching specific data structures
98 *
99 * Args:
100 * syncState container for synchronization data.
101 * This function allocates these matchingData members:
102 * unMatchedInE
103 * unMatchedOutE
104 * unAcked
105 * stats
106 */
107 static void initMatchingTCP(SyncState* const syncState)
108 {
109 MatchingDataTCP* matchingData;
110
111 matchingData= malloc(sizeof(MatchingDataTCP));
112 syncState->matchingData= matchingData;
113
114 matchingData->unMatchedInE= g_hash_table_new_full(&ghfSegmentKeyHash,
115 &gefSegmentKeyEqual, NULL, &gdnDestroyEvent);
116 matchingData->unMatchedOutE= g_hash_table_new_full(&ghfSegmentKeyHash,
117 &gefSegmentKeyEqual, NULL, &gdnDestroyEvent);
118 matchingData->unAcked= g_hash_table_new_full(&ghfConnectionKeyHash,
119 &gefConnectionKeyEqual, &gdnConnectionKeyDestroy,
120 &gdnTCPSegmentListDestroy);
121
122 if (syncState->stats)
123 {
124 unsigned int i;
125
126 matchingData->stats= calloc(1, sizeof(MatchingStatsTCP));
127 matchingData->stats->totMessageArray= malloc(syncState->traceNb *
128 sizeof(unsigned int*));
129 for (i= 0; i < syncState->traceNb; i++)
130 {
131 matchingData->stats->totMessageArray[i]=
132 calloc(syncState->traceNb, sizeof(unsigned int));
133 }
134 }
135 else
136 {
137 matchingData->stats= NULL;
138 }
139
140 if (syncState->graphs)
141 {
142 openGraphDataFiles(syncState);
143 }
144 else
145 {
146 matchingData->messagePoints= NULL;
147 }
148 }
149
150
151 /*
152 * Matching destroy function
153 *
154 * Free the matching specific data structures
155 *
156 * Args:
157 * syncState container for synchronization data.
158 * This function deallocates these matchingData members:
159 * stats
160 */
161 static void destroyMatchingTCP(SyncState* const syncState)
162 {
163 MatchingDataTCP* matchingData;
164
165 matchingData= (MatchingDataTCP*) syncState->matchingData;
166
167 if (matchingData == NULL)
168 {
169 return;
170 }
171
172 partialDestroyMatchingTCP(syncState);
173
174 if (syncState->stats)
175 {
176 unsigned int i;
177
178 for (i= 0; i < syncState->traceNb; i++)
179 {
180 free(matchingData->stats->totMessageArray[i]);
181 }
182 free(matchingData->stats->totMessageArray);
183 free(matchingData->stats);
184 }
185
186 free(syncState->matchingData);
187 syncState->matchingData= NULL;
188 }
189
190
191 /*
192 * Free some of the matching specific data structures
193 *
194 * This function can be called right after the events have been processed to
195 * free some data structures that are not needed for finalization.
196 *
197 * Args:
198 * syncState container for synchronization data.
199 * This function deallocates these matchingData members:
200 * unMatchedInE
201 * unMatchedOut
202 * unAcked
203 */
204 static void partialDestroyMatchingTCP(SyncState* const syncState)
205 {
206 MatchingDataTCP* matchingData;
207
208 matchingData= (MatchingDataTCP*) syncState->matchingData;
209
210 if (matchingData == NULL || matchingData->unMatchedInE == NULL)
211 {
212 return;
213 }
214
215 g_hash_table_destroy(matchingData->unMatchedInE);
216 matchingData->unMatchedInE= NULL;
217 g_hash_table_destroy(matchingData->unMatchedOutE);
218 g_hash_table_destroy(matchingData->unAcked);
219
220 if (syncState->graphs && matchingData->messagePoints)
221 {
222 closeGraphDataFiles(syncState);
223 }
224 }
225
226
227 /*
228 * Try to match one event from a trace with the corresponding event from
229 * another trace.
230 *
231 * Args:
232 * syncState container for synchronization data.
233 * event new event to match
234 * eventType type of event to match
235 */
236 static void matchEventTCP(SyncState* const syncState, Event* const event)
237 {
238 MatchingDataTCP* matchingData;
239
240 matchingData= (MatchingDataTCP*) syncState->matchingData;
241
242 if (event->event.tcpEvent->direction == IN)
243 {
244 matchEvents(syncState, event, matchingData->unMatchedInE,
245 matchingData->unMatchedOutE, offsetof(Message, inE),
246 offsetof(Message, outE));
247 }
248 else
249 {
250 matchEvents(syncState, event, matchingData->unMatchedOutE,
251 matchingData->unMatchedInE, offsetof(Message, outE),
252 offsetof(Message, inE));
253 }
254 }
255
256
257 /*
258 * Call the partial matching destroyer and Obtain the factors from downstream
259 *
260 * Args:
261 * syncState container for synchronization data.
262 *
263 * Returns:
264 * Factors[traceNb] synchronization factors for each trace
265 */
266 static GArray* finalizeMatchingTCP(SyncState* const syncState)
267 {
268 partialDestroyMatchingTCP(syncState);
269
270 return syncState->analysisModule->finalizeAnalysis(syncState);
271 }
272
273
274 /*
275 * Print statistics related to matching and downstream modules. Must be
276 * called after finalizeMatching.
277 *
278 * Args:
279 * syncState container for synchronization data.
280 */
281 static void printMatchingStatsTCP(SyncState* const syncState)
282 {
283 unsigned int i, j;
284 MatchingDataTCP* matchingData;
285
286 if (!syncState->stats)
287 {
288 return;
289 }
290
291 matchingData= (MatchingDataTCP*) syncState->matchingData;
292
293 printf("TCP matching stats:\n");
294 printf("\ttotal input and output events matched together to form a packet: %u\n",
295 matchingData->stats->totPacket);
296
297 printf("\tMessage traffic:\n");
298
299 for (i= 0; i < syncState->traceNb; i++)
300 {
301 for (j= i + 1; j < syncState->traceNb; j++)
302 {
303 printf("\t\t%3d - %-3d: sent %-10u received %-10u\n", i, j,
304 matchingData->stats->totMessageArray[j][i],
305 matchingData->stats->totMessageArray[i][j]);
306 }
307 }
308
309 if (syncState->analysisModule->analyzeExchange != NULL)
310 {
311 printf("\ttotal packets identified needing an acknowledge: %u\n",
312 matchingData->stats->totPacketNeedAck);
313 printf("\ttotal exchanges (four events matched together): %u\n",
314 matchingData->stats->totExchangeEffective);
315 printf("\ttotal synchronization exchanges: %u\n",
316 matchingData->stats->totExchangeSync);
317 }
318
319 if (syncState->analysisModule->printAnalysisStats != NULL)
320 {
321 syncState->analysisModule->printAnalysisStats(syncState);
322 }
323 }
324
325
326 /*
327 * Implementation of a packet matching algorithm for TCP
328 *
329 * Args:
330 * event: new event to match
331 * unMatchedList: list of unmatched events of the same type (send or
332 * receive) as event
333 * unMatchedOppositeList: list of unmatched events of the opposite type of
334 * event
335 * fieldOffset: offset of the Event field in the Message struct for the
336 * field of the type of event
337 * oppositeFieldOffset: offset of the Event field in the Message struct
338 * for the field of the opposite type of event
339 */
340 static void matchEvents(SyncState* const syncState, Event* const event,
341 GHashTable* const unMatchedList, GHashTable* const unMatchedOppositeList,
342 const size_t fieldOffset, const size_t oppositeFieldOffset)
343 {
344 Event* companionEvent;
345 Message* packet;
346 MatchingDataTCP* matchingData;
347 GQueue* conUnAcked;
348
349 matchingData= (MatchingDataTCP*) syncState->matchingData;
350
351 companionEvent= g_hash_table_lookup(unMatchedOppositeList, event->event.tcpEvent->segmentKey);
352 if (companionEvent != NULL)
353 {
354 g_debug("Found matching companion event, ");
355
356 // If it's there, remove it and create a Message
357 g_hash_table_steal(unMatchedOppositeList, event->event.tcpEvent->segmentKey);
358 packet= malloc(sizeof(Message));
359 *((Event**) ((void*) packet + fieldOffset))= event;
360 *((Event**) ((void*) packet + oppositeFieldOffset))= companionEvent;
361 packet->print= &printTCPSegment;
362 // Both events can now share the same segmentKey
363 free(packet->outE->event.tcpEvent->segmentKey);
364 packet->outE->event.tcpEvent->segmentKey= packet->inE->event.tcpEvent->segmentKey;
365
366 if (syncState->stats)
367 {
368 matchingData->stats->totPacket++;
369 matchingData->stats->totMessageArray[packet->inE->traceNum][packet->outE->traceNum]++;
370 }
371
372 // Discard loopback traffic
373 if (packet->inE->traceNum == packet->outE->traceNum)
374 {
375 destroyTCPSegment(packet);
376 return;
377 }
378
379 if (syncState->graphs)
380 {
381 writeMessagePoint(matchingData->messagePoints[packet->inE->traceNum][packet->outE->traceNum],
382 packet);
383 }
384
385 if (syncState->analysisModule->analyzeMessage != NULL)
386 {
387 syncState->analysisModule->analyzeMessage(syncState, packet);
388 }
389
390 // We can skip the rest of the algorithm if the analysis module is not
391 // interested in exchanges
392 if (syncState->analysisModule->analyzeExchange == NULL)
393 {
394 destroyTCPSegment(packet);
395 return;
396 }
397
398 // If this packet acknowleges some data ...
399 if (isAck(packet))
400 {
401 ConnectionKey oppositeConnectionKey;
402
403 buildReversedConnectionKey(&oppositeConnectionKey,
404 &event->event.tcpEvent->segmentKey->connectionKey);
405 conUnAcked= g_hash_table_lookup(matchingData->unAcked,
406 &oppositeConnectionKey);
407 if (conUnAcked != NULL)
408 {
409 Message* ackedPacket;
410 GList* result;
411 Exchange* exchange;
412
413 exchange= NULL;
414
415 result= g_queue_find_custom(conUnAcked, packet, &gcfTCPSegmentAckCompare);
416
417 while (result != NULL)
418 {
419 // Remove the acknowledged packet from the unAcked list
420 // and keep it for later offset calculations
421 g_debug("Found matching unAcked packet, ");
422
423 ackedPacket= (Message*) result->data;
424 g_queue_delete_link(conUnAcked, result);
425
426 if (syncState->stats)
427 {
428 matchingData->stats->totExchangeEffective++;
429 }
430
431 if (exchange == NULL)
432 {
433 exchange= malloc(sizeof(Exchange));
434 exchange->message= packet;
435 exchange->acks= g_queue_new();
436 }
437
438 g_queue_push_tail(exchange->acks, ackedPacket);
439
440 result= g_queue_find_custom(conUnAcked, packet,
441 &gcfTCPSegmentAckCompare);
442 }
443
444 // It might be possible to do an offset calculation
445 if (exchange != NULL)
446 {
447 ackedPacket= g_queue_peek_tail(exchange->acks);
448 if (ackedPacket->outE->traceNum != packet->inE->traceNum
449 || ackedPacket->inE->traceNum !=
450 packet->outE->traceNum || packet->inE->traceNum ==
451 packet->outE->traceNum)
452 {
453 ackedPacket->print(ackedPacket);
454 packet->print(packet);
455 g_error("Disorganized exchange encountered during "
456 "synchronization");
457 }
458 else
459 {
460 if (syncState->stats)
461 {
462 matchingData->stats->totExchangeSync++;
463 }
464
465 syncState->analysisModule->analyzeExchange(syncState,
466 exchange);
467 }
468
469 exchange->message= NULL;
470 destroyTCPExchange(exchange);
471 }
472 }
473 }
474
475 if (needsAck(packet))
476 {
477 if (syncState->stats)
478 {
479 matchingData->stats->totPacketNeedAck++;
480 }
481
482 // If this packet will generate an ack, add it to the unAcked list
483 g_debug("Adding to unAcked, ");
484 conUnAcked= g_hash_table_lookup(matchingData->unAcked,
485 &event->event.tcpEvent->segmentKey->connectionKey);
486 if (conUnAcked == NULL)
487 {
488 ConnectionKey* connectionKey;
489
490 connectionKey= malloc(sizeof(ConnectionKey));
491 memcpy(connectionKey, &event->event.tcpEvent->segmentKey->connectionKey,
492 sizeof(ConnectionKey));
493 g_hash_table_insert(matchingData->unAcked, connectionKey,
494 conUnAcked= g_queue_new());
495 }
496 g_queue_push_tail(conUnAcked, packet);
497 }
498 else
499 {
500 destroyTCPSegment(packet);
501 }
502 }
503 else
504 {
505 // If there's no corresponding event, add the event to the unmatched
506 // list for this type of event
507 g_debug("Adding to unmatched event list, ");
508 g_hash_table_replace(unMatchedList, event->event.tcpEvent->segmentKey, event);
509 }
510 }
511
512
513 /*
514 * Check if a packet is an acknowledge
515 *
516 * Args:
517 * packet TCP Message
518 *
519 * Returns:
520 * true if it is,
521 * false otherwise
522 */
523 static bool isAck(const Message* const packet)
524 {
525 if (packet->inE->event.tcpEvent->segmentKey->ack == 1)
526 {
527 return true;
528 }
529 else
530 {
531 return false;
532 }
533 }
534
535
536 /*
537 * Check if a packet will increment the sequence number, thus needing an
538 * acknowledge
539 *
540 * Args:
541 * packet TCP Message
542 *
543 * Returns:
544 * true if the packet will need an acknowledge
545 * false otherwise
546 */
547 static bool needsAck(const Message* const packet)
548 {
549 if (packet->inE->event.tcpEvent->segmentKey->syn || packet->inE->event.tcpEvent->segmentKey->fin ||
550 packet->inE->event.tcpEvent->segmentKey->tot_len - packet->inE->event.tcpEvent->segmentKey->ihl * 4 -
551 packet->inE->event.tcpEvent->segmentKey->doff * 4 > 0)
552 {
553 return true;
554 }
555 else
556 {
557 return false;
558 }
559 }
560
561
562 /*
563 * Populate a connection key structure for the opposite direction of a
564 * connection
565 *
566 * Args:
567 * reversedConnectionKey the result, must be pre-allocated
568 * connectionKey the connection key to reverse
569 */
570 static void buildReversedConnectionKey(ConnectionKey* const
571 reversedConnectionKey, const ConnectionKey* const connectionKey)
572 {
573 reversedConnectionKey->saddr= connectionKey->daddr;
574 reversedConnectionKey->daddr= connectionKey->saddr;
575 reversedConnectionKey->source= connectionKey->dest;
576 reversedConnectionKey->dest= connectionKey->source;
577 }
578
579
580 /*
581 * Create and open files used to store message points to genereate
582 * graphs. Allocate and populate array to store file pointers.
583 *
584 * Args:
585 * syncState: container for synchronization data
586 */
587 static void openGraphDataFiles(SyncState* const syncState)
588 {
589 unsigned int i, j;
590 int retval;
591 char* cwd;
592 char name[29];
593 MatchingDataTCP* matchingData;
594
595 matchingData= (MatchingDataTCP*) syncState->matchingData;
596
597 cwd= changeToGraphDir(syncState->graphs);
598
599 matchingData->messagePoints= malloc(syncState->traceNb * sizeof(FILE**));
600 for (i= 0; i < syncState->traceNb; i++)
601 {
602 matchingData->messagePoints[i]= malloc(syncState->traceNb *
603 sizeof(FILE*));
604 for (j= 0; j < syncState->traceNb; j++)
605 {
606 if (i != j)
607 {
608 retval= snprintf(name, sizeof(name),
609 "matching_tcp-%03u_to_%03u.data", j, i);
610 if (retval > sizeof(name) - 1)
611 {
612 name[sizeof(name) - 1]= '\0';
613 }
614 if ((matchingData->messagePoints[i][j]= fopen(name, "w")) ==
615 NULL)
616 {
617 g_error(strerror(errno));
618 }
619 }
620 }
621 }
622
623 retval= chdir(cwd);
624 if (retval == -1)
625 {
626 g_error(strerror(errno));
627 }
628 free(cwd);
629 }
630
631
632 /*
633 * Write a message point to a file used to generate graphs
634 *
635 * Args:
636 * stream: FILE*, file pointer where to write the point
637 * message: message for which to write the point
638 */
639 static void writeMessagePoint(FILE* stream, const Message* const message)
640 {
641 LttCycleCount x, y;
642
643 if (message->inE->traceNum < message->outE->traceNum)
644 {
645 // CA is inE->traceNum
646 x= message->inE->time;
647 y= message->outE->time;
648 }
649 else
650 {
651 // CA is outE->traceNum
652 x= message->outE->time;
653 y= message->inE->time;
654 }
655
656 fprintf(stream, "%20llu %20llu\n", x, y);
657 }
658
659
660 /*
661 * Close files used to store convex hull points to genereate graphs.
662 * Deallocate array to store file pointers.
663 *
664 * Args:
665 * syncState: container for synchronization data
666 */
667 static void closeGraphDataFiles(SyncState* const syncState)
668 {
669 unsigned int i, j;
670 MatchingDataTCP* matchingData;
671 int retval;
672
673 matchingData= (MatchingDataTCP*) syncState->matchingData;
674
675 if (matchingData->messagePoints == NULL)
676 {
677 return;
678 }
679
680 for (i= 0; i < syncState->traceNb; i++)
681 {
682 for (j= 0; j < syncState->traceNb; j++)
683 {
684 if (i != j)
685 {
686 retval= fclose(matchingData->messagePoints[i][j]);
687 if (retval != 0)
688 {
689 g_error(strerror(errno));
690 }
691 }
692 }
693 free(matchingData->messagePoints[i]);
694 }
695 free(matchingData->messagePoints);
696
697 matchingData->messagePoints= NULL;
698 }
699
700
701 /*
702 * Write the matching-specific graph lines in the gnuplot script. Call the
703 * downstream module's graph function.
704 *
705 * Args:
706 * stream: stream where to write the data
707 * syncState: container for synchronization data
708 * i: first trace number
709 * j: second trace number, garanteed to be larger than i
710 */
711 static void writeMatchingGraphsPlotsTCP(FILE* stream, SyncState* const
712 syncState, const unsigned int i, const unsigned int j)
713 {
714 fprintf(stream,
715 "\t\"matching_tcp-%1$03d_to_%2$03d.data\" "
716 "title \"Sent messages\" with points linetype 4 "
717 "linecolor rgb \"#98fc66\" pointtype 9 pointsize 2, \\\n"
718 "\t\"matching_tcp-%2$03d_to_%1$03d.data\" "
719 "title \"Received messages\" with points linetype 4 "
720 "linecolor rgb \"#6699cc\" pointtype 11 pointsize 2, \\\n", i, j);
721
722 if (syncState->analysisModule->writeAnalysisGraphsPlots != NULL)
723 {
724 syncState->analysisModule->writeAnalysisGraphsPlots(stream, syncState,
725 i, j);
726 }
727 }
728
729
730 /*
731 * Write the matching-specific options in the gnuplot script (none). Call the
732 * downstream module's options function.
733 *
734 * Args:
735 * stream: stream where to write the data
736 * syncState: container for synchronization data
737 * i: first trace number
738 * j: second trace number, garanteed to be larger than i
739 */
740 static void writeMatchingGraphsOptionsTCP(FILE* stream, SyncState* const
741 syncState, const unsigned int i, const unsigned int j)
742 {
743 if (syncState->analysisModule->writeAnalysisGraphsOptions != NULL)
744 {
745 syncState->analysisModule->writeAnalysisGraphsOptions(stream,
746 syncState, i, j);
747 }
748 }
This page took 0.04352 seconds and 3 git commands to generate.