Refactored PathTracer in heap.cc....

src/heap.h

 // Copyright 2010 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 12 matching lines @@
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 #ifndef V8_HEAP_H_
 #define V8_HEAP_H_
 
 #include <math.h>
 
+#include "list.h"
 #include "spaces.h"
 #include "splay-tree-inl.h"
 #include "v8-counters.h"
 
 namespace v8 {
 namespace internal {
 
 
 // Defines all the roots in Heap.
 #define UNCONDITIONAL_STRONG_ROOT_LIST(V)                                      \
@@ skipping 2102 matching lines @@
  public:
   virtual ~WeakObjectRetainer() {}
 
   // Return whether this object should be retained. If NULL is returned the
   // object has no references. Otherwise the address of the retained object
   // should be returned as in some GC situations the object has been moved.
   virtual Object* RetainAs(Object* object) = 0;
 };
 
 
+#if defined(DEBUG) || defined(LIVE_OBJECT_LIST)
+// Helper class for tracing paths to a search target Object from all roots.
+// The TracePathFrom() method can be used to trace paths from a specific
+// object to the search target object.
+//
+// The "what_to_find" can be kFindFirst or kFindAll.  If kFindFirst is
+// specified, tracing will stop after the first match.  If kFindAll is
+// specified, then tracing will be done for all matches.
+class PathTracer: public ObjectVisitor {

[marklam, 2011/02/20 00:41:15]

PathTracer used to be called MarkRootVisitor in heap.cc.

+ public:
+  PathTracer(Object* search_target,
+             bool search_for_any_global,
+             int what_to_find,
+             bool skip_weak_refs)
+      : search_target_(search_target),
+        search_for_any_global_(search_for_any_global),
+        found_target_(false),
+        what_to_find_(what_to_find),
+        skip_weak_refs_(skip_weak_refs),
+        object_stack_(20),
+        mark_visitor(this),
+        unmark_visitor(this) {}
+
+  void VisitPointers(Object** start, Object** end) {
+    bool done = false;
+    // Visit all HeapObject pointers in [start, end)
+    for (Object** p = start; !done && (p < end); p++) {
+      if ((*p)->IsHeapObject()) {
+        TracePathFrom(p);
+        done = ((what_to_find_ == kFindFirst) && found_target_);

[marklam, 2011/02/20 00:41:15]

I added an optimization to bail here if we've already found what we want.

+      }
+    }
+  }
+
+  void TracePathFrom(Object** root);

[marklam, 2011/02/20 00:41:15]

TracePathFrom() used to be called MarkRootObjectRecursively() in heap.cc.

+
+  bool found() const { return found_target_; }
+
+  // Values for the "what_to_find" argument of the constructor.
+  static const int kFindFirst = 1;  // Will stop the search after first match.
+  static const int kFindAll = 0;  // Will find all matches.
+
+ protected:
+  class MarkVisitor: public ObjectVisitor {

[marklam, 2011/02/20 00:41:15]

MarkVisitor used to be called MarkObjectVisitor in heap.cc.

+   public:
+    explicit MarkVisitor(PathTracer* tracer) : tracer_(tracer) {}
+    void VisitPointers(Object** start, Object** end) {
+      // Scan all HeapObject pointers in [start, end)
+      for (Object** p = start; !tracer_->found() && (p < end); p++) {

[marklam, 2011/02/20 00:41:15]

The check for !tracer->found() is an optimization that allows us to bail from
the loop if we've already found the target.  Otherwise, it would call
MarkRecursively() (previously MarkObjectRecursively()) which does returns and
does nothing if the target is found anyway.  So, there is no semantic change
here.

+        if ((*p)->IsHeapObject())
+          tracer_->MarkRecursively(p);
+      }
+    }
+
+   private:
+    PathTracer* tracer_;
+  };
+
+
+  class UnmarkVisitor: public ObjectVisitor {

[marklam, 2011/02/20 00:41:15]

UnmarkVisitor used to be called UnmarkObjectVisitor in heap.cc.

+   public:
+    explicit UnmarkVisitor(PathTracer* tracer) : tracer_(tracer) {}
+    void VisitPointers(Object** start, Object** end) {
+      // Scan all HeapObject pointers in [start, end)
+      for (Object** p = start; p < end; p++) {
+        if ((*p)->IsHeapObject())
+          tracer_->UnmarkRecursively(p);
+      }
+    }
+
+   private:
+    PathTracer* tracer_;
+  };
+
+  PathTracer();
+
+  void MarkRecursively(Object** p);

[marklam, 2011/02/20 00:41:15]

MarkRecursively() used to be called MarkObjectRecursively() in heap.cc.

+  void UnmarkRecursively(Object** p);

[marklam, 2011/02/20 00:41:15]

UnmarkRecursively() used to be called UnmarkObjectRecursively() in heap.cc.

+  virtual void ProcessResults();
+
+  // Tags 0, 1, and 3 are used. Use 2 for marking visited HeapObject.
+  static const int kMarkTag = 2;
+
+  Object* search_target_;
+  bool search_for_any_global_;
+  bool found_target_;
+  bool what_to_find_;
+  bool skip_weak_refs_;
+  List<Object*> object_stack_;

[marklam, 2011/02/20 00:41:15]

search_target_, search_for_any_global_, found_target_, and object_stack_ used to
be global statics.  I've encapsulated them in the tracer object now.

+
+  MarkVisitor mark_visitor;
+  UnmarkVisitor unmark_visitor;

[marklam, 2011/02/20 00:41:15]

There used to be global static instances of these 2 visitors in heap.cc too. 
Now, their lifecycle is bound to the tracer's. 

+};
+#endif  // DEBUG || LIVE_OBJECT_LIST
+
+
 } }  // namespace v8::internal
 
 #endif  // V8_HEAP_H_