1 // Copyright 2013 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_HEAP_SNAPSHOT_GENERATOR_H_ 6 #define V8_HEAP_SNAPSHOT_GENERATOR_H_ 7 8 #include "src/profile-generator-inl.h" 9 10 namespace v8 { 11 namespace internal { 12 13 class AllocationTracker; 14 class AllocationTraceNode; 15 class HeapEntry; 16 class HeapSnapshot; 17 class SnapshotFiller; 18 19 class HeapGraphEdge BASE_EMBEDDED { 20 public: 21 enum Type { 22 kContextVariable = v8::HeapGraphEdge::kContextVariable, 23 kElement = v8::HeapGraphEdge::kElement, 24 kProperty = v8::HeapGraphEdge::kProperty, 25 kInternal = v8::HeapGraphEdge::kInternal, 26 kHidden = v8::HeapGraphEdge::kHidden, 27 kShortcut = v8::HeapGraphEdge::kShortcut, 28 kWeak = v8::HeapGraphEdge::kWeak 29 }; 30 HeapGraphEdge()31 HeapGraphEdge() { } 32 HeapGraphEdge(Type type, const char* name, int from, int to); 33 HeapGraphEdge(Type type, int index, int from, int to); 34 void ReplaceToIndexWithEntry(HeapSnapshot* snapshot); 35 type()36 Type type() const { return static_cast<Type>(type_); } index()37 int index() const { 38 ASSERT(type_ == kElement || type_ == kHidden); 39 return index_; 40 } name()41 const char* name() const { 42 ASSERT(type_ == kContextVariable 43 || type_ == kProperty 44 || type_ == kInternal 45 || type_ == kShortcut 46 || type_ == kWeak); 47 return name_; 48 } 49 INLINE(HeapEntry* from() const); to()50 HeapEntry* to() const { return to_entry_; } 51 52 private: 53 INLINE(HeapSnapshot* snapshot() const); 54 55 unsigned type_ : 3; 56 int from_index_ : 29; 57 union { 58 // During entries population |to_index_| is used for storing the index, 59 // afterwards it is replaced with a pointer to the entry. 60 int to_index_; 61 HeapEntry* to_entry_; 62 }; 63 union { 64 int index_; 65 const char* name_; 66 }; 67 }; 68 69 70 // HeapEntry instances represent an entity from the heap (or a special 71 // virtual node, e.g. root). 72 class HeapEntry BASE_EMBEDDED { 73 public: 74 enum Type { 75 kHidden = v8::HeapGraphNode::kHidden, 76 kArray = v8::HeapGraphNode::kArray, 77 kString = v8::HeapGraphNode::kString, 78 kObject = v8::HeapGraphNode::kObject, 79 kCode = v8::HeapGraphNode::kCode, 80 kClosure = v8::HeapGraphNode::kClosure, 81 kRegExp = v8::HeapGraphNode::kRegExp, 82 kHeapNumber = v8::HeapGraphNode::kHeapNumber, 83 kNative = v8::HeapGraphNode::kNative, 84 kSynthetic = v8::HeapGraphNode::kSynthetic, 85 kConsString = v8::HeapGraphNode::kConsString, 86 kSlicedString = v8::HeapGraphNode::kSlicedString, 87 kSymbol = v8::HeapGraphNode::kSymbol 88 }; 89 static const int kNoEntry; 90 HeapEntry()91 HeapEntry() { } 92 HeapEntry(HeapSnapshot* snapshot, 93 Type type, 94 const char* name, 95 SnapshotObjectId id, 96 size_t self_size, 97 unsigned trace_node_id); 98 snapshot()99 HeapSnapshot* snapshot() { return snapshot_; } type()100 Type type() { return static_cast<Type>(type_); } name()101 const char* name() { return name_; } set_name(const char * name)102 void set_name(const char* name) { name_ = name; } id()103 inline SnapshotObjectId id() { return id_; } self_size()104 size_t self_size() { return self_size_; } trace_node_id()105 unsigned trace_node_id() const { return trace_node_id_; } 106 INLINE(int index() const); children_count()107 int children_count() const { return children_count_; } 108 INLINE(int set_children_index(int index)); add_child(HeapGraphEdge * edge)109 void add_child(HeapGraphEdge* edge) { 110 children_arr()[children_count_++] = edge; 111 } children()112 Vector<HeapGraphEdge*> children() { 113 return Vector<HeapGraphEdge*>(children_arr(), children_count_); } 114 115 void SetIndexedReference( 116 HeapGraphEdge::Type type, int index, HeapEntry* entry); 117 void SetNamedReference( 118 HeapGraphEdge::Type type, const char* name, HeapEntry* entry); 119 120 void Print( 121 const char* prefix, const char* edge_name, int max_depth, int indent); 122 123 private: 124 INLINE(HeapGraphEdge** children_arr()); 125 const char* TypeAsString(); 126 127 unsigned type_: 4; 128 int children_count_: 28; 129 int children_index_; 130 size_t self_size_; 131 HeapSnapshot* snapshot_; 132 const char* name_; 133 SnapshotObjectId id_; 134 // id of allocation stack trace top node 135 unsigned trace_node_id_; 136 }; 137 138 139 // HeapSnapshot represents a single heap snapshot. It is stored in 140 // HeapProfiler, which is also a factory for 141 // HeapSnapshots. All HeapSnapshots share strings copied from JS heap 142 // to be able to return them even if they were collected. 143 // HeapSnapshotGenerator fills in a HeapSnapshot. 144 class HeapSnapshot { 145 public: 146 HeapSnapshot(HeapProfiler* profiler, 147 const char* title, 148 unsigned uid); 149 void Delete(); 150 profiler()151 HeapProfiler* profiler() { return profiler_; } title()152 const char* title() { return title_; } uid()153 unsigned uid() { return uid_; } 154 size_t RawSnapshotSize() const; root()155 HeapEntry* root() { return &entries_[root_index_]; } gc_roots()156 HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; } natives_root()157 HeapEntry* natives_root() { return &entries_[natives_root_index_]; } gc_subroot(int index)158 HeapEntry* gc_subroot(int index) { 159 return &entries_[gc_subroot_indexes_[index]]; 160 } entries()161 List<HeapEntry>& entries() { return entries_; } edges()162 List<HeapGraphEdge>& edges() { return edges_; } children()163 List<HeapGraphEdge*>& children() { return children_; } 164 void RememberLastJSObjectId(); max_snapshot_js_object_id()165 SnapshotObjectId max_snapshot_js_object_id() const { 166 return max_snapshot_js_object_id_; 167 } 168 169 HeapEntry* AddEntry(HeapEntry::Type type, 170 const char* name, 171 SnapshotObjectId id, 172 size_t size, 173 unsigned trace_node_id); 174 HeapEntry* AddRootEntry(); 175 HeapEntry* AddGcRootsEntry(); 176 HeapEntry* AddGcSubrootEntry(int tag); 177 HeapEntry* AddNativesRootEntry(); 178 HeapEntry* GetEntryById(SnapshotObjectId id); 179 List<HeapEntry*>* GetSortedEntriesList(); 180 void FillChildren(); 181 182 void Print(int max_depth); 183 void PrintEntriesSize(); 184 185 private: 186 HeapProfiler* profiler_; 187 const char* title_; 188 unsigned uid_; 189 int root_index_; 190 int gc_roots_index_; 191 int natives_root_index_; 192 int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags]; 193 List<HeapEntry> entries_; 194 List<HeapGraphEdge> edges_; 195 List<HeapGraphEdge*> children_; 196 List<HeapEntry*> sorted_entries_; 197 SnapshotObjectId max_snapshot_js_object_id_; 198 199 friend class HeapSnapshotTester; 200 201 DISALLOW_COPY_AND_ASSIGN(HeapSnapshot); 202 }; 203 204 205 class HeapObjectsMap { 206 public: 207 explicit HeapObjectsMap(Heap* heap); 208 heap()209 Heap* heap() const { return heap_; } 210 211 SnapshotObjectId FindEntry(Address addr); 212 SnapshotObjectId FindOrAddEntry(Address addr, 213 unsigned int size, 214 bool accessed = true); 215 bool MoveObject(Address from, Address to, int size); 216 void UpdateObjectSize(Address addr, int size); last_assigned_id()217 SnapshotObjectId last_assigned_id() const { 218 return next_id_ - kObjectIdStep; 219 } 220 221 void StopHeapObjectsTracking(); 222 SnapshotObjectId PushHeapObjectsStats(OutputStream* stream); 223 size_t GetUsedMemorySize() const; 224 225 SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info); 226 static inline SnapshotObjectId GetNthGcSubrootId(int delta); 227 228 static const int kObjectIdStep = 2; 229 static const SnapshotObjectId kInternalRootObjectId; 230 static const SnapshotObjectId kGcRootsObjectId; 231 static const SnapshotObjectId kNativesRootObjectId; 232 static const SnapshotObjectId kGcRootsFirstSubrootId; 233 static const SnapshotObjectId kFirstAvailableObjectId; 234 235 int FindUntrackedObjects(); 236 237 void UpdateHeapObjectsMap(); 238 void RemoveDeadEntries(); 239 240 private: 241 struct EntryInfo { EntryInfoEntryInfo242 EntryInfo(SnapshotObjectId id, Address addr, unsigned int size) 243 : id(id), addr(addr), size(size), accessed(true) { } EntryInfoEntryInfo244 EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed) 245 : id(id), addr(addr), size(size), accessed(accessed) { } 246 SnapshotObjectId id; 247 Address addr; 248 unsigned int size; 249 bool accessed; 250 }; 251 struct TimeInterval { TimeIntervalTimeInterval252 explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { } 253 SnapshotObjectId id; 254 uint32_t size; 255 uint32_t count; 256 }; 257 258 SnapshotObjectId next_id_; 259 HashMap entries_map_; 260 List<EntryInfo> entries_; 261 List<TimeInterval> time_intervals_; 262 Heap* heap_; 263 264 DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap); 265 }; 266 267 268 // A typedef for referencing anything that can be snapshotted living 269 // in any kind of heap memory. 270 typedef void* HeapThing; 271 272 273 // An interface that creates HeapEntries by HeapThings. 274 class HeapEntriesAllocator { 275 public: ~HeapEntriesAllocator()276 virtual ~HeapEntriesAllocator() { } 277 virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0; 278 }; 279 280 281 // The HeapEntriesMap instance is used to track a mapping between 282 // real heap objects and their representations in heap snapshots. 283 class HeapEntriesMap { 284 public: 285 HeapEntriesMap(); 286 287 int Map(HeapThing thing); 288 void Pair(HeapThing thing, int entry); 289 290 private: Hash(HeapThing thing)291 static uint32_t Hash(HeapThing thing) { 292 return ComputeIntegerHash( 293 static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)), 294 v8::internal::kZeroHashSeed); 295 } 296 297 HashMap entries_; 298 299 friend class HeapObjectsSet; 300 301 DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap); 302 }; 303 304 305 class HeapObjectsSet { 306 public: 307 HeapObjectsSet(); 308 void Clear(); 309 bool Contains(Object* object); 310 void Insert(Object* obj); 311 const char* GetTag(Object* obj); 312 void SetTag(Object* obj, const char* tag); is_empty()313 bool is_empty() const { return entries_.occupancy() == 0; } 314 315 private: 316 HashMap entries_; 317 318 DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet); 319 }; 320 321 322 class SnapshottingProgressReportingInterface { 323 public: ~SnapshottingProgressReportingInterface()324 virtual ~SnapshottingProgressReportingInterface() { } 325 virtual void ProgressStep() = 0; 326 virtual bool ProgressReport(bool force) = 0; 327 }; 328 329 330 // An implementation of V8 heap graph extractor. 331 class V8HeapExplorer : public HeapEntriesAllocator { 332 public: 333 V8HeapExplorer(HeapSnapshot* snapshot, 334 SnapshottingProgressReportingInterface* progress, 335 v8::HeapProfiler::ObjectNameResolver* resolver); 336 virtual ~V8HeapExplorer(); 337 virtual HeapEntry* AllocateEntry(HeapThing ptr); 338 void AddRootEntries(SnapshotFiller* filler); 339 int EstimateObjectsCount(HeapIterator* iterator); 340 bool IterateAndExtractReferences(SnapshotFiller* filler); 341 void TagGlobalObjects(); 342 void TagCodeObject(Code* code); 343 void TagBuiltinCodeObject(Code* code, const char* name); 344 HeapEntry* AddEntry(Address address, 345 HeapEntry::Type type, 346 const char* name, 347 size_t size); 348 349 static String* GetConstructorName(JSObject* object); 350 351 static HeapObject* const kInternalRootObject; 352 353 private: 354 typedef bool (V8HeapExplorer::*ExtractReferencesMethod)(int entry, 355 HeapObject* object); 356 357 HeapEntry* AddEntry(HeapObject* object); 358 HeapEntry* AddEntry(HeapObject* object, 359 HeapEntry::Type type, 360 const char* name); 361 362 const char* GetSystemEntryName(HeapObject* object); 363 364 template<V8HeapExplorer::ExtractReferencesMethod extractor> 365 bool IterateAndExtractSinglePass(); 366 367 bool ExtractReferencesPass1(int entry, HeapObject* obj); 368 bool ExtractReferencesPass2(int entry, HeapObject* obj); 369 void ExtractJSGlobalProxyReferences(int entry, JSGlobalProxy* proxy); 370 void ExtractJSObjectReferences(int entry, JSObject* js_obj); 371 void ExtractStringReferences(int entry, String* obj); 372 void ExtractSymbolReferences(int entry, Symbol* symbol); 373 void ExtractJSWeakCollectionReferences(int entry, 374 JSWeakCollection* collection); 375 void ExtractContextReferences(int entry, Context* context); 376 void ExtractMapReferences(int entry, Map* map); 377 void ExtractSharedFunctionInfoReferences(int entry, 378 SharedFunctionInfo* shared); 379 void ExtractScriptReferences(int entry, Script* script); 380 void ExtractAccessorPairReferences(int entry, AccessorPair* accessors); 381 void ExtractCodeCacheReferences(int entry, CodeCache* code_cache); 382 void ExtractCodeReferences(int entry, Code* code); 383 void ExtractBoxReferences(int entry, Box* box); 384 void ExtractCellReferences(int entry, Cell* cell); 385 void ExtractPropertyCellReferences(int entry, PropertyCell* cell); 386 void ExtractAllocationSiteReferences(int entry, AllocationSite* site); 387 void ExtractJSArrayBufferReferences(int entry, JSArrayBuffer* buffer); 388 void ExtractFixedArrayReferences(int entry, FixedArray* array); 389 void ExtractClosureReferences(JSObject* js_obj, int entry); 390 void ExtractPropertyReferences(JSObject* js_obj, int entry); 391 bool ExtractAccessorPairProperty(JSObject* js_obj, int entry, 392 Object* key, Object* callback_obj); 393 void ExtractElementReferences(JSObject* js_obj, int entry); 394 void ExtractInternalReferences(JSObject* js_obj, int entry); 395 396 bool IsEssentialObject(Object* object); 397 void SetContextReference(HeapObject* parent_obj, 398 int parent, 399 String* reference_name, 400 Object* child, 401 int field_offset); 402 void SetNativeBindReference(HeapObject* parent_obj, 403 int parent, 404 const char* reference_name, 405 Object* child); 406 void SetElementReference(HeapObject* parent_obj, 407 int parent, 408 int index, 409 Object* child); 410 void SetInternalReference(HeapObject* parent_obj, 411 int parent, 412 const char* reference_name, 413 Object* child, 414 int field_offset = -1); 415 void SetInternalReference(HeapObject* parent_obj, 416 int parent, 417 int index, 418 Object* child, 419 int field_offset = -1); 420 void SetHiddenReference(HeapObject* parent_obj, 421 int parent, 422 int index, 423 Object* child); 424 void SetWeakReference(HeapObject* parent_obj, 425 int parent, 426 const char* reference_name, 427 Object* child_obj, 428 int field_offset); 429 void SetWeakReference(HeapObject* parent_obj, 430 int parent, 431 int index, 432 Object* child_obj, 433 int field_offset); 434 void SetPropertyReference(HeapObject* parent_obj, 435 int parent, 436 Name* reference_name, 437 Object* child, 438 const char* name_format_string = NULL, 439 int field_offset = -1); 440 void SetUserGlobalReference(Object* user_global); 441 void SetRootGcRootsReference(); 442 void SetGcRootsReference(VisitorSynchronization::SyncTag tag); 443 void SetGcSubrootReference( 444 VisitorSynchronization::SyncTag tag, bool is_weak, Object* child); 445 const char* GetStrongGcSubrootName(Object* object); 446 void TagObject(Object* obj, const char* tag); 447 void MarkAsWeakContainer(Object* object); 448 449 HeapEntry* GetEntry(Object* obj); 450 451 static inline HeapObject* GetNthGcSubrootObject(int delta); 452 static inline int GetGcSubrootOrder(HeapObject* subroot); 453 454 Heap* heap_; 455 HeapSnapshot* snapshot_; 456 StringsStorage* names_; 457 HeapObjectsMap* heap_object_map_; 458 SnapshottingProgressReportingInterface* progress_; 459 SnapshotFiller* filler_; 460 HeapObjectsSet objects_tags_; 461 HeapObjectsSet strong_gc_subroot_names_; 462 HeapObjectsSet user_roots_; 463 HeapObjectsSet weak_containers_; 464 v8::HeapProfiler::ObjectNameResolver* global_object_name_resolver_; 465 466 static HeapObject* const kGcRootsObject; 467 static HeapObject* const kFirstGcSubrootObject; 468 static HeapObject* const kLastGcSubrootObject; 469 470 friend class IndexedReferencesExtractor; 471 friend class GcSubrootsEnumerator; 472 friend class RootsReferencesExtractor; 473 474 DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer); 475 }; 476 477 478 class NativeGroupRetainedObjectInfo; 479 480 481 // An implementation of retained native objects extractor. 482 class NativeObjectsExplorer { 483 public: 484 NativeObjectsExplorer(HeapSnapshot* snapshot, 485 SnapshottingProgressReportingInterface* progress); 486 virtual ~NativeObjectsExplorer(); 487 void AddRootEntries(SnapshotFiller* filler); 488 int EstimateObjectsCount(); 489 bool IterateAndExtractReferences(SnapshotFiller* filler); 490 491 private: 492 void FillRetainedObjects(); 493 void FillImplicitReferences(); 494 List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info); 495 void SetNativeRootReference(v8::RetainedObjectInfo* info); 496 void SetRootNativeRootsReference(); 497 void SetWrapperNativeReferences(HeapObject* wrapper, 498 v8::RetainedObjectInfo* info); 499 void VisitSubtreeWrapper(Object** p, uint16_t class_id); 500 InfoHash(v8::RetainedObjectInfo * info)501 static uint32_t InfoHash(v8::RetainedObjectInfo* info) { 502 return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()), 503 v8::internal::kZeroHashSeed); 504 } RetainedInfosMatch(void * key1,void * key2)505 static bool RetainedInfosMatch(void* key1, void* key2) { 506 return key1 == key2 || 507 (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent( 508 reinterpret_cast<v8::RetainedObjectInfo*>(key2)); 509 } INLINE(static bool StringsMatch (void * key1,void * key2))510 INLINE(static bool StringsMatch(void* key1, void* key2)) { 511 return strcmp(reinterpret_cast<char*>(key1), 512 reinterpret_cast<char*>(key2)) == 0; 513 } 514 515 NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label); 516 517 Isolate* isolate_; 518 HeapSnapshot* snapshot_; 519 StringsStorage* names_; 520 SnapshottingProgressReportingInterface* progress_; 521 bool embedder_queried_; 522 HeapObjectsSet in_groups_; 523 // RetainedObjectInfo* -> List<HeapObject*>* 524 HashMap objects_by_info_; 525 HashMap native_groups_; 526 HeapEntriesAllocator* synthetic_entries_allocator_; 527 HeapEntriesAllocator* native_entries_allocator_; 528 // Used during references extraction. 529 SnapshotFiller* filler_; 530 531 static HeapThing const kNativesRootObject; 532 533 friend class GlobalHandlesExtractor; 534 535 DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer); 536 }; 537 538 539 class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface { 540 public: 541 HeapSnapshotGenerator(HeapSnapshot* snapshot, 542 v8::ActivityControl* control, 543 v8::HeapProfiler::ObjectNameResolver* resolver, 544 Heap* heap); 545 bool GenerateSnapshot(); 546 547 private: 548 bool FillReferences(); 549 void ProgressStep(); 550 bool ProgressReport(bool force = false); 551 void SetProgressTotal(int iterations_count); 552 553 HeapSnapshot* snapshot_; 554 v8::ActivityControl* control_; 555 V8HeapExplorer v8_heap_explorer_; 556 NativeObjectsExplorer dom_explorer_; 557 // Mapping from HeapThing pointers to HeapEntry* pointers. 558 HeapEntriesMap entries_; 559 // Used during snapshot generation. 560 int progress_counter_; 561 int progress_total_; 562 Heap* heap_; 563 564 DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator); 565 }; 566 567 class OutputStreamWriter; 568 569 class HeapSnapshotJSONSerializer { 570 public: HeapSnapshotJSONSerializer(HeapSnapshot * snapshot)571 explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot) 572 : snapshot_(snapshot), 573 strings_(StringsMatch), 574 next_node_id_(1), 575 next_string_id_(1), 576 writer_(NULL) { 577 } 578 void Serialize(v8::OutputStream* stream); 579 580 private: INLINE(static bool StringsMatch (void * key1,void * key2))581 INLINE(static bool StringsMatch(void* key1, void* key2)) { 582 return strcmp(reinterpret_cast<char*>(key1), 583 reinterpret_cast<char*>(key2)) == 0; 584 } 585 INLINE(static uint32_t StringHash (const void * string))586 INLINE(static uint32_t StringHash(const void* string)) { 587 const char* s = reinterpret_cast<const char*>(string); 588 int len = static_cast<int>(strlen(s)); 589 return StringHasher::HashSequentialString( 590 s, len, v8::internal::kZeroHashSeed); 591 } 592 593 int GetStringId(const char* s); entry_index(HeapEntry * e)594 int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; } 595 void SerializeEdge(HeapGraphEdge* edge, bool first_edge); 596 void SerializeEdges(); 597 void SerializeImpl(); 598 void SerializeNode(HeapEntry* entry); 599 void SerializeNodes(); 600 void SerializeSnapshot(); 601 void SerializeTraceTree(); 602 void SerializeTraceNode(AllocationTraceNode* node); 603 void SerializeTraceNodeInfos(); 604 void SerializeString(const unsigned char* s); 605 void SerializeStrings(); 606 607 static const int kEdgeFieldsCount; 608 static const int kNodeFieldsCount; 609 610 HeapSnapshot* snapshot_; 611 HashMap strings_; 612 int next_node_id_; 613 int next_string_id_; 614 OutputStreamWriter* writer_; 615 616 friend class HeapSnapshotJSONSerializerEnumerator; 617 friend class HeapSnapshotJSONSerializerIterator; 618 619 DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer); 620 }; 621 622 623 } } // namespace v8::internal 624 625 #endif // V8_HEAP_SNAPSHOT_GENERATOR_H_ 626