From e62a23a90dae387e3707d0fab9bb26aa42a3bd6c Mon Sep 17 00:00:00 2001 From: Alexandre Montplaisir Date: Wed, 22 Oct 2014 14:13:02 -0400 Subject: [PATCH] ss: Also search in the ThreadedHistoryBackend's interval queue If a view, like a live-enabled time graph view, makes a lot of queries close to the "current end time" while the history is being built, it is very possible to miss some intervals due to them being in the ThreadedHistoryBackend's interval queue. We should also search in that queue for possible intervals. Since this case is still relatively rare, it's usually faster to query the history tree first, then go look through the queue, rather than checking in the queue first every time (which can only be explored in O(n)). Fixes bug #443127. Change-Id: I82e389cf95ce04002f61629d5a0d317a35a931ff Signed-off-by: Alexandre Montplaisir Reviewed-on: https://git.eclipse.org/r/35504 Reviewed-by: Genevieve Bastien Tested-by: Hudson CI Reviewed-by: Patrick Tasse --- .../statesystem/core/StateSystem.java | 31 ++++--- .../statesystem/core/ITmfStateSystem.java | 5 +- .../historytree/HistoryTreeBackend.java | 21 ++--- .../ThreadedHistoryTreeBackend.java | 84 +++++++++++++++++-- .../mipmap/TmfStateSystemOperations.java | 5 +- 5 files changed, 104 insertions(+), 42 deletions(-) diff --git a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java index 15e2679b3d..f7e0013e07 100644 --- a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java +++ b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java @@ -29,7 +29,6 @@ import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedE import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; -import org.eclipse.tracecompass.statesystem.core.interval.TmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue.Type; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; @@ -552,16 +551,14 @@ public class StateSystem implements ITmfStateSystemBuilder { throw new StateSystemDisposedException(); } - List stateInfo = new ArrayList<>(getNbAttributes()); + final int nbAttr = getNbAttributes(); + List stateInfo = new ArrayList<>(nbAttr); /* Bring the size of the array to the current number of attributes */ - for (int i = 0; i < getNbAttributes(); i++) { + for (int i = 0; i < nbAttr; i++) { stateInfo.add(null); } - /* Query the storage backend */ - backend.doQuery(stateInfo, t); - /* * If we are currently building the history, also query the "ongoing" * states for stuff that might not yet be written to the history. @@ -570,14 +567,15 @@ public class StateSystem implements ITmfStateSystemBuilder { transState.doQuery(stateInfo, t); } + /* Query the storage backend */ + backend.doQuery(stateInfo, t); + /* * We should have previously inserted an interval for every attribute. - * If we do happen do see a 'null' object here, just replace it with a a - * dummy internal with a null value, to avoid NPE's further up. */ - for (int i = 0; i < stateInfo.size(); i++) { - if (stateInfo.get(i) == null) { - stateInfo.set(i, new TmfStateInterval(t, t, i, TmfStateValue.nullValue())); + for (ITmfStateInterval interval : stateInfo) { + if (interval == null) { + throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$ } } return stateInfo; @@ -600,13 +598,12 @@ public class StateSystem implements ITmfStateSystemBuilder { ret = backend.doSingularQuery(t, attributeQuark); } - /* - * Return a fake interval if we could not find anything in the history. - * We do NOT want to return 'null' here. - */ if (ret == null) { - return new TmfStateInterval(t, this.getCurrentEndTime(), - attributeQuark, TmfStateValue.nullValue()); + /* + * If we did our job correctly, there should be intervals for every + * possible attribute, over all the valid time range. + */ + throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$ } return ret; } diff --git a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java index 78a4ebc8b9..2ca5403124 100644 --- a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java +++ b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/ITmfStateSystem.java @@ -14,6 +14,7 @@ package org.eclipse.tracecompass.statesystem.core; import java.util.List; +import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException; import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; @@ -306,7 +307,7 @@ public interface ITmfStateSystem { * @throws StateSystemDisposedException * If the query is sent after the state system has been disposed */ - List queryFullState(long t) + @NonNull List queryFullState(long t) throws StateSystemDisposedException; /** @@ -331,6 +332,6 @@ public interface ITmfStateSystem { * @throws StateSystemDisposedException * If the query is sent after the state system has been disposed */ - ITmfStateInterval querySingleState(long t, int attributeQuark) + @NonNull ITmfStateInterval querySingleState(long t, int attributeQuark) throws AttributeNotFoundException, StateSystemDisposedException; } \ No newline at end of file diff --git a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/HistoryTreeBackend.java b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/HistoryTreeBackend.java index 72860a9726..9238976698 100644 --- a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/HistoryTreeBackend.java +++ b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/HistoryTreeBackend.java @@ -42,14 +42,11 @@ public class HistoryTreeBackend implements IStateHistoryBackend { /** * The history tree that sits underneath. - * - * Using default visibility to only allow {@link ThreadedHistoryTreeBackend} - * to see it. */ - final HistoryTree sht; + private final HistoryTree sht; /** Indicates if the history tree construction is done */ - protected boolean isFinishedBuilding = false; + protected volatile boolean isFinishedBuilding = false; /** * Constructor for new history files. Use this when creating a new history @@ -119,6 +116,15 @@ public class HistoryTreeBackend implements IStateHistoryBackend { isFinishedBuilding = true; } + /** + * Get the History Tree built by this backend. + * + * @return The history tree + */ + protected HistoryTree getSHT() { + return sht; + } + @Override public long getStartTime() { return sht.getTreeStart(); @@ -243,11 +249,6 @@ public class HistoryTreeBackend implements IStateHistoryBackend { } catch (ClosedChannelException e) { throw new StateSystemDisposedException(e); } - /* - * Since we should now have intervals at every attribute/timestamp - * combination, it should NOT be null here. - */ - assert (interval != null); return interval; } diff --git a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java index 0872f12be7..fb03b4307c 100644 --- a/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java +++ b/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/statesystem/core/backend/historytree/ThreadedHistoryTreeBackend.java @@ -14,12 +14,16 @@ package org.eclipse.tracecompass.statesystem.core.backend.historytree; import java.io.File; import java.io.IOException; +import java.util.List; import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; +import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.internal.statesystem.core.Activator; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval; +import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; +import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue; import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; @@ -33,8 +37,8 @@ import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue; public final class ThreadedHistoryTreeBackend extends HistoryTreeBackend implements Runnable { - private BlockingQueue intervalQueue; - private final Thread shtThread; + private final @NonNull BlockingQueue intervalQueue; + private final @NonNull Thread shtThread; /** * New state history constructor @@ -172,24 +176,23 @@ public final class ThreadedHistoryTreeBackend extends HistoryTreeBackend @Override public void run() { - if (intervalQueue == null) { - Activator.getDefault().logError("Cannot start the storage backend without its interval queue."); //$NON-NLS-1$ - return; - } HTInterval currentInterval; try { currentInterval = intervalQueue.take(); while (currentInterval.getStartTime() != -1) { /* Send the interval to the History Tree */ - sht.insertInterval(currentInterval); + getSHT().insertInterval(currentInterval); currentInterval = intervalQueue.take(); } - assert (currentInterval.getAttribute() == -1); + if (currentInterval.getAttribute() != -1) { + /* Make sure this is the "poison pill" we are waiting for */ + throw new IllegalStateException(); + } /* * We've been told we're done, let's write down everything and quit. * The end time of this "signal interval" is actually correct. */ - sht.closeTree(currentInterval.getEndTime()); + getSHT().closeTree(currentInterval.getEndTime()); return; } catch (InterruptedException e) { /* We've been interrupted abnormally */ @@ -200,4 +203,67 @@ public final class ThreadedHistoryTreeBackend extends HistoryTreeBackend } } + // ------------------------------------------------------------------------ + // Query methods + // ------------------------------------------------------------------------ + + @Override + public void doQuery(List currentStateInfo, long t) + throws TimeRangeException, StateSystemDisposedException { + super.doQuery(currentStateInfo, t); + + if (isFinishedBuilding) { + /* + * The history tree is the only place to look for intervals once + * construction is finished. + */ + return; + } + + /* + * It is possible we may have missed some intervals due to them being in + * the queue while the query was ongoing. Go over the results to see if + * we missed any. + */ + for (int i = 0; i < currentStateInfo.size(); i++) { + if (currentStateInfo.get(i) == null) { + /* Query the missing interval via "unicast" */ + ITmfStateInterval interval = doSingularQuery(t, i); + currentStateInfo.set(i, interval); + } + } + } + + @Override + public ITmfStateInterval doSingularQuery(long t, int attributeQuark) + throws TimeRangeException, StateSystemDisposedException { + ITmfStateInterval ret = super.doSingularQuery(t, attributeQuark); + if (ret != null) { + return ret; + } + + /* + * We couldn't find the interval in the history tree. It's possible that + * it is currently in the intervalQueue. Look for it there. Note that + * ArrayBlockingQueue's iterator() is thread-safe (no need to lock the + * queue). + */ + for (ITmfStateInterval interval : intervalQueue) { + if (interval.getAttribute() == attributeQuark && interval.intersects(t)) { + return interval; + } + } + + /* + * If we missed it again, it's because it got inserted in the tree + * *while we were iterating* on the queue. One last pass in the tree + * should find it. + * + * This case is really rare, which is why we do a second pass at the + * end if needed, instead of systematically checking in the queue first + * (which is slow). + */ + return super.doSingularQuery(t, attributeQuark); + } + } diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/statesystem/mipmap/TmfStateSystemOperations.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/statesystem/mipmap/TmfStateSystemOperations.java index f7d355d778..13290bd2ed 100644 --- a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/statesystem/mipmap/TmfStateSystemOperations.java +++ b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/statesystem/mipmap/TmfStateSystemOperations.java @@ -281,16 +281,13 @@ public final class TmfStateSystemOperations { currentLevelInterval = ss.querySingleState(range.getFirst(), levelQuark); } - if (currentLevelInterval != null && isFullyOverlapped(range, currentLevelInterval)) { + if (isFullyOverlapped(range, currentLevelInterval)) { if (!currentLevelInterval.getStateValue().isNull()) { intervals.add(currentLevelInterval); } range = updateTimeRange(range, currentLevelInterval); } else { if (level == 0) { - if (currentLevelInterval == null) { - return; - } if (!currentLevelInterval.getStateValue().isNull()) { intervals.add(currentLevelInterval); } -- 2.34.1