Fix vdex fast-verify performance regression

Recent CL I0d06b82e31088c58d4493723a5435309740f1d0c generalized the
fast-verify class redefinition check by checking that all vdex-verified
classes resolve to dex files covered by the vdex and are not duplicates
of classes in parent class loaders. This introduced a performance and
allocated memory regression for dex2oat invoked with
compiler-filter=verify(-profile).

This patch removes the regression by acquiring a list of classpath dex
files from the compiler driver and boot classpath dex files from the
class linker, avoiding class resolution altogether.

A small performance overhead remains as previously only boot classpath
was being searched.

Test: run `dex2oat filter=interpret-only; dex2oat filter=verify`
      compare time and allocated memory numbers before CL and after
Change-Id: Ifd690cdafdc99d3eafb9847d67775fc11a5b5023

6 files changed, 75 insertions, 40 deletions

diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 54e94d0ba2..33201cf476 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -1786,7 +1786,13 @@ bool CompilerDriver::FastVerify(jobject jclass_loader,
       hs.NewHandle(soa.Decode<mirror::ClassLoader>(jclass_loader)));
   std::string error_msg;
 
-  if (!verifier_deps->ValidateDependencies(class_loader, soa.Self(), &error_msg)) {
+  if (!verifier_deps->ValidateDependencies(
+      soa.Self(),
+      class_loader,
+      // This returns classpath dex files in no particular order but VerifierDeps
+      // does not care about the order.
+      classpath_classes_.GetDexFiles(),
+      &error_msg)) {
     LOG(WARNING) << "Fast verification failed: " << error_msg;
     return false;
   }
diff --git a/compiler/utils/atomic_dex_ref_map-inl.h b/compiler/utils/atomic_dex_ref_map-inl.h
index 9915498acc..377b7fe352 100644
--- a/compiler/utils/atomic_dex_ref_map-inl.h
+++ b/compiler/utils/atomic_dex_ref_map-inl.h
@@ -134,6 +134,17 @@ inline void AtomicDexRefMap<DexFileReferenceType, Value>::ClearEntries() {
   }
 }
 
+template <typename DexFileReferenceType, typename Value>
+inline std::vector<const DexFile*> AtomicDexRefMap<DexFileReferenceType, Value>::GetDexFiles()
+    const {
+  std::vector<const DexFile*> result;
+  result.reserve(arrays_.size());
+  for (auto& it : arrays_) {
+    result.push_back(it.first);
+  }
+  return result;
+}
+
 }  // namespace art
 
 #endif  // ART_COMPILER_UTILS_ATOMIC_DEX_REF_MAP_INL_H_
