diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index b074dec..e78914c 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -273,7 +273,6 @@
       array_iftable_(nullptr),
       find_array_class_cache_next_victim_(0),
       init_done_(false),
-      log_new_dex_caches_roots_(false),
       log_new_class_table_roots_(false),
       intern_table_(intern_table),
       quick_resolution_trampoline_(nullptr),
@@ -332,6 +331,12 @@
   java_lang_Class->SetSuperClass(java_lang_Object.Get());
   mirror::Class::SetStatus(java_lang_Object, mirror::Class::kStatusLoaded, self);
 
+  java_lang_Object->SetObjectSize(sizeof(mirror::Object));
+  runtime->SetSentinel(heap->AllocObject<true>(self,
+                                               java_lang_Object.Get(),
+                                               java_lang_Object->GetObjectSize(),
+                                               VoidFunctor()));
+
   // Object[] next to hold class roots.
   Handle<mirror::Class> object_array_class(hs.NewHandle(
       AllocClass(self, java_lang_Class.Get(),
@@ -1143,11 +1148,11 @@
   quick_imt_conflict_trampoline_ = oat_file.GetOatHeader().GetQuickImtConflictTrampoline();
   quick_generic_jni_trampoline_ = oat_file.GetOatHeader().GetQuickGenericJniTrampoline();
   quick_to_interpreter_bridge_trampoline_ = oat_file.GetOatHeader().GetQuickToInterpreterBridge();
+  StackHandleScope<2> hs(self);
   mirror::Object* dex_caches_object = space->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
-  mirror::ObjectArray<mirror::DexCache>* dex_caches =
-      dex_caches_object->AsObjectArray<mirror::DexCache>();
+  Handle<mirror::ObjectArray<mirror::DexCache>> dex_caches(
+      hs.NewHandle(dex_caches_object->AsObjectArray<mirror::DexCache>()));
 
-  StackHandleScope<1> hs(self);
   Handle<mirror::ObjectArray<mirror::Class>> class_roots(hs.NewHandle(
           space->GetImageHeader().GetImageRoot(ImageHeader::kClassRoots)->
           AsObjectArray<mirror::Class>()));
@@ -1157,6 +1162,13 @@
   // as being Strings or not
   mirror::String::SetClass(GetClassRoot(kJavaLangString));
 
+  mirror::Class* java_lang_Object = GetClassRoot(kJavaLangObject);
+  java_lang_Object->SetObjectSize(sizeof(mirror::Object));
+  Runtime::Current()->SetSentinel(Runtime::Current()->GetHeap()->AllocObject<true>(self,
+                                                          java_lang_Object,
+                                                          java_lang_Object->GetObjectSize(),
+                                                          VoidFunctor()));
+
   CHECK_EQ(oat_file.GetOatHeader().GetDexFileCount(),
            static_cast<uint32_t>(dex_caches->GetLength()));
   for (int32_t i = 0; i < dex_caches->GetLength(); i++) {
@@ -1250,7 +1262,6 @@
 }
 
 bool ClassLinker::ClassInClassTable(mirror::Class* klass) {
-  ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
   ClassTable* const class_table = ClassTableForClassLoader(klass->GetClassLoader());
   return class_table != nullptr && class_table->Contains(klass);
 }
@@ -1307,27 +1318,6 @@
 // mapped image.
 void ClassLinker::VisitRoots(RootVisitor* visitor, VisitRootFlags flags) {
   class_roots_.VisitRootIfNonNull(visitor, RootInfo(kRootVMInternal));
-  Thread* const self = Thread::Current();
-  {
-    ReaderMutexLock mu(self, dex_lock_);
-    if ((flags & kVisitRootFlagAllRoots) != 0) {
-      for (GcRoot<mirror::DexCache>& dex_cache : dex_caches_) {
-        dex_cache.VisitRoot(visitor, RootInfo(kRootVMInternal));
-      }
-    } else if ((flags & kVisitRootFlagNewRoots) != 0) {
-      for (size_t index : new_dex_cache_roots_) {
-        dex_caches_[index].VisitRoot(visitor, RootInfo(kRootVMInternal));
-      }
-    }
-    if ((flags & kVisitRootFlagClearRootLog) != 0) {
-      new_dex_cache_roots_.clear();
-    }
-    if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
-      log_new_dex_caches_roots_ = true;
-    } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
-      log_new_dex_caches_roots_ = false;
-    }
-  }
   VisitClassRoots(visitor, flags);
   array_iftable_.VisitRootIfNonNull(visitor, RootInfo(kRootVMInternal));
   for (GcRoot<mirror::Class>& root : find_array_class_cache_) {
@@ -1702,7 +1692,6 @@
                 long_array->GetWithoutChecks(j)));
             const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor, hash);
             if (dex_class_def != nullptr) {
-              RegisterDexFile(*cp_dex_file);
               mirror::Class* klass = DefineClass(self, descriptor, hash, class_loader,
                                                  *cp_dex_file, *dex_class_def);
               if (klass == nullptr) {
@@ -1845,11 +1834,15 @@
     klass.Assign(AllocClass(self, SizeOfClassWithoutEmbeddedTables(dex_file, dex_class_def)));
   }
   if (UNLIKELY(klass.Get() == nullptr)) {
-    CHECK(self->IsExceptionPending());  // Expect an OOME.
+    self->AssertPendingOOMException();
     return nullptr;
   }
-  klass->SetDexCache(FindDexCache(dex_file));
-
+  mirror::DexCache* dex_cache = RegisterDexFile(dex_file);
+  if (dex_cache == nullptr) {
+    self->AssertPendingOOMException();
+    return nullptr;
+  }
+  klass->SetDexCache(dex_cache);
   SetupClass(dex_file, dex_class_def, klass, class_loader.Get());
 
   // Mark the string class by setting its access flag.
@@ -2482,58 +2475,54 @@
   RegisterDexFile(dex_file, dex_cache);
 }
 
