Heap profiler: implement diffing of snapshots.

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 163 matching lines @@
     OS::Print(" %s:%d", entry_->resource_name(), entry_->line_number());
   OS::Print("\n");
   for (HashMap::Entry* p = children_.Start();
        p != NULL;
        p = children_.Next(p)) {
     reinterpret_cast<ProfileNode*>(p->value)->Print(indent + 2);
   }
 }
 
 
-namespace {
-
 class DeleteNodesCallback {
  public:
   void BeforeTraversingChild(ProfileNode*, ProfileNode*) { }
 
   void AfterAllChildrenTraversed(ProfileNode* node) {
     delete node;
   }
 
   void AfterChildTraversed(ProfileNode*, ProfileNode*) { }
 };
 
-}  // namespace
-
 
 ProfileTree::ProfileTree()
     : root_entry_(Logger::FUNCTION_TAG,
                   "",
                   "(root)",
                   "",
                   0,
                   TokenEnumerator::kNoSecurityToken),
       root_(new ProfileNode(this, &root_entry_)) {
 }
@@ skipping 24 matching lines @@
        entry != path.start() + path.length();
        ++entry) {
     if (*entry != NULL) {
       node = node->FindOrAddChild(*entry);
     }
   }
   node->IncrementSelfTicks();
 }
 
 
-namespace {
-
 struct NodesPair {
   NodesPair(ProfileNode* src, ProfileNode* dst)
       : src(src), dst(dst) { }
   ProfileNode* src;
   ProfileNode* dst;
 };
 
 
 class FilteredCloneCallback {
  public:
@@ skipping 32 matching lines @@
       return parent_token == TokenEnumerator::kNoSecurityToken
           || parent_token == security_token_id_;
     }
     return false;
   }
 
   List<NodesPair> stack_;
   int security_token_id_;
 };
 
-}  // namespace
-
 void ProfileTree::FilteredClone(ProfileTree* src, int security_token_id) {
   ms_to_ticks_scale_ = src->ms_to_ticks_scale_;
   FilteredCloneCallback cb(root_, security_token_id);
   src->TraverseDepthFirst(&cb);
   CalculateTotalTicks();
 }
 
 
 void ProfileTree::SetTickRatePerMs(double ticks_per_ms) {
   ms_to_ticks_scale_ = ticks_per_ms > 0 ? 1.0 / ticks_per_ms : 1.0;
 }
 
 
-namespace {
-
 class Position {
  public:
   explicit Position(ProfileNode* node)
       : node(node), child_idx_(0) { }
   INLINE(ProfileNode* current_child()) {
     return node->children()->at(child_idx_);
   }
   INLINE(bool has_current_child()) {
     return child_idx_ < node->children()->length();
   }
   INLINE(void next_child()) { ++child_idx_; }
 
   ProfileNode* node;
  private:
   int child_idx_;
 };
 
-}  // namespace
-
 
 // Non-recursive implementation of a depth-first post-order tree traversal.
 template <typename Callback>
 void ProfileTree::TraverseDepthFirst(Callback* callback) {
   List<Position> stack(10);
   stack.Add(Position(root_));
   while (stack.length() > 0) {
     Position& current = stack.last();
     if (current.has_current_child()) {
       callback->BeforeTraversingChild(current.node, current.current_child());
       stack.Add(Position(current.current_child()));
     } else {
       callback->AfterAllChildrenTraversed(current.node);
       if (stack.length() > 1) {
         Position& parent = stack[stack.length() - 2];
         callback->AfterChildTraversed(parent.node, current.node);
         parent.next_child();
       }
       // Remove child from the stack.
       stack.RemoveLast();
     }
   }
 }
 
 
