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