Index: third_party/tcmalloc/chromium/src/leak_analyzer.h |
diff --git a/third_party/tcmalloc/chromium/src/leak_analyzer.h b/third_party/tcmalloc/chromium/src/leak_analyzer.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..de4a195f6693d3a3de82a0d889502835cbf419b4 |
--- /dev/null |
+++ b/third_party/tcmalloc/chromium/src/leak_analyzer.h |
@@ -0,0 +1,265 @@ |
+// 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, |
jar (doing other things)
2015/07/20 22:19:03
Is this a fork of external code? I not, I think t
|
+ 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; |
jar (doing other things)
2015/07/20 22:19:03
why is this giant routine placed in a header, and
|
+ 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_ |