Calculates retaining paths through user fields and ignores VM objects

runtime/vm/object_graph.cc

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object_graph.h"
 
 #include "vm/dart.h"
 #include "vm/growable_array.h"
 #include "vm/isolate.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/raw_object.h"
 #include "vm/reusable_handles.h"
 #include "vm/visitor.h"
 
 namespace dart {
 
 // The state of a pre-order, depth-first traversal of an object graph.
 // When a node is visited, *all* its children are pushed to the stack at once.
 // We insert a sentinel between the node and its children on the stack, to
 // remember that the node has been visited. The node is kept on the stack while
 // its children are processed, to give the visitor a complete chain of parents.
 //
 // TODO(koda): Potential optimizations:
 // - Use tag bits for compact Node and sentinel representations.
 class ObjectGraph::Stack : public ObjectPointerVisitor {
  public:
   explicit Stack(Isolate* isolate)
-      : ObjectPointerVisitor(isolate), data_(kInitialCapacity) {}
+      : ObjectPointerVisitor(isolate),
+        include_vm_objects_(true),
+        data_(kInitialCapacity) {}
 
   // Marks and pushes. Used to initialize this stack with roots.
   virtual void VisitPointers(RawObject** first, RawObject** last) {
     for (RawObject** current = first; current <= last; ++current) {
       if ((*current)->IsHeapObject() && !(*current)->IsMarked()) {
+        if (!include_vm_objects_) {
+          intptr_t cid = (*current)->GetClassId();
+          if ((cid < kInstanceCid) && (cid != kContextCid) &&
+              (cid != kFieldCid)) {
+            continue;
+          }
+        }
         (*current)->SetMarkBit();
         Node node;
         node.ptr = current;
         node.obj = *current;
         data_.Add(node);
       }
     }
   }
 
   // Traverses the object graph from the current state.
@@ skipping 17 matching lines @@
           obj->VisitPointers(this);
           break;
         case ObjectGraph::Visitor::kBacktrack:
           break;
         case ObjectGraph::Visitor::kAbort:
           return;
       }
     }
   }
 
+  bool include_vm_objects_;
+
  private:
   struct Node {
     RawObject** ptr;  // kSentinel for the sentinel node.
     RawObject* obj;
   };
 
   static RawObject** const kSentinel;
   static const intptr_t kInitialCapacity = 1024;
   static const intptr_t kNoParent = -1;
 
@@ skipping 62 matching lines @@
 
   static void UnmarkAll(Isolate* isolate) {
     Unmarker unmarker;
     isolate->heap()->VisitObjectsNoImagePages(&unmarker);
   }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Unmarker);
 };
 
+static void IterateUserFields(ObjectPointerVisitor* visitor) {
+  Thread* thread = Thread::Current();
+  // Scope to prevent handles create here from appearing as stack references.
+  HANDLESCOPE(thread);
+  Zone* zone = thread->zone();
+  const GrowableObjectArray& libraries = GrowableObjectArray::Handle(
+      zone, thread->isolate()->object_store()->libraries());
+  Library& library = Library::Handle(zone);
+  Object& entry = Object::Handle(zone);
+  Class& cls = Class::Handle(zone);
+  Array& fields = Array::Handle(zone);
+  Field& field = Field::Handle(zone);
+  for (intptr_t i = 0; i < libraries.Length(); i++) {
+    library ^= libraries.At(i);
+    DictionaryIterator entries(library);
+    while (entries.HasNext()) {
+      entry = entries.GetNext();
+      if (entry.IsClass()) {
+        cls ^= entry.raw();
+        fields = cls.fields();
+        for (intptr_t j = 0; j < fields.Length(); j++) {
+          field ^= fields.At(j);
+          RawObject* ptr = field.raw();
+          visitor->VisitPointer(&ptr);
+        }
+      } else if (entry.IsField()) {
+        field ^= entry.raw();
+        RawObject* ptr = field.raw();
+        visitor->VisitPointer(&ptr);
+      }
+    }
+  }
+}
+
 ObjectGraph::ObjectGraph(Thread* thread) : StackResource(thread) {
   // The VM isolate has all its objects pre-marked, so iterating over it
   // would be a no-op.
   ASSERT(thread->isolate() != Dart::vm_isolate());
 }
 
 ObjectGraph::~ObjectGraph() {}
 
 void ObjectGraph::IterateObjects(ObjectGraph::Visitor* visitor) {
   NoSafepointScope no_safepoint_scope_;
   Stack stack(isolate());
   isolate()->VisitObjectPointers(&stack, false);
   stack.TraverseGraph(visitor);
   Unmarker::UnmarkAll(isolate());
 }
 
