components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/leak_analyzer.cc

Index: components/metrics/leak_detector/leak_analyzer.cc
diff --git a/components/metrics/leak_detector/leak_analyzer.cc b/components/metrics/leak_detector/leak_analyzer.cc
new file mode 100644
index 0000000000000000000000000000000000000000..52be67006f16be4a3e6a79526cc78e021dbb7e53
--- /dev/null
+++ b/components/metrics/leak_detector/leak_analyzer.cc
@@ -0,0 +1,167 @@
+// 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 "components/metrics/leak_detector/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 (size_t 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 %lu %s *****\n",
+                 ranked_entries_.size(), string_print_->ValueTypeName(true));
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+
+  for (size_t i = 0; i < ranked_entries_.size() && size_remaining > 0; ++i) {

[jar (doing other things), 2015/08/14 02:34:38]

I think you want size_remaining > 1 here, and in lines below.  You definitely
want it here so that the loop can end early (if you run out of space).  

When the buffer size_remaining is 1, then at most a null character will be
written, and one will be returned by snprintf().  It doesn't include the cost of
writing the final null terminator... even though you always give it room to do
so.

[Simon Que, 2015/08/14 04:21:26]

Done.

+    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);

[jar (doing other things), 2015/08/14 02:34:38]

snprintf is probably better, to avoid buffer overruns.  Yes... I can see that
you are way safe... but better would be a defined constant:

const BUFFER_SIZE = 256;
and then use that in the declaration, as well as in the snprintf().

... or use sizeof(prev_entry_buffer) as the limit.

Your choice.

[Simon Que, 2015/08/14 04:21:26]

Done.

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

[jar (doing other things), 2015/08/14 02:34:38]

How do you know you wrote a comma, and didn't run out of space?  How do you know
you had suspected leaks to print?

[Simon Que, 2015/08/14 04:21:26]

Done.

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

[jar (doing other things), 2015/08/14 02:34:38]

This will always be at least 1.

What do you want to return?  Do you want to include the \0 in your tally?

[Simon Que, 2015/08/14 04:21:26]

Done.

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

[jar (doing other things), 2015/08/14 02:34:38]

nit: Personal preference: I like shorter code with less repetitions... and since
both branches of the "if" do an increment on the iter, better might be:

auto erase_iter = iter++;
if (erase_iter->second == 0) {
  suspected_historgram.erase(erase_iter);
}

If you hate this... or this is really external code that you don't want to
improve... ok.... but it is a personal preference.

[Simon Que, 2015/08/14 04:21:26]

This is not external code. Done.

+  }
+
+  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 (size_t i = 0; i < prev_ranked_entries_.size(); ++i) {
+    if (prev_ranked_entries_.entry(i).value == value)
+      return &prev_ranked_entries_.entry(i);

[jar (doing other things), 2015/08/14 02:34:38]

This concerned me a bit... why do you want to return a pointer into such a
structure, when there is other code that mutates these structures (I think).  I
spend less time reviewing code when it is clearly safer.

In both (private) call sites, all you seem to use in the "->count".

Could you return that count, and be a bit safer?

If you're struggling to return a count, and a success/failure, you could pass in
a pointer to place the count, and return a success/fail return code, or such. 
Your choice.

[Simon Que, 2015/08/14 04:21:26]

Done.

+  }
+  return NULL;
+}
+
+}  // namespace leak_detector