*/
@RunWith(Suite.class)
@Suite.SuiteClasses({
- MatchAndSyncTest.class,
- ExperimentSyncTest.class
+ ExperimentSyncTest.class,
+ MatchAndSyncTest.class
})
public class AllTests {
import org.eclipse.linuxtools.tmf.core.trace.TmfExperiment;
import org.eclipse.linuxtools.tmf.ctf.core.CtfTmfTrace;
import org.eclipse.linuxtools.tmf.ctf.core.tests.shared.CtfTmfTestTrace;
-import org.junit.After;
-import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
@SuppressWarnings("nls")
public class ExperimentSyncTest {
- private static final String EXPERIMENT = "MyExperiment";
- private static int BLOCK_SIZE = 1000;
-
- private static ITmfTrace[] fTraces;
- private static TmfExperiment fExperiment;
+ private static final String EXPERIMENT = "MyExperiment";
+ private static int BLOCK_SIZE = 1000;
/**
- * Class setup
+ * Initialize some data
*/
@BeforeClass
- public static void setUpClass() {
- assumeTrue(CtfTmfTestTrace.SYNC_SRC.exists());
- assumeTrue(CtfTmfTestTrace.SYNC_DEST.exists());
- }
-
- /**
- * Setup the traces and experiment
- */
- @Before
- public void setUp() {
- fTraces = new CtfTmfTrace[2];
- fTraces[0] = CtfTmfTestTrace.SYNC_SRC.getTrace();
- fTraces[1] = CtfTmfTestTrace.SYNC_DEST.getTrace();
-
- fExperiment = new TmfExperiment(fTraces[0].getEventType(), EXPERIMENT, fTraces, BLOCK_SIZE);
-
+ public static void setUp() {
TmfEventMatching.registerMatchObject(new TcpEventMatching());
TmfEventMatching.registerMatchObject(new TcpLttngEventMatching());
}
- /**
- * Reset the timestamp transforms on the traces
- */
- @After
- public void cleanUp() {
- fTraces[0].setTimestampTransform(TimestampTransformFactory.getDefaultTransform());
- fTraces[1].setTimestampTransform(TimestampTransformFactory.getDefaultTransform());
- fTraces[0].dispose();
- fTraces[1].dispose();
- }
-
/**
* Testing experiment synchronization
*/
@Test
public void testExperimentSync() {
- try {
- SynchronizationAlgorithm syncAlgo = fExperiment.synchronizeTraces(true);
+ assumeTrue(CtfTmfTestTrace.SYNC_SRC.exists());
+ assumeTrue(CtfTmfTestTrace.SYNC_DEST.exists());
+ try (CtfTmfTrace trace1 = CtfTmfTestTrace.SYNC_SRC.getTrace();
+ CtfTmfTrace trace2 = CtfTmfTestTrace.SYNC_DEST.getTrace();) {
+
+ ITmfTrace[] traces = { trace1, trace2 };
+ TmfExperiment experiment = new TmfExperiment(traces[0].getEventType(), EXPERIMENT, traces, BLOCK_SIZE);
- ITmfTimestampTransform tt1, tt2;
+ SynchronizationAlgorithm syncAlgo = experiment.synchronizeTraces(true);
- tt1 = syncAlgo.getTimestampTransform(fTraces[0]);
- tt2 = syncAlgo.getTimestampTransform(fTraces[1]);
+ ITmfTimestampTransform tt1 = syncAlgo.getTimestampTransform(trace1);
+ ITmfTimestampTransform tt2 = syncAlgo.getTimestampTransform(trace2);
- fTraces[0].setTimestampTransform(tt1);
- fTraces[1].setTimestampTransform(tt2);
+ trace1.setTimestampTransform(tt1);
+ trace2.setTimestampTransform(tt2);
- assertEquals(tt2, TimestampTransformFactory.getDefaultTransform());
assertEquals("TmfTimestampLinear [ slope = 0.9999413783703139011056845831168394, offset = 79796507913179.33347660124688298171 ]", tt1.toString());
+ assertEquals(TimestampTransformFactory.getDefaultTransform(), tt2);
+
+ assertEquals(syncAlgo.getTimestampTransform(trace1.getHostId()), trace1.getTimestampTransform());
+ assertEquals(syncAlgo.getTimestampTransform(trace2.getHostId()), trace2.getTimestampTransform());
+
+ } catch (TmfTraceException e) {
+ fail("Exception thrown in experiment synchronization " + e.getMessage());
+ }
+ }
- assertEquals(syncAlgo.getTimestampTransform(fTraces[0].getHostId()),fTraces[0].getTimestampTransform());
- assertEquals(syncAlgo.getTimestampTransform(fTraces[1].getHostId()),fTraces[1].getTimestampTransform());
+ /**
+ * Testing synchronization with 3 traces, one of which synchronizes with
+ * both other
+ */
+ @Test
+ public void testDjangoExperimentSync() {
+ assumeTrue(CtfTmfTestTrace.DJANGO_CLIENT.exists());
+ assumeTrue(CtfTmfTestTrace.DJANGO_DB.exists());
+ assumeTrue(CtfTmfTestTrace.DJANGO_HTTPD.exists());
+ try (CtfTmfTrace trace1 = CtfTmfTestTrace.DJANGO_CLIENT.getTrace();
+ CtfTmfTrace trace2 = CtfTmfTestTrace.DJANGO_DB.getTrace();
+ CtfTmfTrace trace3 = CtfTmfTestTrace.DJANGO_HTTPD.getTrace();) {
+ ITmfTrace[] traces = { trace1, trace2, trace3 };
+ TmfExperiment experiment = new TmfExperiment(traces[0].getEventType(), EXPERIMENT, traces, BLOCK_SIZE);
+
+ SynchronizationAlgorithm syncAlgo = experiment.synchronizeTraces(true);
+
+ ITmfTimestampTransform tt1 = syncAlgo.getTimestampTransform(trace1);
+ ITmfTimestampTransform tt2 = syncAlgo.getTimestampTransform(trace2);
+ ITmfTimestampTransform tt3 = syncAlgo.getTimestampTransform(trace3);
+
+ trace1.setTimestampTransform(tt1);
+ trace2.setTimestampTransform(tt2);
+ trace3.setTimestampTransform(tt3);
+
+ assertEquals(TimestampTransformFactory.getDefaultTransform(), tt1);
+ assertEquals("TmfTimestampLinear [ slope = 0.9999996313017589597204633828681240, offset = 498490309972.0038068817738527724192 ]", tt2.toString());
+ assertEquals("TmfTimestampLinear [ slope = 1.000000119014882262265342419815932, offset = -166652893534.6189900382736187431134 ]", tt3.toString());
} catch (TmfTraceException e) {
fail("Exception thrown in experiment synchronization " + e.getMessage());
org.eclipse.linuxtools.internal.tmf.core.statesystem.backends.partial;x-friends:="org.eclipse.linuxtools.statesystem.core.tests",
org.eclipse.linuxtools.internal.tmf.core.statesystem.mipmap;x-friends:="org.eclipse.linuxtools.tmf.core.tests",
org.eclipse.linuxtools.internal.tmf.core.synchronization;x-friends:="org.eclipse.linuxtools.tmf.core.tests",
+ org.eclipse.linuxtools.internal.tmf.core.synchronization.graph;x-friends:="org.eclipse.linuxtools.tmf.core.tests",
org.eclipse.linuxtools.internal.tmf.core.trace;x-friends:="org.eclipse.linuxtools.tmf.core.tests",
org.eclipse.linuxtools.internal.tmf.core.trace.indexer;x-friends:="org.eclipse.linuxtools.tmf.core.tests",
org.eclipse.linuxtools.tmf.core,
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2014 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Geneviève Bastien - Initial implementation and API
+ *******************************************************************************/
+
+package org.eclipse.linuxtools.internal.tmf.core.synchronization;
+
+import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
+
+/**
+ * Interface for timestamp transform who also provide an inverse transform.
+ *
+ * @author Geneviève Bastien
+ */
+public interface ITmfTimestampTransformInvertible extends ITmfTimestampTransform {
+
+ /**
+ * Returns the inverse of this transform. The transform composed with its
+ * inverse yields the identity (or as close to it as mathematical
+ * approximations in the formulae allow).
+ *
+ * @return The inverse transform
+ */
+ ITmfTimestampTransform inverse();
+
+}
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
+import org.eclipse.linuxtools.tmf.core.synchronization.TimestampTransformFactory;
import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
import org.eclipse.linuxtools.tmf.core.timestamp.TmfNanoTimestamp;
*
* @author Matthew Khouzam
*/
-public class TmfConstantTransform implements ITmfTimestampTransform {
+public class TmfConstantTransform implements ITmfTimestampTransformInvertible {
/**
* Serial ID
return builder.toString();
}
+ @Override
+ public ITmfTimestampTransform inverse() {
+ return TimestampTransformFactory.createWithOffset(-1 * fOffset);
+ }
+
}
*
* @author Geneviève Bastien
*/
-public class TmfTimestampTransform implements ITmfTimestampTransform {
+public final class TmfTimestampTransform implements ITmfTimestampTransformInvertible {
/**
* Generated serial UID
/**
* Default constructor
*/
- protected TmfTimestampTransform() {
+ private TmfTimestampTransform() {
}
return "TmfTimestampTransform [ IDENTITY ]"; //$NON-NLS-1$
}
+ @Override
+ public ITmfTimestampTransform inverse() {
+ return IDENTITY;
+ }
+
}
import java.math.MathContext;
import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
+import org.eclipse.linuxtools.tmf.core.synchronization.TimestampTransformFactory;
import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
import org.eclipse.linuxtools.tmf.core.timestamp.TmfTimestamp;
* @author Geneviève Bastien
* @since 3.0
*/
-public class TmfTimestampTransformLinear implements ITmfTimestampTransform {
+public class TmfTimestampTransformLinear implements ITmfTimestampTransformInvertible {
/**
* Generated serial UID
TmfTimestampTransformLinear ttl = (TmfTimestampTransformLinear) composeWith;
BigDecimal newAlpha = fAlpha.multiply(ttl.fAlpha, fMc);
BigDecimal newBeta = fAlpha.multiply(ttl.fBeta, fMc).add(fBeta);
- return new TmfTimestampTransformLinear(newAlpha, newBeta);
+ return TimestampTransformFactory.createLinear(newAlpha, newBeta);
} else {
/*
* We do not know what to do with this kind of transform, just
" ]"; //$NON-NLS-1$
}
+ @Override
+ public ITmfTimestampTransform inverse() {
+ return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
+ }
+
}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2014 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Francis Giraldeau - Initial implementation and API
+ *******************************************************************************/
+
+package org.eclipse.linuxtools.internal.tmf.core.synchronization.graph;
+
+/**
+ * An edge in the {@link SyncGraph}
+ *
+ * @author Francis Giraldeau <francis.giraldeau@gmail.com>
+ * @param <V>
+ * The vertices type
+ * @param <E>
+ * The edge annotation type
+ */
+public class Edge<V, E> {
+
+ private final V fFrom;
+ private final V fTo;
+ private final E fLabel;
+
+ /**
+ * An edge constructor
+ *
+ * @param from
+ * The origin vertex
+ * @param to
+ * The destination vertex
+ * @param label
+ * The edge annotation label
+ */
+ public Edge(V from, V to, E label) {
+ fFrom = from;
+ fTo = to;
+ fLabel = label;
+ }
+
+ /**
+ * Get the vertex from
+ *
+ * @return The origin vertex
+ */
+ public V getFrom() {
+ return fFrom;
+ }
+
+ /**
+ * Get the vertex to
+ *
+ * @return The destination vertex
+ */
+ public V getTo() {
+ return fTo;
+ }
+
+ /**
+ * Get the edge label
+ *
+ * @return The edge label
+ */
+ public E getLabel() {
+ return fLabel;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("(%s, %s, %s)", fFrom, fTo, fLabel); //$NON-NLS-1$
+ }
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2014 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Francis Giraldeau - Initial implementation and API
+ *******************************************************************************/
+
+package org.eclipse.linuxtools.internal.tmf.core.synchronization.graph;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+import java.util.Stack;
+
+import com.google.common.collect.ArrayListMultimap;
+import com.google.common.collect.Multimap;
+
+/**
+ * Minimal graph implementation to compute timestamps transforms of a trace from
+ * a given synchronized set of traces. The graph is implemented as an adjacency
+ * list and is directed. To create undirected graph, add the edge in both
+ * directions.
+ *
+ * @author Francis Giraldeau <francis.giraldeau@gmail.com>
+ * @param <V>
+ * The vertices type
+ * @param <E>
+ * The edge annotation type
+ */
+public class SyncGraph<V, E> {
+
+ private Multimap<V, Edge<V, E>> fAdjacentEdges;
+ private Set<V> fVertices;
+
+ /**
+ * Construct empty graph
+ */
+ public SyncGraph() {
+ fAdjacentEdges = ArrayListMultimap.create();
+ fVertices = new HashSet<>();
+ }
+
+ /**
+ * Add edge from v to w and annotation label
+ *
+ * @param from
+ * from vertex
+ * @param to
+ * to vertex
+ * @param label
+ * the edge label
+ */
+ public void addEdge(V from, V to, E label) {
+ fAdjacentEdges.put(from, new Edge<>(from, to, label));
+ fVertices.add(from);
+ fVertices.add(to);
+ }
+
+ /**
+ * Get the number of edges
+ *
+ * @return number of edges
+ */
+ public int getNbEdges() {
+ return fAdjacentEdges.entries().size();
+ }
+
+ /**
+ * Get the number of vertices
+ *
+ * @return number of vertices
+ */
+ public int getNbVertices() {
+ return fVertices.size();
+ }
+
+ /**
+ * Returns the adjacent edges of the given vertex
+ *
+ * @param v
+ * the vertex
+ * @return the adjacent vertices
+ */
+ public Collection<Edge<V, E>> getAdjacentEdges(V v) {
+ return fAdjacentEdges.get(v);
+ }
+
+ /**
+ * Returns a path between start and end vertices.
+ *
+ * @param start
+ * vertex
+ * @param end
+ * vertex
+ * @return the list of edges between start and end vertices
+ */
+ public List<Edge<V, E>> path(V start, V end) {
+ ArrayList<Edge<V, E>> path = new ArrayList<>();
+ HashMap<V, Edge<V, E>> hist = new HashMap<>();
+ HashSet<V> visited = new HashSet<>();
+ Queue<V> queue = new LinkedList<>();
+ queue.offer(start);
+ /**
+ * Build the map of nodes reachable from the start node, by recursively
+ * visiting all accessible nodes. It is a breadth-first search, so the
+ * edges kept for each node will be the shortest path to that node.
+ */
+ while (!queue.isEmpty()) {
+ V node = queue.poll();
+ visited.add(node);
+ for (Edge<V, E> e : getAdjacentEdges(node)) {
+ V to = e.getTo();
+ if (!visited.contains(to)) {
+ queue.offer(e.getTo());
+ if (!hist.containsKey(e.getTo())) {
+ hist.put(e.getTo(), e);
+ }
+ }
+ }
+ }
+ /*
+ * Find path from start to end by traversing the edges backward, from
+ * the end node
+ */
+ V node = end;
+ Edge<V, E> edge = hist.get(node);
+ while (edge != null && node != start) {
+ path.add(edge);
+ node = edge.getFrom();
+ edge = hist.get(node);
+ }
+ Collections.reverse(path);
+ return path;
+ }
+
+ /**
+ * Check if this graph is connected, ie there are no partitions, all
+ * vertices are reachable from every other one. It is a depth-first visit of
+ * all vertices reachable from the first vertex of the graph.
+ *
+ * @return true if the graph is connected, false otherwise
+ */
+ public boolean isConnected() {
+ HashSet<V> visited = new HashSet<>();
+ Stack<V> stack = new Stack<>();
+ stack.push(fVertices.iterator().next());
+ while (!stack.isEmpty()) {
+ V node = stack.pop();
+ visited.add(node);
+ for (Edge<V, E> edge : getAdjacentEdges(node)) {
+ if (!visited.contains(edge.getTo())) {
+ stack.push(edge.getTo());
+ }
+ }
+ }
+ return visited.size() == fVertices.size();
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder str = new StringBuilder();
+ for (V key : fAdjacentEdges.keySet()) {
+ str.append(key + ": " + fAdjacentEdges.get(key) + "\n"); //$NON-NLS-1$ //$NON-NLS-2$
+ }
+ return str.toString();
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2014 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * Geneviève Bastien - Initial implementation and API
+ *******************************************************************************/
+
+package org.eclipse.linuxtools.internal.tmf.core.synchronization.graph;
+
+import java.math.BigDecimal;
+import java.util.List;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.eclipse.linuxtools.internal.tmf.core.synchronization.ITmfTimestampTransformInvertible;
+import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
+import org.eclipse.linuxtools.tmf.core.synchronization.TimestampTransformFactory;
+
+/**
+ * Implements a tree to calculate the synchronization between hosts
+ *
+ * TODO: This minimal implementation does not take into account the accuracy of
+ * the synchronization or the number of hops between 2 traces. A great
+ * improvement would be to implement Masoume Jabbarifar's minimal spanning tree
+ * algorithm to select reference trace(s) and optimal path to each node of the
+ * tree.
+ *
+ * @author Geneviève Bastien
+ */
+public class SyncSpanningTree {
+
+ private final SyncGraph<String, ITmfTimestampTransform> fSyncGraph;
+
+ /*
+ * Using a TreeSet here to make sure the order of the hosts, and thus the
+ * reference node, is predictable, mostly for unit tests.
+ */
+ private SortedSet<String> fHosts = new TreeSet<>();
+
+ /**
+ * Default constructor
+ */
+ public SyncSpanningTree() {
+ fSyncGraph = new SyncGraph<>();
+ }
+
+ /**
+ * Add a synchronization formula between hostFrom and hostTo with a given
+ * accuracy
+ *
+ * @param hostFrom
+ * Host from which the transform applies
+ * @param hostTo
+ * Host to which the transform applies
+ * @param transform
+ * The timestamp transform
+ * @param accuracy
+ * The accuracy of the synchronization between hostFrom and
+ * hostTo
+ */
+ public void addSynchronization(String hostFrom, String hostTo, ITmfTimestampTransform transform, BigDecimal accuracy) {
+ fHosts.add(hostFrom);
+ fHosts.add(hostTo);
+ fSyncGraph.addEdge(hostFrom, hostTo, transform);
+ if (transform instanceof ITmfTimestampTransformInvertible) {
+ fSyncGraph.addEdge(hostTo, hostFrom, ((ITmfTimestampTransformInvertible) transform).inverse());
+ }
+ }
+
+ /**
+ * Get the timestamp transform to a host
+ *
+ * FIXME: This might not work in situations where we have disjoint graphs
+ * since we only calculate 1 root node and each tree has its own root. When
+ * implementing the algorithm with minimal spanning tree, we will solve this
+ * problem.
+ *
+ * @param host
+ * The host to reach
+ * @return The timestamp transform to host
+ */
+ public ITmfTimestampTransform getTimestampTransform(String host) {
+ ITmfTimestampTransform result = TimestampTransformFactory.getDefaultTransform();
+ String rootNode = getRootNode();
+ /*
+ * Compute the path from reference node to the given host id
+ */
+ if (rootNode != null) {
+ List<Edge<String, ITmfTimestampTransform>> path = fSyncGraph.path(rootNode, host);
+ /*
+ * Compute the resulting transform by chaining each transforms on
+ * the path.
+ */
+ for (Edge<String, ITmfTimestampTransform> edge : path) {
+ result = result.composeWith(edge.getLabel());
+ }
+ }
+ return result;
+ }
+
+ private String getRootNode() {
+ /**
+ * Get the root node from which all other paths will be calculated. For
+ * now, we take the first node alphabetically.
+ */
+ if (fHosts.size() == 0) {
+ return null;
+ }
+ return fHosts.first();
+ }
+
+ /**
+ * Check if this multi-host synchronization tree is connected, ie all nodes
+ * have a synchronization path to a reference node.
+ *
+ * @return true if the tree is connected, false otherwise
+ */
+ public boolean isConnected() {
+ return fSyncGraph.isConnected();
+ }
+
+}
*
* Contributors:
* Geneviève Bastien - Initial implementation and API
+ * Francis Giraldeau - Transform computation using synchronization graph
*******************************************************************************/
package org.eclipse.linuxtools.tmf.core.synchronization;
import java.util.List;
import java.util.Map;
+import org.eclipse.linuxtools.internal.tmf.core.synchronization.graph.SyncSpanningTree;
import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
import org.eclipse.linuxtools.tmf.core.event.matching.TmfEventDependency;
import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
private static final MathContext fMc = MathContext.DECIMAL128;
+ /** @Serial */
private final List<ConvexHull> fSyncs;
+ private SyncSpanningTree fTree = null;
+
/**
* Initialization of the attributes
*/
ITmfTrace[] traceArr = traces.toArray(new ITmfTrace[traces.size()]);
fSyncs.clear();
/* Create a convex hull for all trace pairs */
+ // FIXME: is it necessary to make ConvexHull for every pairs up-front?
+ // The ConvexHull seems to be created on the fly in processMatch().
for (int i = 0; i < traceArr.length; i++) {
for (int j = i + 1; j < traceArr.length; j++) {
ConvexHull algo = new ConvexHull(traceArr[i].getHostId(), traceArr[j].getHostId());
fSyncs.add(algo);
}
algo.processMatch(match);
+ invalidateSyncGraph();
+ }
+ private void invalidateSyncGraph() {
+ fTree = null;
}
@Override
@Override
public ITmfTimestampTransform getTimestampTransform(String hostId) {
- for (ConvexHull traceSync : fSyncs) {
- if (traceSync.isTraceSynced(hostId)) {
- /*
- * Since there are many traces, maybe the reference trace is
- * also synchronized, so we need to chain sync formulas
- */
- ITmfTimestampTransform refTt = getTimestampTransform(traceSync.getReferenceHost());
- return refTt.composeWith(traceSync.getTimestampTransform(hostId));
+ SyncSpanningTree tree = getSyncTree();
+ return tree.getTimestampTransform(hostId);
+ }
+
+ /**
+ * Each convex hull computes the synchronization between 2 given hosts. A
+ * synchronization can be done on multiple hosts that may not all
+ * communicate with each other. We must use another algorithm to determine
+ * which host will be the reference node and what synchronization formula
+ * will be used between each host and this reference node.
+ *
+ * For example, take traces a, b and c where a and c talk to b but do not
+ * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
+ * the formulae between their 2 traces, but if a is the reference node, then
+ * the resulting formula of c would be the composition of {@literal a <-> b}
+ * and {@literal b <-> c}
+ *
+ * @return The synchronization spanning tree for this synchronization
+ */
+ private SyncSpanningTree getSyncTree() {
+ if (fTree == null) {
+ fTree = new SyncSpanningTree();
+ for (ConvexHull traceSync : fSyncs) {
+ SyncQuality q = traceSync.getQuality();
+ if (q == SyncQuality.ACCURATE || q == SyncQuality.APPROXIMATE) {
+ String from = traceSync.getReferenceHost();
+ String to = traceSync.getOtherHost();
+ fTree.addSynchronization(from, to, traceSync.getTimestampTransform(to), traceSync.getAccuracy());
+ }
}
}
- return TimestampTransformFactory.getDefaultTransform();
+ return fTree;
}
@Override
@Override
public boolean isTraceSynced(String hostId) {
- boolean traceSynced = false;
- for (ConvexHull traceSync : fSyncs) {
- traceSynced = traceSynced || traceSync.isTraceSynced(hostId);
- }
- return traceSynced;
+ ITmfTimestampTransform t = getTimestampTransform(hostId);
+ return !t.equals(TimestampTransformFactory.getDefaultTransform());
}
@Override
public Map<String, Map<String, Object>> getStats() {
+ /*
+ * TODO: Stats, while still accurate, may be misleading now that the
+ * sync tree changes synchronization formula. The stats should use the
+ * tree instead
+ */
Map<String, Map<String, Object>> statmap = new LinkedHashMap<>();
for (ConvexHull traceSync : fSyncs) {
statmap.put(traceSync.getReferenceHost() + " <==> " + traceSync.getOtherHost(), traceSync.getStats()); //$NON-NLS-1$
fBetamin = BigDecimal.ZERO;
fNbMatches = 0;
fNbAccurateMatches = 0;
- fQuality = SyncQuality.ABSENT;
+ fQuality = SyncQuality.ABSENT; // default quality
}
protected void processMatch(TmfEventDependency match) {
* and approximation of the synchronization at this time
*/
private void approximateSync() {
+
/**
* Line slopes functions
*
fAlpha = fAlphamax.add(fAlphamin).divide(BigDecimal.valueOf(2), fMc);
fBeta = fBetamin.add(fBetamax).divide(BigDecimal.valueOf(2), fMc);
if ((fLmax[0] == null) || (fLmin[0] == null)) {
- fQuality = SyncQuality.APPROXIMATE;
+ setQuality(SyncQuality.APPROXIMATE);
}
else if (fAlphamax.compareTo(fAlphamin) > 0) {
- fQuality = SyncQuality.ACCURATE;
+ setQuality(SyncQuality.ACCURATE);
} else {
/* Lines intersect, not good */
- fQuality = SyncQuality.FAIL;
+ setQuality(SyncQuality.FAIL);
}
} else if (((fLmax[0] == null) && (fLmin[1] == null))
|| ((fLmax[1] == null) && (fLmin[0] == null))) {
/* Either there is no upper hull point or no lower hull */
- fQuality = SyncQuality.INCOMPLETE;
+ setQuality(SyncQuality.INCOMPLETE);
}
}
}
public ITmfTimestampTransform getTimestampTransform(String hostId) {
- if (hostId.equals(fOtherHost) && (fQuality == SyncQuality.ACCURATE || fQuality == SyncQuality.APPROXIMATE || fQuality == SyncQuality.FAIL)) {
+ if (hostId.equals(fOtherHost) && (getQuality() == SyncQuality.ACCURATE || getQuality() == SyncQuality.APPROXIMATE || getQuality() == SyncQuality.FAIL)) {
/* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
}
return fQuality;
}
+ public BigDecimal getAccuracy() {
+ return fAlphamax.subtract(fAlphamin);
+ }
+
public Map<String, Object> getStats() {
if (fStats.size() == 0) {
String syncQuality;
- switch (fQuality) {
+ switch (getQuality()) {
case ABSENT:
syncQuality = Messages.SyncAlgorithmFullyIncremental_absent;
break;
fStats.put(Messages.SyncAlgorithmFullyIncremental_beta, fBeta);
fStats.put(Messages.SyncAlgorithmFullyIncremental_ub, (fUpperBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fUpperBoundList.size());
fStats.put(Messages.SyncAlgorithmFullyIncremental_lb, (fLowerBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fLowerBoundList.size());
- fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, fAlphamax.subtract(fAlphamin).doubleValue()); // -
- // fAlphamin);
+ fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, getAccuracy().doubleValue());
fStats.put(Messages.SyncAlgorithmFullyIncremental_nbmatch, (fNbMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbMatches);
fStats.put(Messages.SyncAlgorithmFullyIncremental_nbacc, (fNbAccurateMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbAccurateMatches);
fStats.put(Messages.SyncAlgorithmFullyIncremental_refformula, Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost);
return fOtherHost;
}
- public boolean isTraceSynced(String hostId) {
- /* Returns true if the timestamp transform is not identity */
- return (hostId.equals(fOtherHost) && (fQuality == SyncQuality.ACCURATE || fQuality == SyncQuality.APPROXIMATE || fQuality == SyncQuality.FAIL));
- }
-
public boolean isForHosts(String hostId1, String hostId2) {
return ((fReferenceHost.equals(hostId1) && fOtherHost.equals(hostId2)) || (fReferenceHost.equals(hostId2) && fOtherHost.equals(hostId1)));
}
fLmax[0] = null;
fLmax[1] = null;
s.defaultWriteObject();
-
}
@SuppressWarnings("nls")
b.append(" alpha " + fAlpha + " beta " + fBeta + " ]");
return b.toString();
}
+
+ private void setQuality(SyncQuality fQuality) {
+ this.fQuality = fQuality;
+ }
+
}
/**
return BigDecimal.valueOf(y.getValue()).subtract(alpha.multiply(BigDecimal.valueOf(x.getValue()), fMc));
}
+ @Override
+ public String toString() {
+ return String.format("%s (%s, %s)", this.getClass().getCanonicalName(), x, y); //$NON-NLS-1$
+ }
+ }
+
+ private void writeObject(ObjectOutputStream s)
+ throws IOException {
+ /*
+ * Remove the tree because it is not serializable
+ */
+ fTree = null;
+ s.defaultWriteObject();
}
}
projects / deliverable / tracecompass.git / commitdiff
