org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/tmf/core/trace/TmfCheckpointIndexer.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012 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  *******************************************************************************/
  12
  13 package org.eclipse.linuxtools.tmf.core.trace;
  14
  15 import java.util.Collections;
  16 import java.util.Vector;
  17
  18 import org.eclipse.core.runtime.IProgressMonitor;
  19 import org.eclipse.core.runtime.IStatus;
  20 import org.eclipse.core.runtime.Status;
  21 import org.eclipse.core.runtime.jobs.Job;
  22 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  23 import org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp;
  24 import org.eclipse.linuxtools.tmf.core.event.TmfTimeRange;
  25 import org.eclipse.linuxtools.tmf.core.request.ITmfDataRequest;
  26 import org.eclipse.linuxtools.tmf.core.request.ITmfEventRequest;
  27 import org.eclipse.linuxtools.tmf.core.request.TmfDataRequest;
  28 import org.eclipse.linuxtools.tmf.core.request.TmfEventRequest;
  29 import org.eclipse.linuxtools.tmf.core.signal.TmfTraceUpdatedSignal;
  30
  31 /**
  32  * A simple trace indexer that builds an array of trace checkpoints. Checkpoints
  33  * are stored at fixed intervals (event rank) in ascending timestamp order.
  34  * <p>
  35  * The goal being to access a random trace event reasonably fast from the user's
  36  * standpoint, picking the right interval value becomes a trade-off between speed
  37  * and memory usage (a shorter inter-event interval is faster but requires more
  38  * checkpoints).
  39  * <p>
  40  * Locating a specific checkpoint is trivial for both rank (rank % interval) and
  41  * timestamp (bsearch in the array).
  42  *
  43  * @since 1.0
  44  * @version 1.0
  45  * @author Francois Chouinard
  46  *
  47  * @see ITmfTraceIndexer
  48  * @see ITmfTrace
  49  * @see ITmfEvent
  50  */
  51 public class TmfCheckpointIndexer<T extends ITmfTrace<ITmfEvent>> implements ITmfTraceIndexer<T> {
  52
  53     // ------------------------------------------------------------------------
  54     // Attributes
  55     // ------------------------------------------------------------------------
  56
  57     /**
  58      * The event trace to index
  59      */
  60     private final ITmfTrace<ITmfEvent> fTrace;
  61
  62     /**
  63      * The interval between checkpoints
  64      */
  65     protected final int fCheckpointInterval;
  66
  67     /**
  68      * The trace index. It is composed of checkpoints taken at intervals of
  69      * fCheckpointInterval events.
  70      */
  71     protected final Vector<TmfCheckpoint> fTraceIndex;
  72
  73     // ------------------------------------------------------------------------
  74     // Construction
  75     // ------------------------------------------------------------------------
  76
  77     /**
  78      * Basic constructor that uses the default trace block size as checkpoints
  79      * intervals
  80      *
  81      * @param trace the trace to index
  82      */
  83     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace) {
  84         this(trace, TmfTrace.DEFAULT_BLOCK_SIZE);
  85     }
  86
  87     /**
  88      * Full trace indexer
  89      *
  90      * @param trace the trace to index
  91      * @param interval the checkpoints interval
  92      */
  93     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace, final int interval) {
  94         fTrace = trace;
  95         fCheckpointInterval = interval;
  96         fTraceIndex = new Vector<TmfCheckpoint>();
  97     }
  98
  99     // ------------------------------------------------------------------------
 100     // ITmfTraceIndexer - buildIndex
 101     // ------------------------------------------------------------------------
 102
 103     /* (non-Javadoc)
 104      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTrace#indexTrace(boolean)
 105      *
 106      * The index is a list of contexts that point to events at regular interval
 107      * (rank-wise) in the trace. After it is built, the index can be used to
 108      * quickly access any event by rank or timestamp (using seekIndex()).
 109      *
 110      * The index is built simply by reading the trace
 111      */
 112     @Override
 113     public void buildIndex(final boolean waitForCompletion) {
 114
 115         // The monitoring job
 116         final Job job = new Job("Indexing " + fTrace.getName() + "...") { //$NON-NLS-1$ //$NON-NLS-2$
 117             @Override
 118             protected IStatus run(final IProgressMonitor monitor) {
 119                 while (!monitor.isCanceled()) {
 120                     try {
 121                         Thread.sleep(100);
 122                     } catch (final InterruptedException e) {
 123                         return Status.OK_STATUS;
 124                     }
 125                 }
 126                 monitor.done();
 127                 return Status.OK_STATUS;
 128             }
 129         };
 130         job.schedule();
 131
 132         // Clear the checkpoints
 133         fTraceIndex.clear();
 134
 135         // Build a background request for all the trace data. The index is
 136         // updated as we go by getNextEvent().
 137         final ITmfEventRequest<ITmfEvent> request = new TmfEventRequest<ITmfEvent>(ITmfEvent.class, TmfTimeRange.ETERNITY,
 138                 TmfDataRequest.ALL_DATA, fCheckpointInterval, ITmfDataRequest.ExecutionType.BACKGROUND)
 139         {
 140             ITmfTimestamp startTime = null;
 141             ITmfTimestamp lastTime = null;
 142
 143             @Override
 144             public void handleData(final ITmfEvent event) {
 145                 super.handleData(event);
 146                 if (event != null) {
 147                     final ITmfTimestamp timestamp = event.getTimestamp();
 148                     if (startTime == null) {
 149                         startTime = timestamp.clone();
 150                     }
 151                     lastTime = timestamp.clone();
 152
 153                     // Update the trace status at regular intervals
 154                     if ((getNbRead() % fCheckpointInterval) == 0) {
 155                         updateTraceStatus();
 156                     }
 157                 }
 158             }
 159
 160             @Override
 161             public void handleSuccess() {
 162                 updateTraceStatus();
 163             }
 164
 165             @Override
 166             public void handleCompleted() {
 167                 job.cancel();
 168                 super.handleCompleted();
 169             }
 170
 171             private void updateTraceStatus() {
 172                 if (getNbRead() != 0) {
 173                     signalNewTimeRange(startTime, lastTime);
 174                 }
 175             }
 176         };
 177
 178         // Submit the request and wait for completion if required
 179         fTrace.sendRequest(request);
 180         if (waitForCompletion) {
 181             try {
 182                 request.waitForCompletion();
 183             } catch (final InterruptedException e) {
 184             }
 185         }
 186     }
 187
 188     /**
 189      * Notify the interested parties that the trace time range has changed
 190      *
 191      * @param startTime the new start time
 192      * @param endTime the new end time
 193      */
 194     private void signalNewTimeRange(final ITmfTimestamp startTime, final ITmfTimestamp endTime) {
 195         fTrace.broadcast(new TmfTraceUpdatedSignal(fTrace, fTrace, new TmfTimeRange(startTime, endTime)));
 196     }
 197
 198     // ------------------------------------------------------------------------
 199     // ITmfTraceIndexer - updateIndex
 200     // ------------------------------------------------------------------------
 201
 202     /* (non-Javadoc)
 203      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#updateIndex(org.eclipse.linuxtools.tmf.core.trace.ITmfContext, org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 204      */
 205     @Override
 206     public synchronized void updateIndex(final ITmfContext context, final ITmfTimestamp timestamp) {
 207         final long rank = context.getRank();
 208         if ((rank % fCheckpointInterval) == 0) {
 209             // Determine the table position
 210             final long position = rank / fCheckpointInterval;
 211             // Add new entry at proper location (if empty)
 212             if (fTraceIndex.size() == position) {
 213                 final ITmfLocation<?> location = context.getLocation().clone();
 214                 fTraceIndex.add(new TmfCheckpoint(timestamp.clone(), location));
 215             }
 216         }
 217     }
 218
 219     // ------------------------------------------------------------------------
 220     // ITmfTraceIndexer - seekIndex
 221     // ------------------------------------------------------------------------
 222
 223     /* (non-Javadoc)
 224      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 225      */
 226     @Override
 227     public synchronized ITmfContext seekIndex(final ITmfTimestamp timestamp) {
 228
 229         // A null timestamp indicates to seek the first event
 230         if (timestamp == null)
 231             return fTrace.seekEvent(0);
 232
 233         // Find the checkpoint at or before the requested timestamp.
 234         // In the very likely event that the timestamp is not at a checkpoint
 235         // boundary, bsearch will return index = (- (insertion point + 1)).
 236         // It is then trivial to compute the index of the previous checkpoint.
 237         int index = Collections.binarySearch(fTraceIndex, new TmfCheckpoint(timestamp, null));
 238         if (index < 0) {
 239             index = Math.max(0, -(index + 2));
 240         }
 241
 242         // Position the trace at the checkpoint
 243         return seekCheckpoint(index);
 244     }
 245
 246     /* (non-Javadoc)
 247      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(long)
 248      */
 249     @Override
 250     public ITmfContext seekIndex(final long rank) {
 251
 252       // A rank < 0 indicates to seek the first event
 253       if (rank < 0)
 254           return fTrace.seekEvent(0);
 255
 256       // Find the checkpoint at or before the requested rank.
 257       final int index = (int) rank / fCheckpointInterval;
 258
 259       // Position the trace at the checkpoint
 260       return seekCheckpoint(index);
 261     }
 262
 263     /**
 264      * Position the trace at the given checkpoint
 265      *
 266      * @param index
 267      *            the checkpoint index
 268      * @return the corresponding context
 269      */
 270     private ITmfContext seekCheckpoint(int index) {
 271         ITmfLocation<?> location;
 272         synchronized (fTraceIndex) {
 273             if (!fTraceIndex.isEmpty()) {
 274                 if (index >= fTraceIndex.size()) {
 275                     index = fTraceIndex.size() - 1;
 276                 }
 277                 location = fTraceIndex.elementAt(index).getLocation();
 278             } else {
 279                 location = null;
 280             }
 281         }
 282         final ITmfContext context = fTrace.seekEvent(location);
 283         context.setRank((long) index * fCheckpointInterval);
 284         return context;
 285     }
 286
 287 }