1 /*******************************************************************************
2 * Copyright (c) 2013, 2014 École Polytechnique de Montréal
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
10 * Geneviève Bastien - Initial implementation and API
11 * Francis Giraldeau - Transform computation using synchronization graph
12 *******************************************************************************/
14 package org
.eclipse
.tracecompass
.internal
.tmf
.core
.synchronization
;
16 import java
.io
.IOException
;
17 import java
.io
.ObjectInputStream
;
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
;
27 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
28 import org
.eclipse
.tracecompass
.internal
.tmf
.core
.synchronization
.graph
.SyncSpanningTree
;
29 import org
.eclipse
.tracecompass
.tmf
.core
.event
.ITmfEvent
;
30 import org
.eclipse
.tracecompass
.tmf
.core
.event
.matching
.TmfEventDependency
;
31 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.ITmfTimestampTransform
;
32 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.Messages
;
33 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.SynchronizationAlgorithm
;
34 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.TimestampTransformFactory
;
35 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
36 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.ITmfTrace
;
39 * Class implementing fully incremental trace synchronization approach as
42 * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
43 * "Streaming Mode Incremental Clock Synchronization"
45 * Since the algorithm itself applies to two traces, it is implemented in a
46 * private class, while this public class manages the synchronization between
49 * @author Geneviève Bastien
51 public class SyncAlgorithmFullyIncremental
extends SynchronizationAlgorithm
{
54 * Auto-generated serial UID
56 private static final long serialVersionUID
= -1782788842774838830L;
58 private static final MathContext fMc
= MathContext
.DECIMAL128
;
61 private final List
<ConvexHull
> fSyncs
;
63 private transient SyncSpanningTree fTree
= null;
66 * Initialization of the attributes
68 public SyncAlgorithmFullyIncremental() {
69 fSyncs
= new LinkedList
<>();
73 * Function called after all matching has been done, to do any post-match
74 * treatment. For this class, it calculates stats, while the data is
78 public void matchingEnded() {
83 public void init(Collection
<ITmfTrace
> traces
) {
84 ITmfTrace
[] traceArr
= traces
.toArray(new ITmfTrace
[traces
.size()]);
86 /* Create a convex hull for all trace pairs */
87 // FIXME: is it necessary to make ConvexHull for every pairs up-front?
88 // The ConvexHull seems to be created on the fly in processMatch().
89 for (int i
= 0; i
< traceArr
.length
; i
++) {
90 for (int j
= i
+ 1; j
< traceArr
.length
; j
++) {
91 if (!traceArr
[i
].getHostId().equals(traceArr
[j
].getHostId())) {
92 ConvexHull algo
= new ConvexHull(traceArr
[i
].getHostId(), traceArr
[j
].getHostId());
100 protected void processMatch(TmfEventDependency match
) {
101 String host1
= match
.getSourceEvent().getTrace().getHostId();
102 String host2
= match
.getDestinationEvent().getTrace().getHostId();
104 /* Process only if source and destination are different */
105 if (host1
.equals(host2
)) {
109 /* Check if a convex hull algorithm already exists for these 2 hosts */
110 ConvexHull algo
= null;
111 for (ConvexHull traceSync
: fSyncs
) {
112 if (traceSync
.isForHosts(host1
, host2
)) {
117 algo
= new ConvexHull(host1
, host2
);
120 algo
.processMatch(match
);
121 invalidateSyncGraph();
124 private void invalidateSyncGraph() {
129 public ITmfTimestampTransform
getTimestampTransform(ITmfTrace trace
) {
130 return getTimestampTransform(trace
.getHostId());
134 public ITmfTimestampTransform
getTimestampTransform(String hostId
) {
135 SyncSpanningTree tree
= getSyncTree();
136 return tree
.getTimestampTransform(hostId
);
140 * Each convex hull computes the synchronization between 2 given hosts. A
141 * synchronization can be done on multiple hosts that may not all
142 * communicate with each other. We must use another algorithm to determine
143 * which host will be the reference node and what synchronization formula
144 * will be used between each host and this reference node.
146 * For example, take traces a, b and c where a and c talk to b but do not
147 * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
148 * the formulae between their 2 traces, but if a is the reference node, then
149 * the resulting formula of c would be the composition of {@literal a <-> b}
150 * and {@literal b <-> c}
152 * @return The synchronization spanning tree for this synchronization
154 private SyncSpanningTree
getSyncTree() {
156 fTree
= new SyncSpanningTree(getRootNode());
157 for (ConvexHull traceSync
: fSyncs
) {
158 SyncQuality q
= traceSync
.getQuality();
159 if (q
== SyncQuality
.ACCURATE
|| q
== SyncQuality
.APPROXIMATE
) {
160 String from
= traceSync
.getReferenceHost();
161 String to
= traceSync
.getOtherHost();
162 fTree
.addSynchronization(from
, to
, traceSync
.getTimestampTransform(to
), traceSync
.getAccuracy());
170 public SyncQuality
getSynchronizationQuality(ITmfTrace trace1
, ITmfTrace trace2
) {
171 for (ConvexHull traceSync
: fSyncs
) {
172 if (traceSync
.isForHosts(trace1
.getHostId(), trace2
.getHostId())) {
173 return traceSync
.getQuality();
176 return SyncQuality
.ABSENT
;
180 public boolean isTraceSynced(String hostId
) {
181 ITmfTimestampTransform t
= getTimestampTransform(hostId
);
182 return !t
.equals(TimestampTransformFactory
.getDefaultTransform());
186 public Map
<String
, Map
<String
, Object
>> getStats() {
188 * TODO: Stats, while still accurate, may be misleading now that the
189 * sync tree changes synchronization formula. The stats should use the
192 Map
<String
, Map
<String
, Object
>> statmap
= new LinkedHashMap
<>();
193 for (ConvexHull traceSync
: fSyncs
) {
194 statmap
.put(traceSync
.getReferenceHost() + " <==> " + traceSync
.getOtherHost(), traceSync
.getStats()); //$NON-NLS-1$
200 public String
toString() {
201 StringBuilder b
= new StringBuilder();
202 b
.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
208 * This is the actual synchronization algorithm between two traces using
211 private class ConvexHull
implements Serializable
{
213 private static final long serialVersionUID
= 8309351175030935291L;
215 private final String fReferenceHost
;
216 private final String fOtherHost
;
219 * Slopes and ordinate at origin of respectively fLmin, fLmax and the
222 private BigDecimal fAlphamin
, fBetamax
, fAlphamax
, fBetamin
, fAlpha
, fBeta
;
223 private int fNbMatches
, fNbAccurateMatches
;
224 private SyncQuality fQuality
;
227 * The list of meaningful points on the upper hull (received by the
228 * reference trace, below in a graph)
230 private transient LinkedList
<SyncPoint
> fUpperBoundList
= new LinkedList
<>();
232 * The list of meaninful points on the lower hull (sent by the reference
233 * trace, above in a graph)
235 private transient LinkedList
<SyncPoint
> fLowerBoundList
= new LinkedList
<>();
237 /** Points forming the line with maximum slope */
238 private transient SyncPoint
[] fLmax
= new SyncPoint
[2];
239 /** Points forming the line with minimum slope */
240 private transient SyncPoint
[] fLmin
= new SyncPoint
[2];
242 private transient Map
<String
, Object
> fStats
= new LinkedHashMap
<>();
245 * Initialization of the attributes
248 * ID of the first host
250 * ID of the second host
252 public ConvexHull(String host1
, String host2
) {
253 if (host1
.compareTo(host2
) > 0) {
254 fReferenceHost
= host2
;
257 fReferenceHost
= host1
;
260 fAlpha
= BigDecimal
.ONE
;
261 fAlphamax
= BigDecimal
.ONE
;
262 fAlphamin
= BigDecimal
.ONE
;
263 fBeta
= BigDecimal
.ZERO
;
264 fBetamax
= BigDecimal
.ZERO
;
265 fBetamin
= BigDecimal
.ZERO
;
267 fNbAccurateMatches
= 0;
268 fQuality
= SyncQuality
.ABSENT
; // default quality
271 protected void processMatch(TmfEventDependency match
) {
273 LinkedList
<SyncPoint
> boundList
, otherBoundList
;
275 SyncPoint
[] line
, otherLine
;
277 int inversionFactor
= 1;
278 boolean qualify
= false;
281 /* Initialize data depending on the which hull the match is part of */
282 if (match
.getSourceEvent().getTrace().getHostId().compareTo(match
.getDestinationEvent().getTrace().getHostId()) > 0) {
283 boundList
= fUpperBoundList
;
284 otherBoundList
= fLowerBoundList
;
287 p
= new SyncPoint(match
.getDestinationEvent(), match
.getSourceEvent());
290 boundList
= fLowerBoundList
;
291 otherBoundList
= fUpperBoundList
;
294 p
= new SyncPoint(match
.getSourceEvent(), match
.getDestinationEvent());
295 inversionFactor
= -1;
299 * Does the message qualify for the hull, or is in on the wrong side
300 * of the reference line
302 if ((line
[0] == null) || (line
[1] == null) || (p
.crossProduct(line
[0], line
[1]) * inversionFactor
> 0)) {
304 * If message qualifies, verify if points need to be removed
305 * from the hull and add the new point as the maximum reference
306 * point for the line. Also clear the stats that are not good
309 fNbAccurateMatches
++;
311 removeUselessPoints(p
, boundList
, inversionFactor
);
317 * Adjust the boundary of the reference line and if one of the
318 * reference point of the other line was removed from the hull, also
319 * adjust the other line
321 adjustBound(line
, otherBoundList
, inversionFactor
);
322 if ((otherLine
[1] != null) && !boundList
.contains(otherLine
[0])) {
323 adjustBound(otherLine
, boundList
, inversionFactor
* -1);
333 * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
334 * and approximation of the synchronization at this time
336 private void approximateSync() {
339 * Line slopes functions
341 * Lmax = alpha_max T + beta_min
343 * Lmin = alpha_min T + beta_max
345 if ((fLmax
[0] != null) || (fLmin
[0] != null)) {
347 * Do not recalculate synchronization after it is failed. We
348 * keep the last not failed result.
350 if (getQuality() != SyncQuality
.FAIL
) {
351 BigDecimal alphamax
= fLmax
[1].getAlpha(fLmax
[0]);
352 BigDecimal alphamin
= fLmin
[1].getAlpha(fLmin
[0]);
353 SyncQuality quality
= null;
355 if ((fLmax
[0] == null) || (fLmin
[0] == null)) {
356 quality
= SyncQuality
.APPROXIMATE
;
358 else if (alphamax
.compareTo(alphamin
) > 0) {
359 quality
= SyncQuality
.ACCURATE
;
361 /* Lines intersect, not good */
362 quality
= SyncQuality
.FAIL
;
365 * Only calculate sync if this match does not cause failure
368 if (quality
!= SyncQuality
.FAIL
) {
369 fAlphamax
= alphamax
;
370 fBetamin
= fLmax
[1].getBeta(fAlphamax
);
371 fAlphamin
= alphamin
;
372 fBetamax
= fLmin
[1].getBeta(fAlphamin
);
373 fAlpha
= fAlphamax
.add(fAlphamin
).divide(BigDecimal
.valueOf(2), fMc
);
374 fBeta
= fBetamin
.add(fBetamax
).divide(BigDecimal
.valueOf(2), fMc
);
378 } else if (((fLmax
[0] == null) && (fLmin
[1] == null))
379 || ((fLmax
[1] == null) && (fLmin
[0] == null))) {
380 /* Either there is no upper hull point or no lower hull */
381 setQuality(SyncQuality
.INCOMPLETE
);
386 * Verify if the line should be adjusted to be more accurate give the
389 private void adjustBound(SyncPoint
[] line
, LinkedList
<SyncPoint
> otherBoundList
, int inversionFactor
) {
390 SyncPoint minPoint
= null, nextPoint
;
391 boolean finishedSearch
= false;
394 * Find in the other bound, the origin point of the line, start from
395 * the beginning if the point was lost
397 int i
= Math
.max(0, otherBoundList
.indexOf(line
[0]));
399 while ((i
< otherBoundList
.size() - 1) && !finishedSearch
) {
400 minPoint
= otherBoundList
.get(i
);
401 nextPoint
= otherBoundList
.get(i
+ 1);
404 * If the rotation (cross-product) is not optimal, move to next
405 * point as reference for the line (if available)
407 * Otherwise, the current minPoint is the minPoint of the line
409 if (minPoint
.crossProduct(nextPoint
, line
[1]) * inversionFactor
> 0) {
410 if (nextPoint
.getTimeX() < line
[1].getTimeX()) {
414 finishedSearch
= true;
418 finishedSearch
= true;
422 if (line
[0] == null) {
426 /* Make sure point 0 is before point 1 */
427 if ((line
[0] != null) && (line
[0].getTimeX() > line
[1].getTimeX())) {
433 * When a point qualifies to be in a hull, we verify if any of the
434 * existing points need to be removed from the hull
436 private void removeUselessPoints(final SyncPoint p
, final LinkedList
<SyncPoint
> boundList
, final int inversionFactor
) {
438 boolean checkRemove
= true;
440 while (checkRemove
&& boundList
.size() >= 2) {
441 if (p
.crossProduct(boundList
.get(boundList
.size() - 2), boundList
.getLast()) * inversionFactor
> 0) {
442 boundList
.removeLast();
447 boundList
.addLast(p
);
450 public ITmfTimestampTransform
getTimestampTransform(String hostId
) {
451 if (hostId
.equals(fOtherHost
) && (getQuality() == SyncQuality
.ACCURATE
|| getQuality() == SyncQuality
.APPROXIMATE
|| getQuality() == SyncQuality
.FAIL
)) {
452 /* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
453 return TimestampTransformFactory
.createLinear(NonNullUtils
.checkNotNull(BigDecimal
.ONE
.divide(fAlpha
, fMc
)), NonNullUtils
.checkNotNull(BigDecimal
.valueOf(-1).multiply(fBeta
).divide(fAlpha
, fMc
)));
455 return TimestampTransformFactory
.getDefaultTransform();
458 public SyncQuality
getQuality() {
462 public BigDecimal
getAccuracy() {
463 return fAlphamax
.subtract(fAlphamin
);
466 public Map
<String
, Object
> getStats() {
467 if (fStats
.size() == 0) {
469 switch (getQuality()) {
471 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_absent
;
474 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_accurate
;
477 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_approx
;
480 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_incomplete
;
484 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_fail
;
488 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_refhost
, fReferenceHost
);
489 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_otherhost
, fOtherHost
);
490 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_quality
, syncQuality
);
491 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_alpha
, fAlpha
);
492 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_beta
, fBeta
);
493 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_ub
, (fUpperBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fUpperBoundList
.size());
494 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_lb
, (fLowerBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fLowerBoundList
.size());
495 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_accuracy
, getAccuracy().doubleValue());
496 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbmatch
, (fNbMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbMatches
);
497 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbacc
, (fNbAccurateMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbAccurateMatches
);
498 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_refformula
, Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceHost
);
499 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_otherformula
, fAlpha
+ Messages
.SyncAlgorithmFullyIncremental_mult
+ Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceHost
+ Messages
.SyncAlgorithmFullyIncremental_add
+ fBeta
);
505 public String
getReferenceHost() {
506 return fReferenceHost
;
509 public String
getOtherHost() {
513 public boolean isForHosts(String hostId1
, String hostId2
) {
514 return ((fReferenceHost
.equals(hostId1
) && fOtherHost
.equals(hostId2
)) || (fReferenceHost
.equals(hostId2
) && fOtherHost
.equals(hostId1
)));
517 private void readObject(ObjectInputStream stream
)
518 throws IOException
, ClassNotFoundException
{
519 stream
.defaultReadObject();
521 /* Initialize transient fields */
522 fUpperBoundList
= new LinkedList
<>();
523 fLowerBoundList
= new LinkedList
<>();
524 fLmax
= new SyncPoint
[2];
525 fLmin
= new SyncPoint
[2];
526 fStats
= new LinkedHashMap
<>();
529 @SuppressWarnings("nls")
531 public String
toString() {
532 StringBuilder b
= new StringBuilder();
533 b
.append("Between " + fReferenceHost
+ " and " + fOtherHost
+ " [");
534 b
.append(" alpha " + fAlpha
+ " beta " + fBeta
+ " ]");
538 private void setQuality(SyncQuality fQuality
) {
539 this.fQuality
= fQuality
;
545 * Private class representing a point to synchronize on a graph. The x axis
546 * is the timestamp of the event from the reference trace while the y axis
547 * is the timestamp of the event on the other trace
549 private class SyncPoint
{
550 private final ITmfTimestamp x
, y
;
552 public SyncPoint(ITmfEvent ex
, ITmfEvent ey
) {
553 x
= ex
.getTimestamp();
554 y
= ey
.getTimestamp();
557 public long getTimeX() {
562 * Calculate a cross product of 3 points:
564 * If the cross-product < 0, then p, pa, pb are clockwise
566 * If the cross-product > 0, then p, pa, pb are counter-clockwise
568 * If cross-product == 0, then they are in a line
574 * @return The cross product
576 public long crossProduct(SyncPoint pa
, SyncPoint pb
) {
577 long cp
= ((pa
.x
.getValue() - x
.getValue()) * (pb
.y
.getValue() - y
.getValue()) - (pa
.y
.getValue() - y
.getValue()) * (pb
.x
.getValue() - x
.getValue()));
582 * Gets the alpha (slope) between two points
584 public BigDecimal
getAlpha(SyncPoint p1
) {
586 return BigDecimal
.ONE
;
588 BigDecimal deltay
= BigDecimal
.valueOf(y
.getValue() - p1
.y
.getValue());
589 BigDecimal deltax
= BigDecimal
.valueOf(x
.getValue() - p1
.x
.getValue());
590 if (deltax
.equals(BigDecimal
.ZERO
)) {
591 return BigDecimal
.ONE
;
593 return deltay
.divide(deltax
, fMc
);
597 * Get the beta value (when x = 0) of the line given alpha
599 public BigDecimal
getBeta(BigDecimal alpha
) {
600 return BigDecimal
.valueOf(y
.getValue()).subtract(alpha
.multiply(BigDecimal
.valueOf(x
.getValue()), fMc
));
604 public String
toString() {
605 return String
.format("%s (%s, %s)", this.getClass().getCanonicalName(), x
, y
); //$NON-NLS-1$