+void ObjectGraph::IterateUserObjects(ObjectGraph::Visitor* visitor) {
+  NoSafepointScope no_safepoint_scope_;
+  Stack stack(isolate());
+  IterateUserFields(&stack);
+  stack.include_vm_objects_ = false;
+  stack.TraverseGraph(visitor);
+  Unmarker::UnmarkAll(isolate());
+}
+
 void ObjectGraph::IterateObjectsFrom(const Object& root,
                                      ObjectGraph::Visitor* visitor) {
   NoSafepointScope no_safepoint_scope_;
   Stack stack(isolate());
   RawObject* root_raw = root.raw();
   stack.VisitPointer(&root_raw);
   stack.TraverseGraph(visitor);
   Unmarker::UnmarkAll(isolate());
 }
 
@@ skipping 190 matching lines @@
 };
 
 intptr_t ObjectGraph::RetainingPath(Object* obj, const Array& path) {
   NoSafepointScope no_safepoint_scope_;
   HeapIterationScope iteration_scope(true);
   // To break the trivial path, the handle 'obj' is temporarily cleared during
   // the search, but restored before returning.
   RawObject* raw = obj->raw();
   *obj = Object::null();
   RetainingPathVisitor visitor(raw, path);
-  IterateObjects(&visitor);
+  IterateUserObjects(&visitor);
+  if (visitor.length() == 0) {
+    IterateObjects(&visitor);
+  }
   *obj = raw;
   return visitor.length();
 }
 
 class InboundReferencesVisitor : public ObjectVisitor,
                                  public ObjectPointerVisitor {
  public:
   // We cannot use a GrowableObjectArray, since we must not trigger GC.
   InboundReferencesVisitor(Isolate* isolate,
                            RawObject* target,
@@ skipping 146 matching lines @@
 
   intptr_t count() const { return count_; }
 
  private:
   WriteStream* stream_;
   WritePointerVisitor ptr_writer_;
   ObjectGraph::SnapshotRoots roots_;
   intptr_t count_;
 };
 
-static void IterateUserFields(ObjectPointerVisitor* visitor) {
-  Thread* thread = Thread::Current();
-  // Scope to prevent handles create here from appearing as stack references.
-  HANDLESCOPE(thread);
-  Zone* zone = thread->zone();
-  const GrowableObjectArray& libraries = GrowableObjectArray::Handle(
-      zone, thread->isolate()->object_store()->libraries());
-  Library& library = Library::Handle(zone);
-  Object& entry = Object::Handle(zone);
-  Class& cls = Class::Handle(zone);
-  Array& fields = Array::Handle(zone);
-  Field& field = Field::Handle(zone);
-  for (intptr_t i = 0; i < libraries.Length(); i++) {
-    library ^= libraries.At(i);
-    DictionaryIterator entries(library);
-    while (entries.HasNext()) {
-      entry = entries.GetNext();
-      if (entry.IsClass()) {
-        cls ^= entry.raw();
-        fields = cls.fields();
-        for (intptr_t j = 0; j < fields.Length(); j++) {
-          field ^= fields.At(j);
-          RawObject* ptr = field.raw();
-          visitor->VisitPointer(&ptr);
-        }
-      } else if (entry.IsField()) {
-        field ^= entry.raw();
-        RawObject* ptr = field.raw();
-        visitor->VisitPointer(&ptr);
-      }
-    }
-  }
-}
-
 intptr_t ObjectGraph::Serialize(WriteStream* stream,
                                 SnapshotRoots roots,
                                 bool collect_garbage) {
   if (collect_garbage) {
     isolate()->heap()->CollectAllGarbage();
   }
   // Current encoding assumes objects do not move, so promote everything to old.
   isolate()->heap()->new_space()->Evacuate();
   HeapIterationScope iteration_scope(true);
 
@@ skipping 36 matching lines @@
   intptr_t object_count = visitor.count();
   if (roots == kVM) {
     object_count += 1;  // root
   } else {
     object_count += 2;  // root and stack
   }
   return object_count;
 }
 
 }  // namespace dart