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 <stdlib.h>
  24 #include <string.h>
  25
  26 #include "event_analysis.h"
  27 #include "sync_chain.h"
  28
  29 #include "event_matching_tcp.h"
  30
  31
  32 #ifndef g_info
  33 #define g_info(format...) g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, format)
  34 #endif
  35
  36
  37 // Functions common to all matching modules
  38 static void initMatchingTCP(SyncState* const syncState);
  39 static void destroyMatchingTCP(SyncState* const syncState);
  40
  41 static void matchEventTCP(SyncState* const syncState, NetEvent* const event,
  42         EventType eventType);
  43 static GArray* finalizeMatchingTCP(SyncState* const syncState);
  44 static void printMatchingStatsTCP(SyncState* const syncState);
  45
  46 // Functions specific to this module
  47 static void registerMatchingTCP() __attribute__((constructor (101)));
  48
  49 static void matchEvents(SyncState* const syncState, NetEvent* const event,
  50         GHashTable* const unMatchedList, GHashTable* const
  51         unMatchedOppositeList, const size_t fieldOffset, const size_t
  52         oppositeFieldOffset);
  53 static void partialDestroyMatchingTCP(SyncState* const syncState);
  54
  55 static bool isAck(const Packet* const packet);
  56 static bool needsAck(const Packet* const packet);
  57 static void buildReversedConnectionKey(ConnectionKey* const
  58         reversedConnectionKey, const ConnectionKey* const connectionKey);
  59
  60
  61 static MatchingModule matchingModuleTCP = {
  62         .name= "TCP",
  63         .initMatching= &initMatchingTCP,
  64         .destroyMatching= &destroyMatchingTCP,
  65         .matchEvent= &matchEventTCP,
  66         .finalizeMatching= &finalizeMatchingTCP,
  67         .printMatchingStats= &printMatchingStatsTCP,
  68 };
  69
  70
  71 /*
  72  * Matching module registering function
  73  */
  74 static void registerMatchingTCP()
  75 {
  76         g_queue_push_tail(&matchingModules, &matchingModuleTCP);
  77 }
  78
  79
  80 /*
  81  * Matching init function
  82  *
  83  * This function is called at the beginning of a synchronization run for a set
  84  * of traces.
  85  *
  86  * Allocate the matching specific data structures
  87  *
  88  * Args:
  89  *   syncState     container for synchronization data.
  90  *                 This function allocates these matchingData members:
  91  *                 unMatchedInE
  92  *                 unMatchedOutE
  93  *                 unAcked
  94  *                 stats
  95  */
  96 static void initMatchingTCP(SyncState* const syncState)
  97 {
  98         MatchingDataTCP* matchingData;
  99
 100         matchingData= malloc(sizeof(MatchingDataTCP));
 101         syncState->matchingData= matchingData;
 102
 103         matchingData->unMatchedInE= g_hash_table_new_full(&ghfPacketKeyHash,
 104                 &gefPacketKeyEqual, NULL, &gdnDestroyNetEvent);
 105         matchingData->unMatchedOutE= g_hash_table_new_full(&ghfPacketKeyHash,
 106                 &gefPacketKeyEqual, NULL, &gdnDestroyNetEvent);
 107         matchingData->unAcked= g_hash_table_new_full(&ghfConnectionKeyHash,
 108                 &gefConnectionKeyEqual, &gdnConnectionKeyDestroy,
 109                 &gdnPacketListDestroy);
 110
 111         if (syncState->stats)
 112         {
 113                 matchingData->stats= calloc(1, sizeof(MatchingStatsTCP));
 114         }
 115         else
 116         {
 117                 matchingData->stats= NULL;
 118         }
 119 }
 120
 121
 122 /*
 123  * Matching destroy function
 124  *
 125  * Free the matching specific data structures
 126  *
 127  * Args:
 128  *   syncState     container for synchronization data.
 129  *                 This function deallocates these matchingData members:
 130  *                 stats
 131  */
 132 static void destroyMatchingTCP(SyncState* const syncState)
 133 {
 134         MatchingDataTCP* matchingData;
 135
 136         matchingData= (MatchingDataTCP*) syncState->matchingData;
 137
 138         if (matchingData == NULL)
 139         {
 140                 return;
 141         }
 142
 143         partialDestroyMatchingTCP(syncState);
 144
 145         if (syncState->stats)
 146         {
 147                 free(matchingData->stats);
 148         }
 149
 150         free(syncState->matchingData);
 151         syncState->matchingData= NULL;
 152 }
 153
 154
 155 /*
 156  * Free some of the matching specific data structures
 157  *
 158  * This function can be called right after the events have been processed to
 159  * free some data structures that are not needed for finalization.
 160  *
 161  * Args:
 162  *   syncState     container for synchronization data.
 163  *                 This function deallocates these matchingData members:
 164  *                 unMatchedInE
 165  *                 unMatchedOut
 166  *                 unAcked
 167  */
 168 static void partialDestroyMatchingTCP(SyncState* const syncState)
 169 {
 170         MatchingDataTCP* matchingData;
 171
 172         matchingData= (MatchingDataTCP*) syncState->matchingData;
 173
 174         if (matchingData == NULL || matchingData->unMatchedInE == NULL)
 175         {
 176                 return;
 177         }
 178
 179         g_debug("Cleaning up unMatchedInE list\n");
 180         g_hash_table_destroy(matchingData->unMatchedInE);
 181         matchingData->unMatchedInE= NULL;
 182         g_debug("Cleaning up unMatchedOutE list\n");
 183         g_hash_table_destroy(matchingData->unMatchedOutE);
 184         g_debug("Cleaning up unAcked list\n");
 185         g_hash_table_destroy(matchingData->unAcked);
 186 }
 187
 188
 189 /*
 190  * Try to match one event from a trace with the corresponding event from
 191  * another trace.
 192  *
 193  * Args:
 194  *   syncState     container for synchronization data.
 195  *   event         new event to match
 196  *   eventType     type of event to match
 197  */
 198 static void matchEventTCP(SyncState* const syncState, NetEvent* const event, EventType eventType)
 199 {
 200         MatchingDataTCP* matchingData;
 201
 202         matchingData= (MatchingDataTCP*) syncState->matchingData;
 203
 204         if (eventType == IN)
 205         {
 206                 matchEvents(syncState, event, matchingData->unMatchedInE,
 207                         matchingData->unMatchedOutE, offsetof(Packet, inE),
 208                         offsetof(Packet, outE));
 209         }
 210         else
 211         {
 212                 matchEvents(syncState, event, matchingData->unMatchedOutE,
 213                         matchingData->unMatchedInE, offsetof(Packet, outE),
 214                         offsetof(Packet, inE));
 215         }
 216 }
 217
 218
 219 /*
 220  * Call the partial matching destroyer and Obtain the factors from downstream
 221  *
 222  * Args:
 223  *   syncState     container for synchronization data.
 224  *
 225  * Returns:
 226  *   Factors[traceNb] synchronization factors for each trace
 227  */
 228 static GArray* finalizeMatchingTCP(SyncState* const syncState)
 229 {
 230         partialDestroyMatchingTCP(syncState);
 231
 232         return syncState->analysisModule->finalizeAnalysis(syncState);
 233 }
 234
 235
 236 /*
 237  * Print statistics related to matching and downstream modules. Must be
 238  * called after finalizeMatching.
 239  *
 240  * Args:
 241  *   syncState     container for synchronization data.
 242  */
 243 static void printMatchingStatsTCP(SyncState* const syncState)
 244 {
 245         MatchingDataTCP* matchingData;
 246
 247         if (!syncState->stats)
 248         {
 249                 return;
 250         }
 251
 252         matchingData= (MatchingDataTCP*) syncState->matchingData;
 253
 254         printf("TCP matching stats:\n");
 255         printf("\ttotal input and output events matched together to form a packet: %d\n",
 256                 matchingData->stats->totPacket);
 257         printf("\ttotal packets identified needing an acknowledge: %d\n",
 258                 matchingData->stats->totPacketNeedAck);
 259         printf("\ttotal exchanges (four events matched together): %d\n",
 260                 matchingData->stats->totExchangeEffective);
 261         printf("\ttotal synchronization exchanges: %d\n",
 262                 matchingData->stats->totExchangeSync);
 263
 264         if (syncState->analysisModule->printAnalysisStats != NULL)
 265         {
 266                 syncState->analysisModule->printAnalysisStats(syncState);
 267         }
 268 }
 269
 270
 271 /*
 272  * Implementation of a packet matching algorithm for TCP
 273  *
 274  * Args:
 275  *   netEvent:     new event to match
 276  *   unMatchedList: list of unmatched events of the same type (send or
 277  *                 receive) as netEvent
 278  *   unMatchedOppositeList: list of unmatched events of the opposite type of
 279  *                 netEvent
 280  *   fieldOffset:  offset of the NetEvent field in the Packet struct for the
 281  *                 field of the type of netEvent
 282  *   oppositeFieldOffset: offset of the NetEvent field in the Packet struct
 283  *                 for the field of the opposite type of netEvent
 284  */
 285 static void matchEvents(SyncState* const syncState, NetEvent* const event,
 286         GHashTable* const unMatchedList, GHashTable* const unMatchedOppositeList,
 287         const size_t fieldOffset, const size_t oppositeFieldOffset)
 288 {
 289         NetEvent* companionEvent;
 290         Packet* packet;
 291         MatchingDataTCP* matchingData;
 292         GQueue* conUnAcked;
 293
 294         matchingData= (MatchingDataTCP*) syncState->matchingData;
 295
 296         companionEvent= g_hash_table_lookup(unMatchedOppositeList, event->packetKey);
 297         if (companionEvent != NULL)
 298         {
 299                 g_debug("Found matching companion event, ");
 300
 301                 if (syncState->stats)
 302                 {
 303                         matchingData->stats->totPacket++;
 304                 }
 305
 306                 // If it's there, remove it and create a Packet
 307                 g_hash_table_steal(unMatchedOppositeList, event->packetKey);
 308                 packet= malloc(sizeof(Packet));
 309                 *((NetEvent**) ((void*) packet + fieldOffset))= event;
 310                 *((NetEvent**) ((void*) packet + oppositeFieldOffset))= companionEvent;
 311                 // Both events can now share the same packetKey
 312                 free(packet->outE->packetKey);
 313                 packet->outE->packetKey= packet->inE->packetKey;
 314                 packet->acks= NULL;
 315
 316                 // Discard loopback traffic
 317                 if (packet->inE->traceNum == packet->outE->traceNum)
 318                 {
 319                         destroyPacket(packet);
 320                         return;
 321                 }
 322
 323                 if (syncState->analysisModule->analyzePacket)
 324                 {
 325                         syncState->analysisModule->analyzePacket(syncState, packet);
 326                 }
 327
 328                 // We can skip the rest of the algorithm if the analysis module is not
 329                 // interested in exchanges
 330                 if (!syncState->analysisModule->analyzeExchange)
 331                 {
 332                         destroyPacket(packet);
 333                         return;
 334                 }
 335
 336                 // If this packet acknowleges some data ...
 337                 if (isAck(packet))
 338                 {
 339                         ConnectionKey oppositeConnectionKey;
 340
 341                         buildReversedConnectionKey(&oppositeConnectionKey,
 342                                 &event->packetKey->connectionKey);
 343                         conUnAcked= g_hash_table_lookup(matchingData->unAcked,
 344                                 &oppositeConnectionKey);
 345                         if (conUnAcked != NULL)
 346                         {
 347                                 Packet* ackedPacket;
 348                                 GList* result;
 349
 350                                 result= g_queue_find_custom(conUnAcked, packet, &gcfPacketAckCompare);
 351
 352                                 while (result != NULL)
 353                                 {
 354                                         // Remove the acknowledged packet from the unAcked list
 355                                         // and keep it for later offset calculations
 356                                         g_debug("Found matching unAcked packet, ");
 357
 358                                         ackedPacket= (Packet*) result->data;
 359                                         g_queue_delete_link(conUnAcked, result);
 360
 361                                         if (syncState->stats)
 362                                         {
 363                                                 matchingData->stats->totExchangeEffective++;
 364                                         }
 365
 366                                         if (packet->acks == NULL)
 367                                         {
 368                                                 packet->acks= g_queue_new();
 369                                         }
 370
 371                                         g_queue_push_tail(packet->acks, ackedPacket);
 372
 373                                         result= g_queue_find_custom(conUnAcked, packet,
 374                                                 &gcfPacketAckCompare);
 375                                 }
 376
 377                                 // It might be possible to do an offset calculation
 378                                 if (packet->acks != NULL)
 379                                 {
 380                                         ackedPacket= g_queue_peek_tail(packet->acks);
 381                                         if (ackedPacket->outE->traceNum != packet->inE->traceNum
 382                                                 || ackedPacket->inE->traceNum !=
 383                                                 packet->outE->traceNum || packet->inE->traceNum ==
 384                                                 packet->outE->traceNum)
 385                                         {
 386                                                 printPacket(ackedPacket);
 387                                                 printPacket(packet);
 388                                                 g_error("Disorganized exchange encountered during "
 389                                                         "synchronization");
 390                                         }
 391                                         else
 392                                         {
 393                                                 if (syncState->stats)
 394                                                 {
 395                                                         matchingData->stats->totExchangeSync++;
 396                                                 }
 397
 398                                                 syncState->analysisModule->analyzeExchange(syncState,
 399                                                         packet);
 400                                         }
 401                                 }
 402                         }
 403                 }
 404
 405                 if (needsAck(packet))
 406                 {
 407                         if (syncState->stats)
 408                         {
 409                                 matchingData->stats->totPacketNeedAck++;
 410                         }
 411
 412                         // If this packet will generate an ack, add it to the unAcked list
 413                         g_debug("Adding to unAcked, ");
 414                         conUnAcked= g_hash_table_lookup(matchingData->unAcked,
 415                                 &event->packetKey->connectionKey);
 416                         if (conUnAcked == NULL)
 417                         {
 418                                 ConnectionKey* connectionKey;
 419
 420                                 connectionKey= malloc(sizeof(ConnectionKey));
 421                                 memcpy(connectionKey, &event->packetKey->connectionKey,
 422                                         sizeof(ConnectionKey));
 423                                 g_hash_table_insert(matchingData->unAcked, connectionKey,
 424                                         conUnAcked= g_queue_new());
 425                         }
 426                         g_queue_push_tail(conUnAcked, packet);
 427                 }
 428                 else
 429                 {
 430                         destroyPacket(packet);
 431                 }
 432         }
 433         else
 434         {
 435                 // If there's no corresponding event, add the event to the unmatched
 436                 // list for this type of event
 437                 g_debug("Adding to unmatched event list, ");
 438                 g_hash_table_replace(unMatchedList, event->packetKey, event);
 439         }
 440 }
 441
 442
 443 /*
 444  * Check if a packet is an acknowledge
 445  *
 446  * Returns:
 447  *   true if it is,
 448  *   false otherwise
 449  */
 450 static bool isAck(const Packet* const packet)
 451 {
 452         if (packet->inE->packetKey->ack == 1)
 453         {
 454                 return true;
 455         }
 456         else
 457         {
 458                 return false;
 459         }
 460 }
 461
 462
 463 /*
 464  * Check if a packet will increment the sequence number, thus needing an
 465  * acknowledge
 466  *
 467  * Returns:
 468  *   true if the packet will need an acknowledge
 469  *   false otherwise
 470  */
 471 static bool needsAck(const Packet* const packet)
 472 {
 473         if (packet->inE->packetKey->syn || packet->inE->packetKey->fin ||
 474                 packet->inE->packetKey->tot_len - packet->inE->packetKey->ihl * 4 -
 475                 packet->inE->packetKey->doff * 4 > 0)
 476         {
 477                 return true;
 478         }
 479         else
 480         {
 481                 return false;
 482         }
 483 }
 484
 485
 486 /*
 487  * Populate a connection key structure for the opposite direction of a
 488  * connection
 489  *
 490  * Args:
 491  *   reversedConnectionKey the result, must be pre-allocated
 492  *   connectionKey the connection key to reverse
 493  */
 494 static void buildReversedConnectionKey(ConnectionKey* const
 495         reversedConnectionKey, const ConnectionKey* const connectionKey)
 496 {
 497         reversedConnectionKey->saddr= connectionKey->daddr;
 498         reversedConnectionKey->daddr= connectionKey->saddr;
 499         reversedConnectionKey->source= connectionKey->dest;
 500         reversedConnectionKey->dest= connectionKey->source;
 501 }