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  * @param <T> The trace event type
  48  *
  49  * @version 1.0
  50  * @author Francois Chouinard
  51  *
  52  * @see ITmfTrace
  53  * @see ITmfEvent
  54  */
  55 public class TmfCheckpointIndexer<T extends ITmfTrace<ITmfEvent>> implements ITmfTraceIndexer<T> {
  56
  57     // ------------------------------------------------------------------------
  58     // Attributes
  59     // ------------------------------------------------------------------------
  60
  61     // The event trace to index
  62     protected final ITmfTrace<ITmfEvent> fTrace;
  63
  64     // The interval between checkpoints
  65     private final int fCheckpointInterval;
  66
  67     // The event trace to index
  68     private boolean fIsIndexing;
  69
  70     /**
  71      * The trace index. It is composed of checkpoints taken at intervals of
  72      * fCheckpointInterval events.
  73      */
  74     protected final List<ITmfCheckpoint> fTraceIndex;
  75
  76     /**
  77      * The indexing request
  78      */
  79     private ITmfEventRequest<ITmfEvent> fIndexingRequest = null;
  80
  81     // ------------------------------------------------------------------------
  82     // Construction
  83     // ------------------------------------------------------------------------
  84
  85     /**
  86      * Basic constructor that uses the default trace block size as checkpoints
  87      * intervals
  88      *
  89      * @param trace the trace to index
  90      */
  91     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace) {
  92         this(trace, TmfDataProvider.DEFAULT_BLOCK_SIZE);
  93     }
  94
  95     /**
  96      * Full trace indexer
  97      *
  98      * @param trace the trace to index
  99      * @param interval the checkpoints interval
 100      */
 101     public TmfCheckpointIndexer(final ITmfTrace<ITmfEvent> trace, final int interval) {
 102         fTrace = trace;
 103         fCheckpointInterval = interval;
 104         fTraceIndex = new ArrayList<ITmfCheckpoint>();
 105         fIsIndexing = false;
 106     }
 107
 108     /* (non-Javadoc)
 109      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#dispose()
 110      */
 111     @Override
 112     public void dispose() {
 113         if ((fIndexingRequest != null) && !fIndexingRequest.isCompleted()) {
 114             fIndexingRequest.cancel();
 115             fTraceIndex.clear();
 116         }
 117     }
 118
 119     // ------------------------------------------------------------------------
 120     // ITmfTraceIndexer - isIndexing
 121     // ------------------------------------------------------------------------
 122
 123     /* (non-Javadoc)
 124      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#isIndexing()
 125      */
 126     @Override
 127     public boolean isIndexing() {
 128         return fIsIndexing;
 129     }
 130
 131     // ------------------------------------------------------------------------
 132     // ITmfTraceIndexer - buildIndex
 133     // ------------------------------------------------------------------------
 134
 135     /* (non-Javadoc)
 136      *
 137      * The index is a list of contexts that point to events at regular interval
 138      * (rank-wise) in the trace. After it is built, the index can be used to
 139      * quickly access any event by rank or timestamp (using seekIndex()).
 140      *
 141      * The index is built simply by reading the trace
 142      *
 143      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#buildIndex(long, org.eclipse.linuxtools.tmf.core.event.TmfTimeRange, boolean)
 144      */
 145     @Override
 146     public void buildIndex(final long offset, final TmfTimeRange range, final boolean waitForCompletion) {
 147
 148         // Don't do anything if we are already indexing
 149         synchronized (fTraceIndex) {
 150             if (fIsIndexing) {
 151                 return;
 152             }
 153             fIsIndexing = true;
 154         }
 155
 156         // The monitoring job
 157         final Job job = new Job("Indexing " + fTrace.getName() + "...") { //$NON-NLS-1$ //$NON-NLS-2$
 158             @Override
 159             protected IStatus run(final IProgressMonitor monitor) {
 160                 while (!monitor.isCanceled()) {
 161                     try {
 162                         Thread.sleep(100);
 163                     } catch (final InterruptedException e) {
 164                         return Status.OK_STATUS;
 165                     }
 166                 }
 167                 monitor.done();
 168                 return Status.OK_STATUS;
 169             }
 170         };
 171         job.schedule();
 172
 173         // Build a background request for all the trace data. The index is
 174         // updated as we go by readNextEvent().
 175         fIndexingRequest = new TmfEventRequest<ITmfEvent>(ITmfEvent.class,
 176                 range, offset, TmfDataRequest.ALL_DATA, fCheckpointInterval, ITmfDataRequest.ExecutionType.BACKGROUND)
 177         {
 178             private ITmfTimestamp startTime = null;
 179             private ITmfTimestamp lastTime = null;
 180
 181             @Override
 182             public void handleData(final ITmfEvent event) {
 183                 super.handleData(event);
 184                 if (event != null) {
 185                     final ITmfTimestamp timestamp = event.getTimestamp();
 186                     if (startTime == null) {
 187                         startTime = timestamp.clone();
 188                     }
 189                     lastTime = timestamp.clone();
 190
 191                     // Update the trace status at regular intervals
 192                     if ((getNbRead() % fCheckpointInterval) == 0) {
 193                         updateTraceStatus();
 194                     }
 195                 }
 196             }
 197
 198             @Override
 199             public void handleSuccess() {
 200                 updateTraceStatus();
 201             }
 202
 203             @Override
 204             public void handleCompleted() {
 205                 job.cancel();
 206                 super.handleCompleted();
 207                 fIsIndexing = false;
 208             }
 209
 210             private void updateTraceStatus() {
 211                 if (getNbRead() != 0) {
 212                     signalNewTimeRange(startTime, lastTime);
 213                 }
 214             }
 215         };
 216
 217         // Submit the request and wait for completion if required
 218         fTrace.sendRequest(fIndexingRequest);
 219         if (waitForCompletion) {
 220             try {
 221                 fIndexingRequest.waitForCompletion();
 222             } catch (final InterruptedException e) {
 223             }
 224         }
 225     }
 226
 227     /**
 228      * Notify the interested parties that the trace time range has changed
 229      *
 230      * @param startTime the new start time
 231      * @param endTime the new end time
 232      */
 233     private void signalNewTimeRange(final ITmfTimestamp startTime, final ITmfTimestamp endTime) {
 234         fTrace.broadcast(new TmfTraceUpdatedSignal(fTrace, fTrace, new TmfTimeRange(startTime, endTime)));
 235     }
 236
 237     // ------------------------------------------------------------------------
 238     // ITmfTraceIndexer - updateIndex
 239     // ------------------------------------------------------------------------
 240
 241     /* (non-Javadoc)
 242      * @see org.eclipse.linuxtools.tmf.core.trace.ITmfTraceIndexer#updateIndex(org.eclipse.linuxtools.tmf.core.trace.ITmfContext, org.eclipse.linuxtools.tmf.core.event.ITmfTimestamp)
 243      */
 244     @Override
 245     public synchronized void updateIndex(final ITmfContext context, final ITmfTimestamp timestamp) {
 246         final long rank = context.getRank();
 247         if ((rank % fCheckpointInterval) == 0) {
 248             // Determine the table position
 249             final long position = rank / fCheckpointInterval;
 250             // Add new entry at proper location (if empty)
 251             if (fTraceIndex.size() == position) {
 252                 fTraceIndex.add(new TmfCheckpoint(timestamp.clone(), saveContext(context)));
 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 restoreCheckpoint(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 restoreCheckpoint(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 restoreCheckpoint(final int checkpoint) {
 310         ITmfLocation<?> location = null;
 311         int index = 0;
 312         synchronized (fTraceIndex) {
 313             if (!fTraceIndex.isEmpty()) {
 314                 index = checkpoint;
 315                 if (index >= fTraceIndex.size()) {
 316                     index = fTraceIndex.size() - 1;
 317                 }
 318                 return restoreContext(fTraceIndex.get(index).getContext());
 319             }
 320         }
 321         final ITmfContext context = fTrace.seekEvent(location);
 322         context.setRank((long) index * fCheckpointInterval);
 323         return context;
 324     }
 325
 326     // ------------------------------------------------------------------------
 327     // Getters
 328     // ------------------------------------------------------------------------
 329
 330     /**
 331      * @return the trace index
 332      */
 333     protected List<ITmfCheckpoint> getTraceIndex() {
 334         return fTraceIndex;
 335     }
 336
 337     // ------------------------------------------------------------------------
 338     // Context conversion functions
 339     // ------------------------------------------------------------------------
 340
 341     private static ITmfContext saveContext(ITmfContext context) {
 342         if (context instanceof TmfExperimentContext) {
 343             return saveExpContext(context);
 344         }
 345         TmfContext ctx = new TmfContext(context.getLocation().clone(), context.getRank());
 346         return ctx;
 347     }
 348
 349     private static ITmfContext saveExpContext(ITmfContext context) {
 350         TmfExperimentContext expContext = (TmfExperimentContext) context;
 351         int size = expContext.getContexts().length;
 352         ITmfContext[] trcCtxts = new TmfContext[size];
 353         for (int i = 0; i < size; i++) {
 354             ITmfContext ctx = expContext.getContexts()[i];
 355             trcCtxts[i] = (ctx != null) ? new TmfContext(ctx.getLocation().clone(), ctx.getRank()) : null;
 356         }
 357         TmfExperimentContext expCtx = new TmfExperimentContext(trcCtxts);
 358         expCtx.setLocation(context.getLocation().clone());
 359         expCtx.setRank(context.getRank());
 360         ITmfEvent[] trcEvts = expCtx.getEvents();
 361         for (int i = 0; i < size; i++) {
 362             ITmfEvent event = expContext.getEvents()[i];
 363             trcEvts[i] = (event != null) ? event.clone() : null;
 364         }
 365         return expCtx;
 366     }
 367
 368     private ITmfContext restoreContext(ITmfContext context) {
 369         if (context instanceof TmfExperimentContext) {
 370             return restoreExpContext(context);
 371         }
 372         ITmfContext ctx = fTrace.seekEvent(context.getLocation());
 373         ctx.setRank(context.getRank());
 374         return ctx;
 375     }
 376
 377     private ITmfContext restoreExpContext(ITmfContext context) {
 378         TmfExperimentContext expContext = (TmfExperimentContext) context;
 379         int size = expContext.getContexts().length;
 380         ITmfContext[] trcCtxts = new ITmfContext[size];
 381         for (int i = 0; i < size; i++) {
 382             ITmfTrace<?> trace = ((TmfExperiment<?>) fTrace).getTraces()[i];
 383             ITmfContext ctx = expContext.getContexts()[i];
 384             trcCtxts[i] = trace.seekEvent(ctx.getLocation().clone());
 385             trcCtxts[i].setRank(ctx.getRank());
 386         }
 387         TmfExperimentContext ctx = new TmfExperimentContext(trcCtxts);
 388         ctx.setLocation(context.getLocation().clone());
 389         ctx.setRank(context.getRank());
 390         ITmfEvent[] trcEvts = expContext.getEvents();
 391         for (int i = 0; i < size; i++) {
 392             ITmfEvent event = trcEvts[i];
 393             ctx.getEvents()[i] = (event != null) ? event.clone() : null;
 394         }
 395         return ctx;
 396     }
 397
 398 }