1 /*******************************************************************************
2 * Copyright (c) 2013 É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
.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
;
27 import org
.eclipse
.tracecompass
.internal
.tmf
.core
.synchronization
.graph
.SyncSpanningTree
;
28 import org
.eclipse
.tracecompass
.tmf
.core
.event
.ITmfEvent
;
29 import org
.eclipse
.tracecompass
.tmf
.core
.event
.matching
.TmfEventDependency
;
30 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.ITmfTimestampTransform
;
31 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.Messages
;
32 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.SynchronizationAlgorithm
;
33 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.TimestampTransformFactory
;
34 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
35 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.ITmfTrace
;
38 * Class implementing fully incremental trace synchronization approach as
41 * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
42 * "Streaming Mode Incremental Clock Synchronization"
44 * Since the algorithm itself applies to two traces, it is implemented in a
45 * private class, while this public class manages the synchronization between
48 * @author Geneviève Bastien
50 public class SyncAlgorithmFullyIncremental
extends SynchronizationAlgorithm
{
53 * Auto-generated serial UID
55 private static final long serialVersionUID
= -1782788842774838830L;
57 private static final MathContext fMc
= MathContext
.DECIMAL128
;
60 private final List
<ConvexHull
> fSyncs
;
62 private SyncSpanningTree fTree
= null;
65 * Initialization of the attributes
67 public SyncAlgorithmFullyIncremental() {
68 fSyncs
= new LinkedList
<>();
72 * Function called after all matching has been done, to do any post-match
73 * treatment. For this class, it calculates stats, while the data is
77 public void matchingEnded() {
82 public void init(Collection
<ITmfTrace
> traces
) {
83 ITmfTrace
[] traceArr
= traces
.toArray(new ITmfTrace
[traces
.size()]);
85 /* Create a convex hull for all trace pairs */
86 // FIXME: is it necessary to make ConvexHull for every pairs up-front?
87 // The ConvexHull seems to be created on the fly in processMatch().
88 for (int i
= 0; i
< traceArr
.length
; i
++) {
89 for (int j
= i
+ 1; j
< traceArr
.length
; j
++) {
90 if (!traceArr
[i
].getHostId().equals(traceArr
[j
].getHostId())) {
91 ConvexHull algo
= new ConvexHull(traceArr
[i
].getHostId(), traceArr
[j
].getHostId());
99 protected void processMatch(TmfEventDependency match
) {
100 String host1
= match
.getSourceEvent().getTrace().getHostId();
101 String host2
= match
.getDestinationEvent().getTrace().getHostId();
103 /* Process only if source and destination are different */
104 if (host1
.equals(host2
)) {
108 /* Check if a convex hull algorithm already exists for these 2 hosts */
109 ConvexHull algo
= null;
110 for (ConvexHull traceSync
: fSyncs
) {
111 if (traceSync
.isForHosts(host1
, host2
)) {
116 algo
= new ConvexHull(host1
, host2
);
119 algo
.processMatch(match
);
120 invalidateSyncGraph();
123 private void invalidateSyncGraph() {
128 public ITmfTimestampTransform
getTimestampTransform(ITmfTrace trace
) {
129 return getTimestampTransform(trace
.getHostId());
133 public ITmfTimestampTransform
getTimestampTransform(String hostId
) {
134 SyncSpanningTree tree
= getSyncTree();
135 return tree
.getTimestampTransform(hostId
);
139 * Each convex hull computes the synchronization between 2 given hosts. A
140 * synchronization can be done on multiple hosts that may not all
141 * communicate with each other. We must use another algorithm to determine
142 * which host will be the reference node and what synchronization formula
143 * will be used between each host and this reference node.
145 * For example, take traces a, b and c where a and c talk to b but do not
146 * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
147 * the formulae between their 2 traces, but if a is the reference node, then
148 * the resulting formula of c would be the composition of {@literal a <-> b}
149 * and {@literal b <-> c}
151 * @return The synchronization spanning tree for this synchronization
153 private SyncSpanningTree
getSyncTree() {
155 fTree
= new SyncSpanningTree();
156 for (ConvexHull traceSync
: fSyncs
) {
157 SyncQuality q
= traceSync
.getQuality();
158 if (q
== SyncQuality
.ACCURATE
|| q
== SyncQuality
.APPROXIMATE
) {
159 String from
= traceSync
.getReferenceHost();
160 String to
= traceSync
.getOtherHost();
161 fTree
.addSynchronization(from
, to
, traceSync
.getTimestampTransform(to
), traceSync
.getAccuracy());
169 public SyncQuality
getSynchronizationQuality(ITmfTrace trace1
, ITmfTrace trace2
) {
170 for (ConvexHull traceSync
: fSyncs
) {
171 if (traceSync
.isForHosts(trace1
.getHostId(), trace2
.getHostId())) {
172 return traceSync
.getQuality();
175 return SyncQuality
.ABSENT
;
179 public boolean isTraceSynced(String hostId
) {
180 ITmfTimestampTransform t
= getTimestampTransform(hostId
);
181 return !t
.equals(TimestampTransformFactory
.getDefaultTransform());
185 public Map
<String
, Map
<String
, Object
>> getStats() {
187 * TODO: Stats, while still accurate, may be misleading now that the
188 * sync tree changes synchronization formula. The stats should use the
191 Map
<String
, Map
<String
, Object
>> statmap
= new LinkedHashMap
<>();
192 for (ConvexHull traceSync
: fSyncs
) {
193 statmap
.put(traceSync
.getReferenceHost() + " <==> " + traceSync
.getOtherHost(), traceSync
.getStats()); //$NON-NLS-1$
199 public String
toString() {
200 StringBuilder b
= new StringBuilder();
201 b
.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
207 * This is the actual synchronization algorithm between two traces using
210 private class ConvexHull
implements Serializable
{
212 private static final long serialVersionUID
= 8309351175030935291L;
215 * The list of meaningful points on the upper hull (received by the
216 * reference trace, below in a graph)
218 private final LinkedList
<SyncPoint
> fUpperBoundList
= new LinkedList
<>();
221 * The list of meaninful points on the lower hull (sent by the reference
222 * trace, above in a graph)
224 private final LinkedList
<SyncPoint
> fLowerBoundList
= new LinkedList
<>();
226 /** Points forming the line with maximum slope */
227 private final SyncPoint
[] fLmax
;
229 /** Points forming the line with minimum slope */
230 private final SyncPoint
[] fLmin
;
233 * Slopes and ordinate at origin of respectively fLmin, fLmax and the
236 private BigDecimal fAlphamin
, fBetamax
, fAlphamax
, fBetamin
, fAlpha
, fBeta
;
238 private int fNbMatches
, fNbAccurateMatches
;
239 private String fReferenceHost
= "", fOtherHost
= ""; //$NON-NLS-1$//$NON-NLS-2$
240 private SyncQuality fQuality
;
242 private 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 fLmax
= new SyncPoint
[2];
261 fLmin
= new SyncPoint
[2];
262 fAlpha
= BigDecimal
.ONE
;
263 fAlphamax
= BigDecimal
.ONE
;
264 fAlphamin
= BigDecimal
.ONE
;
265 fBeta
= BigDecimal
.ZERO
;
266 fBetamax
= BigDecimal
.ZERO
;
267 fBetamin
= BigDecimal
.ZERO
;
269 fNbAccurateMatches
= 0;
270 fQuality
= SyncQuality
.ABSENT
; // default quality
273 protected void processMatch(TmfEventDependency match
) {
275 LinkedList
<SyncPoint
> boundList
, otherBoundList
;
277 SyncPoint
[] line
, otherLine
;
279 int inversionFactor
= 1;
280 boolean qualify
= false;
283 /* Initialize data depending on the which hull the match is part of */
284 if (match
.getSourceEvent().getTrace().getHostId().compareTo(match
.getDestinationEvent().getTrace().getHostId()) > 0) {
285 boundList
= fUpperBoundList
;
286 otherBoundList
= fLowerBoundList
;
289 p
= new SyncPoint(match
.getDestinationEvent(), match
.getSourceEvent());
292 boundList
= fLowerBoundList
;
293 otherBoundList
= fUpperBoundList
;
296 p
= new SyncPoint(match
.getSourceEvent(), match
.getDestinationEvent());
297 inversionFactor
= -1;
301 * Does the message qualify for the hull, or is in on the wrong side
302 * of the reference line
304 if ((line
[0] == null) || (line
[1] == null) || (p
.crossProduct(line
[0], line
[1]) * inversionFactor
> 0)) {
306 * If message qualifies, verify if points need to be removed
307 * from the hull and add the new point as the maximum reference
308 * point for the line. Also clear the stats that are not good
311 fNbAccurateMatches
++;
313 removeUselessPoints(p
, boundList
, inversionFactor
);
319 * Adjust the boundary of the reference line and if one of the
320 * reference point of the other line was removed from the hull, also
321 * adjust the other line
323 adjustBound(line
, otherBoundList
, inversionFactor
);
324 if ((otherLine
[1] != null) && !boundList
.contains(otherLine
[0])) {
325 adjustBound(otherLine
, boundList
, inversionFactor
* -1);
335 * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
336 * and approximation of the synchronization at this time
338 private void approximateSync() {
341 * Line slopes functions
343 * Lmax = alpha_max T + beta_min
345 * Lmin = alpha_min T + beta_max
347 if ((fLmax
[0] != null) || (fLmin
[0] != null)) {
349 * Do not recalculate synchronization after it is failed. We
350 * keep the last not failed result.
352 if (getQuality() != SyncQuality
.FAIL
) {
353 BigDecimal alphamax
= fLmax
[1].getAlpha(fLmax
[0]);
354 BigDecimal alphamin
= fLmin
[1].getAlpha(fLmin
[0]);
355 SyncQuality quality
= null;
357 if ((fLmax
[0] == null) || (fLmin
[0] == null)) {
358 quality
= SyncQuality
.APPROXIMATE
;
360 else if (alphamax
.compareTo(alphamin
) > 0) {
361 quality
= SyncQuality
.ACCURATE
;
363 /* Lines intersect, not good */
364 quality
= SyncQuality
.FAIL
;
367 * Only calculate sync if this match does not cause failure
370 if (quality
!= SyncQuality
.FAIL
) {
371 fAlphamax
= alphamax
;
372 fBetamin
= fLmax
[1].getBeta(fAlphamax
);
373 fAlphamin
= alphamin
;
374 fBetamax
= fLmin
[1].getBeta(fAlphamin
);
375 fAlpha
= fAlphamax
.add(fAlphamin
).divide(BigDecimal
.valueOf(2), fMc
);
376 fBeta
= fBetamin
.add(fBetamax
).divide(BigDecimal
.valueOf(2), fMc
);
380 } else if (((fLmax
[0] == null) && (fLmin
[1] == null))
381 || ((fLmax
[1] == null) && (fLmin
[0] == null))) {
382 /* Either there is no upper hull point or no lower hull */
383 setQuality(SyncQuality
.INCOMPLETE
);
388 * Verify if the line should be adjusted to be more accurate give the
391 private void adjustBound(SyncPoint
[] line
, LinkedList
<SyncPoint
> otherBoundList
, int inversionFactor
) {
392 SyncPoint minPoint
= null, nextPoint
;
393 boolean finishedSearch
= false;
396 * Find in the other bound, the origin point of the line, start from
397 * the beginning if the point was lost
399 int i
= Math
.max(0, otherBoundList
.indexOf(line
[0]));
401 while ((i
< otherBoundList
.size() - 1) && !finishedSearch
) {
402 minPoint
= otherBoundList
.get(i
);
403 nextPoint
= otherBoundList
.get(i
+ 1);
406 * If the rotation (cross-product) is not optimal, move to next
407 * point as reference for the line (if available)
409 * Otherwise, the current minPoint is the minPoint of the line
411 if (minPoint
.crossProduct(nextPoint
, line
[1]) * inversionFactor
> 0) {
412 if (nextPoint
.getTimeX() < line
[1].getTimeX()) {
416 finishedSearch
= true;
420 finishedSearch
= true;
424 if (line
[0] == null) {
428 /* Make sure point 0 is before point 1 */
429 if ((line
[0] != null) && (line
[0].getTimeX() > line
[1].getTimeX())) {
435 * When a point qualifies to be in a hull, we verify if any of the
436 * existing points need to be removed from the hull
438 private void removeUselessPoints(final SyncPoint p
, final LinkedList
<SyncPoint
> boundList
, final int inversionFactor
) {
440 boolean checkRemove
= true;
442 while (checkRemove
&& boundList
.size() >= 2) {
443 if (p
.crossProduct(boundList
.get(boundList
.size() - 2), boundList
.getLast()) * inversionFactor
> 0) {
444 boundList
.removeLast();
449 boundList
.addLast(p
);
452 public ITmfTimestampTransform
getTimestampTransform(String hostId
) {
453 if (hostId
.equals(fOtherHost
) && (getQuality() == SyncQuality
.ACCURATE
|| getQuality() == SyncQuality
.APPROXIMATE
|| getQuality() == SyncQuality
.FAIL
)) {
454 /* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
455 return TimestampTransformFactory
.createLinear(BigDecimal
.ONE
.divide(fAlpha
, fMc
), BigDecimal
.valueOf(-1).multiply(fBeta
).divide(fAlpha
, fMc
));
457 return TimestampTransformFactory
.getDefaultTransform();
460 public SyncQuality
getQuality() {
464 public BigDecimal
getAccuracy() {
465 return fAlphamax
.subtract(fAlphamin
);
468 public Map
<String
, Object
> getStats() {
469 if (fStats
.size() == 0) {
471 switch (getQuality()) {
473 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_absent
;
476 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_accurate
;
479 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_approx
;
482 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_incomplete
;
486 syncQuality
= Messages
.SyncAlgorithmFullyIncremental_fail
;
490 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_refhost
, fReferenceHost
);
491 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_otherhost
, fOtherHost
);
492 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_quality
, syncQuality
);
493 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_alpha
, fAlpha
);
494 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_beta
, fBeta
);
495 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_ub
, (fUpperBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fUpperBoundList
.size());
496 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_lb
, (fLowerBoundList
.size() == 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fLowerBoundList
.size());
497 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_accuracy
, getAccuracy().doubleValue());
498 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbmatch
, (fNbMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbMatches
);
499 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_nbacc
, (fNbAccurateMatches
== 0) ? Messages
.SyncAlgorithmFullyIncremental_NA
: fNbAccurateMatches
);
500 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_refformula
, Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceHost
);
501 fStats
.put(Messages
.SyncAlgorithmFullyIncremental_otherformula
, fAlpha
+ Messages
.SyncAlgorithmFullyIncremental_mult
+ Messages
.SyncAlgorithmFullyIncremental_T_
+ fReferenceHost
+ Messages
.SyncAlgorithmFullyIncremental_add
+ fBeta
);
507 public String
getReferenceHost() {
508 return fReferenceHost
;
511 public String
getOtherHost() {
515 public boolean isForHosts(String hostId1
, String hostId2
) {
516 return ((fReferenceHost
.equals(hostId1
) && fOtherHost
.equals(hostId2
)) || (fReferenceHost
.equals(hostId2
) && fOtherHost
.equals(hostId1
)));
519 private void writeObject(ObjectOutputStream s
)
522 * Remove calculation data because most of it is not serializable.
523 * We have the statistics anyway
525 fUpperBoundList
.clear();
526 fLowerBoundList
.clear();
531 s
.defaultWriteObject();
534 @SuppressWarnings("nls")
536 public String
toString() {
537 StringBuilder b
= new StringBuilder();
538 b
.append("Between " + fReferenceHost
+ " and " + fOtherHost
+ " [");
539 b
.append(" alpha " + fAlpha
+ " beta " + fBeta
+ " ]");
543 private void setQuality(SyncQuality fQuality
) {
544 this.fQuality
= fQuality
;
550 * Private class representing a point to synchronize on a graph. The x axis
551 * is the timestamp of the event from the reference trace while the y axis
552 * is the timestamp of the event on the other trace
554 private class SyncPoint
{
555 private final ITmfTimestamp x
, y
;
557 public SyncPoint(ITmfEvent ex
, ITmfEvent ey
) {
558 x
= ex
.getTimestamp();
559 y
= ey
.getTimestamp();
562 public long getTimeX() {
567 * Calculate a cross product of 3 points:
569 * If the cross-product < 0, then p, pa, pb are clockwise
571 * If the cross-product > 0, then p, pa, pb are counter-clockwise
573 * If cross-product == 0, then they are in a line
579 * @return The cross product
581 public long crossProduct(SyncPoint pa
, SyncPoint pb
) {
582 long cp
= ((pa
.x
.getValue() - x
.getValue()) * (pb
.y
.getValue() - y
.getValue()) - (pa
.y
.getValue() - y
.getValue()) * (pb
.x
.getValue() - x
.getValue()));
587 * Gets the alpha (slope) between two points
589 public BigDecimal
getAlpha(SyncPoint p1
) {
591 return BigDecimal
.ONE
;
593 BigDecimal deltay
= BigDecimal
.valueOf(y
.getValue() - p1
.y
.getValue());
594 BigDecimal deltax
= BigDecimal
.valueOf(x
.getValue() - p1
.x
.getValue());
595 if (deltax
.equals(BigDecimal
.ZERO
)) {
596 return BigDecimal
.ONE
;
598 return deltay
.divide(deltax
, fMc
);
602 * Get the beta value (when x = 0) of the line given alpha
604 public BigDecimal
getBeta(BigDecimal alpha
) {
605 return BigDecimal
.valueOf(y
.getValue()).subtract(alpha
.multiply(BigDecimal
.valueOf(x
.getValue()), fMc
));
609 public String
toString() {
610 return String
.format("%s (%s, %s)", this.getClass().getCanonicalName(), x
, y
); //$NON-NLS-1$
614 private void writeObject(ObjectOutputStream s
)
617 * Remove the tree because it is not serializable
620 s
.defaultWriteObject();