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