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