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