diff --git a/runtime/art_method.cc b/runtime/art_method.cc
index f4a5f23..2a8cf99 100644
--- a/runtime/art_method.cc
+++ b/runtime/art_method.cc
@@ -367,6 +367,10 @@
 }
 
 const OatQuickMethodHeader* ArtMethod::GetOatQuickMethodHeader(uintptr_t pc) {
+  // Our callers should make sure they don't pass the instrumentation exit pc,
+  // as this method does not look at the side instrumentation stack.
+  DCHECK_NE(pc, reinterpret_cast<uintptr_t>(GetQuickInstrumentationExitPc()));
+
   if (IsRuntimeMethod()) {
     return nullptr;
   }
@@ -434,7 +438,7 @@
   }
   const void* oat_entry_point = oat_method.GetQuickCode();
   if (oat_entry_point == nullptr || class_linker->IsQuickGenericJniStub(oat_entry_point)) {
-    DCHECK(IsNative());
+    DCHECK(IsNative()) << PrettyMethod(this);
     return nullptr;
   }
 
@@ -445,12 +449,6 @@
     return method_header;
   }
 
-  if (pc == reinterpret_cast<uintptr_t>(GetQuickInstrumentationExitPc())) {
-    // If we're instrumenting, just return the compiled OAT code.
-    // TODO(ngeoffray): Avoid this call path.
-    return method_header;
-  }
-
   DCHECK(method_header->Contains(pc))
       << PrettyMethod(this)
       << std::hex << pc << " " << oat_entry_point
diff --git a/runtime/instrumentation.cc b/runtime/instrumentation.cc
index 4db37e6..c6a9e6c 100644
--- a/runtime/instrumentation.cc
+++ b/runtime/instrumentation.cc
@@ -66,13 +66,20 @@
 
 
 Instrumentation::Instrumentation()
-    : instrumentation_stubs_installed_(false), entry_exit_stubs_installed_(false),
+    : instrumentation_stubs_installed_(false),
+      entry_exit_stubs_installed_(false),
       interpreter_stubs_installed_(false),
-      interpret_only_(false), forced_interpret_only_(false),
-      have_method_entry_listeners_(false), have_method_exit_listeners_(false),
-      have_method_unwind_listeners_(false), have_dex_pc_listeners_(false),
-      have_field_read_listeners_(false), have_field_write_listeners_(false),
-      have_exception_caught_listeners_(false), have_backward_branch_listeners_(false),
+      interpret_only_(false),
+      forced_interpret_only_(false),
+      have_method_entry_listeners_(false),
+      have_method_exit_listeners_(false),
+      have_method_unwind_listeners_(false),
+      have_dex_pc_listeners_(false),
+      have_field_read_listeners_(false),
+      have_field_write_listeners_(false),
+      have_exception_caught_listeners_(false),
+      have_backward_branch_listeners_(false),
+      have_invoke_virtual_or_interface_listeners_(false),
       deoptimized_methods_lock_("deoptimized methods lock"),
       deoptimization_enabled_(false),
       interpreter_handler_table_(kMainHandlerTable),
@@ -297,7 +304,9 @@
 
 // Removes the instrumentation exit pc as the return PC for every quick frame.
 static void InstrumentationRestoreStack(Thread* thread, void* arg)
-    SHARED_REQUIRES(Locks::mutator_lock_) {
+    REQUIRES(Locks::mutator_lock_) {
+  Locks::mutator_lock_->AssertExclusiveHeld(Thread::Current());
+
   struct RestoreStackVisitor FINAL : public StackVisitor {
     RestoreStackVisitor(Thread* thread_in, uintptr_t instrumentation_exit_pc,
                         Instrumentation* instrumentation)
@@ -594,9 +603,11 @@
       empty = IsDeoptimizedMethodsEmpty();  // Avoid lock violation.
     }
     if (empty) {
-      instrumentation_stubs_installed_ = false;
       MutexLock mu(self, *Locks::thread_list_lock_);
       Runtime::Current()->GetThreadList()->ForEach(InstrumentationRestoreStack, this);
+      // Only do this after restoring, as walking the stack when restoring will see
+      // the instrumentation exit pc.
+      instrumentation_stubs_installed_ = false;
     }
   }
 }
diff --git a/runtime/jit/jit_code_cache.cc b/runtime/jit/jit_code_cache.cc
index ce972ef..4c7cb1e 100644
--- a/runtime/jit/jit_code_cache.cc
+++ b/runtime/jit/jit_code_cache.cc
@@ -370,6 +370,23 @@
     DCHECK(thread == Thread::Current() || thread->IsSuspended());
     MarkCodeVisitor visitor(thread, code_cache_);
     visitor.WalkStack();
