statesystem/org.eclipse.tracecompass.datastore.core.tests/src/org/eclipse/tracecompass/internal/provisional/datastore/core/historytree/AbstractHistoryTreeTestBase.java

   1 /*******************************************************************************
   2  * Copyright (c) 2017 É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.provisional.datastore.core.historytree;
  11
  12 import static org.junit.Assert.assertEquals;
  13 import static org.junit.Assert.assertNotNull;
  14 import static org.junit.Assert.assertTrue;
  15 import static org.junit.Assert.fail;
  16
  17 import java.io.File;
  18 import java.io.IOException;
  19 import java.nio.channels.ClosedChannelException;
  20 import java.util.ArrayList;
  21 import java.util.List;
  22
  23 import org.eclipse.jdt.annotation.Nullable;
  24 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.AbstractHistoryTree;
  25 import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.HTNode;
  26 import org.eclipse.tracecompass.internal.provisional.datastore.core.interval.IHTInterval;
  27 import org.junit.After;
  28 import org.junit.Before;
  29 import org.junit.Test;
  30
  31 /**
  32  * This is the base class for all history tree implementation tests. Specific
  33  * tree's tests can extend this class to have some basic tests.
  34  *
  35  * It tests the {@link AbstractHistoryTree} class. This test class will fill
  36  * nodes only with sequential objects, so that each extending test for trees
  37  * will have to add the tests and filling methods that correspond to their own
  38  * use cases.
  39  *
  40  * @author Geneviève Bastien
  41  * @param <E>
  42  *            The type of objects that will be saved in the tree
  43  * @param <N>
  44  *            The base type of the nodes of this tree
  45  */
  46 public abstract class AbstractHistoryTreeTestBase<E extends IHTInterval, N extends HTNode<E>> {
  47
  48     private @Nullable File fTempFile;
  49
  50     /**
  51      * Create the temporary file for this history tree
  52      */
  53     @Before
  54     public void setupTest() {
  55         try {
  56             fTempFile = File.createTempFile("tmpStateSystem", null);
  57         } catch (IOException e) {
  58             fail(e.getMessage());
  59         }
  60     }
  61
  62     /**
  63      * Delete the temporary history tree file after the test
  64      */
  65     @After
  66     public void cleanup() {
  67         if (fTempFile != null) {
  68             fTempFile.delete();
  69         }
  70     }
  71
  72     /**
  73      * Setup a history tree.
  74      *
  75      * @param maxChildren
  76      *            The max number of children per node in the tree (tree config
  77      *            option)
  78      * @param treeStart
  79      *            The start of the tree
  80      * @return The new history tree
  81      */
  82     protected AbstractHistoryTree<E, N> setupSmallTree(int maxChildren, long treeStart) {
  83         AbstractHistoryTree<E, N> ht = null;
  84         try {
  85             File newFile = fTempFile;
  86             assertNotNull(newFile);
  87
  88             ht = createHistoryTree(newFile,
  89                     HtTestUtils.BLOCKSIZE,
  90                     maxChildren, /* Number of children */
  91                     1, /* Provider version */
  92                     1); /* Start time */
  93
  94         } catch (IOException e) {
  95             fail(e.getMessage());
  96         }
  97
  98         assertNotNull(ht);
  99         return ht;
 100     }
 101
 102     /**
 103      * Create the history tree to test
 104      *
 105      * @param stateHistoryFile
 106      *            The name of the history file
 107      * @param blockSize
 108      *            The size of each "block" on disk in bytes. One node will
 109      *            always fit in one block. It should be at least 4096.
 110      * @param maxChildren
 111      *            The maximum number of children allowed per core (non-leaf)
 112      *            node.
 113      * @param providerVersion
 114      *            The version of the state provider. If a file already exists,
 115      *            and their versions match, the history file will not be rebuilt
 116      *            uselessly.
 117      * @param treeStart
 118      *            The start time of the history
 119      * @return The history tree stub
 120      * @throws IOException
 121      *             Any exception thrown by the history tree
 122      */
 123     protected abstract AbstractHistoryTree<E, N> createHistoryTree(File stateHistoryFile,
 124             int blockSize,
 125             int maxChildren,
 126             int providerVersion,
 127             long treeStart) throws IOException;
 128
 129     /**
 130      * "Reader" constructor : instantiate a history tree from an existing tree
 131      * file on disk
 132      *
 133      * @param existingStateFile
 134      *            Path/filename of the history-file we are to open
 135      * @param expProviderVersion
 136      *            The expected version of the state provider
 137      * @return The history tree stub
 138      * @throws IOException
 139      *             If an error happens reading the file
 140      */
 141     protected abstract AbstractHistoryTree<E, N> createHistoryTree(
 142             File existingStateFile,
 143             int expProviderVersion) throws IOException;
 144
 145     /**
 146      * Create an interval that fits in the tree with the given start/end time
 147      *
 148      * @param start
 149      *            The start time
 150      * @param end
 151      *            The end time
 152      * @return The object
 153      */
 154     protected abstract E createInterval(long start, long end);
 155
 156     /**
 157      * Create a reader history tree
 158      *
 159      * @return The history tree stub
 160      * @throws IOException
 161      *             If an error happened reading the file
 162      */
 163     protected final AbstractHistoryTree<E, N> createHistoryTreeReader() throws IOException {
 164         File tempFile = fTempFile;
 165         assertNotNull(tempFile);
 166         return createHistoryTree(tempFile, 1);
 167     }
 168
 169     /**
 170      * Setup a history tree with config MAX_CHILDREN = 3 and start time of 1
 171      *
 172      * @return A new history tree
 173      */
 174     protected AbstractHistoryTree<E, N> setupSmallTree() {
 175         return setupSmallTree(3, 1);
 176     }
 177
 178     /**
 179      * Add sequential elements to the history up to a certain size. Any element
 180      * that would go above the fixed limit should not be added
 181      *
 182      * @param ht
 183      *            The tree to which to add values
 184      * @param fillSize
 185      *            The limit on the size of the elements to add
 186      * @param start
 187      *            The start time of the values
 188      * @return The latest end time
 189      */
 190     protected abstract long fillValues(AbstractHistoryTree<E, N> ht, int fillSize, long start);
 191
 192     /**
 193      * Insert objects in the tree to fill the current leaf node to capacity,
 194      * without exceeding it.
 195      *
 196      * This guarantees that the following insertion will create new nodes.
 197      *
 198      * @param ht
 199      *            The history tree in which to insert
 200      * @return Start time of the current leaf node. Future insertions should be
 201      *         greater than or equal to this to make sure the intervals go in
 202      *         the leaf node.
 203      */
 204     private long fillNextLeafNode(AbstractHistoryTree<E, N> ht, long leafNodeStart) {
 205         int prevCount = ht.getNodeCount();
 206         int prevDepth = ht.getDepth();
 207
 208         /* Fill the following leaf node */
 209         N node = ht.getLatestLeaf();
 210         long ret = fillValues(ht, node.getNodeFreeSpace(), leafNodeStart);
 211
 212         /* Make sure we haven't changed the depth or node count */
 213         assertEquals(prevCount, ht.getNodeCount());
 214         assertEquals(prevDepth, ht.getDepth());
 215
 216         return ret;
 217     }
 218
 219     /**
 220      * Test that nodes are filled
 221      *
 222      * It fills nodes with sequential elements, so that leafs should be filled.
 223      */
 224     @Test
 225     public void testSequentialFill() {
 226         AbstractHistoryTree<E, N> ht = setupSmallTree();
 227
 228         // Make sure it is empty
 229         N node = ht.getLatestLeaf();
 230         assertEquals(0, node.getNodeUsagePercent());
 231
 232         /* Fill ~10% of the node with elements */
 233         int initialFreeSpace = node.getNodeFreeSpace();
 234         int limit = node.getNodeFreeSpace() / 10;
 235         long start = fillValues(ht, limit, 1);
 236         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - limit);
 237         assertTrue(node.getNodeFreeSpace() < initialFreeSpace);
 238
 239         /* Add elements up to ~20% */
 240         start = fillValues(ht, limit, start);
 241         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 2 * limit);
 242         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - limit);
 243
 244         /* Add elements up to ~30% */
 245         start = fillValues(ht, limit, start);
 246         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 3 * limit);
 247         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 2 * limit);
 248
 249         /* Add elements up to ~40% */
 250         start = fillValues(ht, limit, start);
 251         assertTrue(node.getNodeFreeSpace() > initialFreeSpace - 4 * limit);
 252         assertTrue(node.getNodeFreeSpace() < initialFreeSpace - 3 * limit);
 253
 254         // Assert the integrity of the tree
 255         ht.closeTree(ht.getTreeEnd());
 256         HtTestUtils.assertTreeIntegrity(ht);
 257
 258     }
 259
 260     /**
 261      * Test the addition of new nodes to the tree and make sure the tree is
 262      * built with the right structure
 263      */
 264     @Test
 265     public void testDepth() {
 266         AbstractHistoryTree<E, N> ht = setupSmallTree();
 267
 268         /* Fill a first node */
 269         N node = ht.getLatestLeaf();
 270         long start = 1;
 271         long time = fillValues(ht, node.getNodeFreeSpace(), start);
 272
 273         /*
 274          * Add intervals that should add a sibling to the node and a new root
 275          * node
 276          */
 277         assertEquals(1, ht.getNodeCount());
 278         assertEquals(1, ht.getDepth());
 279         ht.insert(createInterval(time, time + 1));
 280         time += 1;
 281         assertEquals(3, ht.getNodeCount());
 282         assertEquals(2, ht.getDepth());
 283
 284         /* Fill the latest leaf node (2nd child) */
 285         node = ht.getLatestLeaf();
 286         time = fillValues(ht, node.getNodeFreeSpace(), time);
 287
 288         /*
 289          * Add an interval that should add another sibling to the previous nodes
 290          */
 291         ht.insert(createInterval(time, time + 1));
 292         time += 1;
 293         assertEquals(4, ht.getNodeCount());
 294         assertEquals(2, ht.getDepth());
 295
 296         /* Fill the latest leaf node (3rd and last child) */
 297         node = ht.getLatestLeaf();
 298         time = fillValues(ht, node.getNodeFreeSpace(), time);
 299
 300         /* The new node created here should generate a new branch */
 301         ht.insert(createInterval(time, time + 1));
 302         time += 1;
 303         assertEquals(7, ht.getNodeCount());
 304         assertEquals(3, ht.getDepth());
 305
 306         /*
 307          * Completely fill the second level, such that there will be a 4th level
 308          * added
 309          */
 310         while (ht.getDepth() < 4) {
 311             time = fillNextLeafNode(ht, time);
 312             ht.insert(createInterval(time, time + 1));
 313         }
 314         assertEquals(4, ht.getDepth());
 315
 316         // Assert the integrity of the tree
 317         ht.closeTree(ht.getTreeEnd());
 318         HtTestUtils.assertTreeIntegrity(ht);
 319     }
 320
 321     /**
 322      * Make sure the node sequence numbers and parent pointers are set correctly
 323      * when new nodes are created.
 324      *
 325      * <p>
 326      * We are building a tree whose node sequence numbers will look like this at
 327      * the end:
 328      * </p>
 329      *
 330      * <pre>
 331      *     3
 332      *    / \
 333      *   1   4
 334      *  / \   \
 335      * 0   2   5
 336      * </pre>
 337      *
 338      * <p>
 339      * However while building, the parent pointers may be different.
 340      * </p>
 341      *
 342      * @throws ClosedChannelException
 343      *             If the file channel is closed
 344      */
 345     @Test
 346     public void testNodeSequenceNumbers() throws ClosedChannelException {
 347
 348         long time = 1;
 349
 350         AbstractHistoryTree<E, N> ht = setupSmallTree(2, time);
 351         time = fillNextLeafNode(ht, time);
 352
 353         /* There is only one node in the tree at this point, with no parent */
 354         List<N> branch = ht.getLatestBranch();
 355         assertEquals(1, branch.size());
 356         assertEquals(0, branch.get(0).getSequenceNumber());
 357         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 358
 359         /* Create a new branch */
 360         ht.insert(createInterval(time, time + 1));
 361         time = fillNextLeafNode(ht, time + 1);
 362         assertEquals(3, ht.getNodeCount());
 363         assertEquals(2, ht.getDepth());
 364
 365         /* Make sure the first node's parent was updated */
 366         N node = ht.getNode(0);
 367         assertEquals(0, node.getSequenceNumber());
 368         assertEquals(1, node.getParentSequenceNumber());
 369
 370         /* Make sure the new branch is all right */
 371         branch = ht.getLatestBranch();
 372         assertEquals(2, branch.size());
 373         assertEquals(1, branch.get(0).getSequenceNumber());
 374         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 375         assertEquals(2, branch.get(1).getSequenceNumber());
 376         assertEquals(1, branch.get(1).getParentSequenceNumber());
 377
 378         /* Create a third branch */
 379         ht.insert(createInterval(time, time + 1));
 380         time = fillNextLeafNode(ht, time + 1);
 381         assertEquals(6, ht.getNodeCount());
 382         assertEquals(3, ht.getDepth());
 383
 384         /* Make sure all previous nodes are still correct */
 385         node = ht.getNode(0);
 386         assertEquals(0, node.getSequenceNumber());
 387         assertEquals(1, node.getParentSequenceNumber());
 388         node = ht.getNode(1);
 389         assertEquals(1, node.getSequenceNumber());
 390         assertEquals(3, node.getParentSequenceNumber());
 391         node = ht.getNode(2);
 392         assertEquals(2, node.getSequenceNumber());
 393         assertEquals(1, node.getParentSequenceNumber());
 394
 395         /* Verify the contents of the new latest branch */
 396         branch = ht.getLatestBranch();
 397         assertEquals(3, branch.size());
 398         assertEquals(3, branch.get(0).getSequenceNumber());
 399         assertEquals(-1, branch.get(0).getParentSequenceNumber());
 400         assertEquals(4, branch.get(1).getSequenceNumber());
 401         assertEquals(3, branch.get(1).getParentSequenceNumber());
 402         assertEquals(5, branch.get(2).getSequenceNumber());
 403         assertEquals(4, branch.get(2).getParentSequenceNumber());
 404
 405         // Assert the integrity of the tree
 406         ht.closeTree(ht.getTreeEnd());
 407         HtTestUtils.assertTreeIntegrity(ht);
 408     }
 409
 410     /**
 411      * Test reading a tree and make sure it is identical to the original one
 412      *
 413      * <p>
 414      * We are building a tree whose node sequence numbers will look like this at
 415      * the end:
 416      * </p>
 417      *
 418      * <pre>
 419      *       4
 420      *     /   \
 421      *    1     5
 422      *  / | \    \
 423      * 0  2  3    6
 424      * </pre>
 425      *
 426      * @throws IOException
 427      *             Exceptions with the HT file
 428      *
 429      */
 430     @Test
 431     public void testReadTree() throws IOException {
 432
 433         long time = 1;
 434
 435         // Build the tree for the test
 436         AbstractHistoryTree<E, N> ht = setupSmallTree();
 437         time = fillNextLeafNode(ht, time);
 438
 439         /* Create a new branch */
 440         ht.insert(createInterval(time, time + 1));
 441         time = fillNextLeafNode(ht, time + 1);
 442
 443         /* Fill the third child */
 444         ht.insert(createInterval(time, time + 1));
 445         time = fillNextLeafNode(ht, time + 1);
 446
 447         /* Make sure the tree has the expected structure at this point */
 448         assertEquals(4, ht.getNodeCount());
 449         assertEquals(2, ht.getDepth());
 450
 451         /* Add the third branch */
 452         ht.insert(createInterval(time, time + 1));
 453         time = fillNextLeafNode(ht, time + 1);
 454
 455         /* Make sure the tree has the expected structure */
 456         assertEquals(7, ht.getNodeCount());
 457         assertEquals(3, ht.getDepth());
 458
 459         // Close the tree and save the nodes for later
 460         ht.closeTree(time + 1);
 461
 462         List<N> expectedNodes = new ArrayList<>(ht.getNodeCount());
 463         for (int i = 0; i < ht.getNodeCount(); i++) {
 464             expectedNodes.add(ht.getNode(i));
 465         }
 466         ht.closeFile();
 467
 468         // Create a reader history tree
 469         ht = createHistoryTreeReader();
 470
 471         // Make sure the number of nodes and depth is as expected
 472         assertEquals(7, ht.getNodeCount());
 473         assertEquals(3, ht.getDepth());
 474
 475         for (int i = 0; i < ht.getNodeCount(); i++) {
 476             assertEquals(expectedNodes.get(i), ht.readNode(i));
 477         }
 478
 479         // Assert the integrity of the read tree
 480         HtTestUtils.assertTreeIntegrity(ht);
 481     }
 482
 483     /**
 484      * Test the tree end time
 485      */
 486     @Test
 487     public void testTreeEnd() {
 488         long time = 1;
 489
 490         // Check the end time at the start
 491         AbstractHistoryTree<E, N> ht = setupSmallTree();
 492         assertEquals(time, ht.getTreeEnd());
 493
 494         // Fill a node and check the end
 495         time = fillNextLeafNode(ht, time);
 496         assertEquals(time, ht.getTreeEnd());
 497
 498         // Add an object that should not change the end time
 499         E object = createInterval(time - 10, time - 5);
 500         ht.insert(object);
 501         assertEquals(time, ht.getTreeEnd());
 502
 503         // Assert the tree integrity
 504         ht.closeTree(ht.getTreeEnd());
 505         HtTestUtils.assertTreeIntegrity(ht);
 506     }
 507
 508 }