Version 2.5.8...

src/profile-generator.cc

 // 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 811 matching lines @@
       *entry++ = EntryForVMState(sample.state);
     }
   }
 
   profiles_->AddPathToCurrentProfiles(entries);
 }
 
 
 void HeapGraphEdge::Init(
     int child_index, Type type, const char* name, HeapEntry* to) {
-  ASSERT(type == kContextVariable || type == kProperty || type == kInternal);
+  ASSERT(type == kContextVariable
+         || type == kProperty
+         || type == kInternal
+         || type == kShortcut);
   child_index_ = child_index;
   type_ = type;
   name_ = name;
   to_ = to;
 }
 
 
+void HeapGraphEdge::Init(int child_index, Type type, int index, HeapEntry* to) {
+  ASSERT(type == kElement || type == kHidden);
+  child_index_ = child_index;
+  type_ = type;
+  index_ = index;
+  to_ = to;
+}
+
+
 void HeapGraphEdge::Init(int child_index, int index, HeapEntry* to) {
-  child_index_ = child_index;
-  type_ = kElement;
-  index_ = index;
-  to_ = to;
+  Init(child_index, kElement, index, to);
 }
 
 
 HeapEntry* HeapGraphEdge::From() {
   return reinterpret_cast<HeapEntry*>(this - child_index_) - 1;
 }
 
 
 void HeapEntry::Init(HeapSnapshot* snapshot,
                      Type type,
                      const char* name,
                      uint64_t id,
                      int self_size,
                      int children_count,
                      int retainers_count) {
   snapshot_ = snapshot;
   type_ = type;
   painted_ = kUnpainted;
-  calculated_data_index_ = kNoCalculatedData;
   name_ = name;
-  id_ = id;
   self_size_ = self_size;
+  retained_size_ = 0;
   children_count_ = children_count;
   retainers_count_ = retainers_count;
+  dominator_ = NULL;
+
+  union {
+    uint64_t set_id;
+    Id stored_id;
+  } id_adaptor = {id};
+  id_ = id_adaptor.stored_id;
 }
 
 
 void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,
                                   int child_index,
                                   const char* name,
                                   HeapEntry* entry,
                                   int retainer_index) {
   children_arr()[child_index].Init(child_index, type, name, entry);
   entry->retainers_arr()[retainer_index] = children_arr() + child_index;
 }
 
 
-void HeapEntry::SetElementReference(
-    int child_index, int index, HeapEntry* entry, int retainer_index) {
-  children_arr()[child_index].Init(child_index, index, entry);
+void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,
+                                    int child_index,
+                                    int index,
+                                    HeapEntry* entry,
+                                    int retainer_index) {
+  children_arr()[child_index].Init(child_index, type, index, entry);
   entry->retainers_arr()[retainer_index] = children_arr() + child_index;
 }
 
 
 void HeapEntry::SetUnidirElementReference(
     int child_index, int index, HeapEntry* entry) {
   children_arr()[child_index].Init(child_index, index, entry);
 }
 
 
-int HeapEntry::ReachableSize() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
+int HeapEntry::RetainedSize(bool exact) {
+  if (exact && (retained_size_ & kExactRetainedSizeTag) == 0) {
+    CalculateExactRetainedSize();
   }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).ReachableSize(this);
-}
-
-
-int HeapEntry::RetainedSize() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
-  }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).RetainedSize(this);
+  return retained_size_ & (~kExactRetainedSizeTag);
 }
 
 
 List<HeapGraphPath*>* HeapEntry::GetRetainingPaths() {
-  if (calculated_data_index_ == kNoCalculatedData) {
-    calculated_data_index_ = snapshot_->AddCalculatedData();
-  }
-  return snapshot_->GetCalculatedData(
-      calculated_data_index_).GetRetainingPaths(this);
+  return snapshot_->GetRetainingPaths(this);
 }
 
 
 template<class Visitor>
 void HeapEntry::ApplyAndPaintAllReachable(Visitor* visitor) {
   List<HeapEntry*> list(10);
   list.Add(this);
   this->paint_reachable();
   visitor->Apply(this);
   while (!list.is_empty()) {
     HeapEntry* entry = list.RemoveLast();
     Vector<HeapGraphEdge> children = entry->children();
     for (int i = 0; i < children.length(); ++i) {
+      if (children[i].type() == HeapGraphEdge::kShortcut) continue;
       HeapEntry* child = children[i].to();
       if (!child->painted_reachable()) {
         list.Add(child);
         child->paint_reachable();
         visitor->Apply(child);
       }
     }
   }
 }
 
 
 class NullClass {
  public:
   void Apply(HeapEntry* entry) { }
 };
 
 void HeapEntry::PaintAllReachable() {
   NullClass null;
   ApplyAndPaintAllReachable(&null);
 }
 
 
 void HeapEntry::Print(int max_depth, int indent) {
-  OS::Print("%6d %6d %6d [%llu] ",
-            self_size(), ReachableSize(), RetainedSize(), id_);
+  OS::Print("%6d %6d [%llu] ", self_size(), RetainedSize(false), id());
   if (type() != kString) {
     OS::Print("%s %.40s\n", TypeAsString(), name_);
   } else {
     OS::Print("\"");
     const char* c = name_;
     while (*c && (c - name_) <= 40) {
       if (*c != '\n')
         OS::Print("%c", *c);
       else
         OS::Print("\\n");
@@ skipping 11 matching lines @@
         break;
       case HeapGraphEdge::kElement:
         OS::Print("  %*c %d: ", indent, ' ', edge.index());
         break;
       case HeapGraphEdge::kInternal:
         OS::Print("  %*c $%s: ", indent, ' ', edge.name());
         break;
       case HeapGraphEdge::kProperty:
         OS::Print("  %*c %s: ", indent, ' ', edge.name());
         break;
+      case HeapGraphEdge::kHidden:
+        OS::Print("  %*c $%d: ", indent, ' ', edge.index());
+        break;
+      case HeapGraphEdge::kShortcut:
+        OS::Print("  %*c ^%s: ", indent, ' ', edge.name());
+        break;
       default:
         OS::Print("!!! unknown edge type: %d ", edge.type());
     }
     edge.to()->Print(max_depth, indent + 2);
   }
 }
 
 
 const char* HeapEntry::TypeAsString() {
   switch (type()) {
-    case kInternal: return "/internal/";
+    case kHidden: return "/hidden/";
     case kObject: return "/object/";
     case kClosure: return "/closure/";
     case kString: return "/string/";
     case kCode: return "/code/";
     case kArray: return "/array/";
     case kRegExp: return "/regexp/";
     case kHeapNumber: return "/number/";
     default: return "???";
   }
 }
 
 
 int HeapEntry::EntriesSize(int entries_count,
                            int children_count,
                            int retainers_count) {
   return sizeof(HeapEntry) * entries_count         // NOLINT
       + sizeof(HeapGraphEdge) * children_count     // NOLINT
       + sizeof(HeapGraphEdge*) * retainers_count;  // NOLINT
 }
 
 
