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