statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java

   1 /*******************************************************************************
   2  * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others
   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  * Contributors:
  10  *   Alexandre Montplaisir - Initial API and implementation
  11  *   Florian Wininger - Add Extension and Leaf Node
  12  *   Patrick Tasse - Add message to exceptions
  13  *******************************************************************************/
  14
  15 package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree;
  16
  17 import java.io.File;
  18 import java.io.FileInputStream;
  19 import java.io.IOException;
  20 import java.nio.ByteBuffer;
  21 import java.nio.ByteOrder;
  22 import java.nio.channels.ClosedChannelException;
  23 import java.nio.channels.FileChannel;
  24 import java.util.ArrayList;
  25 import java.util.Collections;
  26 import java.util.List;
  27
  28 import org.eclipse.jdt.annotation.NonNull;
  29 import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder;
  30 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  31
  32 import com.google.common.annotations.VisibleForTesting;
  33 import com.google.common.collect.ImmutableList;
  34
  35 /**
  36  * Meta-container for the History Tree. This structure contains all the
  37  * high-level data relevant to the tree.
  38  *
  39  * @author Alexandre Montplaisir
  40  */
  41 public class HistoryTreeClassic implements IHistoryTree {
  42
  43     /**
  44      * The magic number for this file format. Package-private for the factory
  45      * class.
  46      */
  47     static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900;
  48
  49     /** File format version. Increment when breaking compatibility. */
  50     private static final int FILE_VERSION = 7;
  51
  52     // ------------------------------------------------------------------------
  53     // Tree-specific configuration
  54     // ------------------------------------------------------------------------
  55
  56     /** Container for all the configuration constants */
  57     private final HTConfig fConfig;
  58
  59     /** Reader/writer object */
  60     private final @NonNull HT_IO fTreeIO;
  61
  62     // ------------------------------------------------------------------------
  63     // Variable Fields (will change throughout the existence of the SHT)
  64     // ------------------------------------------------------------------------
  65
  66     /** Latest timestamp found in the tree (at any given moment) */
  67     private long fTreeEnd;
  68
  69     /** The total number of nodes that exists in this tree */
  70     private int fNodeCount;
  71
  72     /** "Cache" to keep the active nodes in memory */
  73     private final @NonNull List<@NonNull HTNode> fLatestBranch;
  74
  75     // ------------------------------------------------------------------------
  76     // Constructors/"Destructors"
  77     // ------------------------------------------------------------------------
  78
  79     /**
  80      * Create a new State History from scratch, using a {@link HTConfig} object
  81      * for configuration.
  82      *
  83      * @param conf
  84      *            The config to use for this History Tree.
  85      * @throws IOException
  86      *             If an error happens trying to open/write to the file
  87      *             specified in the config
  88      */
  89     public HistoryTreeClassic(HTConfig conf) throws IOException {
  90         /*
  91          * Simple check to make sure we have enough place in the 0th block for
  92          * the tree configuration
  93          */
  94         if (conf.getBlockSize() < TREE_HEADER_SIZE) {
  95             throw new IllegalArgumentException();
  96         }
  97
  98         fConfig = conf;
  99         fTreeEnd = conf.getTreeStart();
 100         fNodeCount = 0;
 101         fLatestBranch = Collections.synchronizedList(new ArrayList<>());
 102
 103         /* Prepare the IO object */
 104         fTreeIO = new HT_IO(fConfig, true);
 105
 106         /* Add the first node to the tree */
 107         LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart());
 108         fLatestBranch.add(firstNode);
 109     }
 110
 111     /**
 112      * "Reader" constructor : instantiate a SHTree from an existing tree file on
 113      * disk
 114      *
 115      * @param existingStateFile
 116      *            Path/filename of the history-file we are to open
 117      * @param expProviderVersion
 118      *            The expected version of the state provider
 119      * @throws IOException
 120      *             If an error happens reading the file
 121      */
 122     public HistoryTreeClassic(File existingStateFile, int expProviderVersion) throws IOException {
 123         /*
 124          * Open the file ourselves, get the tree header information we need,
 125          * then pass on the descriptor to the TreeIO object.
 126          */
 127         int rootNodeSeqNb, res;
 128         int bs, maxc;
 129         long startTime;
 130
 131         /* Java I/O mumbo jumbo... */
 132         if (!existingStateFile.exists()) {
 133             throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
 134         }
 135         if (existingStateFile.length() <= 0) {
 136             throw new IOException("Empty target file"); //$NON-NLS-1$
 137         }
 138
 139         try (FileInputStream fis = new FileInputStream(existingStateFile);
 140                 FileChannel fc = fis.getChannel();) {
 141
 142             ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE);
 143
 144             buffer.order(ByteOrder.LITTLE_ENDIAN);
 145             buffer.clear();
 146             fc.read(buffer);
 147             buffer.flip();
 148
 149             /*
 150              * Check the magic number to make sure we're opening the right type
 151              * of file
 152              */
 153             res = buffer.getInt();
 154             if (res != HISTORY_FILE_MAGIC_NUMBER) {
 155                 throw new IOException("Wrong magic number"); //$NON-NLS-1$
 156             }
 157
 158             res = buffer.getInt(); /* File format version number */
 159             if (res != FILE_VERSION) {
 160                 throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$
 161             }
 162
 163             res = buffer.getInt(); /* Event handler's version number */
 164             if (res != expProviderVersion &&
 165                     expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) {
 166                 /*
 167                  * The existing history was built using an event handler that
 168                  * doesn't match the current one in the framework.
 169                  *
 170                  * Information could be all wrong. Instead of keeping an
 171                  * incorrect history file, a rebuild is done.
 172                  */
 173                 throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$
 174             }
 175
 176             bs = buffer.getInt(); /* Block Size */
 177             maxc = buffer.getInt(); /* Max nb of children per node */
 178
 179             fNodeCount = buffer.getInt();
 180             rootNodeSeqNb = buffer.getInt();
 181             startTime = buffer.getLong();
 182
 183             fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime);
 184         }
 185
 186         /*
 187          * FIXME We close fis here and the TreeIO will then reopen the same
 188          * file, not extremely elegant. But how to pass the information here to
 189          * the SHT otherwise?
 190          */
 191         fTreeIO = new HT_IO(fConfig, false);
 192
 193         fLatestBranch = buildLatestBranch(rootNodeSeqNb);
 194         fTreeEnd = getRootNode().getNodeEnd();
 195
 196         /*
 197          * Make sure the history start time we read previously is consistent
 198          * with was is actually in the root node.
 199          */
 200         if (startTime != getRootNode().getNodeStart()) {
 201             throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
 202                     "history file, it might be corrupted."); //$NON-NLS-1$
 203         }
 204     }
 205
 206     /**
 207      * Rebuild the latestBranch "cache" object by reading the nodes from disk
 208      * (When we are opening an existing file on disk and want to append to it,
 209      * for example).
 210      *
 211      * @param rootNodeSeqNb
 212      *            The sequence number of the root node, so we know where to
 213      *            start
 214      * @throws ClosedChannelException
 215      */
 216     private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException {
 217         List<@NonNull HTNode> list = new ArrayList<>();
 218
 219         HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb);
 220         list.add(nextChildNode);
 221
 222         /* Follow the last branch up to the leaf */
 223         while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) {
 224             nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild());
 225             list.add(nextChildNode);
 226         }
 227         return Collections.synchronizedList(list);
 228     }
 229
 230     @Override
 231     public void closeTree(long requestedEndTime) {
 232         /* This is an important operation, queries can wait */
 233         synchronized (fLatestBranch) {
 234             /*
 235              * Work-around the "empty branches" that get created when the root
 236              * node becomes full. Overwrite the tree's end time with the
 237              * original wanted end-time, to ensure no queries are sent into
 238              * those empty nodes.
 239              *
 240              * This won't be needed once extended nodes are implemented.
 241              */
 242             fTreeEnd = requestedEndTime;
 243
 244             /* Close off the latest branch of the tree */
 245             for (int i = 0; i < fLatestBranch.size(); i++) {
 246                 fLatestBranch.get(i).closeThisNode(fTreeEnd);
 247                 fTreeIO.writeNode(fLatestBranch.get(i));
 248             }
 249
 250             try (FileChannel fc = fTreeIO.getFcOut();) {
 251                 ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE);
 252                 buffer.order(ByteOrder.LITTLE_ENDIAN);
 253                 buffer.clear();
 254
 255                 /* Save the config of the tree to the header of the file */
 256                 fc.position(0);
 257
 258                 buffer.putInt(HISTORY_FILE_MAGIC_NUMBER);
 259
 260                 buffer.putInt(FILE_VERSION);
 261                 buffer.putInt(fConfig.getProviderVersion());
 262
 263                 buffer.putInt(fConfig.getBlockSize());
 264                 buffer.putInt(fConfig.getMaxChildren());
 265
 266                 buffer.putInt(fNodeCount);
 267
 268                 /* root node seq. nb */
 269                 buffer.putInt(fLatestBranch.get(0).getSequenceNumber());
 270
 271                 /* start time of this history */
 272                 buffer.putLong(fLatestBranch.get(0).getNodeStart());
 273
 274                 buffer.flip();
 275                 int res = fc.write(buffer);
 276                 assert (res <= TREE_HEADER_SIZE);
 277                 /* done writing the file header */
 278
 279             } catch (IOException e) {
 280                 /*
 281                  * If we were able to write so far, there should not be any
 282                  * problem at this point...
 283                  */
 284                 throw new RuntimeException("State system write error"); //$NON-NLS-1$
 285             }
 286         }
 287     }
 288
 289     // ------------------------------------------------------------------------
 290     // Accessors
 291     // ------------------------------------------------------------------------
 292
 293     @Override
 294     public long getTreeStart() {
 295         return fConfig.getTreeStart();
 296     }
 297
 298     @Override
 299     public long getTreeEnd() {
 300         return fTreeEnd;
 301     }
 302
 303     @Override
 304     public int getNodeCount() {
 305         return fNodeCount;
 306     }
 307
 308     @Override
 309     public HTNode getRootNode() {
 310         return fLatestBranch.get(0);
 311     }
 312
 313     /**
 314      * Return the latest branch of the tree. That branch is immutable. Used for
 315      * unit testing and debugging.
 316      *
 317      * @return The immutable latest branch
 318      */
 319     @VisibleForTesting
 320     protected List<@NonNull HTNode> getLatestBranch() {
 321         return ImmutableList.copyOf(fLatestBranch);
 322     }
 323
 324     /**
 325      * Read a node at sequence number
 326      *
 327      * @param seqNum
 328      *            The sequence number of the node to read
 329      * @return The HTNode object
 330      * @throws ClosedChannelException
 331      *             Exception thrown when reading the node
 332      */
 333     @VisibleForTesting
 334     protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException {
 335         // First, check in the latest branch if the node is there
 336         for (HTNode node : fLatestBranch) {
 337             if (node.getSequenceNumber() == seqNum) {
 338                 return node;
 339             }
 340         }
 341         return fTreeIO.readNode(seqNum);
 342     }
 343
 344     /**
 345      * Retrieve the TreeIO object. Should only be used for testing.
 346      *
 347      * @return The TreeIO
 348      */
 349     @VisibleForTesting
 350     protected @NonNull HT_IO getTreeIO() {
 351         return fTreeIO;
 352     }
 353
 354     // ------------------------------------------------------------------------
 355     // HT_IO interface
 356     // ------------------------------------------------------------------------
 357
 358     @Override
 359     public FileInputStream supplyATReader() {
 360         return fTreeIO.supplyATReader(getNodeCount());
 361     }
 362
 363     @Override
 364     public File supplyATWriterFile() {
 365         return fConfig.getStateFile();
 366     }
 367
 368     @Override
 369     public long supplyATWriterFilePos() {
 370         return IHistoryTree.TREE_HEADER_SIZE
 371                 + ((long) getNodeCount() * fConfig.getBlockSize());
 372     }
 373
 374     @Override
 375     public HTNode readNode(int seqNumber) throws ClosedChannelException {
 376         /* Try to read the node from memory */
 377         synchronized (fLatestBranch) {
 378             for (HTNode node : fLatestBranch) {
 379                 if (node.getSequenceNumber() == seqNumber) {
 380                     return node;
 381                 }
 382             }
 383         }
 384
 385         /* Read the node from disk */
 386         return fTreeIO.readNode(seqNumber);
 387     }
 388
 389     @Override
 390     public void writeNode(HTNode node) {
 391         fTreeIO.writeNode(node);
 392     }
 393
 394     @Override
 395     public void closeFile() {
 396         fTreeIO.closeFile();
 397     }
 398
 399     @Override
 400     public void deleteFile() {
 401         fTreeIO.deleteFile();
 402     }
 403
 404     // ------------------------------------------------------------------------
 405     // Operations
 406     // ------------------------------------------------------------------------
 407
 408     @Override
 409     public void insertInterval(HTInterval interval) throws TimeRangeException {
 410         if (interval.getStartTime() < fConfig.getTreeStart()) {
 411             throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$
 412         }
 413         tryInsertAtNode(interval, fLatestBranch.size() - 1);
 414     }
 415
 416     /**
 417      * Inner method to find in which node we should add the interval.
 418      *
 419      * @param interval
 420      *            The interval to add to the tree
 421      * @param indexOfNode
 422      *            The index *in the latestBranch* where we are trying the
 423      *            insertion
 424      */
 425     private void tryInsertAtNode(HTInterval interval, int indexOfNode) {
 426         HTNode targetNode = fLatestBranch.get(indexOfNode);
 427
 428         /* Verify if there is enough room in this node to store this interval */
 429         if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) {
 430             /* Nope, not enough room. Insert in a new sibling instead. */
 431             addSiblingNode(indexOfNode);
 432             tryInsertAtNode(interval, fLatestBranch.size() - 1);
 433             return;
 434         }
 435
 436         /* Make sure the interval time range fits this node */
 437         if (interval.getStartTime() < targetNode.getNodeStart()) {
 438             /*
 439              * No, this interval starts before the startTime of this node. We
 440              * need to check recursively in parents if it can fit.
 441              */
 442             tryInsertAtNode(interval, indexOfNode - 1);
 443             return;
 444         }
 445
 446         /*
 447          * Ok, there is room, and the interval fits in this time slot. Let's add
 448          * it.
 449          */
 450         targetNode.addInterval(interval);
 451
 452         /* Update treeEnd if needed */
 453         if (interval.getEndTime() > fTreeEnd) {
 454             fTreeEnd = interval.getEndTime();
 455         }
 456     }
 457
 458     /**
 459      * Method to add a sibling to any node in the latest branch. This will add
 460      * children back down to the leaf level, if needed.
 461      *
 462      * @param indexOfNode
 463      *            The index in latestBranch where we start adding
 464      */
 465     private void addSiblingNode(int indexOfNode) {
 466         synchronized (fLatestBranch) {
 467             final long splitTime = fTreeEnd;
 468
 469             if (indexOfNode >= fLatestBranch.size()) {
 470                 /*
 471                  * We need to make sure (indexOfNode - 1) doesn't get the last
 472                  * node in the branch, because that one is a Leaf Node.
 473                  */
 474                 throw new IllegalStateException();
 475             }
 476
 477             /* Check if we need to add a new root node */
 478             if (indexOfNode == 0) {
 479                 addNewRootNode();
 480                 return;
 481             }
 482
 483             /* Check if we can indeed add a child to the target parent */
 484             if (((CoreNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) {
 485                 /* If not, add a branch starting one level higher instead */
 486                 addSiblingNode(indexOfNode - 1);
 487                 return;
 488             }
 489
 490             /* Split off the new branch from the old one */
 491             for (int i = indexOfNode; i < fLatestBranch.size(); i++) {
 492                 fLatestBranch.get(i).closeThisNode(splitTime);
 493                 fTreeIO.writeNode(fLatestBranch.get(i));
 494
 495                 CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1);
 496                 HTNode newNode;
 497
 498                 switch (fLatestBranch.get(i).getNodeType()) {
 499                 case CORE:
 500                     newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1);
 501                     break;
 502                 case LEAF:
 503                     newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1);
 504                     break;
 505                 default:
 506                     throw new IllegalStateException();
 507                 }
 508
 509                 prevNode.linkNewChild(newNode);
 510                 fLatestBranch.set(i, newNode);
 511             }
 512         }
 513     }
 514
 515     /**
 516      * Similar to the previous method, except here we rebuild a completely new
 517      * latestBranch
 518      */
 519     private void addNewRootNode() {
 520         final long splitTime = fTreeEnd;
 521
 522         HTNode oldRootNode = fLatestBranch.get(0);
 523         CoreNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart());
 524
 525         /* Tell the old root node that it isn't root anymore */
 526         oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber());
 527
 528         /* Close off the whole current latestBranch */
 529
 530         for (int i = 0; i < fLatestBranch.size(); i++) {
 531             fLatestBranch.get(i).closeThisNode(splitTime);
 532             fTreeIO.writeNode(fLatestBranch.get(i));
 533         }
 534
 535         /* Link the new root to its first child (the previous root node) */
 536         newRootNode.linkNewChild(oldRootNode);
 537
 538         /* Rebuild a new latestBranch */
 539         int depth = fLatestBranch.size();
 540         fLatestBranch.clear();
 541         fLatestBranch.add(newRootNode);
 542
 543         // Create new coreNode
 544         for (int i = 1; i < depth; i++) {
 545             CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1);
 546             CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(),
 547                     splitTime + 1);
 548             prevNode.linkNewChild(newNode);
 549             fLatestBranch.add(newNode);
 550         }
 551
 552         // Create the new leafNode
 553         CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1);
 554         LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1);
 555         prevNode.linkNewChild(newNode);
 556         fLatestBranch.add(newNode);
 557     }
 558
 559     /**
 560      * Add a new empty core node to the tree.
 561      *
 562      * @param parentSeqNumber
 563      *            Sequence number of this node's parent
 564      * @param startTime
 565      *            Start time of the new node
 566      * @return The newly created node
 567      */
 568     private @NonNull CoreNode initNewCoreNode(int parentSeqNumber, long startTime) {
 569         CoreNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber,
 570                 startTime);
 571         fNodeCount++;
 572         return newNode;
 573     }
 574
 575     /**
 576      * Add a new empty leaf node to the tree.
 577      *
 578      * @param parentSeqNumber
 579      *            Sequence number of this node's parent
 580      * @param startTime
 581      *            Start time of the new node
 582      * @return The newly created node
 583      */
 584     private @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) {
 585         LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber,
 586                 startTime);
 587         fNodeCount++;
 588         return newNode;
 589     }
 590
 591     @Override
 592     public HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException {
 593         assert (currentNode.getNbChildren() > 0);
 594         int potentialNextSeqNb = currentNode.getSequenceNumber();
 595
 596         for (int i = 0; i < currentNode.getNbChildren(); i++) {
 597             if (t >= currentNode.getChildStart(i)) {
 598                 potentialNextSeqNb = currentNode.getChild(i);
 599             } else {
 600                 break;
 601             }
 602         }
 603
 604         /*
 605          * Once we exit this loop, we should have found a children to follow. If
 606          * we didn't, there's a problem.
 607          */
 608         if (potentialNextSeqNb == currentNode.getSequenceNumber()) {
 609             throw new IllegalStateException("No next child node found"); //$NON-NLS-1$
 610         }
 611
 612         /*
 613          * Since this code path is quite performance-critical, avoid iterating
 614          * through the whole latestBranch array if we know for sure the next
 615          * node has to be on disk
 616          */
 617         if (currentNode.isOnDisk()) {
 618             return fTreeIO.readNode(potentialNextSeqNb);
 619         }
 620         return readNode(potentialNextSeqNb);
 621     }
 622
 623     @Override
 624     public long getFileSize() {
 625         return fConfig.getStateFile().length();
 626     }
 627
 628     // ------------------------------------------------------------------------
 629     // Test/debugging methods
 630     // ------------------------------------------------------------------------
 631
 632     /* Only used for debugging, shouldn't be externalized */
 633     @SuppressWarnings("nls")
 634     @Override
 635     public String toString() {
 636         return "Information on the current tree:\n\n" + "Blocksize: "
 637                 + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: "
 638                 + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount
 639                 + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n"
 640                 + "Size of the treefile: " + getFileSize() + "\n"
 641                 + "Root node has sequence number: "
 642                 + fLatestBranch.get(0).getSequenceNumber() + "\n"
 643                 + "'Latest leaf' has sequence number: "
 644                 + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber();
 645     }
 646
 647 }