Commit | Line | Data |
---|---|---|
905218ff SF |
1 | /******************************************************************************* |
2 | * Copyright (c) 2016 Ericsson | |
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.timing.core.callgraph; | |
11 | ||
12 | import java.util.ArrayList; | |
13 | import java.util.Arrays; | |
14 | import java.util.Collections; | |
15 | import java.util.List; | |
16 | import java.util.stream.Collectors; | |
17 | ||
18 | import org.eclipse.core.runtime.IProgressMonitor; | |
19 | import org.eclipse.core.runtime.ListenerList; | |
20 | import org.eclipse.jdt.annotation.NonNull; | |
21 | import org.eclipse.jdt.annotation.Nullable; | |
22 | import org.eclipse.tracecompass.analysis.timing.core.segmentstore.IAnalysisProgressListener; | |
23 | import org.eclipse.tracecompass.analysis.timing.core.segmentstore.ISegmentStoreProvider; | |
24 | import org.eclipse.tracecompass.common.core.StreamUtils; | |
25 | import org.eclipse.tracecompass.internal.analysis.timing.core.Activator; | |
905218ff SF |
26 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
27 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
664a3a81 LPD |
28 | import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory; |
29 | import org.eclipse.tracecompass.segmentstore.core.SegmentStoreFactory.SegmentStoreType; | |
905218ff SF |
30 | import org.eclipse.tracecompass.statesystem.core.ITmfStateSystem; |
31 | import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; | |
32 | import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; | |
33 | import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; | |
34 | import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; | |
35 | import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; | |
b3282dcf | 36 | import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue.Type; |
905218ff SF |
37 | import org.eclipse.tracecompass.tmf.core.analysis.IAnalysisModule; |
38 | import org.eclipse.tracecompass.tmf.core.analysis.TmfAbstractAnalysisModule; | |
39 | import org.eclipse.tracecompass.tmf.core.callstack.CallStackAnalysis; | |
40 | import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; | |
41 | import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager; | |
42 | import org.eclipse.tracecompass.tmf.core.trace.TmfTraceUtils; | |
43 | ||
44 | import com.google.common.annotations.VisibleForTesting; | |
45 | import com.google.common.collect.ImmutableList; | |
46 | ||
47 | /** | |
48 | * Call stack analysis used to create a segment for each call function from an | |
49 | * entry/exit event. It builds a segment tree from the state system. An example | |
50 | * taken from the Fibonacci trace's callStack shows the structure of the segment | |
51 | * tree given by this analysis: | |
52 | * | |
53 | * <pre> | |
54 | * (Caller) main | |
55 | * ↓↑ | |
56 | * (Callee) Fibonacci | |
57 | * ↓↑ ↓↑ | |
58 | * Fibonacci Fibonacci | |
59 | * ↓↑ ↓↑ | |
60 | * ... ... | |
61 | * </pre> | |
62 | * | |
63 | * @author Sonia Farrah | |
64 | */ | |
65 | public abstract class CallGraphAnalysis extends TmfAbstractAnalysisModule implements ISegmentStoreProvider { | |
66 | ||
67 | // ------------------------------------------------------------------------ | |
68 | // Attributes | |
69 | // ------------------------------------------------------------------------ | |
70 | ||
71 | /** | |
72 | * Segment store | |
73 | */ | |
664a3a81 | 74 | private final ISegmentStore<@NonNull ISegment> fStore; |
905218ff SF |
75 | |
76 | /** | |
77 | * Listeners | |
78 | */ | |
79 | private final ListenerList fListeners = new ListenerList(ListenerList.IDENTITY); | |
80 | ||
81 | /** | |
82 | * The Trace's root functions list | |
83 | */ | |
2d8d933f | 84 | private final List<ICalledFunction> fRootFunctions = new ArrayList<>(); |
905218ff SF |
85 | |
86 | /** | |
87 | * The sub attributes of a certain thread | |
88 | */ | |
89 | private List<Integer> fCurrentQuarks = Collections.emptyList(); | |
74ccf789 SF |
90 | /** |
91 | * The List of thread nodes. Each thread has a virtual node having the root | |
92 | * function as children | |
93 | */ | |
b3282dcf | 94 | private List<ThreadNode> fThreadNodes = new ArrayList<>(); |
905218ff SF |
95 | |
96 | /** | |
97 | * Default constructor | |
98 | */ | |
99 | public CallGraphAnalysis() { | |
100 | super(); | |
664a3a81 | 101 | fStore = SegmentStoreFactory.createSegmentStore(SegmentStoreType.Fast); |
905218ff SF |
102 | } |
103 | ||
104 | @Override | |
105 | public @NonNull String getHelpText() { | |
106 | String msg = Messages.CallGraphAnalysis_Description; | |
107 | return (msg != null) ? msg : super.getHelpText(); | |
108 | } | |
109 | ||
110 | @Override | |
111 | public @NonNull String getHelpText(@NonNull ITmfTrace trace) { | |
112 | return getHelpText(); | |
113 | } | |
114 | ||
115 | @Override | |
116 | public boolean canExecute(ITmfTrace trace) { | |
117 | /* | |
118 | * FIXME: change to !Iterables.isEmpty(getDependentAnalyses()) when | |
119 | * analysis dependencies work better | |
120 | */ | |
121 | return true; | |
122 | } | |
123 | ||
124 | @Override | |
125 | protected Iterable<IAnalysisModule> getDependentAnalyses() { | |
126 | return TmfTraceManager.getTraceSet(getTrace()).stream() | |
127 | .flatMap(trace -> StreamUtils.getStream(TmfTraceUtils.getAnalysisModulesOfClass(trace, CallStackAnalysis.class))) | |
128 | .distinct().collect(Collectors.toList()); | |
129 | } | |
130 | ||
131 | @Override | |
132 | protected boolean executeAnalysis(@Nullable IProgressMonitor monitor) { | |
133 | ITmfTrace trace = getTrace(); | |
134 | if (monitor == null || trace == null) { | |
135 | return false; | |
136 | } | |
137 | Iterable<IAnalysisModule> dependentAnalyses = getDependentAnalyses(); | |
138 | for (IAnalysisModule module : dependentAnalyses) { | |
139 | if (!(module instanceof CallStackAnalysis)) { | |
140 | return false; | |
141 | } | |
142 | module.schedule(); | |
143 | } | |
144 | // TODO:Look at updates while the state system's being built | |
145 | dependentAnalyses.forEach((t) -> t.waitForCompletion(monitor)); | |
146 | for (IAnalysisModule module : dependentAnalyses) { | |
147 | CallStackAnalysis callstackModule = (CallStackAnalysis) module; | |
148 | String[] threadsPattern = callstackModule.getThreadsPattern(); | |
149 | String[] processesPattern = callstackModule.getProcessesPattern(); | |
150 | String[] callStackPath = callstackModule.getCallStackPath(); | |
151 | ITmfStateSystem ss = callstackModule.getStateSystem(); | |
152 | if (!iterateOverStateSystem(ss, threadsPattern, processesPattern, callStackPath, monitor)) { | |
153 | return false; | |
154 | } | |
155 | } | |
156 | monitor.worked(1); | |
157 | monitor.done(); | |
158 | return true; | |
159 | ||
160 | } | |
161 | ||
162 | /** | |
163 | * Iterate over the process of the state system,then iterate over the | |
164 | * different threads of each process. | |
165 | * | |
166 | * @param ss | |
167 | * The state system | |
168 | * @param threadsPattern | |
169 | * The threads pattern | |
170 | * @param processesPattern | |
171 | * The processes pattern | |
172 | * @param callStackPath | |
173 | * The call stack path | |
174 | * @param monitor | |
175 | * The monitor | |
176 | * @return Boolean | |
177 | */ | |
178 | @VisibleForTesting | |
179 | protected boolean iterateOverStateSystem(@Nullable ITmfStateSystem ss, String[] threadsPattern, String[] processesPattern, String[] callStackPath, IProgressMonitor monitor) { | |
180 | if (ss == null) { | |
181 | return false; | |
182 | } | |
183 | List<Integer> processQuarks = ss.getQuarks(processesPattern); | |
184 | for (int processQuark : processQuarks) { | |
c2845a63 | 185 | int processId = getProcessId(ss, processQuark, ss.getCurrentEndTime()); |
905218ff | 186 | for (int threadQuark : ss.getQuarks(processQuark, threadsPattern)) { |
c2845a63 | 187 | if (!iterateOverQuark(ss, processId, threadQuark, callStackPath, monitor)) { |
905218ff SF |
188 | return false; |
189 | } | |
190 | } | |
191 | } | |
192 | sendUpdate(fStore); | |
193 | return true; | |
194 | } | |
195 | ||
196 | /** | |
197 | * Iterate over functions with the same quark,search for their callees then | |
198 | * add them to the segment store | |
199 | * | |
200 | * @param stateSystem | |
201 | * The state system | |
c2845a63 BH |
202 | * @param processId |
203 | * The process ID of the traced application | |
204 | * @param threadQuark | |
205 | * The thread quark | |
905218ff SF |
206 | * @param subAttributePath |
207 | * sub-Attributes path | |
208 | * @param monitor | |
209 | * The monitor | |
210 | * @return Boolean | |
211 | */ | |
c2845a63 BH |
212 | private boolean iterateOverQuark(ITmfStateSystem stateSystem, int processId, int threadQuark, String[] subAttributePath, IProgressMonitor monitor) { |
213 | String threadName = stateSystem.getAttributeName(threadQuark); | |
b3282dcf SF |
214 | long threadId = -1; |
215 | ITmfStateInterval interval = null; | |
216 | try { | |
c2845a63 | 217 | interval = stateSystem.querySingleState(stateSystem.getStartTime(), threadQuark); |
b3282dcf SF |
218 | ITmfStateValue threadStateValue = interval.getStateValue(); |
219 | if (threadStateValue.getType() == Type.LONG || threadStateValue.getType() == Type.INTEGER) { | |
220 | threadId = threadStateValue.unboxLong(); | |
221 | } else { | |
222 | try { | |
223 | threadId = Long.parseLong(threadName); | |
224 | } catch (NumberFormatException e) { | |
225 | /* use default threadId */ | |
226 | } | |
227 | } | |
228 | } catch (StateSystemDisposedException error) { | |
229 | Activator.getInstance().logError(Messages.QueringStateSystemError, error); | |
230 | } | |
905218ff SF |
231 | try { |
232 | long curTime = stateSystem.getStartTime(); | |
233 | long limit = stateSystem.getCurrentEndTime(); | |
c2845a63 | 234 | AbstractCalledFunction initSegment = CalledFunctionFactory.create(0, 0, 0, threadName, processId, null); |
b3282dcf | 235 | ThreadNode init = new ThreadNode(initSegment, 0, threadId); |
905218ff SF |
236 | while (curTime < limit) { |
237 | if (monitor.isCanceled()) { | |
238 | return false; | |
239 | } | |
c2845a63 | 240 | int callStackQuark = stateSystem.getQuarkRelative(threadQuark, subAttributePath); |
905218ff SF |
241 | fCurrentQuarks = stateSystem.getSubAttributes(callStackQuark, false); |
242 | if (fCurrentQuarks.isEmpty()) { | |
243 | return false; | |
244 | } | |
245 | final int depth = 0; | |
246 | int quarkParent = fCurrentQuarks.get(depth); | |
b3282dcf | 247 | interval = stateSystem.querySingleState(curTime, quarkParent); |
905218ff SF |
248 | ITmfStateValue stateValue = interval.getStateValue(); |
249 | ||
250 | if (!stateValue.isNull()) { | |
251 | long intervalStart = interval.getStartTime(); | |
252 | long intervalEnd = interval.getEndTime(); | |
253 | // Create the segment for the first call event. | |
c2845a63 | 254 | AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, depth, stateValue, processId, null); |
905218ff | 255 | fRootFunctions.add(segment); |
fdf2d9bb | 256 | AggregatedCalledFunction firstNode = new AggregatedCalledFunction(segment, fCurrentQuarks.size()); |
c2845a63 | 257 | if (!findChildren(segment, depth, stateSystem, fCurrentQuarks.size() + fCurrentQuarks.get(depth), firstNode, processId, monitor)) { |
905218ff SF |
258 | return false; |
259 | } | |
74ccf789 | 260 | init.addChild(firstNode); |
905218ff SF |
261 | } |
262 | ||
263 | curTime = interval.getEndTime() + 1; | |
264 | } | |
b3282dcf | 265 | fThreadNodes.add(init); |
905218ff SF |
266 | } catch (AttributeNotFoundException | StateSystemDisposedException | TimeRangeException e) { |
267 | Activator.getInstance().logError(Messages.QueringStateSystemError, e); | |
268 | return false; | |
269 | } | |
270 | return true; | |
271 | } | |
272 | ||
273 | /** | |
274 | * Find the functions called by a parent function in a call stack then add | |
275 | * segments for each child, updating the self times of each node | |
276 | * accordingly. | |
277 | * | |
278 | * @param node | |
279 | * The segment of the stack call event(the parent) callStackQuark | |
280 | * @param depth | |
281 | * The depth of the parent function | |
282 | * @param ss | |
283 | * The quark of the segment parent ss The actual state system | |
284 | * @param maxQuark | |
285 | * The last quark in the state system | |
c2845a63 | 286 | * @param aggregatedCalledFunction |
74ccf789 | 287 | * A node in the aggregation tree |
c2845a63 BH |
288 | * @param processId |
289 | * The process ID of the traced application | |
905218ff SF |
290 | * @param monitor |
291 | * The progress monitor The progress monitor TODO: if stack size | |
292 | * is an issue, convert to a stack instead of recursive function | |
293 | */ | |
c2845a63 | 294 | private boolean findChildren(AbstractCalledFunction node, int depth, ITmfStateSystem ss, int maxQuark, AggregatedCalledFunction aggregatedCalledFunction, int processId, IProgressMonitor monitor) { |
905218ff SF |
295 | fStore.add(node); |
296 | long curTime = node.getStart(); | |
297 | long limit = node.getEnd(); | |
298 | ITmfStateInterval interval = null; | |
299 | while (curTime < limit) { | |
300 | if (monitor.isCanceled()) { | |
301 | return false; | |
302 | } | |
303 | try { | |
304 | if (depth + 1 < fCurrentQuarks.size()) { | |
305 | interval = ss.querySingleState(curTime, fCurrentQuarks.get(depth + 1)); | |
306 | } else { | |
307 | return true; | |
308 | } | |
309 | } catch (StateSystemDisposedException e) { | |
310 | Activator.getInstance().logError(Messages.QueringStateSystemError, e); | |
311 | return false; | |
312 | } | |
313 | ITmfStateValue stateValue = interval.getStateValue(); | |
314 | if (!stateValue.isNull()) { | |
315 | long intervalStart = interval.getStartTime(); | |
316 | long intervalEnd = interval.getEndTime(); | |
317 | if (intervalStart < node.getStart() || intervalEnd > limit) { | |
318 | return true; | |
319 | } | |
c2845a63 | 320 | AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, node.getDepth() + 1, stateValue, processId, node); |
fdf2d9bb | 321 | AggregatedCalledFunction childNode = new AggregatedCalledFunction(segment, aggregatedCalledFunction); |
905218ff | 322 | // Search for the children with the next quark. |
c2845a63 | 323 | findChildren(segment, depth + 1, ss, maxQuark, childNode, processId, monitor); |
74ccf789 | 324 | aggregatedCalledFunction.addChild(childNode); |
905218ff SF |
325 | node.addChild(segment); |
326 | } | |
327 | curTime = interval.getEndTime() + 1; | |
328 | } | |
329 | return true; | |
330 | } | |
331 | ||
332 | @Override | |
333 | public void addListener(@NonNull IAnalysisProgressListener listener) { | |
334 | fListeners.add(listener); | |
335 | } | |
336 | ||
337 | @Override | |
338 | public void removeListener(@NonNull IAnalysisProgressListener listener) { | |
339 | fListeners.remove(listener); | |
340 | } | |
341 | ||
342 | @Override | |
343 | protected void canceling() { | |
344 | // Do nothing | |
345 | } | |
346 | ||
347 | @Override | |
348 | public @Nullable ISegmentStore<@NonNull ISegment> getSegmentStore() { | |
349 | return fStore; | |
350 | } | |
351 | ||
352 | /** | |
353 | * Update listeners | |
354 | * | |
355 | * @param store | |
356 | * The segment store | |
357 | */ | |
358 | protected void sendUpdate(final ISegmentStore<@NonNull ISegment> store) { | |
359 | getListeners().forEach(listener -> listener.onComplete(this, store)); | |
360 | } | |
361 | ||
362 | /** | |
363 | * Get Listeners | |
364 | * | |
365 | * @return The listeners | |
366 | */ | |
367 | protected Iterable<IAnalysisProgressListener> getListeners() { | |
368 | return Arrays.stream(fListeners.getListeners()) | |
369 | .filter(listener -> listener instanceof IAnalysisProgressListener) | |
370 | .map(listener -> (IAnalysisProgressListener) listener) | |
371 | .collect(Collectors.toList()); | |
372 | } | |
373 | ||
374 | /** | |
375 | * The functions of the first level | |
376 | * | |
377 | * @return Functions of the first level | |
378 | */ | |
2d8d933f | 379 | public List<ICalledFunction> getRootFunctions() { |
905218ff SF |
380 | return ImmutableList.copyOf(fRootFunctions); |
381 | } | |
382 | ||
74ccf789 SF |
383 | /** |
384 | * List of thread nodes. Each thread has a virtual node having the root | |
385 | * functions called as children. | |
386 | * | |
387 | * @return The thread nodes | |
388 | */ | |
b3282dcf | 389 | public List<ThreadNode> getThreadNodes() { |
74ccf789 SF |
390 | return ImmutableList.copyOf(fThreadNodes); |
391 | } | |
392 | ||
c2845a63 BH |
393 | private static int getProcessId(ITmfStateSystem ss, int processQuark, long curTime) { |
394 | int processId = -1; | |
395 | if (processQuark != ITmfStateSystem.ROOT_ATTRIBUTE) { | |
396 | try { | |
397 | ITmfStateInterval interval = ss.querySingleState(curTime, processQuark); | |
398 | String processName = ss.getAttributeName(processQuark); | |
399 | ITmfStateValue processStateValue = interval.getStateValue(); | |
400 | if (processStateValue.getType() == Type.INTEGER) { | |
401 | processId = processStateValue.unboxInt(); | |
402 | } else { | |
403 | try { | |
404 | processId = Integer.parseInt(processName); | |
405 | } catch (NumberFormatException e) { | |
406 | /* use default processId */ | |
407 | } | |
408 | } | |
409 | } catch (StateSystemDisposedException e) { | |
410 | // ignore | |
411 | } | |
412 | } | |
413 | return processId; | |
414 | } | |
905218ff | 415 | } |