diff --git a/compiler/utils/atomic_dex_ref_map.h b/compiler/utils/atomic_dex_ref_map.h
index fc2437999e..a8c285f765 100644
--- a/compiler/utils/atomic_dex_ref_map.h
+++ b/compiler/utils/atomic_dex_ref_map.h
@@ -54,6 +54,9 @@ class AtomicDexRefMap {
   void AddDexFile(const DexFile* dex_file);
   void AddDexFiles(const std::vector<const DexFile*>& dex_files);
 
+  // Return a vector of all dex files which were added to the map.
+  std::vector<const DexFile*> GetDexFiles() const;
+
   bool HaveDexFile(const DexFile* dex_file) const {
     return arrays_.find(dex_file) != arrays_.end();
   }
diff --git a/compiler/utils/atomic_dex_ref_map_test.cc b/compiler/utils/atomic_dex_ref_map_test.cc
index 4e1ef1248d..864531ed91 100644
--- a/compiler/utils/atomic_dex_ref_map_test.cc
+++ b/compiler/utils/atomic_dex_ref_map_test.cc
@@ -41,6 +41,9 @@ TEST_F(AtomicDexRefMapTest, RunTests) {
   EXPECT_TRUE(map.Insert(MethodReference(dex.get(), 1), 0, 1) == Map::kInsertResultInvalidDexFile);
   map.AddDexFile(dex.get());
   EXPECT_TRUE(map.HaveDexFile(dex.get()));
+  std::vector<const DexFile*> registered_dex_files = map.GetDexFiles();
+  EXPECT_EQ(1u, registered_dex_files.size());
+  EXPECT_TRUE(registered_dex_files[0] == dex.get());
   EXPECT_GT(dex->NumMethodIds(), 10u);
   // After we have added the get should succeed but return the default value.
   EXPECT_TRUE(map.Get(MethodReference(dex.get(), 1), &value));
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index 9b517136d1..bdffda62f7 100644
--- a/runtime/verifier/verifier_deps.cc
+++ b/runtime/verifier/verifier_deps.cc
@@ -29,6 +29,7 @@
 #include "dex/dex_file-inl.h"
 #include "mirror/class-inl.h"
 #include "mirror/class_loader.h"
+#include "oat_file.h"
 #include "obj_ptr-inl.h"
 #include "runtime.h"
 
@@ -885,11 +886,12 @@ void VerifierDeps::Dump(VariableIndentationOutputStream* vios) const {
   }
 }
 
-bool VerifierDeps::ValidateDependencies(Handle<mirror::ClassLoader> class_loader,
-                                        Thread* self,
+bool VerifierDeps::ValidateDependencies(Thread* self,
+                                        Handle<mirror::ClassLoader> class_loader,
+                                        const std::vector<const DexFile*>& classpath,
                                         /* out */ std::string* error_msg) const {
   for (const auto& entry : dex_deps_) {
-    if (!VerifyDexFile(class_loader, *entry.first, *entry.second, self, error_msg)) {
+    if (!VerifyDexFile(class_loader, *entry.first, *entry.second, classpath, self, error_msg)) {
       return false;
     }
   }
@@ -1113,23 +1115,34 @@ bool VerifierDeps::VerifyMethods(Handle<mirror::ClassLoader> class_loader,
   return true;
 }
 
-bool VerifierDeps::VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
-                                         const DexFile& dex_file,
+bool VerifierDeps::IsInDexFiles(const char* descriptor,
+                                size_t hash,
+                                const std::vector<const DexFile*>& dex_files,
+                                /* out */ const DexFile** out_dex_file) const {
+  for (const DexFile* dex_file : dex_files) {
+    if (OatDexFile::FindClassDef(*dex_file, descriptor, hash) != nullptr) {
+      *out_dex_file = dex_file;
+      return true;
+    }
+  }
+  return false;
+}
+
+bool VerifierDeps::VerifyInternalClasses(const DexFile& dex_file,
+                                         const std::vector<const DexFile*>& classpath,
                                          const std::vector<bool>& verified_classes,
                                          const std::vector<bool>& redefined_classes,
-                                         Thread* self,
                                          /* out */ std::string* error_msg) const {
-  ClassLinker* const class_linker = Runtime::Current()->GetClassLinker();
+  const std::vector<const DexFile*>& boot_classpath =
+      Runtime::Current()->GetClassLinker()->GetBootClassPath();
 
   for (ClassAccessor accessor : dex_file.GetClasses()) {
-    const std::string descriptor = accessor.GetDescriptor();
-    const uint16_t class_def_index = accessor.GetClassDefIndex();
-    const bool verified = verified_classes[class_def_index];
-    const bool redefined = redefined_classes[class_def_index];
+    const char* descriptor = accessor.GetDescriptor();
 
-    if (redefined) {
-      if (verified) {
-        *error_msg = "Class " + descriptor + " marked both verified and redefined";
+    const uint16_t class_def_index = accessor.GetClassDefIndex();
+    if (redefined_classes[class_def_index]) {
+      if (verified_classes[class_def_index]) {
+        *error_msg = std::string("Class ") + descriptor + " marked both verified and redefined";
         return false;
       }
 
@@ -1137,26 +1150,17 @@ bool VerifierDeps::VerifyInternalClasses(Handle<mirror::ClassLoader> class_loade
       continue;
     }
 
-    ObjPtr<mirror::Class> cls =
-        FindClassAndClearException(class_linker, self, descriptor, class_loader);
-    if (UNLIKELY(cls == nullptr)) {
-      // Could not resolve class from the currently verified dex file.
-      // This can happen when the class fails to link. Check if this
-      // expected by looking in the `verified_classes` bit vector.
-      if (verified) {
-        *error_msg = "Failed to resolve internal class " + descriptor;
-        return false;
-      }
-      continue;
-    }
-
     // Check that the class resolved into the same dex file. Otherwise there is
     // a different class with the same descriptor somewhere in one of the parent
     // class loaders.
-    if (&cls->GetDexFile() != &dex_file) {
-      *error_msg = "Class " + descriptor + " redefines a class in the classpath "
-          + "(dexFile expected=" + accessor.GetDexFile().GetLocation()
-          + ", actual=" + cls->GetDexFile().GetLocation() + ")";
+    const size_t hash = ComputeModifiedUtf8Hash(descriptor);
+    const DexFile* cp_dex_file = nullptr;
+    if (IsInDexFiles(descriptor, hash, boot_classpath, &cp_dex_file) ||
+        IsInDexFiles(descriptor, hash, classpath, &cp_dex_file)) {
+      *error_msg = std::string("Class ") + descriptor
+          + " redefines a class in the classpath "
+          + "(dexFile expected=" + dex_file.GetLocation()
+          + ", actual=" + cp_dex_file->GetLocation() + ")";
       return false;
     }
   }
@@ -1167,13 +1171,13 @@ bool VerifierDeps::VerifyInternalClasses(Handle<mirror::ClassLoader> class_loade
 bool VerifierDeps::VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
                                  const DexFile& dex_file,
                                  const DexFileDeps& deps,
+                                 const std::vector<const DexFile*>& classpath,
                                  Thread* self,
                                  /* out */ std::string* error_msg) const {
-  return VerifyInternalClasses(class_loader,
-                               dex_file,
+  return VerifyInternalClasses(dex_file,
+                               classpath,
                                deps.verified_classes_,
                                deps.redefined_classes_,
-                               self,
                                error_msg) &&
          VerifyAssignability(class_loader,
                              dex_file,
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index d38b84091a..bf9cdc75ec 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -120,8 +120,9 @@ class VerifierDeps {
   void Dump(VariableIndentationOutputStream* vios) const;
 
   // Verify the encoded dependencies of this `VerifierDeps` are still valid.
-  bool ValidateDependencies(Handle<mirror::ClassLoader> class_loader,
-                            Thread* self,
+  bool ValidateDependencies(Thread* self,
+                            Handle<mirror::ClassLoader> class_loader,
+                            const std::vector<const DexFile*>& classpath,
                             /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
@@ -310,10 +311,18 @@ class VerifierDeps {
   bool VerifyDexFile(Handle<mirror::ClassLoader> class_loader,
                      const DexFile& dex_file,
                      const DexFileDeps& deps,
+                     const std::vector<const DexFile*>& classpath,
                      Thread* self,
                      /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Iterates over `dex_files` and tries to find a class def matching `descriptor`.
+  // Returns true if such class def is found.
+  bool IsInDexFiles(const char* descriptor,
+                    size_t hash,
+                    const std::vector<const DexFile*>& dex_files,
+                    /* out */ const DexFile** cp_dex_file) const;
+
   // Check that classes which are to be verified using these dependencies
   // are not eclipsed by classes in parent class loaders, e.g. when vdex was
   // created against SDK stubs and the app redefines a non-public class on
@@ -321,11 +330,10 @@ class VerifierDeps {
   // dependencies do not include the dependencies on the presumed-internal class
   // and verification must fail unless the class was recorded to have been
   // redefined during dependencies' generation too.
-  bool VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
-                             const DexFile& dex_file,
+  bool VerifyInternalClasses(const DexFile& dex_file,
+                             const std::vector<const DexFile*>& classpath,
                              const std::vector<bool>& verified_classes,
                              const std::vector<bool>& redefined_classes,
-                             Thread* self,
                              /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);