[tracing] Extend memory dump API with graphs

This CL allows to express ownership relationships between
MemoryAllocatorDump(s). Ownership edges are the building block
to express suballocation, sharing (co-ownership) and
cross-process-sharing (the latter might require an extra CL to
introduce global nodes).
See the related bug for the design doc and concrete use cases.

BUG=492102

Review URL: https://codereview.chromium.org/1161813004

Cr-Commit-Position: refs/heads/master@{#331768}

6 files changed, 137 insertions, 7 deletions

diff --git a/base/trace_event/memory_allocator_dump.cc b/base/trace_event/memory_allocator_dump.cc
index edec31b..755d25d 100644
--- a/base/trace_event/memory_allocator_dump.cc
+++ b/base/trace_event/memory_allocator_dump.cc
@@ -41,8 +41,11 @@ const char MemoryAllocatorDump::kUnitsBytes[] = "bytes";
 const char MemoryAllocatorDump::kUnitsObjects[] = "objects";
 
 MemoryAllocatorDump::MemoryAllocatorDump(const std::string& absolute_name,
-                                         ProcessMemoryDump* process_memory_dump)
-    : absolute_name_(absolute_name), process_memory_dump_(process_memory_dump) {
+                                         ProcessMemoryDump* process_memory_dump,
+                                         const MemoryAllocatorDumpGuid& guid)
+    : absolute_name_(absolute_name),
+      process_memory_dump_(process_memory_dump),
+      guid_(guid) {
   // The |absolute_name| cannot be empty.
   DCHECK(!absolute_name.empty());
 
@@ -55,6 +58,20 @@ MemoryAllocatorDump::MemoryAllocatorDump(const std::string& absolute_name,
   DCHECK_EQ(std::string::npos, absolute_name.find_first_of('.'));
 }
 
+// If the caller didn't provide a guid, make one up by hashing the
+// absolute_name with the current PID.
+// Rationale: |absolute_name| is already supposed to be unique within a
+// process, the pid will make it unique among all processes.
+MemoryAllocatorDump::MemoryAllocatorDump(const std::string& absolute_name,
+                                         ProcessMemoryDump* process_memory_dump)
+    : MemoryAllocatorDump(absolute_name,
+                          process_memory_dump,
+                          MemoryAllocatorDumpGuid(StringPrintf(
+                              "%d:%s",
+                              TraceLog::GetInstance()->process_id(),
+                              absolute_name.c_str()))) {
+}
+
 MemoryAllocatorDump::~MemoryAllocatorDump() {
 }
 
@@ -106,6 +123,8 @@ void MemoryAllocatorDump::AddString(const std::string& name,
 
 void MemoryAllocatorDump::AsValueInto(TracedValue* value) const {
   value->BeginDictionary(absolute_name_.c_str());
+  value->SetString("guid", guid_.ToString());
+
   value->BeginDictionary("attrs");
 
   for (DictionaryValue::Iterator it(attributes_); !it.IsAtEnd(); it.Advance())
diff --git a/base/trace_event/memory_allocator_dump.h b/base/trace_event/memory_allocator_dump.h
index 1bb27f9..a099e0a 100644
--- a/base/trace_event/memory_allocator_dump.h
+++ b/base/trace_event/memory_allocator_dump.h
@@ -8,6 +8,7 @@
 #include "base/base_export.h"
 #include "base/basictypes.h"
 #include "base/logging.h"
+#include "base/trace_event/memory_allocator_dump_guid.h"
 #include "base/values.h"
 
 namespace base {
@@ -22,6 +23,9 @@ class BASE_EXPORT MemoryAllocatorDump {
  public:
   // MemoryAllocatorDump is owned by ProcessMemoryDump.
   MemoryAllocatorDump(const std::string& absolute_name,
+                      ProcessMemoryDump* process_memory_dump,
+                      const MemoryAllocatorDumpGuid& guid);
+  MemoryAllocatorDump(const std::string& absolute_name,
                       ProcessMemoryDump* process_memory_dump);
   ~MemoryAllocatorDump();
 
@@ -68,10 +72,19 @@ class BASE_EXPORT MemoryAllocatorDump {
     return process_memory_dump_;
   }
 
+  // |guid| is an optional global dump identifier, unique across all processes
+  // within the scope of a global dump. It is only required when using the
+  // graph APIs (see TODO_method_name) to express retention / suballocation or
+  // cross process sharing. See crbug.com/492102 for design docs.
+  // Subsequent MemoryAllocatorDump(s) with the same |absolute_name| are
+  // expected to have the same guid.
+  const MemoryAllocatorDumpGuid& guid() const { return guid_; }
+
  private:
   const std::string absolute_name_;
   ProcessMemoryDump* const process_memory_dump_;  // Not owned (PMD owns this).
   DictionaryValue attributes_;
+  MemoryAllocatorDumpGuid guid_;
 
   DISALLOW_COPY_AND_ASSIGN(MemoryAllocatorDump);
 };
diff --git a/base/trace_event/memory_allocator_dump_unittest.cc b/base/trace_event/memory_allocator_dump_unittest.cc
index 0b2cbdf..b6ca482 100644
--- a/base/trace_event/memory_allocator_dump_unittest.cc
+++ b/base/trace_event/memory_allocator_dump_unittest.cc
@@ -6,6 +6,7 @@
 
 #include "base/format_macros.h"
 #include "base/strings/stringprintf.h"
+#include "base/trace_event/memory_allocator_dump_guid.h"
 #include "base/trace_event/memory_dump_provider.h"
 #include "base/trace_event/memory_dump_session_state.h"
 #include "base/trace_event/process_memory_dump.h"
@@ -78,6 +79,29 @@ void CheckAttribute(const MemoryAllocatorDump* dump,
 }
 }  // namespace
 
+TEST(MemoryAllocatorDumpTest, GuidGeneration) {
+  scoped_ptr<MemoryAllocatorDump> mad(
+      new MemoryAllocatorDump("foo", nullptr, MemoryAllocatorDumpGuid(0x42u)));
+  ASSERT_EQ("42", mad->guid().ToString());
+
+  // If the dumper does not provide a Guid, the MAD will make one up on the
+  // flight. Furthermore that Guid will stay stable across across multiple
+  // snapshots if the |absolute_name| of the dump doesn't change
+  mad.reset(new MemoryAllocatorDump("bar", nullptr));
+  const MemoryAllocatorDumpGuid guid_bar = mad->guid();
+  ASSERT_FALSE(guid_bar.empty());
+  ASSERT_FALSE(guid_bar.ToString().empty());
+  ASSERT_EQ(guid_bar, mad->guid());
+
+  mad.reset(new MemoryAllocatorDump("bar", nullptr));
+  const MemoryAllocatorDumpGuid guid_bar_2 = mad->guid();
+  ASSERT_EQ(guid_bar, guid_bar_2);
+
+  mad.reset(new MemoryAllocatorDump("baz", nullptr));
+  const MemoryAllocatorDumpGuid guid_baz = mad->guid();
+  ASSERT_NE(guid_bar, guid_baz);
+}
+
 TEST(MemoryAllocatorDumpTest, DumpIntoProcessMemoryDump) {
   FakeMemoryAllocatorDumpProvider fmadp;
   ProcessMemoryDump pmd(make_scoped_refptr(new MemoryDumpSessionState()));
diff --git a/base/trace_event/process_memory_dump.cc b/base/trace_event/process_memory_dump.cc
index dbf8e3d..4390905 100644
--- a/base/trace_event/process_memory_dump.cc
+++ b/base/trace_event/process_memory_dump.cc
@@ -10,6 +10,10 @@
 namespace base {
 namespace trace_event {
 
+namespace {
+const char kEdgeTypeOwnership[] = "ownership";
+}
+
 ProcessMemoryDump::ProcessMemoryDump(
     const scoped_refptr<MemoryDumpSessionState>& session_state)
     : has_process_totals_(false),
@@ -48,6 +52,7 @@ void ProcessMemoryDump::Clear() {
 
   allocator_dumps_storage_.clear();
   allocator_dumps_.clear();
+  allocator_dumps_edges_.clear();
 }
 
 void ProcessMemoryDump::TakeAllDumpsFrom(ProcessMemoryDump* other) {
@@ -63,26 +68,56 @@ void ProcessMemoryDump::TakeAllDumpsFrom(ProcessMemoryDump* other) {
   }
   other->allocator_dumps_storage_.weak_clear();
   other->allocator_dumps_.clear();
+
+  // Move all the edges.
+  allocator_dumps_edges_.insert(allocator_dumps_edges_.end(),
+                                other->allocator_dumps_edges_.begin(),
+                                other->allocator_dumps_edges_.end());
+  other->allocator_dumps_edges_.clear();
 }
 
 void ProcessMemoryDump::AsValueInto(TracedValue* value) const {
-  // Build up the [dumper name] -> [value] dictionary.
   if (has_process_totals_) {
     value->BeginDictionary("process_totals");
     process_totals_.AsValueInto(value);
     value->EndDictionary();
   }
+
   if (has_process_mmaps_) {
     value->BeginDictionary("process_mmaps");
     process_mmaps_.AsValueInto(value);
     value->EndDictionary();
   }
+
   if (allocator_dumps_storage_.size() > 0) {
     value->BeginDictionary("allocators");
     for (const MemoryAllocatorDump* allocator_dump : allocator_dumps_storage_)
       allocator_dump->AsValueInto(value);
     value->EndDictionary();
   }
+
+  value->BeginArray("allocators_graph");
+  for (const MemoryAllocatorDumpEdge& edge : allocator_dumps_edges_) {
+    value->BeginDictionary();
+    value->SetString("source", edge.source.ToString());
+    value->SetString("target", edge.target.ToString());
+    value->SetInteger("importance", edge.importance);
+    value->SetString("type", edge.type);
+    value->EndDictionary();
+  }
+  value->EndArray();
+}
+
+void ProcessMemoryDump::AddOwnershipEdge(MemoryAllocatorDumpGuid source,
+                                         MemoryAllocatorDumpGuid target,
+                                         int importance) {
+  allocator_dumps_edges_.push_back(
+      {source, target, importance, kEdgeTypeOwnership});
+}
+
+void ProcessMemoryDump::AddOwnershipEdge(MemoryAllocatorDumpGuid source,
+                                         MemoryAllocatorDumpGuid target) {
+  AddOwnershipEdge(source, target, 0 /* importance */);
 }
 
 }  // namespace trace_event
diff --git a/base/trace_event/process_memory_dump.h b/base/trace_event/process_memory_dump.h
index 0bc1dc3..55d7871 100644
--- a/base/trace_event/process_memory_dump.h
+++ b/base/trace_event/process_memory_dump.h
@@ -5,12 +5,15 @@
 #ifndef BASE_TRACE_EVENT_PROCESS_MEMORY_DUMP_H_
 #define BASE_TRACE_EVENT_PROCESS_MEMORY_DUMP_H_
 
+#include <vector>
+
 #include "base/base_export.h"
 #include "base/containers/hash_tables.h"
 #include "base/containers/small_map.h"
 #include "base/memory/ref_counted.h"
 #include "base/memory/scoped_vector.h"
 #include "base/trace_event/memory_allocator_dump.h"
+#include "base/trace_event/memory_allocator_dump_guid.h"
 #include "base/trace_event/memory_dump_session_state.h"
 #include "base/trace_event/process_memory_maps.h"
 #include "base/trace_event/process_memory_totals.h"
@@ -30,6 +33,13 @@ class MemoryDumpSessionState;
 // dump point time.
 class BASE_EXPORT ProcessMemoryDump {
  public:
+  struct MemoryAllocatorDumpEdge {
+    MemoryAllocatorDumpGuid source;
+    MemoryAllocatorDumpGuid target;
+    int importance;
+    const char* type;
+  };
+
   // Maps allocator dumps absolute names (allocator_name/heap/subheap) to
   // MemoryAllocatorDump instances.
   using AllocatorDumpsMap =
@@ -78,6 +88,21 @@ class BASE_EXPORT ProcessMemoryDump {
   // Returns the map of the MemoryAllocatorDumps added to this dump.
   const AllocatorDumpsMap& allocator_dumps() const { return allocator_dumps_; }
 
+  // Adds an ownership relationship between two MemoryAllocatorDump(s) with the
+  // semantics: |source| owns |target|, and has the effect of attributing
+  // the memory usage of |target| to |source|. |importance| is optional and
+  // relevant only for the cases of co-ownership, where it acts as a z-index:
+  // the owner with the highest importance will be attributed |target|'s memory.
+  void AddOwnershipEdge(MemoryAllocatorDumpGuid source,
+                        MemoryAllocatorDumpGuid target,
+                        int importance);
+  void AddOwnershipEdge(MemoryAllocatorDumpGuid source,
+                        MemoryAllocatorDumpGuid target);
+
+  const std::vector<MemoryAllocatorDumpEdge>& allocator_dumps_edges() const {
+    return allocator_dumps_edges_;
+  }
+
   const scoped_refptr<MemoryDumpSessionState>& session_state() const {
     return session_state_;
   }
@@ -97,6 +122,9 @@ class BASE_EXPORT ProcessMemoryDump {
   // State shared among all PMDs instances created in a given trace session.
   scoped_refptr<MemoryDumpSessionState> session_state_;
 
+  // Keeps track of relationships between MemoryAllocatorDump(s).
+  std::vector<MemoryAllocatorDumpEdge> allocator_dumps_edges_;
+
   DISALLOW_COPY_AND_ASSIGN(ProcessMemoryDump);
 };
 
diff --git a/base/trace_event/process_memory_dump_unittest.cc b/base/trace_event/process_memory_dump_unittest.cc
index 93de414..26c4308 100644
--- a/base/trace_event/process_memory_dump_unittest.cc
+++ b/base/trace_event/process_memory_dump_unittest.cc
@@ -5,6 +5,7 @@
 #include "base/trace_event/process_memory_dump.h"
 
 #include "base/memory/scoped_ptr.h"
+#include "base/trace_event/memory_allocator_dump_guid.h"
 #include "base/trace_event/trace_event_argument.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
@@ -23,8 +24,12 @@ TEST(ProcessMemoryDumpTest, Clear) {
   pmd1->process_mmaps()->AddVMRegion({0});
   pmd1->set_has_process_mmaps();
 
+  pmd1->AddOwnershipEdge(MemoryAllocatorDumpGuid(42),
+                         MemoryAllocatorDumpGuid(4242));
+
   pmd1->Clear();
   ASSERT_TRUE(pmd1->allocator_dumps().empty());
+  ASSERT_TRUE(pmd1->allocator_dumps_edges().empty());
   ASSERT_EQ(nullptr, pmd1->GetAllocatorDump("mad1"));
   ASSERT_EQ(nullptr, pmd1->GetAllocatorDump("mad2"));
   ASSERT_FALSE(pmd1->has_process_totals());
@@ -55,20 +60,25 @@ TEST(ProcessMemoryDumpTest, TakeAllDumpsFrom) {
   scoped_refptr<TracedValue> traced_value(new TracedValue());
 
   scoped_ptr<ProcessMemoryDump> pmd1(new ProcessMemoryDump(nullptr));
-  pmd1->CreateAllocatorDump("pmd1/mad1");
-  pmd1->CreateAllocatorDump("pmd1/mad2");
+  auto mad1_1 = pmd1->CreateAllocatorDump("pmd1/mad1");
+  auto mad1_2 = pmd1->CreateAllocatorDump("pmd1/mad2");
+  pmd1->AddOwnershipEdge(mad1_1->guid(), mad1_2->guid());
 
   scoped_ptr<ProcessMemoryDump> pmd2(new ProcessMemoryDump(nullptr));
-  pmd2->CreateAllocatorDump("pmd2/mad1");
-  pmd2->CreateAllocatorDump("pmd2/mad2");
+  auto mad2_1 = pmd2->CreateAllocatorDump("pmd2/mad1");
+  auto mad2_2 = pmd2->CreateAllocatorDump("pmd2/mad2");
+  pmd1->AddOwnershipEdge(mad2_1->guid(), mad2_2->guid());
 
   pmd1->TakeAllDumpsFrom(pmd2.get());
 
   // Make sure that pmd2 is empty but still usable after it has been emptied.
   ASSERT_TRUE(pmd2->allocator_dumps().empty());
+  ASSERT_TRUE(pmd2->allocator_dumps_edges().empty());
   pmd2->CreateAllocatorDump("pmd2/this_mad_stays_with_pmd2");
   ASSERT_EQ(1u, pmd2->allocator_dumps().size());
   ASSERT_EQ(1u, pmd2->allocator_dumps().count("pmd2/this_mad_stays_with_pmd2"));
+  pmd2->AddOwnershipEdge(MemoryAllocatorDumpGuid(42),
+                         MemoryAllocatorDumpGuid(4242));
 
   // Check that calling AsValueInto() doesn't cause a crash.
   pmd2->AsValueInto(traced_value.get());
@@ -83,6 +93,7 @@ TEST(ProcessMemoryDumpTest, TakeAllDumpsFrom) {
   ASSERT_EQ(1u, pmd1->allocator_dumps().count("pmd1/mad2"));
   ASSERT_EQ(1u, pmd1->allocator_dumps().count("pmd2/mad1"));
   ASSERT_EQ(1u, pmd1->allocator_dumps().count("pmd1/mad2"));
+  ASSERT_EQ(2u, pmd1->allocator_dumps_edges().size());
 
   // Check that calling AsValueInto() doesn't cause a crash.
   traced_value = new TracedValue();