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.ArrayList;
  16 import java.util.Collections;
  17 import java.util.List;
  18
  19 import org.eclipse.core.runtime.IProgressMonitor;
  20 import org.eclipse.core.runtime.IStatus;
  21 import org.eclipse.core.runtime.Status;
  22 import org.eclipse.core.runtime.jobs.Job;
  23 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  24 import org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp;
  25 import org.eclipse.linuxtools.tmf.core.event.TmfTimeRange;
  26 import org.eclipse.linuxtools.tmf.core.request.ITmfDataRequest;
  27 import org.eclipse.linuxtools.tmf.core.request.ITmfEventRequest;
  28 import org.eclipse.linuxtools.tmf.core.request.TmfDataRequest;
  29 import org.eclipse.linuxtools.tmf.core.request.TmfEventRequest;
  30 import org.eclipse.linuxtools.tmf.core.signal.TmfTraceUpdatedSignal;
  31
  32 /**
  33  * A simple indexer that manages the trace index as an array of trace
  34  * checkpoints. Checkpoints are stored at fixed intervals (event rank) in
  35  * 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  * @version 1.0
  46  * @author Francois Chouinard
  47  *
  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     // The event trace to index
  58     private final ITmfTrace<ITmfEvent> fTrace;
  59
  60     // The interval between checkpoints
  61     private final int fCheckpointInterval;
  62
  63     // The event trace to index
  64     private boolean fIsIndexing;
  65
  66     /**
  67      * The trace index. It is composed of checkpoints taken at intervals of
  68      * fCheckpointInterval events.
  69      */
  70     private final List<TmfCheckpoint> fTraceIndex;
  71
  72     /**
  73      * The indexing request
  74      */
  75     private ITmfEventRequest<ITmfEvent> fIndexingRequest = null;
  76
  77     // ------------------------------------------------------------------------
  78     // Construction
  79     // ------------------------------------------------------------------------
  80
  81     /**
  82      * Basic constructor that uses the default trace block size as checkpoints
  83      * intervals
  84      *
  85      * @param trace the trace to index
  86      */
  87     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace) {
  88         this(trace, TmfTrace.DEFAULT_BLOCK_SIZE);
  89     }
  90
  91     /**
  92      * Full trace indexer
  93      *
  94      * @param trace the trace to index
  95      * @param interval the checkpoints interval
  96      */
  97     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace, final int interval) {
  98         fTrace = trace;
  99         fCheckpointInterval = interval;
 100         fTraceIndex = new ArrayList<TmfCheckpoint>();
 101         fIsIndexing = false;
 102     }
 103
 104     /* (non-Javadoc)
 105      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#dispose()
 106      */
 107     @Override
 108     public void dispose() {
 109         if ((fIndexingRequest != null) && !fIndexingRequest.isCompleted()) {
 110             fIndexingRequest.cancel();
 111             fTraceIndex.clear();
 112         }
 113     }
 114
 115     // ------------------------------------------------------------------------
 116     // ITmfTraceIndexer - isIndexing
 117     // ------------------------------------------------------------------------
 118
 119     /* (non-Javadoc)
 120      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#isIndexing()
 121      */
 122     @Override
 123     public boolean isIndexing() {
 124         return fIsIndexing;
 125     }
 126
 127     // ------------------------------------------------------------------------
 128     // ITmfTraceIndexer - buildIndex
 129     // ------------------------------------------------------------------------
 130
 131     /* (non-Javadoc)
 132      *
 133      * The index is a list of contexts that point to events at regular interval
 134      * (rank-wise) in the trace. After it is built, the index can be used to
 135      * quickly access any event by rank or timestamp (using seekIndex()).
 136      *
 137      * The index is built simply by reading the trace
 138      *
 139      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#buildIndex(long, org.eclipse.linuxtools.tmf.core.event.TmfTimeRange, boolean)
 140      */
 141     @Override
 142     public void buildIndex(final long offset, final TmfTimeRange range, final boolean waitForCompletion) {
 143
 144         // Don't do anything if we are already indexing
 145         synchronized (fTraceIndex) {
 146             if (fIsIndexing) {
 147                 return;
 148             }
 149             fIsIndexing = true;
 150         }
 151
 152         // The monitoring job
 153         final Job job = new Job("Indexing " + fTrace.getName() + "...") { //$NON-NLS-1$ //$NON-NLS-2$
 154             @Override
 155             protected IStatus run(final IProgressMonitor monitor) {
 156                 while (!monitor.isCanceled()) {
 157                     try {
 158                         Thread.sleep(100);
 159                     } catch (final InterruptedException e) {
 160                         return Status.OK_STATUS;
 161                     }
 162                 }
 163                 monitor.done();
 164                 return Status.OK_STATUS;
 165             }
 166         };
 167         job.schedule();
 168
 169         // Clear the checkpoints
 170         fTraceIndex.clear();
 171
 172         // Build a background request for all the trace data. The index is
 173         // updated as we go by readNextEvent().
 174         fIndexingRequest = new TmfEventRequest<ITmfEvent>(ITmfEvent.class,
 175                 range, offset, TmfDataRequest.ALL_DATA, fCheckpointInterval, ITmfDataRequest.ExecutionType.BACKGROUND)
 176         {
 177             private ITmfTimestamp startTime = null;
 178             private ITmfTimestamp lastTime = null;
 179
 180             @Override
 181             public void handleData(final ITmfEvent event) {
 182                 super.handleData(event);
 183                 if (event != null) {
 184                     final ITmfTimestamp timestamp = event.getTimestamp();
 185                     if (startTime == null) {
 186                         startTime = timestamp.clone();
 187                     }
 188                     lastTime = timestamp.clone();
 189
 190                     // Update the trace status at regular intervals
 191                     if ((getNbRead() % fCheckpointInterval) == 0) {
 192                         updateTraceStatus();
 193                     }
 194                 }
 195             }
 196
 197             @Override
 198             public void handleSuccess() {
 199                 updateTraceStatus();
 200             }
 201
 202             @Override
 203             public void handleCompleted() {
 204                 job.cancel();
 205                 super.handleCompleted();
 206                 fIsIndexing = false;
 207             }
 208
 209             private void updateTraceStatus() {
 210                 if (getNbRead() != 0) {
 211                     signalNewTimeRange(startTime, lastTime);
 212                 }
 213             }
 214         };
 215
 216         // Submit the request and wait for completion if required
 217         fTrace.sendRequest(fIndexingRequest);
 218         if (waitForCompletion) {
 219             try {
 220                 fIndexingRequest.waitForCompletion();
 221             } catch (final InterruptedException e) {
 222             }
 223         }
 224     }
 225
 226     /**
 227      * Notify the interested parties that the trace time range has changed
 228      *
 229      * @param startTime the new start time
 230      * @param endTime the new end time
 231      */
 232     private void signalNewTimeRange(final ITmfTimestamp startTime, final ITmfTimestamp endTime) {
 233         fTrace.broadcast(new TmfTraceUpdatedSignal(fTrace, fTrace, new TmfTimeRange(startTime, endTime)));
 234     }
 235
 236     // ------------------------------------------------------------------------
 237     // ITmfTraceIndexer - updateIndex
 238     // ------------------------------------------------------------------------
 239
 240     /* (non-Javadoc)
 241      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#updateIndex(org.eclipse.linuxtools.tmf.core.trace.ITmfContext, org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 242      */
 243     @Override
 244     public synchronized void updateIndex(final ITmfContext context, final ITmfTimestamp timestamp) {
 245         final long rank = context.getRank();
 246         if ((rank % fCheckpointInterval) == 0) {
 247             // Determine the table position
 248             final long position = rank / fCheckpointInterval;
 249             // Add new entry at proper location (if empty)
 250             if (fTraceIndex.size() == position) {
 251                 final ITmfLocation<?> location = context.getLocation().clone();
 252                 fTraceIndex.add(new TmfCheckpoint(timestamp.clone(), location));
 253             }
 254         }
 255     }
 256
 257     // ------------------------------------------------------------------------
 258     // ITmfTraceIndexer - seekIndex
 259     // ------------------------------------------------------------------------
 260
 261     /* (non-Javadoc)
 262      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 263      */
 264     @Override
 265     public synchronized ITmfContext seekIndex(final ITmfTimestamp timestamp) {
 266
 267         // A null timestamp indicates to seek the first event
 268         if (timestamp == null) {
 269             return fTrace.seekEvent(0);
 270         }
 271
 272         // Find the checkpoint at or before the requested timestamp.
 273         // In the very likely event that the timestamp is not at a checkpoint
 274         // boundary, bsearch will return index = (- (insertion point + 1)).
 275         // It is then trivial to compute the index of the previous checkpoint.
 276         int index = Collections.binarySearch(fTraceIndex, new TmfCheckpoint(timestamp, null));
 277         if (index < 0) {
 278             index = Math.max(0, -(index + 2));
 279         }
 280
 281         // Position the trace at the checkpoint
 282         return seekCheckpoint(index);
 283     }
 284
 285     /* (non-Javadoc)
 286      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(long)
 287      */
 288     @Override
 289     public ITmfContext seekIndex(final long rank) {
 290
 291         // A rank < 0 indicates to seek the first event
 292         if (rank < 0) {
 293             return fTrace.seekEvent(0);
 294         }
 295
 296         // Find the checkpoint at or before the requested rank.
 297         final int index = (int) rank / fCheckpointInterval;
 298
 299         // Position the trace at the checkpoint
 300         return seekCheckpoint(index);
 301     }
 302
 303     /**
 304      * Position the trace at the given checkpoint
 305      *
 306      * @param checkpoint the checkpoint index
 307      * @return the corresponding context
 308      */
 309     private ITmfContext seekCheckpoint(final int checkpoint) {
 310         ITmfLocation<?> location = null;
 311         int index = checkpoint;
 312         synchronized (fTraceIndex) {
 313             if (!fTraceIndex.isEmpty()) {
 314                 if (index >= fTraceIndex.size()) {
 315                     index = fTraceIndex.size() - 1;
 316                 }
 317                 location = fTraceIndex.get(index).getLocation();
 318             }
 319         }
 320         final ITmfContext context = fTrace.seekEvent(location);
 321         context.setRank((long) index * fCheckpointInterval);
 322         return context;
 323     }
 324
 325     // ------------------------------------------------------------------------
 326     // Getters
 327     // ------------------------------------------------------------------------
 328
 329     /**
 330      * @return the trace index
 331      */
 332     protected List<TmfCheckpoint> getTraceIndex() {
 333         return fTraceIndex;
 334     }
 335 }