org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/synchronization/SyncAlgorithmFullyIncremental.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Geneviève Bastien - Initial implementation and API
  11  *   Francis Giraldeau - Transform computation using synchronization graph
  12  *******************************************************************************/
  13
  14 package org.eclipse.linuxtools.tmf.core.synchronization;
  15
  16 import java.io.IOException;
  17 import java.io.ObjectOutputStream;
  18 import java.io.Serializable;
  19 import java.math.BigDecimal;
  20 import java.math.MathContext;
  21 import java.util.Collection;
  22 import java.util.LinkedHashMap;
  23 import java.util.LinkedList;
  24 import java.util.List;
  25 import java.util.Map;
  26
  27 import org.eclipse.linuxtools.internal.tmf.core.synchronization.graph.SyncSpanningTree;
  28 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  29 import org.eclipse.linuxtools.tmf.core.event.matching.TmfEventDependency;
  30 import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
  31 import org.eclipse.linuxtools.tmf.core.trace.ITmfTrace;
  32
  33 /**
  34  * Class implementing fully incremental trace synchronization approach as
  35  * described in
  36  *
  37  * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
  38  * "Streaming Mode Incremental Clock Synchronization"
  39  *
  40  * Since the algorithm itself applies to two traces, it is implemented in a
  41  * private class, while this public class manages the synchronization between
  42  * all traces.
  43  *
  44  * @author Geneviève Bastien
  45  * @since 3.0
  46  */
  47 public class SyncAlgorithmFullyIncremental extends SynchronizationAlgorithm {
  48
  49     /**
  50      * Auto-generated serial UID
  51      */
  52     private static final long serialVersionUID = -1782788842774838830L;
  53
  54     private static final MathContext fMc = MathContext.DECIMAL128;
  55
  56     /** @Serial */
  57     private final List<ConvexHull> fSyncs;
  58
  59     private SyncSpanningTree fTree = null;
  60
  61     /**
  62      * Initialization of the attributes
  63      */
  64     public SyncAlgorithmFullyIncremental() {
  65         fSyncs = new LinkedList<>();
  66     }
  67
  68     /**
  69      * Function called after all matching has been done, to do any post-match
  70      * treatment. For this class, it calculates stats, while the data is
  71      * available
  72      */
  73     @Override
  74     public void matchingEnded() {
  75         getStats();
  76     }
  77
  78     @Override
  79     public void init(Collection<ITmfTrace> traces) {
  80         ITmfTrace[] traceArr = traces.toArray(new ITmfTrace[traces.size()]);
  81         fSyncs.clear();
  82         /* Create a convex hull for all trace pairs */
  83         // FIXME: is it necessary to make ConvexHull for every pairs up-front?
  84         // The ConvexHull seems to be created on the fly in processMatch().
  85         for (int i = 0; i < traceArr.length; i++) {
  86             for (int j = i + 1; j < traceArr.length; j++) {
  87                 ConvexHull algo = new ConvexHull(traceArr[i].getHostId(), traceArr[j].getHostId());
  88                 fSyncs.add(algo);
  89             }
  90         }
  91     }
  92
  93     @Override
  94     protected void processMatch(TmfEventDependency match) {
  95         String host1 = match.getSourceEvent().getTrace().getHostId();
  96         String host2 = match.getDestinationEvent().getTrace().getHostId();
  97
  98         /* Process only if source and destination are different */
  99         if (host1.equals(host2)) {
 100             return;
 101         }
 102
 103         /* Check if a convex hull algorithm already exists for these 2 hosts */
 104         ConvexHull algo = null;
 105         for (ConvexHull traceSync : fSyncs) {
 106             if (traceSync.isForHosts(host1, host2)) {
 107                 algo = traceSync;
 108             }
 109         }
 110         if (algo == null) {
 111             algo = new ConvexHull(host1, host2);
 112             fSyncs.add(algo);
 113         }
 114         algo.processMatch(match);
 115         invalidateSyncGraph();
 116     }
 117
 118     private void invalidateSyncGraph() {
 119         fTree = null;
 120     }
 121
 122     @Override
 123     public ITmfTimestampTransform getTimestampTransform(ITmfTrace trace) {
 124         return getTimestampTransform(trace.getHostId());
 125     }
 126
 127     @Override
 128     public ITmfTimestampTransform getTimestampTransform(String hostId) {
 129         SyncSpanningTree tree = getSyncTree();
 130         return tree.getTimestampTransform(hostId);
 131     }
 132
 133     /**
 134      * Each convex hull computes the synchronization between 2 given hosts. A
 135      * synchronization can be done on multiple hosts that may not all
 136      * communicate with each other. We must use another algorithm to determine
 137      * which host will be the reference node and what synchronization formula
 138      * will be used between each host and this reference node.
 139      *
 140      * For example, take traces a, b and c where a and c talk to b but do not
 141      * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
 142      * the formulae between their 2 traces, but if a is the reference node, then
 143      * the resulting formula of c would be the composition of {@literal a <-> b}
 144      * and {@literal b <-> c}
 145      *
 146      * @return The synchronization spanning tree for this synchronization
 147      */
 148     private SyncSpanningTree getSyncTree() {
 149         if (fTree == null) {
 150             fTree = new SyncSpanningTree();
 151             for (ConvexHull traceSync : fSyncs) {
 152                 SyncQuality q = traceSync.getQuality();
 153                 if (q == SyncQuality.ACCURATE || q == SyncQuality.APPROXIMATE) {
 154                     String from = traceSync.getReferenceHost();
 155                     String to = traceSync.getOtherHost();
 156                     fTree.addSynchronization(from, to, traceSync.getTimestampTransform(to), traceSync.getAccuracy());
 157                 }
 158             }
 159         }
 160         return fTree;
 161     }
 162
 163     @Override
 164     public SyncQuality getSynchronizationQuality(ITmfTrace trace1, ITmfTrace trace2) {
 165         for (ConvexHull traceSync : fSyncs) {
 166             if (traceSync.isForHosts(trace1.getHostId(), trace2.getHostId())) {
 167                 return traceSync.getQuality();
 168             }
 169         }
 170         return SyncQuality.ABSENT;
 171     }
 172
 173     @Override
 174     public boolean isTraceSynced(String hostId) {
 175         ITmfTimestampTransform t = getTimestampTransform(hostId);
 176         return !t.equals(TimestampTransformFactory.getDefaultTransform());
 177     }
 178
 179     @Override
 180     public Map<String, Map<String, Object>> getStats() {
 181         /*
 182          * TODO: Stats, while still accurate, may be misleading now that the
 183          * sync tree changes synchronization formula. The stats should use the
 184          * tree instead
 185          */
 186         Map<String, Map<String, Object>> statmap = new LinkedHashMap<>();
 187         for (ConvexHull traceSync : fSyncs) {
 188             statmap.put(traceSync.getReferenceHost() + " <==> " + traceSync.getOtherHost(), traceSync.getStats()); //$NON-NLS-1$
 189         }
 190         return statmap;
 191     }
 192
 193     @Override
 194     public String toString() {
 195         StringBuilder b = new StringBuilder();
 196         b.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
 197         b.append(fSyncs);
 198         return b.toString();
 199     }
 200
 201     /**
 202      * This is the actual synchronization algorithm between two traces using
 203      * convex hull
 204      */
 205     private class ConvexHull implements Serializable {
 206
 207         private static final long serialVersionUID = 8309351175030935291L;
 208
 209         /**
 210          * The list of meaningful points on the upper hull (received by the
 211          * reference trace, below in a graph)
 212          */
 213         private final LinkedList<SyncPoint> fUpperBoundList = new LinkedList<>();
 214
 215         /**
 216          * The list of meaninful points on the lower hull (sent by the reference
 217          * trace, above in a graph)
 218          */
 219         private final LinkedList<SyncPoint> fLowerBoundList = new LinkedList<>();
 220
 221         /** Points forming the line with maximum slope */
 222         private final SyncPoint[] fLmax;
 223
 224         /** Points forming the line with minimum slope */
 225         private final SyncPoint[] fLmin;
 226
 227         /**
 228          * Slopes and ordinate at origin of respectively fLmin, fLmax and the
 229          * bisector
 230          */
 231         private BigDecimal fAlphamin, fBetamax, fAlphamax, fBetamin, fAlpha, fBeta;
 232
 233         private int fNbMatches, fNbAccurateMatches;
 234         private String fReferenceHost = "", fOtherHost = ""; //$NON-NLS-1$//$NON-NLS-2$
 235         private SyncQuality fQuality;
 236
 237         private Map<String, Object> fStats = new LinkedHashMap<>();
 238
 239         /**
 240          * Initialization of the attributes
 241          *
 242          * @param host1
 243          *            ID of the first host
 244          * @param host2
 245          *            ID of the second host
 246          */
 247         public ConvexHull(String host1, String host2) {
 248             if (host1.compareTo(host2) > 0) {
 249                 fReferenceHost = host2;
 250                 fOtherHost = host1;
 251             } else {
 252                 fReferenceHost = host1;
 253                 fOtherHost = host2;
 254             }
 255             fLmax = new SyncPoint[2];
 256             fLmin = new SyncPoint[2];
 257             fAlpha = BigDecimal.ONE;
 258             fAlphamax = BigDecimal.ONE;
 259             fAlphamin = BigDecimal.ONE;
 260             fBeta = BigDecimal.ZERO;
 261             fBetamax = BigDecimal.ZERO;
 262             fBetamin = BigDecimal.ZERO;
 263             fNbMatches = 0;
 264             fNbAccurateMatches = 0;
 265             fQuality = SyncQuality.ABSENT; // default quality
 266         }
 267
 268         protected void processMatch(TmfEventDependency match) {
 269
 270             LinkedList<SyncPoint> boundList, otherBoundList;
 271
 272             SyncPoint[] line, otherLine;
 273             SyncPoint p;
 274             int inversionFactor = 1;
 275             boolean qualify = false;
 276             fNbMatches++;
 277
 278             /* Initialize data depending on the which hull the match is part of */
 279             if (match.getSourceEvent().getTrace().getHostId().compareTo(match.getDestinationEvent().getTrace().getHostId()) > 0) {
 280                 boundList = fUpperBoundList;
 281                 otherBoundList = fLowerBoundList;
 282                 line = fLmin;
 283                 otherLine = fLmax;
 284                 p = new SyncPoint(match.getDestinationEvent(), match.getSourceEvent());
 285                 inversionFactor = 1;
 286             } else {
 287                 boundList = fLowerBoundList;
 288                 otherBoundList = fUpperBoundList;
 289                 line = fLmax;
 290                 otherLine = fLmin;
 291                 p = new SyncPoint(match.getSourceEvent(), match.getDestinationEvent());
 292                 inversionFactor = -1;
 293             }
 294
 295             /*
 296              * Does the message qualify for the hull, or is in on the wrong side
 297              * of the reference line
 298              */
 299             if ((line[0] == null) || (line[1] == null) || (p.crossProduct(line[0], line[1]) * inversionFactor > 0)) {
 300                 /*
 301                  * If message qualifies, verify if points need to be removed
 302                  * from the hull and add the new point as the maximum reference
 303                  * point for the line. Also clear the stats that are not good
 304                  * anymore
 305                  */
 306                 fNbAccurateMatches++;
 307                 qualify = true;
 308                 removeUselessPoints(p, boundList, inversionFactor);
 309                 line[1] = p;
 310                 fStats.clear();
 311             }
 312
 313             /*
 314              * Adjust the boundary of the reference line and if one of the
 315              * reference point of the other line was removed from the hull, also
 316              * adjust the other line
 317              */
 318             adjustBound(line, otherBoundList, inversionFactor);
 319             if ((otherLine[1] != null) && !boundList.contains(otherLine[0])) {
 320                 adjustBound(otherLine, boundList, inversionFactor * -1);
 321             }
 322
 323             if (qualify) {
 324                 approximateSync();
 325             }
 326
 327         }
 328
 329         /**
 330          * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
 331          * and approximation of the synchronization at this time
 332          */
 333         private void approximateSync() {
 334
 335             /**
 336              * Line slopes functions
 337              *
 338              * Lmax = alpha_max T + beta_min
 339              *
 340              * Lmin = alpha_min T + beta_max
 341              */
 342             if ((fLmax[0] != null) || (fLmin[0] != null)) {
 343                 fAlphamax = fLmax[1].getAlpha(fLmax[0]);
 344                 fBetamin = fLmax[1].getBeta(fAlphamax);
 345                 fAlphamin = fLmin[1].getAlpha(fLmin[0]);
 346                 fBetamax = fLmin[1].getBeta(fAlphamin);
 347                 fAlpha = fAlphamax.add(fAlphamin).divide(BigDecimal.valueOf(2), fMc);
 348                 fBeta = fBetamin.add(fBetamax).divide(BigDecimal.valueOf(2), fMc);
 349                 if ((fLmax[0] == null) || (fLmin[0] == null)) {
 350                     setQuality(SyncQuality.APPROXIMATE);
 351                 }
 352                 else if (fAlphamax.compareTo(fAlphamin) > 0) {
 353                     setQuality(SyncQuality.ACCURATE);
 354                 } else {
 355                     /* Lines intersect, not good */
 356                     setQuality(SyncQuality.FAIL);
 357                 }
 358             } else if (((fLmax[0] == null) && (fLmin[1] == null))
 359                     || ((fLmax[1] == null) && (fLmin[0] == null))) {
 360                 /* Either there is no upper hull point or no lower hull */
 361                 setQuality(SyncQuality.INCOMPLETE);
 362             }
 363         }
 364
 365         /*
 366          * Verify if the line should be adjusted to be more accurate give the
 367          * hull
 368          */
 369         private void adjustBound(SyncPoint[] line, LinkedList<SyncPoint> otherBoundList, int inversionFactor) {
 370             SyncPoint minPoint = null, nextPoint;
 371             boolean finishedSearch = false;
 372
 373             /*
 374              * Find in the other bound, the origin point of the line, start from
 375              * the beginning if the point was lost
 376              */
 377             int i = Math.max(0, otherBoundList.indexOf(line[0]));
 378
 379             while ((i < otherBoundList.size() - 1) && !finishedSearch) {
 380                 minPoint = otherBoundList.get(i);
 381                 nextPoint = otherBoundList.get(i + 1);
 382
 383                 /*
 384                  * If the rotation (cross-product) is not optimal, move to next
 385                  * point as reference for the line (if available)
 386                  *
 387                  * Otherwise, the current minPoint is the minPoint of the line
 388                  */
 389                 if (minPoint.crossProduct(nextPoint, line[1]) * inversionFactor > 0) {
 390                     if (nextPoint.getTimeX() < line[1].getTimeX()) {
 391                         i++;
 392                     } else {
 393                         line[0] = null;
 394                         finishedSearch = true;
 395                     }
 396                 } else {
 397                     line[0] = minPoint;
 398                     finishedSearch = true;
 399                 }
 400             }
 401
 402             if (line[0] == null) {
 403                 line[0] = minPoint;
 404             }
 405
 406             /* Make sure point 0 is before point 1 */
 407             if ((line[0] != null) && (line[0].getTimeX() > line[1].getTimeX())) {
 408                 line[0] = null;
 409             }
 410         }
 411
 412         /*
 413          * When a point qualifies to be in a hull, we verify if any of the
 414          * existing points need to be removed from the hull
 415          */
 416         private void removeUselessPoints(final SyncPoint p, final LinkedList<SyncPoint> boundList, final int inversionFactor) {
 417
 418             boolean checkRemove = true;
 419
 420             while (checkRemove && boundList.size() >= 2) {
 421                 if (p.crossProduct(boundList.get(boundList.size() - 2), boundList.getLast()) * inversionFactor > 0) {
 422                     boundList.removeLast();
 423                 } else {
 424                     checkRemove = false;
 425                 }
 426             }
 427             boundList.addLast(p);
 428         }
 429
 430         public ITmfTimestampTransform getTimestampTransform(String hostId) {
 431             if (hostId.equals(fOtherHost) && (getQuality() == SyncQuality.ACCURATE || getQuality() == SyncQuality.APPROXIMATE || getQuality() == SyncQuality.FAIL)) {
 432                 /* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
 433                 return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
 434             }
 435             return TimestampTransformFactory.getDefaultTransform();
 436         }
 437
 438         public SyncQuality getQuality() {
 439             return fQuality;
 440         }
 441
 442         public BigDecimal getAccuracy() {
 443             return fAlphamax.subtract(fAlphamin);
 444         }
 445
 446         public Map<String, Object> getStats() {
 447             if (fStats.size() == 0) {
 448                 String syncQuality;
 449                 switch (getQuality()) {
 450                 case ABSENT:
 451                     syncQuality = Messages.SyncAlgorithmFullyIncremental_absent;
 452                     break;
 453                 case ACCURATE:
 454                     syncQuality = Messages.SyncAlgorithmFullyIncremental_accurate;
 455                     break;
 456                 case APPROXIMATE:
 457                     syncQuality = Messages.SyncAlgorithmFullyIncremental_approx;
 458                     break;
 459                 case INCOMPLETE:
 460                     syncQuality = Messages.SyncAlgorithmFullyIncremental_incomplete;
 461                     break;
 462                 case FAIL:
 463                 default:
 464                     syncQuality = Messages.SyncAlgorithmFullyIncremental_fail;
 465                     break;
 466                 }
 467
 468                 fStats.put(Messages.SyncAlgorithmFullyIncremental_refhost, fReferenceHost);
 469                 fStats.put(Messages.SyncAlgorithmFullyIncremental_otherhost, fOtherHost);
 470                 fStats.put(Messages.SyncAlgorithmFullyIncremental_quality, syncQuality);
 471                 fStats.put(Messages.SyncAlgorithmFullyIncremental_alpha, fAlpha);
 472                 fStats.put(Messages.SyncAlgorithmFullyIncremental_beta, fBeta);
 473                 fStats.put(Messages.SyncAlgorithmFullyIncremental_ub, (fUpperBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fUpperBoundList.size());
 474                 fStats.put(Messages.SyncAlgorithmFullyIncremental_lb, (fLowerBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fLowerBoundList.size());
 475                 fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, getAccuracy().doubleValue());
 476                 fStats.put(Messages.SyncAlgorithmFullyIncremental_nbmatch, (fNbMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbMatches);
 477                 fStats.put(Messages.SyncAlgorithmFullyIncremental_nbacc, (fNbAccurateMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbAccurateMatches);
 478                 fStats.put(Messages.SyncAlgorithmFullyIncremental_refformula, Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost);
 479                 fStats.put(Messages.SyncAlgorithmFullyIncremental_otherformula, fAlpha + Messages.SyncAlgorithmFullyIncremental_mult + Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost + Messages.SyncAlgorithmFullyIncremental_add + fBeta);
 480             }
 481             return fStats;
 482
 483         }
 484
 485         public String getReferenceHost() {
 486             return fReferenceHost;
 487         }
 488
 489         public String getOtherHost() {
 490             return fOtherHost;
 491         }
 492
 493         public boolean isForHosts(String hostId1, String hostId2) {
 494             return ((fReferenceHost.equals(hostId1) && fOtherHost.equals(hostId2)) || (fReferenceHost.equals(hostId2) && fOtherHost.equals(hostId1)));
 495         }
 496
 497         private void writeObject(ObjectOutputStream s)
 498                 throws IOException {
 499             /*
 500              * Remove calculation data because most of it is not serializable.
 501              * We have the statistics anyway
 502              */
 503             fUpperBoundList.clear();
 504             fLowerBoundList.clear();
 505             fLmin[0] = null;
 506             fLmin[1] = null;
 507             fLmax[0] = null;
 508             fLmax[1] = null;
 509             s.defaultWriteObject();
 510         }
 511
 512         @SuppressWarnings("nls")
 513         @Override
 514         public String toString() {
 515             StringBuilder b = new StringBuilder();
 516             b.append("Between " + fReferenceHost + " and " + fOtherHost + " [");
 517             b.append(" alpha " + fAlpha + " beta " + fBeta + " ]");
 518             return b.toString();
 519         }
 520
 521         private void setQuality(SyncQuality fQuality) {
 522             this.fQuality = fQuality;
 523         }
 524
 525     }
 526
 527     /**
 528      * Private class representing a point to synchronize on a graph. The x axis
 529      * is the timestamp of the event from the reference trace while the y axis
 530      * is the timestamp of the event on the other trace
 531      */
 532     private class SyncPoint {
 533         private final ITmfTimestamp x, y;
 534
 535         public SyncPoint(ITmfEvent ex, ITmfEvent ey) {
 536             x = ex.getTimestamp();
 537             y = ey.getTimestamp();
 538         }
 539
 540         public long getTimeX() {
 541             return x.getValue();
 542         }
 543
 544         /**
 545          * Calculate a cross product of 3 points:
 546          *
 547          * If the cross-product < 0, then p, pa, pb are clockwise
 548          *
 549          * If the cross-product > 0, then p, pa, pb are counter-clockwise
 550          *
 551          * If cross-product == 0, then they are in a line
 552          *
 553          * @param pa
 554          *            First point
 555          * @param pb
 556          *            Second point
 557          * @return The cross product
 558          */
 559         public long crossProduct(SyncPoint pa, SyncPoint pb) {
 560             long cp = ((pa.x.getValue() - x.getValue()) * (pb.y.getValue() - y.getValue()) - (pa.y.getValue() - y.getValue()) * (pb.x.getValue() - x.getValue()));
 561             return cp;
 562         }
 563
 564         /*
 565          * Gets the alpha (slope) between two points
 566          */
 567         public BigDecimal getAlpha(SyncPoint p1) {
 568             if (p1 == null) {
 569                 return BigDecimal.ONE;
 570             }
 571             BigDecimal deltay = BigDecimal.valueOf(y.getValue() - p1.y.getValue());
 572             BigDecimal deltax = BigDecimal.valueOf(x.getValue() - p1.x.getValue());
 573             if (deltax.equals(BigDecimal.ZERO)) {
 574                 return BigDecimal.ONE;
 575             }
 576             return deltay.divide(deltax, fMc);
 577         }
 578
 579         /*
 580          * Get the beta value (when x = 0) of the line given alpha
 581          */
 582         public BigDecimal getBeta(BigDecimal alpha) {
 583             return BigDecimal.valueOf(y.getValue()).subtract(alpha.multiply(BigDecimal.valueOf(x.getValue()), fMc));
 584         }
 585
 586         @Override
 587         public String toString() {
 588             return String.format("%s (%s,  %s)", this.getClass().getCanonicalName(), x, y); //$NON-NLS-1$
 589         }
 590     }
 591
 592     private void writeObject(ObjectOutputStream s)
 593             throws IOException {
 594         /*
 595          * Remove the tree because it is not serializable
 596          */
 597         fTree = null;
 598         s.defaultWriteObject();
 599     }
 600
 601 }