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             int processId = getProcessId(ss, processQuark, ss.getCurrentEndTime());
 184             for (int threadQuark : ss.getQuarks(processQuark, threadsPattern)) {
 185                 if (!iterateOverQuark(ss, processId, threadQuark, callStackPath, monitor)) {
 186                     return false;
 187                 }
 188             }
 189         }
 190         sendUpdate(fStore);
 191         return true;
 192     }
 193
 194     /**
 195      * Iterate over functions with the same quark,search for their callees then
 196      * add them to the segment store
 197      *
 198      * @param stateSystem
 199      *            The state system
 200      * @param processId
 201      *            The process ID of the traced application
 202      * @param threadQuark
 203      *            The thread quark
 204      * @param subAttributePath
 205      *            sub-Attributes path
 206      * @param monitor
 207      *            The monitor
 208      * @return Boolean
 209      */
 210     private boolean iterateOverQuark(ITmfStateSystem stateSystem, int processId, int threadQuark, String[] subAttributePath, IProgressMonitor monitor) {
 211         String threadName = stateSystem.getAttributeName(threadQuark);
 212         long threadId = -1;
 213         ITmfStateInterval interval = null;
 214         try {
 215             interval = stateSystem.querySingleState(stateSystem.getStartTime(), threadQuark);
 216             ITmfStateValue threadStateValue = interval.getStateValue();
 217             if (threadStateValue.getType() == Type.LONG || threadStateValue.getType() == Type.INTEGER) {
 218                 threadId = threadStateValue.unboxLong();
 219             } else {
 220                 try {
 221                     threadId = Long.parseLong(threadName);
 222                 } catch (NumberFormatException e) {
 223                     /* use default threadId */
 224                 }
 225             }
 226         } catch (StateSystemDisposedException error) {
 227             Activator.getInstance().logError(Messages.QueringStateSystemError, error);
 228         }
 229         try {
 230             long curTime = stateSystem.getStartTime();
 231             long limit = stateSystem.getCurrentEndTime();
 232             AbstractCalledFunction initSegment = CalledFunctionFactory.create(0, 0, 0, threadName, processId, null);
 233             ThreadNode init = new ThreadNode(initSegment, 0, threadId);
 234             while (curTime < limit) {
 235                 if (monitor.isCanceled()) {
 236                     return false;
 237                 }
 238                 int callStackQuark = stateSystem.getQuarkRelative(threadQuark, subAttributePath);
 239                 fCurrentQuarks = stateSystem.getSubAttributes(callStackQuark, false);
 240                 if (fCurrentQuarks.isEmpty()) {
 241                     return false;
 242                 }
 243                 final int depth = 0;
 244                 int quarkParent = fCurrentQuarks.get(depth);
 245                 interval = stateSystem.querySingleState(curTime, quarkParent);
 246                 ITmfStateValue stateValue = interval.getStateValue();
 247
 248                 if (!stateValue.isNull()) {
 249                     long intervalStart = interval.getStartTime();
 250                     long intervalEnd = interval.getEndTime();
 251                     // Create the segment for the first call event.
 252                     AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, depth, stateValue, processId, null);
 253                     fRootFunctions.add(segment);
 254                     AggregatedCalledFunction firstNode = new AggregatedCalledFunction(segment, fCurrentQuarks.size());
 255                     if (!findChildren(segment, depth, stateSystem, fCurrentQuarks.size() + fCurrentQuarks.get(depth), firstNode, processId, monitor)) {
 256                         return false;
 257                     }
 258                     init.addChild(firstNode);
 259                 }
 260
 261                 curTime = interval.getEndTime() + 1;
 262             }
 263             fThreadNodes.add(init);
 264         } catch (AttributeNotFoundException | StateSystemDisposedException | TimeRangeException e) {
 265             Activator.getInstance().logError(Messages.QueringStateSystemError, e);
 266             return false;
 267         }
 268         return true;
 269     }
 270
 271     /**
 272      * Find the functions called by a parent function in a call stack then add
 273      * segments for each child, updating the self times of each node
 274      * accordingly.
 275      *
 276      * @param node
 277      *            The segment of the stack call event(the parent) callStackQuark
 278      * @param depth
 279      *            The depth of the parent function
 280      * @param ss
 281      *            The quark of the segment parent ss The actual state system
 282      * @param maxQuark
 283      *            The last quark in the state system
 284      * @param aggregatedCalledFunction
 285      *            A node in the aggregation tree
 286      * @param processId
 287      *            The process ID of the traced application
 288      * @param monitor
 289      *            The progress monitor The progress monitor TODO: if stack size
 290      *            is an issue, convert to a stack instead of recursive function
 291      */
 292     private boolean findChildren(AbstractCalledFunction node, int depth, ITmfStateSystem ss, int maxQuark, AggregatedCalledFunction aggregatedCalledFunction, int processId, IProgressMonitor monitor) {
 293         fStore.add(node);
 294         long curTime = node.getStart();
 295         long limit = node.getEnd();
 296         ITmfStateInterval interval = null;
 297         while (curTime < limit) {
 298             if (monitor.isCanceled()) {
 299                 return false;
 300             }
 301             try {
 302                 if (depth + 1 < fCurrentQuarks.size()) {
 303                     interval = ss.querySingleState(curTime, fCurrentQuarks.get(depth + 1));
 304                 } else {
 305                     return true;
 306                 }
 307             } catch (StateSystemDisposedException e) {
 308                 Activator.getInstance().logError(Messages.QueringStateSystemError, e);
 309                 return false;
 310             }
 311             ITmfStateValue stateValue = interval.getStateValue();
 312             if (!stateValue.isNull()) {
 313                 long intervalStart = interval.getStartTime();
 314                 long intervalEnd = interval.getEndTime();
 315                 if (intervalStart < node.getStart() || intervalEnd > limit) {
 316                     return true;
 317                 }
 318                 AbstractCalledFunction segment = CalledFunctionFactory.create(intervalStart, intervalEnd + 1, node.getDepth() + 1, stateValue, processId, node);
 319                 AggregatedCalledFunction childNode = new AggregatedCalledFunction(segment, aggregatedCalledFunction);
 320                 // Search for the children with the next quark.
 321                 findChildren(segment, depth + 1, ss, maxQuark, childNode, processId, monitor);
 322                 aggregatedCalledFunction.addChild(childNode);
 323                 node.addChild(segment);
 324             }
 325             curTime = interval.getEndTime() + 1;
 326         }
 327         return true;
 328     }
 329
 330     @Override
 331     public void addListener(@NonNull IAnalysisProgressListener listener) {
 332         fListeners.add(listener);
 333     }
 334
 335     @Override
 336     public void removeListener(@NonNull IAnalysisProgressListener listener) {
 337         fListeners.remove(listener);
 338     }
 339
 340     @Override
 341     protected void canceling() {
 342         // Do nothing
 343     }
 344
 345     @Override
 346     public @Nullable ISegmentStore<@NonNull ISegment> getSegmentStore() {
 347         return fStore;
 348     }
 349
 350     /**
 351      * Update listeners
 352      *
 353      * @param store
 354      *            The segment store
 355      */
 356     protected void sendUpdate(final ISegmentStore<@NonNull ISegment> store) {
 357         getListeners().forEach(listener -> listener.onComplete(this, store));
 358     }
 359
 360     /**
 361      * Get Listeners
 362      *
 363      * @return The listeners
 364      */
 365     protected Iterable<IAnalysisProgressListener> getListeners() {
 366         return Arrays.stream(fListeners.getListeners())
 367                 .filter(listener -> listener instanceof IAnalysisProgressListener)
 368                 .map(listener -> (IAnalysisProgressListener) listener)
 369                 .collect(Collectors.toList());
 370     }
 371
 372     /**
 373      * The functions of the first level
 374      *
 375      * @return Functions of the first level
 376      */
 377     public List<ICalledFunction> getRootFunctions() {
 378         return ImmutableList.copyOf(fRootFunctions);
 379     }
 380
 381     /**
 382      * List of thread nodes. Each thread has a virtual node having the root
 383      * functions called as children.
 384      *
 385      * @return The thread nodes
 386      */
 387     public List<ThreadNode> getThreadNodes() {
 388         return ImmutableList.copyOf(fThreadNodes);
 389     }
 390
 391     private static int getProcessId(ITmfStateSystem ss, int processQuark, long curTime) {
 392         int processId = -1;
 393         if (processQuark != ITmfStateSystem.ROOT_ATTRIBUTE) {
 394             try {
 395                 ITmfStateInterval interval = ss.querySingleState(curTime, processQuark);
 396                 String processName = ss.getAttributeName(processQuark);
 397                 ITmfStateValue processStateValue = interval.getStateValue();
 398                 if (processStateValue.getType() == Type.INTEGER) {
 399                     processId = processStateValue.unboxInt();
 400                 } else {
 401                     try {
 402                         processId = Integer.parseInt(processName);
 403                     } catch (NumberFormatException e) {
 404                         /* use default processId */
 405                     }
 406                 }
 407             } catch (StateSystemDisposedException e) {
 408                 // ignore
 409             }
 410         }
 411         return processId;
 412     }
 413 }