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