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

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