Merge changes Ifd690cda,I7bcbe947

* changes:
  Fix vdex fast-verify performance regression
  Improve `verified`, add `redefined` class status in VerifierDeps

16 files changed, 311 insertions, 129 deletions

diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index e9a3d550d9..1c9830bd94 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -1784,7 +1784,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;
   }
@@ -1797,11 +1803,11 @@ bool CompilerDriver::FastVerify(jobject jclass_loader,
   // time. So instead we assume these classes still need to be verified at
   // runtime.
   for (const DexFile* dex_file : dex_files) {
-    // Fetch the list of unverified classes.
-    const std::set<dex::TypeIndex>& unverified_classes =
-        verifier_deps->GetUnverifiedClasses(*dex_file);
+    // Fetch the list of verified classes.
+    const std::vector<bool>& verified_classes = verifier_deps->GetVerifiedClasses(*dex_file);
+    DCHECK_EQ(verified_classes.size(), dex_file->NumClassDefs());
     for (ClassAccessor accessor : dex_file->GetClasses()) {
-      if (unverified_classes.find(accessor.GetClassIdx()) == unverified_classes.end()) {
+      if (verified_classes[accessor.GetClassDefIndex()]) {
         if (compiler_only_verifies) {
           // Just update the compiled_classes_ map. The compiler doesn't need to resolve
           // the type.
@@ -1951,6 +1957,16 @@ class VerifyClassVisitor : public CompilationVisitor {
       }
     } else if (&klass->GetDexFile() != &dex_file) {
       // Skip a duplicate class (as the resolved class is from another, earlier dex file).
+      // Record the information that we skipped this class in the vdex.
+      // If the class resolved to a dex file not covered by the vdex, e.g. boot class path,
+      // it is considered external, dependencies on it will be recorded and the vdex will
+      // remain usable regardless of whether the class remains redefined or not (in the
+      // latter case, this class will be verify-at-runtime).
+      // On the other hand, if the class resolved to a dex file covered by the vdex, i.e.
+      // a different dex file within the same APK, this class will always be eclipsed by it.
+      // Recording that it was redefined is not necessary but will save class resolution
+      // time during fast-verify.
+      verifier::VerifierDeps::MaybeRecordClassRedefinition(dex_file, class_def);
       return;  // Do not update state.
     } else if (!SkipClass(jclass_loader, dex_file, klass.Get())) {
       CHECK(klass->IsResolved()) << klass->PrettyClass();
@@ -1999,8 +2015,7 @@ class VerifyClassVisitor : public CompilationVisitor {
       // Make the skip a soft failure, essentially being considered as verify at runtime.
       failure_kind = verifier::FailureKind::kSoftFailure;
     }
-    verifier::VerifierDeps::MaybeRecordVerificationStatus(
-        dex_file, class_def.class_idx_, failure_kind);
+    verifier::VerifierDeps::MaybeRecordVerificationStatus(dex_file, class_def, failure_kind);
     soa.Self()->AssertNoPendingException();
   }
 
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/compiler/verifier_deps_test.cc b/compiler/verifier_deps_test.cc
index 5c6b815ad5..4d260588f7 100644
--- a/compiler/verifier_deps_test.cc
+++ b/compiler/verifier_deps_test.cc
@@ -226,7 +226,8 @@ class VerifierDepsTest : public CommonCompilerTest {
         hs.NewHandle(soa.Decode<mirror::ClassLoader>(class_loader_)));
     MutableHandle<mirror::Class> cls(hs.NewHandle<mirror::Class>(nullptr));
     for (const DexFile* dex_file : dex_files_) {
-      const std::set<dex::TypeIndex>& unverified_classes = deps.GetUnverifiedClasses(*dex_file);
+      const std::vector<bool>& verified_classes = deps.GetVerifiedClasses(*dex_file);
+      ASSERT_EQ(verified_classes.size(), dex_file->NumClassDefs());
       for (uint32_t i = 0; i < dex_file->NumClassDefs(); ++i) {
         const dex::ClassDef& class_def = dex_file->GetClassDef(i);
         const char* descriptor = dex_file->GetClassDescriptor(class_def);
@@ -236,7 +237,7 @@ class VerifierDepsTest : public CommonCompilerTest {
           soa.Self()->ClearException();
         } else if (&cls->GetDexFile() != dex_file) {
           // Ignore classes from different dex files.
-        } else if (unverified_classes.find(class_def.class_idx_) == unverified_classes.end()) {
+        } else if (verified_classes[i]) {
           ASSERT_EQ(cls->GetStatus(), ClassStatus::kVerified);
         } else {
           ASSERT_LT(cls->GetStatus(), ClassStatus::kVerified);
@@ -245,22 +246,27 @@ class VerifierDepsTest : public CommonCompilerTest {
     }
   }
 
+  uint16_t GetClassDefIndex(const std::string& cls, const DexFile& dex_file) {
+    const dex::TypeId* type_id = dex_file.FindTypeId(cls.c_str());
+    DCHECK(type_id != nullptr);
+    dex::TypeIndex type_idx = dex_file.GetIndexForTypeId(*type_id);
+    const dex::ClassDef* class_def = dex_file.FindClassDef(type_idx);
+    DCHECK(class_def != nullptr);
+    return dex_file.GetIndexForClassDef(*class_def);
+  }
+
   bool HasUnverifiedClass(const std::string& cls) {
     return HasUnverifiedClass(cls, *primary_dex_file_);
   }
 
   bool HasUnverifiedClass(const std::string& cls, const DexFile& dex_file) {
-    const dex::TypeId* type_id = dex_file.FindTypeId(cls.c_str());
-    DCHECK(type_id != nullptr);
-    dex::TypeIndex index = dex_file.GetIndexForTypeId(*type_id);
-    for (const auto& dex_dep : verifier_deps_->dex_deps_) {
-      for (dex::TypeIndex entry : dex_dep.second->unverified_classes_) {
-        if (index == entry) {
-          return true;
-        }
-      }
-    }
-    return false;
+    uint16_t class_def_idx = GetClassDefIndex(cls, dex_file);
+    return !verifier_deps_->GetVerifiedClasses(dex_file)[class_def_idx];
+  }
+
+  bool HasRedefinedClass(const std::string& cls) {
+    uint16_t class_def_idx = GetClassDefIndex(cls, *primary_dex_file_);
+    return verifier_deps_->GetRedefinedClasses(*primary_dex_file_)[class_def_idx];
   }
 
   // Iterates over all assignability records and tries to find an entry which
@@ -423,13 +429,20 @@ class VerifierDepsTest : public CommonCompilerTest {
     return verifier_deps_->dex_deps_.size();
   }
 
+  bool HasBoolValue(const std::vector<bool>& vec, bool value) {
+    return std::count(vec.begin(), vec.end(), value) > 0;
+  }
+
   bool HasEachKindOfRecord() {
     bool has_strings = false;
     bool has_assignability = false;
     bool has_classes = false;
     bool has_fields = false;
     bool has_methods = false;
+    bool has_verified_classes = false;
     bool has_unverified_classes = false;
+    bool has_redefined_classes = false;
+    bool has_not_redefined_classes = false;
 
     for (auto& entry : verifier_deps_->dex_deps_) {
       has_strings |= !entry.second->strings_.empty();
@@ -438,7 +451,10 @@ class VerifierDepsTest : public CommonCompilerTest {
       has_classes |= !entry.second->classes_.empty();
       has_fields |= !entry.second->fields_.empty();
       has_methods |= !entry.second->methods_.empty();
-      has_unverified_classes |= !entry.second->unverified_classes_.empty();
+      has_verified_classes |= HasBoolValue(entry.second->verified_classes_, true);
+      has_unverified_classes |= HasBoolValue(entry.second->verified_classes_, false);
+      has_redefined_classes |= HasBoolValue(entry.second->redefined_classes_, true);
+      has_not_redefined_classes |= HasBoolValue(entry.second->redefined_classes_, false);
     }
 
     return has_strings &&
@@ -446,7 +462,10 @@ class VerifierDepsTest : public CommonCompilerTest {
            has_classes &&
            has_fields &&
            has_methods &&
-           has_unverified_classes;
+           has_verified_classes &&
+           has_unverified_classes &&
+           has_redefined_classes &&
+           has_not_redefined_classes;
   }
 
   // Load the dex file again with a new class loader, decode the VerifierDeps
@@ -468,7 +487,11 @@ class VerifierDepsTest : public CommonCompilerTest {
     StackHandleScope<1> hs(soa.Self());
     Handle<mirror::ClassLoader> new_class_loader =
         hs.NewHandle<mirror::ClassLoader>(soa.Decode<mirror::ClassLoader>(second_loader));
-    return decoded_deps.ValidateDependencies(new_class_loader, soa.Self(), error_msg);
+
+    return decoded_deps.ValidateDependencies(soa.Self(),
+                                             new_class_loader,
+                                             std::vector<const DexFile*>(),
+                                             error_msg);
   }
 
   std::unique_ptr<verifier::VerifierDeps> verifier_deps_;
@@ -1165,6 +1188,20 @@ TEST_F(VerifierDepsTest, UnverifiedClasses) {
   ASSERT_TRUE(HasUnverifiedClass("LMyClassWithNoSuperButFailures;"));
 }
 
+TEST_F(VerifierDepsTest, RedefinedClass) {
+  VerifyDexFile();
+  // Test that a class which redefines a boot classpath class has dependencies recorded.
+  ASSERT_TRUE(HasRedefinedClass("Ljava/net/SocketTimeoutException;"));
+  // These come from test case InstanceField_Resolved_DeclaredInSuperclass1.
+  ASSERT_TRUE(HasClass("Ljava/net/SocketTimeoutException;", true, "public"));
+  ASSERT_TRUE(HasField("Ljava/net/SocketTimeoutException;",
+                       "bytesTransferred",
+                       "I",
+                       true,
+                       "public",
+                       "Ljava/io/InterruptedIOException;"));
+}
+
 TEST_F(VerifierDepsTest, UnverifiedOrder) {
   ScopedObjectAccess soa(Thread::Current());
   jobject loader = LoadDex("VerifierDeps");
@@ -1176,19 +1213,19 @@ TEST_F(VerifierDepsTest, UnverifiedOrder) {
   ASSERT_TRUE(self->GetVerifierDeps() == nullptr);
   self->SetVerifierDeps(&deps1);
   deps1.MaybeRecordVerificationStatus(*dex_file,
-                                      dex::TypeIndex(0),
+                                      dex_file->GetClassDef(0u),
                                       verifier::FailureKind::kHardFailure);
   deps1.MaybeRecordVerificationStatus(*dex_file,
-                                      dex::TypeIndex(1),
+                                      dex_file->GetClassDef(1u),
                                       verifier::FailureKind::kHardFailure);
   VerifierDeps deps2(dex_files);
   self->SetVerifierDeps(nullptr);
   self->SetVerifierDeps(&deps2);
   deps2.MaybeRecordVerificationStatus(*dex_file,
-                                      dex::TypeIndex(1),
+                                      dex_file->GetClassDef(1u),
                                       verifier::FailureKind::kHardFailure);
   deps2.MaybeRecordVerificationStatus(*dex_file,
-                                      dex::TypeIndex(0),
+                                      dex_file->GetClassDef(0u),
                                       verifier::FailureKind::kHardFailure);
   self->SetVerifierDeps(nullptr);
   std::vector<uint8_t> buffer1;
diff --git a/runtime/vdex_file.h b/runtime/vdex_file.h
index a39ec3128f..b357d956aa 100644
--- a/runtime/vdex_file.h
+++ b/runtime/vdex_file.h
@@ -92,8 +92,8 @@ class VdexFile {
     static constexpr uint8_t kVdexMagic[] = { 'v', 'd', 'e', 'x' };
 
     // The format version of the verifier deps header and the verifier deps.
-    // Last update: Add DexSectionHeader
-    static constexpr uint8_t kVerifierDepsVersion[] = { '0', '1', '9', '\0' };
+    // Last update: Add `redefined_classes_`.
+    static constexpr uint8_t kVerifierDepsVersion[] = { '0', '2', '0', '\0' };
 
     // The format version of the dex section header and the dex section, containing
     // both the dex code and the quickening data.
diff --git a/runtime/verifier/verifier_deps.cc b/runtime/verifier/verifier_deps.cc
index 6793a0ab1f..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"
 
@@ -39,7 +40,7 @@ VerifierDeps::VerifierDeps(const std::vector<const DexFile*>& dex_files, bool ou
     : output_only_(output_only) {
   for (const DexFile* dex_file : dex_files) {
     DCHECK(GetDexFileDeps(*dex_file) == nullptr);
-    std::unique_ptr<DexFileDeps> deps(new DexFileDeps());
+    std::unique_ptr<DexFileDeps> deps(new DexFileDeps(dex_file->NumClassDefs()));
     dex_deps_.emplace(dex_file, std::move(deps));
   }
 }
@@ -47,6 +48,18 @@ VerifierDeps::VerifierDeps(const std::vector<const DexFile*>& dex_files, bool ou
 VerifierDeps::VerifierDeps(const std::vector<const DexFile*>& dex_files)
     : VerifierDeps(dex_files, /*output_only=*/ true) {}
 
+// Perform logical OR on two bit vectors and assign back to LHS, i.e. `to_update |= other`.
+// Size of the two vectors must be equal.
+// Size of `other` must be equal to size of `to_update`.
+static inline void BitVectorOr(std::vector<bool>& to_update, const std::vector<bool>& other) {
+  DCHECK_EQ(to_update.size(), other.size());
+  std::transform(other.begin(),
+                 other.end(),
+                 to_update.begin(),
+                 to_update.begin(),
+                 std::logical_or<bool>());
+}
+
 void VerifierDeps::MergeWith(std::unique_ptr<VerifierDeps> other,
                              const std::vector<const DexFile*>& dex_files) {
   DCHECK(other != nullptr);
@@ -62,7 +75,8 @@ void VerifierDeps::MergeWith(std::unique_ptr<VerifierDeps> other,
     my_deps->classes_.merge(other_deps.classes_);
     my_deps->fields_.merge(other_deps.fields_);
     my_deps->methods_.merge(other_deps.methods_);
-    my_deps->unverified_classes_.merge(other_deps.unverified_classes_);
+    BitVectorOr(my_deps->verified_classes_, other_deps.verified_classes_);
+    BitVectorOr(my_deps->redefined_classes_, other_deps.redefined_classes_);
   }
 }
 
@@ -498,18 +512,30 @@ void VerifierDeps::AddAssignability(const DexFile& dex_file,
   }
 }
 
+void VerifierDeps::MaybeRecordClassRedefinition(const DexFile& dex_file,
+                                                const dex::ClassDef& class_def) {
+  VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
+  if (thread_deps != nullptr) {
+    DexFileDeps* dex_deps = thread_deps->GetDexFileDeps(dex_file);
+    DCHECK_EQ(dex_deps->redefined_classes_.size(), dex_file.NumClassDefs());
+    dex_deps->redefined_classes_[dex_file.GetIndexForClassDef(class_def)] = true;
+  }
+}
+
 void VerifierDeps::MaybeRecordVerificationStatus(const DexFile& dex_file,
-                                                 dex::TypeIndex type_idx,
+                                                 const dex::ClassDef& class_def,
                                                  FailureKind failure_kind) {
-  if (failure_kind == FailureKind::kNoFailure) {
-    // We only record classes that did not fully verify at compile time.
+  if (failure_kind != FailureKind::kNoFailure) {
+    // The `verified_classes_` bit vector is initialized to `false`.
+    // Only continue if we are about to write `true`.
     return;
   }
 
   VerifierDeps* thread_deps = GetThreadLocalVerifierDeps();
   if (thread_deps != nullptr) {
     DexFileDeps* dex_deps = thread_deps->GetDexFileDeps(dex_file);
-    dex_deps->unverified_classes_.insert(type_idx);
+    DCHECK_EQ(dex_deps->verified_classes_.size(), dex_file.NumClassDefs());
+    dex_deps->verified_classes_[dex_file.GetIndexForClassDef(class_def)] = true;
   }
 }
 
@@ -588,16 +614,6 @@ template<> inline dex::StringIndex Decode<dex::StringIndex>(uint32_t in) {
   return dex::StringIndex(in);
 }
 
-// TODO: Clean this up, if we use a template arg here it confuses the compiler.
-static inline void EncodeTuple(std::vector<uint8_t>* out, const dex::TypeIndex& t) {
-  EncodeUnsignedLeb128(out, Encode(t));
-}
-
-// TODO: Clean this up, if we use a template arg here it confuses the compiler.
-static inline void DecodeTuple(const uint8_t** in, const uint8_t* end, dex::TypeIndex* t) {
-  *t = Decode<dex::TypeIndex>(DecodeUint32WithOverflowCheck(in, end));
-}
-
 template<typename T1, typename T2>
 static inline void EncodeTuple(std::vector<uint8_t>* out, const std::tuple<T1, T2>& t) {
   EncodeUnsignedLeb128(out, Encode(std::get<0>(t)));
@@ -634,15 +650,6 @@ static inline void EncodeSet(std::vector<uint8_t>* out, const std::set<T>& set)
   }
 }
 
-template <typename T>
-static inline void EncodeUint16Vector(std::vector<uint8_t>* out,
-                                      const std::vector<T>& vector) {
-  EncodeUnsignedLeb128(out, vector.size());
-  for (const T& entry : vector) {
-    EncodeUnsignedLeb128(out, Encode(entry));
-  }
-}
-
 template<typename T>
 static inline void DecodeSet(const uint8_t** in, const uint8_t* end, std::set<T>* set) {
   DCHECK(set->empty());
@@ -654,16 +661,29 @@ static inline void DecodeSet(const uint8_t** in, const uint8_t* end, std::set<T>
   }
 }
 
-template<typename T>
-static inline void DecodeUint16Vector(const uint8_t** in,
-                                      const uint8_t* end,
-                                      std::vector<T>* vector) {
-  DCHECK(vector->empty());
+static inline void EncodeUint16SparseBitVector(std::vector<uint8_t>* out,
+                                               const std::vector<bool>& vector,
+                                               bool sparse_value) {
+  DCHECK(IsUint<16>(vector.size()));
+  EncodeUnsignedLeb128(out, std::count(vector.begin(), vector.end(), sparse_value));
+  for (uint16_t idx = 0; idx < vector.size(); ++idx) {
+    if (vector[idx] == sparse_value) {
+      EncodeUnsignedLeb128(out, Encode(idx));
+    }
+  }
+}
+
+static inline void DecodeUint16SparseBitVector(const uint8_t** in,
+                                               const uint8_t* end,
+                                               std::vector<bool>* vector,
+                                               bool sparse_value) {
+  DCHECK(IsUint<16>(vector->size()));
+  std::fill(vector->begin(), vector->end(), !sparse_value);
   size_t num_entries = DecodeUint32WithOverflowCheck(in, end);
-  vector->reserve(num_entries);
   for (size_t i = 0; i < num_entries; ++i) {
-    vector->push_back(
-        Decode<T>(dchecked_integral_cast<uint16_t>(DecodeUint32WithOverflowCheck(in, end))));
+    uint16_t idx = Decode<uint16_t>(DecodeUint32WithOverflowCheck(in, end));
+    DCHECK_LT(idx, vector->size());
+    (*vector)[idx] = sparse_value;
   }
 }
 
@@ -710,7 +730,8 @@ void VerifierDeps::Encode(const std::vector<const DexFile*>& dex_files,
     EncodeSet(buffer, deps.classes_);
     EncodeSet(buffer, deps.fields_);
     EncodeSet(buffer, deps.methods_);
-    EncodeSet(buffer, deps.unverified_classes_);
+    EncodeUint16SparseBitVector(buffer, deps.verified_classes_, /* sparse_value= */ false);
+    EncodeUint16SparseBitVector(buffer, deps.redefined_classes_, /* sparse_value= */ true);
   }
 }
 
@@ -733,7 +754,14 @@ VerifierDeps::VerifierDeps(const std::vector<const DexFile*>& dex_files,
     DecodeSet(&data_start, data_end, &deps->classes_);
     DecodeSet(&data_start, data_end, &deps->fields_);
     DecodeSet(&data_start, data_end, &deps->methods_);
-    DecodeSet(&data_start, data_end, &deps->unverified_classes_);
+    DecodeUint16SparseBitVector(&data_start,
+                                data_end,
+                                &deps->verified_classes_,
+                                /* sparse_value= */ false);
+    DecodeUint16SparseBitVector(&data_start,
+                                data_end,
+                                &deps->redefined_classes_,
+                                /* sparse_value= */ true);
   }
   CHECK_LE(data_start, data_end);
 }
@@ -771,7 +799,7 @@ bool VerifierDeps::DexFileDeps::Equals(const VerifierDeps::DexFileDeps& rhs) con
          (classes_ == rhs.classes_) &&
          (fields_ == rhs.fields_) &&
          (methods_ == rhs.methods_) &&
-         (unverified_classes_ == rhs.unverified_classes_);
+         (verified_classes_ == rhs.verified_classes_);
 }
 
 void VerifierDeps::Dump(VariableIndentationOutputStream* vios) const {
@@ -848,19 +876,22 @@ void VerifierDeps::Dump(VariableIndentationOutputStream* vios) const {
       }
     }
 
-    for (dex::TypeIndex type_index : dep.second->unverified_classes_) {
-      vios->Stream()
-          << dex_file.StringByTypeIdx(type_index)
-          << " is expected to be verified at runtime\n";
+    for (size_t idx = 0; idx < dep.second->verified_classes_.size(); idx++) {
+      if (!dep.second->verified_classes_[idx]) {
+        vios->Stream()
+            << dex_file.GetClassDescriptor(dex_file.GetClassDef(idx))
+            << " will be verified at runtime\n";
+      }
     }
   }
 }
 
-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;
     }
   }
@@ -1084,37 +1115,52 @@ bool VerifierDeps::VerifyMethods(Handle<mirror::ClassLoader> class_loader,
   return true;
 }
 
-bool VerifierDeps::VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
-                                         const DexFile& dex_file,
-                                         const std::set<dex::TypeIndex>& unverified_classes,
-                                         Thread* self,
+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,
                                          /* 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()) {
-    std::string descriptor = accessor.GetDescriptor();
-    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 `unverified_classes` set.
-      if (unverified_classes.find(accessor.GetClassDef().class_idx_) == unverified_classes.end()) {
-        *error_msg = "Failed to resolve internal class " + descriptor;
+    const char* descriptor = accessor.GetDescriptor();
+
+    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;
       }
+
+      // Class was not verified under these dependencies. No need to check it further.
       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 a parent class loader "
-          + "(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;
     }
   }
@@ -1125,12 +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,
-                               deps.unverified_classes_,
-                               self,
+  return VerifyInternalClasses(dex_file,
+                               classpath,
+                               deps.verified_classes_,
+                               deps.redefined_classes_,
                                error_msg) &&
          VerifyAssignability(class_loader,
                              dex_file,
diff --git a/runtime/verifier/verifier_deps.h b/runtime/verifier/verifier_deps.h
index fb4a4bf5c5..bf9cdc75ec 100644
--- a/runtime/verifier/verifier_deps.h
+++ b/runtime/verifier/verifier_deps.h
@@ -23,6 +23,7 @@
 
 #include "base/array_ref.h"
 #include "base/locks.h"
+#include "dex/dex_file_structs.h"
 #include "dex/dex_file_types.h"
 #include "handle.h"
 #include "obj_ptr.h"
@@ -65,12 +66,17 @@ class VerifierDeps {
   // same set of dex files.
   void MergeWith(std::unique_ptr<VerifierDeps> other, const std::vector<const DexFile*>& dex_files);
 
-  // Record the verification status of the class at `type_idx`.
+  // Record the verification status of the class defined in `class_def`.
   static void MaybeRecordVerificationStatus(const DexFile& dex_file,
-                                            dex::TypeIndex type_idx,
+                                            const dex::ClassDef& class_def,
                                             FailureKind failure_kind)
       REQUIRES(!Locks::verifier_deps_lock_);
 
+  // Record that class defined in `class_def` was not verified because it redefines
+  // a class with the same descriptor which takes precedence in class resolution.
+  static void MaybeRecordClassRedefinition(const DexFile& dex_file, const dex::ClassDef& class_def)
+      REQUIRES(!Locks::verifier_deps_lock_);
+
   // Record the outcome `klass` of resolving type `type_idx` from `dex_file`.
   // If `klass` is null, the class is assumed unresolved.
   static void MaybeRecordClassResolution(const DexFile& dex_file,
@@ -114,13 +120,18 @@ 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_);
 
-  const std::set<dex::TypeIndex>& GetUnverifiedClasses(const DexFile& dex_file) const {
-    return GetDexFileDeps(dex_file)->unverified_classes_;
+  const std::vector<bool>& GetVerifiedClasses(const DexFile& dex_file) const {
+    return GetDexFileDeps(dex_file)->verified_classes_;
+  }
+
+  const std::vector<bool>& GetRedefinedClasses(const DexFile& dex_file) const {
+    return GetDexFileDeps(dex_file)->redefined_classes_;
   }
 
   bool OutputOnly() const {
@@ -184,6 +195,10 @@ class VerifierDeps {
   // Data structure representing dependencies collected during verification of
   // methods inside one DexFile.
   struct DexFileDeps {
+    explicit DexFileDeps(size_t num_class_defs)
+        : verified_classes_(num_class_defs),
+          redefined_classes_(num_class_defs) {}
+
     // Vector of strings which are not present in the corresponding DEX file.
     // These are referred to with ids starting with `NumStringIds()` of that DexFile.
     std::vector<std::string> strings_;
@@ -198,8 +213,15 @@ class VerifierDeps {
     std::set<FieldResolution> fields_;
     std::set<MethodResolution> methods_;
 
-    // List of classes that were not fully verified in that dex file.
-    std::set<dex::TypeIndex> unverified_classes_;
+    // Bit vector indexed by class def indices indicating whether the corresponding
+    // class was successfully verified.
+    std::vector<bool> verified_classes_;
+
+    // Bit vector indexed by class def indices indicating whether the corresponding
+    // class resolved into a different class with the same descriptor (was eclipsed).
+    // The other class might have been both external (not covered by these VerifierDeps)
+    // and internal (same VerifierDeps, different DexFileDeps).
+    std::vector<bool> redefined_classes_;
 
     bool Equals(const DexFileDeps& rhs) const;
   };
@@ -289,22 +311,29 @@ 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
   // boot classpath, or simply if a class is added during an OTA. In such cases,
   // dependencies do not include the dependencies on the presumed-internal class
-  // and verification must fail.
-  // TODO(dbrazdil): Encode a set of redefined classes during full verification.
-  // If such class is found to be redefined at runtime, dependencies remain valid.
-  bool VerifyInternalClasses(Handle<mirror::ClassLoader> class_loader,
-                             const DexFile& dex_file,
-                             const std::set<dex::TypeIndex>& unverified_classes,
-                             Thread* self,
+  // and verification must fail unless the class was recorded to have been
+  // redefined during dependencies' generation too.
+  bool VerifyInternalClasses(const DexFile& dex_file,
+                             const std::vector<const DexFile*>& classpath,
+                             const std::vector<bool>& verified_classes,
+                             const std::vector<bool>& redefined_classes,
                              /* out */ std::string* error_msg) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
diff --git a/test/719-dm-verify-redefinition/check b/test/719-dm-verify-redefinition/check
index 9845eee123..b10a0e2aa9 100644
--- a/test/719-dm-verify-redefinition/check
+++ b/test/719-dm-verify-redefinition/check
@@ -15,7 +15,7 @@
 # limitations under the License.
 
 # Search for the redefinition line and remove unnecessary tags.
-sed -e 's/^dex2oat[d]\?\(\|32\|64\)\ W.*\] \(Fast verification failed: Class L[^;]*; redefines a class in a parent class loader\).*/\2/g' "$2" > "$2.tmp1"
+sed -e 's/^dex2oat[d]\?\(\|32\|64\)\ W.*\] \(Fast verification failed: Class L[^;]*; redefines a class in the classpath\).*/\2/g' "$2" > "$2.tmp1"
 # Remove all other dex2oat/dalvikvm log lines.
 grep -v dex2oat "$2.tmp1" | grep -v dalvikvm >> "$2.tmp2"
 
diff --git a/test/719-dm-verify-redefinition/expected.txt b/test/719-dm-verify-redefinition/expected.txt
index e1ab7d1e56..c210c0d3c1 100644
--- a/test/719-dm-verify-redefinition/expected.txt
+++ b/test/719-dm-verify-redefinition/expected.txt
@@ -1,3 +1,2 @@
-Fast verification failed: Class Ljava/util/BitSet; redefines a class in a parent class loader
+Fast verification failed: Class LRedefined; redefines a class in the classpath
 Hello, world!
-Correct resolution of boot class.
diff --git a/test/719-dm-verify-redefinition/run b/test/719-dm-verify-redefinition/run
index 8e568b59fb..f4e9d7124c 100644
--- a/test/719-dm-verify-redefinition/run
+++ b/test/719-dm-verify-redefinition/run
@@ -14,5 +14,13 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+# This will compile just the primary jar and then compile again with vdex
+# and the secondary jar in classpath. The Redefined class in the secondary
+# jar should take precedence and fast-verify should fail.
 export ANDROID_LOG_TAGS='*:w'
-exec ${RUN} --external-log-tags --dm "${@}"
+exec ${RUN} \
+  --external-log-tags \
+  --dm \
+  --vdex-arg \
+  --class-loader-context=PCL[$DEX_LOCATION/719-dm-verify-redefinition-ex.jar] \
+  "${@}"
diff --git a/test/719-dm-verify-redefinition/src/java/util/BitSet.java b/test/719-dm-verify-redefinition/src-ex/Redefined.java
index 5d91fd8d59..cab7974bf0 100644
--- a/test/719-dm-verify-redefinition/src/java/util/BitSet.java
+++ b/test/719-dm-verify-redefinition/src-ex/Redefined.java
@@ -14,7 +14,5 @@
  * limitations under the License.
  */
 
-package java.util;
-
-public class BitSet {
+public class Redefined {
 }
diff --git a/test/719-dm-verify-redefinition/src/Main.java b/test/719-dm-verify-redefinition/src/Main.java
index 37575b6fcf..241792f892 100644
--- a/test/719-dm-verify-redefinition/src/Main.java
+++ b/test/719-dm-verify-redefinition/src/Main.java
@@ -13,15 +13,9 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-import java.util.BitSet;
 
 public class Main {
   public static void main(String[] args) {
     System.out.println("Hello, world!");
-    if (BitSet.class.getClassLoader().equals(String.class.getClassLoader())) {
-      System.out.println("Correct resolution of boot class.");
-    } else {
-      System.out.println("Bogus resolution of boot class.");
-    }
   }
 }
diff --git a/test/719-dm-verify-redefinition/src/Redefined.java b/test/719-dm-verify-redefinition/src/Redefined.java
new file mode 100644
index 0000000000..cab7974bf0
--- /dev/null
+++ b/test/719-dm-verify-redefinition/src/Redefined.java
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2019 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 Redefined {
+}
diff --git a/test/VerifierDeps/SocketTimeoutException.smali b/test/VerifierDeps/SocketTimeoutException.smali
new file mode 100644
index 0000000000..c43790549f
--- /dev/null
+++ b/test/VerifierDeps/SocketTimeoutException.smali
@@ -0,0 +1,16 @@
+# Copyright (C) 2019 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 public Ljava/net/SocketTimeoutException;
+.super Ljava/lang/Object;
diff --git a/test/etc/run-test-jar b/test/etc/run-test-jar
index 9d79a0b99e..7ed12366a0 100755
--- a/test/etc/run-test-jar
+++ b/test/etc/run-test-jar
@@ -70,6 +70,7 @@ ZYGOTE=""
 DEX_VERIFY=""
 INSTRUCTION_SET_FEATURES=""
 ARGS=""
+VDEX_ARGS=""
 EXTERNAL_LOG_TAGS="n" # if y respect externally set ANDROID_LOG_TAGS.
 DRY_RUN="n" # if y prepare to run the test but don't run it.
 TEST_VDEX="n"
@@ -81,7 +82,6 @@ JVMTI_STEP_STRESS="n"
 JVMTI_FIELD_STRESS="n"
 JVMTI_TRACE_STRESS="n"
 JVMTI_REDEFINE_STRESS="n"
-VDEX_FILTER=""
 PROFILE="n"
 RANDOM_PROFILE="n"
 # The normal dex2oat timeout.
@@ -390,7 +390,11 @@ while true; do
     elif [ "x$1" = "x--vdex-filter" ]; then
         shift
         option="$1"
-        VDEX_FILTER="--compiler-filter=$option"
+        VDEX_ARGS="${VDEX_ARGS} --compiler-filter=$option"
+        shift
+    elif [ "x$1" = "x--vdex-arg" ]; then
+        shift
+        VDEX_ARGS="${VDEX_ARGS} $1"
         shift
     elif [ "x$1" = "x--sync" ]; then
         SYNC_BEFORE_RUN="y"
@@ -851,13 +855,13 @@ if [ "$PREBUILD" = "y" ]; then
     dex2oat_cmdline="timeout -k ${DEX2OAT_TIMEOUT}s -s SIGRTMIN+2 ${DEX2OAT_RT_TIMEOUT}s ${dex2oat_cmdline} --watchdog-timeout=${DEX2OAT_TIMEOUT}000"
   fi
   if [ "$PROFILE" = "y" ] || [ "$RANDOM_PROFILE" = "y" ]; then
-    vdex_cmdline="${dex2oat_cmdline} ${VDEX_FILTER} --input-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex --output-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex"
+    vdex_cmdline="${dex2oat_cmdline} ${VDEX_ARGS} --input-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex --output-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex"
   elif [ "$TEST_VDEX" = "y" ]; then
-    vdex_cmdline="${dex2oat_cmdline} ${VDEX_FILTER} --input-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex"
+    vdex_cmdline="${dex2oat_cmdline} ${VDEX_ARGS} --input-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex"
   elif [ "$TEST_DM" = "y" ]; then
     dex2oat_cmdline="${dex2oat_cmdline} --output-vdex=$DEX_LOCATION/oat/$ISA/primary.vdex"
     dm_cmdline="zip -qj $DEX_LOCATION/oat/$ISA/$TEST_NAME.dm $DEX_LOCATION/oat/$ISA/primary.vdex"
-    vdex_cmdline="${dex2oat_cmdline} --dump-timings --dm-file=$DEX_LOCATION/oat/$ISA/$TEST_NAME.dm"
+    vdex_cmdline="${dex2oat_cmdline} ${VDEX_ARGS} --dump-timings --dm-file=$DEX_LOCATION/oat/$ISA/$TEST_NAME.dm"
   elif [ "$PROFILE" = "y" ] || [ "$RANDOM_PROFILE" = "y" ]; then
     vdex_cmdline="${dex2oat_cmdline} --input-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex --output-vdex=$DEX_LOCATION/oat/$ISA/$TEST_NAME.vdex"
   fi