[tracing] Switch to new heap dump format.

base/trace_event/heap_profiler_stack_frame_deduplicator_unittest.cc

 // Copyright 2015 The Chromium 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 "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
 
 #include <iterator>
 #include <memory>
 
 #include "base/macros.h"
+#include "base/memory/ptr_util.h"
 #include "base/trace_event/heap_profiler_allocation_context.h"
+#include "base/trace_event/heap_profiler_string_deduplicator.h"
+#include "base/trace_event/trace_event_argument.h"
+#include "base/values.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace base {
 namespace trace_event {
 
+namespace {
+
+constexpr static int kInvalidStackFrameIndex =
+    StackFrameDeduplicator::FrameNode::kInvalidFrameIndex;
+
+// Calls StackFrameDeduplicator::SerializeIncrementally() and returns
+// ListValue with serialized entries.
+std::unique_ptr<ListValue> SerializeEntriesIncrementally(
+    StackFrameDeduplicator* dedup) {
+  TracedValue traced_value;
+  traced_value.BeginArray("");
+  dedup->SerializeIncrementally(&traced_value);
+  traced_value.EndArray();
+
+  auto base_value = traced_value.ToBaseValue();
+  DictionaryValue* dictionary;
+  std::unique_ptr<Value> entries;
+  if (!base_value->GetAsDictionary(&dictionary) ||
+      !dictionary->Remove("", &entries)) {
+    return nullptr;
+  }
+  return ListValue::From(std::move(entries));
+}
+
+struct StackFrameMapping {
+  StackFrameMapping(int id,
+                    StackFrame frame,
+                    int parent_id = kInvalidStackFrameIndex)
+      : id(id), parent_id(parent_id) {
+    EXPECT_EQ(StackFrame::Type::TRACE_EVENT_NAME, frame.type);
+    name = static_cast<const char*>(frame.value);
+  }
+
+  int id;
+  const char* name;
+  int parent_id;
+};
+
+std::unique_ptr<ListValue> SerializeMappingsAsEntries(
+    StringDeduplicator* string_dedup,
+    std::initializer_list<StackFrameMapping> mappings) {
+  auto entries = MakeUnique<ListValue>();
+  for (const auto& mapping : mappings) {
+    auto entry = MakeUnique<DictionaryValue>();
+    entry->SetInteger("id", mapping.id);
+    entry->SetInteger("name_sid", string_dedup->Insert(mapping.name));
+    if (mapping.parent_id != kInvalidStackFrameIndex) {
+      entry->SetInteger("parent", mapping.parent_id);
+    }
+    entries->Append(std::move(entry));
+  }
+  return entries;
+}
+
+void ExpectIncrementalEntries(
+    StackFrameDeduplicator* dedup,
+    StringDeduplicator* string_dedup,
+    std::initializer_list<StackFrameMapping> mappings) {
+  auto entries = SerializeEntriesIncrementally(dedup);
+  ASSERT_TRUE(entries);
+
+  auto expected_entries = SerializeMappingsAsEntries(string_dedup, mappings);
+  ASSERT_TRUE(expected_entries->Equals(entries.get()))
+      << "expected_entries = " << *expected_entries << "entries = " << *entries;
+}
+
+}  // namespace
+
 // Define all strings once, because the deduplicator requires pointer equality,
 // and string interning is unreliable.
 StackFrame kBrowserMain = StackFrame::FromTraceEventName("BrowserMain");
 StackFrame kRendererMain = StackFrame::FromTraceEventName("RendererMain");
 StackFrame kCreateWidget = StackFrame::FromTraceEventName("CreateWidget");
 StackFrame kInitialize = StackFrame::FromTraceEventName("Initialize");
 StackFrame kMalloc = StackFrame::FromTraceEventName("malloc");
+StackFrame kNull = StackFrame::FromTraceEventName(nullptr);
+
+TEST(StackFrameDeduplicatorTest, ImplicitId0) {
+  StackFrame null_bt[] = {kNull};
+
+  // Empty backtraces (begin == end) are mapped to an implicitly added
+  // node #0. However, backtrace with a single null frame is not empty,
+  // and should be mapped to some other id.
+
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+
+  // Node #0 is added implicitly and corresponds to an empty backtrace.
+  ASSERT_EQ(dedup.begin() + 1, dedup.end());
+  ASSERT_EQ(0, dedup.Insert(std::begin(null_bt), std::begin(null_bt)));
+
+  // Placeholder entry for ID 0 is a frame with NULL name and no parent.
+  // However inserting such a frame should yield a different ID.
+  ExpectIncrementalEntries(&dedup, &string_dedup, {{0, kNull}});
+  ASSERT_EQ(1, dedup.Insert(std::begin(null_bt), std::end(null_bt)));
+}
 
 TEST(StackFrameDeduplicatorTest, SingleBacktrace) {
   StackFrame bt[] = {kBrowserMain, kCreateWidget, kMalloc};
 
   // The call tree should look like this (index in brackets).
   //
-  // BrowserMain [0]
-  //   CreateWidget [1]
-  //     malloc [2]
+  // BrowserMain [1]
+  //   CreateWidget [2]
+  //     malloc [3]
 
-  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
-  ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt)));
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+  ASSERT_EQ(3, dedup.Insert(std::begin(bt), std::end(bt)));
 
