lttv/lttv/sync/event_analysis_eval.c

   1 /* This file is part of the Linux Trace Toolkit viewer
   2  * Copyright (C) 2009, 2010 Benjamin Poirier <benjamin.poirier@polymtl.ca>
   3  *
   4  * This program is free software: you can redistribute it and/or modify it
   5  * under the terms of the GNU Lesser General Public License as published by
   6  * the Free Software Foundation, either version 2.1 of the License, or (at
   7  * your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  12  * License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public License
  15  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #define _GNU_SOURCE
  19 #define _ISOC99_SOURCE
  20
  21 #ifdef HAVE_CONFIG_H
  22 #include <config.h>
  23 #endif
  24
  25 #include <arpa/inet.h>
  26 #include <errno.h>
  27 #include <math.h>
  28 #include <netinet/in.h>
  29 #include <stddef.h>
  30 #include <stdlib.h>
  31 #include <stdio.h>
  32 #include <string.h>
  33 #include <sys/socket.h>
  34 #include <unistd.h>
  35
  36 #include "lookup3.h"
  37 #include "sync_chain.h"
  38
  39 #include "event_analysis_eval.h"
  40
  41
  42 struct WriteHistogramInfo
  43 {
  44         GHashTable* rttInfo;
  45         FILE* graphsStream;
  46 };
  47
  48 // Functions common to all analysis modules
  49 static void initAnalysisEval(SyncState* const syncState);
  50 static void destroyAnalysisEval(SyncState* const syncState);
  51
  52 static void analyzeMessageEval(SyncState* const syncState, Message* const
  53         message);
  54 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
  55         exchange);
  56 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
  57         broadcast);
  58 static AllFactors* finalizeAnalysisEval(SyncState* const syncState);
  59 static void printAnalysisStatsEval(SyncState* const syncState);
  60
  61 // Functions specific to this module
  62 static guint ghfRttKeyHash(gconstpointer key);
  63 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b);
  64 static void gdnDestroyRttKey(gpointer data);
  65 static void gdnDestroyDouble(gpointer data);
  66 static void readRttInfo(GHashTable* rttInfo, FILE* rttFile);
  67 static void positionStream(FILE* stream);
  68
  69 static void gfSum(gpointer data, gpointer userData);
  70 static void gfSumSquares(gpointer data, gpointer userData);
  71 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
  72         user_data);
  73
  74 static void hitBin(struct Bins* const bins, const double value);
  75 static unsigned int binNum(const double value) __attribute__((pure));
  76 static double binStart(const unsigned int binNum) __attribute__((pure));
  77 static double binEnd(const unsigned int binNum) __attribute__((pure));
  78 static uint32_t normalTotal(struct Bins* const bins) __attribute__((const));
  79
  80 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
  81         graphsDir, const struct RttKey* const rttKey);
  82 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
  83         histogram);
  84 static void gdnDestroyAnalysisHistogramEval(gpointer data);
  85 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer
  86         user_data);
  87 static void dumpBinToFile(const struct Bins* const bins, FILE* const file);
  88 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
  89         double* minRtt, AnalysisHistogramEval* const histogram);
  90
  91 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
  92         e2);
  93
  94
  95 // initialized in registerAnalysisEval()
  96 double binBase;
  97
  98 static AnalysisModule analysisModuleEval= {
  99         .name= "eval",
 100         .initAnalysis= &initAnalysisEval,
 101         .destroyAnalysis= &destroyAnalysisEval,
 102         .analyzeMessage= &analyzeMessageEval,
 103         .analyzeExchange= &analyzeExchangeEval,
 104         .analyzeBroadcast= &analyzeBroadcastEval,
 105         .finalizeAnalysis= &finalizeAnalysisEval,
 106         .printAnalysisStats= &printAnalysisStatsEval,
 107         .graphFunctions= {}
 108 };
 109
 110 static ModuleOption optionEvalRttFile= {
 111         .longName= "eval-rtt-file",
 112         .hasArg= REQUIRED_ARG,
 113         .optionHelp= "specify the file containing RTT information",
 114         .argHelp= "FILE",
 115 };
 116
 117
 118 /*
 119  * Analysis module registering function
 120  */
 121 void registerAnalysisEval()
 122 {
 123         binBase= exp10(6. / (BIN_NB - 3));
 124
 125         g_queue_push_tail(&analysisModules, &analysisModuleEval);
 126         g_queue_push_tail(&moduleOptions, &optionEvalRttFile);
 127 }
 128
 129
 130 /*
 131  * Analysis init function
 132  *
 133  * This function is called at the beginning of a synchronization run for a set
 134  * of traces.
 135  *
 136  * Args:
 137  *   syncState     container for synchronization data.
 138  */
 139 static void initAnalysisEval(SyncState* const syncState)
 140 {
 141         AnalysisDataEval* analysisData;
 142         unsigned int i, j;
 143
 144         analysisData= malloc(sizeof(AnalysisDataEval));
 145         syncState->analysisData= analysisData;
 146
 147         analysisData->rttInfo= g_hash_table_new_full(&ghfRttKeyHash,
 148                 &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble);
 149         if (optionEvalRttFile.arg)
 150         {
 151                 FILE* rttStream;
 152                 int retval;
 153
 154                 rttStream= fopen(optionEvalRttFile.arg, "r");
 155                 if (rttStream == NULL)
 156                 {
 157                         g_error(strerror(errno));
 158                 }
 159
 160                 readRttInfo(analysisData->rttInfo, rttStream);
 161
 162                 retval= fclose(rttStream);
 163                 if (retval == EOF)
 164                 {
 165                         g_error(strerror(errno));
 166                 }
 167         }
 168
 169         if (syncState->stats)
 170         {
 171                 analysisData->stats= calloc(1, sizeof(AnalysisStatsEval));
 172                 analysisData->stats->broadcastRangeMin= INFINITY;
 173                 analysisData->stats->broadcastRangeMax= -INFINITY;
 174
 175                 analysisData->stats->messageStats= malloc(syncState->traceNb *
 176                         sizeof(MessageStats*));
 177                 for (i= 0; i < syncState->traceNb; i++)
 178                 {
 179                         analysisData->stats->messageStats[i]= calloc(syncState->traceNb,
 180                                 sizeof(MessageStats));
 181                 }
 182
 183                 analysisData->stats->exchangeRtt=
 184                         g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual,
 185                                 &gdnDestroyRttKey, &gdnDestroyDouble);
 186         }
 187
 188         if (syncState->graphsStream)
 189         {
 190                 AnalysisGraphsEval* graphs= malloc(sizeof(AnalysisGraphsEval));
 191
 192                 analysisData->graphs= graphs;
 193
 194                 graphs->histograms= g_hash_table_new_full(&ghfRttKeyHash,
 195                         &gefRttKeyEqual, &gdnDestroyRttKey,
 196                         &gdnDestroyAnalysisHistogramEval);
 197
 198                 graphs->bounds= malloc(syncState->traceNb * sizeof(Bounds*));
 199                 for (i= 0; i < syncState->traceNb; i++)
 200                 {
 201                         graphs->bounds[i]= malloc(i * sizeof(Bounds));
 202                         for (j= 0; j < i; j++)
 203                         {
 204                                 graphs->bounds[i][j].min= UINT64_MAX;
 205                                 graphs->bounds[i][j].max= 0;
 206                         }
 207                 }
 208         }
 209 }
 210
 211
 212 /*
 213  * Create and open files used to store histogram points to generate graphs.
 214  * Create data structures to store histogram points during analysis.
 215  *
 216  * Args:
 217  *   graphsDir:    folder where to write files
 218  *   rttKey:       host pair, make sure saddr < daddr
 219  */
 220 static AnalysisHistogramEval* constructAnalysisHistogramEval(const char* const
 221         graphsDir, const struct RttKey* const rttKey)
 222 {
 223         int retval;
 224         unsigned int i;
 225         char* cwd;
 226         char name[60], saddr[16], daddr[16];
 227         AnalysisHistogramEval* histogram= calloc(1, sizeof(*histogram));
 228         const struct {
 229                 size_t pointsOffset;
 230                 const char* fileName;
 231                 const char* host1, *host2;
 232         } loopValues[]= {
 233                 {offsetof(AnalysisHistogramEval, ttSendPoints),
 234                         "analysis_eval_tt-%s_to_%s.data", saddr, daddr},
 235                 {offsetof(AnalysisHistogramEval, ttRecvPoints),
 236                         "analysis_eval_tt-%s_to_%s.data", daddr, saddr},
 237                 {offsetof(AnalysisHistogramEval, hrttPoints),
 238                         "analysis_eval_hrtt-%s_and_%s.data", saddr, daddr},
 239         };
 240
 241         histogram->ttSendBins.min= BIN_NB - 1;
 242         histogram->ttRecvBins.min= BIN_NB - 1;
 243         histogram->hrttBins.min= BIN_NB - 1;
 244
 245         convertIP(saddr, rttKey->saddr);
 246         convertIP(daddr, rttKey->daddr);
 247
 248         cwd= changeToGraphsDir(graphsDir);
 249
 250         for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 251         {
 252                 retval= snprintf(name, sizeof(name), loopValues[i].fileName,
 253                         loopValues[i].host1, loopValues[i].host2);
 254                 if (retval > sizeof(name) - 1)
 255                 {
 256                         name[sizeof(name) - 1]= '\0';
 257                 }
 258                 if ((*(FILE**)((void*) histogram + loopValues[i].pointsOffset)=
 259                                 fopen(name, "w")) == NULL)
 260                 {
 261                         g_error(strerror(errno));
 262                 }
 263         }
 264
 265         retval= chdir(cwd);
 266         if (retval == -1)
 267         {
 268                 g_error(strerror(errno));
 269         }
 270         free(cwd);
 271
 272         return histogram;
 273 }
 274
 275
 276 /*
 277  * Close files used to store histogram points to generate graphs.
 278  *
 279  * Args:
 280  *   graphsDir:    folder where to write files
 281  *   rttKey:       host pair, make sure saddr < daddr
 282  */
 283 static void destroyAnalysisHistogramEval(AnalysisHistogramEval* const
 284         histogram)
 285 {
 286         unsigned int i;
 287         int retval;
 288         const struct {
 289                 size_t pointsOffset;
 290         } loopValues[]= {
 291                 {offsetof(AnalysisHistogramEval, ttSendPoints)},
 292                 {offsetof(AnalysisHistogramEval, ttRecvPoints)},
 293                 {offsetof(AnalysisHistogramEval, hrttPoints)},
 294         };
 295
 296         for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 297         {
 298                 retval= fclose(*(FILE**)((void*) histogram + loopValues[i].pointsOffset));
 299                 if (retval != 0)
 300                 {
 301                         g_error(strerror(errno));
 302                 }
 303         }
 304
 305         free(histogram);
 306 }
 307
 308
 309 /*
 310  * A GDestroyNotify function for g_hash_table_new_full()
 311  *
 312  * Args:
 313  *   data:         AnalysisHistogramEval*
 314  */
 315 static void gdnDestroyAnalysisHistogramEval(gpointer data)
 316 {
 317         destroyAnalysisHistogramEval(data);
 318 }
 319
 320
 321 /*
 322  * A GHFunc for g_hash_table_foreach()
 323  *
 324  * Args:
 325  *   key:          RttKey* where saddr < daddr
 326  *   value:        AnalysisHistogramEval*
 327  *   user_data     struct WriteHistogramInfo*
 328  */
 329 static void ghfWriteHistogram(gpointer key, gpointer value, gpointer user_data)
 330 {
 331         double* rtt1, * rtt2;
 332         struct RttKey* rttKey= key;
 333         struct RttKey oppositeRttKey= {.saddr= rttKey->daddr, .daddr=
 334                 rttKey->saddr};
 335         AnalysisHistogramEval* histogram= value;
 336         struct WriteHistogramInfo* info= user_data;
 337
 338         rtt1= g_hash_table_lookup(info->rttInfo, rttKey);
 339         rtt2= g_hash_table_lookup(info->rttInfo, &oppositeRttKey);
 340
 341         if (rtt1 == NULL)
 342         {
 343                 rtt1= rtt2;
 344         }
 345         else if (rtt2 != NULL)
 346         {
 347                 rtt1= MIN(rtt1, rtt2);
 348         }
 349
 350         dumpBinToFile(&histogram->ttSendBins, histogram->ttSendPoints);
 351         dumpBinToFile(&histogram->ttRecvBins, histogram->ttRecvPoints);
 352         dumpBinToFile(&histogram->hrttBins, histogram->hrttPoints);
 353         writeHistogram(info->graphsStream, rttKey, rtt1, histogram);
 354 }
 355
 356
 357 /*
 358  * Write the content of one bin in a histogram point file
 359  *
 360  * Args:
 361  *   bin:          array of values that make up a histogram
 362  *   file:         FILE*, write to this file
 363  */
 364 static void dumpBinToFile(const struct Bins* const bins, FILE* const file)
 365 {
 366         unsigned int i;
 367
 368         // The first and last bins are skipped, see struct Bins
 369         for (i= 1; i < BIN_NB - 1; i++)
 370         {
 371                 if (bins->bin[i] > 0)
 372                 {
 373                         fprintf(file, "%20.9f %20.9f %20.9f\n", (binStart(i) + binEnd(i))
 374                                 / 2., (double) bins->bin[i] / ((binEnd(i) - binStart(i)) *
 375                                         bins->total), binEnd(i) - binStart(i));
 376                 }
 377         }
 378 }
 379
 380
 381 /*
 382  * Write the analysis-specific plot in the gnuplot script.
 383  *
 384  * Args:
 385  *   graphsStream: write to this file
 386  *   rttKey:       must be sorted such that saddr < daddr
 387  *   minRtt:       if available, else NULL
 388  *   histogram:    struct that contains the bins for the pair of traces
 389  *                 identified by rttKey
 390  */
 391 static void writeHistogram(FILE* graphsStream, const struct RttKey* rttKey,
 392         double* minRtt, AnalysisHistogramEval* const histogram)
 393 {
 394         char saddr[16], daddr[16];
 395
 396         convertIP(saddr, rttKey->saddr);
 397         convertIP(daddr, rttKey->daddr);
 398
 399         fprintf(graphsStream,
 400                 "\nreset\n"
 401                 "set output \"histogram-%s-%s.eps\"\n"
 402                 "set title \"\"\n"
 403                 "set xlabel \"Message Latency (s)\"\n"
 404                 "set ylabel \"Proportion of messages per second\"\n", saddr, daddr);
 405
 406         if (minRtt != NULL)
 407         {
 408                 fprintf(graphsStream,
 409                         "set arrow from %.9f, 0 rto 0, graph 1 "
 410                         "nohead linetype 3 linewidth 3 linecolor rgb \"black\"\n", *minRtt
 411                         / 2);
 412         }
 413
 414         if (normalTotal(&histogram->ttSendBins) ||
 415                 normalTotal(&histogram->ttRecvBins) ||
 416                 normalTotal(&histogram->hrttBins))
 417         {
 418                 fprintf(graphsStream, "plot \\\n");
 419
 420                 if (normalTotal(&histogram->hrttBins))
 421                 {
 422                         fprintf(graphsStream,
 423                                 "\t\"analysis_eval_hrtt-%s_and_%s.data\" "
 424                                         "title \"RTT/2\" with linespoints linetype 1 linewidth 2 "
 425                                         "linecolor rgb \"black\" pointtype 6 pointsize 1,\\\n",
 426                                         saddr, daddr);
 427                 }
 428
 429                 if (normalTotal(&histogram->ttSendBins))
 430                 {
 431                         fprintf(graphsStream,
 432                                 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
 433                                         "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
 434                                         "linecolor rgb \"gray60\" pointtype 6 pointsize 1,\\\n",
 435                                         saddr, daddr);
 436                 }
 437
 438                 if (normalTotal(&histogram->ttRecvBins))
 439                 {
 440                         fprintf(graphsStream,
 441                                 "\t\"analysis_eval_tt-%1$s_to_%2$s.data\" "
 442                                         "title \"%1$s to %2$s\" with linespoints linetype 4 linewidth 2 "
 443                                         "linecolor rgb \"gray30\" pointtype 6 pointsize 1,\\\n",
 444                                         daddr, saddr);
 445                 }
 446
 447                 // Remove the ",\\\n" from the last graph plot line
 448                 if (ftruncate(fileno(graphsStream), ftell(graphsStream) - 3) == -1)
 449                 {
 450                         g_error(strerror(errno));
 451                 }
 452                 if (fseek(graphsStream, 0, SEEK_END) == -1)
 453                 {
 454                         g_error(strerror(errno));
 455                 }
 456                 fprintf(graphsStream, "\n");
 457         }
 458 }
 459
 460
 461 /*
 462  * Analysis destroy function
 463  *
 464  * Free the analysis specific data structures
 465  *
 466  * Args:
 467  *   syncState     container for synchronization data.
 468  */
 469 static void destroyAnalysisEval(SyncState* const syncState)
 470 {
 471         unsigned int i;
 472         AnalysisDataEval* analysisData;
 473
 474         analysisData= (AnalysisDataEval*) syncState->analysisData;
 475
 476         if (analysisData == NULL)
 477         {
 478                 return;
 479         }
 480
 481         g_hash_table_destroy(analysisData->rttInfo);
 482
 483         if (syncState->stats)
 484         {
 485                 AnalysisStatsEval* stats= analysisData->stats;
 486
 487                 for (i= 0; i < syncState->traceNb; i++)
 488                 {
 489                         free(stats->messageStats[i]);
 490                 }
 491                 free(stats->messageStats);
 492
 493                 g_hash_table_destroy(stats->exchangeRtt);
 494
 495                 free(stats);
 496         }
 497
 498         if (syncState->graphsStream)
 499         {
 500                 AnalysisGraphsEval* graphs= analysisData->graphs;
 501
 502                 if (graphs->histograms)
 503                 {
 504                         g_hash_table_destroy(graphs->histograms);
 505                 }
 506
 507                 for (i= 0; i < syncState->traceNb; i++)
 508                 {
 509                         free(graphs->bounds[i]);
 510                 }
 511                 free(graphs->bounds);
 512
 513                 free(graphs);
 514         }
 515
 516         free(syncState->analysisData);
 517         syncState->analysisData= NULL;
 518 }
 519
 520
 521 /*
 522  * Perform analysis on an event pair.
 523  *
 524  * Check if there is message inversion or messages that are too fast.
 525  *
 526  * Args:
 527  *   syncState     container for synchronization data
 528  *   message       structure containing the events
 529  */
 530 static void analyzeMessageEval(SyncState* const syncState, Message* const
 531         message)
 532 {
 533         AnalysisDataEval* analysisData= syncState->analysisData;
 534         MessageStats* messageStats;
 535         double* rtt;
 536         double tt;
 537         struct RttKey rttKey;
 538
 539         g_assert(message->inE->type == TCP);
 540
 541         if (syncState->stats)
 542         {
 543                 messageStats=
 544                         &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
 545                 messageStats->total++;
 546         }
 547
 548         tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
 549         if (tt <= 0)
 550         {
 551                 if (syncState->stats)
 552                 {
 553                         messageStats->inversionNb++;
 554                 }
 555         }
 556         else if (syncState->graphsStream)
 557         {
 558                 struct RttKey rttKey= {
 559                         .saddr=MIN(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 560                                 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
 561                         .daddr=MAX(message->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 562                                 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr),
 563                 };
 564                 AnalysisHistogramEval* histogram=
 565                         g_hash_table_lookup(analysisData->graphs->histograms, &rttKey);
 566
 567                 if (histogram == NULL)
 568                 {
 569                         struct RttKey* tableKey= malloc(sizeof(*tableKey));
 570
 571                         histogram= constructAnalysisHistogramEval(syncState->graphsDir, &rttKey);
 572                         memcpy(tableKey, &rttKey, sizeof(*tableKey));
 573                         g_hash_table_insert(analysisData->graphs->histograms, tableKey, histogram);
 574                 }
 575
 576                 if (message->inE->event.udpEvent->datagramKey->saddr <
 577                         message->inE->event.udpEvent->datagramKey->daddr)
 578                 {
 579                         hitBin(&histogram->ttSendBins, tt);
 580                 }
 581                 else
 582                 {
 583                         hitBin(&histogram->ttRecvBins, tt);
 584                 }
 585         }
 586
 587         if (syncState->stats)
 588         {
 589                 rttKey.saddr=
 590                         message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
 591                 rttKey.daddr=
 592                         message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
 593                 rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
 594                 g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
 595                         rttKey.daddr, rtt ? *rtt : NAN);
 596
 597                 if (rtt)
 598                 {
 599                         g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
 600                         if (tt < *rtt / 2.)
 601                         {
 602                                 messageStats->tooFastNb++;
 603                         }
 604                 }
 605                 else
 606                 {
 607                         messageStats->noRTTInfoNb++;
 608                 }
 609         }
 610
 611         if (syncState->graphsStream)
 612         {
 613                 updateBounds(analysisData->graphs->bounds, message->inE,
 614                         message->outE);
 615         }
 616 }
 617
 618
 619 /*
 620  * Perform analysis on multiple messages
 621  *
 622  * Measure the RTT
 623  *
 624  * Args:
 625  *   syncState     container for synchronization data
 626  *   exchange      structure containing the messages
 627  */
 628 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
 629         exchange)
 630 {
 631         AnalysisDataEval* analysisData= syncState->analysisData;
 632         Message* m1= g_queue_peek_tail(exchange->acks);
 633         Message* m2= exchange->message;
 634         struct RttKey* rttKey;
 635         double* rtt, * exchangeRtt;
 636
 637         g_assert(m1->inE->type == TCP);
 638
 639         // (T2 - T1) - (T3 - T4)
 640         rtt= malloc(sizeof(double));
 641         *rtt= wallTimeSub(&m1->inE->wallTime, &m1->outE->wallTime) -
 642                 wallTimeSub(&m2->outE->wallTime, &m2->inE->wallTime);
 643
 644         rttKey= malloc(sizeof(struct RttKey));
 645         rttKey->saddr=
 646                 MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 647                         m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
 648         rttKey->daddr=
 649                 MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 650                         m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
 651
 652         if (syncState->graphsStream)
 653         {
 654                 AnalysisHistogramEval* histogram=
 655                         g_hash_table_lookup(analysisData->graphs->histograms, rttKey);
 656
 657                 if (histogram == NULL)
 658                 {
 659                         struct RttKey* tableKey= malloc(sizeof(*tableKey));
 660
 661                         histogram= constructAnalysisHistogramEval(syncState->graphsDir,
 662                                 rttKey);
 663                         memcpy(tableKey, rttKey, sizeof(*tableKey));
 664                         g_hash_table_insert(analysisData->graphs->histograms, tableKey,
 665                                 histogram);
 666                 }
 667
 668                 hitBin(&histogram->hrttBins, *rtt / 2);
 669         }
 670
 671         if (syncState->stats)
 672         {
 673                 exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
 674                         rttKey);
 675
 676                 if (exchangeRtt)
 677                 {
 678                         if (*rtt < *exchangeRtt)
 679                         {
 680                                 g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
 681                         }
 682                         else
 683                         {
 684                                 free(rttKey);
 685                                 free(rtt);
 686                         }
 687                 }
 688                 else
 689                 {
 690                         g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
 691                 }
 692         }
 693         else
 694         {
 695                 free(rttKey);
 696                 free(rtt);
 697         }
 698 }
 699
 700
 701 /*
 702  * Perform analysis on muliple events
 703  *
 704  * Sum the broadcast differential delays
 705  *
 706  * Args:
 707  *   syncState     container for synchronization data
 708  *   broadcast     structure containing the events
 709  */
 710 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
 711         broadcast)
 712 {
 713         AnalysisDataEval* analysisData= syncState->analysisData;
 714
 715         if (syncState->stats)
 716         {
 717                 double sum= 0, squaresSum= 0;
 718                 double y;
 719
 720                 g_queue_foreach(broadcast->events, &gfSum, &sum);
 721                 g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
 722
 723                 analysisData->stats->broadcastNb++;
 724                 // Because of numerical errors, this can at times be < 0
 725                 y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
 726                         g_queue_get_length(broadcast->events), 2.);
 727                 if (y > 0)
 728                 {
 729                         analysisData->stats->broadcastStdevSum+= sqrt(y);
 730                 }
 731
 732                 if (syncState->traceNb == 2 && g_queue_get_length(broadcast->events)
 733                         == 2)
 734                 {
 735                         Event* e0, * e1;
 736                         double dd;
 737
 738                         e0= g_queue_peek_head(broadcast->events);
 739                         e1= g_queue_peek_tail(broadcast->events);
 740                         if (e0->traceNum > e1->traceNum)
 741                         {
 742                                 Event* tmp;
 743
 744                                 tmp= e0;
 745                                 e0= e1;
 746                                 e1= tmp;
 747                         }
 748
 749                         dd= wallTimeSub(&e1->wallTime, &e0->wallTime);
 750
 751                         analysisData->stats->broadcastPairNb++;
 752                         if (dd < analysisData->stats->broadcastRangeMin)
 753                         {
 754                                 analysisData->stats->broadcastRangeMin= dd;
 755                         }
 756                         if (dd > analysisData->stats->broadcastRangeMax)
 757                         {
 758                                 analysisData->stats->broadcastRangeMax= dd;
 759                         }
 760
 761                         analysisData->stats->broadcastSum+= dd;
 762                         analysisData->stats->broadcastSumSquares+= pow(dd, 2);
 763                 }
 764         }
 765
 766         if (syncState->graphsStream)
 767         {
 768                 unsigned int i, j;
 769                 GArray* events;
 770                 unsigned int eventNb= broadcast->events->length;
 771
 772                 events= g_array_sized_new(FALSE, FALSE, sizeof(Event*), eventNb);
 773                 g_queue_foreach(broadcast->events, &gfAddEventToArray, events);
 774
 775                 for (i= 0; i < eventNb; i++)
 776                 {
 777                         for (j= 0; j < eventNb; j++)
 778                         {
 779                                 Event* eventI= g_array_index(events, Event*, i), * eventJ=
 780                                         g_array_index(events, Event*, j);
 781
 782                                 if (eventI->traceNum < eventJ->traceNum)
 783                                 {
 784                                         updateBounds(analysisData->graphs->bounds, eventI, eventJ);
 785                                 }
 786                         }
 787                 }
 788
 789                 g_array_free(events, TRUE);
 790         }
 791 }
 792
 793
 794 /*
 795  * Finalize the factor calculations. Since this module does not really
 796  * calculate factors, absent factors are returned. Instead, histograms are
 797  * written out and histogram structures are freed.
 798  *
 799  * Args:
 800  *   syncState     container for synchronization data.
 801  *
 802  * Returns:
 803  *   AllFactors*   synchronization factors for each trace pair
 804  */
 805 static AllFactors* finalizeAnalysisEval(SyncState* const syncState)
 806 {
 807         AnalysisDataEval* analysisData= syncState->analysisData;
 808
 809         if (syncState->graphsStream && analysisData->graphs->histograms)
 810         {
 811                 g_hash_table_foreach(analysisData->graphs->histograms,
 812                         &ghfWriteHistogram, &(struct WriteHistogramInfo) {.rttInfo=
 813                         analysisData->rttInfo, .graphsStream= syncState->graphsStream});
 814                 g_hash_table_destroy(analysisData->graphs->histograms);
 815                 analysisData->graphs->histograms= NULL;
 816         }
 817
 818         return createAllFactors(syncState->traceNb);
 819 }
 820
 821
 822 /*
 823  * Print statistics related to analysis. Must be called after
 824  * finalizeAnalysis.
 825  *
 826  * Args:
 827  *   syncState     container for synchronization data.
 828  */
 829 static void printAnalysisStatsEval(SyncState* const syncState)
 830 {
 831         AnalysisDataEval* analysisData;
 832         unsigned int i, j, k;
 833         unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0;
 834         int charNb;
 835
 836         if (!syncState->stats)
 837         {
 838                 return;
 839         }
 840
 841         analysisData= (AnalysisDataEval*) syncState->analysisData;
 842
 843         printf("Synchronization evaluation analysis stats:\n");
 844         if (analysisData->stats->broadcastNb)
 845         {
 846                 printf("\tBroadcast differential delay:\n");
 847                 printf("\t\tsum of standard deviations: %g\n",
 848                         analysisData->stats->broadcastStdevSum);
 849                 printf("\t\taverage standard deviation: %g\n",
 850                         analysisData->stats->broadcastStdevSum /
 851                         analysisData->stats->broadcastNb);
 852
 853                 if (syncState->traceNb == 2)
 854                 {
 855                         printf("\t\tdifferential delay range: [ %g .. %g ]\n",
 856                                 analysisData->stats->broadcastRangeMin,
 857                                 analysisData->stats->broadcastRangeMax);
 858                         printf("\t\tdifferential delay average: %g\n",
 859                                 analysisData->stats->broadcastSum /
 860                                 analysisData->stats->broadcastPairNb);
 861                         printf("\t\tdifferential delay standard deviation: %g\n",
 862                                 sqrt(analysisData->stats->broadcastSumSquares /
 863                                         analysisData->stats->broadcastPairNb -
 864                                         pow(analysisData->stats->broadcastSum /
 865                                                 analysisData->stats->broadcastPairNb, 2)));
 866                 }
 867         }
 868
 869         printf("\tIndividual evaluation:\n"
 870                 "\t\tTrace pair  Inversions        Too fast          No RTT info  Total\n");
 871
 872         for (i= 0; i < syncState->traceNb; i++)
 873         {
 874                 for (j= i + 1; j < syncState->traceNb; j++)
 875                 {
 876                         MessageStats* messageStats;
 877                         struct {
 878                                 unsigned int t1, t2;
 879                         } loopValues[]= {
 880                                 {i, j},
 881                                 {j, i}
 882                         };
 883
 884                         for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++)
 885                         {
 886                                 messageStats=
 887                                         &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
 888
 889                                 printf("\t\t%3d - %-3d   ", loopValues[k].t1, loopValues[k].t2);
 890                                 printf("%u (%.2f%%)%n", messageStats->inversionNb, (double)
 891                                         messageStats->inversionNb / messageStats->total * 100,
 892                                         &charNb);
 893                                 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
 894                                 printf("%u (%.2f%%)%n", messageStats->tooFastNb, (double)
 895                                         messageStats->tooFastNb / messageStats->total * 100,
 896                                         &charNb);
 897                                 printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
 898                                         1, " ", messageStats->noRTTInfoNb, messageStats->total);
 899
 900                                 totInversion+= messageStats->inversionNb;
 901                                 totTooFast+= messageStats->tooFastNb;
 902                                 totNoInfo+= messageStats->noRTTInfoNb;
 903                                 totTotal+= messageStats->total;
 904                         }
 905                 }
 906         }
 907
 908         printf("\t\t  total     ");
 909         printf("%u (%.2f%%)%n", totInversion, (double) totInversion / totTotal *
 910                 100, &charNb);
 911         printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
 912         printf("%u (%.2f%%)%n", totTooFast, (double) totTooFast / totTotal * 100,
 913                 &charNb);
 914         printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
 915                 totNoInfo, totTotal);
 916
 917         printf("\tRound-trip times:\n"
 918                 "\t\tHost pair                          RTT from exchanges  RTTs from file (ms)\n");
 919         g_hash_table_foreach(analysisData->stats->exchangeRtt,
 920                 &ghfPrintExchangeRtt, analysisData->rttInfo);
 921 }
 922
 923
 924 /*
 925  * A GHFunc for g_hash_table_foreach()
 926  *
 927  * Args:
 928  *   key:          RttKey* where saddr < daddr
 929  *   value:        double*, RTT estimated from exchanges
 930  *   user_data     GHashTable* rttInfo
 931  */
 932 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer
 933         user_data)
 934 {
 935         char addr1[16], addr2[16];
 936         struct RttKey* rttKey1= key;
 937         struct RttKey rttKey2= {rttKey1->daddr, rttKey1->saddr};
 938         double* fileRtt1, *fileRtt2;
 939         GHashTable* rttInfo= user_data;
 940
 941         convertIP(addr1, rttKey1->saddr);
 942         convertIP(addr2, rttKey1->daddr);
 943
 944         fileRtt1= g_hash_table_lookup(rttInfo, rttKey1);
 945         fileRtt2= g_hash_table_lookup(rttInfo, &rttKey2);
 946
 947         printf("\t\t(%15s, %-15s) %-18.3f  ", addr1, addr2, *(double*) value * 1e3);
 948
 949         if (fileRtt1 || fileRtt2)
 950         {
 951                 if (fileRtt1)
 952                 {
 953                         printf("%.3f", *fileRtt1 * 1e3);
 954                 }
 955                 if (fileRtt1 && fileRtt2)
 956                 {
 957                         printf(", ");
 958                 }
 959                 if (fileRtt2)
 960                 {
 961                         printf("%.3f", *fileRtt2 * 1e3);
 962                 }
 963         }
 964         else
 965         {
 966                 printf("-");
 967         }
 968         printf("\n");
 969 }
 970
 971
 972 /*
 973  * A GHashFunc for g_hash_table_new()
 974  *
 975  * Args:
 976  *    key        struct RttKey*
 977  */
 978 static guint ghfRttKeyHash(gconstpointer key)
 979 {
 980         struct RttKey* rttKey;
 981         uint32_t a, b, c;
 982
 983         rttKey= (struct RttKey*) key;
 984
 985         a= rttKey->saddr;
 986         b= rttKey->daddr;
 987         c= 0;
 988         final(a, b, c);
 989
 990         return c;
 991 }
 992
 993
 994 /*
 995  * A GDestroyNotify function for g_hash_table_new_full()
 996  *
 997  * Args:
 998  *   data:         struct RttKey*
 999  */
