From f44be666f279a4493bb2ad1e218f668dc4eace1f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Genevi=C3=A8ve=20Bastien?= Date: Wed, 2 Jul 2014 15:23:59 -0400 Subject: [PATCH] TMF: Change event matching key from a list to a plain old java object MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This improves performance of the event matching and trace synchronization Change-Id: Ib8fcb3152e3907d1218bc568bc51f77d7c32c1a1 Signed-off-by: Geneviève Bastien Reviewed-on: https://git.eclipse.org/r/36668 Tested-by: Hudson CI Reviewed-by: Matthew Khouzam --- .../event/matchandsync/MatchAndSyncTest.java | 22 +----- .../core/event/matching/TcpEventMatching.java | 25 ++---- .../event/matching/TcpLttngEventMatching.java | 65 ++++++++-------- .../META-INF/MANIFEST.MF | 3 +- .../event/matching/IEventMatchingKey.java | 30 ++++++++ .../matching/ITmfMatchEventDefinition.java | 7 +- .../tmf/core/event/matching/TcpEventKey.java | 77 +++++++++++++++++++ .../matching/TmfNetworkEventMatching.java | 50 +++++------- 8 files changed, 171 insertions(+), 108 deletions(-) create mode 100644 org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/IEventMatchingKey.java create mode 100644 org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TcpEventKey.java diff --git a/org.eclipse.tracecompass.lttng2.kernel.core.tests/src/org/eclipse/tracecompass/lttng2/kernel/core/tests/event/matchandsync/MatchAndSyncTest.java b/org.eclipse.tracecompass.lttng2.kernel.core.tests/src/org/eclipse/tracecompass/lttng2/kernel/core/tests/event/matchandsync/MatchAndSyncTest.java index 77d96617a2..5143deca3a 100644 --- a/org.eclipse.tracecompass.lttng2.kernel.core.tests/src/org/eclipse/tracecompass/lttng2/kernel/core/tests/event/matchandsync/MatchAndSyncTest.java +++ b/org.eclipse.tracecompass.lttng2.kernel.core.tests/src/org/eclipse/tracecompass/lttng2/kernel/core/tests/event/matchandsync/MatchAndSyncTest.java @@ -17,12 +17,10 @@ import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; import static org.junit.Assume.assumeTrue; -import java.lang.reflect.Field; import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; import java.util.LinkedList; import java.util.List; -import java.util.Map; import org.eclipse.tracecompass.internal.lttng2.kernel.core.event.matching.TcpEventMatching; import org.eclipse.tracecompass.internal.lttng2.kernel.core.event.matching.TcpLttngEventMatching; @@ -70,25 +68,7 @@ public class MatchAndSyncTest { IMatchProcessingUnit procUnit = (IMatchProcessingUnit) method.invoke(twoTraceMatch); assertEquals(46, procUnit.countMatches()); - /* Verify unmatched incoming */ - Field fieldIn = twoTraceMatch.getClass().getDeclaredField("fUnmatchedIn"); - fieldIn.setAccessible(true); - Map unmatched = (Map ) fieldIn.get(twoTraceMatch); - Map unmatchedTrace = (Map) unmatched.get(trace1); - assertEquals(3, unmatchedTrace.size()); - unmatchedTrace = (Map) unmatched.get(trace2); - assertEquals(2, unmatchedTrace.size()); - - /* Verify unmatched outgoing */ - Field fieldOut = twoTraceMatch.getClass().getDeclaredField("fUnmatchedOut"); - fieldOut.setAccessible(true); - unmatched = (Map ) fieldOut.get(twoTraceMatch); - unmatchedTrace = (Map) unmatched.get(trace1); - assertEquals(2, unmatchedTrace.size()); - unmatchedTrace = (Map) unmatched.get(trace2); - assertEquals(1, unmatchedTrace.size()); - - } catch (NoSuchMethodException | SecurityException | IllegalAccessException | IllegalArgumentException | InvocationTargetException | NoSuchFieldException e) { + } catch (NoSuchMethodException | SecurityException | IllegalAccessException | IllegalArgumentException | InvocationTargetException e) { fail(e.getMessage()); } diff --git a/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpEventMatching.java b/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpEventMatching.java index 7c631b6877..e1838c755c 100644 --- a/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpEventMatching.java +++ b/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpEventMatching.java @@ -12,14 +12,14 @@ package org.eclipse.tracecompass.internal.lttng2.kernel.core.event.matching; -import java.util.ArrayList; -import java.util.List; import java.util.Set; import org.eclipse.tracecompass.internal.lttng2.kernel.core.TcpEventStrings; import org.eclipse.tracecompass.tmf.core.event.ITmfEvent; import org.eclipse.tracecompass.tmf.core.event.ITmfEventField; +import org.eclipse.tracecompass.tmf.core.event.matching.IEventMatchingKey; import org.eclipse.tracecompass.tmf.core.event.matching.ITmfNetworkMatchDefinition; +import org.eclipse.tracecompass.tmf.core.event.matching.TcpEventKey; import org.eclipse.tracecompass.tmf.core.event.matching.TmfEventMatching.MatchingType; import org.eclipse.tracecompass.tmf.core.event.matching.TmfNetworkEventMatching.Direction; import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; @@ -72,23 +72,12 @@ public class TcpEventMatching implements ITmfNetworkMatchDefinition { return null; } - /** - * The key to uniquely identify a TCP packet depends on many fields. This - * method computes the key for a given event. - * - * @param event - * The event for which to compute the key - * @return the unique key for this event - */ @Override - public List getUniqueField(ITmfEvent event) { - List keys = new ArrayList<>(); - - keys.add(event.getContent().getField(TcpEventStrings.SEQ).getValue()); - keys.add(event.getContent().getField(TcpEventStrings.ACKSEQ).getValue()); - keys.add(event.getContent().getField(TcpEventStrings.FLAGS).getValue()); - - return keys; + public IEventMatchingKey getEventKey(ITmfEvent event) { + IEventMatchingKey key = new TcpEventKey((long) event.getContent().getField(TcpEventStrings.SEQ).getValue(), + (long) event.getContent().getField(TcpEventStrings.ACKSEQ).getValue(), + (long) event.getContent().getField(TcpEventStrings.FLAGS).getValue()); + return key; } @Override diff --git a/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpLttngEventMatching.java b/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpLttngEventMatching.java index 71d267058b..d628c22e25 100644 --- a/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpLttngEventMatching.java +++ b/org.eclipse.tracecompass.lttng2.kernel.core/src/org/eclipse/tracecompass/internal/lttng2/kernel/core/event/matching/TcpLttngEventMatching.java @@ -12,15 +12,15 @@ package org.eclipse.tracecompass.internal.lttng2.kernel.core.event.matching; -import java.util.ArrayList; -import java.util.List; import java.util.Set; import org.eclipse.tracecompass.internal.lttng2.kernel.core.TcpEventStrings; import org.eclipse.tracecompass.tmf.core.event.ITmfEvent; import org.eclipse.tracecompass.tmf.core.event.ITmfEventField; import org.eclipse.tracecompass.tmf.core.event.TmfEventField; +import org.eclipse.tracecompass.tmf.core.event.matching.IEventMatchingKey; import org.eclipse.tracecompass.tmf.core.event.matching.ITmfNetworkMatchDefinition; +import org.eclipse.tracecompass.tmf.core.event.matching.TcpEventKey; import org.eclipse.tracecompass.tmf.core.event.matching.TmfEventMatching.MatchingType; import org.eclipse.tracecompass.tmf.core.event.matching.TmfNetworkEventMatching.Direction; import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; @@ -60,37 +60,6 @@ public class TcpLttngEventMatching implements ITmfNetworkMatchDefinition { return false; } - /** - * The key to uniquely identify a TCP packet depends on many fields. This - * method computes the key for a given event. - * - * @param event - * The event for which to compute the key - * @return the unique key for this event - */ - @Override - public List getUniqueField(ITmfEvent event) { - List keys = new ArrayList<>(); - - TmfEventField field = (TmfEventField) event.getContent(); - ITmfEventField data; - - data = field.getSubField(key_seq); - if (data != null) { - keys.add(data.getValue()); - } - data = field.getSubField(key_ackseq); - if (data != null) { - keys.add(data.getValue()); - } - data = field.getSubField(key_flags); - if (data != null) { - keys.add(data.getValue()); - } - - return keys; - } - @Override public boolean canMatchTrace(ITmfTrace trace) { if (!(trace instanceof ITmfTraceWithPreDefinedEvents)) { @@ -122,4 +91,34 @@ public class TcpLttngEventMatching implements ITmfNetworkMatchDefinition { return types; } + @Override + public IEventMatchingKey getEventKey(ITmfEvent event) { + TmfEventField field = (TmfEventField) event.getContent(); + ITmfEventField data; + + long seq = -1, ackseq = -1, flags = -1; + data = field.getSubField(key_seq); + if (data != null) { + seq = (long) data.getValue(); + } else { + return null; + } + data = field.getSubField(key_ackseq); + if (data != null) { + ackseq = (long) data.getValue(); + } else { + return null; + } + data = field.getSubField(key_flags); + if (data != null) { + flags = (long) data.getValue(); + } else { + return null; + } + + IEventMatchingKey key = new TcpEventKey(seq, ackseq, flags); + + return key; + } + } diff --git a/org.eclipse.tracecompass.tmf.core/META-INF/MANIFEST.MF b/org.eclipse.tracecompass.tmf.core/META-INF/MANIFEST.MF index a8238207b3..a21836ea34 100644 --- a/org.eclipse.tracecompass.tmf.core/META-INF/MANIFEST.MF +++ b/org.eclipse.tracecompass.tmf.core/META-INF/MANIFEST.MF @@ -54,4 +54,5 @@ Export-Package: org.eclipse.tracecompass.internal.tmf.core;x-friends:="org.eclip org.eclipse.tracecompass.tmf.core.uml2sd, org.eclipse.tracecompass.tmf.core.util Import-Package: com.google.common.base, - com.google.common.collect + com.google.common.collect, + com.google.common.hash;version="15.0.0" diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/IEventMatchingKey.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/IEventMatchingKey.java new file mode 100644 index 0000000000..6a02932d6f --- /dev/null +++ b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/IEventMatchingKey.java @@ -0,0 +1,30 @@ +/******************************************************************************* + * Copyright (c) 2014 École Polytechnique de Montréal + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Geneviève Bastien - Initial API and implementation + *******************************************************************************/ + +package org.eclipse.tracecompass.tmf.core.event.matching; + +/** + * Interface that classes describing event matching keys should implement. An + * event matching key is a key obtained from an event's data/fields and that + * will be used to match events together. + * + * If you implement this interface, make sure to consider implementing the + * {@link Object#hashCode()} and {@link Object#equals(Object)} as they will be + * used to match 2 keys together. Keys will come from different events and 2 + * keys that are identical using the {@link Object#equals(Object)} method will + * create a match. + * + * @author Geneviève Bastien + */ +public interface IEventMatchingKey { + +} diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/ITmfMatchEventDefinition.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/ITmfMatchEventDefinition.java index 0115f8cb6b..63d92ebde8 100644 --- a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/ITmfMatchEventDefinition.java +++ b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/ITmfMatchEventDefinition.java @@ -12,8 +12,6 @@ package org.eclipse.tracecompass.tmf.core.event.matching; -import java.util.List; - import org.eclipse.tracecompass.tmf.core.event.ITmfEvent; import org.eclipse.tracecompass.tmf.core.event.matching.TmfEventMatching.MatchingType; import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; @@ -28,13 +26,14 @@ import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; public interface ITmfMatchEventDefinition { /** - * Returns a list of values for an event that uniquely identifies this event + * Returns a key for an event that uniquely identifies this event and will + * match the key from another event. * * @param event * The event for which to compute the key * @return the unique key for this event */ - List getUniqueField(ITmfEvent event); + IEventMatchingKey getEventKey(ITmfEvent event); /** * Verifies whether a trace has all required events to match using this diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TcpEventKey.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TcpEventKey.java new file mode 100644 index 0000000000..1fd832903d --- /dev/null +++ b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TcpEventKey.java @@ -0,0 +1,77 @@ +/******************************************************************************* + * Copyright (c) 2014 École Polytechnique de Montréal + * + * All rights reserved. This program and the accompanying materials are + * made available under the terms of the Eclipse Public License v1.0 which + * accompanies this distribution, and is available at + * http://www.eclipse.org/legal/epl-v10.html + * + * Contributors: + * Geneviève Bastien - Initial API and implementation + *******************************************************************************/ + +package org.eclipse.tracecompass.tmf.core.event.matching; + +import org.eclipse.jdt.annotation.NonNull; +import org.eclipse.jdt.annotation.NonNullByDefault; +import org.eclipse.jdt.annotation.Nullable; + +import com.google.common.hash.HashFunction; +import com.google.common.hash.Hashing; + +/** + * Traces can be matched using TCP network packets. To uniquely match a TCP + * packet from a trace with one from another trace, the three following fields + * are used: sequence number, acknowledgment number and the 16-bits following + * the acknowledgment number (data offset, reserved and flags). + * + * All match definitions using TCP fields should return a key of this type so + * all TCP matching methods are compatible. + * + * @author Geneviève Bastien + */ +@NonNullByDefault +public class TcpEventKey implements IEventMatchingKey { + + @SuppressWarnings("null") + private static final @NonNull HashFunction hf = Hashing.goodFastHash(32); + private final long fSeq; + private final long fAckseq; + private final long fFlags; + + /** + * Constructor + * + * @param sequence + * The sequence number of the TCP packet + * @param ack + * The acknowledgement number of the TCP packet + * @param flags + * The 16 bits following the acknowledgment: data offset, + * reserved and flags) + */ + public TcpEventKey(long sequence, long ack, long flags) { + fSeq = sequence; + fAckseq = ack; + fFlags = flags; + } + + @Override + public int hashCode() { + return hf.newHasher() + .putLong(fSeq) + .putLong(fAckseq) + .putLong(fFlags).hash().asInt(); + } + + @Override + public boolean equals(@Nullable Object o) { + if (o instanceof TcpEventKey) { + TcpEventKey key = (TcpEventKey) o; + return (key.fSeq == fSeq && + key.fAckseq == fAckseq && + key.fFlags == fFlags); + } + return false; + } +} diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TmfNetworkEventMatching.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TmfNetworkEventMatching.java index 2cd8385711..e5e54770ce 100644 --- a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TmfNetworkEventMatching.java +++ b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/event/matching/TmfNetworkEventMatching.java @@ -13,14 +13,13 @@ package org.eclipse.tracecompass.tmf.core.event.matching; import java.util.Collection; -import java.util.HashMap; -import java.util.LinkedHashMap; -import java.util.List; -import java.util.Map; import org.eclipse.tracecompass.tmf.core.event.ITmfEvent; import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace; +import com.google.common.collect.HashBasedTable; +import com.google.common.collect.Table; + /** * This class matches events typically network-style, ie. where some events are * 'send' events and the other 'receive' events or out/in events @@ -33,12 +32,12 @@ public class TmfNetworkEventMatching extends TmfEventMatching { /** * Hashtables for unmatches incoming events */ - private final Map, ITmfEvent>> fUnmatchedIn = new LinkedHashMap<>(); + private final Table fUnmatchedIn = HashBasedTable.create(); /** * Hashtables for unmatches outgoing events */ - private final Map, ITmfEvent>> fUnmatchedOut = new LinkedHashMap<>(); + private final Table fUnmatchedOut = HashBasedTable.create(); /** * Enum for in and out types @@ -84,24 +83,9 @@ public class TmfNetworkEventMatching extends TmfEventMatching { // Initialize the matching infrastructure (unmatched event lists) fUnmatchedIn.clear(); fUnmatchedOut.clear(); - for (ITmfTrace trace : getIndividualTraces()) { - fUnmatchedIn.put(trace, new HashMap, ITmfEvent>()); - fUnmatchedOut.put(trace, new HashMap, ITmfEvent>()); - } super.initMatching(); } - /** - * Function that counts the events in a hashtable. - * - * @param tbl - * The table to count events for - * @return The number of events - */ - protected int countEvents(Map, ITmfEvent> tbl) { - return tbl.size(); - } - @Override protected MatchingType getMatchingType() { return MatchingType.NETWORK; @@ -126,8 +110,12 @@ public class TmfNetworkEventMatching extends TmfEventMatching { } /* Get the event's unique fields */ - List eventKey = def.getUniqueField(event); - Map, ITmfEvent>> unmatchedTbl, companionTbl; + IEventMatchingKey eventKey = def.getEventKey(event); + + if (eventKey == null) { + return; + } + Table unmatchedTbl, companionTbl; /* Point to the appropriate table */ switch (evType) { @@ -146,13 +134,13 @@ public class TmfNetworkEventMatching extends TmfEventMatching { boolean found = false; TmfEventDependency dep = null; /* Search for the event in the companion table */ - for (Map, ITmfEvent> map : companionTbl.values()) { - if (map.containsKey(eventKey)) { + for (ITmfTrace mTrace : getIndividualTraces()) { + if (companionTbl.contains(mTrace, eventKey)) { found = true; - ITmfEvent companionEvent = map.get(eventKey); + ITmfEvent companionEvent = companionTbl.get(mTrace, eventKey); /* Remove the element from the companion table */ - map.remove(eventKey); + companionTbl.remove(mTrace, eventKey); /* Create the dependency object */ switch (evType) { @@ -187,8 +175,8 @@ public class TmfNetworkEventMatching extends TmfEventMatching { * events as value for the unmatched table. Not necessary right now * though */ - if (!unmatchedTbl.get(event.getTrace()).containsKey(eventKey)) { - unmatchedTbl.get(event.getTrace()).put(eventKey, event); + if (!unmatchedTbl.contains(event.getTrace(), eventKey)) { + unmatchedTbl.put(event.getTrace(), eventKey, event); } } @@ -208,8 +196,8 @@ public class TmfNetworkEventMatching extends TmfEventMatching { int i = 0; for (ITmfTrace trace : getIndividualTraces()) { b.append("Trace " + i++ + ":" + cr + - " " + countEvents(fUnmatchedIn.get(trace)) + " unmatched incoming events" + cr + - " " + countEvents(fUnmatchedOut.get(trace)) + " unmatched outgoing events" + cr); + " " + fUnmatchedIn.row(trace).size() + " unmatched incoming events" + cr + + " " + fUnmatchedOut.row(trace).size() + " unmatched outgoing events" + cr); } return b.toString(); -- 2.34.1