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

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