org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/StateSystem.java

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