From 51480ca28a10b91f2d8cc0fa0c041a233d7e3baa Mon Sep 17 00:00:00 2001 From: Francis Giraldeau Date: Mon, 29 Jun 2015 21:52:14 -0400 Subject: [PATCH] Analysis: Add the active path module MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This module computes the active path from a execution graph. The active path of a given task has all the blockings replaced recursively by the edges representing the cause of the wait at the system level. Change-Id: Ie19b461ebe5ad595bca43b55f380ce28db416445 Signed-off-by: Geneviève Bastien Signed-off-by: Francis Giraldeau Reviewed-on: https://git.eclipse.org/r/51081 Reviewed-by: Hudson CI Reviewed-by: Matthew Khouzam Tested-by: Matthew Khouzam --- .../META-INF/MANIFEST.MF | 4 +- .../build.properties | 3 +- .../plugin.xml | 24 ++ .../core/criticalpath/CriticalPathModule.java | 216 +++++++++++++ .../criticalpath/ICriticalPathAlgorithm.java | 48 +++ .../graph/core/criticalpath/package-info.java | 11 + .../AbstractCriticalPathAlgorithm.java | 121 +++++++ .../core/criticalpath/AlgorithmManager.java | 66 ++++ .../CriticalPathAlgorithmBounded.java | 303 ++++++++++++++++++ .../graph/core/criticalpath/Messages.java | 36 +++ .../core/criticalpath/messages.properties | 12 + .../graph/core/criticalpath/package-info.java | 11 + 12 files changed, 853 insertions(+), 2 deletions(-) create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/plugin.xml create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/CriticalPathModule.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/ICriticalPathAlgorithm.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/package-info.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AbstractCriticalPathAlgorithm.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AlgorithmManager.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/CriticalPathAlgorithmBounded.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/Messages.java create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/messages.properties create mode 100644 analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/package-info.java diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/META-INF/MANIFEST.MF b/analysis/org.eclipse.tracecompass.analysis.graph.core/META-INF/MANIFEST.MF index 1a8a243c73..77f2ab0bd1 100644 --- a/analysis/org.eclipse.tracecompass.analysis.graph.core/META-INF/MANIFEST.MF +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/META-INF/MANIFEST.MF @@ -15,7 +15,9 @@ Require-Bundle: org.eclipse.ui, 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 diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/build.properties b/analysis/org.eclipse.tracecompass.analysis.graph.core/build.properties index 98fef14eb0..56580e770e 100644 --- a/analysis/org.eclipse.tracecompass.analysis.graph.core/build.properties +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/build.properties @@ -14,6 +14,7 @@ source.. = src/ 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 diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/plugin.xml b/analysis/org.eclipse.tracecompass.analysis.graph.core/plugin.xml new file mode 100644 index 0000000000..8c7a04084c --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/plugin.xml @@ -0,0 +1,24 @@ + + + + + + + + + + + + + + + + diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/CriticalPathModule.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/CriticalPathModule.java new file mode 100644 index 0000000000..549bc6c653 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/CriticalPathModule.java @@ -0,0 +1,216 @@ +/******************************************************************************* + * 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); + } + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/ICriticalPathAlgorithm.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/ICriticalPathAlgorithm.java new file mode 100644 index 0000000000..f564f99594 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/ICriticalPathAlgorithm.java @@ -0,0 +1,48 @@ +/******************************************************************************* + * 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(); + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/package-info.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/package-info.java new file mode 100644 index 0000000000..4e1c0b7cc1 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/analysis/graph/core/criticalpath/package-info.java @@ -0,0 +1,11 @@ +/******************************************************************************* + * 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 diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AbstractCriticalPathAlgorithm.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AbstractCriticalPathAlgorithm.java new file mode 100644 index 0000000000..ce9051f866 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AbstractCriticalPathAlgorithm.java @@ -0,0 +1,121 @@ +/******************************************************************************* + * 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()); + } + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AlgorithmManager.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AlgorithmManager.java new file mode 100644 index 0000000000..78504c0de5 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/AlgorithmManager.java @@ -0,0 +1,66 @@ +/******************************************************************************* + * 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> 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 type) { + map.put(type.getSimpleName(), type); + } + + /** + * Return registered types + * @return the types + */ + public Map> registeredTypes() { + return map; + } + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/CriticalPathAlgorithmBounded.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/CriticalPathAlgorithmBounded.java new file mode 100644 index 0000000000..4179b92b17 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/CriticalPathAlgorithmBounded.java @@ -0,0 +1,303 @@ +/******************************************************************************* + * 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 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 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 resolveBlockingBounded(TmfEdge blocking, TmfVertex bound) { + + LinkedList 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 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. + * + * 
+             *           -------------------------
+             *            BLOCKED    | PREEMPT
+             *           -------------------------
+             *                       ^
+             *                       |WAKE-UP
+             *                       |
+             *         +--------------------+
+             * +-------+      INTERRUPT     +--------+
+             *         +--------------------+
+             *           ^   ^   |       ^
+             *           |   |   |       |
+             *           +   +   v       +
+             *           1   2   3       4
+             *
+ * + * 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; + } + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/Messages.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/Messages.java new file mode 100644 index 0000000000..b0dc804f2f --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/Messages.java @@ -0,0 +1,36 @@ +/******************************************************************************* + * 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() { + } + +} diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/messages.properties b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/messages.properties new file mode 100644 index 0000000000..52bd9410b1 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/messages.properties @@ -0,0 +1,12 @@ +############################################################################### +# 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 diff --git a/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/package-info.java b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/package-info.java new file mode 100644 index 0000000000..a954674bc5 --- /dev/null +++ b/analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/package-info.java @@ -0,0 +1,11 @@ +/******************************************************************************* + * 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 -- 2.34.1