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
.criticalpath
.CriticalPathModule
;
34 import org
.eclipse
.tracecompass
.common
.core
.NonNullUtils
;
35 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.base
.TmfGraphStatistics
;
36 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.core
.base
.TmfGraphVisitor
;
37 import org
.eclipse
.tracecompass
.internal
.analysis
.graph
.ui
.criticalpath
.view
.CriticalPathPresentationProvider
.State
;
38 import org
.eclipse
.tracecompass
.tmf
.core
.signal
.TmfSignalHandler
;
39 import org
.eclipse
.tracecompass
.tmf
.core
.signal
.TmfStartAnalysisSignal
;
40 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.ITmfTrace
;
41 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.TmfTraceUtils
;
42 import org
.eclipse
.tracecompass
.tmf
.ui
.views
.timegraph
.AbstractTimeGraphView
;
43 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.ITimeGraphContentProvider
;
44 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ILinkEvent
;
45 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ITimeEvent
;
46 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.ITimeGraphEntry
;
47 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeEvent
;
48 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeGraphEntry
;
49 import org
.eclipse
.tracecompass
.tmf
.ui
.widgets
.timegraph
.model
.TimeLinkEvent
;
51 import com
.google
.common
.collect
.HashBasedTable
;
52 import com
.google
.common
.collect
.Iterables
;
53 import com
.google
.common
.collect
.Table
;
56 * The Critical Path view
58 * @author Geneviève Bastien
59 * @author Francis Giraldeau
61 public class CriticalPathView
extends AbstractTimeGraphView
{
63 // ------------------------------------------------------------------------
65 // ------------------------------------------------------------------------
68 public static final String ID
= "org.eclipse.linuxtools.tmf.analysis.graph.ui.criticalpath.view.criticalpathview"; //$NON-NLS-1$
70 private static final double NANOINV
= 0.000000001;
72 private static final String COLUMN_PROCESS
= Messages
.getMessage(Messages
.CriticalFlowView_columnProcess
);
73 private static final String COLUMN_ELAPSED
= Messages
.getMessage(Messages
.CriticalFlowView_columnElapsed
);
74 private static final String COLUMN_PERCENT
= Messages
.getMessage(Messages
.CriticalFlowView_columnPercent
);
76 private static final String
[] COLUMN_NAMES
= new String
[] {
82 private static final String
[] FILTER_COLUMN_NAMES
= new String
[] {
86 private final Table
<ITmfTrace
, Object
, List
<ILinkEvent
>> fLinks
= HashBasedTable
.create();
87 /** The trace to entry list hash map */
88 private final Table
<ITmfTrace
, Object
, TmfGraphStatistics
> fObjectStatistics
= HashBasedTable
.create();
90 private final CriticalPathContentProvider fContentProvider
= new CriticalPathContentProvider();
92 private TmfGraphStatistics fStats
= new TmfGraphStatistics();
94 private static final IGraphWorker DEFAULT_WORKER
= new IGraphWorker() {
96 public String
getHostId() {
97 return "default"; //$NON-NLS-1$
101 private class CriticalPathContentProvider
implements ITimeGraphContentProvider
{
103 private final class HorizontalLinksVisitor
extends TmfGraphVisitor
{
104 private final CriticalPathEntry fDefaultParent
;
105 private final Map
<String
, CriticalPathEntry
> fHostEntries
;
106 private final TmfGraph fGraph
;
107 private final ITmfTrace fTrace
;
108 private final HashMap
<Object
, CriticalPathEntry
> fRootList
;
110 private HorizontalLinksVisitor(CriticalPathEntry defaultParent
, Map
<String
, CriticalPathEntry
> hostEntries
, TmfGraph graph
, ITmfTrace trace
, HashMap
<Object
, CriticalPathEntry
> rootList
) {
111 fDefaultParent
= defaultParent
;
112 fHostEntries
= hostEntries
;
115 fRootList
= rootList
;
119 public void visitHead(TmfVertex node
) {
120 /* TODO possible null pointer ? */
121 IGraphWorker owner
= fGraph
.getParentOf(node
);
125 if (fRootList
.containsKey(owner
)) {
128 TmfVertex first
= fGraph
.getHead(owner
);
129 TmfVertex last
= fGraph
.getTail(owner
);
130 if (first
== null || last
== null) {
133 setStartTime(Math
.min(getStartTime(), first
.getTs()));
134 setEndTime(Math
.max(getEndTime(), last
.getTs()));
136 CriticalPathEntry parent
= fDefaultParent
;
137 String host
= owner
.getHostId();
138 if (!fHostEntries
.containsKey(host
)) {
139 fHostEntries
.put(host
, new CriticalPathEntry(host
, fTrace
, getStartTime(), getEndTime(), owner
));
141 parent
= checkNotNull(fHostEntries
.get(host
));
142 CriticalPathEntry entry
= new CriticalPathEntry(NonNullUtils
.nullToEmptyString(owner
), fTrace
, getStartTime(), getEndTime(), owner
);
143 parent
.addChild(entry
);
145 fRootList
.put(owner
, entry
);
149 public void visit(TmfVertex node
) {
150 setStartTime(Math
.min(getStartTime(), node
.getTs()));
151 setEndTime(Math
.max(getEndTime(), node
.getTs()));
155 public void visit(TmfEdge link
, boolean horizontal
) {
157 Object parent
= fGraph
.getParentOf(link
.getVertexFrom());
158 CriticalPathEntry entry
= fRootList
.get(parent
);
159 TimeEvent ev
= new TimeEvent(entry
, link
.getVertexFrom().getTs(), link
.getDuration(),
160 getMatchingState(link
.getType()).ordinal());
166 private final class VerticalLinksVisitor
extends TmfGraphVisitor
{
167 private final TmfGraph fGraph
;
168 private final List
<ILinkEvent
> fGraphLinks
;
169 private final Map
<Object
, CriticalPathEntry
> fEntryMap
;
171 private VerticalLinksVisitor(TmfGraph graph
, List
<ILinkEvent
> graphLinks
, Map
<Object
, CriticalPathEntry
> entryMap
) {
173 fGraphLinks
= graphLinks
;
174 fEntryMap
= entryMap
;
178 public void visitHead(TmfVertex node
) {
183 public void visit(TmfVertex node
) {
188 public void visit(TmfEdge link
, boolean horizontal
) {
190 Object parentFrom
= fGraph
.getParentOf(link
.getVertexFrom());
191 Object parentTo
= fGraph
.getParentOf(link
.getVertexTo());
192 CriticalPathEntry entryFrom
= fEntryMap
.get(parentFrom
);
193 CriticalPathEntry entryTo
= fEntryMap
.get(parentTo
);
194 TimeLinkEvent lk
= new TimeLinkEvent(entryFrom
, entryTo
, link
.getVertexFrom().getTs(),
195 link
.getVertexTo().getTs() - link
.getVertexFrom().getTs(), getMatchingState(link
.getType()).ordinal());
201 private class BuildThread
extends Thread
{
202 private final ITmfTrace fBuildTrace
;
203 private final IProgressMonitor fMonitor
;
205 public BuildThread(final ITmfTrace trace
) {
206 super("Critical path view build"); //$NON-NLS-1$
208 fMonitor
= new NullProgressMonitor();
214 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
215 TmfTraceUtils
.getAnalysisModulesOfClass(fBuildTrace
, CriticalPathModule
.class),
217 if (module
== null) {
221 if (module
.waitForCompletion(fMonitor
)) {
232 public void cancel() {
233 fMonitor
.setCanceled(true);
237 private final Lock fSyncLock
= new ReentrantLock();
238 private final Map
<Object
, Map
<Object
, CriticalPathEntry
>> workerMaps
= new HashMap
<>();
239 private final Map
<Object
, List
<TimeGraphEntry
>> workerEntries
= new HashMap
<>();
240 private final Map
<Object
, List
<ILinkEvent
>> linkMap
= new HashMap
<>();
241 private @Nullable Object fCurrentObject
;
242 private @Nullable BuildThread fBuildThread
= null;
245 public ITimeGraphEntry
[] getElements(@Nullable Object inputElement
) {
246 ITimeGraphEntry
[] ret
= new ITimeGraphEntry
[0];
247 if (inputElement
instanceof List
) {
248 List
<?
> list
= (List
<?
>) inputElement
;
249 if (!list
.isEmpty()) {
250 Object first
= list
.get(0);
251 if (first
instanceof CriticalPathBaseEntry
) {
252 IGraphWorker worker
= ((CriticalPathBaseEntry
) first
).getWorker();
253 ret
= getWorkerEntries(worker
);
260 private ITimeGraphEntry
[] getWorkerEntries(IGraphWorker worker
) {
261 fCurrentObject
= worker
;
262 List
<TimeGraphEntry
> entries
= workerEntries
.get(worker
);
263 if (entries
== null) {
264 buildEntryList(worker
);
265 entries
= workerEntries
.get(worker
);
268 return (entries
== null) ?
269 new ITimeGraphEntry
[0] :
270 entries
.toArray(new @NonNull ITimeGraphEntry
[entries
.size()]);
273 private void buildEntryList(IGraphWorker worker
) {
274 final ITmfTrace trace
= getTrace();
278 final TmfGraph graph
= getGraph(trace
);
282 setStartTime(Long
.MAX_VALUE
);
283 setEndTime(Long
.MIN_VALUE
);
285 final HashMap
<Object
, CriticalPathEntry
> rootList
= new HashMap
<>();
286 fLinks
.remove(trace
, worker
);
288 TmfVertex vertex
= graph
.getHead();
290 /* Calculate statistics */
291 fStats
= new TmfGraphStatistics();
292 fStats
.computeGraphStatistics(graph
, worker
);
293 fObjectStatistics
.put(trace
, worker
, fStats
);
295 // Hosts entries are parent of each worker entries
296 final Map
<String
, CriticalPathEntry
> hostEntries
= new HashMap
<>();
298 /* create all interval entries and horizontal links */
300 final CriticalPathEntry defaultParent
= new CriticalPathEntry("default", trace
, getStartTime(), getEndTime(), DEFAULT_WORKER
); //$NON-NLS-1$
301 graph
.scanLineTraverse(vertex
, new HorizontalLinksVisitor(defaultParent
, hostEntries
, graph
, trace
, rootList
));
303 workerMaps
.put(worker
, rootList
);
305 List
<TimeGraphEntry
> list
= new ArrayList
<>();
306 list
.addAll(hostEntries
.values());
307 if (defaultParent
.hasChildren()) {
308 list
.add(defaultParent
);
311 workerEntries
.put(worker
, list
);
314 private @Nullable TmfGraph
getGraph(final ITmfTrace trace
) {
315 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
316 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class),
318 if (module
== null) {
319 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
322 final TmfGraph graph
= module
.getCriticalPath();
326 public @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
) {
327 Object current
= fCurrentObject
;
328 if (current
== null) {
332 * Critical path typically has relatively few links, so we calculate
333 * and save them all, but just return those in range
335 List
<ILinkEvent
> links
= linkMap
.get(current
);
339 final ITmfTrace trace
= getTrace();
343 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
344 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class), null);
345 if (module
== null) {
346 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
349 final TmfGraph graph
= module
.getCriticalPath();
353 final Map
<Object
, CriticalPathEntry
> entryMap
= workerMaps
.get(current
);
354 if (entryMap
== null) {
358 TmfVertex vertex
= graph
.getHead();
360 final List
<ILinkEvent
> graphLinks
= new ArrayList
<>();
362 /* find vertical links */
363 graph
.scanLineTraverse(vertex
, new VerticalLinksVisitor(graph
, graphLinks
, entryMap
));
364 fLinks
.put(trace
, checkNotNull(fCurrentObject
), graphLinks
);
367 List
<ILinkEvent
> linksInRange
= new ArrayList
<>();
368 for (ILinkEvent link
: links
) {
369 if (((link
.getTime() >= startTime
) && (link
.getTime() <= endTime
)) ||
370 ((link
.getTime() + link
.getDuration() >= startTime
) && (link
.getTime() + link
.getDuration() <= endTime
))) {
371 linksInRange
.add(link
);
378 public void dispose() {
381 BuildThread buildThread
= fBuildThread
;
382 if (buildThread
!= null) {
383 buildThread
.cancel();
391 public void inputChanged(@Nullable Viewer viewer
, @Nullable Object oldInput
, @Nullable Object newInput
) {
392 // The input has changed, the critical path will be re-computed,
393 // wait for the analysis to be finished, then call the refresh
394 // method of the view
395 if (!(newInput
instanceof List
)) {
398 List
<?
> list
= (List
<?
>) newInput
;
399 if (list
.isEmpty()) {
402 final ITmfTrace trace
= getTrace();
409 BuildThread buildThread
= fBuildThread
;
410 if (buildThread
!= null) {
411 buildThread
.cancel();
413 buildThread
= new BuildThread(trace
);
415 fBuildThread
= buildThread
;
422 public ITimeGraphEntry
@Nullable [] getChildren(@Nullable Object parentElement
) {
423 if (parentElement
instanceof CriticalPathEntry
) {
424 List
<?
extends ITimeGraphEntry
> children
= ((CriticalPathEntry
) parentElement
).getChildren();
425 return children
.toArray(new TimeGraphEntry
[children
.size()]);
431 public @Nullable ITimeGraphEntry
getParent(@Nullable Object element
) {
432 if (element
instanceof CriticalPathEntry
) {
433 return ((CriticalPathEntry
) element
).getParent();
439 public boolean hasChildren(@Nullable Object element
) {
440 if (element
instanceof CriticalPathEntry
) {
441 return ((CriticalPathEntry
) element
).hasChildren();
448 private class CriticalPathTreeLabelProvider
extends TreeLabelProvider
{
451 public String
getColumnText(@Nullable Object element
, int columnIndex
) {
452 if (element
== null) {
453 return ""; //$NON-NLS-1$
455 CriticalPathEntry entry
= (CriticalPathEntry
) element
;
456 if (columnIndex
== 0) {
457 return NonNullUtils
.nullToEmptyString(entry
.getName());
458 } else if (columnIndex
== 1) {
459 Long sum
= fStats
.getSum(entry
.getWorker());
460 String value
= String
.format("%.9f", sum
* NANOINV
); //$NON-NLS-1$
461 return NonNullUtils
.nullToEmptyString(value
);
462 } else if (columnIndex
== 2) {
463 Double percent
= fStats
.getPercent(entry
.getWorker());
464 String value
= String
.format("%.2f", percent
* 100); //$NON-NLS-1$
465 return NonNullUtils
.nullToEmptyString(value
);
467 return ""; //$NON-NLS-1$
472 private class CriticalPathEntryComparator
implements Comparator
<ITimeGraphEntry
> {
475 public int compare(@Nullable ITimeGraphEntry o1
, @Nullable ITimeGraphEntry o2
) {
479 if ((o1
instanceof CriticalPathEntry
) && (o2
instanceof CriticalPathEntry
)) {
480 CriticalPathEntry entry1
= (CriticalPathEntry
) o1
;
481 CriticalPathEntry entry2
= (CriticalPathEntry
) o2
;
482 result
= -1 * fStats
.getSum(entry1
.getWorker()).compareTo(fStats
.getSum(entry2
.getWorker()));
491 public CriticalPathView() {
492 super(ID
, new CriticalPathPresentationProvider());
493 setTreeColumns(COLUMN_NAMES
);
494 setFilterColumns(FILTER_COLUMN_NAMES
);
495 setTreeLabelProvider(new CriticalPathTreeLabelProvider());
496 setTimeGraphContentProvider(fContentProvider
);
497 setEntryComparator(new CriticalPathEntryComparator());
500 // ------------------------------------------------------------------------
502 // ------------------------------------------------------------------------
504 private static State
getMatchingState(EdgeType type
) {
505 State state
= State
.UNKNOWN
;
508 state
= State
.RUNNING
;
511 state
= State
.PREEMPTED
;
517 state
= State
.BLOCK_DEVICE
;
520 state
= State
.INTERRUPTED
;
523 state
= State
.NETWORK
;
526 state
= State
.USER_INPUT
;
543 protected void buildEntryList(@NonNull ITmfTrace trace
, @NonNull ITmfTrace parentTrace
, @NonNull IProgressMonitor monitor
) {
544 /* This class uses a content provider instead */
548 protected @Nullable List
<ITimeEvent
> getEventList(TimeGraphEntry entry
,
549 long startTime
, long endTime
, long resolution
,
550 IProgressMonitor monitor
) {
552 * The event list is built in the HorizontalLinksVisitor. This is called
553 * only from the zoom thread and only for the CriticalPathBaseEntry.
559 protected @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
, long resolution
, IProgressMonitor monitor
) {
560 return fContentProvider
.getLinkList(startTime
, endTime
);
564 * Signal handler for analysis started
570 public void analysisStarted(TmfStartAnalysisSignal signal
) {
571 if (!(signal
.getAnalysisModule() instanceof CriticalPathModule
)) {
574 CriticalPathModule module
= (CriticalPathModule
) signal
.getAnalysisModule();
575 Object obj
= module
.getParameter(CriticalPathModule
.PARAM_WORKER
);
579 if (!(obj
instanceof IGraphWorker
)) {
580 throw new IllegalStateException("Wrong type for critical path module parameter " + //$NON-NLS-1$
581 CriticalPathModule
.PARAM_WORKER
+
582 " expected IGraphWorker got " + //$NON-NLS-1$
583 obj
.getClass().getSimpleName());
585 ITmfTrace trace
= getTrace();
587 throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
589 IGraphWorker worker
= (IGraphWorker
) obj
;
590 TmfGraphStatistics stats
= fObjectStatistics
.get(trace
, worker
);
592 stats
= new TmfGraphStatistics();
593 fObjectStatistics
.put(trace
, worker
, stats
);
597 TimeGraphEntry tge
= new CriticalPathBaseEntry(worker
);
598 List
<TimeGraphEntry
> list
= Collections
.singletonList(tge
);
599 putEntryList(trace
, list
);