| /******************************************************************************* |
| * Copyright (c) 2012, 2016 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 2.0 which |
| * accompanies this distribution, and is available at |
| * https://www.eclipse.org/legal/epl-2.0/ |
| * |
| * SPDX-License-Identifier: EPL-2.0 |
| * |
| * Contributors: |
| * Alexandre Montplaisir - Initial API and implementation |
| * 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.channels.ClosedChannelException; |
| import java.util.ArrayDeque; |
| import java.util.Collections; |
| import java.util.Deque; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.logging.Level; |
| import java.util.logging.Logger; |
| |
| import org.eclipse.jdt.annotation.NonNull; |
| import org.eclipse.tracecompass.common.core.log.TraceCompassLog; |
| import org.eclipse.tracecompass.common.core.log.TraceCompassLogUtils; |
| import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.IntegerRangeCondition; |
| import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.TimeRangeCondition; |
| import org.eclipse.tracecompass.internal.statesystem.core.Activator; |
| import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend; |
| import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException; |
| import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException; |
| import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval; |
| |
| import com.google.common.annotations.VisibleForTesting; |
| |
| /** |
| * 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 Alexandre Montplaisir |
| */ |
| public class HistoryTreeBackend implements IStateHistoryBackend { |
| |
| private static final @NonNull Logger LOGGER = TraceCompassLog.getLogger(HistoryTreeBackend.class); |
| |
| private final @NonNull String fSsid; |
| |
| /** |
| * The history tree that sits underneath. |
| */ |
| private final @NonNull IHistoryTree fSht; |
| |
| /** Indicates if the history tree construction is done */ |
| private volatile boolean fFinishedBuilding = false; |
| |
| /** |
| * Indicates if the history tree construction is done |
| * |
| * @return if the history tree construction is done |
| */ |
| protected boolean isFinishedBuilding() { |
| return fFinishedBuilding; |
| } |
| |
| /** |
| * Sets if the history tree is finished building |
| * |
| * @param isFinishedBuilding |
| * is the history tree finished building |
| */ |
| protected void setFinishedBuilding(boolean isFinishedBuilding) { |
| fFinishedBuilding = isFinishedBuilding; |
| } |
| |
| /** |
| * Constructor for new history files. Use this when creating a new history |
| * from scratch. |
| * |
| * @param ssid |
| * The state system's ID |
| * @param newStateFile |
| * The filename/location where to store the state history (Should |
| * end in .ht) |
| * @param providerVersion |
| * Version of of the state provider. We will only try to reopen |
| * existing files if this version matches the one in the |
| * framework. |
| * @param startTime |
| * The earliest time stamp that will be stored in the history |
| * @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 |
| * @throws IOException |
| * Thrown if we can't create the file for some reason |
| */ |
| public HistoryTreeBackend(@NonNull String ssid, |
| File newStateFile, |
| int providerVersion, |
| long startTime, |
| int blockSize, |
| int maxChildren) throws IOException { |
| fSsid = ssid; |
| final HTConfig conf = new HTConfig(newStateFile, blockSize, maxChildren, |
| providerVersion, startTime); |
| fSht = initializeSHT(conf); |
| } |
| |
| /** |
| * Constructor for new history files. Use this when creating a new history |
| * from scratch. This version supplies sane defaults for the configuration |
| * parameters. |
| * |
| * @param ssid |
| * The state system's id |
| * @param newStateFile |
| * The filename/location where to store the state history (Should |
| * end in .ht) |
| * @param providerVersion |
| * Version of of the state provider. We will only try to reopen |
| * existing files if this version matches the one in the |
| * framework. |
| * @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 |
| * @since 1.0 |
| */ |
| public HistoryTreeBackend(@NonNull String ssid, File newStateFile, int providerVersion, long startTime) |
| throws IOException { |
| this(ssid, newStateFile, providerVersion, startTime, 64 * 1024, 50); |
| } |
| |
| /** |
| * Existing history constructor. Use this to open an existing state-file. |
| * |
| * @param ssid |
| * The state system's id |
| * @param existingStateFile |
| * Filename/location of the history we want to load |
| * @param providerVersion |
| * Expected version of of the state provider plugin. |
| * @throws IOException |
| * If we can't read the file, if it doesn't exist, is not |
| * recognized, or if the version of the file does not match the |
| * expected providerVersion. |
| */ |
| public HistoryTreeBackend(@NonNull String ssid, @NonNull File existingStateFile, int providerVersion) |
| throws IOException { |
| fSsid = ssid; |
| fSht = initializeSHT(existingStateFile, providerVersion); |
| fFinishedBuilding = true; |
| } |
| |
| /** |
| * New-tree initializer for the History Tree wrapped by this backend. Can be |
| * overriden to use different implementations. |
| * |
| * @param conf |
| * The HTConfig configuration object |
| * @return The new history tree |
| * @throws IOException |
| * If there was a problem during creation |
| */ |
| @VisibleForTesting |
| protected @NonNull IHistoryTree initializeSHT(@NonNull HTConfig conf) throws IOException { |
| TraceCompassLogUtils.traceObjectCreation(LOGGER, Level.FINER, this); |
| return HistoryTreeFactory.createHistoryTree(conf); |
| } |
| |
| /** |
| * Existing-tree initializer for the History Tree wrapped by this backend. |
| * Can be overriden to use different implementations. |
| * |
| * @param existingStateFile |
| * The file to open |
| * @param providerVersion |
| * The expected state provider version |
| * @return The history tree opened from the given file |
| * @throws IOException |
| * If there was a problem during creation |
| */ |
| @VisibleForTesting |
| protected @NonNull IHistoryTree initializeSHT(@NonNull File existingStateFile, int providerVersion) throws IOException { |
| return HistoryTreeFactory.createFromFile(existingStateFile.toPath(), providerVersion); |
| } |
| |
| /** |
| * Get the History Tree built by this backend. |
| * |
| * Note: Do not override this method. If you want to extend the class to use |
| * a different History Tree implementation, override both variants of |
| * {@link #initializeSHT} instead. |
| * |
| * @return The history tree |
| */ |
| protected final @NonNull IHistoryTree getSHT() { |
| return fSht; |
| } |
| |
| @Override |
| public String getSSID() { |
| return fSsid; |
| } |
| |
| @Override |
| public long getStartTime() { |
| return getSHT().getTreeStart(); |
| } |
| |
| @Override |
| public long getEndTime() { |
| return getSHT().getTreeEnd(); |
| } |
| |
| @Override |
| public void insertPastState(long stateStartTime, long stateEndTime, |
| int quark, Object value) throws TimeRangeException { |
| HTInterval interval = new HTInterval(stateStartTime, stateEndTime, |
| quark, value); |
| |
| /* Start insertions at the "latest leaf" */ |
| getSHT().insertInterval(interval); |
| } |
| |
| @Override |
| public void finishedBuilding(long endTime) { |
| getSHT().closeTree(endTime); |
| fFinishedBuilding = true; |
| } |
| |
| @Override |
| public FileInputStream supplyAttributeTreeReader() { |
| return getSHT().supplyATReader(); |
| } |
| |
| @Override |
| public File supplyAttributeTreeWriterFile() { |
| return getSHT().supplyATWriterFile(); |
| } |
| |
| @Override |
| public long supplyAttributeTreeWriterFilePosition() { |
| return getSHT().supplyATWriterFilePos(); |
| } |
| |
| @Override |
| public void removeFiles() { |
| getSHT().deleteFile(); |
| } |
| |
| @Override |
| public void dispose() { |
| if (fFinishedBuilding) { |
| TraceCompassLogUtils.traceInstant(LOGGER, Level.FINE, "HistoryTreeBackend:ClosingFile", "size", getSHT().getFileSize()); //$NON-NLS-1$ //$NON-NLS-2$ |
| TraceCompassLogUtils.traceObjectDestruction(LOGGER, Level.FINER, this); |
| getSHT().closeFile(); |
| } else { |
| /* |
| * The build is being interrupted, delete the file we partially |
| * built since it won't be complete, so shouldn't be re-used in the |
| * future (.deleteFile() will close the file first) |
| */ |
| getSHT().deleteFile(); |
| } |
| } |
| |
| @Override |
| public void doQuery(List<ITmfStateInterval> stateInfo, long t) |
| throws TimeRangeException, StateSystemDisposedException { |
| checkValidTime(t); |
| |
| /* Queue is a stack of nodes containing nodes intersecting t */ |
| Deque<Integer> queue = new ArrayDeque<>(); |
| |
| /* We start by reading the information in the root node */ |
| queue.add(getSHT().getRootNode().getSequenceNumber()); |
| |
| /* Then we follow the down in the relevant children */ |
| try { |
| while (!queue.isEmpty()) { |
| int sequenceNumber = queue.pop(); |
| HTNode currentNode = getSHT().readNode(sequenceNumber); |
| if (currentNode.getNodeType() == HTNode.NodeType.CORE) { |
| /* Here we add the relevant children nodes for BFS */ |
| queue.addAll(((ParentNode) currentNode).selectNextChildren(t)); |
| } |
| currentNode.writeInfoFromNode(stateInfo, t); |
| } |
| } catch (ClosedChannelException e) { |
| throw new StateSystemDisposedException(e); |
| } |
| |
| /* |
| * The stateInfo should now be filled with everything needed, we pass |
| * the control back to the State System. |
| */ |
| } |
| |
| @Override |
| public ITmfStateInterval doSingularQuery(long t, int attributeQuark) |
| throws TimeRangeException, StateSystemDisposedException { |
| try { |
| return getRelevantInterval(t, attributeQuark); |
| } catch (ClosedChannelException e) { |
| throw new StateSystemDisposedException(e); |
| } |
| } |
| |
| private void checkValidTime(long t) { |
| long startTime = getStartTime(); |
| long endTime = getEndTime(); |
| if (t < startTime || t > endTime) { |
| throw new TimeRangeException(String.format("%s Time:%d, Start:%d, End:%d", //$NON-NLS-1$ |
| fSsid, t, startTime, endTime)); |
| } |
| } |
| |
| /** |
| * Inner method to find the interval in the tree containing the requested |
| * key/timestamp pair, wherever in which node it is. |
| */ |
| private HTInterval getRelevantInterval(long t, int key) |
| throws TimeRangeException, ClosedChannelException { |
| checkValidTime(t); |
| |
| Deque<Integer> queue = new ArrayDeque<>(); |
| queue.add(getSHT().getRootNode().getSequenceNumber()); |
| HTInterval interval = null; |
| while (interval == null && !queue.isEmpty()) { |
| int sequenceNumber = queue.pop(); |
| HTNode currentNode = getSHT().readNode(sequenceNumber); |
| if (currentNode.getNodeType() == HTNode.NodeType.CORE) { |
| /* Here we add the relevant children nodes for BFS */ |
| queue.addAll(((ParentNode) currentNode).selectNextChildren(t, key)); |
| } |
| interval = currentNode.getRelevantInterval(key, t); |
| } |
| return interval; |
| } |
| |
| @Override |
| public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, TimeRangeCondition times) { |
| return query2D(quarks, times, false); |
| } |
| |
| @Override |
| public Iterable<@NonNull ITmfStateInterval> query2D(IntegerRangeCondition quarks, TimeRangeCondition times, boolean reverse) { |
| try (TraceCompassLogUtils.FlowScopeLog log = new TraceCompassLogUtils.FlowScopeLogBuilder(LOGGER, Level.FINER, |
| "HistoryTreeBackend:query2D:init", //$NON-NLS-1$ |
| "ssid", getSSID(), //$NON-NLS-1$ |
| "quarks", quarks, //$NON-NLS-1$ |
| "timeCondition", times).build()) { //$NON-NLS-1$ |
| return () -> new Iterator<@NonNull ITmfStateInterval>() { |
| private final Deque<Integer> seqNumberQueue = new ArrayDeque<>(Collections.singleton(getSHT().getRootNode().getSequenceNumber())); |
| private Iterator<@NonNull HTInterval> intervalQueue = Collections.emptyIterator(); |
| |
| @Override |
| public boolean hasNext() { |
| while (!intervalQueue.hasNext() && !seqNumberQueue.isEmpty()) { |
| try { |
| HTNode currentNode = getSHT().readNode(seqNumberQueue); |
| /* |
| * Compute reduced conditions here to reduce complexity in queuing operations. |
| */ |
| TimeRangeCondition subTimes = times.subCondition(currentNode.getNodeStart(), currentNode.getNodeEnd()); |
| /* |
| * During the SHT construction, the bounds of the children are not final, so we |
| * may have queued some nodes which don't overlap the query. |
| */ |
| if (quarks.intersects(currentNode.getMinQuark(), currentNode.getMaxQuark()) && subTimes != null) { |
| if (currentNode.getNodeType() == HTNode.NodeType.CORE) { |
| // Queue the relevant children nodes for BFS. |
| ((ParentNode) currentNode).queueNextChildren2D(quarks, subTimes, seqNumberQueue, reverse); |
| } |
| intervalQueue = currentNode.iterable2D(quarks, subTimes).iterator(); |
| } |
| } catch (ClosedChannelException e) { |
| try (TraceCompassLogUtils.FlowScopeLog closedChannelLog = new TraceCompassLogUtils.FlowScopeLogBuilder(LOGGER, Level.FINER, |
| "HistoryTreeBackend:query2D:channelClosed").setParentScope(log).build()) { //$NON-NLS-1$ |
| return false; |
| } |
| } |
| } |
| boolean hasNext = intervalQueue.hasNext(); |
| if (!hasNext) { |
| try (TraceCompassLogUtils.FlowScopeLog noNext = new TraceCompassLogUtils.FlowScopeLogBuilder(LOGGER, Level.FINER, |
| "HistoryTreeBackend:query2D:iteratorEnd").setParentScope(log).build()) { //$NON-NLS-1$ |
| } |
| } |
| return intervalQueue.hasNext(); |
| } |
| |
| @Override |
| public ITmfStateInterval next() { |
| return intervalQueue.next(); |
| } |
| }; |
| } |
| } |
| |
| /** |
| * Return the size of the tree history file |
| * |
| * @return The current size of the history file in bytes |
| */ |
| public long getFileSize() { |
| return getSHT().getFileSize(); |
| } |
| |
| /** |
| * 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; |
| |
| try { |
| for (int seq = 0; seq < getSHT().getNodeCount(); seq++) { |
| node = getSHT().readNode(seq); |
| total += node.getNodeUsagePercent(); |
| } |
| } catch (ClosedChannelException e) { |
| Activator.getDefault().logError(e.getMessage(), e); |
| } |
| |
| ret = total / getSHT().getNodeCount(); |
| /* The return value should be a percentage */ |
| if (ret < 0 || ret > 100) { |
| throw new IllegalStateException("Average node usage is not a percentage: " + ret); //$NON-NLS-1$ |
| } |
| return (int) ret; |
| } |
| |
| } |
