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 = new AggregatedCalledFunction(threadName, 0L, 0, 0, null);
 209         try {
 210             long curTime = stateSystem.getStartTime();
 211             long limit = stateSystem.getCurrentEndTime();
 212             while (curTime < limit) {
 213                 if (monitor.isCanceled()) {
 214                     return false;
 215                 }
 216                 int callStackQuark = stateSystem.getQuarkRelative(quark, subAttributePath);
 217                 fCurrentQuarks = stateSystem.getSubAttributes(callStackQuark, false);
 218                 if (fCurrentQuarks.isEmpty()) {
 219                     return false;
 220                 }
 221                 final int depth = 0;
 222                 int quarkParent = fCurrentQuarks.get(depth);
 223                 ITmfStateInterval interval = stateSystem.querySingleState(curTime, quarkParent);
 224                 ITmfStateValue stateValue = interval.getStateValue();
 225
 226                 if (!stateValue.isNull()) {
 227                     long intervalStart = interval.getStartTime();
 228                     long intervalEnd = interval.getEndTime();
 229                     // Create the segment for the first call event.
 230                     AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, depth, stateValue, null);
 231                     fRootFunctions.add(segment);
 232                     AggregatedCalledFunction firstNode = new AggregatedCalledFunction(stateValue, intervalEnd - intervalStart + 1, segment.getDepth(), fCurrentQuarks.size(), null);
 233                     if (!findChildren(segment, depth, stateSystem, fCurrentQuarks.size() + fCurrentQuarks.get(depth), firstNode, monitor)) {
 234                         return false;
 235                     }
 236                     init.addChild(firstNode);
 237                 }
 238
 239                 curTime = interval.getEndTime() + 1;
 240             }
 241
 242         } catch (AttributeNotFoundException | StateSystemDisposedException | TimeRangeException e) {
 243             Activator.getInstance().logError(Messages.QueringStateSystemError, e);
 244             return false;
 245         }
 246         fThreadNodes.add(init);
 247         return true;
 248     }
 249
 250     /**
 251      * Find the functions called by a parent function in a call stack then add
 252      * segments for each child, updating the self times of each node
 253      * accordingly.
 254      *
 255      * @param node
 256      *            The segment of the stack call event(the parent) callStackQuark
 257      * @param depth
 258      *            The depth of the parent function
 259      * @param ss
 260      *            The quark of the segment parent ss The actual state system
 261      * @param maxQuark
 262      *            The last quark in the state system
 263      * @param AggregatedCalledFunction
 264      *            A node in the aggregation tree
 265      * @param monitor
 266      *            The progress monitor The progress monitor TODO: if stack size
 267      *            is an issue, convert to a stack instead of recursive function
 268      */
 269     private boolean findChildren(AbstractCalledFunction node, int depth, ITmfStateSystem ss, int maxQuark, AggregatedCalledFunction aggregatedCalledFunction, IProgressMonitor monitor) {
 270         fStore.add(node);
 271         long curTime = node.getStart();
 272         long limit = node.getEnd();
 273         ITmfStateInterval interval = null;
 274         while (curTime < limit) {
 275             if (monitor.isCanceled()) {
 276                 return false;
 277             }
 278             try {
 279                 if (depth + 1 < fCurrentQuarks.size()) {
 280                     interval = ss.querySingleState(curTime, fCurrentQuarks.get(depth + 1));
 281                 } else {
 282                     return true;
 283                 }
 284             } catch (StateSystemDisposedException e) {
 285                 Activator.getInstance().logError(Messages.QueringStateSystemError, e);
 286                 return false;
 287             }
 288             ITmfStateValue stateValue = interval.getStateValue();
 289             if (!stateValue.isNull()) {
 290                 long intervalStart = interval.getStartTime();
 291                 long intervalEnd = interval.getEndTime();
 292                 if (intervalStart < node.getStart() || intervalEnd > limit) {
 293                     return true;
 294                 }
 295                 AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, node.getDepth() + 1, stateValue, node);
 296                 AggregatedCalledFunction childNode = new AggregatedCalledFunction(stateValue, segment.getLength(), segment.getDepth(), aggregatedCalledFunction.getMaxDepth(), aggregatedCalledFunction);
 297                 // Search for the children with the next quark.
 298                 findChildren(segment, depth + 1, ss, maxQuark, childNode, monitor);
 299                 aggregatedCalledFunction.addChild(childNode);
 300                 node.addChild(segment);
 301             }
 302             curTime = interval.getEndTime() + 1;
 303         }
 304         return true;
 305     }
 306
 307     @Override
 308     public void addListener(@NonNull IAnalysisProgressListener listener) {
 309         fListeners.add(listener);
 310     }
 311
 312     @Override
 313     public void removeListener(@NonNull IAnalysisProgressListener listener) {
 314         fListeners.remove(listener);
 315     }
 316
 317     @Override
 318     protected void canceling() {
 319         // Do nothing
 320     }
 321
 322     @Override
 323     public @Nullable ISegmentStore<@NonNull ISegment> getSegmentStore() {
 324         return fStore;
 325     }
 326
 327     /**
 328      * Update listeners
 329      *
 330      * @param store
 331      *            The segment store
 332      */
 333     protected void sendUpdate(final ISegmentStore<@NonNull ISegment> store) {
 334         getListeners().forEach(listener -> listener.onComplete(this, store));
 335     }
 336
 337     /**
 338      * Get Listeners
 339      *
 340      * @return The listeners
 341      */
 342     protected Iterable<IAnalysisProgressListener> getListeners() {
 343         return Arrays.stream(fListeners.getListeners())
 344                 .filter(listener -> listener instanceof IAnalysisProgressListener)
 345                 .map(listener -> (IAnalysisProgressListener) listener)
 346                 .collect(Collectors.toList());
 347     }
 348
 349     /**
 350      * The functions of the first level
 351      *
 352      * @return Functions of the first level
 353      */
 354     public List<ICalledFunction> getRootFunctions() {
 355         return ImmutableList.copyOf(fRootFunctions);
 356     }
 357
 358     /**
 359      * List of thread nodes. Each thread has a virtual node having the root
 360      * functions called as children.
 361      *
 362      * @return The thread nodes
 363      */
 364     public List<AggregatedCalledFunction> getThreadNodes() {
 365         return ImmutableList.copyOf(fThreadNodes);
 366     }
 367
 368 }