analysis/org.eclipse.tracecompass.analysis.graph.core/src/org/eclipse/tracecompass/internal/analysis/graph/core/criticalpath/CriticalPathAlgorithmBounded.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *******************************************************************************/
   9
  10 package org.eclipse.tracecompass.internal.analysis.graph.core.criticalpath;
  11
  12 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  13
  14 import java.util.Collections;
  15 import java.util.LinkedList;
  16 import java.util.List;
  17 import java.util.Stack;
  18
  19 import org.eclipse.jdt.annotation.Nullable;
  20 import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
  21 import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
  22 import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
  23 import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
  24 import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex.EdgeDirection;
  25 import org.eclipse.tracecompass.analysis.graph.core.criticalpath.CriticalPathAlgorithmException;
  26
  27 /**
  28  * Critical path bounded algorithm: backward resolution of blocking limited to
  29  * the blocking window
  30  *
  31  * This algorithm is described in
  32  *
  33  * F. Giraldeau and M.Dagenais, Wait analysis of distributed systems using
  34  * kernel tracing, IEEE Transactions on Parallel and Distributed Systems
  35  *
  36  * @author Francis Giraldeau
  37  */
  38 public class CriticalPathAlgorithmBounded extends AbstractCriticalPathAlgorithm {
  39
  40     /**
  41      * Constructor
  42      *
  43      * @param graph
  44      *            The graph on which to calculate the critical path
  45      */
  46     public CriticalPathAlgorithmBounded(TmfGraph graph) {
  47         super(graph);
  48     }
  49
  50     @Override
  51     public TmfGraph compute(TmfVertex start, @Nullable TmfVertex end) throws CriticalPathAlgorithmException {
  52         /* Create new graph for the critical path result */
  53         TmfGraph criticalPath = new TmfGraph();
  54
  55         /* Get the main graph from which to get critical path */
  56         TmfGraph graph = getGraph();
  57
  58         /*
  59          * Calculate path starting from the object the start vertex belongs to
  60          */
  61         IGraphWorker parent = checkNotNull(graph.getParentOf(start));
  62         criticalPath.add(parent, new TmfVertex(start));
  63         TmfVertex currentVertex = start;
  64         TmfEdge nextEdge = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
  65
  66         long endTime = Long.MAX_VALUE;
  67         if (end != null) {
  68             endTime = end.getTs();
  69         }
  70
  71         /*
  72          * Run through all horizontal edges from this object and resolve each
  73          * blocking as they come
  74          */
  75         while (nextEdge != null) {
  76             TmfVertex nextVertex = nextEdge.getVertexTo();
  77             if (nextVertex.getTs() >= endTime) {
  78                 break;
  79             }
  80             switch (nextEdge.getType()) {
  81             case IPI:
  82             case USER_INPUT:
  83             case BLOCK_DEVICE:
  84             case TIMER:
  85             case INTERRUPTED:
  86             case PREEMPTED:
  87             case RUNNING:
  88                 /**
  89                  * This edge is not blocked, so nothing to resolve, just add the
  90                  * edge to the critical path
  91                  */
  92                 /**
  93                  * TODO: Normally, the parent of the link's vertex to should be
  94                  * the object itself, verify if that is true
  95                  */
  96                 IGraphWorker parentTo = checkNotNull(graph.getParentOf(nextEdge.getVertexTo()));
  97                 if (parentTo != parent) {
  98                     throw new CriticalPathAlgorithmException("no, the parents of horizontal edges are not always identical... shouldn't they be?"); //$NON-NLS-1$
  99                 }
 100                 criticalPath.append(parentTo, new TmfVertex(nextEdge.getVertexTo()), nextEdge.getType());
 101                 break;
 102             case NETWORK:
 103             case BLOCKED:
 104                 List<TmfEdge> links = resolveBlockingBounded(nextEdge, nextEdge.getVertexFrom());
 105                 Collections.reverse(links);
 106                 appendPathComponent(criticalPath, graph, currentVertex, links);
 107                 break;
 108             case EPS:
 109                 if (nextEdge.getDuration() != 0) {
 110                     throw new CriticalPathAlgorithmException("epsilon duration is not zero " + nextEdge); //$NON-NLS-1$
 111                 }
 112                 break;
 113             case DEFAULT:
 114                 throw new CriticalPathAlgorithmException("Illegal link type " + nextEdge.getType()); //$NON-NLS-1$
 115             case UNKNOWN:
 116             default:
 117                 break;
 118             }
 119             currentVertex = nextVertex;
 120             nextEdge = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
 121         }
 122         return criticalPath;
 123     }
 124
 125     /** Add the links to the critical path, with currentVertex to glue to */
 126     private void appendPathComponent(TmfGraph criticalPath, TmfGraph graph, TmfVertex currentVertex, List<TmfEdge> links) {
 127         IGraphWorker currentActor = checkNotNull(graph.getParentOf(currentVertex));
 128         if (links.isEmpty()) {
 129             /*
 130              * The next vertex should not be null, since we glue only after
 131              * resolve of the blocking of the edge to that vertex
 132              */
 133             TmfEdge next = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
 134             if (next == null) {
 135                 return;
 136             }
 137             criticalPath.append(currentActor, new TmfVertex(next.getVertexTo()), next.getType());
 138             return;
 139         }
 140         // FIXME: assert last link.to actor == currentActor
 141
 142         // attach subpath to b1
 143         TmfVertex b1 = checkNotNull(criticalPath.getTail(currentActor));
 144
 145         // glue head
 146         TmfEdge lnk = links.get(0);
 147         TmfVertex anchor = null;
 148         IGraphWorker objSrc = checkNotNull(graph.getParentOf(lnk.getVertexFrom()));
 149         if (objSrc.equals( currentActor)) {
 150             anchor = b1;
 151         } else {
 152             anchor = new TmfVertex(currentVertex);
 153             criticalPath.add(objSrc, anchor);
 154             b1.linkVertical(anchor);
 155             /* fill any gap with UNKNOWN */
 156             if (lnk.getVertexFrom().compareTo(anchor) > 0) {
 157                 anchor = new TmfVertex(lnk.getVertexFrom());
 158                 TmfEdge edge = checkNotNull(criticalPath.append(objSrc, anchor));
 159                 edge.setType(TmfEdge.EdgeType.UNKNOWN);
 160             }
 161         }
 162
 163         // glue body
 164         TmfEdge prev = null;
 165         for (TmfEdge link : links) {
 166             // check connectivity
 167             if (prev != null && prev.getVertexTo() != link.getVertexFrom()) {
 168                 anchor = copyLink(criticalPath, graph, anchor, prev.getVertexTo(), link.getVertexFrom(),
 169                         prev.getVertexTo().getTs(), TmfEdge.EdgeType.DEFAULT);
 170             }
 171             anchor = copyLink(criticalPath, graph, anchor, link.getVertexFrom(), link.getVertexTo(),
 172                     link.getVertexTo().getTs(), link.getType());
 173             prev = link;
 174         }
 175     }
 176
 177     /**
 178      * Resolve a blocking by going through the graph vertically from the
 179      * blocking edge
 180      *
 181      * FIXME: build a tree with partial subpath in order to return the best
 182      * path, not the last one traversed
 183      *
 184      * @param blocking
 185      *            The blocking edge
 186      * @param bound
 187      *            The vertex that limits the boundary until which to resolve the
 188      *            blocking
 189      * @return The list of non-blocking edges
 190      */
 191     private List<TmfEdge> resolveBlockingBounded(TmfEdge blocking, TmfVertex bound) {
 192
 193         LinkedList<TmfEdge> subPath = new LinkedList<>();
 194         TmfVertex junction = findIncoming(blocking.getVertexTo(), EdgeDirection.OUTGOING_HORIZONTAL_EDGE);
 195         /* if wake-up source is not found, return empty list */
 196         if (junction == null) {
 197             return subPath;
 198         }
 199
 200         TmfEdge down = checkNotNull(junction.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE));
 201         subPath.add(down);
 202         TmfVertex vertexFrom = down.getVertexFrom();
 203
 204         TmfVertex currentBound = bound.compareTo(blocking.getVertexFrom()) < 0 ? blocking.getVertexFrom() : bound;
 205
 206         Stack<TmfVertex> stack = new Stack<>();
 207         while (vertexFrom != null && vertexFrom.compareTo(currentBound) > 0) {
 208             /* shortcut for down link that goes beyond the blocking */
 209             TmfEdge inVerticalEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
 210             if (inVerticalEdge != null && inVerticalEdge.getVertexFrom().compareTo(currentBound) <= 0) {
 211                 subPath.add(inVerticalEdge);
 212                 break;
 213             }
 214
 215             /**
 216              * Add DOWN links to explore stack in case dead-end occurs. Here is
 217              * an example to illustrate the procedure.
 218              *
 219              * <pre>
 220              *           -------------------------
 221              *            BLOCKED    | PREEMPT
 222              *           -------------------------
 223              *                       ^
 224              *                       |WAKE-UP
 225              *                       |
 226              *         +--------------------+
 227              * +-------+      INTERRUPT     +--------+
 228              *         +--------------------+
 229              *           ^   ^   |       ^
 230              *           |   |   |       |
 231              *           +   +   v       +
 232              *           1   2   3       4
 233              * </pre>
 234              *
 235              * The event wake-up is followed backward. The edge 4 will never be
 236              * visited (it cannot be the cause of the wake-up, because it occurs
 237              * after it). The edge 3 will not be explored, because it is
 238              * outgoing. The edges 2 and 1 will be pushed on the stack. When the
 239              * beginning of the interrupt is reached, then the edges on the
 240              * stack will be explored.
 241              *
 242              * If a dead-end is reached, while the stack is not empty, the
 243              * accumulated path is rewinded, and a different incoming edge is
 244              * tried. The backward traversal ends if there is nothing left to
 245              * explore, or if the start of the blocking window start is reached.
 246              *
 247              * Do not add if left is BLOCKED, because this link would be visited
 248              * twice
 249              */
 250             TmfEdge incomingEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE);
 251             if (inVerticalEdge != null &&
 252                     (incomingEdge == null ||
 253                             incomingEdge.getType() != TmfEdge.EdgeType.BLOCKED ||
 254                             incomingEdge.getType() != TmfEdge.EdgeType.NETWORK)) {
 255                 stack.push(vertexFrom);
 256             }
 257             if (incomingEdge != null) {
 258                 if (incomingEdge.getType() == TmfEdge.EdgeType.BLOCKED || incomingEdge.getType() == TmfEdge.EdgeType.NETWORK) {
 259                     subPath.addAll(resolveBlockingBounded(incomingEdge, currentBound));
 260                 } else {
 261                     subPath.add(incomingEdge);
 262                 }
 263                 vertexFrom = incomingEdge.getVertexFrom();
 264             } else {
 265                 if (!stack.isEmpty()) {
 266                     TmfVertex v = stack.pop();
 267                     /* rewind subpath */
 268                     while (!subPath.isEmpty() && subPath.getLast().getVertexFrom() != v) {
 269                         subPath.removeLast();
 270                     }
 271                     TmfEdge edge = v.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE);
 272                     if (edge != null) {
 273                         subPath.add(edge);
 274                         vertexFrom = edge.getVertexFrom();
 275                         continue;
 276                     }
 277                 }
 278                 vertexFrom = null;
 279             }
 280
 281         }
 282         return subPath;
 283     }
 284
 285 }