diff options
Diffstat (limited to 'lttng/org.eclipse.linuxtools.tmf.core/src/org')
26 files changed, 4748 insertions, 0 deletions
diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/ITmfStateInterval.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/ITmfStateInterval.java new file mode 100644 index 0000000000..397f1af3f1 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/ITmfStateInterval.java @@ -0,0 +1,65 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alexandre Montplaisir - Initial API + ******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.interval; + +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; + +/** + * This is the basic interface for accessing state intervals. See + * StateInterval.java for a basic implementation. + * + * A StateInterval is meant to be immutable. All implementing (non-abstract) + * classes should ideally be marked as 'final'. + * + * @author alexmont + * + */ +public interface ITmfStateInterval { + + /** + * Retrieve the start time of the interval + * + * @return + */ + public long getStartTime(); + + /** + * Retrieve the end time of the interval + * + * @return + */ + public long getEndTime(); + + /** + * Retrieve the quark of the attribute this state interval refers to + * + * @return + */ + public int getAttribute(); + + /** + * Retrieve the state value represented by this interval + * + * @return + */ + public ITmfStateValue getStateValue(); + + /** + * Test if this interval intersects another timestamp, inclusively. + * + * @param timestamp + * The target timestamp + * @return True if the interval and timestamp intersect, false if they don't + */ + public boolean intersects(long timestamp); +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/TmfStateInterval.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/TmfStateInterval.java new file mode 100644 index 0000000000..e7ab298c0d --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/interval/TmfStateInterval.java @@ -0,0 +1,90 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.interval; + +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; + +/** + * The StateInterval represents the "state" a particular attribute was in, at a + * given time. It is the main object being returned from queries to the state + * system. + * + + * + * @author alexmont + * + */ +public final class TmfStateInterval implements ITmfStateInterval { + + private final long start; + private final long end; + private final int attribute; + private final ITmfStateValue sv; + + /** + * Construct an interval from its given parameters + * + * @param start + * @param end + * @param attribute + * @param sv + */ + public TmfStateInterval(long start, long end, int attribute, + ITmfStateValue sv) { + this.start = start; + this.end = end; + this.attribute = attribute; + this.sv = sv; + } + + @Override + public long getStartTime() { + return start; + } + + @Override + public long getEndTime() { + return end; + } + + @Override + public int getAttribute() { + return attribute; + } + + @Override + public ITmfStateValue getStateValue() { + return sv; + } + + @Override + public boolean intersects(long timestamp) { + if (start <= timestamp) { + if (end >= timestamp) { + return true; + } + } + return false; + } + + @Override + public String toString() { + /* Only used for debugging */ + StringBuffer buf = new StringBuffer(start + " to "); //$NON-NLS-1$ + buf.append(end + ' '); + buf.append(String.format("key = %4d, ", attribute)); //$NON-NLS-1$ + buf.append("value = " + sv.toString()); //$NON-NLS-1$ + return buf.toString(); + } + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/Attribute.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/Attribute.java new file mode 100644 index 0000000000..cefc3ec7c5 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/Attribute.java @@ -0,0 +1,236 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +import java.io.PrintWriter; +import java.util.Collections; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Vector; + +/** + * An Attribute is a "node" in the Attribute Tree. It represents a smallest + * unit of the model which can be in a particular state at a given time. + * + * It is abstract, as different implementations can provide different ways to + * access sub-attributes + * + * @author alexmont + * + */ +abstract class Attribute { + + private final Attribute parent; + private final String name; + private final int quark; + protected final Vector<Attribute> subAttributes; + + /** + * Constructor + */ + Attribute(Attribute parent, String name, int quark) { + this.parent = parent; + this.quark = quark; + this.name = name; + this.subAttributes = new Vector<Attribute>(); + } + + /** + * @name Accessors + */ + + int getQuark() { + return quark; + } + + Attribute getParent() { + return parent; + } + + List<Attribute> getSubAttributesList() { + return subAttributes; + } + + String getName() { + return name; + } + + /** + * Get the matching quark for a given path-of-strings + * + * @param path + * The path we are looking for, *relative to this node*. + * @return The matching quark, or -1 if that attribute does not exist. + */ + int getSubAttributeQuark(String... path) { + return this.getSubAttributeQuark(path, 0); + } + + /** + * Other method to search through the attribute tree, but instead of + * returning the matching quark we return the AttributeTreeNode object + * itself. It can then be used as new "root node" for faster queries on the + * tree. + * + * @param path + * The target path, *relative to this node* + * @return The Node object matching the last element in the path, or "null" + * if that attribute does not exist. + */ + Attribute getSubAttributeNode(String... path) { + return this.getSubAttributeNode(path, 0); + } + + /** + * "Inner" part of the previous public method, which is used recursively. To + * avoid having to copy sub-arrays to pass down, we just track where we are + * at with the index parameter. It uses getSubAttributeNode(), whose + * implementation is left to the derived classes. + */ + private int getSubAttributeQuark(String[] path, int index) { + Attribute targetNode = this.getSubAttributeNode(path, index); + if (targetNode == null) { + return -1; + } + return targetNode.getQuark(); + } + + /* The methods how to access children are left to derived classes */ + abstract void addSubAttribute(Attribute newSubAttribute); + abstract Attribute getSubAttributeNode(String[] path, int index); + + /** + * Return a String array composed of the full (absolute) path representing + * this attribute + * + * @return + */ + String[] getFullAttribute() { + LinkedList<String> list = new LinkedList<String>(); + Attribute curNode = this; + + /* Add recursive parents to the list, but stop at the root node */ + while (curNode.getParent() != null) { + list.add(curNode.getName()); + curNode = curNode.getParent(); + } + + Collections.reverse(list); + + return list.toArray(new String[0]); + } + + /** + * Return the absolute path of this attribute, as a single slash-separated + * String. + * + * @return + */ + String getFullAttributeName() { + String[] array; + String ret = ""; //$NON-NLS-1$ + + array = this.getFullAttribute(); + for (int i = 0; i < array.length - 1; i++) { + ret += array[i] + '/'; + } + ret += array[array.length - 1]; + return ret; + } + + @Override + public String toString() { + return getFullAttributeName() + " (" + quark + ')'; //$NON-NLS-1$ + } + + private int curDepth; + + private void attributeNodeToString(PrintWriter writer, Attribute currentNode) { + int j; + + writer.println(currentNode.getName() + " (" + currentNode.quark + ')'); //$NON-NLS-1$ + curDepth++; + + for (Attribute nextNode : currentNode.getSubAttributesList()) { + /* Skip printing 'null' entries */ + if (nextNode == null) { + continue; + } + for (j = 0; j < curDepth - 1; j++) { + writer.print(" "); //$NON-NLS-1$ + } + writer.print(" "); //$NON-NLS-1$ + attributeNodeToString(writer, nextNode); + } + curDepth--; + return; + } + + void debugPrint(PrintWriter writer) { + /* Only used for debugging, shouldn't be externalized */ + writer.println("------------------------------"); //$NON-NLS-1$ + writer.println("Attribute tree: (quark)\n"); //$NON-NLS-1$ + curDepth = 0; + attributeNodeToString(writer, this); + writer.print('\n'); + } +} + +/** + * This is the basic implementation, where sub-attributes names can be composed + * of any alphanumeric characters, and are stored as Strings. A HashMap is used + * to access them. + * + * @author alexmont + * + */ +final class AlphaNumAttribute extends Attribute { + + private HashMap<String, Integer> subAttributesMap; + + AlphaNumAttribute(Attribute parent, String name, int quark) { + super(parent, name, quark); + this.subAttributesMap = new HashMap<String, Integer>(); + } + + @Override + synchronized void addSubAttribute(Attribute newSubAttribute) { + assert (newSubAttribute != null); + assert (newSubAttribute.getName() != null); + /* This should catch buggy state changing statements */ + assert (!newSubAttribute.getName().equals(this.getName())); + + subAttributesMap.put(newSubAttribute.getName(), subAttributes.size()); + subAttributes.add(newSubAttribute); + } + + @Override + protected synchronized Attribute getSubAttributeNode(String[] path, + int index) { + Integer indexOfNextNode = subAttributesMap.get(path[index]); + Attribute nextNode; + + if (indexOfNextNode == null) { + /* We don't have the expected child => the attribute does not exist */ + return null; + } + if (index == path.length - 1) { + /* It's our job to process this request */ + return subAttributes.get(indexOfNextNode); + } + + nextNode = subAttributes.get(indexOfNextNode); + return nextNode.getSubAttributeNode(path, index + 1); + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeNotFoundException.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeNotFoundException.java new file mode 100644 index 0000000000..a96af7fab2 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeNotFoundException.java @@ -0,0 +1,29 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +/** + * This exception gets thrown when the user tries to access an attribute which + * doesn't exist in the system, of if the quark is simply invalid (ie, < 0). + * + * @author alexmont + * + */ +public class AttributeNotFoundException extends Exception { + + /** + * + */ + private static final long serialVersionUID = 7964275803369706145L; + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeTree.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeTree.java new file mode 100644 index 0000000000..7cbb7a0797 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/AttributeTree.java @@ -0,0 +1,304 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +import java.io.*; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; + +/** + * The Attribute Tree is the /proc-like filesystem used to organize attributes. + * Each node of this tree is both like a file and a directory in the + * "file system". + * + * @author alexmont + * + */ +final class AttributeTree { + + /* "Magic number" for attribute tree files or file sections */ + private final static int ATTRIB_TREE_MAGIC_NUMBER = 0x06EC3671; + + private final StateSystem ss; + private final List<Attribute> attributeList; + private final Attribute attributeTreeRoot; + + /** + * Standard constructor, create a new empty Attribute Tree + * + * @param ss + * The StateSystem to which this AT is attached + */ + AttributeTree(StateSystem ss) { + this.ss = ss; + this.attributeList = Collections.synchronizedList(new ArrayList<Attribute>()); + this.attributeTreeRoot = new AlphaNumAttribute(null, "root", -1); //$NON-NLS-1$ + } + + /** + * "Existing file" constructor Builds a attribute tree from a "mapping file" + * or mapping section previously saved somewhere. + * + * @param ss + * StateSystem to which this AT is attached + * @param fis + * File stream where to read the AT information. Make sure it's + * seeked at the right place! + * @throws IOException + */ + AttributeTree(StateSystem ss, FileInputStream fis) throws IOException { + this(ss); + DataInputStream in = new DataInputStream(new BufferedInputStream(fis)); + + /* Message for exceptions, shouldn't be externalized */ + final String errorMessage = "The attribute tree file section is either invalid or corrupted."; //$NON-NLS-1$ + + ArrayList<String[]> list = new ArrayList<String[]>(); + byte[] curByteArray; + String curFullString; + String[] curStringArray; + int res, remain, size; + int expectedSize = 0; + int total = 0; + + /* Read the header of the Attribute Tree file (or file section) */ + res = in.readInt(); /* Magic number */ + if (res != ATTRIB_TREE_MAGIC_NUMBER) { + throw new IOException(errorMessage); + } + + /* Expected size of the section */ + expectedSize = in.readInt(); + if (expectedSize <= 12) { + throw new IOException(errorMessage); + } + + /* How many entries we have to read */ + remain = in.readInt(); + total += 12; + + /* Read each entry */ + for (; remain > 0; remain--) { + /* Read the first byte = the size of the entry */ + size = in.readByte(); + curByteArray = new byte[size]; + in.read(curByteArray); + + /* + * Go buffer -> byteArray -> String -> String[] -> insert in list. + * bleh + */ + curFullString = new String(curByteArray); + curStringArray = curFullString.split("/"); //$NON-NLS-1$ + list.add(curStringArray); + + /* Read the 0'ed confirmation byte */ + res = in.readByte(); + if (res != 0) { + throw new IOException(errorMessage); + } + total += curByteArray.length + 2; + } + + if (total != expectedSize) { + throw new IOException(errorMessage); + } + + /* + * Now we have 'list', the ArrayList of String arrays representing all + * the attributes. Simply create attributes the normal way from them. + */ + for (String[] attrib : list) { + this.getQuarkAndAdd(-1, attrib); + } + } + + /** + * Tell the Attribute Tree to write itself somewhere. The passed + * FileOutputStream defines where (which file/position). + * + * @param fos + * Where to write. Make sure it's seeked at the right position + * you want. + * @return The total number of bytes written. + */ + int writeSelf(File file, long pos) { + RandomAccessFile raf; + int total = 0; + byte[] curByteArray; + + try { + raf = new RandomAccessFile(file, "rw"); //$NON-NLS-1$ + raf.seek(pos); + + /* Write the almost-magic number */ + raf.writeInt(ATTRIB_TREE_MAGIC_NUMBER); + + /* Placeholder for the total size of the section... */ + raf.writeInt(-8000); + + /* Write the number of entries */ + raf.writeInt(this.attributeList.size()); + total += 12; + + /* Write the attributes themselves */ + for (Attribute entry : this.attributeList) { + curByteArray = entry.getFullAttributeName().getBytes(); + if (curByteArray.length > Byte.MAX_VALUE) { + throw new IOException("Attribute with name \"" //$NON-NLS-1$ + + Arrays.toString(curByteArray) + "\" is too long."); //$NON-NLS-1$ + } + /* Write the first byte = size of the array */ + raf.writeByte((byte) curByteArray.length); + + /* Write the array itself */ + raf.write(curByteArray); + + /* Write the 0'ed byte */ + raf.writeByte((byte) 0); + + total += curByteArray.length + 2; + } + + /* Now go back and write the actual size of this section */ + raf.seek(pos + 4); + raf.writeInt(total); + + raf.close(); + } catch (IOException e) { + e.printStackTrace(); + } + return total; + } + + /** + * Return the number of attributes this system as seen so far. Note that + * this also equals the integer value (quark) the next added attribute will + * have. + * + * @return + */ + int getNbAttributes() { + return attributeList.size(); + } + + /** + * This is the version to specifically add missing attributes. + * + * If 'numericalNode' is true, all the new attributes created will be of + * type 'NumericalNode' instead of 'AlphaNumNode'. Be careful with this, if + * you do not want ALL added attributes to be numerical, call this function + * first with 'false' to create the parent nodes, then call it again to make + * sure only the final node is numerical. + * + * @throws AttributeNotFoundException + */ + int getQuarkDontAdd(int startingNodeQuark, String... subPath) + throws AttributeNotFoundException { + assert (subPath != null && subPath.length > 0); + assert (startingNodeQuark >= -1); + + Attribute prevNode; + + /* Get the "starting node" */ + if (startingNodeQuark == -1) { + prevNode = attributeTreeRoot; + } else { + prevNode = attributeList.get(startingNodeQuark); + } + + int knownQuark = prevNode.getSubAttributeQuark(subPath); + if (knownQuark == -1) { + /* + * The attribute doesn't exist, but we have been specified to NOT + * add any new attributes. + */ + throw new AttributeNotFoundException(); + } + /* + * The attribute was already existing, return the quark of that + * attribute + */ + return knownQuark; + } + + // FIXME synchronized here is probably quite costly... maybe only locking + // the "for" would be enough? + synchronized int getQuarkAndAdd(int startingNodeQuark, String... subPath) { + assert (subPath != null && subPath.length > 0); + assert (startingNodeQuark >= -1); + + Attribute nextNode = null; + Attribute prevNode; + + /* Get the "starting node" */ + if (startingNodeQuark == -1) { + prevNode = attributeTreeRoot; + } else { + prevNode = attributeList.get(startingNodeQuark); + } + + int knownQuark = prevNode.getSubAttributeQuark(subPath); + if (knownQuark == -1) { + /* + * The attribute was not in the table previously, and we want to add + * it + */ + for (String curDirectory : subPath) { + nextNode = prevNode.getSubAttributeNode(curDirectory); + if (nextNode == null) { + /* This is where we need to start adding */ + nextNode = new AlphaNumAttribute(prevNode, curDirectory, + attributeList.size()); + prevNode.addSubAttribute(nextNode); + attributeList.add(nextNode); + ss.transState.addEmptyEntry(); + } + prevNode = nextNode; + } + return attributeList.size() - 1; + } + /* + * The attribute was already existing, return the quark of that + * attribute + */ + return knownQuark; + } + + int getSubAttributesCount(int quark) { + return attributeList.get(quark).getSubAttributesList().size(); + } + + ArrayList<Integer> getSubAttributes(int attributeQuark) { + ArrayList<Integer> listOfChildren = new ArrayList<Integer>(); + + for (Attribute childNode : attributeList.get(attributeQuark).getSubAttributesList()) { + listOfChildren.add(childNode.getQuark()); + } + return listOfChildren; + } + + String getFullAttributeName(int quark) { + if (quark >= attributeList.size() || quark < 0) { + return null; + } + return attributeList.get(quark).getFullAttributeName(); + } + + void debugPrint(PrintWriter writer) { + attributeTreeRoot.debugPrint(writer); + } + +}
\ No newline at end of file diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateHistorySystem.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateHistorySystem.java new file mode 100644 index 0000000000..3f77430564 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateHistorySystem.java @@ -0,0 +1,277 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.io.PrintWriter; +import java.util.ArrayList; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.helpers.IStateHistoryBackend; + +/** + * This is the extension of the StateSystem, which will save the state intervals + * that are created from the transient state (instead of discarding them, like a + * simple StateSystem would do). + * + * This allows the user to then run queries at past timestamps. + * + * DON'T FORGET to call .closeHistory() when you are done inserting intervals, + * or the storage backend will have no way of knowing it can close and write + * itself to disk, and its thread will keep running. + * + * @author alexmont + * + */ +public class StateHistorySystem extends StateSystem { + + /* + * Inherited from StateSystem + * + * protected ArrayList<AttributeTreeNode> attributeList; protected + * TransientState transState; protected CurrentState curState; + */ + + private final IStateHistoryBackend backend; + + /* + * This the container that will hold the result of full queries obtained + * with loadStateAtTime() + */ + private ArrayList<ITmfStateInterval> currentStateInfo; + + /** + * General constructor + * + * @param backend + * The "state history storage" backend to use. + * @param newFile + * Put true if this is a new history started from scratch. It is + * used to tell the state system where to get its attribute tree. + * @throws IOException + */ + public StateHistorySystem(IStateHistoryBackend backend, boolean newFile) + throws IOException { + this.backend = backend; + transState = new TransientState(backend); + currentStateInfo = new ArrayList<ITmfStateInterval>(); + + if (newFile) { + attributeTree = new AttributeTree(this); + } else { + /* We're opening an existing file */ + FileInputStream attributeTreeInput = backend.supplyAttributeTreeReader(); + this.attributeTree = new AttributeTree(this, attributeTreeInput); + transState.setInactive(); + } + } + + public IStateHistoryBackend getHistoryBackend() { + return backend; + } + + /** + * Method to close off the History Provider. This happens for example when + * we are done reading an off-line trace. First we close the TransientState, + * commit it to the Provider, mark it as inactive, then we write the + * Attribute Tree somewhere so we can reopen it later. + * + * @param endTime + * The requested End Time of the history, since it could be + * bigger than the timestamp of the last event or state change we + * have seen. All "ongoing" states will be extended until this + * 'endTime'. + * @throws TimeRangeException + * If the passed endTime doesn't make sense (for example, if + * it's earlier than the latest time) and the backend doesn't + * know how to handle it. + */ + public void closeHistory(long endTime) throws TimeRangeException { + File attributeTreeFile; + long attributeTreeFilePos; + long realEndTime = endTime; + + if (realEndTime < backend.getEndTime()) { + /* + * This can happen (empty nodes pushing the border further, etc.) + * but shouldn't be too big of a deal. + */ + realEndTime = backend.getEndTime(); + } + transState.closeTransientState(realEndTime); + backend.finishedBuilding(realEndTime); + + attributeTreeFile = backend.supplyAttributeTreeWriterFile(); + attributeTreeFilePos = backend.supplyAttributeTreeWriterFilePosition(); + if (attributeTreeFile != null) { + /* + * If null was returned, we simply won't save the attribute tree, + * too bad! + */ + attributeTree.writeSelf(attributeTreeFile, attributeTreeFilePos); + } + } + + /** + * @name External query methods + */ + + /** + * Load the state information at time 't' as the Current State. You can then + * use the queryState() method to query the value of different attributes, + * as they were at time 't'. + * + * On average if you need around 10 or more queries for the same timestamps, + * use this. If you need less than 10 (for example, running many queries for + * the same attributes but at different timestamps), you might be better + * using the querySingleState() methods instead. + * + * @param t + * We will recreate the state information to what it was at time + * t. + * @throws TimeRangeException + */ + public synchronized void loadStateAtTime(long t) throws TimeRangeException { + /* Empty the currentStateInfo */ + currentStateInfo = new ArrayList<ITmfStateInterval>( + attributeTree.getNbAttributes()); + for (int i = 0; i < attributeTree.getNbAttributes(); i++) { + currentStateInfo.add(null); + } + + backend.doQuery(currentStateInfo, t); + + if (transState.isActive()) { + transState.doQuery(currentStateInfo, t); + } + // We should have previously inserted an interval for every attribute + // for all possible timestamps (and those could contain 'nullValues'). + // There should be no 'null' objects at this point. + for (ITmfStateInterval interval : currentStateInfo) { + assert (interval != null); + } + } + + /** + * Once we have set up the "current state" using loadStateAtTime(), we can + * now run queries to get the state of individual attributes at the + * previously loaded timestamp. + * + * @param attributeQuark + * The quark of attribute for which we want the state. + * @return The StateInterval object matching this timestamp/attribute pair. + * @throws AttributeNotFoundException + */ + public ITmfStateInterval queryState(int attributeQuark) { + return currentStateInfo.get(attributeQuark); + } + + /** + * Alternative, singular version of the "queryState" method. This one does + * not update the whole stateInfo vector, like loadStateAtTimes does. It + * only searches for one specific entry in the state history. + * + * It should be used when you only want very few entries, instead of the + * whole state (or many entries, but all at different timestamps). If you do + * request many entries all at the same time, you should use the + * conventional loadStateAtTime() + queryState() method. + * + * @param t + * The timestamp at which we want the state + * @param attributeQuark + * Which attribute we want to get the state of + * @return The StateInterval representing the state + * @throws TimeRangeException + * @throws AttributeNotFoundException + */ + public ITmfStateInterval querySingleState(long t, int attributeQuark) + throws AttributeNotFoundException, TimeRangeException { + ITmfStateInterval ret; + + if (transState.hasInfoAboutStateOf(t, attributeQuark)) { + ret = transState.getOngoingInterval(attributeQuark); + } else { + ret = backend.doSingularQuery(t, attributeQuark); + } + assert (ret != null); + return ret; + } + + /** + * Return a list of state intervals, containing the "history" of a given + * attribute between timestamps t1 and t2. The list will be ordered by + * ascending time. + * + * @param attributeQuark + * Which attribute this query is interested in + * @param t1 + * Start time of the range query + * @param t2 + * End time of the query + * @return The List of state intervals that happened between t1 and t2 + * @throws TimeRangeException + * @throws AttributeNotFoundException + */ + public List<ITmfStateInterval> queryHistoryRange(int attributeQuark, long t1, + long t2) throws TimeRangeException, AttributeNotFoundException { + + List<ITmfStateInterval> intervals = new ArrayList<ITmfStateInterval>(); + ITmfStateInterval currentInterval; + long ts; + + /* Get the initial state at time T1 */ + currentInterval = querySingleState(t1, attributeQuark); + intervals.add(currentInterval); + + /* Get the following state changes */ + ts = currentInterval.getEndTime(); + while (ts != -1 && ts <= t2) { + ts++; /* To "jump over" to the next state in the history */ + currentInterval = querySingleState(ts, attributeQuark); + intervals.add(currentInterval); + ts = currentInterval.getEndTime(); + } + return intervals; + } + + /** + * @name Debugging methods + */ + + /** + * Print out the contents of the inner structures to the selected + * PrintWriter. + */ + @Override + public void debugPrint(PrintWriter writer) { + /* Only used for debugging, shouldn't be externalized */ + writer.println("------------------------------"); //$NON-NLS-1$ + writer.println("Current State Info vector:\n"); //$NON-NLS-1$ + for (int i = 0; i < currentStateInfo.size(); i++) { + writer.print(i + "\t\t"); //$NON-NLS-1$ + if (currentStateInfo.get(i) == null) { + writer.println("null"); //$NON-NLS-1$ + } else { + writer.println(currentStateInfo.get(i).toString()); + } + } + writer.println('\n'); + + /* Print the other inner containers */ + super.debugPrint(writer); + backend.debugPrint(writer); + } +}
\ No newline at end of file diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateSystem.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateSystem.java new file mode 100644 index 0000000000..0d24cb7631 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/StateSystem.java @@ -0,0 +1,410 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +import java.io.PrintWriter; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; +import org.eclipse.linuxtools.tmf.core.statevalue.StateValueTypeException; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * This is the base class for the StateHistorySystem. It contains all the + * current-state-updating methods. + * + * It's not abstract, as it can be used by itself: in this case, no History tree + * will be built underneath (no information will be saved to disk) and it will + * only be able to respond to queries to the current, latest time. + * + * @author alexmont + * + */ +public class StateSystem { + + /* References to the inner structures */ + protected AttributeTree attributeTree; + protected TransientState transState; + + /** + * Constructor. No configuration needed! + */ + public StateSystem() { + attributeTree = new AttributeTree(this); + + /* This will tell the builder to discard the intervals */ + transState = new TransientState(null); + } + + /** + * @name Quark-retrieving methods + */ + + /** + * Basic quark-retrieving method. Pass an attribute in parameter as an array + * of strings, the matching quark will be returned. + * + * This version will NOT create any new attributes. If an invalid attribute + * is requested, an exception will be thrown. This should ideally be used + * for doing read-only operations on the system, like queries for example. + * + * @param attribute + * Attribute given as its full path in the Attribute Tree + * @return The quark of the requested attribute, if it existed. + * @throws AttributeNotFoundException + * This exception is thrown if the requested attribute simply + * did not exist in the system. + */ + public int getQuarkAbsolute(String... attribute) + throws AttributeNotFoundException { + return attributeTree.getQuarkDontAdd(-1, attribute); + } + + /** + * Basic quark-retrieving method. Pass an attribute in parameter as an array + * of strings, the matching quark will be returned. + * + * This version WILL create new attributes: if the attribute passed in + * parameter is new in the system, it will be added and its new quark will + * be returned. + * + * @param attribute + * Attribute given as its full path in the Attribute Tree + * @return The quark of the attribute (which either existed or just got + * created) + */ + public int getQuarkAbsoluteAndAdd(String... attribute) { + return attributeTree.getQuarkAndAdd(-1, attribute); + } + + /** + * "Relative path" quark-getting method. Instead of specifying a full path, + * if you know the path is relative to another attribute for which you + * already have the quark, use this for better performance. + * + * This is useful for cases where a lot of modifications or queries will + * originate from the same branch of the attribute tree : the common part of + * the path won't have to be re-hashed for every access. + * + * This version will NOT create any new attributes. If an invalid attribute + * is requested, an exception will be thrown. This should ideally be used + * for doing read-only operations on the system, like queries for example. + * + * @param startingNodeQuark + * The quark of the attribute from which 'subPath' originates. + * @param subPath + * "Rest" of the path to get to the final attribute + * @return The matching quark, if it existed + * @throws AttributeNotFoundException + */ + public int getQuarkRelative(int startingNodeQuark, String... subPath) + throws AttributeNotFoundException { + return attributeTree.getQuarkDontAdd(startingNodeQuark, subPath); + } + + /** + * "Relative path" quark-getting method. Instead of specifying a full path, + * if you know the path is relative to another attribute for which you + * already have the quark, use this for better performance. + * + * This is useful for cases where a lot of modifications or queries will + * originate from the same branch of the attribute tree : the common part of + * the path won't have to be re-hashed for every access. + * + * This version WILL create new attributes: if the attribute passed in + * parameter is new in the system, it will be added and its new quark will + * be returned. + * + * @param startingNodeQuark + * The quark of the attribute from which 'subPath' originates. + * @param subPath + * "Rest" of the path to get to the final attribute + * @return The matching quark, either if it's new of just got created. + */ + public int getQuarkRelativeAndAdd(int startingNodeQuark, String... subPath) { + return attributeTree.getQuarkAndAdd(startingNodeQuark, subPath); + } + + /** + * @name External methods related to insertions in the history - + */ + + /** + * Basic attribute modification method, we simply specify a new value, for a + * given attribute, effective at the given timestamp. + * + * @param t + * Timestamp of the state change + * @param value + * The State Value we want to assign to the attribute + * @param attributeQuark + * Integer value of the quark corresponding to the attribute we + * want to modify + * @throws TimeRangeException + * If the requested time is outside of the trace's range + * @throws AttributeNotFoundException + * If the requested attribute quark is invalid + */ + public void modifyAttribute(long t, ITmfStateValue value, int attributeQuark) + throws TimeRangeException, AttributeNotFoundException { + transState.processStateChange(t, value, attributeQuark); + } + + /** + * Increment attribute method. Reads the current value of a given integer + * attribute (this value is right now in the Transient State), and increment + * it by 1. Useful for statistics. + * + * @param t + * Timestamp of the state change + * @param attributeQuark + * Attribute to increment. If it doesn't exist it will be added, + * with a new value of 1. + * @throws StateValueTypeException + * If the attribute already exists but is not of type Integer + * @throws TimeRangeException + * If the given timestamp is invalid + * @throws AttributeNotFoundException + * If the quark is invalid + */ + public void incrementAttribute(long t, int attributeQuark) + throws StateValueTypeException, TimeRangeException, + AttributeNotFoundException { + int prevValue = queryOngoingState(attributeQuark).unboxInt(); + /* prevValue should be == 0 if the attribute wasn't existing before */ + modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1), + attributeQuark); + } + + /** + * "Push" helper method. This uses the given integer attribute as a stack: + * The value of that attribute will represent the stack depth (always >= 1). + * Sub-attributes will be created, their base-name will be the position in + * the stack (1, 2, etc.) and their value will be the state value 'value' + * that was pushed to this position. + * + * @param t + * Timestamp of the state change + * @param value + * State value to assign to this stack position. + * @param attributeQuark + * The base attribute to use as a stack. If it does not exist if + * will be created (with depth = 1) + * @throws TimeRangeException + * If the requested timestamp is invalid + * @throws AttributeNotFoundException + * If the attribute is invalid + * @throws StateValueTypeException + * If the attribute 'attributeQuark' already exists, but is not + * of integer type. + */ + public void pushAttribute(long t, ITmfStateValue value, int attributeQuark) + throws TimeRangeException, AttributeNotFoundException, + StateValueTypeException { + assert (attributeQuark >= 0); + Integer stackDepth = 0; + int subAttributeQuark; + ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark); + + if (previousSV.isNull()) { + /* + * If the StateValue was null, this means this is the first time we + * use this attribute. Leave stackDepth at 0. + */ + } else if (previousSV.getType() == 0) { + /* Previous value was an integer, all is good, use it */ + stackDepth = previousSV.unboxInt(); + if (stackDepth >= 10) { + /* + * Limit stackDepth to 10, to avoid having Attribute Trees grow + * out of control due to buggy insertions + */ + assert (false); + } + } else { + /* Previous state of this attribute was another type? Not good! */ + assert (false); + } + + stackDepth++; + subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, + stackDepth.toString()); + + modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), + attributeQuark); + transState.processStateChange(t, value, subAttributeQuark); + } + + /** + * Antagonist of the pushAttribute(), pops the top-most attribute on the + * stack-attribute. If this brings it back to depth = 0, the attribute is + * kept with depth = 0. If the value is already 0, or if the attribute + * doesn't exist, nothing is done. + * + * @param t + * Timestamp of the state change + * @param attributeQuark + * Quark of the stack-attribute to pop + * @throws AttributeNotFoundException + * If the attribute is invalid + * @throws TimeRangeException + * If the timestamp is invalid + * @throws StateValueTypeException + * If the target attribute already exists, but its state value + * type is invalid (not an integer) + */ + public void popAttribute(long t, int attributeQuark) + throws AttributeNotFoundException, TimeRangeException, + StateValueTypeException { + assert (attributeQuark >= 0); + Integer stackDepth; + int subAttributeQuark; + ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark); + + if (previousSV.isNull()) { + /* + * If the StateValue was null, this means this is the first time we + * use this attribute. + */ + stackDepth = 0; + } else { + assert (previousSV.getType() == 0); + stackDepth = previousSV.unboxInt(); + } + + if (stackDepth == 0) { + /* + * Trying to pop an empty stack. This often happens at the start of + * traces, for example when we see a syscall_exit, without having + * the corresponding syscall_entry in the trace. Just ignore + * silently. + */ + return; + } else if (stackDepth < 0) { + /* This on the other hand should not happen... */ + assert (false); + } + + /* The attribute should already exist... */ + subAttributeQuark = getQuarkRelative(attributeQuark, + stackDepth.toString()); + + stackDepth--; + modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), + attributeQuark); + removeAttribute(t, subAttributeQuark); + } + + /** + * Remove attribute method. Similar to the above modify- methods, with value + * = 0 / null, except we will also "nullify" all the sub-contents of the + * requested path (a bit like "rm -rf") + * + * @param t + * Timestamp of the state change + * @param attributeQuark + * Attribute to remove + * @throws TimeRangeException + * If the timestamp is invalid + * @throws AttributeNotFoundException + * If the quark is invalid + */ + public void removeAttribute(long t, int attributeQuark) + throws TimeRangeException, AttributeNotFoundException { + assert (attributeQuark >= 0); + /* "Nullify our children first, recursively */ + List<Integer> childAttributes = attributeTree.getSubAttributes(attributeQuark); + for (Integer childNodeQuark : childAttributes) { + assert (attributeQuark != childNodeQuark); + removeAttribute(t, childNodeQuark); + } + /* Nullify ourselves */ + transState.processStateChange(t, TmfStateValue.nullValue(), + attributeQuark); + } + + /** + * @name "Current" query/update methods - + */ + + /** + * Returns the current state value we have (in the Transient State) for the + * given attribute. + * + * This is useful even for a StateHistorySystem, as we are guaranteed it + * will only do a memory access and not go look on disk (and we don't even + * have to provide a timestamp!) + * + * @param attributeQuark + * For which attribute we want the current state + * @return The State value that's "current" for this attribute + * @throws AttributeNotFoundException + * If the requested attribute is invalid + */ + public ITmfStateValue queryOngoingState(int attributeQuark) + throws AttributeNotFoundException { + return transState.getOngoingStateValue(attributeQuark); + } + + /** + * Modify a current "ongoing" state (instead of inserting a state change, + * like modifyAttribute() and others). + * + * This can be used to update the value of a previous state change, for + * example when we get information at the end of the state and not at the + * beginning. (return values of system calls, etc.) + * + * Note that past states can only be modified while they are still in + * memory, so only the "current state" can be updated. Once they get + * committed to disk (by inserting a new state change) it becomes too late. + * + * @param newValue + * The new value that will overwrite the "current" one. + * @param attributeQuark + * For which attribute in the system + * @throws AttributeNotFoundException + * If the requested attribute is invalid + */ + public void updateOngoingState(ITmfStateValue newValue, int attributeQuark) + throws AttributeNotFoundException { + transState.changeOngoingStateValue(attributeQuark, newValue); + } + + /** + * @name Debugging methods + */ + + /** + * This returns the slash-separated path of an attribute by providing its + * quark + * + * @param attributeQuark + * The quark of the attribute we want + * @return One single string separated with '/', like a filesystem path + */ + public String getFullAttributePath(int attributeQuark) { + return attributeTree.getFullAttributeName(attributeQuark); + } + + /** + * Print out the contents of the inner structures. + * + * @param writer + * The PrintWriter in which to print the output + */ + public void debugPrint(PrintWriter writer) { + attributeTree.debugPrint(writer); + transState.debugPrint(writer); + } + +}
\ No newline at end of file diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TimeRangeException.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TimeRangeException.java new file mode 100644 index 0000000000..8cde5a9796 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TimeRangeException.java @@ -0,0 +1,33 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +/** + * Generic exception for when the user specifies an invalid time stamp. Usually + * timestamps must be within the range of the trace or state history being + * queried. + * + * For insertions, it's forbidden to insert new states "in the past" (before where + * the cursor is), so this exception is also thrown in that case. + * + * @author alexmont + * + */ +public class TimeRangeException extends Exception { + + /** + * + */ + private static final long serialVersionUID = -4067685227260254532L; + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TransientState.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TransientState.java new file mode 100644 index 0000000000..d0a0a7eb10 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/TransientState.java @@ -0,0 +1,317 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem; + +import java.io.PrintWriter; +import java.util.ArrayList; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.interval.TmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.helpers.IStateHistoryBackend; +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * The Transient State is used to build intervals from puntual state changse. It + * contains a "state info" vector similar to the "current state", except here we + * also record the start time of every state stored in it. + * + * We can then build StateInterval's, to be inserted in the State History when + * we detect state changes : the "start time" of the interval will be the + * recorded time we have here, and the "end time" will be the timestamp of the + * new state-changing event we just read. + * + * @author alexmont + * + */ +class TransientState { + + /* Indicates where to insert state changes that we generate */ + private final IStateHistoryBackend backend; + + private boolean isActive; + private long latestTime; + + private ArrayList<ITmfStateValue> ongoingStateInfo; + private ArrayList<Long> ongoingStateStartTimes; + + TransientState(IStateHistoryBackend backend) { + this.backend = backend; + isActive = true; + ongoingStateInfo = new ArrayList<ITmfStateValue>(); + ongoingStateStartTimes = new ArrayList<Long>(); + + if (backend != null) { + latestTime = backend.getStartTime(); + } else { + latestTime = 0; + } + } + + long getLatestTime() { + return latestTime; + } + + ITmfStateValue getOngoingStateValue(int index) + throws AttributeNotFoundException { + + checkValidAttribute(index); + return ongoingStateInfo.get(index); + } + + void changeOngoingStateValue(int index, ITmfStateValue newValue) + throws AttributeNotFoundException { + + checkValidAttribute(index); + ongoingStateInfo.set(index, newValue); + } + + /** + * Return the "ongoing" value for a given attribute as a dummy interval + * whose end time = -1 (since we don't know its real end time yet). + * + * @param quark + * @throws AttributeNotFoundException + */ + ITmfStateInterval getOngoingInterval(int quark) + throws AttributeNotFoundException { + + checkValidAttribute(quark); + return new TmfStateInterval(ongoingStateStartTimes.get(quark), -1, quark, + ongoingStateInfo.get(quark)); + } + + private void checkValidAttribute(int quark) + throws AttributeNotFoundException { + + if (quark > ongoingStateInfo.size() - 1 || quark < 0) { + throw new AttributeNotFoundException(); + } + } + + /** + * Batch method of changeOngoingStateValue(), updates the complete + * ongoingStateInfo in one go. BE VERY CAREFUL WITH THIS! Especially with + * the sizes of both arrays. + * + * Note that the new ongoingStateInfo will be a shallow copy of + * newStateInfo, so that last one must be already instantiated and all. + * + * @param newStateInfo + * The List of StateValues to replace the old ongoingStateInfo + * one. + */ + void changeOngoingStateInfo(ArrayList<ITmfStateValue> newStateInfo) { + this.ongoingStateInfo = newStateInfo; + } + + /** + * Add an "empty line" to both "ongoing..." vectors. This is needed so the + * Ongoing... tables can stay in sync with the number of attributes in the + * attribute tree, namely when we add sub-path attributes. + */ + synchronized void addEmptyEntry() { + /* + * Since this is a new attribute, we suppose it was in the "null state" + * since the beginning (so we can have intervals covering for all + * timestamps). A null interval will then get added at the first state + * change. + */ + ongoingStateInfo.add(TmfStateValue.nullValue()); + + if (backend == null) { + ongoingStateStartTimes.add(0L); + } else { + ongoingStateStartTimes.add(backend.getStartTime()); + } + } + + /** + * Ask if the state information about attribute 'quark' at time 'time' is + * present in the Builder as it is right now. If it's not, it's either in + * the History Tree, or not in the system at all. + * + * Note that this method does not return the value itself (we don't even + * look for it, we can know by just looking at the timestamp) + * + * @param time + * The timestamp to look for + * @param quark + * The quark of the attribute to look for + * @return True if the value is present in the Transient State at this + * moment in time, false if it's not + */ + boolean hasInfoAboutStateOf(long time, int quark) { + return (this.isActive() && time >= ongoingStateStartTimes.get(quark)); + } + + /** + * This is the lower-level method that will be called by the + * StateHistorySystem (with already-built StateValues and timestamps) + * + * @param index + * The index in the vectors (== the quark of the attribute) + * @param value + * The new StateValue associated to this attribute + * @param eventTime + * The timestamp associated with this state change + * @throws TimeRangeException + * @throws AttributeNotFoundException + */ + synchronized void processStateChange(long eventTime, + ITmfStateValue value, int index) throws TimeRangeException, + AttributeNotFoundException { + assert (this.isActive); + checkValidAttribute(index); + + if (latestTime < eventTime) { + latestTime = eventTime; + } + + if (ongoingStateInfo.get(index).equals(value)) { + /* + * This is the case where the new value and the one already present + * in the Builder are the same. We do not need to create an + * interval, we'll just keep the current one going. + */ + return; + } + + if (backend != null && ongoingStateStartTimes.get(index) < eventTime) { + /* + * These two conditions are necessary to create an interval and + * update ongoingStateInfo. + */ + backend.insertPastState(ongoingStateStartTimes.get(index), /* + * Start + * Time + */ + eventTime - 1, /* End Time */ + index, /* attribute quark */ + ongoingStateInfo.get(index)); /* StateValue */ + + ongoingStateStartTimes.set(index, eventTime); + } + ongoingStateInfo.set(index, value); + return; + } + + /** + * Run a "get state at time" query on the Transient State only. + * + * @param stateInfo + * The stateInfo object in which we will put our relevant + * information + * @param t + * The requested timestamp + */ + void doQuery(List<ITmfStateInterval> stateInfo, long t) { + ITmfStateInterval interval; + + if (!this.isActive) { + return; + } + assert (stateInfo.size() == ongoingStateInfo.size()); + + for (int i = 0; i < ongoingStateInfo.size(); i++) { + /* + * We build a dummy interval with end time = -1 to put in the answer + * to the query. + */ + if (this.hasInfoAboutStateOf(t, i)) { + interval = new TmfStateInterval(ongoingStateStartTimes.get(i), -1, + i, ongoingStateInfo.get(i)); + stateInfo.set(i, interval); + } + } + } + + /** + * Close off the Transient State, used for example when we are done reading a + * static trace file. All the information currently contained in it will be + * converted to intervals and "flushed" to the State History. + */ + void closeTransientState(long endTime) { + assert (this.isActive); + + for (int i = 0; i < ongoingStateInfo.size(); i++) { + if (ongoingStateStartTimes.get(i) == endTime) { + /* + * Handle this rare case where trace end == timetamp of last + * state change + */ + continue; + } + try { + backend.insertPastState(ongoingStateStartTimes.get(i), /* + * Start + * Time + */ + endTime, /* End Time */ + i, /* attribute quark */ + ongoingStateInfo.get(i)); /* StateValue */ + + } catch (TimeRangeException e) { + /* + * This shouldn't happen, since we control where the interval's + * start time comes from + */ + e.printStackTrace(); + } + } + + ongoingStateInfo.clear(); + ongoingStateStartTimes.clear(); + this.isActive = false; + return; + } + + /** + * Simply returns if this Transient State is currently being used or not + * + * @return + */ + boolean isActive() { + return this.isActive; + } + + void setInactive() { + isActive = false; + } + + /** + * Debugging method that prints the contents of both 'ongoing...' vectors + * + * @param writer + */ + void debugPrint(PrintWriter writer) { + /* Only used for debugging, shouldn't be externalized */ + writer.println("------------------------------"); //$NON-NLS-1$ + writer.println("Info stored in the Builder:"); //$NON-NLS-1$ + if (!this.isActive) { + writer.println("Builder is currently inactive"); //$NON-NLS-1$ + writer.println('\n'); + return; + } + writer.println("\nAttribute\tStateValue\tValid since time"); //$NON-NLS-1$ + for (int i = 0; i < ongoingStateInfo.size(); i++) { + writer.format("%d\t\t", i); //$NON-NLS-1$ + writer.print(ongoingStateInfo.get(i).toString() + "\t\t"); //$NON-NLS-1$ + writer.println(ongoingStateStartTimes.get(i).toString()); + } + writer.println('\n'); + return; + } + +}
\ No newline at end of file diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/CoreNode.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/CoreNode.java new file mode 100644 index 0000000000..12bde682f6 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/CoreNode.java @@ -0,0 +1,178 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.nio.ByteBuffer; + +/** + * A Core node is a first-level node of a History Tree which is not a leaf node. + * + * It extends HTNode by adding support for child nodes, and also extensions. + * + * @author alexmont + * + */ +class CoreNode extends HTNode { + + /* Nb. of children this node has */ + private int nbChildren; + + /* Seq. numbers of the children nodes (size = MAX_NB_CHILDREN) */ + private int[] children; + + /* Start times of each of the children (size = MAX_NB_CHILDREN) */ + private long[] childStart; + + /* Seq number of this node's extension. -1 if none */ + private int extension; + + /** + * Initial constructor. Use this to initialize a new EMPTY node. + * + * @param tree + * The HistoryTree to which this node belongs + * @param seqNumber + * The (unique) sequence number assigned to this particular node + * @param parentSeqNumber + * The sequence number of this node's parent node + * @param start + * The earliest timestamp stored in this node + */ + CoreNode(HistoryTree tree, int seqNumber, int parentSeqNumber, + long start) { + super(tree, seqNumber, parentSeqNumber, start); + this.nbChildren = 0; + + /* + * We instantiate the two following arrays at full size right away, + * since we want to reserve that space in the node's header. + * "this.nbChildren" will tell us how many relevant entries there are in + * those tables. + */ + this.children = new int[ownerTree.config.maxChildren]; + this.childStart = new long[ownerTree.config.maxChildren]; + } + + @Override + protected void readSpecificHeader(ByteBuffer buffer) { + int i; + + extension = buffer.getInt(); + nbChildren = buffer.getInt(); + + children = new int[ownerTree.config.maxChildren]; + for (i = 0; i < nbChildren; i++) { + children[i] = buffer.getInt(); + } + for (i = nbChildren; i < ownerTree.config.maxChildren; i++) { + buffer.getInt(); + } + + this.childStart = new long[ownerTree.config.maxChildren]; + for (i = 0; i < nbChildren; i++) { + childStart[i] = buffer.getLong(); + } + for (i = nbChildren; i < ownerTree.config.maxChildren; i++) { + buffer.getLong(); + } + } + + @Override + protected void writeSpecificHeader(ByteBuffer buffer) { + int i; + + buffer.putInt(extension); + buffer.putInt(nbChildren); + + /* Write the "children's seq number" array */ + for (i = 0; i < nbChildren; i++) { + buffer.putInt(children[i]); + } + for (i = nbChildren; i < ownerTree.config.maxChildren; i++) { + buffer.putInt(0); + } + + /* Write the "children's start times" array */ + for (i = 0; i < nbChildren; i++) { + buffer.putLong(childStart[i]); + } + for (i = nbChildren; i < ownerTree.config.maxChildren; i++) { + buffer.putLong(0); + } + } + + int getNbChildren() { + return nbChildren; + } + + int getChild(int index) { + return children[index]; + } + + int getLatestChild() { + return children[nbChildren - 1]; + } + + long getChildStart(int index) { + return childStart[index]; + } + + long getLatestChildStart() { + return childStart[nbChildren - 1]; + } + + int getExtensionSequenceNumber() { + return extension; + } + + /** + * Tell this node that it has a new child (Congrats!) + * + * @param childNode + * The SHTNode object of the new child + */ + void linkNewChild(CoreNode childNode) { + assert (this.nbChildren < ownerTree.config.maxChildren); + + this.children[nbChildren] = childNode.getSequenceNumber(); + this.childStart[nbChildren] = childNode.getNodeStart(); + this.nbChildren++; + } + + @Override + protected byte getNodeType() { + return 1; + } + + @Override + protected int getTotalHeaderSize() { + int specificSize; + specificSize = 4 /* 1x int (extension node) */ + + 4 /* 1x int (nbChildren) */ + + /* MAX_NB * int ('children' table) */ + + 4 * ownerTree.config.maxChildren + + /* MAX_NB * Timevalue ('childStart' table) */ + + 8 * ownerTree.config.maxChildren; + + return getCommonHeaderSize() + specificSize; + } + + @Override + protected String toStringSpecific() { + /* Only used for debugging, shouldn't be externalized */ + return "Core Node, " + nbChildren + " children, "; //$NON-NLS-1$ //$NON-NLS-2$ + } + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTConfig.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTConfig.java new file mode 100644 index 0000000000..d86a398882 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTConfig.java @@ -0,0 +1,46 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.File; + +/** + * Configuration object for a StateHistoryTree. + * + * @author alexmont + * + */ +final class HTConfig { + + public final File stateFile; + public final int blockSize; + public final int maxChildren; + public final long treeStart; + + HTConfig(File newStateFile, int blockSize, int maxChildren, long startTime) { + this.stateFile = newStateFile; + this.blockSize = blockSize; + this.maxChildren = maxChildren; + this.treeStart = startTime; + } + + /** + * Version using default values for blocksize and maxchildren + * + * @param stateFileName + * @param startTime + */ + HTConfig(File newStateFile, long startTime) { + this(newStateFile, 64 * 1024, 50, startTime); + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTInterval.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTInterval.java new file mode 100644 index 0000000000..0ac743ecfc --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTInterval.java @@ -0,0 +1,279 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.IOException; +import java.nio.ByteBuffer; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; +import org.eclipse.linuxtools.tmf.core.statevalue.StateValueTypeException; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * The interval component, which will be contained in a node of the History + * Tree. + * + * @author alexmont + * + */ +final class HTInterval implements ITmfStateInterval, Comparable<HTInterval> { + + private final long start; + private final long end; + private final int attribute; + private final TmfStateValue sv; + + /* + * Size of the strings section entry used by this interval (= 0 if not used) + */ + private final int stringsEntrySize; + + /** + * Standard constructor + * + * @param intervalStart + * @param intervalEnd + * @param attribute + * @param value + * @throws TimeRangeException + */ + HTInterval(long intervalStart, long intervalEnd, int attribute, + TmfStateValue value) throws TimeRangeException { + if (intervalStart > intervalEnd) { + throw new TimeRangeException(); + } + + this.start = intervalStart; + this.end = intervalEnd; + this.attribute = attribute; + this.sv = value; + this.stringsEntrySize = computeStringsEntrySize(); + } + + /** + * Reader constructor. Builds the interval using an already-allocated + * ByteBuffer, which normally comes from a NIO FileChannel. + * + * @param buffer + * The ByteBuffer from which to read the information + * @throws IOException + */ + final static HTInterval readFrom(ByteBuffer buffer) throws IOException { + HTInterval interval; + long intervalStart, intervalEnd; + int attribute; + TmfStateValue value; + int valueOrOffset, valueSize, res; + byte valueType; + byte array[]; + + /* Read the Data Section entry */ + intervalStart = buffer.getLong(); + intervalEnd = buffer.getLong(); + attribute = buffer.getInt(); + + /* Read the 'type' of the value, then react accordingly */ + valueType = buffer.get(); + if (valueType <= 0) { + /* the type of ValueOrOffset is 'value' */ + valueOrOffset = buffer.getInt(); + if (valueOrOffset == -1) { + /* Null value */ + value = TmfStateValue.nullValue(); + } else { + /* Normal integer value */ + value = TmfStateValue.newValueInt(valueOrOffset); + } + + } else { // valueType > 0 + /* the type is 'offset' */ + valueOrOffset = buffer.getInt(); + + /* + * Go read the corresponding entry in the Strings section of the + * block + */ + buffer.mark(); + buffer.position(valueOrOffset); + + /* the first byte = the size to read */ + valueSize = buffer.get(); + + /* + * Careful though, 'valueSize' is the total size of the entry, + * including the 'size' byte at the start and end (0'ed) byte at the + * end. Here we want 'array' to only contain the real payload of the + * value. + */ + array = new byte[valueSize - 2]; + buffer.get(array); + value = TmfStateValue.newValueString(new String(array)); + + /* Confirm the 0'ed byte at the end */ + res = buffer.get(); + if (res != 0) { + throw new IOException( + "Invalid interval data. Maybe your file is corrupt?"); //$NON-NLS-1$ + } + + /* + * Restore the file pointer's position (so we can read the next + * interval) + */ + buffer.reset(); + } + + try { + interval = new HTInterval(intervalStart, intervalEnd, attribute, + value); + } catch (TimeRangeException e) { + throw new IOException( + "Invalid interval data. Maybe your file is corrupt?"); //$NON-NLS-1$ + } + return interval; + } + + /** + * Antagonist of the previous constructor, write the Data entry + * corresponding to this interval in a ByteBuffer (mapped to a block in the + * history-file, hopefully) + * + * @param buffer + * The already-allocated ByteBuffer corresponding to a SHT Node + * @param endPosOfStringEntry + * The initial (before calling this function for this interval) + * position of the Strings Entry for this node. This will change + * from one call to the other if we're writing String + * StateValues. + * @return The size of the Strings Entry that was written, if any. + */ + int writeInterval(ByteBuffer buffer, int endPosOfStringEntry) { + int sizeOfStringEntry; + byte[] byteArrayToWrite; + + buffer.putLong(start); + buffer.putLong(end); + buffer.putInt(attribute); + buffer.put(sv.getType()); + + byteArrayToWrite = sv.toByteArray(); + + if (byteArrayToWrite == null) { + /* We write the 'valueOffset' field as a straight value */ + if (sv.isNull()) { + buffer.putInt(0); + } else { + try { + buffer.putInt(sv.unboxInt()); + } catch (StateValueTypeException e) { + /* + * This should not happen, since the value told us it was of + * type Integer (corrupted value?) + */ + e.printStackTrace(); + } + } + return 0; /* we didn't use a Strings section entry */ + + } + /* + * Size to write (+2 = +1 for size at the start, +1 for the 0 at the + * end) + */ + sizeOfStringEntry = byteArrayToWrite.length + 2; + + /* we use the valueOffset as an offset. */ + buffer.putInt(endPosOfStringEntry - sizeOfStringEntry); + buffer.mark(); + buffer.position(endPosOfStringEntry - sizeOfStringEntry); + + /* + * write the Strings entry (1st byte = size, then the bytes, then + * the 0) + */ + buffer.put((byte) sizeOfStringEntry); + buffer.put(byteArrayToWrite); + buffer.put((byte) 0); + assert (buffer.position() == endPosOfStringEntry); + buffer.reset(); + return sizeOfStringEntry; + } + + @Override + public long getStartTime() { + return start; + } + + @Override + public long getEndTime() { + return end; + } + + @Override + public int getAttribute() { + return attribute; + } + + @Override + public ITmfStateValue getStateValue() { + return sv; + } + + @Override + public boolean intersects(long timestamp) { + if (start <= timestamp) { + if (end >= timestamp) { + return true; + } + } + return false; + } + + int getStringsEntrySize() { + return stringsEntrySize; + } + + /** + * Total serialized size of this interval + * + * @return + */ + int getIntervalSize() { + return stringsEntrySize + HTNode.getDataEntrySize(); + } + + private int computeStringsEntrySize() { + if (sv.toByteArray() == null) { + return 0; + } + return sv.toByteArray().length + 2; + /* (+1 for the first byte indicating the size, +1 for the 0'ed byte) */ + } + + /** + * Compare the END TIMES of different intervals. This is used to sort the + * intervals when we close down a node. + */ + @Override + public int compareTo(HTInterval other) { + if (this.end < other.end) { + return -1; + } else if (this.end > other.end) { + return 1; + } else { + return 0; + } + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTNode.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTNode.java new file mode 100644 index 0000000000..60147dbfcb --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HTNode.java @@ -0,0 +1,530 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.IOException; +import java.io.PrintWriter; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.nio.channels.FileChannel; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * The base class for all the types of nodes that go in the History Tree. + * + * @author alexmont + * + */ +abstract class HTNode { + + /* Reference to the History Tree to whom this node belongs */ + protected final HistoryTree ownerTree; + + /* Time range of this node */ + private final long nodeStart; + private long nodeEnd; + + /* Sequence number = position in the node section of the file */ + private final int sequenceNumber; + private int parentSequenceNumber; /* = -1 if this node is the root node */ + + /* Where the Strings section begins (from the start of the node */ + private int stringSectionOffset; + + /* True if this node is closed (and to be committed to disk) */ + private boolean isDone; + + /* Vector containing all the intervals contained in this node */ + private final ArrayList<HTInterval> intervals; + + HTNode(HistoryTree tree, int seqNumber, int parentSeqNumber, long start) { + this.ownerTree = tree; + this.nodeStart = start; + this.sequenceNumber = seqNumber; + this.parentSequenceNumber = parentSeqNumber; + + this.stringSectionOffset = ownerTree.config.blockSize; + this.isDone = false; + this.intervals = new ArrayList<HTInterval>(); + } + + /** + * Reader factory constructor. Build a Node object (of the right type) by + * reading a block in the file. + * + * @param tree + * Reference to the HT which will own this node + * @param fc + * FileChannel to the history file, ALREADY SEEKED at the start + * of the node. + * @throws IOException + */ + final static HTNode readNode(HistoryTree tree, FileChannel fc) + throws IOException { + HTNode newNode = null; + int res, i; + + ByteBuffer buffer = ByteBuffer.allocate(tree.config.blockSize); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + res = fc.read(buffer); + assert (res == tree.config.blockSize); + // This often breaks, so might as well keep this code not too far... + // if ( res != tree.config.blockSize ) { + // tree.debugPrintFullTree(new PrintWriter(System.out, true), null, + // false); + // assert ( false ); + // } + buffer.flip(); + + /* Read the common header part */ + byte type = buffer.get(); + long start = buffer.getLong(); + long end = buffer.getLong(); + int seqNb = buffer.getInt(); + int parentSeqNb = buffer.getInt(); + int intervalCount = buffer.getInt(); + int stringSectionOffset = buffer.getInt(); + boolean done = byteToBool(buffer.get()); + + /* Now the rest of the header depends on the node type */ + switch (type) { + case 1: + /* Core nodes */ + newNode = new CoreNode(tree, seqNb, parentSeqNb, start); + newNode.readSpecificHeader(buffer); + break; + + // TODO implement other node types + // case 2: + // /* Leaf nodes */ + // + // break; + // + // + // case 3: + // /* "Claudette" (extended) nodes */ + // + // break; + + default: + /* Unrecognized node type */ + throw new IOException(); + } + + /* + * At this point, we should be done reading the header and 'buffer' + * should only have the intervals left + */ + for (i = 0; i < intervalCount; i++) { + newNode.intervals.add(HTInterval.readFrom(buffer)); + } + + /* Assign the node's other information we have read previously */ + newNode.nodeEnd = end; + newNode.stringSectionOffset = stringSectionOffset; + newNode.isDone = done; + + return newNode; + } + + final void writeSelf(FileChannel fc) throws IOException { + int res, size; + int curStringsEntryEndPos = ownerTree.config.blockSize; + + ByteBuffer buffer = ByteBuffer.allocate(ownerTree.config.blockSize); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + + /* Write the common header part */ + buffer.put(this.getNodeType()); + buffer.putLong(nodeStart); + buffer.putLong(nodeEnd); + buffer.putInt(sequenceNumber); + buffer.putInt(parentSequenceNumber); + buffer.putInt(intervals.size()); + buffer.putInt(stringSectionOffset); + buffer.put(boolToByte(isDone)); + + /* Now call the inner method to write the specific header part */ + this.writeSpecificHeader(buffer); + + /* Back to us, we write the intervals */ + for (HTInterval interval : intervals) { + size = interval.writeInterval(buffer, curStringsEntryEndPos); + curStringsEntryEndPos -= size; + } + + /* + * Write padding between the end of the Data section and the start of + * the Strings section (needed to fill the node in case there is no + * Strings section) + */ + while (buffer.position() < stringSectionOffset) { + buffer.put((byte) 0); + } + + /* + * If the offsets were right, the size of the Strings section should be + * == to the expected size + */ + assert (curStringsEntryEndPos == stringSectionOffset); + + /* Finally, write everything in the Buffer to disk */ + + // if we don't do this, flip() will lose what's after. + buffer.position(ownerTree.config.blockSize); + + buffer.flip(); + res = fc.write(buffer); + assert (res == ownerTree.config.blockSize); + } + + /** + * Accessors + */ + long getNodeStart() { + return nodeStart; + } + + long getNodeEnd() { + if (this.isDone) { + return nodeEnd; + } + return 0; + } + + int getSequenceNumber() { + return sequenceNumber; + } + + int getParentSequenceNumber() { + return parentSequenceNumber; + } + + /** + * Change this node's parent. Used when we create a new root node for + * example. + */ + void setParentSequenceNumber(int newParent) { + parentSequenceNumber = newParent; + } + + boolean isDone() { + return isDone; + } + + /** + * Add an interval to this node + * + * @param newInterval + */ + void addInterval(HTInterval newInterval) { + /* Just in case, but should be checked before even calling this function */ + assert (newInterval.getIntervalSize() <= this.getNodeFreeSpace()); + + intervals.add(newInterval); + + /* Update the in-node offset "pointer" */ + stringSectionOffset -= (newInterval.getStringsEntrySize()); + } + + /** + * We've received word from the containerTree that newest nodes now exist to + * our right. (Puts isDone = true and sets the endtime) + * + * @param endtime + * The nodeEnd time that the node will have + * @throws TimeRangeException + */ + void closeThisNode(long endtime) { + assert (endtime >= this.nodeStart); + // /* This also breaks often too */ + // if ( endtime.getValue() <= this.nodeStart.getValue() ) { + // ownerTree.debugPrintFullTree(new PrintWriter(System.out, true), null, + // false); + // assert ( false ); + // } + + if (intervals.size() > 0) { + /* + * Sort the intervals by ascending order of their end time. This + * speeds up lookups a bit + */ + Collections.sort(intervals); + + /* + * Make sure there are no intervals in this node with their EndTime + * > the one requested. Only need to check the last one since they + * are now sorted + */ + assert (endtime >= intervals.get(intervals.size() - 1).getEndTime()); + } + + this.isDone = true; + this.nodeEnd = endtime; + return; + } + + /** + * The method to fill up the stateInfo (passed on from the Current State + * Tree when it does a query on the SHT). We'll replace the data in that + * vector with whatever relevant we can find from this node + * + * @param stateInfo + * The same stateInfo that comes from SHT's doQuery() + * @param t + * The timestamp for which the query is for. Only return + * intervals that intersect t. + * @throws TimeRangeException + */ + void writeInfoFromNode(List<ITmfStateInterval> stateInfo, long t) + throws TimeRangeException { + assert (this.isDone); // not sure this will always be the case... + int startIndex; + + if (intervals.size() == 0) { + return; + } + startIndex = getStartIndexFor(t); + + for (int i = startIndex; i < intervals.size(); i++) { + /* + * Now we only have to compare the Start times, since we now the End + * times necessarily fit + */ + if (intervals.get(i).getStartTime() <= t) { + stateInfo.set(intervals.get(i).getAttribute(), intervals.get(i)); + } + } + return; + } + + /** + * Get a single Interval from the information in this node If the + * key/timestamp pair cannot be found, we return null. + * + * @param key + * @param t + * @return The Interval containing the information we want, or null if it + * wasn't found + * @throws TimeRangeException + */ + HTInterval getRelevantInterval(int key, long t) throws TimeRangeException { + assert (this.isDone); + int startIndex; + + if (intervals.size() == 0) { + return null; + } + + startIndex = getStartIndexFor(t); + + for (int i = startIndex; i < intervals.size(); i++) { + if (intervals.get(i).getAttribute() == key) { + if (intervals.get(i).getStartTime() <= t) { + return intervals.get(i); + } + } + } + /* We didn't find the relevant information in this node */ + return null; + } + + private int getStartIndexFor(long t) throws TimeRangeException { + HTInterval dummy; + int index; + + /* + * Since the intervals are sorted by end time, we can skip all the ones + * at the beginning whose end times are smaller than 't'. Java does + * provides a .binarySearch method, but its API is quite weird... + */ + dummy = new HTInterval(0, t, 0, TmfStateValue.nullValue()); + index = Collections.binarySearch(intervals, dummy); + + if (index < 0) { + /* + * .binarySearch returns a negative number if the exact value was + * not found. Here we just want to know where to start searching, we + * don't care if the value is exact or not. + */ + index = -index - 1; + + } + + /* Sometimes binarySearch yields weird stuff... */ + if (index < 0) { + index = 0; + } + if (index >= intervals.size()) { + index = intervals.size() - 1; + } + + /* + * Another API quirkiness, the returned index is the one of the *last* + * element of a series of equal endtimes, which happens sometimes. We + * want the *first* element of such a series, to read through them + * again. + */ + while (index > 0 + && intervals.get(index - 1).compareTo(intervals.get(index)) == 0) { + index--; + } + // FIXME F*ck all this, just do our own binary search in a saner way... + + // //checks to make sure startIndex works how I think it does + // if ( startIndex > 0 ) { assert ( intervals.get(startIndex-1).getEnd() + // < t ); } + // assert ( intervals.get(startIndex).getEnd() >= t ); + // if ( startIndex < intervals.size()-1 ) { assert ( + // intervals.get(startIndex+1).getEnd() >= t ); } + + return index; + } + + /** + * @return The offset, within the node, where the Data section ends + */ + private int getDataSectionEndOffset() { + return this.getTotalHeaderSize() + HTNode.getDataEntrySize() + * intervals.size(); + } + + /** + * Returns the free space in the node, which is simply put, the + * stringSectionOffset - dataSectionOffset + */ + int getNodeFreeSpace() { + return stringSectionOffset - this.getDataSectionEndOffset(); + } + + /** + * Returns the current space utilisation of this node, as a percentage. + * (used space / total usable space, which excludes the header) + */ + long getNodeUsagePRC() { + float freePercent = (float) this.getNodeFreeSpace() + / (float) (ownerTree.config.blockSize - this.getTotalHeaderSize()) + * 100f; + return (long) (100L - freePercent); + } + + protected final static int getDataEntrySize() { + return 16 /* 2 x Timevalue/long (interval start + end) */ + + 4 /* int (key) */ + + 1 /* byte (type) */ + + 4; /* int (valueOffset) */ + /* = 25 */ + } + + protected final static byte boolToByte(boolean thebool) { + if (thebool) { + return (byte) 1; + } + return (byte) 0; + } + + final static boolean byteToBool(byte thebyte) { + return (thebyte == (byte) 1); + } + + /** + * @name Debugging functions + */ + + @SuppressWarnings("nls") + @Override + public String toString() { + /* Only used for debugging, shouldn't be externalized */ + StringBuffer buf = new StringBuffer("Node #" + sequenceNumber + ", "); + buf.append(this.toStringSpecific()); + buf.append(intervals.size() + " intervals (" + this.getNodeUsagePRC() + + "% used), "); + + buf.append("[" + this.nodeStart + " - "); + if (this.isDone) { + buf = buf.append("" + this.nodeEnd + "]"); + } else { + buf = buf.append("...]"); + } + return buf.toString(); + } + + /** + * Debugging function that prints out the contents of this node + * + * @param writer + * PrintWriter in which we will print the debug output + */ + @SuppressWarnings("nls") + void debugPrintIntervals(PrintWriter writer) { + /* Only used for debugging, shouldn't be externalized */ + writer.println("Node #" + sequenceNumber + ":"); + + /* Array of children */ + if (this.getNodeType() == 1) { /* Only Core Nodes can have children */ + CoreNode thisNode = (CoreNode) this; + writer.print(" " + thisNode.getNbChildren() + " children"); + if (thisNode.getNbChildren() >= 1) { + writer.print(": [ " + thisNode.getChild(0)); + for (int i = 1; i < thisNode.getNbChildren(); i++) { + writer.print(", " + thisNode.getChild(i)); + } + writer.print(']'); + } + writer.print('\n'); + } + + /* List of intervals in the node */ + writer.println(" Intervals contained:"); + for (int i = 0; i < intervals.size(); i++) { + writer.println(intervals.get(i).toString()); + } + writer.println('\n'); + } + + final static int getCommonHeaderSize() { + /* + * 1 - byte (type) + * + * 16 - 2x long (start time, end time) + * + * 16 - 4x int (seq number, parent seq number, intervalcount, strings + * section pos.) + * + * 1 - byte (done or not) + */ + return 34; + } + + /** + * @name Abstract methods + */ + + protected abstract byte getNodeType(); + + protected abstract int getTotalHeaderSize(); + + protected abstract void readSpecificHeader(ByteBuffer buffer); + + protected abstract void writeSpecificHeader(ByteBuffer buffer); + + protected abstract String toStringSpecific(); +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HT_IO.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HT_IO.java new file mode 100644 index 0000000000..66bdcb6a71 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HT_IO.java @@ -0,0 +1,168 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.File; +import java.io.FileInputStream; +import java.io.FileOutputStream; +import java.io.IOException; +import java.nio.channels.FileChannel; + +/** + * This class exists mainly for code isolation/clarification purposes. It + * contains all the methods and descriptors to handle reading/writing to the + * tree-file on disk and all the caching mechanisms. Every HistoryTree should + * contain 1 and only 1 HT_IO element. + * + * @author alexmont + * + */ +class HT_IO { + + /* reference to the tree to which this IO-object belongs */ + private final HistoryTree tree; + + /* Fields related to the file I/O */ + private FileInputStream fis; + private FileOutputStream fos; + private FileChannel fcIn; + private FileChannel fcOut; + + /** + * Standard constructor + * + * @param tree + * @param newFile Are we creating a new file from scratch? + * @throws IOException + */ + HT_IO(HistoryTree tree, boolean newFile) throws IOException { + this.tree = tree; + File historyTreeFile = tree.config.stateFile; + + if (newFile) { + /* Create a new empty History Tree file */ + if (historyTreeFile.exists()) { + historyTreeFile.delete(); + } + historyTreeFile.createNewFile(); + fis = new FileInputStream(historyTreeFile); + fos = new FileOutputStream(historyTreeFile, false); + } else { + /* + * We want to open an existing file, make sure we don't squash the + * existing content when opening the fos! + */ + this.fis = new FileInputStream(historyTreeFile); + this.fos = new FileOutputStream(historyTreeFile, true); + } + this.fcIn = fis.getChannel(); + this.fcOut = fos.getChannel(); + } + + /** + * Generic "read node" method, which checks if the node is in memory first, + * and if it's not it goes to disk to retrieve it. + * + * @param seqNumber + * Sequence number of the node we want + * @return The wanted node in object form + */ + HTNode readNode(int seqNumber) { + HTNode node = readNodeFromMemory(seqNumber); + if (node == null) { + return readNodeFromDisk(seqNumber); + } + return node; + } + + private HTNode readNodeFromMemory(int seqNumber) { + for (HTNode node : tree.latestBranch) { + if (node.getSequenceNumber() == seqNumber) { + return node; + } + } + return null; + } + + /** + * This method here isn't private, if we know for sure the node cannot be in + * memory it's a bit faster to use this directly (when opening a file from + * disk for example) + */ + HTNode readNodeFromDisk(int seqNumber) { + HTNode readNode; + try { + seekFCToNodePos(fcIn, seqNumber); + readNode = HTNode.readNode(tree, fcIn); + return readNode; + } catch (IOException e) { + e.printStackTrace(); + return null; + } + } + + void writeNode(HTNode node) { + try { + /* Position ourselves at the start of the node and write it */ + seekFCToNodePos(fcOut, node.getSequenceNumber()); + node.writeSelf(fcOut); + } catch (IOException e) { + /* If we were able to open the file, we should be fine now... */ + e.printStackTrace(); + } + } + + FileChannel getFcOut() { + return this.fcOut; + } + + FileInputStream supplyATReader() { + try { + /* + * Position ourselves at the start of the Mapping section in the + * file (which is right after the Blocks) + */ + seekFCToNodePos(fcIn, tree.getNodeCount()); + } catch (IOException e) { + e.printStackTrace(); + } + return fis; + } + + File supplyATWriterFile() { + return tree.config.stateFile; + } + + long supplyATWriterFilePos() { + return HistoryTree.getTreeHeaderSize() + + ((long) tree.getNodeCount() * tree.config.blockSize); + } + + /** + * Seek the given FileChannel to the position corresponding to the node that + * has seqNumber + * + * @param seqNumber + * @throws IOException + */ + private void seekFCToNodePos(FileChannel fc, int seqNumber) + throws IOException { + fc.position(HistoryTree.getTreeHeaderSize() + (long) seqNumber + * tree.config.blockSize); + /* + * cast to (long) is needed to make sure the result is a long too and + * doesn't get truncated + */ + } + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTree.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTree.java new file mode 100644 index 0000000000..78cb75dfaa --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTree.java @@ -0,0 +1,633 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.io.PrintWriter; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.nio.channels.FileChannel; +import java.util.Vector; + +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; + +/** + * Meta-container for the History Tree. This structure contains all the + * high-level data relevant to the tree. + * + * @author alexmont + * + */ +class HistoryTree { + + private static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; + + /** + * File format version. Increment minor on backwards-compatible changes. + * Increment major + set minor back to 0 when breaking compatibility. + */ + private static final int MAJOR_VERSION = 3; + private static final byte MINOR_VERSION = 0; + + /** + * Tree-specific configuration + */ + /* Container for all the configuration constants */ + protected final HTConfig config; + + /* Reader/writer object */ + private final HT_IO treeIO; + + /** + * Variable Fields (will change throughout the existance of the SHT) + */ + /* Latest timestamp found in the tree (at any given moment) */ + private long treeEnd; + + /* How many nodes exist in this tree, total */ + private int nodeCount; + + /* "Cache" to keep the active nodes in memory */ + protected Vector<CoreNode> latestBranch; + + /** + * Create a new State History from scratch, using a SHTConfig object for + * configuration + * + * @param conf + * @throws IOException + */ + private HistoryTree(HTConfig conf) throws IOException { + /* + * Simple assertion to make sure we have enough place in the 0th block + * for the tree configuration + */ + assert (conf.blockSize >= getTreeHeaderSize()); + + config = conf; + treeEnd = conf.treeStart; + nodeCount = 0; + latestBranch = new Vector<CoreNode>(); + + /* Prepare the IO object */ + treeIO = new HT_IO(this, true); + + /* Add the first node to the tree */ + CoreNode firstNode = initNewCoreNode(-1, conf.treeStart); + latestBranch.add(firstNode); + } + + /** + * "New State History" constructor, which doesn't use SHTConfig but the + * individual values separately. Kept for now for backwards compatibility, + * but you should definitely consider using SHTConfig instead (since its + * contents can then change without directly affecting SHT's API). + */ + HistoryTree(File newStateFile, int blockSize, int maxChildren, + long startTime) throws IOException { + this(new HTConfig(newStateFile, blockSize, maxChildren, startTime)); + } + + /** + * "Reader" constructor : instantiate a SHTree from an existing tree file on + * disk + * + * @param existingFileName + * Path/filename of the history-file we are to open + * @throws IOException + */ + HistoryTree(File existingStateFile) throws IOException { + /* + * Open the file ourselves, get the tree header information we need, + * then pass on the descriptor to the TreeIO object. + */ + int rootNodeSeqNb, res; + int bs, maxc; + long ts; + + /* Java I/O mumbo jumbo... */ + if ((!existingStateFile.exists()) || existingStateFile.length() <= 0) { + throw new IOException("Invalid state file selected"); //$NON-NLS-1$ + } + + FileInputStream fis = new FileInputStream(existingStateFile); + ByteBuffer buffer = ByteBuffer.allocate(getTreeHeaderSize()); + FileChannel fc = fis.getChannel(); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + fc.read(buffer); + buffer.flip(); + + /* + * Check the magic number,to make sure we're opening the right type of + * file + */ + res = buffer.getInt(); + if (res != HISTORY_FILE_MAGIC_NUMBER) { + throw new IOException("Selected file does not look like a History Tree file"); //$NON-NLS-1$ + } + + res = buffer.getInt(); /* Major version number */ + if (res != MAJOR_VERSION) { + throw new IOException("Select History Tree file is of an older " //$NON-NLS-1$ + + "format. Please use a previous version of " //$NON-NLS-1$ + + "the parser to open it."); //$NON-NLS-1$ + } + + res = buffer.getInt(); /* Minor version number */ + + bs = buffer.getInt(); /* Block Size */ + maxc = buffer.getInt(); /* Max nb of children per node */ + + this.nodeCount = buffer.getInt(); + rootNodeSeqNb = buffer.getInt(); + + /* Go read the start time, which is also the root node's start time */ + // TODO maybe make this part less ugly, as we need treeStart to build + // the SHTConfig object, but we need that object for new SHT_IO() + // and rebuildLatestBranch() ... + fc.position(getTreeHeaderSize() + (long) rootNodeSeqNb * bs); + buffer = ByteBuffer.allocate(8); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + res = fc.read(buffer); + assert (res == 8); + buffer.flip(); + ts = buffer.getLong(); + + this.config = new HTConfig(existingStateFile, bs, maxc, ts); + fis.close(); + /* + * FIXME We close fis here and the TreeIO will then reopen the same + * file, not extremely elegant. But how to pass the information here to + * the SHT otherwise? + */ + this.treeIO = new HT_IO(this, false); + + rebuildLatestBranch(rootNodeSeqNb); + ts = latestBranch.firstElement().getNodeStart(); + this.treeEnd = latestBranch.firstElement().getNodeEnd(); + } + + /** + * "Save" the tree to disk. This method will cause the treeIO object to + * commit all nodes to disk and then return the RandomAccessFile descriptor + * so the Tree object can save its configuration into the header of the + * file. + * + * @param requestedEndTime + */ + void closeTree() { + FileChannel fc; + ByteBuffer buffer; + int i, res; + + /* Close off the latest branch of the tree */ + for (i = 0; i < latestBranch.size(); i++) { + latestBranch.get(i).closeThisNode(treeEnd); + treeIO.writeNode(latestBranch.get(i)); + } + + /* Only use this for debugging purposes, it's VERY slow! */ + // this.checkIntegrity(); + + fc = treeIO.getFcOut(); + buffer = ByteBuffer.allocate(getTreeHeaderSize()); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + + /* Save the config of the tree to the header of the file */ + try { + fc.position(0); + + buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); + + buffer.putInt(MAJOR_VERSION); + buffer.putInt(MINOR_VERSION); + + buffer.putInt(config.blockSize); + buffer.putInt(config.maxChildren); + + buffer.putInt(nodeCount); + + /* root node seq. nb */ + buffer.putInt(latestBranch.firstElement().getSequenceNumber()); + + buffer.flip(); + res = fc.write(buffer); + assert (res <= getTreeHeaderSize()); + /* done writing the file header */ + + } catch (IOException e) { + /* We should have any problems at this point... */ + e.printStackTrace(); + } + return; + } + + /** + * @name Accessors + */ + + long getTreeStart() { + return config.treeStart; + } + + long getTreeEnd() { + return treeEnd; + } + + int getNodeCount() { + return nodeCount; + } + + HT_IO getTreeIO() { + return treeIO; + } + + /** + * Rebuild the latestBranch "cache" object by reading the nodes from disk + * (When we are opening an existing file on disk and want to append to it, + * for example). + * + * @param rootNodeSeqNb + * The sequence number of the root node, so we know where to + * start + */ + private void rebuildLatestBranch(int rootNodeSeqNb) { + HTNode nextChildNode; + + this.latestBranch = new Vector<CoreNode>(); + + nextChildNode = treeIO.readNodeFromDisk(rootNodeSeqNb); + latestBranch.add((CoreNode) nextChildNode); + while (latestBranch.lastElement().getNbChildren() > 0) { + nextChildNode = treeIO.readNodeFromDisk(latestBranch.lastElement().getLatestChild()); + latestBranch.add((CoreNode) nextChildNode); + } + } + + /** + * Insert an interval in the tree + * + * @param interval + */ + void insertInterval(HTInterval interval) throws TimeRangeException { + if (interval.getStartTime() < config.treeStart) { + throw new TimeRangeException(); + } + tryInsertAtNode(interval, latestBranch.size() - 1); + } + + /** + * Inner method to find in which node we should add the interval. + * + * @param interval + * The interval to add to the tree + * @param indexOfNode + * The index *in the latestBranch* where we are trying the + * insertion + */ + private void tryInsertAtNode(HTInterval interval, int indexOfNode) { + HTNode targetNode = latestBranch.get(indexOfNode); + + /* Verify if there is enough room in this node to store this interval */ + if (interval.getIntervalSize() > targetNode.getNodeFreeSpace()) { + /* Nope, not enough room. Insert in a new sibling instead. */ + addSiblingNode(indexOfNode); + tryInsertAtNode(interval, latestBranch.size() - 1); + return; + } + + /* Make sure the interval time range fits this node */ + if (interval.getStartTime() < targetNode.getNodeStart()) { + /* + * No, this interval starts before the startTime of this node. We + * need to check recursively in parents if it can fit. + */ + assert (indexOfNode >= 1); + tryInsertAtNode(interval, indexOfNode - 1); + return; + } + + /* + * Ok, there is room, and the interval fits in this time slot. Let's add + * it. + */ + targetNode.addInterval(interval); + + /* Update treeEnd if needed */ + if (interval.getEndTime() > this.treeEnd) { + this.treeEnd = interval.getEndTime(); + } + return; + } + + /** + * Method to add a sibling to any node in the latest branch. This will add + * children back down to the leaf level, if needed. + * + * @param indexOfNode + * The index in latestBranch where we start adding + */ + private void addSiblingNode(int indexOfNode) { + int i; + CoreNode newNode, prevNode; + long splitTime = treeEnd; + + assert (indexOfNode < latestBranch.size()); + + /* Check if we need to add a new root node */ + if (indexOfNode == 0) { + addNewRootNode(); + return; + } + + /* Check if we can indeed add a child to the target parent */ + if (latestBranch.get(indexOfNode - 1).getNbChildren() == config.maxChildren) { + /* If not, add a branch starting one level higher instead */ + addSiblingNode(indexOfNode - 1); + return; + } + + /* Split off the new branch from the old one */ + for (i = indexOfNode; i < latestBranch.size(); i++) { + latestBranch.get(i).closeThisNode(splitTime); + treeIO.writeNode(latestBranch.get(i)); + + prevNode = latestBranch.get(i - 1); + newNode = initNewCoreNode(prevNode.getSequenceNumber(), + splitTime + 1); + prevNode.linkNewChild(newNode); + + latestBranch.set(i, newNode); + } + return; + } + + /** + * Similar to the previous method, except here we rebuild a completely new + * latestBranch + */ + private void addNewRootNode() { + int i, depth; + CoreNode oldRootNode, newRootNode, newNode, prevNode; + long splitTime = this.treeEnd; + + oldRootNode = latestBranch.firstElement(); + newRootNode = initNewCoreNode(-1, config.treeStart); + + /* Tell the old root node that it isn't root anymore */ + oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); + + /* Close off the whole current latestBranch */ + for (i = 0; i < latestBranch.size(); i++) { + latestBranch.get(i).closeThisNode(splitTime); + treeIO.writeNode(latestBranch.get(i)); + } + + /* Link the new root to its first child (the previous root node) */ + newRootNode.linkNewChild(oldRootNode); + + /* Rebuild a new latestBranch */ + depth = latestBranch.size(); + latestBranch = new Vector<CoreNode>(); + latestBranch.add(newRootNode); + for (i = 1; i < depth + 1; i++) { + prevNode = latestBranch.get(i - 1); + newNode = initNewCoreNode(prevNode.getParentSequenceNumber(), + splitTime + 1); + prevNode.linkNewChild(newNode); + latestBranch.add(newNode); + } + } + + /** + * Add a new empty node to the tree. + * + * @param parentSeqNumber + * Sequence number of this node's parent + * @param startTime + * Start time of the new node + * @return The newly created node + */ + private CoreNode initNewCoreNode(int parentSeqNumber, long startTime) { + CoreNode newNode = new CoreNode(this, this.nodeCount, parentSeqNumber, + startTime); + this.nodeCount++; + + /* Update the treeEnd if needed */ + if (startTime >= this.treeEnd) { + this.treeEnd = startTime + 1; + } + return newNode; + } + + /** + * Inner method to select the next child of the current node intersecting + * the given timestamp. Useful for moving down the tree following one + * branch. + * + * @param currentNode + * @param t + * @return The child node intersecting t + */ + HTNode selectNextChild(CoreNode currentNode, long t) { + assert (currentNode.getNbChildren() > 0); + int potentialNextSeqNb = currentNode.getSequenceNumber(); + + for (int i = 0; i < currentNode.getNbChildren(); i++) { + if (t >= currentNode.getChildStart(i)) { + potentialNextSeqNb = currentNode.getChild(i); + } else { + break; + } + } + /* + * Once we exit this loop, we should have found a children to follow. If + * we didn't, there's a problem. + */ + assert (potentialNextSeqNb != currentNode.getSequenceNumber()); + + /* + * Since this code path is quite performance-critical, avoid iterating + * through the whole latestBranch array if we know for sure the next + * node has to be on disk + */ + if (currentNode.isDone()) { + return treeIO.readNodeFromDisk(potentialNextSeqNb); + } + return treeIO.readNode(potentialNextSeqNb); + } + + /** + * Helper function to get the size of the "tree header" in the tree-file The + * nodes will use this offset to know where they should be in the file. This + * should always be a multiple of 4K. + */ + static int getTreeHeaderSize() { + return 4096; + } + + long getFileSize() { + return config.stateFile.length(); + } + + /** + * @name Test/debugging functions + */ + + /* Only used for debugging, shouldn't be externalized */ + @SuppressWarnings("nls") + boolean checkNodeIntegrity(HTNode zenode) { + + HTNode otherNode; + CoreNode node; + String message = ""; //$NON-NLS-1$ + boolean ret = true; + + // FIXME /* Only testing Core Nodes for now */ + if (!(zenode instanceof CoreNode)) { + return true; + } + + node = (CoreNode) zenode; + + /* + * Test that this node's start and end times match the start of the + * first child and the end of the last child, respectively + */ + if (node.getNbChildren() > 0) { + otherNode = treeIO.readNode(node.getChild(0)); + if (node.getNodeStart() != otherNode.getNodeStart()) { + message += "Start time of node (" + node.getNodeStart() + ") " + + "does not match start time of first child " + "(" + + otherNode.getNodeStart() + "), " + "node #" + + otherNode.getSequenceNumber() + ")\n"; + ret = false; + } + if (node.isDone()) { + otherNode = treeIO.readNode(node.getLatestChild()); + if (node.getNodeEnd() != otherNode.getNodeEnd()) { + message += "End time of node (" + node.getNodeEnd() + + ") does not match end time of last child (" + + otherNode.getNodeEnd() + ", node #" + + otherNode.getSequenceNumber() + ")\n"; + ret = false; + } + } + } + + /* + * Test that the childStartTimes[] array matches the real nodes' start + * times + */ + for (int i = 0; i < node.getNbChildren(); i++) { + otherNode = treeIO.readNode(node.getChild(i)); + if (otherNode.getNodeStart() != node.getChildStart(i)) { + message += " Expected start time of child node #" + + node.getChild(i) + ": " + node.getChildStart(i) + + "\n" + " Actual start time of node #" + + otherNode.getSequenceNumber() + ": " + + otherNode.getNodeStart() + "\n"; + ret = false; + } + } + + if (!ret) { + System.out.println(""); + System.out.println("SHT: Integrity check failed for node #" + + node.getSequenceNumber() + ":"); + System.out.println(message); + } + return ret; + } + + void checkIntegrity() { + for (int i = 0; i < nodeCount; i++) { + checkNodeIntegrity(treeIO.readNode(i)); + } + } + + /* Only used for debugging, shouldn't be externalized */ + @SuppressWarnings("nls") + @Override + public String toString() { + return "Information on the current tree:\n\n" + "Blocksize: " + + config.blockSize + "\n" + "Max nb. of children per node: " + + config.maxChildren + "\n" + "Number of nodes: " + nodeCount + + "\n" + "Depth of the tree: " + latestBranch.size() + "\n" + + "Size of the treefile: " + this.getFileSize() + "\n" + + "Root node has sequence number: " + + latestBranch.firstElement().getSequenceNumber() + "\n" + + "'Latest leaf' has sequence number: " + + latestBranch.lastElement().getSequenceNumber(); + } + + private int curDepth; + + /** + * Start at currentNode and print the contents of all its children, in + * pre-order. Give the root node in parameter to visit the whole tree, and + * have a nice overview. + */ + @SuppressWarnings("nls") + private void preOrderPrint(PrintWriter writer, boolean printIntervals, + CoreNode currentNode) { + /* Only used for debugging, shouldn't be externalized */ + int i, j; + HTNode nextNode; + + writer.println(currentNode.toString()); + if (printIntervals) { + currentNode.debugPrintIntervals(writer); + } + curDepth++; + + for (i = 0; i < currentNode.getNbChildren(); i++) { + nextNode = treeIO.readNode(currentNode.getChild(i)); + assert (nextNode instanceof CoreNode); // TODO temporary + for (j = 0; j < curDepth - 1; j++) { + writer.print(" "); + } + writer.print("+-"); + preOrderPrint(writer, printIntervals, (CoreNode) nextNode); + } + curDepth--; + return; + } + + /** + * Print out the full tree for debugging purposes + * + * @param writer + * PrintWriter in which to write the output + * @param printIntervals + * Says if you want to output the full interval information + */ + void debugPrintFullTree(PrintWriter writer, boolean printIntervals) { + /* Only used for debugging, shouldn't be externalized */ + curDepth = 0; + this.preOrderPrint(writer, false, latestBranch.firstElement()); + + if (printIntervals) { + writer.println("\nDetails of intervals:"); //$NON-NLS-1$ + curDepth = 0; + this.preOrderPrint(writer, true, latestBranch.firstElement()); + } + writer.println('\n'); + } + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTreeBackend.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTreeBackend.java new file mode 100644 index 0000000000..dab8018dd1 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/HistoryTreeBackend.java @@ -0,0 +1,271 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.io.PrintWriter; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; +import org.eclipse.linuxtools.tmf.core.statesystem.helpers.IStateHistoryBackend; +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * History Tree backend for storing a state history. This is the basic version + * that runs in the same thread as the class creating it. + * + * @author alexmont + * + */ +public class HistoryTreeBackend implements IStateHistoryBackend { + + protected final HistoryTree sht; + private final HT_IO treeIO; + + /** + * Construtor for new history files. Use this when creating a new history + * from scratch. + * + * @param newStateFile + * The filename/location where to store the state history (Should + * end in .ht) + * @param blockSize + * The size of the blocks in the history file. This should be a + * multiple of 4096. + * @param maxChildren + * The maximum number of children each core node can have + * @param startTime + * The earliest time stamp that will be stored in the history + * @throws IOException + * Thrown if we can't create the file for some reason + */ + public HistoryTreeBackend(File newStateFile, int blockSize, + int maxChildren, long startTime) throws IOException { + sht = new HistoryTree(newStateFile, blockSize, maxChildren, startTime); + treeIO = sht.getTreeIO(); + } + + /** + * Construtor for new history files. Use this when creating a new history + * from scratch. This version supplies sane defaults for the configuration + * parameters. + * + * @param newStateFile + * The filename/location where to store the state history (Should + * end in .ht) + * @param startTime + * The earliest time stamp that will be stored in the history + * @throws IOException + * Thrown if we can't create the file for some reason + */ + public HistoryTreeBackend(File newStateFile, long startTime) + throws IOException { + this(newStateFile, 64 * 1024, 50, startTime); + } + + /** + * Existing history constructor. Use this to open an existing state-file. + * + * @param existingFileName Filename/location of the history we want to load + * @throws IOException If we can't read the file, if it doesn't exist or is not recognized + */ + public HistoryTreeBackend(File existingStateFile) throws IOException { + sht = new HistoryTree(existingStateFile); + treeIO = sht.getTreeIO(); + } + + @Override + public long getStartTime() { + return sht.getTreeStart(); + } + + @Override + public long getEndTime() { + return sht.getTreeEnd(); + } + + @Override + public void insertPastState(long stateStartTime, long stateEndTime, + int quark, ITmfStateValue value) throws TimeRangeException { + HTInterval interval = new HTInterval(stateStartTime, stateEndTime, + quark, (TmfStateValue) value); + + /* Start insertions at the "latest leaf" */ + sht.insertInterval(interval); + } + + @Override + public void finishedBuilding(long endTime) throws TimeRangeException { + sht.closeTree(); + } + + @Override + public FileInputStream supplyAttributeTreeReader() { + return treeIO.supplyATReader(); + } + + @Override + public File supplyAttributeTreeWriterFile() { + return treeIO.supplyATWriterFile(); + } + + @Override + public long supplyAttributeTreeWriterFilePosition() { + return treeIO.supplyATWriterFilePos(); + } + + @Override + public void doQuery(List<ITmfStateInterval> stateInfo, long t) + throws TimeRangeException { + if (!checkValidTime(t)) { + /* We can't possibly have information about this query */ + throw new TimeRangeException(); + } + + /* We start by reading the information in the root node */ + // FIXME using CoreNode for now, we'll have to redo this part to handle + // different node types + CoreNode currentNode = sht.latestBranch.firstElement(); + currentNode.writeInfoFromNode(stateInfo, t); + + /* Then we follow the branch down in the relevant children */ + while (currentNode.getNbChildren() > 0) { + currentNode = (CoreNode) sht.selectNextChild(currentNode, t); + currentNode.writeInfoFromNode(stateInfo, t); + } + + /* + * The stateInfo should now be filled with everything needed, we pass + * the control back to the State System. + */ + return; + } + + @Override + public ITmfStateInterval doSingularQuery(long t, int attributeQuark) + throws TimeRangeException { + return getRelevantInterval(t, attributeQuark); + } + + /** + * Simple check to make sure the requested timestamps are within the borders + * of this tree. + * + * @param t + * The queried timestamp + * @return True if it's within range, false if not. + */ + private boolean checkValidTime(long t) { + return (t >= sht.getTreeStart() && t <= sht.getTreeEnd()); + } + + /** + * Inner method to find the interval in the tree containing the requested + * key/timestamp pair, wherever in which node it is. + * + * @param t + * @param key + * @return The node containing the information we want + */ + private HTInterval getRelevantInterval(long t, int key) + throws TimeRangeException { + if (!checkValidTime(t)) { + throw new TimeRangeException(); + } + + // FIXME using CoreNode for now, we'll have to redo this part to handle + // different node types + CoreNode currentNode = sht.latestBranch.firstElement(); + HTInterval interval = currentNode.getRelevantInterval(key, t); + + while (interval == null && currentNode.getNbChildren() > 0) { + currentNode = (CoreNode) sht.selectNextChild(currentNode, t); + interval = currentNode.getRelevantInterval(key, t); + } + /* + * Since we should now have intervals at every attribute/timestamp + * combination, it should NOT be null here. + */ + assert (interval != null); + return interval; + } + + /** + * Return the size of the tree history file + * + * @return The current size of the history file in bytes + */ + public long getFileSize() { + return sht.getFileSize(); + } + + /** + * Return the current depth of the tree, ie the number of node levels. + * + * @return The tree depth + */ + public int getTreeDepth() { + return sht.latestBranch.size(); + } + + /** + * Return the average node usage as a percentage (between 0 and 100) + * + * @return Average node usage % + */ + public int getAverageNodeUsage() { + HTNode node; + long total = 0; + long ret; + + for (int seq = 0; seq < sht.getNodeCount(); seq++) { + node = treeIO.readNode(seq); + total += node.getNodeUsagePRC(); + } + + ret = total / sht.getNodeCount(); + assert (ret >= 0 && ret <= 100); + return (int) ret; + } + + @Override + public void debugPrint(PrintWriter writer) { + /* By default don't print out all the intervals */ + this.debugPrint(writer, false); + } + + /** + * The basic debugPrint method will print the tree structure, but not + * their contents. + * + * This method here print the contents (the intervals) as well. + * + * @param writer + * @param printIntervals + */ + public void debugPrint(PrintWriter writer, boolean printIntervals) { + /* Only used for debugging, shouldn't be externalized */ + writer.println("------------------------------"); //$NON-NLS-1$ + writer.println("State History Tree:\n"); //$NON-NLS-1$ + writer.println(sht.toString()); + writer.println("Average node utilization: " //$NON-NLS-1$ + + this.getAverageNodeUsage()); + writer.println(""); //$NON-NLS-1$ + + sht.debugPrintFullTree(writer, printIntervals); + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/ThreadedHistoryTreeBackend.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/ThreadedHistoryTreeBackend.java new file mode 100644 index 0000000000..a66cca13d5 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/backend/historytree/ThreadedHistoryTreeBackend.java @@ -0,0 +1,177 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.backend.historytree; + +import java.io.File; +import java.io.IOException; +import java.util.concurrent.ArrayBlockingQueue; +import java.util.concurrent.BlockingQueue; + +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; +import org.eclipse.linuxtools.tmf.core.statevalue.TmfStateValue; + +/** + * Variant of the HistoryTreeBackend which runs all the interval-insertion logic + * in a separate thread. + * + * @author alexmont + * + */ +public class ThreadedHistoryTreeBackend extends HistoryTreeBackend implements + Runnable { + + /* + * From superclass: + * + * protected final StateHistoryTree sht; + */ + + private BlockingQueue<HTInterval> intervalQueue; + private final Thread shtThread; + + /** + * New state history constructor + * + * Note that it usually doesn't make sense to use a Threaded HT if you're + * opening an existing state-file, but you know what you're doing... + * + * @param newStateFile + * The name of the history file that will be created. Should end + * in ".ht" + * @param blockSize + * The size of the blocks in the file + * @param maxChildren + * The maximum number of children allowed for each core node + * @param startTime + * The earliest timestamp stored in the history + * @param queueSize + * The size of the interval insertion queue. 2000 - 10000 usually + * works well + * @throws IOException + * If there was a problem opening the history file for writing + */ + public ThreadedHistoryTreeBackend(File newStateFile, int blockSize, + int maxChildren, long startTime, int queueSize) throws IOException { + super(newStateFile, blockSize, maxChildren, startTime); + + intervalQueue = new ArrayBlockingQueue<HTInterval>(queueSize); + shtThread = new Thread(this, "History Tree Thread"); //$NON-NLS-1$ + shtThread.start(); + } + + /** + * New State History constructor. This version provides default values for + * blockSize and maxChildren. + * + * @param newStateFile + * The name of the history file that will be created. Should end + * in ".ht" + * @param startTime + * The earliest timestamp stored in the history + * @param queueSize + * The size of the interval insertion queue. 2000 - 10000 usually + * works well + * @throws IOException + * If there was a problem opening the history file for writing + */ + public ThreadedHistoryTreeBackend(File newStateFile, long startTime, + int queueSize) throws IOException { + super(newStateFile, startTime); + + intervalQueue = new ArrayBlockingQueue<HTInterval>(queueSize); + shtThread = new Thread(this, "History Tree Thread"); //$NON-NLS-1$ + shtThread.start(); + } + + /* + * The Threaded version does not specify an "existing file" constructor, + * since the history is already built (and we only use the other thread + * during building). Just use a plain HistoryTreeProvider in this case. + * + * TODO but what about streaming?? + */ + + @Override + public void insertPastState(long stateStartTime, long stateEndTime, + int quark, ITmfStateValue value) throws TimeRangeException { + /* + * Here, instead of directly inserting the elements in the History Tree + * underneath, we'll put them in the Queue. They will then be taken and + * processed by the other thread executing the run() method. + */ + HTInterval interval = new HTInterval(stateStartTime, stateEndTime, + quark, (TmfStateValue) value); + try { + intervalQueue.put(interval); + } catch (InterruptedException e) { + /* We should not get interrupted here */ + System.out.println("State system got interrupted!"); //$NON-NLS-1$ + e.printStackTrace(); + } + } + + @Override + public void finishedBuilding(long endTime) throws TimeRangeException { + /* + * We need to commit everything in the History Tree and stop the + * standalone thread before returning to the StateHistorySystem. (SHS + * will then write the Attribute Tree to the file, that must not happen + * at the same time we are writing the last nodes!) + */ + + /* + * Send the "poison pill" in the queue, then wait for the HT to finish + * its closeTree() + */ + try { + intervalQueue.put(new HTInterval(-1, endTime, -1, + TmfStateValue.nullValue())); + shtThread.join(); + } catch (InterruptedException e) { + e.printStackTrace(); + } + return; + } + + @Override + public void run() { + if (intervalQueue == null) { + System.err.println("Cannot start the storage backend without its interval queue."); //$NON-NLS-1$ + return; + } + HTInterval currentInterval; + try { + currentInterval = intervalQueue.take(); + while (currentInterval.getStartTime() != -1) { + /* Send the interval to the History Tree */ + sht.insertInterval(currentInterval); + currentInterval = intervalQueue.take(); + } + assert (currentInterval.getAttribute() == -1); + /* + * We've been told we're done, let's write down everything and quit + */ + sht.closeTree(); + return; + } catch (InterruptedException e) { + /* We've been interrupted abnormally */ + System.out.println("State History Tree interrupted!"); //$NON-NLS-1$ + e.printStackTrace(); + } catch (TimeRangeException e) { + /* This also should not happen */ + e.printStackTrace(); + } + } + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/HistoryBuilder.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/HistoryBuilder.java new file mode 100644 index 0000000000..5e6a3c6db6 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/HistoryBuilder.java @@ -0,0 +1,91 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.helpers; + +import java.io.IOException; + +import org.eclipse.linuxtools.tmf.core.statesystem.StateHistorySystem; +import org.eclipse.linuxtools.tmf.core.statesystem.StateSystem; + +/** + * This is the high-level wrapper around the State History and its input and + * storage plugins. Just create the object using the constructor then .run() + * + * You can use one HistoryBuilder and it will instantiate everything underneath. + * If you need more fine-grained control you can still ignore this and + * instantiate everything manually. + * + * @author alexmont + * + */ +public class HistoryBuilder implements Runnable { + + private final IStateChangeInput sci; + private final StateSystem ss; + private final IStateHistoryBackend hb; + + private final Thread siThread; + + /** + * Instantiate a new HistoryBuilder helper. + * + * @param stateChangeInput + * The input plugin to use. This is required. + * @param backend + * The backend storage to use. Use "null" here if you want a + * state system with no history. + * @throws IOException + * Is thrown if anything went wrong (usually with the storage + * backend) + */ + public HistoryBuilder(IStateChangeInput stateChangeInput, + IStateHistoryBackend backend) throws IOException { + assert (stateChangeInput != null); + /* "backend" can be null, this implies no history */ + sci = stateChangeInput; + + if (backend == null) { + hb = null; + ss = new StateSystem(); + } else { + hb = backend; + ss = new StateHistorySystem(hb, true); + } + + sci.assignTargetStateSystem(ss); + siThread = new Thread(sci, "Input Plugin"); //$NON-NLS-1$ + } + + @Override + public void run() { + siThread.start(); + + try { + siThread.join(); + } catch (InterruptedException e) { + e.printStackTrace(); + assert (false); + } + } + + /** + * Return the StateSystem (or StateHistorySystem) object that was created by + * this builder. You will need this reference to run queries. + * + * @return The StateSystem that was generated + */ + public StateSystem getSS() { + return ss; + } + +}
\ No newline at end of file diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateChangeInput.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateChangeInput.java new file mode 100644 index 0000000000..dfd7a29534 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateChangeInput.java @@ -0,0 +1,56 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.helpers; + +import org.eclipse.linuxtools.tmf.core.statesystem.StateSystem; + +/** + * This is the interface used to define the "state change input", which is the + * main type of input that goes in the state system. + * + * Usually a state change input, also called "state provider" is the piece of + * the pipeline which converts trace events to state changes. + * + * @author alexmont + * + */ +public interface IStateChangeInput extends Runnable { + + /** + * Return the start time of this "state change input", which is normally the + * start time of the originating trace (or it can be the time of the first + * state-changing event). + * + * @return The start time + */ + public long getStartTime(); + + /** + * Assign the target state system where this SCI will insert its state + * changes. Because of dependencies issues, this can normally not be done at + * the constructor. + * + * This needs to be called before .run()! + * + * @param ss + */ + public void assignTargetStateSystem(StateSystem ss); + + /** + * Return the State System that was assigned to this SCI. + * + * @return The target state system + */ + public StateSystem getStateSystem(); + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateHistoryBackend.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateHistoryBackend.java new file mode 100644 index 0000000000..26d3263783 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statesystem/helpers/IStateHistoryBackend.java @@ -0,0 +1,149 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statesystem.helpers; + +import java.io.File; +import java.io.FileInputStream; +import java.io.PrintWriter; +import java.util.List; + +import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval; +import org.eclipse.linuxtools.tmf.core.statesystem.AttributeNotFoundException; +import org.eclipse.linuxtools.tmf.core.statesystem.TimeRangeException; +import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue; + +/** + * The main difference between StateSystem and StateHistorySystem is that SHS + * allows 'seeking' back in time to reload a Current State at a previous time. + * "How to go back in time" is defined by the implementation of the + * HistoryBackend. + * + * A StateHistorySystem contains one and only one HistoryBackend. If you want to + * use a paradigm with more than one provider (eg. more or less precision + * depending on what's asked by the user), implement one wrapper HistoryBackend + * which can then contain your 2-3 other backends underneath. + * + * @author alexmont + * + */ +public interface IStateHistoryBackend { + + /** + * Get the start time of this state history. This is usually the same as the + * start time of the originating trace. + * + * @return The start time + */ + public long getStartTime(); + + /** + * Get the current end time of the state history. It will change as the + * history is being built. + * + * @return The end time + */ + public long getEndTime(); + + /** + * Main method to insert state intervals into the history. + * + * @param stateStartTime + * The start time of the interval + * @param stateEndTime + * The end time of the interval + * @param quark + * The quark of the attribute this interval refers to + * @param value + * The StateValue represented by this interval + * @throws TimeRangeException + * If the start or end time are invalid + */ + // FIXME change to IStateInterval? + public void insertPastState(long stateStartTime, long stateEndTime, + int quark, ITmfStateValue value) throws TimeRangeException; + + /** + * Indicate to the provider that we are done building the history (so it can + * close off, stop threads, etc.) + * + * @param endTime + * The end time to assign to this state history. It could be + * farther in time than the last state inserted, for example. + * @throws TimeRangeException + * If the requested time makes no sense. + */ + public void finishedBuilding(long endTime) throws TimeRangeException; + + /** + * It is the responsibility of the backend to define where to save the + * Attribute Tree (since it's only useful to "reopen" an Attribute Tree if + * we have the matching History). + * + * This method defines where to read for the attribute tree when opening an + * already-existing history. Refer to the file format documentation. + * + * @return A FileInputStream object pointing to the correct file/location in + * the file where to read the attribute tree information. + */ + public FileInputStream supplyAttributeTreeReader(); + + // FIXME change to FOS too? + public File supplyAttributeTreeWriterFile(); + + public long supplyAttributeTreeWriterFilePosition(); + + /** + * @name Query methods + */ + + /** + * Complete "give me the state at a given time" method 'currentStateInfo' is + * an "out" parameter, that is, write to it the needed information and + * return. DO NOT 'new' currentStateInfo, it will be lost and nothing will + * be returned! + * + * @param currentStateInfo + * List of StateValues (index == quark) to fill up + * @param t + * Target timestamp of the query + */ + public void doQuery(List<ITmfStateInterval> currentStateInfo, long t) + throws TimeRangeException; + + /** + * Some providers might want to specify a different way to obtain just a + * single StateValue instead of updating the whole list. If the method to + * use is the same, then feel free to just implement this as a wrapper using + * doQuery(). + * + * @param t + * The target timestamp of the query. + * @param attributeQuark + * The single attribute for which you want the state interval + * @return The state interval matching this timestamp/attribute pair + * @throws TimeRangeException + * If the timestamp was invalid + * @throws AttributeNotFoundException + * If the quark was invalid + */ + public ITmfStateInterval doSingularQuery(long t, int attributeQuark) + throws TimeRangeException, AttributeNotFoundException; + + /** + * Debug method to print the contents of the history backend. + * + * @param writer + * The PrintWriter where to write the output + */ + public void debugPrint(PrintWriter writer); +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/ITmfStateValue.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/ITmfStateValue.java new file mode 100644 index 0000000000..d078e3af87 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/ITmfStateValue.java @@ -0,0 +1,57 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Alexandre Montplaisir - Initial API + ******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + + +/** + * This is the interface for using state values and reading their contents. + * + * @author alexmont + * + */ +public interface ITmfStateValue { + + /** + * Each implementation has to supply a "type" number. This will get written + * as-is in the History file to recognize the type, so it needs to be unique + * + * @return The unique "int8" assigned to this state value type + */ + public byte getType(); + + /** + * Only "null values" should return true here + * + * @return True if this type of SV is considered "null", false if it + * contains a real value. + */ + public boolean isNull(); + + /** + * Read the contained value as an 'int' primitive + * + * @return The integer contained in the state value + * @throws StateValueTypeException + * If the contained value cannot be read as an integer + */ + public int unboxInt() throws StateValueTypeException; + + /** + * Read the contained value as a String + * + * @return The String contained in the state value + * @throws StateValueTypeException + * If the contained value cannot be read as a String + */ + public String unboxStr() throws StateValueTypeException; +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/IntegerStateValue.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/IntegerStateValue.java new file mode 100644 index 0000000000..5b7cc65510 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/IntegerStateValue.java @@ -0,0 +1,53 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + +/** + * A state value containing a simple integer. + * + * @author alexmont + * + */ +final class IntegerStateValue extends TmfStateValue { + + private final int valueInt; + + public IntegerStateValue(int valueAsInt) { + this.valueInt = valueAsInt; + } + + @Override + public byte getType() { + return 0; + } + + @Override + public boolean isNull() { + return false; + } + + @Override + public Integer getValue() { + return valueInt; + } + + @Override + public byte[] toByteArray() { + return null; + } + + @Override + public String toString() { + return String.format("%3d", valueInt); //$NON-NLS-1$ + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/NullStateValue.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/NullStateValue.java new file mode 100644 index 0000000000..8afcce6a46 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/NullStateValue.java @@ -0,0 +1,50 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + +/** + * A state value that contains no particular value. It is sometimes needed over + * a "null" reference, since we avoid NPE's this way. + * + * It can also be read either as a String ("nullValue") or an Integer (-1). + * + * @author alexmont + * + */ +final class NullStateValue extends TmfStateValue { + + @Override + public byte getType() { + return -1; + } + + @Override + public boolean isNull() { + return true; + } + + @Override + public Object getValue() { + return null; + } + + @Override + public byte[] toByteArray() { + return null; + } + + @Override + public String toString() { + return "nullValue"; //$NON-NLS-1$ + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StateValueTypeException.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StateValueTypeException.java new file mode 100644 index 0000000000..ad010e21d6 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StateValueTypeException.java @@ -0,0 +1,33 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + +/** + * The StateValue is a wrapper around the different type of values that can be + * used and stored in the state system and history. "Unboxing" the value means + * retrieving the base type (int, String, etc.) inside it. + * + * This exception is thrown if the user tries to unbox a StateValue with an + * incorrect type (for example, tries to read a String value as an Int). + * + * @author alexmont + * + */ +public class StateValueTypeException extends Exception { + + /** + * + */ + private static final long serialVersionUID = -4548793451746144513L; + +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StringStateValue.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StringStateValue.java new file mode 100644 index 0000000000..4be757c462 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/StringStateValue.java @@ -0,0 +1,54 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + *******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + +/** + * A state value containing a variable-sized string + * + * @author alexmont + * + */ +final class StringStateValue extends TmfStateValue { + + private final String valueStr; + + public StringStateValue(String valueAsString) { + assert (valueAsString != null); + this.valueStr = valueAsString; + } + + @Override + public byte getType() { + return 1; + } + + @Override + public boolean isNull() { + return false; + } + + @Override + public String getValue() { + return valueStr; + } + + @Override + public byte[] toByteArray() { + return valueStr.getBytes(); + } + + @Override + public String toString() { + return valueStr; + } +} diff --git a/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/TmfStateValue.java b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/TmfStateValue.java new file mode 100644 index 0000000000..53a0aac033 --- /dev/null +++ b/lttng/org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/statevalue/TmfStateValue.java @@ -0,0 +1,162 @@ +/******************************************************************************* + * Copyright (c) 2012 Ericsson + * Copyright (c) 2010, 2011 École Polytechnique de Montréal + * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com> + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + ******************************************************************************/ + +package org.eclipse.linuxtools.tmf.core.statevalue; + + +/** + * This is the wrapper class that exposes the different types of 'state values' + * available to use in the State System. + * + * This also defines how these values are to be stored in the History Tree. For + * example, we can save numerical values as integers instead of arrays of + * 1-digit characters. + * + * For now the two available types are either int or String. + * + * @author alexmont + * + */ +public abstract class TmfStateValue implements ITmfStateValue { + + /** + * Retrieve directly the value object contained within. Implementing + * subclasses may limit the return type here. + * + * It's protected, since we do not want to expose this directly in the + * public API (and require all its users to manually cast to the right + * types). All accesses to the values should go through the "unbox-" + * methods. + * + * @return The underneath object assigned to this state value. + */ + protected abstract Object getValue(); + + /** + * Specify how to "serialize" this value when writing it to a file. + * Alternatively you can return "null" here if you do not need a byte-array + * indirection (the getValue will get written as-in instead of the offset in + * the file block) + */ + public abstract byte[] toByteArray(); + + @Override + public boolean equals(Object other) { + if (this == other) { + return true; + } + if (!(other instanceof TmfStateValue)) { + return false; + } + + /* If both types are different they're necessarily not equal */ + if (this.getType() != ((TmfStateValue) other).getType()) { + return false; + } + + /* + * This checks for the case where we'd compare two null values (and so + * avoid a NPE below) + */ + if (this.isNull()) { + return true; + } + + /* The two are valid and comparable, let's compare them */ + return this.getValue().equals(((TmfStateValue) other).getValue()); + } + + @Override + public int hashCode() { + if (this.isNull()) { + return 0; + } + return this.getValue().hashCode(); + } + + /** + * Return the max size that a variable-length state value can have when + * serialized. + * + * @return The maximum size in bytes + */ + public static int getStateValueMaxSize() { + return Byte.MAX_VALUE; + } + + /* + * Since all "null state values" are the same, we only need one copy in + * memory. + */ + private static TmfStateValue nullValue = new NullStateValue(); + + /** + * Return an instance of a "null" value. Only one copy exists in memory. + * + * @return A null value + */ + public final static TmfStateValue nullValue() { + return nullValue; + } + + /** + * Factory constructor for Integer state values + * + * @param intValue The integer value to contain + * @return The newly-created TmfStateValue object + */ + public static TmfStateValue newValueInt(int intValue) { + if (intValue == -1) { + return nullValue(); + } + return new IntegerStateValue(intValue); + } + + /** + * Factory constructor for String state values + * + * @param strValue The string value to contain + * @return The newly-create TmfStateValue object + */ + public static TmfStateValue newValueString(String strValue) { + if (strValue == null) { + return nullValue(); + } + return new StringStateValue(strValue); + } + + @Override + public int unboxInt() throws StateValueTypeException { + if (this.isNull()) { + /* Int value expected, return "-1" instead */ + return -1; + } + + if (this.getType() != 0) { /* 0 = int type */ + throw new StateValueTypeException(); + } + return (Integer) this.getValue(); + } + + @Override + public String unboxStr() throws StateValueTypeException { + if (this.isNull()) { + /* String value expected, return "nullValue" instead */ + return "nullValue"; //$NON-NLS-1$ + } + + if (this.getType() != 1) { /* 1 = string type */ + throw new StateValueTypeException(); + } + return (String) this.getValue(); + } +} |