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 <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:
+  // For local allocations.
+  typedef void* (*Allocator)(size_t size);
+  typedef void  (*DeAllocator)(void* ptr);
+
+  // 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];
+  };
+
+  LeakAnalyzer(int ranking_size, int num_suspicions_threshold,
+               Allocator alloc, DeAllocator dealloc,
+               StringPrint* string_print)
+      : ranking_size_(ranking_size),
+        score_increase_(1 << num_suspicions_threshold),
+        score_threshold_((1 << num_suspicions_threshold) * 2 - 1),
+        num_suspected_leaks_(0),
+        alloc_(alloc),
+        dealloc_(dealloc),
+        ranked_entries_(ranking_size, alloc, dealloc),
+        prev_ranked_entries_(ranking_size, alloc, dealloc),
+        string_print_(string_print) {
+    size_t suspected_histogram_size = ranking_size * sizeof(SuspicionEntry);
+    suspected_histogram_ =
+        static_cast<SuspicionEntry*>(alloc_(suspected_histogram_size));
+    memset(suspected_histogram_, 0, suspected_histogram_size);
+
+    size_t suspected_leak_size = ranking_size * sizeof(T);
+    suspected_leaks_ = static_cast<T*>(alloc_(suspected_leak_size));
+    memset(suspected_leaks_, 0, suspected_leak_size);
+  }
+
+  ~LeakAnalyzer() {
+    dealloc_(suspected_histogram_);
+    dealloc_(suspected_leaks_);
+
+    suspected_histogram_ = NULL;
+    suspected_leaks_ = NULL;
+  }
+
+  // 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_, alloc_, dealloc_);
+    for (int i = 0; i < ranked_list.size(); ++i) {
+      const RankedEntry* entry =
+          reinterpret_cast<const RankedEntry*>(&ranked_list.entries()[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 (num_suspected_leaks_) {
+      for (int i = 0; i < num_suspected_leaks_ && size_remaining > 0; ++i) {
+        attempted_size =
+            snprintf(buffer, size_remaining, "%s, ",
+                     string_print_->ValueToString(suspected_leaks_[i], 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 T* suspected_leaks() const {
+    return suspected_leaks_;
+  }
+  int num_suspected_leaks() const {
+    return num_suspected_leaks_;
+  }
+
+ private:
+  using RankedEntry = typename RankedList<T>::Entry;
+
+  // An entry that is suspected as a possible leak. |score| is the level of
+  // suspicion, which can increase over time. Once it reaches |score_threshold_|
+  // the entry is reported as a suspected leak in |suspected_leaks_|.
+  struct SuspicionEntry {
+    int score;
+    T value;
+
+    // Flag indicating that this entry is valid, used in a fixed-size array.
+    bool valid;
+  };
+
+  // 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.
+    for (int i = 0; i < ranking_size_; ++i) {
+      suspected_histogram_[i].score /= 2;
+      // Invalidate entries with scores of 0 so that entries that are no longer
+      // under suspicion do not take up a slot that could be occupied by a new
+      // entry that is under suspicion.
+      if (suspected_histogram_[i].score == 0)
+        suspected_histogram_[i].valid = false;
+    }
+
+    const RankedEntry* entries =
+        reinterpret_cast<const RankedEntry*>(ranked_deltas.entries());
+    bool found_drop = false;
+    int drop_index = -1;
+    for (int i = 0; i < ranked_deltas.size() - 1; ++i) {
+      const RankedEntry& entry = entries[i];
+      const RankedEntry& next_entry = entries[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) {
+      for (int j = 0; j < ranking_size_; ++j) {
+        SuspicionEntry* suspected = &suspected_histogram_[j];
+        // Add a new suspected with the current value if there's an empty slot.
+        if (!suspected->valid) {
+          suspected->valid = true;
+          suspected->value = entries[i].value;
+        }
+        if (suspected->value == entries[i].value) {
+          suspected->score += score_increase_;
+          break;
+        }
+      }
+    }
+
+    // Now check the leak suspicion scores.
+    num_suspected_leaks_ = 0;
+    for (int i = 0;
+         i < ranking_size_ && num_suspected_leaks_ < ranking_size_;
+         ++i) {
+      // Only report suspected values that have accumulated a suspicion score.
+      // This is achieved by maintaining suspicion for several cycles, with few
+      // skips.
+      const SuspicionEntry& suspected = suspected_histogram_[i];
+      if (!suspected.valid || suspected.score < score_threshold_) {
+        continue;
+      }
+      // Store the size.
+      suspected_leaks_[num_suspected_leaks_++] = suspected.value;
+    }
+  }
+
+  // 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_;
+
+  // The number of currently reported suspected leaks.
+  int num_suspected_leaks_;
+
+  // For local allocation.
+  const Allocator alloc_;
+  const DeAllocator dealloc_;
+
+  // Points to an array to track allocation values and their suspicion scores.
+  SuspicionEntry *suspected_histogram_;
+
+  // Array of allocated values that passed the suspicion threshold and are being
+  // reported.
+  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_