lttv/lttv/sync/event_analysis_eval.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 #define _GNU_SOURCE
  20 #define _ISOC99_SOURCE
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <arpa/inet.h>
  27 #include <errno.h>
  28 #include <math.h>
  29 #include <netinet/in.h>
  30 #include <stddef.h>
  31 #include <stdlib.h>
  32 #include <stdio.h>
  33 #include <string.h>
  34 #include <sys/socket.h>
  35 #include <unistd.h>
  36
  37 #include "lookup3.h"
  38 #include "sync_chain.h"
  39
  40 #include "event_analysis_eval.h"
  41
  42
  43 // Functions common to all analysis modules
  44 static void initAnalysisEval(SyncState* const syncState);
  45 static void destroyAnalysisEval(SyncState* const syncState);
  46
  47 static void analyzeMessageEval(SyncState* const syncState, Message* const
  48         message);
  49 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const
  50         exchange);
  51 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const
  52         broadcast);
  53 static GArray* finalizeAnalysisEval(SyncState* const syncState);
  54 static void printAnalysisStatsEval(SyncState* const syncState);
  55 static void writeAnalysisGraphsPlotsEval(FILE* stream, SyncState* const
  56         syncState, const unsigned int i, const unsigned int j);
  57 static void writeAnalysisGraphsOptionsEval(FILE* stream, SyncState*
  58     const syncState, const unsigned int i, const unsigned int j);
  59
  60 // Functions specific to this module
  61 static void registerAnalysisEval() __attribute__((constructor (102)));
  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 user_data);
  72
  73 static void initGraphs(SyncState* const syncState);
  74 static void writeGraphFiles(SyncState* const syncState);
  75 static void dumpBinToFile(const uint32_t* const bin, const uint32_t total,
  76         FILE* const file);
  77 static void destroyGraphs(SyncState* const syncState);
  78 static unsigned int binNum(const double value) __attribute__((pure));
  79 static double binStart(const unsigned int binNum) __attribute__((pure));
  80 static double binEnd(const unsigned int binNum) __attribute__((pure));
  81
  82
  83 const unsigned int binNb= 10000;
  84 double binBase;
  85
  86 static AnalysisModule analysisModuleEval= {
  87         .name= "eval",
  88         .initAnalysis= &initAnalysisEval,
  89         .destroyAnalysis= &destroyAnalysisEval,
  90         .analyzeMessage= &analyzeMessageEval,
  91         .analyzeExchange= &analyzeExchangeEval,
  92         .analyzeBroadcast= &analyzeBroadcastEval,
  93         .finalizeAnalysis= &finalizeAnalysisEval,
  94         .printAnalysisStats= &printAnalysisStatsEval,
  95         .writeAnalysisGraphsPlots= &writeAnalysisGraphsPlotsEval,
  96         .writeAnalysisGraphsOptions= &writeAnalysisGraphsOptionsEval,
  97 };
  98
  99 static ModuleOption optionEvalRttFile= {
 100         .longName= "eval-rtt-file",
 101         .hasArg= REQUIRED_ARG,
 102         {.arg= NULL},
 103         .optionHelp= "specify the file containing RTT information",
 104         .argHelp= "FILE",
 105 };
 106
 107
 108 /*
 109  * Analysis module registering function
 110  */
 111 static void registerAnalysisEval()
 112 {
 113         g_queue_push_tail(&analysisModules, &analysisModuleEval);
 114         g_queue_push_tail(&moduleOptions, &optionEvalRttFile);
 115 }
 116
 117
 118 /*
 119  * Analysis init function
 120  *
 121  * This function is called at the beginning of a synchronization run for a set
 122  * of traces.
 123  *
 124  * Args:
 125  *   syncState     container for synchronization data.
 126  */
 127 static void initAnalysisEval(SyncState* const syncState)
 128 {
 129         AnalysisDataEval* analysisData;
 130         unsigned int i;
 131
 132         analysisData= malloc(sizeof(AnalysisDataEval));
 133         syncState->analysisData= analysisData;
 134
 135         analysisData->rttInfo= g_hash_table_new_full(&ghfRttKeyHash,
 136                 &gefRttKeyEqual, &gdnDestroyRttKey, &gdnDestroyDouble);
 137         if (optionEvalRttFile.arg)
 138         {
 139                 FILE* rttStream;
 140                 int retval;
 141
 142                 rttStream= fopen(optionEvalRttFile.arg, "r");
 143                 if (rttStream == NULL)
 144                 {
 145                         g_error(strerror(errno));
 146                 }
 147
 148                 readRttInfo(analysisData->rttInfo, rttStream);
 149
 150                 retval= fclose(rttStream);
 151                 if (retval == EOF)
 152                 {
 153                         g_error(strerror(errno));
 154                 }
 155         }
 156
 157         if (syncState->stats)
 158         {
 159                 analysisData->stats= calloc(1, sizeof(AnalysisStatsEval));
 160                 analysisData->stats->broadcastDiffSum= 0.;
 161
 162                 analysisData->stats->messageStats= malloc(syncState->traceNb *
 163                         sizeof(MessageStats*));
 164                 for (i= 0; i < syncState->traceNb; i++)
 165                 {
 166                         analysisData->stats->messageStats[i]= calloc(syncState->traceNb,
 167                                 sizeof(MessageStats));
 168                 }
 169
 170                 analysisData->stats->exchangeRtt=
 171                         g_hash_table_new_full(&ghfRttKeyHash, &gefRttKeyEqual,
 172                                 &gdnDestroyRttKey, &gdnDestroyDouble);
 173         }
 174
 175         if (syncState->graphs)
 176         {
 177                 binBase= exp10(6. / (binNb - 2));
 178                 analysisData->graphs= malloc(sizeof(AnalysisGraphsEval));
 179                 initGraphs(syncState);
 180         }
 181 }
 182
 183
 184 /*
 185  * Create and open files used to store histogram points to genereate
 186  * graphs. Allocate and populate array to store file pointers.
 187  *
 188  * Also create data structures to store histogram points during analysis.
 189  *
 190  * Args:
 191  *   syncState:    container for synchronization data
 192  */
 193 static void initGraphs(SyncState* const syncState)
 194 {
 195         unsigned int i, j;
 196         int retval;
 197         char* cwd;
 198         char name[36];
 199         AnalysisDataEval* analysisData= syncState->analysisData;
 200
 201         cwd= changeToGraphDir(syncState->graphs);
 202
 203         analysisData->graphs->ttPoints= malloc(syncState->traceNb *
 204                 sizeof(FILE**));
 205         analysisData->graphs->ttBinsArray= malloc(syncState->traceNb *
 206                 sizeof(uint32_t**));
 207         analysisData->graphs->ttBinsTotal= malloc(syncState->traceNb *
 208                 sizeof(uint32_t*));
 209         for (i= 0; i < syncState->traceNb; i++)
 210         {
 211                 analysisData->graphs->ttPoints[i]= malloc(syncState->traceNb *
 212                         sizeof(FILE*));
 213                 analysisData->graphs->ttBinsArray[i]= malloc(syncState->traceNb *
 214                         sizeof(uint32_t*));
 215                 analysisData->graphs->ttBinsTotal[i]= calloc(syncState->traceNb,
 216                         sizeof(uint32_t));
 217                 for (j= 0; j < syncState->traceNb; j++)
 218                 {
 219                         if (i != j)
 220                         {
 221                                 retval= snprintf(name, sizeof(name),
 222                                         "analysis_eval_tt-%03u_to_%03u.data", i, j);
 223                                 if (retval > sizeof(name) - 1)
 224                                 {
 225                                         name[sizeof(name) - 1]= '\0';
 226                                 }
 227                                 if ((analysisData->graphs->ttPoints[i][j]= fopen(name, "w")) ==
 228                                         NULL)
 229                                 {
 230                                         g_error(strerror(errno));
 231                                 }
 232
 233                                 analysisData->graphs->ttBinsArray[i][j]= calloc(binNb,
 234                                         sizeof(uint32_t));
 235                         }
 236                 }
 237         }
 238
 239         analysisData->graphs->hrttPoints= malloc(syncState->traceNb *
 240                 sizeof(FILE**));
 241         analysisData->graphs->hrttBinsArray= malloc(syncState->traceNb *
 242                 sizeof(uint32_t**));
 243         analysisData->graphs->hrttBinsTotal= malloc(syncState->traceNb *
 244                 sizeof(uint32_t*));
 245         for (i= 0; i < syncState->traceNb; i++)
 246         {
 247                 analysisData->graphs->hrttPoints[i]= malloc(i * sizeof(FILE*));
 248                 analysisData->graphs->hrttBinsArray[i]= malloc(i * sizeof(uint32_t*));
 249                 analysisData->graphs->hrttBinsTotal[i]= calloc(i, sizeof(uint32_t));
 250                 for (j= 0; j < i; j++)
 251                 {
 252                         retval= snprintf(name, sizeof(name),
 253                                 "analysis_eval_hrtt-%03u_and_%03u.data", i, j);
 254                         if (retval > sizeof(name) - 1)
 255                         {
 256                                 name[sizeof(name) - 1]= '\0';
 257                         }
 258                         if ((analysisData->graphs->hrttPoints[i][j]= fopen(name, "w")) ==
 259                                 NULL)
 260                         {
 261                                 g_error(strerror(errno));
 262                         }
 263
 264                         analysisData->graphs->hrttBinsArray[i][j]= calloc(binNb,
 265                                 sizeof(uint32_t));
 266                 }
 267         }
 268
 269         retval= chdir(cwd);
 270         if (retval == -1)
 271         {
 272                 g_error(strerror(errno));
 273         }
 274         free(cwd);
 275 }
 276
 277
 278 /*
 279  * Write histogram points to all files to generate graphs.
 280  *
 281  * Args:
 282  *   syncState:    container for synchronization data
 283  */
 284 static void writeGraphFiles(SyncState* const syncState)
 285 {
 286         unsigned int i, j;
 287         AnalysisDataEval* analysisData= syncState->analysisData;
 288
 289         for (i= 0; i < syncState->traceNb; i++)
 290         {
 291                 for (j= 0; j < syncState->traceNb; j++)
 292                 {
 293                         if (i != j)
 294                         {
 295                                 dumpBinToFile(analysisData->graphs->ttBinsArray[i][j],
 296                                         analysisData->graphs->ttBinsTotal[i][j] -
 297                                         analysisData->graphs->ttBinsArray[i][j][binNb - 1],
 298                                         analysisData->graphs->ttPoints[i][j]);
 299                         }
 300
 301                         if (i > j)
 302                         {
 303                                 dumpBinToFile(analysisData->graphs->hrttBinsArray[i][j],
 304                                         analysisData->graphs->hrttBinsTotal[i][j] -
 305                                         analysisData->graphs->hrttBinsArray[i][j][binNb - 1],
 306                                         analysisData->graphs->hrttPoints[i][j]);
 307                         }
 308                 }
 309         }
 310 }
 311
 312
 313 /*
 314  * Write the content of one bin in a histogram point file
 315  *
 316  * Args:
 317  *   bin:          array of values that make up a histogram
 318  *   total:        total number of messages in bins 0 to binNb - 2
 319  *   file:         FILE*
 320  */
 321 static void dumpBinToFile(const uint32_t* const bin, const uint32_t total,
 322         FILE* const file)
 323 {
 324         unsigned int i;
 325
 326         // Last bin is skipped because is continues till infinity
 327         for (i= 0; i < binNb - 1; i++)
 328         {
 329                 if (bin[i] > 0)
 330                 {
 331                         fprintf(file, "%20.9f %20.9f %20.9f\n", (binStart(i) + binEnd(i)) / 2, (double) bin[i]
 332                                 / ((binEnd(i) - binStart(i)) * total), binEnd(i) - binStart(i));
 333                 }
 334         }
 335 }
 336
 337
 338 /*
 339  * Close files used to store histogram points to generate graphs. Deallocate
 340  * arrays of file pointers and arrays used to store histogram points during
 341  * analysis.
 342  *
 343  * Args:
 344  *   syncState:    container for synchronization data
 345  */
 346 static void destroyGraphs(SyncState* const syncState)
 347 {
 348         unsigned int i, j;
 349         AnalysisDataEval* analysisData= syncState->analysisData;
 350         int retval;
 351
 352         if (analysisData->graphs == NULL || analysisData->graphs->ttPoints ==
 353                 NULL)
 354         {
 355                 return;
 356         }
 357
 358         for (i= 0; i < syncState->traceNb; i++)
 359         {
 360                 for (j= 0; j < syncState->traceNb; j++)
 361                 {
 362                         if (i != j)
 363                         {
 364                                 retval= fclose(analysisData->graphs->ttPoints[i][j]);
 365                                 if (retval != 0)
 366                                 {
 367                                         g_error(strerror(errno));
 368                                 }
 369
 370                                 free(analysisData->graphs->ttBinsArray[i][j]);
 371                         }
 372                 }
 373                 free(analysisData->graphs->ttPoints[i]);
 374                 free(analysisData->graphs->ttBinsArray[i]);
 375                 free(analysisData->graphs->ttBinsTotal[i]);
 376         }
 377         free(analysisData->graphs->ttPoints);
 378         free(analysisData->graphs->ttBinsArray);
 379         free(analysisData->graphs->ttBinsTotal);
 380
 381         for (i= 0; i < syncState->traceNb; i++)
 382         {
 383                 for (j= 0; j < i; j++)
 384                 {
 385                         retval= fclose(analysisData->graphs->hrttPoints[i][j]);
 386                         if (retval != 0)
 387                         {
 388                                 g_error(strerror(errno));
 389                         }
 390
 391                         free(analysisData->graphs->hrttBinsArray[i][j]);
 392                 }
 393                 free(analysisData->graphs->hrttPoints[i]);
 394                 free(analysisData->graphs->hrttBinsArray[i]);
 395                 free(analysisData->graphs->hrttBinsTotal[i]);
 396         }
 397         free(analysisData->graphs->hrttPoints);
 398         free(analysisData->graphs->hrttBinsArray);
 399         free(analysisData->graphs->hrttBinsTotal);
 400
 401         analysisData->graphs->ttPoints= NULL;
 402 }
 403
 404
 405 /*
 406  * Analysis destroy function
 407  *
 408  * Free the analysis specific data structures
 409  *
 410  * Args:
 411  *   syncState     container for synchronization data.
 412  */
 413 static void destroyAnalysisEval(SyncState* const syncState)
 414 {
 415         unsigned int i;
 416         AnalysisDataEval* analysisData;
 417
 418         analysisData= (AnalysisDataEval*) syncState->analysisData;
 419
 420         if (analysisData == NULL || analysisData->rttInfo == NULL)
 421         {
 422                 return;
 423         }
 424
 425         g_hash_table_destroy(analysisData->rttInfo);
 426         analysisData->rttInfo= NULL;
 427
 428         if (syncState->stats)
 429         {
 430                 for (i= 0; i < syncState->traceNb; i++)
 431                 {
 432                         free(analysisData->stats->messageStats[i]);
 433                 }
 434                 free(analysisData->stats->messageStats);
 435
 436                 g_hash_table_destroy(analysisData->stats->exchangeRtt);
 437
 438                 free(analysisData->stats);
 439         }
 440
 441         if (syncState->graphs && analysisData->graphs)
 442         {
 443                 destroyGraphs(syncState);
 444                 free(analysisData->graphs);
 445         }
 446
 447         free(syncState->analysisData);
 448         syncState->analysisData= NULL;
 449 }
 450
 451
 452 /*
 453  * Perform analysis on an event pair.
 454  *
 455  * Check if there is message inversion or messages that are too fast.
 456  *
 457  * Args:
 458  *   syncState     container for synchronization data
 459  *   message       structure containing the events
 460  */
 461 static void analyzeMessageEval(SyncState* const syncState, Message* const message)
 462 {
 463         AnalysisDataEval* analysisData;
 464         MessageStats* messageStats;
 465         double* rtt;
 466         double tt;
 467         struct RttKey rttKey;
 468
 469         if (!syncState->stats)
 470         {
 471                 return;
 472         }
 473
 474         analysisData= (AnalysisDataEval*) syncState->analysisData;
 475         messageStats=
 476                 &analysisData->stats->messageStats[message->outE->traceNum][message->inE->traceNum];
 477
 478         messageStats->total++;
 479
 480         tt= wallTimeSub(&message->inE->wallTime, &message->outE->wallTime);
 481         if (tt <= 0)
 482         {
 483                 messageStats->inversionNb++;
 484         }
 485         else if (syncState->graphs)
 486         {
 487                 analysisData->graphs->ttBinsArray[message->outE->traceNum][message->inE->traceNum][binNum(tt)]++;
 488                 analysisData->graphs->ttBinsTotal[message->outE->traceNum][message->inE->traceNum]++;
 489         }
 490
 491         g_assert(message->inE->type == TCP);
 492         rttKey.saddr=
 493                 message->inE->event.tcpEvent->segmentKey->connectionKey.saddr;
 494         rttKey.daddr=
 495                 message->inE->event.tcpEvent->segmentKey->connectionKey.daddr;
 496         rtt= g_hash_table_lookup(analysisData->rttInfo, &rttKey);
 497         g_debug("rttInfo, looking up (%u, %u)->(%f)", rttKey.saddr,
 498                 rttKey.daddr, rtt ? *rtt : NAN);
 499
 500         if (rtt)
 501         {
 502                 g_debug("rttInfo, tt: %f rtt / 2: %f", tt, *rtt / 2.);
 503                 if (tt < *rtt / 2.)
 504                 {
 505                         messageStats->tooFastNb++;
 506                 }
 507         }
 508         else
 509         {
 510                 messageStats->noRTTInfoNb++;
 511         }
 512 }
 513
 514
 515 /*
 516  * Perform analysis on multiple messages
 517  *
 518  * Measure the RTT
 519  *
 520  * Args:
 521  *   syncState     container for synchronization data
 522  *   exchange      structure containing the messages
 523  */
 524 static void analyzeExchangeEval(SyncState* const syncState, Exchange* const exchange)
 525 {
 526         AnalysisDataEval* analysisData= syncState->analysisData;
 527         Message* m1= g_queue_peek_tail(exchange->acks);
 528         Message* m2= exchange->message;
 529         struct RttKey* rttKey;
 530         double* rtt, * exchangeRtt;
 531
 532         if (!syncState->stats)
 533         {
 534                 return;
 535         }
 536
 537         // (T2 - T1) - (T3 - T4)
 538         rtt= malloc(sizeof(double));
 539         *rtt= wallTimeSub(&m1->inE->wallTime, &m1->outE->wallTime) -
 540                 wallTimeSub(&m2->outE->wallTime, &m2->inE->wallTime);
 541
 542         if (syncState->graphs)
 543         {
 544                 unsigned int row= MAX(m1->inE->traceNum, m1->outE->traceNum);
 545                 unsigned int col= MIN(m1->inE->traceNum, m1->outE->traceNum);
 546
 547                 analysisData->graphs->hrttBinsArray[row][col][binNum(*rtt / 2.)]++;
 548                 analysisData->graphs->hrttBinsTotal[row][col]++;
 549         }
 550
 551         g_assert(m1->inE->type == TCP);
 552         rttKey= malloc(sizeof(struct RttKey));
 553         rttKey->saddr=
 554                 MIN(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 555                         m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
 556         rttKey->daddr=
 557                 MAX(m1->inE->event.tcpEvent->segmentKey->connectionKey.saddr,
 558                         m1->inE->event.tcpEvent->segmentKey->connectionKey.daddr);
 559         exchangeRtt= g_hash_table_lookup(analysisData->stats->exchangeRtt,
 560                 rttKey);
 561
 562         if (exchangeRtt)
 563         {
 564                 if (*rtt < *exchangeRtt)
 565                 {
 566                         g_hash_table_replace(analysisData->stats->exchangeRtt, rttKey, rtt);
 567                 }
 568         }
 569         else
 570         {
 571                 g_hash_table_insert(analysisData->stats->exchangeRtt, rttKey, rtt);
 572         }
 573 }
 574
 575
 576 /*
 577  * Perform analysis on muliple events
 578  *
 579  * Sum the broadcast differential delays
 580  *
 581  * Args:
 582  *   syncState     container for synchronization data
 583  *   broadcast     structure containing the events
 584  */
 585 static void analyzeBroadcastEval(SyncState* const syncState, Broadcast* const broadcast)
 586 {
 587         AnalysisDataEval* analysisData;
 588         double sum= 0, squaresSum= 0;
 589         double y;
 590
 591         if (!syncState->stats)
 592         {
 593                 return;
 594         }
 595
 596         analysisData= (AnalysisDataEval*) syncState->analysisData;
 597
 598         g_queue_foreach(broadcast->events, &gfSum, &sum);
 599         g_queue_foreach(broadcast->events, &gfSumSquares, &squaresSum);
 600
 601         analysisData->stats->broadcastNb++;
 602         // Because of numerical errors, this can at times be < 0
 603         y= squaresSum / g_queue_get_length(broadcast->events) - pow(sum /
 604                 g_queue_get_length(broadcast->events), 2.);
 605         if (y > 0)
 606         {
 607                 analysisData->stats->broadcastDiffSum+= sqrt(y);
 608         }
 609 }
 610
 611
 612 /*
 613  * Finalize the factor calculations
 614  *
 615  * Since this module does not really calculate factors, identity factors are
 616  * returned.
 617  *
 618  * Args:
 619  *   syncState     container for synchronization data.
 620  *
 621  * Returns:
 622  *   Factors[traceNb] identity factors for each trace
 623  */
 624 static GArray* finalizeAnalysisEval(SyncState* const syncState)
 625 {
 626         GArray* factors;
 627         unsigned int i;
 628         AnalysisDataEval* analysisData= syncState->analysisData;
 629
 630         if (syncState->graphs && analysisData->graphs)
 631         {
 632                 writeGraphFiles(syncState);
 633                 destroyGraphs(syncState);
 634                 analysisData->graphs= NULL;
 635         }
 636
 637         factors= g_array_sized_new(FALSE, FALSE, sizeof(Factors),
 638                 syncState->traceNb);
 639         g_array_set_size(factors, syncState->traceNb);
 640         for (i= 0; i < syncState->traceNb; i++)
 641         {
 642                 Factors* e;
 643
 644                 e= &g_array_index(factors, Factors, i);
 645                 e->drift= 1.;
 646                 e->offset= 0.;
 647         }
 648
 649         return factors;
 650 }
 651
 652
 653 /*
 654  * Print statistics related to analysis. Must be called after
 655  * finalizeAnalysis.
 656  *
 657  * Args:
 658  *   syncState     container for synchronization data.
 659  */
 660 static void printAnalysisStatsEval(SyncState* const syncState)
 661 {
 662         AnalysisDataEval* analysisData;
 663         unsigned int i, j;
 664
 665         if (!syncState->stats)
 666         {
 667                 return;
 668         }
 669
 670         analysisData= (AnalysisDataEval*) syncState->analysisData;
 671
 672         printf("Synchronization evaluation analysis stats:\n");
 673         printf("\tsum of broadcast differential delays: %g\n",
 674                 analysisData->stats->broadcastDiffSum);
 675         printf("\taverage broadcast differential delays: %g\n",
 676                 analysisData->stats->broadcastDiffSum /
 677                 analysisData->stats->broadcastNb);
 678
 679         printf("\tIndividual evaluation:\n"
 680                 "\t\tTrace pair  Inversions Too fast   (No RTT info) Total\n");
 681
 682         for (i= 0; i < syncState->traceNb; i++)
 683         {
 684                 for (j= i + 1; j < syncState->traceNb; j++)
 685                 {
 686                         MessageStats* messageStats;
 687                         const char* format= "\t\t%3d - %-3d   %-10u %-10u %-10u    %u\n";
 688
 689                         messageStats= &analysisData->stats->messageStats[i][j];
 690
 691                         printf(format, i, j, messageStats->inversionNb, messageStats->tooFastNb,
 692                                 messageStats->noRTTInfoNb, messageStats->total);
 693
 694                         messageStats= &analysisData->stats->messageStats[j][i];
 695
 696                         printf(format, j, i, messageStats->inversionNb, messageStats->tooFastNb,
 697                                 messageStats->noRTTInfoNb, messageStats->total);
 698                 }
 699         }
 700
 701         printf("\tRound-trip times:\n"
 702                 "\t\tHost pair                          RTT from exchanges  RTTs from file (ms)\n");
 703         g_hash_table_foreach(analysisData->stats->exchangeRtt,
 704                 &ghfPrintExchangeRtt, analysisData->rttInfo);
 705 }
 706
 707
 708 /*
 709  * A GHFunc for g_hash_table_foreach()
 710  *
 711  * Args:
 712  *   key:          RttKey* where saddr < daddr
 713  *   value:        double*, RTT estimated from exchanges
 714  *   user_data     GHashTable* rttInfo
 715  */
 716 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data)
 717 {
 718         char addr1[16], addr2[16];
 719         struct RttKey* rttKey1= key;
 720         struct RttKey rttKey2= {rttKey1->daddr, rttKey1->saddr};
 721         double* fileRtt1, *fileRtt2;
 722         GHashTable* rttInfo= user_data;
 723
 724         convertIP(addr1, rttKey1->saddr);
 725         convertIP(addr2, rttKey1->daddr);
 726
 727         fileRtt1= g_hash_table_lookup(rttInfo, rttKey1);
 728         fileRtt2= g_hash_table_lookup(rttInfo, &rttKey2);
 729
 730         printf("\t\t(%15s, %-15s) %-18.3f  ", addr1, addr2, *(double*) value * 1e3);
 731
 732         if (fileRtt1 || fileRtt2)
 733         {
 734                 if (fileRtt1)
 735                 {
 736                         printf("%.3f", *fileRtt1 * 1e3);
 737                 }
 738                 if (fileRtt1 && fileRtt2)
 739                 {
 740                         printf(", ");
 741                 }
 742                 if (fileRtt2)
 743                 {
 744                         printf("%.3f", *fileRtt2 * 1e3);
 745                 }
 746         }
 747         else
 748         {
 749                 printf("-");
 750         }
 751         printf("\n");
 752 }
 753
 754
 755 /*
 756  * A GHashFunc for g_hash_table_new()
 757  *
 758  * Args:
 759  *    key        struct RttKey*
 760  */
 761 static guint ghfRttKeyHash(gconstpointer key)
 762 {
 763         struct RttKey* rttKey;
 764         uint32_t a, b, c;
 765
 766         rttKey= (struct RttKey*) key;
 767
 768         a= rttKey->saddr;
 769         b= rttKey->daddr;
 770         c= 0;
 771         final(a, b, c);
 772
 773         return c;
 774 }
 775
 776
 777 /*
 778  * A GDestroyNotify function for g_hash_table_new_full()
 779  *
 780  * Args:
 781  *   data:         struct RttKey*
 782  */
 783 static void gdnDestroyRttKey(gpointer data)
 784 {
 785         free(data);
 786 }
 787
 788
 789 /*
 790  * A GDestroyNotify function for g_hash_table_new_full()
 791  *
 792  * Args:
 793  *   data:         double*
 794  */
 795 static void gdnDestroyDouble(gpointer data)
 796 {
 797         free(data);
 798 }
 799
 800
 801 /*
 802  * A GEqualFunc for g_hash_table_new()
 803  *
 804  * Args:
 805  *   a, b          RttKey*
 806  *
 807  * Returns:
 808  *   TRUE if both values are equal
 809  */
 810 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b)
 811 {
 812         const struct RttKey* rkA, * rkB;
 813
 814         rkA= (struct RttKey*) a;
 815         rkB= (struct RttKey*) b;
 816
 817         if (rkA->saddr == rkB->saddr && rkA->daddr == rkB->daddr)
 818         {
 819                 return TRUE;
 820         }
 821         else
 822         {
 823                 return FALSE;
 824         }
 825 }
 826
 827
 828 /*
 829  * Read a file contain minimum round trip time values and fill an array with
 830  * them. The file is formatted as such:
 831  * <host1 IP> <host2 IP> <RTT in milliseconds>
 832  * ip's should be in dotted quad format
 833  *
 834  * Args:
 835  *   rttInfo:      double* rttInfo[RttKey], empty table, will be filled
 836  *   rttStream:      stream from which to read
 837  */
 838 static void readRttInfo(GHashTable* rttInfo, FILE* rttStream)
 839 {
 840         char* line= NULL;
 841         size_t len;
 842         int retval;
 843
 844         positionStream(rttStream);
 845         retval= getline(&line, &len, rttStream);
 846         while(!feof(rttStream))
 847         {
 848                 struct RttKey* rttKey;
 849                 char saddrDQ[20], daddrDQ[20];
 850                 double* rtt;
 851                 char tmp;
 852                 struct in_addr addr;
 853                 unsigned int i;
 854                 struct {
 855                         char* dq;
 856                         size_t offset;
 857                 } loopValues[] = {
 858                         {saddrDQ, offsetof(struct RttKey, saddr)},
 859                         {daddrDQ, offsetof(struct RttKey, daddr)}
 860                 };
 861
 862                 if (retval == -1 && !feof(rttStream))
 863                 {
 864                         g_error(strerror(errno));
 865                 }
 866
 867                 if (line[retval - 1] == '\n')
 868                 {
 869                         line[retval - 1]= '\0';
 870                 }
 871
 872                 rtt= malloc(sizeof(double));
 873                 retval= sscanf(line, " %19s %19s %lf %c", saddrDQ, daddrDQ, rtt,
 874                         &tmp);
 875                 if (retval == EOF)
 876                 {
 877                         g_error(strerror(errno));
 878                 }
 879                 else if (retval != 3)
 880                 {
 881                         g_error("Error parsing RTT file, line was '%s'", line);
 882                 }
 883
 884                 rttKey= malloc(sizeof(struct RttKey));
 885                 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 886                 {
 887                         retval= inet_aton(loopValues[i].dq, &addr);
 888                         if (retval == 0)
 889                         {
 890                                 g_error("Error converting address '%s'", loopValues[i].dq);
 891                         }
 892                         *(uint32_t*) ((void*) rttKey + loopValues[i].offset)=
 893                                 addr.s_addr;
 894                 }
 895
 896                 *rtt/= 1e3;
 897                 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey->saddr,
 898                         rttKey->daddr, *rtt);
 899                 g_hash_table_insert(rttInfo, rttKey, rtt);
 900
 901                 positionStream(rttStream);
 902                 retval= getline(&line, &len, rttStream);
 903         }
 904
 905         if (line)
 906         {
 907                 free(line);
 908         }
 909 }
 910
 911
 912 /*
 913  * Advance stream over empty space, empty lines and lines that begin with '#'
 914  *
 915  * Args:
 916  *   stream:     stream, at exit, will be over the first non-empty character
 917  *               of a line of be at EOF
 918  */
 919 static void positionStream(FILE* stream)
 920 {
 921         int firstChar;
 922         ssize_t retval;
 923         char* line= NULL;
 924         size_t len;
 925
 926         do
 927         {
 928                 firstChar= fgetc(stream);
 929                 if (firstChar == (int) '#')
 930                 {
 931                         retval= getline(&line, &len, stream);
 932                         if (retval == -1)
 933                         {
 934                                 if (feof(stream))
 935                                 {
 936                                         goto outEof;
 937                                 }
 938                                 else
 939                                 {
 940                                         g_error(strerror(errno));
 941                                 }
 942                         }
 943                 }
 944                 else if (firstChar == (int) '\n' || firstChar == (int) ' ' ||
 945                         firstChar == (int) '\t')
 946                 {}
 947                 else if (firstChar == EOF)
 948                 {
 949                         goto outEof;
 950                 }
 951                 else
 952                 {
 953                         break;
 954                 }
 955         } while (true);
 956         retval= ungetc(firstChar, stream);
 957         if (retval == EOF)
 958         {
 959                 g_error("Error: ungetc()");
 960         }
 961
 962 outEof:
 963         if (line)
 964         {
 965                 free(line);
 966         }
 967 }
 968
 969
 970 /*
 971  * A GFunc for g_queue_foreach()
 972  *
 973  * Args:
 974  *   data          Event*, a UDP broadcast event
 975  *   user_data     double*, the running sum
 976  *
 977  * Returns:
 978  *   Adds the time of the event to the sum
 979  */
 980 static void gfSum(gpointer data, gpointer userData)
 981 {
 982         Event* event= (Event*) data;
 983
 984         *(double*) userData+= event->wallTime.seconds + event->wallTime.nanosec /
 985                 1e9;
 986 }
 987
 988
 989 /*
 990  * A GFunc for g_queue_foreach()
 991  *
 992  * Args:
 993  *   data          Event*, a UDP broadcast event
 994  *   user_data     double*, the running sum
 995  *
 996  * Returns:
 997  *   Adds the square of the time of the event to the sum
 998  */
 999 static void gfSumSquares(gpointer data, gpointer userData)