-static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
-  delete *path_ptr;
-}
-
-void HeapEntryCalculatedData::Dispose() {
-  if (retaining_paths_ != NULL) retaining_paths_->Iterate(DeleteHeapGraphPath);
-  delete retaining_paths_;
-}
-
-
-int HeapEntryCalculatedData::ReachableSize(HeapEntry* entry) {
-  if (reachable_size_ == kUnknownSize) CalculateSizes(entry);
-  return reachable_size_;
-}
-
-
-int HeapEntryCalculatedData::RetainedSize(HeapEntry* entry) {
-  if (retained_size_ == kUnknownSize) CalculateSizes(entry);
-  return retained_size_;
-}
-
-
-class ReachableSizeCalculator {
- public:
-  ReachableSizeCalculator()
-      : reachable_size_(0) {
-  }
-
-  int reachable_size() const { return reachable_size_; }
-
-  void Apply(HeapEntry* entry) {
-    reachable_size_ += entry->self_size();
-  }
-
- private:
-  int reachable_size_;
-};
-
 class RetainedSizeCalculator {
  public:
   RetainedSizeCalculator()
       : retained_size_(0) {
   }
 
   int reained_size() const { return retained_size_; }
 
   void Apply(HeapEntry** entry_ptr) {
     if ((*entry_ptr)->painted_reachable()) {
       retained_size_ += (*entry_ptr)->self_size();
     }
   }
 
  private:
   int retained_size_;
 };
 
