From 29614f3a7f84955e75dbdacdaa0abb18fc9e5231 Mon Sep 17 00:00:00 2001 From: Peter Varga Date: Fri, 23 Nov 2012 15:47:13 +0100 Subject: Updated V8 from git://github.com/v8/v8.git to 2215c442af2f0a4fce076e35ea061486d62778a1 Update V8 source to version 3.15.2 * Performance and stability improvements on all platforms. * Avoid overdeep recursion in regexp where a guarded expression with a minimum repetition count is inside another quantifier. * Exposed last seen heap object id via v8 public api. * Implemented heap profiler memory usage reporting. * Preserved error message during finally block in try..finally. * Improved heuristics to keep objects in fast mode with inherited constructors. * Fixed lazy sweeping heuristics to prevent old-space expansion. * Fixed sharing of literal boilerplates for optimized code. * Expose more detailed memory statistics. * Cleaned up hardfp ABI detection for ARM (V8 issue 2140). * Report "hidden properties" in heap profiler for properties case. * Added optimizing compiler support for JavaScript getters. * Fixed computation of call targets on prototypes in Crankshaft. * Fixed ICs for slow objects with native accessor. * Fixed transcendental cache on ARM in optimized code (issue 2234). * New heap inspection tools: counters for object sizes and counts, histograms for external fragmentation. * Added more support for heap analysis. * Interpret negative hexadecimal literals as NaN. (issue 2240) * Improved API calls that return empty handles. * Added checks for interceptors to negative lookup code in Crankshaft. * Introduced global contexts to represent lexical global scope(s). * Allocate block-scoped global bindings to global context. * Add empty-handle checks to API functions (#ifdef ENABLE_EXTRA_CHECKS) * Check the return value of API calls on ia32 and x64. * Activated fixed ES5 readonly semantics by default. * Added validity checking to API functions and calls. * Switched on code compaction on incremental GCs. * ARM: allowed VFP3 instructions when hardfloat is enabled. (Chromium issue 152506) * Killed off the SCons based build. (relevant for testing) * Added a faster API for creating v8::Integer objects. * Speeded up function deoptimization by avoiding quadratic pass over optimized function list. (Chromium issue 155270) * ES6: Added support for size to Set and Map (issue 2395) * ES6: Added support for Set and Map clear method (issue 2400) * Made formatting error message side-effect-free. (issue 2398) * Fixed V8 issues: 915, 1374, 1465, 1569, 1591, 1609 1645, 1804, 1914, 1981, 1991, 2016, 2017, 2034, 2077, 2087, 2094, 2119, 2120, 2133, 2134, 2139, 2143, 2151, 2156, 2166, 2170, 2172, 2177, 2179, 2185, 2193, 2194, 2201, 2210, 2212, 2219, 2220, 2225, 2239, 2245, 2252, 2260, 2261, 2294, 2297, 2308, 2312, 2313, 2317, 2318, 2322, 2326, 2364, 2372, 2380 Change-Id: Ifa82ec37b6150fdf1c4364c93987a32bbbf6bfd1 Reviewed-by: Simon Hausmann --- src/3rdparty/v8/src/profile-generator.cc | 507 ++++++++++--------------------- 1 file changed, 168 insertions(+), 339 deletions(-) (limited to 'src/3rdparty/v8/src/profile-generator.cc') diff --git a/src/3rdparty/v8/src/profile-generator.cc b/src/3rdparty/v8/src/profile-generator.cc index da2a969..9839edf 100644 --- a/src/3rdparty/v8/src/profile-generator.cc +++ b/src/3rdparty/v8/src/profile-generator.cc @@ -169,6 +169,15 @@ const char* StringsStorage::GetName(int index) { } +size_t StringsStorage::GetUsedMemorySize() const { + size_t size = sizeof(*this); + size += sizeof(HashMap::Entry) * names_.capacity(); + for (HashMap::Entry* p = names_.Start(); p != NULL; p = names_.Next(p)) { + size += strlen(reinterpret_cast(p->value)) + 1; + } + return size; +} + const char* const CodeEntry::kEmptyNamePrefix = ""; @@ -964,16 +973,10 @@ HeapEntry::HeapEntry(HeapSnapshot* snapshot, const char* name, SnapshotObjectId id, int self_size) - : painted_(false), - user_reachable_(false), - dominator_(kNoEntry), - type_(type), - retainers_count_(0), - retainers_index_(-1), + : type_(type), children_count_(0), children_index_(-1), self_size_(self_size), - retained_size_(0), id_(id), snapshot_(snapshot), name_(name) { } @@ -985,7 +988,6 @@ void HeapEntry::SetNamedReference(HeapGraphEdge::Type type, HeapGraphEdge edge(type, name, this->index(), entry->index()); snapshot_->edges().Add(edge); ++children_count_; - ++entry->retainers_count_; } @@ -995,7 +997,6 @@ void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type, HeapGraphEdge edge(type, index, this->index(), entry->index()); snapshot_->edges().Add(edge); ++children_count_; - ++entry->retainers_count_; } @@ -1007,9 +1008,8 @@ Handle HeapEntry::GetHeapObject() { void HeapEntry::Print( const char* prefix, const char* edge_name, int max_depth, int indent) { STATIC_CHECK(sizeof(unsigned) == sizeof(id())); - OS::Print("%6d %7d @%6u %*c %s%s: ", - self_size(), retained_size(), id(), - indent, ' ', prefix, edge_name); + OS::Print("%6d @%6u %*c %s%s: ", + self_size(), id(), indent, ' ', prefix, edge_name); if (type() != kString) { OS::Print("%s %.40s\n", TypeAsString(), name_); } else { @@ -1091,13 +1091,17 @@ template struct SnapshotSizeConstants; template <> struct SnapshotSizeConstants<4> { static const int kExpectedHeapGraphEdgeSize = 12; - static const int kExpectedHeapEntrySize = 40; + static const int kExpectedHeapEntrySize = 24; + static const int kExpectedHeapSnapshotsCollectionSize = 96; + static const int kExpectedHeapSnapshotSize = 136; static const size_t kMaxSerializableSnapshotRawSize = 256 * MB; }; template <> struct SnapshotSizeConstants<8> { static const int kExpectedHeapGraphEdgeSize = 24; - static const int kExpectedHeapEntrySize = 48; + static const int kExpectedHeapEntrySize = 32; + static const int kExpectedHeapSnapshotsCollectionSize = 144; + static const int kExpectedHeapSnapshotSize = 168; static const uint64_t kMaxSerializableSnapshotRawSize = static_cast(6000) * MB; }; @@ -1139,16 +1143,6 @@ void HeapSnapshot::RememberLastJSObjectId() { } -static void HeapEntryClearPaint(HeapEntry* entry_ptr) { - entry_ptr->clear_paint(); -} - - -void HeapSnapshot::ClearPaint() { - entries_.Iterate(HeapEntryClearPaint); -} - - HeapEntry* HeapSnapshot::AddRootEntry() { ASSERT(root_index_ == HeapEntry::kNoEntry); ASSERT(entries_.is_empty()); // Root entry must be the first one. @@ -1196,32 +1190,19 @@ HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type, } -void HeapSnapshot::FillChildrenAndRetainers() { +void HeapSnapshot::FillChildren() { ASSERT(children().is_empty()); children().Allocate(edges().length()); - ASSERT(retainers().is_empty()); - retainers().Allocate(edges().length()); int children_index = 0; - int retainers_index = 0; for (int i = 0; i < entries().length(); ++i) { HeapEntry* entry = &entries()[i]; children_index = entry->set_children_index(children_index); - retainers_index = entry->set_retainers_index(retainers_index); } ASSERT(edges().length() == children_index); - ASSERT(edges().length() == retainers_index); for (int i = 0; i < edges().length(); ++i) { HeapGraphEdge* edge = &edges()[i]; edge->ReplaceToIndexWithEntry(this); edge->from()->add_child(edge); - edge->to()->add_retainer(edge); - } -} - - -void HeapSnapshot::SetDominatorsToSelf() { - for (int i = 0; i < entries_.length(); ++i) { - entries_[i].set_dominator(&entries_[i]); } } @@ -1275,16 +1256,18 @@ void HeapSnapshot::Print(int max_depth) { template static size_t GetMemoryUsedByList(const List& list) { - return list.capacity() * sizeof(T); + return list.length() * sizeof(T) + sizeof(list); } size_t HeapSnapshot::RawSnapshotSize() const { + STATIC_CHECK(SnapshotSizeConstants::kExpectedHeapSnapshotSize == + sizeof(HeapSnapshot)); // NOLINT return + sizeof(*this) + GetMemoryUsedByList(entries_) + GetMemoryUsedByList(edges_) + GetMemoryUsedByList(children_) + - GetMemoryUsedByList(retainers_) + GetMemoryUsedByList(sorted_entries_); } @@ -1390,7 +1373,7 @@ void HeapObjectsMap::UpdateHeapObjectsMap() { } -void HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream) { +SnapshotObjectId HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream) { UpdateHeapObjectsMap(); time_intervals_.Add(TimeInterval(next_id_)); int prefered_chunk_size = stream->GetChunkSize(); @@ -1420,7 +1403,7 @@ void HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream) { if (stats_buffer.length() >= prefered_chunk_size) { OutputStream::WriteResult result = stream->WriteHeapStatsChunk( &stats_buffer.first(), stats_buffer.length()); - if (result == OutputStream::kAbort) return; + if (result == OutputStream::kAbort) return last_assigned_id(); stats_buffer.Clear(); } } @@ -1429,9 +1412,10 @@ void HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream) { if (!stats_buffer.is_empty()) { OutputStream::WriteResult result = stream->WriteHeapStatsChunk( &stats_buffer.first(), stats_buffer.length()); - if (result == OutputStream::kAbort) return; + if (result == OutputStream::kAbort) return last_assigned_id(); } stream->EndOfStream(); + return last_assigned_id(); } @@ -1478,6 +1462,15 @@ SnapshotObjectId HeapObjectsMap::GenerateId(v8::RetainedObjectInfo* info) { } +size_t HeapObjectsMap::GetUsedMemorySize() const { + return + sizeof(*this) + + sizeof(HashMap::Entry) * entries_map_.capacity() + + GetMemoryUsedByList(entries_) + + GetMemoryUsedByList(time_intervals_); +} + + HeapSnapshotsCollection::HeapSnapshotsCollection() : is_tracking_objects_(false), snapshots_uids_(HeapSnapshotsMatch), @@ -1557,6 +1550,22 @@ Handle HeapSnapshotsCollection::FindHeapObjectById( } +size_t HeapSnapshotsCollection::GetUsedMemorySize() const { + STATIC_CHECK(SnapshotSizeConstants:: + kExpectedHeapSnapshotsCollectionSize == + sizeof(HeapSnapshotsCollection)); // NOLINT + size_t size = sizeof(*this); + size += names_.GetUsedMemorySize(); + size += ids_.GetUsedMemorySize(); + size += sizeof(HashMap::Entry) * snapshots_uids_.capacity(); + size += GetMemoryUsedByList(snapshots_); + for (int i = 0; i < snapshots_.length(); ++i) { + size += snapshots_[i]->RawSnapshotSize(); + } + return size; +} + + HeapEntriesMap::HeapEntriesMap() : entries_(HeapThingsMatch) { } @@ -1702,8 +1711,8 @@ HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object) { name->IsString() ? collection_->names()->GetName(String::cast(name)) : ""); - } else if (object->IsGlobalContext()) { - return AddEntry(object, HeapEntry::kHidden, "system / GlobalContext"); + } else if (object->IsNativeContext()) { + return AddEntry(object, HeapEntry::kHidden, "system / NativeContext"); } else if (object->IsContext()) { return AddEntry(object, HeapEntry::kHidden, "system / Context"); } else if (object->IsFixedArray() || @@ -1937,8 +1946,8 @@ void V8HeapExplorer::ExtractJSObjectReferences( "builtins", global_obj->builtins(), GlobalObject::kBuiltinsOffset); SetInternalReference(global_obj, entry, - "global_context", global_obj->global_context(), - GlobalObject::kGlobalContextOffset); + "native_context", global_obj->native_context(), + GlobalObject::kNativeContextOffset); SetInternalReference(global_obj, entry, "global_receiver", global_obj->global_receiver(), GlobalObject::kGlobalReceiverOffset); @@ -1973,17 +1982,17 @@ void V8HeapExplorer::ExtractContextReferences(int entry, Context* context) { EXTRACT_CONTEXT_FIELD(CLOSURE_INDEX, JSFunction, closure); EXTRACT_CONTEXT_FIELD(PREVIOUS_INDEX, Context, previous); EXTRACT_CONTEXT_FIELD(EXTENSION_INDEX, Object, extension); - EXTRACT_CONTEXT_FIELD(GLOBAL_INDEX, GlobalObject, global); - if (context->IsGlobalContext()) { + EXTRACT_CONTEXT_FIELD(GLOBAL_OBJECT_INDEX, GlobalObject, global); + if (context->IsNativeContext()) { TagObject(context->jsfunction_result_caches(), "(context func. result caches)"); TagObject(context->normalized_map_cache(), "(context norm. map cache)"); TagObject(context->runtime_context(), "(runtime context)"); TagObject(context->data(), "(context data)"); - GLOBAL_CONTEXT_FIELDS(EXTRACT_CONTEXT_FIELD); + NATIVE_CONTEXT_FIELDS(EXTRACT_CONTEXT_FIELD); #undef EXTRACT_CONTEXT_FIELD for (int i = Context::FIRST_WEAK_SLOT; - i < Context::GLOBAL_CONTEXT_SLOTS; + i < Context::NATIVE_CONTEXT_SLOTS; ++i) { SetWeakReference(context, entry, i, context->get(i), FixedArray::OffsetOfElementAt(i)); @@ -1998,22 +2007,34 @@ void V8HeapExplorer::ExtractMapReferences(int entry, Map* map) { SetInternalReference(map, entry, "constructor", map->constructor(), Map::kConstructorOffset); - if (!map->instance_descriptors()->IsEmpty()) { - TagObject(map->instance_descriptors(), "(map descriptors)"); + if (map->HasTransitionArray()) { + TransitionArray* transitions = map->transitions(); + + Object* back_pointer = transitions->back_pointer_storage(); + TagObject(transitions->back_pointer_storage(), "(back pointer)"); + SetInternalReference(transitions, entry, + "backpointer", back_pointer, + TransitionArray::kBackPointerStorageOffset); + IndexedReferencesExtractor transitions_refs(this, transitions, entry); + transitions->Iterate(&transitions_refs); + + TagObject(transitions, "(transition array)"); SetInternalReference(map, entry, - "descriptors", map->instance_descriptors(), - Map::kInstanceDescriptorsOrBitField3Offset); - } - if (map->unchecked_prototype_transitions()->IsFixedArray()) { - TagObject(map->prototype_transitions(), "(prototype transitions)"); - SetInternalReference(map, entry, - "prototype_transitions", map->prototype_transitions(), - Map::kPrototypeTransitionsOrBackPointerOffset); + "transitions", transitions, + Map::kTransitionsOrBackPointerOffset); } else { + Object* back_pointer = map->GetBackPointer(); + TagObject(back_pointer, "(back pointer)"); SetInternalReference(map, entry, - "back_pointer", map->GetBackPointer(), - Map::kPrototypeTransitionsOrBackPointerOffset); + "backpointer", back_pointer, + Map::kTransitionsOrBackPointerOffset); } + DescriptorArray* descriptors = map->instance_descriptors(); + TagObject(descriptors, "(map descriptors)"); + SetInternalReference(map, entry, + "descriptors", descriptors, + Map::kDescriptorsOffset); + SetInternalReference(map, entry, "code_cache", map->code_cache(), Map::kCodeCacheOffset); @@ -2169,20 +2190,37 @@ void V8HeapExplorer::ExtractClosureReferences(JSObject* js_obj, int entry) { void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) { if (js_obj->HasFastProperties()) { DescriptorArray* descs = js_obj->map()->instance_descriptors(); + int real_size = js_obj->map()->NumberOfOwnDescriptors(); for (int i = 0; i < descs->number_of_descriptors(); i++) { + if (descs->GetDetails(i).descriptor_index() > real_size) continue; switch (descs->GetType(i)) { case FIELD: { int index = descs->GetFieldIndex(i); + + String* k = descs->GetKey(i); if (index < js_obj->map()->inobject_properties()) { - SetPropertyReference( - js_obj, entry, - descs->GetKey(i), js_obj->InObjectPropertyAt(index), - NULL, - js_obj->GetInObjectPropertyOffset(index)); + Object* value = js_obj->InObjectPropertyAt(index); + if (k != heap_->hidden_symbol()) { + SetPropertyReference( + js_obj, entry, + k, value, + NULL, + js_obj->GetInObjectPropertyOffset(index)); + } else { + TagObject(value, "(hidden properties)"); + SetInternalReference( + js_obj, entry, + "hidden_properties", value, + js_obj->GetInObjectPropertyOffset(index)); + } } else { - SetPropertyReference( - js_obj, entry, - descs->GetKey(i), js_obj->FastPropertyAt(index)); + Object* value = js_obj->FastPropertyAt(index); + if (k != heap_->hidden_symbol()) { + SetPropertyReference(js_obj, entry, k, value); + } else { + TagObject(value, "(hidden properties)"); + SetInternalReference(js_obj, entry, "hidden_properties", value); + } } break; } @@ -2209,10 +2247,10 @@ void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) { case NORMAL: // only in slow mode case HANDLER: // only in lookup results, not in descriptors case INTERCEPTOR: // only in lookup results, not in descriptors - case MAP_TRANSITION: // we do not care about transitions here... - case ELEMENTS_TRANSITION: - case CONSTANT_TRANSITION: - case NULL_DESCRIPTOR: // ... and not about "holes" + break; + case TRANSITION: + case NONEXISTENT: + UNREACHABLE(); break; } } @@ -2227,7 +2265,7 @@ void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) { Object* value = target->IsJSGlobalPropertyCell() ? JSGlobalPropertyCell::cast(target)->value() : target; - if (String::cast(k)->length() > 0) { + if (k != heap_->hidden_symbol()) { SetPropertyReference(js_obj, entry, String::cast(k), value); } else { TagObject(value, "(hidden properties)"); @@ -2240,7 +2278,7 @@ void V8HeapExplorer::ExtractPropertyReferences(JSObject* js_obj, int entry) { void V8HeapExplorer::ExtractElementReferences(JSObject* js_obj, int entry) { - if (js_obj->HasFastElements()) { + if (js_obj->HasFastObjectElements()) { FixedArray* elements = FixedArray::cast(js_obj->elements()); int length = js_obj->IsJSArray() ? Smi::cast(JSArray::cast(js_obj)->length())->value() : @@ -2286,11 +2324,12 @@ String* V8HeapExplorer::GetConstructorName(JSObject* object) { Object* constructor_prop = NULL; LookupResult result(heap->isolate()); object->LocalLookupRealNamedProperty(heap->constructor_symbol(), &result); - if (result.IsProperty()) { - constructor_prop = result.GetLazyValue(); - } + if (!result.IsFound()) return object->constructor_name(); + + constructor_prop = result.GetLazyValue(); if (constructor_prop->IsJSFunction()) { - Object* maybe_name = JSFunction::cast(constructor_prop)->shared()->name(); + Object* maybe_name = + JSFunction::cast(constructor_prop)->shared()->name(); if (maybe_name->IsString()) { String* name = String::cast(maybe_name); if (name->length() > 0) return name; @@ -2404,19 +2443,17 @@ bool V8HeapExplorer::IterateAndExtractReferences( bool V8HeapExplorer::IsEssentialObject(Object* object) { - // We have to use raw_unchecked_* versions because checked versions - // would fail during iteration over object properties. return object->IsHeapObject() && !object->IsOddball() - && object != heap_->raw_unchecked_empty_byte_array() - && object != heap_->raw_unchecked_empty_fixed_array() - && object != heap_->raw_unchecked_empty_descriptor_array() - && object != heap_->raw_unchecked_fixed_array_map() - && object != heap_->raw_unchecked_global_property_cell_map() - && object != heap_->raw_unchecked_shared_function_info_map() - && object != heap_->raw_unchecked_free_space_map() - && object != heap_->raw_unchecked_one_pointer_filler_map() - && object != heap_->raw_unchecked_two_pointer_filler_map(); + && object != heap_->empty_byte_array() + && object != heap_->empty_fixed_array() + && object != heap_->empty_descriptor_array() + && object != heap_->fixed_array_map() + && object != heap_->global_property_cell_map() + && object != heap_->shared_function_info_map() + && object != heap_->free_space_map() + && object != heap_->one_pointer_filler_map() + && object != heap_->two_pointer_filler_map(); } @@ -2552,20 +2589,6 @@ void V8HeapExplorer::SetPropertyReference(HeapObject* parent_obj, } -void V8HeapExplorer::SetPropertyShortcutReference(HeapObject* parent_obj, - int parent_entry, - String* reference_name, - Object* child_obj) { - HeapEntry* child_entry = GetEntry(child_obj); - if (child_entry != NULL) { - filler_->SetNamedReference(HeapGraphEdge::kShortcut, - parent_entry, - collection_->names()->GetName(reference_name), - child_entry); - } -} - - void V8HeapExplorer::SetRootGcRootsReference() { filler_->SetIndexedAutoIndexReference( HeapGraphEdge::kElement, @@ -2646,7 +2669,7 @@ class GlobalObjectsEnumerator : public ObjectVisitor { public: virtual void VisitPointers(Object** start, Object** end) { for (Object** p = start; p < end; p++) { - if ((*p)->IsGlobalContext()) { + if ((*p)->IsNativeContext()) { Context* context = Context::cast(*p); JSObject* proxy = context->global_proxy(); if (proxy->IsJSGlobalProxy()) { @@ -2684,6 +2707,10 @@ void V8HeapExplorer::TagGlobalObjects() { Object* obj_document; if (global_obj->GetProperty(*document_string)->ToObject(&obj_document) && obj_document->IsJSObject()) { + // FixMe: Workaround: SharedWorker's current Isolate has NULL context. + // As result GetProperty(*url_string) will crash. + if (!Isolate::Current()->context() && obj_document->IsJSGlobalProxy()) + continue; JSObject* document = JSObject::cast(obj_document); Object* obj_url; if (document->GetProperty(*url_string)->ToObject(&obj_url) && @@ -3066,37 +3093,34 @@ bool HeapSnapshotGenerator::GenerateSnapshot() { Heap::kMakeHeapIterableMask, "HeapSnapshotGenerator::GenerateSnapshot"); -#ifdef DEBUG +#ifdef VERIFY_HEAP Heap* debug_heap = Isolate::Current()->heap(); - ASSERT(!debug_heap->old_data_space()->was_swept_conservatively()); - ASSERT(!debug_heap->old_pointer_space()->was_swept_conservatively()); - ASSERT(!debug_heap->code_space()->was_swept_conservatively()); - ASSERT(!debug_heap->cell_space()->was_swept_conservatively()); - ASSERT(!debug_heap->map_space()->was_swept_conservatively()); + CHECK(!debug_heap->old_data_space()->was_swept_conservatively()); + CHECK(!debug_heap->old_pointer_space()->was_swept_conservatively()); + CHECK(!debug_heap->code_space()->was_swept_conservatively()); + CHECK(!debug_heap->cell_space()->was_swept_conservatively()); + CHECK(!debug_heap->map_space()->was_swept_conservatively()); #endif // The following code uses heap iterators, so we want the heap to be // stable. It should follow TagGlobalObjects as that can allocate. AssertNoAllocation no_alloc; -#ifdef DEBUG +#ifdef VERIFY_HEAP debug_heap->Verify(); #endif SetProgressTotal(1); // 1 pass. -#ifdef DEBUG +#ifdef VERIFY_HEAP debug_heap->Verify(); #endif if (!FillReferences()) return false; - snapshot_->FillChildrenAndRetainers(); + snapshot_->FillChildren(); snapshot_->RememberLastJSObjectId(); - if (!SetEntriesDominators()) return false; - if (!CalculateRetainedSizes()) return false; - progress_counter_ = progress_total_; if (!ProgressReport(true)) return false; return true; @@ -3138,187 +3162,6 @@ bool HeapSnapshotGenerator::FillReferences() { } -bool HeapSnapshotGenerator::IsUserGlobalReference(const HeapGraphEdge* edge) { - ASSERT(edge->from() == snapshot_->root()); - return edge->type() == HeapGraphEdge::kShortcut; -} - - -void HeapSnapshotGenerator::MarkUserReachableObjects() { - List worklist; - - Vector children = snapshot_->root()->children(); - for (int i = 0; i < children.length(); ++i) { - if (IsUserGlobalReference(children[i])) { - worklist.Add(children[i]->to()); - } - } - - while (!worklist.is_empty()) { - HeapEntry* entry = worklist.RemoveLast(); - if (entry->user_reachable()) continue; - entry->set_user_reachable(); - Vector children = entry->children(); - for (int i = 0; i < children.length(); ++i) { - HeapEntry* child = children[i]->to(); - if (!child->user_reachable()) { - worklist.Add(child); - } - } - } -} - - -static bool IsRetainingEdge(HeapGraphEdge* edge) { - if (edge->type() == HeapGraphEdge::kShortcut) return false; - // The edge is not retaining if it goes from system domain - // (i.e. an object not reachable from window) to the user domain - // (i.e. a reachable object). - return edge->from()->user_reachable() - || !edge->to()->user_reachable(); -} - - -void HeapSnapshotGenerator::FillPostorderIndexes( - Vector* entries) { - snapshot_->ClearPaint(); - int current_entry = 0; - List nodes_to_visit; - HeapEntry* root = snapshot_->root(); - nodes_to_visit.Add(root); - snapshot_->root()->paint(); - while (!nodes_to_visit.is_empty()) { - HeapEntry* entry = nodes_to_visit.last(); - Vector children = entry->children(); - bool has_new_edges = false; - for (int i = 0; i < children.length(); ++i) { - if (entry != root && !IsRetainingEdge(children[i])) continue; - HeapEntry* child = children[i]->to(); - if (!child->painted()) { - nodes_to_visit.Add(child); - child->paint(); - has_new_edges = true; - } - } - if (!has_new_edges) { - entry->set_postorder_index(current_entry); - (*entries)[current_entry++] = entry; - nodes_to_visit.RemoveLast(); - } - } - ASSERT_EQ(current_entry, entries->length()); -} - - -static int Intersect(int i1, int i2, const Vector& dominators) { - int finger1 = i1, finger2 = i2; - while (finger1 != finger2) { - while (finger1 < finger2) finger1 = dominators[finger1]; - while (finger2 < finger1) finger2 = dominators[finger2]; - } - 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& entries, - Vector* dominators) { - if (entries.length() == 0) return true; - HeapEntry* root = snapshot_->root(); - const int entries_length = entries.length(), root_index = entries_length - 1; - for (int i = 0; i < root_index; ++i) (*dominators)[i] = HeapEntry::kNoEntry; - (*dominators)[root_index] = root_index; - - // The affected array is used to mark entries which dominators - // have to be racalculated because of changes in their retainers. - ScopedVector affected(entries_length); - for (int i = 0; i < affected.length(); ++i) affected[i] = false; - // Mark the root direct children as affected. - Vector children = entries[root_index]->children(); - for (int i = 0; i < children.length(); ++i) { - affected[children[i]->to()->postorder_index()] = true; - } - - bool changed = true; - while (changed) { - changed = false; - if (!ProgressReport(false)) return false; - for (int i = root_index - 1; i >= 0; --i) { - if (!affected[i]) continue; - affected[i] = false; - // If dominator of the entry has already been set to root, - // then it can't propagate any further. - if ((*dominators)[i] == root_index) continue; - int new_idom_index = HeapEntry::kNoEntry; - Vector rets = entries[i]->retainers(); - for (int j = 0; j < rets.length(); ++j) { - if (rets[j]->from() != root && !IsRetainingEdge(rets[j])) continue; - int ret_index = rets[j]->from()->postorder_index(); - if (dominators->at(ret_index) != HeapEntry::kNoEntry) { - new_idom_index = new_idom_index == HeapEntry::kNoEntry - ? ret_index - : Intersect(ret_index, new_idom_index, *dominators); - // If idom has already reached the root, it doesn't make sense - // to check other retainers. - if (new_idom_index == root_index) break; - } - } - if (new_idom_index != HeapEntry::kNoEntry - && dominators->at(i) != new_idom_index) { - (*dominators)[i] = new_idom_index; - changed = true; - Vector children = entries[i]->children(); - for (int j = 0; j < children.length(); ++j) { - affected[children[j]->to()->postorder_index()] = true; - } - } - } - } - return true; -} - - -bool HeapSnapshotGenerator::SetEntriesDominators() { - MarkUserReachableObjects(); - // This array is used for maintaining postorder of nodes. - ScopedVector ordered_entries(snapshot_->entries().length()); - FillPostorderIndexes(&ordered_entries); - ScopedVector dominators(ordered_entries.length()); - if (!BuildDominatorTree(ordered_entries, &dominators)) return false; - for (int i = 0; i < ordered_entries.length(); ++i) { - ASSERT(dominators[i] != HeapEntry::kNoEntry); - ordered_entries[i]->set_dominator(ordered_entries[dominators[i]]); - } - return true; -} - - -bool HeapSnapshotGenerator::CalculateRetainedSizes() { - // 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. - List& entries = snapshot_->entries(); - for (int i = 0; i < entries.length(); ++i) { - HeapEntry* entry = &entries[i]; - entry->set_retained_size(entry->self_size()); - } - for (int i = 0; i < entries.length(); ++i) { - int entry_size = entries[i].self_size(); - HeapEntry* current = &entries[i]; - for (HeapEntry* dominator = current->dominator(); - dominator != current; - current = dominator, dominator = current->dominator()) { - ASSERT(current->dominator() != NULL); - dominator->add_retained_size(entry_size); - } - } - return true; -} - - template struct MaxDecimalDigitsIn; template<> struct MaxDecimalDigitsIn<4> { static const int kSigned = 11; @@ -3417,8 +3260,8 @@ class OutputStreamWriter { // type, name|index, to_node. const int HeapSnapshotJSONSerializer::kEdgeFieldsCount = 3; -// type, name, id, self_size, retained_size, dominator, children_index. -const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 7; +// type, name, id, self_size, children_index. +const int HeapSnapshotJSONSerializer::kNodeFieldsCount = 5; void HeapSnapshotJSONSerializer::Serialize(v8::OutputStream* stream) { ASSERT(writer_ == NULL); @@ -3458,14 +3301,12 @@ HeapSnapshot* HeapSnapshotJSONSerializer::CreateFakeSnapshot() { (snapshot_->RawSnapshotSize() + MB - 1) / MB); HeapEntry* message = result->AddEntry(HeapEntry::kString, text, 0, 4); result->root()->SetIndexedReference(HeapGraphEdge::kElement, 1, message); - result->FillChildrenAndRetainers(); - result->SetDominatorsToSelf(); + result->FillChildren(); return result; } void HeapSnapshotJSONSerializer::SerializeImpl() { - List& nodes = snapshot_->entries(); ASSERT(0 == snapshot_->root()->index()); writer_->AddCharacter('{'); writer_->AddString("\"snapshot\":{"); @@ -3473,11 +3314,11 @@ void HeapSnapshotJSONSerializer::SerializeImpl() { if (writer_->aborted()) return; writer_->AddString("},\n"); writer_->AddString("\"nodes\":["); - SerializeNodes(nodes); + SerializeNodes(); if (writer_->aborted()) return; writer_->AddString("],\n"); writer_->AddString("\"edges\":["); - SerializeEdges(nodes); + SerializeEdges(); if (writer_->aborted()) return; writer_->AddString("],\n"); writer_->AddString("\"strings\":["); @@ -3519,9 +3360,9 @@ static int utoa(unsigned value, const Vector& buffer, int buffer_pos) { void HeapSnapshotJSONSerializer::SerializeEdge(HeapGraphEdge* edge, bool first_edge) { - // The buffer needs space for 3 ints, 3 commas and \0 + // The buffer needs space for 3 unsigned ints, 3 commas, \n and \0 static const int kBufferSize = - MaxDecimalDigitsIn::kSigned * 3 + 3 + 1; // NOLINT + MaxDecimalDigitsIn::kUnsigned * 3 + 3 + 2; // NOLINT EmbeddedVector buffer; int edge_name_or_index = edge->type() == HeapGraphEdge::kElement || edge->type() == HeapGraphEdge::kHidden @@ -3536,32 +3377,28 @@ void HeapSnapshotJSONSerializer::SerializeEdge(HeapGraphEdge* edge, buffer_pos = utoa(edge_name_or_index, buffer, buffer_pos); buffer[buffer_pos++] = ','; buffer_pos = utoa(entry_index(edge->to()), buffer, buffer_pos); + buffer[buffer_pos++] = '\n'; buffer[buffer_pos++] = '\0'; writer_->AddString(buffer.start()); } -void HeapSnapshotJSONSerializer::SerializeEdges(const List& nodes) { - bool first_edge = true; - for (int i = 0; i < nodes.length(); ++i) { - HeapEntry* entry = &nodes[i]; - Vector children = entry->children(); - for (int j = 0; j < children.length(); ++j) { - SerializeEdge(children[j], first_edge); - first_edge = false; - if (writer_->aborted()) return; - } +void HeapSnapshotJSONSerializer::SerializeEdges() { + List& edges = snapshot_->children(); + for (int i = 0; i < edges.length(); ++i) { + ASSERT(i == 0 || + edges[i - 1]->from()->index() <= edges[i]->from()->index()); + SerializeEdge(edges[i], i == 0); + if (writer_->aborted()) return; } } -void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry, - int edges_index) { - // The buffer needs space for 6 ints, 1 uint32_t, 7 commas, \n and \0 +void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry) { + // The buffer needs space for 5 unsigned ints, 5 commas, \n and \0 static const int kBufferSize = - 6 * MaxDecimalDigitsIn::kSigned // NOLINT - + MaxDecimalDigitsIn::kUnsigned // NOLINT - + 7 + 1 + 1; + 5 * MaxDecimalDigitsIn::kUnsigned // NOLINT + + 5 + 1 + 1; EmbeddedVector buffer; int buffer_pos = 0; if (entry_index(entry) != 0) { @@ -3575,23 +3412,17 @@ void HeapSnapshotJSONSerializer::SerializeNode(HeapEntry* entry, buffer[buffer_pos++] = ','; buffer_pos = utoa(entry->self_size(), buffer, buffer_pos); buffer[buffer_pos++] = ','; - buffer_pos = utoa(entry->retained_size(), buffer, buffer_pos); - buffer[buffer_pos++] = ','; - buffer_pos = utoa(entry_index(entry->dominator()), buffer, buffer_pos); - buffer[buffer_pos++] = ','; - buffer_pos = utoa(edges_index, buffer, buffer_pos); + buffer_pos = utoa(entry->children_count(), buffer, buffer_pos); buffer[buffer_pos++] = '\n'; buffer[buffer_pos++] = '\0'; writer_->AddString(buffer.start()); } -void HeapSnapshotJSONSerializer::SerializeNodes(const List& nodes) { - int edges_index = 0; - for (int i = 0; i < nodes.length(); ++i) { - HeapEntry* entry = &nodes[i]; - SerializeNode(entry, edges_index); - edges_index += entry->children().length() * kEdgeFieldsCount; +void HeapSnapshotJSONSerializer::SerializeNodes() { + List& entries = snapshot_->entries(); + for (int i = 0; i < entries.length(); ++i) { + SerializeNode(&entries[i]); if (writer_->aborted()) return; } } @@ -3615,9 +3446,7 @@ void HeapSnapshotJSONSerializer::SerializeSnapshot() { JSON_S("name") "," JSON_S("id") "," JSON_S("self_size") "," - JSON_S("retained_size") "," - JSON_S("dominator") "," - JSON_S("edges_index")) "," + JSON_S("edge_count")) "," JSON_S("node_types") ":" JSON_A( JSON_A( JSON_S("hidden") "," -- cgit v1.2.3