statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012, 2016 Ericsson
   3  * Copyright (c) 2010, 2011 École Polytechnique de Montréal
   4  * Copyright (c) 2010, 2011 Alexandre Montplaisir <alexandre.montplaisir@gmail.com>
   5  *
   6  * All rights reserved. This program and the accompanying materials are
   7  * made available under the terms of the Eclipse Public License v1.0 which
   8  * accompanies this distribution, and is available at
   9  * http://www.eclipse.org/legal/epl-v10.html
  10  *
  11  * Contributors:
  12  *   Alexandre Montplaisir - Initial API and implementation
  13  *   Patrick Tasse - Add message to exceptions
  14  *******************************************************************************/
  15
  16 package org.eclipse.tracecompass.internal.statesystem.core;
  17
  18 import java.io.File;
  19 import java.io.IOException;
  20 import java.util.ArrayList;
  21 import java.util.Arrays;
  22 import java.util.LinkedList;
  23 import java.util.List;
  24 import java.util.concurrent.CountDownLatch;
  25 import java.util.concurrent.TimeUnit;
  26 import java.util.logging.Logger;
  27
  28 import org.eclipse.jdt.annotation.NonNull;
  29 import org.eclipse.jdt.annotation.Nullable;
  30 import org.eclipse.tracecompass.common.core.log.TraceCompassLog;
  31 import org.eclipse.tracecompass.statesystem.core.ITmfStateSystemBuilder;
  32 import org.eclipse.tracecompass.statesystem.core.backend.IStateHistoryBackend;
  33 import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
  34 import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException;
  35 import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException;
  36 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  37 import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
  38 import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue;
  39 import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue.Type;
  40 import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
  41
  42 import com.google.common.collect.ImmutableCollection.Builder;
  43 import com.google.common.collect.ImmutableSet;
  44
  45 /**
  46  * This is the core class of the Generic State System. It contains all the
  47  * methods to build and query a state history. It's exposed externally through
  48  * the IStateSystemQuerier and IStateSystemBuilder interfaces, depending if the
  49  * user needs read-only access or read-write access.
  50  *
  51  * When building, DON'T FORGET to call .closeHistory() when you are done
  52  * inserting intervals, or the storage backend will have no way of knowing it
  53  * can close and write itself to disk, and its thread will keep running.
  54  *
  55  * @author alexmont
  56  *
  57  */
  58 public class StateSystem implements ITmfStateSystemBuilder {
  59
  60     private static final String PARENT = ".."; //$NON-NLS-1$
  61     private static final String WILDCARD = "*"; //$NON-NLS-1$
  62
  63     private static final Logger LOGGER = TraceCompassLog.getLogger(StateSystem.class);
  64
  65     /* References to the inner structures */
  66     private final AttributeTree attributeTree;
  67     private final TransientState transState;
  68     private final IStateHistoryBackend backend;
  69
  70     /* Latch tracking if the state history is done building or not */
  71     private final CountDownLatch finishedLatch = new CountDownLatch(1);
  72
  73     private boolean buildCancelled = false;
  74     private boolean isDisposed = false;
  75
  76     /**
  77      * New-file constructor. For when you build a state system with a new file,
  78      * or if the back-end does not require a file on disk.
  79      *
  80      * @param backend
  81      *            Back-end plugin to use
  82      */
  83     public StateSystem(@NonNull IStateHistoryBackend backend) {
  84         this.backend = backend;
  85         this.transState = new TransientState(backend);
  86         this.attributeTree = new AttributeTree(this);
  87     }
  88
  89     /**
  90      * General constructor
  91      *
  92      * @param backend
  93      *            The "state history storage" back-end to use.
  94      * @param newFile
  95      *            Put true if this is a new history started from scratch. It is
  96      *            used to tell the state system where to get its attribute tree.
  97      * @throws IOException
  98      *             If there was a problem creating the new history file
  99      */
 100     public StateSystem(@NonNull IStateHistoryBackend backend, boolean newFile)
 101             throws IOException {
 102         this.backend = backend;
 103         this.transState = new TransientState(backend);
 104
 105         if (newFile) {
 106             attributeTree = new AttributeTree(this);
 107         } else {
 108             /* We're opening an existing file */
 109             this.attributeTree = new AttributeTree(this, backend.supplyAttributeTreeReader());
 110             transState.setInactive();
 111             finishedLatch.countDown(); /* The history is already built */
 112         }
 113     }
 114
 115     @Override
 116     public String getSSID() {
 117         return backend.getSSID();
 118     }
 119
 120     @Override
 121     public boolean isCancelled() {
 122         return buildCancelled;
 123     }
 124
 125     @Override
 126     public void waitUntilBuilt() {
 127         try {
 128             finishedLatch.await();
 129         } catch (InterruptedException e) {
 130             e.printStackTrace();
 131         }
 132     }
 133
 134     @Override
 135     public boolean waitUntilBuilt(long timeout) {
 136         boolean ret = false;
 137         try {
 138             ret = finishedLatch.await(timeout, TimeUnit.MILLISECONDS);
 139         } catch (InterruptedException e) {
 140             e.printStackTrace();
 141         }
 142         return ret;
 143     }
 144
 145     @Override
 146     public synchronized void dispose() {
 147         isDisposed = true;
 148         if (transState.isActive()) {
 149             transState.setInactive();
 150             buildCancelled = true;
 151         }
 152         backend.dispose();
 153     }
 154
 155     //--------------------------------------------------------------------------
 156     //        General methods related to the attribute tree
 157     //--------------------------------------------------------------------------
 158
 159     /**
 160      * Get the attribute tree associated with this state system. This should be
 161      * the only way of accessing it (and if subclasses want to point to a
 162      * different attribute tree than their own, they should only need to
 163      * override this).
 164      *
 165      * @return The attribute tree
 166      */
 167     public AttributeTree getAttributeTree() {
 168         return attributeTree;
 169     }
 170
 171     /**
 172      * Method used by the attribute tree when creating new attributes, to keep
 173      * the attribute count in the transient state in sync.
 174      */
 175     public void addEmptyAttribute() {
 176         transState.addEmptyEntry();
 177     }
 178
 179     @Override
 180     public int getNbAttributes() {
 181         return getAttributeTree().getNbAttributes();
 182     }
 183
 184     @Override
 185     public String getAttributeName(int attributeQuark) {
 186         return getAttributeTree().getAttributeName(attributeQuark);
 187     }
 188
 189     @Override
 190     public String getFullAttributePath(int attributeQuark) {
 191         return getAttributeTree().getFullAttributeName(attributeQuark);
 192     }
 193
 194     @Override
 195     public String[] getFullAttributePathArray(int attributeQuark) {
 196         return getAttributeTree().getFullAttributePathArray(attributeQuark);
 197     }
 198
 199     //--------------------------------------------------------------------------
 200     //        Methods related to the storage backend
 201     //--------------------------------------------------------------------------
 202
 203     @Override
 204     public long getStartTime() {
 205         return backend.getStartTime();
 206     }
 207
 208     @Override
 209     public long getCurrentEndTime() {
 210         return backend.getEndTime();
 211     }
 212
 213     @Override
 214     public void closeHistory(long endTime) throws TimeRangeException {
 215         File attributeTreeFile;
 216         long attributeTreeFilePos;
 217         long realEndTime = endTime;
 218
 219         if (realEndTime < backend.getEndTime()) {
 220             /*
 221              * This can happen (empty nodes pushing the border further, etc.)
 222              * but shouldn't be too big of a deal.
 223              */
 224             realEndTime = backend.getEndTime();
 225         }
 226         transState.closeTransientState(realEndTime);
 227         backend.finishedBuilding(realEndTime);
 228
 229         attributeTreeFile = backend.supplyAttributeTreeWriterFile();
 230         attributeTreeFilePos = backend.supplyAttributeTreeWriterFilePosition();
 231         if (attributeTreeFile != null) {
 232             /*
 233              * If null was returned, we simply won't save the attribute tree,
 234              * too bad!
 235              */
 236             getAttributeTree().writeSelf(attributeTreeFile, attributeTreeFilePos);
 237         }
 238         finishedLatch.countDown(); /* Mark the history as finished building */
 239     }
 240
 241     //--------------------------------------------------------------------------
 242     //        Quark-retrieving methods
 243     //--------------------------------------------------------------------------
 244
 245     @Override
 246     public int getQuarkAbsolute(String... attribute)
 247             throws AttributeNotFoundException {
 248         int quark = getAttributeTree().getQuarkDontAdd(ROOT_ATTRIBUTE, attribute);
 249         if (quark == INVALID_ATTRIBUTE) {
 250             throw new AttributeNotFoundException(getSSID() + " Path:" + Arrays.toString(attribute)); //$NON-NLS-1$
 251         }
 252         return quark;
 253     }
 254
 255     @Override
 256     public int optQuarkAbsolute(String... attribute) {
 257         return getAttributeTree().getQuarkDontAdd(ROOT_ATTRIBUTE, attribute);
 258     }
 259
 260     @Override
 261     public int getQuarkAbsoluteAndAdd(String... attribute) {
 262         return getAttributeTree().getQuarkAndAdd(ROOT_ATTRIBUTE, attribute);
 263     }
 264
 265     @Override
 266     public int getQuarkRelative(int startingNodeQuark, String... subPath)
 267             throws AttributeNotFoundException {
 268         int quark = getAttributeTree().getQuarkDontAdd(startingNodeQuark, subPath);
 269         if (quark == INVALID_ATTRIBUTE) {
 270             throw new AttributeNotFoundException(getSSID() + " Quark:" + startingNodeQuark + ", SubPath:" + Arrays.toString(subPath)); //$NON-NLS-1$ //$NON-NLS-2$
 271         }
 272         return quark;
 273     }
 274
 275     @Override
 276     public int optQuarkRelative(int startingNodeQuark, String... subPath) {
 277         return getAttributeTree().getQuarkDontAdd(startingNodeQuark, subPath);
 278     }
 279
 280     @Override
 281     public int getQuarkRelativeAndAdd(int startingNodeQuark, String... subPath) {
 282         return getAttributeTree().getQuarkAndAdd(startingNodeQuark, subPath);
 283     }
 284
 285     @Override
 286     public List<@NonNull Integer> getSubAttributes(int quark, boolean recursive) {
 287         return getAttributeTree().getSubAttributes(quark, recursive);
 288     }
 289
 290     @Override
 291     public List<@NonNull Integer> getSubAttributes(int quark, boolean recursive, String pattern) {
 292         List<Integer> all = getSubAttributes(quark, recursive);
 293         List<@NonNull Integer> ret = new LinkedList<>();
 294         for (Integer attQuark : all) {
 295             String name = getAttributeName(attQuark.intValue());
 296             if (name.matches(pattern)) {
 297                 ret.add(attQuark);
 298             }
 299         }
 300         return ret;
 301     }
 302
 303     @Override
 304     public int getParentAttributeQuark(int quark) {
 305         return getAttributeTree().getParentAttributeQuark(quark);
 306     }
 307
 308     @Override
 309     public List<@NonNull Integer> getQuarks(String... pattern) {
 310         return getQuarks(ROOT_ATTRIBUTE, pattern);
 311     }
 312
 313     @Override
 314     public List<@NonNull Integer> getQuarks(int startingNodeQuark, String... pattern) {
 315         Builder<@NonNull Integer> builder = ImmutableSet.builder();
 316         if (pattern.length > 0) {
 317             getQuarks(builder, startingNodeQuark, Arrays.asList(pattern));
 318         } else {
 319             builder.add(startingNodeQuark);
 320         }
 321         return builder.build().asList();
 322     }
 323
 324     private void getQuarks(Builder<@NonNull Integer> builder, int quark, List<String> pattern) {
 325         String element = pattern.get(0);
 326         if (element == null) {
 327             return;
 328         }
 329         List<String> remainder = pattern.subList(1, pattern.size());
 330         if (remainder.isEmpty()) {
 331             if (element.equals(WILDCARD)) {
 332                 builder.addAll(getSubAttributes(quark, false));
 333             } else if (element.equals(PARENT)){
 334                 builder.add(getParentAttributeQuark(quark));
 335             } else {
 336                 int subQuark = optQuarkRelative(quark, element);
 337                 if (subQuark != INVALID_ATTRIBUTE) {
 338                     builder.add(subQuark);
 339                 }
 340             }
 341         } else {
 342             if (element.equals(WILDCARD)) {
 343                 for (@NonNull Integer subquark : getSubAttributes(quark, false)) {
 344                     getQuarks(builder, subquark, remainder);
 345                 }
 346             } else if (element.equals(PARENT)){
 347                 getQuarks(builder, getParentAttributeQuark(quark), remainder);
 348             } else {
 349                 int subQuark = optQuarkRelative(quark, element);
 350                 if (subQuark != INVALID_ATTRIBUTE) {
 351                     getQuarks(builder, subQuark, remainder);
 352                 }
 353             }
 354         }
 355     }
 356
 357     //--------------------------------------------------------------------------
 358     //        Methods related to insertions in the history
 359     //--------------------------------------------------------------------------
 360
 361     @Override
 362     public void modifyAttribute(long t, @NonNull ITmfStateValue value, int attributeQuark)
 363             throws TimeRangeException, StateValueTypeException {
 364         transState.processStateChange(t, value, attributeQuark);
 365     }
 366
 367     @Deprecated
 368     @Override
 369     public void incrementAttribute(long t, int attributeQuark)
 370             throws StateValueTypeException, TimeRangeException {
 371         ITmfStateValue stateValue = queryOngoingState(attributeQuark);
 372         int prevValue = 0;
 373         /* if the attribute was previously null, start counting at 0 */
 374         if (!stateValue.isNull()) {
 375             prevValue = stateValue.unboxInt();
 376         }
 377         modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1),
 378                 attributeQuark);
 379     }
 380
 381     @Override
 382     public void pushAttribute(long t, @NonNull ITmfStateValue value, int attributeQuark)
 383             throws TimeRangeException, StateValueTypeException {
 384         int stackDepth;
 385         int subAttributeQuark;
 386         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 387
 388         if (previousSV.isNull()) {
 389             /*
 390              * If the StateValue was null, this means this is the first time we
 391              * use this attribute. Leave stackDepth at 0.
 392              */
 393             stackDepth = 0;
 394         } else if (previousSV.getType() == Type.INTEGER) {
 395             /* Previous value was an integer, all is good, use it */
 396             stackDepth = previousSV.unboxInt();
 397         } else {
 398             /* Previous state of this attribute was another type? Not good! */
 399             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getType() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 400         }
 401
 402         if (stackDepth >= 100000) {
 403             /*
 404              * Limit stackDepth to 100000, to avoid having Attribute Trees grow
 405              * out of control due to buggy insertions
 406              */
 407             String message = " Stack limit reached, not pushing"; //$NON-NLS-1$
 408             throw new IllegalStateException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
 409         }
 410
 411         stackDepth++;
 412         subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, String.valueOf(stackDepth));
 413
 414         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), attributeQuark);
 415         modifyAttribute(t, value, subAttributeQuark);
 416     }
 417
 418     @Override
 419     public ITmfStateValue popAttribute(long t, int attributeQuark)
 420             throws TimeRangeException, StateValueTypeException {
 421         /* These are the state values of the stack-attribute itself */
 422         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 423
 424         if (previousSV.isNull()) {
 425             /*
 426              * Trying to pop an empty stack. This often happens at the start of
 427              * traces, for example when we see a syscall_exit, without having
 428              * the corresponding syscall_entry in the trace. Just ignore
 429              * silently.
 430              */
 431             return null;
 432         }
 433         if (previousSV.getType() != Type.INTEGER) {
 434             /*
 435              * The existing value was not an integer (which is expected for
 436              * stack tops), this doesn't look like a valid stack attribute.
 437              */
 438             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getType() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 439         }
 440
 441         int stackDepth = previousSV.unboxInt();
 442
 443         if (stackDepth <= 0) {
 444             /* This on the other hand should not happen... */
 445             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Stack depth:" + stackDepth);  //$NON-NLS-1$//$NON-NLS-2$
 446         }
 447
 448         /* The attribute should already exist at this point */
 449         int subAttributeQuark;
 450         try {
 451             subAttributeQuark = getQuarkRelative(attributeQuark, String.valueOf(stackDepth));
 452         } catch (AttributeNotFoundException e) {
 453             String message = " Stack attribute missing sub-attribute for depth:" + stackDepth; //$NON-NLS-1$
 454             throw new IllegalStateException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
 455         }
 456         ITmfStateValue poppedValue = queryOngoingState(subAttributeQuark);
 457
 458         /* Update the state value of the stack-attribute */
 459         ITmfStateValue nextSV;
 460         if (--stackDepth == 0) {
 461             /* Store a null state value */
 462             nextSV = TmfStateValue.nullValue();
 463         } else {
 464             nextSV = TmfStateValue.newValueInt(stackDepth);
 465         }
 466         modifyAttribute(t, nextSV, attributeQuark);
 467
 468         /* Delete the sub-attribute that contained the user's state value */
 469         removeAttribute(t, subAttributeQuark);
 470
 471         return poppedValue;
 472     }
 473
 474     @Override
 475     public void removeAttribute(long t, int attributeQuark)
 476             throws TimeRangeException {
 477         /*
 478          * Nullify our children first, recursively. We pass 'false' because we
 479          * handle the recursion ourselves.
 480          */
 481         List<Integer> childAttributes = getSubAttributes(attributeQuark, false);
 482         for (int childNodeQuark : childAttributes) {
 483             if (attributeQuark == childNodeQuark) {
 484                 /* Something went very wrong when building out attribute tree */
 485                 throw new IllegalStateException();
 486             }
 487             removeAttribute(t, childNodeQuark);
 488         }
 489         /* Nullify ourselves */
 490         try {
 491             transState.processStateChange(t, TmfStateValue.nullValue(), attributeQuark);
 492         } catch (StateValueTypeException e) {
 493             /*
 494              * Will not happen since we're inserting null values only, but poor
 495              * compiler has no way of knowing this...
 496              */
 497             throw new IllegalStateException(e);
 498         }
 499     }
 500
 501     //--------------------------------------------------------------------------
 502     //        "Current" query/update methods
 503     //--------------------------------------------------------------------------
 504
 505     @Override
 506     public ITmfStateValue queryOngoingState(int attributeQuark) {
 507         return transState.getOngoingStateValue(attributeQuark);
 508     }
 509
 510     @Override
 511     public long getOngoingStartTime(int attribute) {
 512         return transState.getOngoingStartTime(attribute);
 513     }
 514
 515     @Override
 516     public void updateOngoingState(ITmfStateValue newValue, int attributeQuark) {
 517         transState.changeOngoingStateValue(attributeQuark, newValue);
 518     }
 519
 520     /**
 521      * Modify the whole "ongoing state" (state values + start times). This can
 522      * be used when "seeking" a state system to a different point in the trace
 523      * (and restoring the known stateInfo at this location). Use with care!
 524      *
 525      * @param newStateIntervals
 526      *            The new List of state values to use as ongoing state info
 527      */
 528     protected void replaceOngoingState(@NonNull List<@NonNull ITmfStateInterval> newStateIntervals) {
 529         transState.replaceOngoingState(newStateIntervals);
 530     }
 531
 532     //--------------------------------------------------------------------------
 533     //        Regular query methods (sent to the back-end)
 534     //--------------------------------------------------------------------------
 535
 536     @Override
 537     public synchronized List<ITmfStateInterval> queryFullState(long t)
 538             throws TimeRangeException, StateSystemDisposedException {
 539         if (isDisposed) {
 540             throw new StateSystemDisposedException();
 541         }
 542
 543         LOGGER.info(() -> "[StateSystem:FullQueryStart] ssid=" + this.getSSID() + ", ts=" + t);  //$NON-NLS-1$//$NON-NLS-2$
 544
 545         final int nbAttr = getNbAttributes();
 546         List<@Nullable ITmfStateInterval> stateInfo = new ArrayList<>(nbAttr);
 547
 548         /* Bring the size of the array to the current number of attributes */
 549         for (int i = 0; i < nbAttr; i++) {
 550             stateInfo.add(null);
 551         }
 552
 553         /*
 554          * If we are currently building the history, also query the "ongoing"
 555          * states for stuff that might not yet be written to the history.
 556          */
 557         if (transState.isActive()) {
 558             transState.doQuery(stateInfo, t);
 559         }
 560
 561         /* Query the storage backend */
 562         backend.doQuery(stateInfo, t);
 563
 564         /*
 565          * We should have previously inserted an interval for every attribute.
 566          */
 567         for (ITmfStateInterval interval : stateInfo) {
 568             if (interval == null) {
 569                 throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 570             }
 571         }
 572         LOGGER.info(() -> "[StateSystem:FullQueryEnd]");  //$NON-NLS-1$
 573         return stateInfo;
 574     }
 575
 576     @Override
 577     public ITmfStateInterval querySingleState(long t, int attributeQuark)
 578             throws TimeRangeException, StateSystemDisposedException {
 579         if (isDisposed) {
 580             throw new StateSystemDisposedException();
 581         }
 582
 583         LOGGER.info(() -> "[StateSystem:SingleQueryStart] ssid=" + this.getSSID() + ", ts=" + t + ", attribute=" + attributeQuark);  //$NON-NLS-1$//$NON-NLS-2$ //$NON-NLS-3$
 584
 585         ITmfStateInterval ret = transState.getIntervalAt(t, attributeQuark);
 586         if (ret == null) {
 587             /*
 588              * The transient state did not have the information, let's look into
 589              * the backend next.
 590              */
 591             ret = backend.doSingularQuery(t, attributeQuark);
 592         }
 593
 594         if (ret == null) {
 595             /*
 596              * If we did our job correctly, there should be intervals for every
 597              * possible attribute, over all the valid time range.
 598              */
 599             throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 600         }
 601         LOGGER.info(() -> "[StateSystem:SingleQueryEnd]");  //$NON-NLS-1$
 602         return ret;
 603     }
 604
 605     @Override
 606     public void removeFiles() {
 607         backend.removeFiles();
 608     }
 609
 610     //--------------------------------------------------------------------------
 611     //        Debug methods
 612     //--------------------------------------------------------------------------
 613
 614     static void logMissingInterval(int attribute, long timestamp) {
 615         Activator.getDefault().logInfo("No data found in history for attribute " + //$NON-NLS-1$
 616                 attribute + " at time " + timestamp + //$NON-NLS-1$
 617                 ", returning dummy interval"); //$NON-NLS-1$
 618     }
 619 }