Add FirstPathFromRootSet and use it to debug reachability issues

Specifically issues where classes aren't pruned in image writer.

Added test.

Test: mm test-art-host-gtest-heap_verification_test -j32

Change-Id: Iea87309aaddf9e28f1856698699a925fb6ab92a1

4 files changed, 119 insertions, 3 deletions

diff --git a/compiler/image_writer.cc b/compiler/image_writer.cc
index 406892e499..a8fdecaa4a 100644
--- a/compiler/image_writer.cc
+++ b/compiler/image_writer.cc
@@ -46,7 +46,9 @@
 #include "gc/heap.h"
 #include "gc/space/large_object_space.h"
 #include "gc/space/space-inl.h"
+#include "gc/verification.h"
 #include "globals.h"
+#include "handle_scope-inl.h"
 #include "image.h"
 #include "imt_conflict_table.h"
 #include "jni_internal.h"
@@ -69,7 +71,6 @@
 #include "oat_file_manager.h"
 #include "runtime.h"
 #include "scoped_thread_state_change-inl.h"
-#include "handle_scope-inl.h"
 #include "utils/dex_cache_arrays_layout-inl.h"
 
 using ::art::mirror::Class;
@@ -1094,8 +1095,8 @@ void ImageWriter::CheckNonImageClassesRemovedCallback(Object* obj, void* arg) {
     if (!image_writer->KeepClass(klass)) {
       image_writer->DumpImageClasses();
       std::string temp;
-      CHECK(image_writer->KeepClass(klass)) << klass->GetDescriptor(&temp)
-                                            << " " << klass->PrettyDescriptor();
+      CHECK(image_writer->KeepClass(klass))
+          << Runtime::Current()->GetHeap()->GetVerification()->FirstPathFromRootSet(klass);
     }
   }
 }
diff --git a/runtime/gc/heap_verification_test.cc b/runtime/gc/heap_verification_test.cc
index a307c519cb..8ea0459c89 100644
--- a/runtime/gc/heap_verification_test.cc
+++ b/runtime/gc/heap_verification_test.cc
@@ -141,5 +141,24 @@ TEST_F(VerificationTest, LogHeapCorruption) {
   v->LogHeapCorruption(nullptr, MemberOffset(0), arr.Get(), false);
 }
 
+TEST_F(VerificationTest, FindPathFromRootSet) {
+  TEST_DISABLED_FOR_MEMORY_TOOL();
+  ScopedLogSeverity sls(LogSeverity::INFO);
+  ScopedObjectAccess soa(Thread::Current());
+  Runtime* const runtime = Runtime::Current();
+  VariableSizedHandleScope hs(soa.Self());
+  Handle<mirror::ObjectArray<mirror::Object>> arr(
+      hs.NewHandle(AllocObjectArray<mirror::Object>(soa.Self(), 256)));
+  ObjPtr<mirror::String> str = mirror::String::AllocFromModifiedUtf8(soa.Self(), "obj");
+  arr->Set(0, str);
+  const Verification* const v = runtime->GetHeap()->GetVerification();
+  std::string path = v->FirstPathFromRootSet(str);
+  EXPECT_GT(path.length(), 0u);
+  std::ostringstream oss;
+  oss << arr.Get();
+  EXPECT_NE(path.find(oss.str()), std::string::npos);
+  LOG(INFO) << path;
+}
+
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/verification.cc b/runtime/gc/verification.cc
index c14f250528..03b26a0a6b 100644
--- a/runtime/gc/verification.cc
+++ b/runtime/gc/verification.cc
@@ -21,6 +21,7 @@
 
 #include "art_field-inl.h"
 #include "mirror/class-inl.h"
