diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 0fb2a8b..a47e711 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -838,21 +838,73 @@
   return true;
 }
 
-class ImageWriter::NonImageClassesVisitor : public ClassVisitor {
+class ImageWriter::PruneClassesVisitor : public ClassVisitor {
  public:
-  explicit NonImageClassesVisitor(ImageWriter* image_writer) : image_writer_(image_writer) {}
+  PruneClassesVisitor(ImageWriter* image_writer, ObjPtr<mirror::ClassLoader> class_loader)
+      : image_writer_(image_writer),
+        class_loader_(class_loader),
+        classes_to_prune_(),
+        defined_class_count_(0u) { }
 
-  bool operator()(ObjPtr<Class> klass) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
+  bool operator()(ObjPtr<mirror::Class> klass) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
     if (!image_writer_->KeepClass(klass.Ptr())) {
       classes_to_prune_.insert(klass.Ptr());
+      if (klass->GetClassLoader() == class_loader_) {
+        ++defined_class_count_;
+      }
     }
     return true;
   }
 
-  std::unordered_set<mirror::Class*> classes_to_prune_;
+  size_t Prune() REQUIRES_SHARED(Locks::mutator_lock_) {
+    ClassTable* class_table =
+        Runtime::Current()->GetClassLinker()->ClassTableForClassLoader(class_loader_);
+    for (mirror::Class* klass : classes_to_prune_) {
+      std::string storage;
+      const char* descriptor = klass->GetDescriptor(&storage);
+      bool result = class_table->Remove(descriptor);
+      DCHECK(result);
+      DCHECK(!class_table->Remove(descriptor)) << descriptor;
+    }
+    return defined_class_count_;
+  }
+
+ private:
   ImageWriter* const image_writer_;
+  const ObjPtr<mirror::ClassLoader> class_loader_;
+  std::unordered_set<mirror::Class*> classes_to_prune_;
+  size_t defined_class_count_;
 };
 
+class ImageWriter::PruneClassLoaderClassesVisitor : public ClassLoaderVisitor {
+ public:
+  explicit PruneClassLoaderClassesVisitor(ImageWriter* image_writer)
+      : image_writer_(image_writer), removed_class_count_(0) {}
+
+  virtual void Visit(ObjPtr<mirror::ClassLoader> class_loader) OVERRIDE
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    PruneClassesVisitor classes_visitor(image_writer_, class_loader);
+    ClassTable* class_table =
+        Runtime::Current()->GetClassLinker()->ClassTableForClassLoader(class_loader);
+    class_table->Visit(classes_visitor);
+    removed_class_count_ += classes_visitor.Prune();
+  }
+
+  size_t GetRemovedClassCount() const {
+    return removed_class_count_;
+  }
+
+ private:
+  ImageWriter* const image_writer_;
+  size_t removed_class_count_;
+};
+
+void ImageWriter::VisitClassLoaders(ClassLoaderVisitor* visitor) {
+  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+  visitor->Visit(nullptr);  // Visit boot class loader.
+  Runtime::Current()->GetClassLinker()->VisitClassLoaders(visitor);
+}
+
 void ImageWriter::PruneNonImageClasses() {
   Runtime* runtime = Runtime::Current();
   ClassLinker* class_linker = runtime->GetClassLinker();
@@ -862,21 +914,11 @@
   // path dex caches.
   class_linker->ClearClassTableStrongRoots();
 
-  // Make a list of classes we would like to prune.
-  NonImageClassesVisitor visitor(this);
-  class_linker->VisitClasses(&visitor);
-
   // Remove the undesired classes from the class roots.
-  VLOG(compiler) << "Pruning " << visitor.classes_to_prune_.size() << " classes";
-  for (mirror::Class* klass : visitor.classes_to_prune_) {
-    std::string temp;
-    const char* name = klass->GetDescriptor(&temp);
-    VLOG(compiler) << "Pruning class " << name;
-    if (!compile_app_image_) {
-      DCHECK(IsBootClassLoaderClass(klass));
-    }
-    bool result = class_linker->RemoveClass(name, klass->GetClassLoader());
-    DCHECK(result);
+  {
+    PruneClassLoaderClassesVisitor class_loader_visitor(this);
+    VisitClassLoaders(&class_loader_visitor);
+    VLOG(compiler) << "Pruned " << class_loader_visitor.GetRemovedClassCount() << " classes";
   }
 
   // Clear references to removed classes from the DexCaches.
@@ -1508,8 +1550,10 @@
     }
     // Calculate the size of the class table.
     ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
-    DCHECK_EQ(image_info.class_table_->NumZygoteClasses(), 0u);
-    if (image_info.class_table_->NumNonZygoteClasses() != 0u) {
+    CHECK_EQ(class_loaders_.size(), compile_app_image_ ? 1u : 0u);
+    mirror::ClassLoader* class_loader = compile_app_image_ ? *class_loaders_.begin() : nullptr;
+    DCHECK_EQ(image_info.class_table_->NumZygoteClasses(class_loader), 0u);
+    if (image_info.class_table_->NumNonZygoteClasses(class_loader) != 0u) {
       image_info.class_table_bytes_ += image_info.class_table_->WriteToMemory(nullptr);
     }
   }
@@ -1854,8 +1898,10 @@
     // above comment for intern tables.
     ClassTable temp_class_table;
     temp_class_table.ReadFromMemory(class_table_memory_ptr);
-    CHECK_EQ(temp_class_table.NumZygoteClasses(), table->NumNonZygoteClasses() +
-             table->NumZygoteClasses());
+    CHECK_EQ(class_loaders_.size(), compile_app_image_ ? 1u : 0u);
+    mirror::ClassLoader* class_loader = compile_app_image_ ? *class_loaders_.begin() : nullptr;
+    CHECK_EQ(temp_class_table.NumZygoteClasses(class_loader),
+             table->NumNonZygoteClasses(class_loader) + table->NumZygoteClasses(class_loader));
     UnbufferedRootVisitor visitor(&root_visitor, RootInfo(kRootUnknown));
     temp_class_table.VisitRoots(visitor);
   }
diff --git a/compiler/image_writer.h b/compiler/image_writer.h
index 24fad46..c537483 100644
--- a/compiler/image_writer.h
+++ b/compiler/image_writer.h
@@ -50,6 +50,7 @@
 }  // namespace space
 }  // namespace gc
 
+class ClassLoaderVisitor;
 class ClassTable;
 
 static constexpr int kInvalidFd = -1;
