1 /*******************************************************************************
2 * Copyright (c) 2016 Ericsson
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 *******************************************************************************/
10 package org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
;
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
;
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
;
26 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.store
.ArrayListStore
;
27 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
28 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegmentStore
;
29 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystem
;
30 import org
.eclipse
.tracecompass
.statesystem
.core
.exceptions
.AttributeNotFoundException
;
31 import org
.eclipse
.tracecompass
.statesystem
.core
.exceptions
.StateSystemDisposedException
;
32 import org
.eclipse
.tracecompass
.statesystem
.core
.exceptions
.TimeRangeException
;
33 import org
.eclipse
.tracecompass
.statesystem
.core
.interval
.ITmfStateInterval
;
34 import org
.eclipse
.tracecompass
.statesystem
.core
.statevalue
.ITmfStateValue
;
35 import org
.eclipse
.tracecompass
.tmf
.core
.analysis
.IAnalysisModule
;
36 import org
.eclipse
.tracecompass
.tmf
.core
.analysis
.TmfAbstractAnalysisModule
;
37 import org
.eclipse
.tracecompass
.tmf
.core
.callstack
.CallStackAnalysis
;
38 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.ITmfTrace
;
39 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.TmfTraceManager
;
40 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.TmfTraceUtils
;
42 import com
.google
.common
.annotations
.VisibleForTesting
;
43 import com
.google
.common
.collect
.ImmutableList
;
46 * Call stack analysis used to create a segment for each call function from an
47 * entry/exit event. It builds a segment tree from the state system. An example
48 * taken from the Fibonacci trace's callStack shows the structure of the segment
49 * tree given by this analysis:
61 * @author Sonia Farrah
63 public abstract class CallGraphAnalysis
extends TmfAbstractAnalysisModule
implements ISegmentStoreProvider
{
65 // ------------------------------------------------------------------------
67 // ------------------------------------------------------------------------
72 private final ISegmentStore
<@NonNull ISegment
> fStore
= new ArrayListStore
<>();
77 private final ListenerList fListeners
= new ListenerList(ListenerList
.IDENTITY
);
80 * The Trace's root functions list
82 private final List
<CalledFunction
> fRootFunctions
= new ArrayList
<>();
85 * The sub attributes of a certain thread
87 private List
<Integer
> fCurrentQuarks
= Collections
.emptyList();
92 public CallGraphAnalysis() {
97 public @NonNull String
getHelpText() {
98 String msg
= Messages
.CallGraphAnalysis_Description
;
99 return (msg
!= null) ? msg
: super.getHelpText();
103 public @NonNull String
getHelpText(@NonNull ITmfTrace trace
) {
104 return getHelpText();
108 public boolean canExecute(ITmfTrace trace
) {
110 * FIXME: change to !Iterables.isEmpty(getDependentAnalyses()) when
111 * analysis dependencies work better
117 protected Iterable
<IAnalysisModule
> getDependentAnalyses() {
118 return TmfTraceManager
.getTraceSet(getTrace()).stream()
119 .flatMap(trace
-> StreamUtils
.getStream(TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CallStackAnalysis
.class)))
120 .distinct().collect(Collectors
.toList());
124 protected boolean executeAnalysis(@Nullable IProgressMonitor monitor
) {
125 ITmfTrace trace
= getTrace();
126 if (monitor
== null || trace
== null) {
129 Iterable
<IAnalysisModule
> dependentAnalyses
= getDependentAnalyses();
130 for (IAnalysisModule module
: dependentAnalyses
) {
131 if (!(module
instanceof CallStackAnalysis
)) {
136 // TODO:Look at updates while the state system's being built
137 dependentAnalyses
.forEach((t
) -> t
.waitForCompletion(monitor
));
138 for (IAnalysisModule module
: dependentAnalyses
) {
139 CallStackAnalysis callstackModule
= (CallStackAnalysis
) module
;
140 String
[] threadsPattern
= callstackModule
.getThreadsPattern();
141 String
[] processesPattern
= callstackModule
.getProcessesPattern();
142 String
[] callStackPath
= callstackModule
.getCallStackPath();
143 ITmfStateSystem ss
= callstackModule
.getStateSystem();
144 if (!iterateOverStateSystem(ss
, threadsPattern
, processesPattern
, callStackPath
, monitor
)) {
155 * Iterate over the process of the state system,then iterate over the
156 * different threads of each process.
160 * @param threadsPattern
161 * The threads pattern
162 * @param processesPattern
163 * The processes pattern
164 * @param callStackPath
165 * The call stack path
171 protected boolean iterateOverStateSystem(@Nullable ITmfStateSystem ss
, String
[] threadsPattern
, String
[] processesPattern
, String
[] callStackPath
, IProgressMonitor monitor
) {
175 List
<Integer
> processQuarks
= ss
.getQuarks(processesPattern
);
176 for (int processQuark
: processQuarks
) {
177 for (int threadQuark
: ss
.getQuarks(processQuark
, threadsPattern
)) {
178 if (!iterateOverQuark(ss
, threadQuark
, callStackPath
, monitor
)) {
188 * Iterate over functions with the same quark,search for their callees then
189 * add them to the segment store
195 * @param subAttributePath
196 * sub-Attributes path
201 private boolean iterateOverQuark(ITmfStateSystem stateSystem
, int quark
, String
[] subAttributePath
, IProgressMonitor monitor
) {
203 long curTime
= stateSystem
.getStartTime();
204 long limit
= stateSystem
.getCurrentEndTime();
205 while (curTime
< limit
) {
206 if (monitor
.isCanceled()) {
209 int callStackQuark
= stateSystem
.getQuarkRelative(quark
, subAttributePath
);
210 fCurrentQuarks
= stateSystem
.getSubAttributes(callStackQuark
, false);
211 if (fCurrentQuarks
.isEmpty()) {
215 int quarkParent
= fCurrentQuarks
.get(depth
);
216 ITmfStateInterval interval
= stateSystem
.querySingleState(curTime
, quarkParent
);
217 ITmfStateValue stateValue
= interval
.getStateValue();
219 if (!stateValue
.isNull()) {
220 long intervalStart
= interval
.getStartTime();
221 long intervalEnd
= interval
.getEndTime();
222 // Create the segment for the first call event.
223 CalledFunction segment
= new CalledFunction(intervalStart
, intervalEnd
+ 1, stateValue
.unboxLong(), depth
);
224 fRootFunctions
.add(segment
);
225 if (!findChildren(segment
, depth
, stateSystem
, fCurrentQuarks
.size() + fCurrentQuarks
.get(depth
), monitor
)) {
231 curTime
= interval
.getEndTime() + 1;
234 } catch (AttributeNotFoundException
| StateSystemDisposedException
| TimeRangeException e
) {
235 Activator
.getInstance().logError(Messages
.QueringStateSystemError
, e
);
242 * Find the functions called by a parent function in a call stack then add
243 * segments for each child, updating the self times of each node
247 * The segment of the stack call event(the parent) callStackQuark
249 * The depth of the parent function
251 * The quark of the segment parent ss The actual state system
253 * The last quark in the state system
255 * The progress monitor The progress monitor TODO: if stack size
256 * is an issue, convert to a stack instead of recursive function
258 private boolean findChildren(CalledFunction node
, int depth
, ITmfStateSystem ss
, int maxQuark
, IProgressMonitor monitor
) {
260 long curTime
= node
.getStart();
261 long limit
= node
.getEnd();
262 ITmfStateInterval interval
= null;
263 while (curTime
< limit
) {
264 if (monitor
.isCanceled()) {
268 if (depth
+ 1 < fCurrentQuarks
.size()) {
269 interval
= ss
.querySingleState(curTime
, fCurrentQuarks
.get(depth
+ 1));
273 } catch (StateSystemDisposedException e
) {
274 Activator
.getInstance().logError(Messages
.QueringStateSystemError
, e
);
277 ITmfStateValue stateValue
= interval
.getStateValue();
278 if (!stateValue
.isNull()) {
279 long intervalStart
= interval
.getStartTime();
280 long intervalEnd
= interval
.getEndTime();
281 if (intervalStart
< node
.getStart() || intervalEnd
> limit
) {
284 CalledFunction segment
= new CalledFunction(intervalStart
, intervalEnd
+ 1, stateValue
.unboxLong(), node
.getDepth() + 1);
285 // Search for the children with the next quark.
286 findChildren(segment
, depth
+ 1, ss
, maxQuark
, monitor
);
287 node
.addChild(segment
);
289 curTime
= interval
.getEndTime() + 1;
295 public void addListener(@NonNull IAnalysisProgressListener listener
) {
296 fListeners
.add(listener
);
300 public void removeListener(@NonNull IAnalysisProgressListener listener
) {
301 fListeners
.remove(listener
);
305 protected void canceling() {
310 public @Nullable ISegmentStore
<@NonNull ISegment
> getSegmentStore() {
320 protected void sendUpdate(final ISegmentStore
<@NonNull ISegment
> store
) {
321 getListeners().forEach(listener
-> listener
.onComplete(this, store
));
327 * @return The listeners
329 protected Iterable
<IAnalysisProgressListener
> getListeners() {
330 return Arrays
.stream(fListeners
.getListeners())
331 .filter(listener
-> listener
instanceof IAnalysisProgressListener
)
332 .map(listener
-> (IAnalysisProgressListener
) listener
)
333 .collect(Collectors
.toList());
337 * The functions of the first level
339 * @return Functions of the first level
341 public List
<CalledFunction
> getThreads() {
342 return ImmutableList
.copyOf(fRootFunctions
);