-namespace {
-
 class CalculateTotalTicksCallback {
  public:
   void BeforeTraversingChild(ProfileNode*, ProfileNode*) { }
 
   void AfterAllChildrenTraversed(ProfileNode* node) {
     node->IncreaseTotalTicks(node->self_ticks());
   }
 
   void AfterChildTraversed(ProfileNode* parent, ProfileNode* child) {
     parent->IncreaseTotalTicks(child->total_ticks());
   }
 };
 
-}  // namespace
-
 
 void ProfileTree::CalculateTotalTicks() {
   CalculateTotalTicksCallback cb;
   TraverseDepthFirst(&cb);
 }
 
 
 void ProfileTree::ShortPrint() {
   OS::Print("root: %u %u %.2fms %.2fms\n",
             root_->total_ticks(), root_->self_ticks(),
@@ skipping 485 matching lines @@
 void HeapEntry::SetPropertyReference(const char* name, HeapEntry* entry) {
   AddEdge(new HeapGraphEdge(HeapGraphEdge::PROPERTY, name, this, entry));
 }
 
 
 void HeapEntry::SetAutoIndexReference(HeapEntry* entry) {
   SetElementReference(next_auto_index_++, entry);
 }
 
 
+void HeapEntry::SetUnidirAutoIndexReference(HeapEntry* entry) {
+  children_.Add(new HeapGraphEdge(next_auto_index_++, this, entry));
+}
+
+
 int HeapEntry::TotalSize() {
   return total_size_ != kUnknownSize ? total_size_ : CalculateTotalSize();
 }
 
 
 int HeapEntry::NonSharedTotalSize() {
   return non_shared_total_size_ != kUnknownSize ?
       non_shared_total_size_ : CalculateNonSharedTotalSize();
 }
 
 
-int HeapEntry::CalculateTotalSize() {
-  snapshot_->ClearPaint();
+template<class Visitor>
+void HeapEntry::ApplyAndPaintAllReachable(Visitor* visitor) {
   List<HeapEntry*> list(10);
   list.Add(this);
-  total_size_ = self_size_;
   this->PaintReachable();
+  visitor->Apply(this);
   while (!list.is_empty()) {
     HeapEntry* entry = list.RemoveLast();
     const int children_count = entry->children_.length();
     for (int i = 0; i < children_count; ++i) {
       HeapEntry* child = entry->children_[i]->to();
       if (!child->painted_reachable()) {
         list.Add(child);
         child->PaintReachable();
-        total_size_ += child->self_size_;
+        visitor->Apply(child);
       }
     }
   }
+}
+
+
+class NullClass {
+ public:
+  void Apply(HeapEntry* entry) { }
+};
+
+void HeapEntry::PaintAllReachable() {
+  NullClass null;
+  ApplyAndPaintAllReachable(&null);
+}
+
+
+class TotalSizeCalculator {
+ public:
+  TotalSizeCalculator()
+      : total_size_(0) {
+  }
+
+  int total_size() const { return total_size_; }
+
+  void Apply(HeapEntry* entry) {
+    total_size_ += entry->self_size();
+  }
+
+ private:
+  int total_size_;
+};
+
+int HeapEntry::CalculateTotalSize() {
+  snapshot_->ClearPaint();
+  TotalSizeCalculator calc;
+  ApplyAndPaintAllReachable(&calc);
+  total_size_ = calc.total_size();
   return total_size_;
 }
 
 
-namespace {
-
 class NonSharedSizeCalculator {
  public:
   NonSharedSizeCalculator()
       : non_shared_total_size_(0) {
   }
 
   int non_shared_total_size() const { return non_shared_total_size_; }
 
   void Apply(HeapEntry* entry) {
     if (entry->painted_reachable()) {
       non_shared_total_size_ += entry->self_size();
     }
   }
 
  private:
   int non_shared_total_size_;
 };
 
-}  // namespace
-
 int HeapEntry::CalculateNonSharedTotalSize() {
   // To calculate non-shared total size, first we paint all reachable
   // nodes in one color, then we paint all nodes reachable from other
   // nodes with a different color. Then we consider only nodes painted
-  // with the first color for caclulating the total size.
+  // with the first color for calculating the total size.
   snapshot_->ClearPaint();
+  PaintAllReachable();
+
   List<HeapEntry*> list(10);
-  list.Add(this);
-  this->PaintReachable();
+  if (this != snapshot_->root()) {
+    list.Add(snapshot_->root());
+    snapshot_->root()->PaintReachableFromOthers();
+  }
   while (!list.is_empty()) {
     HeapEntry* entry = list.RemoveLast();
     const int children_count = entry->children_.length();
     for (int i = 0; i < children_count; ++i) {
       HeapEntry* child = entry->children_[i]->to();
-      if (!child->painted_reachable()) {
+      if (child != this && child->not_painted_reachable_from_others()) {
         list.Add(child);
-        child->PaintReachable();
-      }
-    }
-  }
-
-  List<HeapEntry*> list2(10);
-  if (this != snapshot_->root()) {
-    list2.Add(snapshot_->root());
-    snapshot_->root()->PaintReachableFromOthers();
-  }
-  while (!list2.is_empty()) {
-    HeapEntry* entry = list2.RemoveLast();
-    const int children_count = entry->children_.length();
-    for (int i = 0; i < children_count; ++i) {
-      HeapEntry* child = entry->children_[i]->to();
-      if (child != this && child->not_painted_reachable_from_others()) {
-        list2.Add(child);
         child->PaintReachableFromOthers();
       }
     }
   }
 
   NonSharedSizeCalculator calculator;
   snapshot_->IterateEntries(&calculator);
-  return calculator.non_shared_total_size();
+  non_shared_total_size_ = calculator.non_shared_total_size();
+  return non_shared_total_size_;
 }
 
 
 class CachedHeapGraphPath {
  public:
   CachedHeapGraphPath()
       : nodes_(NodesMatch) { }
   CachedHeapGraphPath(const CachedHeapGraphPath& src)
       : nodes_(NodesMatch, &HashMap::DefaultAllocator, src.nodes_.capacity()),
         path_(src.path_.length() + 1) {
@@ skipping 85 matching lines @@
 
   for (int i = 0; i < retainers_.length(); ++i) {
     HeapGraphEdge* edge = retainers_[i];
     edge->from()->RemoveChild(edge);
   }
   retainers_.Clear();
 }
 
 
 void HeapEntry::Print(int max_depth, int indent) {
-  OS::Print("%6d %6d %6d ", self_size_, TotalSize(), NonSharedTotalSize());
+  OS::Print("%6d %6d %6d [%ld] ",
+            self_size_, TotalSize(), NonSharedTotalSize(), id_);
   if (type_ != STRING) {
     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 145 matching lines @@
   cache_entry->value = entry;
 }
 
 
 HeapSnapshot::HeapSnapshot(HeapSnapshotsCollection* collection,
                            const char* title,
                            unsigned uid)
     : collection_(collection),
       title_(title),
       uid_(uid),
-      root_(this) {
+      root_(this),
+      sorted_entries_(NULL) {
 }
 
 
+HeapSnapshot::~HeapSnapshot() {
+  delete sorted_entries_;
+}
+
+
 void HeapSnapshot::ClearPaint() {
   root_.ClearPaint();
   entries_.Apply(&HeapEntry::ClearPaint);
 }
 
 
 HeapEntry* HeapSnapshot::GetEntry(Object* obj) {
   if (!obj->IsHeapObject()) return NULL;
   HeapObject* object = HeapObject::cast(obj);
 
@@ skipping 87 matching lines @@
   }
 }
 
 
 HeapEntry* HeapSnapshot::AddEntry(HeapObject* object,
                                   HeapEntry::Type type,
                                   const char* name) {
   HeapEntry* entry = new HeapEntry(this,
                                    type,
                                    name,
+                                   collection_->GetObjectId(object->address()),
                                    GetObjectSize(object),
                                    GetObjectSecurityToken(object));
   entries_.Pair(object, entry);
 
   // Detect, if this is a JS global object of the current context, and
   // add it to snapshot's roots. There can be several JS global objects
   // in a context.
   if (object->IsJSGlobalProxy()) {
     int global_security_token = GetGlobalSecurityToken();
     int object_security_token =
         collection_->token_enumerator()->GetTokenId(
             Context::cast(
                 JSGlobalProxy::cast(object)->context())->security_token());
     if (object_security_token == TokenEnumerator::kNoSecurityToken
         || object_security_token == global_security_token) {
       HeapEntry* global_object_entry =
           GetEntry(HeapObject::cast(object->map()->prototype()));
       ASSERT(global_object_entry != NULL);
       root_.SetAutoIndexReference(global_object_entry);
     }
   }
 
   return entry;
 }
 
 
-namespace {
-
 class EdgesCutter {
  public:
   explicit EdgesCutter(int global_security_token)
       : global_security_token_(global_security_token) {
   }
 
   void Apply(HeapEntry* entry) {
     if (entry->security_token_id() != TokenEnumerator::kNoSecurityToken
         && entry->security_token_id() != global_security_token_) {
       entry->CutEdges();
     }
   }
 
  private:
   const int global_security_token_;
 };
 
-}  // namespace
-
 void HeapSnapshot::CutObjectsFromForeignSecurityContexts() {
   EdgesCutter cutter(GetGlobalSecurityToken());
   entries_.Apply(&cutter);
 }
 
 
 int HeapSnapshot::GetGlobalSecurityToken() {
   return collection_->token_enumerator()->GetTokenId(
       Top::context()->global()->global_context()->security_token());
 }
@@ skipping 32 matching lines @@
       size += f->context()->Size();
     }
     if (f->literals()->length() != 0) {
       size += f->literals()->Size();
     }
   }
   return size;
 }
 
 
+class EntriesCollector {
+ public:
+  explicit EntriesCollector(List<HeapEntry*>* list) : list_(list) { }
+  void Apply(HeapEntry* entry) {
+    list_->Add(entry);
+  }
+ private:
+  List<HeapEntry*>* list_;
+};
+
+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 (sorted_entries_ != NULL) return sorted_entries_;
+  sorted_entries_ = new List<HeapEntry*>(entries_.capacity());
+  EntriesCollector collector(sorted_entries_);
+  entries_.Apply(&collector);
+  sorted_entries_->Sort(SortByIds);
+  return sorted_entries_;
+}
+
+
+HeapSnapshotsDiff* HeapSnapshot::CompareWith(HeapSnapshot* snapshot) {
+  return collection_->CompareSnapshots(this, snapshot);
+}
+
+
 void HeapSnapshot::Print(int max_depth) {
   root_.Print(max_depth, 0);
 }
 
 
+HeapObjectsMap::HeapObjectsMap()
+    : initial_fill_mode_(true),
+      next_id_(1),
+      entries_map_(AddressesMatch),
+      entries_(new List<EntryInfo>()) { }
+
+
+HeapObjectsMap::~HeapObjectsMap() {
+  delete entries_;
+}
+
+
+void HeapObjectsMap::SnapshotGenerationFinished() {
+    initial_fill_mode_ = false;
+    RemoveDeadEntries();
+}
+
+
+uint64_t HeapObjectsMap::FindObject(Address addr) {
+  if (!initial_fill_mode_) {
+    uint64_t existing = FindEntry(addr);
+    if (existing != 0) return existing;
+  }
+  uint64_t id = next_id_++;
+  AddEntry(addr, id);
+  return id;
+}
+
+
+void HeapObjectsMap::MoveObject(Address from, Address to) {
+  HashMap::Entry* entry = entries_map_.Lookup(from, AddressHash(from), false);
+  if (entry != NULL) {
+    void* value = entry->value;
+    entries_map_.Remove(from, AddressHash(from));
+    entry = entries_map_.Lookup(to, AddressHash(to), true);
+    ASSERT(entry->value == NULL);
+    entry->value = value;
+  }
+}
+
+
+void HeapObjectsMap::AddEntry(Address addr, uint64_t id) {
+  HashMap::Entry* entry = entries_map_.Lookup(addr, AddressHash(addr), true);
+  ASSERT(entry->value == NULL);
+  entry->value = reinterpret_cast<void*>(entries_->length());
+  entries_->Add(EntryInfo(id));
+}
+
+
+uint64_t HeapObjectsMap::FindEntry(Address addr) {
+  HashMap::Entry* entry = entries_map_.Lookup(addr, AddressHash(addr), false);
+  if (entry != NULL) {
+    int entry_index = reinterpret_cast<intptr_t>(entry->value);
+    EntryInfo& entry_info = entries_->at(entry_index);
+    entry_info.accessed = true;
+    return entry_info.id;
+  } else {
+    return 0;
+  }
+}
+
+
+void HeapObjectsMap::RemoveDeadEntries() {
+  List<EntryInfo>* new_entries = new List<EntryInfo>();
+  for (HashMap::Entry* entry = entries_map_.Start();
+       entry != NULL;
+       entry = entries_map_.Next(entry)) {
+    int entry_index = reinterpret_cast<intptr_t>(entry->value);
+    EntryInfo& entry_info = entries_->at(entry_index);
+    if (entry_info.accessed) {
+      entry->value = reinterpret_cast<void*>(new_entries->length());
+      new_entries->Add(EntryInfo(entry_info.id, false));
+    }
+  }
+  delete entries_;
+  entries_ = new_entries;
+}
+
+
 HeapSnapshotsCollection::HeapSnapshotsCollection()
-    : snapshots_uids_(HeapSnapshotsMatch),
+    : is_tracking_objects_(false),
+      snapshots_uids_(HeapSnapshotsMatch),
       token_enumerator_(new TokenEnumerator()) {
 }
 
 
 static void DeleteHeapSnapshot(HeapSnapshot** snapshot_ptr) {
   delete *snapshot_ptr;
 }
 
 
 HeapSnapshotsCollection::~HeapSnapshotsCollection() {
   delete token_enumerator_;
   snapshots_.Iterate(DeleteHeapSnapshot);
 }
 
 
 HeapSnapshot* HeapSnapshotsCollection::NewSnapshot(const char* name,
                                                    unsigned uid) {
+  is_tracking_objects_ = true;  // Start watching for heap objects moves.
   HeapSnapshot* snapshot = new HeapSnapshot(this, name, uid);
   snapshots_.Add(snapshot);
   HashMap::Entry* entry =
       snapshots_uids_.Lookup(reinterpret_cast<void*>(snapshot->uid()),
                              static_cast<uint32_t>(snapshot->uid()),
                              true);
   ASSERT(entry->value == NULL);
   entry->value = snapshot;
   return snapshot;
 }
 
 
 HeapSnapshot* HeapSnapshotsCollection::GetSnapshot(unsigned uid) {
   HashMap::Entry* entry = snapshots_uids_.Lookup(reinterpret_cast<void*>(uid),
                                                  static_cast<uint32_t>(uid),
                                                  false);
   return entry != NULL ? reinterpret_cast<HeapSnapshot*>(entry->value) : NULL;
 }
 
 
+HeapSnapshotsDiff* HeapSnapshotsCollection::CompareSnapshots(
+    HeapSnapshot* snapshot1,
+    HeapSnapshot* snapshot2) {
+  return comparator_.Compare(snapshot1, snapshot2);
+}
+
+
 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot)
     : snapshot_(snapshot) {
 }
 
 
 void HeapSnapshotGenerator::GenerateSnapshot() {
   AssertNoAllocation no_alloc;
 
   // Iterate heap contents.
   HeapIterator iterator;
@@ skipping 112 matching lines @@
       Object* k = dictionary->KeyAt(i);
       if (dictionary->IsKey(k)) {
         ASSERT(k->IsNumber());
         uint32_t index = static_cast<uint32_t>(k->Number());
         snapshot_->SetElementReference(entry, index, dictionary->ValueAt(i));
       }
     }
   }
 }
 