1000 {
1001         Event* event= (Event*) data;
1002
1003         *(double*) userData+= pow(event->wallTime.seconds + event->wallTime.nanosec
1004                 / 1e9, 2.);
1005 }
1006
1007
1008 /*
1009  * Figure out the bin in a histogram to which a value belongs.
1010  *
1011  * This uses exponentially sized bins that go from 0 to infinity.
1012  *
1013  * Args:
1014  *   value:        the value, must be >=0, or else expect the unexpected
1015  *                 (floating point exception)
1016  */
1017 static unsigned int binNum(const double value)
1018 {
1019         if (value == 0)
1020         {
1021                 return 0;
1022         }
1023         else
1024         {
1025                 double result= floor(log(value) / log(binBase)) + (binNb - 1);
1026
1027                 if (result < 0.)
1028                 {
1029                         return 0.;
1030                 }
1031                 else
1032                 {
1033                         return result;
1034                 }
1035         }
1036 }
1037
1038
1039 /*
1040  * Figure out the start of the interval of a bin in a histogram. The starting
1041  * value is included in the interval.
1042  *
1043  * This uses exponentially sized bins that go from 0 to infinity.
1044  *
1045  * Args:
1046  *   binNum:       bin number
1047  */
1048 static double binStart(const unsigned int binNum)
1049 {
1050         g_assert(binNum < binNb);
1051
1052         if (binNum == 0)
1053         {
1054                 return 0;
1055         }
1056         else
1057         {
1058                 return pow(binBase, (double) binNum - (binNb - 1));
1059         }
1060 }
1061
1062
1063 /*
1064  * Figure out the end of the interval of a bin in a histogram. The end value
1065  * is not included in the interval.
1066  *
1067  * This uses exponentially sized bins that go from 0 to infinity.
1068  *
1069  * Args:
1070  *   binNum:       bin number
1071  */
1072 static double binEnd(const unsigned int binNum)
1073 {
1074         g_assert(binNum < binNb);
1075
1076         if (binNum < binNb)
1077         {
1078                 return pow(binBase, (double) binNum - (binNb - 2));
1079         }
1080         else
1081         {
1082                 return INFINITY;
1083         }
1084 }
1085
1086
1087 /*
1088  * Write the analysis-specific graph lines in the gnuplot script.
1089  *
1090  * Args:
1091  *   stream:       stream where to write the data
1092  *   syncState:    container for synchronization data
1093  *   i:            first trace number
1094  *   j:            second trace number, garanteed to be larger than i
1095  */
1096 static void writeAnalysisGraphsPlotsEval(FILE* stream, SyncState* const
1097         syncState, const unsigned int i, const unsigned int j)
1098 {
1099         fprintf(stream,
1100                 "\t\"analysis_eval_hrtt-%2$03d_and_%1$03d.data\" "
1101                         "title \"RTT/2\" with boxes linetype 1 linewidth 3 "
1102                         "linecolor rgb \"black\" fill transparent solid 0.75, \\\n"
1103                 /*"\t\"analysis_eval_tt-%1$03d_to_%2$03d.data\" "
1104                         "title \"%1$u to %2$u\" with boxes linetype 1 linewidth 3 "
1105                         "linecolor rgb \"black\" fill transparent solid 0.5, \\\n"
1106                 "\t\"analysis_eval_tt-%2$03d_to_%1$03d.data\" "
1107                         "title \"%2$u to %1$u\" with boxes linetype 1 linewidth 3 "
1108                         "linecolor rgb \"black\" fill transparent solid 0.25, \\\n"*/
1109                         , i, j);
1110         /*
1111         fprintf(stream,
1112                 "\t\"analysis_eval_hrtt-%2$03d_and_%1$03d.data\" "
1113                         "title \"RTT/2\" with linespoints linetype 1 linewidth 3 "
1114                         "linecolor rgb \"black\", \\\n"
1115                 "\t\"analysis_eval_tt-%1$03d_to_%2$03d.data\" "
1116                         "title \"%1$u to %2$u\" with linespoints linetype 1 linewidth 3 "
1117                         "linecolor rgb \"gray70\", \\\n"
1118                 "\t\"analysis_eval_tt-%2$03d_to_%1$03d.data\" "
1119                         "title \"%2$u to %1$u\" with linespoints linetype 1 linewidth 3 "
1120                         "linecolor rgb \"gray40\", \\\n", i, j);
1121 */
1122 }
1123
1124
1125 /*
1126  * Write the analysis-specific options in the gnuplot script.
1127  *
1128  * Args:
1129  *   stream:       stream where to write the data
1130  *   syncState:    container for synchronization data
1131  *   i:            first trace number
1132  *   j:            second trace number, garanteed to be larger than i
1133  */
1134 static void writeAnalysisGraphsOptionsEval(FILE* stream, SyncState*
1135     const syncState, const unsigned int i, const unsigned int j)
1136 {
1137         fprintf(stream,
1138                 "set xlabel \"Message Latency (s)\"\n"
1139                 "set ylabel \"Proportion of messages per second\"\n");
1140 }