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