1 /*******************************************************************************
2 * Copyright (c) 2010, 2015 Ericsson, École Polytechnique de Montréal, and others
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
10 * Alexandre Montplaisir - Initial API and implementation
11 * Florian Wininger - Add Extension and Leaf Node
12 * Patrick Tasse - Add message to exceptions
13 *******************************************************************************/
15 package org
.eclipse
.tracecompass
.internal
.statesystem
.core
.backend
.historytree
;
18 import java
.io
.FileInputStream
;
19 import java
.io
.IOException
;
20 import java
.io
.PrintWriter
;
21 import java
.nio
.ByteBuffer
;
22 import java
.nio
.ByteOrder
;
23 import java
.nio
.channels
.ClosedChannelException
;
24 import java
.nio
.channels
.FileChannel
;
25 import java
.util
.ArrayList
;
26 import java
.util
.Collections
;
27 import java
.util
.List
;
29 import org
.eclipse
.tracecompass
.internal
.statesystem
.core
.Activator
;
30 import org
.eclipse
.tracecompass
.statesystem
.core
.ITmfStateSystemBuilder
;
31 import org
.eclipse
.tracecompass
.statesystem
.core
.exceptions
.TimeRangeException
;
34 * Meta-container for the History Tree. This structure contains all the
35 * high-level data relevant to the tree.
37 * @author Alexandre Montplaisir
39 public class HistoryTree
{
42 * Size of the "tree header" in the tree-file The nodes will use this offset
43 * to know where they should be in the file. This should always be a
46 public static final int TREE_HEADER_SIZE
= 4096;
48 private static final int HISTORY_FILE_MAGIC_NUMBER
= 0x05FFA900;
50 /** File format version. Increment when breaking compatibility. */
51 private static final int FILE_VERSION
= 4;
53 // ------------------------------------------------------------------------
54 // Tree-specific configuration
55 // ------------------------------------------------------------------------
57 /** Container for all the configuration constants */
58 private final HTConfig config
;
60 /** Reader/writer object */
61 private final HT_IO treeIO
;
63 // ------------------------------------------------------------------------
64 // Variable Fields (will change throughout the existence of the SHT)
65 // ------------------------------------------------------------------------
67 /** Latest timestamp found in the tree (at any given moment) */
70 /** The total number of nodes that exists in this tree */
71 private int nodeCount
;
73 /** "Cache" to keep the active nodes in memory */
74 private final List
<HTNode
> latestBranch
;
76 // ------------------------------------------------------------------------
77 // Constructors/"Destructors"
78 // ------------------------------------------------------------------------
81 * Create a new State History from scratch, using a {@link HTConfig} object
85 * The config to use for this History Tree.
87 * If an error happens trying to open/write to the file
88 * specified in the config
90 public HistoryTree(HTConfig conf
) throws IOException
{
92 * Simple check to make sure we have enough place in the 0th block for
93 * the tree configuration
95 if (conf
.getBlockSize() < TREE_HEADER_SIZE
) {
96 throw new IllegalArgumentException();
100 treeEnd
= conf
.getTreeStart();
102 latestBranch
= Collections
.synchronizedList(new ArrayList
<HTNode
>());
104 /* Prepare the IO object */
105 treeIO
= new HT_IO(config
, true);
107 /* Add the first node to the tree */
108 LeafNode firstNode
= initNewLeafNode(-1, conf
.getTreeStart());
109 latestBranch
.add(firstNode
);
113 * "Reader" constructor : instantiate a SHTree from an existing tree file on
116 * @param existingStateFile
117 * Path/filename of the history-file we are to open
118 * @param expProviderVersion
119 * The expected version of the state provider
120 * @throws IOException
121 * If an error happens reading the file
123 public HistoryTree(File existingStateFile
, int expProviderVersion
) throws IOException
{
125 * Open the file ourselves, get the tree header information we need,
126 * then pass on the descriptor to the TreeIO object.
128 int rootNodeSeqNb
, res
;
132 /* Java I/O mumbo jumbo... */
133 if (!existingStateFile
.exists()) {
134 throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
136 if (existingStateFile
.length() <= 0) {
137 throw new IOException("Empty target file"); //$NON-NLS-1$
140 try (FileInputStream fis
= new FileInputStream(existingStateFile
);
141 FileChannel fc
= fis
.getChannel();) {
143 ByteBuffer buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
145 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
151 * Check the magic number to make sure we're opening the right type
154 res
= buffer
.getInt();
155 if (res
!= HISTORY_FILE_MAGIC_NUMBER
) {
156 throw new IOException("Wrong magic number"); //$NON-NLS-1$
159 res
= buffer
.getInt(); /* File format version number */
160 if (res
!= FILE_VERSION
) {
161 throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$
164 res
= buffer
.getInt(); /* Event handler's version number */
165 if (res
!= expProviderVersion
&&
166 expProviderVersion
!= ITmfStateSystemBuilder
.IGNORE_PROVIDER_VERSION
) {
168 * The existing history was built using an event handler that
169 * doesn't match the current one in the framework.
171 * Information could be all wrong. Instead of keeping an
172 * incorrect history file, a rebuild is done.
174 throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$
177 bs
= buffer
.getInt(); /* Block Size */
178 maxc
= buffer
.getInt(); /* Max nb of children per node */
180 this.nodeCount
= buffer
.getInt();
181 rootNodeSeqNb
= buffer
.getInt();
182 startTime
= buffer
.getLong();
184 this.config
= new HTConfig(existingStateFile
, bs
, maxc
, expProviderVersion
, startTime
);
188 * FIXME We close fis here and the TreeIO will then reopen the same
189 * file, not extremely elegant. But how to pass the information here to
192 this.treeIO
= new HT_IO(config
, false);
194 this.latestBranch
= buildLatestBranch(rootNodeSeqNb
);
195 this.treeEnd
= getRootNode().getNodeEnd();
198 * Make sure the history start time we read previously is consistent
199 * with was is actually in the root node.
201 if (startTime
!= getRootNode().getNodeStart()) {
202 throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
203 "history file, it might be corrupted."); //$NON-NLS-1$
208 * Rebuild the latestBranch "cache" object by reading the nodes from disk
209 * (When we are opening an existing file on disk and want to append to it,
212 * @param rootNodeSeqNb
213 * The sequence number of the root node, so we know where to
215 * @throws ClosedChannelException
217 private List
<HTNode
> buildLatestBranch(int rootNodeSeqNb
) throws ClosedChannelException
{
218 List
<HTNode
> list
= new ArrayList
<>();
220 HTNode nextChildNode
= treeIO
.readNode(rootNodeSeqNb
);
221 list
.add(nextChildNode
);
223 /* Follow the last branch up to the leaf */
224 while (nextChildNode
.getNodeType() == HTNode
.NodeType
.CORE
) {
225 nextChildNode
= treeIO
.readNode(((CoreNode
) nextChildNode
).getLatestChild());
226 list
.add(nextChildNode
);
228 return Collections
.synchronizedList(list
);
232 * "Save" the tree to disk. This method will cause the treeIO object to
233 * commit all nodes to disk and then return the RandomAccessFile descriptor
234 * so the Tree object can save its configuration into the header of the
237 * @param requestedEndTime
238 * The greatest timestamp present in the history tree
240 public void closeTree(long requestedEndTime
) {
241 /* This is an important operation, queries can wait */
242 synchronized (latestBranch
) {
244 * Work-around the "empty branches" that get created when the root
245 * node becomes full. Overwrite the tree's end time with the
246 * original wanted end-time, to ensure no queries are sent into
249 * This won't be needed once extended nodes are implemented.
251 this.treeEnd
= requestedEndTime
;
253 /* Close off the latest branch of the tree */
254 for (int i
= 0; i
< latestBranch
.size(); i
++) {
255 latestBranch
.get(i
).closeThisNode(treeEnd
);
256 treeIO
.writeNode(latestBranch
.get(i
));
259 try (FileChannel fc
= treeIO
.getFcOut();) {
260 ByteBuffer buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
261 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
264 /* Save the config of the tree to the header of the file */
267 buffer
.putInt(HISTORY_FILE_MAGIC_NUMBER
);
269 buffer
.putInt(FILE_VERSION
);
270 buffer
.putInt(config
.getProviderVersion());
272 buffer
.putInt(config
.getBlockSize());
273 buffer
.putInt(config
.getMaxChildren());
275 buffer
.putInt(nodeCount
);
277 /* root node seq. nb */
278 buffer
.putInt(latestBranch
.get(0).getSequenceNumber());
280 /* start time of this history */
281 buffer
.putLong(latestBranch
.get(0).getNodeStart());
284 int res
= fc
.write(buffer
);
285 assert (res
<= TREE_HEADER_SIZE
);
286 /* done writing the file header */
288 } catch (IOException e
) {
290 * If we were able to write so far, there should not be any
291 * problem at this point...
293 throw new RuntimeException("State system write error"); //$NON-NLS-1$
298 // ------------------------------------------------------------------------
300 // ------------------------------------------------------------------------
303 * Get the start time of this tree.
305 * @return The start time
307 public long getTreeStart() {
308 return config
.getTreeStart();
312 * Get the current end time of this tree.
314 * @return The end time
316 public long getTreeEnd() {
321 * Get the number of nodes in this tree.
323 * @return The number of nodes
325 public int getNodeCount() {
330 * Get the current root node of this tree
332 * @return The root node
334 public HTNode
getRootNode() {
335 return latestBranch
.get(0);
338 // ------------------------------------------------------------------------
340 // ------------------------------------------------------------------------
343 * Return the FileInputStream reader with which we will read an attribute
344 * tree (it will be sought to the correct position).
346 * @return The FileInputStream indicating the file and position from which
347 * the attribute tree can be read.
349 public FileInputStream
supplyATReader() {
350 return treeIO
.supplyATReader(getNodeCount());
354 * Return the file to which we will write the attribute tree.
356 * @return The file to which we will write the attribute tree
358 public File
supplyATWriterFile() {
359 return config
.getStateFile();
363 * Return the position in the file (given by {@link #supplyATWriterFile})
364 * where to start writing the attribute tree.
366 * @return The position in the file where to start writing
368 public long supplyATWriterFilePos() {
369 return HistoryTree
.TREE_HEADER_SIZE
370 + ((long) getNodeCount() * config
.getBlockSize());
374 * Read a node from the tree.
377 * The sequence number of the node to read
379 * @throws ClosedChannelException
380 * If the tree IO is unavailable
382 public HTNode
readNode(int seqNumber
) throws ClosedChannelException
{
383 /* Try to read the node from memory */
384 synchronized (latestBranch
) {
385 for (HTNode node
: latestBranch
) {
386 if (node
.getSequenceNumber() == seqNumber
) {
392 /* Read the node from disk */
393 return treeIO
.readNode(seqNumber
);
397 * Write a node object to the history file.
400 * The node to write to disk
402 public void writeNode(HTNode node
) {
403 treeIO
.writeNode(node
);
407 * Close the history file.
409 public void closeFile() {
414 * Delete the history file.
416 public void deleteFile() {
420 // ------------------------------------------------------------------------
422 // ------------------------------------------------------------------------
425 * Insert an interval in the tree.
428 * The interval to be inserted
429 * @throws TimeRangeException
430 * If the start of end time of the interval are invalid
432 public void insertInterval(HTInterval interval
) throws TimeRangeException
{
433 if (interval
.getStartTime() < config
.getTreeStart()) {
434 throw new TimeRangeException("Interval Start:" + interval
.getStartTime() + ", Config Start:" + config
.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$
436 tryInsertAtNode(interval
, latestBranch
.size() - 1);
440 * Inner method to find in which node we should add the interval.
443 * The interval to add to the tree
445 * The index *in the latestBranch* where we are trying the
448 private void tryInsertAtNode(HTInterval interval
, int indexOfNode
) {
449 HTNode targetNode
= latestBranch
.get(indexOfNode
);
451 /* Verify if there is enough room in this node to store this interval */
452 if (interval
.getIntervalSize() > targetNode
.getNodeFreeSpace()) {
453 /* Nope, not enough room. Insert in a new sibling instead. */
454 addSiblingNode(indexOfNode
);
455 tryInsertAtNode(interval
, latestBranch
.size() - 1);
459 /* Make sure the interval time range fits this node */
460 if (interval
.getStartTime() < targetNode
.getNodeStart()) {
462 * No, this interval starts before the startTime of this node. We
463 * need to check recursively in parents if it can fit.
465 assert (indexOfNode
>= 1);
466 tryInsertAtNode(interval
, indexOfNode
- 1);
471 * Ok, there is room, and the interval fits in this time slot. Let's add
474 targetNode
.addInterval(interval
);
476 /* Update treeEnd if needed */
477 if (interval
.getEndTime() > this.treeEnd
) {
478 this.treeEnd
= interval
.getEndTime();
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.
487 * The index in latestBranch where we start adding
489 private void addSiblingNode(int indexOfNode
) {
490 synchronized (latestBranch
) {
491 final long splitTime
= treeEnd
;
493 if (indexOfNode
>= latestBranch
.size()) {
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.
498 throw new IllegalStateException();
501 /* Check if we need to add a new root node */
502 if (indexOfNode
== 0) {
507 /* Check if we can indeed add a child to the target parent */
508 if (((CoreNode
) latestBranch
.get(indexOfNode
- 1)).getNbChildren() == config
.getMaxChildren()) {
509 /* If not, add a branch starting one level higher instead */
510 addSiblingNode(indexOfNode
- 1);
514 /* Split off the new branch from the old one */
515 for (int i
= indexOfNode
; i
< latestBranch
.size(); i
++) {
516 latestBranch
.get(i
).closeThisNode(splitTime
);
517 treeIO
.writeNode(latestBranch
.get(i
));
519 CoreNode prevNode
= (CoreNode
) latestBranch
.get(i
- 1);
522 switch (latestBranch
.get(i
).getNodeType()) {
524 newNode
= initNewCoreNode(prevNode
.getSequenceNumber(), splitTime
+ 1);
527 newNode
= initNewLeafNode(prevNode
.getSequenceNumber(), splitTime
+ 1);
530 throw new IllegalStateException();
533 prevNode
.linkNewChild(newNode
);
534 latestBranch
.set(i
, newNode
);
540 * Similar to the previous method, except here we rebuild a completely new
543 private void addNewRootNode() {
544 final long splitTime
= this.treeEnd
;
546 HTNode oldRootNode
= latestBranch
.get(0);
547 CoreNode newRootNode
= initNewCoreNode(-1, config
.getTreeStart());
549 /* Tell the old root node that it isn't root anymore */
550 oldRootNode
.setParentSequenceNumber(newRootNode
.getSequenceNumber());
552 /* Close off the whole current latestBranch */
554 for (int i
= 0; i
< latestBranch
.size(); i
++) {
555 latestBranch
.get(i
).closeThisNode(splitTime
);
556 treeIO
.writeNode(latestBranch
.get(i
));
559 /* Link the new root to its first child (the previous root node) */
560 newRootNode
.linkNewChild(oldRootNode
);
562 /* Rebuild a new latestBranch */
563 int depth
= latestBranch
.size();
564 latestBranch
.clear();
565 latestBranch
.add(newRootNode
);
567 // Create new coreNode
568 for (int i
= 1; i
< depth
+ 1; i
++) {
569 CoreNode prevNode
= (CoreNode
) latestBranch
.get(i
- 1);
570 CoreNode newNode
= initNewCoreNode(prevNode
.getParentSequenceNumber(),
572 prevNode
.linkNewChild(newNode
);
573 latestBranch
.add(newNode
);
576 // Create the new leafNode
577 CoreNode prevNode
= (CoreNode
) latestBranch
.get(depth
);
578 LeafNode newNode
= initNewLeafNode(prevNode
.getParentSequenceNumber(), splitTime
+ 1);
579 prevNode
.linkNewChild(newNode
);
580 latestBranch
.add(newNode
);
584 * Add a new empty core node to the tree.
586 * @param parentSeqNumber
587 * Sequence number of this node's parent
589 * Start time of the new node
590 * @return The newly created node
592 private CoreNode
initNewCoreNode(int parentSeqNumber
, long startTime
) {
593 CoreNode newNode
= new CoreNode(config
, this.nodeCount
, parentSeqNumber
,
597 /* Update the treeEnd if needed */
598 if (startTime
>= this.treeEnd
) {
599 this.treeEnd
= startTime
+ 1;
605 * Add a new empty leaf node to the tree.
607 * @param parentSeqNumber
608 * Sequence number of this node's parent
610 * Start time of the new node
611 * @return The newly created node
613 private LeafNode
initNewLeafNode(int parentSeqNumber
, long startTime
) {
614 LeafNode newNode
= new LeafNode(config
, this.nodeCount
, parentSeqNumber
,
618 /* Update the treeEnd if needed */
619 if (startTime
>= this.treeEnd
) {
620 this.treeEnd
= startTime
+ 1;
626 * Inner method to select the next child of the current node intersecting
627 * the given timestamp. Useful for moving down the tree following one
631 * The node on which the request is made
633 * The timestamp to choose which child is the next one
634 * @return The child node intersecting t
635 * @throws ClosedChannelException
636 * If the file channel was closed while we were reading the tree
638 public HTNode
selectNextChild(CoreNode currentNode
, long t
) throws ClosedChannelException
{
639 assert (currentNode
.getNbChildren() > 0);
640 int potentialNextSeqNb
= currentNode
.getSequenceNumber();
642 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
643 if (t
>= currentNode
.getChildStart(i
)) {
644 potentialNextSeqNb
= currentNode
.getChild(i
);
651 * Once we exit this loop, we should have found a children to follow. If
652 * we didn't, there's a problem.
654 assert (potentialNextSeqNb
!= currentNode
.getSequenceNumber());
657 * Since this code path is quite performance-critical, avoid iterating
658 * through the whole latestBranch array if we know for sure the next
659 * node has to be on disk
661 if (currentNode
.isOnDisk()) {
662 return treeIO
.readNode(potentialNextSeqNb
);
664 return readNode(potentialNextSeqNb
);
668 * Get the current size of the history file.
670 * @return The history file size
672 public long getFileSize() {
673 return config
.getStateFile().length();
676 // ------------------------------------------------------------------------
677 // Test/debugging methods
678 // ------------------------------------------------------------------------
681 * Debugging method to make sure all intervals contained in the given node
682 * have valid start and end times.
686 * @return True if everything is fine, false if there is at least one
687 * invalid timestamp (end time < start time, time outside of the
688 * range of the node, etc.)
690 @SuppressWarnings("nls")
691 public boolean checkNodeIntegrity(HTNode zenode
) {
692 /* Only used for debugging, shouldn't be externalized */
695 StringBuffer buf
= new StringBuffer();
698 // FIXME /* Only testing Core Nodes for now */
699 if (!(zenode
instanceof CoreNode
)) {
703 node
= (CoreNode
) zenode
;
707 * Test that this node's start and end times match the start of the
708 * first child and the end of the last child, respectively
710 if (node
.getNbChildren() > 0) {
711 otherNode
= treeIO
.readNode(node
.getChild(0));
712 if (node
.getNodeStart() != otherNode
.getNodeStart()) {
713 buf
.append("Start time of node (" + node
.getNodeStart() + ") "
714 + "does not match start time of first child " + "("
715 + otherNode
.getNodeStart() + "), " + "node #"
716 + otherNode
.getSequenceNumber() + ")\n");
719 if (node
.isOnDisk()) {
720 otherNode
= treeIO
.readNode(node
.getLatestChild());
721 if (node
.getNodeEnd() != otherNode
.getNodeEnd()) {
722 buf
.append("End time of node (" + node
.getNodeEnd()
723 + ") does not match end time of last child ("
724 + otherNode
.getNodeEnd() + ", node #"
725 + otherNode
.getSequenceNumber() + ")\n");
732 * Test that the childStartTimes[] array matches the real nodes'
735 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
736 otherNode
= treeIO
.readNode(node
.getChild(i
));
737 if (otherNode
.getNodeStart() != node
.getChildStart(i
)) {
738 buf
.append(" Expected start time of child node #"
739 + node
.getChild(i
) + ": " + node
.getChildStart(i
)
740 + "\n" + " Actual start time of node #"
741 + otherNode
.getSequenceNumber() + ": "
742 + otherNode
.getNodeStart() + "\n");
747 } catch (ClosedChannelException e
) {
752 System
.out
.println("");
753 System
.out
.println("SHT: Integrity check failed for node #"
754 + node
.getSequenceNumber() + ":");
755 System
.out
.println(buf
.toString());
761 * Check the integrity of all the nodes in the tree. Calls
762 * {@link #checkNodeIntegrity} for every node in the tree.
764 public void checkIntegrity() {
766 for (int i
= 0; i
< nodeCount
; i
++) {
767 checkNodeIntegrity(treeIO
.readNode(i
));
769 } catch (ClosedChannelException e
) {
773 /* Only used for debugging, shouldn't be externalized */
774 @SuppressWarnings("nls")
776 public String
toString() {
777 return "Information on the current tree:\n\n" + "Blocksize: "
778 + config
.getBlockSize() + "\n" + "Max nb. of children per node: "
779 + config
.getMaxChildren() + "\n" + "Number of nodes: " + nodeCount
780 + "\n" + "Depth of the tree: " + latestBranch
.size() + "\n"
781 + "Size of the treefile: " + this.getFileSize() + "\n"
782 + "Root node has sequence number: "
783 + latestBranch
.get(0).getSequenceNumber() + "\n"
784 + "'Latest leaf' has sequence number: "
785 + latestBranch
.get(latestBranch
.size() - 1).getSequenceNumber();
789 * Start at currentNode and print the contents of all its children, in
790 * pre-order. Give the root node in parameter to visit the whole tree, and
791 * have a nice overview.
793 /* Only used for debugging, shouldn't be externalized */
794 @SuppressWarnings("nls")
795 private void preOrderPrint(PrintWriter writer
, boolean printIntervals
,
796 HTNode currentNode
, int curDepth
) {
798 writer
.println(currentNode
.toString());
799 if (printIntervals
) {
800 currentNode
.debugPrintIntervals(writer
);
803 switch (currentNode
.getNodeType()) {
805 /* Stop if it's the leaf node */
810 final CoreNode node
= (CoreNode
) currentNode
;
811 /* Print the extensions, if any */
812 int extension
= node
.getExtensionSequenceNumber();
813 while (extension
!= -1) {
814 HTNode nextNode
= treeIO
.readNode(extension
);
815 preOrderPrint(writer
, printIntervals
, nextNode
, curDepth
);
818 /* Print the child nodes */
819 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
820 HTNode nextNode
= treeIO
.readNode(node
.getChild(i
));
821 for (int j
= 0; j
< curDepth
; j
++) {
825 preOrderPrint(writer
, printIntervals
, nextNode
, curDepth
+ 1);
827 } catch (ClosedChannelException e
) {
828 Activator
.getDefault().logError(e
.getMessage());
838 * Print out the full tree for debugging purposes
841 * PrintWriter in which to write the output
842 * @param printIntervals
843 * Flag to enable full output of the interval information
845 public void debugPrintFullTree(PrintWriter writer
, boolean printIntervals
) {
846 /* Only used for debugging, shouldn't be externalized */
848 this.preOrderPrint(writer
, false, latestBranch
.get(0), 0);
850 if (printIntervals
) {
851 writer
.println("\nDetails of intervals:"); //$NON-NLS-1$
852 this.preOrderPrint(writer
, true, latestBranch
.get(0), 0);
854 writer
.println('\n');