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