OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1364 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1375 uint64_t id, | 1375 uint64_t id, |
1376 int size, | 1376 int size, |
1377 int children_count, | 1377 int children_count, |
1378 int retainers_count) { | 1378 int retainers_count) { |
1379 HeapEntry* entry = GetNextEntryToInit(); | 1379 HeapEntry* entry = GetNextEntryToInit(); |
1380 entry->Init(this, type, name, id, size, children_count, retainers_count); | 1380 entry->Init(this, type, name, id, size, children_count, retainers_count); |
1381 return entry; | 1381 return entry; |
1382 } | 1382 } |
1383 | 1383 |
1384 | 1384 |
| 1385 void HeapSnapshot::FillReversePostorderIndexes(Vector<HeapEntry*>* entries) { |
| 1386 ClearPaint(); |
| 1387 int current_entry = 0; |
| 1388 List<HeapEntry*> nodes_to_visit; |
| 1389 nodes_to_visit.Add(root()); |
| 1390 root()->paint_reachable(); |
| 1391 while (!nodes_to_visit.is_empty()) { |
| 1392 HeapEntry* entry = nodes_to_visit.last(); |
| 1393 Vector<HeapGraphEdge> children = entry->children(); |
| 1394 bool has_new_edges = false; |
| 1395 for (int i = 0; i < children.length(); ++i) { |
| 1396 if (children[i].type() == HeapGraphEdge::kShortcut) continue; |
| 1397 HeapEntry* child = children[i].to(); |
| 1398 if (!child->painted_reachable()) { |
| 1399 nodes_to_visit.Add(child); |
| 1400 child->paint_reachable(); |
| 1401 has_new_edges = true; |
| 1402 } |
| 1403 } |
| 1404 if (!has_new_edges) { |
| 1405 entry->set_ordered_index(current_entry); |
| 1406 (*entries)[current_entry++] = entry; |
| 1407 nodes_to_visit.RemoveLast(); |
| 1408 } |
| 1409 } |
| 1410 entries->Truncate(current_entry); |
| 1411 } |
| 1412 |
| 1413 |
| 1414 static int Intersect(int i1, int i2, const Vector<HeapEntry*>& dominators) { |
| 1415 int finger1 = i1, finger2 = i2; |
| 1416 while (finger1 != finger2) { |
| 1417 while (finger1 < finger2) finger1 = dominators[finger1]->ordered_index(); |
| 1418 while (finger2 < finger1) finger2 = dominators[finger2]->ordered_index(); |
| 1419 } |
| 1420 return finger1; |
| 1421 } |
| 1422 |
| 1423 // The algorithm is based on the article: |
| 1424 // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm" |
| 1425 // Softw. Pract. Exper. 4 (2001), pp. 1–10. |
| 1426 void HeapSnapshot::BuildDominatorTree(const Vector<HeapEntry*>& entries, |
| 1427 Vector<HeapEntry*>* dominators) { |
| 1428 if (entries.length() == 0) return; |
| 1429 const int root_index = entries.length() - 1; |
| 1430 for (int i = 0; i < root_index; ++i) (*dominators)[i] = NULL; |
| 1431 (*dominators)[root_index] = entries[root_index]; |
| 1432 bool changed = true; |
| 1433 while (changed) { |
| 1434 changed = false; |
| 1435 for (int i = root_index - 1; i >= 0; --i) { |
| 1436 HeapEntry* new_idom = NULL; |
| 1437 Vector<HeapGraphEdge*> rets = entries[i]->retainers(); |
| 1438 int j = 0; |
| 1439 for (; j < rets.length(); ++j) { |
| 1440 if (rets[j]->type() == HeapGraphEdge::kShortcut) continue; |
| 1441 HeapEntry* ret = rets[j]->From(); |
| 1442 if (dominators->at(ret->ordered_index()) != NULL) { |
| 1443 new_idom = ret; |
| 1444 break; |
| 1445 } |
| 1446 } |
| 1447 for (++j; j < rets.length(); ++j) { |
| 1448 if (rets[j]->type() == HeapGraphEdge::kShortcut) continue; |
| 1449 HeapEntry* ret = rets[j]->From(); |
| 1450 if (dominators->at(ret->ordered_index()) != NULL) { |
| 1451 new_idom = entries[Intersect(ret->ordered_index(), |
| 1452 new_idom->ordered_index(), |
| 1453 *dominators)]; |
| 1454 } |
| 1455 } |
| 1456 if (new_idom != NULL && dominators->at(i) != new_idom) { |
| 1457 (*dominators)[i] = new_idom; |
| 1458 changed = true; |
| 1459 } |
| 1460 } |
| 1461 } |
| 1462 } |
| 1463 |
| 1464 |
1385 void HeapSnapshot::SetDominatorsToSelf() { | 1465 void HeapSnapshot::SetDominatorsToSelf() { |
1386 for (int i = 0; i < entries_.length(); ++i) { | 1466 for (int i = 0; i < entries_.length(); ++i) { |
1387 HeapEntry* entry = entries_[i]; | 1467 HeapEntry* entry = entries_[i]; |
1388 if (entry->dominator() == NULL) entry->set_dominator(entry); | 1468 if (entry->dominator() == NULL) entry->set_dominator(entry); |
1389 } | 1469 } |
1390 } | 1470 } |
1391 | 1471 |
1392 | 1472 |
| 1473 void HeapSnapshot::SetEntriesDominators() { |
| 1474 // This array is used for maintaining reverse postorder of nodes. |
| 1475 ScopedVector<HeapEntry*> ordered_entries(entries_.length()); |
| 1476 FillReversePostorderIndexes(&ordered_entries); |
| 1477 ScopedVector<HeapEntry*> dominators(ordered_entries.length()); |
| 1478 BuildDominatorTree(ordered_entries, &dominators); |
| 1479 for (int i = 0; i < ordered_entries.length(); ++i) { |
| 1480 ASSERT(dominators[i] != NULL); |
| 1481 ordered_entries[i]->set_dominator(dominators[i]); |
| 1482 } |
| 1483 // For nodes unreachable from root, set dominator to itself. |
| 1484 SetDominatorsToSelf(); |
| 1485 } |
| 1486 |
| 1487 |
| 1488 void HeapSnapshot::ApproximateRetainedSizes() { |
| 1489 SetEntriesDominators(); |
| 1490 // As for the dominators tree we only know parent nodes, not |
| 1491 // children, to sum up total sizes we traverse the tree level by |
| 1492 // level upwards, starting from leaves. |
| 1493 for (int i = 0; i < entries_.length(); ++i) { |
| 1494 HeapEntry* entry = entries_[i]; |
| 1495 entry->set_retained_size(entry->self_size()); |
| 1496 entry->set_leaf(); |
| 1497 } |
| 1498 while (true) { |
| 1499 bool onlyLeaves = true; |
| 1500 for (int i = 0; i < entries_.length(); ++i) { |
| 1501 HeapEntry *entry = entries_[i], *dominator = entry->dominator(); |
| 1502 if (!entry->is_processed() && dominator != entry) { |
| 1503 dominator->set_non_leaf(); |
| 1504 onlyLeaves = false; |
| 1505 } |
| 1506 } |
| 1507 if (onlyLeaves) break; |
| 1508 |
| 1509 for (int i = 0; i < entries_.length(); ++i) { |
| 1510 HeapEntry *entry = entries_[i], *dominator = entry->dominator(); |
| 1511 if (entry->is_leaf() && dominator != entry) { |
| 1512 dominator->add_retained_size(entry->retained_size()); |
| 1513 } |
| 1514 } |
| 1515 |
| 1516 // Mark all current leaves as processed, reset non-leaves back to leaves. |
| 1517 for (int i = 0; i < entries_.length(); ++i) { |
| 1518 HeapEntry* entry = entries_[i]; |
| 1519 if (entry->is_leaf()) |
| 1520 entry->set_processed(); |
| 1521 else if (entry->is_non_leaf()) |
| 1522 entry->set_leaf(); |
| 1523 } |
| 1524 } |
| 1525 } |
| 1526 |
| 1527 |
1393 HeapEntry* HeapSnapshot::GetNextEntryToInit() { | 1528 HeapEntry* HeapSnapshot::GetNextEntryToInit() { |
1394 if (entries_.length() > 0) { | 1529 if (entries_.length() > 0) { |
1395 HeapEntry* last_entry = entries_.last(); | 1530 HeapEntry* last_entry = entries_.last(); |
1396 entries_.Add(reinterpret_cast<HeapEntry*>( | 1531 entries_.Add(reinterpret_cast<HeapEntry*>( |
1397 reinterpret_cast<char*>(last_entry) + last_entry->EntrySize())); | 1532 reinterpret_cast<char*>(last_entry) + last_entry->EntrySize())); |
1398 } else { | 1533 } else { |
1399 entries_.Add(reinterpret_cast<HeapEntry*>(raw_entries_)); | 1534 entries_.Add(reinterpret_cast<HeapEntry*>(raw_entries_)); |
1400 } | 1535 } |
1401 ASSERT(reinterpret_cast<char*>(entries_.last()) < | 1536 ASSERT(reinterpret_cast<char*>(entries_.last()) < |
1402 (raw_entries_ + raw_entries_size_)); | 1537 (raw_entries_ + raw_entries_size_)); |
(...skipping 171 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1574 HeapSnapshotsCollection::~HeapSnapshotsCollection() { | 1709 HeapSnapshotsCollection::~HeapSnapshotsCollection() { |
1575 delete token_enumerator_; | 1710 delete token_enumerator_; |
1576 snapshots_.Iterate(DeleteHeapSnapshot); | 1711 snapshots_.Iterate(DeleteHeapSnapshot); |
1577 } | 1712 } |
1578 | 1713 |
1579 | 1714 |
1580 HeapSnapshot* HeapSnapshotsCollection::NewSnapshot(HeapSnapshot::Type type, | 1715 HeapSnapshot* HeapSnapshotsCollection::NewSnapshot(HeapSnapshot::Type type, |
1581 const char* name, | 1716 const char* name, |
1582 unsigned uid) { | 1717 unsigned uid) { |
1583 is_tracking_objects_ = true; // Start watching for heap objects moves. | 1718 is_tracking_objects_ = true; // Start watching for heap objects moves. |
1584 return new HeapSnapshot(this, type, name, uid); | 1719 HeapSnapshot* snapshot = new HeapSnapshot(this, type, name, uid); |
| 1720 snapshots_.Add(snapshot); |
| 1721 HashMap::Entry* entry = |
| 1722 snapshots_uids_.Lookup(reinterpret_cast<void*>(snapshot->uid()), |
| 1723 static_cast<uint32_t>(snapshot->uid()), |
| 1724 true); |
| 1725 ASSERT(entry->value == NULL); |
| 1726 entry->value = snapshot; |
| 1727 return snapshot; |
1585 } | 1728 } |
1586 | 1729 |
1587 | 1730 |
1588 void HeapSnapshotsCollection::SnapshotGenerationFinished( | |
1589 HeapSnapshot* snapshot) { | |
1590 ids_.SnapshotGenerationFinished(); | |
1591 if (snapshot != NULL) { | |
1592 snapshots_.Add(snapshot); | |
1593 HashMap::Entry* entry = | |
1594 snapshots_uids_.Lookup(reinterpret_cast<void*>(snapshot->uid()), | |
1595 static_cast<uint32_t>(snapshot->uid()), | |
1596 true); | |
1597 ASSERT(entry->value == NULL); | |
1598 entry->value = snapshot; | |
1599 } | |
1600 } | |
1601 | |
1602 | |
1603 HeapSnapshot* HeapSnapshotsCollection::GetSnapshot(unsigned uid) { | 1731 HeapSnapshot* HeapSnapshotsCollection::GetSnapshot(unsigned uid) { |
1604 HashMap::Entry* entry = snapshots_uids_.Lookup(reinterpret_cast<void*>(uid), | 1732 HashMap::Entry* entry = snapshots_uids_.Lookup(reinterpret_cast<void*>(uid), |
1605 static_cast<uint32_t>(uid), | 1733 static_cast<uint32_t>(uid), |
1606 false); | 1734 false); |
1607 return entry != NULL ? reinterpret_cast<HeapSnapshot*>(entry->value) : NULL; | 1735 return entry != NULL ? reinterpret_cast<HeapSnapshot*>(entry->value) : NULL; |
1608 } | 1736 } |
1609 | 1737 |
1610 | 1738 |
1611 HeapSnapshotsDiff* HeapSnapshotsCollection::CompareSnapshots( | 1739 HeapSnapshotsDiff* HeapSnapshotsCollection::CompareSnapshots( |
1612 HeapSnapshot* snapshot1, | 1740 HeapSnapshot* snapshot1, |
(...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1697 if (!obj->IsHeapObject()) return; | 1825 if (!obj->IsHeapObject()) return; |
1698 HeapObject* object = HeapObject::cast(obj); | 1826 HeapObject* object = HeapObject::cast(obj); |
1699 HashMap::Entry* cache_entry = | 1827 HashMap::Entry* cache_entry = |
1700 entries_.Lookup(object, HeapEntriesMap::Hash(object), true); | 1828 entries_.Lookup(object, HeapEntriesMap::Hash(object), true); |
1701 if (cache_entry->value == NULL) { | 1829 if (cache_entry->value == NULL) { |
1702 cache_entry->value = HeapEntriesMap::kHeapEntryPlaceholder; | 1830 cache_entry->value = HeapEntriesMap::kHeapEntryPlaceholder; |
1703 } | 1831 } |
1704 } | 1832 } |
1705 | 1833 |
1706 | 1834 |
1707 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot, | 1835 HeapSnapshotGenerator::HeapSnapshotGenerator(HeapSnapshot* snapshot) |
1708 v8::ActivityControl* control) | |
1709 : snapshot_(snapshot), | 1836 : snapshot_(snapshot), |
1710 control_(control), | |
1711 collection_(snapshot->collection()), | 1837 collection_(snapshot->collection()), |
1712 filler_(NULL) { | 1838 filler_(NULL) { |
1713 } | 1839 } |
1714 | 1840 |
1715 class SnapshotCounter : public HeapSnapshotGenerator::SnapshotFillerInterface { | 1841 class SnapshotCounter : public HeapSnapshotGenerator::SnapshotFillerInterface { |
1716 public: | 1842 public: |
1717 explicit SnapshotCounter(HeapEntriesMap* entries) | 1843 explicit SnapshotCounter(HeapEntriesMap* entries) |
1718 : entries_(entries) { } | 1844 : entries_(entries) { } |
1719 HeapEntry* AddEntry(HeapObject* obj) { | 1845 HeapEntry* AddEntry(HeapObject* obj) { |
1720 entries_->Pair(obj, HeapEntriesMap::kHeapEntryPlaceholder); | 1846 entries_->Pair(obj, HeapEntriesMap::kHeapEntryPlaceholder); |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1857 : generator_(generator) { | 1983 : generator_(generator) { |
1858 } | 1984 } |
1859 void VisitPointers(Object** start, Object** end) { | 1985 void VisitPointers(Object** start, Object** end) { |
1860 for (Object** p = start; p < end; p++) generator_->SetGcRootsReference(*p); | 1986 for (Object** p = start; p < end; p++) generator_->SetGcRootsReference(*p); |
1861 } | 1987 } |
1862 private: | 1988 private: |
1863 HeapSnapshotGenerator* generator_; | 1989 HeapSnapshotGenerator* generator_; |
1864 }; | 1990 }; |
1865 | 1991 |
1866 | 1992 |
1867 bool HeapSnapshotGenerator::GenerateSnapshot() { | 1993 void HeapSnapshotGenerator::GenerateSnapshot() { |
1868 AssertNoAllocation no_alloc; | 1994 AssertNoAllocation no_alloc; |
1869 | 1995 |
1870 SetProgressTotal(4); // 2 passes + dominators + sizes. | |
1871 | |
1872 // Pass 1. Iterate heap contents to count entries and references. | 1996 // Pass 1. Iterate heap contents to count entries and references. |
1873 if (!CountEntriesAndReferences()) return false; | 1997 SnapshotCounter counter(&entries_); |
| 1998 filler_ = &counter; |
| 1999 filler_->AddEntry(HeapSnapshot::kInternalRootObject); |
| 2000 filler_->AddEntry(HeapSnapshot::kGcRootsObject); |
| 2001 HeapIterator iterator(HeapIterator::kPreciseFiltering); |
| 2002 for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) { |
| 2003 ExtractReferences(obj); |
| 2004 } |
| 2005 SetRootGcRootsReference(); |
| 2006 RootsReferencesExtractor extractor(this); |
| 2007 Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG); |
1874 | 2008 |
1875 // Allocate and fill entries in the snapshot, allocate references. | 2009 // Allocate and fill entries in the snapshot, allocate references. |
1876 snapshot_->AllocateEntries(entries_.entries_count(), | 2010 snapshot_->AllocateEntries(entries_.entries_count(), |
1877 entries_.total_children_count(), | 2011 entries_.total_children_count(), |
1878 entries_.total_retainers_count()); | 2012 entries_.total_retainers_count()); |
1879 SnapshotAllocator allocator(snapshot_); | 2013 SnapshotAllocator allocator(snapshot_); |
1880 entries_.UpdateEntries(&allocator); | 2014 entries_.UpdateEntries(&allocator); |
1881 | 2015 |
1882 // Pass 2. Fill references. | 2016 // Pass 2. Fill references. |
1883 if (!FillReferences()) return false; | 2017 SnapshotFiller filler(snapshot_, &entries_); |
| 2018 filler_ = &filler; |
| 2019 iterator.reset(); |
| 2020 for (HeapObject* obj = iterator.next(); obj != NULL; obj = iterator.next()) { |
| 2021 ExtractReferences(obj); |
| 2022 } |
| 2023 SetRootGcRootsReference(); |
| 2024 Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG); |
1884 | 2025 |
1885 if (!SetEntriesDominators()) return false; | 2026 snapshot_->ApproximateRetainedSizes(); |
1886 if (!ApproximateRetainedSizes()) return false; | |
1887 | |
1888 progress_counter_ = progress_total_; | |
1889 if (!ReportProgress(true)) return false; | |
1890 return true; | |
1891 } | 2027 } |
1892 | 2028 |
1893 | 2029 |
1894 HeapEntry* HeapSnapshotGenerator::GetEntry(Object* obj) { | 2030 HeapEntry* HeapSnapshotGenerator::GetEntry(Object* obj) { |
1895 if (!obj->IsHeapObject()) return NULL; | 2031 if (!obj->IsHeapObject()) return NULL; |
1896 HeapObject* object = HeapObject::cast(obj); | 2032 HeapObject* object = HeapObject::cast(obj); |
1897 HeapEntry* entry = entries_.Map(object); | 2033 HeapEntry* entry = entries_.Map(object); |
1898 // A new entry. | 2034 // A new entry. |
1899 if (entry == NULL) entry = filler_->AddEntry(object); | 2035 if (entry == NULL) entry = filler_->AddEntry(object); |
1900 return entry; | 2036 return entry; |
(...skipping 307 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2208 | 2344 |
2209 | 2345 |
2210 void HeapSnapshotGenerator::SetGcRootsReference(Object* child_obj) { | 2346 void HeapSnapshotGenerator::SetGcRootsReference(Object* child_obj) { |
2211 HeapEntry* child_entry = GetEntry(child_obj); | 2347 HeapEntry* child_entry = GetEntry(child_obj); |
2212 if (child_entry != NULL) { | 2348 if (child_entry != NULL) { |
2213 filler_->SetStrongRootReference(child_obj, child_entry); | 2349 filler_->SetStrongRootReference(child_obj, child_entry); |
2214 } | 2350 } |
2215 } | 2351 } |
2216 | 2352 |
2217 | 2353 |
2218 void HeapSnapshotGenerator::SetProgressTotal(int iterations_count) { | |
2219 if (control_ == NULL) return; | |
2220 | |
2221 HeapIterator iterator(HeapIterator::kPreciseFiltering); | |
2222 int objects_count = 0; | |
2223 for (HeapObject* obj = iterator.next(); | |
2224 obj != NULL; | |
2225 obj = iterator.next(), ++objects_count) {} | |
2226 progress_total_ = objects_count * iterations_count; | |
2227 progress_counter_ = 0; | |
2228 } | |
2229 | |
2230 | |
2231 bool HeapSnapshotGenerator::CountEntriesAndReferences() { | |
2232 SnapshotCounter counter(&entries_); | |
2233 filler_ = &counter; | |
2234 filler_->AddEntry(HeapSnapshot::kInternalRootObject); | |
2235 filler_->AddEntry(HeapSnapshot::kGcRootsObject); | |
2236 return IterateAndExtractReferences(); | |
2237 } | |
2238 | |
2239 | |
2240 bool HeapSnapshotGenerator::FillReferences() { | |
2241 SnapshotFiller filler(snapshot_, &entries_); | |
2242 filler_ = &filler; | |
2243 return IterateAndExtractReferences(); | |
2244 } | |
2245 | |
2246 | |
2247 void HeapSnapshotGenerator::FillReversePostorderIndexes( | |
2248 Vector<HeapEntry*>* entries) { | |
2249 snapshot_->ClearPaint(); | |
2250 int current_entry = 0; | |
2251 List<HeapEntry*> nodes_to_visit; | |
2252 nodes_to_visit.Add(snapshot_->root()); | |
2253 snapshot_->root()->paint_reachable(); | |
2254 while (!nodes_to_visit.is_empty()) { | |
2255 HeapEntry* entry = nodes_to_visit.last(); | |
2256 Vector<HeapGraphEdge> children = entry->children(); | |
2257 bool has_new_edges = false; | |
2258 for (int i = 0; i < children.length(); ++i) { | |
2259 if (children[i].type() == HeapGraphEdge::kShortcut) continue; | |
2260 HeapEntry* child = children[i].to(); | |
2261 if (!child->painted_reachable()) { | |
2262 nodes_to_visit.Add(child); | |
2263 child->paint_reachable(); | |
2264 has_new_edges = true; | |
2265 } | |
2266 } | |
2267 if (!has_new_edges) { | |
2268 entry->set_ordered_index(current_entry); | |
2269 (*entries)[current_entry++] = entry; | |
2270 nodes_to_visit.RemoveLast(); | |
2271 } | |
2272 } | |
2273 entries->Truncate(current_entry); | |
2274 } | |
2275 | |
2276 | |
2277 static int Intersect(int i1, int i2, const Vector<HeapEntry*>& dominators) { | |
2278 int finger1 = i1, finger2 = i2; | |
2279 while (finger1 != finger2) { | |
2280 while (finger1 < finger2) finger1 = dominators[finger1]->ordered_index(); | |
2281 while (finger2 < finger1) finger2 = dominators[finger2]->ordered_index(); | |
2282 } | |
2283 return finger1; | |
2284 } | |
2285 | |
2286 // The algorithm is based on the article: | |
2287 // K. Cooper, T. Harvey and K. Kennedy "A Simple, Fast Dominance Algorithm" | |
2288 // Softw. Pract. Exper. 4 (2001), pp. 1–10. | |
2289 bool HeapSnapshotGenerator::BuildDominatorTree( | |
2290 const Vector<HeapEntry*>& entries, | |
2291 Vector<HeapEntry*>* dominators) { | |
2292 if (entries.length() == 0) return true; | |
2293 const int entries_length = entries.length(), root_index = entries_length - 1; | |
2294 for (int i = 0; i < root_index; ++i) (*dominators)[i] = NULL; | |
2295 (*dominators)[root_index] = entries[root_index]; | |
2296 int changed = 1; | |
2297 const int base_progress_counter = progress_counter_; | |
2298 while (changed != 0) { | |
2299 changed = 0; | |
2300 for (int i = root_index - 1; i >= 0; --i) { | |
2301 HeapEntry* new_idom = NULL; | |
2302 Vector<HeapGraphEdge*> rets = entries[i]->retainers(); | |
2303 int j = 0; | |
2304 for (; j < rets.length(); ++j) { | |
2305 if (rets[j]->type() == HeapGraphEdge::kShortcut) continue; | |
2306 HeapEntry* ret = rets[j]->From(); | |
2307 if (dominators->at(ret->ordered_index()) != NULL) { | |
2308 new_idom = ret; | |
2309 break; | |
2310 } | |
2311 } | |
2312 for (++j; j < rets.length(); ++j) { | |
2313 if (rets[j]->type() == HeapGraphEdge::kShortcut) continue; | |
2314 HeapEntry* ret = rets[j]->From(); | |
2315 if (dominators->at(ret->ordered_index()) != NULL) { | |
2316 new_idom = entries[Intersect(ret->ordered_index(), | |
2317 new_idom->ordered_index(), | |
2318 *dominators)]; | |
2319 } | |
2320 } | |
2321 if (new_idom != NULL && dominators->at(i) != new_idom) { | |
2322 (*dominators)[i] = new_idom; | |
2323 ++changed; | |
2324 } | |
2325 } | |
2326 int remaining = entries_length - changed; | |
2327 if (remaining < 0) remaining = 0; | |
2328 progress_counter_ = base_progress_counter + remaining; | |
2329 if (!ReportProgress(true)) return false; | |
2330 } | |
2331 return true; | |
2332 } | |
2333 | |
2334 | |
2335 bool HeapSnapshotGenerator::SetEntriesDominators() { | |
2336 // This array is used for maintaining reverse postorder of nodes. | |
2337 ScopedVector<HeapEntry*> ordered_entries(snapshot_->entries()->length()); | |
2338 FillReversePostorderIndexes(&ordered_entries); | |
2339 ScopedVector<HeapEntry*> dominators(ordered_entries.length()); | |
2340 if (!BuildDominatorTree(ordered_entries, &dominators)) return false; | |
2341 for (int i = 0; i < ordered_entries.length(); ++i) { | |
2342 ASSERT(dominators[i] != NULL); | |
2343 ordered_entries[i]->set_dominator(dominators[i]); | |
2344 } | |
2345 // For nodes unreachable from root, set dominator to itself. | |
2346 snapshot_->SetDominatorsToSelf(); | |
2347 return true; | |
2348 } | |
2349 | |
2350 | |
2351 bool HeapSnapshotGenerator::ApproximateRetainedSizes() { | |
2352 // As for the dominators tree we only know parent nodes, not | |
2353 // children, to sum up total sizes we "bubble" node's self size | |
2354 // adding it to all of its parents. | |
2355 for (int i = 0; i < snapshot_->entries()->length(); ++i) { | |
2356 HeapEntry* entry = snapshot_->entries()->at(i); | |
2357 entry->set_retained_size(entry->self_size()); | |
2358 } | |
2359 for (int i = 0; | |
2360 i < snapshot_->entries()->length(); | |
2361 ++i, IncProgressCounter()) { | |
2362 HeapEntry* entry = snapshot_->entries()->at(i); | |
2363 int entry_size = entry->self_size(); | |
2364 for (HeapEntry* dominator = entry->dominator(); | |
2365 dominator != entry; | |
2366 entry = dominator, dominator = entry->dominator()) { | |
2367 dominator->add_retained_size(entry_size); | |
2368 } | |
2369 if (!ReportProgress()) return false; | |
2370 } | |
2371 return true; | |
2372 } | |
2373 | |
2374 | |
2375 bool HeapSnapshotGenerator::IterateAndExtractReferences() { | |
2376 HeapIterator iterator(HeapIterator::kPreciseFiltering); | |
2377 bool interrupted = false; | |
2378 // Heap iteration with precise filtering must be finished in any case. | |
2379 for (HeapObject* obj = iterator.next(); | |
2380 obj != NULL; | |
2381 obj = iterator.next(), IncProgressCounter()) { | |
2382 if (!interrupted) { | |
2383 ExtractReferences(obj); | |
2384 if (!ReportProgress()) interrupted = true; | |
2385 } | |
2386 } | |
2387 if (interrupted) return false; | |
2388 SetRootGcRootsReference(); | |
2389 RootsReferencesExtractor extractor(this); | |
2390 Heap::IterateRoots(&extractor, VISIT_ONLY_STRONG); | |
2391 return ReportProgress(); | |
2392 } | |
2393 | |
2394 | |
2395 void HeapSnapshotsDiff::CreateRoots(int additions_count, int deletions_count) { | 2354 void HeapSnapshotsDiff::CreateRoots(int additions_count, int deletions_count) { |
2396 raw_additions_root_ = | 2355 raw_additions_root_ = |
2397 NewArray<char>(HeapEntry::EntriesSize(1, additions_count, 0)); | 2356 NewArray<char>(HeapEntry::EntriesSize(1, additions_count, 0)); |
2398 additions_root()->Init( | 2357 additions_root()->Init( |
2399 snapshot2_, HeapEntry::kHidden, "", 0, 0, additions_count, 0); | 2358 snapshot2_, HeapEntry::kHidden, "", 0, 0, additions_count, 0); |
2400 raw_deletions_root_ = | 2359 raw_deletions_root_ = |
2401 NewArray<char>(HeapEntry::EntriesSize(1, deletions_count, 0)); | 2360 NewArray<char>(HeapEntry::EntriesSize(1, deletions_count, 0)); |
2402 deletions_root()->Init( | 2361 deletions_root()->Init( |
2403 snapshot1_, HeapEntry::kHidden, "", 0, 0, deletions_count, 0); | 2362 snapshot1_, HeapEntry::kHidden, "", 0, 0, deletions_count, 0); |
2404 } | 2363 } |
(...skipping 430 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2835 | 2794 |
2836 | 2795 |
2837 String* GetConstructorNameForHeapProfile(JSObject* object) { | 2796 String* GetConstructorNameForHeapProfile(JSObject* object) { |
2838 if (object->IsJSFunction()) return Heap::closure_symbol(); | 2797 if (object->IsJSFunction()) return Heap::closure_symbol(); |
2839 return object->constructor_name(); | 2798 return object->constructor_name(); |
2840 } | 2799 } |
2841 | 2800 |
2842 } } // namespace v8::internal | 2801 } } // namespace v8::internal |
2843 | 2802 |
2844 #endif // ENABLE_LOGGING_AND_PROFILING | 2803 #endif // ENABLE_LOGGING_AND_PROFILING |
OLD | NEW |