components/metrics: Add runtime memory leak detector

third_party/tcmalloc/chromium/src/leak_detector_impl.cc

+// 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.
+
+#include "leak_detector_impl.h"
+
+#include <cstddef>
+#include <cstring>
+
+#include <algorithm>
+
+#include "base/basictypes.h"
+#include "base/commandlineflags.h"
+#include "base/logging.h"
+#include "call_stack_table.h"
+#include "farmhash.h"
+#include "ranked_list.h"
+
+// A size must be suspected this many times to be reported as a leak suspect.
+DECLARE_int32(size_suspicion_threshold);
+
+// If set, dumps all leak analysis data, not just suspected leak reports.
+DECLARE_bool(dump_leak_analysis);
+
+namespace leak_detector {
+
+namespace {
+
+// Look for leaks in the the top N entries in each tier, where N is this value.
+const int kRankedListSize = 16;
+
+using ValueType = LeakDetectorValueType;
+
+// Used for printing size values in LeakAnalyzer.
+class SizeStringPrint : public LeakAnalyzer::StringPrint {
+ public:
+  // Gets the string representation of a value.
+  virtual const char* ValueToString(const ValueType& value, bool spacing_on) {
+    snprintf(buffer_, sizeof(buffer_), spacing_on ? "%10u" : "%u",
+             value.size());
+    return buffer_;
+  }
+
+  // Gets the word that describes the value type.
+  virtual const char* ValueTypeName(bool is_plural) {
+    return is_plural ? "sizes" : "size";
+  }
+} size_string_print;
+
+// Prints the input string buffer using RAW_LOG, pre-fixing each line with the
+// process id.
+void PrintWithPidOnEachLine(char* buf) {
+  char *ptr = strchr(buf, '\n');
+  do {
+    // Break up the string.
+    if (ptr)
+      *ptr = '\0';
+    // Print out the former part.
+    RAW_LOG(0, "%d: %s", getpid(), buf);
+    // Re-point |buf| to the latter part.
+    if (ptr)
+      buf = ptr + 1;
+  } while (ptr = strchr(buf, '\n'));
+}
+
+// For passing to AddressMap.
+void* Alloc(size_t size) {
+  return CustomAllocator::Allocate(size);
+}
+void DeAlloc(void* ptr) {
+  CustomAllocator::Free(ptr, 0);
+}
+
+}  // namespace
+
+LeakDetectorImpl::LeakDetectorImpl(uint64 mapping_addr, uint64 mapping_size)
+    : num_stack_tables_(0),
+      address_map_(Alloc, DeAlloc),
+      size_leak_analyzer_(kRankedListSize, FLAGS_size_suspicion_threshold,
+                          &size_string_print),
+      mapping_addr_(mapping_addr),
+      mapping_size_(mapping_size) {
+  // Initialize.
+  memset(entries_, 0, sizeof(entries_));
+  memset(&stats_, 0, sizeof(stats_));
+  memset(&call_stack_stats_, 0, sizeof(call_stack_stats_));
+}
+
+LeakDetectorImpl::~LeakDetectorImpl() {
+  for (CallStack* call_stack : call_stacks_)
+    DeAlloc(call_stack);
+
+  // Free any call stack tables.
+  for (int i = 0; i < kNumSizeEntries; ++i) {
+    CallStackTable* table = entries_[i].stack_table;
+    if (!table)
+      continue;
+    table->~CallStackTable();
+    DeAlloc(table);
+  }
+}
+
+bool LeakDetectorImpl::ShouldGetStackTraceForSize(size_t size) const {
+  return entries_[SizeToIndex(size)].stack_table != NULL;
+}
+
+void LeakDetectorImpl::RecordAlloc(
+    const void* ptr, size_t size,
+    int stack_depth, const void* const stack[]) {
+  AllocInfo alloc_info;
+  alloc_info.bytes = size;
+
+  stats_.alloc_size += alloc_info.bytes;
+  stats_.allocs++;
+
+  AllocSizeEntry* entry = GetEntryForSize(size);
+  ++entry->num_allocs;
+
+  if (stack_depth > 0) {
+    CallStack* call_stack = GetCallStack(stack_depth, stack);
+    call_stack->allocs++;
+    call_stack->alloc_size += size;
+    alloc_info.call_stack = call_stack;
+
+    call_stack_stats_.alloc_size += alloc_info.bytes;
+    call_stack_stats_.allocs++;
+
+    if (entry->stack_table)
+      entry->stack_table->Add(call_stack);
+  }
+
+  address_map_.Insert(ptr, alloc_info);
+}
+
+void LeakDetectorImpl::RecordFree(const void* ptr) {
+  // Look up entry.
+  AllocInfo alloc_info;
+  if (!address_map_.FindAndRemove(ptr, &alloc_info))
+    return;
+
+  AllocSizeEntry* entry = GetEntryForSize(alloc_info.bytes);
+  ++entry->num_frees;
+
+  CallStack* call_stack = alloc_info.call_stack;
+  if (call_stack) {
+    call_stack->frees++;
+    call_stack->free_size += alloc_info.bytes;
+
+    call_stack_stats_.frees++;
+    call_stack_stats_.free_size += alloc_info.bytes;
+
+    if (entry->stack_table)
+      entry->stack_table->Remove(call_stack);
+  }
+  stats_.frees++;
+  stats_.free_size += alloc_info.bytes;
+}
+
+void LeakDetectorImpl::TestForLeaks() {
+  // Add net alloc counts for each size to a ranked list.
+  RankedList size_ranked_list(kRankedListSize);
+  for (int i = 0; i < kNumSizeEntries; ++i) {
+    const AllocSizeEntry& entry = entries_[i];
+    ValueType size_value(IndexToSize(i));
+    size_ranked_list.Add(size_value, entry.num_allocs - entry.num_frees);
+  }
+  size_leak_analyzer_.AddSample(size_ranked_list);
+
+  // Dump out the top entries.
+  if (FLAGS_dump_leak_analysis) {
+    char buf[0x4000];
+    buf[0] = '\0';
+    size_leak_analyzer_.Dump(buf, sizeof(buf));
+    PrintWithPidOnEachLine(buf);
+  }
+
+  // Get suspected leaks by size.
+  for (const ValueType& size_value : size_leak_analyzer_.suspected_leaks()) {
+    uint32_t size = size_value.size();
+    AllocSizeEntry* entry = GetEntryForSize(size);
+    if (entry->stack_table)
+      continue;
+    RAW_VLOG(0, "%d: Adding stack table for size %u", getpid(), size);
+    entry->stack_table = new(Alloc(sizeof(CallStackTable))) CallStackTable;
+    ++num_stack_tables_;
+  }
+
+  // Check for leaks in each CallStackTable. It makes sense to this before
+  // checking the size allocations, because that could potentially create new
+  // CallStackTable. However, the overhead to check a new CallStackTable is
+  // small since this function is run very rarely. So handle the leak checks of
+  // Tier 2 here.
+  for (int i = 0; i < arraysize(entries_); ++i) {
+    const AllocSizeEntry& entry = entries_[i];
+    CallStackTable* stack_table = entry.stack_table;
+    if (!stack_table)
+      continue;
+
+    if (FLAGS_dump_leak_analysis) {
+      // Dump table info.
+      char buf[0x4000];
+      RAW_VLOG(0, "%d: Stack table for size %d", getpid(), IndexToSize(i));
+      buf[0] = '\0';
+      stack_table->Dump(buf, sizeof(buf));
+      PrintWithPidOnEachLine(buf);
+    }
+
+    // Get suspected leaks by call stack.
+    stack_table->TestForLeaks();
+    const LeakAnalyzer& leak_analyzer = stack_table->leak_analyzer();
+    for (const ValueType& call_stack_value : leak_analyzer.suspected_leaks()) {
+      const CallStack* call_stack = call_stack_value.call_stack();
+      RAW_VLOG(0, "%d: Suspected call stack for size %u: %p",
+               getpid(), IndexToSize(i), call_stack);
+      for (int k = 0; k < call_stack->depth; ++k)
+        RAW_VLOG(0, "%d:   %p", getpid(), GetOffset(call_stack->stack[k]));
+    }
+  }
+}
+
+void LeakDetectorImpl::DumpStats() const {
+  RAW_VLOG(0, "%d: Alloc size: %lu\n", getpid(), stats_.alloc_size);
+  RAW_VLOG(0, "%d: Free size: %lu\n", getpid(), stats_.free_size);
+  RAW_VLOG(0, "%d: Net alloc size: %lu\n", getpid(),
+           stats_.alloc_size - stats_.free_size);
+  RAW_VLOG(0, "%d: Number of stack tables: %d\n", getpid(), num_stack_tables_);
+  if (stats_.alloc_size) {
+    RAW_VLOG(0, "%d: %% of calls with stack trace: %.2f%%\n", getpid(),
+             static_cast<double>(call_stack_stats_.alloc_size * 100) /
+                 stats_.alloc_size);
+  }
+  RAW_VLOG(0, "%d: Number of call stack buckets: %d\n", getpid(),
+           call_stacks_.bucket_count());
+}
+
+// static
+inline int LeakDetectorImpl::SizeToIndex(size_t size) {
+  int result = static_cast<int>(size /= sizeof(uint32));
+  if (result < kNumSizeEntries)
+    return result;
+  return 0;
+}
+
+// static
+inline size_t LeakDetectorImpl::IndexToSize(int index) {
+  return sizeof(uint32) * index;
+}
+
+LeakDetectorImpl::CallStack* LeakDetectorImpl::GetCallStack(
+    int depth, const void* const stack[]) {
+  // Temporarily create a call stack object for lookup in |call_stacks_|.
+  CallStack temp;
+  temp.depth = depth;
+  temp.stack = const_cast<const void**>(stack);
+
+  auto iter = call_stacks_.find(&temp);
+  if (iter != call_stacks_.end())
+    return *iter;
+
+  // Since |call_stacks_| stores CallStack pointers rather than actual objects,
+  // create new call objects manually here.
+  CallStack* new_call_stack = new(Alloc(sizeof(CallStack))) CallStack;
+  memset(new_call_stack, 0, sizeof(*new_call_stack));
+  new_call_stack->depth = depth;
+  new_call_stack->hash = call_stacks_.hash_function()(&temp);
+  new_call_stack->stack =
+      reinterpret_cast<const void**>(Alloc(sizeof(*stack) * depth));
+  std::copy(stack, stack + depth, new_call_stack->stack);
+
+  call_stacks_.insert(new_call_stack);
+  return new_call_stack;
+}
+
+uint64 LeakDetectorImpl::GetOffset(const void *ptr) const {
+  uint64 ptr_value = reinterpret_cast<uint64>(ptr);
+  if (ptr_value >= mapping_addr_ && ptr_value < mapping_addr_ + mapping_size_)
+    return ptr_value - mapping_addr_;
+  return ptr_value;
+}
+
+// static
+// Use FarmHash to hash a call stack.
+uint64 LeakDetectorImpl::CallStackToHash(const CallStack* call_stack) {
+  return util::Hash(reinterpret_cast<const char*>(call_stack->stack),
+                    sizeof(*(call_stack->stack)) * call_stack->depth);
+}
+
+}  // namespace leak_detector