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_PROFILER_HEAP_SNAPSHOT_GENERATOR_H_
6#define V8_PROFILER_HEAP_SNAPSHOT_GENERATOR_H_
7
8#include <deque>
9#include <unordered_map>
10#include <unordered_set>
11#include <vector>
12
13#include "include/v8-profiler.h"
14#include "src/base/platform/time.h"
15#include "src/objects.h"
16#include "src/objects/fixed-array.h"
17#include "src/objects/hash-table.h"
18#include "src/objects/heap-object.h"
19#include "src/objects/js-objects.h"
20#include "src/objects/literal-objects.h"
21#include "src/profiler/strings-storage.h"
22#include "src/string-hasher.h"
23#include "src/visitors.h"
24
25namespace v8 {
26namespace internal {
27
28class AllocationTracker;
29class AllocationTraceNode;
30class HeapEntry;
31class HeapIterator;
32class HeapProfiler;
33class HeapSnapshot;
34class HeapSnapshotGenerator;
35class JSArrayBuffer;
36class JSCollection;
37class JSGeneratorObject;
38class JSGlobalObject;
39class JSGlobalProxy;
40class JSPromise;
41class JSWeakCollection;
42
43struct SourceLocation {
44 SourceLocation(int entry_index, int scriptId, int line, int col)
45 : entry_index(entry_index), scriptId(scriptId), line(line), col(col) {}
46
47 const int entry_index;
48 const int scriptId;
49 const int line;
50 const int col;
51};
52
53class HeapGraphEdge {
54 public:
55 enum Type {
56 kContextVariable = v8::HeapGraphEdge::kContextVariable,
57 kElement = v8::HeapGraphEdge::kElement,
58 kProperty = v8::HeapGraphEdge::kProperty,
59 kInternal = v8::HeapGraphEdge::kInternal,
60 kHidden = v8::HeapGraphEdge::kHidden,
61 kShortcut = v8::HeapGraphEdge::kShortcut,
62 kWeak = v8::HeapGraphEdge::kWeak
63 };
64
65 HeapGraphEdge(Type type, const char* name, HeapEntry* from, HeapEntry* to);
66 HeapGraphEdge(Type type, int index, HeapEntry* from, HeapEntry* to);
67
68 Type type() const { return TypeField::decode(bit_field_); }
69 int index() const {
70 DCHECK(type() == kElement || type() == kHidden);
71 return index_;
72 }
73 const char* name() const {
74 DCHECK(type() == kContextVariable || type() == kProperty ||
75 type() == kInternal || type() == kShortcut || type() == kWeak);
76 return name_;
77 }
78 V8_INLINE HeapEntry* from() const;
79 HeapEntry* to() const { return to_entry_; }
80
81 V8_INLINE Isolate* isolate() const;
82
83 private:
84 V8_INLINE HeapSnapshot* snapshot() const;
85 int from_index() const { return FromIndexField::decode(bit_field_); }
86
87 class TypeField : public BitField<Type, 0, 3> {};
88 class FromIndexField : public BitField<int, 3, 29> {};
89 uint32_t bit_field_;
90 HeapEntry* to_entry_;
91 union {
92 int index_;
93 const char* name_;
94 };
95};
96
97
98// HeapEntry instances represent an entity from the heap (or a special
99// virtual node, e.g. root).
100class HeapEntry {
101 public:
102 enum Type {
103 kHidden = v8::HeapGraphNode::kHidden,
104 kArray = v8::HeapGraphNode::kArray,
105 kString = v8::HeapGraphNode::kString,
106 kObject = v8::HeapGraphNode::kObject,
107 kCode = v8::HeapGraphNode::kCode,
108 kClosure = v8::HeapGraphNode::kClosure,
109 kRegExp = v8::HeapGraphNode::kRegExp,
110 kHeapNumber = v8::HeapGraphNode::kHeapNumber,
111 kNative = v8::HeapGraphNode::kNative,
112 kSynthetic = v8::HeapGraphNode::kSynthetic,
113 kConsString = v8::HeapGraphNode::kConsString,
114 kSlicedString = v8::HeapGraphNode::kSlicedString,
115 kSymbol = v8::HeapGraphNode::kSymbol,
116 kBigInt = v8::HeapGraphNode::kBigInt
117 };
118
119 HeapEntry(HeapSnapshot* snapshot, int index, Type type, const char* name,
120 SnapshotObjectId id, size_t self_size, unsigned trace_node_id);
121
122 HeapSnapshot* snapshot() { return snapshot_; }
123 Type type() const { return static_cast<Type>(type_); }
124 void set_type(Type type) { type_ = type; }
125 const char* name() const { return name_; }
126 void set_name(const char* name) { name_ = name; }
127 SnapshotObjectId id() const { return id_; }
128 size_t self_size() const { return self_size_; }
129 unsigned trace_node_id() const { return trace_node_id_; }
130 int index() const { return index_; }
131 V8_INLINE int children_count() const;
132 V8_INLINE int set_children_index(int index);
133 V8_INLINE void add_child(HeapGraphEdge* edge);
134 V8_INLINE HeapGraphEdge* child(int i);
135 V8_INLINE Isolate* isolate() const;
136
137 void SetIndexedReference(
138 HeapGraphEdge::Type type, int index, HeapEntry* entry);
139 void SetNamedReference(
140 HeapGraphEdge::Type type, const char* name, HeapEntry* entry);
141 void SetIndexedAutoIndexReference(HeapGraphEdge::Type type,
142 HeapEntry* child) {
143 SetIndexedReference(type, children_count_ + 1, child);
144 }
145 void SetNamedAutoIndexReference(HeapGraphEdge::Type type,
146 const char* description, HeapEntry* child,
147 StringsStorage* strings);
148
149 V8_EXPORT_PRIVATE void Print(const char* prefix, const char* edge_name,
150 int max_depth, int indent);
151
152 private:
153 V8_INLINE std::vector<HeapGraphEdge*>::iterator children_begin() const;
154 V8_INLINE std::vector<HeapGraphEdge*>::iterator children_end() const;
155 const char* TypeAsString();
156
157 unsigned type_: 4;
158 unsigned index_ : 28; // Supports up to ~250M objects.
159 union {
160 // The count is used during the snapshot build phase,
161 // then it gets converted into the index by the |FillChildren| function.
162 unsigned children_count_;
163 unsigned children_end_index_;
164 };
165 size_t self_size_;
166 HeapSnapshot* snapshot_;
167 const char* name_;
168 SnapshotObjectId id_;
169 // id of allocation stack trace top node
170 unsigned trace_node_id_;
171};
172
173// HeapSnapshot represents a single heap snapshot. It is stored in
174// HeapProfiler, which is also a factory for
175// HeapSnapshots. All HeapSnapshots share strings copied from JS heap
176// to be able to return them even if they were collected.
177// HeapSnapshotGenerator fills in a HeapSnapshot.
178class HeapSnapshot {
179 public:
180 explicit HeapSnapshot(HeapProfiler* profiler);
181 void Delete();
182
183 HeapProfiler* profiler() const { return profiler_; }
184 HeapEntry* root() const { return root_entry_; }
185 HeapEntry* gc_roots() const { return gc_roots_entry_; }
186 HeapEntry* gc_subroot(Root root) const {
187 return gc_subroot_entries_[static_cast<int>(root)];
188 }
189 std::deque<HeapEntry>& entries() { return entries_; }
190 std::deque<HeapGraphEdge>& edges() { return edges_; }
191 std::vector<HeapGraphEdge*>& children() { return children_; }
192 const std::vector<SourceLocation>& locations() const { return locations_; }
193 void RememberLastJSObjectId();
194 SnapshotObjectId max_snapshot_js_object_id() const {
195 return max_snapshot_js_object_id_;
196 }
197 bool is_complete() const { return !children_.empty(); }
198
199 void AddLocation(HeapEntry* entry, int scriptId, int line, int col);
200 HeapEntry* AddEntry(HeapEntry::Type type,
201 const char* name,
202 SnapshotObjectId id,
203 size_t size,
204 unsigned trace_node_id);
205 void AddSyntheticRootEntries();
206 HeapEntry* GetEntryById(SnapshotObjectId id);
207 void FillChildren();
208
209 void Print(int max_depth);
210
211 private:
212 void AddRootEntry();
213 void AddGcRootsEntry();
214 void AddGcSubrootEntry(Root root, SnapshotObjectId id);
215
216 HeapProfiler* profiler_;
217 HeapEntry* root_entry_ = nullptr;
218 HeapEntry* gc_roots_entry_ = nullptr;
219 HeapEntry* gc_subroot_entries_[static_cast<int>(Root::kNumberOfRoots)];
220 // For |entries_| we rely on the deque property, that it never reallocates
221 // backing storage, thus all entry pointers remain valid for the duration
222 // of snapshotting.
223 std::deque<HeapEntry> entries_;
224 std::deque<HeapGraphEdge> edges_;
225 std::vector<HeapGraphEdge*> children_;
226 std::unordered_map<SnapshotObjectId, HeapEntry*> entries_by_id_cache_;
227 std::vector<SourceLocation> locations_;
228 SnapshotObjectId max_snapshot_js_object_id_ = -1;
229
230 DISALLOW_COPY_AND_ASSIGN(HeapSnapshot);
231};
232
233
234class HeapObjectsMap {
235 public:
236 struct TimeInterval {
237 explicit TimeInterval(SnapshotObjectId id)
238 : id(id), size(0), count(0), timestamp(base::TimeTicks::Now()) {}
239 SnapshotObjectId last_assigned_id() const { return id - kObjectIdStep; }
240 SnapshotObjectId id;
241 uint32_t size;
242 uint32_t count;
243 base::TimeTicks timestamp;
244 };
245
246 explicit HeapObjectsMap(Heap* heap);
247
248 Heap* heap() const { return heap_; }
249
250 SnapshotObjectId FindEntry(Address addr);
251 SnapshotObjectId FindOrAddEntry(Address addr,
252 unsigned int size,
253 bool accessed = true);
254 bool MoveObject(Address from, Address to, int size);
255 void UpdateObjectSize(Address addr, int size);
256 SnapshotObjectId last_assigned_id() const {
257 return next_id_ - kObjectIdStep;
258 }
259
260 void StopHeapObjectsTracking();
261 SnapshotObjectId PushHeapObjectsStats(OutputStream* stream,
262 int64_t* timestamp_us);
263 const std::vector<TimeInterval>& samples() const { return time_intervals_; }
264
265 static const int kObjectIdStep = 2;
266 static const SnapshotObjectId kInternalRootObjectId;
267 static const SnapshotObjectId kGcRootsObjectId;
268 static const SnapshotObjectId kGcRootsFirstSubrootId;
269 static const SnapshotObjectId kFirstAvailableObjectId;
270
271 void UpdateHeapObjectsMap();
272 void RemoveDeadEntries();
273
274 private:
275 struct EntryInfo {
276 EntryInfo(SnapshotObjectId id, Address addr, unsigned int size,
277 bool accessed)
278 : id(id), addr(addr), size(size), accessed(accessed) {}
279 SnapshotObjectId id;
280 Address addr;
281 unsigned int size;
282 bool accessed;
283 };
284
285 SnapshotObjectId next_id_;
286 // TODO(jkummerow): Use a map that uses {Address} as the key type.
287 base::HashMap entries_map_;
288 std::vector<EntryInfo> entries_;
289 std::vector<TimeInterval> time_intervals_;
290 Heap* heap_;
291
292 DISALLOW_COPY_AND_ASSIGN(HeapObjectsMap);
293};
294
295// A typedef for referencing anything that can be snapshotted living
296// in any kind of heap memory.
297typedef void* HeapThing;
298
299// An interface that creates HeapEntries by HeapThings.
300class HeapEntriesAllocator {
301 public:
302 virtual ~HeapEntriesAllocator() = default;
303 virtual HeapEntry* AllocateEntry(HeapThing ptr) = 0;
304};
305
306class SnapshottingProgressReportingInterface {
307 public:
308 virtual ~SnapshottingProgressReportingInterface() = default;
309 virtual void ProgressStep() = 0;
310 virtual bool ProgressReport(bool force) = 0;
311};
312
313// An implementation of V8 heap graph extractor.
314class V8_EXPORT_PRIVATE V8HeapExplorer : public HeapEntriesAllocator {
315 public:
316 V8HeapExplorer(HeapSnapshot* snapshot,
317 SnapshottingProgressReportingInterface* progress,
318 v8::HeapProfiler::ObjectNameResolver* resolver);
319 ~V8HeapExplorer() override = default;
320
321 HeapEntry* AllocateEntry(HeapThing ptr) override;
322 int EstimateObjectsCount();
323 bool IterateAndExtractReferences(HeapSnapshotGenerator* generator);
324 void TagGlobalObjects();
325 void TagBuiltinCodeObject(Code code, const char* name);
326 HeapEntry* AddEntry(Address address,
327 HeapEntry::Type type,
328 const char* name,
329 size_t size);
330
331 static JSFunction GetConstructor(JSReceiver receiver);
332 static String GetConstructorName(JSObject object);
333
334 private:
335 void MarkVisitedField(int offset);
336
337 HeapEntry* AddEntry(HeapObject object);
338 HeapEntry* AddEntry(HeapObject object, HeapEntry::Type type,
339 const char* name);
340
341 const char* GetSystemEntryName(HeapObject object);
342
343 void ExtractLocation(HeapEntry* entry, HeapObject object);
344 void ExtractLocationForJSFunction(HeapEntry* entry, JSFunction func);
345 void ExtractReferences(HeapEntry* entry, HeapObject obj);
346 void ExtractJSGlobalProxyReferences(HeapEntry* entry, JSGlobalProxy proxy);
347 void ExtractJSObjectReferences(HeapEntry* entry, JSObject js_obj);
348 void ExtractStringReferences(HeapEntry* entry, String obj);
349 void ExtractSymbolReferences(HeapEntry* entry, Symbol symbol);
350 void ExtractJSCollectionReferences(HeapEntry* entry, JSCollection collection);
351 void ExtractJSWeakCollectionReferences(HeapEntry* entry,
352 JSWeakCollection collection);
353 void ExtractEphemeronHashTableReferences(HeapEntry* entry,
354 EphemeronHashTable table);
355 void ExtractContextReferences(HeapEntry* entry, Context context);
356 void ExtractMapReferences(HeapEntry* entry, Map map);
357 void ExtractSharedFunctionInfoReferences(HeapEntry* entry,
358 SharedFunctionInfo shared);
359 void ExtractScriptReferences(HeapEntry* entry, Script script);
360 void ExtractAccessorInfoReferences(HeapEntry* entry,
361 AccessorInfo accessor_info);
362 void ExtractAccessorPairReferences(HeapEntry* entry, AccessorPair accessors);
363 void ExtractCodeReferences(HeapEntry* entry, Code code);
364 void ExtractCellReferences(HeapEntry* entry, Cell cell);
365 void ExtractFeedbackCellReferences(HeapEntry* entry,
366 FeedbackCell feedback_cell);
367 void ExtractPropertyCellReferences(HeapEntry* entry, PropertyCell cell);
368 void ExtractAllocationSiteReferences(HeapEntry* entry, AllocationSite site);
369 void ExtractArrayBoilerplateDescriptionReferences(
370 HeapEntry* entry, ArrayBoilerplateDescription value);
371 void ExtractJSArrayBufferReferences(HeapEntry* entry, JSArrayBuffer buffer);
372 void ExtractJSPromiseReferences(HeapEntry* entry, JSPromise promise);
373 void ExtractJSGeneratorObjectReferences(HeapEntry* entry,
374 JSGeneratorObject generator);
375 void ExtractFixedArrayReferences(HeapEntry* entry, FixedArray array);
376 void ExtractFeedbackVectorReferences(HeapEntry* entry,
377 FeedbackVector feedback_vector);
378 void ExtractDescriptorArrayReferences(HeapEntry* entry,
379 DescriptorArray array);
380 template <typename T>
381 void ExtractWeakArrayReferences(int header_size, HeapEntry* entry, T array);
382 void ExtractPropertyReferences(JSObject js_obj, HeapEntry* entry);
383 void ExtractAccessorPairProperty(HeapEntry* entry, Name key,
384 Object callback_obj, int field_offset = -1);
385 void ExtractElementReferences(JSObject js_obj, HeapEntry* entry);
386 void ExtractInternalReferences(JSObject js_obj, HeapEntry* entry);
387
388 bool IsEssentialObject(Object object);
389 bool IsEssentialHiddenReference(Object parent, int field_offset);
390
391 void SetContextReference(HeapEntry* parent_entry, String reference_name,
392 Object child, int field_offset);
393 void SetNativeBindReference(HeapEntry* parent_entry,
394 const char* reference_name, Object child);
395 void SetElementReference(HeapEntry* parent_entry, int index, Object child);
396 void SetInternalReference(HeapEntry* parent_entry, const char* reference_name,
397 Object child, int field_offset = -1);
398 void SetInternalReference(HeapEntry* parent_entry, int index, Object child,
399 int field_offset = -1);
400 void SetHiddenReference(HeapObject parent_obj, HeapEntry* parent_entry,
401 int index, Object child, int field_offset);
402 void SetWeakReference(HeapEntry* parent_entry, const char* reference_name,
403 Object child_obj, int field_offset);
404 void SetWeakReference(HeapEntry* parent_entry, int index, Object child_obj,
405 int field_offset);
406 void SetPropertyReference(HeapEntry* parent_entry, Name reference_name,
407 Object child,
408 const char* name_format_string = nullptr,
409 int field_offset = -1);
410 void SetDataOrAccessorPropertyReference(
411 PropertyKind kind, HeapEntry* parent_entry, Name reference_name,
412 Object child, const char* name_format_string = nullptr,
413 int field_offset = -1);
414
415 void SetUserGlobalReference(Object user_global);
416 void SetRootGcRootsReference();
417 void SetGcRootsReference(Root root);
418 void SetGcSubrootReference(Root root, const char* description, bool is_weak,
419 Object child);
420 const char* GetStrongGcSubrootName(Object object);
421 void TagObject(Object obj, const char* tag);
422
423 HeapEntry* GetEntry(Object obj);
424
425 Heap* heap_;
426 HeapSnapshot* snapshot_;
427 StringsStorage* names_;
428 HeapObjectsMap* heap_object_map_;
429 SnapshottingProgressReportingInterface* progress_;
430 HeapSnapshotGenerator* generator_ = nullptr;
431 std::unordered_map<JSGlobalObject, const char*, Object::Hasher> objects_tags_;
432 std::unordered_map<Object, const char*, Object::Hasher>
433 strong_gc_subroot_names_;
434 std::unordered_set<JSGlobalObject, Object::Hasher> user_roots_;
435 v8::HeapProfiler::ObjectNameResolver* global_object_name_resolver_;
436
437 std::vector<bool> visited_fields_;
438
439 friend class IndexedReferencesExtractor;
440 friend class RootsReferencesExtractor;
441
442 DISALLOW_COPY_AND_ASSIGN(V8HeapExplorer);
443};
444
445// An implementation of retained native objects extractor.
446class NativeObjectsExplorer {
447 public:
448 NativeObjectsExplorer(HeapSnapshot* snapshot,
449 SnapshottingProgressReportingInterface* progress);
450 bool IterateAndExtractReferences(HeapSnapshotGenerator* generator);
451
452 private:
453 HeapEntry* EntryForEmbedderGraphNode(EmbedderGraph::Node* node);
454
455 Isolate* isolate_;
456 HeapSnapshot* snapshot_;
457 StringsStorage* names_;
458 std::unique_ptr<HeapEntriesAllocator> embedder_graph_entries_allocator_;
459 // Used during references extraction.
460 HeapSnapshotGenerator* generator_ = nullptr;
461
462 static HeapThing const kNativesRootObject;
463
464 friend class GlobalHandlesExtractor;
465
466 DISALLOW_COPY_AND_ASSIGN(NativeObjectsExplorer);
467};
468
469class HeapSnapshotGenerator : public SnapshottingProgressReportingInterface {
470 public:
471 // The HeapEntriesMap instance is used to track a mapping between
472 // real heap objects and their representations in heap snapshots.
473 using HeapEntriesMap = std::unordered_map<HeapThing, HeapEntry*>;
474
475 HeapSnapshotGenerator(HeapSnapshot* snapshot,
476 v8::ActivityControl* control,
477 v8::HeapProfiler::ObjectNameResolver* resolver,
478 Heap* heap);
479 bool GenerateSnapshot();
480
481 HeapEntry* FindEntry(HeapThing ptr) {
482 auto it = entries_map_.find(ptr);
483 return it != entries_map_.end() ? it->second : nullptr;
484 }
485
486 HeapEntry* AddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
487 return entries_map_.emplace(ptr, allocator->AllocateEntry(ptr))
488 .first->second;
489 }
490
491 HeapEntry* FindOrAddEntry(HeapThing ptr, HeapEntriesAllocator* allocator) {
492 HeapEntry* entry = FindEntry(ptr);
493 return entry != nullptr ? entry : AddEntry(ptr, allocator);
494 }
495
496 private:
497 bool FillReferences();
498 void ProgressStep() override;
499 bool ProgressReport(bool force = false) override;
500 void InitProgressCounter();
501
502 HeapSnapshot* snapshot_;
503 v8::ActivityControl* control_;
504 V8HeapExplorer v8_heap_explorer_;
505 NativeObjectsExplorer dom_explorer_;
506 // Mapping from HeapThing pointers to HeapEntry indices.
507 HeapEntriesMap entries_map_;
508 // Used during snapshot generation.
509 int progress_counter_;
510 int progress_total_;
511 Heap* heap_;
512
513 DISALLOW_COPY_AND_ASSIGN(HeapSnapshotGenerator);
514};
515
516class OutputStreamWriter;
517
518class HeapSnapshotJSONSerializer {
519 public:
520 explicit HeapSnapshotJSONSerializer(HeapSnapshot* snapshot)
521 : snapshot_(snapshot),
522 strings_(StringsMatch),
523 next_node_id_(1),
524 next_string_id_(1),
525 writer_(nullptr) {}
526 void Serialize(v8::OutputStream* stream);
527
528 private:
529 V8_INLINE static bool StringsMatch(void* key1, void* key2) {
530 return strcmp(reinterpret_cast<char*>(key1),
531 reinterpret_cast<char*>(key2)) == 0;
532 }
533
534 V8_INLINE static uint32_t StringHash(const void* string);
535
536 int GetStringId(const char* s);
537 V8_INLINE int to_node_index(const HeapEntry* e);
538 V8_INLINE int to_node_index(int entry_index);
539 void SerializeEdge(HeapGraphEdge* edge, bool first_edge);
540 void SerializeEdges();
541 void SerializeImpl();
542 void SerializeNode(const HeapEntry* entry);
543 void SerializeNodes();
544 void SerializeSnapshot();
545 void SerializeTraceTree();
546 void SerializeTraceNode(AllocationTraceNode* node);
547 void SerializeTraceNodeInfos();
548 void SerializeSamples();
549 void SerializeString(const unsigned char* s);
550 void SerializeStrings();
551 void SerializeLocation(const SourceLocation& location);
552 void SerializeLocations();
553
554 static const int kEdgeFieldsCount;
555 static const int kNodeFieldsCount;
556
557 HeapSnapshot* snapshot_;
558 base::CustomMatcherHashMap strings_;
559 int next_node_id_;
560 int next_string_id_;
561 OutputStreamWriter* writer_;
562
563 friend class HeapSnapshotJSONSerializerEnumerator;
564 friend class HeapSnapshotJSONSerializerIterator;
565
566 DISALLOW_COPY_AND_ASSIGN(HeapSnapshotJSONSerializer);
567};
568
569
570} // namespace internal
571} // namespace v8
572
573#endif // V8_PROFILER_HEAP_SNAPSHOT_GENERATOR_H_
574