org.eclipse.tracecompass.tmf.core/src/org/eclipse/linuxtools/tmf/core/trace/indexer/checkpoint/TmfCheckpointIndexer.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012, 2014 Ericsson
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Francois Chouinard - Initial API and implementation
  11  *   Bernd Hufmann - Update way of broadcasting of TmfTraceUpdatedSignal
  12  *******************************************************************************/
  13
  14 package org.eclipse.linuxtools.tmf.core.trace.indexer.checkpoint;
  15
  16 import org.eclipse.core.runtime.IProgressMonitor;
  17 import org.eclipse.core.runtime.IStatus;
  18 import org.eclipse.core.runtime.Status;
  19 import org.eclipse.core.runtime.jobs.Job;
  20 import org.eclipse.linuxtools.internal.tmf.core.Messages;
  21 import org.eclipse.linuxtools.internal.tmf.core.trace.indexer.TmfMemoryIndex;
  22 import org.eclipse.linuxtools.tmf.core.component.TmfEventProvider;
  23 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  24 import org.eclipse.linuxtools.tmf.core.request.ITmfEventRequest;
  25 import org.eclipse.linuxtools.tmf.core.request.TmfEventRequest;
  26 import org.eclipse.linuxtools.tmf.core.signal.TmfTraceUpdatedSignal;
  27 import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
  28 import org.eclipse.linuxtools.tmf.core.timestamp.TmfTimeRange;
  29 import org.eclipse.linuxtools.tmf.core.trace.ITmfContext;
  30 import org.eclipse.linuxtools.tmf.core.trace.ITmfTrace;
  31 import org.eclipse.linuxtools.tmf.core.trace.ITmfTraceCompleteness;
  32 import org.eclipse.linuxtools.tmf.core.trace.indexer.ITmfTraceIndexer;
  33 import org.eclipse.linuxtools.tmf.core.trace.location.ITmfLocation;
  34
  35 /**
  36  * A simple indexer that manages the trace index as an array of trace
  37  * checkpoints. Checkpoints are stored in memory at fixed intervals (event rank) in
  38  * ascending timestamp order.
  39  * <p>
  40  * The goal being to access a random trace event reasonably fast from the user's
  41  * standpoint, picking the right interval value becomes a trade-off between speed
  42  * and memory usage (a shorter inter-event interval is faster but requires more
  43  * checkpoints).
  44  * <p>
  45  * Locating a specific checkpoint is trivial for both rank (rank % interval) and
  46  * timestamp (bsearch in the array).
  47  * *
  48  * @see ITmfTrace
  49  * @see ITmfEvent
  50  *
  51  * @author Francois Chouinard
  52  * @since 3.0
  53  */
  54 public class TmfCheckpointIndexer implements ITmfTraceIndexer {
  55
  56     // ------------------------------------------------------------------------
  57     // Attributes
  58     // ------------------------------------------------------------------------
  59
  60     /** The event trace to index */
  61     protected final ITmfTrace fTrace;
  62
  63     /** The interval between checkpoints */
  64     private final int fCheckpointInterval;
  65
  66     /** The event trace to index */
  67     private boolean fIsIndexing;
  68
  69     /**
  70      * The trace index. It is composed of checkpoints taken at intervals of
  71      * fCheckpointInterval events.
  72      */
  73     protected final ITmfCheckpointIndex fTraceIndex;
  74
  75     /**
  76      * The indexing request
  77      */
  78     private ITmfEventRequest fIndexingRequest = null;
  79
  80     // ------------------------------------------------------------------------
  81     // Construction
  82     // ------------------------------------------------------------------------
  83
  84     /**
  85      * Basic constructor that uses the default trace block size as checkpoints
  86      * intervals
  87      *
  88      * @param trace the trace to index
  89      */
  90     public TmfCheckpointIndexer(final ITmfTrace trace) {
  91         this(trace, TmfEventProvider.DEFAULT_BLOCK_SIZE);
  92     }
  93
  94     /**
  95      * Full trace indexer
  96      *
  97      * @param trace the trace to index
  98      * @param interval the checkpoints interval
  99      */
 100     public TmfCheckpointIndexer(final ITmfTrace trace, final int interval) {
 101         fTrace = trace;
 102         fCheckpointInterval = interval;
 103         fTraceIndex = createIndex(trace);
 104         fIsIndexing = false;
 105     }
 106
 107     /**
 108      * Creates the index instance. Classes extending this class
 109      * can override this to provide a different index implementation.
 110      *
 111      * @param trace the trace to index
 112      * @return the index
 113      * @since 3.0
 114      */
 115     protected ITmfCheckpointIndex createIndex(final ITmfTrace trace) {
 116         return new TmfMemoryIndex(trace);
 117     }
 118
 119     @Override
 120     public void dispose() {
 121         if ((fIndexingRequest != null) && !fIndexingRequest.isCompleted()) {
 122             fIndexingRequest.cancel();
 123         }
 124
 125         fTraceIndex.dispose();
 126     }
 127
 128     // ------------------------------------------------------------------------
 129     // ITmfTraceIndexer - isIndexing
 130     // ------------------------------------------------------------------------
 131
 132     @Override
 133     public boolean isIndexing() {
 134         return fIsIndexing;
 135     }
 136
 137     // ------------------------------------------------------------------------
 138     // ITmfTraceIndexer - buildIndex
 139     // ------------------------------------------------------------------------
 140
 141     /**
 142      * @since 2.0
 143      */
 144     @Override
 145     public void buildIndex(final long offset, final TmfTimeRange range, final boolean waitForCompletion) {
 146
 147         // Don't do anything if we are already indexing
 148         synchronized (fTraceIndex) {
 149             if (fIsIndexing) {
 150                 return;
 151             }
 152             fIsIndexing = true;
 153         }
 154
 155         // No need to build the index, it has been restored
 156         if (!fTraceIndex.isCreatedFromScratch()) {
 157             // Set some trace attributes that depends on indexing
 158             TmfTraceUpdatedSignal signal = new TmfTraceUpdatedSignal(this, fTrace, new TmfTimeRange(fTraceIndex.getTimeRange().getStartTime(), fTraceIndex.getTimeRange().getEndTime()), fTraceIndex.getNbEvents());
 159             if (waitForCompletion) {
 160                 fTrace.broadcast(signal);
 161             } else {
 162                 fTrace.broadcastAsync(signal);
 163             }
 164             fIsIndexing = false;
 165             return;
 166         }
 167
 168         // The monitoring job
 169         final Job job = new Job("Indexing " + fTrace.getName() + "...") { //$NON-NLS-1$ //$NON-NLS-2$
 170             @Override
 171             protected IStatus run(final IProgressMonitor monitor) {
 172                 monitor.beginTask("", IProgressMonitor.UNKNOWN); //$NON-NLS-1$
 173                 while (!monitor.isCanceled()) {
 174                     try {
 175                         long prevNbEvents = fTrace.getNbEvents();
 176                         Thread.sleep(250);
 177                         long nbEvents = fTrace.getNbEvents();
 178                         setName(Messages.TmfCheckpointIndexer_Indexing + ' ' + fTrace.getName() + " (" + nbEvents + ")"); //$NON-NLS-1$ //$NON-NLS-2$
 179                         // setName doesn't refresh the UI, setTaskName does
 180                         long rate = (nbEvents - prevNbEvents) * 4;
 181                         monitor.setTaskName(rate + " " + Messages.TmfCheckpointIndexer_EventsPerSecond); //$NON-NLS-1$
 182                     } catch (final InterruptedException e) {
 183                         return Status.OK_STATUS;
 184                     }
 185                 }
 186                 monitor.done();
 187                 return Status.OK_STATUS;
 188             }
 189         };
 190         job.setSystem(!isCompleteTrace(fTrace));
 191         job.schedule();
 192
 193         // Build a background request for all the trace data. The index is
 194         // updated as we go by readNextEvent().
 195         fIndexingRequest = new TmfEventRequest(ITmfEvent.class,
 196                 range, offset, ITmfEventRequest.ALL_DATA,
 197                 ITmfEventRequest.ExecutionType.BACKGROUND) {
 198             @Override
 199             public void handleData(final ITmfEvent event) {
 200                 super.handleData(event);
 201                 // Update the trace status at regular intervals
 202                 if ((getNbRead() % fCheckpointInterval) == 0) {
 203                     updateTraceStatus();
 204                 }
 205             }
 206
 207             @Override
 208             public void handleSuccess() {
 209                 fTraceIndex.setTimeRange(fTrace.getTimeRange());
 210                 fTraceIndex.setNbEvents(fTrace.getNbEvents());
 211                 if (isCompleteTrace(fTrace)) {
 212                     fTraceIndex.setIndexComplete();
 213                 }
 214                 updateTraceStatus();
 215             }
 216
 217             @Override
 218             public void handleCompleted() {
 219                 job.cancel();
 220                 super.handleCompleted();
 221                 fIsIndexing = false;
 222             }
 223
 224             private void updateTraceStatus() {
 225                 if (fTrace.getNbEvents() > 0) {
 226                     signalNewTimeRange(fTrace.getStartTime(), fTrace.getEndTime());
 227                 }
 228             }
 229         };
 230
 231         // Submit the request and wait for completion if required
 232         fTrace.sendRequest(fIndexingRequest);
 233         if (waitForCompletion) {
 234             try {
 235                 fIndexingRequest.waitForCompletion();
 236             } catch (final InterruptedException e) {
 237             }
 238         }
 239     }
 240
 241     /**
 242      * Notify the interested parties that the trace time range has changed
 243      *
 244      * @param startTime the new start time
 245      * @param endTime the new end time
 246      */
 247     private void signalNewTimeRange(final ITmfTimestamp startTime, final ITmfTimestamp endTime) {
 248         fTrace.broadcast(new TmfTraceUpdatedSignal(fTrace, fTrace, new TmfTimeRange(startTime, endTime), fTrace.getNbEvents()));
 249     }
 250
 251     // ------------------------------------------------------------------------
 252     // ITmfTraceIndexer - updateIndex
 253     // ------------------------------------------------------------------------
 254
 255     /**
 256      * @since 2.0
 257      */
 258     @Override
 259     public synchronized void updateIndex(final ITmfContext context, final ITmfTimestamp timestamp) {
 260         if ((context.getRank() % fCheckpointInterval) == 0) {
 261             // Determine the table position
 262             final long position = context.getRank() / fCheckpointInterval;
 263             // Add new entry at proper location (if empty)
 264             if (fTraceIndex.size() == position) {
 265                 fTraceIndex.insert(new TmfCheckpoint(timestamp, context.getLocation(), position));
 266             }
 267         }
 268     }
 269
 270     // ------------------------------------------------------------------------
 271     // ITmfTraceIndexer - seekIndex
 272     // ------------------------------------------------------------------------
 273
 274     /**
 275      * @since 2.0
 276      */
 277     @Override
 278     public synchronized ITmfContext seekIndex(final ITmfTimestamp timestamp) {
 279
 280         // A null timestamp indicates to seek the first event
 281         if (timestamp == null) {
 282             return fTrace.seekEvent(0);
 283         }
 284
 285         // Find the checkpoint at or before the requested timestamp.
 286         // In the very likely event that the timestamp is not at a checkpoint
 287         // boundary, bsearch will return index = (- (insertion point + 1)).
 288         // It is then trivial to compute the index of the previous checkpoint.
 289         long index = fTraceIndex.binarySearch(new TmfCheckpoint(timestamp, null, 0));
 290         if (index < 0) {
 291             index = Math.max(0, -(index + 2));
 292         } else {
 293             // If timestamp was in the list, use previous index to be able to find the
 294             // first event with the same timestamp before the checkpoint
 295             index = Math.max(0, index - 1);
 296         }
 297
 298         // Position the trace at the checkpoint
 299         return restoreCheckpoint(index);
 300     }
 301
 302     @Override
 303     public ITmfContext seekIndex(final long rank) {
 304
 305         // A rank < 0 indicates to seek the first event
 306         if (rank < 0) {
 307             return fTrace.seekEvent(0);
 308         }
 309
 310         // Find the checkpoint at or before the requested rank.
 311         final int index = (int) rank / fCheckpointInterval;
 312
 313         // Position the trace at the checkpoint
 314         return restoreCheckpoint(index);
 315     }
 316
 317     /**
 318      * Position the trace at the given checkpoint
 319      *
 320      * @param checkpoint the checkpoint index
 321      * @return the corresponding context
 322      */
 323     private ITmfContext restoreCheckpoint(final long checkpoint) {
 324         ITmfLocation location = null;
 325         long index = 0;
 326         synchronized (fTraceIndex) {
 327             if (!fTraceIndex.isEmpty()) {
 328                 index = checkpoint;
 329                 if (index >= fTraceIndex.size()) {
 330                     index = fTraceIndex.size() - 1;
 331                 }
 332                 location = fTraceIndex.get(index).getLocation();
 333             }
 334         }
 335         final ITmfContext context = fTrace.seekEvent(location);
 336         context.setRank(index * fCheckpointInterval);
 337         return context;
 338     }
 339
 340     // ------------------------------------------------------------------------
 341     // Getters
 342     // ------------------------------------------------------------------------
 343
 344     /**
 345      * @return the trace index
 346      * @since 3.0
 347      */
 348     protected ITmfCheckpointIndex getTraceIndex() {
 349         return fTraceIndex;
 350     }
 351
 352     private static boolean isCompleteTrace(ITmfTrace trace) {
 353         return !(trace instanceof ITmfTraceCompleteness) || ((ITmfTraceCompleteness)trace).isComplete();
 354     }
 355 }