org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/backends/historytree/HTNode.java

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