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