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

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