+#include "mirror/object-refvisitor-inl.h"
 
 namespace art {
 namespace gc {
@@ -138,5 +139,92 @@ bool Verification::IsValidClass(const void* addr) const {
   return k1 == k2;
 }
 
+using ObjectSet = std::set<mirror::Object*>;
+using WorkQueue = std::deque<std::pair<mirror::Object*, std::string>>;
+
+// Use for visiting the GcRoots held live by ArtFields, ArtMethods, and ClassLoaders.
+class Verification::BFSFindReachable {
+ public:
+  explicit BFSFindReachable(ObjectSet* visited) : visited_(visited) {}
+
+  void operator()(mirror::Object* obj, MemberOffset offset, bool is_static ATTRIBUTE_UNUSED) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    ArtField* field = obj->FindFieldByOffset(offset);
+    Visit(obj->GetFieldObject<mirror::Object>(offset),
+          field != nullptr ? field->GetName() : "");
+  }
+
+  void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (!root->IsNull()) {
+      VisitRoot(root);
+    }
+  }
+
+  void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    Visit(root->AsMirrorPtr(), "!nativeRoot");
+  }
+
+  void Visit(mirror::Object* ref, const std::string& field_name) const
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (ref != nullptr && visited_->insert(ref).second) {
+      new_visited_.emplace_back(ref, field_name);
+    }
+  }
+
+  const WorkQueue& NewlyVisited() const {
+    return new_visited_;
+  }
+
+ private:
+  ObjectSet* visited_;
+  mutable WorkQueue new_visited_;
+};
+
+class Verification::CollectRootVisitor : public SingleRootVisitor {
+ public:
+  CollectRootVisitor(ObjectSet* visited, WorkQueue* work) : visited_(visited), work_(work) {}
+
+  void VisitRoot(mirror::Object* obj, const RootInfo& info)
+      OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) {
+    if (obj != nullptr && visited_->insert(obj).second) {
+      std::ostringstream oss;
+      oss << info.ToString() << " = " << obj << "(" << obj->PrettyTypeOf() << ")";
+      work_->emplace_back(obj, oss.str());
+    }
+  }
+
+ private:
+  ObjectSet* const visited_;
+  WorkQueue* const work_;
+};
+
+std::string Verification::FirstPathFromRootSet(ObjPtr<mirror::Object> target) const {
+  Runtime* const runtime =  Runtime::Current();
+  std::set<mirror::Object*> visited;
+  std::deque<std::pair<mirror::Object*, std::string>> work;
+  {
+    CollectRootVisitor root_visitor(&visited, &work);
+    runtime->VisitRoots(&root_visitor, kVisitRootFlagAllRoots);
+  }
+  while (!work.empty()) {
+    auto pair = work.front();
+    work.pop_front();
+    if (pair.first == target) {
+      return pair.second;
+    }
+    BFSFindReachable visitor(&visited);
+    pair.first->VisitReferences(visitor, VoidFunctor());
+    for (auto&& pair2 : visitor.NewlyVisited()) {
+      std::ostringstream oss;
+      mirror::Object* obj = pair2.first;
+      oss << pair.second << " -> " << obj << "(" << obj->PrettyTypeOf() << ")." << pair2.second;
+      work.emplace_back(obj, oss.str());
+    }
+  }
+  return "<no path found>";
+}
+
 }  // namespace gc
 }  // namespace art
diff --git a/runtime/gc/verification.h b/runtime/gc/verification.h
index 3d95d93015..903e159c5a 100644
--- a/runtime/gc/verification.h
+++ b/runtime/gc/verification.h
@@ -57,8 +57,16 @@ class Verification {
   bool IsValidHeapObjectAddress(const void* addr, space::Space** out_space = nullptr) const
       REQUIRES_SHARED(Locks::mutator_lock_);
 
+  // Find the first path to the target from the root set. Should be called while paused since
+  // visiting roots is not safe otherwise.
+  std::string FirstPathFromRootSet(ObjPtr<mirror::Object> target) const
+      REQUIRES_SHARED(Locks::mutator_lock_);
+
  private:
   gc::Heap* const heap_;
+
+  class BFSFindReachable;
+  class CollectRootVisitor;
 };
 
 }  // namespace gc