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, k;
 694         unsigned int totInversion= 0, totTooFast= 0, totNoInfo= 0, totTotal= 0;
 695         int charNb;
 696
 697         if (!syncState->stats)
 698         {
 699                 return;
 700         }
 701
 702         analysisData= (AnalysisDataEval*) syncState->analysisData;
 703
 704         printf("Synchronization evaluation analysis stats:\n");
 705         if (analysisData->stats->broadcastNb)
 706         {
 707                 printf("\tsum of broadcast differential delays: %g\n",
 708                         analysisData->stats->broadcastDiffSum);
 709                 printf("\taverage broadcast differential delays: %g\n",
 710                         analysisData->stats->broadcastDiffSum /
 711                         analysisData->stats->broadcastNb);
 712         }
 713
 714         printf("\tIndividual evaluation:\n"
 715                 "\t\tTrace pair  Inversions        Too fast          No RTT info  Total\n");
 716
 717         for (i= 0; i < syncState->traceNb; i++)
 718         {
 719                 for (j= i + 1; j < syncState->traceNb; j++)
 720                 {
 721                         MessageStats* messageStats;
 722                         struct {
 723                                 unsigned int t1, t2;
 724                         } loopValues[]= {
 725                                 {i, j},
 726                                 {j, i}
 727                         };
 728
 729                         for (k= 0; k < sizeof(loopValues) / sizeof(*loopValues); k++)
 730                         {
 731                                 messageStats=
 732                                         &analysisData->stats->messageStats[loopValues[k].t1][loopValues[k].t2];
 733
 734                                 printf("\t\t%3d - %-3d   ", loopValues[k].t1, loopValues[k].t2);
 735                                 printf("%u (%u%%)%n", messageStats->inversionNb, (unsigned
 736                                                 int) ceil((double) messageStats->inversionNb /
 737                                                 messageStats->total * 100), &charNb);
 738                                 printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
 739                                 printf("%u (%u%%)%n", messageStats->tooFastNb, (unsigned int)
 740                                         ceil((double) messageStats->tooFastNb /
 741                                                 messageStats->total * 100), &charNb);
 742                                 printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1:
 743                                         1, " ", messageStats->noRTTInfoNb, messageStats->total);
 744
 745                                 totInversion+= messageStats->inversionNb;
 746                                 totTooFast+= messageStats->tooFastNb;
 747                                 totNoInfo+= messageStats->noRTTInfoNb;
 748                                 totTotal+= messageStats->total;
 749                         }
 750                 }
 751         }
 752
 753         printf("\t\t  total     ");
 754         printf("%u (%u%%)%n", totInversion, (unsigned int) ceil((double)
 755                         totInversion / totTotal * 100), &charNb);
 756         printf("%*s", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ");
 757         printf("%u (%u%%)%n", totTooFast, (unsigned int) ceil((double) totTooFast
 758                         / totTotal * 100), &charNb);
 759         printf("%*s%-10u   %u\n", 17 - charNb > 0 ? 17 - charNb + 1: 1, " ",
 760                 totNoInfo, totTotal);
 761
 762         printf("\tRound-trip times:\n"
 763                 "\t\tHost pair                          RTT from exchanges  RTTs from file (ms)\n");
 764         g_hash_table_foreach(analysisData->stats->exchangeRtt,
 765                 &ghfPrintExchangeRtt, analysisData->rttInfo);
 766 }
 767
 768
 769 /*
 770  * A GHFunc for g_hash_table_foreach()
 771  *
 772  * Args:
 773  *   key:          RttKey* where saddr < daddr
 774  *   value:        double*, RTT estimated from exchanges
 775  *   user_data     GHashTable* rttInfo
 776  */
 777 static void ghfPrintExchangeRtt(gpointer key, gpointer value, gpointer user_data)
 778 {
 779         char addr1[16], addr2[16];
 780         struct RttKey* rttKey1= key;
 781         struct RttKey rttKey2= {rttKey1->daddr, rttKey1->saddr};
 782         double* fileRtt1, *fileRtt2;
 783         GHashTable* rttInfo= user_data;
 784
 785         convertIP(addr1, rttKey1->saddr);
 786         convertIP(addr2, rttKey1->daddr);
 787
 788         fileRtt1= g_hash_table_lookup(rttInfo, rttKey1);
 789         fileRtt2= g_hash_table_lookup(rttInfo, &rttKey2);
 790
 791         printf("\t\t(%15s, %-15s) %-18.3f  ", addr1, addr2, *(double*) value * 1e3);
 792
 793         if (fileRtt1 || fileRtt2)
 794         {
 795                 if (fileRtt1)
 796                 {
 797                         printf("%.3f", *fileRtt1 * 1e3);
 798                 }
 799                 if (fileRtt1 && fileRtt2)
 800                 {
 801                         printf(", ");
 802                 }
 803                 if (fileRtt2)
 804                 {
 805                         printf("%.3f", *fileRtt2 * 1e3);
 806                 }
 807         }
 808         else
 809         {
 810                 printf("-");
 811         }
 812         printf("\n");
 813 }
 814
 815
 816 /*
 817  * A GHashFunc for g_hash_table_new()
 818  *
 819  * Args:
 820  *    key        struct RttKey*
 821  */
 822 static guint ghfRttKeyHash(gconstpointer key)
 823 {
 824         struct RttKey* rttKey;
 825         uint32_t a, b, c;
 826
 827         rttKey= (struct RttKey*) key;
 828
 829         a= rttKey->saddr;
 830         b= rttKey->daddr;
 831         c= 0;
 832         final(a, b, c);
 833
 834         return c;
 835 }
 836
 837
 838 /*
 839  * A GDestroyNotify function for g_hash_table_new_full()
 840  *
 841  * Args:
 842  *   data:         struct RttKey*
 843  */
 844 static void gdnDestroyRttKey(gpointer data)
 845 {
 846         free(data);
 847 }
 848
 849
 850 /*
 851  * A GDestroyNotify function for g_hash_table_new_full()
 852  *
 853  * Args:
 854  *   data:         double*
 855  */
 856 static void gdnDestroyDouble(gpointer data)
 857 {
 858         free(data);
 859 }
 860
 861
 862 /*
 863  * A GEqualFunc for g_hash_table_new()
 864  *
 865  * Args:
 866  *   a, b          RttKey*
 867  *
 868  * Returns:
 869  *   TRUE if both values are equal
 870  */
 871 static gboolean gefRttKeyEqual(gconstpointer a, gconstpointer b)
 872 {
 873         const struct RttKey* rkA, * rkB;
 874
 875         rkA= (struct RttKey*) a;
 876         rkB= (struct RttKey*) b;
 877
 878         if (rkA->saddr == rkB->saddr && rkA->daddr == rkB->daddr)
 879         {
 880                 return TRUE;
 881         }
 882         else
 883         {
 884                 return FALSE;
 885         }
 886 }
 887
 888
 889 /*
 890  * Read a file contain minimum round trip time values and fill an array with
 891  * them. The file is formatted as such:
 892  * <host1 IP> <host2 IP> <RTT in milliseconds>
 893  * ip's should be in dotted quad format
 894  *
 895  * Args:
 896  *   rttInfo:      double* rttInfo[RttKey], empty table, will be filled
 897  *   rttStream:      stream from which to read
 898  */
 899 static void readRttInfo(GHashTable* rttInfo, FILE* rttStream)
 900 {
 901         char* line= NULL;
 902         size_t len;
 903         int retval;
 904
 905         positionStream(rttStream);
 906         retval= getline(&line, &len, rttStream);
 907         while(!feof(rttStream))
 908         {
 909                 struct RttKey* rttKey;
 910                 char saddrDQ[20], daddrDQ[20];
 911                 double* rtt;
 912                 char tmp;
 913                 struct in_addr addr;
 914                 unsigned int i;
 915                 struct {
 916                         char* dq;
 917                         size_t offset;
 918                 } loopValues[] = {
 919                         {saddrDQ, offsetof(struct RttKey, saddr)},
 920                         {daddrDQ, offsetof(struct RttKey, daddr)}
 921                 };
 922
 923                 if (retval == -1 && !feof(rttStream))
 924                 {
 925                         g_error(strerror(errno));
 926                 }
 927
 928                 if (line[retval - 1] == '\n')
 929                 {
 930                         line[retval - 1]= '\0';
 931                 }
 932
 933                 rtt= malloc(sizeof(double));
 934                 retval= sscanf(line, " %19s %19s %lf %c", saddrDQ, daddrDQ, rtt,
 935                         &tmp);
 936                 if (retval == EOF)
 937                 {
 938                         g_error(strerror(errno));
 939                 }
 940                 else if (retval != 3)
 941                 {
 942                         g_error("Error parsing RTT file, line was '%s'", line);
 943                 }
 944
 945                 rttKey= malloc(sizeof(struct RttKey));
 946                 for (i= 0; i < sizeof(loopValues) / sizeof(*loopValues); i++)
 947                 {
 948                         retval= inet_aton(loopValues[i].dq, &addr);
 949                         if (retval == 0)
 950                         {
 951                                 g_error("Error converting address '%s'", loopValues[i].dq);
 952                         }
 953                         *(uint32_t*) ((void*) rttKey + loopValues[i].offset)=
 954                                 addr.s_addr;
 955                 }
 956
 957                 *rtt/= 1e3;
 958                 g_debug("rttInfo, Inserting (%u, %u)->(%f)", rttKey->saddr,
 959                         rttKey->daddr, *rtt);
 960                 g_hash_table_insert(rttInfo, rttKey, rtt);
 961
 962                 positionStream(rttStream);
 963                 retval= getline(&line, &len, rttStream);
 964         }
 965
 966         if (line)
 967         {
 968                 free(line);
 969         }
 970 }
 971
 972
 973 /*
 974  * Advance stream over empty space, empty lines and lines that begin with '#'
 975  *
 976  * Args:
 977  *   stream:     stream, at exit, will be over the first non-empty character
 978  *               of a line of be at EOF
 979  */
 980 static void positionStream(FILE* stream)
 981 {
 982         int firstChar;
 983         ssize_t retval;
 984         char* line= NULL;
 985         size_t len;
 986
 987         do
 988         {
 989                 firstChar= fgetc(stream);
 990                 if (firstChar == (int) '#')
 991                 {
 992                         retval= getline(&line, &len, stream);
 993                         if (retval == -1)
 994                         {
 995                                 if (feof(stream))
 996                                 {
 997                                         goto outEof;
 998                                 }
 999                                 else
1000                                 {
1001                                         g_error(strerror(errno));
1002                                 }
1003                         }
1004                 }
1005                 else if (firstChar == (int) '\n' || firstChar == (int) ' ' ||
1006                         firstChar == (int) '\t')
1007                 {}
1008                 else if (firstChar == EOF)
1009                 {
1010                         goto outEof;
1011                 }
1012                 else
1013                 {
1014                         break;
1015                 }
1016         } while (true);
1017         retval= ungetc(firstChar, stream);
1018         if (retval == EOF)
1019         {
1020                 g_error("Error: ungetc()");
1021         }
1022
1023 outEof:
1024         if (line)
1025         {
1026                 free(line);
1027         }
1028 }
1029
1030
1031 /*
1032  * A GFunc for g_queue_foreach()
1033  *
1034  * Args:
1035  *   data          Event*, a UDP broadcast event
1036  *   user_data     double*, the running sum
1037  *
1038  * Returns:
1039  *   Adds the time of the event to the sum
1040  */
1041 static void gfSum(gpointer data, gpointer userData)
1042 {
1043         Event* event= (Event*) data;
1044
1045         *(double*) userData+= event->wallTime.seconds + event->wallTime.nanosec /
1046                 1e9;
1047 }
1048
1049
1050 /*
1051  * A GFunc for g_queue_foreach()
1052  *
1053  * Args:
1054  *   data          Event*, a UDP broadcast event
1055  *   user_data     double*, the running sum
1056  *
1057  * Returns:
1058  *   Adds the square of the time of the event to the sum
1059  */
1060 static void gfSumSquares(gpointer data, gpointer userData)
1061 {
1062         Event* event= (Event*) data;
1063
1064         *(double*) userData+= pow(event->wallTime.seconds + event->wallTime.nanosec
1065                 / 1e9, 2.);
1066 }
1067
1068
1069 /*
1070  * Update a struct Bins according to a new value
1071  *
1072  * Args:
1073  *   bins:         the structure containing bins to build a histrogram
1074  *   value:        the new value
1075  */
1076 static void hitBin(struct Bins* const bins, const double value)
1077 {
1078         unsigned int binN= binNum(value);
1079
1080         if (binN < bins->min)
1081         {
1082                 bins->min= binN;
1083         }
1084         else if (binN > bins->max)
1085         {
1086                 bins->max= binN;
1087         }
1088
1089         bins->total++;
1090
1091         bins->bin[binN]++;
1092 }
1093
1094
1095 /*
1096  * Figure out the bin in a histogram to which a value belongs.
1097  *
1098  * This uses exponentially sized bins that go from 0 to infinity.
1099  *
1100  * Args:
1101  *   value:        in the range -INFINITY to INFINITY
1102  *
1103  * Returns:
1104  *   The number of the bin in a struct Bins.bin
1105  */
1106 static unsigned int binNum(const double value)
1107 {
1108         if (value <= 0)
1109         {
1110                 return 0;
1111         }
1112         else if (value < binEnd(1))
1113         {
1114                 return 1;
1115         }
1116         else if (value >= binStart(BIN_NB - 1))
1117         {
1118                 return BIN_NB - 1;
1119         }
1120         else
1121         {
1122                 return floor(log(value) / log(binBase)) + BIN_NB + 1;
1123         }
1124 }
1125
1126
1127 /*
1128  * Figure out the start of the interval of a bin in a histogram. See struct
1129  * Bins.
1130  *
1131  * This uses exponentially sized bins that go from 0 to infinity.
1132  *
1133  * Args:
1134  *   binNum:       bin number
1135  *
1136  * Return:
1137  *   The start of the interval, this value is included in the interval (except
1138  *   for -INFINITY, naturally)
1139  */
1140 static double binStart(const unsigned int binNum)
1141 {
1142         g_assert_cmpuint(binNum, <, BIN_NB);
1143
1144         if (binNum == 0)
1145         {
1146                 return -INFINITY;
1147         }
1148         else if (binNum == 1)
1149         {
1150                 return 0.;
1151         }
1152         else
1153         {
1154                 return pow(binBase, (double) binNum - BIN_NB + 1);
1155         }
1156 }
1157
1158
1159 /*
1160  * Figure out the end of the interval of a bin in a histogram. See struct
1161  * Bins.
1162  *
1163  * This uses exponentially sized bins that go from 0 to infinity.
1164  *
1165  * Args:
1166  *   binNum:       bin number
1167  *
1168  * Return:
1169  *   The end of the interval, this value is not included in the interval
1170  */
1171 static double binEnd(const unsigned int binNum)
1172 {
1173         g_assert_cmpuint(binNum, <, BIN_NB);
1174
1175         if (binNum == 0)
1176         {
1177                 return 0.;
1178         }
1179         else if (binNum < BIN_NB - 1)
1180         {
1181                 return pow(binBase, (double) binNum - BIN_NB + 2);
1182         }
1183         else
1184         {
1185                 return INFINITY;
1186         }
1187 }