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