+    if (kIsDebugBuild) {
+      // The stack walking code queries the side instrumentation stack if it
+      // sees an instrumentation exit pc, so the JIT code of methods in that stack
+      // must have been seen. We sanity check this below.
+      for (const instrumentation::InstrumentationStackFrame& frame
+              : *thread->GetInstrumentationStack()) {
+        // The 'method_' in InstrumentationStackFrame is the one that has return_pc_ in
+        // its stack frame, it is not the method owning return_pc_. We just pass null to
+        // LookupMethodHeader: the method is only checked against in debug builds.
+        OatQuickMethodHeader* method_header =
+            code_cache_->LookupMethodHeader(frame.return_pc_, nullptr);
+        if (method_header != nullptr) {
+          const void* code = method_header->GetCode();
+          CHECK(code_cache_->GetLiveBitmap()->Test(FromCodeToAllocation(code)));
+        }
+      }
+    }
     barrier_->Pass(Thread::Current());
   }
 
@@ -489,8 +506,10 @@
   if (!method_header->Contains(pc)) {
     return nullptr;
   }
-  DCHECK_EQ(it->second, method)
-      << PrettyMethod(method) << " " << PrettyMethod(it->second) << " " << std::hex << pc;
+  if (kIsDebugBuild && method != nullptr) {
+    DCHECK_EQ(it->second, method)
+        << PrettyMethod(method) << " " << PrettyMethod(it->second) << " " << std::hex << pc;
+  }
   return method_header;
 }
 
