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