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             throws AttributeNotFoundException {
 285         return getAttributeTree().getSubAttributes(quark, recursive);
 286     }
 287
 288     @Override
 289     public List<@NonNull Integer> getSubAttributes(int quark, boolean recursive, String pattern)
 290             throws AttributeNotFoundException {
 291         List<Integer> all = getSubAttributes(quark, recursive);
 292         List<@NonNull Integer> ret = new LinkedList<>();
 293         for (Integer attQuark : all) {
 294             String name = getAttributeName(attQuark.intValue());
 295             if (name.matches(pattern)) {
 296                 ret.add(attQuark);
 297             }
 298         }
 299         return ret;
 300     }
 301
 302     @Override
 303     public int getParentAttributeQuark(int quark) {
 304         return getAttributeTree().getParentAttributeQuark(quark);
 305     }
 306
 307     @Override
 308     public List<@NonNull Integer> getQuarks(String... pattern) {
 309         return getQuarks(ROOT_ATTRIBUTE, pattern);
 310     }
 311
 312     @Override
 313     public List<@NonNull Integer> getQuarks(int startingNodeQuark, String... pattern) {
 314         Builder<@NonNull Integer> builder = ImmutableSet.builder();
 315         if (pattern.length > 0) {
 316             getQuarks(builder, startingNodeQuark, Arrays.asList(pattern));
 317         } else {
 318             builder.add(startingNodeQuark);
 319         }
 320         return builder.build().asList();
 321     }
 322
 323     private void getQuarks(Builder<@NonNull Integer> builder, int quark, List<String> pattern) {
 324         try {
 325             String element = pattern.get(0);
 326             if (element == null) {
 327                 return;
 328             }
 329             List<String> remainder = pattern.subList(1, pattern.size());
 330             if (remainder.isEmpty()) {
 331                 if (element.equals(WILDCARD)) {
 332                     builder.addAll(getSubAttributes(quark, false));
 333                 } else if (element.equals(PARENT)){
 334                     builder.add(getParentAttributeQuark(quark));
 335                 } else {
 336                     int subQuark = optQuarkRelative(quark, element);
 337                     if (subQuark != INVALID_ATTRIBUTE) {
 338                         builder.add(subQuark);
 339                     }
 340                 }
 341             } else {
 342                 if (element.equals(WILDCARD)) {
 343                     for (@NonNull Integer subquark : getSubAttributes(quark, false)) {
 344                         getQuarks(builder, subquark, remainder);
 345                     }
 346                 } else if (element.equals(PARENT)){
 347                     getQuarks(builder, getParentAttributeQuark(quark), remainder);
 348                 } else {
 349                     int subQuark = optQuarkRelative(quark, element);
 350                     if (subQuark != INVALID_ATTRIBUTE) {
 351                         getQuarks(builder, subQuark, remainder);
 352                     }
 353                 }
 354             }
 355         } catch (AttributeNotFoundException e) {
 356             /* The starting node quark is out of range */
 357             throw new IndexOutOfBoundsException(String.format("Index: %d, Size: %d", quark, getNbAttributes())); //$NON-NLS-1$
 358         }
 359     }
 360
 361     //--------------------------------------------------------------------------
 362     //        Methods related to insertions in the history
 363     //--------------------------------------------------------------------------
 364
 365     @Override
 366     public void modifyAttribute(long t, ITmfStateValue value, int attributeQuark)
 367             throws TimeRangeException, AttributeNotFoundException,
 368             StateValueTypeException {
 369         if (value == null) {
 370             /*
 371              * TODO Replace with @NonNull parameter (will require fixing all the
 372              * state providers!)
 373              */
 374             throw new IllegalArgumentException();
 375         }
 376         transState.processStateChange(t, value, attributeQuark);
 377     }
 378
 379     @Deprecated
 380     @Override
 381     public void incrementAttribute(long t, int attributeQuark)
 382             throws StateValueTypeException, TimeRangeException,
 383             AttributeNotFoundException {
 384         ITmfStateValue stateValue = queryOngoingState(attributeQuark);
 385         int prevValue = 0;
 386         /* if the attribute was previously null, start counting at 0 */
 387         if (!stateValue.isNull()) {
 388             prevValue = stateValue.unboxInt();
 389         }
 390         modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1),
 391                 attributeQuark);
 392     }
 393
 394     @Override
 395     public void pushAttribute(long t, ITmfStateValue value, int attributeQuark)
 396             throws TimeRangeException, AttributeNotFoundException,
 397             StateValueTypeException {
 398         int stackDepth;
 399         int subAttributeQuark;
 400         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 401
 402         if (previousSV.isNull()) {
 403             /*
 404              * If the StateValue was null, this means this is the first time we
 405              * use this attribute. Leave stackDepth at 0.
 406              */
 407             stackDepth = 0;
 408         } else if (previousSV.getType() == Type.INTEGER) {
 409             /* Previous value was an integer, all is good, use it */
 410             stackDepth = previousSV.unboxInt();
 411         } else {
 412             /* Previous state of this attribute was another type? Not good! */
 413             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getType() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 414         }
 415
 416         if (stackDepth >= 100000) {
 417             /*
 418              * Limit stackDepth to 100000, to avoid having Attribute Trees grow
 419              * out of control due to buggy insertions
 420              */
 421             String message = " Stack limit reached, not pushing"; //$NON-NLS-1$
 422             throw new AttributeNotFoundException(getSSID() + " Quark:" + attributeQuark + message); //$NON-NLS-1$
 423         }
 424
 425         stackDepth++;
 426         subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, String.valueOf(stackDepth));
 427
 428         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), attributeQuark);
 429         modifyAttribute(t, value, subAttributeQuark);
 430     }
 431
 432     @Override
 433     public ITmfStateValue popAttribute(long t, int attributeQuark)
 434             throws AttributeNotFoundException, TimeRangeException,
 435             StateValueTypeException {
 436         /* These are the state values of the stack-attribute itself */
 437         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 438
 439         if (previousSV.isNull()) {
 440             /*
 441              * Trying to pop an empty stack. This often happens at the start of
 442              * traces, for example when we see a syscall_exit, without having
 443              * the corresponding syscall_entry in the trace. Just ignore
 444              * silently.
 445              */
 446             return null;
 447         }
 448         if (previousSV.getType() != Type.INTEGER) {
 449             /*
 450              * The existing value was not an integer (which is expected for
 451              * stack tops), this doesn't look like a valid stack attribute.
 452              */
 453             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Type:" + previousSV.getType() + ", Expected:" + Type.INTEGER); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
 454         }
 455
 456         int stackDepth = previousSV.unboxInt();
 457
 458         if (stackDepth <= 0) {
 459             /* This on the other hand should not happen... */
 460             throw new StateValueTypeException(getSSID() + " Quark:" + attributeQuark + ", Stack depth:" + stackDepth);  //$NON-NLS-1$//$NON-NLS-2$
 461         }
 462
 463         /* The attribute should already exist at this point */
 464         int subAttributeQuark = getQuarkRelative(attributeQuark, String.valueOf(stackDepth));
 465         ITmfStateValue poppedValue = queryOngoingState(subAttributeQuark);
 466
 467         /* Update the state value of the stack-attribute */
 468         ITmfStateValue nextSV;
 469         if (--stackDepth == 0) {
 470             /* Store a null state value */
 471             nextSV = TmfStateValue.nullValue();
 472         } else {
 473             nextSV = TmfStateValue.newValueInt(stackDepth);
 474         }
 475         modifyAttribute(t, nextSV, attributeQuark);
 476
 477         /* Delete the sub-attribute that contained the user's state value */
 478         removeAttribute(t, subAttributeQuark);
 479
 480         return poppedValue;
 481     }
 482
 483     @Override
 484     public void removeAttribute(long t, int attributeQuark)
 485             throws TimeRangeException, AttributeNotFoundException {
 486         if (attributeQuark < 0) {
 487             throw new IllegalArgumentException();
 488         }
 489
 490         /*
 491          * Nullify our children first, recursively. We pass 'false' because we
 492          * handle the recursion ourselves.
 493          */
 494         List<Integer> childAttributes = getSubAttributes(attributeQuark, false);
 495         for (int childNodeQuark : childAttributes) {
 496             if (attributeQuark == childNodeQuark) {
 497                 /* Something went very wrong when building out attribute tree */
 498                 throw new IllegalStateException();
 499             }
 500             removeAttribute(t, childNodeQuark);
 501         }
 502         /* Nullify ourselves */
 503         try {
 504             transState.processStateChange(t, TmfStateValue.nullValue(), attributeQuark);
 505         } catch (StateValueTypeException e) {
 506             /*
 507              * Will not happen since we're inserting null values only, but poor
 508              * compiler has no way of knowing this...
 509              */
 510             throw new IllegalStateException(e);
 511         }
 512     }
 513
 514     //--------------------------------------------------------------------------
 515     //        "Current" query/update methods
 516     //--------------------------------------------------------------------------
 517
 518     @Override
 519     public ITmfStateValue queryOngoingState(int attributeQuark)
 520             throws AttributeNotFoundException {
 521         return transState.getOngoingStateValue(attributeQuark);
 522     }
 523
 524     @Override
 525     public long getOngoingStartTime(int attribute)
 526             throws AttributeNotFoundException {
 527         return transState.getOngoingStartTime(attribute);
 528     }
 529
 530     @Override
 531     public void updateOngoingState(ITmfStateValue newValue, int attributeQuark)
 532             throws AttributeNotFoundException {
 533         transState.changeOngoingStateValue(attributeQuark, newValue);
 534     }
 535
 536     /**
 537      * Modify the whole "ongoing state" (state values + start times). This can
 538      * be used when "seeking" a state system to a different point in the trace
 539      * (and restoring the known stateInfo at this location). Use with care!
 540      *
 541      * @param newStateIntervals
 542      *            The new List of state values to use as ongoing state info
 543      */
 544     protected void replaceOngoingState(@NonNull List<@NonNull ITmfStateInterval> newStateIntervals) {
 545         transState.replaceOngoingState(newStateIntervals);
 546     }
 547
 548     //--------------------------------------------------------------------------
 549     //        Regular query methods (sent to the back-end)
 550     //--------------------------------------------------------------------------
 551
 552     @Override
 553     public synchronized List<ITmfStateInterval> queryFullState(long t)
 554             throws TimeRangeException, StateSystemDisposedException {
 555         if (isDisposed) {
 556             throw new StateSystemDisposedException();
 557         }
 558
 559         final int nbAttr = getNbAttributes();
 560         List<@Nullable ITmfStateInterval> stateInfo = new ArrayList<>(nbAttr);
 561
 562         /* Bring the size of the array to the current number of attributes */
 563         for (int i = 0; i < nbAttr; i++) {
 564             stateInfo.add(null);
 565         }
 566
 567         /*
 568          * If we are currently building the history, also query the "ongoing"
 569          * states for stuff that might not yet be written to the history.
 570          */
 571         if (transState.isActive()) {
 572             transState.doQuery(stateInfo, t);
 573         }
 574
 575         /* Query the storage backend */
 576         backend.doQuery(stateInfo, t);
 577
 578         /*
 579          * We should have previously inserted an interval for every attribute.
 580          */
 581         for (ITmfStateInterval interval : stateInfo) {
 582             if (interval == null) {
 583                 throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 584             }
 585         }
 586         return stateInfo;
 587     }
 588
 589     @Override
 590     public ITmfStateInterval querySingleState(long t, int attributeQuark)
 591             throws AttributeNotFoundException, TimeRangeException,
 592             StateSystemDisposedException {
 593         if (isDisposed) {
 594             throw new StateSystemDisposedException();
 595         }
 596
 597         ITmfStateInterval ret = transState.getIntervalAt(t, attributeQuark);
 598         if (ret == null) {
 599             /*
 600              * The transient state did not have the information, let's look into
 601              * the backend next.
 602              */
 603             ret = backend.doSingularQuery(t, attributeQuark);
 604         }
 605
 606         if (ret == null) {
 607             /*
 608              * If we did our job correctly, there should be intervals for every
 609              * possible attribute, over all the valid time range.
 610              */
 611             throw new IllegalStateException("Incoherent interval storage"); //$NON-NLS-1$
 612         }
 613         return ret;
 614     }
 615
 616     //--------------------------------------------------------------------------
 617     //        Debug methods
 618     //--------------------------------------------------------------------------
 619
 620     static void logMissingInterval(int attribute, long timestamp) {
 621         Activator.getDefault().logInfo("No data found in history for attribute " + //$NON-NLS-1$
 622                 attribute + " at time " + timestamp + //$NON-NLS-1$
 623                 ", returning dummy interval"); //$NON-NLS-1$
 624     }
 625
 626     /**
 627      * Print out the contents of the inner structures.
 628      *
 629      * @param writer
 630      *            The PrintWriter in which to print the output
 631      */
 632     public void debugPrint(@NonNull PrintWriter writer) {
 633         getAttributeTree().debugPrint(writer);
 634         transState.debugPrint(writer);
 635         backend.debugPrint(writer);
 636     }
 637
 638 }