1 /*******************************************************************************
2 * Copyright (c) 2012, 2013 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
.ArrayList
;
24 import java
.util
.Collections
;
25 import java
.util
.List
;
27 import org
.eclipse
.linuxtools
.tmf
.core
.exceptions
.TimeRangeException
;
28 import org
.eclipse
.linuxtools
.tmf
.core
.statesystem
.ITmfStateProvider
;
31 * Meta-container for the History Tree. This structure contains all the
32 * high-level data relevant to the tree.
40 * Size of the "tree header" in the tree-file The nodes will use this offset
41 * to know where they should be in the file. This should always be a
44 public static final int TREE_HEADER_SIZE
= 4096;
46 private static final int HISTORY_FILE_MAGIC_NUMBER
= 0x05FFA900;
48 /** File format version. Increment when breaking compatibility. */
49 private static final int FILE_VERSION
= 3;
51 // ------------------------------------------------------------------------
52 // Tree-specific configuration
53 // ------------------------------------------------------------------------
55 /** Container for all the configuration constants */
56 private final HTConfig config
;
58 /** Reader/writer object */
59 private final HT_IO treeIO
;
61 // ------------------------------------------------------------------------
62 // Variable Fields (will change throughout the existence of the SHT)
63 // ------------------------------------------------------------------------
65 /** Latest timestamp found in the tree (at any given moment) */
68 /** How many nodes exist in this tree, total */
69 private int nodeCount
;
71 /** "Cache" to keep the active nodes in memory */
72 private List
<CoreNode
> latestBranch
;
74 // ------------------------------------------------------------------------
75 // Constructors/"Destructors"
76 // ------------------------------------------------------------------------
79 * Create a new State History from scratch, using a SHTConfig object for
82 HistoryTree(HTConfig conf
) throws IOException
{
84 * Simple check to make sure we have enough place in the 0th block
85 * for the tree configuration
87 if (conf
.getBlockSize() < TREE_HEADER_SIZE
) {
88 throw new IllegalArgumentException();
92 treeEnd
= conf
.getTreeStart();
94 latestBranch
= new ArrayList
<CoreNode
>();
96 /* Prepare the IO object */
97 treeIO
= new HT_IO(this, true);
99 /* Add the first node to the tree */
100 CoreNode firstNode
= initNewCoreNode(-1, conf
.getTreeStart());
101 latestBranch
.add(firstNode
);
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 * @param expProviderVersion
111 * The expected version of the state provider
112 * @throws IOException
114 HistoryTree(File existingStateFile
, int expProviderVersion
) throws IOException
{
116 * Open the file ourselves, get the tree header information we need,
117 * then pass on the descriptor to the TreeIO object.
119 int rootNodeSeqNb
, res
;
123 /* Java I/O mumbo jumbo... */
124 if (!existingStateFile
.exists()) {
125 throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
127 if (existingStateFile
.length() <= 0) {
128 throw new IOException("Empty target file"); //$NON-NLS-1$
131 FileInputStream fis
= new FileInputStream(existingStateFile
);
132 ByteBuffer buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
133 FileChannel fc
= fis
.getChannel();
134 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
140 * Check the magic number,to make sure we're opening the right type of
143 res
= buffer
.getInt();
144 if (res
!= HISTORY_FILE_MAGIC_NUMBER
) {
147 throw new IOException("Wrong magic number"); //$NON-NLS-1$
150 res
= buffer
.getInt(); /* File format version number */
151 if (res
!= FILE_VERSION
) {
154 throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$
157 res
= buffer
.getInt(); /* Event handler's version number */
158 if (res
!= expProviderVersion
&&
159 expProviderVersion
!= ITmfStateProvider
.IGNORE_PROVIDER_VERSION
) {
161 * The existing history was built using a event handler that doesn't
162 * match the current one in the framework. Information could be all
163 * wrong, so we'll force a rebuild of the history file instead.
167 throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$
170 bs
= buffer
.getInt(); /* Block Size */
171 maxc
= buffer
.getInt(); /* Max nb of children per node */
173 this.nodeCount
= buffer
.getInt();
174 rootNodeSeqNb
= buffer
.getInt();
175 startTime
= buffer
.getLong();
177 this.config
= new HTConfig(existingStateFile
, bs
, maxc
, expProviderVersion
, startTime
);
181 * FIXME We close fis here and the TreeIO will then reopen the same
182 * file, not extremely elegant. But how to pass the information here to
185 this.treeIO
= new HT_IO(this, false);
187 rebuildLatestBranch(rootNodeSeqNb
);
188 this.treeEnd
= latestBranch
.get(0).getNodeEnd();
191 * Make sure the history start time we read previously is consistent
192 * with was is actually in the root node.
194 if (startTime
!= latestBranch
.get(0).getNodeStart()) {
197 throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
198 "history file, it might be corrupted."); //$NON-NLS-1$
203 * "Save" the tree to disk. This method will cause the treeIO object to
204 * commit all nodes to disk and then return the RandomAccessFile descriptor
205 * so the Tree object can save its configuration into the header of the
208 * @param requestedEndTime
210 void closeTree(long requestedEndTime
) {
216 * Work-around the "empty branches" that get created when the root node
217 * becomes full. Overwrite the tree's end time with the original wanted
218 * end-time, to ensure no queries are sent into those empty nodes.
220 * This won't be needed once extended nodes are implemented.
222 this.treeEnd
= requestedEndTime
;
224 /* Close off the latest branch of the tree */
225 for (i
= 0; i
< latestBranch
.size(); i
++) {
226 latestBranch
.get(i
).closeThisNode(treeEnd
);
227 treeIO
.writeNode(latestBranch
.get(i
));
230 fc
= treeIO
.getFcOut();
231 buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
232 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
235 /* Save the config of the tree to the header of the file */
239 buffer
.putInt(HISTORY_FILE_MAGIC_NUMBER
);
241 buffer
.putInt(FILE_VERSION
);
242 buffer
.putInt(config
.getProviderVersion());
244 buffer
.putInt(config
.getBlockSize());
245 buffer
.putInt(config
.getMaxChildren());
247 buffer
.putInt(nodeCount
);
249 /* root node seq. nb */
250 buffer
.putInt(latestBranch
.get(0).getSequenceNumber());
252 /* start time of this history */
253 buffer
.putLong(latestBranch
.get(0).getNodeStart());
256 res
= fc
.write(buffer
);
257 assert (res
<= TREE_HEADER_SIZE
);
258 /* done writing the file header */
260 } catch (IOException e
) {
261 /* We should not have any problems at this point... */
265 } catch (IOException e
) {
271 // ------------------------------------------------------------------------
273 // ------------------------------------------------------------------------
275 HTConfig
getConfig() {
279 long getTreeStart() {
280 return config
.getTreeStart();
295 List
<CoreNode
> getLatestBranch() {
296 return Collections
.unmodifiableList(latestBranch
);
299 // ------------------------------------------------------------------------
301 // ------------------------------------------------------------------------
304 * Rebuild the latestBranch "cache" object by reading the nodes from disk
305 * (When we are opening an existing file on disk and want to append to it,
308 * @param rootNodeSeqNb
309 * The sequence number of the root node, so we know where to
311 * @throws ClosedChannelException
313 private void rebuildLatestBranch(int rootNodeSeqNb
) throws ClosedChannelException
{
314 HTNode nextChildNode
;
316 this.latestBranch
= new ArrayList
<CoreNode
>();
318 nextChildNode
= treeIO
.readNodeFromDisk(rootNodeSeqNb
);
319 latestBranch
.add((CoreNode
) nextChildNode
);
320 while (latestBranch
.get(latestBranch
.size() - 1).getNbChildren() > 0) {
321 nextChildNode
= treeIO
.readNodeFromDisk(latestBranch
.get(latestBranch
.size() - 1).getLatestChild());
322 latestBranch
.add((CoreNode
) nextChildNode
);
327 * Insert an interval in the tree
331 void insertInterval(HTInterval interval
) throws TimeRangeException
{
332 if (interval
.getStartTime() < config
.getTreeStart()) {
333 throw new TimeRangeException();
335 tryInsertAtNode(interval
, latestBranch
.size() - 1);
339 * Inner method to find in which node we should add the interval.
342 * The interval to add to the tree
344 * The index *in the latestBranch* where we are trying the
347 private void tryInsertAtNode(HTInterval interval
, int indexOfNode
) {
348 HTNode targetNode
= latestBranch
.get(indexOfNode
);
350 /* Verify if there is enough room in this node to store this interval */
351 if (interval
.getIntervalSize() > targetNode
.getNodeFreeSpace()) {
352 /* Nope, not enough room. Insert in a new sibling instead. */
353 addSiblingNode(indexOfNode
);
354 tryInsertAtNode(interval
, latestBranch
.size() - 1);
358 /* Make sure the interval time range fits this node */
359 if (interval
.getStartTime() < targetNode
.getNodeStart()) {
361 * No, this interval starts before the startTime of this node. We
362 * need to check recursively in parents if it can fit.
364 assert (indexOfNode
>= 1);
365 tryInsertAtNode(interval
, indexOfNode
- 1);
370 * Ok, there is room, and the interval fits in this time slot. Let's add
373 targetNode
.addInterval(interval
);
375 /* Update treeEnd if needed */
376 if (interval
.getEndTime() > this.treeEnd
) {
377 this.treeEnd
= interval
.getEndTime();
383 * Method to add a sibling to any node in the latest branch. This will add
384 * children back down to the leaf level, if needed.
387 * The index in latestBranch where we start adding
389 private void addSiblingNode(int indexOfNode
) {
391 CoreNode newNode
, prevNode
;
392 long splitTime
= treeEnd
;
394 assert (indexOfNode
< latestBranch
.size());
396 /* Check if we need to add a new root node */
397 if (indexOfNode
== 0) {
402 /* Check if we can indeed add a child to the target parent */
403 if (latestBranch
.get(indexOfNode
- 1).getNbChildren() == config
.getMaxChildren()) {
404 /* If not, add a branch starting one level higher instead */
405 addSiblingNode(indexOfNode
- 1);
409 /* Split off the new branch from the old one */
410 for (i
= indexOfNode
; i
< latestBranch
.size(); i
++) {
411 latestBranch
.get(i
).closeThisNode(splitTime
);
412 treeIO
.writeNode(latestBranch
.get(i
));
414 prevNode
= latestBranch
.get(i
- 1);
415 newNode
= initNewCoreNode(prevNode
.getSequenceNumber(),
417 prevNode
.linkNewChild(newNode
);
419 latestBranch
.set(i
, newNode
);
425 * Similar to the previous method, except here we rebuild a completely new
428 private void addNewRootNode() {
430 CoreNode oldRootNode
, newRootNode
, newNode
, prevNode
;
431 long splitTime
= this.treeEnd
;
433 oldRootNode
= latestBranch
.get(0);
434 newRootNode
= initNewCoreNode(-1, config
.getTreeStart());
436 /* Tell the old root node that it isn't root anymore */
437 oldRootNode
.setParentSequenceNumber(newRootNode
.getSequenceNumber());
439 /* Close off the whole current latestBranch */
440 for (i
= 0; i
< latestBranch
.size(); i
++) {
441 latestBranch
.get(i
).closeThisNode(splitTime
);
442 treeIO
.writeNode(latestBranch
.get(i
));
445 /* Link the new root to its first child (the previous root node) */
446 newRootNode
.linkNewChild(oldRootNode
);
448 /* Rebuild a new latestBranch */
449 depth
= latestBranch
.size();
450 latestBranch
= new ArrayList
<CoreNode
>();
451 latestBranch
.add(newRootNode
);
452 for (i
= 1; i
< depth
+ 1; i
++) {
453 prevNode
= latestBranch
.get(i
- 1);
454 newNode
= initNewCoreNode(prevNode
.getParentSequenceNumber(),
456 prevNode
.linkNewChild(newNode
);
457 latestBranch
.add(newNode
);
462 * Add a new empty node to the tree.
464 * @param parentSeqNumber
465 * Sequence number of this node's parent
467 * Start time of the new node
468 * @return The newly created node
470 private CoreNode
initNewCoreNode(int parentSeqNumber
, long startTime
) {
471 CoreNode newNode
= new CoreNode(this, this.nodeCount
, parentSeqNumber
,
475 /* Update the treeEnd if needed */
476 if (startTime
>= this.treeEnd
) {
477 this.treeEnd
= startTime
+ 1;
483 * Inner method to select the next child of the current node intersecting
484 * the given timestamp. Useful for moving down the tree following one
489 * @return The child node intersecting t
490 * @throws ClosedChannelException
491 * If the file channel was closed while we were reading the tree
493 HTNode
selectNextChild(CoreNode currentNode
, long t
) throws ClosedChannelException
{
494 assert (currentNode
.getNbChildren() > 0);
495 int potentialNextSeqNb
= currentNode
.getSequenceNumber();
497 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
498 if (t
>= currentNode
.getChildStart(i
)) {
499 potentialNextSeqNb
= currentNode
.getChild(i
);
505 * Once we exit this loop, we should have found a children to follow. If
506 * we didn't, there's a problem.
508 assert (potentialNextSeqNb
!= currentNode
.getSequenceNumber());
511 * Since this code path is quite performance-critical, avoid iterating
512 * through the whole latestBranch array if we know for sure the next
513 * node has to be on disk
515 if (currentNode
.isDone()) {
516 return treeIO
.readNodeFromDisk(potentialNextSeqNb
);
518 return treeIO
.readNode(potentialNextSeqNb
);
522 return config
.getStateFile().length();
525 // ------------------------------------------------------------------------
526 // Test/debugging methods
527 // ------------------------------------------------------------------------
529 /* Only used for debugging, shouldn't be externalized */
530 @SuppressWarnings("nls")
531 boolean checkNodeIntegrity(HTNode zenode
) {
535 StringBuffer buf
= new StringBuffer();
538 // FIXME /* Only testing Core Nodes for now */
539 if (!(zenode
instanceof CoreNode
)) {
543 node
= (CoreNode
) zenode
;
547 * Test that this node's start and end times match the start of the
548 * first child and the end of the last child, respectively
550 if (node
.getNbChildren() > 0) {
551 otherNode
= treeIO
.readNode(node
.getChild(0));
552 if (node
.getNodeStart() != otherNode
.getNodeStart()) {
553 buf
.append("Start time of node (" + node
.getNodeStart() + ") "
554 + "does not match start time of first child " + "("
555 + otherNode
.getNodeStart() + "), " + "node #"
556 + otherNode
.getSequenceNumber() + ")\n");
560 otherNode
= treeIO
.readNode(node
.getLatestChild());
561 if (node
.getNodeEnd() != otherNode
.getNodeEnd()) {
562 buf
.append("End time of node (" + node
.getNodeEnd()
563 + ") does not match end time of last child ("
564 + otherNode
.getNodeEnd() + ", node #"
565 + otherNode
.getSequenceNumber() + ")\n");
572 * Test that the childStartTimes[] array matches the real nodes' start
575 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
576 otherNode
= treeIO
.readNode(node
.getChild(i
));
577 if (otherNode
.getNodeStart() != node
.getChildStart(i
)) {
578 buf
.append(" Expected start time of child node #"
579 + node
.getChild(i
) + ": " + node
.getChildStart(i
)
580 + "\n" + " Actual start time of node #"
581 + otherNode
.getSequenceNumber() + ": "
582 + otherNode
.getNodeStart() + "\n");
587 } catch (ClosedChannelException e
) {
592 System
.out
.println("");
593 System
.out
.println("SHT: Integrity check failed for node #"
594 + node
.getSequenceNumber() + ":");
595 System
.out
.println(buf
.toString());
600 void checkIntegrity() {
602 for (int i
= 0; i
< nodeCount
; i
++) {
603 checkNodeIntegrity(treeIO
.readNode(i
));
605 } catch (ClosedChannelException e
) {
609 /* Only used for debugging, shouldn't be externalized */
610 @SuppressWarnings("nls")
612 public String
toString() {
613 return "Information on the current tree:\n\n" + "Blocksize: "
614 + config
.getBlockSize() + "\n" + "Max nb. of children per node: "
615 + config
.getMaxChildren() + "\n" + "Number of nodes: " + nodeCount
616 + "\n" + "Depth of the tree: " + latestBranch
.size() + "\n"
617 + "Size of the treefile: " + this.getFileSize() + "\n"
618 + "Root node has sequence number: "
619 + latestBranch
.get(0).getSequenceNumber() + "\n"
620 + "'Latest leaf' has sequence number: "
621 + latestBranch
.get(latestBranch
.size() - 1).getSequenceNumber();
624 private int curDepth
;
627 * Start at currentNode and print the contents of all its children, in
628 * pre-order. Give the root node in parameter to visit the whole tree, and
629 * have a nice overview.
631 @SuppressWarnings("nls")
632 private void preOrderPrint(PrintWriter writer
, boolean printIntervals
,
633 CoreNode currentNode
) {
634 /* Only used for debugging, shouldn't be externalized */
638 writer
.println(currentNode
.toString());
639 if (printIntervals
) {
640 currentNode
.debugPrintIntervals(writer
);
645 for (i
= 0; i
< currentNode
.getNbChildren(); i
++) {
646 nextNode
= treeIO
.readNode(currentNode
.getChild(i
));
647 assert (nextNode
instanceof CoreNode
); // TODO temporary
648 for (j
= 0; j
< curDepth
- 1; j
++) {
652 preOrderPrint(writer
, printIntervals
, (CoreNode
) nextNode
);
654 } catch (ClosedChannelException e
) {
662 * Print out the full tree for debugging purposes
665 * PrintWriter in which to write the output
666 * @param printIntervals
667 * Says if you want to output the full interval information
669 void debugPrintFullTree(PrintWriter writer
, boolean printIntervals
) {
670 /* Only used for debugging, shouldn't be externalized */
672 this.preOrderPrint(writer
, false, latestBranch
.get(0));
674 if (printIntervals
) {
675 writer
.println("\nDetails of intervals:"); //$NON-NLS-1$
677 this.preOrderPrint(writer
, true, latestBranch
.get(0));
679 writer
.println('\n');