@@ -373,6 +374,9 @@
   void ComputeLazyFieldsForImageClasses()
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Visit all class loaders.
+  void VisitClassLoaders(ClassLoaderVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Remove unwanted classes from various roots.
   void PruneNonImageClasses() REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -588,7 +592,8 @@
   class FixupVisitor;
   class GetRootsVisitor;
   class NativeLocationVisitor;
-  class NonImageClassesVisitor;
+  class PruneClassesVisitor;
+  class PruneClassLoaderClassesVisitor;
   class VisitReferencesVisitor;
 
   DISALLOW_COPY_AND_ASSIGN(ImageWriter);
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 319991b..3137769 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1981,13 +1981,36 @@
   void Visit(ObjPtr<mirror::ClassLoader> class_loader)
       REQUIRES_SHARED(Locks::classlinker_classes_lock_, Locks::mutator_lock_) OVERRIDE {
     ClassTable* const class_table = class_loader->GetClassTable();
-    if (!done_ && class_table != nullptr && !class_table->Visit(*visitor_)) {
-      // If the visitor ClassTable returns false it means that we don't need to continue.
-      done_ = true;
+    if (!done_ && class_table != nullptr) {
+      DefiningClassLoaderFilterVisitor visitor(class_loader, visitor_);
+      if (!class_table->Visit(visitor)) {
+        // If the visitor ClassTable returns false it means that we don't need to continue.
+        done_ = true;
+      }
     }
   }
 
  private:
+  // Class visitor that limits the class visits from a ClassTable to the classes with
+  // the provided defining class loader. This filter is used to avoid multiple visits
+  // of the same class which can be recorded for multiple initiating class loaders.
+  class DefiningClassLoaderFilterVisitor : public ClassVisitor {
+   public:
+    DefiningClassLoaderFilterVisitor(ObjPtr<mirror::ClassLoader> defining_class_loader,
+                                     ClassVisitor* visitor)
+        : defining_class_loader_(defining_class_loader), visitor_(visitor) { }
+
+    bool operator()(ObjPtr<mirror::Class> klass) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
+      if (klass->GetClassLoader() != defining_class_loader_) {
+        return true;
+      }
+      return (*visitor_)(klass);
+    }
+
+    ObjPtr<mirror::ClassLoader> const defining_class_loader_;
+    ClassVisitor* const visitor_;
+  };
+
   ClassVisitor* const visitor_;
   // If done is true then we don't need to do any more visiting.
   bool done_;
@@ -2474,56 +2497,109 @@
     }
   } else {
     ScopedObjectAccessUnchecked soa(self);
-    ObjPtr<mirror::Class> cp_klass;
-    if (FindClassInBaseDexClassLoader(soa, self, descriptor, hash, class_loader, &cp_klass)) {
-      // The chain was understood. So the value in cp_klass is either the class we were looking
-      // for, or not found.
-      if (cp_klass != nullptr) {
-        return cp_klass.Ptr();
-      }
-      // TODO: We handle the boot classpath loader in FindClassInBaseDexClassLoader. Try to unify
-      //       this and the branch above. TODO: throw the right exception here.
+    ObjPtr<mirror::Class> result_ptr;
+    bool descriptor_equals;
+    bool known_hierarchy =
+        FindClassInBaseDexClassLoader(soa, self, descriptor, hash, class_loader, &result_ptr);
+    if (result_ptr != nullptr) {
+      // The chain was understood and we found the class. We still need to add the class to
+      // the class table to protect from racy programs that can try and redefine the path list
+      // which would change the Class<?> returned for subsequent evaluation of const-class.
+      DCHECK(known_hierarchy);
+      DCHECK(result_ptr->DescriptorEquals(descriptor));
+      descriptor_equals = true;
+    } else {
+      // Either the chain wasn't understood or the class wasn't found.
+      //
+      // If the chain was understood but we did not find the class, let the Java-side
+      // rediscover all this and throw the exception with the right stack trace. Note that
+      // the Java-side could still succeed for racy programs if another thread is actively
+      // modifying the class loader's path list.
 
-      // We'll let the Java-side rediscover all this and throw the exception with the right stack
-      // trace.
-    }
-
-    if (Runtime::Current()->IsAotCompiler()) {
-      // Oops, compile-time, can't run actual class-loader code.
-      ObjPtr<mirror::Throwable> pre_allocated = Runtime::Current()->GetPreAllocatedNoClassDefFoundError();
-      self->SetException(pre_allocated);
-      return nullptr;
-    }
-
-    ScopedLocalRef<jobject> class_loader_object(soa.Env(),
-                                                soa.AddLocalReference<jobject>(class_loader.Get()));
-    std::string class_name_string(DescriptorToDot(descriptor));
-    ScopedLocalRef<jobject> result(soa.Env(), nullptr);
-    {
-      ScopedThreadStateChange tsc(self, kNative);
-      ScopedLocalRef<jobject> class_name_object(soa.Env(),
-                                                soa.Env()->NewStringUTF(class_name_string.c_str()));
-      if (class_name_object.get() == nullptr) {
-        DCHECK(self->IsExceptionPending());  // OOME.
+      if (Runtime::Current()->IsAotCompiler()) {
+        // Oops, compile-time, can't run actual class-loader code.
+        ObjPtr<mirror::Throwable> pre_allocated =
+            Runtime::Current()->GetPreAllocatedNoClassDefFoundError();
+        self->SetException(pre_allocated);
         return nullptr;
       }
-      CHECK(class_loader_object.get() != nullptr);
-      result.reset(soa.Env()->CallObjectMethod(class_loader_object.get(),
-                                               WellKnownClasses::java_lang_ClassLoader_loadClass,
-                                               class_name_object.get()));
+
+      ScopedLocalRef<jobject> class_loader_object(
+          soa.Env(), soa.AddLocalReference<jobject>(class_loader.Get()));
+      std::string class_name_string(DescriptorToDot(descriptor));
+      ScopedLocalRef<jobject> result(soa.Env(), nullptr);
+      {
+        ScopedThreadStateChange tsc(self, kNative);
+        ScopedLocalRef<jobject> class_name_object(
+            soa.Env(), soa.Env()->NewStringUTF(class_name_string.c_str()));
+        if (class_name_object.get() == nullptr) {
+          DCHECK(self->IsExceptionPending());  // OOME.
+          return nullptr;
+        }
+        CHECK(class_loader_object.get() != nullptr);
+        result.reset(soa.Env()->CallObjectMethod(class_loader_object.get(),
+                                                 WellKnownClasses::java_lang_ClassLoader_loadClass,
+                                                 class_name_object.get()));
+      }
+      if (self->IsExceptionPending()) {
+        // If the ClassLoader threw, pass that exception up.
+        // However, to comply with the RI behavior, first check if another thread succeeded.
+        result_ptr = LookupClass(self, descriptor, hash, class_loader.Get());
+        if (result_ptr != nullptr && !result_ptr->IsErroneous()) {
+          self->ClearException();
+          return EnsureResolved(self, descriptor, result_ptr);
+        }
+        return nullptr;
+      } else if (result.get() == nullptr) {
+        // broken loader - throw NPE to be compatible with Dalvik
+        ThrowNullPointerException(StringPrintf("ClassLoader.loadClass returned null for %s",
+                                               class_name_string.c_str()).c_str());
+        return nullptr;
+      }
+      result_ptr = soa.Decode<mirror::Class>(result.get());
+      // Check the name of the returned class.
+      descriptor_equals = result_ptr->DescriptorEquals(descriptor);
     }
-    if (self->IsExceptionPending()) {
-      // If the ClassLoader threw, pass that exception up.
-      return nullptr;
-    } else if (result.get() == nullptr) {
-      // broken loader - throw NPE to be compatible with Dalvik
-      ThrowNullPointerException(StringPrintf("ClassLoader.loadClass returned null for %s",
-                                             class_name_string.c_str()).c_str());
-      return nullptr;
-    } else {
-      // success, return mirror::Class*
-      return soa.Decode<mirror::Class>(result.get()).Ptr();
+
+    // Try to insert the class to the class table, checking for mismatch.
+    ObjPtr<mirror::Class> old;
+    {
+      WriterMutexLock mu(self, *Locks::classlinker_classes_lock_);
+      ClassTable* const class_table = InsertClassTableForClassLoader(class_loader.Get());
+      old = class_table->Lookup(descriptor, hash);
+      if (old == nullptr) {
+        old = result_ptr;  // For the comparison below, after releasing the lock.
+        if (descriptor_equals) {
+          class_table->InsertWithHash(result_ptr.Ptr(), hash);
+          Runtime::Current()->GetHeap()->WriteBarrierEveryFieldOf(class_loader.Get());
+        }  // else throw below, after releasing the lock.
+      }
     }
+    if (UNLIKELY(old != result_ptr)) {
+      // Return `old` (even if `!descriptor_equals`) to mimic the RI behavior for parallel
+      // capable class loaders.  (All class loaders are considered parallel capable on Android.)
+      mirror::Class* loader_class = class_loader->GetClass();
+      const char* loader_class_name =
+          loader_class->GetDexFile().StringByTypeIdx(loader_class->GetDexTypeIndex());
+      LOG(WARNING) << "Initiating class loader of type " << DescriptorToDot(loader_class_name)
+          << " is not well-behaved; it returned a different Class for racing loadClass(\""
+          << DescriptorToDot(descriptor) << "\").";
+      return EnsureResolved(self, descriptor, old);
+    }
+    if (UNLIKELY(!descriptor_equals)) {
+      std::string result_storage;
+      const char* result_name = result_ptr->GetDescriptor(&result_storage);
+      std::string loader_storage;
+      const char* loader_class_name = class_loader->GetClass()->GetDescriptor(&loader_storage);
+      ThrowNoClassDefFoundError(
+          "Initiating class loader of type %s returned class %s instead of %s.",
+          DescriptorToDot(loader_class_name).c_str(),
+          DescriptorToDot(result_name).c_str(),
+          DescriptorToDot(descriptor).c_str());
+      return nullptr;
+    }
+    // success, return mirror::Class*
+    return result_ptr.Ptr();
   }
   UNREACHABLE();
 }
@@ -3609,12 +3685,6 @@
   Runtime::Current()->GetHeap()->WriteBarrierEveryFieldOf(klass);
 }
 
-bool ClassLinker::RemoveClass(const char* descriptor, ObjPtr<mirror::ClassLoader> class_loader) {
-  WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
-  ClassTable* const class_table = ClassTableForClassLoader(class_loader);
-  return class_table != nullptr && class_table->Remove(descriptor);
-}
-
 mirror::Class* ClassLinker::LookupClass(Thread* self,
                                         const char* descriptor,
                                         size_t hash,
@@ -3665,7 +3735,8 @@
       REQUIRES_SHARED(Locks::classlinker_classes_lock_, Locks::mutator_lock_) OVERRIDE {
     ClassTable* const class_table = class_loader->GetClassTable();
     ObjPtr<mirror::Class> klass = class_table->Lookup(descriptor_, hash_);
-    if (klass != nullptr) {
+    // Add `klass` only if `class_loader` is its defining (not just initiating) class loader.
+    if (klass != nullptr && klass->GetClassLoader() == class_loader) {
       result_->push_back(klass);
     }
   }
@@ -3684,6 +3755,7 @@
   const size_t hash = ComputeModifiedUtf8Hash(descriptor);
   ObjPtr<mirror::Class> klass = boot_class_table_.Lookup(descriptor, hash);
   if (klass != nullptr) {
+    DCHECK(klass->GetClassLoader() == nullptr);
     result.push_back(klass);
   }
   LookupClassesVisitor visitor(descriptor, hash, &result);
@@ -7972,8 +8044,8 @@
       REQUIRES_SHARED(Locks::classlinker_classes_lock_, Locks::mutator_lock_) OVERRIDE {
     ClassTable* const class_table = class_loader->GetClassTable();
     if (class_table != nullptr) {
-      num_zygote_classes += class_table->NumZygoteClasses();
-      num_non_zygote_classes += class_table->NumNonZygoteClasses();
+      num_zygote_classes += class_table->NumZygoteClasses(class_loader);
+      num_non_zygote_classes += class_table->NumNonZygoteClasses(class_loader);
     }
   }
 
@@ -7984,13 +8056,13 @@
 size_t ClassLinker::NumZygoteClasses() const {
   CountClassesVisitor visitor;
   VisitClassLoaders(&visitor);
-  return visitor.num_zygote_classes + boot_class_table_.NumZygoteClasses();
+  return visitor.num_zygote_classes + boot_class_table_.NumZygoteClasses(nullptr);
 }
 
 size_t ClassLinker::NumNonZygoteClasses() const {
   CountClassesVisitor visitor;
   VisitClassLoaders(&visitor);
-  return visitor.num_non_zygote_classes + boot_class_table_.NumNonZygoteClasses();
+  return visitor.num_non_zygote_classes + boot_class_table_.NumNonZygoteClasses(nullptr);
 }
 
 size_t ClassLinker::NumLoadedClasses() {
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index de1f0f0..9b25303 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -218,12 +218,6 @@
 
   mirror::Class* FindPrimitiveClass(char type) REQUIRES_SHARED(Locks::mutator_lock_);
 
-  // General class unloading is not supported, this is used to prune
-  // unwanted classes during image writing.
-  bool RemoveClass(const char* descriptor, ObjPtr<mirror::ClassLoader> class_loader)
-      REQUIRES(!Locks::classlinker_classes_lock_)
-      REQUIRES_SHARED(Locks::mutator_lock_);
-
   void DumpForSigQuit(std::ostream& os) REQUIRES(!Locks::classlinker_classes_lock_);
 
   size_t NumLoadedClasses()
diff --git a/runtime/class_table.cc b/runtime/class_table.cc
index 6eb7496..ec33e5e 100644
--- a/runtime/class_table.cc
+++ b/runtime/class_table.cc
@@ -84,18 +84,29 @@
 
 #pragma clang diagnostic pop  // http://b/31104323
 
-size_t ClassTable::NumZygoteClasses() const {
+size_t ClassTable::CountDefiningLoaderClasses(ObjPtr<mirror::ClassLoader> defining_loader,
+                                              const ClassSet& set) const {
+  size_t count = 0;
+  for (const TableSlot& root : set) {
+    if (root.Read()->GetClassLoader() == defining_loader) {
+      ++count;
+    }
+  }
+  return count;
+}
+
+size_t ClassTable::NumZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const {
   ReaderMutexLock mu(Thread::Current(), lock_);
   size_t sum = 0;
   for (size_t i = 0; i < classes_.size() - 1; ++i) {
-    sum += classes_[i].Size();
+    sum += CountDefiningLoaderClasses(defining_loader, classes_[i]);
   }
   return sum;
 }
 
-size_t ClassTable::NumNonZygoteClasses() const {
+size_t ClassTable::NumNonZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const {
   ReaderMutexLock mu(Thread::Current(), lock_);
-  return classes_.back().Size();
+  return CountDefiningLoaderClasses(defining_loader, classes_.back());
 }
 
 mirror::Class* ClassTable::Lookup(const char* descriptor, size_t hash) {
@@ -104,7 +115,7 @@
   for (ClassSet& class_set : classes_) {
     auto it = class_set.FindWithHash(pair, hash);
     if (it != class_set.end()) {
-     return it->Read();
+      return it->Read();
     }
   }
   return nullptr;
@@ -150,7 +161,6 @@
     DCHECK(!a.Read()->DescriptorEquals(b.Read()->GetDescriptor(&temp)));
     return false;
   }
-  DCHECK_EQ(a.Read()->GetClassLoader(), b.Read()->GetClassLoader());
   std::string temp;
   return a.Read()->DescriptorEquals(b.Read()->GetDescriptor(&temp));
 }
diff --git a/runtime/class_table.h b/runtime/class_table.h
index fe0bbb3..104871f 100644
--- a/runtime/class_table.h
+++ b/runtime/class_table.h
@@ -142,10 +142,14 @@
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Returns the number of classes in previous snapshots.
-  size_t NumZygoteClasses() const REQUIRES(!lock_);
+  size_t NumZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const
+      REQUIRES(!lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Returns all off the classes in the lastest snapshot.
-  size_t NumNonZygoteClasses() const REQUIRES(!lock_);
+  size_t NumNonZygoteClasses(ObjPtr<mirror::ClassLoader> defining_loader) const
+      REQUIRES(!lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
 
   // Update a class in the table with the new class. Returns the existing class which was replaced.
   mirror::Class* UpdateClass(const char* descriptor, mirror::Class* new_klass, size_t hash)
@@ -231,6 +235,11 @@
  private:
   void InsertWithoutLocks(ObjPtr<mirror::Class> klass) NO_THREAD_SAFETY_ANALYSIS;
 
+  size_t CountDefiningLoaderClasses(ObjPtr<mirror::ClassLoader> defining_loader,
+                                    const ClassSet& set) const
+      REQUIRES(lock_)
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
   // Return true if we inserted the oat file, false if it already exists.
   bool InsertOatFileLocked(const OatFile* oat_file)
       REQUIRES(lock_)
diff --git a/test/626-const-class-linking/clear_dex_cache_types.cc b/test/626-const-class-linking/clear_dex_cache_types.cc
new file mode 100644
index 0000000..b035896
--- /dev/null
+++ b/test/626-const-class-linking/clear_dex_cache_types.cc
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+#include "jni.h"
+#include "object_lock.h"
+#include "scoped_thread_state_change-inl.h"
+
+namespace art {
+
+extern "C" JNIEXPORT void JNICALL Java_Main_nativeClearResolvedTypes(JNIEnv*, jclass, jclass cls) {
+  ScopedObjectAccess soa(Thread::Current());
+  mirror::DexCache* dex_cache = soa.Decode<mirror::Class>(cls)->GetDexCache();
+  for (size_t i = 0, num_types = dex_cache->NumResolvedTypes(); i != num_types; ++i) {
+    dex_cache->SetResolvedType(dex::TypeIndex(i), ObjPtr<mirror::Class>(nullptr));
+  }
+}
+
+extern "C" JNIEXPORT void JNICALL Java_Main_nativeSkipVerification(JNIEnv*, jclass, jclass cls) {
+  ScopedObjectAccess soa(Thread::Current());
+  StackHandleScope<1> hs(soa.Self());
+  Handle<mirror::Class> klass = hs.NewHandle(soa.Decode<mirror::Class>(cls));
+  mirror::Class::Status status = klass->GetStatus();
+  if (status == mirror::Class::kStatusResolved) {
+    ObjectLock<mirror::Class> lock(soa.Self(), klass);
+    klass->SetStatus(klass, mirror::Class::kStatusVerified, soa.Self());
+  } else {
+    LOG(ERROR) << klass->PrettyClass() << " has unexpected status: " << status;
+  }
+}
+
+extern "C" JNIEXPORT void JNICALL Java_Main_nativeDumpClasses(JNIEnv*, jclass, jobjectArray array) {
+  ScopedObjectAccess soa(Thread::Current());
+  StackHandleScope<1> hs(soa.Self());
+  Handle<mirror::ObjectArray<mirror::Object>> classes =
+      hs.NewHandle(soa.Decode<mirror::ObjectArray<mirror::Object>>(array));
+  CHECK(classes.Get() != nullptr);
+  for (size_t i = 0, length = classes->GetLength(); i != length; ++i) {
+    CHECK(classes->Get(i) != nullptr) << i;
+    CHECK(classes->Get(i)->IsClass())
+        << i << " " << classes->Get(i)->GetClass()->PrettyDescriptor();
+    mirror::Class* as_class = classes->Get(i)->AsClass();
+    mirror::ClassLoader* loader = as_class->GetClassLoader();
+    LOG(ERROR) << "Class #" << i << ": " << as_class->PrettyDescriptor()
+        << " @" << static_cast<const void*>(as_class)
+        << " status:" << as_class->GetStatus()
+        << " definingLoader:" << static_cast<const void*>(loader)
+        << " definingLoaderClass:"
+        << (loader != nullptr ? loader->GetClass()->PrettyDescriptor() : "N/A");
+  }
+}
+
+}  // namespace art
diff --git a/test/626-const-class-linking/expected.txt b/test/626-const-class-linking/expected.txt
new file mode 100644
index 0000000..de1b815
--- /dev/null
+++ b/test/626-const-class-linking/expected.txt
@@ -0,0 +1,61 @@
+JNI_OnLoad called
+first: Helper1 class loader: DelegatingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: DelegatingLoader
+second: Test class loader: DefiningLoader
+testClearDexCache done
+first: Helper1 class loader: DelegatingLoader
+second: Test class loader: DefiningLoader
+first: Helper2 class loader: DelegatingLoader
+second: Test class loader: DefiningLoader
+testMultiDex done
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+total: 4
+  throwables: 0
+  classes: 4 (1 unique)
+testRacyLoader done
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyLoader
+second: Test class loader: DefiningLoader
+first: Helper3 class loader: RacyLoader
+second: Test3 class loader: DefiningLoader
+first: Helper3 class loader: RacyLoader
+second: Test3 class loader: DefiningLoader
+total: 4
+  throwables: 0
+  classes: 4 (2 unique)
+testRacyLoader2 done
+java.lang.NoClassDefFoundError: Initiating class loader of type MisbehavingLoader returned class Helper2 instead of Test.
+testMisbehavingLoader done
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+total: 4
+  throwables: 0
+  classes: 4 (1 unique)
+testRacyMisbehavingLoader done
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+first: Helper1 class loader: RacyMisbehavingLoader
+second: Test class loader: DefiningLoader
+total: 4
+  throwables: 0
+  classes: 4 (1 unique)
+testRacyMisbehavingLoader2 done
diff --git a/test/626-const-class-linking/info.txt b/test/626-const-class-linking/info.txt
new file mode 100644
index 0000000..9c19a46
--- /dev/null
+++ b/test/626-const-class-linking/info.txt
@@ -0,0 +1,3 @@
+Test that once a const-class instruction is linked, it will keep referring
+to the same class even in the presence of custom class loaders even after
+clearing the dex cache type array.
diff --git a/test/626-const-class-linking/multidex.jpp b/test/626-const-class-linking/multidex.jpp
new file mode 100644
index 0000000..c7a6648
--- /dev/null
+++ b/test/626-const-class-linking/multidex.jpp
@@ -0,0 +1,27 @@
+ClassPair:
+  @@com.android.jack.annotations.ForceInMainDex
+  class ClassPair
+DefiningLoader:
+  @@com.android.jack.annotations.ForceInMainDex
+  class DefiningLoader
+DelegatingLoader:
+  @@com.android.jack.annotations.ForceInMainDex
+  class DelegatingLoader
+Helper1:
+  @@com.android.jack.annotations.ForceInMainDex
+  class Helper1
+Main:
+  @@com.android.jack.annotations.ForceInMainDex
+  class Main
+MisbehavingLoader:
+  @@com.android.jack.annotations.ForceInMainDex
+  class MisbehavingLoader
+RacyLoader:
+  @@com.android.jack.annotations.ForceInMainDex
+  class RacyLoader
+RacyMisbehavingHelper:
+  @@com.android.jack.annotations.ForceInMainDex
+  class RacyMisbehavingHelper
+RacyMisbehavingLoader:
+  @@com.android.jack.annotations.ForceInMainDex
+  class RacyMisbehavingLoader
diff --git a/test/626-const-class-linking/src-multidex/Helper2.java b/test/626-const-class-linking/src-multidex/Helper2.java
new file mode 100644
index 0000000..5bb31ee
--- /dev/null
+++ b/test/626-const-class-linking/src-multidex/Helper2.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Helper2 {
+    public static ClassPair get() {
+        Class<?> helper2_class = Helper2.class;
+        Class<?> test_class = Test.class;
+        return new ClassPair(helper2_class, test_class);
+    }
+}
diff --git a/test/626-const-class-linking/src-multidex/Helper3.java b/test/626-const-class-linking/src-multidex/Helper3.java
new file mode 100644
index 0000000..af996de
--- /dev/null
+++ b/test/626-const-class-linking/src-multidex/Helper3.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Helper3 {
+    public static ClassPair get() {
+        Class<?> helper3_class = Helper3.class;
+        Class<?> test3_class = Test3.class;
+        return new ClassPair(helper3_class, test3_class);
+    }
+}
diff --git a/test/626-const-class-linking/src-multidex/Test.java b/test/626-const-class-linking/src-multidex/Test.java
new file mode 100644
index 0000000..1b0cc2a
--- /dev/null
+++ b/test/626-const-class-linking/src-multidex/Test.java
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Test {
+}
diff --git a/test/626-const-class-linking/src-multidex/Test3.java b/test/626-const-class-linking/src-multidex/Test3.java
new file mode 100644
index 0000000..c4b134d
--- /dev/null
+++ b/test/626-const-class-linking/src-multidex/Test3.java
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Test3 {
+}
diff --git a/test/626-const-class-linking/src/ClassPair.java b/test/626-const-class-linking/src/ClassPair.java
new file mode 100644
index 0000000..b07036c
--- /dev/null
+++ b/test/626-const-class-linking/src/ClassPair.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class ClassPair {
+    public Class<?> first;
+    public Class<?> second;
+
+    public ClassPair(Class<?> first, Class<?> second) {
+        this.first = first;
+        this.second = second;
+    }
+
+    public void print() {
+        String first_loader_name = first.getClassLoader().getClass().getName();
+        System.out.println("first: " + first.getName() + " class loader: " + first_loader_name);
+        String second_loader_name = second.getClassLoader().getClass().getName();
+        System.out.println("second: " + second.getName() + " class loader: " + second_loader_name);
+    }
+}
diff --git a/test/626-const-class-linking/src/DefiningLoader.java b/test/626-const-class-linking/src/DefiningLoader.java
new file mode 100644
index 0000000..b17ab77
--- /dev/null
+++ b/test/626-const-class-linking/src/DefiningLoader.java
@@ -0,0 +1,239 @@
+/*
+ * Copyright (C) 2016 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.FileNotFoundException;
+import java.io.IOException;
+import java.io.RandomAccessFile;
+import java.lang.reflect.Constructor;
+import java.lang.reflect.Method;
+import java.lang.reflect.InvocationTargetException;
+
+/**
+ * A class loader with atypical behavior: we try to load a private
+ * class implementation before asking the system or boot loader.  This
+ * is used to create multiple classes with identical names in a single VM.
+ *
+ * If DexFile is available, we use that; if not, we assume we're not in
+ * Dalvik and instantiate the class with defineClass().
+ *
+ * The location of the DEX files and class data is dependent upon the
+ * test framework.
+ */
+public class DefiningLoader extends ClassLoader {
+    static {
+        // For JVM, register as parallel capable.
+        // Android treats all class loaders as parallel capable and makes this a no-op.
+        registerAsParallelCapable();
+    }
+
+    /* this is where the .class files live */
+    static final String CLASS_PATH1 = "classes/";
+    static final String CLASS_PATH2 = "classes2/";
+
+    /* this is the DEX/Jar file */
+    static final String DEX_FILE = System.getenv("DEX_LOCATION") + "/626-const-class-linking.jar";
+
+    /* on Dalvik, this is a DexFile; otherwise, it's null */
+    private Class<?> mDexClass;
+
+    private Object mDexFile;
+
+    /**
+     * Construct DefiningLoader, grabbing a reference to the DexFile class
+     * if we're running under Dalvik.
+     */
+    public DefiningLoader(ClassLoader parent) {
+        super(parent);
+
+        try {
+            mDexClass = parent.loadClass("dalvik.system.DexFile");
+        } catch (ClassNotFoundException cnfe) {
+            // ignore -- not running Dalvik
+        }
+    }
+
+    /**
+     * Finds the class with the specified binary name.
+     *
+     * We search for a file in CLASS_PATH or pull an entry from DEX_FILE.
+     * If we don't find a match, we throw an exception.
+     */
+    protected Class<?> findClass(String name) throws ClassNotFoundException
+    {
+        if (mDexClass != null) {
+            return findClassDalvik(name);
+        } else {
+            return findClassNonDalvik(name);
+        }
+    }
+
+    /**
+     * Finds the class with the specified binary name, from a DEX file.
+     */
+    private Class<?> findClassDalvik(String name)
+        throws ClassNotFoundException {
+
+        if (mDexFile == null) {
+            synchronized (DefiningLoader.class) {
+                Constructor<?> ctor;
+                /*
+                 * Construct a DexFile object through reflection.
+                 */
+                try {
+                    ctor = mDexClass.getConstructor(String.class);
+                } catch (NoSuchMethodException nsme) {
+                    throw new ClassNotFoundException("getConstructor failed",
+                        nsme);
+                }
+
+                try {
+                    mDexFile = ctor.newInstance(DEX_FILE);
+                } catch (InstantiationException ie) {
+                    throw new ClassNotFoundException("newInstance failed", ie);
+                } catch (IllegalAccessException iae) {
+                    throw new ClassNotFoundException("newInstance failed", iae);
+                } catch (InvocationTargetException ite) {
+                    throw new ClassNotFoundException("newInstance failed", ite);
+                }
+            }
+        }
+
+        /*
+         * Call DexFile.loadClass(String, ClassLoader).
+         */
+        Method meth;
+
+        try {
+            meth = mDexClass.getMethod("loadClass", String.class, ClassLoader.class);
+        } catch (NoSuchMethodException nsme) {
+            throw new ClassNotFoundException("getMethod failed", nsme);
+        }
+
+        try {
+            meth.invoke(mDexFile, name, this);
+        } catch (IllegalAccessException iae) {
+            throw new ClassNotFoundException("loadClass failed", iae);
+        } catch (InvocationTargetException ite) {
+            throw new ClassNotFoundException("loadClass failed",
+                ite.getCause());
+        }
+
+        return null;
+    }
+
+    /**
+     * Finds the class with the specified binary name, from .class files.
+     */
+    private Class<?> findClassNonDalvik(String name)
+        throws ClassNotFoundException {
+
+        String[] pathNames = { CLASS_PATH1 + name + ".class", CLASS_PATH2 + name + ".class" };
+
+        String pathName = null;
+        RandomAccessFile raf = null;
+
+        for (String pn : pathNames) {
+            pathName = pn;
+            try {
+                //System.out.println("--- Defining: looking for " + pathName);
+                raf = new RandomAccessFile(new File(pathName), "r");
+                break;
+            } catch (FileNotFoundException fnfe) {
+            }
+        }
+        if (raf == null) {
+            throw new ClassNotFoundException("Not found: " + pathNames[0] + ":" + pathNames[1]);
+        }
+
+        /* read the entire file in */
+        byte[] fileData;
+        try {
+            fileData = new byte[(int) raf.length()];
+            raf.readFully(fileData);
+        } catch (IOException ioe) {
+            throw new ClassNotFoundException("Read error: " + pathName);
+        } finally {
+            try {
+                raf.close();
+            } catch (IOException ioe) {
+                // drop
+            }
+        }
+
+        /* create the class */
+        //System.out.println("--- Defining: defining " + name);
+        try {
+            return defineClass(name, fileData, 0, fileData.length);
+        } catch (Throwable th) {
+            throw new ClassNotFoundException("defineClass failed", th);
+        }
+    }
+
+    /**
+     * Load a class.
+     *
+     * Normally a class loader wouldn't override this, but we want our
+     * version of the class to take precedence over an already-loaded
+     * version.
+     *
+     * We still want the system classes (e.g. java.lang.Object) from the
+     * bootstrap class loader.
+     */
+    synchronized protected Class<?> loadClass(String name, boolean resolve)
+        throws ClassNotFoundException
+    {
+        Class<?> res;
+
+        /*
+         * 1. Invoke findLoadedClass(String) to check if the class has
+         * already been loaded.
+         *
+         * This doesn't change.
+         */
+        res = findLoadedClass(name);
+        if (res != null) {
+            // System.out.println("FancyLoader.loadClass: " + name + " already loaded");
+            if (resolve)
+                resolveClass(res);
+            return res;
+        }
+
+        /*
+         * 3. Invoke the findClass(String) method to find the class.
+         */
+        try {
+            res = findClass(name);
+            if (resolve)
+                resolveClass(res);
+        }
+        catch (ClassNotFoundException e) {
+            // we couldn't find it, so eat the exception and keep going
+        }
+
+        /*
+         * 2. Invoke the loadClass method on the parent class loader.  If
+         * the parent loader is null the class loader built-in to the
+         * virtual machine is used, instead.
+         *
+         * (Since we're not in java.lang, we can't actually invoke the
+         * parent's loadClass() method, but we passed our parent to the
+         * super-class which can take care of it for us.)
+         */
+        res = super.loadClass(name, resolve);   // returns class or throws
+        return res;
+    }
+}
diff --git a/test/626-const-class-linking/src/DelegatingLoader.java b/test/626-const-class-linking/src/DelegatingLoader.java
new file mode 100644
index 0000000..49955d4
--- /dev/null
+++ b/test/626-const-class-linking/src/DelegatingLoader.java
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class DelegatingLoader extends DefiningLoader {
+    private DefiningLoader defining_loader;
+
+    public DelegatingLoader(ClassLoader parent, DefiningLoader defining_loader) {
+        super(parent);
+        this.defining_loader = defining_loader;
+    }
+
+    public void resetDefiningLoader(DefiningLoader defining_loader) {
+        this.defining_loader = defining_loader;
+    }
+
+    protected Class<?> findClass(String name) throws ClassNotFoundException
+    {
+        if (name.equals("Test")) {
+            throw new Error("Unexpected DelegatingLoader.findClass(\"Test\")");
+        }
+        return super.findClass(name);
+    }
+
+    protected Class<?> loadClass(String name, boolean resolve)
+        throws ClassNotFoundException
+    {
+        if (name.equals("Test")) {
+            return defining_loader.loadClass(name, resolve);
+        }
+        return super.loadClass(name, resolve);
+    }
+}
diff --git a/test/626-const-class-linking/src/Helper1.java b/test/626-const-class-linking/src/Helper1.java
new file mode 100644
index 0000000..ff9cd1a
--- /dev/null
+++ b/test/626-const-class-linking/src/Helper1.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class Helper1 {
+    public static ClassPair get() {
+        Class<?> helper1_class = Helper1.class;
+        Class<?> test_class = Test.class;
+        return new ClassPair(helper1_class, test_class);
+    }
+}
diff --git a/test/626-const-class-linking/src/Main.java b/test/626-const-class-linking/src/Main.java
new file mode 100644
index 0000000..0029428
--- /dev/null
+++ b/test/626-const-class-linking/src/Main.java
@@ -0,0 +1,354 @@
+/*
+ * Copyright (C) 2016 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.lang.ref.WeakReference;
+import java.lang.reflect.Field;
+import java.lang.reflect.InvocationTargetException;
+import java.lang.reflect.Method;
+import java.util.ArrayList;
+
+public class Main {
+    public static void main(String[] args) throws Exception {
+        try {
+            System.loadLibrary(args[0]);
+        } catch (UnsatisfiedLinkError ule) {
+            usingRI = true;
+            // Add expected JNI_OnLoad log line to match expected.txt.
+            System.out.println("JNI_OnLoad called");
+        }
+
+        testClearDexCache();
+        testMultiDex();
+        testRacyLoader();
+        testRacyLoader2();
+        testMisbehavingLoader();
+        testRacyMisbehavingLoader();
+        testRacyMisbehavingLoader2();
+    }
+
+    private static void testClearDexCache() throws Exception {
+        DelegatingLoader delegating_loader = createDelegatingLoader();
+        Class<?> helper = delegating_loader.loadClass("Helper1");
+
+        WeakReference<Class<?>> weak_test1 = wrapHelperGet(helper);
+        changeInner(delegating_loader);
+        clearResolvedTypes(helper);
+        Runtime.getRuntime().gc();
+        WeakReference<Class<?>> weak_test2 = wrapHelperGet(helper);
+        Runtime.getRuntime().gc();
+
+        Class<?> test1 = weak_test1.get();
+        if (test1 == null) {
+            System.out.println("test1 disappeared");
+        }
+        Class<?> test2 = weak_test2.get();
+        if (test2 == null) {
+            System.out.println("test2 disappeared");
+        }
+        if (test1 != test2) {
+            System.out.println("test1 != test2");
+        }
+
+        System.out.println("testClearDexCache done");
+    }
+
+    private static void testMultiDex() throws Exception {
+        DelegatingLoader delegating_loader = createDelegatingLoader();
+
+        Class<?> helper1 = delegating_loader.loadClass("Helper1");
+        WeakReference<Class<?>> weak_test1 = wrapHelperGet(helper1);
+
+        changeInner(delegating_loader);
+
+        Class<?> helper2 = delegating_loader.loadClass("Helper2");
+        WeakReference<Class<?>> weak_test2 = wrapHelperGet(helper2);
+
+        Runtime.getRuntime().gc();
+
+        Class<?> test1 = weak_test1.get();
+        if (test1 == null) {
+            System.out.println("test1 disappeared");
+        }
+        Class<?> test2 = weak_test2.get();
+        if (test2 == null) {
+            System.out.println("test2 disappeared");
+        }
+        if (test1 != test2) {
+            System.out.println("test1 != test2");
+        }
+
+        System.out.println("testMultiDex done");
+    }
+
+    private static void testMisbehavingLoader() throws Exception {
+        ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+        DefiningLoader defining_loader = new DefiningLoader(system_loader);
+        MisbehavingLoader misbehaving_loader =
+            new MisbehavingLoader(system_loader, defining_loader);
+        Class<?> helper = misbehaving_loader.loadClass("Helper1");
+
+        try {
+            WeakReference<Class<?>> weak_test = wrapHelperGet(helper);
+        } catch (InvocationTargetException ite) {
+            String message = ite.getCause().getMessage();
+            if (usingRI && "Test".equals(message)) {
+              // Replace RI message with dalvik message to match expected.txt.
+              message = "Initiating class loader of type " +
+                  misbehaving_loader.getClass().getName() +
+                  " returned class Helper2 instead of Test.";
+            }
+            System.out.println(ite.getCause().getClass().getName() + ": " + message);
+        }
+        System.out.println("testMisbehavingLoader done");
+    }
+
+    private static void testRacyLoader() throws Exception {
+        final ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+
+        final Thread[] threads = new Thread[4];
+        final Object[] results = new Object[threads.length];
+
+        final RacyLoader racy_loader = new RacyLoader(system_loader, threads.length);
+        final Class<?> helper1 = racy_loader.loadClass("Helper1");
+        skipVerification(helper1);  // Avoid class loading during verification.
+
+        for (int i = 0; i != threads.length; ++i) {
+            final int my_index = i;
+            Thread t = new Thread() {
+                public void run() {
+                    try {
+                        Method get = helper1.getDeclaredMethod("get");
+                        results[my_index] = get.invoke(null);
+                    } catch (InvocationTargetException ite) {
+                        results[my_index] = ite.getCause();
+                    } catch (Throwable t) {
+                        results[my_index] = t;
+                    }
+                }
+            };
+            t.start();
+            threads[i] = t;
+        }
+        for (Thread t : threads) {
+            t.join();
+        }
+        dumpResultStats(results, 1);
+        System.out.println("testRacyLoader done");
+    }
+
+    private static void testRacyLoader2() throws Exception {
+        final ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+
+        final Thread[] threads = new Thread[4];
+        final Object[] results = new Object[threads.length];
+
+        final RacyLoader racy_loader = new RacyLoader(system_loader, threads.length);
+        final Class<?> helper1 = racy_loader.loadClass("Helper1");
+        skipVerification(helper1);  // Avoid class loading during verification.
+        final Class<?> helper3 = racy_loader.loadClass("Helper3");
+        skipVerification(helper3);  // Avoid class loading during verification.
+
+        for (int i = 0; i != threads.length; ++i) {
+            final int my_index = i;
+            Thread t = new Thread() {
+                public void run() {
+                    try {
+                        Class<?> helper = (my_index < threads.length / 2) ? helper1 : helper3;
+                        Method get = helper.getDeclaredMethod("get");
+                        results[my_index] = get.invoke(null);
+                    } catch (InvocationTargetException ite) {
+                        results[my_index] = ite.getCause();
+                    } catch (Throwable t) {
+                        results[my_index] = t;
+                    }
+                }
+            };
+            t.start();
+            threads[i] = t;
+        }
+        for (Thread t : threads) {
+            t.join();
+        }
+        dumpResultStats(results, 2);
+        System.out.println("testRacyLoader2 done");
+    }
+
+    private static void testRacyMisbehavingLoader() throws Exception {
+        final ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+
+        final Thread[] threads = new Thread[4];
+        final Object[] results = new Object[threads.length];
+
+        final RacyMisbehavingLoader racy_loader =
+            new RacyMisbehavingLoader(system_loader, threads.length, false);
+        final Class<?> helper1 = racy_loader.loadClass("RacyMisbehavingHelper");
+        skipVerification(helper1);  // Avoid class loading during verification.
+
+        for (int i = 0; i != threads.length; ++i) {
+            final int my_index = i;
+            Thread t = new Thread() {
+                public void run() {
+                    try {
+                        Method get = helper1.getDeclaredMethod("get");
+                        results[my_index] = get.invoke(null);
+                    } catch (InvocationTargetException ite) {
+                        results[my_index] = ite.getCause();
+                    } catch (Throwable t) {
+                        results[my_index] = t;
+                    }
+                }
+            };
+            t.start();
+            threads[i] = t;
+        }
+        for (Thread t : threads) {
+            t.join();
+        }
+        dumpResultStats(results, 1);
+        System.out.println("testRacyMisbehavingLoader done");
+    }
+
+    private static void testRacyMisbehavingLoader2() throws Exception {
+        final ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+
+        final Thread[] threads = new Thread[4];
+        final Object[] results = new Object[threads.length];
+
+        final RacyMisbehavingLoader racy_loader =
+            new RacyMisbehavingLoader(system_loader, threads.length, true);
+        final Class<?> helper1 = racy_loader.loadClass("RacyMisbehavingHelper");
+        skipVerification(helper1);  // Avoid class loading during verification.
+
+        for (int i = 0; i != threads.length; ++i) {
+            final int my_index = i;
+            Thread t = new Thread() {
+                public void run() {
+                    try {
+                        Method get = helper1.getDeclaredMethod("get");
+                        results[my_index] = get.invoke(null);
+                    } catch (InvocationTargetException ite) {
+                        results[my_index] = ite.getCause();
+                    } catch (Throwable t) {
+                        results[my_index] = t;
+                    }
+                }
+            };
+            t.start();
+            threads[i] = t;
+        }
+        for (Thread t : threads) {
+            t.join();
+        }
+        dumpResultStats(results, 1);
+        System.out.println("testRacyMisbehavingLoader2 done");
+    }
+
+    private static void dumpResultStats(Object[] results, int expected_unique) throws Exception {
+        int throwables = 0;
+        int classes = 0;
+        int unique_classes = 0;
+        for (int i = 0; i != results.length; ++i) {
+            Object r = results[i];
+            if (r instanceof Throwable) {
+                ++throwables;
+                System.out.println(((Throwable) r).getMessage());
+            } else if (isClassPair(r)) {
+                printPair(r);
+                Object ref = getSecond(r);
+                ++classes;
+                ++unique_classes;
+                for (int j = 0; j != i; ++j) {
+                    Object rj = results[j];
+                    if (isClassPair(results[j]) && getSecond(results[j]) == ref) {
+                        --unique_classes;
+                        break;
+                    }
+                }
+            }
+        }
+        System.out.println("total: " + results.length);
+        System.out.println("  throwables: " + throwables);
+        System.out.println("  classes: " + classes
+            + " (" + unique_classes + " unique)");
+        if (expected_unique != unique_classes) {
+            System.out.println("MISMATCH with expected_unique: " + expected_unique);
+            ArrayList<Class<?>> list = new ArrayList<Class<?>>();
+            for (int i = 0; i != results.length; ++i) {
+                Object r = results[i];
+                if (isClassPair(r)) {
+                    list.add(getSecond(r));
+                }
+            }
+            nativeDumpClasses(list.toArray());
+        }
+    }
+
+    private static DelegatingLoader createDelegatingLoader() {
+        ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+        DefiningLoader defining_loader = new DefiningLoader(system_loader);
+        return new DelegatingLoader(system_loader, defining_loader);
+    }
+
+    private static void changeInner(DelegatingLoader delegating_loader) {
+        ClassLoader system_loader = ClassLoader.getSystemClassLoader();
+        DefiningLoader defining_loader = new DefiningLoader(system_loader);
+        delegating_loader.resetDefiningLoader(defining_loader);
+    }
+
+    private static WeakReference<Class<?>> wrapHelperGet(Class<?> helper) throws Exception {
+        Method get = helper.getDeclaredMethod("get");
+        Object pair = get.invoke(null);
+        printPair(pair);
+        return new WeakReference<Class<?>>(getSecond(pair));
+    }
+
+    private static void printPair(Object pair) throws Exception {
+        Method print = pair.getClass().getDeclaredMethod("print");
+        print.invoke(pair);
+    }
+
+    private static Class<?> getSecond(Object pair) throws Exception {
+        Field second = pair.getClass().getDeclaredField("second");
+        return (Class<?>) second.get(pair);
+    }
+
+    private static boolean isClassPair(Object r) {
+        return r != null && r.getClass().getName().equals("ClassPair");
+    }
+
+    public static void clearResolvedTypes(Class<?> c) {
+        if (!usingRI) {
+            nativeClearResolvedTypes(c);
+        }
+    }
+
+    // Skip verification of a class on ART. Verification can cause classes to be loaded
+    // while holding a lock on the class being verified and holding that lock can interfere
+    // with the intent of the "racy" tests. In these tests we're waiting in the loadClass()
+    // for all the tested threads to synchronize and they cannot reach that point if they
+    // are waiting for the class lock on ClassLinker::InitializeClass(Helper1/Helper3).
+    public static void skipVerification(Class<?> c) {
+        if (!usingRI) {
+            nativeSkipVerification(c);
+        }
+    }
+
+    public static native void nativeClearResolvedTypes(Class<?> c);
+    public static native void nativeSkipVerification(Class<?> c);
+    public static native void nativeDumpClasses(Object[] array);
+
+    static boolean usingRI = false;
+}
diff --git a/test/626-const-class-linking/src/MisbehavingLoader.java b/test/626-const-class-linking/src/MisbehavingLoader.java
new file mode 100644
index 0000000..ca9783e
--- /dev/null
+++ b/test/626-const-class-linking/src/MisbehavingLoader.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+// Class loader that returns Helper2.class when asked to load "Test".
+public class MisbehavingLoader extends DefiningLoader {
+    private DefiningLoader defining_loader;
+
+    public MisbehavingLoader(ClassLoader parent, DefiningLoader defining_loader) {
+        super(parent);
+        this.defining_loader = defining_loader;
+    }
+
+    protected Class<?> findClass(String name) throws ClassNotFoundException
+    {
+        if (name.equals("Helper1") || name.equals("Helper2")) {
+            return super.findClass(name);
+        } else if (name.equals("Test")) {
+            throw new Error("Unexpected MisbehavingLoader.findClass(\"Test\")");
+        }
+        return super.findClass(name);
+    }
+
+    protected Class<?> loadClass(String name, boolean resolve)
+        throws ClassNotFoundException
+    {
+        if (name.equals("Helper1") || name.equals("Helper2")) {
+            return super.loadClass(name, resolve);
+        } else if (name.equals("Test")) {
+            // Ask for a different class.
+            return defining_loader.loadClass("Helper2", resolve);
+        }
+        return super.loadClass(name, resolve);
+    }
+}
diff --git a/test/626-const-class-linking/src/RacyLoader.java b/test/626-const-class-linking/src/RacyLoader.java
new file mode 100644
index 0000000..9c164a3
--- /dev/null
+++ b/test/626-const-class-linking/src/RacyLoader.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class RacyLoader extends DefiningLoader {
+    static {
+        // For JVM, register as parallel capable.
+        // Android treats all class loaders as parallel capable and makes this a no-op.
+        registerAsParallelCapable();
+    }
+
+    private Object lock = new Object();
+    private int index = 0;
+    private int count;
+
+    private DefiningLoader[] defining_loaders;
+
+    public RacyLoader(ClassLoader parent, int count) {
+        super(parent);
+        this.count = count;
+        defining_loaders = new DefiningLoader[2];
+        for (int i = 0; i != defining_loaders.length; ++i) {
+            defining_loaders[i] = new DefiningLoader(parent);
+        }
+    }
+
+    protected Class<?> findClass(String name) throws ClassNotFoundException
+    {
+        if (name.equals("Test") || name.equals("Test3")) {
+            throw new Error("Unexpected RacyLoader.findClass(\"" + name + "\")");
+        }
+        return super.findClass(name);
+    }
+
+    protected Class<?> loadClass(String name, boolean resolve)
+        throws ClassNotFoundException
+    {
+        if (name.equals("Test") || name.equals("Test3")) {
+            int my_index = syncWithOtherInstances(count);
+            Class<?> result = defining_loaders[my_index & 1].loadClass(name, resolve);
+            syncWithOtherInstances(2 * count);
+            return result;
+        }
+        return super.loadClass(name, resolve);
+    }
+
+    private int syncWithOtherInstances(int limit) {
+        int my_index;
+        synchronized (lock) {
+            my_index = index;
+            ++index;
+            if (index != limit) {
+                do {
+                    try {
+                        lock.wait();
+                    } catch (InterruptedException ie) {
+                        throw new Error(ie);
+                    }
+                } while (index < limit);
+            } else {
+                lock.notifyAll();
+            }
+        }
+        return my_index;
+    }
+}
diff --git a/test/626-const-class-linking/src/RacyMisbehavingHelper.java b/test/626-const-class-linking/src/RacyMisbehavingHelper.java
new file mode 100644
index 0000000..4525278
--- /dev/null
+++ b/test/626-const-class-linking/src/RacyMisbehavingHelper.java
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2016 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.lang.reflect.Method;
+
+public class RacyMisbehavingHelper {
+    public static ClassPair get() {
+        Class<?> helper1_class = Helper1.class;
+        Class<?> test_class = Test.class;
+        try {
+            // After loading the correct class, allow loading the incorrect class.
+            ClassLoader loader = helper1_class.getClassLoader();
+            Method reportAfterLoading = loader.getClass().getDeclaredMethod("reportAfterLoading");
+            reportAfterLoading.invoke(loader);
+        } catch (Throwable t) {
+            t.printStackTrace();
+        }
+        return new ClassPair(helper1_class, test_class);
+    }
+}
diff --git a/test/626-const-class-linking/src/RacyMisbehavingLoader.java b/test/626-const-class-linking/src/RacyMisbehavingLoader.java
new file mode 100644
index 0000000..f5bcb4c
--- /dev/null
+++ b/test/626-const-class-linking/src/RacyMisbehavingLoader.java
@@ -0,0 +1,99 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+public class RacyMisbehavingLoader extends DefiningLoader {
+    static {
+        // For JVM, register as parallel capable.
+        // Android treats all class loaders as parallel capable and makes this a no-op.
+        registerAsParallelCapable();
+    }
+
+    private Object lock = new Object();
+    private int index = 0;
+    private int count;
+    private boolean throw_error;
+
+    private DefiningLoader[] defining_loaders;
+
+    public RacyMisbehavingLoader(ClassLoader parent, int count, boolean throw_error) {
+        super(parent);
+        this.count = count;
+        this.throw_error = throw_error;
+        defining_loaders = new DefiningLoader[2];
+        for (int i = 0; i != defining_loaders.length; ++i) {
+            defining_loaders[i] = new DefiningLoader(parent);
+        }
+    }
+
+    public void reportAfterLoading() {
+        synchronized (lock) {
+            ++index;
+            if (index == 2 * count) {
+                lock.notifyAll();
+            }
+        }
+    }
+
+    protected Class<?> findClass(String name) throws ClassNotFoundException
+    {
+        if (name.equals("Test")) {
+            throw new Error("Unexpected RacyLoader.findClass(\"" + name + "\")");
+        }
+        return super.findClass(name);
+    }
+
+    protected Class<?> loadClass(String name, boolean resolve)
+        throws ClassNotFoundException
+    {
+        if (name.equals("Test")) {
+            int my_index = syncWithOtherInstances(count);
+            Class<?> result;
+            if ((my_index & 1) == 0) {
+              // Do not delay loading the correct class.
+              result = defining_loaders[my_index & 1].loadClass(name, resolve);
+            } else {
+              // Delay loading the wrong class.
+              syncWithOtherInstances(2 * count);
+              if (throw_error) {
+                throw new Error("RacyMisbehavingLoader throw_error=true");
+              }
+              result = defining_loaders[my_index & 1].loadClass("Test3", resolve);
+            }
+            return result;
+        }
+        return super.loadClass(name, resolve);
+    }
+
+    private int syncWithOtherInstances(int limit) {
+        int my_index;
+        synchronized (lock) {
+            my_index = index;
+            ++index;
+            if (index != limit) {
+                do {
+                    try {
+                        lock.wait();
+                    } catch (InterruptedException ie) {
+                        throw new Error(ie);
+                    }
+                } while (index < limit);
+            } else {
+                lock.notifyAll();
+            }
+        }
+        return my_index;
+    }
+}
diff --git a/test/Android.bp b/test/Android.bp
index 44c64c1..2625f56 100644
--- a/test/Android.bp
+++ b/test/Android.bp
@@ -314,6 +314,7 @@
         "595-profile-saving/profile-saving.cc",
         "596-app-images/app_images.cc",
         "597-deopt-new-string/deopt.cc",
+        "626-const-class-linking/clear_dex_cache_types.cc",
     ],
     shared_libs: [
         "libbacktrace",
diff --git a/test/etc/default-build b/test/etc/default-build
index f2b5078..51ae175 100755
--- a/test/etc/default-build
+++ b/test/etc/default-build
@@ -273,8 +273,10 @@
 fi
 
 # Create a single jar with two dex files for multidex.
-if [ ${HAS_SRC_MULTIDEX} = "true" ] || [ ${HAS_SMALI_MULTIDEX} = "true" ]; then
-  zip $TEST_NAME.jar classes.dex classes2.dex
-elif [ ${NEED_DEX} = "true" ]; then
-  zip $TEST_NAME.jar classes.dex
+if [ ${NEED_DEX} = "true" ]; then
+  if [ ${HAS_SRC_MULTIDEX} = "true" ] || [ ${HAS_SMALI_MULTIDEX} = "true" ]; then
+    zip $TEST_NAME.jar classes.dex classes2.dex
+  else
+    zip $TEST_NAME.jar classes.dex
+  fi
 fi
diff --git a/test/etc/run-test-jar b/test/etc/run-test-jar
index bb3a3ad..f0abb44 100755
--- a/test/etc/run-test-jar
+++ b/test/etc/run-test-jar
@@ -316,7 +316,8 @@
 if [ "$USE_JVM" = "y" ]; then
   export LD_LIBRARY_PATH=${ANDROID_HOST_OUT}/lib64
   # Xmx is necessary since we don't pass down the ART flags to JVM.
-  cmdline="${JAVA} ${DEBUGGER_OPTS} ${JVM_VERIFY_ARG} -Xmx256m -classpath classes ${FLAGS} $MAIN $@ ${ARGS}"
+  # We pass the classes2 path whether it's used (src-multidex) or not.
+  cmdline="${JAVA} ${DEBUGGER_OPTS} ${JVM_VERIFY_ARG} -Xmx256m -classpath classes:classes2 ${FLAGS} $MAIN $@ ${ARGS}"
   if [ "$DEV_MODE" = "y" ]; then
     echo $cmdline
   fi