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