org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/statesystem/StateSystem.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012 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.linuxtools.internal.tmf.core.statesystem;
  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
  23 import org.eclipse.core.runtime.IProgressMonitor;
  24 import org.eclipse.core.runtime.NullProgressMonitor;
  25 import org.eclipse.linuxtools.internal.tmf.core.Activator;
  26 import org.eclipse.linuxtools.tmf.core.exceptions.AttributeNotFoundException;
  27 import org.eclipse.linuxtools.tmf.core.exceptions.StateSystemDisposedException;
  28 import org.eclipse.linuxtools.tmf.core.exceptions.StateValueTypeException;
  29 import org.eclipse.linuxtools.tmf.core.exceptions.TimeRangeException;
  30 import org.eclipse.linuxtools.tmf.core.interval.ITmfStateInterval;
  31 import org.eclipse.linuxtools.tmf.core.interval.TmfStateInterval;
  32 import org.eclipse.linuxtools.tmf.core.statesystem.ITmfStateSystemBuilder;
  33 import org.eclipse.linuxtools.tmf.core.statevalue.ITmfStateValue;
  34 import org.eclipse.linuxtools.tmf.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      * General constructor
  64      *
  65      * @param backend
  66      *            The "state history storage" backend to use.
  67      * @param newFile
  68      *            Put true if this is a new history started from scratch. It is
  69      *            used to tell the state system where to get its attribute tree.
  70      * @throws IOException
  71      *             If there was a problem creating the new history file
  72      */
  73     public StateSystem(IStateHistoryBackend backend, boolean newFile)
  74             throws IOException {
  75         this.backend = backend;
  76         this.transState = new TransientState(backend);
  77
  78         if (newFile) {
  79             attributeTree = new AttributeTree(this);
  80         } else {
  81             /* We're opening an existing file */
  82             this.attributeTree = new AttributeTree(this, backend.supplyAttributeTreeReader());
  83             transState.setInactive();
  84             finishedLatch.countDown(); /* The history is already built */
  85         }
  86     }
  87
  88     @Override
  89     public boolean waitUntilBuilt() {
  90         try {
  91             finishedLatch.await();
  92         } catch (InterruptedException e) {
  93             e.printStackTrace();
  94         }
  95         return !buildCancelled;
  96     }
  97
  98     @Override
  99     public synchronized void dispose() {
 100         isDisposed = true;
 101         if (transState.isActive()) {
 102             transState.setInactive();
 103             buildCancelled = true;
 104         }
 105         backend.dispose();
 106     }
 107
 108     //--------------------------------------------------------------------------
 109     //        General methods related to the attribute tree
 110     //--------------------------------------------------------------------------
 111
 112     /**
 113      * Method used by the attribute tree when creating new attributes, to keep
 114      * the attribute count in the transient state in sync.
 115      */
 116     void addEmptyAttribute() {
 117         transState.addEmptyEntry();
 118     }
 119
 120     @Override
 121     public int getNbAttributes() {
 122         return attributeTree.getNbAttributes();
 123     }
 124
 125     @Override
 126     public boolean isLastAttribute(int quark) {
 127         return (quark == getNbAttributes() - 1) ? true : false;
 128     }
 129
 130     @Override
 131     public String getAttributeName(int attributeQuark) {
 132         return attributeTree.getAttributeName(attributeQuark);
 133     }
 134
 135     @Override
 136     public String getFullAttributePath(int attributeQuark) {
 137         return attributeTree.getFullAttributeName(attributeQuark);
 138     }
 139
 140     //--------------------------------------------------------------------------
 141     //        Methods related to the storage backend
 142     //--------------------------------------------------------------------------
 143
 144     @Override
 145     public long getStartTime() {
 146         return backend.getStartTime();
 147     }
 148
 149     @Override
 150     public long getCurrentEndTime() {
 151         return backend.getEndTime();
 152     }
 153
 154     @Override
 155     public void closeHistory(long endTime) throws TimeRangeException {
 156         File attributeTreeFile;
 157         long attributeTreeFilePos;
 158         long realEndTime = endTime;
 159
 160         if (realEndTime < backend.getEndTime()) {
 161             /*
 162              * This can happen (empty nodes pushing the border further, etc.)
 163              * but shouldn't be too big of a deal.
 164              */
 165             realEndTime = backend.getEndTime();
 166         }
 167         transState.closeTransientState(realEndTime);
 168         backend.finishedBuilding(realEndTime);
 169
 170         attributeTreeFile = backend.supplyAttributeTreeWriterFile();
 171         attributeTreeFilePos = backend.supplyAttributeTreeWriterFilePosition();
 172         if (attributeTreeFile != null) {
 173             /*
 174              * If null was returned, we simply won't save the attribute tree,
 175              * too bad!
 176              */
 177             attributeTree.writeSelf(attributeTreeFile, attributeTreeFilePos);
 178         }
 179         finishedLatch.countDown(); /* Mark the history as finished building */
 180     }
 181
 182     //--------------------------------------------------------------------------
 183     //        Quark-retrieving methods
 184     //--------------------------------------------------------------------------
 185
 186     @Override
 187     public int getQuarkAbsolute(String... attribute)
 188             throws AttributeNotFoundException {
 189         return attributeTree.getQuarkDontAdd(-1, attribute);
 190     }
 191
 192     @Override
 193     public int getQuarkAbsoluteAndAdd(String... attribute) {
 194         return attributeTree.getQuarkAndAdd(-1, attribute);
 195     }
 196
 197     @Override
 198     public int getQuarkRelative(int startingNodeQuark, String... subPath)
 199             throws AttributeNotFoundException {
 200         return attributeTree.getQuarkDontAdd(startingNodeQuark, subPath);
 201     }
 202
 203     @Override
 204     public int getQuarkRelativeAndAdd(int startingNodeQuark, String... subPath) {
 205         return attributeTree.getQuarkAndAdd(startingNodeQuark, subPath);
 206     }
 207
 208     @Override
 209     public List<Integer> getSubAttributes(int quark, boolean recursive)
 210             throws AttributeNotFoundException {
 211         return attributeTree.getSubAttributes(quark, recursive);
 212     }
 213
 214     @Override
 215     public List<Integer> getQuarks(String... pattern) {
 216         List<Integer> quarks = new LinkedList<Integer>();
 217         List<String> prefix = new LinkedList<String>();
 218         List<String> suffix = new LinkedList<String>();
 219         boolean split = false;
 220         String[] prefixStr;
 221         String[] suffixStr;
 222         List<Integer> directChildren;
 223         int startingAttribute;
 224
 225         /* Fill the "prefix" and "suffix" parts of the pattern around the '*' */
 226         for (String entry : pattern) {
 227             if (entry.equals("*")) { //$NON-NLS-1$
 228                 if (split) {
 229                     /*
 230                      * Split was already true? This means there was more than
 231                      * one wildcard. This is not supported, return an empty
 232                      * list.
 233                      */
 234                     return quarks;
 235                 }
 236                 split = true;
 237                 continue;
 238             }
 239
 240             if (split) {
 241                 suffix.add(entry);
 242             } else {
 243                 prefix.add(entry);
 244             }
 245         }
 246         prefixStr = prefix.toArray(new String[prefix.size()]);
 247         suffixStr = suffix.toArray(new String[suffix.size()]);
 248
 249         /*
 250          * If there was no wildcard, we'll only return the one matching
 251          * attribute, if there is one.
 252          */
 253         if (split == false) {
 254             int quark;
 255             try {
 256                 quark = getQuarkAbsolute(prefixStr);
 257             } catch (AttributeNotFoundException e) {
 258                 /* It's fine, we'll just return the empty List */
 259                 return quarks;
 260             }
 261             quarks.add(quark);
 262             return quarks;
 263         }
 264
 265         try {
 266             if (prefix.size() == 0) {
 267                 /*
 268                  * If 'prefix' is empty, this means the wildcard was the first
 269                  * element. Look for the root node's sub-attributes.
 270                  */
 271                 startingAttribute = -1;
 272             } else {
 273                 startingAttribute = getQuarkAbsolute(prefixStr);
 274             }
 275             directChildren = attributeTree.getSubAttributes(startingAttribute,
 276                     false);
 277         } catch (AttributeNotFoundException e) {
 278             /* That attribute path did not exist, return the empty array */
 279             return quarks;
 280         }
 281
 282         /*
 283          * Iterate of all the sub-attributes, and only keep those who match the
 284          * 'suffix' part of the initial pattern.
 285          */
 286         for (int childQuark : directChildren) {
 287             int matchingQuark;
 288             try {
 289                 matchingQuark = getQuarkRelative(childQuark, suffixStr);
 290             } catch (AttributeNotFoundException e) {
 291                 continue;
 292             }
 293             quarks.add(matchingQuark);
 294         }
 295
 296         return quarks;
 297     }
 298
 299     //--------------------------------------------------------------------------
 300     //        Methods related to insertions in the history
 301     //--------------------------------------------------------------------------
 302
 303     @Override
 304     public void modifyAttribute(long t, ITmfStateValue value, int attributeQuark)
 305             throws TimeRangeException, AttributeNotFoundException,
 306             StateValueTypeException {
 307         transState.processStateChange(t, value, attributeQuark);
 308     }
 309
 310     @Override
 311     public void incrementAttribute(long t, int attributeQuark)
 312             throws StateValueTypeException, TimeRangeException,
 313             AttributeNotFoundException {
 314         int prevValue = queryOngoingState(attributeQuark).unboxInt();
 315         if (prevValue == -1) {
 316             /* if the attribute was previously null, start counting at 0 */
 317             prevValue = 0;
 318         }
 319         modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1),
 320                 attributeQuark);
 321     }
 322
 323     @Override
 324     public void pushAttribute(long t, ITmfStateValue value, int attributeQuark)
 325             throws TimeRangeException, AttributeNotFoundException,
 326             StateValueTypeException {
 327         Integer stackDepth = 0;
 328         int subAttributeQuark;
 329         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 330
 331         if (previousSV.isNull()) {
 332             /*
 333              * If the StateValue was null, this means this is the first time we
 334              * use this attribute. Leave stackDepth at 0.
 335              */
 336         } else if (previousSV.getType() == 0) {
 337             /* Previous value was an integer, all is good, use it */
 338             stackDepth = previousSV.unboxInt();
 339         } else {
 340             /* Previous state of this attribute was another type? Not good! */
 341             throw new StateValueTypeException();
 342         }
 343
 344         if (stackDepth >= 10) {
 345             /*
 346              * Limit stackDepth to 10, to avoid having Attribute Trees grow out
 347              * of control due to buggy insertions
 348              */
 349             String message = "Stack limit reached, not pushing"; //$NON-NLS-1$
 350             throw new AttributeNotFoundException(message);
 351         }
 352
 353         stackDepth++;
 354         subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark, stackDepth.toString());
 355
 356         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), attributeQuark);
 357         modifyAttribute(t, value, subAttributeQuark);
 358     }
 359
 360     @Override
 361     public ITmfStateValue popAttribute(long t, int attributeQuark)
 362             throws AttributeNotFoundException, TimeRangeException,
 363             StateValueTypeException {
 364         /* These are the state values of the stack-attribute itself */
 365         ITmfStateValue previousSV = queryOngoingState(attributeQuark);
 366
 367         if (previousSV.isNull()) {
 368             /*
 369              * Trying to pop an empty stack. This often happens at the start of
 370              * traces, for example when we see a syscall_exit, without having
 371              * the corresponding syscall_entry in the trace. Just ignore
 372              * silently.
 373              */
 374             return null;
 375         }
 376         if (previousSV.getType() != ITmfStateValue.TYPE_INTEGER) {
 377             /*
 378              * The existing value was a string, this doesn't look like a valid
 379              * stack attribute.
 380              */
 381             throw new StateValueTypeException();
 382         }
 383
 384         Integer stackDepth = previousSV.unboxInt();
 385
 386         if (stackDepth <= 0) {
 387             /* This on the other hand should not happen... */
 388             /* the case where == -1 was handled previously by .isNull() */
 389             String message = "A top-level stack attribute cannot " + //$NON-NLS-1$
 390                     "have a value of 0 or less (except -1/null)."; //$NON-NLS-1$
 391             throw new StateValueTypeException(message);
 392         }
 393
 394         /* The attribute should already exist at this point */
 395         int subAttributeQuark = getQuarkRelative(attributeQuark, stackDepth.toString());
 396         ITmfStateValue poppedValue = queryOngoingState(subAttributeQuark);
 397
 398         /* Update the state value of the stack-attribute */
 399         ITmfStateValue nextSV;
 400         if (--stackDepth == 0 ) {
 401             /* Jump over "0" and store -1 (a null state value) */
 402             nextSV = TmfStateValue.nullValue();
 403         } else {
 404             nextSV = TmfStateValue.newValueInt(stackDepth);
 405         }
 406         modifyAttribute(t, nextSV, attributeQuark);
 407
 408         /* Delete the sub-attribute that contained the user's state value */
 409         removeAttribute(t, subAttributeQuark);
 410
 411         return poppedValue;
 412     }
 413
 414     @Override
 415     public void removeAttribute(long t, int attributeQuark)
 416             throws TimeRangeException, AttributeNotFoundException {
 417         assert (attributeQuark >= 0);
 418         List<Integer> childAttributes;
 419
 420         /*
 421          * "Nullify our children first, recursively. We pass 'false' because we
 422          * handle the recursion ourselves.
 423          */
 424         childAttributes = attributeTree.getSubAttributes(attributeQuark, false);
 425         for (Integer childNodeQuark : childAttributes) {
 426             assert (attributeQuark != childNodeQuark);
 427             removeAttribute(t, childNodeQuark);
 428         }
 429         /* Nullify ourselves */
 430         try {
 431             transState.processStateChange(t, TmfStateValue.nullValue(),
 432                     attributeQuark);
 433         } catch (StateValueTypeException e) {
 434             /*
 435              * Will not happen since we're inserting null values only, but poor
 436              * compiler has no way of knowing this...
 437              */
 438             e.printStackTrace();
 439         }
 440     }
 441
 442     //--------------------------------------------------------------------------
 443     //        "Current" query/update methods
 444     //--------------------------------------------------------------------------
 445
 446     @Override
 447     public ITmfStateValue queryOngoingState(int attributeQuark)
 448             throws AttributeNotFoundException {
 449         return transState.getOngoingStateValue(attributeQuark);
 450     }
 451
 452     @Override
 453     public void updateOngoingState(ITmfStateValue newValue, int attributeQuark)
 454             throws AttributeNotFoundException {
 455         transState.changeOngoingStateValue(attributeQuark, newValue);
 456     }
 457
 458
 459
 460     //--------------------------------------------------------------------------
 461     //        Regular query methods (sent to the back-end)
 462     //--------------------------------------------------------------------------
 463
 464     @Override
 465     public synchronized List<ITmfStateInterval> queryFullState(long t)
 466             throws TimeRangeException, StateSystemDisposedException {
 467         if (isDisposed) {
 468             throw new StateSystemDisposedException();
 469         }
 470
 471         List<ITmfStateInterval> stateInfo = new ArrayList<ITmfStateInterval>(
 472                 attributeTree.getNbAttributes());
 473
 474         /* Bring the size of the array to the current number of attributes */
 475         for (int i = 0; i < attributeTree.getNbAttributes(); i++) {
 476             stateInfo.add(null);
 477         }
 478
 479         /* Query the storage backend */
 480         backend.doQuery(stateInfo, t);
 481
 482         /*
 483          * If we are currently building the history, also query the "ongoing"
 484          * states for stuff that might not yet be written to the history.
 485          */
 486         if (transState.isActive()) {
 487             transState.doQuery(stateInfo, t);
 488         }
 489
 490         /*
 491          * We should have previously inserted an interval for every attribute.
 492          * If we do happen do see a 'null' object here, just replace it with a a
 493          * dummy internal with a null value, to avoid NPE's further up.
 494          */
 495         for (int i = 0; i < stateInfo.size(); i++) {
 496             if (stateInfo.get(i) == null) {
 497                 //logMissingInterval(i, t);
 498                 stateInfo.set(i, new TmfStateInterval(t, t, i, TmfStateValue.nullValue()));
 499             }
 500         }
 501         return stateInfo;
 502     }
 503
 504     @Override
 505     public ITmfStateInterval querySingleState(long t, int attributeQuark)
 506             throws AttributeNotFoundException, TimeRangeException,
 507             StateSystemDisposedException {
 508         if (isDisposed) {
 509             throw new StateSystemDisposedException();
 510         }
 511
 512         ITmfStateInterval ret;
 513         if (transState.hasInfoAboutStateOf(t, attributeQuark)) {
 514             ret = transState.getOngoingInterval(attributeQuark);
 515         } else {
 516             ret = backend.doSingularQuery(t, attributeQuark);
 517         }
 518
 519         /*
 520          * Return a fake interval if we could not find anything in the history.
 521          * We do NOT want to return 'null' here.
 522          */
 523         if (ret == null) {
 524             //logMissingInterval(attributeQuark, t);
 525             return new TmfStateInterval(t, this.getCurrentEndTime(),
 526                     attributeQuark, TmfStateValue.nullValue());
 527         }
 528         return ret;
 529     }
 530
 531     @Override
 532     public ITmfStateInterval querySingleStackTop(long t, int stackAttributeQuark)
 533             throws StateValueTypeException, AttributeNotFoundException,
 534             TimeRangeException, StateSystemDisposedException {
 535         Integer curStackDepth = querySingleState(t, stackAttributeQuark).getStateValue().unboxInt();
 536
 537         if (curStackDepth == -1) {
 538             /* There is nothing stored in this stack at this moment */
 539             return null;
 540         } else if (curStackDepth < -1 || curStackDepth == 0) {
 541             /*
 542              * This attribute is an integer attribute, but it doesn't seem like
 543              * it's used as a stack-attribute...
 544              */
 545             throw new StateValueTypeException();
 546         }
 547
 548         int subAttribQuark = getQuarkRelative(stackAttributeQuark, curStackDepth.toString());
 549         ITmfStateInterval ret = querySingleState(t, subAttribQuark);
 550         return ret;
 551     }
 552
 553     @Override
 554     public List<ITmfStateInterval> queryHistoryRange(int attributeQuark,
 555             long t1, long t2) throws TimeRangeException,
 556             AttributeNotFoundException, StateSystemDisposedException {
 557         if (isDisposed) {
 558             throw new StateSystemDisposedException();
 559         }
 560
 561         List<ITmfStateInterval> intervals;
 562         ITmfStateInterval currentInterval;
 563         long ts, tEnd;
 564
 565         /* Make sure the time range makes sense */
 566         if (t2 <= t1) {
 567             throw new TimeRangeException();
 568         }
 569
 570         /* Set the actual, valid end time of the range query */
 571         if (t2 > this.getCurrentEndTime()) {
 572             tEnd = this.getCurrentEndTime();
 573         } else {
 574             tEnd = t2;
 575         }
 576
 577         /* Get the initial state at time T1 */
 578         intervals = new ArrayList<ITmfStateInterval>();
 579         currentInterval = querySingleState(t1, attributeQuark);
 580         intervals.add(currentInterval);
 581
 582         /* Get the following state changes */
 583         ts = currentInterval.getEndTime();
 584         while (ts != -1 && ts < tEnd) {
 585             ts++; /* To "jump over" to the next state in the history */
 586             currentInterval = querySingleState(ts, attributeQuark);
 587             intervals.add(currentInterval);
 588             ts = currentInterval.getEndTime();
 589         }
 590         return intervals;
 591     }
 592
 593     @Override
 594     public List<ITmfStateInterval> queryHistoryRange(int attributeQuark,
 595             long t1, long t2, long resolution, IProgressMonitor monitor)
 596             throws TimeRangeException, AttributeNotFoundException,
 597             StateSystemDisposedException {
 598         if (isDisposed) {
 599             throw new StateSystemDisposedException();
 600         }
 601
 602         List<ITmfStateInterval> intervals;
 603         ITmfStateInterval currentInterval;
 604         long ts, tEnd;
 605
 606         IProgressMonitor mon = monitor;
 607         if (mon == null) {
 608             mon = new NullProgressMonitor();
 609         }
 610
 611         /* Make sure the time range makes sense */
 612         if (t2 < t1 || resolution <= 0) {
 613             throw new TimeRangeException();
 614         }
 615
 616         /* Set the actual, valid end time of the range query */
 617         if (t2 > this.getCurrentEndTime()) {
 618             tEnd = this.getCurrentEndTime();
 619         } else {
 620             tEnd = t2;
 621         }
 622
 623         /* Get the initial state at time T1 */
 624         intervals = new ArrayList<ITmfStateInterval>();
 625         currentInterval = querySingleState(t1, attributeQuark);
 626         intervals.add(currentInterval);
 627
 628         /*
 629          * Iterate over the "resolution points". We skip unneeded queries in the
 630          * case the current interval is longer than the resolution.
 631          */
 632         for (ts = t1; (currentInterval.getEndTime() != -1) && (ts < tEnd);
 633                 ts += resolution) {
 634             if (mon.isCanceled()) {
 635                 return intervals;
 636             }
 637             if (ts <= currentInterval.getEndTime()) {
 638                 continue;
 639             }
 640             currentInterval = querySingleState(ts, attributeQuark);
 641             intervals.add(currentInterval);
 642         }
 643
 644         /* Add the interval at t2, if it wasn't included already. */
 645         if (currentInterval.getEndTime() < tEnd) {
 646             currentInterval = querySingleState(tEnd, attributeQuark);
 647             intervals.add(currentInterval);
 648         }
 649         return intervals;
 650     }
 651
 652     //--------------------------------------------------------------------------
 653     //        Debug methods
 654     //--------------------------------------------------------------------------
 655
 656     static void logMissingInterval(int attribute, long timestamp) {
 657         Activator.logInfo("No data found in history for attribute " + //$NON-NLS-1$
 658                 attribute + " at time " + timestamp + //$NON-NLS-1$
 659                 ", returning dummy interval"); //$NON-NLS-1$
 660     }
 661
 662     /**
 663      * Print out the contents of the inner structures.
 664      *
 665      * @param writer
 666      *            The PrintWriter in which to print the output
 667      */
 668     public void debugPrint(PrintWriter writer) {
 669         attributeTree.debugPrint(writer);
 670         transState.debugPrint(writer);
 671         backend.debugPrint(writer);
 672     }
 673
 674 }