From: Geneviève Bastien Date: Tue, 2 Aug 2016 13:43:08 +0000 (-0400) Subject: ss: History trees can define their own node types X-Git-Url: http://git.efficios.com/?p=deliverable%2Ftracecompass.git;a=commitdiff_plain;h=f4baf640acb2940d56ade46f42d7e5cbad0a598f ss: History trees can define their own node types This patch moves the HistoryTreeClassic to its own package and allows each history tree class to define their own HTNode types. Change-Id: I800469c12fbcaf21156ed340c94b611b59b70ea1 Signed-off-by: Geneviève Bastien Signed-off-by: Alexandre Montplaisir Reviewed-on: https://git.eclipse.org/r/78354 Reviewed-by: Hudson CI --- diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java index 49354ea7db..99a08f2156 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core.tests/stubs/org/eclipse/tracecompass/statesystem/core/tests/stubs/backend/HistoryTreeClassicStub.java @@ -20,11 +20,13 @@ import java.io.PrintWriter; import java.nio.channels.ClosedChannelException; import java.util.List; -import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.CoreNode; +import org.eclipse.tracecompass.internal.statesystem.core.Activator; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode; -import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HistoryTreeClassic; import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.IHistoryTree; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic.CoreNode; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic.HistoryTreeClassic; import com.google.common.collect.Iterables; @@ -178,6 +180,7 @@ public class HistoryTreeClassicStub extends HistoryTreeClassic { preOrderPrint(writer, printIntervals, nextNode, curDepth + 1, ts); } } catch (ClosedChannelException e) { + Activator.getDefault().logError(e.getMessage()); } break; @@ -212,8 +215,8 @@ public class HistoryTreeClassicStub extends HistoryTreeClassic { * The node to check */ private void assertNodeIntegrity(HTNode node) { - if (node instanceof CoreNode) { - assertChildrenIntegrity((CoreNode) node); + if (node instanceof ParentNode) { + assertChildrenIntegrity((ParentNode) node); } /* Check that all intervals are within the node's range */ @@ -221,7 +224,7 @@ public class HistoryTreeClassicStub extends HistoryTreeClassic { } - private void assertChildrenIntegrity(CoreNode node) { + private void assertChildrenIntegrity(ParentNode node) { try { /* * Test that this node's start and end times match the start of the diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF b/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF index 36b4ebb4f3..0404091143 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/META-INF/MANIFEST.MF @@ -15,6 +15,7 @@ Export-Package: org.eclipse.tracecompass.internal.provisional.statesystem.core.s org.eclipse.tracecompass.internal.statesystem.core;x-friends:="org.eclipse.tracecompass.statesystem.core.tests", org.eclipse.tracecompass.internal.statesystem.core.backend;x-internal:=true, org.eclipse.tracecompass.internal.statesystem.core.backend.historytree;x-friends:="org.eclipse.tracecompass.statesystem.core.tests", + org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic;x-friends:="org.eclipse.tracecompass.statesystem.core.tests", org.eclipse.tracecompass.internal.statesystem.core.statevalue;x-friends:="org.eclipse.tracecompass.statesystem.core.tests", org.eclipse.tracecompass.statesystem.core, org.eclipse.tracecompass.statesystem.core.backend, diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java deleted file mode 100644 index 480c0d925f..0000000000 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/CoreNode.java +++ /dev/null @@ -1,252 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others - * - * 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 and implementation - * Florian Wininger - Add Extension and Leaf Node - *******************************************************************************/ - -package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; - -import java.nio.ByteBuffer; -import java.util.Arrays; -import java.util.concurrent.locks.ReentrantReadWriteLock; - -/** - * 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 Alexandre Montplaisir - */ -public final 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 volatile int extension = -1; - - /** - * Lock used to gate the accesses to the children arrays. Meant to be a - * different lock from the one in {@link HTNode}. - */ - private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(false); - - /** - * Initial constructor. Use this to initialize a new EMPTY node. - * - * @param config - * Configuration of the History Tree - * @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 - */ - public CoreNode(HTConfig config, int seqNumber, int parentSeqNumber, - long start) { - super(config, seqNumber, parentSeqNumber, start); - this.nbChildren = 0; - int size = config.getMaxChildren(); - - /* - * 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[size]; - this.childStart = new long[size]; - } - - @Override - protected void readSpecificHeader(ByteBuffer buffer) { - int size = getConfig().getMaxChildren(); - - extension = buffer.getInt(); - nbChildren = buffer.getInt(); - - children = new int[size]; - for (int i = 0; i < nbChildren; i++) { - children[i] = buffer.getInt(); - } - for (int i = nbChildren; i < size; i++) { - buffer.getInt(); - } - - this.childStart = new long[size]; - for (int i = 0; i < nbChildren; i++) { - childStart[i] = buffer.getLong(); - } - for (int i = nbChildren; i < size; i++) { - buffer.getLong(); - } - } - - @Override - protected void writeSpecificHeader(ByteBuffer buffer) { - int size = getConfig().getMaxChildren(); - - buffer.putInt(extension); - buffer.putInt(nbChildren); - - /* Write the "children's seq number" array */ - for (int i = 0; i < nbChildren; i++) { - buffer.putInt(children[i]); - } - for (int i = nbChildren; i < size; i++) { - buffer.putInt(0); - } - - /* Write the "children's start times" array */ - for (int i = 0; i < nbChildren; i++) { - buffer.putLong(childStart[i]); - } - for (int i = nbChildren; i < size; i++) { - buffer.putLong(0); - } - } - - /** - * Return the number of child nodes this node has. - * - * @return The number of child nodes - */ - public int getNbChildren() { - rwl.readLock().lock(); - int ret = nbChildren; - rwl.readLock().unlock(); - return ret; - } - - /** - * Get the child node corresponding to the specified index - * - * @param index The index of the child to lookup - * @return The child node - */ - public int getChild(int index) { - rwl.readLock().lock(); - try { - return children[index]; - } finally { - rwl.readLock().unlock(); - } - } - - /** - * Get the latest (right-most) child node of this node. - * - * @return The latest child node - */ - public int getLatestChild() { - rwl.readLock().lock(); - try { - return children[nbChildren - 1]; - } finally { - rwl.readLock().unlock(); - } - } - - /** - * Get the start time of the specified child node. - * - * @param index - * The index of the child node - * @return The start time of the that child node. - */ - public long getChildStart(int index) { - rwl.readLock().lock(); - try { - return childStart[index]; - } finally { - rwl.readLock().unlock(); - } - } - - /** - * Get the start time of the latest (right-most) child node. - * - * @return The start time of the latest child - */ - public long getLatestChildStart() { - rwl.readLock().lock(); - try { - return childStart[nbChildren - 1]; - } finally { - rwl.readLock().unlock(); - } - } - - /** - * Get the sequence number of the extension to this node (if there is one). - * - * @return The sequence number of the extended node. '-1' is returned if - * there is no extension node. - */ - public int getExtensionSequenceNumber() { - return extension; - } - - /** - * Tell this node that it has a new child (Congrats!) - * - * @param childNode - * The SHTNode object of the new child - */ - public void linkNewChild(HTNode childNode) { - rwl.writeLock().lock(); - try { - assert (nbChildren < getConfig().getMaxChildren()); - - children[nbChildren] = childNode.getSequenceNumber(); - childStart[nbChildren] = childNode.getNodeStart(); - nbChildren++; - - } finally { - rwl.writeLock().unlock(); - } - } - - @Override - public NodeType getNodeType() { - return NodeType.CORE; - } - - @Override - protected int getSpecificHeaderSize() { - int maxChildren = getConfig().getMaxChildren(); - int specificSize = - Integer.BYTES /* 1x int (extension node) */ - + Integer.BYTES /* 1x int (nbChildren) */ - - /* MAX_NB * int ('children' table) */ - + Integer.BYTES * maxChildren - - /* MAX_NB * Timevalue ('childStart' table) */ - + Long.BYTES * maxChildren; - - return specificSize; - } - - @Override - public String toStringSpecific() { - /* Only used for debugging, shouldn't be externalized */ - return String.format("Core Node, %d children %s", //$NON-NLS-1$ - nbChildren, Arrays.toString(Arrays.copyOf(children, nbChildren))); - } - -} diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java index 9cb7b74572..9cada2d4f4 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java @@ -168,11 +168,13 @@ public abstract class HTNode { * @param fc * FileChannel to the history file, ALREADY SEEKED at the start * of the node. + * @param nodeFactory + * The factory to create the nodes for this tree * @return The node object * @throws IOException * If there was an error reading from the file channel */ - public static final @NonNull HTNode readNode(HTConfig config, FileChannel fc) + public static final @NonNull HTNode readNode(HTConfig config, FileChannel fc, IHistoryTree.IHTNodeFactory nodeFactory) throws IOException { HTNode newNode = null; int res, i; @@ -198,13 +200,13 @@ public abstract class HTNode { switch (type) { case CORE: /* Core nodes */ - newNode = new CoreNode(config, seqNb, parentSeqNb, start); + newNode = nodeFactory.createCoreNode(config, seqNb, parentSeqNb, start); newNode.readSpecificHeader(buffer); break; case LEAF: /* Leaf nodes */ - newNode = new LeafNode(config, seqNb, parentSeqNb, start); + newNode = nodeFactory.createLeafNode(config, seqNb, parentSeqNb, start); newNode.readSpecificHeader(buffer); break; @@ -610,8 +612,8 @@ public abstract class HTNode { writer.println("Intervals for node #" + fSequenceNumber + ":"); /* Array of children */ - if (getNodeType() == NodeType.CORE) { /* Only Core Nodes can have children */ - CoreNode thisNode = (CoreNode) this; + if (getNodeType() != NodeType.LEAF) { /* Only Core Nodes can have children */ + ParentNode thisNode = (ParentNode) this; writer.print(" " + thisNode.getNbChildren() + " children"); if (thisNode.getNbChildren() >= 1) { writer.print(": [ " + thisNode.getChild(0)); diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HT_IO.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HT_IO.java index 25f7281518..b26225b733 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HT_IO.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HT_IO.java @@ -23,12 +23,13 @@ import java.nio.channels.FileChannel; import java.util.logging.Logger; import org.eclipse.jdt.annotation.NonNull; -import org.eclipse.tracecompass.common.core.log.TraceCompassLog; import java.util.Objects; import java.util.concurrent.ExecutionException; import org.eclipse.jdt.annotation.Nullable; +import org.eclipse.tracecompass.common.core.log.TraceCompassLog; import org.eclipse.tracecompass.internal.statesystem.core.Activator; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.IHistoryTree.IHTNodeFactory; import com.google.common.cache.CacheBuilder; import com.google.common.cache.CacheLoader; @@ -100,7 +101,7 @@ public class HT_IO { synchronized (io) { io.seekFCToNodePos(io.fFileChannelIn, seqNb); - return HTNode.readNode(io.fConfig, io.fFileChannelIn); + return HTNode.readNode(io.fConfig, io.fFileChannelIn, key.fStateHistory.fNodeFactory); } } })); @@ -119,6 +120,8 @@ public class HT_IO { private final FileChannel fFileChannelIn; private final FileChannel fFileChannelOut; + private final IHTNodeFactory fNodeFactory; + // ------------------------------------------------------------------------ // Methods // ------------------------------------------------------------------------ @@ -132,11 +135,13 @@ public class HT_IO { * The configuration object for the StateHistoryTree * @param newFile * Flag indicating that the file must be created from scratch + * @param nodeFactory + * The factory to create new nodes for this tree * * @throws IOException * An exception can be thrown when file cannot be accessed */ - public HT_IO(HTConfig config, boolean newFile) throws IOException { + public HT_IO(HTConfig config, boolean newFile, IHTNodeFactory nodeFactory) throws IOException { fConfig = config; File historyTreeFile = config.getStateFile(); @@ -164,6 +169,7 @@ public class HT_IO { } fFileChannelIn = fFileInputStream.getChannel(); fFileChannelOut = fFileOutputStream.getChannel(); + fNodeFactory = nodeFactory; } /** diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java index 1f5f12a344..2aaa1e390c 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeBackend.java @@ -278,8 +278,8 @@ public class HistoryTreeBackend implements IStateHistoryBackend { while (!queue.isEmpty()) { HTNode currentNode = queue.pop(); if (currentNode.getNodeType() == HTNode.NodeType.CORE) { - /* Here we add the relevant children nodes for BFS */ - queue.addAll(getSHT().selectNextChildren((CoreNode) currentNode, t)); + /*Here we add the relevant children nodes for BFS*/ + queue.addAll(getSHT().selectNextChildren((ParentNode) currentNode, t)); } currentNode.writeInfoFromNode(stateInfo, t); } @@ -326,7 +326,7 @@ public class HistoryTreeBackend implements IStateHistoryBackend { while (interval == null && !queue.isEmpty()) { HTNode currentNode = queue.pop(); if (currentNode.getNodeType() == HTNode.NodeType.CORE) { - queue.addAll(getSHT().selectNextChildren((CoreNode) currentNode, t)); + queue.addAll(getSHT().selectNextChildren((ParentNode) currentNode, t)); } interval = currentNode.getRelevantInterval(key, t); } diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java deleted file mode 100644 index 461fbf6eb2..0000000000 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeClassic.java +++ /dev/null @@ -1,652 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others - * - * 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 and implementation - * Florian Wininger - Add Extension and Leaf Node - * Patrick Tasse - Add message to exceptions - *******************************************************************************/ - -package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; - -import java.io.File; -import java.io.FileInputStream; -import java.io.IOException; -import java.nio.ByteBuffer; -import java.nio.ByteOrder; -import java.nio.channels.ClosedChannelException; -import java.nio.channels.FileChannel; -import java.util.ArrayList; -import java.util.Collection; -import java.util.Collections; -import java.util.List; - -import org.eclipse.jdt.annotation.NonNull; -import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; -import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; - -import com.google.common.annotations.VisibleForTesting; -import com.google.common.collect.ImmutableList; - -/** - * Meta-container for the History Tree. This structure contains all the - * high-level data relevant to the tree. - * - * @author Alexandre Montplaisir - */ -public class HistoryTreeClassic implements IHistoryTree { - - /** - * The magic number for this file format. Package-private for the factory - * class. - */ - static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; - - /** File format version. Increment when breaking compatibility. */ - private static final int FILE_VERSION = 7; - - // ------------------------------------------------------------------------ - // Tree-specific configuration - // ------------------------------------------------------------------------ - - /** Container for all the configuration constants */ - private final HTConfig fConfig; - - /** Reader/writer object */ - private final @NonNull HT_IO fTreeIO; - - // ------------------------------------------------------------------------ - // Variable Fields (will change throughout the existence of the SHT) - // ------------------------------------------------------------------------ - - /** Latest timestamp found in the tree (at any given moment) */ - private long fTreeEnd; - - /** The total number of nodes that exists in this tree */ - private int fNodeCount; - - /** "Cache" to keep the active nodes in memory */ - private final @NonNull List<@NonNull HTNode> fLatestBranch; - - // ------------------------------------------------------------------------ - // Constructors/"Destructors" - // ------------------------------------------------------------------------ - - /** - * Create a new State History from scratch, using a {@link HTConfig} object - * for configuration. - * - * @param conf - * The config to use for this History Tree. - * @throws IOException - * If an error happens trying to open/write to the file - * specified in the config - */ - public HistoryTreeClassic(HTConfig conf) throws IOException { - /* - * Simple check to make sure we have enough place in the 0th block for - * the tree configuration - */ - if (conf.getBlockSize() < TREE_HEADER_SIZE) { - throw new IllegalArgumentException(); - } - - fConfig = conf; - fTreeEnd = conf.getTreeStart(); - fNodeCount = 0; - fLatestBranch = Collections.synchronizedList(new ArrayList<>()); - - /* Prepare the IO object */ - fTreeIO = new HT_IO(fConfig, true); - - /* Add the first node to the tree */ - LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart()); - fLatestBranch.add(firstNode); - } - - /** - * "Reader" constructor : instantiate a SHTree from an existing tree file on - * disk - * - * @param existingStateFile - * Path/filename of the history-file we are to open - * @param expProviderVersion - * The expected version of the state provider - * @throws IOException - * If an error happens reading the file - */ - public HistoryTreeClassic(File existingStateFile, int expProviderVersion) 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 startTime; - - /* Java I/O mumbo jumbo... */ - if (!existingStateFile.exists()) { - throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ - } - if (existingStateFile.length() <= 0) { - throw new IOException("Empty target file"); //$NON-NLS-1$ - } - - try (FileInputStream fis = new FileInputStream(existingStateFile); - FileChannel fc = fis.getChannel();) { - - ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); - buffer.order(ByteOrder.LITTLE_ENDIAN); - buffer.clear(); - - res = fc.read(buffer); - if (res != TREE_HEADER_SIZE) { - throw new IOException("Invalid header size"); //$NON-NLS-1$ - } - - 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("Wrong magic number"); //$NON-NLS-1$ - } - - res = buffer.getInt(); /* File format version number */ - if (res != FILE_VERSION) { - throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ - } - - res = buffer.getInt(); /* Event handler's version number */ - if (res != expProviderVersion && - expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) { - /* - * The existing history was built using an event handler that - * doesn't match the current one in the framework. - * - * Information could be all wrong. Instead of keeping an - * incorrect history file, a rebuild is done. - */ - throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ - } - - bs = buffer.getInt(); /* Block Size */ - maxc = buffer.getInt(); /* Max nb of children per node */ - - fNodeCount = buffer.getInt(); - rootNodeSeqNb = buffer.getInt(); - startTime = buffer.getLong(); - - fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime); - } - - /* - * 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? - */ - fTreeIO = new HT_IO(fConfig, false); - - fLatestBranch = buildLatestBranch(rootNodeSeqNb); - fTreeEnd = getRootNode().getNodeEnd(); - - /* - * Make sure the history start time we read previously is consistent - * with was is actually in the root node. - */ - if (startTime != getRootNode().getNodeStart()) { - throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$ - "history file, it might be corrupted."); //$NON-NLS-1$ - } - } - - /** - * 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 - * @throws ClosedChannelException - */ - private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { - List<@NonNull HTNode> list = new ArrayList<>(); - - HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb); - list.add(nextChildNode); - - /* Follow the last branch up to the leaf */ - while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { - nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild()); - list.add(nextChildNode); - } - return Collections.synchronizedList(list); - } - - @Override - public void closeTree(long requestedEndTime) { - /* This is an important operation, queries can wait */ - synchronized (fLatestBranch) { - /* - * Work-around the "empty branches" that get created when the root - * node becomes full. Overwrite the tree's end time with the - * original wanted end-time, to ensure no queries are sent into - * those empty nodes. - * - * This won't be needed once extended nodes are implemented. - */ - fTreeEnd = requestedEndTime; - - /* Close off the latest branch of the tree */ - for (int i = 0; i < fLatestBranch.size(); i++) { - fLatestBranch.get(i).closeThisNode(fTreeEnd); - fTreeIO.writeNode(fLatestBranch.get(i)); - } - - try (FileChannel fc = fTreeIO.getFcOut();) { - ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); - buffer.order(ByteOrder.LITTLE_ENDIAN); - buffer.clear(); - - /* Save the config of the tree to the header of the file */ - fc.position(0); - - buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); - - buffer.putInt(FILE_VERSION); - buffer.putInt(fConfig.getProviderVersion()); - - buffer.putInt(fConfig.getBlockSize()); - buffer.putInt(fConfig.getMaxChildren()); - - buffer.putInt(fNodeCount); - - /* root node seq. nb */ - buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); - - /* start time of this history */ - buffer.putLong(fLatestBranch.get(0).getNodeStart()); - - buffer.flip(); - int res = fc.write(buffer); - assert (res <= TREE_HEADER_SIZE); - /* done writing the file header */ - - } catch (IOException e) { - /* - * If we were able to write so far, there should not be any - * problem at this point... - */ - throw new RuntimeException("State system write error"); //$NON-NLS-1$ - } - } - } - - // ------------------------------------------------------------------------ - // Accessors - // ------------------------------------------------------------------------ - - @Override - public long getTreeStart() { - return fConfig.getTreeStart(); - } - - @Override - public long getTreeEnd() { - return fTreeEnd; - } - - @Override - public int getNodeCount() { - return fNodeCount; - } - - @Override - public HTNode getRootNode() { - return fLatestBranch.get(0); - } - - /** - * Return the latest branch of the tree. That branch is immutable. Used for - * unit testing and debugging. - * - * @return The immutable latest branch - */ - @VisibleForTesting - protected List<@NonNull HTNode> getLatestBranch() { - return ImmutableList.copyOf(fLatestBranch); - } - - /** - * Read a node at sequence number - * - * @param seqNum - * The sequence number of the node to read - * @return The HTNode object - * @throws ClosedChannelException - * Exception thrown when reading the node - */ - @VisibleForTesting - protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException { - // First, check in the latest branch if the node is there - for (HTNode node : fLatestBranch) { - if (node.getSequenceNumber() == seqNum) { - return node; - } - } - return fTreeIO.readNode(seqNum); - } - - /** - * Retrieve the TreeIO object. Should only be used for testing. - * - * @return The TreeIO - */ - @VisibleForTesting - protected @NonNull HT_IO getTreeIO() { - return fTreeIO; - } - - // ------------------------------------------------------------------------ - // HT_IO interface - // ------------------------------------------------------------------------ - - @Override - public FileInputStream supplyATReader() { - return fTreeIO.supplyATReader(getNodeCount()); - } - - @Override - public File supplyATWriterFile() { - return fConfig.getStateFile(); - } - - @Override - public long supplyATWriterFilePos() { - return IHistoryTree.TREE_HEADER_SIZE - + ((long) getNodeCount() * fConfig.getBlockSize()); - } - - @Override - public HTNode readNode(int seqNumber) throws ClosedChannelException { - /* Try to read the node from memory */ - synchronized (fLatestBranch) { - for (HTNode node : fLatestBranch) { - if (node.getSequenceNumber() == seqNumber) { - return node; - } - } - } - - /* Read the node from disk */ - return fTreeIO.readNode(seqNumber); - } - - @Override - public void writeNode(HTNode node) { - fTreeIO.writeNode(node); - } - - @Override - public void closeFile() { - fTreeIO.closeFile(); - } - - @Override - public void deleteFile() { - fTreeIO.deleteFile(); - } - - // ------------------------------------------------------------------------ - // Operations - // ------------------------------------------------------------------------ - - @Override - public void insertInterval(HTInterval interval) throws TimeRangeException { - if (interval.getStartTime() < fConfig.getTreeStart()) { - throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$ - } - tryInsertAtNode(interval, fLatestBranch.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 = fLatestBranch.get(indexOfNode); - - /* Verify if there is enough room in this node to store this interval */ - if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { - /* Nope, not enough room. Insert in a new sibling instead. */ - addSiblingNode(indexOfNode); - tryInsertAtNode(interval, fLatestBranch.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. - */ - 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() > fTreeEnd) { - fTreeEnd = interval.getEndTime(); - } - } - - /** - * 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) { - synchronized (fLatestBranch) { - final long splitTime = fTreeEnd; - - if (indexOfNode >= fLatestBranch.size()) { - /* - * We need to make sure (indexOfNode - 1) doesn't get the last - * node in the branch, because that one is a Leaf Node. - */ - throw new IllegalStateException(); - } - - /* 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 (((CoreNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) { - /* If not, add a branch starting one level higher instead */ - addSiblingNode(indexOfNode - 1); - return; - } - - /* Split off the new branch from the old one */ - for (int i = indexOfNode; i < fLatestBranch.size(); i++) { - fLatestBranch.get(i).closeThisNode(splitTime); - fTreeIO.writeNode(fLatestBranch.get(i)); - - CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); - HTNode newNode; - - switch (fLatestBranch.get(i).getNodeType()) { - case CORE: - newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); - break; - case LEAF: - newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); - break; - default: - throw new IllegalStateException(); - } - - prevNode.linkNewChild(newNode); - fLatestBranch.set(i, newNode); - } - } - } - - /** - * Similar to the previous method, except here we rebuild a completely new - * latestBranch - */ - private void addNewRootNode() { - final long splitTime = fTreeEnd; - - HTNode oldRootNode = fLatestBranch.get(0); - CoreNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart()); - - /* Tell the old root node that it isn't root anymore */ - oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); - - /* Close off the whole current latestBranch */ - - for (int i = 0; i < fLatestBranch.size(); i++) { - fLatestBranch.get(i).closeThisNode(splitTime); - fTreeIO.writeNode(fLatestBranch.get(i)); - } - - /* Link the new root to its first child (the previous root node) */ - newRootNode.linkNewChild(oldRootNode); - - /* Rebuild a new latestBranch */ - int depth = fLatestBranch.size(); - fLatestBranch.clear(); - fLatestBranch.add(newRootNode); - - // Create new coreNode - for (int i = 1; i < depth; i++) { - CoreNode prevNode = (CoreNode) fLatestBranch.get(i - 1); - CoreNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), - splitTime + 1); - prevNode.linkNewChild(newNode); - fLatestBranch.add(newNode); - } - - // Create the new leafNode - CoreNode prevNode = (CoreNode) fLatestBranch.get(depth - 1); - LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); - prevNode.linkNewChild(newNode); - fLatestBranch.add(newNode); - } - - /** - * Add a new empty core 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 @NonNull CoreNode initNewCoreNode(int parentSeqNumber, long startTime) { - CoreNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber, - startTime); - fNodeCount++; - return newNode; - } - - /** - * Add a new empty leaf 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 @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) { - LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber, - startTime); - fNodeCount++; - return newNode; - } - - @Override - public Collection selectNextChildren(CoreNode currentNode, long t) throws ClosedChannelException { - 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. - */ - if (potentialNextSeqNb == currentNode.getSequenceNumber()) { - throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ - } - - /* - * 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.isOnDisk()) { - return Collections.singleton(fTreeIO.readNode(potentialNextSeqNb)); - } - return Collections.singleton(readNode(potentialNextSeqNb)); - } - - @Override - public long getFileSize() { - return fConfig.getStateFile().length(); - } - - // ------------------------------------------------------------------------ - // Test/debugging methods - // ------------------------------------------------------------------------ - - /* Only used for debugging, shouldn't be externalized */ - @SuppressWarnings("nls") - @Override - public String toString() { - return "Information on the current tree:\n\n" + "Blocksize: " - + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: " - + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount - + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" - + "Size of the treefile: " + getFileSize() + "\n" - + "Root node has sequence number: " - + fLatestBranch.get(0).getSequenceNumber() + "\n" - + "'Latest leaf' has sequence number: " - + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); - } - -} diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeFactory.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeFactory.java index 61aae2307c..31d4487d97 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeFactory.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HistoryTreeFactory.java @@ -18,6 +18,7 @@ import java.nio.file.Path; import java.nio.file.StandardOpenOption; import org.eclipse.jdt.annotation.NonNullByDefault; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic.HistoryTreeClassic; /** * Class that contains factory methods to build different types of history trees diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java index f1d09a8e5e..51282c0b3a 100644 --- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/IHistoryTree.java @@ -11,6 +11,7 @@ package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree; import java.io.File; import java.io.FileInputStream; +import java.io.IOException; import java.nio.channels.ClosedChannelException; import java.util.Collection; @@ -21,9 +22,54 @@ import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; * high-level data relevant to the tree. * * @author Alexandre Montplaisir + * @author Geneviève Bastien */ public interface IHistoryTree { + /** + * Interface for history to create the various HTNodes + */ + interface IHTNodeFactory { + + /** + * Creates a new core node for the specific history tree + * + * @param config + * Configuration of the History Tree + * @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 + * @return The new core node + * @throws IOException + * any exception occurring while trying to read/create the + * node + */ + HTNode createCoreNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) throws IOException; + + /** + * Creates a new core node for the specific history tree + * + * @param config + * Configuration of the History Tree + * @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 + * @return The new core node + * @throws IOException + * any exception occurring while trying to read/create the + * node + */ + HTNode createLeafNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) throws IOException; + } + /** * 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 @@ -158,7 +204,7 @@ public interface IHistoryTree { * @throws ClosedChannelException * If the file channel was closed while we were reading the tree */ - Collection selectNextChildren(CoreNode currentNode, long t) throws ClosedChannelException; + Collection selectNextChildren(ParentNode currentNode, long t) throws ClosedChannelException; /** * Get the current size of the history file. diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java new file mode 100644 index 0000000000..34b798d6e3 --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/ParentNode.java @@ -0,0 +1,85 @@ +/******************************************************************************* + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others + * + * 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.tracecompass.internal.statesystem.core.backend.historytree; + +/** + * 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 Alexandre Montplaisir + * @author Florian Wininger + */ +public abstract class ParentNode extends HTNode { + + /** + * Initial constructor. Use this to initialize a new EMPTY node. + * + * @param config + * Configuration of the History Tree + * @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 + */ + public ParentNode(HTConfig config, int seqNumber, int parentSeqNumber, + long start) { + super(config, seqNumber, parentSeqNumber, start); + } + + /** + * Return the number of child nodes this node has. + * + * @return The number of child nodes + */ + public abstract int getNbChildren(); + + /** + * Get the child node corresponding to the specified index + * + * @param index The index of the child to lookup + * @return The child node + */ + public abstract int getChild(int index); + + /** + * Get the latest (right-most) child node of this node. + * + * @return The latest child node + */ + public abstract int getLatestChild(); + + /** + * Get the start time of the specified child node. + * + * @param index + * The index of the child node + * @return The start time of the that child node. + */ + public abstract long getChildStart(int index); + + /** + * Get the start time of the latest (right-most) child node. + * + * @return The start time of the latest child + */ + public abstract long getLatestChildStart(); + + /** + * Tell this node that it has a new child (Congrats!) + * + * @param childNode + * The SHTNode object of the new child + */ + public abstract void linkNewChild(HTNode childNode); + +} diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java new file mode 100644 index 0000000000..f70365a159 --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java @@ -0,0 +1,236 @@ +/******************************************************************************* + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others + * + * 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 and implementation + * Florian Wininger - Add Extension and Leaf Node + *******************************************************************************/ + +package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic; + +import java.nio.ByteBuffer; +import java.util.Arrays; +import java.util.concurrent.locks.ReentrantReadWriteLock; + +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode; + +/** + * 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 Alexandre Montplaisir + */ +public final class CoreNode extends ParentNode { + + /** 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 volatile int extension = -1; + + /** + * Lock used to gate the accesses to the children arrays. Meant to be a + * different lock from the one in {@link HTNode}. + */ + private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(false); + + /** + * Initial constructor. Use this to initialize a new EMPTY node. + * + * @param config + * Configuration of the History Tree + * @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 + */ + public CoreNode(HTConfig config, int seqNumber, int parentSeqNumber, + long start) { + super(config, seqNumber, parentSeqNumber, start); + this.nbChildren = 0; + int size = config.getMaxChildren(); + + /* + * 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[size]; + this.childStart = new long[size]; + } + + @Override + protected void readSpecificHeader(ByteBuffer buffer) { + int size = getConfig().getMaxChildren(); + + extension = buffer.getInt(); + nbChildren = buffer.getInt(); + + children = new int[size]; + for (int i = 0; i < nbChildren; i++) { + children[i] = buffer.getInt(); + } + for (int i = nbChildren; i < size; i++) { + buffer.getInt(); + } + + this.childStart = new long[size]; + for (int i = 0; i < nbChildren; i++) { + childStart[i] = buffer.getLong(); + } + for (int i = nbChildren; i < size; i++) { + buffer.getLong(); + } + } + + @Override + protected void writeSpecificHeader(ByteBuffer buffer) { + int size = getConfig().getMaxChildren(); + + buffer.putInt(extension); + buffer.putInt(nbChildren); + + /* Write the "children's seq number" array */ + for (int i = 0; i < nbChildren; i++) { + buffer.putInt(children[i]); + } + for (int i = nbChildren; i < size; i++) { + buffer.putInt(0); + } + + /* Write the "children's start times" array */ + for (int i = 0; i < nbChildren; i++) { + buffer.putLong(childStart[i]); + } + for (int i = nbChildren; i < size; i++) { + buffer.putLong(0); + } + } + + @Override + public int getNbChildren() { + rwl.readLock().lock(); + int ret = nbChildren; + rwl.readLock().unlock(); + return ret; + } + + @Override + public int getChild(int index) { + rwl.readLock().lock(); + try { + return children[index]; + } finally { + rwl.readLock().unlock(); + } + } + + @Override + public int getLatestChild() { + rwl.readLock().lock(); + try { + return children[nbChildren - 1]; + } finally { + rwl.readLock().unlock(); + } + } + + @Override + public long getChildStart(int index) { + rwl.readLock().lock(); + try { + return childStart[index]; + } finally { + rwl.readLock().unlock(); + } + } + + @Override + public long getLatestChildStart() { + rwl.readLock().lock(); + try { + return childStart[nbChildren - 1]; + } finally { + rwl.readLock().unlock(); + } + } + + /** + * Get the sequence number of the extension to this node (if there is one). + * + * @return The sequence number of the extended node. '-1' is returned if + * there is no extension node. + */ + public int getExtensionSequenceNumber() { + return extension; + } + + /** + * Tell this node that it has a new child (Congrats!) + * + * @param childNode + * The SHTNode object of the new child + */ + @Override + public void linkNewChild(HTNode childNode) { + rwl.writeLock().lock(); + try { + if (nbChildren >= getConfig().getMaxChildren()) { + throw new IllegalStateException("Asked to link another child but parent already has maximum number of children"); //$NON-NLS-1$ + } + + children[nbChildren] = childNode.getSequenceNumber(); + childStart[nbChildren] = childNode.getNodeStart(); + nbChildren++; + + } finally { + rwl.writeLock().unlock(); + } + } + + @Override + public NodeType getNodeType() { + return NodeType.CORE; + } + + @Override + protected int getSpecificHeaderSize() { + int maxChildren = getConfig().getMaxChildren(); + int specificSize = + Integer.BYTES /* 1x int (extension node) */ + + Integer.BYTES /* 1x int (nbChildren) */ + + /* MAX_NB * int ('children' table) */ + + Integer.BYTES * maxChildren + + /* MAX_NB * Timevalue ('childStart' table) */ + + Long.BYTES * maxChildren; + + return specificSize; + } + + @Override + public String toStringSpecific() { + /* Only used for debugging, shouldn't be externalized */ + return String.format("Core Node, %d children %s", //$NON-NLS-1$ + nbChildren, Arrays.toString(Arrays.copyOf(children, nbChildren))); + } + +} diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java new file mode 100644 index 0000000000..7f8c4d4d7c --- /dev/null +++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/HistoryTreeClassic.java @@ -0,0 +1,672 @@ +/******************************************************************************* + * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others + * + * 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 and implementation + * Florian Wininger - Add Extension and Leaf Node + * Patrick Tasse - Add message to exceptions + *******************************************************************************/ + +package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic; + +import java.io.File; +import java.io.FileInputStream; +import java.io.IOException; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.nio.channels.ClosedChannelException; +import java.nio.channels.FileChannel; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTInterval; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HT_IO; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.IHistoryTree; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.LeafNode; +import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode; +import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder; +import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.collect.ImmutableList; + +/** + * Meta-container for the History Tree. This structure contains all the + * high-level data relevant to the tree. + * + * @author Alexandre Montplaisir + */ +public class HistoryTreeClassic implements IHistoryTree { + + /** + * The magic number for this file format. + */ + public static final int HISTORY_FILE_MAGIC_NUMBER = 0x05FFA900; + + /** File format version. Increment when breaking compatibility. */ + private static final int FILE_VERSION = 7; + + private static final IHTNodeFactory CLASSIC_NODE_FACTORY = new IHTNodeFactory() { + + @Override + public HTNode createCoreNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) { + return new CoreNode(config, seqNumber, parentSeqNumber, start); + } + + @Override + public HTNode createLeafNode(HTConfig config, int seqNumber, int parentSeqNumber, long start) { + return new LeafNode(config, seqNumber, parentSeqNumber, start); + } + + }; + + // ------------------------------------------------------------------------ + // Tree-specific configuration + // ------------------------------------------------------------------------ + + /** Container for all the configuration constants */ + private final HTConfig fConfig; + + /** Reader/writer object */ + private final @NonNull HT_IO fTreeIO; + + // ------------------------------------------------------------------------ + // Variable Fields (will change throughout the existence of the SHT) + // ------------------------------------------------------------------------ + + /** Latest timestamp found in the tree (at any given moment) */ + private long fTreeEnd; + + /** The total number of nodes that exists in this tree */ + private int fNodeCount; + + /** "Cache" to keep the active nodes in memory */ + private final @NonNull List<@NonNull HTNode> fLatestBranch; + + // ------------------------------------------------------------------------ + // Constructors/"Destructors" + // ------------------------------------------------------------------------ + + /** + * Create a new State History from scratch, using a {@link HTConfig} object + * for configuration. + * + * @param conf + * The config to use for this History Tree. + * @throws IOException + * If an error happens trying to open/write to the file + * specified in the config + */ + public HistoryTreeClassic(HTConfig conf) throws IOException { + /* + * Simple check to make sure we have enough place in the 0th block for + * the tree configuration + */ + if (conf.getBlockSize() < TREE_HEADER_SIZE) { + throw new IllegalArgumentException(); + } + + fConfig = conf; + fTreeEnd = conf.getTreeStart(); + fNodeCount = 0; + fLatestBranch = Collections.synchronizedList(new ArrayList<>()); + + /* Prepare the IO object */ + fTreeIO = new HT_IO(fConfig, true, CLASSIC_NODE_FACTORY); + + /* Add the first node to the tree */ + LeafNode firstNode = initNewLeafNode(-1, conf.getTreeStart()); + fLatestBranch.add(firstNode); + } + + /** + * "Reader" constructor : instantiate a SHTree from an existing tree file on + * disk + * + * @param existingStateFile + * Path/filename of the history-file we are to open + * @param expProviderVersion + * The expected version of the state provider + * @throws IOException + * If an error happens reading the file + */ + public HistoryTreeClassic(File existingStateFile, int expProviderVersion) 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 startTime; + + /* Java I/O mumbo jumbo... */ + if (!existingStateFile.exists()) { + throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ + } + if (existingStateFile.length() <= 0) { + throw new IOException("Empty target file"); //$NON-NLS-1$ + } + + try (FileInputStream fis = new FileInputStream(existingStateFile); + FileChannel fc = fis.getChannel();) { + + ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + + res = fc.read(buffer); + if (res != TREE_HEADER_SIZE) { + throw new IOException("Invalid header size"); //$NON-NLS-1$ + } + + 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("Wrong magic number"); //$NON-NLS-1$ + } + + res = buffer.getInt(); /* File format version number */ + if (res != FILE_VERSION) { + throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ + } + + res = buffer.getInt(); /* Event handler's version number */ + if (res != expProviderVersion && + expProviderVersion != ITmfStateSystemBuilder.IGNORE_PROVIDER_VERSION) { + /* + * The existing history was built using an event handler that + * doesn't match the current one in the framework. + * + * Information could be all wrong. Instead of keeping an + * incorrect history file, a rebuild is done. + */ + throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ + } + + bs = buffer.getInt(); /* Block Size */ + maxc = buffer.getInt(); /* Max nb of children per node */ + + fNodeCount = buffer.getInt(); + rootNodeSeqNb = buffer.getInt(); + startTime = buffer.getLong(); + + fConfig = new HTConfig(existingStateFile, bs, maxc, expProviderVersion, startTime); + } + + /* + * 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? + */ + fTreeIO = new HT_IO(fConfig, false, CLASSIC_NODE_FACTORY); + + fLatestBranch = buildLatestBranch(rootNodeSeqNb); + fTreeEnd = getRootNode().getNodeEnd(); + + /* + * Make sure the history start time we read previously is consistent + * with was is actually in the root node. + */ + if (startTime != getRootNode().getNodeStart()) { + throw new IOException("Inconsistent start times in the" + //$NON-NLS-1$ + "history file, it might be corrupted."); //$NON-NLS-1$ + } + } + + /** + * 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 + * @throws ClosedChannelException + */ + private @NonNull List<@NonNull HTNode> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { + List<@NonNull HTNode> list = new ArrayList<>(); + + HTNode nextChildNode = fTreeIO.readNode(rootNodeSeqNb); + list.add(nextChildNode); + + /* Follow the last branch up to the leaf */ + while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { + nextChildNode = fTreeIO.readNode(((CoreNode) nextChildNode).getLatestChild()); + list.add(nextChildNode); + } + return Collections.synchronizedList(list); + } + + @Override + public void closeTree(long requestedEndTime) { + /* This is an important operation, queries can wait */ + synchronized (fLatestBranch) { + /* + * Work-around the "empty branches" that get created when the root + * node becomes full. Overwrite the tree's end time with the + * original wanted end-time, to ensure no queries are sent into + * those empty nodes. + * + * This won't be needed once extended nodes are implemented. + */ + fTreeEnd = requestedEndTime; + + /* Close off the latest branch of the tree */ + for (int i = 0; i < fLatestBranch.size(); i++) { + fLatestBranch.get(i).closeThisNode(fTreeEnd); + fTreeIO.writeNode(fLatestBranch.get(i)); + } + + try (FileChannel fc = fTreeIO.getFcOut();) { + ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); + buffer.order(ByteOrder.LITTLE_ENDIAN); + buffer.clear(); + + /* Save the config of the tree to the header of the file */ + fc.position(0); + + buffer.putInt(HISTORY_FILE_MAGIC_NUMBER); + + buffer.putInt(FILE_VERSION); + buffer.putInt(fConfig.getProviderVersion()); + + buffer.putInt(fConfig.getBlockSize()); + buffer.putInt(fConfig.getMaxChildren()); + + buffer.putInt(fNodeCount); + + /* root node seq. nb */ + buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); + + /* start time of this history */ + buffer.putLong(fLatestBranch.get(0).getNodeStart()); + + buffer.flip(); + int res = fc.write(buffer); + assert (res <= TREE_HEADER_SIZE); + /* done writing the file header */ + + } catch (IOException e) { + /* + * If we were able to write so far, there should not be any + * problem at this point... + */ + throw new RuntimeException("State system write error"); //$NON-NLS-1$ + } + } + } + + // ------------------------------------------------------------------------ + // Accessors + // ------------------------------------------------------------------------ + + @Override + public long getTreeStart() { + return fConfig.getTreeStart(); + } + + @Override + public long getTreeEnd() { + return fTreeEnd; + } + + @Override + public int getNodeCount() { + return fNodeCount; + } + + @Override + public HTNode getRootNode() { + return fLatestBranch.get(0); + } + + /** + * Return the latest branch of the tree. That branch is immutable. Used for + * unit testing and debugging. + * + * @return The immutable latest branch + */ + @VisibleForTesting + protected List<@NonNull HTNode> getLatestBranch() { + return ImmutableList.copyOf(fLatestBranch); + } + + /** + * Read a node at sequence number + * + * @param seqNum + * The sequence number of the node to read + * @return The HTNode object + * @throws ClosedChannelException + * Exception thrown when reading the node + */ + @VisibleForTesting + protected @NonNull HTNode getNode(int seqNum) throws ClosedChannelException { + // First, check in the latest branch if the node is there + for (HTNode node : fLatestBranch) { + if (node.getSequenceNumber() == seqNum) { + return node; + } + } + return fTreeIO.readNode(seqNum); + } + + /** + * Retrieve the TreeIO object. Should only be used for testing. + * + * @return The TreeIO + */ + @VisibleForTesting + protected @NonNull HT_IO getTreeIO() { + return fTreeIO; + } + + // ------------------------------------------------------------------------ + // HT_IO interface + // ------------------------------------------------------------------------ + + @Override + public FileInputStream supplyATReader() { + return fTreeIO.supplyATReader(getNodeCount()); + } + + @Override + public File supplyATWriterFile() { + return fConfig.getStateFile(); + } + + @Override + public long supplyATWriterFilePos() { + return IHistoryTree.TREE_HEADER_SIZE + + ((long) getNodeCount() * fConfig.getBlockSize()); + } + + @Override + public HTNode readNode(int seqNumber) throws ClosedChannelException { + /* Try to read the node from memory */ + synchronized (fLatestBranch) { + for (HTNode node : fLatestBranch) { + if (node.getSequenceNumber() == seqNumber) { + return node; + } + } + } + + /* Read the node from disk */ + return fTreeIO.readNode(seqNumber); + } + + @Override + public void writeNode(HTNode node) { + fTreeIO.writeNode(node); + } + + @Override + public void closeFile() { + fTreeIO.closeFile(); + } + + @Override + public void deleteFile() { + fTreeIO.deleteFile(); + } + + // ------------------------------------------------------------------------ + // Operations + // ------------------------------------------------------------------------ + + @Override + public void insertInterval(HTInterval interval) throws TimeRangeException { + if (interval.getStartTime() < fConfig.getTreeStart()) { + throw new TimeRangeException("Interval Start:" + interval.getStartTime() + ", Config Start:" + fConfig.getTreeStart()); //$NON-NLS-1$ //$NON-NLS-2$ + } + tryInsertAtNode(interval, fLatestBranch.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 = fLatestBranch.get(indexOfNode); + + /* Verify if there is enough room in this node to store this interval */ + if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { + /* Nope, not enough room. Insert in a new sibling instead. */ + addSiblingNode(indexOfNode); + tryInsertAtNode(interval, fLatestBranch.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. + */ + 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() > fTreeEnd) { + fTreeEnd = interval.getEndTime(); + } + } + + /** + * 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) { + synchronized (fLatestBranch) { + final long splitTime = fTreeEnd; + + if (indexOfNode >= fLatestBranch.size()) { + /* + * We need to make sure (indexOfNode - 1) doesn't get the last + * node in the branch, because that one is a Leaf Node. + */ + throw new IllegalStateException(); + } + + /* 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 (((ParentNode) fLatestBranch.get(indexOfNode - 1)).getNbChildren() == fConfig.getMaxChildren()) { + /* If not, add a branch starting one level higher instead */ + addSiblingNode(indexOfNode - 1); + return; + } + + /* Split off the new branch from the old one */ + for (int i = indexOfNode; i < fLatestBranch.size(); i++) { + fLatestBranch.get(i).closeThisNode(splitTime); + fTreeIO.writeNode(fLatestBranch.get(i)); + + ParentNode prevNode = (ParentNode) fLatestBranch.get(i - 1); + HTNode newNode; + + switch (fLatestBranch.get(i).getNodeType()) { + case CORE: + newNode = initNewCoreNode(prevNode.getSequenceNumber(), splitTime + 1); + break; + case LEAF: + newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); + break; + default: + throw new IllegalStateException(); + } + + prevNode.linkNewChild(newNode); + fLatestBranch.set(i, newNode); + } + } + } + + /** + * Similar to the previous method, except here we rebuild a completely new + * latestBranch + */ + private void addNewRootNode() { + final long splitTime = fTreeEnd; + + HTNode oldRootNode = fLatestBranch.get(0); + ParentNode newRootNode = initNewCoreNode(-1, fConfig.getTreeStart()); + + /* Tell the old root node that it isn't root anymore */ + oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); + + /* Close off the whole current latestBranch */ + + for (int i = 0; i < fLatestBranch.size(); i++) { + fLatestBranch.get(i).closeThisNode(splitTime); + fTreeIO.writeNode(fLatestBranch.get(i)); + } + + /* Link the new root to its first child (the previous root node) */ + newRootNode.linkNewChild(oldRootNode); + + /* Rebuild a new latestBranch */ + int depth = fLatestBranch.size(); + fLatestBranch.clear(); + fLatestBranch.add(newRootNode); + + // Create new coreNode + for (int i = 1; i < depth; i++) { + ParentNode prevNode = (ParentNode) fLatestBranch.get(i - 1); + ParentNode newNode = initNewCoreNode(prevNode.getSequenceNumber(), + splitTime + 1); + prevNode.linkNewChild(newNode); + fLatestBranch.add(newNode); + } + + // Create the new leafNode + ParentNode prevNode = (ParentNode) fLatestBranch.get(depth - 1); + LeafNode newNode = initNewLeafNode(prevNode.getSequenceNumber(), splitTime + 1); + prevNode.linkNewChild(newNode); + fLatestBranch.add(newNode); + } + + /** + * Add a new empty core 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 @NonNull ParentNode initNewCoreNode(int parentSeqNumber, long startTime) { + ParentNode newNode = new CoreNode(fConfig, fNodeCount, parentSeqNumber, + startTime); + fNodeCount++; + return newNode; + } + + /** + * Add a new empty leaf 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 @NonNull LeafNode initNewLeafNode(int parentSeqNumber, long startTime) { + LeafNode newNode = new LeafNode(fConfig, fNodeCount, parentSeqNumber, + startTime); + fNodeCount++; + return newNode; + } + + @Override + public Collection selectNextChildren(ParentNode currentNode, long t) throws ClosedChannelException { + 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. + */ + if (potentialNextSeqNb == currentNode.getSequenceNumber()) { + throw new IllegalStateException("No next child node found"); //$NON-NLS-1$ + } + + /* + * 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.isOnDisk()) { + return Collections.singleton(fTreeIO.readNode(potentialNextSeqNb)); + } + return Collections.singleton(readNode(potentialNextSeqNb)); + } + + @Override + public long getFileSize() { + return fConfig.getStateFile().length(); + } + + // ------------------------------------------------------------------------ + // Test/debugging methods + // ------------------------------------------------------------------------ + + /* Only used for debugging, shouldn't be externalized */ + @SuppressWarnings("nls") + @Override + public String toString() { + return "Information on the current tree:\n\n" + "Blocksize: " + + fConfig.getBlockSize() + "\n" + "Max nb. of children per node: " + + fConfig.getMaxChildren() + "\n" + "Number of nodes: " + fNodeCount + + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" + + "Size of the treefile: " + getFileSize() + "\n" + + "Root node has sequence number: " + + fLatestBranch.get(0).getSequenceNumber() + "\n" + + "'Latest leaf' has sequence number: " + + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); + } + +}