• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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     DCHECK(type_ == kElement || type_ == kHidden);
39     return index_;
40   }
name()41   const char* name() const {
42     DCHECK(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   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_]; }
gc_subroot(int index)157   HeapEntry* gc_subroot(int index) {
158     return &entries_[gc_subroot_indexes_[index]];
159   }
entries()160   List<HeapEntry>& entries() { return entries_; }
edges()161   List<HeapGraphEdge>& edges() { return edges_; }
children()162   List<HeapGraphEdge*>& children() { return children_; }
163   void RememberLastJSObjectId();
max_snapshot_js_object_id()164   SnapshotObjectId max_snapshot_js_object_id() const {
165     return max_snapshot_js_object_id_;
166   }
167 
168   HeapEntry* AddEntry(HeapEntry::Type type,
169                       const char* name,
170                       SnapshotObjectId id,
171                       size_t size,
172                       unsigned trace_node_id);
173   void AddSyntheticRootEntries();
174   HeapEntry* GetEntryById(SnapshotObjectId id);
175   List<HeapEntry*>* GetSortedEntriesList();
176   void FillChildren();
177 
178   void Print(int max_depth);
179   void PrintEntriesSize();
180 
181  private:
182   HeapEntry* AddRootEntry();
183   HeapEntry* AddGcRootsEntry();
184   HeapEntry* AddGcSubrootEntry(int tag, SnapshotObjectId id);
185 
186   HeapProfiler* profiler_;
187   const char* title_;
188   unsigned uid_;
189   int root_index_;
190   int gc_roots_index_;
191   int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags];
192   List<HeapEntry> entries_;
193   List<HeapGraphEdge> edges_;
194   List<HeapGraphEdge*> children_;
195   List<HeapEntry*> sorted_entries_;
196   SnapshotObjectId max_snapshot_js_object_id_;
197 
198   friend class HeapSnapshotTester;
199 
200   DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
201 };
202 
203 
204 class HeapObjectsMap {
205  public:
206   explicit HeapObjectsMap(Heap* heap);
207 
heap()208   Heap* heap() const { return heap_; }
209 
210   SnapshotObjectId FindEntry(Address addr);
211   SnapshotObjectId FindOrAddEntry(Address addr,
212                                   unsigned int size,
213                                   bool accessed = true);
214   bool MoveObject(Address from, Address to, int size);
215   void UpdateObjectSize(Address addr, int size);
last_assigned_id()216   SnapshotObjectId last_assigned_id() const {
217     return next_id_ - kObjectIdStep;
218   }
219 
220   void StopHeapObjectsTracking();
221   SnapshotObjectId PushHeapObjectsStats(OutputStream* stream);
222   size_t GetUsedMemorySize() const;
223 
224   SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info);
225 
226   static const int kObjectIdStep = 2;
227   static const SnapshotObjectId kInternalRootObjectId;
228   static const SnapshotObjectId kGcRootsObjectId;
229   static const SnapshotObjectId kGcRootsFirstSubrootId;
230   static const SnapshotObjectId kFirstAvailableObjectId;
231 
232   int FindUntrackedObjects();
233 
234   void UpdateHeapObjectsMap();
235   void RemoveDeadEntries();
236 
237  private:
238   struct EntryInfo {
EntryInfoEntryInfo239   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
240       : id(id), addr(addr), size(size), accessed(true) { }
EntryInfoEntryInfo241   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed)
242       : id(id), addr(addr), size(size), accessed(accessed) { }
243     SnapshotObjectId id;
244     Address addr;
245     unsigned int size;
246     bool accessed;
247   };
248   struct TimeInterval {
TimeIntervalTimeInterval249     explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { }
250     SnapshotObjectId id;
251     uint32_t size;
252     uint32_t count;
253   };
254 
255   SnapshotObjectId next_id_;
256   HashMap entries_map_;
257   List<EntryInfo> entries_;
258   List<TimeInterval> time_intervals_;
259   Heap* heap_;
260 
261   DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
262 };
263 
264 
265 // A typedef for referencing anything that can be snapshotted living
266 // in any kind of heap memory.
267 typedef void* HeapThing;
268 
269 
270 // An interface that creates HeapEntries by HeapThings.
271 class HeapEntriesAllocator {
272  public:
~HeapEntriesAllocator()273   virtual ~HeapEntriesAllocator() { }
274   virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
275 };
276 
277 
278 // The HeapEntriesMap instance is used to track a mapping between
279 // real heap objects and their representations in heap snapshots.
280 class HeapEntriesMap {
281  public:
282   HeapEntriesMap();
283 
284   int Map(HeapThing thing);
285   void Pair(HeapThing thing, int entry);
286 
287  private:
Hash(HeapThing thing)288   static uint32_t Hash(HeapThing thing) {
289     return ComputeIntegerHash(
290         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
291         v8::internal::kZeroHashSeed);
292   }
293 
294   HashMap entries_;
295 
296   friend class HeapObjectsSet;
297 
298   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
299 };
300 
301 
302 class HeapObjectsSet {
303  public:
304   HeapObjectsSet();
305   void Clear();
306   bool Contains(Object* object);
307   void Insert(Object* obj);
308   const char* GetTag(Object* obj);
309   void SetTag(Object* obj, const char* tag);
is_empty()310   bool is_empty() const { return entries_.occupancy() == 0; }
311 
312  private:
313   HashMap entries_;
314 
315   DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
316 };
317 
318 
319 class SnapshottingProgressReportingInterface {
320  public:
~SnapshottingProgressReportingInterface()321   virtual ~SnapshottingProgressReportingInterface() { }
322   virtual void ProgressStep() = 0;
323   virtual bool ProgressReport(bool force) = 0;
324 };
325 
326 
327 // An implementation of V8 heap graph extractor.
328 class V8HeapExplorer : public HeapEntriesAllocator {
329  public:
330   V8HeapExplorer(HeapSnapshot* snapshot,
331                  SnapshottingProgressReportingInterface* progress,
332                  v8::HeapProfiler::ObjectNameResolver* resolver);
333   virtual ~V8HeapExplorer();
334   virtual HeapEntry* AllocateEntry(HeapThing ptr);
335   void AddRootEntries(SnapshotFiller* filler);
336   int EstimateObjectsCount(HeapIterator* iterator);
337   bool IterateAndExtractReferences(SnapshotFiller* filler);
338   void TagGlobalObjects();
339   void TagCodeObject(Code* code);
340   void TagBuiltinCodeObject(Code* code, const char* name);
341   HeapEntry* AddEntry(Address address,
342                       HeapEntry::Type type,
343                       const char* name,
344                       size_t size);
345 
346   static String* GetConstructorName(JSObject* object);
347 
348  private:
349   typedef bool (V8HeapExplorer::*ExtractReferencesMethod)(int entry,
350                                                           HeapObject* object);
351 
352   HeapEntry* AddEntry(HeapObject* object);
353   HeapEntry* AddEntry(HeapObject* object,
354                       HeapEntry::Type type,
355                       const char* name);
356 
357   const char* GetSystemEntryName(HeapObject* object);
358 
359   template<V8HeapExplorer::ExtractReferencesMethod extractor>
360   bool IterateAndExtractSinglePass();
361 
362   bool ExtractReferencesPass1(int entry, HeapObject* obj);
363   bool ExtractReferencesPass2(int entry, HeapObject* obj);
364   void ExtractJSGlobalProxyReferences(int entry, JSGlobalProxy* proxy);
365   void ExtractJSObjectReferences(int entry, JSObject* js_obj);
366   void ExtractStringReferences(int entry, String* obj);
367   void ExtractSymbolReferences(int entry, Symbol* symbol);
368   void ExtractJSCollectionReferences(int entry, JSCollection* collection);
369   void ExtractJSWeakCollectionReferences(int entry,
370                                          JSWeakCollection* collection);
371   void ExtractContextReferences(int entry, Context* context);
372   void ExtractMapReferences(int entry, Map* map);
373   void ExtractSharedFunctionInfoReferences(int entry,
374                                            SharedFunctionInfo* shared);
375   void ExtractScriptReferences(int entry, Script* script);
376   void ExtractAccessorInfoReferences(int entry, AccessorInfo* accessor_info);
377   void ExtractAccessorPairReferences(int entry, AccessorPair* accessors);
378   void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
379   void ExtractCodeReferences(int entry, Code* code);
380   void ExtractBoxReferences(int entry, Box* box);
381   void ExtractCellReferences(int entry, Cell* cell);
382   void ExtractPropertyCellReferences(int entry, PropertyCell* cell);
383   void ExtractAllocationSiteReferences(int entry, AllocationSite* site);
384   void ExtractJSArrayBufferReferences(int entry, JSArrayBuffer* buffer);
385   void ExtractFixedArrayReferences(int entry, FixedArray* array);
386   void ExtractClosureReferences(JSObject* js_obj, int entry);
387   void ExtractPropertyReferences(JSObject* js_obj, int entry);
388   bool ExtractAccessorPairProperty(JSObject* js_obj, int entry,
389                                    Object* key, Object* callback_obj);
390   void ExtractElementReferences(JSObject* js_obj, int entry);
391   void ExtractInternalReferences(JSObject* js_obj, int entry);
392 
393   bool IsEssentialObject(Object* object);
394   void SetContextReference(HeapObject* parent_obj,
395                            int parent,
396                            String* reference_name,
397                            Object* child,
398                            int field_offset);
399   void SetNativeBindReference(HeapObject* parent_obj,
400                               int parent,
401                               const char* reference_name,
402                               Object* child);
403   void SetElementReference(HeapObject* parent_obj,
404                            int parent,
405                            int index,
406                            Object* child);
407   void SetInternalReference(HeapObject* parent_obj,
408                             int parent,
409                             const char* reference_name,
410                             Object* child,
411                             int field_offset = -1);
412   void SetInternalReference(HeapObject* parent_obj,
413                             int parent,
414                             int index,
415                             Object* child,
416                             int field_offset = -1);
417   void SetHiddenReference(HeapObject* parent_obj,
418                           int parent,
419                           int index,
420                           Object* child);
421   void SetWeakReference(HeapObject* parent_obj,
422                         int parent,
423                         const char* reference_name,
424                         Object* child_obj,
425                         int field_offset);
426   void SetWeakReference(HeapObject* parent_obj,
427                         int parent,
428                         int index,
429                         Object* child_obj,
430                         int field_offset);
431   void SetPropertyReference(HeapObject* parent_obj,
432                             int parent,
433                             Name* reference_name,
434                             Object* child,
435                             const char* name_format_string = NULL,
436                             int field_offset = -1);
437   void SetUserGlobalReference(Object* user_global);
438   void SetRootGcRootsReference();
439   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
440   void SetGcSubrootReference(
441       VisitorSynchronization::SyncTag tag, bool is_weak, Object* child);
442   const char* GetStrongGcSubrootName(Object* object);
443   void TagObject(Object* obj, const char* tag);
444   void MarkAsWeakContainer(Object* object);
445 
446   HeapEntry* GetEntry(Object* obj);
447 
448   Heap* heap_;
449   HeapSnapshot* snapshot_;
450   StringsStorage* names_;
451   HeapObjectsMap* heap_object_map_;
452   SnapshottingProgressReportingInterface* progress_;
453   SnapshotFiller* filler_;
454   HeapObjectsSet objects_tags_;
455   HeapObjectsSet strong_gc_subroot_names_;
456   HeapObjectsSet user_roots_;
457   HeapObjectsSet weak_containers_;
458   v8::HeapProfiler::ObjectNameResolver* global_object_name_resolver_;
459 
460   friend class IndexedReferencesExtractor;
461   friend class RootsReferencesExtractor;
462 
463   DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
464 };
465 
466 
467 class NativeGroupRetainedObjectInfo;
468 
469 
470 // An implementation of retained native objects extractor.
471 class NativeObjectsExplorer {
472  public:
473   NativeObjectsExplorer(HeapSnapshot* snapshot,
474                         SnapshottingProgressReportingInterface* progress);
475   virtual ~NativeObjectsExplorer();
476   void AddRootEntries(SnapshotFiller* filler);
477   int EstimateObjectsCount();
478   bool IterateAndExtractReferences(SnapshotFiller* filler);
479 
480  private:
481   void FillRetainedObjects();
482   void FillImplicitReferences();
483   List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info);
484   void SetNativeRootReference(v8::RetainedObjectInfo* info);
485   void SetRootNativeRootsReference();
486   void SetWrapperNativeReferences(HeapObject* wrapper,
487                                       v8::RetainedObjectInfo* info);
488   void VisitSubtreeWrapper(Object** p, uint16_t class_id);
489 
InfoHash(v8::RetainedObjectInfo * info)490   static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
491     return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
492                               v8::internal::kZeroHashSeed);
493   }
RetainedInfosMatch(void * key1,void * key2)494   static bool RetainedInfosMatch(void* key1, void* key2) {
495     return key1 == key2 ||
496         (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent(
497             reinterpret_cast<v8::RetainedObjectInfo*>(key2));
498   }
INLINE(static bool StringsMatch (void * key1,void * key2))499   INLINE(static bool StringsMatch(void* key1, void* key2)) {
500     return strcmp(reinterpret_cast<char*>(key1),
501                   reinterpret_cast<char*>(key2)) == 0;
502   }
503 
504   NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label);
505 
506   Isolate* isolate_;
507   HeapSnapshot* snapshot_;
508   StringsStorage* names_;
509   SnapshottingProgressReportingInterface* progress_;
510   bool embedder_queried_;
511   HeapObjectsSet in_groups_;
512   // RetainedObjectInfo* -> List<HeapObject*>*
513   HashMap objects_by_info_;
514   HashMap native_groups_;
515   HeapEntriesAllocator* synthetic_entries_allocator_;
516   HeapEntriesAllocator* native_entries_allocator_;
517   // Used during references extraction.
518   SnapshotFiller* filler_;
519 
520   static HeapThing const kNativesRootObject;
521 
522   friend class GlobalHandlesExtractor;
523 
524   DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer);
525 };
526 
527 
528 class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
529  public:
530   HeapSnapshotGenerator(HeapSnapshot* snapshot,
531                         v8::ActivityControl* control,
532                         v8::HeapProfiler::ObjectNameResolver* resolver,
533                         Heap* heap);
534   bool GenerateSnapshot();
535 
536  private:
537   bool FillReferences();
538   void ProgressStep();
539   bool ProgressReport(bool force = false);
540   void SetProgressTotal(int iterations_count);
541 
542   HeapSnapshot* snapshot_;
543   v8::ActivityControl* control_;
544   V8HeapExplorer v8_heap_explorer_;
545   NativeObjectsExplorer dom_explorer_;
546   // Mapping from HeapThing pointers to HeapEntry* pointers.
547   HeapEntriesMap entries_;
548   // Used during snapshot generation.
549   int progress_counter_;
550   int progress_total_;
551   Heap* heap_;
552 
553   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
554 };
555 
556 class OutputStreamWriter;
557 
558 class HeapSnapshotJSONSerializer {
559  public:
HeapSnapshotJSONSerializer(HeapSnapshot * snapshot)560   explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot)
561       : snapshot_(snapshot),
562         strings_(StringsMatch),
563         next_node_id_(1),
564         next_string_id_(1),
565         writer_(NULL) {
566   }
567   void Serialize(v8::OutputStream* stream);
568 
569  private:
INLINE(static bool StringsMatch (void * key1,void * key2))570   INLINE(static bool StringsMatch(void* key1, void* key2)) {
571     return strcmp(reinterpret_cast<char*>(key1),
572                   reinterpret_cast<char*>(key2)) == 0;
573   }
574 
INLINE(static uint32_t StringHash (const void * string))575   INLINE(static uint32_t StringHash(const void* string)) {
576     const char* s = reinterpret_cast<const char*>(string);
577     int len = static_cast<int>(strlen(s));
578     return StringHasher::HashSequentialString(
579         s, len, v8::internal::kZeroHashSeed);
580   }
581 
582   int GetStringId(const char* s);
entry_index(HeapEntry * e)583   int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; }
584   void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
585   void SerializeEdges();
586   void SerializeImpl();
587   void SerializeNode(HeapEntry* entry);
588   void SerializeNodes();
589   void SerializeSnapshot();
590   void SerializeTraceTree();
591   void SerializeTraceNode(AllocationTraceNode* node);
592   void SerializeTraceNodeInfos();
593   void SerializeString(const unsigned char* s);
594   void SerializeStrings();
595 
596   static const int kEdgeFieldsCount;
597   static const int kNodeFieldsCount;
598 
599   HeapSnapshot* snapshot_;
600   HashMap strings_;
601   int next_node_id_;
602   int next_string_id_;
603   OutputStreamWriter* writer_;
604 
605   friend class HeapSnapshotJSONSerializerEnumerator;
606   friend class HeapSnapshotJSONSerializerIterator;
607 
608   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
609 };
610 
611 
612 } }  // namespace v8::internal
613 
614 #endif  // V8_HEAP_SNAPSHOT_GENERATOR_H_
615