Change ClassLinker::dex_caches_ from list to unordered_map.

Move the DexFile* pointer from struct field out to map key.
This makes it easy and fast to find DexCache from DexFile.

Add check that given DexFile* is registered only once.

Test: test.py -b -r --host --64
Test: generated images are identical as before
Change-Id: I84a6d6cbf963af2408abe5bb5e4c99d0ca11df78

5 files changed, 60 insertions, 70 deletions

diff --git a/dex2oat/linker/image_writer.cc b/dex2oat/linker/image_writer.cc
index d7c2d65352..b0473873c4 100644
--- a/dex2oat/linker/image_writer.cc
+++ b/dex2oat/linker/image_writer.cc
@@ -1205,7 +1205,8 @@ std::vector<ObjPtr<mirror::DexCache>> ImageWriter::FindDexCaches(Thread* self) {
   ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
   ReaderMutexLock mu2(self, *Locks::dex_lock_);
   dex_caches.reserve(class_linker->GetDexCachesData().size());
-  for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
+  for (const auto& entry : class_linker->GetDexCachesData()) {
+    const ClassLinker::DexCacheData& data = entry.second;
     if (self->IsJWeakCleared(data.weak_root)) {
       continue;
     }
@@ -1256,7 +1257,8 @@ ObjPtr<mirror::ObjectArray<mirror::Object>> ImageWriter::CollectDexCaches(Thread
   {
     ReaderMutexLock mu(self, *Locks::dex_lock_);
     // Count number of dex caches not in the boot image.
-    for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
+    for (const auto& entry : class_linker->GetDexCachesData()) {
+      const ClassLinker::DexCacheData& data = entry.second;
       ObjPtr<mirror::DexCache> dex_cache =
           ObjPtr<mirror::DexCache>::DownCast(self->DecodeJObject(data.weak_root));
       if (dex_cache == nullptr) {
@@ -1273,34 +1275,28 @@ ObjPtr<mirror::ObjectArray<mirror::Object>> ImageWriter::CollectDexCaches(Thread
   CHECK(dex_caches != nullptr) << "Failed to allocate a dex cache array.";
   {
     ReaderMutexLock mu(self, *Locks::dex_lock_);
-    size_t non_image_dex_caches = 0;
-    // Re-count number of non image dex caches.
-    for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
+    // Collect all dex caches (and sort them by registration index to make output deterministic).
+    std::map<uint64_t, ObjPtr<mirror::DexCache>> non_image_dex_caches;
+    for (const auto& entry : class_linker->GetDexCachesData()) {
+      const ClassLinker::DexCacheData& data = entry.second;
       ObjPtr<mirror::DexCache> dex_cache =
           ObjPtr<mirror::DexCache>::DownCast(self->DecodeJObject(data.weak_root));
       if (dex_cache == nullptr) {
         continue;
       }
       const DexFile* dex_file = dex_cache->GetDexFile();
-      if (IsImageDexCache(dex_cache)) {
-        non_image_dex_caches += image_dex_files.find(dex_file) != image_dex_files.end() ? 1u : 0u;
+      if (IsImageDexCache(dex_cache) &&
+          image_dex_files.find(dex_file) != image_dex_files.end()) {
+        bool inserted = non_image_dex_caches.emplace(data.registration_index, dex_cache).second;
+        CHECK(inserted);
       }
     }
-    CHECK_EQ(dex_cache_count, non_image_dex_caches)
+    CHECK_EQ(dex_cache_count, non_image_dex_caches.size())
         << "The number of non-image dex caches changed.";
+    // Write the dex caches to the output array (in registration order).
     size_t i = 0;
-    for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
-      ObjPtr<mirror::DexCache> dex_cache =
-          ObjPtr<mirror::DexCache>::DownCast(self->DecodeJObject(data.weak_root));
-      if (dex_cache == nullptr) {
-        continue;
-      }
-      const DexFile* dex_file = dex_cache->GetDexFile();
-      if (IsImageDexCache(dex_cache) &&
-          image_dex_files.find(dex_file) != image_dex_files.end()) {
-        dex_caches->Set<false>(i, dex_cache.Ptr());
-        ++i;
-      }
+    for (const auto& entry : non_image_dex_caches) {
+      dex_caches->Set<false>(i++, entry.second.Ptr());
     }
   }
   return dex_caches;
@@ -2102,7 +2098,8 @@ void ImageWriter::LayoutHelper::VerifyImageBinSlotsAssigned() {
     ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
     Thread* self = Thread::Current();
     ReaderMutexLock mu(self, *Locks::dex_lock_);
-    for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
+    for (const auto& entry : class_linker->GetDexCachesData()) {
+      const ClassLinker::DexCacheData& data = entry.second;
       ObjPtr<mirror::DexCache> dex_cache =
           ObjPtr<mirror::DexCache>::DownCast(self->DecodeJObject(data.weak_root));
       if (dex_cache == nullptr ||
diff --git a/runtime/class_linker-inl.h b/runtime/class_linker-inl.h
index da066d1180..4e8f8edf64 100644
--- a/runtime/class_linker-inl.h
+++ b/runtime/class_linker-inl.h
@@ -455,10 +455,8 @@ void ClassLinker::VisitKnownDexFiles(Thread* self, Visitor visitor) {
   ReaderMutexLock rmu(self, *Locks::dex_lock_);
   std::for_each(dex_caches_.begin(),
                 dex_caches_.end(),
-                [&](DexCacheData& dcd) REQUIRES(Locks::mutator_lock_) {
-                  if (dcd.IsValid()) {
-                    visitor(dcd.dex_file);
-                  }
+                [&](const auto& entry) REQUIRES(Locks::mutator_lock_) {
+                  visitor(/*dex_file=*/entry.first);
                 });
 }
 
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 2ce02943f1..4d1589bbf5 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -3894,14 +3894,14 @@ void ClassLinker::RegisterDexFileLocked(const DexFile& dex_file,
   bool initialize_oat_file_data = (oat_file != nullptr) && oat_file->IsExecutable();
   JavaVMExt* const vm = self->GetJniEnv()->GetVm();
   for (auto it = dex_caches_.begin(); it != dex_caches_.end(); ) {
-    DexCacheData data = *it;
+    const DexCacheData& data = it->second;
     if (self->IsJWeakCleared(data.weak_root)) {
       vm->DeleteWeakGlobalRef(self, data.weak_root);
       it = dex_caches_.erase(it);
     } else {
       if (initialize_oat_file_data &&
-          it->dex_file->GetOatDexFile() != nullptr &&
-          it->dex_file->GetOatDexFile()->GetOatFile() == oat_file) {
+          it->first->GetOatDexFile() != nullptr &&
+          it->first->GetOatDexFile()->GetOatFile() == oat_file) {
         initialize_oat_file_data = false;  // Already initialized.
       }
       ++it;
@@ -3916,9 +3916,8 @@ void ClassLinker::RegisterDexFileLocked(const DexFile& dex_file,
   jweak dex_cache_jweak = vm->AddWeakGlobalRef(self, dex_cache);
   DexCacheData data;
   data.weak_root = dex_cache_jweak;
-  data.dex_file = dex_cache->GetDexFile();
   data.class_table = ClassTableForClassLoader(class_loader);
-  AddNativeDebugInfoForDex(self, data.dex_file);
+  AddNativeDebugInfoForDex(self, &dex_file);
   DCHECK(data.class_table != nullptr);
   // Make sure to hold the dex cache live in the class table. This case happens for the boot class
   // path dex caches without an image.
@@ -3930,7 +3929,8 @@ void ClassLinker::RegisterDexFileLocked(const DexFile& dex_file,
     // remembered sets and generational GCs.
     WriteBarrier::ForEveryFieldWrite(class_loader);
   }
-  dex_caches_.push_back(data);
+  bool inserted = dex_caches_.emplace(&dex_file, std::move(data)).second;
+  CHECK(inserted);
 }
 
 ObjPtr<mirror::DexCache> ClassLinker::DecodeDexCacheLocked(Thread* self, const DexCacheData* data) {
@@ -3944,7 +3944,7 @@ bool ClassLinker::IsSameClassLoader(
     const DexCacheData* data,
     ObjPtr<mirror::ClassLoader> class_loader) {
   CHECK(data != nullptr);
-  DCHECK_EQ(dex_cache->GetDexFile(), data->dex_file);
+  DCHECK_EQ(FindDexCacheDataLocked(*dex_cache->GetDexFile()), data);
   return data->class_table == ClassTableForClassLoader(class_loader);
 }
 
@@ -4089,13 +4089,14 @@ ObjPtr<mirror::DexCache> ClassLinker::FindDexCache(Thread* self, const DexFile&
     return dex_cache;
   }
   // Failure, dump diagnostic and abort.
-  for (const DexCacheData& data : dex_caches_) {
+  for (const auto& entry : dex_caches_) {
+    const DexCacheData& data = entry.second;
     if (DecodeDexCacheLocked(self, &data) != nullptr) {
-      LOG(FATAL_WITHOUT_ABORT) << "Registered dex file " << data.dex_file->GetLocation();
+      LOG(FATAL_WITHOUT_ABORT) << "Registered dex file " << entry.first->GetLocation();
     }
   }
   LOG(FATAL) << "Failed to find DexCache for DexFile " << dex_file.GetLocation()
-             << " " << &dex_file << " " << dex_cache_data->dex_file;
+             << " " << &dex_file;
   UNREACHABLE();
 }
 
@@ -4103,29 +4104,21 @@ ClassTable* ClassLinker::FindClassTable(Thread* self, ObjPtr<mirror::DexCache> d
   const DexFile* dex_file = dex_cache->GetDexFile();
   DCHECK(dex_file != nullptr);
   ReaderMutexLock mu(self, *Locks::dex_lock_);
-  // Search assuming unique-ness of dex file.
-  for (const DexCacheData& data : dex_caches_) {
-    // Avoid decoding (and read barriers) other unrelated dex caches.
-    if (data.dex_file == dex_file) {
-      ObjPtr<mirror::DexCache> registered_dex_cache = DecodeDexCacheLocked(self, &data);
-      if (registered_dex_cache != nullptr) {
-        CHECK_EQ(registered_dex_cache, dex_cache) << dex_file->GetLocation();
-        return data.class_table;
-      }
+  auto it = dex_caches_.find(dex_file);
+  if (it != dex_caches_.end()) {
+    const DexCacheData& data = it->second;
+    ObjPtr<mirror::DexCache> registered_dex_cache = DecodeDexCacheLocked(self, &data);
+    if (registered_dex_cache != nullptr) {
+      CHECK_EQ(registered_dex_cache, dex_cache) << dex_file->GetLocation();
+      return data.class_table;
     }
   }
   return nullptr;
 }
 
 const ClassLinker::DexCacheData* ClassLinker::FindDexCacheDataLocked(const DexFile& dex_file) {
-  // Search assuming unique-ness of dex file.
-  for (const DexCacheData& data : dex_caches_) {
-    // Avoid decoding (and read barriers) other unrelated dex caches.
-    if (data.dex_file == &dex_file) {
-      return &data;
-    }
-  }
-  return nullptr;
+  auto it = dex_caches_.find(&dex_file);
+  return it != dex_caches_.end() ? &it->second : nullptr;
 }
 
 void ClassLinker::CreatePrimitiveClass(Thread* self,
@@ -9754,13 +9747,14 @@ void ClassLinker::DumpForSigQuit(std::ostream& os) {
     if (loader != nullptr) {
       os << "#" << class_loader_index++ << " " << loader->GetClass()->PrettyDescriptor() << ": [";
       bool saw_one_dex_file = false;
-      for (const DexCacheData& dex_cache : dex_caches_) {
-        if (dex_cache.IsValid() && dex_cache.class_table == class_loader.class_table) {
+      for (const auto& entry : dex_caches_) {
+        const DexCacheData& dex_cache = entry.second;
+        if (dex_cache.class_table == class_loader.class_table) {
           if (saw_one_dex_file) {
             os << ":";
           }
           saw_one_dex_file = true;
-          os << dex_cache.dex_file->GetLocation();
+          os << entry.first->GetLocation();
         }
       }
       os << "]";
diff --git a/runtime/class_linker.h b/runtime/class_linker.h
index 5faf7602cb..59797f95bb 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -22,6 +22,7 @@
 #include <set>
 #include <string>
 #include <type_traits>
+#include <unordered_map>
 #include <utility>
 #include <vector>
 
@@ -807,27 +808,26 @@ class ClassLinker {
 
   struct DexCacheData {
     // Construct an invalid data object.
-    DexCacheData()
-        : weak_root(nullptr),
-          dex_file(nullptr),
-          class_table(nullptr) { }
-
-    // Check if the data is valid.
-    bool IsValid() const {
-      return dex_file != nullptr;
+    DexCacheData() : weak_root(nullptr), class_table(nullptr) {
+      static std::atomic_uint64_t s_registration_count(0);
+      registration_index = s_registration_count.fetch_add(1, std::memory_order_seq_cst);
     }
+    DexCacheData(DexCacheData&&) = default;
 
     // Weak root to the DexCache. Note: Do not decode this unnecessarily or else class unloading may
     // not work properly.
     jweak weak_root;
-    // The following field caches the DexCache's field here to avoid unnecessary jweak decode that
-    // triggers read barriers (and marks them alive unnecessarily and messes with class unloading.)
-    const DexFile* dex_file;
     // Identify the associated class loader's class table. This is used to make sure that
     // the Java call to native DexCache.setResolvedType() inserts the resolved type in that
     // class table. It is also used to make sure we don't register the same dex cache with
     // multiple class loaders.
     ClassTable* class_table;
+    // Monotonically increasing integer which records the order in which DexFiles were registered.
+    // Used only to preserve determinism when creating compiled image.
+    uint64_t registration_index;
+
+   private:
+    DISALLOW_COPY_AND_ASSIGN(DexCacheData);
   };
 
   // Forces a class to be marked as initialized without actually running initializers. Should only
@@ -1103,7 +1103,7 @@ class ClassLinker {
       REQUIRES(Locks::dex_lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
   const DexCacheData* FindDexCacheDataLocked(const DexFile& dex_file)
-      REQUIRES(Locks::dex_lock_)
+      REQUIRES_SHARED(Locks::dex_lock_)
       REQUIRES_SHARED(Locks::mutator_lock_);
   static ObjPtr<mirror::DexCache> DecodeDexCacheLocked(Thread* self, const DexCacheData* data)
       REQUIRES_SHARED(Locks::dex_lock_, Locks::mutator_lock_);
@@ -1244,7 +1244,7 @@ class ClassLinker {
   size_t GetDexCacheCount() REQUIRES_SHARED(Locks::mutator_lock_, Locks::dex_lock_) {
     return dex_caches_.size();
   }
-  const std::list<DexCacheData>& GetDexCachesData()
+  const std::unordered_map<const DexFile*, DexCacheData>& GetDexCachesData()
       REQUIRES_SHARED(Locks::mutator_lock_, Locks::dex_lock_) {
     return dex_caches_;
   }
@@ -1358,7 +1358,7 @@ class ClassLinker {
 
   // JNI weak globals and side data to allow dex caches to get unloaded. We lazily delete weak
   // globals when we register new dex files.
-  std::list<DexCacheData> dex_caches_ GUARDED_BY(Locks::dex_lock_);
+  std::unordered_map<const DexFile*, DexCacheData> dex_caches_ GUARDED_BY(Locks::dex_lock_);
 
   // This contains the class loaders which have class tables. It is populated by
   // InsertClassTableForClassLoader.
diff --git a/runtime/class_linker_test.cc b/runtime/class_linker_test.cc
index e0f498d6aa..035a9cbfa5 100644
--- a/runtime/class_linker_test.cc
+++ b/runtime/class_linker_test.cc
@@ -1520,7 +1520,8 @@ TEST_F(ClassLinkerTest, RegisterDexFileName) {
   MutableHandle<mirror::DexCache> dex_cache(hs.NewHandle<mirror::DexCache>(nullptr));
   {
     ReaderMutexLock mu(soa.Self(), *Locks::dex_lock_);
-    for (const ClassLinker::DexCacheData& data : class_linker->GetDexCachesData()) {
+    for (const auto& entry : class_linker->GetDexCachesData()) {
+      const ClassLinker::DexCacheData& data = entry.second;
       dex_cache.Assign(soa.Self()->DecodeJObject(data.weak_root)->AsDexCache());
       if (dex_cache != nullptr) {
         break;