Upstream version 7.36.149.0
[platform/framework/web/crosswalk.git] / src / 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 "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() { }
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
36   Type type() const { return static_cast<Type>(type_); }
37   int index() const {
38     ASSERT(type_ == kElement || type_ == kHidden);
39     return index_;
40   }
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);
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   };
88   static const int kNoEntry;
89
90   HeapEntry() { }
91   HeapEntry(HeapSnapshot* snapshot,
92             Type type,
93             const char* name,
94             SnapshotObjectId id,
95             size_t self_size,
96             unsigned trace_node_id);
97
98   HeapSnapshot* snapshot() { return snapshot_; }
99   Type type() { return static_cast<Type>(type_); }
100   const char* name() { return name_; }
101   void set_name(const char* name) { name_ = name; }
102   inline SnapshotObjectId id() { return id_; }
103   size_t self_size() { return self_size_; }
104   unsigned trace_node_id() const { return trace_node_id_; }
105   INLINE(int index() const);
106   int children_count() const { return children_count_; }
107   INLINE(int set_children_index(int index));
108   void add_child(HeapGraphEdge* edge) {
109     children_arr()[children_count_++] = edge;
110   }
111   Vector<HeapGraphEdge*> children() {
112     return Vector<HeapGraphEdge*>(children_arr(), children_count_); }
113
114   void SetIndexedReference(
115       HeapGraphEdge::Type type, int index, HeapEntry* entry);
116   void SetNamedReference(
117       HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
118
119   void Print(
120       const char* prefix, const char* edge_name, int max_depth, int indent);
121
122  private:
123   INLINE(HeapGraphEdge** children_arr());
124   const char* TypeAsString();
125
126   unsigned type_: 4;
127   int children_count_: 28;
128   int children_index_;
129   size_t self_size_;
130   HeapSnapshot* snapshot_;
131   const char* name_;
132   SnapshotObjectId id_;
133   // id of allocation stack trace top node
134   unsigned trace_node_id_;
135 };
136
137
138 // HeapSnapshot represents a single heap snapshot. It is stored in
139 // HeapProfiler, which is also a factory for
140 // HeapSnapshots. All HeapSnapshots share strings copied from JS heap
141 // to be able to return them even if they were collected.
142 // HeapSnapshotGenerator fills in a HeapSnapshot.
143 class HeapSnapshot {
144  public:
145   HeapSnapshot(HeapProfiler* profiler,
146                const char* title,
147                unsigned uid);
148   void Delete();
149
150   HeapProfiler* profiler() { return profiler_; }
151   const char* title() { return title_; }
152   unsigned uid() { return uid_; }
153   size_t RawSnapshotSize() const;
154   HeapEntry* root() { return &entries_[root_index_]; }
155   HeapEntry* gc_roots() { return &entries_[gc_roots_index_]; }
156   HeapEntry* natives_root() { return &entries_[natives_root_index_]; }
157   HeapEntry* gc_subroot(int index) {
158     return &entries_[gc_subroot_indexes_[index]];
159   }
160   List<HeapEntry>& entries() { return entries_; }
161   List<HeapGraphEdge>& edges() { return edges_; }
162   List<HeapGraphEdge*>& children() { return children_; }
163   void RememberLastJSObjectId();
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   HeapEntry* AddRootEntry();
174   HeapEntry* AddGcRootsEntry();
175   HeapEntry* AddGcSubrootEntry(int tag);
176   HeapEntry* AddNativesRootEntry();
177   HeapEntry* GetEntryById(SnapshotObjectId id);
178   List<HeapEntry*>* GetSortedEntriesList();
179   void FillChildren();
180
181   void Print(int max_depth);
182   void PrintEntriesSize();
183
184  private:
185   HeapProfiler* profiler_;
186   const char* title_;
187   unsigned uid_;
188   int root_index_;
189   int gc_roots_index_;
190   int natives_root_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
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);
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   static inline SnapshotObjectId GetNthGcSubrootId(int delta);
226
227   static const int kObjectIdStep = 2;
228   static const SnapshotObjectId kInternalRootObjectId;
229   static const SnapshotObjectId kGcRootsObjectId;
230   static const SnapshotObjectId kNativesRootObjectId;
231   static const SnapshotObjectId kGcRootsFirstSubrootId;
232   static const SnapshotObjectId kFirstAvailableObjectId;
233
234   int FindUntrackedObjects();
235
236   void UpdateHeapObjectsMap();
237   void RemoveDeadEntries();
238
239  private:
240   struct EntryInfo {
241   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
242       : id(id), addr(addr), size(size), accessed(true) { }
243   EntryInfo(SnapshotObjectId id, Address addr, unsigned int size, bool accessed)
244       : id(id), addr(addr), size(size), accessed(accessed) { }
245     SnapshotObjectId id;
246     Address addr;
247     unsigned int size;
248     bool accessed;
249   };
250   struct TimeInterval {
251     explicit TimeInterval(SnapshotObjectId id) : id(id), size(0), count(0) { }
252     SnapshotObjectId id;
253     uint32_t size;
254     uint32_t count;
255   };
256
257   SnapshotObjectId next_id_;
258   HashMap entries_map_;
259   List<EntryInfo> entries_;
260   List<TimeInterval> time_intervals_;
261   Heap* heap_;
262
263   DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
264 };
265
266
267 // A typedef for referencing anything that can be snapshotted living
268 // in any kind of heap memory.
269 typedef void* HeapThing;
270
271
272 // An interface that creates HeapEntries by HeapThings.
273 class HeapEntriesAllocator {
274  public:
275   virtual ~HeapEntriesAllocator() { }
276   virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
277 };
278
279
280 // The HeapEntriesMap instance is used to track a mapping between
281 // real heap objects and their representations in heap snapshots.
282 class HeapEntriesMap {
283  public:
284   HeapEntriesMap();
285
286   int Map(HeapThing thing);
287   void Pair(HeapThing thing, int entry);
288
289  private:
290   static uint32_t Hash(HeapThing thing) {
291     return ComputeIntegerHash(
292         static_cast<uint32_t>(reinterpret_cast<uintptr_t>(thing)),
293         v8::internal::kZeroHashSeed);
294   }
295
296   HashMap entries_;
297
298   friend class HeapObjectsSet;
299
300   DISALLOW_COPY_AND_ASSIGN(HeapEntriesMap);
301 };
302
303
304 class HeapObjectsSet {
305  public:
306   HeapObjectsSet();
307   void Clear();
308   bool Contains(Object* object);
309   void Insert(Object* obj);
310   const char* GetTag(Object* obj);
311   void SetTag(Object* obj, const char* tag);
312   bool is_empty() const { return entries_.occupancy() == 0; }
313
314  private:
315   HashMap entries_;
316
317   DISALLOW_COPY_AND_ASSIGN(HeapObjectsSet);
318 };
319
320
321 class SnapshottingProgressReportingInterface {
322  public:
323   virtual ~SnapshottingProgressReportingInterface() { }
324   virtual void ProgressStep() = 0;
325   virtual bool ProgressReport(bool force) = 0;
326 };
327
328
329 // An implementation of V8 heap graph extractor.
330 class V8HeapExplorer : public HeapEntriesAllocator {
331  public:
332   V8HeapExplorer(HeapSnapshot* snapshot,
333                  SnapshottingProgressReportingInterface* progress,
334                  v8::HeapProfiler::ObjectNameResolver* resolver);
335   virtual ~V8HeapExplorer();
336   virtual HeapEntry* AllocateEntry(HeapThing ptr);
337   void AddRootEntries(SnapshotFiller* filler);
338   int EstimateObjectsCount(HeapIterator* iterator);
339   bool IterateAndExtractReferences(SnapshotFiller* filler);
340   void TagGlobalObjects();
341   void TagCodeObject(Code* code);
342   void TagBuiltinCodeObject(Code* code, const char* name);
343   HeapEntry* AddEntry(Address address,
344                       HeapEntry::Type type,
345                       const char* name,
346                       size_t size);
347
348   static String* GetConstructorName(JSObject* object);
349
350   static HeapObject* const kInternalRootObject;
351
352  private:
353   typedef bool (V8HeapExplorer::*ExtractReferencesMethod)(int entry,
354                                                           HeapObject* object);
355
356   HeapEntry* AddEntry(HeapObject* object);
357   HeapEntry* AddEntry(HeapObject* object,
358                       HeapEntry::Type type,
359                       const char* name);
360
361   const char* GetSystemEntryName(HeapObject* object);
362
363   template<V8HeapExplorer::ExtractReferencesMethod extractor>
364   bool IterateAndExtractSinglePass();
365
366   bool ExtractReferencesPass1(int entry, HeapObject* obj);
367   bool ExtractReferencesPass2(int entry, HeapObject* obj);
368   void ExtractJSGlobalProxyReferences(int entry, JSGlobalProxy* proxy);
369   void ExtractJSObjectReferences(int entry, JSObject* js_obj);
370   void ExtractStringReferences(int entry, String* obj);
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 ExtractAccessorPairReferences(int entry, AccessorPair* accessors);
377   void ExtractCodeCacheReferences(int entry, CodeCache* code_cache);
378   void ExtractCodeReferences(int entry, Code* code);
379   void ExtractBoxReferences(int entry, Box* box);
380   void ExtractCellReferences(int entry, Cell* cell);
381   void ExtractPropertyCellReferences(int entry, PropertyCell* cell);
382   void ExtractAllocationSiteReferences(int entry, AllocationSite* site);
383   void ExtractJSArrayBufferReferences(int entry, JSArrayBuffer* buffer);
384   void ExtractFixedArrayReferences(int entry, FixedArray* array);
385   void ExtractClosureReferences(JSObject* js_obj, int entry);
386   void ExtractPropertyReferences(JSObject* js_obj, int entry);
387   bool ExtractAccessorPairProperty(JSObject* js_obj, int entry,
388                                    Object* key, Object* callback_obj);
389   void ExtractElementReferences(JSObject* js_obj, int entry);
390   void ExtractInternalReferences(JSObject* js_obj, int entry);
391
392   bool IsEssentialObject(Object* object);
393   void SetContextReference(HeapObject* parent_obj,
394                            int parent,
395                            String* reference_name,
396                            Object* child,
397                            int field_offset);
398   void SetNativeBindReference(HeapObject* parent_obj,
399                               int parent,
400                               const char* reference_name,
401                               Object* child);
402   void SetElementReference(HeapObject* parent_obj,
403                            int parent,
404                            int index,
405                            Object* child);
406   void SetInternalReference(HeapObject* parent_obj,
407                             int parent,
408                             const char* reference_name,
409                             Object* child,
410                             int field_offset = -1);
411   void SetInternalReference(HeapObject* parent_obj,
412                             int parent,
413                             int index,
414                             Object* child,
415                             int field_offset = -1);
416   void SetHiddenReference(HeapObject* parent_obj,
417                           int parent,
418                           int index,
419                           Object* child);
420   void SetWeakReference(HeapObject* parent_obj,
421                         int parent,
422                         const char* reference_name,
423                         Object* child_obj,
424                         int field_offset);
425   void SetWeakReference(HeapObject* parent_obj,
426                         int parent,
427                         int index,
428                         Object* child_obj,
429                         int field_offset);
430   void SetPropertyReference(HeapObject* parent_obj,
431                             int parent,
432                             Name* reference_name,
433                             Object* child,
434                             const char* name_format_string = NULL,
435                             int field_offset = -1);
436   void SetUserGlobalReference(Object* user_global);
437   void SetRootGcRootsReference();
438   void SetGcRootsReference(VisitorSynchronization::SyncTag tag);
439   void SetGcSubrootReference(
440       VisitorSynchronization::SyncTag tag, bool is_weak, Object* child);
441   const char* GetStrongGcSubrootName(Object* object);
442   void TagObject(Object* obj, const char* tag);
443   void MarkAsWeakContainer(Object* object);
444
445   HeapEntry* GetEntry(Object* obj);
446
447   static inline HeapObject* GetNthGcSubrootObject(int delta);
448   static inline int GetGcSubrootOrder(HeapObject* subroot);
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   static HeapObject* const kGcRootsObject;
463   static HeapObject* const kFirstGcSubrootObject;
464   static HeapObject* const kLastGcSubrootObject;
465
466   friend class IndexedReferencesExtractor;
467   friend class GcSubrootsEnumerator;
468   friend class RootsReferencesExtractor;
469
470   DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
471 };
472
473
474 class NativeGroupRetainedObjectInfo;
475
476
477 // An implementation of retained native objects extractor.
478 class NativeObjectsExplorer {
479  public:
480   NativeObjectsExplorer(HeapSnapshot* snapshot,
481                         SnapshottingProgressReportingInterface* progress);
482   virtual ~NativeObjectsExplorer();
483   void AddRootEntries(SnapshotFiller* filler);
484   int EstimateObjectsCount();
485   bool IterateAndExtractReferences(SnapshotFiller* filler);
486
487  private:
488   void FillRetainedObjects();
489   void FillImplicitReferences();
490   List<HeapObject*>* GetListMaybeDisposeInfo(v8::RetainedObjectInfo* info);
491   void SetNativeRootReference(v8::RetainedObjectInfo* info);
492   void SetRootNativeRootsReference();
493   void SetWrapperNativeReferences(HeapObject* wrapper,
494                                       v8::RetainedObjectInfo* info);
495   void VisitSubtreeWrapper(Object** p, uint16_t class_id);
496
497   static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
498     return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
499                               v8::internal::kZeroHashSeed);
500   }
501   static bool RetainedInfosMatch(void* key1, void* key2) {
502     return key1 == key2 ||
503         (reinterpret_cast<v8::RetainedObjectInfo*>(key1))->IsEquivalent(
504             reinterpret_cast<v8::RetainedObjectInfo*>(key2));
505   }
506   INLINE(static bool StringsMatch(void* key1, void* key2)) {
507     return strcmp(reinterpret_cast<char*>(key1),
508                   reinterpret_cast<char*>(key2)) == 0;
509   }
510
511   NativeGroupRetainedObjectInfo* FindOrAddGroupInfo(const char* label);
512
513   Isolate* isolate_;
514   HeapSnapshot* snapshot_;
515   StringsStorage* names_;
516   SnapshottingProgressReportingInterface* progress_;
517   bool embedder_queried_;
518   HeapObjectsSet in_groups_;
519   // RetainedObjectInfo* -> List<HeapObject*>*
520   HashMap objects_by_info_;
521   HashMap native_groups_;
522   HeapEntriesAllocator* synthetic_entries_allocator_;
523   HeapEntriesAllocator* native_entries_allocator_;
524   // Used during references extraction.
525   SnapshotFiller* filler_;
526
527   static HeapThing const kNativesRootObject;
528
529   friend class GlobalHandlesExtractor;
530
531   DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer);
532 };
533
534
535 class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
536  public:
537   HeapSnapshotGenerator(HeapSnapshot* snapshot,
538                         v8::ActivityControl* control,
539                         v8::HeapProfiler::ObjectNameResolver* resolver,
540                         Heap* heap);
541   bool GenerateSnapshot();
542
543  private:
544   bool FillReferences();
545   void ProgressStep();
546   bool ProgressReport(bool force = false);
547   void SetProgressTotal(int iterations_count);
548
549   HeapSnapshot* snapshot_;
550   v8::ActivityControl* control_;
551   V8HeapExplorer v8_heap_explorer_;
552   NativeObjectsExplorer dom_explorer_;
553   // Mapping from HeapThing pointers to HeapEntry* pointers.
554   HeapEntriesMap entries_;
555   // Used during snapshot generation.
556   int progress_counter_;
557   int progress_total_;
558   Heap* heap_;
559
560   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
561 };
562
563 class OutputStreamWriter;
564
565 class HeapSnapshotJSONSerializer {
566  public:
567   explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot)
568       : snapshot_(snapshot),
569         strings_(StringsMatch),
570         next_node_id_(1),
571         next_string_id_(1),
572         writer_(NULL) {
573   }
574   void Serialize(v8::OutputStream* stream);
575
576  private:
577   INLINE(static bool StringsMatch(void* key1, void* key2)) {
578     return strcmp(reinterpret_cast<char*>(key1),
579                   reinterpret_cast<char*>(key2)) == 0;
580   }
581
582   INLINE(static uint32_t StringHash(const void* string)) {
583     const char* s = reinterpret_cast<const char*>(string);
584     int len = static_cast<int>(strlen(s));
585     return StringHasher::HashSequentialString(
586         s, len, v8::internal::kZeroHashSeed);
587   }
588
589   int GetStringId(const char* s);
590   int entry_index(HeapEntry* e) { return e->index() * kNodeFieldsCount; }
591   void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
592   void SerializeEdges();
593   void SerializeImpl();
594   void SerializeNode(HeapEntry* entry);
595   void SerializeNodes();
596   void SerializeSnapshot();
597   void SerializeTraceTree();
598   void SerializeTraceNode(AllocationTraceNode* node);
599   void SerializeTraceNodeInfos();
600   void SerializeString(const unsigned char* s);
601   void SerializeStrings();
602
603   static const int kEdgeFieldsCount;
604   static const int kNodeFieldsCount;
605
606   HeapSnapshot* snapshot_;
607   HashMap strings_;
608   int next_node_id_;
609   int next_string_id_;
610   OutputStreamWriter* writer_;
611
612   friend class HeapSnapshotJSONSerializerEnumerator;
613   friend class HeapSnapshotJSONSerializerIterator;
614
615   DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
616 };
617
618
619 } }  // namespace v8::internal
620
621 #endif  // V8_HEAP_SNAPSHOT_GENERATOR_H_