-void HeapEntryCalculatedData::CalculateSizes(HeapEntry* entry) {
+void HeapEntry::CalculateExactRetainedSize() {
   // To calculate retained size, first we paint all reachable nodes in
-  // one color (and calculate reachable size as a byproduct), then we
-  // paint (or re-paint) all nodes reachable from other nodes with a
-  // different color. Then we consider only nodes painted with the
-  // first color for calculating the retained size.
-  entry->snapshot()->ClearPaint();
-  ReachableSizeCalculator rch_size_calc;
-  entry->ApplyAndPaintAllReachable(&rch_size_calc);
-  reachable_size_ = rch_size_calc.reachable_size();
+  // one color, then we paint (or re-paint) all nodes reachable from
+  // other nodes with a different color. Then we sum up self sizes of
+  // nodes painted with the first color.
+  snapshot()->ClearPaint();
+  PaintAllReachable();
 
   List<HeapEntry*> list(10);
-  HeapEntry* root = entry->snapshot()->root();
-  if (entry != root) {
+  HeapEntry* root = snapshot()->root();
+  if (this != root) {
     list.Add(root);
     root->paint_reachable_from_others();
   }
   while (!list.is_empty()) {
     HeapEntry* curr = list.RemoveLast();
     Vector<HeapGraphEdge> children = curr->children();
     for (int i = 0; i < children.length(); ++i) {
+      if (children[i].type() == HeapGraphEdge::kShortcut) continue;
       HeapEntry* child = children[i].to();
-      if (child != entry && child->not_painted_reachable_from_others()) {
+      if (child != this && child->not_painted_reachable_from_others()) {
         list.Add(child);
         child->paint_reachable_from_others();
       }
     }
   }
 
   RetainedSizeCalculator ret_size_calc;
-  entry->snapshot()->IterateEntries(&ret_size_calc);
+  snapshot()->IterateEntries(&ret_size_calc);
   retained_size_ = ret_size_calc.reained_size();
+  ASSERT((retained_size_ & kExactRetainedSizeTag) == 0);
+  retained_size_ |= kExactRetainedSizeTag;
 }
 
 
 class CachedHeapGraphPath {
  public:
   CachedHeapGraphPath()
       : nodes_(NodesMatch) { }
   CachedHeapGraphPath(const CachedHeapGraphPath& src)
       : nodes_(NodesMatch, &HashMap::DefaultAllocator, src.nodes_.capacity()),
         path_(src.path_.length() + 1) {
@@ skipping 17 matching lines @@
   static uint32_t Hash(HeapEntry* entry) {
     return static_cast<uint32_t>(reinterpret_cast<intptr_t>(entry));
   }
   static bool NodesMatch(void* key1, void* key2) { return key1 == key2; }
 
   HashMap nodes_;
   List<HeapGraphEdge*> path_;
 };
 
 
-List<HeapGraphPath*>* HeapEntryCalculatedData::GetRetainingPaths(
-    HeapEntry* entry) {
-  if (retaining_paths_ == NULL) retaining_paths_ = new List<HeapGraphPath*>(4);
-  if (retaining_paths_->length() == 0 && entry->retainers().length() != 0) {
-    CachedHeapGraphPath path;
-    FindRetainingPaths(entry, &path);
-  }
-  return retaining_paths_;
+List<HeapGraphPath*>* HeapEntry::CalculateRetainingPaths() {
+  List<HeapGraphPath*>* retaining_paths = new List<HeapGraphPath*>(4);
+  CachedHeapGraphPath path;
+  FindRetainingPaths(&path, retaining_paths);
+  return retaining_paths;
 }
 
 
-void HeapEntryCalculatedData::FindRetainingPaths(
-    HeapEntry* entry,
-    CachedHeapGraphPath* prev_path) {
-  Vector<HeapGraphEdge*> retainers = entry->retainers();
-  for (int i = 0; i < retainers.length(); ++i) {
-    HeapGraphEdge* ret_edge = retainers[i];
+void HeapEntry::FindRetainingPaths(CachedHeapGraphPath* prev_path,
+                                   List<HeapGraphPath*>* retaining_paths) {
+  Vector<HeapGraphEdge*> rets = retainers();
+  for (int i = 0; i < rets.length(); ++i) {
+    HeapGraphEdge* ret_edge = rets[i];
     if (prev_path->ContainsNode(ret_edge->From())) continue;
-    if (ret_edge->From() != entry->snapshot()->root()) {
+    if (ret_edge->From() != snapshot()->root()) {
       CachedHeapGraphPath path(*prev_path);
       path.Add(ret_edge);
-      FindRetainingPaths(ret_edge->From(), &path);
+      ret_edge->From()->FindRetainingPaths(&path, retaining_paths);
     } else {
       HeapGraphPath* ret_path = new HeapGraphPath(*prev_path->path());
       ret_path->Set(0, ret_edge);
-      retaining_paths_->Add(ret_path);
+      retaining_paths->Add(ret_path);
     }
   }
 }
 
 
 HeapGraphPath::HeapGraphPath(const List<HeapGraphEdge*>& path)
     : path_(path.length() + 1) {
   Add(NULL);
   for (int i = path.length() - 1; i >= 0; --i) {
     Add(path[i]);
   }
 }
 
 
 void HeapGraphPath::Print() {
   path_[0]->From()->Print(1, 0);
   for (int i = 0; i < path_.length(); ++i) {
     OS::Print(" -> ");
     HeapGraphEdge* edge = path_[i];
     switch (edge->type()) {
       case HeapGraphEdge::kContextVariable:
         OS::Print("[#%s] ", edge->name());
         break;
       case HeapGraphEdge::kElement:
+      case HeapGraphEdge::kHidden:
         OS::Print("[%d] ", edge->index());
         break;
       case HeapGraphEdge::kInternal:
         OS::Print("[$%s] ", edge->name());
         break;
       case HeapGraphEdge::kProperty:
         OS::Print("[%s] ", edge->name());
         break;
+      case HeapGraphEdge::kShortcut:
+        OS::Print("[^%s] ", edge->name());
+        break;
       default:
         OS::Print("!!! unknown edge type: %d ", edge->type());
     }
     edge->to()->Print(1, 0);
   }
   OS::Print("\n");
 }
 
 
 HeapObject *const HeapSnapshot::kInternalRootObject =
     reinterpret_cast<HeapObject*>(1);
+HeapObject *const HeapSnapshot::kGcRootsObject =
+    reinterpret_cast<HeapObject*>(2);
 
 
 // It is very important to keep objects that form a heap snapshot
 // as small as possible.
 namespace {  // Avoid littering the global namespace.
 
 template <size_t ptr_size> struct SnapshotSizeConstants;
 
 template <> struct SnapshotSizeConstants<4> {
   static const int kExpectedHeapGraphEdgeSize = 12;
-  static const int kExpectedHeapEntrySize = 32;
+  static const int kExpectedHeapEntrySize = 36;
 };
 
 template <> struct SnapshotSizeConstants<8> {
   static const int kExpectedHeapGraphEdgeSize = 24;
-  static const int kExpectedHeapEntrySize = 40;
+  static const int kExpectedHeapEntrySize = 48;
 };
 
 }  // namespace
 
 HeapSnapshot::HeapSnapshot(HeapSnapshotsCollection* collection,
                            HeapSnapshot::Type type,
                            const char* title,
                            unsigned uid)
     : collection_(collection),
       type_(type),
       title_(title),
       uid_(uid),
       root_entry_(NULL),
+      gc_roots_entry_(NULL),
       raw_entries_(NULL),
-      entries_sorted_(false) {
+      entries_sorted_(false),
+      retaining_paths_(HeapEntry::Match) {
   STATIC_ASSERT(
       sizeof(HeapGraphEdge) ==
       SnapshotSizeConstants<sizeof(void*)>::kExpectedHeapGraphEdgeSize);  // NOLINT
   STATIC_ASSERT(
       sizeof(HeapEntry) ==
       SnapshotSizeConstants<sizeof(void*)>::kExpectedHeapEntrySize);  // NOLINT
 }
 
 
-static void DisposeCalculatedData(HeapEntryCalculatedData* cdata) {
-  cdata->Dispose();
+static void DeleteHeapGraphPath(HeapGraphPath** path_ptr) {
+  delete *path_ptr;
 }
 
 HeapSnapshot::~HeapSnapshot() {
   DeleteArray(raw_entries_);
-  calculated_data_.Iterate(DisposeCalculatedData);
+  for (HashMap::Entry* p = retaining_paths_.Start();
+       p != NULL;
+       p = retaining_paths_.Next(p)) {
+    List<HeapGraphPath*>* list =
+        reinterpret_cast<List<HeapGraphPath*>*>(p->value);
+    list->Iterate(DeleteHeapGraphPath);
+    delete list;
+  }
 }
 
 
 void HeapSnapshot::AllocateEntries(int entries_count,
                                    int children_count,
                                    int retainers_count) {
   ASSERT(raw_entries_ == NULL);
   raw_entries_ = NewArray<char>(
       HeapEntry::EntriesSize(entries_count, children_count, retainers_count));
 #ifdef DEBUG
   raw_entries_size_ =
       HeapEntry::EntriesSize(entries_count, children_count, retainers_count);
 #endif
 }
 
 
 HeapEntry* HeapSnapshot::AddEntry(HeapObject* object,
                                   int children_count,
                                   int retainers_count) {
   if (object == kInternalRootObject) {
     ASSERT(root_entry_ == NULL);
     ASSERT(retainers_count == 0);
-    root_entry_ = AddEntry(
-        HeapEntry::kInternal, "", 0, 0, children_count, retainers_count);
-    return root_entry_;
+    return (root_entry_ = AddEntry(HeapEntry::kObject,
+                                   "",
+                                   HeapObjectsMap::kInternalRootObjectId,
+                                   0,
+                                   children_count,
+                                   retainers_count));
+  } else if (object == kGcRootsObject) {
+    ASSERT(gc_roots_entry_ == NULL);
+    return (gc_roots_entry_ = AddEntry(HeapEntry::kObject,
+                                       "(GC roots)",
+                                       HeapObjectsMap::kGcRootsObjectId,
+                                       0,
+                                       children_count,
+                                       retainers_count));
   } else if (object->IsJSFunction()) {
     JSFunction* func = JSFunction::cast(object);
     SharedFunctionInfo* shared = func->shared();
     return AddEntry(object,
                     HeapEntry::kClosure,
                     collection_->GetName(String::cast(shared->name())),
                     children_count,
                     retainers_count);
   } else if (object->IsJSRegExp()) {
     JSRegExp* re = JSRegExp::cast(object);
@@ skipping 42 matching lines @@
                     "",
                     children_count,
                     retainers_count);
   } else if (object->IsHeapNumber()) {
     return AddEntry(object,
                     HeapEntry::kHeapNumber,
                     "number",
                     children_count,
                     retainers_count);
   }
-  // No interest in this object.
-  return NULL;
-}
-
-
-bool HeapSnapshot::WillAddEntry(HeapObject* object) {
-  return object == kInternalRootObject
-      || object->IsJSFunction()
-      || object->IsJSRegExp()
-      || object->IsJSObject()
-      || object->IsString()
-      || object->IsCode()
-      || object->IsSharedFunctionInfo()
-      || object->IsScript()
-      || object->IsFixedArray()
-      || object->IsHeapNumber();
+  return AddEntry(object,
+                  HeapEntry::kHidden,
+                  "system",
+                  children_count,
+                  retainers_count);
 }
 
 
 static void HeapEntryClearPaint(HeapEntry** entry_ptr) {
   (*entry_ptr)->clear_paint();
 }
 
 void HeapSnapshot::ClearPaint() {
   entries_.Iterate(HeapEntryClearPaint);
 }
 
 
-int HeapSnapshot::AddCalculatedData() {
-  calculated_data_.Add(HeapEntryCalculatedData());
-  return calculated_data_.length() - 1;
-}
-
-
 HeapEntry* HeapSnapshot::AddEntry(HeapObject* object,
                                   HeapEntry::Type type,
                                   const char* name,
                                   int children_count,
                                   int retainers_count) {
   return AddEntry(type,
                   name,
                   collection_->GetObjectId(object->address()),
-                  GetObjectSize(object),
+                  object->Size(),
                   children_count,
                   retainers_count);
 }
 
 
 HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,
                                   const char* name,
                                   uint64_t id,
                                   int size,
                                   int children_count,
                                   int retainers_count) {
   HeapEntry* entry = GetNextEntryToInit();
   entry->Init(this, type, name, id, size, children_count, retainers_count);
   return entry;
 }
 
 
+void HeapSnapshot::FillReversePostorderIndexes(Vector<HeapEntry*>* entries) {
+  ClearPaint();
+  int current_entry = 0;
+  List<HeapEntry*> nodes_to_visit;
+  nodes_to_visit.Add(root());
+  root()->paint_reachable();
+  while (!nodes_to_visit.is_empty()) {
+    HeapEntry* entry = nodes_to_visit.last();
+    Vector<HeapGraphEdge> children = entry->children();
+    bool has_new_edges = false;
+    for (int i = 0; i < children.length(); ++i) {
+      if (children[i].type() == HeapGraphEdge::kShortcut) continue;
+      HeapEntry* child = children[i].to();
+      if (!child->painted_reachable()) {
+        nodes_to_visit.Add(child);
+        child->paint_reachable();
+        has_new_edges = true;
+      }
+    }
+    if (!has_new_edges) {
+      entry->set_ordered_index(current_entry);
+      entries->at(current_entry++) = entry;
+      nodes_to_visit.RemoveLast();
+    }
+  }
+  entries->Truncate(current_entry);
+}
+
+
+static int Intersect(int i1, int i2, const Vector<HeapEntry*>& dominators) {
+  int finger1 = i1, finger2 = i2;
+  while (finger1 != finger2) {
+    while (finger1 < finger2) finger1 = dominators[finger1]->ordered_index();
+    while (finger2 < finger1) finger2 = dominators[finger2]->ordered_index();
+  }
+  return finger1;
+}
+
+// The algorithm is based on the article:
+// K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm"
+// Softw. Pract. Exper. 4 (2001), pp. 1–10.
+void HeapSnapshot::BuildDominatorTree(const Vector<HeapEntry*>& entries,
+                                      Vector<HeapEntry*>* dominators) {
+  if (entries.length() == 0) return;
+  const int root_index = entries.length() - 1;
+  for (int i = 0; i < root_index; ++i) dominators->at(i) = NULL;
+  dominators->at(root_index) = entries[root_index];
+  bool changed = true;
+  while (changed) {
+    changed = false;
+    for (int i = root_index - 1; i >= 0; --i) {
+      HeapEntry* new_idom = NULL;
+      Vector<HeapGraphEdge*> rets = entries[i]->retainers();
+      int j = 0;
+      for (; j < rets.length(); ++j) {
+        if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+        HeapEntry* ret = rets[j]->From();
+        if (dominators->at(ret->ordered_index()) != NULL) {
+          new_idom = ret;
+          break;
+        }
+      }
+      for (++j; j < rets.length(); ++j) {
+        if (rets[j]->type() == HeapGraphEdge::kShortcut) continue;
+        HeapEntry* ret = rets[j]->From();
+        if (dominators->at(ret->ordered_index()) != NULL) {
+          new_idom = entries[Intersect(ret->ordered_index(),
+                                       new_idom->ordered_index(),
+                                       *dominators)];
+        }
+      }
+      if (new_idom != NULL && dominators->at(i) != new_idom) {
+        dominators->at(i) = new_idom;
+        changed = true;
+      }
+    }
+  }
+}
+
+
+void HeapSnapshot::SetEntriesDominators() {
+  // This array is used for maintaining reverse postorder of nodes.
+  ScopedVector<HeapEntry*> ordered_entries(entries_.length());
+  FillReversePostorderIndexes(&ordered_entries);
+  ScopedVector<HeapEntry*> dominators(ordered_entries.length());
+  BuildDominatorTree(ordered_entries, &dominators);
+  for (int i = 0; i < ordered_entries.length(); ++i) {
+    ASSERT(dominators[i] != NULL);
+    ordered_entries[i]->set_dominator(dominators[i]);
+  }
+  // For nodes unreachable from root, set dominator to itself.
+  for (int i = 0; i < entries_.length(); ++i) {
+    HeapEntry* entry = entries_[i];
+    if (entry->dominator() == NULL) entry->set_dominator(entry);
+  }
+}
+
+
+void HeapSnapshot::ApproximateRetainedSizes() {
+  SetEntriesDominators();
+  // As for the dominators tree we only know parent nodes, not
+  // children, to sum up total sizes we traverse the tree level by
+  // level upwards, starting from leaves.
+  for (int i = 0; i < entries_.length(); ++i) {
+    HeapEntry* entry = entries_[i];
+    entry->set_retained_size(entry->self_size());
+    entry->set_leaf();
+  }
+  while (true) {
+    bool onlyLeaves = true;
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+      if (!entry->is_processed() && dominator != entry) {
+        dominator->set_non_leaf();
+        onlyLeaves = false;
+      }
+    }
+    if (onlyLeaves) break;
+
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry *entry = entries_[i], *dominator = entry->dominator();
+      if (entry->is_leaf() && dominator != entry) {
+        dominator->add_retained_size(entry->retained_size());
+      }
+    }
+
+    // Mark all current leaves as processed, reset non-leaves back to leaves.
+    for (int i = 0; i < entries_.length(); ++i) {
+      HeapEntry* entry = entries_[i];
+      if (entry->is_leaf())
+        entry->set_processed();
+      else if (entry->is_non_leaf())
+        entry->set_leaf();
+    }
+  }
+}
+
+
 HeapEntry* HeapSnapshot::GetNextEntryToInit() {
   if (entries_.length() > 0) {
     HeapEntry* last_entry = entries_.last();
     entries_.Add(reinterpret_cast<HeapEntry*>(
         reinterpret_cast<char*>(last_entry) + last_entry->EntrySize()));
   } else {
     entries_.Add(reinterpret_cast<HeapEntry*>(raw_entries_));
   }
   ASSERT(reinterpret_cast<char*>(entries_.last()) <
          (raw_entries_ + raw_entries_size_));
   return entries_.last();
 }
 
 
-int HeapSnapshot::GetObjectSize(HeapObject* obj) {
-  return obj->IsJSObject() ?
-      CalculateNetworkSize(JSObject::cast(obj)) : obj->Size();
-}
-
-
-int HeapSnapshot::CalculateNetworkSize(JSObject* obj) {
-  int size = obj->Size();
-  // If 'properties' and 'elements' are non-empty (thus, non-shared),
-  // take their size into account.
-  if (obj->properties() != Heap::empty_fixed_array()) {
-    size += obj->properties()->Size();
-  }
-  if (obj->elements() != Heap::empty_fixed_array()) {
-    size += obj->elements()->Size();
-  }
-  // For functions, also account non-empty context and literals sizes.
-  if (obj->IsJSFunction()) {
-    JSFunction* f = JSFunction::cast(obj);
-    if (f->unchecked_context()->IsContext()) {
-      size += f->context()->Size();
-    }
-    if (f->literals()->length() != 0) {
-      size += f->literals()->Size();
-    }
-  }
-  return size;
-}
-
-
 HeapSnapshotsDiff* HeapSnapshot::CompareWith(HeapSnapshot* snapshot) {
   return collection_->CompareSnapshots(this, snapshot);
 }
 
 
+List<HeapGraphPath*>* HeapSnapshot::GetRetainingPaths(HeapEntry* entry) {
+  HashMap::Entry* p =
+      retaining_paths_.Lookup(entry, HeapEntry::Hash(entry), true);
+  if (p->value == NULL) {
+    p->value = entry->CalculateRetainingPaths();
+  }
+  return reinterpret_cast<List<HeapGraphPath*>*>(p->value);
+}
+
+
 template<class T>
 static int SortByIds(const T* entry1_ptr,
                      const T* entry2_ptr) {
   if ((*entry1_ptr)->id() == (*entry2_ptr)->id()) return 0;
   return (*entry1_ptr)->id() < (*entry2_ptr)->id() ? -1 : 1;
 }
 
 List<HeapEntry*>* HeapSnapshot::GetSortedEntriesList() {
   if (!entries_sorted_) {
     entries_.Sort(SortByIds);
     entries_sorted_ = true;
   }
   return &entries_;
 }
 
 
 void HeapSnapshot::Print(int max_depth) {
   root()->Print(max_depth, 0);
 }
 
 
+const uint64_t HeapObjectsMap::kInternalRootObjectId = 0;
+const uint64_t HeapObjectsMap::kGcRootsObjectId = 1;
+// Increase kFirstAvailableObjectId if new 'special' objects appear.
+const uint64_t HeapObjectsMap::kFirstAvailableObjectId = 2;
+
 HeapObjectsMap::HeapObjectsMap()
     : initial_fill_mode_(true),
-      next_id_(1),
+      next_id_(kFirstAvailableObjectId),
       entries_map_(AddressesMatch),
       entries_(new List<EntryInfo>()) { }
 
 
 HeapObjectsMap::~HeapObjectsMap() {
   delete entries_;
 }
 
 
 void HeapObjectsMap::SnapshotGenerationFinished() {
@@ skipping 130 matching lines @@
 HeapEntriesMap::HeapEntriesMap()
     : entries_(HeapObjectsMatch),
       entries_count_(0),
       total_children_count_(0),
       total_retainers_count_(0) {
 }
 
 
 HeapEntriesMap::~HeapEntriesMap() {
   for (HashMap::Entry* p = entries_.Start(); p != NULL; p = entries_.Next(p)) {
-    if (!IsAlias(p->value)) delete reinterpret_cast<EntryInfo*>(p->value);
-  }
-}
-
-
-void HeapEntriesMap::Alias(HeapObject* from, HeapObject* to) {
-  HashMap::Entry* from_cache_entry = entries_.Lookup(from, Hash(from), true);
-  HashMap::Entry* to_cache_entry = entries_.Lookup(to, Hash(to), false);
-  if (from_cache_entry->value == NULL) {
-    ASSERT(to_cache_entry != NULL);
-    from_cache_entry->value = MakeAlias(to_cache_entry->value);
+    delete reinterpret_cast<EntryInfo*>(p->value);
   }
 }
 
 
 HeapEntry* HeapEntriesMap::Map(HeapObject* object) {
   HashMap::Entry* cache_entry = entries_.Lookup(object, Hash(object), false);
   if (cache_entry != NULL) {
-    EntryInfo* entry_info =
-        reinterpret_cast<EntryInfo*>(Unalias(cache_entry->value));
+    EntryInfo* entry_info = reinterpret_cast<EntryInfo*>(cache_entry->value);
     return entry_info->entry;
   } else {
     return NULL;
   }
 }
 
 
 void HeapEntriesMap::Pair(HeapObject* object, HeapEntry* entry) {
   HashMap::Entry* cache_entry = entries_.Lookup(object, Hash(object), true);
   ASSERT(cache_entry->value == NULL);
   cache_entry->value = new EntryInfo(entry);
   ++entries_count_;
 }
 
 
 void HeapEntriesMap::CountReference(HeapObject* from, HeapObject* to,
                                     int* prev_children_count,
                                     int* prev_retainers_count) {
   HashMap::Entry* from_cache_entry = entries_.Lookup(from, Hash(from), false);
   HashMap::Entry* to_cache_entry = entries_.Lookup(to, Hash(to), false);
   ASSERT(from_cache_entry != NULL);
   ASSERT(to_cache_entry != NULL);
   EntryInfo* from_entry_info =
-      reinterpret_cast<EntryInfo*>(Unalias(from_cache_entry->value));
+      reinterpret_cast<EntryInfo*>(from_cache_entry->value);
   EntryInfo* to_entry_info =
-      reinterpret_cast<EntryInfo*>(Unalias(to_cache_entry->value));
+      reinterpret_cast<EntryInfo*>(to_cache_entry->value);
   if (prev_children_count)
     *prev_children_count = from_entry_info->children_count;
   if (prev_retainers_count)
     *prev_retainers_count = to_entry_info->retainers_count;
   ++from_entry_info->children_count;
   ++to_entry_info->retainers_count;
   ++total_children_count_;
   ++total_retainers_count_;
 }
 
 
+HeapObjectsSet::HeapObjectsSet()
+    : entries_(HeapEntriesMap::HeapObjectsMatch) {
+}
+
+
+void HeapObjectsSet::Clear() {
+  entries_.Clear();
+}
+
+
+bool HeapObjectsSet::Contains(Object* obj) {
+  if (!obj->IsHeapObject()) return false;
+  HeapObject* object = HeapObject::cast(obj);
+  HashMap::Entry* cache_entry =
+      entries_.Lookup(object, HeapEntriesMap::Hash(object), false);
+  return cache_entry != NULL;
+}
+
+
+void HeapObjectsSet::Insert(Object* obj) {
+  if (!obj->IsHeapObject()) return;
+  HeapObject* object = HeapObject::cast(obj);
+  HashMap::Entry* cache_entry =
+      entries_.Lookup(object, HeapEntriesMap::Hash(object), true);
+  if (cache_entry->value == NULL) {
+    cache_entry->value = HeapEntriesMap::kHeapEntryPlaceholder;
+  }
+}
+
+
 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot)
     : snapshot_(snapshot),
       collection_(snapshot->collection()),
       filler_(NULL) {
 }
 
 class SnapshotCounter : public HeapSnapshotGenerator::SnapshotFillerInterface {
  public:
   explicit SnapshotCounter(HeapEntriesMap* entries)
       : entries_(entries) { }
   HeapEntry* AddEntry(HeapObject* obj) {
     entries_->Pair(obj, HeapEntriesMap::kHeapEntryPlaceholder);
     return HeapEntriesMap::kHeapEntryPlaceholder;
   }
-  void SetElementReference(HeapObject* parent_obj,
+  void SetIndexedReference(HeapGraphEdge::Type,
+                           HeapObject* parent_obj,
                            HeapEntry*,
                            int,
                            Object* child_obj,
                            HeapEntry*) {
     entries_->CountReference(parent_obj, HeapObject::cast(child_obj));
   }
   void SetNamedReference(HeapGraphEdge::Type,
                          HeapObject* parent_obj,
                          HeapEntry*,
                          const char*,
                          Object* child_obj,
                          HeapEntry*) {
     entries_->CountReference(parent_obj, HeapObject::cast(child_obj));
   }
-  void SetRootReference(Object* child_obj, HeapEntry*) {
+  void SetRootShortcutReference(Object* child_obj, HeapEntry*) {
     entries_->CountReference(
         HeapSnapshot::kInternalRootObject, HeapObject::cast(child_obj));
   }
+  void SetRootGcRootsReference() {
+    entries_->CountReference(
+        HeapSnapshot::kInternalRootObject, HeapSnapshot::kGcRootsObject);
+  }
+  void SetStrongRootReference(Object* child_obj, HeapEntry*) {
+    entries_->CountReference(
+        HeapSnapshot::kGcRootsObject, HeapObject::cast(child_obj));
+  }
  private:
   HeapEntriesMap* entries_;
 };
 
 
 class SnapshotFiller : public HeapSnapshotGenerator::SnapshotFillerInterface {
  public:
   explicit SnapshotFiller(HeapSnapshot* snapshot, HeapEntriesMap* entries)
       : snapshot_(snapshot),
         collection_(snapshot->collection()),
         entries_(entries) { }
   HeapEntry* AddEntry(HeapObject* obj) {
     UNREACHABLE();
     return NULL;
   }
-  void SetElementReference(HeapObject* parent_obj,
+  void SetIndexedReference(HeapGraphEdge::Type type,
+                           HeapObject* parent_obj,
                            HeapEntry* parent_entry,
                            int index,
                            Object* child_obj,
                            HeapEntry* child_entry) {
     int child_index, retainer_index;
-    entries_->CountReference(parent_obj, HeapObject::cast(child_obj),
-                             &child_index, &retainer_index);
-    parent_entry->SetElementReference(
-        child_index, index, child_entry, retainer_index);
+    entries_->CountReference(parent_obj,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    parent_entry->SetIndexedReference(
+        type, child_index, index, child_entry, retainer_index);
   }
   void SetNamedReference(HeapGraphEdge::Type type,
                          HeapObject* parent_obj,
                          HeapEntry* parent_entry,
                          const char* reference_name,
                          Object* child_obj,
                          HeapEntry* child_entry) {
     int child_index, retainer_index;
     entries_->CountReference(parent_obj, HeapObject::cast(child_obj),
                              &child_index, &retainer_index);
     parent_entry->SetNamedReference(type,
                               child_index,
                               reference_name,
                               child_entry,
                               retainer_index);
   }
-  void SetRootReference(Object* child_obj, HeapEntry* child_entry) {
+  void SetRootGcRootsReference() {
     int child_index, retainer_index;
-    entries_->CountReference(
-        HeapSnapshot::kInternalRootObject, HeapObject::cast(child_obj),
-        &child_index, &retainer_index);
-    snapshot_->root()->SetElementReference(
-        child_index, child_index + 1, child_entry, retainer_index);
+    entries_->CountReference(HeapSnapshot::kInternalRootObject,
+                             HeapSnapshot::kGcRootsObject,
+                             &child_index,
+                             &retainer_index);
+    snapshot_->root()->SetIndexedReference(HeapGraphEdge::kElement,
+                                           child_index,
+                                           child_index + 1,
+                                           snapshot_->gc_roots(),
+                                           retainer_index);
+  }
+  void SetRootShortcutReference(Object* child_obj,
+                                HeapEntry* child_entry) {
+    int child_index, retainer_index;
+    entries_->CountReference(HeapSnapshot::kInternalRootObject,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    snapshot_->root()->SetNamedReference(HeapGraphEdge::kShortcut,
+                                         child_index,
+                                         collection_->GetName(child_index + 1),
+                                         child_entry,
+                                         retainer_index);
+  }
+  void SetStrongRootReference(Object* child_obj,
+                              HeapEntry* child_entry) {
+    int child_index, retainer_index;
+    entries_->CountReference(HeapSnapshot::kGcRootsObject,
+                             HeapObject::cast(child_obj),
+                             &child_index,
+                             &retainer_index);
+    snapshot_->gc_roots()->SetIndexedReference(HeapGraphEdge::kElement,
+                                               child_index,
+                                               child_index + 1,
+                                               child_entry,
+                                               retainer_index);
   }
  private:
   HeapSnapshot* snapshot_;
   HeapSnapshotsCollection* collection_;
   HeapEntriesMap* entries_;
 };
 
 class SnapshotAllocator {
  public:
   explicit SnapshotAllocator(HeapSnapshot* snapshot)
       : snapshot_(snapshot) { }
   HeapEntry* GetEntry(
       HeapObject* obj, int children_count, int retainers_count) {
     HeapEntry* entry =
         snapshot_->AddEntry(obj, children_count, retainers_count);
     ASSERT(entry != NULL);
     return entry;
   }
  private:
   HeapSnapshot* snapshot_;
 };
 
+class RootsReferencesExtractor : public ObjectVisitor {
+ public:
+  explicit RootsReferencesExtractor(HeapSnapshotGenerator* generator)
+      : generator_(generator) {
+  }
+  void VisitPointers(Object** start, Object** end) {
+    for (Object** p = start; p < end; p++) generator_->SetGcRootsReference(*p);
+  }
+ private:
+  HeapSnapshotGenerator* generator_;
+};
+
+
 void HeapSnapshotGenerator::GenerateSnapshot() {
   AssertNoAllocation no_alloc;
 
   // Pass 1. Iterate heap contents to count entries and references.
   SnapshotCounter counter(&entries_);
   filler_ = &counter;
   filler_->AddEntry(HeapSnapshot::kInternalRootObject);
-  HeapIterator iterator1;
-  for (HeapObject* obj = iterator1.next();
-       obj != NULL;
-       obj = iterator1.next()) {
+  filler_->AddEntry(HeapSnapshot::kGcRootsObject);
+  HeapIterator iterator(HeapIterator::kPreciseFiltering);
+  for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
     ExtractReferences(obj);
   }
+  SetRootGcRootsReference();
+  RootsReferencesExtractor extractor(this);
+  Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG);
 
   // Allocate and fill entries in the snapshot, allocate references.
   snapshot_->AllocateEntries(entries_.entries_count(),
                              entries_.total_children_count(),
                              entries_.total_retainers_count());
   SnapshotAllocator allocator(snapshot_);
   entries_.UpdateEntries(&allocator);
 
   // Pass 2. Fill references.
   SnapshotFiller filler(snapshot_, &entries_);
   filler_ = &filler;
-  HeapIterator iterator2;
-  for (HeapObject* obj = iterator2.next();
-       obj != NULL;
-       obj = iterator2.next()) {
+  iterator.reset();
+  for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) {
     ExtractReferences(obj);
   }
+  SetRootGcRootsReference();
+  Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG);
+
+  snapshot_->ApproximateRetainedSizes();
 }
 
 
 HeapEntry* HeapSnapshotGenerator::GetEntry(Object* obj) {
   if (!obj->IsHeapObject()) return NULL;
   HeapObject* object = HeapObject::cast(obj);
   HeapEntry* entry = entries_.Map(object);
-
   // A new entry.
-  if (entry == NULL) {
-    if (obj->IsJSGlobalPropertyCell()) {
-      Object* cell_target = JSGlobalPropertyCell::cast(obj)->value();
-      entry = GetEntry(cell_target);
-      // If GPC references an object that we have interest in (see
-      // HeapSnapshot::AddEntry, WillAddEntry), add the object.  We
-      // don't store HeapEntries for GPCs. Instead, we make our hash
-      // map to point to object's HeapEntry by GPCs address.
-      if (entry != NULL) {
-        entries_.Alias(object, HeapObject::cast(cell_target));
-      }
-      return entry;
-    }
-
-    if (snapshot_->WillAddEntry(object)) entry = filler_->AddEntry(object);
-  }
-
+  if (entry == NULL) entry = filler_->AddEntry(object);
   return entry;
 }
 
 
 class IndexedReferencesExtractor : public ObjectVisitor {
  public:
   IndexedReferencesExtractor(HeapSnapshotGenerator* generator,
                              HeapObject* parent_obj,
-                             HeapEntry* parent_entry)
+                             HeapEntry* parent_entry,
+                             HeapObjectsSet* known_references = NULL)
       : generator_(generator),
         parent_obj_(parent_obj),
         parent_(parent_entry),
+        known_references_(known_references),
         next_index_(1) {
   }
-
-  void VisitPointer(Object** o) {
-    generator_->SetElementReference(parent_obj_, parent_, next_index_++, *o);
+  void VisitPointers(Object** start, Object** end) {
+    for (Object** p = start; p < end; p++) {
+      if (!known_references_ || !known_references_->Contains(*p)) {
+        generator_->SetHiddenReference(parent_obj_, parent_, next_index_++, *p);
+      }
+    }
   }
-
-  void VisitPointers(Object** start, Object** end) {
-    for (Object** p = start; p < end; p++) VisitPointer(p);
-  }
-
  private:
   HeapSnapshotGenerator* generator_;
   HeapObject* parent_obj_;
   HeapEntry* parent_;
+  HeapObjectsSet* known_references_;
   int next_index_;
 };
 
 
 void HeapSnapshotGenerator::ExtractReferences(HeapObject* obj) {
-  // We need to reference JS global objects from snapshot's root.
-  // We use JSGlobalProxy because this is what embedder (e.g. browser)
-  // uses for the global object.
-  if (obj->IsJSGlobalProxy()) {
-    JSGlobalProxy* proxy = JSGlobalProxy::cast(obj);
-    SetRootReference(proxy->map()->prototype());
-    return;
-  }
-
   HeapEntry* entry = GetEntry(obj);
   if (entry == NULL) return;  // No interest in this object.
 
-  if (obj->IsJSObject()) {
+  known_references_.Clear();
+  if (obj->IsJSGlobalProxy()) {
+    // We need to reference JS global objects from snapshot's root.
+    // We use JSGlobalProxy because this is what embedder (e.g. browser)
+    // uses for the global object.
+    JSGlobalProxy* proxy = JSGlobalProxy::cast(obj);
+    SetRootShortcutReference(proxy->map()->prototype());
+    IndexedReferencesExtractor refs_extractor(this, obj, entry);
+    obj->Iterate(&refs_extractor);
+  } else if (obj->IsJSObject()) {
     JSObject* js_obj = JSObject::cast(obj);
     ExtractClosureReferences(js_obj, entry);
     ExtractPropertyReferences(js_obj, entry);
     ExtractElementReferences(js_obj, entry);
     ExtractInternalReferences(js_obj, entry);
     SetPropertyReference(
         obj, entry, Heap::Proto_symbol(), js_obj->GetPrototype());
     if (obj->IsJSFunction()) {
       JSFunction* js_fun = JSFunction::cast(obj);
       if (js_fun->has_prototype()) {
         SetPropertyReference(
             obj, entry, Heap::prototype_symbol(), js_fun->prototype());
       }
     }
+    IndexedReferencesExtractor refs_extractor(
+        this, obj, entry, &known_references_);
+    obj->Iterate(&refs_extractor);
   } else if (obj->IsString()) {
     if (obj->IsConsString()) {
       ConsString* cs = ConsString::cast(obj);
-      SetInternalReference(obj, entry, "1", cs->first());
-      SetInternalReference(obj, entry, "2", cs->second());
+      SetInternalReference(obj, entry, 1, cs->first());
+      SetInternalReference(obj, entry, 2, cs->second());
     }
-  } else if (obj->IsCode() || obj->IsSharedFunctionInfo() || obj->IsScript()) {
-    IndexedReferencesExtractor refs_extractor(this, obj, entry);
-    obj->Iterate(&refs_extractor);
-  } else if (obj->IsFixedArray()) {
+  } else {
     IndexedReferencesExtractor refs_extractor(this, obj, entry);
     obj->Iterate(&refs_extractor);
   }
 }
 
 
 void HeapSnapshotGenerator::ExtractClosureReferences(JSObject* js_obj,
                                                      HeapEntry* entry) {
   if (js_obj->IsJSFunction()) {
     HandleScope hs;
@@ skipping 34 matching lines @@
           break;
         default: ;
       }
     }
   } else {
     StringDictionary* dictionary = js_obj->property_dictionary();
     int length = dictionary->Capacity();
     for (int i = 0; i < length; ++i) {
       Object* k = dictionary->KeyAt(i);
       if (dictionary->IsKey(k)) {
+        Object* target = dictionary->ValueAt(i);
         SetPropertyReference(
-            js_obj, entry, String::cast(k), dictionary->ValueAt(i));
+            js_obj, entry, String::cast(k), target);
+        // We assume that global objects can only have slow properties.
+        if (target->IsJSGlobalPropertyCell()) {
+          SetPropertyShortcutReference(js_obj,
+                                       entry,
+                                       String::cast(k),
+                                       JSGlobalPropertyCell::cast(
+                                           target)->value());
+        }
       }
     }
   }
 }
 
 
 void HeapSnapshotGenerator::ExtractElementReferences(JSObject* js_obj,
                                                      HeapEntry* entry) {
   if (js_obj->HasFastElements()) {
     FixedArray* elements = FixedArray::cast(js_obj->elements());
@@ skipping 35 matching lines @@
                                                 String* reference_name,
                                                 Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kContextVariable,
                                parent_obj,
                                parent_entry,
                                collection_->GetName(reference_name),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
 
 void HeapSnapshotGenerator::SetElementReference(HeapObject* parent_obj,
                                                 HeapEntry* parent_entry,
                                                 int index,
                                                 Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
-    filler_->SetElementReference(
-        parent_obj, parent_entry, index, child_obj, child_entry);
+    filler_->SetIndexedReference(HeapGraphEdge::kElement,
+                                 parent_obj,
+                                 parent_entry,
+                                 index,
+                                 child_obj,
+                                 child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
 
 void HeapSnapshotGenerator::SetInternalReference(HeapObject* parent_obj,
                                                  HeapEntry* parent_entry,
                                                  const char* reference_name,
                                                  Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kInternal,
                                parent_obj,
                                parent_entry,
                                reference_name,
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
   }
 }
 
 
 void HeapSnapshotGenerator::SetInternalReference(HeapObject* parent_obj,
                                                  HeapEntry* parent_entry,
                                                  int index,
                                                  Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     filler_->SetNamedReference(HeapGraphEdge::kInternal,
                                parent_obj,
                                parent_entry,
                                collection_->GetName(index),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
+  }
+}
+
+
+void HeapSnapshotGenerator::SetHiddenReference(HeapObject* parent_obj,
+                                               HeapEntry* parent_entry,
+                                               int index,
+                                               Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetIndexedReference(HeapGraphEdge::kHidden,
+                                 parent_obj,
+                                 parent_entry,
+                                 index,
+                                 child_obj,
+                                 child_entry);
   }
 }
 
 
 void HeapSnapshotGenerator::SetPropertyReference(HeapObject* parent_obj,
                                                  HeapEntry* parent_entry,
                                                  String* reference_name,
                                                  Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   if (child_entry != NULL) {
     HeapGraphEdge::Type type = reference_name->length() > 0 ?
         HeapGraphEdge::kProperty : HeapGraphEdge::kInternal;
     filler_->SetNamedReference(type,
                                parent_obj,
                                parent_entry,
                                collection_->GetName(reference_name),
                                child_obj,
                                child_entry);
+    known_references_.Insert(child_obj);
+  }
+}
+
+
+void HeapSnapshotGenerator::SetPropertyShortcutReference(
+    HeapObject* parent_obj,
+    HeapEntry* parent_entry,
+    String* reference_name,
+    Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetNamedReference(HeapGraphEdge::kShortcut,
+                               parent_obj,
+                               parent_entry,
+                               collection_->GetName(reference_name),
+                               child_obj,
+                               child_entry);
   }
 }
 
 
-void HeapSnapshotGenerator::SetRootReference(Object* child_obj) {
+void HeapSnapshotGenerator::SetRootGcRootsReference() {
+  filler_->SetRootGcRootsReference();
+}
+
+
+void HeapSnapshotGenerator::SetRootShortcutReference(Object* child_obj) {
   HeapEntry* child_entry = GetEntry(child_obj);
   ASSERT(child_entry != NULL);
-  filler_->SetRootReference(child_obj, child_entry);
+  filler_->SetRootShortcutReference(child_obj, child_entry);
+}
+
+
+void HeapSnapshotGenerator::SetGcRootsReference(Object* child_obj) {
+  HeapEntry* child_entry = GetEntry(child_obj);
+  if (child_entry != NULL) {
+    filler_->SetStrongRootReference(child_obj, child_entry);
+  }
 }
 
 
 void HeapSnapshotsDiff::CreateRoots(int additions_count, int deletions_count) {
   raw_additions_root_ =
       NewArray<char>(HeapEntry::EntriesSize(1, additions_count, 0));
   additions_root()->Init(
-      snapshot2_, HeapEntry::kInternal, "", 0, 0, additions_count, 0);
+      snapshot2_, HeapEntry::kHidden, "", 0, 0, additions_count, 0);
   raw_deletions_root_ =
       NewArray<char>(HeapEntry::EntriesSize(1, deletions_count, 0));
   deletions_root()->Init(
-      snapshot1_, HeapEntry::kInternal, "", 0, 0, deletions_count, 0);
+      snapshot1_, HeapEntry::kHidden, "", 0, 0, deletions_count, 0);
 }
 
 
 static void DeleteHeapSnapshotsDiff(HeapSnapshotsDiff** diff_ptr) {
   delete *diff_ptr;
 }
 
 HeapSnapshotsComparator::~HeapSnapshotsComparator() {
   diffs_.Iterate(DeleteHeapSnapshotsDiff);
 }
@@ skipping 198 matching lines @@
     cache_entry->value = reinterpret_cast<void*>(next_string_id_++);
   }
   return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeEdge(HeapGraphEdge* edge) {
   writer_->AddCharacter(',');
   writer_->AddNumber(edge->type());
   writer_->AddCharacter(',');
-  if (edge->type() == HeapGraphEdge::kElement) {
+  if (edge->type() == HeapGraphEdge::kElement
+      || edge->type() == HeapGraphEdge::kHidden) {
     writer_->AddNumber(edge->index());
   } else {
     writer_->AddNumber(GetStringId(edge->name()));
   }
   writer_->AddCharacter(',');
   writer_->AddNumber(GetNodeId(edge->to()));
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry) {
   writer_->AddCharacter('\n');
   writer_->AddCharacter(',');
   writer_->AddNumber(entry->type());
   writer_->AddCharacter(',');
   writer_->AddNumber(GetStringId(entry->name()));
   writer_->AddCharacter(',');
   writer_->AddNumber(entry->id());
   writer_->AddCharacter(',');
   writer_->AddNumber(entry->self_size());
+  writer_->AddCharacter(',');
+  writer_->AddNumber(entry->RetainedSize(false));
+  writer_->AddCharacter(',');
+  writer_->AddNumber(GetNodeId(entry->dominator()));
   Vector<HeapGraphEdge> children = entry->children();
   writer_->AddCharacter(',');
   writer_->AddNumber(children.length());
   for (int i = 0; i < children.length(); ++i) {
     SerializeEdge(&children[i]);
     if (writer_->aborted()) return;
   }
 }
 
 
 void HeapSnapshotJSONSerializer::SerializeNodes() {
-  // The first (zero) item of nodes array is a JSON-ified object
-  // describing node serialization layout.
-  // We use a set of macros to improve readability.
+  // The first (zero) item of nodes array is an object describing node
+  // serialization layout.  We use a set of macros to improve
+  // readability.
 #define JSON_A(s) "["s"]"
 #define JSON_O(s) "{"s"}"
-#define JSON_S(s) "\\\""s"\\\""
-  writer_->AddString("\"" JSON_O(
+#define JSON_S(s) "\""s"\""
+  writer_->AddString(JSON_O(
     JSON_S("fields") ":" JSON_A(
         JSON_S("type")
         "," JSON_S("name")
         "," JSON_S("id")
         "," JSON_S("self_size")
+        "," JSON_S("retained_size")
+        "," JSON_S("dominator")
         "," JSON_S("children_count")
         "," JSON_S("children"))
     "," JSON_S("types") ":" JSON_A(
         JSON_A(
-            JSON_S("internal")
+            JSON_S("hidden")
             "," JSON_S("array")
             "," JSON_S("string")
             "," JSON_S("object")
             "," JSON_S("code")
             "," JSON_S("closure")
             "," JSON_S("regexp")
             "," JSON_S("number"))
         "," JSON_S("string")
         "," JSON_S("number")
         "," JSON_S("number")
         "," JSON_S("number")
+        "," JSON_S("number")
+        "," JSON_S("number")
         "," JSON_O(
             JSON_S("fields") ":" JSON_A(
                 JSON_S("type")
                 "," JSON_S("name_or_index")
                 "," JSON_S("to_node"))
             "," JSON_S("types") ":" JSON_A(
                 JSON_A(
                     JSON_S("context")
                     "," JSON_S("element")
                     "," JSON_S("property")
-                    "," JSON_S("internal"))
+                    "," JSON_S("internal")
+                    "," JSON_S("hidden")
+                    "," JSON_S("shortcut"))
                 "," JSON_S("string_or_number")
-                "," JSON_S("node"))))) "\"");
+                "," JSON_S("node"))))));
 #undef JSON_S
 #undef JSON_O
 #undef JSON_A
 
-  const int node_fields_count = 5;  // type,name,id,self_size,children_count.
+  const int node_fields_count = 7;
+  // type,name,id,self_size,retained_size,dominator,children_count.
   const int edge_fields_count = 3;  // type,name|index,to_node.
   List<HashMap::Entry*> sorted_nodes;
   SortHashMap(&nodes_, &sorted_nodes);
   // Rewrite node ids, so they refer to actual array positions.
   if (sorted_nodes.length() > 1) {
     // Nodes start from array index 1.
     int prev_value = 1;
     sorted_nodes[0]->value = reinterpret_cast<void*>(prev_value);
     for (int i = 1; i < sorted_nodes.length(); ++i) {
       HeapEntry* prev_heap_entry =
@@ skipping 108 matching lines @@
 void HeapSnapshotJSONSerializer::SortHashMap(
     HashMap* map, List<HashMap::Entry*>* sorted_entries) {
   for (HashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p))
     sorted_entries->Add(p);
   sorted_entries->Sort(SortUsingEntryValue);
 }
 
 } }  // namespace v8::internal
 
 #endif  // ENABLE_LOGGING_AND_PROFILING