Include parent field/list index in retaining path.

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/raw_object.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:
-// - Linked chunks instead of std::vector.
-// - Use smi/heap tag bit instead of full-word sentinel.
-// - Extend RawObject with incremental iteration (one child at a time).
+// - Use tag bits for compact Node and sentinel representations.
 class ObjectGraph::Stack : public ObjectPointerVisitor {
  public:
   explicit Stack(Isolate* isolate)
       : ObjectPointerVisitor(isolate), 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()) {
         (*current)->SetMarkBit();
-        data_.Add(*current);
+        Node node;
+        node.ptr = current;
+        node.obj = *current;
+        data_.Add(node);
       }
     }
   }
 
   // Traverses the object graph from the current state.
   void TraverseGraph(ObjectGraph::Visitor* visitor) {
     while (!data_.is_empty()) {
-      RawObject* obj = data_.Last();
-      if (obj == kSentinel) {
+      Node node = data_.Last();
+      if (node.ptr == kSentinel) {
         data_.RemoveLast();
         // The node below the sentinel has already been visited.
         data_.RemoveLast();
         continue;
       }
+      RawObject* obj = node.obj;
       ASSERT(obj->IsHeapObject());
-      data_.Add(kSentinel);
+      Node sentinel;
+      sentinel.ptr = kSentinel;
+      data_.Add(sentinel);
       StackIterator it(this, data_.length() - 2);
       switch (visitor->VisitObject(&it)) {
         case ObjectGraph::Visitor::kProceed:
           obj->VisitPointers(this);
           break;
         case ObjectGraph::Visitor::kBacktrack:
           break;
         case ObjectGraph::Visitor::kAbort:
           return;
       }
     }
   }
 
  private:
-  static RawObject* const kSentinel;
+  struct Node {
+    RawObject** ptr;  // kSentinel for the sentinel node.
+    RawObject* obj;
+  };
+
+  static RawObject** const kSentinel;
   static const intptr_t kInitialCapacity = 1024;
-  GrowableArray<RawObject*> data_;
+  static const intptr_t kNoParent = -1;
+
+  intptr_t Parent(intptr_t index) const {
+    // The parent is just below the next sentinel.
+    for (intptr_t i = index; i >= 1; --i) {
+      if (data_[i].ptr == kSentinel) {
+        return i - 1;
+      }
+    }
+    return kNoParent;
+  }
+
+  GrowableArray<Node> data_;
   friend class StackIterator;
   DISALLOW_COPY_AND_ASSIGN(Stack);
 };
 
 
-// We only visit heap objects, so any Smi works as the sentinel.
-RawObject* const ObjectGraph::Stack::kSentinel = Smi::New(0);
+RawObject** const ObjectGraph::Stack::kSentinel = NULL;
 
 
 RawObject* ObjectGraph::StackIterator::Get() const {
-  return stack_->data_[index_];
+  return stack_->data_[index_].obj;
 }
 
 
 bool ObjectGraph::StackIterator::MoveToParent() {
-  // The parent is just below the next sentinel.
-  for (int i = index_; i >= 1; --i) {
-    if (stack_->data_[i] == Stack::kSentinel) {
-      index_ = i - 1;
-      return true;
-    }
+  intptr_t parent = stack_->Parent(index_);
+  if (parent == Stack::kNoParent) {
+    return false;
+  } else {
+    index_ = parent;
+    return true;
   }
-  return false;
+}
+
+
+intptr_t ObjectGraph::StackIterator::OffsetFromParentInWords() const {
+  intptr_t parent_index = stack_->Parent(index_);
+  if (parent_index == Stack::kNoParent) {
+    return -1;
+  }
+  Stack::Node parent = stack_->data_[parent_index];
+  uword parent_start = RawObject::ToAddr(parent.obj);
+  Stack::Node child = stack_->data_[index_];
+  ASSERT(child.obj == *child.ptr);
+  uword child_ptr_addr = reinterpret_cast<uword>(child.ptr);
+  intptr_t offset = child_ptr_addr - parent_start;
+  if (offset > 0 && offset < parent.obj->Size()) {
+    ASSERT(Utils::IsAligned(offset, kWordSize));
+    return offset >> kWordSizeLog2;
+  } else {
+    // Some internal VM objects visit pointers not contained within the parent.
+    // For instance, RawCode::VisitCodePointers visits pointers in instructions.
+    ASSERT(!parent.obj->IsDartInstance());
+    return -1;
+  }
 }
 
 
 class Unmarker : public ObjectVisitor {
  public:
   explicit Unmarker(Isolate* isolate) : ObjectVisitor(isolate) { }
 
   void VisitObject(RawObject* obj) {
     if (obj->IsMarked()) {
       obj->ClearMarkBit();
@@ skipping 114 matching lines @@
   }
 
   intptr_t length() const { return length_; }
 
   virtual Direction VisitObject(ObjectGraph::StackIterator* it) {
     if (it->Get() != obj_) {
       return kProceed;
     } else {
       HANDLESCOPE(Isolate::Current());
       Object& current = Object::Handle();
+      Smi& offset_from_parent = Smi::Handle();
       do {
-        if (!path_.IsNull() && length_ < path_.Length()) {
+        intptr_t obj_index = length_ * 2;
+        intptr_t offset_index = obj_index + 1;
+        if (!path_.IsNull() && offset_index < path_.Length()) {
           current = it->Get();
-          path_.SetAt(length_, current);
+          path_.SetAt(obj_index, current);
+          offset_from_parent = Smi::New(it->OffsetFromParentInWords());
+          path_.SetAt(offset_index, offset_from_parent);
         }
         ++length_;
       } while (it->MoveToParent());
       return kAbort;
     }
   }
 
  private:
   RawObject* obj_;
   const Array& path_;
   intptr_t length_;
 };
 
 
 intptr_t ObjectGraph::RetainingPath(Object* obj, const Array& path) {
   NoGCScope no_gc_scope_;
   // 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);
   *obj = raw;
   return visitor.length();
 }
 
 }  // namespace dart