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