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#include "src/api.h"
10#include "src/base/ieee754.h"
11#include "src/base/utils/random-number-generator.h"
12#include "src/frames-inl.h"
13#include "src/heap/heap.h"
14#include "src/isolate.h"
15#include "src/profiler/strings-storage.h"
16
17namespace v8 {
18namespace internal {
19
20// We sample with a Poisson process, with constant average sampling interval.
21// This follows the exponential probability distribution with parameter
22// λ = 1/rate where rate is the average number of bytes between samples.
23//
24// Let u be a uniformly distributed random number between 0 and 1, then
25// next_sample = (- ln u) / λ
26intptr_t SamplingAllocationObserver::GetNextSampleInterval(uint64_t rate) {
27  if (FLAG_sampling_heap_profiler_suppress_randomness) {
28    return static_cast<intptr_t>(rate);
29  }
30  double u = random_->NextDouble();
31  double next = (-base::ieee754::log(u)) * rate;
32  return next < kPointerSize
33             ? kPointerSize
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.
44v8::AllocationProfile::Allocation SamplingHeapProfiler::ScaleSample(
45    size_t size, unsigned int count) {
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
51SamplingHeapProfiler::SamplingHeapProfiler(
52    Heap* heap, StringsStorage* names, uint64_t rate, int stack_depth,
53    v8::HeapProfiler::SamplingFlags flags)
54    : isolate_(heap->isolate()),
55      heap_(heap),
56      new_space_observer_(new SamplingAllocationObserver(
57          heap_, static_cast<intptr_t>(rate), rate, this,
58          heap->isolate()->random_number_generator())),
59      other_spaces_observer_(new SamplingAllocationObserver(
60          heap_, static_cast<intptr_t>(rate), rate, this,
61          heap->isolate()->random_number_generator())),
62      names_(names),
63      profile_root_(nullptr, "(root)", v8::UnboundScript::kNoScriptId, 0),
64      samples_(),
65      stack_depth_(stack_depth),
66      rate_(rate),
67      flags_(flags) {
68  CHECK_GT(rate_, 0);
69  heap->new_space()->AddAllocationObserver(new_space_observer_.get());
70  AllSpaces spaces(heap);
71  for (Space* space = spaces.next(); space != nullptr; space = spaces.next()) {
72    if (space != heap->new_space()) {
73      space->AddAllocationObserver(other_spaces_observer_.get());
74    }
75  }
76}
77
78
79SamplingHeapProfiler::~SamplingHeapProfiler() {
80  heap_->new_space()->RemoveAllocationObserver(new_space_observer_.get());
81  AllSpaces spaces(heap_);
82  for (Space* space = spaces.next(); space != nullptr; space = spaces.next()) {
83    if (space != heap_->new_space()) {
84      space->RemoveAllocationObserver(other_spaces_observer_.get());
85    }
86  }
87
88  for (auto sample : samples_) {
89    delete sample;
90  }
91  std::set<Sample*> empty;
92  samples_.swap(empty);
93}
94
95
96void SamplingHeapProfiler::SampleObject(Address soon_object, size_t size) {
97  DisallowHeapAllocation no_allocation;
98
99  HandleScope scope(isolate_);
100  HeapObject* heap_object = HeapObject::FromAddress(soon_object);
101  Handle<Object> obj(heap_object, isolate_);
102
103  // Mark the new block as FreeSpace to make sure the heap is iterable while we
104  // are taking the sample.
105  heap()->CreateFillerObjectAt(soon_object, static_cast<int>(size),
106                               ClearRecordedSlots::kNo);
107
108  Local<v8::Value> loc = v8::Utils::ToLocal(obj);
109
110  AllocationNode* node = AddStack();
111  node->allocations_[size]++;
112  Sample* sample = new Sample(size, node, loc, this);
113  samples_.insert(sample);
114  sample->global.SetWeak(sample, OnWeakCallback, WeakCallbackType::kParameter);
115  sample->global.MarkIndependent();
116}
117
118void SamplingHeapProfiler::OnWeakCallback(
119    const WeakCallbackInfo<Sample>& data) {
120  Sample* sample = data.GetParameter();
121  AllocationNode* node = sample->owner;
122  DCHECK(node->allocations_[sample->size] > 0);
123  node->allocations_[sample->size]--;
124  if (node->allocations_[sample->size] == 0) {
125    node->allocations_.erase(sample->size);
126    while (node->allocations_.empty() && node->children_.empty() &&
127           node->parent_ && !node->parent_->pinned_) {
128      AllocationNode* parent = node->parent_;
129      AllocationNode::FunctionId id = AllocationNode::function_id(
130          node->script_id_, node->script_position_, node->name_);
131      parent->children_.erase(id);
132      delete node;
133      node = parent;
134    }
135  }
136  sample->profiler->samples_.erase(sample);
137  delete sample;
138}
139
140SamplingHeapProfiler::AllocationNode*
141SamplingHeapProfiler::AllocationNode::FindOrAddChildNode(const char* name,
142                                                         int script_id,
143                                                         int start_position) {
144  FunctionId id = function_id(script_id, start_position, name);
145  auto it = children_.find(id);
146  if (it != children_.end()) {
147    DCHECK(strcmp(it->second->name_, name) == 0);
148    return it->second;
149  }
150  auto child = new AllocationNode(this, name, script_id, start_position);
151  children_.insert(std::make_pair(id, child));
152  return child;
153}
154
155SamplingHeapProfiler::AllocationNode* SamplingHeapProfiler::AddStack() {
156  AllocationNode* node = &profile_root_;
157
158  std::vector<SharedFunctionInfo*> stack;
159  JavaScriptFrameIterator it(isolate_);
160  int frames_captured = 0;
161  while (!it.done() && frames_captured < stack_depth_) {
162    JavaScriptFrame* frame = it.frame();
163    SharedFunctionInfo* shared = frame->function()->shared();
164    stack.push_back(shared);
165
166    frames_captured++;
167    it.Advance();
168  }
169
170  if (frames_captured == 0) {
171    const char* name = nullptr;
172    switch (isolate_->current_vm_state()) {
173      case GC:
174        name = "(GC)";
175        break;
176      case COMPILER:
177        name = "(COMPILER)";
178        break;
179      case OTHER:
180        name = "(V8 API)";
181        break;
182      case EXTERNAL:
183        name = "(EXTERNAL)";
184        break;
185      case IDLE:
186        name = "(IDLE)";
187        break;
188      case JS:
189        name = "(JS)";
190        break;
191    }
192    return node->FindOrAddChildNode(name, v8::UnboundScript::kNoScriptId, 0);
193  }
194
195  // We need to process the stack in reverse order as the top of the stack is
196  // the first element in the list.
197  for (auto it = stack.rbegin(); it != stack.rend(); ++it) {
198    SharedFunctionInfo* shared = *it;
199    const char* name = this->names()->GetFunctionName(shared->DebugName());
200    int script_id = v8::UnboundScript::kNoScriptId;
201    if (shared->script()->IsScript()) {
202      Script* script = Script::cast(shared->script());
203      script_id = script->id();
204    }
205    node = node->FindOrAddChildNode(name, script_id, shared->start_position());
206  }
207  return node;
208}
209
210v8::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      scripts.find(node->script_id_) != scripts.end()) {
224    // Cannot use std::map<T>::at because it is not available on android.
225    auto non_const_scripts =
226        const_cast<std::map<int, Handle<Script>>&>(scripts);
227    Handle<Script> script = non_const_scripts[node->script_id_];
228    if (!script.is_null()) {
229      if (script->name()->IsName()) {
230        Name* name = Name::cast(script->name());
231        script_name = ToApiHandle<v8::String>(
232            isolate_->factory()->InternalizeUtf8String(names_->GetName(name)));
233      }
234      line = 1 + Script::GetLineNumber(script, node->script_position_);
235      column = 1 + Script::GetColumnNumber(script, node->script_position_);
236    }
237  }
238  for (auto alloc : node->allocations_) {
239    allocations.push_back(ScaleSample(alloc.first, alloc.second));
240  }
241
242  profile->nodes().push_back(v8::AllocationProfile::Node(
243      {ToApiHandle<v8::String>(
244           isolate_->factory()->InternalizeUtf8String(node->name_)),
245       script_name, node->script_id_, node->script_position_, line, column,
246       std::vector<v8::AllocationProfile::Node*>(), allocations}));
247  v8::AllocationProfile::Node* current = &profile->nodes().back();
248  // The children map may have nodes inserted into it during translation
249  // because the translation may allocate strings on the JS heap that have
250  // the potential to be sampled. That's ok since map iterators are not
251  // invalidated upon std::map insertion.
252  for (auto it : node->children_) {
253    current->children.push_back(
254        TranslateAllocationNode(profile, it.second, scripts));
255  }
256  node->pinned_ = false;
257  return current;
258}
259
260v8::AllocationProfile* SamplingHeapProfiler::GetAllocationProfile() {
261  if (flags_ & v8::HeapProfiler::kSamplingForceGC) {
262    isolate_->heap()->CollectAllGarbage(Heap::kNoGCFlags,
263                                        "SamplingHeapProfiler");
264  }
265  // To resolve positions to line/column numbers, we will need to look up
266  // scripts. Build a map to allow fast mapping from script id to script.
267  std::map<int, Handle<Script>> scripts;
268  {
269    Script::Iterator iterator(isolate_);
270    while (Script* script = iterator.Next()) {
271      scripts[script->id()] = handle(script);
272    }
273  }
274  auto profile = new v8::internal::AllocationProfile();
275  TranslateAllocationNode(profile, &profile_root_, scripts);
276  return profile;
277}
278
279
280}  // namespace internal
281}  // namespace v8
282