diff --git a/test/545-tracing-and-jit/expected.txt b/test/545-tracing-and-jit/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/545-tracing-and-jit/expected.txt
diff --git a/test/545-tracing-and-jit/info.txt b/test/545-tracing-and-jit/info.txt
new file mode 100644
index 0000000..34e654e
--- /dev/null
+++ b/test/545-tracing-and-jit/info.txt
@@ -0,0 +1,2 @@
+Tests interaction between the JIT and the method tracing
+functionality.
diff --git a/test/545-tracing-and-jit/src/Main.java b/test/545-tracing-and-jit/src/Main.java
new file mode 100644
index 0000000..d3c79ae
--- /dev/null
+++ b/test/545-tracing-and-jit/src/Main.java
@@ -0,0 +1,242 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+import java.io.File;
+import java.io.IOException;
+import java.lang.reflect.Method;
+import java.util.concurrent.ConcurrentSkipListMap;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+public class Main {
+    private static final String TEMP_FILE_NAME_PREFIX = "test";
+    private static final String TEMP_FILE_NAME_SUFFIX = ".trace";
+    private static File file;
+
+    public static void main(String[] args) throws Exception {
+        String name = System.getProperty("java.vm.name");
+        if (!"Dalvik".equals(name)) {
+            System.out.println("This test is not supported on " + name);
+            return;
+        }
+        file = createTempFile();
+        try {
+            new Main().ensureCaller(true, 0);
+            new Main().ensureCaller(false, 0);
+        } finally {
+            if (file != null) {
+              file.delete();
+            }
+        }
+    }
+
+    private static File createTempFile() throws Exception {
+        try {
+            return  File.createTempFile(TEMP_FILE_NAME_PREFIX, TEMP_FILE_NAME_SUFFIX);
+        } catch (IOException e) {
+            System.setProperty("java.io.tmpdir", "/data/local/tmp");
+            try {
+                return File.createTempFile(TEMP_FILE_NAME_PREFIX, TEMP_FILE_NAME_SUFFIX);
+            } catch (IOException e2) {
+                System.setProperty("java.io.tmpdir", "/sdcard");
+                return File.createTempFile(TEMP_FILE_NAME_PREFIX, TEMP_FILE_NAME_SUFFIX);
+            }
+        }
+    }
+
+    // We make sure 'doLoadsOfStuff' has a caller, because it is this caller that will be
+    // pushed in the side instrumentation frame.
+    public void ensureCaller(boolean warmup, int invocationCount) throws Exception {
+        doLoadsOfStuff(warmup, invocationCount);
+    }
+
+    // The number of recursive calls we are going to do in 'doLoadsOfStuff' to ensure
+    // the JIT sees it hot.
+    static final int NUMBER_OF_INVOCATIONS = 5;
+
+    public void doLoadsOfStuff(boolean warmup, int invocationCount) throws Exception {
+        // Warmup is to make sure the JIT gets a chance to compile 'doLoadsOfStuff'.
+        if (warmup) {
+            if (invocationCount < NUMBER_OF_INVOCATIONS) {
+                doLoadsOfStuff(warmup, ++invocationCount);
+            } else {
+                // Give the JIT a chance to compiler.
+                Thread.sleep(1000);
+            }
+        } else {
+            if (invocationCount == 0) {
+                VMDebug.startMethodTracing(file.getPath(), 0, 0, false, 0);
+            }
+            fillJit();
+            if (invocationCount < NUMBER_OF_INVOCATIONS) {
+                doLoadsOfStuff(warmup, ++invocationCount);
+            } else {
+                VMDebug.stopMethodTracing();
+            }
+        }
+    }
+
+    // This method creates enough profiling data to fill the code cache and trigger
+    // a collection in debug mode (at the time of the test 10KB of data space). We
+    // used to crash by not looking at the instrumentation stack and deleting JIT code
+    // that will be later restored by the instrumentation.
+    public static void fillJit() throws Exception {
+        Map map = new HashMap();
+        map.put("foo", "bar");
+        map.clear();
+        map.containsKey("foo");
+        map.containsValue("foo");
+        map.entrySet();
+        map.equals(map);
+        map.hashCode();
+        map.isEmpty();
+        map.keySet();
+        map.putAll(map);
+        map.remove("foo");
+        map.size();
+        map.put("bar", "foo");
+        map.values();
+
+        map = new LinkedHashMap();
+        map.put("foo", "bar");
+        map.clear();
+        map.containsKey("foo");
+        map.containsValue("foo");
+        map.entrySet();
+        map.equals(map);
+        map.hashCode();
+        map.isEmpty();
+        map.keySet();
+        map.putAll(map);
+        map.remove("foo");
+        map.size();
+        map.put("bar", "foo");
+        map.values();
+
+        map = new TreeMap();
+        map.put("foo", "bar");
+        map.clear();
+        map.containsKey("foo");
+        map.containsValue("foo");
+        map.entrySet();
+        map.equals(map);
+        map.hashCode();
+        map.isEmpty();
+        map.keySet();
+        map.putAll(map);
+        map.remove("foo");
+        map.size();
+        map.put("bar", "foo");
+        map.values();
+
+        map = new ConcurrentSkipListMap();
+        map.put("foo", "bar");
+        map.clear();
+        map.containsKey("foo");
+        map.containsValue("foo");
+        map.entrySet();
+        map.equals(map);
+        map.hashCode();
+        map.isEmpty();
+        map.keySet();
+        map.putAll(map);
+        map.remove("foo");
+        map.size();
+        map.put("bar", "foo");
+        map.values();
+
+        Set set = new HashSet();
+        set.add("foo");
+        set.addAll(set);
+        set.clear();
+        set.contains("foo");
+        set.containsAll(set);
+        set.equals(set);
+        set.hashCode();
+        set.isEmpty();
+        set.iterator();
+        set.remove("foo");
+        set.removeAll(set);
+        set.retainAll(set);
+        set.size();
+        set.add("foo");
+        set.toArray();
+
+        set = new LinkedHashSet();
+        set.add("foo");
+        set.addAll(set);
+        set.clear();
+        set.contains("foo");
+        set.containsAll(set);
+        set.equals(set);
+        set.hashCode();
+        set.isEmpty();
+        set.iterator();
+        set.remove("foo");
+        set.removeAll(set);
+        set.retainAll(set);
+        set.size();
+        set.add("foo");
+        set.toArray();
+
+        set = new TreeSet();
+        set.add("foo");
+        set.addAll(set);
+        set.clear();
+        set.contains("foo");
+        set.containsAll(set);
+        set.equals(set);
+        set.hashCode();
+        set.isEmpty();
+        set.iterator();
+        set.remove("foo");
+        set.removeAll(set);
+        set.retainAll(set);
+        set.size();
+        set.add("foo");
+        set.toArray();
+    }
+
+    private static class VMDebug {
+        private static final Method startMethodTracingMethod;
+        private static final Method stopMethodTracingMethod;
+        static {
+            try {
+                Class c = Class.forName("dalvik.system.VMDebug");
+                startMethodTracingMethod = c.getDeclaredMethod("startMethodTracing", String.class,
+                        Integer.TYPE, Integer.TYPE, Boolean.TYPE, Integer.TYPE);
+                stopMethodTracingMethod = c.getDeclaredMethod("stopMethodTracing");
+            } catch (Exception e) {
+                throw new RuntimeException(e);
+            }
+        }
+
+        public static void startMethodTracing(String filename, int bufferSize, int flags,
+                boolean samplingEnabled, int intervalUs) throws Exception {
+            startMethodTracingMethod.invoke(null, filename, bufferSize, flags, samplingEnabled,
+                    intervalUs);
+        }
+        public static void stopMethodTracing() throws Exception {
+            stopMethodTracingMethod.invoke(null);
+        }
+    }
+}