analysis/org.eclipse.tracecompass.analysis.timing.core.tests/src/org/eclipse/tracecompass/analysis/timing/core/tests/callgraph/CallGraphAnalysisTest.java

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