org.eclipse.tracecompass.tmf.core
Export-Package: org.eclipse.tracecompass.analysis.graph.core.base,
org.eclipse.tracecompass.analysis.graph.core.building,
+ org.eclipse.tracecompass.analysis.graph.core.criticalpath,
org.eclipse.tracecompass.internal.analysis.graph.core;x-internal=true;uses:="org.eclipse.tracecompass.common.core",
- org.eclipse.tracecompass.internal.analysis.graph.core.base;x-friends:="org.eclipse.tracecompass.analysis.graph.ui,org.eclipse.tracecompass.analysis.graph.core.tests"
+ org.eclipse.tracecompass.internal.analysis.graph.core.base;x-friends:="org.eclipse.tracecompass.analysis.graph.ui,org.eclipse.tracecompass.analysis.graph.core.tests",
+ org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;x-friends:="org.eclipse.tracecompass.analysis.graph.core.tests"
Import-Package: com.google.common.collect,
com.google.common.hash
output.. = bin/
bin.includes = META-INF/,\
plugin.properties,\
- .
+ .,\
+ plugin.xml
additional.bundles = org.eclipse.jdt.annotation
jars.extra.classpath = platform:/plugin/org.eclipse.jdt.annotation
--- /dev/null
+<?xml version="1.0" encoding="UTF-8"?>
+<?eclipse version="3.4"?>
+<plugin>
+ <extension
+ point="org.eclipse.linuxtools.tmf.core.analysis">
+ <module
+ analysis_module="org.eclipse.tracecompass.analysis.graph.core.criticalpath.CriticalPathModule"
+ id="org.eclipse.tracecompass.analysis.graph.core.criticalpath"
+ name="Critical Path">
+ <parameter
+ name="graph">
+ </parameter>
+ <parameter
+ name="workerid">
+ </parameter>
+ <parameter
+ name="algorithm">
+ </parameter>
+ <tracetype
+ class="org.eclipse.tracecompass.tmf.core.trace.TmfTrace">
+ </tracetype>
+ </module>
+ </extension>
+</plugin>
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.analysis.graph.core.criticalpath;
+
+import org.eclipse.core.runtime.IProgressMonitor;
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.osgi.util.NLS;
+import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
+import org.eclipse.tracecompass.analysis.graph.core.building.TmfGraphBuilderModule;
+import org.eclipse.tracecompass.common.core.NonNullUtils;
+import org.eclipse.tracecompass.internal.analysis.graph.core.Activator;
+import org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath.CriticalPathAlgorithmBounded;
+import org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath.Messages;
+import org.eclipse.tracecompass.tmf.core.analysis.IAnalysisModule;
+import org.eclipse.tracecompass.tmf.core.analysis.TmfAbstractAnalysisModule;
+import org.eclipse.tracecompass.tmf.core.exceptions.TmfAnalysisException;
+import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimeRange;
+import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
+import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager;
+import org.eclipse.tracecompass.tmf.core.trace.TmfTraceUtils;
+
+/**
+ * Class to implement the critical path analysis
+ *
+ * @author Francis Giraldeau
+ * @author Geneviève Bastien
+ */
+public class CriticalPathModule extends TmfAbstractAnalysisModule {
+
+ /**
+ * Analysis ID for this module
+ */
+ public static final String ANALYSIS_ID = "org.eclipse.tracecompass.analysis.graph.core.criticalpath"; //$NON-NLS-1$
+
+ /** Graph parameter name */
+ public static final String PARAM_GRAPH = "graph"; //$NON-NLS-1$
+
+ /** Worker_id parameter name */
+ public static final String PARAM_WORKER = "workerid"; //$NON-NLS-1$
+
+ private @Nullable TmfGraphBuilderModule fGraphModule;
+
+ private @Nullable TmfGraph fCriticalPath;
+
+ /**
+ * Default constructor
+ */
+ public CriticalPathModule() {
+ super();
+ }
+
+ @Override
+ protected boolean executeAnalysis(final IProgressMonitor monitor) throws TmfAnalysisException {
+ /* Get the graph */
+ TmfGraphBuilderModule graphModule = getGraph();
+ if (graphModule == null) {
+ Activator.getInstance().logWarning("No graph was found to execute the critical path on"); //$NON-NLS-1$
+ return true;
+ }
+ graphModule.schedule();
+
+ monitor.setTaskName(NLS.bind(Messages.CriticalPathModule_waitingForGraph, graphModule.getName()));
+ if (!graphModule.waitForCompletion(monitor)) {
+ Activator.getInstance().logInfo("Critical path execution: graph building was cancelled. Results may not be accurate."); //$NON-NLS-1$
+ return false;
+ }
+ TmfGraph graph = graphModule.getGraph();
+ if (graph == null) {
+ throw new TmfAnalysisException("Critical Path analysis: graph " + graphModule.getName() + " is null"); //$NON-NLS-1$//$NON-NLS-2$
+ }
+
+ /* Get the worker id */
+ Object workerObj = getParameter(PARAM_WORKER);
+ if (workerObj == null) {
+ return false;
+ }
+ if (!(workerObj instanceof IGraphWorker)) {
+ throw new IllegalStateException();
+ }
+ IGraphWorker worker = (IGraphWorker) workerObj;
+
+ TmfVertex head = graph.getHead(worker);
+ if (head == null) {
+ /* Nothing happens with this worker, return an empty graph */
+ fCriticalPath = new TmfGraph();
+ return true;
+ }
+ TmfTimeRange tr = TmfTraceManager.getInstance().getCurrentTraceContext().getWindowRange();
+ TmfVertex start = graph.getVertexAt(tr.getStartTime(), worker);
+ if (start == null) {
+ /*
+ * Nothing happens with this worker after start, return an empty
+ * graph
+ */
+ fCriticalPath = new TmfGraph();
+ return true;
+ }
+ ICriticalPathAlgorithm cp = getAlgorithm(graph);
+ fCriticalPath = cp.compute(start, null);
+
+ return true;
+ }
+
+ @Override
+ protected void canceling() {
+
+ }
+
+ @Override
+ public @Nullable Object getParameter(String name) {
+ if (name.equals(PARAM_GRAPH)) {
+ return getGraph();
+ }
+ return super.getParameter(name);
+ }
+
+ @Override
+ public synchronized void setParameter(String name, @Nullable Object value) throws RuntimeException {
+ if (name.equals(PARAM_GRAPH) && (value instanceof String)) {
+ setGraph((String) value);
+ }
+ super.setParameter(name, value);
+ }
+
+ @Override
+ protected void parameterChanged(String name) {
+ cancel();
+ resetAnalysis();
+ schedule();
+ }
+
+ /**
+ * The value of graph should be the id of the analysis module that builds
+ * the required graph
+ *
+ * @param graphName
+ * Id of the graph
+ */
+ private void setGraph(String graphName) {
+ ITmfTrace trace = getTrace();
+ if (trace == null) {
+ return;
+ }
+ IAnalysisModule module = trace.getAnalysisModule(graphName);
+ if (module instanceof TmfGraphBuilderModule) {
+ fGraphModule = (TmfGraphBuilderModule) module;
+ }
+ }
+
+ private @Nullable TmfGraphBuilderModule getGraph() {
+ /* The graph module is null, take the first available graph if any */
+ TmfGraphBuilderModule module = fGraphModule;
+ if (module == null) {
+ ITmfTrace trace = getTrace();
+ if (trace == null) {
+ return fGraphModule;
+ }
+ for (TmfGraphBuilderModule mod : TmfTraceUtils.getAnalysisModulesOfClass(trace, TmfGraphBuilderModule.class)) {
+ module = mod;
+ break;
+ }
+ if (module != null) {
+ fGraphModule = module;
+ }
+ }
+ return module;
+ }
+
+ private static ICriticalPathAlgorithm getAlgorithm(TmfGraph graph) {
+ return new CriticalPathAlgorithmBounded(graph);
+ }
+
+ @Override
+ public boolean canExecute(@NonNull ITmfTrace trace) {
+ /*
+ * TODO: The critical path executes on a graph, so at least a graph must
+ * be available for this trace
+ */
+ return true;
+ }
+
+ /**
+ * Gets the graph for the critical path
+ *
+ * @return The critical path graph
+ */
+ public @Nullable TmfGraph getCriticalPath() {
+ return fCriticalPath;
+ }
+
+ @Override
+ protected @NonNull String getFullHelpText() {
+ return NonNullUtils.nullToEmptyString(Messages.CriticalPathModule_fullHelpText);
+ }
+
+ @Override
+ protected @NonNull String getShortHelpText(ITmfTrace trace) {
+ return getFullHelpText();
+ }
+
+ @Override
+ protected @NonNull String getTraceCannotExecuteHelpText(@NonNull ITmfTrace trace) {
+ return NonNullUtils.nullToEmptyString(Messages.CriticalPathModule_cantExecute);
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.analysis.graph.core.criticalpath;
+
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
+
+/**
+ * Interface for all critical path algorithms
+ *
+ * @author Francis Giraldeau
+ */
+public interface ICriticalPathAlgorithm {
+
+ /**
+ * Computes the critical path
+ *
+ * @param start
+ * The starting vertex
+ * @param end
+ * The end vertex
+ * @return The graph of the critical path
+ */
+ public TmfGraph compute(TmfVertex start, @Nullable TmfVertex end);
+
+ /**
+ * Unique ID of this analysis
+ *
+ * @return the ID string
+ */
+ public String getID();
+
+ /**
+ * Human readable display name
+ *
+ * @return display name
+ */
+ public String getDisplayName();
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.analysis.graph.core.criticalpath;
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
+
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex.EdgeDirection;
+import org.eclipse.tracecompass.analysis.graph.core.criticalpath.ICriticalPathAlgorithm;
+import org.eclipse.tracecompass.common.core.NonNullUtils;
+
+/**
+ * Abstract class for critical path algorithms
+ *
+ * @author Francis Giraldeau
+ */
+public abstract class AbstractCriticalPathAlgorithm implements ICriticalPathAlgorithm {
+
+ private final TmfGraph fGraph;
+
+ /**
+ * Constructor
+ *
+ * @param graph
+ * The graph on which to calculate critical path
+ */
+ public AbstractCriticalPathAlgorithm(TmfGraph graph) {
+ fGraph = graph;
+ }
+
+ /**
+ * Get the graph
+ *
+ * @return the graph
+ */
+ public TmfGraph getGraph() {
+ return fGraph;
+ }
+
+ /**
+ * Copy link of type TYPE between nodes FROM and TO in the graph PATH. The
+ * return value is the tail node for the new path.
+ *
+ * @param criticalPath
+ * The graph on which to add the link
+ * @param graph
+ * The original graph on which to calculate critical path
+ * @param anchor
+ * The anchor vertex from the path graph
+ * @param from
+ * The origin vertex in the main graph
+ * @param to
+ * The destination vertex in the main graph
+ * @param ts
+ * The timestamp of the edge
+ * @param type
+ * The type of the edge to create
+ * @return The destination vertex in the path graph
+ */
+ public TmfVertex copyLink(TmfGraph criticalPath, TmfGraph graph, TmfVertex anchor, TmfVertex from, TmfVertex to, long ts, TmfEdge.EdgeType type) {
+ IGraphWorker parentFrom = graph.getParentOf(from);
+ IGraphWorker parentTo = graph.getParentOf(to);
+ if (parentTo == null) {
+ throw new NullPointerException();
+ }
+ TmfVertex tmp = new TmfVertex(ts);
+ criticalPath.add(parentTo, tmp);
+ if (parentFrom == parentTo) {
+ anchor.linkHorizontal(tmp).setType(type);
+ } else {
+ anchor.linkVertical(tmp).setType(type);
+ }
+ return tmp;
+ }
+
+ /**
+ * Find the next incoming vertex from another object (in vertical) from a
+ * node in a given direction
+ *
+ * @param vertex
+ * The starting vertex
+ * @param dir
+ * The direction in which to search
+ * @return The next incoming vertex
+ */
+ public static @Nullable TmfVertex findIncoming(TmfVertex vertex, EdgeDirection dir) {
+ TmfVertex currentVertex = vertex;
+ while (true) {
+ TmfEdge incoming = currentVertex.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
+ if (incoming != null) {
+ return currentVertex;
+ }
+ TmfEdge edge = currentVertex.getEdge(dir);
+ if (edge == null || edge.getType() != TmfEdge.EdgeType.EPS) {
+ break;
+ }
+ currentVertex = TmfVertex.getNeighborFromEdge(edge, dir);
+ }
+ return null;
+ }
+
+ @Override
+ public String getID() {
+ return NonNullUtils.checkNotNull(getClass().getName());
+ }
+
+ @Override
+ public String getDisplayName() {
+ return NonNullUtils.checkNotNull(getClass().getSimpleName());
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.analysis.graph.core.criticalpath.ICriticalPathAlgorithm;
+
+/**
+ * Register algorithm
+ *
+ * FIXME: is there already a facility in Eclipse to replace this class?
+ * @author Francis Giraldeau
+ *
+ */
+public final class AlgorithmManager {
+
+ private static @Nullable AlgorithmManager INSTANCE;
+ private final Map<String, Class<? extends ICriticalPathAlgorithm>> map;
+
+ private AlgorithmManager() {
+ map = new HashMap<>();
+ }
+
+ /**
+ * Get the singleton instance
+ *
+ * @return the instance
+ */
+ public static AlgorithmManager getInstance() {
+ AlgorithmManager manager = INSTANCE;
+ if (manager == null) {
+ manager = new AlgorithmManager();
+ manager.register(CriticalPathAlgorithmBounded.class);
+ INSTANCE = manager;
+ }
+ return manager;
+ }
+
+ /**
+ * Register a type in the manager
+ *
+ * @param type the class to register
+ */
+ public void register(Class<? extends ICriticalPathAlgorithm> type) {
+ map.put(type.getSimpleName(), type);
+ }
+
+ /**
+ * Return registered types
+ * @return the types
+ */
+ public Map<String, Class<? extends ICriticalPathAlgorithm>> registeredTypes() {
+ return map;
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
+
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Stack;
+
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
+import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex.EdgeDirection;
+
+/**
+ * Critical path bounded algorithm: backward resolution of blocking limited to
+ * the blocking window
+ *
+ * This algorithm is described in
+ *
+ * F. Giraldeau and M.Dagenais, Wait analysis of distributed systems using
+ * kernel tracing, IEEE Transactions on Parallel and Distributed Systems
+ *
+ * @author Francis Giraldeau
+ */
+public class CriticalPathAlgorithmBounded extends AbstractCriticalPathAlgorithm {
+
+ /**
+ * Constructor
+ *
+ * @param graph
+ * The graph on which to calculate the critical path
+ */
+ public CriticalPathAlgorithmBounded(TmfGraph graph) {
+ super(graph);
+ }
+
+ @Override
+ public TmfGraph compute(TmfVertex start, @Nullable TmfVertex end) {
+ /* Create new graph for the critical path result */
+ TmfGraph criticalPath = new TmfGraph();
+
+ /* Get the main graph from which to get critical path */
+ TmfGraph graph = getGraph();
+
+ /*
+ * Calculate path starting from the object the start vertex belongs to
+ */
+ IGraphWorker parent = graph.getParentOf(start);
+ if (parent == null) {
+ throw new NullPointerException();
+ }
+ criticalPath.add(parent, new TmfVertex(start));
+ TmfVertex currentVertex = start;
+ TmfEdge nextEdge = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
+
+ long endTime = Long.MAX_VALUE;
+ if (end != null) {
+ endTime = end.getTs();
+ }
+
+ /*
+ * Run through all horizontal edges from this object and resolve each
+ * blocking as they come
+ */
+ while (nextEdge != null) {
+ TmfVertex nextVertex = nextEdge.getVertexTo();
+ if (nextVertex.getTs() >= endTime) {
+ break;
+ }
+ switch (nextEdge.getType()) {
+ case USER_INPUT:
+ case BLOCK_DEVICE:
+ case TIMER:
+ case INTERRUPTED:
+ case PREEMPTED:
+ case RUNNING:
+ /**
+ * This edge is not blocked, so nothing to resolve, just add the
+ * edge to the critical path
+ */
+ /**
+ * TODO: Normally, the parent of the link's vertex to should be
+ * the object itself, verify if that is true
+ */
+ IGraphWorker parentTo = graph.getParentOf(nextEdge.getVertexTo());
+ if (parentTo == null) {
+ throw new NullPointerException();
+ }
+ if (parentTo != parent) {
+ System.err.println("no, the parents of horizontal edges are not always identical... shouldn't they be?"); //$NON-NLS-1$
+ }
+ criticalPath.append(parentTo, new TmfVertex(nextEdge.getVertexTo()), nextEdge.getType());
+ break;
+ case NETWORK:
+ case BLOCKED:
+ List<TmfEdge> links = resolveBlockingBounded(nextEdge, nextEdge.getVertexFrom());
+ Collections.reverse(links);
+ appendPathComponent(criticalPath, graph, currentVertex, links);
+ break;
+ case EPS:
+ if (nextEdge.getDuration() != 0) {
+ throw new RuntimeException("epsilon duration is not zero " + nextEdge); //$NON-NLS-1$
+ }
+ break;
+ case DEFAULT:
+ throw new RuntimeException("Illegal link type " + nextEdge.getType()); //$NON-NLS-1$
+ case UNKNOWN:
+ default:
+ break;
+ }
+ currentVertex = nextVertex;
+ nextEdge = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
+ }
+ return criticalPath;
+ }
+
+ /** Add the links to the critical path, with currentVertex to glue to */
+ private void appendPathComponent(TmfGraph criticalPath, TmfGraph graph, TmfVertex currentVertex, List<TmfEdge> links) {
+ IGraphWorker currentActor = graph.getParentOf(currentVertex);
+ if (currentActor == null) {
+ throw new NullPointerException();
+ }
+ if (links.isEmpty()) {
+ /*
+ * The next vertex should not be null, since we glue only after
+ * resolve of the blocking of the edge to that vertex
+ */
+ TmfEdge next = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
+ if (next == null) {
+ return;
+ }
+ criticalPath.append(currentActor, new TmfVertex(next.getVertexTo()), next.getType());
+ return;
+ }
+ // FIXME: assert last link.to actor == currentActor
+
+ // attach subpath to b1 and b2
+ TmfVertex b1 = criticalPath.getTail(currentActor);
+ if (b1 == null) {
+ throw new NullPointerException();
+ }
+ // TmfVertex b2 = new TmfVertex(curr.neighbor(TmfVertex.OUTH));
+
+ // glue head
+ TmfEdge lnk = links.get(0);
+ TmfVertex anchor = null;
+ IGraphWorker objSrc = graph.getParentOf(lnk.getVertexFrom());
+ if (objSrc == null) {
+ throw new NullPointerException();
+ }
+ if (objSrc == currentActor) {
+ anchor = b1;
+ } else {
+ anchor = new TmfVertex(currentVertex);
+ criticalPath.add(objSrc, anchor);
+ b1.linkVertical(anchor);
+ /* fill any gap with UNKNOWN */
+ if (lnk.getVertexFrom().compareTo(anchor) > 0) {
+ anchor = new TmfVertex(lnk.getVertexFrom());
+ TmfEdge edge = criticalPath.append(objSrc, anchor);
+ if (edge == null) {
+ throw new NullPointerException();
+ }
+ edge.setType(TmfEdge.EdgeType.UNKNOWN);
+ }
+ }
+
+ // glue body
+ TmfEdge prev = null;
+ for (TmfEdge link : links) {
+ // check connectivity
+ if (prev != null && prev.getVertexTo() != link.getVertexFrom()) {
+ anchor = copyLink(criticalPath, graph, anchor, prev.getVertexTo(), link.getVertexFrom(),
+ prev.getVertexTo().getTs(), TmfEdge.EdgeType.DEFAULT);
+ }
+ anchor = copyLink(criticalPath, graph, anchor, link.getVertexFrom(), link.getVertexTo(),
+ link.getVertexTo().getTs(), link.getType());
+ prev = link;
+ }
+ }
+
+ /**
+ * Resolve a blocking by going through the graph vertically from the
+ * blocking edge
+ *
+ * FIXME: build a tree with partial subpath in order to return the best
+ * path, not the last one traversed
+ *
+ * @param blocking
+ * The blocking edge
+ * @param bound
+ * The vertex that limits the boundary until which to resolve the
+ * blocking
+ * @return The list of non-blocking edges
+ */
+ private List<TmfEdge> resolveBlockingBounded(TmfEdge blocking, TmfVertex bound) {
+
+ LinkedList<TmfEdge> subPath = new LinkedList<>();
+ TmfVertex junction = findIncoming(blocking.getVertexTo(), EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
+ /* if wake-up source is not found, return empty list */
+ if (junction == null) {
+ return subPath;
+ }
+
+ TmfEdge down = junction.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
+ if (down == null) {
+ throw new NullPointerException();
+ }
+ subPath.add(down);
+ TmfVertex vertexFrom = down.getVertexFrom();
+
+ TmfVertex currentBound = bound.compareTo(blocking.getVertexFrom()) < 0 ? blocking.getVertexFrom() : bound;
+
+ Stack<TmfVertex> stack = new Stack<>();
+ while (vertexFrom != null && vertexFrom.compareTo(currentBound) > 0) {
+ /* shortcut for down link that goes beyond the blocking */
+ TmfEdge inVerticalEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
+ if (inVerticalEdge != null && inVerticalEdge.getVertexFrom().compareTo(currentBound) <= 0) {
+ subPath.add(inVerticalEdge);
+ break;
+ }
+
+ /**
+ * Add DOWN links to explore stack in case dead-end occurs. Here is
+ * an example to illustrate the procedure.
+ *
+ * <pre>
+ * -------------------------
+ * BLOCKED | PREEMPT
+ * -------------------------
+ * ^
+ * |WAKE-UP
+ * |
+ * +--------------------+
+ * +-------+ INTERRUPT +--------+
+ * +--------------------+
+ * ^ ^ | ^
+ * | | | |
+ * + + v +
+ * 1 2 3 4
+ * </pre>
+ *
+ * The event wake-up is followed backward. The edge 4 will never be
+ * visited (it cannot be the cause of the wake-up, because it occurs
+ * after it). The edge 3 will not be explored, because it is
+ * outgoing. The edges 2 and 1 will be pushed on the stack. When the
+ * beginning of the interrupt is reached, then the edges on the
+ * stack will be explored.
+ *
+ * If a dead-end is reached, while the stack is not empty, the
+ * accumulated path is rewinded, and a different incoming edge is
+ * tried. The backward traversal ends if there is nothing left to
+ * explore, or if the start of the blocking window start is reached.
+ *
+ * Do not add if left is BLOCKED, because this link would be visited
+ * twice
+ */
+ TmfEdge incomingEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
+ if (inVerticalEdge != null &&
+ (incomingEdge == null ||
+ incomingEdge.getType() != TmfEdge.EdgeType.BLOCKED ||
+ incomingEdge.getType() != TmfEdge.EdgeType.NETWORK)) {
+ stack.push(vertexFrom);
+ }
+ if (incomingEdge != null) {
+ if (incomingEdge.getType() == TmfEdge.EdgeType.BLOCKED || incomingEdge.getType() == TmfEdge.EdgeType.NETWORK) {
+ subPath.addAll(resolveBlockingBounded(incomingEdge, currentBound));
+ } else {
+ subPath.add(incomingEdge);
+ }
+ vertexFrom = incomingEdge.getVertexFrom();
+ } else {
+ if (!stack.isEmpty()) {
+ TmfVertex v = stack.pop();
+ /* rewind subpath */
+ while (!subPath.isEmpty() && subPath.getLast().getVertexFrom() != v) {
+ subPath.removeLast();
+ }
+ TmfEdge edge = v.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
+ if (edge != null) {
+ subPath.add(edge);
+ vertexFrom = edge.getVertexFrom();
+ continue;
+ }
+ }
+ vertexFrom = null;
+ }
+
+ }
+ return subPath;
+ }
+
+}
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
+
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.osgi.util.NLS;
+
+/**
+ * Externalized string for this package
+ *
+ * @author Geneviève Bastien
+ */
+@SuppressWarnings("javadoc")
+public class Messages {
+ private static final String BUNDLE_NAME = "org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath.messages"; //$NON-NLS-1$
+
+ public static @Nullable String CriticalPathModule_waitingForGraph;
+ public static @Nullable String CriticalPathModule_fullHelpText;
+ public static @Nullable String CriticalPathModule_cantExecute;
+
+ static {
+ // initialize resource bundle
+ NLS.initializeMessages(BUNDLE_NAME, Messages.class);
+ }
+
+ private Messages() {
+ }
+
+}
--- /dev/null
+###############################################################################
+# Copyright (c) 2015 É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
+###############################################################################
+
+CriticalPathModule_waitingForGraph=Waiting for {0} module to complete...
+CriticalPathModule_fullHelpText=Computes the critical path of an execution graph. To compute the critical path, you need to select a process in the control flow view and the path will be computed for that process.
+CriticalPathModule_cantExecute=There is no graph available on which to compute the critical path
\ No newline at end of file
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2015 É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
+ *******************************************************************************/
+
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
\ No newline at end of file
projects / deliverable / tracecompass.git / commitdiff
