1// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_OBJECT_GRAPH_H_
6#define RUNTIME_VM_OBJECT_GRAPH_H_
7
8#include <memory>
9
10#include "vm/allocation.h"
11#include "vm/dart_api_state.h"
12#include "vm/thread_stack_resource.h"
13
14namespace dart {
15
16class Array;
17class Object;
18class CountingPage;
19
20#if !defined(PRODUCT)
21
22// Utility to traverse the object graph in an ordered fashion.
23// Example uses:
24// - find a retaining path from the isolate roots to a particular object, or
25// - determine how much memory is retained by some particular object(s).
26class ObjectGraph : public ThreadStackResource {
27 public:
28 class Stack;
29
30 // Allows climbing the search tree all the way to the root.
31 class StackIterator {
32 public:
33 // The object this iterator currently points to.
34 ObjectPtr Get() const;
35 // Returns false if there is no parent.
36 bool MoveToParent();
37 // Offset into parent for the pointer to current object. -1 if no parent.
38 intptr_t OffsetFromParentInWords() const;
39
40 private:
41 StackIterator(const Stack* stack, intptr_t index)
42 : stack_(stack), index_(index) {}
43 const Stack* stack_;
44 intptr_t index_;
45 friend class ObjectGraph::Stack;
46 DISALLOW_IMPLICIT_CONSTRUCTORS(StackIterator);
47 };
48
49 class Visitor {
50 public:
51 // Directs how the search should continue after visiting an object.
52 enum Direction {
53 kProceed, // Recurse on this object's pointers.
54 kBacktrack, // Ignore this object's pointers.
55 kAbort, // Terminate the entire search immediately.
56 };
57 virtual ~Visitor() {}
58 // Visits the object pointed to by *it. The iterator is only valid
59 // during this call. This method must not allocate from the heap or
60 // trigger GC in any way.
61 virtual Direction VisitObject(StackIterator* it) = 0;
62
63 virtual bool visit_weak_persistent_handles() const { return false; }
64
65 const char* gc_root_type = NULL;
66 bool is_traversing = false;
67 };
68
69 typedef struct {
70 intptr_t length;
71 const char* gc_root_type;
72 } RetainingPathResult;
73
74 explicit ObjectGraph(Thread* thread);
75 ~ObjectGraph();
76
77 // Visits all strongly reachable objects in the isolate's heap, in a
78 // pre-order, depth first traversal.
79 void IterateObjects(Visitor* visitor);
80 void IterateUserObjects(Visitor* visitor);
81
82 // Like 'IterateObjects', but restricted to objects reachable from 'root'
83 // (including 'root' itself).
84 void IterateObjectsFrom(const Object& root, Visitor* visitor);
85 void IterateObjectsFrom(intptr_t class_id,
86 HeapIterationScope* iteration,
87 Visitor* visitor);
88
89 // The number of bytes retained by 'obj'.
90 intptr_t SizeRetainedByInstance(const Object& obj);
91 intptr_t SizeReachableByInstance(const Object& obj);
92
93 // The number of bytes retained by the set of all objects of the given class.
94 intptr_t SizeRetainedByClass(intptr_t class_id);
95 intptr_t SizeReachableByClass(intptr_t class_id);
96
97 // Finds some retaining path from the isolate roots to 'obj'. Populates the
98 // provided array with pairs of (object, offset from parent in words),
99 // starting with 'obj' itself, as far as there is room. Returns the number
100 // of objects on the full path. A null input array behaves like a zero-length
101 // input array. The 'offset' of a root is -1.
102 //
103 // To break the trivial path, the handle 'obj' is temporarily cleared during
104 // the search, but restored before returning. If no path is found (i.e., the
105 // provided handle was the only way to reach the object), zero is returned.
106 RetainingPathResult RetainingPath(Object* obj, const Array& path);
107
108 // Find the objects that reference 'obj'. Populates the provided array with
109 // pairs of (object pointing to 'obj', offset of pointer in words), as far as
110 // there is room. Returns the number of objects found.
111 //
112 // An object for which this function answers no inbound references might still
113 // be live due to references from the stack or embedder handles.
114 intptr_t InboundReferences(Object* obj, const Array& references);
115
116 private:
117 DISALLOW_IMPLICIT_CONSTRUCTORS(ObjectGraph);
118};
119
120// Generates a dump of the heap, whose format is described in
121// runtime/vm/service/heap_snapshot.md.
122class HeapSnapshotWriter : public ThreadStackResource {
123 public:
124 explicit HeapSnapshotWriter(Thread* thread) : ThreadStackResource(thread) {}
125
126 void WriteSigned(int64_t value) {
127 EnsureAvailable((sizeof(value) * kBitsPerByte) / 7 + 1);
128
129 bool is_last_part = false;
130 while (!is_last_part) {
131 uint8_t part = value & 0x7F;
132 value >>= 7;
133 if ((value == 0 && (part & 0x40) == 0) ||
134 (value == static_cast<intptr_t>(-1) && (part & 0x40) != 0)) {
135 is_last_part = true;
136 } else {
137 part |= 0x80;
138 }
139 buffer_[size_++] = part;
140 }
141 }
142
143 void WriteUnsigned(uintptr_t value) {
144 EnsureAvailable((sizeof(value) * kBitsPerByte) / 7 + 1);
145
146 bool is_last_part = false;
147 while (!is_last_part) {
148 uint8_t part = value & 0x7F;
149 value >>= 7;
150 if (value == 0) {
151 is_last_part = true;
152 } else {
153 part |= 0x80;
154 }
155 buffer_[size_++] = part;
156 }
157 }
158
159 void WriteBytes(const void* bytes, intptr_t len) {
160 EnsureAvailable(len);
161 memmove(&buffer_[size_], bytes, len);
162 size_ += len;
163 }
164
165 void ScrubAndWriteUtf8(char* value) {
166 intptr_t len = strlen(value);
167 for (intptr_t i = len - 1; i >= 0; i--) {
168 if (value[i] == '@') {
169 value[i] = '\0';
170 }
171 }
172 WriteUtf8(value);
173 }
174
175 void WriteUtf8(const char* value) {
176 intptr_t len = strlen(value);
177 WriteUnsigned(len);
178 WriteBytes(value, len);
179 }
180
181 void AssignObjectId(ObjectPtr obj);
182 intptr_t GetObjectId(ObjectPtr obj) const;
183 void ClearObjectIds();
184 void CountReferences(intptr_t count);
185 void CountExternalProperty();
186
187 void Write();
188
189 private:
190 static const intptr_t kMetadataReservation = 512;
191 static const intptr_t kPreferredChunkSize = MB;
192
193 void SetupCountingPages();
194 bool OnImagePage(ObjectPtr obj) const;
195 CountingPage* FindCountingPage(ObjectPtr obj) const;
196
197 void EnsureAvailable(intptr_t needed);
198 void Flush(bool last = false);
199
200 uint8_t* buffer_ = nullptr;
201 intptr_t size_ = 0;
202 intptr_t capacity_ = 0;
203
204 intptr_t class_count_ = 0;
205 intptr_t object_count_ = 0;
206 intptr_t reference_count_ = 0;
207 intptr_t external_property_count_ = 0;
208
209 struct ImagePageRange {
210 uword base;
211 uword size;
212 };
213 // There are up to 4 images to consider:
214 // {instructions, data} x {vm isolate, current isolate}
215 static const intptr_t kMaxImagePages = 4;
216 ImagePageRange image_page_ranges_[kMaxImagePages];
217
218 DISALLOW_COPY_AND_ASSIGN(HeapSnapshotWriter);
219};
220
221class CountObjectsVisitor : public ObjectVisitor, public HandleVisitor {
222 public:
223 CountObjectsVisitor(Thread* thread, intptr_t class_count);
224 ~CountObjectsVisitor() {}
225
226 void VisitObject(ObjectPtr obj);
227 void VisitHandle(uword addr);
228
229 std::unique_ptr<intptr_t[]> new_count_;
230 std::unique_ptr<intptr_t[]> new_size_;
231 std::unique_ptr<intptr_t[]> new_external_size_;
232 std::unique_ptr<intptr_t[]> old_count_;
233 std::unique_ptr<intptr_t[]> old_size_;
234 std::unique_ptr<intptr_t[]> old_external_size_;
235
236 DISALLOW_COPY_AND_ASSIGN(CountObjectsVisitor);
237};
238
239#endif // !defined(PRODUCT)
240
241} // namespace dart
242
243#endif // RUNTIME_VM_OBJECT_GRAPH_H_
244