statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java

   1 /*******************************************************************************
   2  * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others
   3  *
   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
   8  *
   9  * Contributors:
  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  *******************************************************************************/
  14
  15 package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree;
  16
  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;
  26
  27 import org.eclipse.jdt.annotation.NonNull;
  28 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  29 import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
  30 import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
  31
  32 import com.google.common.collect.Iterables;
  33
  34 /**
  35  * The base class for all the types of nodes that go in the History Tree.
  36  *
  37  * @author Alexandre Montplaisir
  38  */
  39 public abstract class HTNode {
  40
  41     // ------------------------------------------------------------------------
  42     // Class fields
  43     // ------------------------------------------------------------------------
  44
  45     /**
  46      * The type of node
  47      */
  48     public static enum NodeType {
  49         /**
  50          * Core node, which is a "front" node, at any level of the tree except
  51          * the bottom-most one. It has children, and may have extensions.
  52          */
  53         CORE,
  54         /**
  55          * Leaf node, which is a node at the last bottom level of the tree. It
  56          * cannot have any children or extensions.
  57          */
  58         LEAF;
  59
  60         /**
  61          * Determine a node type by reading a serialized byte.
  62          *
  63          * @param rep
  64          *            The byte representation of the node type
  65          * @return The corresponding NodeType
  66          * @throws IOException
  67          *             If the NodeType is unrecognized
  68          */
  69         public static NodeType fromByte(byte rep) throws IOException {
  70             switch (rep) {
  71             case 1:
  72                 return CORE;
  73             case 2:
  74                 return LEAF;
  75             default:
  76                 throw new IOException();
  77             }
  78         }
  79
  80         /**
  81          * Get the byte representation of this node type. It can then be read
  82          * with {@link #fromByte}.
  83          *
  84          * @return The byte matching this node type
  85          */
  86         public byte toByte() {
  87             switch (this) {
  88             case CORE:
  89                 return 1;
  90             case LEAF:
  91                 return 2;
  92             default:
  93                 throw new IllegalStateException();
  94             }
  95         }
  96     }
  97
  98     /**
  99      * <pre>
 100      *  1 - byte (type)
 101      * 16 - 2x long (start time, end time)
 102      * 16 - 3x int (seq number, parent seq number, intervalcount)
 103      *  1 - byte (done or not)
 104      * </pre>
 105      */
 106     private static final int COMMON_HEADER_SIZE = Byte.BYTES
 107             + 2 * Long.BYTES
 108             + 3 * Integer.BYTES
 109             + Byte.BYTES;
 110
 111     // ------------------------------------------------------------------------
 112     // Attributes
 113     // ------------------------------------------------------------------------
 114
 115     /* Configuration of the History Tree to which belongs this node */
 116     private final HTConfig fConfig;
 117
 118     /* Time range of this node */
 119     private final long fNodeStart;
 120     private long fNodeEnd;
 121
 122     /* Sequence number = position in the node section of the file */
 123     private final int fSequenceNumber;
 124     private int fParentSequenceNumber; /* = -1 if this node is the root node */
 125
 126     /* Sum of bytes of all intervals in the node */
 127     private int fSizeOfIntervalSection;
 128
 129     /* True if this node was read from disk (meaning its end time is now fixed) */
 130     private volatile boolean fIsOnDisk;
 131
 132     /* Vector containing all the intervals contained in this node */
 133     private final List<HTInterval> fIntervals;
 134
 135     /* Lock used to protect the accesses to intervals, nodeEnd and such */
 136     private final ReentrantReadWriteLock fRwl = new ReentrantReadWriteLock(false);
 137
 138     /**
 139      * Constructor
 140      *
 141      * @param config
 142      *            Configuration of the History Tree
 143      * @param seqNumber
 144      *            The (unique) sequence number assigned to this particular node
 145      * @param parentSeqNumber
 146      *            The sequence number of this node's parent node
 147      * @param start
 148      *            The earliest timestamp stored in this node
 149      */
 150     protected HTNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) {
 151         fConfig = config;
 152         fNodeStart = start;
 153         fSequenceNumber = seqNumber;
 154         fParentSequenceNumber = parentSeqNumber;
 155
 156         fSizeOfIntervalSection = 0;
 157         fIsOnDisk = false;
 158         fIntervals = new ArrayList<>();
 159     }
 160
 161     /**
 162      * Reader factory method. Build a Node object (of the right type) by reading
 163      * a block in the file.
 164      *
 165      * @param config
 166      *            Configuration of the History Tree
 167      * @param fc
 168      *            FileChannel to the history file, ALREADY SEEKED at the start
 169      *            of the node.
 170      * @param nodeFactory
 171      *            The factory to create the nodes for this tree
 172      * @return The node object
 173      * @throws IOException
 174      *             If there was an error reading from the file channel
 175      */
 176     public static final @NonNull HTNode readNode(HTConfig config, FileChannel fc, IHistoryTree.IHTNodeFactory nodeFactory)
 177             throws IOException {
 178         HTNode newNode = null;
 179         int res, i;
 180
 181         ByteBuffer buffer = ByteBuffer.allocate(config.getBlockSize());
 182         buffer.order(ByteOrder.LITTLE_ENDIAN);
 183         buffer.clear();
 184         res = fc.read(buffer);
 185         assert (res == config.getBlockSize());
 186         buffer.flip();
 187
 188         /* Read the common header part */
 189         byte typeByte = buffer.get();
 190         NodeType type = NodeType.fromByte(typeByte);
 191         long start = buffer.getLong();
 192         long end = buffer.getLong();
 193         int seqNb = buffer.getInt();
 194         int parentSeqNb = buffer.getInt();
 195         int intervalCount = buffer.getInt();
 196         buffer.get(); // TODO Used to be "isDone", to be removed from the header
 197
 198         /* Now the rest of the header depends on the node type */
 199         switch (type) {
 200         case CORE:
 201             /* Core nodes */
 202             newNode = nodeFactory.createCoreNode(config, seqNb, parentSeqNb, start);
 203             newNode.readSpecificHeader(buffer);
 204             break;
 205
 206         case LEAF:
 207             /* Leaf nodes */
 208             newNode = nodeFactory.createLeafNode(config, seqNb, parentSeqNb, start);
 209             newNode.readSpecificHeader(buffer);
 210             break;
 211
 212         default:
 213             /* Unrecognized node type */
 214             throw new IOException();
 215         }
 216
 217         /*
 218          * At this point, we should be done reading the header and 'buffer'
 219          * should only have the intervals left
 220          */
 221         for (i = 0; i < intervalCount; i++) {
 222             HTInterval interval = HTInterval.readFrom(buffer);
 223             newNode.fIntervals.add(interval);
 224             newNode.fSizeOfIntervalSection += interval.getSizeOnDisk();
 225         }
 226
 227         /* Assign the node's other information we have read previously */
 228         newNode.fNodeEnd = end;
 229         newNode.fIsOnDisk = true;
 230
 231         return newNode;
 232     }
 233
 234     /**
 235      * Write this node to the given file channel.
 236      *
 237      * @param fc
 238      *            The file channel to write to (should be sought to be correct
 239      *            position)
 240      * @throws IOException
 241      *             If there was an error writing
 242      */
 243     public final void writeSelf(FileChannel fc) throws IOException {
 244         /*
 245          * Yes, we are taking the *read* lock here, because we are reading the
 246          * information in the node to write it to disk.
 247          */
 248         fRwl.readLock().lock();
 249         try {
 250             final int blockSize = fConfig.getBlockSize();
 251
 252             ByteBuffer buffer = ByteBuffer.allocate(blockSize);
 253             buffer.order(ByteOrder.LITTLE_ENDIAN);
 254             buffer.clear();
 255
 256             /* Write the common header part */
 257             buffer.put(getNodeType().toByte());
 258             buffer.putLong(fNodeStart);
 259             buffer.putLong(fNodeEnd);
 260             buffer.putInt(fSequenceNumber);
 261             buffer.putInt(fParentSequenceNumber);
 262             buffer.putInt(fIntervals.size());
 263             buffer.put((byte) 1); // TODO Used to be "isDone", to be removed from header
 264
 265             /* Now call the inner method to write the specific header part */
 266             writeSpecificHeader(buffer);
 267
 268             /* Back to us, we write the intervals */
 269             fIntervals.forEach(i -> i.writeInterval(buffer));
 270             if (blockSize - buffer.position() != getNodeFreeSpace()) {
 271                 throw new IllegalStateException("Wrong free space: Actual: " + (blockSize - buffer.position()) + ", Expected: " + getNodeFreeSpace()); //$NON-NLS-1$ //$NON-NLS-2$
 272             }
 273             /*
 274              * Fill the rest with zeros
 275              */
 276             while (buffer.position() < blockSize) {
 277                 buffer.put((byte) 0);
 278             }
 279
 280             /* Finally, write everything in the Buffer to disk */
 281             buffer.flip();
 282             int res = fc.write(buffer);
 283             if (res != blockSize) {
 284                 throw new IllegalStateException("Wrong size of block written: Actual: " + res + ", Expected: " + blockSize); //$NON-NLS-1$ //$NON-NLS-2$
 285             }
 286
 287         } finally {
 288             fRwl.readLock().unlock();
 289         }
 290         fIsOnDisk = true;
 291     }
 292
 293     // ------------------------------------------------------------------------
 294     // Accessors
 295     // ------------------------------------------------------------------------
 296
 297     /**
 298      * Retrieve the history tree configuration used for this node.
 299      *
 300      * @return The history tree config
 301      */
 302     protected HTConfig getConfig() {
 303         return fConfig;
 304     }
 305
 306     /**
 307      * Get the start time of this node.
 308      *
 309      * @return The start time of this node
 310      */
 311     public long getNodeStart() {
 312         return fNodeStart;
 313     }
 314
 315     /**
 316      * Get the end time of this node.
 317      *
 318      * @return The end time of this node
 319      */
 320     public long getNodeEnd() {
 321         if (fIsOnDisk) {
 322             return fNodeEnd;
 323         }
 324         return 0;
 325     }
 326
 327     /**
 328      * Get the sequence number of this node.
 329      *
 330      * @return The sequence number of this node
 331      */
 332     public int getSequenceNumber() {
 333         return fSequenceNumber;
 334     }
 335
 336     /**
 337      * Get the sequence number of this node's parent.
 338      *
 339      * @return The parent sequence number
 340      */
 341     public int getParentSequenceNumber() {
 342         return fParentSequenceNumber;
 343     }
 344
 345     /**
 346      * Change this node's parent. Used when we create a new root node for
 347      * example.
 348      *
 349      * @param newParent
 350      *            The sequence number of the node that is the new parent
 351      */
 352     public void setParentSequenceNumber(int newParent) {
 353         fParentSequenceNumber = newParent;
 354     }
 355
 356     /**
 357      * Return if this node is "done" (full and written to disk).
 358      *
 359      * @return If this node is done or not
 360      */
 361     public boolean isOnDisk() {
 362         return fIsOnDisk;
 363     }
 364
 365     /**
 366      * Add an interval to this node
 367      *
 368      * @param newInterval
 369      *            Interval to add to this node
 370      */
 371     public void addInterval(HTInterval newInterval) {
 372         fRwl.writeLock().lock();
 373         try {
 374             /* Just in case, should be checked before even calling this function */
 375             assert (newInterval.getSizeOnDisk() <= getNodeFreeSpace());
 376
 377             /* Find the insert position to keep the list sorted */
 378             int index = fIntervals.size();
 379             while (index > 0 && newInterval.compareTo(fIntervals.get(index - 1)) < 0) {
 380                 index--;
 381             }
 382
 383             fIntervals.add(index, newInterval);
 384             fSizeOfIntervalSection += newInterval.getSizeOnDisk();
 385
 386         } finally {
 387             fRwl.writeLock().unlock();
 388         }
 389     }
 390
 391     /**
 392      * We've received word from the containerTree that newest nodes now exist to
 393      * our right. (Puts isDone = true and sets the endtime)
 394      *
 395      * @param endtime
 396      *            The nodeEnd time that the node will have
 397      */
 398     public void closeThisNode(long endtime) {
 399         fRwl.writeLock().lock();
 400         try {
 401             /**
 402              * FIXME: was assert (endtime >= fNodeStart); but that exception
 403              * is reached with an empty node that has start time endtime + 1
 404              */
 405 //            if (endtime < fNodeStart) {
 406 //                throw new IllegalArgumentException("Endtime " + endtime + " cannot be lower than start time " + fNodeStart);
 407 //            }
 408
 409             if (!fIntervals.isEmpty()) {
 410                 /*
 411                  * Make sure there are no intervals in this node with their
 412                  * EndTime > the one requested. Only need to check the last one
 413                  * since they are sorted
 414                  */
 415                 if (endtime < Iterables.getLast(fIntervals).getEndTime()) {
 416                     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$
 417                 }
 418             }
 419
 420             fNodeEnd = endtime;
 421         } finally {
 422             fRwl.writeLock().unlock();
 423         }
 424     }
 425
 426     /**
 427      * The method to fill up the stateInfo (passed on from the Current State
 428      * Tree when it does a query on the SHT). We'll replace the data in that
 429      * vector with whatever relevant we can find from this node
 430      *
 431      * @param stateInfo
 432      *            The same stateInfo that comes from SHT's doQuery()
 433      * @param t
 434      *            The timestamp for which the query is for. Only return
 435      *            intervals that intersect t.
 436      * @throws TimeRangeException
 437      *             If 't' is invalid
 438      */
 439     public void writeInfoFromNode(List<ITmfStateInterval> stateInfo, long t)
 440             throws TimeRangeException {
 441         /* This is from a state system query, we are "reading" this node */
 442         fRwl.readLock().lock();
 443         try {
 444             for (int i = getStartIndexFor(t); i < fIntervals.size(); i++) {
 445                 /*
 446                  * Now we only have to compare the Start times, since we now the
 447                  * End times necessarily fit.
 448                  *
 449                  * Second condition is to ignore new attributes that might have
 450                  * been created after stateInfo was instantiated (they would be
 451                  * null anyway).
 452                  */
 453                 ITmfStateInterval interval = fIntervals.get(i);
 454                 if (t >= interval.getStartTime() &&
 455                         interval.getAttribute() < stateInfo.size()) {
 456                     stateInfo.set(interval.getAttribute(), interval);
 457                 }
 458             }
 459         } finally {
 460             fRwl.readLock().unlock();
 461         }
 462     }
 463
 464     /**
 465      * Get a single Interval from the information in this node If the
 466      * key/timestamp pair cannot be found, we return null.
 467      *
 468      * @param key
 469      *            The attribute quark to look for
 470      * @param t
 471      *            The timestamp
 472      * @return The Interval containing the information we want, or null if it
 473      *         wasn't found
 474      * @throws TimeRangeException
 475      *             If 't' is invalid
 476      */
 477     public HTInterval getRelevantInterval(int key, long t) throws TimeRangeException {
 478         fRwl.readLock().lock();
 479         try {
 480             for (int i = getStartIndexFor(t); i < fIntervals.size(); i++) {
 481                 HTInterval curInterval = fIntervals.get(i);
 482                 if (curInterval.getAttribute() == key
 483                         && curInterval.getStartTime() <= t
 484                         && curInterval.getEndTime() >= t) {
 485                     return curInterval;
 486                 }
 487             }
 488
 489             /* We didn't find the relevant information in this node */
 490             return null;
 491
 492         } finally {
 493             fRwl.readLock().unlock();
 494         }
 495     }
 496
 497     private int getStartIndexFor(long t) throws TimeRangeException {
 498         /* Should only be called by methods with the readLock taken */
 499
 500         if (fIntervals.isEmpty()) {
 501             return 0;
 502         }
 503         /*
 504          * Since the intervals are sorted by end time, we can skip all the ones
 505          * at the beginning whose end times are smaller than 't'. Java does
 506          * provides a .binarySearch method, but its API is quite weird...
 507          */
 508         HTInterval dummy = new HTInterval(0, t, 0, TmfStateValue.nullValue());
 509         int index = Collections.binarySearch(fIntervals, dummy);
 510
 511         if (index < 0) {
 512             /*
 513              * .binarySearch returns a negative number if the exact value was
 514              * not found. Here we just want to know where to start searching, we
 515              * don't care if the value is exact or not.
 516              */
 517             index = -index - 1;
 518
 519         } else {
 520             /*
 521              * Another API quirkiness, the returned index is the one of the *last*
 522              * element of a series of equal endtimes, which happens sometimes. We
 523              * want the *first* element of such a series, to read through them
 524              * again.
 525              */
 526             while (index > 0
 527                     && fIntervals.get(index - 1).compareTo(fIntervals.get(index)) == 0) {
 528                 index--;
 529             }
 530         }
 531
 532         return index;
 533     }
 534
 535     /**
 536      * Return the total header size of this node (will depend on the node type).
 537      *
 538      * @return The total header size
 539      */
 540     public final int getTotalHeaderSize() {
 541         return COMMON_HEADER_SIZE + getSpecificHeaderSize();
 542     }
 543
 544     /**
 545      * @return The offset, within the node, where the Data section ends
 546      */
 547     private int getDataSectionEndOffset() {
 548         return getTotalHeaderSize() + fSizeOfIntervalSection;
 549     }
 550
 551     /**
 552      * Returns the free space in the node, which is simply put, the
 553      * stringSectionOffset - dataSectionOffset
 554      *
 555      * @return The amount of free space in the node (in bytes)
 556      */
 557     public int getNodeFreeSpace() {
 558         fRwl.readLock().lock();
 559         int ret = fConfig.getBlockSize() - getDataSectionEndOffset();
 560         fRwl.readLock().unlock();
 561
 562         return ret;
 563     }
 564
 565     /**
 566      * Returns the current space utilization of this node, as a percentage.
 567      * (used space / total usable space, which excludes the header)
 568      *
 569      * @return The percentage (value between 0 and 100) of space utilization in
 570      *         in this node.
 571      */
 572     public long getNodeUsagePercent() {
 573         fRwl.readLock().lock();
 574         try {
 575             final int blockSize = fConfig.getBlockSize();
 576             float freePercent = (float) getNodeFreeSpace()
 577                     / (float) (blockSize - getTotalHeaderSize())
 578                     * 100F;
 579             return (long) (100L - freePercent);
 580
 581         } finally {
 582             fRwl.readLock().unlock();
 583         }
 584     }
 585
 586     /**
 587      * @name Debugging functions
 588      */
 589
 590     @SuppressWarnings("nls")
 591     @Override
 592     public String toString() {
 593         /* Only used for debugging, shouldn't be externalized */
 594         return String.format("Node #%d, %s, %s, %d intervals (%d%% used), [%d - %s]",
 595                 fSequenceNumber,
 596                 (fParentSequenceNumber == -1) ? "Root" : "Parent #" + fParentSequenceNumber,
 597                 toStringSpecific(),
 598                 fIntervals.size(),
 599                 getNodeUsagePercent(),
 600                 fNodeStart,
 601                 (fIsOnDisk || fNodeEnd != 0) ? fNodeEnd : "...");
 602     }
 603
 604     /**
 605      * Debugging function that prints out the contents of this node
 606      *
 607      * @param writer
 608      *            PrintWriter in which we will print the debug output
 609      */
 610     @SuppressWarnings("nls")
 611     public void debugPrintIntervals(PrintWriter writer) {
 612         /* Only used for debugging, shouldn't be externalized */
 613         writer.println("Intervals for node #" + fSequenceNumber + ":");
 614
 615         /* Array of children */
 616         if (getNodeType() != NodeType.LEAF) { /* Only Core Nodes can have children */
 617             ParentNode thisNode = (ParentNode) this;
 618             writer.print("  " + thisNode.getNbChildren() + " children");
 619             if (thisNode.getNbChildren() >= 1) {
 620                 writer.print(": [ " + thisNode.getChild(0));
 621                 for (int i = 1; i < thisNode.getNbChildren(); i++) {
 622                     writer.print(", " + thisNode.getChild(i));
 623                 }
 624                 writer.print(']');
 625             }
 626             writer.print('\n');
 627         }
 628
 629         /* List of intervals in the node */
 630         writer.println("  Intervals contained:");
 631         for (int i = 0; i < fIntervals.size(); i++) {
 632             writer.println(fIntervals.get(i).toString());
 633         }
 634         writer.println('\n');
 635     }
 636
 637     // ------------------------------------------------------------------------
 638     // Abstract methods
 639     // ------------------------------------------------------------------------
 640
 641     /**
 642      * Get the byte value representing the node type.
 643      *
 644      * @return The node type
 645      */
 646     public abstract NodeType getNodeType();
 647
 648     /**
 649      * Return the specific header size of this node. This means the size
 650      * occupied by the type-specific section of the header (not counting the
 651      * common part).
 652      *
 653      * @return The specific header size
 654      */
 655     protected abstract int getSpecificHeaderSize();
 656
 657     /**
 658      * Read the type-specific part of the node header from a byte buffer.
 659      *
 660      * @param buffer
 661      *            The byte buffer to read from. It should be already positioned
 662      *            correctly.
 663      */
 664     protected abstract void readSpecificHeader(ByteBuffer buffer);
 665
 666     /**
 667      * Write the type-specific part of the header in a byte buffer.
 668      *
 669      * @param buffer
 670      *            The buffer to write to. It should already be at the correct
 671      *            position.
 672      */
 673     protected abstract void writeSpecificHeader(ByteBuffer buffer);
 674
 675     /**
 676      * Node-type-specific toString method. Used for debugging.
 677      *
 678      * @return A string representing the node
 679      */
 680     protected abstract String toStringSpecific();
 681 }