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