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         ITmfStateValue previousSV = queryOngoingState(attributeQuark);
 335
 336         if (previousSV.isNull()) {
 337             /* Same as if stackDepth == 0, see below */
 338             return null;
 339         }
 340         if (previousSV.getType() != 0) {
 341             /*
 342              * The existing value was a string, this doesn't look like a valid
 343              * stack attribute.
 344              */
 345             throw new StateValueTypeException();
 346         }
 347
 348         Integer stackDepth = previousSV.unboxInt();
 349
 350         if (stackDepth == 0) {
 351             /*
 352              * Trying to pop an empty stack. This often happens at the start of
 353              * traces, for example when we see a syscall_exit, without having
 354              * the corresponding syscall_entry in the trace. Just ignore
 355              * silently.
 356              */
 357             return null;
 358         }
 359
 360         if (stackDepth < 0) {
 361             /* This on the other hand should not happen... */
 362             String message = "A top-level stack attribute " + //$NON-NLS-1$
 363                     "cannot have a negative integer value."; //$NON-NLS-1$
 364             throw new StateValueTypeException(message);
 365         }
 366
 367         /* The attribute should already exist... */
 368         int subAttributeQuark = getQuarkRelative(attributeQuark, stackDepth.toString());
 369         ITmfStateValue poppedValue = queryOngoingState(subAttributeQuark);
 370
 371         stackDepth--;
 372         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth), attributeQuark);
 373         removeAttribute(t, subAttributeQuark);
 374         return poppedValue;
 375     }
 376
 377     @Override
 378     public void removeAttribute(long t, int attributeQuark)
 379             throws TimeRangeException, AttributeNotFoundException {
 380         assert (attributeQuark >= 0);
 381         List<Integer> childAttributes;
 382
 383         /*
 384          * "Nullify our children first, recursively. We pass 'false' because we
 385          * handle the recursion ourselves.
 386          */
 387         childAttributes = attributeTree.getSubAttributes(attributeQuark, false);
 388         for (Integer childNodeQuark : childAttributes) {
 389             assert (attributeQuark != childNodeQuark);
 390             removeAttribute(t, childNodeQuark);
 391         }
 392         /* Nullify ourselves */
 393         try {
 394             transState.processStateChange(t, TmfStateValue.nullValue(),
 395                     attributeQuark);
 396         } catch (StateValueTypeException e) {
 397             /*
 398              * Will not happen since we're inserting null values only, but poor
 399              * compiler has no way of knowing this...
 400              */
 401             e.printStackTrace();
 402         }
 403     }
 404
 405     //--------------------------------------------------------------------------
 406     //        "Current" query/update methods
 407     //--------------------------------------------------------------------------
 408
 409     @Override
 410     public ITmfStateValue queryOngoingState(int attributeQuark)
 411             throws AttributeNotFoundException {
 412         return transState.getOngoingStateValue(attributeQuark);
 413     }
 414
 415     @Override
 416     public void updateOngoingState(ITmfStateValue newValue, int attributeQuark)
 417             throws AttributeNotFoundException {
 418         transState.changeOngoingStateValue(attributeQuark, newValue);
 419     }
 420
 421
 422
 423     //--------------------------------------------------------------------------
 424     //        Regular query methods (sent to the back-end)
 425     //--------------------------------------------------------------------------
 426
 427     @Override
 428     public synchronized List<ITmfStateInterval> queryFullState(long t)
 429             throws TimeRangeException {
 430         List<ITmfStateInterval> stateInfo = new ArrayList<ITmfStateInterval>(
 431                 attributeTree.getNbAttributes());
 432
 433         /* Bring the size of the array to the current number of attributes */
 434         for (int i = 0; i < attributeTree.getNbAttributes(); i++) {
 435             stateInfo.add(null);
 436         }
 437
 438         /* Query the storage backend */
 439         backend.doQuery(stateInfo, t);
 440
 441         /*
 442          * If we are currently building the history, also query the "ongoing"
 443          * states for stuff that might not yet be written to the history.
 444          */
 445         if (transState.isActive()) {
 446             transState.doQuery(stateInfo, t);
 447         }
 448
 449         /*
 450          * We should have previously inserted an interval for every attribute.
 451          * If we do happen do see a 'null' object here, just replace it with a a
 452          * dummy internal with a null value, to avoid NPE's further up.
 453          */
 454         for (int i = 0; i < stateInfo.size(); i++) {
 455             if (stateInfo.get(i) == null) {
 456                 //logMissingInterval(i, t);
 457                 stateInfo.set(i, new TmfStateInterval(t, t, i, TmfStateValue.nullValue()));
 458             }
 459         }
 460         return stateInfo;
 461     }
 462
 463     @Override
 464     public ITmfStateInterval querySingleState(long t, int attributeQuark)
 465             throws AttributeNotFoundException, TimeRangeException {
 466         ITmfStateInterval ret;
 467
 468         if (transState.hasInfoAboutStateOf(t, attributeQuark)) {
 469             ret = transState.getOngoingInterval(attributeQuark);
 470         } else {
 471             ret = backend.doSingularQuery(t, attributeQuark);
 472         }
 473
 474         /*
 475          * Return a fake interval if we could not find anything in the history.
 476          * We do NOT want to return 'null' here.
 477          */
 478         if (ret == null) {
 479             //logMissingInterval(attributeQuark, t);
 480             return new TmfStateInterval(t, this.getCurrentEndTime(),
 481                     attributeQuark, TmfStateValue.nullValue());
 482         }
 483         return ret;
 484     }
 485
 486     @Override
 487     public List<ITmfStateInterval> queryHistoryRange(int attributeQuark,
 488             long t1, long t2) throws TimeRangeException,
 489             AttributeNotFoundException {
 490         List<ITmfStateInterval> intervals;
 491         ITmfStateInterval currentInterval;
 492         long ts, tEnd;
 493
 494         /* Make sure the time range makes sense */
 495         if (t2 <= t1) {
 496             throw new TimeRangeException();
 497         }
 498
 499         /* Set the actual, valid end time of the range query */
 500         if (t2 > this.getCurrentEndTime()) {
 501             tEnd = this.getCurrentEndTime();
 502         } else {
 503             tEnd = t2;
 504         }
 505
 506         /* Get the initial state at time T1 */
 507         intervals = new ArrayList<ITmfStateInterval>();
 508         currentInterval = querySingleState(t1, attributeQuark);
 509         intervals.add(currentInterval);
 510
 511         /* Get the following state changes */
 512         ts = currentInterval.getEndTime();
 513         while (ts != -1 && ts < tEnd) {
 514             ts++; /* To "jump over" to the next state in the history */
 515             currentInterval = querySingleState(ts, attributeQuark);
 516             intervals.add(currentInterval);
 517             ts = currentInterval.getEndTime();
 518         }
 519         return intervals;
 520     }
 521
 522     @Override
 523     public List<ITmfStateInterval> queryHistoryRange(int attributeQuark,
 524             long t1, long t2, long resolution, IProgressMonitor monitor)
 525             throws TimeRangeException, AttributeNotFoundException {
 526         List<ITmfStateInterval> intervals;
 527         ITmfStateInterval currentInterval;
 528         long ts, tEnd;
 529
 530         if (monitor == null) {
 531             monitor = new NullProgressMonitor();
 532         }
 533
 534         /* Make sure the time range makes sense */
 535         if (t2 < t1 || resolution <= 0) {
 536             throw new TimeRangeException();
 537         }
 538
 539         /* Set the actual, valid end time of the range query */
 540         if (t2 > this.getCurrentEndTime()) {
 541             tEnd = this.getCurrentEndTime();
 542         } else {
 543             tEnd = t2;
 544         }
 545
 546         /* Get the initial state at time T1 */
 547         intervals = new ArrayList<ITmfStateInterval>();
 548         currentInterval = querySingleState(t1, attributeQuark);
 549         intervals.add(currentInterval);
 550
 551         /*
 552          * Iterate over the "resolution points". We skip unneeded queries in the
 553          * case the current interval is longer than the resolution.
 554          */
 555         for (ts = t1; (currentInterval.getEndTime() != -1) && (ts < tEnd);
 556                 ts += resolution) {
 557             if (monitor.isCanceled()) {
 558                 return intervals;
 559             }
 560             if (ts <= currentInterval.getEndTime()) {
 561                 continue;
 562             }
 563             currentInterval = querySingleState(ts, attributeQuark);
 564             intervals.add(currentInterval);
 565         }
 566
 567         /* Add the interval at t2, if it wasn't included already. */
 568         if (currentInterval.getEndTime() < tEnd) {
 569             currentInterval = querySingleState(tEnd, attributeQuark);
 570             intervals.add(currentInterval);
 571         }
 572         return intervals;
 573     }
 574
 575     //--------------------------------------------------------------------------
 576     //        Debug methods
 577     //--------------------------------------------------------------------------
 578
 579     static void logMissingInterval(int attribute, long timestamp) {
 580         Tracer.traceInfo("No data found in history for attribute " + //$NON-NLS-1$
 581                 attribute + " at time " + timestamp + //$NON-NLS-1$
 582                 ", returning dummy interval"); //$NON-NLS-1$
 583     }
 584
 585     /**
 586      * Print out the contents of the inner structures.
 587      *
 588      * @param writer
 589      *            The PrintWriter in which to print the output
 590      */
 591     public void debugPrint(PrintWriter writer) {
 592         attributeTree.debugPrint(writer);
 593         transState.debugPrint(writer);
 594         backend.debugPrint(writer);
 595     }
 596
 597 }