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