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 - Keep interval list sorted on insert
13 *******************************************************************************/
15 package org
.eclipse
.tracecompass
.internal
.statesystem
.core
.backend
.historytree
;
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
.ArrayList
;
23 import java
.util
.Collections
;
24 import java
.util
.List
;
25 import java
.util
.concurrent
.locks
.ReentrantReadWriteLock
;
27 import org
.eclipse
.tracecompass
.statesystem
.core
.exceptions
.TimeRangeException
;
28 import org
.eclipse
.tracecompass
.statesystem
.core
.interval
.ITmfStateInterval
;
29 import org
.eclipse
.tracecompass
.statesystem
.core
.statevalue
.TmfStateValue
;
31 import com
.google
.common
.collect
.Iterables
;
34 * The base class for all the types of nodes that go in the History Tree.
36 * @author Alexandre Montplaisir
38 public abstract class HTNode
{
40 // ------------------------------------------------------------------------
42 // ------------------------------------------------------------------------
47 public static enum NodeType
{
49 * Core node, which is a "front" node, at any level of the tree except
50 * the bottom-most one. It has children, and may have extensions.
54 * Leaf node, which is a node at the last bottom level of the tree. It
55 * cannot have any children or extensions.
60 * Determine a node type by reading a serialized byte.
63 * The byte representation of the node type
64 * @return The corresponding NodeType
66 * If the NodeType is unrecognized
68 public static NodeType
fromByte(byte rep
) throws IOException
{
75 throw new IOException();
80 * Get the byte representation of this node type. It can then be read
81 * with {@link #fromByte}.
83 * @return The byte matching this node type
85 public byte toByte() {
92 throw new IllegalStateException();
100 * 16 - 2x long (start time, end time)
101 * 16 - 4x int (seq number, parent seq number, intervalcount,
102 * strings section pos.)
103 * 1 - byte (done or not)
106 private static final int COMMON_HEADER_SIZE
= 34;
108 // ------------------------------------------------------------------------
110 // ------------------------------------------------------------------------
112 /* Configuration of the History Tree to which belongs this node */
113 private final HTConfig fConfig
;
115 /* Time range of this node */
116 private final long fNodeStart
;
117 private long fNodeEnd
;
119 /* Sequence number = position in the node section of the file */
120 private final int fSequenceNumber
;
121 private int fParentSequenceNumber
; /* = -1 if this node is the root node */
123 /* Where the Strings section begins (from the start of the node */
124 private int fStringSectionOffset
;
126 /* Sum of bytes of all intervals in the node */
127 private int fSizeOfIntervalSection
;
129 /* True if this node was read from disk (meaning its end time is now fixed) */
130 private volatile boolean fIsOnDisk
;
132 /* Vector containing all the intervals contained in this node */
133 private final List
<HTInterval
> fIntervals
;
135 /* Lock used to protect the accesses to intervals, nodeEnd and such */
136 private final ReentrantReadWriteLock fRwl
= new ReentrantReadWriteLock(false);
142 * Configuration of the History Tree
144 * The (unique) sequence number assigned to this particular node
145 * @param parentSeqNumber
146 * The sequence number of this node's parent node
148 * The earliest timestamp stored in this node
150 protected HTNode(HTConfig config
, int seqNumber
, int parentSeqNumber
, long start
) {
153 fSequenceNumber
= seqNumber
;
154 fParentSequenceNumber
= parentSeqNumber
;
156 fStringSectionOffset
= config
.getBlockSize();
157 fSizeOfIntervalSection
= 0;
159 fIntervals
= new ArrayList
<>();
163 * Reader factory method. Build a Node object (of the right type) by reading
164 * a block in the file.
167 * Configuration of the History Tree
169 * FileChannel to the history file, ALREADY SEEKED at the start
171 * @return The node object
172 * @throws IOException
173 * If there was an error reading from the file channel
175 public static final HTNode
readNode(HTConfig config
, FileChannel fc
)
177 HTNode newNode
= null;
180 ByteBuffer buffer
= ByteBuffer
.allocate(config
.getBlockSize());
181 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
183 res
= fc
.read(buffer
);
184 assert (res
== config
.getBlockSize());
187 /* Read the common header part */
188 byte typeByte
= buffer
.get();
189 NodeType type
= NodeType
.fromByte(typeByte
);
190 long start
= buffer
.getLong();
191 long end
= buffer
.getLong();
192 int seqNb
= buffer
.getInt();
193 int parentSeqNb
= buffer
.getInt();
194 int intervalCount
= buffer
.getInt();
195 int stringSectionOffset
= buffer
.getInt();
196 buffer
.get(); // TODO Used to be "isDone", to be removed from the header
198 /* Now the rest of the header depends on the node type */
202 newNode
= new CoreNode(config
, seqNb
, parentSeqNb
, start
);
203 newNode
.readSpecificHeader(buffer
);
208 newNode
= new LeafNode(config
, seqNb
, parentSeqNb
, start
);
209 newNode
.readSpecificHeader(buffer
);
213 /* Unrecognized node type */
214 throw new IOException();
218 * At this point, we should be done reading the header and 'buffer'
219 * should only have the intervals left
221 for (i
= 0; i
< intervalCount
; i
++) {
222 HTInterval interval
= HTInterval
.readFrom(buffer
);
223 newNode
.fIntervals
.add(interval
);
224 newNode
.fSizeOfIntervalSection
+= HTInterval
.DATA_ENTRY_SIZE
;
227 /* Assign the node's other information we have read previously */
228 newNode
.fNodeEnd
= end
;
229 newNode
.fStringSectionOffset
= stringSectionOffset
;
230 newNode
.fIsOnDisk
= true;
236 * Write this node to the given file channel.
239 * The file channel to write to (should be sought to be correct
241 * @throws IOException
242 * If there was an error writing
244 public final void writeSelf(FileChannel fc
) throws IOException
{
246 * Yes, we are taking the *read* lock here, because we are reading the
247 * information in the node to write it to disk.
249 fRwl
.readLock().lock();
251 final int blockSize
= fConfig
.getBlockSize();
252 int curStringsEntryEndPos
= blockSize
;
254 ByteBuffer buffer
= ByteBuffer
.allocate(blockSize
);
255 buffer
.order(ByteOrder
.LITTLE_ENDIAN
);
258 /* Write the common header part */
259 buffer
.put(getNodeType().toByte());
260 buffer
.putLong(fNodeStart
);
261 buffer
.putLong(fNodeEnd
);
262 buffer
.putInt(fSequenceNumber
);
263 buffer
.putInt(fParentSequenceNumber
);
264 buffer
.putInt(fIntervals
.size());
265 buffer
.putInt(fStringSectionOffset
);
266 buffer
.put((byte) 1); // TODO Used to be "isDone", to be removed from header
268 /* Now call the inner method to write the specific header part */
269 writeSpecificHeader(buffer
);
271 /* Back to us, we write the intervals */
272 for (HTInterval interval
: fIntervals
) {
273 int size
= interval
.writeInterval(buffer
, curStringsEntryEndPos
);
274 curStringsEntryEndPos
-= size
;
278 * Write padding between the end of the Data section and the start
279 * of the Strings section (needed to fill the node in case there is
280 * no Strings section)
282 while (buffer
.position() < fStringSectionOffset
) {
283 buffer
.put((byte) 0);
287 * If the offsets were right, the size of the Strings section should
288 * be == to the expected size
290 if (curStringsEntryEndPos
!= fStringSectionOffset
) {
291 throw new IllegalStateException("Wrong size of Strings section: Actual: " + curStringsEntryEndPos
+ ", Expected: " + fStringSectionOffset
); //$NON-NLS-1$ //$NON-NLS-2$
294 /* Finally, write everything in the Buffer to disk */
296 // if we don't do this, flip() will lose what's after.
297 buffer
.position(blockSize
);
300 int res
= fc
.write(buffer
);
301 if (res
!= blockSize
) {
302 throw new IllegalStateException("Wrong size of block written: Actual: " + res
+ ", Expected: " + blockSize
); //$NON-NLS-1$ //$NON-NLS-2$
306 fRwl
.readLock().unlock();
311 // ------------------------------------------------------------------------
313 // ------------------------------------------------------------------------
316 * Retrieve the history tree configuration used for this node.
318 * @return The history tree config
320 protected HTConfig
getConfig() {
325 * Get the start time of this node.
327 * @return The start time of this node
329 public long getNodeStart() {
334 * Get the end time of this node.
336 * @return The end time of this node
338 public long getNodeEnd() {
346 * Get the sequence number of this node.
348 * @return The sequence number of this node
350 public int getSequenceNumber() {
351 return fSequenceNumber
;
355 * Get the sequence number of this node's parent.
357 * @return The parent sequence number
359 public int getParentSequenceNumber() {
360 return fParentSequenceNumber
;
364 * Change this node's parent. Used when we create a new root node for
368 * The sequence number of the node that is the new parent
370 public void setParentSequenceNumber(int newParent
) {
371 fParentSequenceNumber
= newParent
;
375 * Return if this node is "done" (full and written to disk).
377 * @return If this node is done or not
379 public boolean isOnDisk() {
384 * Add an interval to this node
387 * Interval to add to this node
389 public void addInterval(HTInterval newInterval
) {
390 fRwl
.writeLock().lock();
392 /* Just in case, should be checked before even calling this function */
393 assert (newInterval
.getIntervalSize() <= getNodeFreeSpace());
395 /* Find the insert position to keep the list sorted */
396 int index
= fIntervals
.size();
397 while (index
> 0 && newInterval
.compareTo(fIntervals
.get(index
- 1)) < 0) {
401 fIntervals
.add(index
, newInterval
);
402 fSizeOfIntervalSection
+= HTInterval
.DATA_ENTRY_SIZE
;
404 /* Update the in-node offset "pointer" */
405 fStringSectionOffset
-= (newInterval
.getStringsEntrySize());
407 fRwl
.writeLock().unlock();
412 * We've received word from the containerTree that newest nodes now exist to
413 * our right. (Puts isDone = true and sets the endtime)
416 * The nodeEnd time that the node will have
418 public void closeThisNode(long endtime
) {
419 fRwl
.writeLock().lock();
422 * FIXME: was assert (endtime >= fNodeStart); but that exception
423 * is reached with an empty node that has start time endtime + 1
425 // if (endtime < fNodeStart) {
426 // throw new IllegalArgumentException("Endtime " + endtime + " cannot be lower than start time " + fNodeStart);
429 if (!fIntervals
.isEmpty()) {
431 * Make sure there are no intervals in this node with their
432 * EndTime > the one requested. Only need to check the last one
433 * since they are sorted
435 if (endtime
< Iterables
.getLast(fIntervals
).getEndTime()) {
436 throw new IllegalArgumentException("Closing end time should be greater than or equal to the end time of the intervals of this node"); //$NON-NLS-1$
442 fRwl
.writeLock().unlock();
447 * The method to fill up the stateInfo (passed on from the Current State
448 * Tree when it does a query on the SHT). We'll replace the data in that
449 * vector with whatever relevant we can find from this node
452 * The same stateInfo that comes from SHT's doQuery()
454 * The timestamp for which the query is for. Only return
455 * intervals that intersect t.
456 * @throws TimeRangeException
459 public void writeInfoFromNode(List
<ITmfStateInterval
> stateInfo
, long t
)
460 throws TimeRangeException
{
461 /* This is from a state system query, we are "reading" this node */
462 fRwl
.readLock().lock();
464 for (int i
= getStartIndexFor(t
); i
< fIntervals
.size(); i
++) {
466 * Now we only have to compare the Start times, since we now the
467 * End times necessarily fit.
469 * Second condition is to ignore new attributes that might have
470 * been created after stateInfo was instantiated (they would be
473 ITmfStateInterval interval
= fIntervals
.get(i
);
474 if (interval
.getStartTime() <= t
&&
475 interval
.getAttribute() < stateInfo
.size()) {
476 stateInfo
.set(interval
.getAttribute(), interval
);
480 fRwl
.readLock().unlock();
485 * Get a single Interval from the information in this node If the
486 * key/timestamp pair cannot be found, we return null.
489 * The attribute quark to look for
492 * @return The Interval containing the information we want, or null if it
494 * @throws TimeRangeException
497 public HTInterval
getRelevantInterval(int key
, long t
) throws TimeRangeException
{
498 fRwl
.readLock().lock();
500 for (int i
= getStartIndexFor(t
); i
< fIntervals
.size(); i
++) {
501 HTInterval curInterval
= fIntervals
.get(i
);
502 if (curInterval
.getAttribute() == key
503 && curInterval
.getStartTime() <= t
504 && curInterval
.getEndTime() >= t
) {
509 /* We didn't find the relevant information in this node */
513 fRwl
.readLock().unlock();
517 private int getStartIndexFor(long t
) throws TimeRangeException
{
518 /* Should only be called by methods with the readLock taken */
520 if (fIntervals
.isEmpty()) {
524 * Since the intervals are sorted by end time, we can skip all the ones
525 * at the beginning whose end times are smaller than 't'. Java does
526 * provides a .binarySearch method, but its API is quite weird...
528 HTInterval dummy
= new HTInterval(0, t
, 0, TmfStateValue
.nullValue());
529 int index
= Collections
.binarySearch(fIntervals
, dummy
);
533 * .binarySearch returns a negative number if the exact value was
534 * not found. Here we just want to know where to start searching, we
535 * don't care if the value is exact or not.
541 /* Sometimes binarySearch yields weird stuff... */
545 if (index
>= fIntervals
.size()) {
546 index
= fIntervals
.size() - 1;
550 * Another API quirkiness, the returned index is the one of the *last*
551 * element of a series of equal endtimes, which happens sometimes. We
552 * want the *first* element of such a series, to read through them
556 && fIntervals
.get(index
- 1).compareTo(fIntervals
.get(index
)) == 0) {
564 * Return the total header size of this node (will depend on the node type).
566 * @return The total header size
568 public final int getTotalHeaderSize() {
569 return COMMON_HEADER_SIZE
+ getSpecificHeaderSize();
573 * @return The offset, within the node, where the Data section ends
575 private int getDataSectionEndOffset() {
576 return getTotalHeaderSize() + fSizeOfIntervalSection
;
580 * Returns the free space in the node, which is simply put, the
581 * stringSectionOffset - dataSectionOffset
583 * @return The amount of free space in the node (in bytes)
585 public int getNodeFreeSpace() {
586 fRwl
.readLock().lock();
587 int ret
= fStringSectionOffset
- getDataSectionEndOffset();
588 fRwl
.readLock().unlock();
594 * Returns the current space utilization of this node, as a percentage.
595 * (used space / total usable space, which excludes the header)
597 * @return The percentage (value between 0 and 100) of space utilization in
600 public long getNodeUsagePercent() {
601 fRwl
.readLock().lock();
603 final int blockSize
= fConfig
.getBlockSize();
604 float freePercent
= (float) getNodeFreeSpace()
605 / (float) (blockSize
- getTotalHeaderSize())
607 return (long) (100L - freePercent
);
610 fRwl
.readLock().unlock();
615 * @name Debugging functions
618 @SuppressWarnings("nls")
620 public String
toString() {
621 /* Only used for debugging, shouldn't be externalized */
622 StringBuffer buf
= new StringBuffer("Node #" + fSequenceNumber
+ ", ");
623 buf
.append(toStringSpecific());
624 buf
.append(fIntervals
.size() + " intervals (" + getNodeUsagePercent()
627 buf
.append("[" + fNodeStart
+ " - ");
629 buf
= buf
.append("" + fNodeEnd
+ "]");
631 buf
= buf
.append("...]");
633 return buf
.toString();
637 * Debugging function that prints out the contents of this node
640 * PrintWriter in which we will print the debug output
642 @SuppressWarnings("nls")
643 public void debugPrintIntervals(PrintWriter writer
) {
644 /* Only used for debugging, shouldn't be externalized */
645 writer
.println("Node #" + fSequenceNumber
+ ":");
647 /* Array of children */
648 if (getNodeType() == NodeType
.CORE
) { /* Only Core Nodes can have children */
649 CoreNode thisNode
= (CoreNode
) this;
650 writer
.print(" " + thisNode
.getNbChildren() + " children");
651 if (thisNode
.getNbChildren() >= 1) {
652 writer
.print(": [ " + thisNode
.getChild(0));
653 for (int i
= 1; i
< thisNode
.getNbChildren(); i
++) {
654 writer
.print(", " + thisNode
.getChild(i
));
661 /* List of intervals in the node */
662 writer
.println(" Intervals contained:");
663 for (int i
= 0; i
< fIntervals
.size(); i
++) {
664 writer
.println(fIntervals
.get(i
).toString());
666 writer
.println('\n');
669 // ------------------------------------------------------------------------
671 // ------------------------------------------------------------------------
674 * Get the byte value representing the node type.
676 * @return The node type
678 public abstract NodeType
getNodeType();
681 * Return the specific header size of this node. This means the size
682 * occupied by the type-specific section of the header (not counting the
685 * @return The specific header size
687 protected abstract int getSpecificHeaderSize();
690 * Read the type-specific part of the node header from a byte buffer.
693 * The byte buffer to read from. It should be already positioned
696 protected abstract void readSpecificHeader(ByteBuffer buffer
);
699 * Write the type-specific part of the header in a byte buffer.
702 * The buffer to write to. It should already be at the correct
705 protected abstract void writeSpecificHeader(ByteBuffer buffer
);
708 * Node-type-specific toString method. Used for debugging.
710 * @return A string representing the node
712 protected abstract String
toStringSpecific();