8aef43739cb1cedc6fa1091cfd0efc15592be177
[platform/upstream/nodejs.git] / deps / v8 / src / heap-snapshot-generator.h
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
31   HeapGraphEdge(Type type, const char* name, int from, int to);
32   HeapGraphEdge(Type type, int index, int from, int to);
33   void ReplaceToIndexWithEntry(HeapSnapshot* snapshot);
34
35   Type type() const { return TypeField::decode(bit_field_); }
36   int index() const {
37     DCHECK(type() == kElement || type() == kHidden);
38     return index_;
39   }
40   const char* name() const {
41     DCHECK(type() == kContextVariable || type() == kProperty ||
42            type() == kInternal || type() == kShortcut || type() == kWeak);
43     return name_;
44   }
45   INLINE(HeapEntry* from() const);
46   HeapEntry* to() const { return to_entry_; }
47
48  private:
49   INLINE(HeapSnapshot* snapshot() const);
50   int from_index() const { return FromIndexField::decode(bit_field_); }
51
52   class TypeField : public BitField<Type, 0, 3> {};
53   class FromIndexField : public BitField<int, 3, 29> {};
54   uint32_t bit_field_;
55   union {
56     // During entries population |to_index_| is used for storing the index,
57     // afterwards it is replaced with a pointer to the entry.
58     int to_index_;
59     HeapEntry* to_entry_;
60   };
61   union {
62     int index_;
63     const char* name_;
64   };
65 };
66
67
68 // HeapEntry instances represent an entity from the heap (or a special
69 // virtual node, e.g. root).
70 class HeapEntry BASE_EMBEDDED {
71  public:
72   enum Type {
73     kHidden = v8::HeapGraphNode::kHidden,
74     kArray = v8::HeapGraphNode::kArray,
75     kString = v8::HeapGraphNode::kString,
76     kObject = v8::HeapGraphNode::kObject,
77     kCode = v8::HeapGraphNode::kCode,
78     kClosure = v8::HeapGraphNode::kClosure,
79     kRegExp = v8::HeapGraphNode::kRegExp,
80     kHeapNumber = v8::HeapGraphNode::kHeapNumber,
81     kNative = v8::HeapGraphNode::kNative,
82     kSynthetic = v8::HeapGraphNode::kSynthetic,
83     kConsString = v8::HeapGraphNode::kConsString,
84     kSlicedString = v8::HeapGraphNode::kSlicedString,
85     kSymbol = v8::HeapGraphNode::kSymbol
86   };
87   static const int kNoEntry;
88
89   HeapEntry() { }
90   HeapEntry(HeapSnapshot* snapshot,
91             Type type,
92             const char* name,
93             SnapshotObjectId id,
94             size_t self_size,
95             unsigned trace_node_id);
96
97   HeapSnapshot* snapshot() { return snapshot_; }
98   Type type() { return static_cast<Type>(type_); }
99   const char* name() { return name_; }
100   void set_name(const char* name) { name_ = name; }
101   SnapshotObjectId id() { return id_; }
102   size_t self_size() { return self_size_; }
103   unsigned trace_node_id() const { return trace_node_id_; }
104   INLINE(int index() const);
105   int children_count() const { return children_count_; }
106   INLINE(int set_children_index(int index));
107   void add_child(HeapGraphEdge* edge) {
108     children_arr()[children_count_++] = edge;
109   }
110   Vector<HeapGraphEdge*> children() {
111     return Vector<HeapGraphEdge*>(children_arr(), children_count_); }
112
113   void SetIndexedReference(
114       HeapGraphEdge::Type type, int index, HeapEntry* entry);
115   void SetNamedReference(
116       HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
117
118   void Print(
119       const char* prefix, const char* edge_name, int max_depth, int indent);
120
121  private:
122   INLINE(HeapGraphEdge** children_arr());
123   const char* TypeAsString();
124
125   unsigned type_: 4;
126   int children_count_: 28;
127   int children_index_;
128   size_t self_size_;
129   HeapSnapshot* snapshot_;
130   const char* name_;
131   SnapshotObjectId id_;
132   // id of allocation stack trace top node
133   unsigned trace_node_id_;
134 };
135
136
137 // HeapSnapshot represents a single heap snapshot. It is stored in
138 // HeapProfiler, which is also a factory for
139 // HeapSnapshots. All HeapSnapshots share strings copied from JS heap
140 // to be able to return them even if they were collected.
141 // HeapSnapshotGenerator fills in a HeapSnapshot.
142 class HeapSnapshot {
143  public:
144   HeapSnapshot(HeapProfiler* profiler,
145                const char* title,
146                unsigned uid);
147   void Delete();
148
149   HeapProfiler* profiler() { return profiler_; }
150   const char* title() { return title_; }
151   unsigned uid() { return uid_; }
152   size_t RawSnapshotSize() const;
153   HeapEntry* root() { return &entries_[root_index_]; }
154   HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; }
155   HeapEntry* gc_subroot(int index) {
156     return &entries_[gc_subroot_indexes_[index]];
157   }
158   List<HeapEntry>& entries() { return entries_; }
159   List<HeapGraphEdge>& edges() { return edges_; }
160   List<HeapGraphEdge*>& children() { return children_; }
161   void RememberLastJSObjectId();
162   SnapshotObjectId max_snapshot_js_object_id() const {
163     return max_snapshot_js_object_id_;
164   }
165
166   HeapEntry* AddEntry(HeapEntry::Type type,
167                       const char* name,
168                       SnapshotObjectId id,
169                       size_t size,
170                       unsigned trace_node_id);
171   void AddSyntheticRootEntries();
172   HeapEntry* GetEntryById(SnapshotObjectId id);
173   List<HeapEntry*>* GetSortedEntriesList();
174   void FillChildren();
175
176   void Print(int max_depth);
177
178  private:
179   HeapEntry* AddRootEntry();
180   HeapEntry* AddGcRootsEntry();
181   HeapEntry* AddGcSubrootEntry(int tag, SnapshotObjectId id);
182
183   HeapProfiler* profiler_;
184   const char* title_;
185   unsigned uid_;
186   int root_index_;
187   int gc_roots_index_;
188   int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags];
189   List<HeapEntry> entries_;
190   List<HeapGraphEdge> edges_;
191   List<HeapGraphEdge*> children_;
192   List<HeapEntry*> sorted_entries_;
193   SnapshotObjectId max_snapshot_js_object_id_;
194
195   friend class HeapSnapshotTester;
196
197   DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
198 };
199
200
201 class HeapObjectsMap {
202  public:
203   explicit HeapObjectsMap(Heap* heap);
204
205   Heap* heap() const { return heap_; }
206
207   SnapshotObjectId FindEntry(Address addr);
208   SnapshotObjectId FindOrAddEntry(Address addr,
209                                   unsigned int size,
210                                   bool accessed = true);
211   bool MoveObject(Address from, Address to, int size);
212   void UpdateObjectSize(Address addr, int size);
213   SnapshotObjectId last_assigned_id() const {
214     return next_id_ - kObjectIdStep;
215   }
216
217   void StopHeapObjectsTracking();
218   SnapshotObjectId PushHeapObjectsStats(OutputStream* stream);
219   size_t GetUsedMemorySize() const;
220
221   SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info);
222
223   static const int kObjectIdStep = 2;
224   static const SnapshotObjectId kInternalRootObjectId;
225   static const SnapshotObjectId kGcRootsObjectId;
226   static const SnapshotObjectId kGcRootsFirstSubrootId;
227   static const SnapshotObjectId kFirstAvailableObjectId;
228
229   int FindUntrackedObjects();
230
231   void UpdateHeapObjectsMap();
232   void RemoveDeadEntries();
233
234  private:
235   struct EntryInfo {
236   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
237       : id(id), addr(addr), size(size), accessed(true) { }
238   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed)
239       : id(id), addr(addr), size(size), accessed(accessed) { }
240     SnapshotObjectId id;
241     Address addr;
242     unsigned int size;
243     bool accessed;
244   };
245   struct TimeInterval {
246     explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { }
247     SnapshotObjectId id;
248     uint32_t size;
249     uint32_t count;
250   };
251
252   SnapshotObjectId next_id_;
253   HashMap entries_map_;
254   List<EntryInfo> entries_;
255   List<TimeInterval> time_intervals_;
256   Heap* heap_;
257
258   DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
259 };
260
261
262 // A typedef for referencing anything that can be snapshotted living
263 // in any kind of heap memory.
264 typedef void* HeapThing;
265
266
267 // An interface that creates HeapEntries by HeapThings.
268 class HeapEntriesAllocator {
269  public:
270   virtual ~HeapEntriesAllocator() { }
271   virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
272 };
273
274
275 // The HeapEntriesMap instance is used to track a mapping between
276 // real heap objects and their representations in heap snapshots.
277 class HeapEntriesMap {
278  public:
279   HeapEntriesMap();
280
281   int Map(HeapThing thing);
282   void Pair(HeapThing thing, int entry);
283
284  private:
285   static uint32_t Hash(HeapThing thing) {
286     return ComputeIntegerHash(
287         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
288         v8::internal::kZeroHashSeed);
289   }
290
291   HashMap entries_;
292
293   friend class HeapObjectsSet;
294
295   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
296 };
297
298
299 class HeapObjectsSet {
300  public:
301   HeapObjectsSet();
302   void Clear();
303   bool Contains(Object* object);
304   void Insert(Object* obj);
305   const char* GetTag(Object* obj);
306   void SetTag(Object* obj, const char* tag);
307   bool is_empty() const { return entries_.occupancy() == 0; }
308
309  private:
310   HashMap entries_;
311
312   DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
313 };
314
315
316 class SnapshottingProgressReportingInterface {
317  public:
318   virtual ~SnapshottingProgressReportingInterface() { }
319   virtual void ProgressStep() = 0;
320   virtual bool ProgressReport(bool force) = 0;
321 };
322
323
324 // An implementation of V8 heap graph extractor.
325 class V8HeapExplorer : public HeapEntriesAllocator {
326  public:
327   V8HeapExplorer(HeapSnapshot* snapshot,
328                  SnapshottingProgressReportingInterface* progress,
329                  v8::HeapProfiler::ObjectNameResolver* resolver);
330   virtual ~V8HeapExplorer();
331   virtual HeapEntry* AllocateEntry(HeapThing ptr);
332   int EstimateObjectsCount(HeapIterator* iterator);
333   bool IterateAndExtractReferences(SnapshotFiller* filler);
334   void TagGlobalObjects();
335   void TagCodeObject(Code* code);
336   void TagBuiltinCodeObject(Code* code, const char* name);
337   HeapEntry* AddEntry(Address address,
338                       HeapEntry::Type type,
339                       const char* name,
340                       size_t size);
341
342   static String* GetConstructorName(JSObject* object);
343
344  private:
345   typedef bool (V8HeapExplorer::*ExtractReferencesMethod)(int entry,
346                                                           HeapObject* object);
347
348   HeapEntry* AddEntry(HeapObject* object);
349   HeapEntry* AddEntry(HeapObject* object,
350                       HeapEntry::Type type,
351                       const char* name);
352
353   const char* GetSystemEntryName(HeapObject* object);
354
355   template<V8HeapExplorer::ExtractReferencesMethod extractor>
356   bool IterateAndExtractSinglePass();
357
358   bool ExtractReferencesPass1(int entry, HeapObject* obj);
359   bool ExtractReferencesPass2(int entry, HeapObject* obj);
360   void ExtractJSGlobalProxyReferences(int entry, JSGlobalProxy* proxy);
361   void ExtractJSObjectReferences(int entry, JSObject* js_obj);
362   void ExtractStringReferences(int entry, String* obj);
363   void ExtractSymbolReferences(int entry, Symbol* symbol);
364   void ExtractJSCollectionReferences(int entry, JSCollection* collection);
365   void ExtractJSWeakCollectionReferences(int entry,
366                                          JSWeakCollection* collection);
367   void ExtractContextReferences(int entry, Context* context);
368   void ExtractMapReferences(int entry, Map* map);
369   void ExtractSharedFunctionInfoReferences(int entry,
370                                            SharedFunctionInfo* shared);
371   void ExtractScriptReferences(int entry, Script* script);
372   void ExtractAccessorInfoReferences(int entry, AccessorInfo* accessor_info);
373   void ExtractAccessorPairReferences(int entry, AccessorPair* accessors);
374   void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
375   void ExtractCodeReferences(int entry, Code* code);
376   void ExtractBoxReferences(int entry, Box* box);
377   void ExtractCellReferences(int entry, Cell* cell);
378   void ExtractPropertyCellReferences(int entry, PropertyCell* cell);
379   void ExtractAllocationSiteReferences(int entry, AllocationSite* site);
380   void ExtractJSArrayBufferReferences(int entry, JSArrayBuffer* buffer);
381   void ExtractFixedArrayReferences(int entry, FixedArray* array);
382   void ExtractClosureReferences(JSObject* js_obj, int entry);
383   void ExtractPropertyReferences(JSObject* js_obj, int entry);
384   void ExtractAccessorPairProperty(JSObject* js_obj, int entry, Name* key,
385                                    Object* callback_obj, int field_offset = -1);
386   void ExtractElementReferences(JSObject* js_obj, int entry);
387   void ExtractInternalReferences(JSObject* js_obj, int entry);
388
389   bool IsEssentialObject(Object* object);
390   void SetContextReference(HeapObject* parent_obj,
391                            int parent,
392                            String* reference_name,
393                            Object* child,
394                            int field_offset);
395   void SetNativeBindReference(HeapObject* parent_obj,
396                               int parent,
397                               const char* reference_name,
398                               Object* child);
399   void SetElementReference(HeapObject* parent_obj,
400                            int parent,
401                            int index,
402                            Object* child);
403   void SetInternalReference(HeapObject* parent_obj,
404                             int parent,
405                             const char* reference_name,
406                             Object* child,
407                             int field_offset = -1);
408   void SetInternalReference(HeapObject* parent_obj,
409                             int parent,
410                             int index,
411                             Object* child,
412                             int field_offset = -1);
413   void SetHiddenReference(HeapObject* parent_obj,
414                           int parent,
415                           int index,
416                           Object* child);
417   void SetWeakReference(HeapObject* parent_obj,
418                         int parent,
419                         const char* reference_name,
420                         Object* child_obj,
421                         int field_offset);
422   void SetWeakReference(HeapObject* parent_obj,
423                         int parent,
424                         int index,
425                         Object* child_obj,
426                         int field_offset);
427   void SetPropertyReference(HeapObject* parent_obj,
428                             int parent,
429                             Name* reference_name,
430                             Object* child,
431                             const char* name_format_string = NULL,
432                             int field_offset = -1);
433   void SetDataOrAccessorPropertyReference(PropertyKind kind,
434                                           JSObject* parent_obj, int parent,
435                                           Name* reference_name, Object* child,
436                                           const char* name_format_string = NULL,
437                                           int field_offset = -1);
438
439   void SetUserGlobalReference(Object* user_global);
440   void SetRootGcRootsReference();
441   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
442   void SetGcSubrootReference(
443       VisitorSynchronization::SyncTag tag, bool is_weak, Object* child);
444   const char* GetStrongGcSubrootName(Object* object);
445   void TagObject(Object* obj, const char* tag);
446   void MarkAsWeakContainer(Object* object);
447
448   HeapEntry* GetEntry(Object* obj);
449
450   Heap* heap_;
451   HeapSnapshot* snapshot_;
452   StringsStorage* names_;
453   HeapObjectsMap* heap_object_map_;
454   SnapshottingProgressReportingInterface* progress_;
455   SnapshotFiller* filler_;
456   HeapObjectsSet objects_tags_;
457   HeapObjectsSet strong_gc_subroot_names_;
458   HeapObjectsSet user_roots_;
459   HeapObjectsSet weak_containers_;
460   v8::HeapProfiler::ObjectNameResolver* global_object_name_resolver_;
461
462   friend class IndexedReferencesExtractor;
463   friend class RootsReferencesExtractor;
464
465   DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
466 };
467
468
469 class NativeGroupRetainedObjectInfo;
470
471
472 // An implementation of retained native objects extractor.
473 class NativeObjectsExplorer {
474  public:
475   NativeObjectsExplorer(HeapSnapshot* snapshot,
476                         SnapshottingProgressReportingInterface* progress);
477   virtual ~NativeObjectsExplorer();
478   int EstimateObjectsCount();
479   bool IterateAndExtractReferences(SnapshotFiller* filler);
480
481  private:
482   void FillRetainedObjects();
483   void FillImplicitReferences();
484   List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info);
485   void SetNativeRootReference(v8::RetainedObjectInfo* info);
486   void SetRootNativeRootsReference();
487   void SetWrapperNativeReferences(HeapObject* wrapper,
488                                       v8::RetainedObjectInfo* info);
489   void VisitSubtreeWrapper(Object** p, uint16_t class_id);
490
491   static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
492     return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
493                               v8::internal::kZeroHashSeed);
494   }
495   static bool RetainedInfosMatch(void* key1, void* key2) {
496     return key1 == key2 ||
497         (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent(
498             reinterpret_cast<v8::RetainedObjectInfo*>(key2));
499   }
500   INLINE(static bool StringsMatch(void* key1, void* key2)) {
501     return strcmp(reinterpret_cast<char*>(key1),
502                   reinterpret_cast<char*>(key2)) == 0;
503   }
504
505   NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label);
506
507   Isolate* isolate_;
508   HeapSnapshot* snapshot_;
509   StringsStorage* names_;
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:
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:
570   INLINE(static bool StringsMatch(void* key1, void* key2)) {
571     return strcmp(reinterpret_cast<char*>(key1),
572                   reinterpret_cast<char*>(key2)) == 0;
573   }
574
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);
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_