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

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