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