1 /*******************************************************************************
2 * Copyright (c) 2012, 2014 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.
34 * @author Alexandre Montplaisir
36 public class HistoryTree
{
39 * Size of the "tree header" in the tree-file The nodes will use this offset
40 * to know where they should be in the file. This should always be a
43 public static final int TREE_HEADER_SIZE
= 4096;
45 private static final int HISTORY_FILE_MAGIC_NUMBER
= 0x05FFA900;
47 /** File format version. Increment when breaking compatibility. */
48 private static final int FILE_VERSION
= 3;
50 // ------------------------------------------------------------------------
51 // Tree-specific configuration
52 // ------------------------------------------------------------------------
54 /** Container for all the configuration constants */
55 private final HTConfig config
;
57 /** Reader/writer object */
58 private final HT_IO treeIO
;
60 // ------------------------------------------------------------------------
61 // Variable Fields (will change throughout the existence of the SHT)
62 // ------------------------------------------------------------------------
64 /** Latest timestamp found in the tree (at any given moment) */
67 /** The total number of nodes that exists in this tree */
68 private int nodeCount
;
70 /** "Cache" to keep the active nodes in memory */
71 private final List
<CoreNode
> latestBranch
;
73 // ------------------------------------------------------------------------
74 // Constructors/"Destructors"
75 // ------------------------------------------------------------------------
78 * Create a new State History from scratch, using a {@link HTConfig} object
82 * The config to use for this History Tree.
84 * If an error happens trying to open/write to the file
85 * specified in the config
87 public HistoryTree(HTConfig conf
) throws IOException
{
89 * Simple check to make sure we have enough place in the 0th block
90 * for the tree configuration
92 if (conf
.getBlockSize() < TREE_HEADER_SIZE
) {
93 throw new IllegalArgumentException();
97 treeEnd
= conf
.getTreeStart();
99 latestBranch
= Collections
.synchronizedList(new ArrayList
<CoreNode
>());
101 /* Prepare the IO object */
102 treeIO
= new HT_IO(config
, true);
104 /* Add the first node to the tree */
105 CoreNode firstNode
= initNewCoreNode(-1, conf
.getTreeStart());
106 latestBranch
.add(firstNode
);
110 * "Reader" constructor : instantiate a SHTree from an existing tree file on
113 * @param existingStateFile
114 * Path/filename of the history-file we are to open
115 * @param expProviderVersion
116 * The expected version of the state provider
117 * @throws IOException
118 * If an error happens reading the file
120 public HistoryTree(File existingStateFile
, int expProviderVersion
) throws IOException
{
122 * Open the file ourselves, get the tree header information we need,
123 * then pass on the descriptor to the TreeIO object.
125 int rootNodeSeqNb
, res
;
129 /* Java I/O mumbo jumbo... */
130 if (!existingStateFile
.exists()) {
131 throw new IOException("Selected state file does not exist"); //$NON-NLS-1$
133 if (existingStateFile
.length() <= 0) {
134 throw new IOException("Empty target file"); //$NON-NLS-1$
137 try (FileInputStream fis
= new FileInputStream(existingStateFile
);
138 FileChannel fc
= fis
.getChannel();) {
140 ByteBuffer buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
142 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
148 * Check the magic number to make sure we're opening the right type
151 res
= buffer
.getInt();
152 if (res
!= HISTORY_FILE_MAGIC_NUMBER
) {
153 throw new IOException("Wrong magic number"); //$NON-NLS-1$
156 res
= buffer
.getInt(); /* File format version number */
157 if (res
!= FILE_VERSION
) {
158 throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$
161 res
= buffer
.getInt(); /* Event handler's version number */
162 if (res
!= expProviderVersion
&&
163 expProviderVersion
!= ITmfStateProvider
.IGNORE_PROVIDER_VERSION
) {
165 * The existing history was built using an event handler that
166 * doesn't match the current one in the framework.
168 * Information could be all wrong. Instead of keeping an
169 * incorrect history file, a rebuild is done.
171 throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$
174 bs
= buffer
.getInt(); /* Block Size */
175 maxc
= buffer
.getInt(); /* Max nb of children per node */
177 this.nodeCount
= buffer
.getInt();
178 rootNodeSeqNb
= buffer
.getInt();
179 startTime
= buffer
.getLong();
181 this.config
= new HTConfig(existingStateFile
, bs
, maxc
, expProviderVersion
, startTime
);
185 * FIXME We close fis here and the TreeIO will then reopen the same
186 * file, not extremely elegant. But how to pass the information here to
189 this.treeIO
= new HT_IO(config
, false);
191 this.latestBranch
= buildLatestBranch(rootNodeSeqNb
);
192 this.treeEnd
= getRootNode().getNodeEnd();
195 * Make sure the history start time we read previously is consistent
196 * with was is actually in the root node.
198 if (startTime
!= getRootNode().getNodeStart()) {
199 throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$
200 "history file, it might be corrupted."); //$NON-NLS-1$
205 * Rebuild the latestBranch "cache" object by reading the nodes from disk
206 * (When we are opening an existing file on disk and want to append to it,
209 * @param rootNodeSeqNb
210 * The sequence number of the root node, so we know where to
212 * @throws ClosedChannelException
214 private List
<CoreNode
> buildLatestBranch(int rootNodeSeqNb
) throws ClosedChannelException
{
215 HTNode nextChildNode
;
217 List
<CoreNode
> list
= new ArrayList
<>();
219 nextChildNode
= treeIO
.readNode(rootNodeSeqNb
);
220 list
.add((CoreNode
) nextChildNode
);
221 while (list
.get(list
.size() - 1).getNbChildren() > 0) {
222 nextChildNode
= treeIO
.readNode(list
.get(list
.size() - 1).getLatestChild());
223 list
.add((CoreNode
) nextChildNode
);
225 return Collections
.synchronizedList(list
);
229 * "Save" the tree to disk. This method will cause the treeIO object to
230 * commit all nodes to disk and then return the RandomAccessFile descriptor
231 * so the Tree object can save its configuration into the header of the
234 * @param requestedEndTime
235 * The greatest timestamp present in the history tree
237 public void closeTree(long requestedEndTime
) {
238 /* This is an important operation, queries can wait */
239 synchronized (latestBranch
) {
241 * Work-around the "empty branches" that get created when the root
242 * node becomes full. Overwrite the tree's end time with the
243 * original wanted end-time, to ensure no queries are sent into
246 * This won't be needed once extended nodes are implemented.
248 this.treeEnd
= requestedEndTime
;
250 /* Close off the latest branch of the tree */
251 for (int i
= 0; i
< latestBranch
.size(); i
++) {
252 latestBranch
.get(i
).closeThisNode(treeEnd
);
253 treeIO
.writeNode(latestBranch
.get(i
));
256 try (FileChannel fc
= treeIO
.getFcOut();) {
257 ByteBuffer buffer
= ByteBuffer
.allocate(TREE_HEADER_SIZE
);
258 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
261 /* Save the config of the tree to the header of the file */
264 buffer
.putInt(HISTORY_FILE_MAGIC_NUMBER
);
266 buffer
.putInt(FILE_VERSION
);
267 buffer
.putInt(config
.getProviderVersion());
269 buffer
.putInt(config
.getBlockSize());
270 buffer
.putInt(config
.getMaxChildren());
272 buffer
.putInt(nodeCount
);
274 /* root node seq. nb */
275 buffer
.putInt(latestBranch
.get(0).getSequenceNumber());
277 /* start time of this history */
278 buffer
.putLong(latestBranch
.get(0).getNodeStart());
281 int res
= fc
.write(buffer
);
282 assert (res
<= TREE_HEADER_SIZE
);
283 /* done writing the file header */
285 } catch (IOException e
) {
287 * If we were able to write so far, there should not be any
288 * problem at this point...
290 throw new RuntimeException("State system write error"); //$NON-NLS-1$
295 // ------------------------------------------------------------------------
297 // ------------------------------------------------------------------------
300 * Get the start time of this tree.
302 * @return The start time
304 public long getTreeStart() {
305 return config
.getTreeStart();
309 * Get the current end time of this tree.
311 * @return The end time
313 public long getTreeEnd() {
318 * Get the number of nodes in this tree.
320 * @return The number of nodes
322 public int getNodeCount() {
327 * Get the current root node of this tree
329 * @return The root node
331 public CoreNode
getRootNode() {
332 return latestBranch
.get(0);
335 // ------------------------------------------------------------------------
337 // ------------------------------------------------------------------------
340 * Return the FileInputStream reader with which we will read an attribute
341 * tree (it will be sought to the correct position).
343 * @return The FileInputStream indicating the file and position from which
344 * the attribute tree can be read.
346 public FileInputStream
supplyATReader() {
347 return treeIO
.supplyATReader(getNodeCount());
351 * Return the file to which we will write the attribute tree.
353 * @return The file to which we will write the attribute tree
355 public File
supplyATWriterFile() {
356 return config
.getStateFile();
360 * Return the position in the file (given by {@link #supplyATWriterFile})
361 * where to start writing the attribute tree.
363 * @return The position in the file where to start writing
365 public long supplyATWriterFilePos() {
366 return HistoryTree
.TREE_HEADER_SIZE
367 + ((long) getNodeCount() * config
.getBlockSize());
371 * Read a node from the tree.
374 * The sequence number of the node to read
376 * @throws ClosedChannelException
377 * If the tree IO is unavailable
379 public HTNode
readNode(int seqNumber
) throws ClosedChannelException
{
380 /* Try to read the node from memory */
381 synchronized (latestBranch
) {
382 for (HTNode node
: latestBranch
) {
383 if (node
.getSequenceNumber() == seqNumber
) {
389 /* Read the node from disk */
390 return treeIO
.readNode(seqNumber
);
394 * Write a node object to the history file.
397 * The node to write to disk
399 public void writeNode(HTNode node
) {
400 treeIO
.writeNode(node
);
404 * Close the history file.
406 public void closeFile() {
411 * Delete the history file.
413 public void deleteFile() {
417 // ------------------------------------------------------------------------
419 // ------------------------------------------------------------------------
422 * Insert an interval in the tree.
425 * The interval to be inserted
426 * @throws TimeRangeException
427 * If the start of end time of the interval are invalid
429 public void insertInterval(HTInterval interval
) throws TimeRangeException
{
430 if (interval
.getStartTime() < config
.getTreeStart()) {
431 throw new TimeRangeException();
433 tryInsertAtNode(interval
, latestBranch
.size() - 1);
437 * Inner method to find in which node we should add the interval.
440 * The interval to add to the tree
442 * The index *in the latestBranch* where we are trying the
445 private void tryInsertAtNode(HTInterval interval
, int indexOfNode
) {
446 HTNode targetNode
= latestBranch
.get(indexOfNode
);
448 /* Verify if there is enough room in this node to store this interval */
449 if (interval
.getIntervalSize() > targetNode
.getNodeFreeSpace()) {
450 /* Nope, not enough room. Insert in a new sibling instead. */
451 addSiblingNode(indexOfNode
);
452 tryInsertAtNode(interval
, latestBranch
.size() - 1);
456 /* Make sure the interval time range fits this node */
457 if (interval
.getStartTime() < targetNode
.getNodeStart()) {
459 * No, this interval starts before the startTime of this node. We
460 * need to check recursively in parents if it can fit.
462 assert (indexOfNode
>= 1);
463 tryInsertAtNode(interval
, indexOfNode
- 1);
468 * Ok, there is room, and the interval fits in this time slot. Let's add
471 targetNode
.addInterval(interval
);
473 /* Update treeEnd if needed */
474 if (interval
.getEndTime() > this.treeEnd
) {
475 this.treeEnd
= interval
.getEndTime();
480 * Method to add a sibling to any node in the latest branch. This will add
481 * children back down to the leaf level, if needed.
484 * The index in latestBranch where we start adding
486 private void addSiblingNode(int indexOfNode
) {
487 synchronized (latestBranch
) {
488 final long splitTime
= treeEnd
;
490 assert (indexOfNode
< latestBranch
.size());
492 /* Check if we need to add a new root node */
493 if (indexOfNode
== 0) {
498 /* Check if we can indeed add a child to the target parent */
499 if (latestBranch
.get(indexOfNode
- 1).getNbChildren() == config
.getMaxChildren()) {
500 /* If not, add a branch starting one level higher instead */
501 addSiblingNode(indexOfNode
- 1);
505 /* Split off the new branch from the old one */
506 for (int i
= indexOfNode
; i
< latestBranch
.size(); i
++) {
507 latestBranch
.get(i
).closeThisNode(splitTime
);
508 treeIO
.writeNode(latestBranch
.get(i
));
510 CoreNode prevNode
= latestBranch
.get(i
- 1);
511 CoreNode newNode
= initNewCoreNode(prevNode
.getSequenceNumber(),
513 prevNode
.linkNewChild(newNode
);
515 latestBranch
.set(i
, newNode
);
521 * Similar to the previous method, except here we rebuild a completely new
524 private void addNewRootNode() {
525 final long splitTime
= this.treeEnd
;
527 CoreNode oldRootNode
= latestBranch
.get(0);
528 CoreNode newRootNode
= initNewCoreNode(-1, config
.getTreeStart());
530 /* Tell the old root node that it isn't root anymore */
531 oldRootNode
.setParentSequenceNumber(newRootNode
.getSequenceNumber());
533 /* Close off the whole current latestBranch */
535 for (int i
= 0; i
< latestBranch
.size(); i
++) {
536 latestBranch
.get(i
).closeThisNode(splitTime
);
537 treeIO
.writeNode(latestBranch
.get(i
));
540 /* Link the new root to its first child (the previous root node) */
541 newRootNode
.linkNewChild(oldRootNode
);
543 /* Rebuild a new latestBranch */
544 int depth
= latestBranch
.size();
545 latestBranch
.clear();
546 latestBranch
.add(newRootNode
);
547 for (int i
= 1; i
< depth
+ 1; i
++) {
548 CoreNode prevNode
= latestBranch
.get(i
- 1);
549 CoreNode newNode
= initNewCoreNode(prevNode
.getParentSequenceNumber(),
551 prevNode
.linkNewChild(newNode
);
552 latestBranch
.add(newNode
);
557 * Add a new empty node to the tree.
559 * @param parentSeqNumber
560 * Sequence number of this node's parent
562 * Start time of the new node
563 * @return The newly created node
565 private CoreNode
initNewCoreNode(int parentSeqNumber
, long startTime
) {
566 CoreNode newNode
= new CoreNode(config
, this.nodeCount
, parentSeqNumber
,
570 /* Update the treeEnd if needed */
571 if (startTime
>= this.treeEnd
) {
572 this.treeEnd
= startTime
+ 1;
578 * Inner method to select the next child of the current node intersecting
579 * the given timestamp. Useful for moving down the tree following one
583 * The node on which the request is made
585 * The timestamp to choose which child is the next one
586 * @return The child node intersecting t
587 * @throws ClosedChannelException
588 * If the file channel was closed while we were reading the tree
590 public HTNode
selectNextChild(CoreNode currentNode
, long t
) throws ClosedChannelException
{
591 assert (currentNode
.getNbChildren() > 0);
592 int potentialNextSeqNb
= currentNode
.getSequenceNumber();
594 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
595 if (t
>= currentNode
.getChildStart(i
)) {
596 potentialNextSeqNb
= currentNode
.getChild(i
);
603 * Once we exit this loop, we should have found a children to follow. If
604 * we didn't, there's a problem.
606 assert (potentialNextSeqNb
!= currentNode
.getSequenceNumber());
609 * Since this code path is quite performance-critical, avoid iterating
610 * through the whole latestBranch array if we know for sure the next
611 * node has to be on disk
613 if (currentNode
.isOnDisk()) {
614 return treeIO
.readNode(potentialNextSeqNb
);
616 return readNode(potentialNextSeqNb
);
620 * Get the current size of the history file.
622 * @return The history file size
624 public long getFileSize() {
625 return config
.getStateFile().length();
628 // ------------------------------------------------------------------------
629 // Test/debugging methods
630 // ------------------------------------------------------------------------
633 * Debugging method to make sure all intervals contained in the given node
634 * have valid start and end times.
638 * @return True if everything is fine, false if there is at least one
639 * invalid timestamp (end time < start time, time outside of the
640 * range of the node, etc.)
642 @SuppressWarnings("nls")
643 public boolean checkNodeIntegrity(HTNode zenode
) {
644 /* Only used for debugging, shouldn't be externalized */
647 StringBuffer buf
= new StringBuffer();
650 // FIXME /* Only testing Core Nodes for now */
651 if (!(zenode
instanceof CoreNode
)) {
655 node
= (CoreNode
) zenode
;
659 * Test that this node's start and end times match the start of the
660 * first child and the end of the last child, respectively
662 if (node
.getNbChildren() > 0) {
663 otherNode
= treeIO
.readNode(node
.getChild(0));
664 if (node
.getNodeStart() != otherNode
.getNodeStart()) {
665 buf
.append("Start time of node (" + node
.getNodeStart() + ") "
666 + "does not match start time of first child " + "("
667 + otherNode
.getNodeStart() + "), " + "node #"
668 + otherNode
.getSequenceNumber() + ")\n");
671 if (node
.isOnDisk()) {
672 otherNode
= treeIO
.readNode(node
.getLatestChild());
673 if (node
.getNodeEnd() != otherNode
.getNodeEnd()) {
674 buf
.append("End time of node (" + node
.getNodeEnd()
675 + ") does not match end time of last child ("
676 + otherNode
.getNodeEnd() + ", node #"
677 + otherNode
.getSequenceNumber() + ")\n");
684 * Test that the childStartTimes[] array matches the real nodes' start
687 for (int i
= 0; i
< node
.getNbChildren(); i
++) {
688 otherNode
= treeIO
.readNode(node
.getChild(i
));
689 if (otherNode
.getNodeStart() != node
.getChildStart(i
)) {
690 buf
.append(" Expected start time of child node #"
691 + node
.getChild(i
) + ": " + node
.getChildStart(i
)
692 + "\n" + " Actual start time of node #"
693 + otherNode
.getSequenceNumber() + ": "
694 + otherNode
.getNodeStart() + "\n");
699 } catch (ClosedChannelException e
) {
704 System
.out
.println("");
705 System
.out
.println("SHT: Integrity check failed for node #"
706 + node
.getSequenceNumber() + ":");
707 System
.out
.println(buf
.toString());
713 * Check the integrity of all the nodes in the tree. Calls
714 * {@link #checkNodeIntegrity} for every node in the tree.
716 public void checkIntegrity() {
718 for (int i
= 0; i
< nodeCount
; i
++) {
719 checkNodeIntegrity(treeIO
.readNode(i
));
721 } catch (ClosedChannelException e
) {
725 /* Only used for debugging, shouldn't be externalized */
726 @SuppressWarnings("nls")
728 public String
toString() {
729 return "Information on the current tree:\n\n" + "Blocksize: "
730 + config
.getBlockSize() + "\n" + "Max nb. of children per node: "
731 + config
.getMaxChildren() + "\n" + "Number of nodes: " + nodeCount
732 + "\n" + "Depth of the tree: " + latestBranch
.size() + "\n"
733 + "Size of the treefile: " + this.getFileSize() + "\n"
734 + "Root node has sequence number: "
735 + latestBranch
.get(0).getSequenceNumber() + "\n"
736 + "'Latest leaf' has sequence number: "
737 + latestBranch
.get(latestBranch
.size() - 1).getSequenceNumber();
741 * Start at currentNode and print the contents of all its children, in
742 * pre-order. Give the root node in parameter to visit the whole tree, and
743 * have a nice overview.
745 /* Only used for debugging, shouldn't be externalized */
746 @SuppressWarnings("nls")
747 private void preOrderPrint(PrintWriter writer
, boolean printIntervals
,
748 CoreNode currentNode
, int curDepth
) {
750 writer
.println(currentNode
.toString());
751 if (printIntervals
) {
752 currentNode
.debugPrintIntervals(writer
);
756 for (int i
= 0; i
< currentNode
.getNbChildren(); i
++) {
757 HTNode nextNode
= treeIO
.readNode(currentNode
.getChild(i
));
758 assert (nextNode
instanceof CoreNode
); // TODO temporary
759 for (int j
= 0; j
< curDepth
; j
++) {
763 preOrderPrint(writer
, printIntervals
, (CoreNode
) nextNode
,
766 } catch (ClosedChannelException e
) {
772 * Print out the full tree for debugging purposes
775 * PrintWriter in which to write the output
776 * @param printIntervals
777 * Flag to enable full output of the interval information
779 public void debugPrintFullTree(PrintWriter writer
, boolean printIntervals
) {
780 /* Only used for debugging, shouldn't be externalized */
782 this.preOrderPrint(writer
, false, latestBranch
.get(0), 0);
784 if (printIntervals
) {
785 writer
.println("\nDetails of intervals:"); //$NON-NLS-1$
786 this.preOrderPrint(writer
, true, latestBranch
.get(0), 0);
788 writer
.println('\n');