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()) { | |
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 | */ | |
da4232b4 | 95 | IGraphWorker parentTo = checkNotNull(graph.getParentOf(nextEdge.getVertexTo())); |
51480ca2 | 96 | if (parentTo != parent) { |
da4232b4 | 97 | throw new CriticalPathAlgorithmException("no, the parents of horizontal edges are not always identical... shouldn't they be?"); //$NON-NLS-1$ |
51480ca2 FG |
98 | } |
99 | criticalPath.append(parentTo, new TmfVertex(nextEdge.getVertexTo()), nextEdge.getType()); | |
100 | break; | |
101 | case NETWORK: | |
102 | case BLOCKED: | |
103 | List<TmfEdge> links = resolveBlockingBounded(nextEdge, nextEdge.getVertexFrom()); | |
104 | Collections.reverse(links); | |
105 | appendPathComponent(criticalPath, graph, currentVertex, links); | |
106 | break; | |
107 | case EPS: | |
108 | if (nextEdge.getDuration() != 0) { | |
da4232b4 | 109 | throw new CriticalPathAlgorithmException("epsilon duration is not zero " + nextEdge); //$NON-NLS-1$ |
51480ca2 FG |
110 | } |
111 | break; | |
112 | case DEFAULT: | |
da4232b4 | 113 | throw new CriticalPathAlgorithmException("Illegal link type " + nextEdge.getType()); //$NON-NLS-1$ |
51480ca2 FG |
114 | case UNKNOWN: |
115 | default: | |
116 | break; | |
117 | } | |
118 | currentVertex = nextVertex; | |
119 | nextEdge = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
120 | } | |
121 | return criticalPath; | |
122 | } | |
123 | ||
124 | /** Add the links to the critical path, with currentVertex to glue to */ | |
125 | private void appendPathComponent(TmfGraph criticalPath, TmfGraph graph, TmfVertex currentVertex, List<TmfEdge> links) { | |
da4232b4 | 126 | IGraphWorker currentActor = checkNotNull(graph.getParentOf(currentVertex)); |
51480ca2 FG |
127 | if (links.isEmpty()) { |
128 | /* | |
129 | * The next vertex should not be null, since we glue only after | |
130 | * resolve of the blocking of the edge to that vertex | |
131 | */ | |
132 | TmfEdge next = currentVertex.getEdge(EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
133 | if (next == null) { | |
134 | return; | |
135 | } | |
136 | criticalPath.append(currentActor, new TmfVertex(next.getVertexTo()), next.getType()); | |
137 | return; | |
138 | } | |
139 | // FIXME: assert last link.to actor == currentActor | |
140 | ||
da4232b4 MK |
141 | // attach subpath to b1 |
142 | TmfVertex b1 = checkNotNull(criticalPath.getTail(currentActor)); | |
51480ca2 FG |
143 | |
144 | // glue head | |
145 | TmfEdge lnk = links.get(0); | |
146 | TmfVertex anchor = null; | |
da4232b4 MK |
147 | IGraphWorker objSrc = checkNotNull(graph.getParentOf(lnk.getVertexFrom())); |
148 | if (objSrc.equals( currentActor)) { | |
51480ca2 FG |
149 | anchor = b1; |
150 | } else { | |
151 | anchor = new TmfVertex(currentVertex); | |
152 | criticalPath.add(objSrc, anchor); | |
153 | b1.linkVertical(anchor); | |
154 | /* fill any gap with UNKNOWN */ | |
155 | if (lnk.getVertexFrom().compareTo(anchor) > 0) { | |
156 | anchor = new TmfVertex(lnk.getVertexFrom()); | |
da4232b4 | 157 | TmfEdge edge = checkNotNull(criticalPath.append(objSrc, anchor)); |
51480ca2 FG |
158 | edge.setType(TmfEdge.EdgeType.UNKNOWN); |
159 | } | |
160 | } | |
161 | ||
162 | // glue body | |
163 | TmfEdge prev = null; | |
164 | for (TmfEdge link : links) { | |
165 | // check connectivity | |
166 | if (prev != null && prev.getVertexTo() != link.getVertexFrom()) { | |
167 | anchor = copyLink(criticalPath, graph, anchor, prev.getVertexTo(), link.getVertexFrom(), | |
168 | prev.getVertexTo().getTs(), TmfEdge.EdgeType.DEFAULT); | |
169 | } | |
170 | anchor = copyLink(criticalPath, graph, anchor, link.getVertexFrom(), link.getVertexTo(), | |
171 | link.getVertexTo().getTs(), link.getType()); | |
172 | prev = link; | |
173 | } | |
174 | } | |
175 | ||
176 | /** | |
177 | * Resolve a blocking by going through the graph vertically from the | |
178 | * blocking edge | |
179 | * | |
180 | * FIXME: build a tree with partial subpath in order to return the best | |
181 | * path, not the last one traversed | |
182 | * | |
183 | * @param blocking | |
184 | * The blocking edge | |
185 | * @param bound | |
186 | * The vertex that limits the boundary until which to resolve the | |
187 | * blocking | |
188 | * @return The list of non-blocking edges | |
189 | */ | |
190 | private List<TmfEdge> resolveBlockingBounded(TmfEdge blocking, TmfVertex bound) { | |
191 | ||
192 | LinkedList<TmfEdge> subPath = new LinkedList<>(); | |
193 | TmfVertex junction = findIncoming(blocking.getVertexTo(), EdgeDirection.OUTGOING_HORIZONTAL_EDGE); | |
194 | /* if wake-up source is not found, return empty list */ | |
195 | if (junction == null) { | |
196 | return subPath; | |
197 | } | |
198 | ||
da4232b4 | 199 | TmfEdge down = checkNotNull(junction.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE)); |
51480ca2 FG |
200 | subPath.add(down); |
201 | TmfVertex vertexFrom = down.getVertexFrom(); | |
202 | ||
203 | TmfVertex currentBound = bound.compareTo(blocking.getVertexFrom()) < 0 ? blocking.getVertexFrom() : bound; | |
204 | ||
205 | Stack<TmfVertex> stack = new Stack<>(); | |
206 | while (vertexFrom != null && vertexFrom.compareTo(currentBound) > 0) { | |
207 | /* shortcut for down link that goes beyond the blocking */ | |
208 | TmfEdge inVerticalEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE); | |
209 | if (inVerticalEdge != null && inVerticalEdge.getVertexFrom().compareTo(currentBound) <= 0) { | |
210 | subPath.add(inVerticalEdge); | |
211 | break; | |
212 | } | |
213 | ||
214 | /** | |
215 | * Add DOWN links to explore stack in case dead-end occurs. Here is | |
216 | * an example to illustrate the procedure. | |
217 | * | |
218 | * <pre> | |
219 | * ------------------------- | |
220 | * BLOCKED | PREEMPT | |
221 | * ------------------------- | |
222 | * ^ | |
223 | * |WAKE-UP | |
224 | * | | |
225 | * +--------------------+ | |
226 | * +-------+ INTERRUPT +--------+ | |
227 | * +--------------------+ | |
228 | * ^ ^ | ^ | |
229 | * | | | | | |
230 | * + + v + | |
231 | * 1 2 3 4 | |
232 | * </pre> | |
233 | * | |
234 | * The event wake-up is followed backward. The edge 4 will never be | |
235 | * visited (it cannot be the cause of the wake-up, because it occurs | |
236 | * after it). The edge 3 will not be explored, because it is | |
237 | * outgoing. The edges 2 and 1 will be pushed on the stack. When the | |
238 | * beginning of the interrupt is reached, then the edges on the | |
239 | * stack will be explored. | |
240 | * | |
241 | * If a dead-end is reached, while the stack is not empty, the | |
242 | * accumulated path is rewinded, and a different incoming edge is | |
243 | * tried. The backward traversal ends if there is nothing left to | |
244 | * explore, or if the start of the blocking window start is reached. | |
245 | * | |
246 | * Do not add if left is BLOCKED, because this link would be visited | |
247 | * twice | |
248 | */ | |
249 | TmfEdge incomingEdge = vertexFrom.getEdge(EdgeDirection.INCOMING_HORIZONTAL_EDGE); | |
250 | if (inVerticalEdge != null && | |
251 | (incomingEdge == null || | |
252 | incomingEdge.getType() != TmfEdge.EdgeType.BLOCKED || | |
253 | incomingEdge.getType() != TmfEdge.EdgeType.NETWORK)) { | |
254 | stack.push(vertexFrom); | |
255 | } | |
256 | if (incomingEdge != null) { | |
257 | if (incomingEdge.getType() == TmfEdge.EdgeType.BLOCKED || incomingEdge.getType() == TmfEdge.EdgeType.NETWORK) { | |
258 | subPath.addAll(resolveBlockingBounded(incomingEdge, currentBound)); | |
259 | } else { | |
260 | subPath.add(incomingEdge); | |
261 | } | |
262 | vertexFrom = incomingEdge.getVertexFrom(); | |
263 | } else { | |
264 | if (!stack.isEmpty()) { | |
265 | TmfVertex v = stack.pop(); | |
266 | /* rewind subpath */ | |
267 | while (!subPath.isEmpty() && subPath.getLast().getVertexFrom() != v) { | |
268 | subPath.removeLast(); | |
269 | } | |
270 | TmfEdge edge = v.getEdge(EdgeDirection.INCOMING_VERTICAL_EDGE); | |
271 | if (edge != null) { | |
272 | subPath.add(edge); | |
273 | vertexFrom = edge.getVertexFrom(); | |
274 | continue; | |
275 | } | |
276 | } | |
277 | vertexFrom = null; | |
278 | } | |
279 | ||
280 | } | |
281 | return subPath; | |
282 | } | |
283 | ||
284 | } |