From b2ca67ca32f4eb2b422f37997c82eee0d09421db Mon Sep 17 00:00:00 2001 From: Patrick Tasse Date: Fri, 8 Jan 2016 15:34:19 -0500 Subject: [PATCH] ss: Bug 485463: Incorrect parent sequence number in HTNode When creating a new 'latest branch' in HistoryTree.addNewRootNode(), the new nodes' parent sequence number is incorrectly set to their parent's parent sequence number instead of their parent's sequence number. The toString() implementation of HTNode used for debugging purposes is augmented to show the sequence number of parent and children nodes. This helps in debugging problems such as this one. Change-Id: Ie6ec689bb28c72eda612d4279b6d27ead7ecc42c Signed-off-by: Patrick Tasse Signed-off-by: Alexandre Montplaisir Reviewed-on: https://git.eclipse.org/r/63898 Reviewed-by: Hudson CI --- .../core/tests/backend/HistoryTreeTest.java | 133 +++++++++++++++++- .../tests/stubs/backend/HistoryTreeStub.java | 5 + .../core/backend/historytree/CoreNode.java | 6 +- .../core/backend/historytree/HTNode.java | 22 ++- .../core/backend/historytree/HistoryTree.java | 6 +- .../core/backend/historytree/LeafNode.java | 4 +- 6 files changed, 154 insertions(+), 22 deletions(-) diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java index 1021f0d7bc..73fb35aca6 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/src/org/eclipse/tracecompass/statesystem/core/tests/backend/HistoryTreeTest.java @@ -15,6 +15,8 @@ import static org.junit.Assert.fail; import java.io.File; import java.io.IOException; +import java.nio.channels.ClosedChannelException; +import java.util.List; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; @@ -69,14 +71,21 @@ public class HistoryTreeTest { fTempFile.delete(); } - private HistoryTreeStub setupSmallTree() { + /** + * Setup a history tree. + * + * @param maxChildren + * The max number of children per node in the tree (tree config + * option) + */ + private HistoryTreeStub setupSmallTree(int maxChildren) { HistoryTreeStub ht = null; try { File newFile = fTempFile; assertNotNull(newFile); HTConfig config = new HTConfig(newFile, BLOCK_SIZE, - 3, /* Number of children */ + maxChildren, /* Number of children */ 1, /* Provider version */ 1); /* Start time */ ht = new HistoryTreeStub(config); @@ -89,6 +98,13 @@ public class HistoryTreeTest { return ht; } + /** + * Setup a history tree with config MAX_CHILDREN = 3. + */ + private HistoryTreeStub setupSmallTree() { + return setupSmallTree(3); + } + private static long fillValues(HistoryTree ht, @NonNull TmfStateValue value, int nbValues, long start) { for (int i = 0; i < nbValues; i++) { ht.insertInterval(new HTInterval(start + i, start + i + 1, 1, value)); @@ -96,6 +112,35 @@ public class HistoryTreeTest { return start + nbValues; } + /** + * Insert intervals in the tree to fill the current leaf node to capacity, + * without exceeding it. + * + * This guarantees that the following insertion will create new nodes. + * + * @param ht + * The history tree in which to insert + * @return Start time of the current leaf node. Future insertions should be + * greater than or equal to this to make sure the intervals go in + * the leaf node. + */ + private static long fillNextLeafNode(HistoryTreeStub ht, long leafNodeStart) { + int prevCount = ht.getNodeCount(); + int prevDepth = ht.getDepth(); + + /* Fill the following leaf node */ + HTNode node = ht.getLatestLeaf(); + int nodeFreeSpace = node.getNodeFreeSpace(); + int nbIntervals = nodeFreeSpace / (HTInterval.DATA_ENTRY_SIZE + TEST_STRING.length() + STRING_PADDING); + long ret = fillValues(ht, STRING_VALUE, nbIntervals, leafNodeStart); + + /* Make sure we haven't changed the depth or node count */ + assertEquals(prevCount, ht.getNodeCount()); + assertEquals(prevDepth, ht.getDepth()); + + return ret; + } + /** * Test that nodes are filled * @@ -180,4 +225,88 @@ public class HistoryTreeTest { assertEquals(7, ht.getNodeCount()); assertEquals(3, ht.getDepth()); } + + /** + * Make sure the node sequence numbers and parent pointers are set correctly + * when new nodes are created. + * + *

+ * We are building a tree whose node sequence numbers will look like this at + * the end: + *

+ * + * 
+     *     3
+     *    / \
+     *   1   4
+     *  / \   \
+     * 0   2   5
+     *
+ * + *

+ * However while building, the parent pointers may be different. + *

+ * + * @throws ClosedChannelException + * If the test fails + */ + @Test + public void testNodeSequenceNumbers() throws ClosedChannelException { + /* Represents the start time of the current leaf node */ + long start = 1; + + HistoryTreeStub ht = setupSmallTree(2); + start = fillNextLeafNode(ht, start); + + List branch = ht.getLatestBranch(); + assertEquals(1, branch.size()); + assertEquals( 0, branch.get(0).getSequenceNumber()); + assertEquals(-1, branch.get(0).getParentSequenceNumber()); + + /* Create a new branch */ + start = fillValues(ht, STRING_VALUE, 1, start); + start = fillNextLeafNode(ht, start); + assertEquals(3, ht.getNodeCount()); + assertEquals(2, ht.getDepth()); + + /* Make sure the first node's parent was updated */ + HTNode node = ht.readNode(0); + assertEquals(0, node.getSequenceNumber()); + assertEquals(1, node.getParentSequenceNumber()); + + /* Make sure the new branch is alright */ + branch = ht.getLatestBranch(); + assertEquals(2, branch.size()); + assertEquals( 1, branch.get(0).getSequenceNumber()); + assertEquals(-1, branch.get(0).getParentSequenceNumber()); + assertEquals( 2, branch.get(1).getSequenceNumber()); + assertEquals( 1, branch.get(1).getParentSequenceNumber()); + + /* Create a third branch */ + start = fillValues(ht, STRING_VALUE, 1, start); + start = fillNextLeafNode(ht, start); + assertEquals(6, ht.getNodeCount()); + assertEquals(3, ht.getDepth()); + + /* Make sure all previous nodes are still correct */ + node = ht.readNode(0); + assertEquals(0, node.getSequenceNumber()); + assertEquals(1, node.getParentSequenceNumber()); + node = ht.readNode(1); + assertEquals(1, node.getSequenceNumber()); + assertEquals(3, node.getParentSequenceNumber()); + node = ht.readNode(2); + assertEquals(2, node.getSequenceNumber()); + assertEquals(1, node.getParentSequenceNumber()); + + /* Verify the contents of the new latest branch */ + branch = ht.getLatestBranch(); + assertEquals(3, branch.size()); + assertEquals( 3, branch.get(0).getSequenceNumber()); + assertEquals(-1, branch.get(0).getParentSequenceNumber()); + assertEquals( 4, branch.get(1).getSequenceNumber()); + assertEquals( 3, branch.get(1).getParentSequenceNumber()); + assertEquals( 5, branch.get(2).getSequenceNumber()); + assertEquals( 4, branch.get(2).getParentSequenceNumber()); + } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java index b26fd53e29..d783b7ac96 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompasss/statesystem/core/tests/stubs/backend/HistoryTreeStub.java @@ -44,6 +44,11 @@ public class HistoryTreeStub extends HistoryTree { super(conf); } + @Override + public List getLatestBranch() { + return checkNotNull(super.getLatestBranch()); + } + /** * Get the latest leaf of the tree * diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java index db8f9a2c0a..645b377420 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2010, 2014 Ericsson, École Polytechnique de Montréal, and others + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others * * All rights reserved. This program and the accompanying materials are * made available under the terms of the Eclipse Public License v1.0 which @@ -14,6 +14,7 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; import java.nio.ByteBuffer; +import java.util.Arrays; import java.util.concurrent.locks.ReentrantReadWriteLock; /** @@ -250,7 +251,8 @@ public final class CoreNode extends HTNode { @Override public String toStringSpecific() { /* Only used for debugging, shouldn't be externalized */ - return "Core Node, " + nbChildren + " children, "; //$NON-NLS-1$ //$NON-NLS-2$ + return String.format("Core Node, %d children %s", //$NON-NLS-1$ + nbChildren, Arrays.toString(Arrays.copyOf(children, nbChildren))); } } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java index 9013b89787..5a44cfd333 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2010, 2015 Ericsson, École Polytechnique de Montréal, and others + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others * * All rights reserved. This program and the accompanying materials are * made available under the terms of the Eclipse Public License v1.0 which @@ -620,18 +620,14 @@ public abstract class HTNode { @Override public String toString() { /* Only used for debugging, shouldn't be externalized */ - StringBuffer buf = new StringBuffer("Node #" + fSequenceNumber + ", "); - buf.append(toStringSpecific()); - buf.append(fIntervals.size() + " intervals (" + getNodeUsagePercent() - + "% used), "); - - buf.append("[" + fNodeStart + " - "); - if (fIsOnDisk) { - buf = buf.append("" + fNodeEnd + "]"); - } else { - buf = buf.append("...]"); - } - return buf.toString(); + return String.format("Node #%d, %s, %s, %d intervals (%d%% used), [%d - %s]", + fSequenceNumber, + (fParentSequenceNumber == -1) ? "Root" : "Parent #" + fParentSequenceNumber, + toStringSpecific(), + fIntervals.size(), + getNodeUsagePercent(), + fNodeStart, + (fIsOnDisk || fNodeEnd != 0) ? fNodeEnd : "..."); } /** diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java index 67d6a1f1d4..60374ba149 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTree.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2010, 2015 Ericsson, École Polytechnique de Montréal, and others + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others * * All rights reserved. This program and the accompanying materials are * made available under the terms of the Eclipse Public License v1.0 which @@ -579,7 +579,7 @@ public class HistoryTree { // Create new coreNode for (int i = 1; i < depth; i++) { CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); - CoreNode newNode = initNewCoreNode(prevNode.getParentSequenceNumber(), + CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); prevNode.linkNewChild(newNode); fLatestBranch.add(newNode); @@ -587,7 +587,7 @@ public class HistoryTree { // Create the new leafNode CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1); - LeafNode newNode = initNewLeafNode(prevNode.getParentSequenceNumber(), splitTime + 1); + LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); prevNode.linkNewChild(newNode); fLatestBranch.add(newNode); } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/LeafNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/LeafNode.java index 4cc3c70ab4..d4cecf39d8 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/LeafNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/LeafNode.java @@ -1,5 +1,5 @@ /******************************************************************************* - * Copyright (c) 2014 École Polytechnique de Montréal + * Copyright (c) 2014, 2016 École Polytechnique de Montréal and others * * All rights reserved. This program and the accompanying materials are * made available under the terms of the Eclipse Public License v1.0 which @@ -65,7 +65,7 @@ public final class LeafNode extends HTNode { @Override public String toStringSpecific() { /* Only used for debugging, shouldn't be externalized */ - return "Leaf Node, "; //$NON-NLS-1$; + return "Leaf Node"; //$NON-NLS-1$; } } -- 2.34.1