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