-  auto iter = dedup->begin();
+  auto iter = dedup.begin() + 1;  // skip implicit node #0
   ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
-  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
+  ASSERT_EQ(kInvalidStackFrameIndex, (iter + 0)->parent_frame_index);
 
   ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
-  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
+  ASSERT_EQ(1, (iter + 1)->parent_frame_index);
 
   ASSERT_EQ(kMalloc, (iter + 2)->frame);
-  ASSERT_EQ(1, (iter + 2)->parent_frame_index);
+  ASSERT_EQ(2, (iter + 2)->parent_frame_index);
 
-  ASSERT_EQ(iter + 3, dedup->end());
+  ASSERT_EQ(iter + 3, dedup.end());
 }
 
 TEST(StackFrameDeduplicatorTest, SingleBacktraceWithNull) {
   StackFrame null_frame = StackFrame::FromTraceEventName(nullptr);
   StackFrame bt[] = {kBrowserMain, null_frame, kMalloc};
 
   // Deduplicator doesn't care about what's inside StackFrames,
   // and handles nullptr StackFrame values as any other.
   //
   // So the call tree should look like this (index in brackets).
   //
-  // BrowserMain [0]
-  //   (null) [1]
-  //     malloc [2]
+  // BrowserMain [1]
+  //   (null) [2]
+  //     malloc [3]
 
-  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
-  ASSERT_EQ(2, dedup->Insert(std::begin(bt), std::end(bt)));
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+  ASSERT_EQ(3, dedup.Insert(std::begin(bt), std::end(bt)));
 
-  auto iter = dedup->begin();
+  auto iter = dedup.begin() + 1;  // skip implicit node #0
   ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
-  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
+  ASSERT_EQ(kInvalidStackFrameIndex, (iter + 0)->parent_frame_index);
 
   ASSERT_EQ(null_frame, (iter + 1)->frame);
-  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
+  ASSERT_EQ(1, (iter + 1)->parent_frame_index);
 
   ASSERT_EQ(kMalloc, (iter + 2)->frame);
-  ASSERT_EQ(1, (iter + 2)->parent_frame_index);
+  ASSERT_EQ(2, (iter + 2)->parent_frame_index);
 
-  ASSERT_EQ(iter + 3, dedup->end());
+  ASSERT_EQ(iter + 3, dedup.end());
 }
 
 // Test that there can be different call trees (there can be multiple bottom
 // frames). Also verify that frames with the same name but a different caller
 // are represented as distinct nodes.
 TEST(StackFrameDeduplicatorTest, MultipleRoots) {
   StackFrame bt0[] = {kBrowserMain, kCreateWidget};
   StackFrame bt1[] = {kRendererMain, kCreateWidget};
 
   // The call tree should look like this (index in brackets).
   //
-  // BrowserMain [0]
-  //   CreateWidget [1]
-  // RendererMain [2]
-  //   CreateWidget [3]
+  // BrowserMain [1]
+  //   CreateWidget [2]
+  // RendererMain [3]
+  //   CreateWidget [4]
   //
   // Note that there will be two instances of CreateWidget,
   // with different parents.
 
-  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
-  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
-  ASSERT_EQ(3, dedup->Insert(std::begin(bt1), std::end(bt1)));
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+  ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0)));
+  ASSERT_EQ(4, dedup.Insert(std::begin(bt1), std::end(bt1)));
 
