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.statesystem.IStateSystemQuerier2;
  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 IStateSystemBuilder, IStateSystemQuerier2{
  49
  50     /* References to the inner structures */
  51     private final AttributeTree attributeTree;
  52     private final TransientState transState;
  53     private final IStateHistoryBackend backend;
  54
  55     /**
  56      * General constructor
  57      *
  58      * @param backend
  59      *            The "state history storage" backend to use.
  60      * @param newFile
  61      *            Put true if this is a new history started from scratch. It is
  62      *            used to tell the state system where to get its attribute tree.
  63      * @throws IOException
  64      *             If there was a problem creating the new history file
  65      */
  66     public StateSystem(IStateHistoryBackend backend, boolean newFile)
  67             throws IOException {
  68         this.backend = backend;
  69         this.transState = new TransientState(backend);
  70
  71         if (newFile) {
  72             attributeTree = new AttributeTree(this);
  73         } else {
  74             /* We're opening an existing file */
  75             this.attributeTree = new AttributeTree(this, backend.supplyAttributeTreeReader());
  76             transState.setInactive();
  77         }
  78     }
  79
  80     //--------------------------------------------------------------------------
  81     //        General methods related to the attribute tree
  82     //--------------------------------------------------------------------------
  83
  84     /**
  85      * Method used by the attribute tree when creating new attributes, to keep
  86      * the attribute count in the transient state in sync.
  87      */
  88     void addEmptyAttribute() {
  89         transState.addEmptyEntry();
  90     }
  91
  92     @Override
  93     public int getNbAttributes() {
  94         return attributeTree.getNbAttributes();
  95     }
  96
  97     @Override
  98     public String getAttributeName(int attributeQuark) {
  99         return attributeTree.getAttributeName(attributeQuark);
 100     }
 101
 102     @Override
 103     public String getFullAttributePath(int attributeQuark) {
 104         return attributeTree.getFullAttributeName(attributeQuark);
 105     }
 106
 107     //--------------------------------------------------------------------------
 108     //        Methods related to the storage backend
 109     //--------------------------------------------------------------------------
 110
 111     @Override
 112     public long getStartTime() {
 113         return backend.getStartTime();
 114     }
 115
 116     @Override
 117     public long getCurrentEndTime() {
 118         return backend.getEndTime();
 119     }
 120
 121     @Override
 122     public void closeHistory(long endTime) throws TimeRangeException {
 123         File attributeTreeFile;
 124         long attributeTreeFilePos;
 125         long realEndTime = endTime;
 126
 127         if (realEndTime < backend.getEndTime()) {
 128             /*
 129              * This can happen (empty nodes pushing the border further, etc.)
 130              * but shouldn't be too big of a deal.
 131              */
 132             realEndTime = backend.getEndTime();
 133         }
 134         transState.closeTransientState(realEndTime);
 135         backend.finishedBuilding(realEndTime);
 136
 137         attributeTreeFile = backend.supplyAttributeTreeWriterFile();
 138         attributeTreeFilePos = backend.supplyAttributeTreeWriterFilePosition();
 139         if (attributeTreeFile != null) {
 140             /*
 141              * If null was returned, we simply won't save the attribute tree,
 142              * too bad!
 143              */
 144             attributeTree.writeSelf(attributeTreeFile, attributeTreeFilePos);
 145         }
 146     }
 147
 148     //--------------------------------------------------------------------------
 149     //        Quark-retrieving methods
 150     //--------------------------------------------------------------------------
 151
 152     @Override
 153     public int getQuarkAbsolute(String... attribute)
 154             throws AttributeNotFoundException {
 155         return attributeTree.getQuarkDontAdd(-1, attribute);
 156     }
 157
 158     @Override
 159     public int getQuarkAbsoluteAndAdd(String... attribute) {
 160         return attributeTree.getQuarkAndAdd(-1, attribute);
 161     }
 162
 163     @Override
 164     public int getQuarkRelative(int startingNodeQuark, String... subPath)
 165             throws AttributeNotFoundException {
 166         return attributeTree.getQuarkDontAdd(startingNodeQuark, subPath);
 167     }
 168
 169     @Override
 170     public int getQuarkRelativeAndAdd(int startingNodeQuark, String... subPath) {
 171         return attributeTree.getQuarkAndAdd(startingNodeQuark, subPath);
 172     }
 173
 174     @Override
 175     public List<Integer> getSubAttributes(int quark, boolean recursive)
 176             throws AttributeNotFoundException {
 177         return attributeTree.getSubAttributes(quark, recursive);
 178     }
 179
 180     @Override
 181     public List<Integer> getQuarks(String... pattern) {
 182         List<Integer> quarks = new LinkedList<Integer>();
 183         List<String> prefix = new LinkedList<String>();
 184         List<String> suffix = new LinkedList<String>();
 185         boolean split = false;
 186         String[] prefixStr;
 187         String[] suffixStr;
 188         List<Integer> directChildren;
 189         int startingAttribute;
 190
 191         /* Fill the "prefix" and "suffix" parts of the pattern around the '*' */
 192         for (String entry : pattern) {
 193             if (entry.equals("*")) { //$NON-NLS-1$
 194                 if (split) {
 195                     /*
 196                      * Split was already true? This means there was more than
 197                      * one wildcard. This is not supported, return an empty
 198                      * list.
 199                      */
 200                     return quarks;
 201                 }
 202                 split = true;
 203                 continue;
 204             }
 205
 206             if (split) {
 207                 suffix.add(entry);
 208             } else {
 209                 prefix.add(entry);
 210             }
 211         }
 212         prefixStr = prefix.toArray(new String[prefix.size()]);
 213         suffixStr = suffix.toArray(new String[suffix.size()]);
 214
 215         /*
 216          * If there was no wildcard, we'll only return the one matching
 217          * attribute, if there is one.
 218          */
 219         if (split == false) {
 220             int quark;
 221             try {
 222                 quark = getQuarkAbsolute(prefixStr);
 223             } catch (AttributeNotFoundException e) {
 224                 /* It's fine, we'll just return the empty List */
 225                 return quarks;
 226             }
 227             quarks.add(quark);
 228             return quarks;
 229         }
 230
 231         try {
 232             if (prefix.size() == 0) {
 233                 /*
 234                  * If 'prefix' is empty, this means the wildcard was the first
 235                  * element. Look for the root node's sub-attributes.
 236                  */
 237                 startingAttribute = -1;
 238             } else {
 239                 startingAttribute = getQuarkAbsolute(prefixStr);
 240             }
 241             directChildren = attributeTree.getSubAttributes(startingAttribute,
 242                     false);
 243         } catch (AttributeNotFoundException e) {
 244             /* That attribute path did not exist, return the empty array */
 245             return quarks;
 246         }
 247
 248         /*
 249          * Iterate of all the sub-attributes, and only keep those who match the
 250          * 'suffix' part of the initial pattern.
 251          */
 252         for (int childQuark : directChildren) {
 253             int matchingQuark;
 254             try {
 255                 matchingQuark = getQuarkRelative(childQuark, suffixStr);
 256             } catch (AttributeNotFoundException e) {
 257                 continue;
 258             }
 259             quarks.add(matchingQuark);
 260         }
 261
 262         return quarks;
 263     }
 264
 265     //--------------------------------------------------------------------------
 266     //        Methods related to insertions in the history
 267     //--------------------------------------------------------------------------
 268
 269     @Override
 270     public void modifyAttribute(long t, ITmfStateValue value, int attributeQuark)
 271             throws TimeRangeException, AttributeNotFoundException,
 272             StateValueTypeException {
 273         transState.processStateChange(t, value, attributeQuark);
 274     }
 275
 276     @Override
 277     public void incrementAttribute(long t, int attributeQuark)
 278             throws StateValueTypeException, TimeRangeException,
 279             AttributeNotFoundException {
 280         int prevValue = queryOngoingState(attributeQuark).unboxInt();
 281         if (prevValue == -1) {
 282             /* if the attribute was previously null, start counting at 0 */
 283             prevValue = 0;
 284         }
 285         modifyAttribute(t, TmfStateValue.newValueInt(prevValue + 1),
 286                 attributeQuark);
 287     }
 288
 289     @Override
 290     public void pushAttribute(long t, ITmfStateValue value, int attributeQuark)
 291             throws TimeRangeException, AttributeNotFoundException,
 292             StateValueTypeException {
 293         Integer stackDepth = 0;
 294         int subAttributeQuark;
 295         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 296
 297         if (previousSV.isNull()) {
 298             /*
 299              * If the StateValue was null, this means this is the first time we
 300              * use this attribute. Leave stackDepth at 0.
 301              */
 302         } else if (previousSV.getType() == 0) {
 303             /* Previous value was an integer, all is good, use it */
 304             stackDepth = previousSV.unboxInt();
 305         } else {
 306             /* Previous state of this attribute was another type? Not good! */
 307             throw new StateValueTypeException();
 308         }
 309
 310         if (stackDepth >= 10) {
 311             /*
 312              * Limit stackDepth to 10, to avoid having Attribute Trees grow out
 313              * of control due to buggy insertions
 314              */
 315             String message = "Stack limit reached, not pushing"; //$NON-NLS-1$
 316             throw new AttributeNotFoundException(message);
 317         }
 318
 319         stackDepth++;
 320         subAttributeQuark = getQuarkRelativeAndAdd(attributeQuark,
 321                 stackDepth.toString());
 322
 323         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth),
 324                 attributeQuark);
 325         modifyAttribute(t, value, subAttributeQuark);
 326     }
 327
 328     @Override
 329     public void popAttribute(long t, int attributeQuark)
 330             throws AttributeNotFoundException, TimeRangeException,
 331             StateValueTypeException {
 332         Integer stackDepth;
 333         int subAttributeQuark;
 334         ITmfStateValue previousSV = transState.getOngoingStateValue(attributeQuark);
 335
 336         if (previousSV.isNull()) {
 337             /* Same as if stackDepth == 0, see below */
 338             return;
 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         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;
 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         subAttributeQuark = getQuarkRelative(attributeQuark,
 369                 stackDepth.toString());
 370
 371         stackDepth--;
 372         modifyAttribute(t, TmfStateValue.newValueInt(stackDepth),
 373                 attributeQuark);
 374         removeAttribute(t, subAttributeQuark);
 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) throws TimeRangeException,
 525             AttributeNotFoundException {
 526         return queryHistoryRange(attributeQuark, t1, t2, resolution, new NullProgressMonitor());
 527     }
 528
 529     @Override
 530     public List<ITmfStateInterval> queryHistoryRange(int attributeQuark,
 531             long t1, long t2, long resolution, IProgressMonitor monitor) throws TimeRangeException,
 532             AttributeNotFoundException {
 533         List<ITmfStateInterval> intervals;
 534         ITmfStateInterval currentInterval;
 535         long ts, tEnd;
 536
 537         /* Make sure the time range makes sense */
 538         if (t2 < t1 || resolution <= 0) {
 539             throw new TimeRangeException();
 540         }
 541
 542         /* Set the actual, valid end time of the range query */
 543         if (t2 > this.getCurrentEndTime()) {
 544             tEnd = this.getCurrentEndTime();
 545         } else {
 546             tEnd = t2;
 547         }
 548
 549         /* Get the initial state at time T1 */
 550         intervals = new ArrayList<ITmfStateInterval>();
 551         currentInterval = querySingleState(t1, attributeQuark);
 552         intervals.add(currentInterval);
 553
 554         /*
 555          * Iterate over the "resolution points". We skip unneeded queries in the
 556          * case the current interval is longer than the resolution.
 557          */
 558         for (ts = t1; (currentInterval.getEndTime() != -1) && (ts < tEnd);
 559                 ts += resolution) {
 560             if (monitor.isCanceled()) {
 561                 return intervals;
 562             }
 563             if (ts <= currentInterval.getEndTime()) {
 564                 continue;
 565             }
 566             currentInterval = querySingleState(ts, attributeQuark);
 567             intervals.add(currentInterval);
 568         }
 569
 570         /* Add the interval at t2, if it wasn't included already. */
 571         if (currentInterval.getEndTime() < tEnd) {
 572             currentInterval = querySingleState(tEnd, attributeQuark);
 573             intervals.add(currentInterval);
 574         }
 575         return intervals;
 576     }
 577
 578     //--------------------------------------------------------------------------
 579     //        Debug methods
 580     //--------------------------------------------------------------------------
 581
 582     static void logMissingInterval(int attribute, long timestamp) {
 583         Tracer.traceInfo("No data found in history for attribute " + //$NON-NLS-1$
 584                 attribute + " at time " + timestamp + //$NON-NLS-1$
 585                 ", returning dummy interval"); //$NON-NLS-1$
 586     }
 587
 588     /**
 589      * Print out the contents of the inner structures.
 590      *
 591      * @param writer
 592      *            The PrintWriter in which to print the output
 593      */
 594     public void debugPrint(PrintWriter writer) {
 595         attributeTree.debugPrint(writer);
 596         transState.debugPrint(writer);
 597         backend.debugPrint(writer);
 598     }
 599
 600 }