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     @Deprecated
 405     @Override
 406     public void incrementAttribute(long t, int attributeQuark)
 407             throws StateValueTypeException, TimeRangeException,
 408             AttributeNotFoundException {
 409         ITmfStateValue stateValue = queryOngoingState(attributeQuark);
 410         int prevValue = 0;
 411         /* if the attribute was previously null, start counting at 0 */
 412         if (!stateValue.isNull()) {
 413             prevValue = stateValue.unboxInt();
 414         }
 415         modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1),
 416                 attributeQuark);
 417     }
 418
 419     @Override
 420     public void pushAttribute(long t, ITmfStateValue value, int attributeQuark)
 421             throws TimeRangeException, AttributeNotFoundException,
 422             StateValueTypeException {
 423         int stackDepth;
 424         int subAttributeQuark;
 425         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 426
 427         if (previousSV.isNull()) {
 428             /*
 429              * If the StateValue was null, this means this is the first time we
 430              * use this attribute. Leave stackDepth at 0.
 431              */
 432             stackDepth = 0;
 433         } else if (previousSV.getType() == Type.INTEGER) {
 434             /* Previous value was an integer, all is good, use it */
 435             stackDepth = previousSV.unboxInt();
 436         } else {
 437             /* Previous state of this attribute was another type? Not good! */
 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         if (stackDepth >= 100000) {
 442             /*
 443              * Limit stackDepth to 100000, to avoid having Attribute Trees grow
 444              * out of control due to buggy insertions
 445              */
 446             String message = " Stack limit reached, not pushing"; //$NON-NLS-1$
 447             throw new AttributeNotFoundException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
 448         }
 449
 450         stackDepth++;
 451         subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, String.valueOf(stackDepth));
 452
 453         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), attributeQuark);
 454         modifyAttribute(t, value, subAttributeQuark);
 455     }
 456
 457     @Override
 458     public ITmfStateValue popAttribute(long t, int attributeQuark)
 459             throws AttributeNotFoundException, TimeRangeException,
 460             StateValueTypeException {
 461         /* These are the state values of the stack-attribute itself */
 462         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 463
 464         if (previousSV.isNull()) {
 465             /*
 466              * Trying to pop an empty stack. This often happens at the start of
 467              * traces, for example when we see a syscall_exit, without having
 468              * the corresponding syscall_entry in the trace. Just ignore
 469              * silently.
 470              */
 471             return null;
 472         }
 473         if (previousSV.getType() != Type.INTEGER) {
 474             /*
 475              * The existing value was not an integer (which is expected for
 476              * stack tops), this doesn't look like a valid stack attribute.
 477              */
 478             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getType() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 479         }
 480
 481         int stackDepth = previousSV.unboxInt();
 482
 483         if (stackDepth <= 0) {
 484             /* This on the other hand should not happen... */
 485             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Stack depth:" + stackDepth);  //$NON-NLS-1$//$NON-NLS-2$
 486         }
 487
 488         /* The attribute should already exist at this point */
 489         int subAttributeQuark = getQuarkRelative(attributeQuark, String.valueOf(stackDepth));
 490         ITmfStateValue poppedValue = queryOngoingState(subAttributeQuark);
 491
 492         /* Update the state value of the stack-attribute */
 493         ITmfStateValue nextSV;
 494         if (--stackDepth == 0) {
 495             /* Store a null state value */
 496             nextSV = TmfStateValue.nullValue();
 497         } else {
 498             nextSV = TmfStateValue.newValueInt(stackDepth);
 499         }
 500         modifyAttribute(t, nextSV, attributeQuark);
 501
 502         /* Delete the sub-attribute that contained the user's state value */
 503         removeAttribute(t, subAttributeQuark);
 504
 505         return poppedValue;
 506     }
 507
 508     @Override
 509     public void removeAttribute(long t, int attributeQuark)
 510             throws TimeRangeException, AttributeNotFoundException {
 511         if (attributeQuark < 0) {
 512             throw new IllegalArgumentException();
 513         }
 514
 515         /*
 516          * Nullify our children first, recursively. We pass 'false' because we
 517          * handle the recursion ourselves.
 518          */
 519         List<Integer> childAttributes = getSubAttributes(attributeQuark, false);
 520         for (int childNodeQuark : childAttributes) {
 521             if (attributeQuark == childNodeQuark) {
 522                 /* Something went very wrong when building out attribute tree */
 523                 throw new IllegalStateException();
 524             }
 525             removeAttribute(t, childNodeQuark);
 526         }
 527         /* Nullify ourselves */
 528         try {
 529             transState.processStateChange(t, TmfStateValue.nullValue(), attributeQuark);
 530         } catch (StateValueTypeException e) {
 531             /*
 532              * Will not happen since we're inserting null values only, but poor
 533              * compiler has no way of knowing this...
 534              */
 535             throw new IllegalStateException(e);
 536         }
 537     }
 538
 539     //--------------------------------------------------------------------------
 540     //        "Current" query/update methods
 541     //--------------------------------------------------------------------------
 542
 543     @Override
 544     public ITmfStateValue queryOngoingState(int attributeQuark)
 545             throws AttributeNotFoundException {
 546         return transState.getOngoingStateValue(attributeQuark);
 547     }
 548
 549     @Override
 550     public long getOngoingStartTime(int attribute)
 551             throws AttributeNotFoundException {
 552         return transState.getOngoingStartTime(attribute);
 553     }
 554
 555     @Override
 556     public void updateOngoingState(ITmfStateValue newValue, int attributeQuark)
 557             throws AttributeNotFoundException {
 558         transState.changeOngoingStateValue(attributeQuark, newValue);
 559     }
 560
 561     /**
 562      * Modify the whole "ongoing state" (state values + start times). This can
 563      * be used when "seeking" a state system to a different point in the trace
 564      * (and restoring the known stateInfo at this location). Use with care!
 565      *
 566      * @param newStateIntervals
 567      *            The new List of state values to use as ongoing state info
 568      */
 569     protected void replaceOngoingState(@NonNull List<@NonNull ITmfStateInterval> newStateIntervals) {
 570         transState.replaceOngoingState(newStateIntervals);
 571     }
 572
 573     //--------------------------------------------------------------------------
 574     //        Regular query methods (sent to the back-end)
 575     //--------------------------------------------------------------------------
 576
 577     @Override
 578     public synchronized List<ITmfStateInterval> queryFullState(long t)
 579             throws TimeRangeException, StateSystemDisposedException {
 580         if (isDisposed) {
 581             throw new StateSystemDisposedException();
 582         }
 583
 584         final int nbAttr = getNbAttributes();
 585         List<@Nullable ITmfStateInterval> stateInfo = new ArrayList<>(nbAttr);
 586
 587         /* Bring the size of the array to the current number of attributes */
 588         for (int i = 0; i < nbAttr; i++) {
 589             stateInfo.add(null);
 590         }
 591
 592         /*
 593          * If we are currently building the history, also query the "ongoing"
 594          * states for stuff that might not yet be written to the history.
 595          */
 596         if (transState.isActive()) {
 597             transState.doQuery(stateInfo, t);
 598         }
 599
 600         /* Query the storage backend */
 601         backend.doQuery(stateInfo, t);
 602
 603         /*
 604          * We should have previously inserted an interval for every attribute.
 605          */
 606         for (ITmfStateInterval interval : stateInfo) {
 607             if (interval == null) {
 608                 throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 609             }
 610         }
 611         return stateInfo;
 612     }
 613
 614     @Override
 615     public ITmfStateInterval querySingleState(long t, int attributeQuark)
 616             throws AttributeNotFoundException, TimeRangeException,
 617             StateSystemDisposedException {
 618         if (isDisposed) {
 619             throw new StateSystemDisposedException();
 620         }
 621
 622         ITmfStateInterval ret = transState.getIntervalAt(t, attributeQuark);
 623         if (ret == null) {
 624             /*
 625              * The transient state did not have the information, let's look into
 626              * the backend next.
 627              */
 628             ret = backend.doSingularQuery(t, attributeQuark);
 629         }
 630
 631         if (ret == null) {
 632             /*
 633              * If we did our job correctly, there should be intervals for every
 634              * possible attribute, over all the valid time range.
 635              */
 636             throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 637         }
 638         return ret;
 639     }
 640
 641     //--------------------------------------------------------------------------
 642     //        Debug methods
 643     //--------------------------------------------------------------------------
 644
 645     static void logMissingInterval(int attribute, long timestamp) {
 646         Activator.getDefault().logInfo("No data found in history for attribute " + //$NON-NLS-1$
 647                 attribute + " at time " + timestamp + //$NON-NLS-1$
 648                 ", returning dummy interval"); //$NON-NLS-1$
 649     }
 650
 651     /**
 652      * Print out the contents of the inner structures.
 653      *
 654      * @param writer
 655      *            The PrintWriter in which to print the output
 656      */
 657     public void debugPrint(@NonNull PrintWriter writer) {
 658         getAttributeTree().debugPrint(writer);
 659         transState.debugPrint(writer);
 660         backend.debugPrint(writer);
 661     }
 662
 663 }