[Tracing] Make heap profiler type info a string

Instead of keeping a 16-bit "type ID" to do type profiling, the heap
profiler will just keep a |const char*| with the type name. The type
names are deduplicated at dump time, so in the trace log heap dumps
still reference types by ID, and there is one dictionary at the end that
maps type IDs to their names.

Internally, a null pointer type name is used to indicate "unknown type".
It is dumped in the trace as type name "[unknown]", so it requires no
special treatment from the UI. (Contrary to previous intent.) The
mapping dictionary follows the same convention as the current
"stackFrames" dictionary: it is one metadata event per process, with
name "typeNames". The args of this event contain a dictionary that maps
type IDs to their name.

This is part of the heap profiler in chrome://tracing.

BUG=524631

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

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

16 files changed, 319 insertions, 90 deletions

diff --git a/base/trace_event/BUILD.gn b/base/trace_event/BUILD.gn
index 493316e..07d28fe 100644
--- a/base/trace_event/BUILD.gn
+++ b/base/trace_event/BUILD.gn
@@ -17,6 +17,8 @@ source_set("trace_event") {
     "heap_profiler_heap_dump_writer.h",
     "heap_profiler_stack_frame_deduplicator.cc",
     "heap_profiler_stack_frame_deduplicator.h",
+    "heap_profiler_type_name_deduplicator.cc",
+    "heap_profiler_type_name_deduplicator.h",
     "java_heap_dump_provider_android.cc",
     "java_heap_dump_provider_android.h",
     "memory_allocator_dump.cc",
@@ -116,6 +118,7 @@ source_set("trace_event_unittests") {
     "heap_profiler_allocation_register_unittest.cc",
     "heap_profiler_heap_dump_writer_unittest.cc",
     "heap_profiler_stack_frame_deduplicator_unittest.cc",
+    "heap_profiler_type_name_deduplicator_unittest.cc",
     "java_heap_dump_provider_android_unittest.cc",
     "memory_allocator_dump_unittest.cc",
     "memory_dump_manager_unittest.cc",
diff --git a/base/trace_event/heap_profiler_allocation_context.cc b/base/trace_event/heap_profiler_allocation_context.cc
index ce8e50d..038c083 100644
--- a/base/trace_event/heap_profiler_allocation_context.cc
+++ b/base/trace_event/heap_profiler_allocation_context.cc
@@ -22,7 +22,7 @@ AllocationContext AllocationContext::Empty() {
   for (size_t i = 0; i < arraysize(ctx.backtrace.frames); i++)
     ctx.backtrace.frames[i] = nullptr;
 
-  ctx.type_id = 0;
+  ctx.type_name = nullptr;
 
   return ctx;
 }
@@ -34,7 +34,7 @@ bool operator==(const Backtrace& lhs, const Backtrace& rhs) {
 }
 
 bool operator==(const AllocationContext& lhs, const AllocationContext& rhs) {
-  return (lhs.backtrace == rhs.backtrace) && (lhs.type_id == rhs.type_id);
+  return (lhs.backtrace == rhs.backtrace) && (lhs.type_name == rhs.type_name);
 }
 
 }  // namespace trace_event
@@ -50,13 +50,18 @@ size_t hash<Backtrace>::operator()(const Backtrace& backtrace) const {
 }
 
 size_t hash<AllocationContext>::operator()(const AllocationContext& ctx) const {
-  size_t ctx_hash = hash<Backtrace>()(ctx.backtrace);
+  size_t backtrace_hash = hash<Backtrace>()(ctx.backtrace);
+
+  // Multiplicative hash from [Knuth 1998]. Works best if |size_t| is 32 bits,
+  // because the magic number is a prime very close to 2^32 / golden ratio, but
+  // will still redistribute keys bijectively on 64-bit architectures because
+  // the magic number is coprime to 2^64.
+  size_t type_hash = reinterpret_cast<size_t>(ctx.type_name) * 2654435761;
 
   // Multiply one side to break the commutativity of +. Multiplication with a
   // number coprime to |numeric_limits<size_t>::max() + 1| is bijective so
-  // randomness is preserved. The type ID is assumed to be distributed randomly
-  // already so there is no need to hash it.
-  return (ctx_hash * 3) + static_cast<size_t>(ctx.type_id);
+  // randomness is preserved.
+  return (backtrace_hash * 3) + type_hash;
 }
 
 }  // BASE_HASH_NAMESPACE