+
+static void DeleteHeapSnapshotsDiff(HeapSnapshotsDiff** diff_ptr) {
+  delete *diff_ptr;
+}
+
+HeapSnapshotsComparator::~HeapSnapshotsComparator() {
+  diffs_.Iterate(DeleteHeapSnapshotsDiff);
+}
+
+
+HeapSnapshotsDiff* HeapSnapshotsComparator::Compare(HeapSnapshot* snapshot1,
+                                                    HeapSnapshot* snapshot2) {
+  HeapSnapshotsDiff* diff = new HeapSnapshotsDiff(snapshot1, snapshot2);
+  diffs_.Add(diff);
+  List<HeapEntry*>* entries1 = snapshot1->GetSortedEntriesList();
+  List<HeapEntry*>* entries2 = snapshot2->GetSortedEntriesList();
+  int i = 0, j = 0;
+  List<HeapEntry*> added_entries, deleted_entries;
+  while (i < entries1->length() && j < entries2->length()) {
+    uint64_t id1 = entries1->at(i)->id();
+    uint64_t id2 = entries2->at(j)->id();
+    if (id1 == id2) {
+      i++;
+      j++;
+    } else if (id1 < id2) {
+      HeapEntry* entry = entries1->at(i++);
+      deleted_entries.Add(entry);
+    } else {
+      HeapEntry* entry = entries2->at(j++);
+      added_entries.Add(entry);
+    }
+  }
+  while (i < entries1->length()) {
+    HeapEntry* entry = entries1->at(i++);
+    deleted_entries.Add(entry);
+  }
+  while (j < entries2->length()) {
+    HeapEntry* entry = entries2->at(j++);
+    added_entries.Add(entry);
+  }
+
+  snapshot1->ClearPaint();
+  snapshot1->root()->PaintAllReachable();
+  for (int i = 0; i < deleted_entries.length(); ++i) {
+    HeapEntry* entry = deleted_entries[i];
+    if (entry->painted_reachable())
+      diff->AddDeletedEntry(entry);
+  }
+  snapshot2->ClearPaint();
+  snapshot2->root()->PaintAllReachable();
+  for (int i = 0; i < added_entries.length(); ++i) {
+    HeapEntry* entry = added_entries[i];
+    if (entry->painted_reachable())
+      diff->AddAddedEntry(entry);
+  }
+  return diff;
+}
+
 } }  // namespace v8::internal
 
 #endif  // ENABLE_LOGGING_AND_PROFILING