critical path: bug 489360 Build the critical path in a separate thread
[deliverable/tracecompass.git] / analysis / org.eclipse.tracecompass.analysis.graph.ui / src / org / eclipse / tracecompass / internal / analysis / graph / ui / criticalpath / view / CriticalPathView.java
1 /*******************************************************************************
2 * Copyright (c) 2015, 2016 É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.List;
19 import java.util.Map;
20 import java.util.concurrent.locks.Lock;
21 import java.util.concurrent.locks.ReentrantLock;
22
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;
50
51 import com.google.common.collect.HashBasedTable;
52 import com.google.common.collect.Iterables;
53 import com.google.common.collect.Table;
54
55 /**
56 * The Critical Path view
57 *
58 * @author Geneviève Bastien
59 * @author Francis Giraldeau
60 */
61 public class CriticalPathView extends AbstractTimeGraphView {
62
63 // ------------------------------------------------------------------------
64 // Constants
65 // ------------------------------------------------------------------------
66
67 /** View ID */
68 public static final String ID = "org.eclipse.linuxtools.tmf.analysis.graph.ui.criticalpath.view.criticalpathview"; //$NON-NLS-1$
69
70 private static final double NANOINV = 0.000000001;
71
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);
75
76 private static final String[] COLUMN_NAMES = new String[] {
77 COLUMN_PROCESS,
78 COLUMN_ELAPSED,
79 COLUMN_PERCENT
80 };
81
82 private static final String[] FILTER_COLUMN_NAMES = new String[] {
83 COLUMN_PROCESS
84 };
85
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();
89
90 private final CriticalPathContentProvider fContentProvider = new CriticalPathContentProvider();
91
92 private TmfGraphStatistics fStats = new TmfGraphStatistics();
93
94 private static final IGraphWorker DEFAULT_WORKER = new IGraphWorker() {
95 @Override
96 public String getHostId() {
97 return "default"; //$NON-NLS-1$
98 }
99 };
100
101 private class CriticalPathContentProvider implements ITimeGraphContentProvider {
102
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;
109
110 private HorizontalLinksVisitor(CriticalPathEntry defaultParent, Map<String, CriticalPathEntry> hostEntries, TmfGraph graph, ITmfTrace trace, HashMap<Object, CriticalPathEntry> rootList) {
111 fDefaultParent = defaultParent;
112 fHostEntries = hostEntries;
113 fGraph = graph;
114 fTrace = trace;
115 fRootList = rootList;
116 }
117
118 @Override
119 public void visitHead(TmfVertex node) {
120 /* TODO possible null pointer ? */
121 IGraphWorker owner = fGraph.getParentOf(node);
122 if (owner == null) {
123 return;
124 }
125 if (fRootList.containsKey(owner)) {
126 return;
127 }
128 TmfVertex first = fGraph.getHead(owner);
129 TmfVertex last = fGraph.getTail(owner);
130 if (first == null || last == null) {
131 return;
132 }
133 setStartTime(Math.min(getStartTime(), first.getTs()));
134 setEndTime(Math.max(getEndTime(), last.getTs()));
135 // create host entry
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));
140 }
141 parent = checkNotNull(fHostEntries.get(host));
142 CriticalPathEntry entry = new CriticalPathEntry(NonNullUtils.nullToEmptyString(owner), fTrace, getStartTime(), getEndTime(), owner);
143 parent.addChild(entry);
144
145 fRootList.put(owner, entry);
146 }
147
148 @Override
149 public void visit(TmfVertex node) {
150 setStartTime(Math.min(getStartTime(), node.getTs()));
151 setEndTime(Math.max(getEndTime(), node.getTs()));
152 }
153
154 @Override
155 public void visit(TmfEdge link, boolean horizontal) {
156 if (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());
161 entry.addEvent(ev);
162 }
163 }
164 }
165
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;
170
171 private VerticalLinksVisitor(TmfGraph graph, List<ILinkEvent> graphLinks, Map<Object, CriticalPathEntry> entryMap) {
172 fGraph = graph;
173 fGraphLinks = graphLinks;
174 fEntryMap = entryMap;
175 }
176
177 @Override
178 public void visitHead(TmfVertex node) {
179
180 }
181
182 @Override
183 public void visit(TmfVertex node) {
184
185 }
186
187 @Override
188 public void visit(TmfEdge link, boolean horizontal) {
189 if (!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());
196 fGraphLinks.add(lk);
197 }
198 }
199 }
200
201 private class BuildThread extends Thread {
202 private final ITmfTrace fBuildTrace;
203 private final IProgressMonitor fMonitor;
204
205 public BuildThread(final ITmfTrace trace) {
206 super("Critical path view build"); //$NON-NLS-1$
207 fBuildTrace = trace;
208 fMonitor = new NullProgressMonitor();
209 }
210
211 @Override
212 public void run() {
213 try {
214 CriticalPathModule module = Iterables.<@Nullable CriticalPathModule> getFirst(
215 TmfTraceUtils.getAnalysisModulesOfClass(fBuildTrace, CriticalPathModule.class),
216 null);
217 if (module == null) {
218 return;
219 }
220 module.schedule();
221 if (module.waitForCompletion(fMonitor)) {
222 refresh();
223 }
224
225 } finally {
226 fSyncLock.lock();
227 fBuildThread = null;
228 fSyncLock.unlock();
229 }
230 }
231
232 public void cancel() {
233 fMonitor.setCanceled(true);
234 }
235 }
236
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;
243
244 @Override
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);
254 }
255 }
256 }
257 return ret;
258 }
259
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);
266 }
267
268 return (entries == null) ?
269 new ITimeGraphEntry[0] :
270 entries.toArray(new @NonNull ITimeGraphEntry[entries.size()]);
271 }
272
273 private void buildEntryList(IGraphWorker worker) {
274 final ITmfTrace trace = getTrace();
275 if (trace == null) {
276 return;
277 }
278 final TmfGraph graph = getGraph(trace);
279 if (graph == null) {
280 return;
281 }
282 setStartTime(Long.MAX_VALUE);
283 setEndTime(Long.MIN_VALUE);
284
285 final HashMap<Object, CriticalPathEntry> rootList = new HashMap<>();
286 fLinks.remove(trace, worker);
287
288 TmfVertex vertex = graph.getHead();
289
290 /* Calculate statistics */
291 fStats = new TmfGraphStatistics();
292 fStats.computeGraphStatistics(graph, worker);
293 fObjectStatistics.put(trace, worker, fStats);
294
295 // Hosts entries are parent of each worker entries
296 final Map<String, CriticalPathEntry> hostEntries = new HashMap<>();
297
298 /* create all interval entries and horizontal links */
299
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));
302
303 workerMaps.put(worker, rootList);
304
305 List<TimeGraphEntry> list = new ArrayList<>();
306 list.addAll(hostEntries.values());
307 if (defaultParent.hasChildren()) {
308 list.add(defaultParent);
309 }
310
311 workerEntries.put(worker, list);
312 }
313
314 private @Nullable TmfGraph getGraph(final ITmfTrace trace) {
315 CriticalPathModule module = Iterables.<@Nullable CriticalPathModule> getFirst(
316 TmfTraceUtils.getAnalysisModulesOfClass(trace, CriticalPathModule.class),
317 null);
318 if (module == null) {
319 throw new IllegalStateException("View requires an analysis module"); //$NON-NLS-1$
320 }
321
322 final TmfGraph graph = module.getCriticalPath();
323 return graph;
324 }
325
326 public @Nullable List<ILinkEvent> getLinkList(long startTime, long endTime) {
327 Object current = fCurrentObject;
328 if (current == null) {
329 return null;
330 }
331 /*
332 * Critical path typically has relatively few links, so we calculate
333 * and save them all, but just return those in range
334 */
335 List<ILinkEvent> links = linkMap.get(current);
336 if (links != null) {
337 return links;
338 }
339 final ITmfTrace trace = getTrace();
340 if (trace == null) {
341 return null;
342 }
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$
347 }
348
349 final TmfGraph graph = module.getCriticalPath();
350 if (graph == null) {
351 return null;
352 }
353 final Map<Object, CriticalPathEntry> entryMap = workerMaps.get(current);
354 if (entryMap == null) {
355 return null;
356 }
357
358 TmfVertex vertex = graph.getHead();
359
360 final List<ILinkEvent> graphLinks = new ArrayList<>();
361
362 /* find vertical links */
363 graph.scanLineTraverse(vertex, new VerticalLinksVisitor(graph, graphLinks, entryMap));
364 fLinks.put(trace, checkNotNull(fCurrentObject), graphLinks);
365 links = graphLinks;
366
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);
372 }
373 }
374 return linksInRange;
375 }
376
377 @Override
378 public void dispose() {
379 fSyncLock.lock();
380 try {
381 BuildThread buildThread = fBuildThread;
382 if (buildThread != null) {
383 buildThread.cancel();
384 }
385 } finally {
386 fSyncLock.unlock();
387 }
388 }
389
390 @Override
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)) {
396 return;
397 }
398 List<?> list = (List<?>) newInput;
399 if (list.isEmpty()) {
400 return;
401 }
402 final ITmfTrace trace = getTrace();
403 if (trace == null) {
404 return;
405 }
406
407 fSyncLock.lock();
408 try {
409 BuildThread buildThread = fBuildThread;
410 if (buildThread != null) {
411 buildThread.cancel();
412 }
413 buildThread = new BuildThread(trace);
414 buildThread.start();
415 fBuildThread = buildThread;
416 } finally {
417 fSyncLock.unlock();
418 }
419 }
420
421 @Override
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()]);
426 }
427 return null;
428 }
429
430 @Override
431 public @Nullable ITimeGraphEntry getParent(@Nullable Object element) {
432 if (element instanceof CriticalPathEntry) {
433 return ((CriticalPathEntry) element).getParent();
434 }
435 return null;
436 }
437
438 @Override
439 public boolean hasChildren(@Nullable Object element) {
440 if (element instanceof CriticalPathEntry) {
441 return ((CriticalPathEntry) element).hasChildren();
442 }
443 return false;
444 }
445
446 }
447
448 private class CriticalPathTreeLabelProvider extends TreeLabelProvider {
449
450 @Override
451 public String getColumnText(@Nullable Object element, int columnIndex) {
452 if (element == null) {
453 return ""; //$NON-NLS-1$
454 }
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);
466 }
467 return ""; //$NON-NLS-1$
468 }
469
470 }
471
472 private class CriticalPathEntryComparator implements Comparator<ITimeGraphEntry> {
473
474 @Override
475 public int compare(@Nullable ITimeGraphEntry o1, @Nullable ITimeGraphEntry o2) {
476
477 int result = 0;
478
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()));
483 }
484 return result;
485 }
486 }
487
488 /**
489 * Constructor
490 */
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());
498 }
499
500 // ------------------------------------------------------------------------
501 // Internal
502 // ------------------------------------------------------------------------
503
504 private static State getMatchingState(EdgeType type) {
505 State state = State.UNKNOWN;
506 switch (type) {
507 case RUNNING:
508 state = State.RUNNING;
509 break;
510 case PREEMPTED:
511 state = State.PREEMPTED;
512 break;
513 case TIMER:
514 state = State.TIMER;
515 break;
516 case BLOCK_DEVICE:
517 state = State.BLOCK_DEVICE;
518 break;
519 case INTERRUPTED:
520 state = State.INTERRUPTED;
521 break;
522 case NETWORK:
523 state = State.NETWORK;
524 break;
525 case USER_INPUT:
526 state = State.USER_INPUT;
527 break;
528 case IPI:
529 state = State.IPI;
530 break;
531 case EPS:
532 case UNKNOWN:
533 case DEFAULT:
534 case BLOCKED:
535 break;
536 default:
537 break;
538 }
539 return state;
540 }
541
542 @Override
543 protected void buildEntryList(@NonNull ITmfTrace trace, @NonNull ITmfTrace parentTrace, @NonNull IProgressMonitor monitor) {
544 /* This class uses a content provider instead */
545 }
546
547 @Override
548 protected @Nullable List<ITimeEvent> getEventList(TimeGraphEntry entry,
549 long startTime, long endTime, long resolution,
550 IProgressMonitor monitor) {
551 /*
552 * The event list is built in the HorizontalLinksVisitor. This is called
553 * only from the zoom thread and only for the CriticalPathBaseEntry.
554 */
555 return null;
556 }
557
558 @Override
559 protected @Nullable List<ILinkEvent> getLinkList(long startTime, long endTime, long resolution, IProgressMonitor monitor) {
560 return fContentProvider.getLinkList(startTime, endTime);
561 }
562
563 /**
564 * Signal handler for analysis started
565 *
566 * @param signal
567 * The signal
568 */
569 @TmfSignalHandler
570 public void analysisStarted(TmfStartAnalysisSignal signal) {
571 if (!(signal.getAnalysisModule() instanceof CriticalPathModule)) {
572 return;
573 }
574 CriticalPathModule module = (CriticalPathModule) signal.getAnalysisModule();
575 Object obj = module.getParameter(CriticalPathModule.PARAM_WORKER);
576 if (obj == null) {
577 return;
578 }
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());
584 }
585 ITmfTrace trace = getTrace();
586 if (trace == null) {
587 throw new IllegalStateException("Trace is null"); //$NON-NLS-1$
588 }
589 IGraphWorker worker = (IGraphWorker) obj;
590 TmfGraphStatistics stats = fObjectStatistics.get(trace, worker);
591 if (stats == null) {
592 stats = new TmfGraphStatistics();
593 fObjectStatistics.put(trace, worker, stats);
594 }
595 fStats = stats;
596
597 TimeGraphEntry tge = new CriticalPathBaseEntry(worker);
598 List<TimeGraphEntry> list = Collections.singletonList(tge);
599 putEntryList(trace, list);
600 refresh();
601 }
602
603 }
This page took 0.046965 seconds and 5 git commands to generate.