diff --git a/base/trace_event/heap_profiler_allocation_context.h b/base/trace_event/heap_profiler_allocation_context.h
index c5f1fdf..6a46d03 100644
--- a/base/trace_event/heap_profiler_allocation_context.h
+++ b/base/trace_event/heap_profiler_allocation_context.h
@@ -52,17 +52,16 @@ bool BASE_EXPORT operator==(const Backtrace& lhs, const Backtrace& rhs);
 // static lifetime.
 struct BASE_EXPORT AllocationContext {
  public:
-  // A type ID is a number that is unique for every C++ type. A type ID is
-  // stored instead of the type name to avoid inflating the binary with type
-  // name strings. There is an out of band lookup table mapping IDs to the type
-  // names. A value of 0 means that the type is not known.
-  using TypeId = uint16_t;
-
-  // An allocation context with empty backtrace and type ID 0 (unknown type).
+  // An allocation context with empty backtrace and unknown type.
   static AllocationContext Empty();
 
   Backtrace backtrace;
-  TypeId type_id;
+
+  // Type name of the type stored in the allocated memory. A null pointer
+  // indicates "unknown type". Grouping is done by comparing pointers, not by
+  // deep string comparison. In a component build, where a type name can have a
+  // string literal in several dynamic libraries, this may distort grouping.
+  const char* type_name;
 
  private:
   friend class AllocationContextTracker;
diff --git a/base/trace_event/heap_profiler_allocation_context_tracker.cc b/base/trace_event/heap_profiler_allocation_context_tracker.cc
index 51e4590..791ab7a 100644
--- a/base/trace_event/heap_profiler_allocation_context_tracker.cc
+++ b/base/trace_event/heap_profiler_allocation_context_tracker.cc
@@ -106,7 +106,7 @@ AllocationContext AllocationContextTracker::GetContextSnapshot() {
     std::fill(dst, dst_end, nullptr);
   }
 
-  ctx.type_id = 0;
+  ctx.type_name = nullptr;
 
   return ctx;
 }
diff --git a/base/trace_event/heap_profiler_heap_dump_writer.cc b/base/trace_event/heap_profiler_heap_dump_writer.cc
index dc27823..d69ed7b 100644
--- a/base/trace_event/heap_profiler_heap_dump_writer.cc
+++ b/base/trace_event/heap_profiler_heap_dump_writer.cc
@@ -12,13 +12,12 @@
 #include "base/format_macros.h"
 #include "base/strings/stringprintf.h"
 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
