[profiler] Implement POC Sampling Heap Profiler

src/profiler/sampling-heap-profiler.cc

+// Copyright 2015 the V8 project authors. All rights reserved.

[alph, 2016/01/19 23:43:57]

ditto

[ofrobots, 2016/01/20 02:14:50]

This file was authored and published publicly (in the form of this CL) on Dec
29th 2015. The rule I am following is:

"the year the file was created in full numeric form (e.g., 2010); don't change
this if you edit, move, or copy the file."

+// 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 <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{};

[alph, 2016/01/19 23:43:57]

looks like a banned feature: http://chromium-cpp.appspot.com/

[ofrobots, 2016/01/20 02:14:50]

Done.

+  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.

[alph, 2016/01/19 23:43:57]

Out of curiosity, why it is better to have a random sampling intervals rather
than constant ones. E.g. CPU profilers usually use constant sampling interval.

[ofrobots, 2016/01/20 02:21:46]

The random sample interval makes sure that our observations don't bias towards
any application phases. For example imagine a program that allocates, in a loop,
512 bytes of Point objects followed by an Array. If we sampled with an interval
of 512 bytes, we will only observe the Array allocations and conclude that the
program only allocates Arrays.

This could affect the CPU profiler too, but is probably not that severe a
problem because IO latencies add random-ish perturbations to thread-scheduling.
Object allocation, on the other hand, typically can follow a very deterministic
allocation pattern, and it is important that any periods in the application
itself are not in phase with the 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 std::max(static_cast<intptr_t>(kPointerSize),
+                  static_cast<intptr_t>(next));

[alph, 2016/01/19 23:43:57]

looks like undefined behavior when next happens to be outside the intptr_t
limits.

[ofrobots, 2016/01/20 02:14:50]

Done.

+}
+
+
+void SamplingHeapProfiler::SampledAllocation::OnWeakCallback(
+    const WeakCallbackInfo<SampledAllocation>& data) {
+  SampledAllocation* sample = data.GetParameter();
+  sample->shp_->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();
+    if (script->name()->IsName()) {
+      Name* name = Name::cast(script->name());
+      script_name_ = names->GetName(name);
+    }
+  }
+}
+
+
+SamplingHeapProfiler::SampledAllocation::SampledAllocation(
+    SamplingHeapProfiler* shp, Isolate* isolate, Local<Value> local,
+    size_t size, int max_frames)
+    : shp_(shp),
+      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, shp->names()));
+
+    frames_captured++;
+    it.Advance();
+  }
+
+  if (frames_captured == 0) {
+    const char* name = nullptr;
+    switch (isolate->current_vm_state()) {
+      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(
+    v8::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) {
+    Handle<Script> script(scripts.at(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(

[alph, 2016/01/19 23:43:57]

looks like a banned feature. http://chromium-cpp.appspot.com/

[ofrobots, 2016/01/20 02:14:50]

Done.

+                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, std::vector<Node*>(),
+            std::vector<v8::AllocationProfile::Allocation>()}));
+
+  return &profile.nodes.back();
+}
+
+
+SamplingHeapProfiler::Node* SamplingHeapProfiler::FindOrAddChildNode(
+    v8::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() &&
+        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(
+    v8::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;
+    }
+  }
+
+
+  v8::AllocationProfile profile;
+
+  // Create the root node.
+  FunctionInfo function_info("(root)", "", v8::UnboundScript::kNoScriptId, 0);
+  AllocateNode(profile, scripts, &function_info);
+
+  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