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
.analysis
.timing
.core
.tests
.callgraph
;
12 import static org
.junit
.Assert
.*;
14 import java
.util
.Collections
;
15 import java
.util
.List
;
17 import org
.eclipse
.core
.runtime
.IProgressMonitor
;
18 import org
.eclipse
.core
.runtime
.NullProgressMonitor
;
19 import org
.eclipse
.jdt
.annotation
.NonNull
;
20 import org
.eclipse
.jdt
.annotation
.Nullable
;
21 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
22 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.CallGraphAnalysis
;
23 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.CalledFunction
;
24 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
25 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegmentStore
;
26 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystem
;
27 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystemBuilder
;
28 import org
.eclipse
.tracecompass
.statesystem
.core
.StateSystemFactory
;
29 import org
.eclipse
.tracecompass
.statesystem
.core
.backend
.IStateHistoryBackend
;
30 import org
.eclipse
.tracecompass
.statesystem
.core
.backend
.StateHistoryBackendFactory
;
31 import org
.eclipse
.tracecompass
.statesystem
.core
.statevalue
.TmfStateValue
;
32 import org
.eclipse
.tracecompass
.tmf
.core
.segment
.ISegmentAspect
;
33 import org
.junit
.Test
;
36 * Test the CallGraphAnalysis.This creates a virtual state system in each test
37 * and tests the segment store returned by the CallGraphAnalysis.
39 * @author Sonia Farrah
42 public class CallGraphAnalysisTest
{
44 private static final @NonNull String PROCESS_PATH
= "Processes";
45 private static final @NonNull String THREAD_PATH
= "Thread";
46 private static final @NonNull String CALLSTACK_PATH
= "CallStack";
47 private static final String QUARK_0
= "0";
48 private static final String QUARK_1
= "1";
49 private static final String QUARK_2
= "2";
50 private static final Integer SMALL_AMOUNT_OF_SEGMENT
= 3;
51 private static final int LARGE_AMOUNT_OF_SEGMENTS
= 1000;
52 private static final String
@NonNull [] CSP
= { CALLSTACK_PATH
};
53 private static final String
@NonNull [] PP
= { PROCESS_PATH
};
54 private static final String
@NonNull [] TP
= { THREAD_PATH
};
57 * This class is used to make the CallGraphAnalysis's method
58 * iterateOverStateSystem() visible to test
60 private class CGAnalysis
extends CallGraphAnalysis
{
63 protected boolean iterateOverStateSystem(@Nullable ITmfStateSystem ss
, String
[] threadsPattern
, String
[] processesPattern
, String
[] callStackPath
, IProgressMonitor monitor
) {
64 return super.iterateOverStateSystem(ss
, threadsPattern
, processesPattern
, callStackPath
, monitor
);
68 public @NonNull Iterable
<@NonNull ISegmentAspect
> getSegmentAspects() {
69 return Collections
.EMPTY_LIST
;
74 private static ITmfStateSystemBuilder
createFixture() {
75 IStateHistoryBackend backend
;
76 backend
= StateHistoryBackendFactory
.createInMemoryBackend("Test", 0L);
77 ITmfStateSystemBuilder fixture
= StateSystemFactory
.newStateSystem(backend
);
82 * Test cascade state system. The call stack's structure used in this test
93 public void CascadeTest() {
94 ITmfStateSystemBuilder fixture
= createFixture();
95 // Build the state system
98 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
99 for (int i
= 1; i
<= SMALL_AMOUNT_OF_SEGMENT
; i
++) {
100 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
101 TmfStateValue statev
= TmfStateValue
.newValueLong(i
);
102 fixture
.modifyAttribute(start
, TmfStateValue
.nullValue(), quark
);
103 fixture
.modifyAttribute(start
+ i
, statev
, quark
);
104 fixture
.modifyAttribute(end
- i
, TmfStateValue
.nullValue(), quark
);
107 fixture
.closeHistory(1002);
108 // Execute the CallGraphAnalysis
109 CGAnalysis cga
= new CGAnalysis();
110 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
111 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
112 // Test the segment store generated by the analysis
113 assertNotNull(segmentStore
);
114 Object
[] segments
= segmentStore
.toArray();
115 assertEquals("Number of segments Found", 3, segments
.length
);
116 CalledFunction f1
= (CalledFunction
) segments
[0];
117 CalledFunction f2
= (CalledFunction
) segments
[1];
118 CalledFunction f3
= (CalledFunction
) segments
[2];
119 assertEquals("Test the parenthood", NonNullUtils
.checkNotNull(f2
.getParent()).getAddr(), f1
.getAddr());
120 assertEquals("Children number:First parent", 1, f1
.getChildren().size());
121 assertEquals("Children number:Second parent", 1, f2
.getChildren().size());
122 assertTrue("Children number:Second parent", f3
.getChildren().isEmpty());
123 assertTrue("Children number:Child(leaf)", ((CalledFunction
) segments
[2]).getChildren().isEmpty());
124 assertEquals("Parent's self time", 2, f1
.getSelfTime());
125 assertEquals("Child's self time", 2, f2
.getSelfTime());
126 assertEquals("The leaf's self time", 994, f3
.getSelfTime());
127 assertEquals("Test first function's duration", 998, f1
.getLength());
128 assertEquals("Test second function's duration", 996, f2
.getLength());
129 assertEquals("Test third function's duration", 994, f3
.getLength());
130 assertEquals("Depth:First parent", 0, f1
.getDepth());
131 assertEquals("Depth:Second parent", 1, f2
.getDepth());
132 assertEquals("Depth:Last child", 2, f3
.getDepth());
136 * Build a pyramid shaped call stack.This call stack contains three
137 * functions ,Its structure is shown below :
145 private static void buildPyramidCallStack(ITmfStateSystemBuilder fixture
) {
146 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
147 // Create the first function
148 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
149 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
150 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
151 fixture
.modifyAttribute(10, statev
, quark
);
152 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
153 // Create the second function
154 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
155 statev
= TmfStateValue
.newValueLong(1);
156 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
157 fixture
.modifyAttribute(5, statev
, quark
);
158 fixture
.modifyAttribute(25, TmfStateValue
.nullValue(), quark
);
159 // Create the third function
160 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_2
);
161 statev
= TmfStateValue
.newValueLong(2);
162 fixture
.modifyAttribute(0, statev
, quark
);
163 fixture
.modifyAttribute(30, TmfStateValue
.nullValue(), quark
);
165 fixture
.closeHistory(31);
169 * Test pyramid state system. The call stack's structure used in this test
179 public void PyramidTest() {
180 ITmfStateSystemBuilder fixture
= createFixture();
181 buildPyramidCallStack(fixture
);
182 // Execute the callGraphAnalysis
183 CGAnalysis cga
= new CGAnalysis();
184 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
185 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
186 assertNotNull(segmentStore
);
187 Object
[] segments
= segmentStore
.toArray();
188 CalledFunction f1
= (CalledFunction
) segments
[0];
189 assertEquals("Number of segments Found", 1, segments
.length
);
190 assertEquals("Callees number", 0, f1
.getChildren().size());
191 assertEquals("Function's self time", 10, f1
.getSelfTime());
192 assertEquals("Compare the function's self time and total time", f1
.getLength(), f1
.getSelfTime());
193 assertEquals("Function's depth", 0, f1
.getDepth());
197 * Test mutliRoots state system. The call stack's structure used in this
198 * test is shown below:
206 public void multiFunctionRootsTest() {
207 ITmfStateSystemBuilder fixture
= createFixture();
208 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
209 // Create the first root function
210 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
211 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
212 fixture
.modifyAttribute(0, statev
, quark
);
213 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
214 // Create the second root function
215 statev
= TmfStateValue
.newValueLong(1);
216 fixture
.modifyAttribute(30, statev
, quark
);
217 fixture
.modifyAttribute(50, TmfStateValue
.nullValue(), quark
);
218 // Create the first root function's callee
219 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
220 statev
= TmfStateValue
.newValueLong(2);
221 fixture
.modifyAttribute(0, statev
, quark
);
222 fixture
.modifyAttribute(10, TmfStateValue
.nullValue(), quark
);
223 // Create the second root function's callee
224 statev
= TmfStateValue
.newValueLong(3);
225 fixture
.modifyAttribute(30, statev
, quark
);
226 fixture
.modifyAttribute(40, TmfStateValue
.nullValue(), quark
);
227 fixture
.closeHistory(51);
229 // Execute the callGraphAnalysis
230 CGAnalysis cga
= new CGAnalysis();
231 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
232 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
233 // Test the segment store
234 assertNotNull(segmentStore
);
235 Object
[] segments
= segmentStore
.toArray();
236 List
<@NonNull CalledFunction
> threads
= cga
.getThreads();
237 assertEquals("Number of root functions", 2, threads
.size());
238 assertEquals("Number of children: first root function", 1, threads
.get(0).getChildren().size());
239 assertEquals("Number of children: first root function", 1, threads
.get(1).getChildren().size());
240 CalledFunction firstChild
= threads
.get(0).getChildren().get(0);
241 CalledFunction secondChild
= threads
.get(1).getChildren().get(0);
242 assertEquals("Number of segments found", 4, segments
.length
);
243 assertNotNull(firstChild
.getParent());
244 assertNotNull(secondChild
.getParent());
246 assertEquals("Test of parenthood", NonNullUtils
.checkNotNull(firstChild
.getParent()).getAddr(), threads
.get(0).getAddr());
247 assertEquals("Test of parenthood", NonNullUtils
.checkNotNull(secondChild
.getParent()).getAddr(), threads
.get(1).getAddr());
252 * Test state system with a Large amount of segments. All segments have the
253 * same length. The call stack's structure used in this test is shown below:
263 public void LargeTest() {
264 // Build the state system
265 ITmfStateSystemBuilder fixture
= createFixture();
266 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
267 for (int i
= 0; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
268 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
269 TmfStateValue statev
= TmfStateValue
.newValueLong(i
);
270 fixture
.pushAttribute(0, statev
, quark
);
272 for (int i
= 0; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
273 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
274 fixture
.popAttribute(10, quark
);
276 fixture
.closeHistory(11);
277 // Execute the callGraphAnalysis
278 CGAnalysis cga
= new CGAnalysis();
279 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
280 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
281 // Test segment store
282 assertNotNull(segmentStore
);
283 Object
[] segments
= segmentStore
.toArray();
284 assertEquals("Number of segments found", LARGE_AMOUNT_OF_SEGMENTS
, segments
.length
);
285 for (int i
= 1; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
286 assertEquals("Test parenthood", ((CalledFunction
) segments
[i
- 1]).getAddr(), NonNullUtils
.checkNotNull(((CalledFunction
) segments
[i
]).getParent()).getAddr());
291 * Test an empty state system
294 public void EmptyStateSystemTest() {
295 ITmfStateSystemBuilder fixture
= createFixture();
296 fixture
.closeHistory(1002);
297 CGAnalysis cga
= new CGAnalysis();
298 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
299 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
300 assertNotNull(segmentStore
);
301 Object
[] segments
= segmentStore
.toArray();
302 assertEquals("Number of root functions", 0, segments
.length
);
306 * Test a tree shaped call stack. The root function calls the same function
307 * twice. The call stack's structure used in this test is shown below:
310 *---------1----------
316 public void treeTest() {
317 // Build the state system
318 ITmfStateSystemBuilder fixture
= createFixture();
319 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
320 // Create the root function
321 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
322 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
323 fixture
.modifyAttribute(0, statev
, quark
);
324 fixture
.modifyAttribute(100, TmfStateValue
.nullValue(), quark
);
325 // Create the first child
326 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
327 statev
= TmfStateValue
.newValueLong(1);
328 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
329 fixture
.modifyAttribute(10, statev
, quark
);
330 fixture
.modifyAttribute(40, TmfStateValue
.nullValue(), quark
);
331 // Create the second child
332 statev
= TmfStateValue
.newValueLong(2);
333 fixture
.modifyAttribute(50, statev
, quark
);
334 fixture
.modifyAttribute(70, TmfStateValue
.nullValue(), quark
);
335 // Create the third child
336 statev
= TmfStateValue
.newValueLong(1);
337 fixture
.modifyAttribute(80, statev
, quark
);
338 fixture
.modifyAttribute(100, TmfStateValue
.nullValue(), quark
);
340 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_2
);
341 statev
= TmfStateValue
.newValueLong(3);
342 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
343 fixture
.modifyAttribute(15, statev
, quark
);
344 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
345 fixture
.closeHistory(102);
347 // Execute the callGraphAnalysis
348 CGAnalysis cga
= new CGAnalysis();
349 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
350 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
351 // Test segment store
352 assertNotNull(segmentStore
);
353 Object
[] segments
= segmentStore
.toArray();
354 assertEquals("Number of segments found", 5, segments
.length
);
355 List
<@NonNull CalledFunction
> rootFunctions
= cga
.getThreads();
356 assertEquals("Test the number of root functions found", 1, rootFunctions
.size());
357 CalledFunction rootFunction
= rootFunctions
.get(0);
359 // Test the segments links
360 assertEquals("Children number:First parent", 3, rootFunction
.getChildren().size());
361 List
<@NonNull CalledFunction
> firstDepthFunctions
= rootFunctions
.get(0).getChildren();
362 CalledFunction firstChild
= firstDepthFunctions
.get(0);
363 CalledFunction secondChild
= firstDepthFunctions
.get(1);
364 CalledFunction thirdChild
= firstDepthFunctions
.get(2);
365 assertEquals("Test parenthood: First child", rootFunction
.getAddr(), NonNullUtils
.checkNotNull(firstChild
.getParent()).getAddr());
366 assertEquals("Test parenthood: Second parent", rootFunction
.getAddr(), NonNullUtils
.checkNotNull(secondChild
.getParent()).getAddr());
367 assertEquals("Test parenthood: Third parent", rootFunction
.getAddr(), NonNullUtils
.checkNotNull(thirdChild
.getParent()).getAddr());
368 assertEquals("Children number: First child", 1, firstChild
.getChildren().size());
369 CalledFunction leaf
= firstChild
.getChildren().get(0);
370 assertEquals("Test parenthood: Third parent", firstChild
.getAddr(), NonNullUtils
.checkNotNull(leaf
.getParent()).getAddr());
371 assertTrue("Children number:leaf", leaf
.getChildren().isEmpty());
373 // Test the segments self time
374 assertEquals("Parent's self time", 30, rootFunction
.getSelfTime());
375 assertEquals("First child's self time", 25, firstChild
.getSelfTime());
376 assertEquals("Second child's self time", 20, secondChild
.getSelfTime());
377 assertEquals("Third child's self time", 20, thirdChild
.getSelfTime());
378 assertEquals("Leaf's self time", 5, leaf
.getSelfTime());
379 // Test the segments duration
380 assertEquals("Test first function's duration", 100, rootFunction
.getLength());
381 assertEquals("Test first child's duration", 30, firstChild
.getLength());
382 assertEquals("Test second child's duration", 20, secondChild
.getLength());
383 assertEquals("Test third child's duration", 20, thirdChild
.getLength());
384 assertEquals("Test leaf's duration", 5, leaf
.getLength());
386 // Test the segments Depth
387 assertEquals("Depth: Parent", 0, rootFunction
.getDepth());
388 assertEquals("Depth: First child", 1, firstChild
.getDepth());
389 assertEquals("Depth: Second child", 1, secondChild
.getDepth());
390 assertEquals("Depth: Third child", 1, thirdChild
.getDepth());
391 assertEquals("Depth: Leaf", 2, leaf
.getDepth());
393 // Test if the first child and the third one have the same address
394 assertEquals("Test the address of two functions", firstChild
.getAddr(), thirdChild
.getAddr());