components/metrics: Add runtime memory leak detector

third_party/tcmalloc/chromium/src/leak_analyzer.cc

Index: third_party/tcmalloc/chromium/src/leak_analyzer.cc
diff --git a/third_party/tcmalloc/chromium/src/leak_analyzer.cc b/third_party/tcmalloc/chromium/src/leak_analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..7ebd3677431a24761400edc645c295fb86056b11
--- /dev/null
+++ b/third_party/tcmalloc/chromium/src/leak_analyzer.cc
@@ -0,0 +1,167 @@
+// Copyright (c) 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 "leak_analyzer.h"
+
+namespace leak_detector {
+
+void LeakAnalyzer::AddSample(const RankedList& ranked_list) {
+  // Save the ranked entries from the previous call.
+  prev_ranked_entries_ = ranked_entries_;
+
+  // Save the current entries.
+  ranked_entries_ = ranked_list;
+
+  RankedList ranked_deltas(ranking_size_);
+  for (int i = 0; i < ranked_list.size(); ++i) {
+    const RankedEntry& entry = ranked_list.entry(i);
+
+    // Determine what count was recorded for this value last time.
+    const RankedEntry* prev_entry = GetPreviousEntryWithValue(entry.value);
+    if (prev_entry)
+      ranked_deltas.Add(entry.value, entry.count - prev_entry->count);
+  }
+
+  AnalyzeDeltas(ranked_deltas);
+}
+
+int LeakAnalyzer::Dump(char* buffer, const int buffer_size) const {
+  int size_remaining = buffer_size;
+  int attempted_size = 0;
+
+  // Dump the top entries.
+  if (size_remaining > 0) {
+    attempted_size =
+        snprintf(buffer, size_remaining, "***** Top %d %s *****\n",
+                 ranked_entries_.size(), string_print_->ValueTypeName(true));
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+
+  for (int i = 0; i < ranked_entries_.size() && size_remaining > 0; ++i) {
+    const RankedEntry& entry = ranked_entries_.entry(i);
+    if (entry.count == 0)
+      continue;
+
+    // Determine what count was recorded for this value last time.
+    const RankedEntry* prev_entry = GetPreviousEntryWithValue(entry.value);
+
+    char prev_entry_buffer[256];
+    prev_entry_buffer[0] = '\0';
+    if (prev_entry)
+      sprintf(prev_entry_buffer, "(%10d)", entry.count - prev_entry->count);
+
+    int attempted_size =
+        snprintf(buffer, size_remaining, "%s: %10u %s\n",
+                 string_print_->ValueToString(entry.value, true), entry.count,
+                 prev_entry ? prev_entry_buffer : "");
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+
+  // Now report the suspected sizes.
+  if (size_remaining > 0) {
+    attempted_size = snprintf(buffer, size_remaining, "Suspected %s: ",
+                              string_print_->ValueTypeName(true));
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+  if (size_remaining > 0) {
+    for (const ValueType& leak_value : suspected_leaks_) {
+      attempted_size =
+          snprintf(buffer, size_remaining, "%s, ",
+                   string_print_->ValueToString(leak_value, false));
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+    }
+    // Erase the last comma and space.
+    buffer -= 2;
+    size_remaining += 2;
+  }
+  if (size_remaining > 0) {
+    attempted_size = snprintf(buffer, size_remaining, "\n");
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+
+  // Return the number of bytes written.
+  if (size_remaining >= 0)
+    return buffer_size - size_remaining;
+  return buffer_size;
+}
+
+void LeakAnalyzer::AnalyzeDeltas(const RankedList& ranked_deltas) {
+  // First, let the suspicion scores decay to deprecate older suspicions.
+  auto iter = suspected_histogram_.begin();
+  while (iter != suspected_histogram_.end()) {
+    // Suspicion score is the map value.
+    iter->second /= 2;
+
+    // Erase entries whose suspicion score reaches 0.
+    if (iter->second == 0) {
+      auto erase_iter = iter++;
+      suspected_histogram_.erase(erase_iter);
+    } else {
+      ++iter;
+    }
+  }
+
+  bool found_drop = false;
+  int drop_index = -1;
+  for (int i = 0; i < static_cast<int>(ranked_deltas.size()) - 1; ++i) {
+    const RankedEntry& entry = ranked_deltas.entry(i);
+    const RankedEntry& next_entry = ranked_deltas.entry(i + 1);
+
+    // If the first entry is 0, that means all deltas are 0 or negative. Do
+    // not treat this as a suspicion of leaks; just quit.
+    if (i == 0 && entry.count == 0)
+      break;
+
+    // Find the first major drop in values.
+    if (entry.count > next_entry.count * 2) {
+      found_drop = true;
+      drop_index = i + 1;
+      break;
+    }
+  }
+
+  // Take the pre-drop sizes and increase their suspicion score.
+  for (int i = 0; found_drop && i < drop_index; ++i) {
+    const ValueType& value = ranked_deltas.entry(i).value;
+
+    auto iter = suspected_histogram_.find(value);
+    if (iter != suspected_histogram_.end()) {
+      iter->second += score_increase_;
+    } else if (suspected_histogram_.size() < ranking_size_) {
+      // Create a new entry.
+      suspected_histogram_[value] = score_increase_;
+    }
+  }
+
+  // Now check the leak suspicion scores. Make sure to erase the suspected
+  // leaks from the previous call.
+  suspected_leaks_.clear();
+  for (const auto& entry : suspected_histogram_) {
+    if (suspected_leaks_.size() > ranking_size_)
+      break;
+
+    // Only report suspected values that have accumulated a suspicion score.
+    // This is achieved by maintaining suspicion for several cycles, with few
+    // skips.
+    if (entry.second >= score_threshold_)
+      suspected_leaks_.emplace_back(entry.first);
+  }
+}
+
+const LeakAnalyzer::RankedEntry* LeakAnalyzer::GetPreviousEntryWithValue(
+    const ValueType& value) const {
+  // Determine what count was recorded for this value last time.
+  for (int i = 0; i < prev_ranked_entries_.size(); ++i) {
+    if (prev_ranked_entries_.entry(i).value == value)
+      return &prev_ranked_entries_.entry(i);
+  }
+  return NULL;
+}
+
+}  // namespace leak_detector