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