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