-  auto iter = dedup->begin();
+  auto iter = dedup.begin() + 1;  // skip implicit node #0
   ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
-  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
+  ASSERT_EQ(kInvalidStackFrameIndex, (iter + 0)->parent_frame_index);
 
   ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
-  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
+  ASSERT_EQ(1, (iter + 1)->parent_frame_index);
 
   ASSERT_EQ(kRendererMain, (iter + 2)->frame);
-  ASSERT_EQ(-1, (iter + 2)->parent_frame_index);
+  ASSERT_EQ(kInvalidStackFrameIndex, (iter + 2)->parent_frame_index);
 
   ASSERT_EQ(kCreateWidget, (iter + 3)->frame);
-  ASSERT_EQ(2, (iter + 3)->parent_frame_index);
+  ASSERT_EQ(3, (iter + 3)->parent_frame_index);
 
-  ASSERT_EQ(iter + 4, dedup->end());
+  ASSERT_EQ(iter + 4, dedup.end());
 }
 
 TEST(StackFrameDeduplicatorTest, Deduplication) {
   StackFrame bt0[] = {kBrowserMain, kCreateWidget};
   StackFrame bt1[] = {kBrowserMain, kInitialize};
 
   // The call tree should look like this (index in brackets).
   //
-  // BrowserMain [0]
-  //   CreateWidget [1]
-  //   Initialize [2]
+  // BrowserMain [1]
+  //   CreateWidget [2]
+  //   Initialize [3]
   //
   // Note that BrowserMain will be re-used.
 
-  std::unique_ptr<StackFrameDeduplicator> dedup(new StackFrameDeduplicator);
-  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
-  ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1)));
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+  ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0)));
+  ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1)));
 
-  auto iter = dedup->begin();
+  auto iter = dedup.begin() + 1;  // skip implicit node #0
   ASSERT_EQ(kBrowserMain, (iter + 0)->frame);
-  ASSERT_EQ(-1, (iter + 0)->parent_frame_index);
+  ASSERT_EQ(kInvalidStackFrameIndex, (iter + 0)->parent_frame_index);
 
   ASSERT_EQ(kCreateWidget, (iter + 1)->frame);
-  ASSERT_EQ(0, (iter + 1)->parent_frame_index);
+  ASSERT_EQ(1, (iter + 1)->parent_frame_index);
 
   ASSERT_EQ(kInitialize, (iter + 2)->frame);
-  ASSERT_EQ(0, (iter + 2)->parent_frame_index);
+  ASSERT_EQ(1, (iter + 2)->parent_frame_index);
 
-  ASSERT_EQ(iter + 3, dedup->end());
+  ASSERT_EQ(iter + 3, dedup.end());
 
   // Inserting the same backtrace again should return the index of the existing
   // node.
-  ASSERT_EQ(1, dedup->Insert(std::begin(bt0), std::end(bt0)));
-  ASSERT_EQ(2, dedup->Insert(std::begin(bt1), std::end(bt1)));
-  ASSERT_EQ(dedup->begin() + 3, dedup->end());
+  ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0)));
+  ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1)));
+  ASSERT_EQ(4 /* 1 implicit + 3 added */, dedup.end() - dedup.begin());
+}
+
+TEST(StackFrameDeduplicatorTest, SerializeIncrementally) {
+  StringDeduplicator string_dedup;
+  StackFrameDeduplicator dedup(&string_dedup);
+
+  StackFrame bt0[] = {kBrowserMain, kCreateWidget};
+  ASSERT_EQ(2, dedup.Insert(std::begin(bt0), std::end(bt0)));
+
+  ExpectIncrementalEntries(
+      &dedup, &string_dedup,
+      {{0, kNull}, {1, kBrowserMain}, {2, kCreateWidget, 1}});
+
+  StackFrame bt1[] = {kBrowserMain, kInitialize};
+  ASSERT_EQ(3, dedup.Insert(std::begin(bt1), std::end(bt1)));
+
+  ExpectIncrementalEntries(&dedup, &string_dedup, {{3, kInitialize, 1}});
+
+  ExpectIncrementalEntries(&dedup, &string_dedup, {});
 }
 
 }  // namespace trace_event
 }  // namespace base