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
.tmf
.core
.statesystem
.backend
.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
.FileChannel
;
22 import java
.util
.Vector
;
24 import org
.eclipse
.linuxtools
.tmf
.core
.statesystem
.TimeRangeException
;
27 * Meta-container for the History Tree. This structure contains all the
28 * high-level data relevant to the tree.
35 private static final int HISTORY_FILE_MAGIC_NUMBER
= 0x05FFA900;
38 * File format version. Increment minor on backwards-compatible changes.
39 * Increment major + set minor back to 0 when breaking compatibility.
41 private static final int MAJOR_VERSION
= 3;
42 private static final byte MINOR_VERSION
= 0;
45 * Tree-specific configuration
47 /* Container for all the configuration constants */
48 protected final HTConfig config
;
50 /* Reader/writer object */
51 private final HT_IO treeIO
;
54 * Variable Fields (will change throughout the existance of the SHT)
56 /* Latest timestamp found in the tree (at any given moment) */
59 /* How many nodes exist in this tree, total */
60 private int nodeCount
;
62 /* "Cache" to keep the active nodes in memory */
63 protected Vector
<CoreNode
> latestBranch
;
66 * Create a new State History from scratch, using a SHTConfig object for
72 private HistoryTree(HTConfig conf
) throws IOException
{
74 * Simple assertion to make sure we have enough place in the 0th block
75 * for the tree configuration
77 assert (conf
.blockSize
>= getTreeHeaderSize());
80 treeEnd
= conf
.treeStart
;
82 latestBranch
= new Vector
<CoreNode
>();
84 /* Prepare the IO object */
85 treeIO
= new HT_IO(this, true);
87 /* Add the first node to the tree */
88 CoreNode firstNode
= initNewCoreNode(-1, conf
.treeStart
);
89 latestBranch
.add(firstNode
);
93 * "New State History" constructor, which doesn't use SHTConfig but the
94 * individual values separately. Kept for now for backwards compatibility,
95 * but you should definitely consider using SHTConfig instead (since its
96 * contents can then change without directly affecting SHT's API).
98 HistoryTree(File newStateFile
, int blockSize
, int maxChildren
,
99 long startTime
) throws IOException
{
100 this(new HTConfig(newStateFile
, blockSize
, maxChildren
, startTime
));
104 * "Reader" constructor : instantiate a SHTree from an existing tree file on
107 * @param existingFileName
108 * Path/filename of the history-file we are to open
109 * @throws IOException
111 HistoryTree(File existingStateFile
) throws IOException
{
113 * Open the file ourselves, get the tree header information we need,
114 * then pass on the descriptor to the TreeIO object.
116 int rootNodeSeqNb
, res
;
120 /* Java I/O mumbo jumbo... */
121 if ((!existingStateFile
.exists()) || existingStateFile
.length() <= 0) {
122 throw new IOException("Invalid state file selected"); //$NON-NLS-1$
125 FileInputStream fis
= new FileInputStream(existingStateFile
);
126 ByteBuffer buffer
= ByteBuffer
.allocate(getTreeHeaderSize());
127 FileChannel fc
= fis
.getChannel();
128 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
134 * Check the magic number,to make sure we're opening the right type of
137 res
= buffer
.getInt();
138 if (res
!= HISTORY_FILE_MAGIC_NUMBER
) {
141 throw new IOException(
142 "Selected file does not look like a History Tree file"); //$NON-NLS-1$
145 res
= buffer
.getInt(); /* Major version number */
146 if (res
!= MAJOR_VERSION
) {
149 throw new IOException("Select History Tree file is of an older " //$NON-NLS-1$
150 + "format. Please use a previous version of " //$NON-NLS-1$
151 + "the parser to open it."); //$NON-NLS-1$
154 res
= buffer
.getInt(); /* Minor version number */
156 bs
= buffer
.getInt(); /* Block Size */
157 maxc
= buffer
.getInt(); /* Max nb of children per node */
159 this.nodeCount
= buffer
.getInt();
160 rootNodeSeqNb
= buffer
.getInt();
162 /* Go read the start time, which is also the root node's start time */
163 // TODO maybe make this part less ugly, as we need treeStart to build
164 // the SHTConfig object, but we need that object for new SHT_IO()
165 // and rebuildLatestBranch() ...
166 fc
.position(getTreeHeaderSize() + (long) rootNodeSeqNb
* bs
);
167 buffer
= ByteBuffer
.allocate(8);
168 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
170 res
= fc
.read(buffer
);
173 ts
= buffer
.getLong();
175 this.config
= new HTConfig(existingStateFile
, bs
, maxc
, ts
);
179 * FIXME We close fis here and the TreeIO will then reopen the same
180 * file, not extremely elegant. But how to pass the information here to
183 this.treeIO
= new HT_IO(this, false);
185 rebuildLatestBranch(rootNodeSeqNb
);
186 this.treeEnd
= latestBranch
.firstElement().getNodeEnd();
190 * "Save" the tree to disk. This method will cause the treeIO object to
191 * commit all nodes to disk and then return the RandomAccessFile descriptor
192 * so the Tree object can save its configuration into the header of the
195 * @param requestedEndTime
202 /* Close off the latest branch of the tree */
203 for (i
= 0; i
< latestBranch
.size(); i
++) {
204 latestBranch
.get(i
).closeThisNode(treeEnd
);
205 treeIO
.writeNode(latestBranch
.get(i
));
208 /* Only use this for debugging purposes, it's VERY slow! */
209 // this.checkIntegrity();
211 fc
= treeIO
.getFcOut();
212 buffer
= ByteBuffer
.allocate(getTreeHeaderSize());
213 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
216 /* Save the config of the tree to the header of the file */
220 buffer
.putInt(HISTORY_FILE_MAGIC_NUMBER
);
222 buffer
.putInt(MAJOR_VERSION
);
223 buffer
.putInt(MINOR_VERSION
);
225 buffer
.putInt(config
.blockSize
);
226 buffer
.putInt(config
.maxChildren
);
228 buffer
.putInt(nodeCount
);
230 /* root node seq. nb */
231 buffer
.putInt(latestBranch
.firstElement().getSequenceNumber());
234 res
= fc
.write(buffer
);
235 assert (res
<= getTreeHeaderSize());
236 /* done writing the file header */
238 } catch (IOException e
) {
239 /* We should not have any problems at this point... */
244 } catch (IOException e
) {
255 long getTreeStart() {
256 return config
.treeStart
;
272 * Rebuild the latestBranch "cache" object by reading the nodes from disk
273 * (When we are opening an existing file on disk and want to append to it,
276 * @param rootNodeSeqNb
277 * The sequence number of the root node, so we know where to
280 private void rebuildLatestBranch(int rootNodeSeqNb
) {
281 HTNode nextChildNode
;
283 this.latestBranch
= new Vector
<CoreNode
>();
285 nextChildNode
= treeIO
.readNodeFromDisk(rootNodeSeqNb
);
286 latestBranch
.add((CoreNode
) nextChildNode
);
287 while (latestBranch
.lastElement().getNbChildren() > 0) {
288 nextChildNode
= treeIO
.readNodeFromDisk(latestBranch
.lastElement().getLatestChild());
289 latestBranch
.add((CoreNode
) nextChildNode
);
294 * Insert an interval in the tree
298 void insertInterval(HTInterval interval
) throws TimeRangeException
{
299 if (interval
.getStartTime() < config
.treeStart
) {
300 throw new TimeRangeException();
302 tryInsertAtNode(interval
, latestBranch
.size() - 1);
306 * Inner method to find in which node we should add the interval.
309 * The interval to add to the tree
311 * The index *in the latestBranch* where we are trying the
314 private void tryInsertAtNode(HTInterval interval
, int indexOfNode
) {
315 HTNode targetNode
= latestBranch
.get(indexOfNode
);
317 /* Verify if there is enough room in this node to store this interval */
318 if (interval
.getIntervalSize() > targetNode
.getNodeFreeSpace()) {
319 /* Nope, not enough room. Insert in a new sibling instead. */
320 addSiblingNode(indexOfNode
);
321 tryInsertAtNode(interval
, latestBranch
.size() - 1);
325 /* Make sure the interval time range fits this node */
326 if (interval
.getStartTime() < targetNode
.getNodeStart()) {
328 * No, this interval starts before the startTime of this node. We
329 * need to check recursively in parents if it can fit.
331 assert (indexOfNode
>= 1);
332 tryInsertAtNode(interval
, indexOfNode
- 1);
337 * Ok, there is room, and the interval fits in this time slot. Let's add
340 targetNode
.addInterval(interval
);
342 /* Update treeEnd if needed */
343 if (interval
.getEndTime() > this.treeEnd
) {
344 this.treeEnd
= interval
.getEndTime();
350 * Method to add a sibling to any node in the latest branch. This will add
351 * children back down to the leaf level, if needed.
354 * The index in latestBranch where we start adding
356 private void addSiblingNode(int indexOfNode
) {
358 CoreNode newNode
, prevNode
;
359 long splitTime
= treeEnd
;
361 assert (indexOfNode
< latestBranch
.size());
363 /* Check if we need to add a new root node */
364 if (indexOfNode
== 0) {
369 /* Check if we can indeed add a child to the target parent */
370 if (latestBranch
.get(indexOfNode
- 1).getNbChildren() == config
.maxChildren
) {
371 /* If not, add a branch starting one level higher instead */
372 addSiblingNode(indexOfNode
- 1);
376 /* Split off the new branch from the old one */
377 for (i
= indexOfNode
; i
< latestBranch
.size(); i
++) {
378 latestBranch
.get(i
).closeThisNode(splitTime
);
379 treeIO
.writeNode(latestBranch
.get(i
));
381 prevNode
= latestBranch
.get(i
- 1);
382 newNode
= initNewCoreNode(prevNode
.getSequenceNumber(),
384 prevNode
.linkNewChild(newNode
);
386 latestBranch
.set(i
, newNode
);
392 * Similar to the previous method, except here we rebuild a completely new
395 private void addNewRootNode() {
397 CoreNode oldRootNode
, newRootNode
, newNode
, prevNode
;
398 long splitTime
= this.treeEnd
;
400 oldRootNode
= latestBranch
.firstElement();
401 newRootNode
= initNewCoreNode(-1, config
.treeStart
);
403 /* Tell the old root node that it isn't root anymore */
404 oldRootNode
.setParentSequenceNumber(newRootNode
.getSequenceNumber());
406 /* Close off the whole current latestBranch */
407 for (i
= 0; i
< latestBranch
.size(); i
++) {
408 latestBranch
.get(i
).closeThisNode(splitTime
);
409 treeIO
.writeNode(latestBranch
.get(i
));
412 /* Link the new root to its first child (the previous root node) */
413 newRootNode
.linkNewChild(oldRootNode
);
415 /* Rebuild a new latestBranch */
416 depth
= latestBranch
.size();
417 latestBranch
= new Vector
<CoreNode
>();
418 latestBranch
.add(newRootNode
);
419 for (i
= 1; i
< depth
+ 1; i
++) {
420 prevNode
= latestBranch
.get(i
- 1);
421 newNode
= initNewCoreNode(prevNode
.getParentSequenceNumber(),
423 prevNode
.linkNewChild(newNode
);
424 latestBranch
.add(newNode
);
429 * Add a new empty node to the tree.
431 * @param parentSeqNumber
432 * Sequence number of this node's parent
434 * Start time of the new node
435 * @return The newly created node
437 private CoreNode
initNewCoreNode(int parentSeqNumber
, long startTime
) {
438 CoreNode newNode
= new CoreNode(this, this.nodeCount
, parentSeqNumber
,
442 /* Update the treeEnd if needed */
443 if (startTime
>= this.treeEnd
) {
444 this.treeEnd
= startTime
+ 1;
450 * Inner method to select the next child of the current node intersecting
451 * the given timestamp. Useful for moving down the tree following one
456 * @return The child node intersecting t
458 HTNode
selectNextChild(CoreNode currentNode
, long t
) {
459 assert (currentNode
.getNbChildren() > 0);
460 int potentialNextSeqNb
= currentNode
.getSequenceNumber();
462 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
463 if (t
>= currentNode
.getChildStart(i
)) {
464 potentialNextSeqNb
= currentNode
.getChild(i
);
470 * Once we exit this loop, we should have found a children to follow. If
471 * we didn't, there's a problem.
473 assert (potentialNextSeqNb
!= currentNode
.getSequenceNumber());
476 * Since this code path is quite performance-critical, avoid iterating
477 * through the whole latestBranch array if we know for sure the next
478 * node has to be on disk
480 if (currentNode
.isDone()) {
481 return treeIO
.readNodeFromDisk(potentialNextSeqNb
);
483 return treeIO
.readNode(potentialNextSeqNb
);
487 * Helper function to get the size of the "tree header" in the tree-file The
488 * nodes will use this offset to know where they should be in the file. This
489 * should always be a multiple of 4K.
491 static int getTreeHeaderSize() {
496 return config
.stateFile
.length();
500 * @name Test/debugging functions
503 /* Only used for debugging, shouldn't be externalized */
504 @SuppressWarnings("nls")
505 boolean checkNodeIntegrity(HTNode zenode
) {
509 StringBuffer buf
= new StringBuffer();
512 // FIXME /* Only testing Core Nodes for now */
513 if (!(zenode
instanceof CoreNode
)) {
517 node
= (CoreNode
) zenode
;
520 * Test that this node's start and end times match the start of the
521 * first child and the end of the last child, respectively
523 if (node
.getNbChildren() > 0) {
524 otherNode
= treeIO
.readNode(node
.getChild(0));
525 if (node
.getNodeStart() != otherNode
.getNodeStart()) {
526 buf
.append("Start time of node (" + node
.getNodeStart() + ") "
527 + "does not match start time of first child " + "("
528 + otherNode
.getNodeStart() + "), " + "node #"
529 + otherNode
.getSequenceNumber() + ")\n");
533 otherNode
= treeIO
.readNode(node
.getLatestChild());
534 if (node
.getNodeEnd() != otherNode
.getNodeEnd()) {
535 buf
.append("End time of node (" + node
.getNodeEnd()
536 + ") does not match end time of last child ("
537 + otherNode
.getNodeEnd() + ", node #"
538 + otherNode
.getSequenceNumber() + ")\n");
545 * Test that the childStartTimes[] array matches the real nodes' start
548 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
549 otherNode
= treeIO
.readNode(node
.getChild(i
));
550 if (otherNode
.getNodeStart() != node
.getChildStart(i
)) {
551 buf
.append(" Expected start time of child node #"
552 + node
.getChild(i
) + ": " + node
.getChildStart(i
)
553 + "\n" + " Actual start time of node #"
554 + otherNode
.getSequenceNumber() + ": "
555 + otherNode
.getNodeStart() + "\n");
561 System
.out
.println("");
562 System
.out
.println("SHT: Integrity check failed for node #"
563 + node
.getSequenceNumber() + ":");
564 System
.out
.println(buf
.toString());
569 void checkIntegrity() {
570 for (int i
= 0; i
< nodeCount
; i
++) {
571 checkNodeIntegrity(treeIO
.readNode(i
));
575 /* Only used for debugging, shouldn't be externalized */
576 @SuppressWarnings("nls")
578 public String
toString() {
579 return "Information on the current tree:\n\n" + "Blocksize: "
580 + config
.blockSize
+ "\n" + "Max nb. of children per node: "
581 + config
.maxChildren
+ "\n" + "Number of nodes: " + nodeCount
582 + "\n" + "Depth of the tree: " + latestBranch
.size() + "\n"
583 + "Size of the treefile: " + this.getFileSize() + "\n"
584 + "Root node has sequence number: "
585 + latestBranch
.firstElement().getSequenceNumber() + "\n"
586 + "'Latest leaf' has sequence number: "
587 + latestBranch
.lastElement().getSequenceNumber();
590 private int curDepth
;
593 * Start at currentNode and print the contents of all its children, in
594 * pre-order. Give the root node in parameter to visit the whole tree, and
595 * have a nice overview.
597 @SuppressWarnings("nls")
598 private void preOrderPrint(PrintWriter writer
, boolean printIntervals
,
599 CoreNode currentNode
) {
600 /* Only used for debugging, shouldn't be externalized */
604 writer
.println(currentNode
.toString());
605 if (printIntervals
) {
606 currentNode
.debugPrintIntervals(writer
);
610 for (i
= 0; i
< currentNode
.getNbChildren(); i
++) {
611 nextNode
= treeIO
.readNode(currentNode
.getChild(i
));
612 assert (nextNode
instanceof CoreNode
); // TODO temporary
613 for (j
= 0; j
< curDepth
- 1; j
++) {
617 preOrderPrint(writer
, printIntervals
, (CoreNode
) nextNode
);
624 * Print out the full tree for debugging purposes
627 * PrintWriter in which to write the output
628 * @param printIntervals
629 * Says if you want to output the full interval information
631 void debugPrintFullTree(PrintWriter writer
, boolean printIntervals
) {
632 /* Only used for debugging, shouldn't be externalized */
634 this.preOrderPrint(writer
, false, latestBranch
.firstElement());
636 if (printIntervals
) {
637 writer
.println("\nDetails of intervals:"); //$NON-NLS-1$
639 this.preOrderPrint(writer
, true, latestBranch
.firstElement());
641 writer
.println('\n');