-bool ClassLinker::IsDexFileRegisteredLocked(const DexFile& dex_file) {
-  dex_lock_.AssertSharedHeld(Thread::Current());
-  for (GcRoot<mirror::DexCache>& root : dex_caches_) {
-    mirror::DexCache* dex_cache = root.Read();
-    if (dex_cache->GetDexFile() == &dex_file) {
-      return true;
-    }
-  }
-  return false;
-}
-
-bool ClassLinker::IsDexFileRegistered(const DexFile& dex_file) {
-  ReaderMutexLock mu(Thread::Current(), dex_lock_);
-  return IsDexFileRegisteredLocked(dex_file);
-}
-
 void ClassLinker::RegisterDexFileLocked(const DexFile& dex_file,
                                         Handle<mirror::DexCache> dex_cache) {
-  dex_lock_.AssertExclusiveHeld(Thread::Current());
+  Thread* const self = Thread::Current();
+  dex_lock_.AssertExclusiveHeld(self);
   CHECK(dex_cache.Get() != nullptr) << dex_file.GetLocation();
   CHECK(dex_cache->GetLocation()->Equals(dex_file.GetLocation()))
       << dex_cache->GetLocation()->ToModifiedUtf8() << " " << dex_file.GetLocation();
-  dex_caches_.push_back(GcRoot<mirror::DexCache>(dex_cache.Get()));
-  dex_cache->SetDexFile(&dex_file);
-  if (log_new_dex_caches_roots_) {
-    // TODO: This is not safe if we can remove dex caches.
-    new_dex_cache_roots_.push_back(dex_caches_.size() - 1);
+  // Clean up pass to remove null dex caches.
+  // Null dex caches can occur due to class unloading and we are lazily removing null entries.
+  JavaVMExt* const vm = self->GetJniEnv()->vm;
+  for (auto it = dex_caches_.begin(); it != dex_caches_.end();) {
+    mirror::Object* dex_cache_root = self->DecodeJObject(*it);
+    if (dex_cache_root == nullptr) {
+      vm->DeleteWeakGlobalRef(self, *it);
+      it = dex_caches_.erase(it);
+    } else {
+      ++it;
+    }
   }
+  dex_caches_.push_back(vm->AddWeakGlobalRef(self, dex_cache.Get()));
+  dex_cache->SetDexFile(&dex_file);
 }
 
-void ClassLinker::RegisterDexFile(const DexFile& dex_file) {
+mirror::DexCache* ClassLinker::RegisterDexFile(const DexFile& dex_file) {
   Thread* self = Thread::Current();
   {
     ReaderMutexLock mu(self, dex_lock_);
-    if (IsDexFileRegisteredLocked(dex_file)) {
-      return;
+    mirror::DexCache* dex_cache = FindDexCacheLocked(self, dex_file, true);
+    if (dex_cache != nullptr) {
+      return dex_cache;
     }
   }
   // Don't alloc while holding the lock, since allocation may need to
   // suspend all threads and another thread may need the dex_lock_ to
   // get to a suspend point.
   StackHandleScope<1> hs(self);
-  Handle<mirror::DexCache> dex_cache(hs.NewHandle(AllocDexCache(self, dex_file)));
-  CHECK(dex_cache.Get() != nullptr) << "Failed to allocate dex cache for "
-                                    << dex_file.GetLocation();
-  {
-    WriterMutexLock mu(self, dex_lock_);
-    if (IsDexFileRegisteredLocked(dex_file)) {
-      return;
-    }
-    RegisterDexFileLocked(dex_file, dex_cache);
+  Handle<mirror::DexCache> h_dex_cache(hs.NewHandle(AllocDexCache(self, dex_file)));
+  WriterMutexLock mu(self, dex_lock_);
+  mirror::DexCache* dex_cache = FindDexCacheLocked(self, dex_file, true);
+  if (dex_cache != nullptr) {
+    return dex_cache;
   }
+  if (h_dex_cache.Get() == nullptr) {
+    self->AssertPendingOOMException();
+    return nullptr;
+  }
+  RegisterDexFileLocked(dex_file, h_dex_cache);
+  return h_dex_cache.Get();
 }
 
 void ClassLinker::RegisterDexFile(const DexFile& dex_file,
@@ -2542,36 +2531,52 @@
   RegisterDexFileLocked(dex_file, dex_cache);
 }
 
-mirror::DexCache* ClassLinker::FindDexCache(const DexFile& dex_file) {
-  ReaderMutexLock mu(Thread::Current(), dex_lock_);
+mirror::DexCache* ClassLinker::FindDexCache(Thread* self,
+                                            const DexFile& dex_file,
+                                            bool allow_failure) {
+  ReaderMutexLock mu(self, dex_lock_);
+  return FindDexCacheLocked(self, dex_file, allow_failure);
+}
+
+mirror::DexCache* ClassLinker::FindDexCacheLocked(Thread* self,
+                                                  const DexFile& dex_file,
+                                                  bool allow_failure) {
   // Search assuming unique-ness of dex file.
-  for (size_t i = 0; i != dex_caches_.size(); ++i) {
-    mirror::DexCache* dex_cache = GetDexCache(i);
-    if (dex_cache->GetDexFile() == &dex_file) {
-      return dex_cache;
+  JavaVMExt* const vm = self->GetJniEnv()->vm;
+  {
+    MutexLock mu(self, vm->WeakGlobalsLock());
+    for (jobject weak_root : dex_caches_) {
+      DCHECK_EQ(GetIndirectRefKind(weak_root), kWeakGlobal);
+      mirror::DexCache* dex_cache = down_cast<mirror::DexCache*>(
+          vm->DecodeWeakGlobalLocked(self, weak_root));
+      if (dex_cache != nullptr && dex_cache->GetDexFile() == &dex_file) {
+        return dex_cache;
+      }
     }
   }
-  // Search matching by location name.
+  if (allow_failure) {
+    return nullptr;
+  }
   std::string location(dex_file.GetLocation());
-  for (size_t i = 0; i != dex_caches_.size(); ++i) {
-    mirror::DexCache* dex_cache = GetDexCache(i);
-    if (dex_cache->GetDexFile()->GetLocation() == location) {
-      return dex_cache;
-    }
-  }
   // Failure, dump diagnostic and abort.
-  for (size_t i = 0; i != dex_caches_.size(); ++i) {
-    mirror::DexCache* dex_cache = GetDexCache(i);
-    LOG(ERROR) << "Registered dex file " << i << " = " << dex_cache->GetDexFile()->GetLocation();
+  for (jobject weak_root : dex_caches_) {
+    mirror::DexCache* dex_cache = down_cast<mirror::DexCache*>(self->DecodeJObject(weak_root));
+    if (dex_cache != nullptr) {
+      LOG(ERROR) << "Registered dex file " << dex_cache->GetDexFile()->GetLocation();
+    }
   }
   LOG(FATAL) << "Failed to find DexCache for DexFile " << location;
   UNREACHABLE();
 }
 
 void ClassLinker::FixupDexCaches(ArtMethod* resolution_method) {
-  ReaderMutexLock mu(Thread::Current(), dex_lock_);
-  for (auto& dex_cache : dex_caches_) {
-    dex_cache.Read()->Fixup(resolution_method, image_pointer_size_);
+  Thread* const self = Thread::Current();
+  ReaderMutexLock mu(self, dex_lock_);
+  for (jobject weak_root : dex_caches_) {
+    mirror::DexCache* dex_cache = down_cast<mirror::DexCache*>(self->DecodeJObject(weak_root));
+    if (dex_cache != nullptr) {
+      dex_cache->Fixup(resolution_method, image_pointer_size_);
+    }
   }
 }
 
@@ -3407,11 +3412,13 @@
   DCHECK(proxy_class->IsProxyClass());
   DCHECK(proxy_method->IsProxyMethod());
   {
-    ReaderMutexLock mu(Thread::Current(), dex_lock_);
+    Thread* const self = Thread::Current();
+    ReaderMutexLock mu(self, dex_lock_);
     // Locate the dex cache of the original interface/Object
-    for (const GcRoot<mirror::DexCache>& root : dex_caches_) {
-      auto* dex_cache = root.Read();
-      if (proxy_method->HasSameDexCacheResolvedTypes(dex_cache->GetResolvedTypes())) {
+    for (jobject weak_root : dex_caches_) {
+      mirror::DexCache* dex_cache = down_cast<mirror::DexCache*>(self->DecodeJObject(weak_root));
+      if (dex_cache != nullptr &&
+          proxy_method->HasSameDexCacheResolvedTypes(dex_cache->GetResolvedTypes())) {
         ArtMethod* resolved_method = dex_cache->GetResolvedMethod(
             proxy_method->GetDexMethodIndex(), image_pointer_size_);
         CHECK(resolved_method != nullptr);
@@ -5878,11 +5885,6 @@
   // We could move the jobject to the callers, but all call-sites do this...
   ScopedObjectAccessUnchecked soa(self);
 
-  // Register the dex files.
-  for (const DexFile* dex_file : dex_files) {
-    RegisterDexFile(*dex_file);
-  }
-
   // For now, create a libcore-level DexFile for each ART DexFile. This "explodes" multidex.
   StackHandleScope<10> hs(self);