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