Add convex hull algorithm-based synchronization
[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.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, NetEvent* const event,
44 EventType eventType);
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);
51
52 // Functions specific to this module
53 static void registerMatchingTCP() __attribute__((constructor (101)));
54
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
58 oppositeFieldOffset);
59 static void partialDestroyMatchingTCP(SyncState* const syncState);
60
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);
65
66 static void openGraphDataFiles(SyncState* const syncState);
67 static void closeGraphDataFiles(SyncState* const syncState);
68 static void writeMessagePoint(FILE* stream, const Packet* const packet);
69
70
71 static MatchingModule matchingModuleTCP = {
72 .name= "TCP",
73 .initMatching= &initMatchingTCP,
74 .destroyMatching= &destroyMatchingTCP,
75 .matchEvent= &matchEventTCP,
76 .finalizeMatching= &finalizeMatchingTCP,
77 .printMatchingStats= &printMatchingStatsTCP,
78 .writeMatchingGraphsPlots= &writeMatchingGraphsPlotsTCP,
79 .writeMatchingGraphsOptions= &writeMatchingGraphsOptionsTCP,
80 };
81
82
83 /*
84 * Matching module registering function
85 */
86 static void registerMatchingTCP()
87 {
88 g_queue_push_tail(&matchingModules, &matchingModuleTCP);
89 }
90
91
92 /*
93 * Matching init function
94 *
95 * This function is called at the beginning of a synchronization run for a set
96 * of traces.
97 *
98 * Allocate the matching specific data structures
99 *
100 * Args:
101 * syncState container for synchronization data.
102 * This function allocates these matchingData members:
103 * unMatchedInE
104 * unMatchedOutE
105 * unAcked
106 * stats
107 */
108 static void initMatchingTCP(SyncState* const syncState)
109 {
110 MatchingDataTCP* matchingData;
111
112 matchingData= malloc(sizeof(MatchingDataTCP));
113 syncState->matchingData= matchingData;
114
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);
122
123 if (syncState->stats)
124 {
125 unsigned int i;
126
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++)
131 {
132 matchingData->stats->totMessageArray[i]=
133 calloc(syncState->traceNb, sizeof(unsigned int));
134 }
135 }
136 else
137 {
138 matchingData->stats= NULL;
139 }
140
141 if (syncState->graphs)
142 {
143 openGraphDataFiles(syncState);
144 }
145 else
146 {
147 matchingData->messagePoints= NULL;
148 }
149 }
150
151
152 /*
153 * Matching destroy function
154 *
155 * Free the matching specific data structures
156 *
157 * Args:
158 * syncState container for synchronization data.
159 * This function deallocates these matchingData members:
160 * stats
161 */
162 static void destroyMatchingTCP(SyncState* const syncState)
163 {
164 MatchingDataTCP* matchingData;
165
166 matchingData= (MatchingDataTCP*) syncState->matchingData;
167
168 if (matchingData == NULL)
169 {
170 return;
171 }
172
173 partialDestroyMatchingTCP(syncState);
174
175 if (syncState->stats)
176 {
177 unsigned int i;
178
179 for (i= 0; i < syncState->traceNb; i++)
180 {
181 free(matchingData->stats->totMessageArray[i]);
182 }
183 free(matchingData->stats->totMessageArray);
184 free(matchingData->stats);
185 }
186
187 free(syncState->matchingData);
188 syncState->matchingData= NULL;
189 }
190
191
192 /*
193 * Free some of the matching specific data structures
194 *
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.
197 *
198 * Args:
199 * syncState container for synchronization data.
200 * This function deallocates these matchingData members:
201 * unMatchedInE
202 * unMatchedOut
203 * unAcked
204 */
205 static void partialDestroyMatchingTCP(SyncState* const syncState)
206 {
207 MatchingDataTCP* matchingData;
208
209 matchingData= (MatchingDataTCP*) syncState->matchingData;
210
211 if (matchingData == NULL || matchingData->unMatchedInE == NULL)
212 {
213 return;
214 }
215
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);
220
221 if (syncState->graphs && matchingData->messagePoints)
222 {
223 closeGraphDataFiles(syncState);
224 }
225 }
226
227
228 /*
229 * Try to match one event from a trace with the corresponding event from
230 * another trace.
231 *
232 * Args:
233 * syncState container for synchronization data.
234 * event new event to match
235 * eventType type of event to match
236 */
237 static void matchEventTCP(SyncState* const syncState, NetEvent* const event, EventType eventType)
238 {
239 MatchingDataTCP* matchingData;
240
241 matchingData= (MatchingDataTCP*) syncState->matchingData;
242
243 if (eventType == IN)
244 {
245 matchEvents(syncState, event, matchingData->unMatchedInE,
246 matchingData->unMatchedOutE, offsetof(Packet, inE),
247 offsetof(Packet, outE));
248 }
249 else
250 {
251 matchEvents(syncState, event, matchingData->unMatchedOutE,
252 matchingData->unMatchedInE, offsetof(Packet, outE),
253 offsetof(Packet, inE));
254 }
255 }
256
257
258 /*
259 * Call the partial matching destroyer and Obtain the factors from downstream
260 *
261 * Args:
262 * syncState container for synchronization data.
263 *
264 * Returns:
265 * Factors[traceNb] synchronization factors for each trace
266 */
267 static GArray* finalizeMatchingTCP(SyncState* const syncState)
268 {
269 partialDestroyMatchingTCP(syncState);
270
271 return syncState->analysisModule->finalizeAnalysis(syncState);
272 }
273
274
275 /*
276 * Print statistics related to matching and downstream modules. Must be
277 * called after finalizeMatching.
278 *
279 * Args:
280 * syncState container for synchronization data.
281 */
282 static void printMatchingStatsTCP(SyncState* const syncState)
283 {
284 unsigned int i, j;
285 MatchingDataTCP* matchingData;
286
287 if (!syncState->stats)
288 {
289 return;
290 }
291
292 matchingData= (MatchingDataTCP*) syncState->matchingData;
293
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);
297
298 printf("\tMessage traffic:\n");
299
300 for (i= 0; i < syncState->traceNb; i++)
301 {
302 for (j= i + 1; j < syncState->traceNb; j++)
303 {
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]);
307 }
308 }
309
310 if (syncState->analysisModule->analyzeExchange != NULL)
311 {
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);
318 }
319
320 if (syncState->analysisModule->printAnalysisStats != NULL)
321 {
322 syncState->analysisModule->printAnalysisStats(syncState);
323 }
324 }
325
326
327 /*
328 * Implementation of a packet matching algorithm for TCP
329 *
330 * Args:
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
335 * netEvent
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
340 */
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)
344 {
345 NetEvent* companionEvent;
346 Packet* packet;
347 MatchingDataTCP* matchingData;
348 GQueue* conUnAcked;
349
350 matchingData= (MatchingDataTCP*) syncState->matchingData;
351
352 companionEvent= g_hash_table_lookup(unMatchedOppositeList, event->packetKey);
353 if (companionEvent != NULL)
354 {
355 g_debug("Found matching companion event, ");
356
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;
365 packet->acks= NULL;
366
367 if (syncState->stats)
368 {
369 matchingData->stats->totPacket++;
370 matchingData->stats->totMessageArray[packet->inE->traceNum][packet->outE->traceNum]++;
371 }
372
373 // Discard loopback traffic
374 if (packet->inE->traceNum == packet->outE->traceNum)
375 {
376 destroyPacket(packet);
377 return;
378 }
379
380 if (syncState->graphs)
381 {
382 writeMessagePoint(matchingData->messagePoints[packet->inE->traceNum][packet->outE->traceNum],
383 packet);
384 }
385
386 if (syncState->analysisModule->analyzePacket != NULL)
387 {
388 syncState->analysisModule->analyzePacket(syncState, packet);
389 }
390
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)
394 {
395 destroyPacket(packet);
396 return;
397 }
398
399 // If this packet acknowleges some data ...
400 if (isAck(packet))
401 {
402 ConnectionKey oppositeConnectionKey;
403
404 buildReversedConnectionKey(&oppositeConnectionKey,
405 &event->packetKey->connectionKey);
406 conUnAcked= g_hash_table_lookup(matchingData->unAcked,
407 &oppositeConnectionKey);
408 if (conUnAcked != NULL)
409 {
410 Packet* ackedPacket;
411 GList* result;
412
413 result= g_queue_find_custom(conUnAcked, packet, &gcfPacketAckCompare);
414
415 while (result != NULL)
416 {
417 // Remove the acknowledged packet from the unAcked list
418 // and keep it for later offset calculations
419 g_debug("Found matching unAcked packet, ");
420
421 ackedPacket= (Packet*) result->data;
422 g_queue_delete_link(conUnAcked, result);
423
424 if (syncState->stats)
425 {
426 matchingData->stats->totExchangeEffective++;
427 }
428
429 if (packet->acks == NULL)
430 {
431 packet->acks= g_queue_new();
432 }
433
434 g_queue_push_tail(packet->acks, ackedPacket);
435
436 result= g_queue_find_custom(conUnAcked, packet,
437 &gcfPacketAckCompare);
438 }
439
440 // It might be possible to do an offset calculation
441 if (packet->acks != NULL)
442 {
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)
448 {
449 printPacket(ackedPacket);
450 printPacket(packet);
451 g_error("Disorganized exchange encountered during "
452 "synchronization");
453 }
454 else
455 {
456 if (syncState->stats)
457 {
458 matchingData->stats->totExchangeSync++;
459 }
460
461 syncState->analysisModule->analyzeExchange(syncState,
462 packet);
463 }
464 }
465 }
466 }
467
468 if (needsAck(packet))
469 {
470 if (syncState->stats)
471 {
472 matchingData->stats->totPacketNeedAck++;
473 }
474
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)
480 {
481 ConnectionKey* connectionKey;
482
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());
488 }
489 g_queue_push_tail(conUnAcked, packet);
490 }
491 else
492 {
493 destroyPacket(packet);
494 }
495 }
496 else
497 {
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);
502 }
503 }
504
505
506 /*
507 * Check if a packet is an acknowledge
508 *
509 * Returns:
510 * true if it is,
511 * false otherwise
512 */
513 static bool isAck(const Packet* const packet)
514 {
515 if (packet->inE->packetKey->ack == 1)
516 {
517 return true;
518 }
519 else
520 {
521 return false;
522 }
523 }
524
525
526 /*
527 * Check if a packet will increment the sequence number, thus needing an
528 * acknowledge
529 *
530 * Returns:
531 * true if the packet will need an acknowledge
532 * false otherwise
533 */
534 static bool needsAck(const Packet* const packet)
535 {
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)
539 {
540 return true;
541 }
542 else
543 {
544 return false;
545 }
546 }
547
548
549 /*
550 * Populate a connection key structure for the opposite direction of a
551 * connection
552 *
553 * Args:
554 * reversedConnectionKey the result, must be pre-allocated
555 * connectionKey the connection key to reverse
556 */
557 static void buildReversedConnectionKey(ConnectionKey* const
558 reversedConnectionKey, const ConnectionKey* const connectionKey)
559 {
560 reversedConnectionKey->saddr= connectionKey->daddr;
561 reversedConnectionKey->daddr= connectionKey->saddr;
562 reversedConnectionKey->source= connectionKey->dest;
563 reversedConnectionKey->dest= connectionKey->source;
564 }
565
566
567 /*
568 * Create and open files used to store message points to genereate
569 * graphs. Allocate and populate array to store file pointers.
570 *
571 * Args:
572 * syncState: container for synchronization data
573 */
574 static void openGraphDataFiles(SyncState* const syncState)
575 {
576 unsigned int i, j;
577 int retval;
578 char* cwd;
579 char name[29];
580 MatchingDataTCP* matchingData;
581
582 matchingData= (MatchingDataTCP*) syncState->matchingData;
583
584 cwd= changeToGraphDir(syncState->graphs);
585
586 matchingData->messagePoints= malloc(syncState->traceNb * sizeof(FILE**));
587 for (i= 0; i < syncState->traceNb; i++)
588 {
589 matchingData->messagePoints[i]= malloc(syncState->traceNb *
590 sizeof(FILE*));
591 for (j= 0; j < syncState->traceNb; j++)
592 {
593 if (i != j)
594 {
595 retval= snprintf(name, sizeof(name),
596 "matching_tcp-%03u_to_%03u.data", j, i);
597 if (retval > sizeof(name) - 1)
598 {
599 name[sizeof(name) - 1]= '\0';
600 }
601 if ((matchingData->messagePoints[i][j]= fopen(name, "w")) ==
602 NULL)
603 {
604 g_error(strerror(errno));
605 }
606 }
607 }
608 }
609
610 retval= chdir(cwd);
611 if (retval == -1)
612 {
613 g_error(strerror(errno));
614 }
615 free(cwd);
616 }
617
618
619 /*
620 * Write a message point to a file used to generate graphs
621 *
622 * Args:
623 * stream: FILE*, file pointer where to write the point
624 * packet: message for which to write the point
625 */
626 static void writeMessagePoint(FILE* stream, const Packet* const packet)
627 {
628 LttCycleCount x, y;
629
630 if (packet->inE->traceNum < packet->outE->traceNum)
631 {
632 // CA is inE->traceNum
633 x= packet->inE->tsc;
634 y= packet->outE->tsc;
635 }
636 else
637 {
638 // CA is outE->traceNum
639 x= packet->outE->tsc;
640 y= packet->inE->tsc;
641 }
642
643 fprintf(stream, "%20llu %20llu\n", x, y);
644 }
645
646
647 /*
648 * Close files used to store convex hull points to genereate graphs.
649 * Deallocate array to store file pointers.
650 *
651 * Args:
652 * syncState: container for synchronization data
653 */
654 static void closeGraphDataFiles(SyncState* const syncState)
655 {
656 unsigned int i, j;
657 MatchingDataTCP* matchingData;
658 int retval;
659
660 matchingData= (MatchingDataTCP*) syncState->matchingData;
661
662 if (matchingData->messagePoints == NULL)
663 {
664 return;
665 }
666
667 for (i= 0; i < syncState->traceNb; i++)
668 {
669 for (j= 0; j < syncState->traceNb; j++)
670 {
671 if (i != j)
672 {
673 retval= fclose(matchingData->messagePoints[i][j]);
674 if (retval != 0)
675 {
676 g_error(strerror(errno));
677 }
678 }
679 }
680 free(matchingData->messagePoints[i]);
681 }
682 free(matchingData->messagePoints);
683
684 matchingData->messagePoints= NULL;
685 }
686
687
688 /*
689 * Write the matching-specific graph lines in the gnuplot script. Call the
690 * downstream module's graph function.
691 *
692 * Args:
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
697 */
698 static void writeMatchingGraphsPlotsTCP(FILE* stream, SyncState* const
699 syncState, const unsigned int i, const unsigned int j)
700 {
701 fprintf(stream,
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);
708
709 if (syncState->analysisModule->writeAnalysisGraphsPlots != NULL)
710 {
711 syncState->analysisModule->writeAnalysisGraphsPlots(stream, syncState,
712 i, j);
713 }
714 }
715
716
717 /*
718 * Write the matching-specific options in the gnuplot script (none). Call the
719 * downstream module's options function.
720 *
721 * Args:
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
726 */
727 static void writeMatchingGraphsOptionsTCP(FILE* stream, SyncState* const
728 syncState, const unsigned int i, const unsigned int j)
729 {
730 if (syncState->analysisModule->writeAnalysisGraphsOptions != NULL)
731 {
732 syncState->analysisModule->writeAnalysisGraphsOptions(stream,
733 syncState, i, j);
734 }
735 }
This page took 0.04482 seconds and 4 git commands to generate.