1 // Copyright 2015 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 #include "src/profiler/sampling-heap-profiler.h"
6
7 #include <stdint.h>
8 #include <memory>
9
10 #include "src/api/api-inl.h"
11 #include "src/base/ieee754.h"
12 #include "src/base/utils/random-number-generator.h"
13 #include "src/execution/frames-inl.h"
14 #include "src/execution/isolate.h"
15 #include "src/heap/heap.h"
16 #include "src/profiler/strings-storage.h"
17
18 namespace v8 {
19 namespace internal {
20
21 // We sample with a Poisson process, with constant average sampling interval.
22 // This follows the exponential probability distribution with parameter
23 // λ = 1/rate where rate is the average number of bytes between samples.
24 //
25 // Let u be a uniformly distributed random number between 0 and 1, then
26 // next_sample = (- ln u) / λ
GetNextSampleInterval(uint64_t rate)27 intptr_t SamplingHeapProfiler::Observer::GetNextSampleInterval(uint64_t rate) {
28 if (FLAG_sampling_heap_profiler_suppress_randomness)
29 return static_cast<intptr_t>(rate);
30 double u = random_->NextDouble();
31 double next = (-base::ieee754::log(u)) * rate;
32 return next < kTaggedSize
33 ? kTaggedSize
34 : (next > INT_MAX ? INT_MAX : static_cast<intptr_t>(next));
35 }
36
37 // Samples were collected according to a poisson process. Since we have not
38 // recorded all allocations, we must approximate the shape of the underlying
39 // space of allocations based on the samples we have collected. Given that
40 // we sample at rate R, the probability that an allocation of size S will be
41 // sampled is 1-exp(-S/R). This function uses the above probability to
42 // approximate the true number of allocations with size *size* given that
43 // *count* samples were observed.
ScaleSample(size_t size,unsigned int count) const44 v8::AllocationProfile::Allocation SamplingHeapProfiler::ScaleSample(
45 size_t size, unsigned int count) const {
46 double scale = 1.0 / (1.0 - std::exp(-static_cast<double>(size) / rate_));
47 // Round count instead of truncating.
48 return {size, static_cast<unsigned int>(count * scale + 0.5)};
49 }
50
SamplingHeapProfiler(Heap * heap,StringsStorage * names,uint64_t rate,int stack_depth,v8::HeapProfiler::SamplingFlags flags)51 SamplingHeapProfiler::SamplingHeapProfiler(
52 Heap* heap, StringsStorage* names, uint64_t rate, int stack_depth,
53 v8::HeapProfiler::SamplingFlags flags)
54 : isolate_(Isolate::FromHeap(heap)),
55 heap_(heap),
56 allocation_observer_(heap_, static_cast<intptr_t>(rate), rate, this,
57 isolate_->random_number_generator()),
58 names_(names),
59 profile_root_(nullptr, "(root)", v8::UnboundScript::kNoScriptId, 0,
60 next_node_id()),
61 stack_depth_(stack_depth),
62 rate_(rate),
63 flags_(flags) {
64 CHECK_GT(rate_, 0u);
65 heap_->AddAllocationObserversToAllSpaces(&allocation_observer_,
66 &allocation_observer_);
67 }
68
~SamplingHeapProfiler()69 SamplingHeapProfiler::~SamplingHeapProfiler() {
70 heap_->RemoveAllocationObserversFromAllSpaces(&allocation_observer_,
71 &allocation_observer_);
72 }
73
SampleObject(Address soon_object,size_t size)74 void SamplingHeapProfiler::SampleObject(Address soon_object, size_t size) {
75 DisallowGarbageCollection no_gc;
76
77 // Check if the area is iterable by confirming that it starts with a map.
78 DCHECK(HeapObject::FromAddress(soon_object).map(isolate_).IsMap(isolate_));
79
80 HandleScope scope(isolate_);
81 HeapObject heap_object = HeapObject::FromAddress(soon_object);
82 Handle<Object> obj(heap_object, isolate_);
83
84 Local<v8::Value> loc = v8::Utils::ToLocal(obj);
85
86 AllocationNode* node = AddStack();
87 node->allocations_[size]++;
88 auto sample =
89 std::make_unique<Sample>(size, node, loc, this, next_sample_id());
90 sample->global.SetWeak(sample.get(), OnWeakCallback,
91 WeakCallbackType::kParameter);
92 samples_.emplace(sample.get(), std::move(sample));
93 }
94
OnWeakCallback(const WeakCallbackInfo<Sample> & data)95 void SamplingHeapProfiler::OnWeakCallback(
96 const WeakCallbackInfo<Sample>& data) {
97 Sample* sample = data.GetParameter();
98 AllocationNode* node = sample->owner;
99 DCHECK_GT(node->allocations_[sample->size], 0);
100 node->allocations_[sample->size]--;
101 if (node->allocations_[sample->size] == 0) {
102 node->allocations_.erase(sample->size);
103 while (node->allocations_.empty() && node->children_.empty() &&
104 node->parent_ && !node->parent_->pinned_) {
105 AllocationNode* parent = node->parent_;
106 AllocationNode::FunctionId id = AllocationNode::function_id(
107 node->script_id_, node->script_position_, node->name_);
108 parent->children_.erase(id);
109 node = parent;
110 }
111 }
112 sample->profiler->samples_.erase(sample);
113 // sample is deleted because its unique ptr was erased from samples_.
114 }
115
FindOrAddChildNode(AllocationNode * parent,const char * name,int script_id,int start_position)116 SamplingHeapProfiler::AllocationNode* SamplingHeapProfiler::FindOrAddChildNode(
117 AllocationNode* parent, const char* name, int script_id,
118 int start_position) {
119 AllocationNode::FunctionId id =
120 AllocationNode::function_id(script_id, start_position, name);
121 AllocationNode* child = parent->FindChildNode(id);
122 if (child) {
123 DCHECK_EQ(strcmp(child->name_, name), 0);
124 return child;
125 }
126 auto new_child = std::make_unique<AllocationNode>(
127 parent, name, script_id, start_position, next_node_id());
128 return parent->AddChildNode(id, std::move(new_child));
129 }
130
AddStack()131 SamplingHeapProfiler::AllocationNode* SamplingHeapProfiler::AddStack() {
132 AllocationNode* node = &profile_root_;
133
134 std::vector<SharedFunctionInfo> stack;
135 JavaScriptFrameIterator frame_it(isolate_);
136 int frames_captured = 0;
137 bool found_arguments_marker_frames = false;
138 while (!frame_it.done() && frames_captured < stack_depth_) {
139 JavaScriptFrame* frame = frame_it.frame();
140 // If we are materializing objects during deoptimization, inlined
141 // closures may not yet be materialized, and this includes the
142 // closure on the stack. Skip over any such frames (they'll be
143 // in the top frames of the stack). The allocations made in this
144 // sensitive moment belong to the formerly optimized frame anyway.
145 if (frame->unchecked_function().IsJSFunction()) {
146 SharedFunctionInfo shared = frame->function().shared();
147 stack.push_back(shared);
148 frames_captured++;
149 } else {
150 found_arguments_marker_frames = true;
151 }
152 frame_it.Advance();
153 }
154
155 if (frames_captured == 0) {
156 const char* name = nullptr;
157 switch (isolate_->current_vm_state()) {
158 case GC:
159 name = "(GC)";
160 break;
161 case PARSER:
162 name = "(PARSER)";
163 break;
164 case COMPILER:
165 name = "(COMPILER)";
166 break;
167 case BYTECODE_COMPILER:
168 name = "(BYTECODE_COMPILER)";
169 break;
170 case OTHER:
171 name = "(V8 API)";
172 break;
173 case EXTERNAL:
174 name = "(EXTERNAL)";
175 break;
176 case IDLE:
177 name = "(IDLE)";
178 break;
179 // Treat atomics wait as a normal JS event; we don't care about the
180 // difference for allocations.
181 case ATOMICS_WAIT:
182 case JS:
183 name = "(JS)";
184 break;
185 }
186 return FindOrAddChildNode(node, name, v8::UnboundScript::kNoScriptId, 0);
187 }
188
189 // We need to process the stack in reverse order as the top of the stack is
190 // the first element in the list.
191 for (auto it = stack.rbegin(); it != stack.rend(); ++it) {
192 SharedFunctionInfo shared = *it;
193 const char* name = this->names()->GetCopy(shared.DebugNameCStr().get());
194 int script_id = v8::UnboundScript::kNoScriptId;
195 if (shared.script().IsScript()) {
196 Script script = Script::cast(shared.script());
197 script_id = script.id();
198 }
199 node = FindOrAddChildNode(node, name, script_id, shared.StartPosition());
200 }
201
202 if (found_arguments_marker_frames) {
203 node =
204 FindOrAddChildNode(node, "(deopt)", v8::UnboundScript::kNoScriptId, 0);
205 }
206
207 return node;
208 }
209
TranslateAllocationNode(AllocationProfile * profile,SamplingHeapProfiler::AllocationNode * node,const std::map<int,Handle<Script>> & scripts)210 v8::AllocationProfile::Node* SamplingHeapProfiler::TranslateAllocationNode(
211 AllocationProfile* profile, SamplingHeapProfiler::AllocationNode* node,
212 const std::map<int, Handle<Script>>& scripts) {
213 // By pinning the node we make sure its children won't get disposed if
214 // a GC kicks in during the tree retrieval.
215 node->pinned_ = true;
216 Local<v8::String> script_name =
217 ToApiHandle<v8::String>(isolate_->factory()->InternalizeUtf8String(""));
218 int line = v8::AllocationProfile::kNoLineNumberInfo;
219 int column = v8::AllocationProfile::kNoColumnNumberInfo;
220 std::vector<v8::AllocationProfile::Allocation> allocations;
221 allocations.reserve(node->allocations_.size());
222 if (node->script_id_ != v8::UnboundScript::kNoScriptId) {
223 auto script_iterator = scripts.find(node->script_id_);
224 if (script_iterator != scripts.end()) {
225 Handle<Script> script = script_iterator->second;
226 if (script->name().IsName()) {
227 Name name = Name::cast(script->name());
228 script_name = ToApiHandle<v8::String>(
229 isolate_->factory()->InternalizeUtf8String(names_->GetName(name)));
230 }
231 line = 1 + Script::GetLineNumber(script, node->script_position_);
232 column = 1 + Script::GetColumnNumber(script, node->script_position_);
233 }
234 }
235 for (auto alloc : node->allocations_) {
236 allocations.push_back(ScaleSample(alloc.first, alloc.second));
237 }
238
239 profile->nodes_.push_back(v8::AllocationProfile::Node{
240 ToApiHandle<v8::String>(
241 isolate_->factory()->InternalizeUtf8String(node->name_)),
242 script_name, node->script_id_, node->script_position_, line, column,
243 node->id_, std::vector<v8::AllocationProfile::Node*>(), allocations});
244 v8::AllocationProfile::Node* current = &profile->nodes_.back();
245 // The |children_| map may have nodes inserted into it during translation
246 // because the translation may allocate strings on the JS heap that have
247 // the potential to be sampled. That's ok since map iterators are not
248 // invalidated upon std::map insertion.
249 for (const auto& it : node->children_) {
250 current->children.push_back(
251 TranslateAllocationNode(profile, it.second.get(), scripts));
252 }
253 node->pinned_ = false;
254 return current;
255 }
256
GetAllocationProfile()257 v8::AllocationProfile* SamplingHeapProfiler::GetAllocationProfile() {
258 if (flags_ & v8::HeapProfiler::kSamplingForceGC) {
259 isolate_->heap()->CollectAllGarbage(
260 Heap::kNoGCFlags, GarbageCollectionReason::kSamplingProfiler);
261 }
262 // To resolve positions to line/column numbers, we will need to look up
263 // scripts. Build a map to allow fast mapping from script id to script.
264 std::map<int, Handle<Script>> scripts;
265 {
266 Script::Iterator iterator(isolate_);
267 for (Script script = iterator.Next(); !script.is_null();
268 script = iterator.Next()) {
269 scripts[script.id()] = handle(script, isolate_);
270 }
271 }
272 auto profile = new v8::internal::AllocationProfile();
273 TranslateAllocationNode(profile, &profile_root_, scripts);
274 profile->samples_ = BuildSamples();
275
276 return profile;
277 }
278
279 const std::vector<v8::AllocationProfile::Sample>
BuildSamples() const280 SamplingHeapProfiler::BuildSamples() const {
281 std::vector<v8::AllocationProfile::Sample> samples;
282 samples.reserve(samples_.size());
283 for (const auto& it : samples_) {
284 const Sample* sample = it.second.get();
285 samples.emplace_back(v8::AllocationProfile::Sample{
286 sample->owner->id_, sample->size, ScaleSample(sample->size, 1).count,
287 sample->sample_id});
288 }
289 return samples;
290 }
291
292 } // namespace internal
293 } // namespace v8
294