+#include "base/trace_event/heap_profiler_type_name_deduplicator.h"
 #include "base/trace_event/trace_event_argument.h"
 
 namespace base {
 namespace trace_event {
 
-using TypeId = AllocationContext::TypeId;
-
 namespace {
 
 template <typename T>
@@ -41,9 +40,11 @@ std::vector<std::pair<T, size_t>> SortBySizeDescending(
 
 }  // namespace
 
-HeapDumpWriter::HeapDumpWriter(StackFrameDeduplicator* stack_frame_deduplicator)
+HeapDumpWriter::HeapDumpWriter(StackFrameDeduplicator* stack_frame_deduplicator,
+                               TypeNameDeduplicator* type_name_deduplicator)
     : traced_value_(new TracedValue()),
-      stack_frame_deduplicator_(stack_frame_deduplicator) {}
+      stack_frame_deduplicator_(stack_frame_deduplicator),
+      type_name_deduplicator_(type_name_deduplicator) {}
 
 HeapDumpWriter::~HeapDumpWriter() {}
 
@@ -57,12 +58,12 @@ scoped_refptr<TracedValue> HeapDumpWriter::WriteHeapDump() {
   // iterating anyway.
   size_t total_size = 0;
   hash_map<Backtrace, size_t> bytes_by_backtrace;
-  hash_map<TypeId, size_t> bytes_by_type;
+  hash_map<const char*, size_t> bytes_by_type;
 
   for (auto context_size : bytes_by_context_) {
     total_size += context_size.second;
     bytes_by_backtrace[context_size.first.backtrace] += context_size.second;
-    bytes_by_type[context_size.first.type_id] += context_size.second;
+    bytes_by_type[context_size.first.type_name] += context_size.second;
   }
 
   auto sorted_bytes_by_backtrace = SortBySizeDescending(bytes_by_backtrace);
@@ -90,7 +91,9 @@ scoped_refptr<TracedValue> HeapDumpWriter::WriteHeapDump() {
   // Entries with the size per type.
   for (const auto& entry : sorted_bytes_by_type) {
     traced_value_->BeginDictionary();
-    WriteTypeId(entry.first);
+    // Insert a forward reference to the type name that will be written to the
+    // trace when it is flushed.
+    WriteTypeId(type_name_deduplicator_->Insert(entry.first));
     WriteSize(entry.second);
     traced_value_->EndDictionary();
   }
@@ -113,17 +116,10 @@ void HeapDumpWriter::WriteStackFrameIndex(int index) {
   }
 }
 
-void HeapDumpWriter::WriteTypeId(TypeId type_id) {
-  if (type_id == 0) {
-    // Type ID 0 represents "unknown type". Instead of writing it as "0" which
-    // could be mistaken for an actual type ID, an unknown type is represented
-    // by the empty string.
-    traced_value_->SetString("type", "");
-  } else {
-    // Format the type ID as a string.
-    SStringPrintf(&buffer_, "%" PRIu16, type_id);
-    traced_value_->SetString("type", buffer_);
-  }
+void HeapDumpWriter::WriteTypeId(int type_id) {
+  // Format the type ID as a string.
+  SStringPrintf(&buffer_, "%i", type_id);
+  traced_value_->SetString("type", buffer_);
 }
 
 void HeapDumpWriter::WriteSize(size_t size) {
diff --git a/base/trace_event/heap_profiler_heap_dump_writer.h b/base/trace_event/heap_profiler_heap_dump_writer.h
index 4b99543..c3a7767 100644
--- a/base/trace_event/heap_profiler_heap_dump_writer.h
+++ b/base/trace_event/heap_profiler_heap_dump_writer.h
@@ -16,8 +16,9 @@
 namespace base {
 namespace trace_event {
 
-class TracedValue;
 class StackFrameDeduplicator;
+class TracedValue;
+class TypeNameDeduplicator;
 
 // Helper class to dump a snapshot of an |AllocationRegister| or other heap
 // bookkeeping structure into a |TracedValue|. This class is intended to be
@@ -26,9 +27,11 @@ class StackFrameDeduplicator;
 // to do the processing and generate a heap dump value for the trace log.
 class BASE_EXPORT HeapDumpWriter {
  public:
-  // The |StackFrameDeduplicator| is not owned. The heap dump writer assumes
-  // exclusive access to it during the lifetime of the dump writer.
-  HeapDumpWriter(StackFrameDeduplicator* stack_frame_deduplicator);
+  // The |StackFrameDeduplicator| and |TypeNameDeduplicator| are not owned. The
+  // heap dump writer assumes exclusive access to them during the lifetime of
+  // the dump writer.
+  HeapDumpWriter(StackFrameDeduplicator* stack_frame_deduplicator,
+                 TypeNameDeduplicator* type_name_deduplicator);
   ~HeapDumpWriter();
 
   // Inserts information from which the heap dump will be generated. This method
@@ -45,7 +48,7 @@ class BASE_EXPORT HeapDumpWriter {
   void WriteStackFrameIndex(int index);
 
   // Writes a "type" key with the stringified type ID.
-  void WriteTypeId(AllocationContext::TypeId type_id);
+  void WriteTypeId(int type_id);
 
   // Writes a "size" key with value |size| as a hexidecimal string to the traced
   // value.
@@ -58,6 +61,10 @@ class BASE_EXPORT HeapDumpWriter {
   // this heap dump writer instance.
   StackFrameDeduplicator* const stack_frame_deduplicator_;
 
+  // Helper for converting type names to IDs. Not owned, must outlive this heap
+  // dump writer instance.
+  TypeNameDeduplicator* const type_name_deduplicator_;
+
   // A map of allocation context to the number of bytes allocated for that
   // context.
   hash_map<AllocationContext, size_t> bytes_by_context_;
diff --git a/base/trace_event/heap_profiler_heap_dump_writer_unittest.cc b/base/trace_event/heap_profiler_heap_dump_writer_unittest.cc
index 2edf863..c936f4e 100644
--- a/base/trace_event/heap_profiler_heap_dump_writer_unittest.cc
+++ b/base/trace_event/heap_profiler_heap_dump_writer_unittest.cc
@@ -11,6 +11,7 @@
 #include "base/trace_event/heap_profiler_allocation_context.h"
 #include "base/trace_event/heap_profiler_heap_dump_writer.h"
 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
+#include "base/trace_event/heap_profiler_type_name_deduplicator.h"
 #include "base/trace_event/trace_event_argument.h"
 #include "base/values.h"
 #include "testing/gtest/include/gtest/gtest.h"
@@ -24,19 +25,15 @@ const char kRendererMain[] = "RendererMain";
 const char kCreateWidget[] = "CreateWidget";
 const char kInitialize[] = "Initialize";
 
+const char kInt[] = "int";
+const char kBool[] = "bool";
+const char kString[] = "string";
+
 }  // namespace
 
 namespace base {
 namespace trace_event {
 
-void AssertStringEq(const DictionaryValue* entry,
-                    const char* key,
-                    const char* expected_value) {
-  std::string str;
-  ASSERT_TRUE(entry->GetString(key, &str));
-  ASSERT_EQ(expected_value, str);
-}
-
 // Asserts that an integer stored in the json as a string has the correct value.
 void AssertIntEq(const DictionaryValue* entry,
                  const char* key,
@@ -53,45 +50,46 @@ scoped_ptr<Value> DumpAndReadBack(HeapDumpWriter* writer) {
   return JSONReader::Read(json);
 }
 
-TEST(HeapDumpWriterTest, BacktraceTypeIdTable) {
-  auto deduplicator = make_scoped_refptr(new StackFrameDeduplicator);
-  HeapDumpWriter writer(deduplicator.get());
+TEST(HeapDumpWriterTest, BacktraceTypeNameTable) {
+  auto sf_deduplicator = make_scoped_refptr(new StackFrameDeduplicator);
+  auto tn_deduplicator = make_scoped_refptr(new TypeNameDeduplicator);
+  HeapDumpWriter writer(sf_deduplicator.get(), tn_deduplicator.get());
 
   AllocationContext ctx = AllocationContext::Empty();
   ctx.backtrace.frames[0] = kBrowserMain;
   ctx.backtrace.frames[1] = kCreateWidget;
-  ctx.type_id = 1;
+  ctx.type_name = kInt;
 
-  // 10 bytes with context { type: 1, bt: [BrowserMain, CreateWidget] }.
+  // 10 bytes with context { type: int, bt: [BrowserMain, CreateWidget] }.
   writer.InsertAllocation(ctx, 2);
   writer.InsertAllocation(ctx, 3);
   writer.InsertAllocation(ctx, 5);
 
-  ctx.type_id = 2;
+  ctx.type_name = kBool;
 
-  // 18 bytes with context { type: 2, bt: [BrowserMain, CreateWidget] }.
+  // 18 bytes with context { type: bool, bt: [BrowserMain, CreateWidget] }.
   writer.InsertAllocation(ctx, 7);
   writer.InsertAllocation(ctx, 11);
 
   ctx.backtrace.frames[0] = kRendererMain;
   ctx.backtrace.frames[1] = kInitialize;
 
-  // 30 bytes with context { type: 2, bt: [RendererMain, Initialize] }.
+  // 30 bytes with context { type: bool, bt: [RendererMain, Initialize] }.
   writer.InsertAllocation(ctx, 13);
   writer.InsertAllocation(ctx, 17);
 
-  ctx.type_id = 3;
+  ctx.type_name = kString;
 
-  // 19 bytes with context { type: 3, bt: [RendererMain, Initialize] }.
+  // 19 bytes with context { type: string, bt: [RendererMain, Initialize] }.
   writer.InsertAllocation(ctx, 19);
 
   // At this point the heap looks like this:
   //
   // |        | CrWidget <- BrMain | Init <- RenMain | Sum |
   // +--------+--------------------+-----------------+-----+
-  // | Type 1 |                 10 |               0 |  10 |
-  // | Type 2 |                 18 |              30 |  48 |
-  // | Type 3 |                  0 |              19 |  19 |
+  // | int    |                 10 |               0 |  10 |
+  // | bool   |                 18 |              30 |  48 |
+  // | string |                  0 |              19 |  19 |
   // +--------+--------------------+-----------------+-----+
   // | Sum    |                 28 |              49 |  77 |
 
@@ -103,18 +101,21 @@ TEST(HeapDumpWriterTest, BacktraceTypeIdTable) {
   //     { "size": "4d" },                                    // 77 = 0x4d.
   //     { "size": "31", "bt": "id_of(Init <- RenMain)" },    // 49 = 0x31.
   //     { "size": "1c", "bt": "id_of(CrWidget <- BrMain)" }, // 28 = 0x1c.
-  //     { "size": "30", "type": "2" },                       // 48 = 0x30.
-  //     { "size": "13", "type": "3" },                       // 19 = 0x13.
-  //     { "size": "a", "type": "1" }                         // 10 = 0xa.
+  //     { "size": "30", "type": "id_of(bool)" },             // 48 = 0x30.
+  //     { "size": "13", "type": "id_of(string)" },           // 19 = 0x13.
+  //     { "size": "a", "type": "id_of(int)" }                // 10 = 0xa.
   //   ]
   // }
 
-  // Get the indices of the backtraces by adding them again to the deduplicator.
-  // Because they were added before, the same number is returned.
+  // Get the indices of the backtraces and types by adding them again to the
+  // deduplicator. Because they were added before, the same number is returned.
   int bt_renderer_main_initialize =
-      deduplicator->Insert({{kRendererMain, kInitialize}});
+      sf_deduplicator->Insert({{kRendererMain, kInitialize}});
   int bt_browser_main_create_widget =
-      deduplicator->Insert({{kBrowserMain, kCreateWidget}});
+      sf_deduplicator->Insert({{kBrowserMain, kCreateWidget}});
+  int type_id_int = tn_deduplicator->Insert(kInt);
+  int type_id_bool = tn_deduplicator->Insert(kBool);
+  int type_id_string = tn_deduplicator->Insert(kString);
 
   const DictionaryValue* dictionary;
   ASSERT_TRUE(heap_dump->GetAsDictionary(&dictionary));
@@ -154,19 +155,19 @@ TEST(HeapDumpWriterTest, BacktraceTypeIdTable) {
       AssertIntEq(entry, "bt", bt_browser_main_create_widget);
       x1c_seen++;
     } else if (size == "30") {
-      // Entry for type ID 2.
+      // Entry for type bool.
       ASSERT_EQ(2u, entry->size());  // Dictionary must have two elements.
-      AssertStringEq(entry, "type", "2");
+      AssertIntEq(entry, "type", type_id_bool);
       x30_seen++;
     } else if (size == "13") {
-      // Entry for type ID 3.
+      // Entry for type string.
       ASSERT_EQ(2u, entry->size());  // Dictionary must have two elements.
-      AssertStringEq(entry, "type", "3");
+      AssertIntEq(entry, "type", type_id_string);
       x13_seen++;
     } else if (size == "a") {
-      // Entry for type ID 1.
+      // Entry for type int.
       ASSERT_EQ(2u, entry->size());  // Dictionary must have two elements.
-      AssertStringEq(entry, "type", "1");
+      AssertIntEq(entry, "type", type_id_int);
       xa_seen++;
     }
   }
@@ -180,14 +181,15 @@ TEST(HeapDumpWriterTest, BacktraceTypeIdTable) {
 }
 
 // Test that the entry for the empty backtrace ends up in the json with the
-// "bt" field set to the empty string. Also test that the entry for "unknown
-// type" (type ID 0) ends up in the json with the "type" field set to the empty
-// string.
-TEST(HeapDumpWriterTest, EmptyBacktraceIndexAndUnknownTypeIdAreEmptyString) {
-  auto deduplicator = make_scoped_refptr(new StackFrameDeduplicator);
-  HeapDumpWriter writer(deduplicator.get());
-
-  // A context with empty backtrace and type ID 0 (unknown type).
+// "bt" field set to the empty string. Also test that an entry for "unknown
+// type" (nullptr type name) does not dereference the null pointer when writing
+// the type names, and that the type ID is 0.
+TEST(HeapDumpWriterTest, EmptyBacktraceIndexIsEmptyString) {
+  auto sf_deduplicator = make_scoped_refptr(new StackFrameDeduplicator);
+  auto tn_deduplicator = make_scoped_refptr(new TypeNameDeduplicator);
+  HeapDumpWriter writer(sf_deduplicator.get(), tn_deduplicator.get());
+
+  // A context with empty backtrace and unknown type (nullptr).
   AllocationContext ctx = AllocationContext::Empty();
 
   writer.InsertAllocation(ctx, 1);
@@ -218,7 +220,7 @@ TEST(HeapDumpWriterTest, EmptyBacktraceIndexAndUnknownTypeIdAreEmptyString) {
     if (entry->HasKey("type") && entry->size() == 2) {
       std::string type_id;
       ASSERT_TRUE(entry->GetString("type", &type_id));
-      ASSERT_EQ("", type_id);
+      ASSERT_EQ("0", type_id);
       unknown_type_seen++;
     }
   }
diff --git a/base/trace_event/heap_profiler_type_name_deduplicator.cc b/base/trace_event/heap_profiler_type_name_deduplicator.cc
new file mode 100644
index 0000000..17c3cee
--- /dev/null
+++ b/base/trace_event/heap_profiler_type_name_deduplicator.cc
@@ -0,0 +1,75 @@
+// 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_type_name_deduplicator.h"
+
+#include <stdlib.h>
+#include <string>
+#include <utility>
+
+#include "base/json/string_escape.h"
+#include "base/strings/stringprintf.h"
+#include "base/trace_event/trace_event_memory_overhead.h"
+
+namespace base {
+namespace trace_event {
+
+TypeNameDeduplicator::TypeNameDeduplicator() {
+  // A null pointer has type ID 0 ("unknown type");
+  type_ids_.insert(std::make_pair(nullptr, 0));
+}
+
+TypeNameDeduplicator::~TypeNameDeduplicator() {}
+
+int TypeNameDeduplicator::Insert(const char* type_name) {
+  auto result = type_ids_.insert(std::make_pair(type_name, 0));
+  auto& elem = result.first;
+  bool did_not_exist_before = result.second;
+
+  if (did_not_exist_before) {
+    // The type IDs are assigned sequentially and they are zero-based, so
+    // |size() - 1| is the ID of the new element.
+    elem->second = static_cast<int>(type_ids_.size() - 1);
+  }
+
+  return elem->second;
+}
+
+void TypeNameDeduplicator::AppendAsTraceFormat(std::string* out) const {
+  out->append("{");  // Begin the type names dictionary.
+
+  auto it = type_ids_.begin();
+  std::string buffer;
+
+  // Write the first entry manually; the null pointer must not be dereferenced.
+  // (The first entry is the null pointer because a |std::map| is ordered.)
+  it++;
+  out->append("\"0\":\"[unknown]\"");
+
+  for (; it != type_ids_.end(); it++) {
+    // Type IDs in the trace are strings, write them as stringified keys of
+    // a dictionary.
+    SStringPrintf(&buffer, ",\"%d\":", it->second);
+
+    // |EscapeJSONString| appends, it does not overwrite |buffer|.
+    bool put_in_quotes = true;
+    EscapeJSONString(it->first, put_in_quotes, &buffer);
+    out->append(buffer);
+  }
+
+  out->append("}");  // End the type names dictionary.
+}
+
+void TypeNameDeduplicator::EstimateTraceMemoryOverhead(
+    TraceEventMemoryOverhead* overhead) {
+  // The size here is only an estimate; it fails to take into account the size
+  // of the tree nodes for the map, but as an estimate this should be fine.
+  size_t map_size = type_ids_.size() * sizeof(std::pair<const char*, int>);
+
+  overhead->Add("TypeNameDeduplicator",
+                sizeof(TypeNameDeduplicator) + map_size);
+}
+
+}  // namespace trace_event
+}  // namespace base
diff --git a/base/trace_event/heap_profiler_type_name_deduplicator.h b/base/trace_event/heap_profiler_type_name_deduplicator.h
new file mode 100644
index 0000000..317ea5e
--- /dev/null
+++ b/base/trace_event/heap_profiler_type_name_deduplicator.h
@@ -0,0 +1,46 @@
+// 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.
+
+#ifndef BASE_TRACE_EVENT_HEAP_PROFILER_TYPE_NAME_DEDUPLICATOR_H_
+#define BASE_TRACE_EVENT_HEAP_PROFILER_TYPE_NAME_DEDUPLICATOR_H_
+
+#include <map>
+#include <string>
+
+#include "base/base_export.h"
+#include "base/macros.h"
+#include "base/trace_event/trace_event_impl.h"
+
+namespace base {
+namespace trace_event {
+
+class TraceEventMemoryOverhead;
+
+// Data structure that assigns a unique numeric ID to |const char*|s.
+class BASE_EXPORT TypeNameDeduplicator : public ConvertableToTraceFormat {
+ public:
+  TypeNameDeduplicator();
+
+  // Inserts a type name and returns its ID.
+  int Insert(const char* type_name);
+
+  // Estimates memory overhead including |sizeof(TypeNameDeduplicator)|.
+  void EstimateTraceMemoryOverhead(TraceEventMemoryOverhead* overhead) override;
+
+ private:
+  ~TypeNameDeduplicator() override;
+
+  // Writes the type ID -> type name mapping to the trace log.
+  void AppendAsTraceFormat(std::string* out) const override;
+
+  // Map from type name to type ID.
+  std::map<const char*, int> type_ids_;
+
+  DISALLOW_COPY_AND_ASSIGN(TypeNameDeduplicator);
+};
+
+}  // namespace trace_event
+}  // namespace base
+
+#endif  // BASE_TRACE_EVENT_HEAP_PROFILER_TYPE_NAME_DEDUPLICATOR_H_
diff --git a/base/trace_event/heap_profiler_type_name_deduplicator_unittest.cc b/base/trace_event/heap_profiler_type_name_deduplicator_unittest.cc
new file mode 100644
index 0000000..82c8fb5
--- /dev/null
+++ b/base/trace_event/heap_profiler_type_name_deduplicator_unittest.cc
@@ -0,0 +1,71 @@
+// 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 <string>
+
+#include "base/json/json_reader.h"
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/trace_event/heap_profiler_type_name_deduplicator.h"
+#include "base/values.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace trace_event {
+
+// Define all strings once, because the deduplicator requires pointer equality,
+// and string interning is unreliable.
+const char kInt[] = "int";
+const char kBool[] = "bool";
+const char kString[] = "string";
+const char kNeedsEscape[] = "\"quotes\"";
+
+scoped_ptr<Value> DumpAndReadBack(const ConvertableToTraceFormat& convertable) {
+  std::string json;
+  convertable.AppendAsTraceFormat(&json);
+  return JSONReader::Read(json);
+}
+
+TEST(TypeNameDeduplicatorTest, Deduplication) {
+  // The type IDs should be like this:
+  // 0: [unknown]
+  // 1: int
+  // 2: bool
+  // 3: string
+
+  scoped_refptr<TypeNameDeduplicator> dedup = new TypeNameDeduplicator;
+  ASSERT_EQ(1, dedup->Insert(kInt));
+  ASSERT_EQ(2, dedup->Insert(kBool));
+  ASSERT_EQ(3, dedup->Insert(kString));
+
+  // Inserting again should return the same IDs.
+  ASSERT_EQ(2, dedup->Insert(kBool));
+  ASSERT_EQ(1, dedup->Insert(kInt));
+  ASSERT_EQ(3, dedup->Insert(kString));
+
+  // A null pointer should yield type ID 0.
+  ASSERT_EQ(0, dedup->Insert(nullptr));
+}
+
+TEST(TypeNameDeduplicatorTest, EscapeTypeName) {
+  scoped_refptr<TypeNameDeduplicator> dedup = new TypeNameDeduplicator;
+  ASSERT_EQ(1, dedup->Insert(kNeedsEscape));
+
+  // Reading json should not fail, because the type name should have been
+  // escaped properly.
+  scoped_ptr<Value> type_names = DumpAndReadBack(*dedup);
+  ASSERT_NE(nullptr, type_names);
+
+  const DictionaryValue* dictionary;
+  ASSERT_TRUE(type_names->GetAsDictionary(&dictionary));
+
+  // When the type name was inserted, it got ID 1. The exported key "1"
+  // should contain the name, with quotes.
+  std::string type_name;
+  ASSERT_TRUE(dictionary->GetString("1", &type_name));
+  ASSERT_EQ("\"quotes\"", type_name);
+}
+
+}  // namespace trace_event
+}  // namespace base
diff --git a/base/trace_event/memory_allocator_dump_unittest.cc b/base/trace_event/memory_allocator_dump_unittest.cc
index 8d8d147..124de0d 100644
--- a/base/trace_event/memory_allocator_dump_unittest.cc
+++ b/base/trace_event/memory_allocator_dump_unittest.cc
@@ -125,7 +125,7 @@ TEST(MemoryAllocatorDumpTest, GuidGeneration) {
 
 TEST(MemoryAllocatorDumpTest, DumpIntoProcessMemoryDump) {
   FakeMemoryAllocatorDumpProvider fmadp;
-  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr));
+  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr, nullptr));
   MemoryDumpArgs dump_args = {MemoryDumpLevelOfDetail::DETAILED};
 
   fmadp.OnMemoryDump(dump_args, &pmd);
@@ -172,7 +172,7 @@ TEST(MemoryAllocatorDumpTest, DumpIntoProcessMemoryDump) {
 #if !defined(NDEBUG) && !defined(OS_ANDROID) && !defined(OS_IOS)
 TEST(MemoryAllocatorDumpTest, ForbidDuplicatesDeathTest) {
   FakeMemoryAllocatorDumpProvider fmadp;
-  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr));
+  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr, nullptr));
   pmd.CreateAllocatorDump("foo_allocator");
   pmd.CreateAllocatorDump("bar_allocator/heap");
   ASSERT_DEATH(pmd.CreateAllocatorDump("foo_allocator"), "");
diff --git a/base/trace_event/memory_dump_manager.cc b/base/trace_event/memory_dump_manager.cc
index e6a1cc3..7b46e41 100644
--- a/base/trace_event/memory_dump_manager.cc
+++ b/base/trace_event/memory_dump_manager.cc
@@ -15,6 +15,7 @@
 #include "base/threading/thread.h"
 #include "base/trace_event/heap_profiler_allocation_context_tracker.h"
 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
+#include "base/trace_event/heap_profiler_type_name_deduplicator.h"
 #include "base/trace_event/malloc_dump_provider.h"
 #include "base/trace_event/memory_dump_provider.h"
 #include "base/trace_event/memory_dump_session_state.h"
@@ -519,19 +520,26 @@ void MemoryDumpManager::OnTraceLogEnabled() {
   DCHECK(delegate_);  // At this point we must have a delegate.
 
   scoped_refptr<StackFrameDeduplicator> stack_frame_deduplicator = nullptr;
+  scoped_refptr<TypeNameDeduplicator> type_name_deduplicator = nullptr;
 
   if (heap_profiling_enabled_) {
-    // If heap profiling is enabled, the stack frame deduplicator will be in
-    // use. Add a metadata event to write its frames.
+    // If heap profiling is enabled, the stack frame deduplicator and type name
+    // deduplicator will be in use. Add a metadata events to write the frames
+    // and type IDs.
     stack_frame_deduplicator = new StackFrameDeduplicator;
+    type_name_deduplicator = new TypeNameDeduplicator;
     TRACE_EVENT_API_ADD_METADATA_EVENT(
         "stackFrames", "stackFrames",
         scoped_refptr<ConvertableToTraceFormat>(stack_frame_deduplicator));
+    TRACE_EVENT_API_ADD_METADATA_EVENT(
+        "typeNames", "typeNames",
+        scoped_refptr<ConvertableToTraceFormat>(type_name_deduplicator));
   }
 
   DCHECK(!dump_thread_);
   dump_thread_ = std::move(dump_thread);
-  session_state_ = new MemoryDumpSessionState(stack_frame_deduplicator);
+  session_state_ = new MemoryDumpSessionState(stack_frame_deduplicator,
+                                              type_name_deduplicator);
 
   for (auto it = dump_providers_.begin(); it != dump_providers_.end(); ++it) {
     it->disabled = false;
diff --git a/base/trace_event/memory_dump_session_state.cc b/base/trace_event/memory_dump_session_state.cc
index b9b0d1e..5aa79b1 100644
--- a/base/trace_event/memory_dump_session_state.cc
+++ b/base/trace_event/memory_dump_session_state.cc
@@ -8,8 +8,10 @@ namespace base {
 namespace trace_event {
 
 MemoryDumpSessionState::MemoryDumpSessionState(
-    const scoped_refptr<StackFrameDeduplicator>& stack_frame_deduplicator)
-    : stack_frame_deduplicator_(stack_frame_deduplicator) {}
+    const scoped_refptr<StackFrameDeduplicator>& stack_frame_deduplicator,
+    const scoped_refptr<TypeNameDeduplicator>& type_name_deduplicator)
+    : stack_frame_deduplicator_(stack_frame_deduplicator),
+      type_name_deduplicator_(type_name_deduplicator) {}
 
 MemoryDumpSessionState::~MemoryDumpSessionState() {
 }
diff --git a/base/trace_event/memory_dump_session_state.h b/base/trace_event/memory_dump_session_state.h
index 8a03207..6834471 100644
--- a/base/trace_event/memory_dump_session_state.h
+++ b/base/trace_event/memory_dump_session_state.h
@@ -8,6 +8,7 @@
 #include "base/base_export.h"
 #include "base/memory/ref_counted.h"
 #include "base/trace_event/heap_profiler_stack_frame_deduplicator.h"
+#include "base/trace_event/heap_profiler_type_name_deduplicator.h"
 
 namespace base {
 namespace trace_event {
@@ -18,7 +19,8 @@ class BASE_EXPORT MemoryDumpSessionState
     : public RefCountedThreadSafe<MemoryDumpSessionState> {
  public:
   MemoryDumpSessionState(
-      const scoped_refptr<StackFrameDeduplicator>& stack_frame_deduplicator);
+      const scoped_refptr<StackFrameDeduplicator>& stack_frame_deduplicator,
+      const scoped_refptr<TypeNameDeduplicator>& type_name_deduplicator);
 
   // Returns the stack frame deduplicator that should be used by memory dump
   // providers when doing a heap dump.
@@ -26,6 +28,12 @@ class BASE_EXPORT MemoryDumpSessionState
     return stack_frame_deduplicator_.get();
   }
 
+  // Returns the type name deduplicator that should be used by memory dump
+  // providers when doing a heap dump.
+  TypeNameDeduplicator* type_name_deduplicator() {
+    return type_name_deduplicator_.get();
+  }
+
  private:
   friend class RefCountedThreadSafe<MemoryDumpSessionState>;
   ~MemoryDumpSessionState();
@@ -33,6 +41,10 @@ class BASE_EXPORT MemoryDumpSessionState
   // Deduplicates backtraces in heap dumps so they can be written once when the
   // trace is finalized.
   scoped_refptr<StackFrameDeduplicator> stack_frame_deduplicator_;
+
+  // Deduplicates type names in heap dumps so they can be written once when the
+  // trace is finalized.
+  scoped_refptr<TypeNameDeduplicator> type_name_deduplicator_;
 };
 
 }  // namespace trace_event
diff --git a/base/trace_event/trace_event.gypi b/base/trace_event/trace_event.gypi
index 2e163c3..ca37015 100644
--- a/base/trace_event/trace_event.gypi
+++ b/base/trace_event/trace_event.gypi
@@ -17,6 +17,8 @@
       'trace_event/heap_profiler_heap_dump_writer.h',
       'trace_event/heap_profiler_stack_frame_deduplicator.cc',
       'trace_event/heap_profiler_stack_frame_deduplicator.h',
+      'trace_event/heap_profiler_type_name_deduplicator.cc',
+      'trace_event/heap_profiler_type_name_deduplicator.h',
       'trace_event/java_heap_dump_provider_android.cc',
       'trace_event/java_heap_dump_provider_android.h',
       'trace_event/memory_allocator_dump.cc',
@@ -72,6 +74,7 @@
       'trace_event/heap_profiler_allocation_register_unittest.cc',
       'trace_event/heap_profiler_heap_dump_writer_unittest.cc',
       'trace_event/heap_profiler_stack_frame_deduplicator_unittest.cc',
+      'trace_event/heap_profiler_type_name_deduplicator_unittest.cc',
       'trace_event/java_heap_dump_provider_android_unittest.cc',
       'trace_event/memory_allocator_dump_unittest.cc',
       'trace_event/memory_dump_manager_unittest.cc',
diff --git a/base/trace_event/winheap_dump_provider_win_unittest.cc b/base/trace_event/winheap_dump_provider_win_unittest.cc
index fac002f..c74a7b7 100644
--- a/base/trace_event/winheap_dump_provider_win_unittest.cc
+++ b/base/trace_event/winheap_dump_provider_win_unittest.cc
@@ -14,7 +14,7 @@ namespace base {
 namespace trace_event {
 
 TEST(WinHeapDumpProviderTest, OnMemoryDump) {
-  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr));
+  ProcessMemoryDump pmd(new MemoryDumpSessionState(nullptr, nullptr));
   MemoryDumpArgs dump_args = {MemoryDumpLevelOfDetail::DETAILED};
 
   WinHeapDumpProvider* winheap_dump_provider =