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