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