components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/leak_analyzer.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 "components/metrics/leak_detector/leak_analyzer.h"
+
+#include <algorithm>
+
+namespace leak_detector {
+
+void LeakAnalyzer::AddSample(const RankedList& ranked_list) {
+  // Save the ranked entries from the previous call.
+  prev_ranked_entries_ = ranked_entries_;

[jar (doing other things), 2015/08/21 02:48:42]

This seems to instigate a vector copy... which presumably causes an
allocation... and a deallocation of the old vector.  Is this really what you
wanted to do?  ...and is the ongoing cost contained??

[Simon Que, 2015/08/21 05:44:05]

I can optimize this.

However, keep in mind that the leak analysis doesn't run that frequently...
something on the order of once per few seconds. The performance here is not a
bottleneck.

[Simon Que, 2015/08/21 21:59:19]

I'm going to hold off on implementing this until I've reworked RankedList into a
form that we're both satisfied with.

+
+  // 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.
+    uint32_t prev_count = 0;
+    if (GetPreviousCountForValue(entry.value, &prev_count))
+      ranked_deltas.Add(entry.value, entry.count - prev_count);

[jar (doing other things), 2015/08/21 02:48:42]

Since each Add() is an O(N) operation (to do the emplace vector insertion), it
would appear that iterating over this vector to accumulate the deltas (this way)
is an O(N^2) operation.  Is this what your plan was?  How large is this vector
expected to routinely be when this method is called?

[Simon Que, 2015/08/21 05:44:04]

N=16.

+  }
+
+  AnalyzeDeltas(ranked_deltas);
+}
+
+int LeakAnalyzer::Dump(char* buffer, const int buffer_size) const {
+  int size_remaining = buffer_size;
+  int attempted_size = 0;
+
+  // Buffer used for calling LeakDetectorValueType::ToString().
+  char to_string_buffer[256];
+  to_string_buffer[0] = '\0';

[jar (doing other things), 2015/08/21 02:48:42]

nit: What is the significance of this line?  Should it be deleted?  I think you
mutate this buffer below, destroying this initial value (before reuse), so it is
a bit misleading to ever have this setting made.

[Simon Que, 2015/08/21 21:59:19]

Deleted.

+
+  if (ranked_entries_.size() > 0) {
+    // Dump the top entries.
+    if (size_remaining > 1) {
+      attempted_size =
+          snprintf(buffer, size_remaining, "***** Top %zu %ss *****\n",
+                   ranked_entries_.size(),
+                   ranked_entries_.entry(0).value.GetTypeName());
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+    }
+
+    for (size_t i = 0; i < ranked_entries_.size() && size_remaining > 1; ++i) {
+      const RankedEntry& entry = ranked_entries_.entry(i);
+      if (entry.count == 0)
+        continue;

[jar (doing other things), 2015/08/21 02:48:42]

*IF* you assume RankedEntries are indeed in reverse sorted order, can't you
conclude that all the other counts will be zero, and we should break here?  Is
there a reason not to?

[Simon Que, 2015/08/21 21:59:19]

You're right, it makes more sense to break.

+
+      // Determine what count was recorded for this value last time.
+      char prev_entry_buffer[256];
+      prev_entry_buffer[0] = '\0';
+
+      uint32_t prev_count = 0;
+      if (GetPreviousCountForValue(entry.value, &prev_count)) {
+        snprintf(prev_entry_buffer, sizeof(prev_entry_buffer),
+                 "(%10d)", entry.count - prev_count);
+      }
+
+      attempted_size =
+          snprintf(
+              buffer, size_remaining, "%10s: %10u %s\n",
+              entry.value.ToString(to_string_buffer, sizeof(to_string_buffer)),
+              entry.count, prev_entry_buffer);
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+    }
+  }
+
+  if (!suspected_leaks_.empty()) {
+    // Report the suspected sizes.
+    if (size_remaining > 1) {
+      const ValueType& first_leak_value = suspected_leaks_[0];
+      attempted_size = snprintf(buffer, size_remaining, "Suspected %ss: ",
+                                first_leak_value.GetTypeName());
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+    }
+    if (size_remaining > 1) {
+      bool wrote_suspected_leak = false;
+      for (const ValueType& leak_value : suspected_leaks_) {
+        attempted_size =
+            snprintf(buffer, size_remaining, "%s, ",
+                     leak_value.ToString(
+                         to_string_buffer, sizeof(to_string_buffer)));
+        size_remaining -= attempted_size;
+        buffer += attempted_size;
+        wrote_suspected_leak = true;
+      }
+      // Erase the last comma and space if they were written, even if partially.
+      if (wrote_suspected_leak) {
+        int length_of_comma_and_space = std::min(2, attempted_size);
+        buffer -= length_of_comma_and_space;
+        size_remaining += length_of_comma_and_space;

[jar (doing other things), 2015/08/21 02:48:42]

Note that this "backtracking" has left you buffer without a null termination.  
I guess your test on line 102 is now guaranteed to pass... so line 103 will
probably get you back to a null-terminated state... but this probably makes your
code more fragile.  better would be to write a null here as well.

nit: Personal preference: A better pattern (than backtracking) for putting in
commas between entries is to have a bi-valued variable that indicates that
you've printed at least one... and when that becomes true, always *prepend* ", "
before you print the next item.

For example:
char* optional_comma = "";  // Instead of wrote_suspected_leak.
for (...leak_values : suspected_leaks_) {
   ... snprint(buffer, size_remaining, "%s%s",
         optional_commana, leak_value.ToString())
   optional_comma = ", ";
   ...
}

It is your choice of which way to write the code....  but the latter will be
simpler.... and *slightly* more correct, as your current code would often
(sometimes?) kill off characters that were not trailing spaces and commas.

[Simon Que, 2015/08/21 21:59:20]

Done.

+      }
+    }
+    if (size_remaining > 1) {
+      attempted_size = snprintf(buffer, size_remaining, "\n");
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+    }
+  }
+
+  // Return the number of bytes written, excluding the null terminator.
+  return buffer_size - size_remaining;
+}
+
+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.
+    auto erase_iter = iter++;
+    if (iter->second == 0) {
+      suspected_histogram_.erase(erase_iter);
+    }
+  }
+
+  bool found_drop = false;
+  int drop_index = -1;
+  for (size_t i = 1; i < ranked_deltas.size(); ++i) {
+    const RankedEntry& entry = ranked_deltas.entry(i - 1);
+    const RankedEntry& next_entry = ranked_deltas.entry(i);
+
+    // 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 == 1 && entry.count == 0)
+      break;
+
+    // Find the first major drop in values.
+    if (entry.count > next_entry.count * 2) {
+      found_drop = true;
+      drop_index = i;
+      break;
+    }
+  }
+
+  // Take the pre-drop sizes and increase their suspicion score.
+  if (found_drop) {
+    for (int i = 0; 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);
+  }
+}
+
+bool LeakAnalyzer::GetPreviousCountForValue(const ValueType& value,
+                                            uint32_t* count) 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) {
+      *count = prev_ranked_entries_.entry(i).count;
+      return true;
+    }
+  }
+  return false;
+}
+
+}  // namespace leak_detector