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
.assertEquals
;
13 import static org
.junit
.Assert
.assertFalse
;
14 import static org
.junit
.Assert
.assertNotNull
;
15 import static org
.junit
.Assert
.assertTrue
;
17 import java
.util
.Collection
;
18 import java
.util
.Collections
;
19 import java
.util
.Iterator
;
20 import java
.util
.List
;
21 import java
.util
.Objects
;
23 import org
.eclipse
.core
.runtime
.IProgressMonitor
;
24 import org
.eclipse
.core
.runtime
.NullProgressMonitor
;
25 import org
.eclipse
.jdt
.annotation
.NonNull
;
26 import org
.eclipse
.jdt
.annotation
.Nullable
;
27 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
28 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.AggregatedCalledFunction
;
29 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.CallGraphAnalysis
;
30 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.ICalledFunction
;
31 import org
.eclipse
.tracecompass
.internal
.analysis
.timing
.core
.callgraph
.ThreadNode
;
32 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegment
;
33 import org
.eclipse
.tracecompass
.segmentstore
.core
.ISegmentStore
;
34 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystem
;
35 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystemBuilder
;
36 import org
.eclipse
.tracecompass
.statesystem
.core
.StateSystemFactory
;
37 import org
.eclipse
.tracecompass
.statesystem
.core
.backend
.IStateHistoryBackend
;
38 import org
.eclipse
.tracecompass
.statesystem
.core
.backend
.StateHistoryBackendFactory
;
39 import org
.eclipse
.tracecompass
.statesystem
.core
.statevalue
.TmfStateValue
;
40 import org
.eclipse
.tracecompass
.tmf
.core
.segment
.ISegmentAspect
;
41 import org
.junit
.Assert
;
42 import org
.junit
.Test
;
45 * Test the CallGraphAnalysis.This creates a virtual state system in each test
46 * and tests the segment store returned by the CallGraphAnalysis.
48 * @author Sonia Farrah
51 public class CallGraphAnalysisTest
{
53 private static final @NonNull String PROCESS_PATH
= "Processes";
54 private static final @NonNull String THREAD_PATH
= "Thread";
55 private static final @NonNull String CALLSTACK_PATH
= "CallStack";
56 private static final String QUARK_0
= "0";
57 private static final String QUARK_1
= "1";
58 private static final String QUARK_2
= "2";
59 private static final Integer SMALL_AMOUNT_OF_SEGMENT
= 3;
60 private static final int LARGE_AMOUNT_OF_SEGMENTS
= 1000;
61 private static final String
@NonNull [] CSP
= { CALLSTACK_PATH
};
62 private static final String
@NonNull [] PP
= { PROCESS_PATH
};
63 private static final String
@NonNull [] TP
= { THREAD_PATH
};
66 * This class is used to make the CallGraphAnalysis's method
67 * iterateOverStateSystem() visible to test
69 private class CGAnalysis
extends CallGraphAnalysis
{
72 protected boolean iterateOverStateSystem(@Nullable ITmfStateSystem ss
, String
[] threadsPattern
, String
[] processesPattern
, String
[] callStackPath
, IProgressMonitor monitor
) {
73 return super.iterateOverStateSystem(ss
, threadsPattern
, processesPattern
, callStackPath
, monitor
);
77 public @NonNull Iterable
<@NonNull ISegmentAspect
> getSegmentAspects() {
78 return Collections
.EMPTY_LIST
;
83 private static ITmfStateSystemBuilder
createFixture() {
84 IStateHistoryBackend backend
;
85 backend
= StateHistoryBackendFactory
.createInMemoryBackend("Test", 0L);
86 ITmfStateSystemBuilder fixture
= StateSystemFactory
.newStateSystem(backend
);
91 * Test cascade state system. The call stack's structure used in this test
102 public void CascadeTest() {
103 ITmfStateSystemBuilder fixture
= createFixture();
104 // Build the state system
107 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
108 for (int i
= 1; i
<= SMALL_AMOUNT_OF_SEGMENT
; i
++) {
109 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
110 TmfStateValue statev
= TmfStateValue
.newValueLong(i
);
111 fixture
.modifyAttribute(start
, TmfStateValue
.nullValue(), quark
);
112 fixture
.modifyAttribute(start
+ i
, statev
, quark
);
113 fixture
.modifyAttribute(end
- i
, TmfStateValue
.nullValue(), quark
);
116 fixture
.closeHistory(1002);
117 // Execute the CallGraphAnalysis
118 CGAnalysis cga
= new CGAnalysis();
119 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
120 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
121 // Test the segment store generated by the analysis
122 assertNotNull(segmentStore
);
123 Object
[] segments
= segmentStore
.toArray();
124 assertEquals("Number of segments Found", 3, segments
.length
);
125 ICalledFunction f1
= (ICalledFunction
) segments
[0];
126 ICalledFunction f2
= (ICalledFunction
) segments
[1];
127 ICalledFunction f3
= (ICalledFunction
) segments
[2];
128 assertEquals("Test the parenthood", NonNullUtils
.checkNotNull(f2
.getParent()).getSymbol(), f1
.getSymbol());
129 assertEquals("Children number:First parent", 1, f1
.getChildren().size());
130 assertEquals("Children number:Second parent", 1, f2
.getChildren().size());
131 assertTrue("Children number:Second parent", f3
.getChildren().isEmpty());
132 assertTrue("Children number:Child(leaf)", ((ICalledFunction
) segments
[2]).getChildren().isEmpty());
133 assertEquals("Parent's self time", 2, f1
.getSelfTime());
134 assertEquals("Child's self time", 2, f2
.getSelfTime());
135 assertEquals("The leaf's self time", 994, f3
.getSelfTime());
136 assertEquals("Test first function's duration", 998, f1
.getLength());
137 assertEquals("Test second function's duration", 996, f2
.getLength());
138 assertEquals("Test third function's duration", 994, f3
.getLength());
139 assertEquals("Depth:First parent", 0, f1
.getDepth());
140 assertEquals("Depth:Second parent", 1, f2
.getDepth());
141 assertEquals("Depth:Last child", 2, f3
.getDepth());
146 * Build a pyramid shaped call stack.This call stack contains three
147 * functions ,Its structure is shown below :
155 private static void buildPyramidCallStack(ITmfStateSystemBuilder fixture
) {
156 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
157 // Create the first function
158 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
159 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
160 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
161 fixture
.modifyAttribute(10, statev
, quark
);
162 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
163 // Create the second function
164 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
165 statev
= TmfStateValue
.newValueLong(1);
166 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
167 fixture
.modifyAttribute(5, statev
, quark
);
168 fixture
.modifyAttribute(25, TmfStateValue
.nullValue(), quark
);
169 // Create the third function
170 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_2
);
171 statev
= TmfStateValue
.newValueLong(2);
172 fixture
.modifyAttribute(0, statev
, quark
);
173 fixture
.modifyAttribute(30, TmfStateValue
.nullValue(), quark
);
175 fixture
.closeHistory(31);
179 * Test pyramid state system. The call stack's structure used in this test
189 public void PyramidTest() {
190 ITmfStateSystemBuilder fixture
= createFixture();
191 buildPyramidCallStack(fixture
);
192 // Execute the callGraphAnalysis
193 CGAnalysis cga
= new CGAnalysis();
194 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
195 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
196 assertNotNull(segmentStore
);
197 Object
[] segments
= segmentStore
.toArray();
198 ICalledFunction f1
= (ICalledFunction
) segments
[0];
199 assertEquals("Number of segments Found", 1, segments
.length
);
200 assertEquals("Callees number", 0, f1
.getChildren().size());
201 assertEquals("Function's self time", 10, f1
.getSelfTime());
202 assertEquals("Compare the function's self time and total time", f1
.getLength(), f1
.getSelfTime());
203 assertEquals("Function's depth", 0, f1
.getDepth());
208 * Test mutliRoots state system. The call stack's structure used in this
209 * test is shown below:
217 public void multiFunctionRootsTest() {
218 ITmfStateSystemBuilder fixture
= createFixture();
219 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
220 // Create the first root function
221 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
222 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
223 fixture
.modifyAttribute(0, statev
, quark
);
224 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
225 // Create the second root function
226 statev
= TmfStateValue
.newValueLong(1);
227 fixture
.modifyAttribute(30, statev
, quark
);
228 fixture
.modifyAttribute(50, TmfStateValue
.nullValue(), quark
);
229 // Create the first root function's callee
230 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
231 statev
= TmfStateValue
.newValueLong(2);
232 fixture
.modifyAttribute(0, statev
, quark
);
233 fixture
.modifyAttribute(10, TmfStateValue
.nullValue(), quark
);
234 // Create the second root function's callee
235 statev
= TmfStateValue
.newValueLong(3);
236 fixture
.modifyAttribute(30, statev
, quark
);
237 fixture
.modifyAttribute(40, TmfStateValue
.nullValue(), quark
);
238 fixture
.closeHistory(51);
240 // Execute the callGraphAnalysis
241 CGAnalysis cga
= new CGAnalysis();
242 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
243 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
244 // Test the segment store
245 assertNotNull(segmentStore
);
246 Object
[] segments
= segmentStore
.toArray();
247 List
<@NonNull ICalledFunction
> threads
= cga
.getRootFunctions();
248 assertEquals("Number of root functions", 2, threads
.size());
249 assertEquals("Number of children: first root function", 1, threads
.get(0).getChildren().size());
250 assertEquals("Number of children: first root function", 1, threads
.get(1).getChildren().size());
251 ICalledFunction firstChild
= threads
.get(0).getChildren().get(0);
252 ICalledFunction secondChild
= threads
.get(1).getChildren().get(0);
253 assertEquals("Number of segments found", 4, segments
.length
);
254 assertNotNull(firstChild
.getParent());
255 assertNotNull(secondChild
.getParent());
257 assertEquals("Test of parenthood", NonNullUtils
.checkNotNull(firstChild
.getParent()).getSymbol(), threads
.get(0).getSymbol());
258 assertEquals("Test of parenthood", NonNullUtils
.checkNotNull(secondChild
.getParent()).getSymbol(), threads
.get(1).getSymbol());
263 * Test state system with a Large amount of segments. All segments have the
264 * same length. The call stack's structure used in this test is shown below:
274 public void LargeTest() {
275 // Build the state system
276 ITmfStateSystemBuilder fixture
= createFixture();
277 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
278 for (int i
= 0; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
279 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
280 TmfStateValue statev
= TmfStateValue
.newValueLong(i
);
281 fixture
.pushAttribute(0, statev
, quark
);
283 for (int i
= 0; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
284 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, Integer
.toString(i
));
285 fixture
.popAttribute(10, quark
);
287 fixture
.closeHistory(11);
288 // Execute the callGraphAnalysis
289 CGAnalysis cga
= new CGAnalysis();
290 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
291 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
292 // Test segment store
293 assertNotNull(segmentStore
);
294 Object
[] segments
= segmentStore
.toArray();
295 assertEquals("Number of segments found", LARGE_AMOUNT_OF_SEGMENTS
, segments
.length
);
296 for (int i
= 1; i
< LARGE_AMOUNT_OF_SEGMENTS
; i
++) {
297 assertEquals("Test parenthood", ((ICalledFunction
) segments
[i
- 1]).getSymbol(), NonNullUtils
.checkNotNull(((ICalledFunction
) segments
[i
]).getParent()).getSymbol());
303 * Test an empty state system
306 public void EmptyStateSystemTest() {
307 ITmfStateSystemBuilder fixture
= createFixture();
308 fixture
.closeHistory(1002);
309 CGAnalysis cga
= new CGAnalysis();
310 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
311 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
312 assertNotNull(segmentStore
);
313 Object
[] segments
= segmentStore
.toArray();
314 assertEquals("Number of root functions", 0, segments
.length
);
319 * Test a tree shaped call stack. The root function calls the same function
320 * twice. The call stack's structure used in this test is shown below:
323 *---------1----------
329 public void treeTest() {
330 // Build the state system
331 ITmfStateSystemBuilder fixture
= createFixture();
332 int parentQuark
= fixture
.getQuarkAbsoluteAndAdd(PROCESS_PATH
, THREAD_PATH
, CALLSTACK_PATH
);
333 // Create the root function
334 int quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_0
);
335 TmfStateValue statev
= TmfStateValue
.newValueLong(0);
336 fixture
.modifyAttribute(0, statev
, quark
);
337 fixture
.modifyAttribute(100, TmfStateValue
.nullValue(), quark
);
338 // Create the first child
339 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_1
);
340 statev
= TmfStateValue
.newValueLong(1);
341 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
342 fixture
.modifyAttribute(10, statev
, quark
);
343 fixture
.modifyAttribute(40, TmfStateValue
.nullValue(), quark
);
344 // Create the second child
345 statev
= TmfStateValue
.newValueLong(2);
346 fixture
.modifyAttribute(50, statev
, quark
);
347 fixture
.modifyAttribute(70, TmfStateValue
.nullValue(), quark
);
348 // Create the third child
349 statev
= TmfStateValue
.newValueLong(1);
350 fixture
.modifyAttribute(80, statev
, quark
);
351 fixture
.modifyAttribute(100, TmfStateValue
.nullValue(), quark
);
353 quark
= fixture
.getQuarkRelativeAndAdd(parentQuark
, QUARK_2
);
354 statev
= TmfStateValue
.newValueLong(3);
355 fixture
.modifyAttribute(0, TmfStateValue
.nullValue(), quark
);
356 fixture
.modifyAttribute(15, statev
, quark
);
357 fixture
.modifyAttribute(20, TmfStateValue
.nullValue(), quark
);
358 fixture
.closeHistory(102);
360 // Execute the callGraphAnalysis
361 CGAnalysis cga
= new CGAnalysis();
362 assertTrue(cga
.iterateOverStateSystem(fixture
, TP
, PP
, CSP
, new NullProgressMonitor()));
363 ISegmentStore
<@NonNull ISegment
> segmentStore
= cga
.getSegmentStore();
364 // Test segment store
365 assertNotNull(segmentStore
);
366 Object
[] segments
= segmentStore
.toArray();
367 assertEquals("Number of segments found", 5, segments
.length
);
368 List
<@NonNull ICalledFunction
> rootFunctions
= cga
.getRootFunctions();
369 assertEquals("Test the number of root functions found", 1, rootFunctions
.size());
370 ICalledFunction rootFunction
= rootFunctions
.get(0);
372 // Test the segments links
373 assertEquals("Children number:First parent", 3, rootFunction
.getChildren().size());
374 List
<@NonNull ICalledFunction
> firstDepthFunctions
= rootFunctions
.get(0).getChildren();
375 ICalledFunction firstChild
= firstDepthFunctions
.get(0);
376 ICalledFunction secondChild
= firstDepthFunctions
.get(1);
377 ICalledFunction thirdChild
= firstDepthFunctions
.get(2);
378 assertEquals("Test parenthood: First child", rootFunction
.getSymbol(), NonNullUtils
.checkNotNull(firstChild
.getParent()).getSymbol());
379 assertEquals("Test parenthood: Second parent", rootFunction
.getSymbol(), NonNullUtils
.checkNotNull(secondChild
.getParent()).getSymbol());
380 assertEquals("Test parenthood: Third parent", rootFunction
.getSymbol(), NonNullUtils
.checkNotNull(thirdChild
.getParent()).getSymbol());
381 assertEquals("Children number: First child", 1, firstChild
.getChildren().size());
382 ICalledFunction leaf
= firstChild
.getChildren().get(0);
383 assertEquals("Test parenthood: Third parent", firstChild
.getSymbol(), NonNullUtils
.checkNotNull(leaf
.getParent()).getSymbol());
384 assertTrue("Children number:leaf", leaf
.getChildren().isEmpty());
386 // Test the segments self time
387 assertEquals("Parent's self time", 30, rootFunction
.getSelfTime());
388 assertEquals("First child's self time", 25, firstChild
.getSelfTime());
389 assertEquals("Second child's self time", 20, secondChild
.getSelfTime());
390 assertEquals("Third child's self time", 20, thirdChild
.getSelfTime());
391 assertEquals("Leaf's self time", 5, leaf
.getSelfTime());
392 // Test the segments duration
393 assertEquals("Test first function's duration", 100, rootFunction
.getLength());
394 assertEquals("Test first child's duration", 30, firstChild
.getLength());
395 assertEquals("Test second child's duration", 20, secondChild
.getLength());
396 assertEquals("Test third child's duration", 20, thirdChild
.getLength());
397 assertEquals("Test leaf's duration", 5, leaf
.getLength());
399 // Test the segments Depth
400 assertEquals("Depth: Parent", 0, rootFunction
.getDepth());
401 assertEquals("Depth: First child", 1, firstChild
.getDepth());
402 assertEquals("Depth: Second child", 1, secondChild
.getDepth());
403 assertEquals("Depth: Third child", 1, thirdChild
.getDepth());
404 assertEquals("Depth: Leaf", 2, leaf
.getDepth());
406 // Test if the first child and the third one have the same address
407 assertEquals("Test the address of two functions", firstChild
.getSymbol(), thirdChild
.getSymbol());
410 Collection
<@NonNull ThreadNode
> flameGraph
= cga
.getFlameGraph();
411 assertNotNull("Test Flamegraph", flameGraph
);
412 assertFalse(flameGraph
.isEmpty());
413 ThreadNode flamegraphRoot
= flameGraph
.iterator().next();
414 assertNotNull("Test Flamegraph root", flamegraphRoot
);
416 Collection
<@NonNull ThreadNode
> threadGraph
= cga
.getThreadNodes();
417 assertNotNull("Test ThreadNodes", threadGraph
);
418 assertFalse(threadGraph
.isEmpty());
419 ThreadNode threadgraphRoot
= threadGraph
.iterator().next();
420 localAssertEquals("Test Flamegraph root", threadgraphRoot
, flamegraphRoot
);
425 private void localAssertEquals(String message
, AggregatedCalledFunction aggregatedCalledFunction
, AggregatedCalledFunction actualElem
) {
426 if (Objects
.equals(aggregatedCalledFunction
, actualElem
)) {
429 assertNotNull(message
, aggregatedCalledFunction
);
430 assertNotNull(message
, actualElem
);
431 Assert
.assertEquals(message
, aggregatedCalledFunction
.getDepth(), actualElem
.getDepth());
432 Assert
.assertEquals(message
, aggregatedCalledFunction
.getDuration(), actualElem
.getDuration());
433 Assert
.assertEquals(message
, aggregatedCalledFunction
.getMaxDepth(), actualElem
.getMaxDepth());
434 Assert
.assertEquals(message
, aggregatedCalledFunction
.getMaxDepth(), actualElem
.getMaxDepth());
435 Assert
.assertEquals(message
, aggregatedCalledFunction
.getSelfTime(), actualElem
.getSelfTime());
436 localAssertEquals(message
, aggregatedCalledFunction
.getChildren(), actualElem
.getChildren());
439 private void localAssertEquals(String message
, @NonNull Collection
<@NonNull AggregatedCalledFunction
> expected
, @NonNull Collection
<@NonNull AggregatedCalledFunction
> actual
) {
440 Iterator
<@NonNull AggregatedCalledFunction
> expectedIter
= expected
.iterator();
441 for (AggregatedCalledFunction actualElem
: actual
) {
442 localAssertEquals(message
, expectedIter
.next(), actualElem
);