analysis/org.eclipse.tracecompass.analysis.graph.ui/src/org/eclipse/tracecompass/internal/analysis/graph/ui/criticalpath/view/CriticalPathView.java

   1 /*******************************************************************************
   2  * Copyright (c) 2015, 2016 École Polytechnique de Montréal
   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.graph.ui.criticalpath.view;
  11
  12 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  13
  14 import java.util.ArrayList;
  15 import java.util.Collections;
  16 import java.util.Comparator;
  17 import java.util.HashMap;
  18 import java.util.List;
  19 import java.util.Map;
  20
  21 import org.eclipse.core.runtime.IProgressMonitor;
  22 import org.eclipse.jdt.annotation.NonNull;
  23 import org.eclipse.jdt.annotation.Nullable;
  24 import org.eclipse.jface.viewers.Viewer;
  25 import org.eclipse.tracecompass.analysis.graph.core.base.IGraphWorker;
  26 import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge;
  27 import org.eclipse.tracecompass.analysis.graph.core.base.TmfEdge.EdgeType;
  28 import org.eclipse.tracecompass.analysis.graph.core.base.TmfGraph;
  29 import org.eclipse.tracecompass.analysis.graph.core.base.TmfVertex;
  30 import org.eclipse.tracecompass.analysis.graph.core.criticalpath.CriticalPathModule;
  31 import org.eclipse.tracecompass.common.core.NonNullUtils;
  32 import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphStatistics;
  33 import org.eclipse.tracecompass.internal.analysis.graph.core.base.TmfGraphVisitor;
  34 import org.eclipse.tracecompass.internal.analysis.graph.ui.criticalpath.view.CriticalPathPresentationProvider.State;
  35 import org.eclipse.tracecompass.tmf.core.signal.TmfSignalHandler;
  36 import org.eclipse.tracecompass.tmf.core.signal.TmfStartAnalysisSignal;
  37 import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
  38 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceUtils;
  39 import org.eclipse.tracecompass.tmf.ui.views.timegraph.AbstractTimeGraphView;
  40 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.ITimeGraphContentProvider;
  41 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
  42 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeEvent;
  43 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeGraphEntry;
  44 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeEvent;
  45 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeGraphEntry;
  46 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeLinkEvent;
  47
  48 import com.google.common.collect.HashBasedTable;
  49 import com.google.common.collect.Iterables;
  50 import com.google.common.collect.Table;
  51
  52 /**
  53  * The Critical Path view
  54  *
  55  * @author Geneviève Bastien
  56  * @author Francis Giraldeau
  57  */
  58 public class CriticalPathView extends AbstractTimeGraphView {
  59
  60     // ------------------------------------------------------------------------
  61     // Constants
  62     // ------------------------------------------------------------------------
  63
  64     /** View ID */
  65     public static final String ID = "org.eclipse.linuxtools.tmf.analysis.graph.ui.criticalpath.view.criticalpathview"; //$NON-NLS-1$
  66
  67     private static final double NANOINV = 0.000000001;
  68
  69     private static final String COLUMN_PROCESS = Messages.getMessage(Messages.CriticalFlowView_columnProcess);
  70     private static final String COLUMN_ELAPSED = Messages.getMessage(Messages.CriticalFlowView_columnElapsed);
  71     private static final String COLUMN_PERCENT = Messages.getMessage(Messages.CriticalFlowView_columnPercent);
  72
  73     private static final String[] COLUMN_NAMES = new String[] {
  74             COLUMN_PROCESS,
  75             COLUMN_ELAPSED,
  76             COLUMN_PERCENT
  77     };
  78
  79     private static final String[] FILTER_COLUMN_NAMES = new String[] {
  80             COLUMN_PROCESS
  81     };
  82
  83     private final Table<ITmfTrace, Object, List<ILinkEvent>> fLinks = HashBasedTable.create();
  84     /** The trace to entry list hash map */
  85     private final Table<ITmfTrace, Object, TmfGraphStatistics> fObjectStatistics = HashBasedTable.create();
  86
  87     private final CriticalPathContentProvider fContentProvider = new CriticalPathContentProvider();
  88
  89     private TmfGraphStatistics fStats = new TmfGraphStatistics();
  90
  91     private static final IGraphWorker DEFAULT_WORKER = new IGraphWorker() {
  92         @Override
  93         public String getHostId() {
  94             return "default"; //$NON-NLS-1$
  95         }
  96     };
  97
  98     private class CriticalPathContentProvider implements ITimeGraphContentProvider {
  99
 100         private final class HorizontalLinksVisitor extends TmfGraphVisitor {
 101             private final CriticalPathEntry fDefaultParent;
 102             private final Map<String, CriticalPathEntry> fHostEntries;
 103             private final TmfGraph fGraph;
 104             private final ITmfTrace fTrace;
 105             private final HashMap<Object, CriticalPathEntry> fRootList;
 106
 107             private HorizontalLinksVisitor(CriticalPathEntry defaultParent, Map<String, CriticalPathEntry> hostEntries, TmfGraph graph, ITmfTrace trace, HashMap<Object, CriticalPathEntry> rootList) {
 108                 fDefaultParent = defaultParent;
 109                 fHostEntries = hostEntries;
 110                 fGraph = graph;
 111                 fTrace = trace;
 112                 fRootList = rootList;
 113             }
 114
 115             @Override
 116             public void visitHead(TmfVertex node) {
 117                 /* TODO possible null pointer ? */
 118                 IGraphWorker owner = fGraph.getParentOf(node);
 119                 if (owner == null) {
 120                     return;
 121                 }
 122                 if (fRootList.containsKey(owner)) {
 123                     return;
 124                 }
 125                 TmfVertex first = fGraph.getHead(owner);
 126                 TmfVertex last = fGraph.getTail(owner);
 127                 if (first == null || last == null) {
 128                     return;
 129                 }
 130                 setStartTime(Math.min(getStartTime(), first.getTs()));
 131                 setEndTime(Math.max(getEndTime(), last.getTs()));
 132                 // create host entry
 133                 CriticalPathEntry parent = fDefaultParent;
 134                 String host = owner.getHostId();
 135                 if (!fHostEntries.containsKey(host)) {
 136                     fHostEntries.put(host, new CriticalPathEntry(host, fTrace, getStartTime(), getEndTime(), owner));
 137                 }
 138                 parent = checkNotNull(fHostEntries.get(host));
 139                 CriticalPathEntry entry = new CriticalPathEntry(NonNullUtils.nullToEmptyString(owner), fTrace, getStartTime(), getEndTime(), owner);
 140                 parent.addChild(entry);
 141
 142                 fRootList.put(owner, entry);
 143             }
 144
 145             @Override
 146             public void visit(TmfVertex node) {
 147                 setStartTime(Math.min(getStartTime(), node.getTs()));
 148                 setEndTime(Math.max(getEndTime(), node.getTs()));
 149             }
 150
 151             @Override
 152             public void visit(TmfEdge link, boolean horizontal) {
 153                 if (horizontal) {
 154                     Object parent = fGraph.getParentOf(link.getVertexFrom());
 155                     CriticalPathEntry entry = fRootList.get(parent);
 156                     TimeEvent ev = new TimeEvent(entry, link.getVertexFrom().getTs(), link.getDuration(),
 157                             getMatchingState(link.getType()).ordinal());
 158                     entry.addEvent(ev);
 159                 }
 160             }
 161         }
 162
 163         private final class VerticalLinksVisitor extends TmfGraphVisitor {
 164             private final TmfGraph fGraph;
 165             private final List<ILinkEvent> fGraphLinks;
 166             private final Map<Object, CriticalPathEntry> fEntryMap;
 167
 168             private VerticalLinksVisitor(TmfGraph graph, List<ILinkEvent> graphLinks, Map<Object, CriticalPathEntry> entryMap) {
 169                 fGraph = graph;
 170                 fGraphLinks = graphLinks;
 171                 fEntryMap = entryMap;
 172             }
 173
 174             @Override
 175             public void visitHead(TmfVertex node) {
 176
 177             }
 178
 179             @Override
 180             public void visit(TmfVertex node) {
 181
 182             }
 183
 184             @Override
 185             public void visit(TmfEdge link, boolean horizontal) {
 186                 if (!horizontal) {
 187                     Object parentFrom = fGraph.getParentOf(link.getVertexFrom());
 188                     Object parentTo = fGraph.getParentOf(link.getVertexTo());
 189                     CriticalPathEntry entryFrom = fEntryMap.get(parentFrom);
 190                     CriticalPathEntry entryTo = fEntryMap.get(parentTo);
 191                     TimeLinkEvent lk = new TimeLinkEvent(entryFrom, entryTo, link.getVertexFrom().getTs(),
 192                             link.getVertexTo().getTs() - link.getVertexFrom().getTs(), getMatchingState(link.getType()).ordinal());
 193                     fGraphLinks.add(lk);
 194                 }
 195             }
 196         }
 197
 198         private Map<Object, Map<Object, CriticalPathEntry>> workerMaps = new HashMap<>();
 199         private Map<Object, List<TimeGraphEntry>> workerEntries = new HashMap<>();
 200         private Map<Object, List<ILinkEvent>> linkMap = new HashMap<>();
 201         private @Nullable Object fCurrentObject;
 202
 203         @Override
 204         public ITimeGraphEntry[] getElements(@Nullable Object inputElement) {
 205             ITimeGraphEntry[] ret = new ITimeGraphEntry[0];
 206             if (inputElement instanceof List) {
 207                 List<?> list = (List<?>) inputElement;
 208                 if (!list.isEmpty()) {
 209                     Object first = list.get(0);
 210                     if (first instanceof CriticalPathBaseEntry) {
 211                         IGraphWorker worker = ((CriticalPathBaseEntry) first).getWorker();
 212                         ret = getWorkerEntries(worker);
 213                     }
 214                 }
 215             }
 216             return ret;
 217         }
 218
 219         private ITimeGraphEntry[] getWorkerEntries(IGraphWorker worker) {
 220             fCurrentObject = worker;
 221             List<TimeGraphEntry> entries = workerEntries.get(worker);
 222             if (entries == null) {
 223                 buildEntryList(worker);
 224                 entries = workerEntries.get(worker);
 225             }
 226
 227             return (entries == null) ?
 228                 new ITimeGraphEntry[0] :
 229                 entries.toArray(new @NonNull ITimeGraphEntry[entries.size()]);
 230         }
 231
 232         private void buildEntryList(IGraphWorker worker) {
 233             final ITmfTrace trace = getTrace();
 234             if (trace == null) {
 235                 return;
 236             }
 237             final TmfGraph graph = getGraph(trace);
 238             if (graph == null) {
 239                 return;
 240             }
 241             setStartTime(Long.MAX_VALUE);
 242             setEndTime(Long.MIN_VALUE);
 243
 244             final HashMap<Object, CriticalPathEntry> rootList = new HashMap<>();
 245             fLinks.remove(trace, worker);
 246
 247             TmfVertex vertex = graph.getHead();
 248
 249             /* Calculate statistics */
 250             fStats = new TmfGraphStatistics();
 251             fStats.computeGraphStatistics(graph, worker);
 252             fObjectStatistics.put(trace, worker, fStats);
 253
 254             // Hosts entries are parent of each worker entries
 255             final Map<String, CriticalPathEntry> hostEntries = new HashMap<>();
 256
 257             /* create all interval entries and horizontal links */
 258
 259             final CriticalPathEntry defaultParent = new CriticalPathEntry("default", trace, getStartTime(), getEndTime(), DEFAULT_WORKER); //$NON-NLS-1$
 260             graph.scanLineTraverse(vertex, new HorizontalLinksVisitor(defaultParent, hostEntries, graph, trace, rootList));
 261
 262             workerMaps.put(worker, rootList);
 263
 264             List<TimeGraphEntry> list = new ArrayList<>();
 265             list.addAll(hostEntries.values());
 266             if (defaultParent.hasChildren()) {
 267                 list.add(defaultParent);
 268             }
 269
 270             workerEntries.put(worker, list);
 271         }
 272
 273         private @Nullable TmfGraph getGraph(final ITmfTrace trace) {
 274             CriticalPathModule module = Iterables.<@Nullable CriticalPathModule> getFirst(
 275                     TmfTraceUtils.getAnalysisModulesOfClass(trace, CriticalPathModule.class),
 276                     null);
 277             if (module == null) {
 278                 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
 279             }
 280
 281             module.schedule();
 282             if (!module.waitForCompletion()) {
 283                 return null;
 284             }
 285             final TmfGraph graph = module.getCriticalPath();
 286             return graph;
 287         }
 288
 289         public @Nullable List<ILinkEvent> getLinkList(long startTime, long endTime) {
 290             Object current = fCurrentObject;
 291             if (current == null) {
 292                 return null;
 293             }
 294             /*
 295              * Critical path typically has relatively few links, so we calculate
 296              * and save them all, but just return those in range
 297              */
 298             List<ILinkEvent> links = linkMap.get(current);
 299             if (links != null) {
 300                 return links;
 301             }
 302             final ITmfTrace trace = getTrace();
 303             if (trace == null) {
 304                 return null;
 305             }
 306             CriticalPathModule module = Iterables.<@Nullable CriticalPathModule> getFirst(
 307                     TmfTraceUtils.getAnalysisModulesOfClass(trace, CriticalPathModule.class), null);
 308             if (module == null) {
 309                 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
 310             }
 311
 312             final TmfGraph graph = module.getCriticalPath();
 313             if (graph == null) {
 314                 return null;
 315             }
 316             final Map<Object, CriticalPathEntry> entryMap = workerMaps.get(current);
 317             if (entryMap == null) {
 318                 return null;
 319             }
 320
 321             TmfVertex vertex = graph.getHead();
 322
 323             final List<ILinkEvent> graphLinks = new ArrayList<>();
 324
 325             /* find vertical links */
 326             graph.scanLineTraverse(vertex, new VerticalLinksVisitor(graph, graphLinks, entryMap));
 327             fLinks.put(trace, checkNotNull(fCurrentObject), graphLinks);
 328             links = graphLinks;
 329
 330             List<ILinkEvent> linksInRange = new ArrayList<>();
 331             for (ILinkEvent link : links) {
 332                 if (((link.getTime() >= startTime) && (link.getTime() <= endTime)) ||
 333                         ((link.getTime() + link.getDuration() >= startTime) && (link.getTime() + link.getDuration() <= endTime))) {
 334                     linksInRange.add(link);
 335                 }
 336             }
 337             return linksInRange;
 338         }
 339
 340         @Override
 341         public void dispose() {
 342
 343         }
 344
 345         @Override
 346         public void inputChanged(@Nullable Viewer viewer, @Nullable Object oldInput, @Nullable Object newInput) {
 347         }
 348
 349         @Override
 350         public ITimeGraphEntry @Nullable [] getChildren(@Nullable Object parentElement) {
 351             if (parentElement instanceof CriticalPathEntry) {
 352                 List<? extends ITimeGraphEntry> children = ((CriticalPathEntry) parentElement).getChildren();
 353                 return children.toArray(new TimeGraphEntry[children.size()]);
 354             }
 355             return null;
 356         }
 357
 358         @Override
 359         public @Nullable ITimeGraphEntry getParent(@Nullable Object element) {
 360             if (element instanceof CriticalPathEntry) {
 361                 return ((CriticalPathEntry) element).getParent();
 362             }
 363             return null;
 364         }
 365
 366         @Override
 367         public boolean hasChildren(@Nullable Object element) {
 368             if (element instanceof CriticalPathEntry) {
 369                 return ((CriticalPathEntry) element).hasChildren();
 370             }
 371             return false;
 372         }
 373
 374     }
 375
 376     private class CriticalPathTreeLabelProvider extends TreeLabelProvider {
 377
 378         @Override
 379         public String getColumnText(@Nullable Object element, int columnIndex) {
 380             if (element == null) {
 381                 return ""; //$NON-NLS-1$
 382             }
 383             CriticalPathEntry entry = (CriticalPathEntry) element;
 384             if (columnIndex == 0) {
 385                 return NonNullUtils.nullToEmptyString(entry.getName());
 386             } else if (columnIndex == 1) {
 387                 Long sum = fStats.getSum(entry.getWorker());
 388                 String value = String.format("%.9f", sum * NANOINV); //$NON-NLS-1$
 389                 return NonNullUtils.nullToEmptyString(value);
 390             } else if (columnIndex == 2) {
 391                 Double percent = fStats.getPercent(entry.getWorker());
 392                 String value = String.format("%.2f", percent * 100); //$NON-NLS-1$
 393                 return NonNullUtils.nullToEmptyString(value);
 394             }
 395             return ""; //$NON-NLS-1$
 396         }
 397
 398     }
 399
 400     private class CriticalPathEntryComparator implements Comparator<ITimeGraphEntry> {
 401
 402         @Override
 403         public int compare(@Nullable ITimeGraphEntry o1, @Nullable ITimeGraphEntry o2) {
 404
 405             int result = 0;
 406
 407             if ((o1 instanceof CriticalPathEntry) && (o2 instanceof CriticalPathEntry)) {
 408                 CriticalPathEntry entry1 = (CriticalPathEntry) o1;
 409                 CriticalPathEntry entry2 = (CriticalPathEntry) o2;
 410                 result = -1 * fStats.getSum(entry1.getWorker()).compareTo(fStats.getSum(entry2.getWorker()));
 411             }
 412             return result;
 413         }
 414     }
 415
 416     /**
 417      * Constructor
 418      */
 419     public CriticalPathView() {
 420         super(ID, new CriticalPathPresentationProvider());
 421         setTreeColumns(COLUMN_NAMES);
 422         setFilterColumns(FILTER_COLUMN_NAMES);
 423         setTreeLabelProvider(new CriticalPathTreeLabelProvider());
 424         setTimeGraphContentProvider(fContentProvider);
 425         setEntryComparator(new CriticalPathEntryComparator());
 426     }
 427
 428     // ------------------------------------------------------------------------
 429     // Internal
 430     // ------------------------------------------------------------------------
 431
 432     private static State getMatchingState(EdgeType type) {
 433         State state = State.UNKNOWN;
 434         switch (type) {
 435         case RUNNING:
 436             state = State.RUNNING;
 437             break;
 438         case PREEMPTED:
 439             state = State.PREEMPTED;
 440             break;
 441         case TIMER:
 442             state = State.TIMER;
 443             break;
 444         case BLOCK_DEVICE:
 445             state = State.BLOCK_DEVICE;
 446             break;
 447         case INTERRUPTED:
 448             state = State.INTERRUPTED;
 449             break;
 450         case NETWORK:
 451             state = State.NETWORK;
 452             break;
 453         case USER_INPUT:
 454             state = State.USER_INPUT;
 455             break;
 456         case IPI:
 457             state = State.IPI;
 458             break;
 459         case EPS:
 460         case UNKNOWN:
 461         case DEFAULT:
 462         case BLOCKED:
 463             break;
 464         default:
 465             break;
 466         }
 467         return state;
 468     }
 469
 470     @Override
 471     protected void buildEntryList(@NonNull ITmfTrace trace, @NonNull ITmfTrace parentTrace, @NonNull IProgressMonitor monitor) {
 472         /* This class uses a content provider instead */
 473     }
 474
 475     @Override
 476     protected @Nullable List<ITimeEvent> getEventList(TimeGraphEntry entry,
 477             long startTime, long endTime, long resolution,
 478             IProgressMonitor monitor) {
 479         /*
 480          * The event list is built in the HorizontalLinksVisitor. This is called
 481          * only from the zoom thread and only for the CriticalPathBaseEntry.
 482          */
 483         return null;
 484     }
 485
 486     @Override
 487     protected @Nullable List<ILinkEvent> getLinkList(long startTime, long endTime, long resolution, IProgressMonitor monitor) {
 488         return fContentProvider.getLinkList(startTime, endTime);
 489     }
 490
 491     /**
 492      * Signal handler for analysis started
 493      *
 494      * @param signal
 495      *            The signal
 496      */
 497     @TmfSignalHandler
 498     public void analysisStarted(TmfStartAnalysisSignal signal) {
 499         if (!(signal.getAnalysisModule() instanceof CriticalPathModule)) {
 500             return;
 501         }
 502         CriticalPathModule module = (CriticalPathModule) signal.getAnalysisModule();
 503         Object obj = module.getParameter(CriticalPathModule.PARAM_WORKER);
 504         if (obj == null) {
 505             return;
 506         }
 507         if (!(obj instanceof IGraphWorker)) {
 508             throw new IllegalStateException("Wrong type for critical path module parameter " + //$NON-NLS-1$
 509                     CriticalPathModule.PARAM_WORKER +
 510                     " expected IGraphWorker got " + //$NON-NLS-1$
 511                     obj.getClass().getSimpleName());
 512         }
 513         ITmfTrace trace = getTrace();
 514         if (trace == null) {
 515             throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
 516         }
 517         IGraphWorker worker = (IGraphWorker) obj;
 518         TmfGraphStatistics stats = fObjectStatistics.get(trace, worker);
 519         if (stats == null) {
 520             stats = new TmfGraphStatistics();
 521             fObjectStatistics.put(trace, worker, stats);
 522         }
 523         fStats = stats;
 524
 525         TimeGraphEntry tge = new CriticalPathBaseEntry(worker);
 526         List<TimeGraphEntry> list = Collections.singletonList(tge);
 527         putEntryList(trace, list);
 528         refresh();
 529     }
 530
 531 }