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>
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
11 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.internal
.tmf
.core
.statesystem
.backends
.historytree
;
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
;
25 import org
.eclipse
.linuxtools
.tmf
.core
.exceptions
.TimeRangeException
;
28 * Meta-container for the History Tree. This structure contains all the
29 * high-level data relevant to the tree.
36 private static final int HISTORY_FILE_MAGIC_NUMBER
= 0x05FFA900;
39 * File format version. Increment minor on backwards-compatible changes.
40 * Increment major + set minor back to 0 when breaking compatibility.
42 private static final int MAJOR_VERSION
= 3;
43 private static final byte MINOR_VERSION
= 0;
46 * Tree-specific configuration
48 /* Container for all the configuration constants */
49 protected final HTConfig config
;
51 /* Reader/writer object */
52 private final HT_IO treeIO
;
55 * Variable Fields (will change throughout the existance of the SHT)
57 /* Latest timestamp found in the tree (at any given moment) */
60 /* How many nodes exist in this tree, total */
61 private int nodeCount
;
63 /* "Cache" to keep the active nodes in memory */
64 protected Vector
<CoreNode
> latestBranch
;
67 * Create a new State History from scratch, using a SHTConfig object for
73 private HistoryTree(HTConfig conf
) throws IOException
{
75 * Simple assertion to make sure we have enough place in the 0th block
76 * for the tree configuration
78 assert (conf
.blockSize
>= getTreeHeaderSize());
81 treeEnd
= conf
.treeStart
;
83 latestBranch
= new Vector
<CoreNode
>();
85 /* Prepare the IO object */
86 treeIO
= new HT_IO(this, true);
88 /* Add the first node to the tree */
89 CoreNode firstNode
= initNewCoreNode(-1, conf
.treeStart
);
90 latestBranch
.add(firstNode
);
94 * "New State History" constructor, which doesn't use SHTConfig but the
95 * individual values separately. Kept for now for backwards compatibility,
96 * but you should definitely consider using SHTConfig instead (since its
97 * contents can then change without directly affecting SHT's API).
99 HistoryTree(File newStateFile
, int blockSize
, int maxChildren
,
100 long startTime
) throws IOException
{
101 this(new HTConfig(newStateFile
, blockSize
, maxChildren
, startTime
));
105 * "Reader" constructor : instantiate a SHTree from an existing tree file on
108 * @param existingFileName
109 * Path/filename of the history-file we are to open
110 * @throws IOException
112 HistoryTree(File existingStateFile
) throws IOException
{
114 * Open the file ourselves, get the tree header information we need,
115 * then pass on the descriptor to the TreeIO object.
117 int rootNodeSeqNb
, res
;
121 /* Java I/O mumbo jumbo... */
122 if (!existingStateFile
.exists()) {
123 throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
125 if (existingStateFile
.length() <= 0) {
126 throw new IOException("Invalid state file selected, " + //$NON-NLS-1$
127 "target file is empty"); //$NON-NLS-1$
130 FileInputStream fis
= new FileInputStream(existingStateFile
);
131 ByteBuffer buffer
= ByteBuffer
.allocate(getTreeHeaderSize());
132 FileChannel fc
= fis
.getChannel();
133 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
139 * Check the magic number,to make sure we're opening the right type of
142 res
= buffer
.getInt();
143 if (res
!= HISTORY_FILE_MAGIC_NUMBER
) {
146 throw new IOException("Selected file does not" + //$NON-NLS-1$
147 "look like a History Tree file"); //$NON-NLS-1$
150 res
= buffer
.getInt(); /* Major version number */
151 if (res
!= MAJOR_VERSION
) {
154 throw new IOException("Select History Tree file is of an older " //$NON-NLS-1$
155 + "format. Please use a previous version of " //$NON-NLS-1$
156 + "the parser to open it."); //$NON-NLS-1$
159 res
= buffer
.getInt(); /* Minor version number */
161 bs
= buffer
.getInt(); /* Block Size */
162 maxc
= buffer
.getInt(); /* Max nb of children per node */
164 this.nodeCount
= buffer
.getInt();
165 rootNodeSeqNb
= buffer
.getInt();
166 startTime
= buffer
.getLong();
168 this.config
= new HTConfig(existingStateFile
, bs
, maxc
, startTime
);
172 * FIXME We close fis here and the TreeIO will then reopen the same
173 * file, not extremely elegant. But how to pass the information here to
176 this.treeIO
= new HT_IO(this, false);
178 rebuildLatestBranch(rootNodeSeqNb
);
179 this.treeEnd
= latestBranch
.firstElement().getNodeEnd();
182 * Make sure the history start time we read previously is consistent
183 * with was is actually in the root node.
185 if (startTime
!= latestBranch
.firstElement().getNodeStart()) {
188 throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
189 "history file, it might be corrupted."); //$NON-NLS-1$
194 * "Save" the tree to disk. This method will cause the treeIO object to
195 * commit all nodes to disk and then return the RandomAccessFile descriptor
196 * so the Tree object can save its configuration into the header of the
199 * @param requestedEndTime
201 void closeTree(long requestedEndTime
) {
207 * Work-around the "empty branches" that get created when the root node
208 * becomes full. Overwrite the tree's end time with the original wanted
209 * end-time, to ensure no queries are sent into those empty nodes.
211 * This won't be needed once extended nodes are implemented.
213 this.treeEnd
= requestedEndTime
;
215 /* Close off the latest branch of the tree */
216 for (i
= 0; i
< latestBranch
.size(); i
++) {
217 latestBranch
.get(i
).closeThisNode(treeEnd
);
218 treeIO
.writeNode(latestBranch
.get(i
));
221 /* Only use this for debugging purposes, it's VERY slow! */
222 // this.checkIntegrity();
224 fc
= treeIO
.getFcOut();
225 buffer
= ByteBuffer
.allocate(getTreeHeaderSize());
226 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
229 /* Save the config of the tree to the header of the file */
233 buffer
.putInt(HISTORY_FILE_MAGIC_NUMBER
);
235 buffer
.putInt(MAJOR_VERSION
);
236 buffer
.putInt(MINOR_VERSION
);
238 buffer
.putInt(config
.blockSize
);
239 buffer
.putInt(config
.maxChildren
);
241 buffer
.putInt(nodeCount
);
243 /* root node seq. nb */
244 buffer
.putInt(latestBranch
.firstElement().getSequenceNumber());
246 /* start time of this history */
247 buffer
.putLong(latestBranch
.firstElement().getNodeStart());
250 res
= fc
.write(buffer
);
251 assert (res
<= getTreeHeaderSize());
252 /* done writing the file header */
254 } catch (IOException e
) {
255 /* We should not have any problems at this point... */
260 } catch (IOException e
) {
271 long getTreeStart() {
272 return config
.treeStart
;
288 * Rebuild the latestBranch "cache" object by reading the nodes from disk
289 * (When we are opening an existing file on disk and want to append to it,
292 * @param rootNodeSeqNb
293 * The sequence number of the root node, so we know where to
295 * @throws ClosedChannelException
297 private void rebuildLatestBranch(int rootNodeSeqNb
) throws ClosedChannelException
{
298 HTNode nextChildNode
;
300 this.latestBranch
= new Vector
<CoreNode
>();
302 nextChildNode
= treeIO
.readNodeFromDisk(rootNodeSeqNb
);
303 latestBranch
.add((CoreNode
) nextChildNode
);
304 while (latestBranch
.lastElement().getNbChildren() > 0) {
305 nextChildNode
= treeIO
.readNodeFromDisk(latestBranch
.lastElement().getLatestChild());
306 latestBranch
.add((CoreNode
) nextChildNode
);
311 * Insert an interval in the tree
315 void insertInterval(HTInterval interval
) throws TimeRangeException
{
316 if (interval
.getStartTime() < config
.treeStart
) {
317 throw new TimeRangeException();
319 tryInsertAtNode(interval
, latestBranch
.size() - 1);
323 * Inner method to find in which node we should add the interval.
326 * The interval to add to the tree
328 * The index *in the latestBranch* where we are trying the
331 private void tryInsertAtNode(HTInterval interval
, int indexOfNode
) {
332 HTNode targetNode
= latestBranch
.get(indexOfNode
);
334 /* Verify if there is enough room in this node to store this interval */
335 if (interval
.getIntervalSize() > targetNode
.getNodeFreeSpace()) {
336 /* Nope, not enough room. Insert in a new sibling instead. */
337 addSiblingNode(indexOfNode
);
338 tryInsertAtNode(interval
, latestBranch
.size() - 1);
342 /* Make sure the interval time range fits this node */
343 if (interval
.getStartTime() < targetNode
.getNodeStart()) {
345 * No, this interval starts before the startTime of this node. We
346 * need to check recursively in parents if it can fit.
348 assert (indexOfNode
>= 1);
349 tryInsertAtNode(interval
, indexOfNode
- 1);
354 * Ok, there is room, and the interval fits in this time slot. Let's add
357 targetNode
.addInterval(interval
);
359 /* Update treeEnd if needed */
360 if (interval
.getEndTime() > this.treeEnd
) {
361 this.treeEnd
= interval
.getEndTime();
367 * Method to add a sibling to any node in the latest branch. This will add
368 * children back down to the leaf level, if needed.
371 * The index in latestBranch where we start adding
373 private void addSiblingNode(int indexOfNode
) {
375 CoreNode newNode
, prevNode
;
376 long splitTime
= treeEnd
;
378 assert (indexOfNode
< latestBranch
.size());
380 /* Check if we need to add a new root node */
381 if (indexOfNode
== 0) {
386 /* Check if we can indeed add a child to the target parent */
387 if (latestBranch
.get(indexOfNode
- 1).getNbChildren() == config
.maxChildren
) {
388 /* If not, add a branch starting one level higher instead */
389 addSiblingNode(indexOfNode
- 1);
393 /* Split off the new branch from the old one */
394 for (i
= indexOfNode
; i
< latestBranch
.size(); i
++) {
395 latestBranch
.get(i
).closeThisNode(splitTime
);
396 treeIO
.writeNode(latestBranch
.get(i
));
398 prevNode
= latestBranch
.get(i
- 1);
399 newNode
= initNewCoreNode(prevNode
.getSequenceNumber(),
401 prevNode
.linkNewChild(newNode
);
403 latestBranch
.set(i
, newNode
);
409 * Similar to the previous method, except here we rebuild a completely new
412 private void addNewRootNode() {
414 CoreNode oldRootNode
, newRootNode
, newNode
, prevNode
;
415 long splitTime
= this.treeEnd
;
417 oldRootNode
= latestBranch
.firstElement();
418 newRootNode
= initNewCoreNode(-1, config
.treeStart
);
420 /* Tell the old root node that it isn't root anymore */
421 oldRootNode
.setParentSequenceNumber(newRootNode
.getSequenceNumber());
423 /* Close off the whole current latestBranch */
424 for (i
= 0; i
< latestBranch
.size(); i
++) {
425 latestBranch
.get(i
).closeThisNode(splitTime
);
426 treeIO
.writeNode(latestBranch
.get(i
));
429 /* Link the new root to its first child (the previous root node) */
430 newRootNode
.linkNewChild(oldRootNode
);
432 /* Rebuild a new latestBranch */
433 depth
= latestBranch
.size();
434 latestBranch
= new Vector
<CoreNode
>();
435 latestBranch
.add(newRootNode
);
436 for (i
= 1; i
< depth
+ 1; i
++) {
437 prevNode
= latestBranch
.get(i
- 1);
438 newNode
= initNewCoreNode(prevNode
.getParentSequenceNumber(),
440 prevNode
.linkNewChild(newNode
);
441 latestBranch
.add(newNode
);
446 * Add a new empty node to the tree.
448 * @param parentSeqNumber
449 * Sequence number of this node's parent
451 * Start time of the new node
452 * @return The newly created node
454 private CoreNode
initNewCoreNode(int parentSeqNumber
, long startTime
) {
455 CoreNode newNode
= new CoreNode(this, this.nodeCount
, parentSeqNumber
,
459 /* Update the treeEnd if needed */
460 if (startTime
>= this.treeEnd
) {
461 this.treeEnd
= startTime
+ 1;
467 * Inner method to select the next child of the current node intersecting
468 * the given timestamp. Useful for moving down the tree following one
473 * @return The child node intersecting t
474 * @throws ClosedChannelException
475 * If the file channel was closed while we were reading the tree
477 HTNode
selectNextChild(CoreNode currentNode
, long t
) throws ClosedChannelException
{
478 assert (currentNode
.getNbChildren() > 0);
479 int potentialNextSeqNb
= currentNode
.getSequenceNumber();
481 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
482 if (t
>= currentNode
.getChildStart(i
)) {
483 potentialNextSeqNb
= currentNode
.getChild(i
);
489 * Once we exit this loop, we should have found a children to follow. If
490 * we didn't, there's a problem.
492 assert (potentialNextSeqNb
!= currentNode
.getSequenceNumber());
495 * Since this code path is quite performance-critical, avoid iterating
496 * through the whole latestBranch array if we know for sure the next
497 * node has to be on disk
499 if (currentNode
.isDone()) {
500 return treeIO
.readNodeFromDisk(potentialNextSeqNb
);
502 return treeIO
.readNode(potentialNextSeqNb
);
506 * Helper function to get the size of the "tree header" in the tree-file The
507 * nodes will use this offset to know where they should be in the file. This
508 * should always be a multiple of 4K.
510 static int getTreeHeaderSize() {
515 return config
.stateFile
.length();
518 // ------------------------------------------------------------------------
519 // Test/debugging methods
520 // ------------------------------------------------------------------------
522 /* Only used for debugging, shouldn't be externalized */
523 @SuppressWarnings("nls")
524 boolean checkNodeIntegrity(HTNode zenode
) {
528 StringBuffer buf
= new StringBuffer();
531 // FIXME /* Only testing Core Nodes for now */
532 if (!(zenode
instanceof CoreNode
)) {
536 node
= (CoreNode
) zenode
;
540 * Test that this node's start and end times match the start of the
541 * first child and the end of the last child, respectively
543 if (node
.getNbChildren() > 0) {
544 otherNode
= treeIO
.readNode(node
.getChild(0));
545 if (node
.getNodeStart() != otherNode
.getNodeStart()) {
546 buf
.append("Start time of node (" + node
.getNodeStart() + ") "
547 + "does not match start time of first child " + "("
548 + otherNode
.getNodeStart() + "), " + "node #"
549 + otherNode
.getSequenceNumber() + ")\n");
553 otherNode
= treeIO
.readNode(node
.getLatestChild());
554 if (node
.getNodeEnd() != otherNode
.getNodeEnd()) {
555 buf
.append("End time of node (" + node
.getNodeEnd()
556 + ") does not match end time of last child ("
557 + otherNode
.getNodeEnd() + ", node #"
558 + otherNode
.getSequenceNumber() + ")\n");
565 * Test that the childStartTimes[] array matches the real nodes' start
568 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
569 otherNode
= treeIO
.readNode(node
.getChild(i
));
570 if (otherNode
.getNodeStart() != node
.getChildStart(i
)) {
571 buf
.append(" Expected start time of child node #"
572 + node
.getChild(i
) + ": " + node
.getChildStart(i
)
573 + "\n" + " Actual start time of node #"
574 + otherNode
.getSequenceNumber() + ": "
575 + otherNode
.getNodeStart() + "\n");
580 } catch (ClosedChannelException e
) {
585 System
.out
.println("");
586 System
.out
.println("SHT: Integrity check failed for node #"
587 + node
.getSequenceNumber() + ":");
588 System
.out
.println(buf
.toString());
593 void checkIntegrity() {
595 for (int i
= 0; i
< nodeCount
; i
++) {
596 checkNodeIntegrity(treeIO
.readNode(i
));
598 } catch (ClosedChannelException e
) {
603 /* Only used for debugging, shouldn't be externalized */
604 @SuppressWarnings("nls")
606 public String
toString() {
607 return "Information on the current tree:\n\n" + "Blocksize: "
608 + config
.blockSize
+ "\n" + "Max nb. of children per node: "
609 + config
.maxChildren
+ "\n" + "Number of nodes: " + nodeCount
610 + "\n" + "Depth of the tree: " + latestBranch
.size() + "\n"
611 + "Size of the treefile: " + this.getFileSize() + "\n"
612 + "Root node has sequence number: "
613 + latestBranch
.firstElement().getSequenceNumber() + "\n"
614 + "'Latest leaf' has sequence number: "
615 + latestBranch
.lastElement().getSequenceNumber();
618 private int curDepth
;
621 * Start at currentNode and print the contents of all its children, in
622 * pre-order. Give the root node in parameter to visit the whole tree, and
623 * have a nice overview.
625 @SuppressWarnings("nls")
626 private void preOrderPrint(PrintWriter writer
, boolean printIntervals
,
627 CoreNode currentNode
) {
628 /* Only used for debugging, shouldn't be externalized */
632 writer
.println(currentNode
.toString());
633 if (printIntervals
) {
634 currentNode
.debugPrintIntervals(writer
);
639 for (i
= 0; i
< currentNode
.getNbChildren(); i
++) {
640 nextNode
= treeIO
.readNode(currentNode
.getChild(i
));
641 assert (nextNode
instanceof CoreNode
); // TODO temporary
642 for (j
= 0; j
< curDepth
- 1; j
++) {
646 preOrderPrint(writer
, printIntervals
, (CoreNode
) nextNode
);
648 } catch (ClosedChannelException e
) {
656 * Print out the full tree for debugging purposes
659 * PrintWriter in which to write the output
660 * @param printIntervals
661 * Says if you want to output the full interval information
663 void debugPrintFullTree(PrintWriter writer
, boolean printIntervals
) {
664 /* Only used for debugging, shouldn't be externalized */
666 this.preOrderPrint(writer
, false, latestBranch
.firstElement());
668 if (printIntervals
) {
669 writer
.println("\nDetails of intervals:"); //$NON-NLS-1$
671 this.preOrderPrint(writer
, true, latestBranch
.firstElement());
673 writer
.println('\n');