[profiler] Implement POC Sampling Heap Profiler

src/profiler/sampling-heap-profiler.cc

+// Copyright 2015 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/profiler/sampling-heap-profiler.h"
+
+#include <stdint.h>
+#include <memory>
+#include "src/api.h"
+#include "src/frames-inl.h"
+#include "src/heap/heap.h"
+#include "src/isolate.h"
+#include "src/profiler/strings-storage.h"
+
+namespace v8 {
+namespace internal {
+
+SamplingHeapProfiler::SamplingHeapProfiler(Heap* heap, StringsStorage* names,
+                                           uint64_t rate, int stack_depth)
+    : InlineAllocationObserver(GetNextSampleInterval(
+          heap->isolate()->random_number_generator(), rate)),
+      isolate_(heap->isolate()),
+      heap_(heap),
+      random_(isolate_->random_number_generator()),
+      names_(names),
+      samples_(),
+      rate_(rate),
+      stack_depth_(stack_depth) {
+  heap->new_space()->AddInlineAllocationObserver(this);
+}
+
+
+SamplingHeapProfiler::~SamplingHeapProfiler() {
+  heap_->new_space()->RemoveInlineAllocationObserver(this);
+
+  // Clear samples and drop all the weak references we are keeping.
+  std::set<SampledAllocation*>::iterator it;
+  for (it = samples_.begin(); it != samples_.end(); ++it) {
+    delete *it;
+  }
+  std::set<SampledAllocation*> empty;
+  samples_.swap(empty);
+}
+
+void SamplingHeapProfiler::Step(int bytes_allocated, Address soon_object,
+                                size_t size) {
+  DCHECK(heap_->gc_state() == Heap::NOT_IN_GC);
+  DCHECK(soon_object);
+  SampleObject(soon_object, size);
+}
+
+
+void SamplingHeapProfiler::SampleObject(Address soon_object, size_t size) {
+  DisallowHeapAllocation no_allocation;
+
+  HandleScope scope(isolate_);
+  HeapObject* heap_object = HeapObject::FromAddress(soon_object);
+  Handle<Object> obj(heap_object, isolate_);
+
+  // Mark the new block as FreeSpace to make sure the heap is iterable while we
+  // are taking the sample.
+  heap()->CreateFillerObjectAt(soon_object, static_cast<int>(size));
+
+  Local<v8::Value> loc = v8::Utils::ToLocal(obj);
+
+  SampledAllocation* sample =
+      new SampledAllocation(this, isolate_, loc, size, stack_depth_);
+  samples_.insert(sample);
+}
+
+
+// We sample with a Poisson process, with constant average sampling interval.
+// This follows the exponential probability distribution with parameter
+// λ = 1/rate where rate is the average number of bytes between samples.
+//
+// Let u be a uniformly distributed random number between 0 and 1, then
+// next_sample = (- ln u) / λ
+intptr_t SamplingHeapProfiler::GetNextSampleInterval(
+    base::RandomNumberGenerator* random, uint64_t rate) {
+  double u = random->NextDouble();
+  double next = (-std::log(u)) * rate;
+  return next < kPointerSize
+             ? kPointerSize
+             : (next > INTPTR_MAX ? INTPTR_MAX : static_cast<intptr_t>(next));

[alph, 2016/01/20 23:13:01]

I have a little concern here. The Poisson distribution works fine in a
theoretical case where the stream is infinite.

But in reality it could happen that we get a fairly large number for the next
interval and we just end up having no samples collected for the profile.

Though that's seems to only be possible when random returns zero, so the
probability is quite low. But nevertheless, how about using some sane number
instead of INTPTR_MAX? wdyt?

[ofrobots, 2016/01/21 03:03:28]

The probability of `next` being close to INTPTR_MAX is not just low, it is
astronomically improbable given the poisson probability distribution.
Regardless, I changed it to INT_MAX instead because INTPTR_MAX doesn't seem to
be defined in android's stdint.h. INT_MAX is large enough, but this will break
down if the clients of the profiler want to use a sample rate within an order of
magnitude of INT_MAX. :/

[alph, 2016/01/21 03:21:55]

Well, the probability of getting a weird number is the probability of getting
zero out of NextDouble which is 2^-52 or 10^-15, which is pretty low.

The next possible value which is -log(2^-52) =~ 36 looks safe.

+}
+
+
+void SamplingHeapProfiler::SampledAllocation::OnWeakCallback(
+    const WeakCallbackInfo<SampledAllocation>& data) {
+  SampledAllocation* sample = data.GetParameter();
+  sample->sampling_heap_profiler_->samples_.erase(sample);
+  delete sample;
+}
+
+
+SamplingHeapProfiler::FunctionInfo::FunctionInfo(SharedFunctionInfo* shared,
+                                                 StringsStorage* names)
+    : name_(names->GetFunctionName(shared->DebugName())),
+      script_name_(""),
+      script_id_(v8::UnboundScript::kNoScriptId),
+      start_position_(0) {
+  if (shared->script()->IsScript()) {
+    Script* script = Script::cast(shared->script());
+    script_id_ = script->id();
+    start_position_ = shared->start_position();

[alph, 2016/01/20 23:13:01]

Can you always set start_position_?

[ofrobots, 2016/01/21 03:03:28]

Done.

+    if (script->name()->IsName()) {
+      Name* name = Name::cast(script->name());
+      script_name_ = names->GetName(name);
+    }
+  }
+}
+
+
+SamplingHeapProfiler::SampledAllocation::SampledAllocation(
+    SamplingHeapProfiler* sampling_heap_profiler, Isolate* isolate,
+    Local<Value> local, size_t size, int max_frames)
+    : sampling_heap_profiler_(sampling_heap_profiler),
+      global_(reinterpret_cast<v8::Isolate*>(isolate), local),
+      size_(size) {
+  global_.SetWeak(this, OnWeakCallback, WeakCallbackType::kParameter);
+
+  StackTraceFrameIterator it(isolate);
+  int frames_captured = 0;
+  while (!it.done() && frames_captured < max_frames) {
+    JavaScriptFrame* frame = it.frame();
+    SharedFunctionInfo* shared = frame->function()->shared();
+    stack_.push_back(new FunctionInfo(shared, sampling_heap_profiler->names()));
+
+    frames_captured++;
+    it.Advance();
+  }
+
+  if (frames_captured == 0) {
+    const char* name = nullptr;
+    switch (isolate->current_vm_state()) {

[alph, 2016/01/20 23:13:01]

Could you reuse StateToString here?
https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/vm-state-in...

[ofrobots, 2016/01/21 03:03:28]

The format returned by that isn't great for this purpose. The parentheses added
here make sure the function names are distinguishable from real JS functions
named 'GC' or 'COMPILER' etc.

+      case GC:
+        name = "(GC)";
+        break;
+      case COMPILER:
+        name = "(COMPILER)";
+        break;
+      case OTHER:
+        name = "(V8 API)";
+        break;
+      case EXTERNAL:
+        name = "(EXTERNAL)";
+        break;
+      case IDLE:
+        name = "(IDLE)";
+        break;
+      case JS:
+        name = "(JS)";
+        break;
+    }
+    stack_.push_back(
+        new FunctionInfo(name, "", v8::UnboundScript::kNoScriptId, 0));
+  }
+}
+
+
+SamplingHeapProfiler::Node* SamplingHeapProfiler::AllocateNode(
+    AllocationProfile& profile, const std::map<int, Script*>& scripts,
+    FunctionInfo* function_info) {
+  DCHECK(function_info->get_name());
+  DCHECK(function_info->get_script_name());
+
+  int line = v8::AllocationProfile::kNoLineNumberInfo;
+  int column = v8::AllocationProfile::kNoColumnNumberInfo;
+
+  if (function_info->get_script_id() != v8::UnboundScript::kNoScriptId) {
+    // Cannot use std::map<T>::at because it is not available on android.
+    auto non_const_scripts = const_cast<std::map<int, Script*>&>(scripts);
+    Handle<Script> script(non_const_scripts[function_info->get_script_id()]);
+
+    line =
+        1 + Script::GetLineNumber(script, function_info->get_start_position());
+    column = 1 + Script::GetColumnNumber(script,
+                                         function_info->get_start_position());
+  }
+
+  profile.nodes().push_back(
+      Node(ToApiHandle<v8::String>(isolate_->factory()->InternalizeUtf8String(
+               function_info->get_name())),
+           ToApiHandle<v8::String>(isolate_->factory()->InternalizeUtf8String(
+               function_info->get_script_name())),
+           function_info->get_script_id(), function_info->get_start_position(),
+           line, column));
+
+  return &profile.nodes().back();
+}
+
+
+SamplingHeapProfiler::Node* SamplingHeapProfiler::FindOrAddChildNode(
+    AllocationProfile& profile, const std::map<int, Script*>& scripts,
+    Node* parent, FunctionInfo* function_info) {
+  for (Node* child : parent->children) {
+    if (child->script_id == function_info->get_script_id() &&

[alph, 2016/01/20 23:13:01]

Makes sense to use a map for children.

[ofrobots, 2016/01/21 03:03:28]

I agree that this would be a nice optimization in the future. Do you think it
should be done before this CL lands?

[alph, 2016/01/21 03:21:55]

It affect the API, so if you want to change it it's better to do it rather
earlier than later.

+        child->start_position == function_info->get_start_position())
+      return child;
+  }
+  Node* child = AllocateNode(profile, scripts, function_info);
+  parent->children.push_back(child);
+  return child;
+}
+
+
+SamplingHeapProfiler::Node* SamplingHeapProfiler::AddStack(
+    AllocationProfile& profile, const std::map<int, Script*>& scripts,
+    const std::vector<FunctionInfo*>& stack) {
+  Node* node = profile.GetRootNode();
+
+  // We need to process the stack in reverse order as the top of the stack is
+  // the first element in the list.
+  for (auto it = stack.rbegin(); it != stack.rend(); ++it) {
+    FunctionInfo* function_info = *it;
+    node = FindOrAddChildNode(profile, scripts, node, function_info);
+  }
+  return node;
+}
+
+
+v8::AllocationProfile* SamplingHeapProfiler::GetAllocationProfile() {
+  // To resolve positions to line/column numbers, we will need to look up
+  // scripts. Build a map to allow fast mapping from script id to script.
+  std::map<int, Script*> scripts;
+  {
+    Script::Iterator iterator(isolate_);
+    Script* script;
+    while ((script = iterator.Next())) {
+      scripts[script->id()] = script;
+    }
+  }
+
+

[alph, 2016/01/20 23:13:01]

kill extra line

[ofrobots, 2016/01/21 03:03:28]

Done.

+  auto profile = new v8::internal::AllocationProfile();
+
+  // Create the root node.
+  FunctionInfo function_info("(root)", "", v8::UnboundScript::kNoScriptId, 0);

[alph, 2016/01/20 23:13:01]

Seems to be the last three parameters are never used. Kill them?

[ofrobots, 2016/01/21 03:03:28]

Done.

+  AllocateNode(*profile, scripts, &function_info);

[alph, 2016/01/20 23:13:01]

profile is an out parameter. Makes sense to pass it by pointer to emphasize that
fact.

[ofrobots, 2016/01/21 03:03:28]

Done.

+
+  for (SampledAllocation* allocation : samples_) {
+    Node* node = AddStack(*profile, scripts, allocation->get_stack());
+    node->allocations.push_back({allocation->get_size(), 1});
+  }
+
+  return profile;
+}
+
+
+}  // namespace internal
+}  // namespace v8