1000 static void gdnDestroyRttKey(gpointer data)
1001 {
1002         free(data);
1003 }
1004
1005
1006 /*
1007  * A GDestroyNotify function for g_hash_table_new_full()
1008  *
1009  * Args:
1010  *   data:         double*
1011  */
1012 static void gdnDestroyDouble(gpointer data)
1013 {
1014         free(data);
1015 }
1016
1017
1018 /*
1019  * A GEqualFunc for g_hash_table_new()
1020  *
1021  * Args:
1022  *   a, b          RttKey*
1023  *
1024  * Returns:
1025  *   TRUE if both values are equal
1026  */
1027 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b)
1028 {
1029         const struct RttKey* rkA, * rkB;
1030
1031         rkA= (struct RttKey*) a;
1032         rkB= (struct RttKey*) b;
1033
1034         if (rkA->saddr == rkB->saddr && rkA->daddr == rkB->daddr)
1035         {
1036                 return TRUE;
1037         }
1038         else
1039         {
1040                 return FALSE;
1041         }
1042 }
1043
1044
1045 /*
1046  * Read a file contain minimum round trip time values and fill an array with
1047  * them. The file is formatted as such:
1048  * <host1 IP> <host2 IP> <RTT in milliseconds>
1049  * ip's should be in dotted quad format
1050  *
1051  * Args:
1052  *   rttInfo:      double* rttInfo[RttKey], empty table, will be filled
1053  *   rttStream:      stream from which to read
1054  */
1055 static void readRttInfo(GHashTable* rttInfo, FILE* rttStream)
1056 {
1057         char* line= NULL;
1058         size_t len;
1059         int retval;
1060
1061         positionStream(rttStream);
1062         retval= getline(&line, &len, rttStream);
1063         while(!feof(rttStream))
1064         {
1065                 struct RttKey* rttKey;
1066                 char saddrDQ[20], daddrDQ[20];
1067                 double* rtt;
1068                 char tmp;
1069                 struct in_addr addr;
1070                 unsigned int i;
1071                 struct {
1072                         char* dq;
1073                         size_t offset;
1074                 } loopValues[] = {
1075                         {saddrDQ, offsetof(struct RttKey, saddr)},
1076                         {daddrDQ, offsetof(struct RttKey, daddr)}
1077                 };
1078
1079                 if (retval == -1 && !feof(rttStream))
1080                 {
1081                         g_error(strerror(errno));
1082                 }
1083
1084                 if (line[retval - 1] == '\n')
1085                 {
1086                         line[retval - 1]= '\0';
1087                 }
1088
1089                 rtt= malloc(sizeof(double));
1090                 retval= sscanf(line, " %19s %19s %lf %c", saddrDQ, daddrDQ, rtt,
1091                         &tmp);
1092                 if (retval == EOF)
1093                 {
1094                         g_error(strerror(errno));
1095                 }
1096                 else if (retval != 3)
1097                 {
1098                         g_error("Error parsing RTT file, line was '%s'", line);
1099                 }
1100
1101                 rttKey= malloc(sizeof(struct RttKey));
1102                 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
1103                 {
1104                         retval= inet_aton(loopValues[i].dq, &addr);
1105                         if (retval == 0)
1106                         {
1107                                 g_error("Error converting address '%s'", loopValues[i].dq);
1108                         }
1109                         *(uint32_t*) ((void*) rttKey + loopValues[i].offset)=
1110                                 addr.s_addr;
1111                 }
1112
1113                 *rtt/= 1e3;
1114                 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey->saddr,
1115                         rttKey->daddr, *rtt);
1116                 g_hash_table_insert(rttInfo, rttKey, rtt);
1117
1118                 positionStream(rttStream);
1119                 retval= getline(&line, &len, rttStream);
1120         }
1121
1122         if (line)
1123         {
1124                 free(line);
1125         }
1126 }
1127
1128
1129 /*
1130  * Advance stream over empty space, empty lines and lines that begin with '#'
1131  *
1132  * Args:
1133  *   stream:     stream, at exit, will be over the first non-empty character
1134  *               of a line of be at EOF
1135  */
1136 static void positionStream(FILE* stream)
1137 {
1138         int firstChar;
1139         ssize_t retval;
1140         char* line= NULL;
1141         size_t len;
1142
1143         do
1144         {
1145                 firstChar= fgetc(stream);
1146                 if (firstChar == (int) '#')
1147                 {
1148                         retval= getline(&line, &len, stream);
1149                         if (retval == -1)
1150                         {
1151                                 if (feof(stream))
1152                                 {
1153                                         goto outEof;
1154                                 }
1155                                 else
1156                                 {
1157                                         g_error(strerror(errno));
1158                                 }
1159                         }
1160                 }
1161                 else if (firstChar == (int) '\n' || firstChar == (int) ' ' ||
1162                         firstChar == (int) '\t')
1163                 {}
1164                 else if (firstChar == EOF)
1165                 {
1166                         goto outEof;
1167                 }
1168                 else
1169                 {
1170                         break;
1171                 }
1172         } while (true);
1173         retval= ungetc(firstChar, stream);
1174         if (retval == EOF)
1175         {
1176                 g_error("Error: ungetc()");
1177         }
1178
1179 outEof:
1180         if (line)
1181         {
1182                 free(line);
1183         }
1184 }
1185
1186
1187 /*
1188  * A GFunc for g_queue_foreach()
1189  *
1190  * Args:
1191  *   data          Event*, a UDP broadcast event
1192  *   user_data     double*, the running sum
1193  *
1194  * Returns:
1195  *   Adds the time of the event to the sum
1196  */
1197 static void gfSum(gpointer data, gpointer userData)
1198 {
1199         Event* event= (Event*) data;
1200
1201         *(double*) userData+= event->wallTime.seconds + event->wallTime.nanosec /
1202                 1e9;
1203 }
1204
1205
1206 /*
1207  * A GFunc for g_queue_foreach()
1208  *
1209  * Args:
1210  *   data          Event*, a UDP broadcast event
1211  *   user_data     double*, the running sum
1212  *
1213  * Returns:
1214  *   Adds the square of the time of the event to the sum
1215  */
1216 static void gfSumSquares(gpointer data, gpointer userData)
1217 {
1218         Event* event= (Event*) data;
1219
1220         *(double*) userData+= pow(event->wallTime.seconds + event->wallTime.nanosec
1221                 / 1e9, 2.);
1222 }
1223
1224
1225 /*
1226  * Update a struct Bins according to a new value
1227  *
1228  * Args:
1229  *   bins:         the structure containing bins to build a histrogram
1230  *   value:        the new value
1231  */
1232 static void hitBin(struct Bins* const bins, const double value)
1233 {
1234         unsigned int binN= binNum(value);
1235
1236         if (binN < bins->min)
1237         {
1238                 bins->min= binN;
1239         }
1240         else if (binN > bins->max)
1241         {
1242                 bins->max= binN;
1243         }
1244
1245         bins->total++;
1246
1247         bins->bin[binN]++;
1248 }
1249
1250
1251 /*
1252  * Figure out the bin in a histogram to which a value belongs.
1253  *
1254  * This uses exponentially sized bins that go from 0 to infinity.
1255  *
1256  * Args:
1257  *   value:        in the range -INFINITY to INFINITY
1258  *
1259  * Returns:
1260  *   The number of the bin in a struct Bins.bin
1261  */
1262 static unsigned int binNum(const double value)
1263 {
1264         if (value <= 0)
1265         {
1266                 return 0;
1267         }
1268         else if (value < binEnd(1))
1269         {
1270                 return 1;
1271         }
1272         else if (value >= binStart(BIN_NB - 1))
1273         {
1274                 return BIN_NB - 1;
1275         }
1276         else
1277         {
1278                 return floor(log(value) / log(binBase)) + BIN_NB + 1;
1279         }
1280 }
1281
1282
1283 /*
1284  * Figure out the start of the interval of a bin in a histogram. See struct
1285  * Bins.
1286  *
1287  * This uses exponentially sized bins that go from 0 to infinity.
1288  *
1289  * Args:
1290  *   binNum:       bin number
1291  *
1292  * Return:
1293  *   The start of the interval, this value is included in the interval (except
1294  *   for -INFINITY, naturally)
1295  */
1296 static double binStart(const unsigned int binNum)
1297 {
1298         g_assert_cmpuint(binNum, <, BIN_NB);
1299
1300         if (binNum == 0)
1301         {
1302                 return -INFINITY;
1303         }
1304         else if (binNum == 1)
1305         {
1306                 return 0.;
1307         }
1308         else
1309         {
1310                 return pow(binBase, (double) binNum - BIN_NB + 1);
1311         }
1312 }
1313
1314
1315 /*
1316  * Figure out the end of the interval of a bin in a histogram. See struct
1317  * Bins.
1318  *
1319  * This uses exponentially sized bins that go from 0 to infinity.
1320  *
1321  * Args:
1322  *   binNum:       bin number
1323  *
1324  * Return:
1325  *   The end of the interval, this value is not included in the interval
1326  */
1327 static double binEnd(const unsigned int binNum)
1328 {
1329         g_assert_cmpuint(binNum, <, BIN_NB);
1330
1331         if (binNum == 0)
1332         {
1333                 return 0.;
1334         }
1335         else if (binNum < BIN_NB - 1)
1336         {
1337                 return pow(binBase, (double) binNum - BIN_NB + 2);
1338         }
1339         else
1340         {
1341                 return INFINITY;
1342         }
1343 }
1344
1345
1346 /*
1347  * Return the total number of elements in the "normal" bins (not underflow or
1348  * overflow)
1349  *
1350  * Args:
1351  *   bins:         the structure containing bins to build a histrogram
1352  */
1353 static uint32_t normalTotal(struct Bins* const bins)
1354 {
1355         return bins->total - bins->bin[0] - bins->bin[BIN_NB - 1];
1356 }
1357
1358
1359 /* Update the bounds between two traces
1360  *
1361  * Args:
1362  *   bounds:       the array containing all the trace-pair bounds
1363  *   e1, e2:       the two related events
1364  */
1365 static void updateBounds(Bounds** const bounds, Event* const e1, Event* const
1366         e2)
1367 {
1368         unsigned int traceI, traceJ;
1369         uint64_t messageTime;
1370         Bounds* tpBounds;
1371
1372         if (e1->traceNum < e2->traceNum)
1373         {
1374                 traceI= e2->traceNum;
1375                 traceJ= e1->traceNum;
1376                 messageTime= e1->cpuTime;
1377         }
1378         else
1379         {
1380                 traceI= e1->traceNum;
1381                 traceJ= e2->traceNum;
1382                 messageTime= e2->cpuTime;
1383         }
1384         tpBounds= &bounds[traceI][traceJ];
1385
1386         if (messageTime < tpBounds->min)
1387         {
1388                 tpBounds->min= messageTime;
1389         }
1390         if (messageTime > tpBounds->max)
1391         {
1392                 tpBounds->max= messageTime;
1393         }
1394 }