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.internal.tmf.core.trace.TmfExperimentContext;
  24 import org.eclipse.linuxtools.tmf.core.component.TmfDataProvider;
  25 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  26 import org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp;
  27 import org.eclipse.linuxtools.tmf.core.event.TmfTimeRange;
  28 import org.eclipse.linuxtools.tmf.core.request.ITmfDataRequest;
  29 import org.eclipse.linuxtools.tmf.core.request.ITmfEventRequest;
  30 import org.eclipse.linuxtools.tmf.core.request.TmfDataRequest;
  31 import org.eclipse.linuxtools.tmf.core.request.TmfEventRequest;
  32 import org.eclipse.linuxtools.tmf.core.signal.TmfTraceUpdatedSignal;
  33
  34 /**
  35  * A simple indexer that manages the trace index as an array of trace
  36  * checkpoints. Checkpoints are stored at fixed intervals (event rank) in
  37  * ascending timestamp order.
  38  * <p>
  39  * The goal being to access a random trace event reasonably fast from the user's
  40  * standpoint, picking the right interval value becomes a trade-off between speed
  41  * and memory usage (a shorter inter-event interval is faster but requires more
  42  * checkpoints).
  43  * <p>
  44  * Locating a specific checkpoint is trivial for both rank (rank % interval) and
  45  * timestamp (bsearch in the array).
  46  *
  47  * @version 1.0
  48  * @author Francois Chouinard
  49  *
  50  * @see ITmfTrace
  51  * @see ITmfEvent
  52  */
  53 public class TmfCheckpointIndexer<T extends ITmfTrace<ITmfEvent>> implements ITmfTraceIndexer<T> {
  54
  55     // ------------------------------------------------------------------------
  56     // Attributes
  57     // ------------------------------------------------------------------------
  58
  59     // The event trace to index
  60     protected final ITmfTrace<ITmfEvent> fTrace;
  61
  62     // The interval between checkpoints
  63     private final int fCheckpointInterval;
  64
  65     // The event trace to index
  66     private boolean fIsIndexing;
  67
  68     /**
  69      * The trace index. It is composed of checkpoints taken at intervals of
  70      * fCheckpointInterval events.
  71      */
  72     protected final List<ITmfCheckpoint> fTraceIndex;
  73
  74     /**
  75      * The indexing request
  76      */
  77     private ITmfEventRequest<ITmfEvent> fIndexingRequest = null;
  78
  79     // ------------------------------------------------------------------------
  80     // Construction
  81     // ------------------------------------------------------------------------
  82
  83     /**
  84      * Basic constructor that uses the default trace block size as checkpoints
  85      * intervals
  86      *
  87      * @param trace the trace to index
  88      */
  89     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace) {
  90         this(trace, TmfDataProvider.DEFAULT_BLOCK_SIZE);
  91     }
  92
  93     /**
  94      * Full trace indexer
  95      *
  96      * @param trace the trace to index
  97      * @param interval the checkpoints interval
  98      */
  99     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace, final int interval) {
 100         fTrace = trace;
 101         fCheckpointInterval = interval;
 102         fTraceIndex = new ArrayList<ITmfCheckpoint>();
 103         fIsIndexing = false;
 104     }
 105
 106     /* (non-Javadoc)
 107      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#dispose()
 108      */
 109     @Override
 110     public void dispose() {
 111         if ((fIndexingRequest != null) && !fIndexingRequest.isCompleted()) {
 112             fIndexingRequest.cancel();
 113             fTraceIndex.clear();
 114         }
 115     }
 116
 117     // ------------------------------------------------------------------------
 118     // ITmfTraceIndexer - isIndexing
 119     // ------------------------------------------------------------------------
 120
 121     /* (non-Javadoc)
 122      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#isIndexing()
 123      */
 124     @Override
 125     public boolean isIndexing() {
 126         return fIsIndexing;
 127     }
 128
 129     // ------------------------------------------------------------------------
 130     // ITmfTraceIndexer - buildIndex
 131     // ------------------------------------------------------------------------
 132
 133     /* (non-Javadoc)
 134      *
 135      * The index is a list of contexts that point to events at regular interval
 136      * (rank-wise) in the trace. After it is built, the index can be used to
 137      * quickly access any event by rank or timestamp (using seekIndex()).
 138      *
 139      * The index is built simply by reading the trace
 140      *
 141      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#buildIndex(long, org.eclipse.linuxtools.tmf.core.event.TmfTimeRange, boolean)
 142      */
 143     @Override
 144     public void buildIndex(final long offset, final TmfTimeRange range, final boolean waitForCompletion) {
 145
 146         // Don't do anything if we are already indexing
 147         synchronized (fTraceIndex) {
 148             if (fIsIndexing) {
 149                 return;
 150             }
 151             fIsIndexing = true;
 152         }
 153
 154         // The monitoring job
 155         final Job job = new Job("Indexing " + fTrace.getName() + "...") { //$NON-NLS-1$ //$NON-NLS-2$
 156             @Override
 157             protected IStatus run(final IProgressMonitor monitor) {
 158                 while (!monitor.isCanceled()) {
 159                     try {
 160                         Thread.sleep(100);
 161                     } catch (final InterruptedException e) {
 162                         return Status.OK_STATUS;
 163                     }
 164                 }
 165                 monitor.done();
 166                 return Status.OK_STATUS;
 167             }
 168         };
 169         job.schedule();
 170
 171         // Build a background request for all the trace data. The index is
 172         // updated as we go by readNextEvent().
 173         fIndexingRequest = new TmfEventRequest<ITmfEvent>(ITmfEvent.class,
 174                 range, offset, TmfDataRequest.ALL_DATA, fCheckpointInterval, ITmfDataRequest.ExecutionType.BACKGROUND)
 175         {
 176             private ITmfTimestamp startTime = null;
 177             private ITmfTimestamp lastTime = null;
 178
 179             @Override
 180             public void handleData(final ITmfEvent event) {
 181                 super.handleData(event);
 182                 if (event != null) {
 183                     final ITmfTimestamp timestamp = event.getTimestamp();
 184                     if (startTime == null) {
 185                         startTime = timestamp.clone();
 186                     }
 187                     lastTime = timestamp.clone();
 188
 189                     // Update the trace status at regular intervals
 190                     if ((getNbRead() % fCheckpointInterval) == 0) {
 191                         updateTraceStatus();
 192                     }
 193                 }
 194             }
 195
 196             @Override
 197             public void handleSuccess() {
 198                 updateTraceStatus();
 199             }
 200
 201             @Override
 202             public void handleCompleted() {
 203                 job.cancel();
 204                 super.handleCompleted();
 205                 fIsIndexing = false;
 206             }
 207
 208             private void updateTraceStatus() {
 209                 if (getNbRead() != 0) {
 210                     signalNewTimeRange(startTime, lastTime);
 211                 }
 212             }
 213         };
 214
 215         // Submit the request and wait for completion if required
 216         fTrace.sendRequest(fIndexingRequest);
 217         if (waitForCompletion) {
 218             try {
 219                 fIndexingRequest.waitForCompletion();
 220             } catch (final InterruptedException e) {
 221             }
 222         }
 223     }
 224
 225     /**
 226      * Notify the interested parties that the trace time range has changed
 227      *
 228      * @param startTime the new start time
 229      * @param endTime the new end time
 230      */
 231     private void signalNewTimeRange(final ITmfTimestamp startTime, final ITmfTimestamp endTime) {
 232         fTrace.broadcast(new TmfTraceUpdatedSignal(fTrace, fTrace, new TmfTimeRange(startTime, endTime)));
 233     }
 234
 235     // ------------------------------------------------------------------------
 236     // ITmfTraceIndexer - updateIndex
 237     // ------------------------------------------------------------------------
 238
 239     /* (non-Javadoc)
 240      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#updateIndex(org.eclipse.linuxtools.tmf.core.trace.ITmfContext, org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 241      */
 242     @Override
 243     public synchronized void updateIndex(final ITmfContext context, final ITmfTimestamp timestamp) {
 244         final long rank = context.getRank();
 245         if ((rank % fCheckpointInterval) == 0) {
 246             // Determine the table position
 247             final long position = rank / fCheckpointInterval;
 248             // Add new entry at proper location (if empty)
 249             if (fTraceIndex.size() == position) {
 250                 fTraceIndex.add(new TmfCheckpoint(timestamp.clone(), saveContext(context)));
 251             }
 252         }
 253     }
 254
 255     // ------------------------------------------------------------------------
 256     // ITmfTraceIndexer - seekIndex
 257     // ------------------------------------------------------------------------
 258
 259     /* (non-Javadoc)
 260      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 261      */
 262     @Override
 263     public synchronized ITmfContext seekIndex(final ITmfTimestamp timestamp) {
 264
 265         // A null timestamp indicates to seek the first event
 266         if (timestamp == null) {
 267             return fTrace.seekEvent(0);
 268         }
 269
 270         // Find the checkpoint at or before the requested timestamp.
 271         // In the very likely event that the timestamp is not at a checkpoint
 272         // boundary, bsearch will return index = (- (insertion point + 1)).
 273         // It is then trivial to compute the index of the previous checkpoint.
 274         int index = Collections.binarySearch(fTraceIndex, new TmfCheckpoint(timestamp, null));
 275         if (index < 0) {
 276             index = Math.max(0, -(index + 2));
 277         }
 278
 279         // Position the trace at the checkpoint
 280         return restoreCheckpoint(index);
 281     }
 282
 283     /* (non-Javadoc)
 284      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#seekIndex(long)
 285      */
 286     @Override
 287     public ITmfContext seekIndex(final long rank) {
 288
 289         // A rank < 0 indicates to seek the first event
 290         if (rank < 0) {
 291             return fTrace.seekEvent(0);
 292         }
 293
 294         // Find the checkpoint at or before the requested rank.
 295         final int index = (int) rank / fCheckpointInterval;
 296
 297         // Position the trace at the checkpoint
 298         return restoreCheckpoint(index);
 299     }
 300
 301     /**
 302      * Position the trace at the given checkpoint
 303      *
 304      * @param checkpoint the checkpoint index
 305      * @return the corresponding context
 306      */
 307     private ITmfContext restoreCheckpoint(final int checkpoint) {
 308         ITmfLocation<?> location = null;
 309         int index = 0;
 310         synchronized (fTraceIndex) {
 311             if (!fTraceIndex.isEmpty()) {
 312                 index = checkpoint;
 313                 if (index >= fTraceIndex.size()) {
 314                     index = fTraceIndex.size() - 1;
 315                 }
 316                 return restoreContext(fTraceIndex.get(index).getContext());
 317             }
 318         }
 319         final ITmfContext context = fTrace.seekEvent(location);
 320         context.setRank((long) index * fCheckpointInterval);
 321         return context;
 322     }
 323
 324     // ------------------------------------------------------------------------
 325     // Getters
 326     // ------------------------------------------------------------------------
 327
 328     /**
 329      * @return the trace index
 330      */
 331     protected List<ITmfCheckpoint> getTraceIndex() {
 332         return fTraceIndex;
 333     }
 334
 335     // ------------------------------------------------------------------------
 336     // Context conversion functions
 337     // ------------------------------------------------------------------------
 338
 339     private static ITmfContext saveContext(ITmfContext context) {
 340         if (context instanceof TmfExperimentContext) {
 341             return saveExpContext(context);
 342         }
 343         TmfContext ctx = new TmfContext(context.getLocation().clone(), context.getRank());
 344         return ctx;
 345     }
 346
 347     private static ITmfContext saveExpContext(ITmfContext context) {
 348         TmfExperimentContext expContext = (TmfExperimentContext) context;
 349         int size = expContext.getContexts().length;
 350         ITmfContext[] trcCtxts = new TmfContext[size];
 351         for (int i = 0; i < size; i++) {
 352             ITmfContext ctx = expContext.getContexts()[i];
 353             trcCtxts[i] = (ctx != null) ? new TmfContext(ctx.getLocation().clone(), ctx.getRank()) : null;
 354         }
 355         TmfExperimentContext expCtx = new TmfExperimentContext(trcCtxts);
 356         expCtx.setLocation(context.getLocation().clone());
 357         expCtx.setRank(context.getRank());
 358         ITmfEvent[] trcEvts = expCtx.getEvents();
 359         for (int i = 0; i < size; i++) {
 360             ITmfEvent event = expContext.getEvents()[i];
 361             trcEvts[i] = (event != null) ? event.clone() : null;
 362         }
 363         return expCtx;
 364     }
 365
 366     private ITmfContext restoreContext(ITmfContext context) {
 367         if (context instanceof TmfExperimentContext) {
 368             return restoreExpContext(context);
 369         }
 370         ITmfContext ctx = fTrace.seekEvent(context.getLocation());
 371         ctx.setRank(context.getRank());
 372         return ctx;
 373     }
 374
 375     private ITmfContext restoreExpContext(ITmfContext context) {
 376         TmfExperimentContext expContext = (TmfExperimentContext) context;
 377         int size = expContext.getContexts().length;
 378         ITmfContext[] trcCtxts = new ITmfContext[size];
 379         for (int i = 0; i < size; i++) {
 380             ITmfTrace<?> trace = ((TmfExperiment<?>) fTrace).getTraces()[i];
 381             ITmfContext ctx = expContext.getContexts()[i];
 382             trcCtxts[i] = trace.seekEvent(ctx.getLocation().clone());
 383             trcCtxts[i].setRank(ctx.getRank());
 384         }
 385         TmfExperimentContext ctx = new TmfExperimentContext(trcCtxts);
 386         ctx.setLocation(context.getLocation().clone());
 387         ctx.setRank(context.getRank());
 388         ITmfEvent[] trcEvts = expContext.getEvents();
 389         for (int i = 0; i < size; i++) {
 390             ITmfEvent event = trcEvts[i];
 391             ctx.getEvents()[i] = (event != null) ? event.clone() : null;
 392         }
 393         return ctx;
 394     }
 395
 396 }