1 /*******************************************************************************
2 * Copyright (c) 2015, 2016 École Polytechnique de Montréal
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 *******************************************************************************/
10 package org
.eclipse
.tracecompass
.internal
.analysis
.graph
.ui
.criticalpath
.view
;
12 import static org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
.checkNotNull
;
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
;
20 import java
.util
.concurrent
.locks
.Lock
;
21 import java
.util
.concurrent
.locks
.ReentrantLock
;
23 import org
.eclipse
.core
.runtime
.IProgressMonitor
;
24 import org
.eclipse
.core
.runtime
.NullProgressMonitor
;
25 import org
.eclipse
.jdt
.annotation
.NonNull
;
26 import org
.eclipse
.jdt
.annotation
.Nullable
;
27 import org
.eclipse
.jface
.viewers
.Viewer
;
28 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.IGraphWorker
;
29 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
;
30 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfEdge
.EdgeType
;
31 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfGraph
;
32 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.base
.TmfVertex
;
33 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.building
.TmfGraphBuilderModule
;
34 import org
.eclipse
.tracecompass
.analysis
.graph
.core
.criticalpath
.CriticalPathModule
;
35 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
36 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.base
.TmfGraphStatistics
;
37 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.base
.TmfGraphVisitor
;
38 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.ui
.criticalpath
.view
.CriticalPathPresentationProvider
.State
;
39 import org
.eclipse
.tracecompass
.tmf
.core
.signal
.TmfSignalHandler
;
40 import org
.eclipse
.tracecompass
.tmf
.core
.signal
.TmfStartAnalysisSignal
;
41 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.ITmfTrace
;
42 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.TmfTraceUtils
;
43 import org
.eclipse
.tracecompass
.tmf
.ui
.views
.timegraph
.AbstractTimeGraphView
;
44 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.ITimeGraphContentProvider
;
45 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ILinkEvent
;
46 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ITimeEvent
;
47 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ITimeGraphEntry
;
48 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeEvent
;
49 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeGraphEntry
;
50 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeLinkEvent
;
52 import com
.google
.common
.collect
.HashBasedTable
;
53 import com
.google
.common
.collect
.Iterables
;
54 import com
.google
.common
.collect
.Table
;
57 * The Critical Path view
59 * @author Geneviève Bastien
60 * @author Francis Giraldeau
62 public class CriticalPathView
extends AbstractTimeGraphView
{
64 // ------------------------------------------------------------------------
66 // ------------------------------------------------------------------------
69 public static final String ID
= "org.eclipse.linuxtools.tmf.analysis.graph.ui.criticalpath.view.criticalpathview"; //$NON-NLS-1$
71 private static final double NANOINV
= 0.000000001;
73 private static final String COLUMN_PROCESS
= Messages
.getMessage(Messages
.CriticalFlowView_columnProcess
);
74 private static final String COLUMN_ELAPSED
= Messages
.getMessage(Messages
.CriticalFlowView_columnElapsed
);
75 private static final String COLUMN_PERCENT
= Messages
.getMessage(Messages
.CriticalFlowView_columnPercent
);
77 private static final String
[] COLUMN_NAMES
= new String
[] {
83 private static final String
[] FILTER_COLUMN_NAMES
= new String
[] {
87 private final Table
<ITmfTrace
, Object
, List
<ILinkEvent
>> fLinks
= HashBasedTable
.create();
88 /** The trace to entry list hash map */
89 private final Table
<ITmfTrace
, Object
, TmfGraphStatistics
> fObjectStatistics
= HashBasedTable
.create();
91 private final CriticalPathContentProvider fContentProvider
= new CriticalPathContentProvider();
93 private TmfGraphStatistics fStats
= new TmfGraphStatistics();
95 private static final IGraphWorker DEFAULT_WORKER
= new IGraphWorker() {
97 public String
getHostId() {
98 return "default"; //$NON-NLS-1$
102 private class CriticalPathContentProvider
implements ITimeGraphContentProvider
{
104 private final class HorizontalLinksVisitor
extends TmfGraphVisitor
{
105 private final CriticalPathEntry fDefaultParent
;
106 private final Map
<String
, CriticalPathEntry
> fHostEntries
;
107 private final TmfGraph fGraph
;
108 private final ITmfTrace fTrace
;
109 private final HashMap
<Object
, CriticalPathEntry
> fRootList
;
111 private HorizontalLinksVisitor(CriticalPathEntry defaultParent
, Map
<String
, CriticalPathEntry
> hostEntries
, TmfGraph graph
, ITmfTrace trace
, HashMap
<Object
, CriticalPathEntry
> rootList
) {
112 fDefaultParent
= defaultParent
;
113 fHostEntries
= hostEntries
;
116 fRootList
= rootList
;
120 public void visitHead(TmfVertex node
) {
121 /* TODO possible null pointer ? */
122 IGraphWorker owner
= fGraph
.getParentOf(node
);
126 if (fRootList
.containsKey(owner
)) {
129 TmfVertex first
= fGraph
.getHead(owner
);
130 TmfVertex last
= fGraph
.getTail(owner
);
131 if (first
== null || last
== null) {
134 setStartTime(Math
.min(getStartTime(), first
.getTs()));
135 setEndTime(Math
.max(getEndTime(), last
.getTs()));
137 CriticalPathEntry parent
= fDefaultParent
;
138 String host
= owner
.getHostId();
139 if (!fHostEntries
.containsKey(host
)) {
140 fHostEntries
.put(host
, new CriticalPathEntry(host
, fTrace
, getStartTime(), getEndTime(), owner
));
142 parent
= checkNotNull(fHostEntries
.get(host
));
143 CriticalPathEntry entry
= new CriticalPathEntry(NonNullUtils
.nullToEmptyString(owner
), fTrace
, getStartTime(), getEndTime(), owner
);
144 parent
.addChild(entry
);
146 fRootList
.put(owner
, entry
);
150 public void visit(TmfEdge link
, boolean horizontal
) {
152 Object parent
= fGraph
.getParentOf(link
.getVertexFrom());
153 CriticalPathEntry entry
= fRootList
.get(parent
);
154 TimeEvent ev
= new TimeEvent(entry
, link
.getVertexFrom().getTs(), link
.getDuration(),
155 getMatchingState(link
.getType()).ordinal());
161 private final class VerticalLinksVisitor
extends TmfGraphVisitor
{
162 private final TmfGraph fGraph
;
163 private final List
<ILinkEvent
> fGraphLinks
;
164 private final Map
<Object
, CriticalPathEntry
> fEntryMap
;
166 private VerticalLinksVisitor(TmfGraph graph
, List
<ILinkEvent
> graphLinks
, Map
<Object
, CriticalPathEntry
> entryMap
) {
168 fGraphLinks
= graphLinks
;
169 fEntryMap
= entryMap
;
173 public void visitHead(TmfVertex node
) {
178 public void visit(TmfVertex node
) {
183 public void visit(TmfEdge link
, boolean horizontal
) {
185 Object parentFrom
= fGraph
.getParentOf(link
.getVertexFrom());
186 Object parentTo
= fGraph
.getParentOf(link
.getVertexTo());
187 CriticalPathEntry entryFrom
= fEntryMap
.get(parentFrom
);
188 CriticalPathEntry entryTo
= fEntryMap
.get(parentTo
);
189 TimeLinkEvent lk
= new TimeLinkEvent(entryFrom
, entryTo
, link
.getVertexFrom().getTs(),
190 link
.getVertexTo().getTs() - link
.getVertexFrom().getTs(), getMatchingState(link
.getType()).ordinal());
196 private class BuildThread
extends Thread
{
197 private final ITmfTrace fBuildTrace
;
198 private final IProgressMonitor fMonitor
;
200 public BuildThread(final ITmfTrace trace
) {
201 super("Critical path view build"); //$NON-NLS-1$
203 fMonitor
= new NullProgressMonitor();
209 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
210 TmfTraceUtils
.getAnalysisModulesOfClass(fBuildTrace
, CriticalPathModule
.class),
212 if (module
== null) {
216 if (module
.waitForCompletion(fMonitor
)) {
217 // Module is completed, set the start and end time of
219 setStartEndTime(module
);
230 public void cancel() {
231 fMonitor
.setCanceled(true);
235 private final Lock fSyncLock
= new ReentrantLock();
236 private final Map
<Object
, Map
<Object
, CriticalPathEntry
>> workerMaps
= new HashMap
<>();
237 private final Map
<Object
, List
<TimeGraphEntry
>> workerEntries
= new HashMap
<>();
238 private final Map
<Object
, List
<ILinkEvent
>> linkMap
= new HashMap
<>();
239 private @Nullable Object fCurrentObject
;
240 private @Nullable BuildThread fBuildThread
= null;
243 public ITimeGraphEntry
[] getElements(@Nullable Object inputElement
) {
244 ITimeGraphEntry
[] ret
= new ITimeGraphEntry
[0];
245 if (inputElement
instanceof List
) {
246 List
<?
> list
= (List
<?
>) inputElement
;
247 if (!list
.isEmpty()) {
248 Object first
= list
.get(0);
249 if (first
instanceof CriticalPathBaseEntry
) {
250 IGraphWorker worker
= ((CriticalPathBaseEntry
) first
).getWorker();
251 ret
= getWorkerEntries(worker
);
258 private ITimeGraphEntry
[] getWorkerEntries(IGraphWorker worker
) {
259 fCurrentObject
= worker
;
260 List
<TimeGraphEntry
> entries
= workerEntries
.get(worker
);
261 ITmfTrace trace
= getTrace();
262 if (entries
== null) {
263 buildEntryList(worker
);
264 entries
= workerEntries
.get(worker
);
265 } else if (trace
!= null) {
266 // Get the statistics object for this worker
267 TmfGraphStatistics stats
= fObjectStatistics
.get(trace
, worker
);
269 stats
= new TmfGraphStatistics();
274 return (entries
== null) ?
275 new ITimeGraphEntry
[0] :
276 entries
.toArray(new @NonNull ITimeGraphEntry
[entries
.size()]);
279 private void buildEntryList(IGraphWorker worker
) {
280 final ITmfTrace trace
= getTrace();
284 final TmfGraph graph
= getGraph(trace
);
289 final HashMap
<Object
, CriticalPathEntry
> rootList
= new HashMap
<>();
290 fLinks
.remove(trace
, worker
);
292 TmfVertex vertex
= graph
.getHead();
294 /* Calculate statistics */
295 fStats
= new TmfGraphStatistics();
296 fStats
.computeGraphStatistics(graph
, worker
);
297 fObjectStatistics
.put(trace
, worker
, fStats
);
299 // Hosts entries are parent of each worker entries
300 final Map
<String
, CriticalPathEntry
> hostEntries
= new HashMap
<>();
302 /* create all interval entries and horizontal links */
304 final CriticalPathEntry defaultParent
= new CriticalPathEntry("default", trace
, getStartTime(), getEndTime(), DEFAULT_WORKER
); //$NON-NLS-1$
305 graph
.scanLineTraverse(vertex
, new HorizontalLinksVisitor(defaultParent
, hostEntries
, graph
, trace
, rootList
));
307 workerMaps
.put(worker
, rootList
);
309 List
<TimeGraphEntry
> list
= new ArrayList
<>();
310 list
.addAll(hostEntries
.values());
311 if (defaultParent
.hasChildren()) {
312 list
.add(defaultParent
);
315 workerEntries
.put(worker
, list
);
318 private @Nullable TmfGraph
getGraph(final ITmfTrace trace
) {
319 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
320 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class),
322 if (module
== null) {
323 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
326 final TmfGraph graph
= module
.getCriticalPath();
330 public @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
) {
331 Object current
= fCurrentObject
;
332 if (current
== null) {
336 * Critical path typically has relatively few links, so we calculate
337 * and save them all, but just return those in range
339 List
<ILinkEvent
> links
= linkMap
.get(current
);
343 final ITmfTrace trace
= getTrace();
347 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
348 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class), null);
349 if (module
== null) {
350 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
353 final TmfGraph graph
= module
.getCriticalPath();
357 final Map
<Object
, CriticalPathEntry
> entryMap
= workerMaps
.get(current
);
358 if (entryMap
== null) {
362 TmfVertex vertex
= graph
.getHead();
364 final List
<ILinkEvent
> graphLinks
= new ArrayList
<>();
366 /* find vertical links */
367 graph
.scanLineTraverse(vertex
, new VerticalLinksVisitor(graph
, graphLinks
, entryMap
));
368 fLinks
.put(trace
, checkNotNull(fCurrentObject
), graphLinks
);
371 List
<ILinkEvent
> linksInRange
= new ArrayList
<>();
372 for (ILinkEvent link
: links
) {
373 if (((link
.getTime() >= startTime
) && (link
.getTime() <= endTime
)) ||
374 ((link
.getTime() + link
.getDuration() >= startTime
) && (link
.getTime() + link
.getDuration() <= endTime
))) {
375 linksInRange
.add(link
);
382 public void dispose() {
385 BuildThread buildThread
= fBuildThread
;
386 if (buildThread
!= null) {
387 buildThread
.cancel();
395 public void inputChanged(@Nullable Viewer viewer
, @Nullable Object oldInput
, @Nullable Object newInput
) {
396 // The input has changed, the critical path will be re-computed,
397 // wait for the analysis to be finished, then call the refresh
398 // method of the view
399 if (!(newInput
instanceof List
)) {
402 List
<?
> list
= (List
<?
>) newInput
;
403 if (list
.isEmpty()) {
406 final ITmfTrace trace
= getTrace();
413 BuildThread buildThread
= fBuildThread
;
414 if (buildThread
!= null) {
415 buildThread
.cancel();
417 buildThread
= new BuildThread(trace
);
419 fBuildThread
= buildThread
;
426 public ITimeGraphEntry
@Nullable [] getChildren(@Nullable Object parentElement
) {
427 if (parentElement
instanceof CriticalPathEntry
) {
428 List
<?
extends ITimeGraphEntry
> children
= ((CriticalPathEntry
) parentElement
).getChildren();
429 return children
.toArray(new TimeGraphEntry
[children
.size()]);
435 public @Nullable ITimeGraphEntry
getParent(@Nullable Object element
) {
436 if (element
instanceof CriticalPathEntry
) {
437 return ((CriticalPathEntry
) element
).getParent();
443 public boolean hasChildren(@Nullable Object element
) {
444 if (element
instanceof CriticalPathEntry
) {
445 return ((CriticalPathEntry
) element
).hasChildren();
452 private class CriticalPathTreeLabelProvider
extends TreeLabelProvider
{
455 public String
getColumnText(@Nullable Object element
, int columnIndex
) {
456 if (element
== null) {
457 return ""; //$NON-NLS-1$
459 CriticalPathEntry entry
= (CriticalPathEntry
) element
;
460 if (columnIndex
== 0) {
461 return NonNullUtils
.nullToEmptyString(entry
.getName());
462 } else if (columnIndex
== 1) {
463 Long sum
= fStats
.getSum(entry
.getWorker());
464 String value
= String
.format("%.9f", sum
* NANOINV
); //$NON-NLS-1$
465 return NonNullUtils
.nullToEmptyString(value
);
466 } else if (columnIndex
== 2) {
467 Double percent
= fStats
.getPercent(entry
.getWorker());
468 String value
= String
.format("%.2f", percent
* 100); //$NON-NLS-1$
469 return NonNullUtils
.nullToEmptyString(value
);
471 return ""; //$NON-NLS-1$
476 private class CriticalPathEntryComparator
implements Comparator
<ITimeGraphEntry
> {
479 public int compare(@Nullable ITimeGraphEntry o1
, @Nullable ITimeGraphEntry o2
) {
483 if ((o1
instanceof CriticalPathEntry
) && (o2
instanceof CriticalPathEntry
)) {
484 CriticalPathEntry entry1
= (CriticalPathEntry
) o1
;
485 CriticalPathEntry entry2
= (CriticalPathEntry
) o2
;
486 result
= -1 * fStats
.getSum(entry1
.getWorker()).compareTo(fStats
.getSum(entry2
.getWorker()));
495 public CriticalPathView() {
496 super(ID
, new CriticalPathPresentationProvider());
497 setTreeColumns(COLUMN_NAMES
);
498 setFilterColumns(FILTER_COLUMN_NAMES
);
499 setTreeLabelProvider(new CriticalPathTreeLabelProvider());
500 setTimeGraphContentProvider(fContentProvider
);
501 setEntryComparator(new CriticalPathEntryComparator());
504 // ------------------------------------------------------------------------
506 // ------------------------------------------------------------------------
508 private static State
getMatchingState(EdgeType type
) {
509 State state
= State
.UNKNOWN
;
512 state
= State
.RUNNING
;
515 state
= State
.PREEMPTED
;
521 state
= State
.BLOCK_DEVICE
;
524 state
= State
.INTERRUPTED
;
527 state
= State
.NETWORK
;
530 state
= State
.USER_INPUT
;
547 protected void buildEntryList(@NonNull ITmfTrace trace
, @NonNull ITmfTrace parentTrace
, @NonNull IProgressMonitor monitor
) {
548 /* This class uses a content provider instead */
552 protected @Nullable List
<ITimeEvent
> getEventList(TimeGraphEntry entry
,
553 long startTime
, long endTime
, long resolution
,
554 IProgressMonitor monitor
) {
556 * The event list is built in the HorizontalLinksVisitor. This is called
557 * only from the zoom thread and only for the CriticalPathBaseEntry.
563 protected @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
, long resolution
, IProgressMonitor monitor
) {
564 return fContentProvider
.getLinkList(startTime
, endTime
);
568 * Signal handler for analysis started
574 public void analysisStarted(TmfStartAnalysisSignal signal
) {
575 if (!(signal
.getAnalysisModule() instanceof CriticalPathModule
)) {
578 CriticalPathModule module
= (CriticalPathModule
) signal
.getAnalysisModule();
579 Object obj
= module
.getParameter(CriticalPathModule
.PARAM_WORKER
);
583 if (!(obj
instanceof IGraphWorker
)) {
584 throw new IllegalStateException("Wrong type for critical path module parameter " + //$NON-NLS-1$
585 CriticalPathModule
.PARAM_WORKER
+
586 " expected IGraphWorker got " + //$NON-NLS-1$
587 obj
.getClass().getSimpleName());
589 ITmfTrace trace
= getTrace();
591 throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
593 IGraphWorker worker
= (IGraphWorker
) obj
;
595 TimeGraphEntry tge
= new CriticalPathBaseEntry(worker
);
596 List
<TimeGraphEntry
> list
= Collections
.singletonList(tge
);
597 putEntryList(trace
, list
);
601 private void setStartEndTime(CriticalPathModule module
) {
602 // Initialize the start/end time of the view to trace's times
603 ITmfTrace trace
= getTrace();
605 throw new IllegalStateException("The trace should not be null when we have a critical path to display"); //$NON-NLS-1$
607 long start
= trace
.getStartTime().toNanos();
608 long end
= trace
.getEndTime().toNanos();
610 // Set the start/end time of the view
611 Object paramGraph
= module
.getParameter(CriticalPathModule
.PARAM_GRAPH
);
612 if (paramGraph
instanceof TmfGraphBuilderModule
) {
613 TmfGraphBuilderModule graphModule
= (TmfGraphBuilderModule
) paramGraph
;
614 TmfGraph graph
= graphModule
.getGraph();
618 TmfVertex head
= graph
.getHead();
620 start
= Math
.min(start
, head
.getTs());
621 for (IGraphWorker w
: graph
.getWorkers()) {
622 TmfVertex tail
= graph
.getTail(w
);
624 end
= Math
.max(end
, tail
.getTs());