tmf/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TmfEventMatching.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013, 2015 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * 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  *   Geneviève Bastien - Initial implementation and API
  11  *******************************************************************************/
  12
  13 package org.eclipse.tracecompass.tmf.core.event.matching;
  14
  15 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  16
  17 import java.util.Collection;
  18 import java.util.HashSet;
  19 import java.util.Set;
  20
  21 import org.eclipse.core.runtime.IProgressMonitor;
  22 import org.eclipse.core.runtime.IStatus;
  23 import org.eclipse.core.runtime.NullProgressMonitor;
  24 import org.eclipse.core.runtime.Status;
  25 import org.eclipse.core.runtime.jobs.Job;
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.osgi.util.NLS;
  28 import org.eclipse.tracecompass.internal.tmf.core.Activator;
  29 import org.eclipse.tracecompass.tmf.core.event.ITmfEvent;
  30 import org.eclipse.tracecompass.tmf.core.request.ITmfEventRequest;
  31 import org.eclipse.tracecompass.tmf.core.request.TmfEventRequest;
  32 import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimeRange;
  33 import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
  34 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager;
  35 import org.eclipse.tracecompass.tmf.core.trace.experiment.TmfExperiment;
  36
  37 import com.google.common.collect.HashBasedTable;
  38 import com.google.common.collect.HashMultimap;
  39 import com.google.common.collect.ImmutableList;
  40 import com.google.common.collect.Multimap;
  41 import com.google.common.collect.Table;
  42
  43 /**
  44  * Abstract class to extend to match certain type of events in a trace
  45  *
  46  * @author Geneviève Bastien
  47  */
  48 public class TmfEventMatching implements ITmfEventMatching {
  49
  50     private static final Set<ITmfMatchEventDefinition> MATCH_DEFINITIONS = new HashSet<>();
  51
  52     /**
  53      * The array of traces to match
  54      */
  55     private final @NonNull Collection<@NonNull ITmfTrace> fTraces;
  56
  57     /**
  58      * The class to call once a match is found
  59      */
  60     private final IMatchProcessingUnit fMatches;
  61
  62     private final Multimap<ITmfTrace, ITmfMatchEventDefinition> fMatchMap = HashMultimap.create();
  63
  64     /**
  65      * Hashtables for unmatches incoming events
  66      */
  67     private final Table<ITmfTrace, IEventMatchingKey, ITmfEvent> fUnmatchedIn = HashBasedTable.create();
  68
  69     /**
  70      * Hashtables for unmatches outgoing events
  71      */
  72     private final Table<ITmfTrace, IEventMatchingKey, ITmfEvent> fUnmatchedOut = HashBasedTable.create();
  73
  74     /**
  75      * Enum for cause and effect types of event
  76      * @since 1.0
  77      */
  78     public enum Direction {
  79         /**
  80          * The event is the first event of the match
  81          */
  82         CAUSE,
  83         /**
  84          * The event is the second event, the one that matches with the cause
  85          */
  86         EFFECT,
  87     }
  88
  89     /**
  90      * Constructor with multiple traces
  91      *
  92      * @param traces
  93      *            The set of traces for which to match events
  94      * @since 1.0
  95      */
  96     public TmfEventMatching(Collection<@NonNull ITmfTrace> traces) {
  97         this(traces, new TmfEventMatches());
  98     }
  99
 100     /**
 101      * Constructor with multiple traces and a match processing object
 102      *
 103      * @param traces
 104      *            The set of traces for which to match events
 105      * @param tmfEventMatches
 106      *            The match processing class
 107      */
 108     public TmfEventMatching(Collection<@NonNull ITmfTrace> traces, IMatchProcessingUnit tmfEventMatches) {
 109         if (tmfEventMatches == null) {
 110             throw new IllegalArgumentException();
 111         }
 112         fTraces = new HashSet<>(traces);
 113         fMatches = tmfEventMatches;
 114     }
 115
 116     /**
 117      * Returns the traces to synchronize. These are the traces that were
 118      * specified in the constructor, they may contain either traces or
 119      * experiment.
 120      *
 121      * @return The traces to synchronize
 122      */
 123     protected Collection<ITmfTrace> getTraces() {
 124         return new HashSet<>(fTraces);
 125     }
 126
 127     /**
 128      * Returns the individual traces to process. If some of the traces specified
 129      * to synchronize in the constructor were experiments, only the traces
 130      * contained in this experiment will be returned. No {@link TmfExperiment}
 131      * are returned by this method.
 132      *
 133      * @return The individual traces to synchronize, no experiments
 134      */
 135     protected Collection<ITmfTrace> getIndividualTraces() {
 136         Set<ITmfTrace> traces = new HashSet<>();
 137         for (ITmfTrace trace : fTraces) {
 138             traces.addAll(TmfTraceManager.getTraceSet(trace));
 139         }
 140         return traces;
 141     }
 142
 143     /**
 144      * Returns the match processing unit
 145      *
 146      * @return The match processing unit
 147      */
 148     protected IMatchProcessingUnit getProcessingUnit() {
 149         return fMatches;
 150     }
 151
 152     /**
 153      * Returns the match event definitions corresponding to the trace
 154      *
 155      * @param trace
 156      *            The trace
 157      * @return The match event definition object
 158      */
 159     protected Collection<ITmfMatchEventDefinition> getEventDefinitions(ITmfTrace trace) {
 160         return ImmutableList.copyOf(fMatchMap.get(trace));
 161     }
 162
 163     /**
 164      * Method that initializes any data structure for the event matching. It
 165      * also assigns to each trace an event matching definition instance that
 166      * applies to the trace
 167      *
 168      * @since 1.0
 169      */
 170     public void initMatching() {
 171         // Initialize the matching infrastructure (unmatched event lists)
 172         fUnmatchedIn.clear();
 173         fUnmatchedOut.clear();
 174
 175         fMatches.init(fTraces);
 176         for (ITmfTrace trace : getIndividualTraces()) {
 177             for (ITmfMatchEventDefinition def : MATCH_DEFINITIONS) {
 178                 if (def.canMatchTrace(trace)) {
 179                     fMatchMap.put(trace, def);
 180                 }
 181             }
 182         }
 183     }
 184
 185     /**
 186      * Calls any post matching methods of the processing class
 187      */
 188     protected void finalizeMatching() {
 189         fMatches.matchingEnded();
 190     }
 191
 192     /**
 193      * Prints stats from the matching
 194      *
 195      * @return string of statistics
 196      */
 197     @Override
 198     public String toString() {
 199         final String cr = System.getProperty("line.separator"); //$NON-NLS-1$
 200         StringBuilder b = new StringBuilder();
 201         b.append(getProcessingUnit());
 202         int i = 0;
 203         for (ITmfTrace trace : getIndividualTraces()) {
 204             b.append("Trace " + i++ + ":" + cr + //$NON-NLS-1$ //$NON-NLS-2$
 205                     "  " + fUnmatchedIn.row(trace).size() + " unmatched incoming events" + cr + //$NON-NLS-1$ //$NON-NLS-2$
 206                     "  " + fUnmatchedOut.row(trace).size() + " unmatched outgoing events" + cr); //$NON-NLS-1$ //$NON-NLS-2$
 207         }
 208
 209         return b.toString();
 210     }
 211
 212     /**
 213      * Matches one event
 214      *
 215      * @param event
 216      *            The event to match
 217      * @param trace
 218      *            The trace to which this event belongs
 219      * @param monitor
 220      *            The monitor for the synchronization job
 221      * @since 1.0
 222      */
 223     public void matchEvent(ITmfEvent event, ITmfTrace trace, @NonNull IProgressMonitor monitor) {
 224         ITmfMatchEventDefinition def = null;
 225         Direction evType = null;
 226         for (ITmfMatchEventDefinition oneDef : getEventDefinitions(event.getTrace())) {
 227             def = oneDef;
 228             evType = def.getDirection(event);
 229             if (evType != null) {
 230                 break;
 231             }
 232
 233         }
 234
 235         if (def == null || evType == null) {
 236             return;
 237         }
 238
 239         /* Get the event's unique fields */
 240         IEventMatchingKey eventKey = def.getEventKey(event);
 241
 242         if (eventKey == null) {
 243             return;
 244         }
 245         Table<ITmfTrace, IEventMatchingKey, ITmfEvent> unmatchedTbl, companionTbl;
 246
 247         /* Point to the appropriate table */
 248         switch (evType) {
 249         case CAUSE:
 250             unmatchedTbl = fUnmatchedIn;
 251             companionTbl = fUnmatchedOut;
 252             break;
 253         case EFFECT:
 254             unmatchedTbl = fUnmatchedOut;
 255             companionTbl = fUnmatchedIn;
 256             break;
 257         default:
 258             return;
 259         }
 260
 261         boolean found = false;
 262         TmfEventDependency dep = null;
 263         /* Search for the event in the companion table */
 264         for (ITmfTrace mTrace : getIndividualTraces()) {
 265             if (companionTbl.contains(mTrace, eventKey)) {
 266                 found = true;
 267                 ITmfEvent companionEvent = companionTbl.get(mTrace, eventKey);
 268
 269                 /* Remove the element from the companion table */
 270                 companionTbl.remove(mTrace, eventKey);
 271
 272                 /* Create the dependency object */
 273                 switch (evType) {
 274                 case CAUSE:
 275                     dep = new TmfEventDependency(companionEvent, event);
 276                     break;
 277                 case EFFECT:
 278                     dep = new TmfEventDependency(event, companionEvent);
 279                     break;
 280                 default:
 281                     break;
 282
 283                 }
 284             }
 285         }
 286
 287         /*
 288          * If no companion was found, add the event to the appropriate unMatched
 289          * lists
 290          */
 291         if (found) {
 292             getProcessingUnit().addMatch(checkNotNull(dep));
 293             monitor.subTask(NLS.bind(Messages.TmfEventMatching_MatchesFound, getProcessingUnit().countMatches()));
 294         } else {
 295             /*
 296              * If an event is already associated with this key, do not add it
 297              * again, we keep the first event chronologically, so if its match
 298              * is eventually found, it is associated with the first send or
 299              * receive event. At best, it is a good guess, at worst, the match
 300              * will be too far off to be accurate. Too bad!
 301              *
 302              * TODO: maybe instead of just one event, we could have a list of
 303              * events as value for the unmatched table. Not necessary right now
 304              * though
 305              */
 306             if (!unmatchedTbl.contains(event.getTrace(), eventKey)) {
 307                 unmatchedTbl.put(event.getTrace(), eventKey, event);
 308             }
 309         }
 310     }
 311
 312     /**
 313      * Method that start the process of matching events
 314      *
 315      * @return Whether the match was completed correctly or not
 316      */
 317     @Override
 318     public boolean matchEvents() {
 319
 320         /* Are there traces to match? If no, return false */
 321         if (!(fTraces.size() > 0)) {
 322             return false;
 323         }
 324
 325         initMatching();
 326
 327         /*
 328          * Actual analysis will be run on a separate thread
 329          */
 330         Job job = new Job(Messages.TmfEventMatching_MatchingEvents) {
 331             @Override
 332             protected IStatus run(final IProgressMonitor monitor) {
 333                 /**
 334                  * FIXME For now, we use the experiment strategy: the trace that
 335                  * is asked to be matched is actually an experiment and the
 336                  * experiment does the request. But depending on how divergent
 337                  * the traces' times are and how long it takes to get the first
 338                  * match, it can use a lot of memory.
 339                  *
 340                  * Some strategies can help limit the memory usage of this
 341                  * algorithm:
 342                  *
 343                  * <pre>
 344                  * Other possible matching strategy:
 345                  * * start with the shortest trace
 346                  * * take a few events at the beginning and at the end and try
 347                  *   to match them
 348                  * </pre>
 349                  */
 350                 for (ITmfTrace trace : fTraces) {
 351                     monitor.beginTask(NLS.bind(Messages.TmfEventMatching_LookingEventsFrom, trace.getName()), IProgressMonitor.UNKNOWN);
 352                     setName(NLS.bind(Messages.TmfEventMatching_RequestingEventsFrom, trace.getName()));
 353
 354                     /* Send the request to the trace */
 355                     EventMatchingBuildRequest request = new EventMatchingBuildRequest(TmfEventMatching.this, trace, monitor);
 356                     trace.sendRequest(request);
 357                     try {
 358                         request.waitForCompletion();
 359                     } catch (InterruptedException e) {
 360                         Activator.logInfo(e.getMessage());
 361                     }
 362                     if (monitor.isCanceled()) {
 363                         return Status.CANCEL_STATUS;
 364                     }
 365                 }
 366                 return Status.OK_STATUS;
 367             }
 368         };
 369         job.schedule();
 370         try {
 371             job.join();
 372         } catch (InterruptedException e) {
 373
 374         }
 375
 376         finalizeMatching();
 377
 378         return true;
 379     }
 380
 381     /**
 382      * Registers an event match definition
 383      *
 384      * @param match
 385      *            The event matching definition
 386      */
 387     public static void registerMatchObject(ITmfMatchEventDefinition match) {
 388         MATCH_DEFINITIONS.add(match);
 389     }
 390
 391 }
 392
 393 class EventMatchingBuildRequest extends TmfEventRequest {
 394
 395     private final TmfEventMatching matching;
 396     private final ITmfTrace trace;
 397     private final @NonNull IProgressMonitor fMonitor;
 398
 399     EventMatchingBuildRequest(TmfEventMatching matching, ITmfTrace trace, IProgressMonitor monitor) {
 400         super(ITmfEvent.class,
 401                 TmfTimeRange.ETERNITY,
 402                 0,
 403                 ITmfEventRequest.ALL_DATA,
 404                 ITmfEventRequest.ExecutionType.FOREGROUND);
 405         this.matching = matching;
 406         this.trace = trace;
 407         if (monitor == null) {
 408             fMonitor = new NullProgressMonitor();
 409         } else {
 410             fMonitor = monitor;
 411         }
 412     }
 413
 414     @Override
 415     public void handleData(final ITmfEvent event) {
 416         super.handleData(event);
 417         if (fMonitor.isCanceled()) {
 418             this.cancel();
 419         }
 420         matching.matchEvent(event, trace, fMonitor);
 421     }
 422
 423     @Override
 424     public void handleSuccess() {
 425         super.handleSuccess();
 426     }
 427
 428     @Override
 429     public void handleCancel() {
 430         super.handleCancel();
 431     }
 432
 433     @Override
 434     public void handleFailure() {
 435         super.handleFailure();
 436     }
 437 }