Commit | Line | Data |
---|---|---|
51480ca2 FG |
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 | ||
da4232b4 MK |
12 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; |
13 | ||
51480ca2 FG |
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; | |
da4232b4 | 25 | import org.eclipse.tracecompass.analysis.graph.core.criticalpath.CriticalPathAlgorithmException; |
51480ca2 FG |
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 | |
da4232b4 | 51 | public TmfGraph compute(TmfVertex start, @Nullable TmfVertex end) throws CriticalPathAlgorithmException { |
51480ca2 FG |
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 | */ | |
da4232b4 | 61 | IGraphWorker parent = checkNotNull(graph.getParentOf(start)); |
51480ca2 FG |
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()) { | |
5aa7fe19 | 81 | case IPI: |
51480ca2 FG |
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 | */ | |
da4232b4 | 96 | IGraphWorker parentTo = checkNotNull(graph.getParentOf(nextEdge.getVertexTo())); |
51480ca2 | 97 | if (parentTo != parent) { |
da4232b4 | 98 | throw new CriticalPathAlgorithmException("no, the parents of horizontal edges are not always identical... shouldn't they be?"); //$NON-NLS-1$ |
51480ca2 FG |
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) { | |
da4232b4 | 110 | throw new CriticalPathAlgorithmException("epsilon duration is not zero " + nextEdge); //$NON-NLS-1$ |
51480ca2 FG |
111 | } |
112 | break; | |
113 | case DEFAULT: | |
da4232b4 | 114 | throw new CriticalPathAlgorithmException("Illegal link type " + nextEdge.getType()); //$NON-NLS-1$ |
51480ca2 FG |
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) { | |
da4232b4 | 127 | IGraphWorker currentActor = checkNotNull(graph.getParentOf(currentVertex)); |
51480ca2 FG |
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 | ||
da4232b4 MK |
142 | // attach subpath to b1 |
143 | TmfVertex b1 = checkNotNull(criticalPath.getTail(currentActor)); | |
51480ca2 FG |
144 | |
145 | // glue head | |
146 | TmfEdge lnk = links.get(0); | |
147 | TmfVertex anchor = null; | |
da4232b4 MK |
148 | IGraphWorker objSrc = checkNotNull(graph.getParentOf(lnk.getVertexFrom())); |
149 | if (objSrc.equals( currentActor)) { | |
51480ca2 FG |
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()); | |
da4232b4 | 158 | TmfEdge edge = checkNotNull(criticalPath.append(objSrc, anchor)); |
51480ca2 FG |
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 | ||
da4232b4 | 200 | TmfEdge down = checkNotNull(junction.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE)); |
51480ca2 FG |
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 | } |