org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/historytree/HistoryTree.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012 Ericsson
   3  * Copyright (c) 2010, 2011 École Polytechnique de Montréal
   4  * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
   5  *
   6  * All rights reserved. This program and the accompanying materials are
   7  * made available under the terms of the Eclipse Public License v1.0 which
   8  * accompanies this distribution, and is available at
   9  * http://www.eclipse.org/legal/epl-v10.html
  10  *
  11  *******************************************************************************/
  12
  13 package org.eclipse.linuxtools.internal.tmf.core.statesystem.backends.historytree;
  14
  15 import java.io.File;
  16 import java.io.FileInputStream;
  17 import java.io.IOException;
  18 import java.io.PrintWriter;
  19 import java.nio.ByteBuffer;
  20 import java.nio.ByteOrder;
  21 import java.nio.channels.ClosedChannelException;
  22 import java.nio.channels.FileChannel;
  23 import java.util.Vector;
  24
  25 import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException;
  26
  27 /**
  28  * Meta-container for the History Tree. This structure contains all the
  29  * high-level data relevant to the tree.
  30  *
  31  * @author alexmont
  32  *
  33  */
  34 class HistoryTree {
  35
  36     private static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900;
  37
  38     /*
  39      * File format version. Increment minor on backwards-compatible changes.
  40      * Increment major + set minor back to 0 when breaking compatibility.
  41      */
  42     private static final int MAJOR_VERSION = 3;
  43     private static final byte MINOR_VERSION = 0;
  44
  45     // ------------------------------------------------------------------------
  46     // Tree-specific configuration
  47     // ------------------------------------------------------------------------
  48
  49     /** Container for all the configuration constants */
  50     protected final HTConfig config;
  51
  52     /** Reader/writer object */
  53     private final HT_IO treeIO;
  54
  55     // ------------------------------------------------------------------------
  56     // Variable Fields (will change throughout the existance of the SHT)
  57     // ------------------------------------------------------------------------
  58
  59     /** Latest timestamp found in the tree (at any given moment) */
  60     private long treeEnd;
  61
  62     /** How many nodes exist in this tree, total */
  63     private int nodeCount;
  64
  65     /** "Cache" to keep the active nodes in memory */
  66     protected Vector<CoreNode> latestBranch;
  67
  68     // ------------------------------------------------------------------------
  69     // Constructors/"Destructors"
  70     // ------------------------------------------------------------------------
  71
  72     /**
  73      * Create a new State History from scratch, using a SHTConfig object for
  74      * configuration
  75      */
  76     private HistoryTree(HTConfig conf) throws IOException {
  77         /*
  78          * Simple check to make sure we have enough place in the 0th block
  79          * for the tree configuration
  80          */
  81         if (conf.blockSize < getTreeHeaderSize()) {
  82             throw new IllegalArgumentException();
  83         }
  84
  85         config = conf;
  86         treeEnd = conf.treeStart;
  87         nodeCount = 0;
  88         latestBranch = new Vector<CoreNode>();
  89
  90         /* Prepare the IO object */
  91         treeIO = new HT_IO(this, true);
  92
  93         /* Add the first node to the tree */
  94         CoreNode firstNode = initNewCoreNode(-1, conf.treeStart);
  95         latestBranch.add(firstNode);
  96     }
  97
  98     /**
  99      * "New State History" constructor, which doesn't use HTConfig but the
 100      * individual values separately. Kept for now for backwards compatibility,
 101      * but you should definitely consider using SHTConfig instead (since its
 102      * contents can then change without directly affecting SHT's API).
 103      */
 104     @Deprecated
 105     HistoryTree(File newStateFile, int blockSize, int maxChildren,
 106             long startTime) throws IOException {
 107         this(new HTConfig(newStateFile, blockSize, maxChildren, startTime));
 108     }
 109
 110     /**
 111      * "Reader" constructor : instantiate a SHTree from an existing tree file on
 112      * disk
 113      *
 114      * @param existingFileName
 115      *            Path/filename of the history-file we are to open
 116      * @throws IOException
 117      */
 118     HistoryTree(File existingStateFile) throws IOException {
 119         /*
 120          * Open the file ourselves, get the tree header information we need,
 121          * then pass on the descriptor to the TreeIO object.
 122          */
 123         int rootNodeSeqNb, res;
 124         int bs, maxc;
 125         long startTime;
 126
 127         /* Java I/O mumbo jumbo... */
 128         if (!existingStateFile.exists()) {
 129             throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
 130         }
 131         if (existingStateFile.length() <= 0) {
 132             throw new IOException("Invalid state file selected, " + //$NON-NLS-1$
 133                     "target file is empty"); //$NON-NLS-1$
 134         }
 135
 136         FileInputStream fis = new FileInputStream(existingStateFile);
 137         ByteBuffer buffer = ByteBuffer.allocate(getTreeHeaderSize());
 138         FileChannel fc = fis.getChannel();
 139         buffer.order(ByteOrder.LITTLE_ENDIAN);
 140         buffer.clear();
 141         fc.read(buffer);
 142         buffer.flip();
 143
 144         /*
 145          * Check the magic number,to make sure we're opening the right type of
 146          * file
 147          */
 148         res = buffer.getInt();
 149         if (res != HISTORY_FILE_MAGIC_NUMBER) {
 150             fc.close();
 151             fis.close();
 152             throw new IOException("Selected file does not" + //$NON-NLS-1$
 153                     "look like a History Tree file"); //$NON-NLS-1$
 154         }
 155
 156         res = buffer.getInt(); /* Major version number */
 157         if (res != MAJOR_VERSION) {
 158             fc.close();
 159             fis.close();
 160             throw new IOException("Select History Tree file is of an older " //$NON-NLS-1$
 161                     + "format. Please use a previous version of " //$NON-NLS-1$
 162                     + "the parser to open it."); //$NON-NLS-1$
 163         }
 164
 165         res = buffer.getInt(); /* Minor version number */
 166
 167         bs = buffer.getInt(); /* Block Size */
 168         maxc = buffer.getInt(); /* Max nb of children per node */
 169
 170         this.nodeCount = buffer.getInt();
 171         rootNodeSeqNb = buffer.getInt();
 172         startTime = buffer.getLong();
 173
 174         this.config = new HTConfig(existingStateFile, bs, maxc, startTime);
 175         fc.close();
 176         fis.close();
 177         /*
 178          * FIXME We close fis here and the TreeIO will then reopen the same
 179          * file, not extremely elegant. But how to pass the information here to
 180          * the SHT otherwise?
 181          */
 182         this.treeIO = new HT_IO(this, false);
 183
 184         rebuildLatestBranch(rootNodeSeqNb);
 185         this.treeEnd = latestBranch.firstElement().getNodeEnd();
 186
 187         /*
 188          * Make sure the history start time we read previously is consistent
 189          * with was is actually in the root node.
 190          */
 191         if (startTime != latestBranch.firstElement().getNodeStart()) {
 192             fc.close();
 193             fis.close();
 194             throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
 195                     "history file, it might be corrupted."); //$NON-NLS-1$
 196         }
 197     }
 198
 199     /**
 200      * "Save" the tree to disk. This method will cause the treeIO object to
 201      * commit all nodes to disk and then return the RandomAccessFile descriptor
 202      * so the Tree object can save its configuration into the header of the
 203      * file.
 204      *
 205      * @param requestedEndTime
 206      */
 207     void closeTree(long requestedEndTime) {
 208         FileChannel fc;
 209         ByteBuffer buffer;
 210         int i, res;
 211
 212         /*
 213          * Work-around the "empty branches" that get created when the root node
 214          * becomes full. Overwrite the tree's end time with the original wanted
 215          * end-time, to ensure no queries are sent into those empty nodes.
 216          *
 217          * This won't be needed once extended nodes are implemented.
 218          */
 219         this.treeEnd = requestedEndTime;
 220
 221         /* Close off the latest branch of the tree */
 222         for (i = 0; i < latestBranch.size(); i++) {
 223             latestBranch.get(i).closeThisNode(treeEnd);
 224             treeIO.writeNode(latestBranch.get(i));
 225         }
 226
 227         /* Only use this for debugging purposes, it's VERY slow! */
 228         // this.checkIntegrity();
 229
 230         fc = treeIO.getFcOut();
 231         buffer = ByteBuffer.allocate(getTreeHeaderSize());
 232         buffer.order(ByteOrder.LITTLE_ENDIAN);
 233         buffer.clear();
 234
 235         /* Save the config of the tree to the header of the file */
 236         try {
 237             fc.position(0);
 238
 239             buffer.putInt(HISTORY_FILE_MAGIC_NUMBER);
 240
 241             buffer.putInt(MAJOR_VERSION);
 242             buffer.putInt(MINOR_VERSION);
 243
 244             buffer.putInt(config.blockSize);
 245             buffer.putInt(config.maxChildren);
 246
 247             buffer.putInt(nodeCount);
 248
 249             /* root node seq. nb */
 250             buffer.putInt(latestBranch.firstElement().getSequenceNumber());
 251
 252             /* start time of this history */
 253             buffer.putLong(latestBranch.firstElement().getNodeStart());
 254
 255             buffer.flip();
 256             res = fc.write(buffer);
 257             assert (res <= getTreeHeaderSize());
 258             /* done writing the file header */
 259
 260         } catch (IOException e) {
 261             /* We should not have any problems at this point... */
 262             e.printStackTrace();
 263         } finally {
 264             try {
 265                 fc.close();
 266             } catch (IOException e) {
 267                 e.printStackTrace();
 268             }
 269         }
 270         return;
 271     }
 272
 273     // ------------------------------------------------------------------------
 274     // Accessors
 275     // ------------------------------------------------------------------------
 276
 277     long getTreeStart() {
 278         return config.treeStart;
 279     }
 280
 281     long getTreeEnd() {
 282         return treeEnd;
 283     }
 284
 285     int getNodeCount() {
 286         return nodeCount;
 287     }
 288
 289     HT_IO getTreeIO() {
 290         return treeIO;
 291     }
 292
 293     // ------------------------------------------------------------------------
 294     // Operations
 295     // ------------------------------------------------------------------------
 296
 297     /**
 298      * Rebuild the latestBranch "cache" object by reading the nodes from disk
 299      * (When we are opening an existing file on disk and want to append to it,
 300      * for example).
 301      *
 302      * @param rootNodeSeqNb
 303      *            The sequence number of the root node, so we know where to
 304      *            start
 305      * @throws ClosedChannelException
 306      */
 307     private void rebuildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException {
 308         HTNode nextChildNode;
 309
 310         this.latestBranch = new Vector<CoreNode>();
 311
 312         nextChildNode = treeIO.readNodeFromDisk(rootNodeSeqNb);
 313         latestBranch.add((CoreNode) nextChildNode);
 314         while (latestBranch.lastElement().getNbChildren() > 0) {
 315             nextChildNode = treeIO.readNodeFromDisk(latestBranch.lastElement().getLatestChild());
 316             latestBranch.add((CoreNode) nextChildNode);
 317         }
 318     }
 319
 320     /**
 321      * Insert an interval in the tree
 322      *
 323      * @param interval
 324      */
 325     void insertInterval(HTInterval interval) throws TimeRangeException {
 326         if (interval.getStartTime() < config.treeStart) {
 327             throw new TimeRangeException();
 328         }
 329         tryInsertAtNode(interval, latestBranch.size() - 1);
 330     }
 331
 332     /**
 333      * Inner method to find in which node we should add the interval.
 334      *
 335      * @param interval
 336      *            The interval to add to the tree
 337      * @param indexOfNode
 338      *            The index *in the latestBranch* where we are trying the
 339      *            insertion
 340      */
 341     private void tryInsertAtNode(HTInterval interval, int indexOfNode) {
 342         HTNode targetNode = latestBranch.get(indexOfNode);
 343
 344         /* Verify if there is enough room in this node to store this interval */
 345         if (interval.getIntervalSize() > targetNode.getNodeFreeSpace()) {
 346             /* Nope, not enough room. Insert in a new sibling instead. */
 347             addSiblingNode(indexOfNode);
 348             tryInsertAtNode(interval, latestBranch.size() - 1);
 349             return;
 350         }
 351
 352         /* Make sure the interval time range fits this node */
 353         if (interval.getStartTime() < targetNode.getNodeStart()) {
 354             /*
 355              * No, this interval starts before the startTime of this node. We
 356              * need to check recursively in parents if it can fit.
 357              */
 358             assert (indexOfNode >= 1);
 359             tryInsertAtNode(interval, indexOfNode - 1);
 360             return;
 361         }
 362
 363         /*
 364          * Ok, there is room, and the interval fits in this time slot. Let's add
 365          * it.
 366          */
 367         targetNode.addInterval(interval);
 368
 369         /* Update treeEnd if needed */
 370         if (interval.getEndTime() > this.treeEnd) {
 371             this.treeEnd = interval.getEndTime();
 372         }
 373         return;
 374     }
 375
 376     /**
 377      * Method to add a sibling to any node in the latest branch. This will add
 378      * children back down to the leaf level, if needed.
 379      *
 380      * @param indexOfNode
 381      *            The index in latestBranch where we start adding
 382      */
 383     private void addSiblingNode(int indexOfNode) {
 384         int i;
 385         CoreNode newNode, prevNode;
 386         long splitTime = treeEnd;
 387
 388         assert (indexOfNode < latestBranch.size());
 389
 390         /* Check if we need to add a new root node */
 391         if (indexOfNode == 0) {
 392             addNewRootNode();
 393             return;
 394         }
 395
 396         /* Check if we can indeed add a child to the target parent */
 397         if (latestBranch.get(indexOfNode - 1).getNbChildren() == config.maxChildren) {
 398             /* If not, add a branch starting one level higher instead */
 399             addSiblingNode(indexOfNode - 1);
 400             return;
 401         }
 402
 403         /* Split off the new branch from the old one */
 404         for (i = indexOfNode; i < latestBranch.size(); i++) {
 405             latestBranch.get(i).closeThisNode(splitTime);
 406             treeIO.writeNode(latestBranch.get(i));
 407
 408             prevNode = latestBranch.get(i - 1);
 409             newNode = initNewCoreNode(prevNode.getSequenceNumber(),
 410                     splitTime + 1);
 411             prevNode.linkNewChild(newNode);
 412
 413             latestBranch.set(i, newNode);
 414         }
 415         return;
 416     }
 417
 418     /**
 419      * Similar to the previous method, except here we rebuild a completely new
 420      * latestBranch
 421      */
 422     private void addNewRootNode() {
 423         int i, depth;
 424         CoreNode oldRootNode, newRootNode, newNode, prevNode;
 425         long splitTime = this.treeEnd;
 426
 427         oldRootNode = latestBranch.firstElement();
 428         newRootNode = initNewCoreNode(-1, config.treeStart);
 429
 430         /* Tell the old root node that it isn't root anymore */
 431         oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber());
 432
 433         /* Close off the whole current latestBranch */
 434         for (i = 0; i < latestBranch.size(); i++) {
 435             latestBranch.get(i).closeThisNode(splitTime);
 436             treeIO.writeNode(latestBranch.get(i));
 437         }
 438
 439         /* Link the new root to its first child (the previous root node) */
 440         newRootNode.linkNewChild(oldRootNode);
 441
 442         /* Rebuild a new latestBranch */
 443         depth = latestBranch.size();
 444         latestBranch = new Vector<CoreNode>();
 445         latestBranch.add(newRootNode);
 446         for (i = 1; i < depth + 1; i++) {
 447             prevNode = latestBranch.get(i - 1);
 448             newNode = initNewCoreNode(prevNode.getParentSequenceNumber(),
 449                     splitTime + 1);
 450             prevNode.linkNewChild(newNode);
 451             latestBranch.add(newNode);
 452         }
 453     }
 454
 455     /**
 456      * Add a new empty node to the tree.
 457      *
 458      * @param parentSeqNumber
 459      *            Sequence number of this node's parent
 460      * @param startTime
 461      *            Start time of the new node
 462      * @return The newly created node
 463      */
 464     private CoreNode initNewCoreNode(int parentSeqNumber, long startTime) {
 465         CoreNode newNode = new CoreNode(this, this.nodeCount, parentSeqNumber,
 466                 startTime);
 467         this.nodeCount++;
 468
 469         /* Update the treeEnd if needed */
 470         if (startTime >= this.treeEnd) {
 471             this.treeEnd = startTime + 1;
 472         }
 473         return newNode;
 474     }
 475
 476     /**
 477      * Inner method to select the next child of the current node intersecting
 478      * the given timestamp. Useful for moving down the tree following one
 479      * branch.
 480      *
 481      * @param currentNode
 482      * @param t
 483      * @return The child node intersecting t
 484      * @throws ClosedChannelException
 485      *             If the file channel was closed while we were reading the tree
 486      */
 487     HTNode selectNextChild(CoreNode currentNode, long t) throws ClosedChannelException {
 488         assert (currentNode.getNbChildren() > 0);
 489         int potentialNextSeqNb = currentNode.getSequenceNumber();
 490
 491         for (int i = 0; i < currentNode.getNbChildren(); i++) {
 492             if (t >= currentNode.getChildStart(i)) {
 493                 potentialNextSeqNb = currentNode.getChild(i);
 494             } else {
 495                 break;
 496             }
 497         }
 498         /*
 499          * Once we exit this loop, we should have found a children to follow. If
 500          * we didn't, there's a problem.
 501          */
 502         assert (potentialNextSeqNb != currentNode.getSequenceNumber());
 503
 504         /*
 505          * Since this code path is quite performance-critical, avoid iterating
 506          * through the whole latestBranch array if we know for sure the next
 507          * node has to be on disk
 508          */
 509         if (currentNode.isDone()) {
 510             return treeIO.readNodeFromDisk(potentialNextSeqNb);
 511         }
 512         return treeIO.readNode(potentialNextSeqNb);
 513     }
 514
 515     /**
 516      * Helper function to get the size of the "tree header" in the tree-file The
 517      * nodes will use this offset to know where they should be in the file. This
 518      * should always be a multiple of 4K.
 519      */
 520     static int getTreeHeaderSize() {
 521         return 4096;
 522     }
 523
 524     long getFileSize() {
 525         return config.stateFile.length();
 526     }
 527
 528     // ------------------------------------------------------------------------
 529     // Test/debugging methods
 530     // ------------------------------------------------------------------------
 531
 532     /* Only used for debugging, shouldn't be externalized */
 533     @SuppressWarnings("nls")
 534     boolean checkNodeIntegrity(HTNode zenode) {
 535
 536         HTNode otherNode;
 537         CoreNode node;
 538         StringBuffer buf = new StringBuffer();
 539         boolean ret = true;
 540
 541         // FIXME /* Only testing Core Nodes for now */
 542         if (!(zenode instanceof CoreNode)) {
 543             return true;
 544         }
 545
 546         node = (CoreNode) zenode;
 547
 548         try {
 549             /*
 550              * Test that this node's start and end times match the start of the
 551              * first child and the end of the last child, respectively
 552              */
 553             if (node.getNbChildren() > 0) {
 554                 otherNode = treeIO.readNode(node.getChild(0));
 555                 if (node.getNodeStart() != otherNode.getNodeStart()) {
 556                     buf.append("Start time of node (" + node.getNodeStart() + ") "
 557                             + "does not match start time of first child " + "("
 558                             + otherNode.getNodeStart() + "), " + "node #"
 559                             + otherNode.getSequenceNumber() + ")\n");
 560                     ret = false;
 561                 }
 562                 if (node.isDone()) {
 563                     otherNode = treeIO.readNode(node.getLatestChild());
 564                     if (node.getNodeEnd() != otherNode.getNodeEnd()) {
 565                         buf.append("End time of node (" + node.getNodeEnd()
 566                                 + ") does not match end time of last child ("
 567                                 + otherNode.getNodeEnd() + ", node #"
 568                                 + otherNode.getSequenceNumber() + ")\n");
 569                         ret = false;
 570                     }
 571                 }
 572             }
 573
 574             /*
 575              * Test that the childStartTimes[] array matches the real nodes' start
 576              * times
 577              */
 578             for (int i = 0; i < node.getNbChildren(); i++) {
 579                 otherNode = treeIO.readNode(node.getChild(i));
 580                 if (otherNode.getNodeStart() != node.getChildStart(i)) {
 581                     buf.append("  Expected start time of child node #"
 582                             + node.getChild(i) + ": " + node.getChildStart(i)
 583                             + "\n" + "  Actual start time of node #"
 584                             + otherNode.getSequenceNumber() + ": "
 585                             + otherNode.getNodeStart() + "\n");
 586                     ret = false;
 587                 }
 588             }
 589
 590         } catch (ClosedChannelException e) {
 591             e.printStackTrace();
 592         }
 593
 594         if (!ret) {
 595             System.out.println("");
 596             System.out.println("SHT: Integrity check failed for node #"
 597                     + node.getSequenceNumber() + ":");
 598             System.out.println(buf.toString());
 599         }
 600         return ret;
 601     }
 602
 603     void checkIntegrity() {
 604         try {
 605             for (int i = 0; i < nodeCount; i++) {
 606                 checkNodeIntegrity(treeIO.readNode(i));
 607             }
 608         } catch (ClosedChannelException e) {
 609             e.printStackTrace();
 610         }
 611     }
 612
 613     /* Only used for debugging, shouldn't be externalized */
 614     @SuppressWarnings("nls")
 615     @Override
 616     public String toString() {
 617         return "Information on the current tree:\n\n" + "Blocksize: "
 618                 + config.blockSize + "\n" + "Max nb. of children per node: "
 619                 + config.maxChildren + "\n" + "Number of nodes: " + nodeCount
 620                 + "\n" + "Depth of the tree: " + latestBranch.size() + "\n"
 621                 + "Size of the treefile: " + this.getFileSize() + "\n"
 622                 + "Root node has sequence number: "
 623                 + latestBranch.firstElement().getSequenceNumber() + "\n"
 624                 + "'Latest leaf' has sequence number: "
 625                 + latestBranch.lastElement().getSequenceNumber();
 626     }
 627
 628     private int curDepth;
 629
 630     /**
 631      * Start at currentNode and print the contents of all its children, in
 632      * pre-order. Give the root node in parameter to visit the whole tree, and
 633      * have a nice overview.
 634      */
 635     @SuppressWarnings("nls")
 636     private void preOrderPrint(PrintWriter writer, boolean printIntervals,
 637             CoreNode currentNode) {
 638         /* Only used for debugging, shouldn't be externalized */
 639         int i, j;
 640         HTNode nextNode;
 641
 642         writer.println(currentNode.toString());
 643         if (printIntervals) {
 644             currentNode.debugPrintIntervals(writer);
 645         }
 646         curDepth++;
 647
 648         try {
 649             for (i = 0; i < currentNode.getNbChildren(); i++) {
 650                 nextNode = treeIO.readNode(currentNode.getChild(i));
 651                 assert (nextNode instanceof CoreNode); // TODO temporary
 652                 for (j = 0; j < curDepth - 1; j++) {
 653                     writer.print("  ");
 654                 }
 655                 writer.print("+-");
 656                 preOrderPrint(writer, printIntervals, (CoreNode) nextNode);
 657             }
 658         } catch (ClosedChannelException e) {
 659             e.printStackTrace();
 660         }
 661         curDepth--;
 662         return;
 663     }
 664
 665     /**
 666      * Print out the full tree for debugging purposes
 667      *
 668      * @param writer
 669      *            PrintWriter in which to write the output
 670      * @param printIntervals
 671      *            Says if you want to output the full interval information
 672      */
 673     void debugPrintFullTree(PrintWriter writer, boolean printIntervals) {
 674         /* Only used for debugging, shouldn't be externalized */
 675         curDepth = 0;
 676         this.preOrderPrint(writer, false, latestBranch.firstElement());
 677
 678         if (printIntervals) {
 679             writer.println("\nDetails of intervals:"); //$NON-NLS-1$
 680             curDepth = 0;
 681             this.preOrderPrint(writer, true, latestBranch.firstElement());
 682         }
 683         writer.println('\n');
 684     }
 685
 686 }