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