deps: update v8 to 4.3.61.21
[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/strings-storage.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   explicit HeapSnapshot(HeapProfiler* profiler);
145   void Delete();
146
147   HeapProfiler* profiler() { return profiler_; }
148   size_t RawSnapshotSize() const;
149   HeapEntry* root() { return &entries_[root_index_]; }
150   HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; }
151   HeapEntry* gc_subroot(int index) {
152     return &entries_[gc_subroot_indexes_[index]];
153   }
154   List<HeapEntry>& entries() { return entries_; }
155   List<HeapGraphEdge>& edges() { return edges_; }
156   List<HeapGraphEdge*>& children() { return children_; }
157   void RememberLastJSObjectId();
158   SnapshotObjectId max_snapshot_js_object_id() const {
159     return max_snapshot_js_object_id_;
160   }
161
162   HeapEntry* AddEntry(HeapEntry::Type type,
163                       const char* name,
164                       SnapshotObjectId id,
165                       size_t size,
166                       unsigned trace_node_id);
167   void AddSyntheticRootEntries();
168   HeapEntry* GetEntryById(SnapshotObjectId id);
169   List<HeapEntry*>* GetSortedEntriesList();
170   void FillChildren();
171
172   void Print(int max_depth);
173
174  private:
175   HeapEntry* AddRootEntry();
176   HeapEntry* AddGcRootsEntry();
177   HeapEntry* AddGcSubrootEntry(int tag, SnapshotObjectId id);
178
179   HeapProfiler* profiler_;
180   int root_index_;
181   int gc_roots_index_;
182   int gc_subroot_indexes_[VisitorSynchronization::kNumberOfSyncTags];
183   List<HeapEntry> entries_;
184   List<HeapGraphEdge> edges_;
185   List<HeapGraphEdge*> children_;
186   List<HeapEntry*> sorted_entries_;
187   SnapshotObjectId max_snapshot_js_object_id_;
188
189   friend class HeapSnapshotTester;
190
191   DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
192 };
193
194
195 class HeapObjectsMap {
196  public:
197   struct TimeInterval {
198     explicit TimeInterval(SnapshotObjectId id)
199         : id(id), size(0), count(0), timestamp(base::TimeTicks::Now()) {}
200     SnapshotObjectId last_assigned_id() const { return id - kObjectIdStep; }
201     SnapshotObjectId id;
202     uint32_t size;
203     uint32_t count;
204     base::TimeTicks timestamp;
205   };
206
207   explicit HeapObjectsMap(Heap* heap);
208
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);
217   SnapshotObjectId last_assigned_id() const {
218     return next_id_ - kObjectIdStep;
219   }
220
221   void StopHeapObjectsTracking();
222   SnapshotObjectId PushHeapObjectsStats(OutputStream* stream,
223                                         int64_t* timestamp_us);
224   const List<TimeInterval>& samples() const { return time_intervals_; }
225   size_t GetUsedMemorySize() const;
226
227   SnapshotObjectId GenerateId(v8::RetainedObjectInfo* info);
228
229   static const int kObjectIdStep = 2;
230   static const SnapshotObjectId kInternalRootObjectId;
231   static const SnapshotObjectId kGcRootsObjectId;
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 {
242   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
243       : id(id), addr(addr), size(size), accessed(true) { }
244   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
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 SerializeSamples();
594   void SerializeString(const unsigned char* s);
595   void SerializeStrings();
596
597   static const int kEdgeFieldsCount;
598   static const int kNodeFieldsCount;
599
600   HeapSnapshot* snapshot_;
601   HashMap strings_;
602   int next_node_id_;
603   int next_string_id_;
604   OutputStreamWriter* writer_;
605
606   friend class HeapSnapshotJSONSerializerEnumerator;
607   friend class HeapSnapshotJSONSerializerIterator;
608
609   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
610 };
611
612
613 } }  // namespace v8::internal
614
615 #endif  // V8_HEAP_SNAPSHOT_GENERATOR_H_