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
10namespace v8 {
11namespace internal {
12
13class AllocationTracker;
14class AllocationTraceNode;
15class HeapEntry;
16class HeapSnapshot;
17class SnapshotFiller;
18
19class 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    DCHECK(type_ == kElement || type_ == kHidden);
39    return index_;
40  }
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);
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).
72class 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
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
99  HeapSnapshot* snapshot() { return snapshot_; }
100  Type type() { return static_cast<Type>(type_); }
101  const char* name() { return name_; }
102  void set_name(const char* name) { name_ = name; }
103  SnapshotObjectId id() { return id_; }
104  size_t self_size() { return self_size_; }
105  unsigned trace_node_id() const { return trace_node_id_; }
106  INLINE(int index() const);
107  int children_count() const { return children_count_; }
108  INLINE(int set_children_index(int index));
109  void add_child(HeapGraphEdge* edge) {
110    children_arr()[children_count_++] = edge;
111  }
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.
144class HeapSnapshot {
145 public:
146  HeapSnapshot(HeapProfiler* profiler,
147               const char* title,
148               unsigned uid);
149  void Delete();
150
151  HeapProfiler* profiler() { return profiler_; }
152  const char* title() { return title_; }
153  unsigned uid() { return uid_; }
154  size_t RawSnapshotSize() const;
155  HeapEntry* root() { return &entries_[root_index_]; }
156  HeapEntry* gc_roots() { return &entries_[gc_roots_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  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
204class 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
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 {
239  EntryInfo(SnapshotObjectId id, Address addr, unsigned int size)
240      : id(id), addr(addr), size(size), accessed(true) { }
241  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 {
249    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.
267typedef void* HeapThing;
268
269
270// An interface that creates HeapEntries by HeapThings.
271class HeapEntriesAllocator {
272 public:
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.
280class HeapEntriesMap {
281 public:
282  HeapEntriesMap();
283
284  int Map(HeapThing thing);
285  void Pair(HeapThing thing, int entry);
286
287 private:
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
302class 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);
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
319class SnapshottingProgressReportingInterface {
320 public:
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.
328class 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
467class NativeGroupRetainedObjectInfo;
468
469
470// An implementation of retained native objects extractor.
471class 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
490  static uint32_t InfoHash(v8::RetainedObjectInfo* info) {
491    return ComputeIntegerHash(static_cast<uint32_t>(info->GetHash()),
492                              v8::internal::kZeroHashSeed);
493  }
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  }
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
528class 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
556class OutputStreamWriter;
557
558class 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_
615