1 /*******************************************************************************
2 * Copyright (c) 2015 É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
.Iterator
;
19 import java
.util
.List
;
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
;
50 import com
.google
.common
.collect
.HashBasedTable
;
51 import com
.google
.common
.collect
.Iterables
;
52 import com
.google
.common
.collect
.Table
;
55 * The Critical Path view
57 * @author Geneviève Bastien
58 * @author Francis Giraldeau
60 public class CriticalPathView
extends AbstractTimeGraphView
{
62 // ------------------------------------------------------------------------
64 // ------------------------------------------------------------------------
67 public static final String ID
= "org.eclipse.linuxtools.tmf.analysis.graph.ui.criticalpath.view.criticalpathview"; //$NON-NLS-1$
69 private static final double NANOINV
= 0.000000001;
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
);
75 private static final String
[] COLUMN_NAMES
= new String
[] {
81 private static final String
[] FILTER_COLUMN_NAMES
= new String
[] {
85 private final Table
<ITmfTrace
, Object
, List
<ILinkEvent
>> fLinks
= NonNullUtils
.checkNotNull(HashBasedTable
.<ITmfTrace
, Object
, List
<ILinkEvent
>> create());
86 /** The trace to entry list hash map */
87 private final Table
<ITmfTrace
, Object
, TmfGraphStatistics
> fObjectStatistics
= NonNullUtils
.checkNotNull(HashBasedTable
.<ITmfTrace
, Object
, TmfGraphStatistics
> create());
89 private final CriticalPathContentProvider fContentProvider
= new CriticalPathContentProvider();
91 private TmfGraphStatistics fStats
= new TmfGraphStatistics();
93 private static final IGraphWorker DEFAULT_WORKER
= new IGraphWorker() {
95 public String
getHostId() {
96 return "default"; //$NON-NLS-1$
100 private class CriticalPathContentProvider
implements ITimeGraphContentProvider
{
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
;
109 private HorizontalLinksVisitor(CriticalPathEntry defaultParent
, Map
<String
, CriticalPathEntry
> hostEntries
, TmfGraph graph
, ITmfTrace trace
, HashMap
<Object
, CriticalPathEntry
> rootList
) {
110 fDefaultParent
= defaultParent
;
111 fHostEntries
= hostEntries
;
114 fRootList
= rootList
;
118 public void visitHead(TmfVertex node
) {
119 /* TODO possible null pointer ? */
120 IGraphWorker owner
= fGraph
.getParentOf(node
);
124 if (fRootList
.containsKey(owner
)) {
127 TmfVertex first
= fGraph
.getHead(owner
);
128 TmfVertex last
= fGraph
.getTail(owner
);
129 if (first
== null || last
== null) {
132 setStartTime(Math
.min(getStartTime(), first
.getTs()));
133 setEndTime(Math
.max(getEndTime(), last
.getTs()));
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
));
140 parent
= checkNotNull(fHostEntries
.get(host
));
141 CriticalPathEntry entry
= new CriticalPathEntry(NonNullUtils
.nullToEmptyString(owner
), fTrace
, getStartTime(), getEndTime(), owner
);
142 parent
.addChild(entry
);
144 fRootList
.put(owner
, entry
);
148 public void visit(TmfVertex node
) {
149 setStartTime(Math
.min(getStartTime(), node
.getTs()));
150 setEndTime(Math
.max(getEndTime(), node
.getTs()));
154 public void visit(TmfEdge link
, boolean 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());
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
;
170 private VerticalLinksVisitor(TmfGraph graph
, List
<ILinkEvent
> graphLinks
, Map
<Object
, CriticalPathEntry
> entryMap
) {
172 fGraphLinks
= graphLinks
;
173 fEntryMap
= entryMap
;
177 public void visitHead(TmfVertex node
) {
182 public void visit(TmfVertex node
) {
187 public void visit(TmfEdge link
, boolean 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());
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
;
206 public @Nullable 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
);
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
);
228 return (entries
== null) ?
229 new ITimeGraphEntry
[0] :
230 NonNullUtils
.checkNotNull(entries
.toArray(new ITimeGraphEntry
[entries
.size()]));
233 private void buildEntryList(IGraphWorker worker
) {
234 final ITmfTrace trace
= getTrace();
238 final TmfGraph graph
= getGraph(trace
);
242 setStartTime(Long
.MAX_VALUE
);
243 setEndTime(Long
.MIN_VALUE
);
245 final HashMap
<Object
, CriticalPathEntry
> rootList
= new HashMap
<>();
246 fLinks
.remove(trace
, worker
);
248 TmfVertex vertex
= graph
.getHead();
250 /* Calculate statistics */
251 fStats
= new TmfGraphStatistics();
252 fStats
.computeGraphStatistics(graph
, worker
);
253 fObjectStatistics
.put(trace
, worker
, fStats
);
255 // Hosts entries are parent of each worker entries
256 final Map
<String
, CriticalPathEntry
> hostEntries
= new HashMap
<>();
258 /* create all interval entries and horizontal links */
260 final CriticalPathEntry defaultParent
= new CriticalPathEntry("default", trace
, getStartTime(), getEndTime(), DEFAULT_WORKER
); //$NON-NLS-1$
261 graph
.scanLineTraverse(vertex
, new HorizontalLinksVisitor(defaultParent
, hostEntries
, graph
, trace
, rootList
));
263 workerMaps
.put(worker
, rootList
);
265 List
<TimeGraphEntry
> list
= new ArrayList
<>();
266 list
.addAll(hostEntries
.values());
267 if (defaultParent
.hasChildren()) {
268 list
.add(defaultParent
);
271 for (TimeGraphEntry entry
: list
) {
272 buildStatusEvents(trace
, (CriticalPathEntry
) NonNullUtils
.checkNotNull(entry
));
274 workerEntries
.put(worker
, list
);
277 private @Nullable TmfGraph
getGraph(final ITmfTrace trace
) {
278 CriticalPathModule module
= Iterables
.getFirst(TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class), null);
279 if (module
== null) {
283 if (!module
.waitForCompletion()) {
286 final TmfGraph graph
= module
.getCriticalPath();
290 public @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
) {
291 Object current
= fCurrentObject
;
292 if (current
== null) {
296 * Critical path typically has relatively few links, so we calculate
297 * and save them all, but just return those in range
299 List
<ILinkEvent
> links
= linkMap
.get(current
);
303 final ITmfTrace trace
= getTrace();
307 CriticalPathModule module
= Iterables
.getFirst(TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class), null);
308 if (module
== null) {
311 final TmfGraph graph
= module
.getCriticalPath();
315 final Map
<Object
, CriticalPathEntry
> entryMap
= workerMaps
.get(current
);
316 if (entryMap
== null) {
320 TmfVertex vertex
= graph
.getHead();
322 final List
<ILinkEvent
> graphLinks
= new ArrayList
<>();
324 /* find vertical links */
325 graph
.scanLineTraverse(vertex
, new VerticalLinksVisitor(graph
, graphLinks
, entryMap
));
326 fLinks
.put(trace
, fCurrentObject
, graphLinks
);
329 List
<ILinkEvent
> linksInRange
= new ArrayList
<>();
330 for (ILinkEvent link
: links
) {
331 if (((link
.getTime() >= startTime
) && (link
.getTime() <= endTime
)) ||
332 ((link
.getTime() + link
.getDuration() >= startTime
) && (link
.getTime() + link
.getDuration() <= endTime
))) {
333 linksInRange
.add(link
);
340 public void dispose() {
345 public void inputChanged(@Nullable Viewer viewer
, @Nullable Object oldInput
, @Nullable Object newInput
) {
349 public @Nullable ITimeGraphEntry
[] getChildren(@Nullable Object parentElement
) {
350 if (parentElement
instanceof CriticalPathEntry
) {
351 List
<?
extends ITimeGraphEntry
> children
= ((CriticalPathEntry
) parentElement
).getChildren();
352 return children
.toArray(new TimeGraphEntry
[children
.size()]);
358 public @Nullable ITimeGraphEntry
getParent(@Nullable Object element
) {
359 if (element
instanceof CriticalPathEntry
) {
360 return ((CriticalPathEntry
) element
).getParent();
366 public boolean hasChildren(@Nullable Object element
) {
367 if (element
instanceof CriticalPathEntry
) {
368 return ((CriticalPathEntry
) element
).hasChildren();
375 private class CriticalPathTreeLabelProvider
extends TreeLabelProvider
{
378 public String
getColumnText(@Nullable Object element
, int columnIndex
) {
379 if (element
== null) {
380 return ""; //$NON-NLS-1$
382 CriticalPathEntry entry
= (CriticalPathEntry
) element
;
383 if (columnIndex
== 0) {
384 return NonNullUtils
.nullToEmptyString(entry
.getName());
385 } else if (columnIndex
== 1) {
386 Long sum
= fStats
.getSum(entry
.getWorker());
387 String value
= String
.format("%.9f", sum
* NANOINV
); //$NON-NLS-1$
388 return NonNullUtils
.nullToEmptyString(value
);
389 } else if (columnIndex
== 2) {
390 Double percent
= fStats
.getPercent(entry
.getWorker());
391 String value
= String
.format("%.2f", percent
* 100); //$NON-NLS-1$
392 return NonNullUtils
.nullToEmptyString(value
);
394 return ""; //$NON-NLS-1$
399 private class CriticalPathEntryComparator
implements Comparator
<ITimeGraphEntry
> {
402 public int compare(@Nullable ITimeGraphEntry o1
, @Nullable ITimeGraphEntry o2
) {
406 if ((o1
instanceof CriticalPathEntry
) && (o2
instanceof CriticalPathEntry
)) {
407 CriticalPathEntry entry1
= (CriticalPathEntry
) o1
;
408 CriticalPathEntry entry2
= (CriticalPathEntry
) o2
;
409 result
= -1 * fStats
.getSum(entry1
.getWorker()).compareTo(fStats
.getSum(entry2
.getWorker()));
418 public CriticalPathView() {
419 super(ID
, new CriticalPathPresentationProvider());
420 setTreeColumns(COLUMN_NAMES
);
421 setFilterColumns(FILTER_COLUMN_NAMES
);
422 setTreeLabelProvider(new CriticalPathTreeLabelProvider());
423 setTimeGraphContentProvider(fContentProvider
);
424 setEntryComparator(new CriticalPathEntryComparator());
427 // ------------------------------------------------------------------------
429 // ------------------------------------------------------------------------
431 private static State
getMatchingState(EdgeType type
) {
432 State state
= State
.UNKNOWN
;
435 state
= State
.RUNNING
;
438 state
= State
.PREEMPTED
;
444 state
= State
.BLOCK_DEVICE
;
447 state
= State
.INTERRUPTED
;
450 state
= State
.NETWORK
;
453 state
= State
.USER_INPUT
;
466 private void buildStatusEvents(ITmfTrace trace
, CriticalPathEntry entry
) {
468 long start
= trace
.getStartTime().getValue();
469 long end
= trace
.getEndTime().getValue() + 1;
470 long resolution
= Math
.max(1, (end
- start
) / getDisplayWidth());
471 List
<ITimeEvent
> eventList
= getEventList(entry
, entry
.getStartTime(), entry
.getEndTime(), resolution
, new NullProgressMonitor());
473 entry
.setZoomedEventList(eventList
);
477 for (ITimeGraphEntry child
: entry
.getChildren()) {
479 throw new NullPointerException();
481 buildStatusEvents(trace
, (CriticalPathEntry
) child
);
486 protected void buildEventList(@NonNull ITmfTrace trace
, @NonNull ITmfTrace parentTrace
, @NonNull IProgressMonitor monitor
) {
487 /* This class uses a content provider instead */
491 protected @Nullable List
<ITimeEvent
> getEventList(TimeGraphEntry entry
,
492 long startTime
, long endTime
, long resolution
,
493 IProgressMonitor monitor
) {
495 final long realStart
= Math
.max(startTime
, entry
.getStartTime());
496 final long realEnd
= Math
.min(endTime
, entry
.getEndTime());
497 if (realEnd
<= realStart
) {
500 List
<ITimeEvent
> eventList
= null;
501 entry
.setZoomedEventList(null);
502 Iterator
<ITimeEvent
> iterator
= entry
.getTimeEventsIterator();
503 eventList
= new ArrayList
<>();
505 while (iterator
.hasNext()) {
506 ITimeEvent event
= iterator
.next();
507 /* is event visible */
508 if (intersects(realStart
, realEnd
, NonNullUtils
.checkNotNull(event
))) {
509 eventList
.add(event
);
515 private static boolean intersects(final long realStart
, final long realEnd
, ITimeEvent event
) {
516 return ((event
.getTime() >= realStart
) && (event
.getTime() <= realEnd
)) ||
517 ((event
.getTime() + event
.getDuration() > realStart
) &&
518 (event
.getTime() + event
.getDuration() < realEnd
));
522 protected @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
, long resolution
, IProgressMonitor monitor
) {
523 return fContentProvider
.getLinkList(startTime
, endTime
);
527 * Signal handler for analysis started
533 public void analysisStarted(TmfStartAnalysisSignal signal
) {
534 if (!(signal
.getAnalysisModule() instanceof CriticalPathModule
)) {
537 CriticalPathModule module
= (CriticalPathModule
) signal
.getAnalysisModule();
538 Object obj
= module
.getParameter(CriticalPathModule
.PARAM_WORKER
);
542 if (!(obj
instanceof IGraphWorker
)) {
543 throw new IllegalStateException("Wrong type for critical path module parameter " + //$NON-NLS-1$
544 CriticalPathModule
.PARAM_WORKER
+
545 " expected IGraphWorker got " + //$NON-NLS-1$
546 obj
.getClass().getSimpleName());
548 ITmfTrace trace
= getTrace();
550 throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
552 IGraphWorker worker
= (IGraphWorker
) obj
;
553 TmfGraphStatistics stats
= fObjectStatistics
.get(trace
, worker
);
555 stats
= new TmfGraphStatistics();
556 fObjectStatistics
.put(trace
, worker
, stats
);
560 TimeGraphEntry tge
= new CriticalPathBaseEntry(worker
);
561 List
<TimeGraphEntry
> list
= Collections
.singletonList(tge
);
562 putEntryList(trace
, list
);