summaryrefslogtreecommitdiffstatsabout
diff options
context:
space:
mode:
authorSimon Delisle2013-05-09 12:58:54 (EDT)
committer Alexandre Montplaisir2013-07-04 18:43:41 (EDT)
commit972869380c66a93ecb448be8b56afde4c9964ab5 (patch)
treea0b6877e01f8209e1d6f7943968c3b2b7ae48a65
parent46201da19d01a67e96e2f235816bf02aa9d381bb (diff)
downloadorg.eclipse.linuxtools-972869380c66a93ecb448be8b56afde4c9964ab5.zip
org.eclipse.linuxtools-972869380c66a93ecb448be8b56afde4c9964ab5.tar.gz
org.eclipse.linuxtools-972869380c66a93ecb448be8b56afde4c9964ab5.tar.bz2
Ctf: Callsite bug fix when position is negative (binarySearch)refs/changes/09/14109/3
Change-Id: Id1fdb06c717299f7b0fa8ad0576485d35003ce2b Signed-off-by: Simon Delisle <simon.delisle@ericsson.com> Reviewed-on: https://git.eclipse.org/r/14109 Tested-by: Hudson CI IP-Clean: Alexandre Montplaisir <alexmonthy@voxpopuli.im> Tested-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im> Reviewed-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
-rw-r--r--lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceCallsitePerformanceTest.java4
-rw-r--r--lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceTest.java23
-rw-r--r--lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/CTFTrace.java51
-rw-r--r--lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/event/CTFCallsiteComparator.java72
4 files changed, 119 insertions, 31 deletions
diff --git a/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceCallsitePerformanceTest.java b/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceCallsitePerformanceTest.java
index c361ec2..2d11615 100644
--- a/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceCallsitePerformanceTest.java
+++ b/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceCallsitePerformanceTest.java
@@ -15,8 +15,8 @@ import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertTrue;
import static org.junit.Assume.assumeTrue;
-import java.util.List;
import java.util.Random;
+import java.util.TreeSet;
import org.eclipse.linuxtools.ctf.core.event.CTFCallsite;
import org.eclipse.linuxtools.ctf.core.tests.shared.CtfTestTraces;
@@ -93,7 +93,7 @@ public class CTFTraceCallsitePerformanceTest {
}
private long testMain() {
- List<CTFCallsite> l = fTrace.getCallsiteCandidates(callsites[0]);
+ TreeSet<CTFCallsite> l = fTrace.getCallsiteCandidates(callsites[0]);
CTFCallsite cs = fTrace.getCallsite(1);
CTFCallsite cs1 = fTrace.getCallsite(callsites[0]);
CTFCallsite cs2 = fTrace.getCallsite(callsites[0], 1);
diff --git a/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceTest.java b/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceTest.java
index 6d94600..c0a4379 100644
--- a/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceTest.java
+++ b/lttng/org.eclipse.linuxtools.ctf.core.tests/src/org/eclipse/linuxtools/ctf/core/tests/trace/CTFTraceTest.java
@@ -8,6 +8,7 @@
* Contributors:
* Matthew Khouzam - Initial API and implementation
* Marc-Andre Laperle - Test in traces directory recursively
+ * Simon Delisle - Add test for getCallsite(eventName, ip)
*******************************************************************************/
package org.eclipse.linuxtools.ctf.core.tests.trace;
@@ -451,4 +452,26 @@ public class CTFTraceTest {
}
}
+ /**
+ * Test for getCallsite(eventName, ip)
+ */
+ @Test
+ public void callsitePosition(){
+ long ip1 = 2;
+ long ip2 = 5;
+ long ip3 = 7;
+ CTFTrace callsiteTest = CtfTestTraces.getTestTraceFromFile(TRACE_INDEX);
+ callsiteTest.addCallsite("testEvent", null, ip1, null, 23);
+ callsiteTest.addCallsite("testEvent", null, ip2, null, 50);
+ callsiteTest.addCallsite("testEvent", null, ip3, null, 15);
+
+ assertEquals(2, (callsiteTest.getCallsite("testEvent", 1)).getIp());
+ assertEquals(2, (callsiteTest.getCallsite("testEvent", 2)).getIp());
+ assertEquals(5, (callsiteTest.getCallsite("testEvent", 3)).getIp());
+ assertEquals(5, (callsiteTest.getCallsite("testEvent", 5)).getIp());
+ assertEquals(7, (callsiteTest.getCallsite("testEvent", 6)).getIp());
+ assertEquals(7, (callsiteTest.getCallsite("testEvent", 7)).getIp());
+ assertEquals(7, (callsiteTest.getCallsite("testEvent", 8)).getIp());
+ }
+
}
diff --git a/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/CTFTrace.java b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/CTFTrace.java
index f7b0bad..a71d92f 100644
--- a/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/CTFTrace.java
+++ b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/ctf/core/trace/CTFTrace.java
@@ -9,6 +9,7 @@
* Contributors:
* Matthew Khouzam - Initial API and implementation
* Alexandre Montplaisir - Initial API and implementation
+ * Simon Delisle - Replace LinkedList by TreeSet in callsitesByName attribute
*******************************************************************************/
package org.eclipse.linuxtools.ctf.core.trace;
@@ -23,13 +24,11 @@ import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
import java.util.Arrays;
-import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
-import java.util.ListIterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
@@ -47,6 +46,7 @@ import org.eclipse.linuxtools.ctf.core.event.types.IDefinitionScope;
import org.eclipse.linuxtools.ctf.core.event.types.IntegerDefinition;
import org.eclipse.linuxtools.ctf.core.event.types.StructDeclaration;
import org.eclipse.linuxtools.ctf.core.event.types.StructDefinition;
+import org.eclipse.linuxtools.internal.ctf.core.event.CTFCallsiteComparator;
import org.eclipse.linuxtools.internal.ctf.core.event.metadata.exceptions.ParseException;
import org.eclipse.linuxtools.internal.ctf.core.trace.StreamInputPacketIndex;
@@ -144,7 +144,9 @@ public class CTFTrace implements IDefinitionScope {
private final Map<StreamInput, StreamInputPacketIndex> indexes = new HashMap<StreamInput, StreamInputPacketIndex>();
/** Callsite helpers */
- private Map<String, LinkedList<CTFCallsite>> callsitesByName = new HashMap<String, LinkedList<CTFCallsite>>();
+ private CTFCallsiteComparator ctfCallsiteComparator = new CTFCallsiteComparator();
+
+ private Map<String, TreeSet<CTFCallsite>> callsitesByName = new HashMap<String, TreeSet<CTFCallsite>>();
/** Callsite helpers */
private TreeSet<CTFCallsite> callsitesByIP = new TreeSet<CTFCallsite>();
@@ -837,37 +839,29 @@ public class CTFTrace implements IDefinitionScope {
String fileName, long lineNumber) {
final CTFCallsite cs = new CTFCallsite(eventName, funcName, ip,
fileName, lineNumber);
- LinkedList<CTFCallsite> csl = callsitesByName.get(eventName);
+ TreeSet<CTFCallsite> csl = callsitesByName.get(eventName);
if (csl == null) {
- csl = new LinkedList<CTFCallsite>();
+ csl = new TreeSet<CTFCallsite>(ctfCallsiteComparator);
callsitesByName.put(eventName, csl);
}
- ListIterator<CTFCallsite> iter = csl.listIterator();
- int index = 0;
- for (; index < csl.size(); index++) {
- if (iter.next().compareTo(cs) < 0) {
- break;
- }
- }
-
- csl.add(index, cs);
+ csl.add(cs);
callsitesByIP.add(cs);
}
/**
- * Gets the list of callsites associated to an event name. O(1)
+ * Gets the set of callsites associated to an event name. O(1)
*
* @param eventName
* the event name
- * @return the callsite list can be empty
- * @since 1.2
+ * @return the callsite set can be empty
+ * @since 3.0
*/
- public List<CTFCallsite> getCallsiteCandidates(String eventName) {
- LinkedList<CTFCallsite> retVal = callsitesByName.get(eventName);
- if( retVal == null ) {
- retVal = new LinkedList<CTFCallsite>();
+ public TreeSet<CTFCallsite> getCallsiteCandidates(String eventName) {
+ TreeSet<CTFCallsite> retVal = callsitesByName.get(eventName);
+ if (retVal == null) {
+ retVal = new TreeSet<CTFCallsite>(ctfCallsiteComparator);
}
return retVal;
}
@@ -881,9 +875,9 @@ public class CTFTrace implements IDefinitionScope {
* @since 1.2
*/
public CTFCallsite getCallsite(String eventName) {
- LinkedList<CTFCallsite> callsites = callsitesByName.get(eventName);
+ TreeSet<CTFCallsite> callsites = callsitesByName.get(eventName);
if (callsites != null) {
- return callsites.getFirst();
+ return callsites.first();
}
return null;
}
@@ -912,15 +906,14 @@ public class CTFTrace implements IDefinitionScope {
* @return the closest matching callsite, can be null
*/
public CTFCallsite getCallsite(String eventName, long ip) {
- final LinkedList<CTFCallsite> candidates = callsitesByName.get(eventName);
+ final TreeSet<CTFCallsite> candidates = callsitesByName.get(eventName);
final CTFCallsite dummyCs = new CTFCallsite(null, null, ip, null, -1);
- final int pos = Collections.binarySearch(candidates, dummyCs)+1;
- if( pos >= candidates.size()) {
- return null;
+ final CTFCallsite callsite = candidates.ceiling(dummyCs);
+ if (callsite == null) {
+ return candidates.floor(dummyCs);
}
- return candidates.get(pos);
+ return callsite;
}
-
}
class MetadataFileFilter implements FileFilter {
diff --git a/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/event/CTFCallsiteComparator.java b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/event/CTFCallsiteComparator.java
new file mode 100644
index 0000000..ab36f0a
--- /dev/null
+++ b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/event/CTFCallsiteComparator.java
@@ -0,0 +1,72 @@
+/*******************************************************************************
+ * Copyright (c) 2013 Ericsson
+ *
+ * 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:
+ * Simon Delisle - Initial implementation
+ *******************************************************************************/
+
+package org.eclipse.linuxtools.internal.ctf.core.event;
+
+import java.util.Comparator;
+
+import org.eclipse.linuxtools.ctf.core.event.CTFCallsite;
+
+/**
+ * Comparator for CTFCallsite
+ *
+ * @author Simon Delisle
+ * @since 3.0
+ *
+ */
+public class CTFCallsiteComparator implements Comparator<CTFCallsite> {
+
+ private static final long MASK32 = 0x00000000ffffffffL;
+
+ /*
+ * The callsites will be sorted by calling addresses. To do this we take IPs
+ * (instruction pointers) and compare them. Java only supports signed
+ * operation and since memory addresses are unsigned, we will convert the
+ * longs into integers that contain the high and low bytes and compare them.
+ */
+ @Override
+ public int compare(CTFCallsite o1, CTFCallsite o2) {
+ /*
+ * mask32 is 32 zeros followed by 32 ones, when we bitwise and this it
+ * will return the lower 32 bits
+ */
+
+ long other = o2.getIp();
+ /*
+ * To get a high int: we downshift by 32 and bitwise and with the mask
+ * to get rid of the sign
+ *
+ * To get the low int: we bitwise and with the mask.
+ */
+ long otherHigh = (other >> 32) & MASK32;
+ long otherLow = other & MASK32;
+ long ownHigh = (o1.getIp() >> 32) & MASK32;
+ long ownLow = o1.getIp() & MASK32;
+ /* are the high values different, if so ignore the lower values */
+ if (ownHigh > otherHigh) {
+ return 1;
+ }
+ if (ownHigh < otherHigh ) {
+ return -1;
+ }
+ /* the high values are the same, compare the lower values */
+ if (ownLow > otherLow) {
+ return 1;
+ }
+ if (ownLow < otherLow) {
+ return -1;
+ }
+ /* the values are identical */
+ return 0;
+ }
+
+}