Index: src/profile-generator.cc |
diff --git a/src/profile-generator.cc b/src/profile-generator.cc |
index 364f51d4f1c8e1a68d1b0c2d8b440879e539a0d0..ff4661fbc5ec8ad7d9d9bea8a9bb0594be760bfe 100644 |
--- a/src/profile-generator.cc |
+++ b/src/profile-generator.cc |
@@ -1382,6 +1382,86 @@ HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type, |
} |
+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)[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)[i] = NULL; |
+ (*dominators)[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)[i] = new_idom; |
+ changed = true; |
+ } |
+ } |
+ } |
+} |
+ |
+ |
void HeapSnapshot::SetDominatorsToSelf() { |
for (int i = 0; i < entries_.length(); ++i) { |
HeapEntry* entry = entries_[i]; |
@@ -1390,6 +1470,61 @@ void HeapSnapshot::SetDominatorsToSelf() { |
} |
+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. |
+ SetDominatorsToSelf(); |
+} |
+ |
+ |
+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(); |
@@ -1581,22 +1716,15 @@ HeapSnapshot* HeapSnapshotsCollection::NewSnapshot(HeapSnapshot::Type type, |
const char* name, |
unsigned uid) { |
is_tracking_objects_ = true; // Start watching for heap objects moves. |
- return new HeapSnapshot(this, type, name, uid); |
-} |
- |
- |
-void HeapSnapshotsCollection::SnapshotGenerationFinished( |
- HeapSnapshot* snapshot) { |
- ids_.SnapshotGenerationFinished(); |
- if (snapshot != NULL) { |
- 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; |
- } |
+ HeapSnapshot* snapshot = new HeapSnapshot(this, type, 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; |
} |
@@ -1704,10 +1832,8 @@ void HeapObjectsSet::Insert(Object* obj) { |
} |
-HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot, |
- v8::ActivityControl* control) |
+HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot) |
: snapshot_(snapshot), |
- control_(control), |
collection_(snapshot->collection()), |
filler_(NULL) { |
} |
@@ -1864,13 +1990,21 @@ class RootsReferencesExtractor : public ObjectVisitor { |
}; |
-bool HeapSnapshotGenerator::GenerateSnapshot() { |
+void HeapSnapshotGenerator::GenerateSnapshot() { |
AssertNoAllocation no_alloc; |
- SetProgressTotal(4); // 2 passes + dominators + sizes. |
- |
// Pass 1. Iterate heap contents to count entries and references. |
- if (!CountEntriesAndReferences()) return false; |
+ SnapshotCounter counter(&entries_); |
+ filler_ = &counter; |
+ filler_->AddEntry(HeapSnapshot::kInternalRootObject); |
+ 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(), |
@@ -1880,14 +2014,16 @@ bool HeapSnapshotGenerator::GenerateSnapshot() { |
entries_.UpdateEntries(&allocator); |
// Pass 2. Fill references. |
- if (!FillReferences()) return false; |
- |
- if (!SetEntriesDominators()) return false; |
- if (!ApproximateRetainedSizes()) return false; |
+ SnapshotFiller filler(snapshot_, &entries_); |
+ filler_ = &filler; |
+ iterator.reset(); |
+ for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) { |
+ ExtractReferences(obj); |
+ } |
+ SetRootGcRootsReference(); |
+ Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG); |
- progress_counter_ = progress_total_; |
- if (!ReportProgress(true)) return false; |
- return true; |
+ snapshot_->ApproximateRetainedSizes(); |
} |
@@ -2215,183 +2351,6 @@ void HeapSnapshotGenerator::SetGcRootsReference(Object* child_obj) { |
} |
-void HeapSnapshotGenerator::SetProgressTotal(int iterations_count) { |
- if (control_ == NULL) return; |
- |
- HeapIterator iterator(HeapIterator::kPreciseFiltering); |
- int objects_count = 0; |
- for (HeapObject* obj = iterator.next(); |
- obj != NULL; |
- obj = iterator.next(), ++objects_count) {} |
- progress_total_ = objects_count * iterations_count; |
- progress_counter_ = 0; |
-} |
- |
- |
-bool HeapSnapshotGenerator::CountEntriesAndReferences() { |
- SnapshotCounter counter(&entries_); |
- filler_ = &counter; |
- filler_->AddEntry(HeapSnapshot::kInternalRootObject); |
- filler_->AddEntry(HeapSnapshot::kGcRootsObject); |
- return IterateAndExtractReferences(); |
-} |
- |
- |
-bool HeapSnapshotGenerator::FillReferences() { |
- SnapshotFiller filler(snapshot_, &entries_); |
- filler_ = &filler; |
- return IterateAndExtractReferences(); |
-} |
- |
- |
-void HeapSnapshotGenerator::FillReversePostorderIndexes( |
- Vector<HeapEntry*>* entries) { |
- snapshot_->ClearPaint(); |
- int current_entry = 0; |
- List<HeapEntry*> nodes_to_visit; |
- nodes_to_visit.Add(snapshot_->root()); |
- snapshot_->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)[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. |
-bool HeapSnapshotGenerator::BuildDominatorTree( |
- const Vector<HeapEntry*>& entries, |
- Vector<HeapEntry*>* dominators) { |
- if (entries.length() == 0) return true; |
- const int entries_length = entries.length(), root_index = entries_length - 1; |
- for (int i = 0; i < root_index; ++i) (*dominators)[i] = NULL; |
- (*dominators)[root_index] = entries[root_index]; |
- int changed = 1; |
- const int base_progress_counter = progress_counter_; |
- while (changed != 0) { |
- changed = 0; |
- 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)[i] = new_idom; |
- ++changed; |
- } |
- } |
- int remaining = entries_length - changed; |
- if (remaining < 0) remaining = 0; |
- progress_counter_ = base_progress_counter + remaining; |
- if (!ReportProgress(true)) return false; |
- } |
- return true; |
-} |
- |
- |
-bool HeapSnapshotGenerator::SetEntriesDominators() { |
- // This array is used for maintaining reverse postorder of nodes. |
- ScopedVector<HeapEntry*> ordered_entries(snapshot_->entries()->length()); |
- FillReversePostorderIndexes(&ordered_entries); |
- ScopedVector<HeapEntry*> dominators(ordered_entries.length()); |
- if (!BuildDominatorTree(ordered_entries, &dominators)) return false; |
- 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. |
- snapshot_->SetDominatorsToSelf(); |
- return true; |
-} |
- |
- |
-bool HeapSnapshotGenerator::ApproximateRetainedSizes() { |
- // As for the dominators tree we only know parent nodes, not |
- // children, to sum up total sizes we "bubble" node's self size |
- // adding it to all of its parents. |
- for (int i = 0; i < snapshot_->entries()->length(); ++i) { |
- HeapEntry* entry = snapshot_->entries()->at(i); |
- entry->set_retained_size(entry->self_size()); |
- } |
- for (int i = 0; |
- i < snapshot_->entries()->length(); |
- ++i, IncProgressCounter()) { |
- HeapEntry* entry = snapshot_->entries()->at(i); |
- int entry_size = entry->self_size(); |
- for (HeapEntry* dominator = entry->dominator(); |
- dominator != entry; |
- entry = dominator, dominator = entry->dominator()) { |
- dominator->add_retained_size(entry_size); |
- } |
- if (!ReportProgress()) return false; |
- } |
- return true; |
-} |
- |
- |
-bool HeapSnapshotGenerator::IterateAndExtractReferences() { |
- HeapIterator iterator(HeapIterator::kPreciseFiltering); |
- bool interrupted = false; |
- // Heap iteration with precise filtering must be finished in any case. |
- for (HeapObject* obj = iterator.next(); |
- obj != NULL; |
- obj = iterator.next(), IncProgressCounter()) { |
- if (!interrupted) { |
- ExtractReferences(obj); |
- if (!ReportProgress()) interrupted = true; |
- } |
- } |
- if (interrupted) return false; |
- SetRootGcRootsReference(); |
- RootsReferencesExtractor extractor(this); |
- Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG); |
- return ReportProgress(); |
-} |
- |
- |
void HeapSnapshotsDiff::CreateRoots(int additions_count, int deletions_count) { |
raw_additions_root_ = |
NewArray<char>(HeapEntry::EntriesSize(1, additions_count, 0)); |