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
.create());
86 /** The trace to entry list hash map */
87 private final Table
<ITmfTrace
, Object
, TmfGraphStatistics
> fObjectStatistics
= NonNullUtils
.checkNotNull(HashBasedTable
.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 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
);
229 return (entries
== null) ?
230 new ITimeGraphEntry
[0] :
231 NonNullUtils
.checkNotNull(entries
.toArray(new ITimeGraphEntry
[entries
.size()]));
234 private void buildEntryList(IGraphWorker worker
) {
235 final ITmfTrace trace
= getTrace();
239 final TmfGraph graph
= getGraph(trace
);
243 setStartTime(Long
.MAX_VALUE
);
244 setEndTime(Long
.MIN_VALUE
);
246 final HashMap
<Object
, CriticalPathEntry
> rootList
= new HashMap
<>();
247 fLinks
.remove(trace
, worker
);
249 TmfVertex vertex
= graph
.getHead();
251 /* Calculate statistics */
252 fStats
= new TmfGraphStatistics();
253 fStats
.computeGraphStatistics(graph
, worker
);
254 fObjectStatistics
.put(trace
, worker
, fStats
);
256 // Hosts entries are parent of each worker entries
257 final Map
<String
, CriticalPathEntry
> hostEntries
= new HashMap
<>();
259 /* create all interval entries and horizontal links */
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
));
264 workerMaps
.put(worker
, rootList
);
266 List
<TimeGraphEntry
> list
= new ArrayList
<>();
267 list
.addAll(hostEntries
.values());
268 if (defaultParent
.hasChildren()) {
269 list
.add(defaultParent
);
272 for (TimeGraphEntry entry
: list
) {
273 buildStatusEvents(trace
, (CriticalPathEntry
) NonNullUtils
.checkNotNull(entry
));
275 workerEntries
.put(worker
, list
);
278 private @Nullable TmfGraph
getGraph(final ITmfTrace trace
) {
279 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
280 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class),
282 if (module
== null) {
283 throw new IllegalStateException();
287 if (!module
.waitForCompletion()) {
290 final TmfGraph graph
= module
.getCriticalPath();
294 public @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
) {
295 Object current
= fCurrentObject
;
296 if (current
== null) {
300 * Critical path typically has relatively few links, so we calculate
301 * and save them all, but just return those in range
303 List
<ILinkEvent
> links
= linkMap
.get(current
);
307 final ITmfTrace trace
= getTrace();
311 CriticalPathModule module
= Iterables
.<@Nullable CriticalPathModule
> getFirst(
312 TmfTraceUtils
.getAnalysisModulesOfClass(trace
, CriticalPathModule
.class), null);
313 if (module
== null) {
314 throw new IllegalStateException();
317 final TmfGraph graph
= module
.getCriticalPath();
321 final Map
<Object
, CriticalPathEntry
> entryMap
= workerMaps
.get(current
);
322 if (entryMap
== null) {
326 TmfVertex vertex
= graph
.getHead();
328 final List
<ILinkEvent
> graphLinks
= new ArrayList
<>();
330 /* find vertical links */
331 graph
.scanLineTraverse(vertex
, new VerticalLinksVisitor(graph
, graphLinks
, entryMap
));
332 fLinks
.put(trace
, checkNotNull(fCurrentObject
), graphLinks
);
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
);
346 public void dispose() {
351 public void inputChanged(@Nullable Viewer viewer
, @Nullable Object oldInput
, @Nullable Object newInput
) {
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()]);
364 public @Nullable ITimeGraphEntry
getParent(@Nullable Object element
) {
365 if (element
instanceof CriticalPathEntry
) {
366 return ((CriticalPathEntry
) element
).getParent();
372 public boolean hasChildren(@Nullable Object element
) {
373 if (element
instanceof CriticalPathEntry
) {
374 return ((CriticalPathEntry
) element
).hasChildren();
381 private class CriticalPathTreeLabelProvider
extends TreeLabelProvider
{
384 public String
getColumnText(@Nullable Object element
, int columnIndex
) {
385 if (element
== null) {
386 return ""; //$NON-NLS-1$
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
);
400 return ""; //$NON-NLS-1$
405 private class CriticalPathEntryComparator
implements Comparator
<ITimeGraphEntry
> {
408 public int compare(@Nullable ITimeGraphEntry o1
, @Nullable ITimeGraphEntry o2
) {
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()));
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());
433 // ------------------------------------------------------------------------
435 // ------------------------------------------------------------------------
437 private static State
getMatchingState(EdgeType type
) {
438 State state
= State
.UNKNOWN
;
441 state
= State
.RUNNING
;
444 state
= State
.PREEMPTED
;
450 state
= State
.BLOCK_DEVICE
;
453 state
= State
.INTERRUPTED
;
456 state
= State
.NETWORK
;
459 state
= State
.USER_INPUT
;
475 private void buildStatusEvents(ITmfTrace trace
, CriticalPathEntry entry
) {
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());
482 entry
.setZoomedEventList(eventList
);
486 for (ITimeGraphEntry child
: entry
.getChildren()) {
487 buildStatusEvents(trace
, (CriticalPathEntry
) child
);
492 protected void buildEventList(@NonNull ITmfTrace trace
, @NonNull ITmfTrace parentTrace
, @NonNull IProgressMonitor monitor
) {
493 /* This class uses a content provider instead */
497 protected @Nullable List
<ITimeEvent
> getEventList(TimeGraphEntry entry
,
498 long startTime
, long endTime
, long resolution
,
499 IProgressMonitor monitor
) {
501 final long realStart
= Math
.max(startTime
, entry
.getStartTime());
502 final long realEnd
= Math
.min(endTime
, entry
.getEndTime());
503 if (realEnd
<= realStart
) {
506 List
<ITimeEvent
> eventList
= null;
507 entry
.setZoomedEventList(null);
508 Iterator
<ITimeEvent
> iterator
= entry
.getTimeEventsIterator();
509 eventList
= new ArrayList
<>();
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
);
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
));
528 protected @Nullable List
<ILinkEvent
> getLinkList(long startTime
, long endTime
, long resolution
, IProgressMonitor monitor
) {
529 return fContentProvider
.getLinkList(startTime
, endTime
);
533 * Signal handler for analysis started
539 public void analysisStarted(TmfStartAnalysisSignal signal
) {
540 if (!(signal
.getAnalysisModule() instanceof CriticalPathModule
)) {
543 CriticalPathModule module
= (CriticalPathModule
) signal
.getAnalysisModule();
544 Object obj
= module
.getParameter(CriticalPathModule
.PARAM_WORKER
);
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());
554 ITmfTrace trace
= getTrace();
556 throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
558 IGraphWorker worker
= (IGraphWorker
) obj
;
559 TmfGraphStatistics stats
= fObjectStatistics
.get(trace
, worker
);
561 stats
= new TmfGraphStatistics();
562 fObjectStatistics
.put(trace
, worker
, stats
);
566 TimeGraphEntry tge
= new CriticalPathBaseEntry(worker
);
567 List
<TimeGraphEntry
> list
= Collections
.singletonList(tge
);
568 putEntryList(trace
, list
);