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"
+
+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.
+    uint32_t prev_count = 0;
+    if (GetPreviousCountForValue(entry.value, &prev_count))
+      ranked_deltas.Add(entry.value, entry.count - prev_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 > 1) {
+    attempted_size =
+        snprintf(buffer, size_remaining, "***** Top %zu %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 > 1; ++i) {
+    const RankedEntry& entry = ranked_entries_.entry(i);
+    if (entry.count == 0)
+      continue;
+
+    // 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);
+    }
+
+    int attempted_size =

[jar (doing other things), 2015/08/15 03:29:01]

nit: Why don't you use the attempted_size declared in the outer scope?  

[Simon Que, 2015/08/15 23:28:31]

Done.

+        snprintf(buffer, size_remaining, "%s: %10u %s\n",
+                 string_print_->ValueToString(entry.value, true), entry.count,
+                 prev_entry_buffer);
+    size_remaining -= attempted_size;
+    buffer += attempted_size;
+  }
+
+  // Now report the suspected sizes.
+  if (size_remaining > 1) {
+    attempted_size = snprintf(buffer, size_remaining, "Suspected %s: ",
+                              string_print_->ValueTypeName(true));
+    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, ",
+                   string_print_->ValueToString(leak_value, false));
+      size_remaining -= attempted_size;
+      buffer += attempted_size;
+      wrote_suspected_leak = true;
+    }
+    // Erase the last comma and space.

[jar (doing other things), 2015/08/15 03:29:01]

As mentioned in my earlier comment: How do you know that you didn't run out of
space?  If you did run out (in the any of the iterations of the for loop on line
74), then the last item may not be a comma and space. 

It is also fairly extreme... but if this function is called with a buffer of
length 2, then you can actually undeflow the buffer with this pointer adjustment
on line 84.  

I think the first issue is more worrisome... though I don't know how "terrible"
it will be if we truncate some charaters that are not trailing commas... but I
don't know how the output will be processed.

[Simon Que, 2015/08/15 23:28:31]

All this logging code is meant to be temporary. In a future iteration, I intend
to replace it with passing data structures to UMA.

That said, I've fixed this.

+    if (wrote_suspected_leak) {
+      buffer -= 2;
+      size_remaining += 2;
+    }
+  }
+  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 (int i = 0; i < static_cast<int>(ranked_deltas.size()) - 1; ++i) {

[jar (doing other things), 2015/08/15 03:29:01]

nit: Prefer to not use casts.  I'm not sure I'm following the logic here...
but... perhaps...

In this case, I think(?) your concerns is that you don't want to subtract 1 from
a size(), when size could be zero.  

Can you avoid the problem by instead itterating:

for (size_t i = 1; i < ranked_delats.size(); ++i)

and then using i-1 and i rather than (what you're using now) i and i+1

[Simon Que, 2015/08/15 23:28:31]

Done.

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

[jar (doing other things), 2015/08/15 03:29:01]

nit: This was a little confusing that you tested found_drop constantly, but yet
never changed it in this loop.  It would probably read more clearly as:

if (found_drop) {
  for (...) {
    ...
  }

[Simon Que, 2015/08/15 23:28:31]

Done.

+    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