components/metrics: Add runtime memory leak detector

third_party/tcmalloc/chromium/src/leak_analyzer.h

+// 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.
+
+// ---
+// Author: Simon Que
+
+#ifndef _LEAK_ANALYZER_H_
+#define _LEAK_ANALYZER_H_
+
+#include <map>
+#include <vector>
+
+#include "base/custom_allocator.h"
+#include "ranked_list.h"
+
+// This class looks for possible leak patterns in allocation data over time.
+// The typename T can be any data type associated with an allocation class, e.g.
+// size or call stack.
+
+namespace leak_detector {
+
+template <typename T>
+class LeakAnalyzer {
+ public:
+  // Interface for printing strings for the template class type.
+  class StringPrint {
+   public:
+    // Gets the string representation of a value. Returns the string stored in
+    // |buffer_|. The contents of |buffer_| will change if this is called again
+    // with different inputs.
+    virtual const char* ValueToString(const T& value, bool spacing_on) = 0;
+
+    // Gets the word that describes the value type.
+    virtual const char* ValueTypeName(bool is_plural) = 0;
+
+   protected:
+    // Buffer for returning the string representation of a value.
+    static const int kStringPrintBufferSize = 1024;
+    char buffer_[kStringPrintBufferSize];
+  };
+
+  template <typename Type>
+  using Allocator = STL_Allocator<Type, CustomAllocator>;
+
+  LeakAnalyzer(int ranking_size, int num_suspicions_threshold,
+               StringPrint* string_print)
+      : ranking_size_(ranking_size),
+        score_increase_(1 << num_suspicions_threshold),
+        score_threshold_((1 << num_suspicions_threshold) * 2 - 1),
+        ranked_entries_(ranking_size),
+        prev_ranked_entries_(ranking_size),
+        string_print_(string_print) {
+    suspected_leaks_.reserve(ranking_size);
+  }
+
+  ~LeakAnalyzer() {}
+
+  // Take in a list of allocations, sorted by count.
+  void AddSample(const RankedList<T>& ranked_list) {
+    // Save the ranked entries from the previous call.
+    prev_ranked_entries_ = ranked_entries_;
+
+    // Save the current entries.
+    ranked_entries_ = ranked_list;
+
+    RankedList<T> 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);
+  }
+
+  // Log the leak detector's top sizes and suspected sizes. |buffer| is a char
+  // buffer of size |buffer_size| that can eventually be logged.
+  int 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 T& 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;
+  }
+
+  // Used to report suspected leaks.
+  const std::vector<T, Allocator<T>>& suspected_leaks() const {
+    return suspected_leaks_;
+  }
+
+ private:
+  using RankedEntry = typename RankedList<T>::Entry;
+
+  // Analyze a list of allocation count deltas from the previous iteration. If
+  // anything looks like a possible leak, update the suspicion scores.
+  void AnalyzeDeltas(const RankedList<T>& 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 T& 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);
+    }
+  }
+
+  // Returns the RankedEntry from the previous analysis that had the given
+  // value, or NULL if it didn't exist.
+  const RankedEntry* GetPreviousEntryWithValue(const T& 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;
+  }
+
+  // Look for the top |ranking_size_| entries when analyzing leaks.
+  const int ranking_size_;
+
+  // Each time an entry is suspected as a possible leak, increase its suspicion
+  // score by this much.
+  const int score_increase_;
+
+  // Report suspected leaks when the suspicion score reaches this value.
+  const int score_threshold_;
+
+  // A mapping of allocation values to suspicion score. All allocations in this
+  // container are suspected leaks. The score can increase or decrease over
+  // time. Once the score  reaches |score_threshold_|, the entry is reported as
+  // a suspected leak in |suspected_leaks_|.
+  std::map<T, uint32, std::less<T>, Allocator<std::pair<T, uint32>>>
+      suspected_histogram_;
+
+  // Array of allocated values that passed the suspicion threshold and are being
+  // reported.
+  std::vector<T, Allocator<T>> suspected_leaks_;
+
+  // The most recent allocation entries, since the last call to AddSample().
+  RankedList<T> ranked_entries_;
+  // The previous allocation entries, from before the last call to AddSample().
+  RankedList<T> prev_ranked_entries_;
+
+  // For logging.
+  StringPrint* string_print_;
+
+  DISALLOW_COPY_AND_ASSIGN(LeakAnalyzer);
+};
+
+}  // namespace leak_detector
+
+#endif  // _LEAK_ANALYZER_H_