components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/leak_detector_impl_unittest.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_detector_impl.h"
+
+#include <math.h>
+#include <stdint.h>
+
+#include <complex>
+#include <new>
+#include <set>
+#include <vector>
+
+#include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
+#include "components/metrics/leak_detector/custom_allocator.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace metrics {
+namespace leak_detector {
+
+namespace {
+
+// Makes working with complex numbers easier.
+using Complex = std::complex<double>;
+
+// The mapping location in memory for a fictional executable.
+const uintptr_t kMappingAddr = 0x800000;
+const size_t kMappingSize = 0x200000;
+
+// Some call stacks within the fictional executable.
+// * - outside the mapping range, e.g. JIT code.
+const uintptr_t kRawStack0[] = {
+  0x800100,
+  0x900000,
+  0x880080,
+  0x810000,
+};
+const uintptr_t kRawStack1[] = {
+  0x940000,
+  0x980000,
+  0xdeadbeef,  // *
+  0x9a0000,
+};
+const uintptr_t kRawStack2[] = {
+  0x8f0d00,
+  0x803abc,
+  0x9100a0,
+};
+const uintptr_t kRawStack3[] = {
+  0x90fcde,
+  0x900df00d,  // *
+  0x801000,
+  0x880088,
+  0xdeadcafe,  // *
+  0x9f0000,
+  0x8700a0,
+  0x96037c,
+};
+const uintptr_t kRawStack4[] = {
+  0x8c0000,
+  0x85d00d,
+  0x921337,
+  0x780000,  // *
+};
+const uintptr_t kRawStack5[] = {
+  0x990000,
+  0x888888,
+  0x830ac0,
+  0x8e0000,
+  0xc00000,  // *
+};
+
+// This struct makes it easier to pass call stack info to
+// LeakDetectorImplTest::Alloc().
+struct TestCallStack {
+  const uintptr_t* stack;  // A reference to the original stack data.
+  size_t depth;
+};
+
+const TestCallStack kStack0 = { kRawStack0, arraysize(kRawStack0) };
+const TestCallStack kStack1 = { kRawStack1, arraysize(kRawStack1) };
+const TestCallStack kStack2 = { kRawStack2, arraysize(kRawStack2) };
+const TestCallStack kStack3 = { kRawStack3, arraysize(kRawStack3) };
+const TestCallStack kStack4 = { kRawStack4, arraysize(kRawStack4) };
+const TestCallStack kStack5 = { kRawStack5, arraysize(kRawStack5) };
+
+// The interval between consecutive analyses (LeakDetectorImpl::TestForLeaks),
+// in number of bytes allocated. e.g. if |kAllocedSizeAnalysisInterval| = 1024
+// then call TestForLeaks() every 1024 bytes of allocation that occur.
+static const size_t kAllocedSizeAnalysisInterval = 8192;
+
+}  // namespace
+
+// This test suite will test the ability of LeakDetectorImpl to catch leaks in
+// a program. Individual tests can run leaky code locally.
+//
+// The leaky code must call Alloc() and Free() for heap memory management. It
+// should not call See comments on those
+// functions for more details.
+class LeakDetectorImplTest : public ::testing::Test {
+ public:
+  LeakDetectorImplTest()
+      : total_num_allocs_(0),
+        total_num_frees_(0),
+        total_alloced_size_(0),
+        next_analysis_total_alloced_size_(kAllocedSizeAnalysisInterval) {}
+
+  void SetUp() override {
+    CustomAllocator::Initialize();
+
+    const int kSizeSuspicionThreshold = 4;
+    const int kCallStackSuspicionThreshold = 4;
+    detector_.reset(new LeakDetectorImpl(kMappingAddr,
+                                         kMappingSize,
+                                         kSizeSuspicionThreshold,
+                                         kCallStackSuspicionThreshold));
+  }
+
+  void TearDown() override {
+    // Free any memory that was leaked by test cases. Do not use Free() because
+    // that will try to modify |alloced_ptrs_|.
+    for (void* ptr : alloced_ptrs_)
+      delete [] reinterpret_cast<char*>(ptr);
+    alloced_ptrs_.clear();
+
+    // Must destroy all objects that use CustomAllocator before shutting down.
+    detector_.reset();
+    stored_reports_.clear();
+
+    EXPECT_TRUE(CustomAllocator::Shutdown());
+  }
+
+ protected:
+  // Alloc and free functions that allocate and free heap memory and
+  // automatically pass alloc/free info to |detector_|. They emulate the
+  // alloc/free hook functions that would call into LeakDetectorImpl in
+  // real-life usage. They also keep track of individual allocations locally, so
+  // any leaked memory could be cleaned up.
+  //
+  // |stack| is just a nominal call stack object to identify the call site. It
+  // doesn't have to contain the stack trace of the actual call stack.
+  void* Alloc(size_t size, const TestCallStack& stack) {
+    void* ptr = new char[size];
+    detector_->RecordAlloc(ptr, size, stack.depth,
+                           reinterpret_cast<const void* const*>(stack.stack));
+
+    EXPECT_TRUE(alloced_ptrs_.find(ptr) == alloced_ptrs_.end());
+    alloced_ptrs_.insert(ptr);
+
+    ++total_num_allocs_;
+    total_alloced_size_ += size;
+    if (total_alloced_size_ >= next_analysis_total_alloced_size_) {
+      InternalVector<InternalLeakReport> reports;
+      detector_->TestForLeaks(&reports);
+      for (const InternalLeakReport& report : reports)
+        stored_reports_.insert(report);
+
+      // Determine when the next leak analysis should occur.
+      while (total_alloced_size_ >= next_analysis_total_alloced_size_)
+        next_analysis_total_alloced_size_ += kAllocedSizeAnalysisInterval;
+    }
+    return ptr;
+  }
+
+  // See comment for Alloc().
+  void Free(void* ptr) {
+    auto find_ptr_iter = alloced_ptrs_.find(ptr);
+    EXPECT_FALSE(find_ptr_iter == alloced_ptrs_.end());
+    if (find_ptr_iter == alloced_ptrs_.end())
+      return;
+    alloced_ptrs_.erase(find_ptr_iter);
+    ++total_num_frees_;
+
+    detector_->RecordFree(ptr);
+
+    delete [] reinterpret_cast<char*>(ptr);
+  }
+
+  // TEST CASE: Julia set fractal computation. Pass in enable_leaks=true to
+  // trigger some memory leaks.
+  void JuliaSet(bool enable_leaks);
+
+  // Instance of the class being tested.
+  scoped_ptr<LeakDetectorImpl> detector_;
+
+  // Number of pointers allocated and freed so far.
+  size_t total_num_allocs_;
+  size_t total_num_frees_;
+
+  // Keeps count of total size allocated by Alloc().
+  size_t total_alloced_size_;
+
+  // The cumulative allocation size at which to trigger the TestForLeaks() call.
+  size_t next_analysis_total_alloced_size_;
+
+  // Stores all pointers to memory allocated by by Alloc() so we can manually
+  // free the leaked pointers at the end. This also serves as redundant
+  // bookkeepping: it stores all pointers that have been allocated but not yet
+  // freed.
+  std::set<void*> alloced_ptrs_;
+
+  // Store leak reports here. Use a set so duplicate reports are not stored.
+  std::set<InternalLeakReport> stored_reports_;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LeakDetectorImplTest);
+};
+
+void LeakDetectorImplTest::JuliaSet(bool enable_leaks) {
+  // The center region of the complex plane that is the basis for our Julia set

[jar (doing other things), 2015/11/14 02:58:37]

I was amazed/surprised to see code working with Complex numbers.  What is the
point of this?

Please motivate this code.  This sure looks to be adding more complexity than is
desirable in a unit test.

[Simon Que, 2015/11/17 00:28:48]

I tried to come up with a self-contained program that does something other than
purposefully leak memory. This is to simulate a real-life leak scenario where
the developer is leaking in a not-so-obvious way -- there are several alloc
sites but not all of them are leaky, which simulates accidentally forgetting to
free at one site.

This code is not intended to be modified going forward except to fix bugs or
optimize for performance. If we were to add new functionality to
LeakDetectorImpl (e.g. false positive detection) in the future, we should write
a new piece of test code that has exactly that scenario, rather than adding some
false positive pattern to the JuliaSet code.

That said, I do think this function is too long. I don't know how to reduce it
significantly, except for choosing a lower value of |n| for the Julia Set
function. But that would result in fewer call sites... I'm trying to keep more
than one of both leaky and non-leaky call sites, currently 2 and 3 respectively.

+  // computations is a circle of radius kRadius.
+  constexpr double kRadius = 2;
+
+  // To track points in the complex plane, we will use a rectangular grid in the
+  // range defined by [-kRadius, kRadius] along both axes.
+  constexpr double kRangeMin = -kRadius;
+  constexpr double kRangeMax = kRadius;
+
+  // Divide each axis into intervals, each of which is associated with a point
+  // on that axis at its center.
+  constexpr double kIntervalInverse = 64;
+  constexpr double kInterval = 1.0 / kIntervalInverse;
+  constexpr int kNumPoints = (kRangeMax - kRangeMin) / kInterval + 1;
+
+  // Contains some useful functions for converting between points on the complex
+  // plane and in a gridlike data structure.
+  struct ComplexPlane {
+    static int GetXGridIndex(const Complex& value) {
+      return (value.real() + kInterval / 2 - kRangeMin) / kInterval;
+    }
+    static int GetYGridIndex(const Complex& value) {
+      return (value.imag() + kInterval / 2 - kRangeMin) / kInterval;
+    }
+    static Complex GetComplexForGridPoint(size_t x, size_t y) {
+      return Complex(kRangeMin + x * kInterval, kRangeMin + y * kInterval);
+    }
+  };
+
+  // Make sure the choice of interval doesn't result in any loss of precision.
+  ASSERT_EQ(1.0, kInterval * kIntervalInverse);
+
+  // Create a grid for part of the complex plane, with each axis within the
+  // range [kRangeMin, kRangeMax].
+  constexpr size_t width = kNumPoints;
+  constexpr size_t height = kNumPoints;
+  std::vector<Complex*> grid(width * height);
+
+  // Initialize an object for each point within the inner circle |z| < kRadius.
+  for (size_t i = 0; i < width; ++i) {
+    for (size_t j = 0; j < height; ++j) {
+      Complex point = ComplexPlane::GetComplexForGridPoint(i, j);
+      // Do not store any values outside the inner circle.
+      if (abs(point) <= kRadius) {
+        grid[i + j * width] =
+            new(Alloc(sizeof(Complex), kStack0)) Complex(point);
+      }
+    }
+  }
+  EXPECT_LE(alloced_ptrs_.size(), width * height);
+
+  // Create a new grid for the result of the transformation.
+  std::vector<Complex*> next_grid(width * height, nullptr);
+
+  const int kNumIterations = 20;
+  for (int n = 0; n < kNumIterations; ++n) {
+    for (int i = 0; i < kNumPoints; ++i) {
+      for (int j = 0; j < kNumPoints; ++j) {
+        if (!grid[i + j * width])
+          continue;
+
+        // NOTE: The below code is NOT an efficient way to compute a Julia set.
+        // This is only to test the leak detector with some nontrivial code.
+
+        // A simple polynomial function for generating Julia sets is:
+        //   f(z) = z^n + c
+
+        // But in this algorithm, we need the inverse:
+        //   fInv(z) = (z - c)^(1/n)
+
+        // Here, let's use n=5 and c=0.544.
+        const Complex c(0.544, 0);
+        const Complex& z = *grid[i + j * width];
+
+        // This is the principal root.
+        Complex root = pow(z - c, 0.2);
+
+        // Discard the result if it is too far out from the center of the plane.
+        if (abs(root) > kRadius)
+          continue;
+
+        // The below code only allocates Complex objects of the same size. The
+        // leak detector expects various sizes, so increase the allocation size
+        // by a different amount at each call site.
+
+        // Nth root produces N results.
+        // Place all root results on |next_grid|.
+
+        // First, place the principal root.
+        int next_i = ComplexPlane::GetXGridIndex(root);
+        int next_j = ComplexPlane::GetYGridIndex(root);
+        if (!next_grid[next_i + next_j * width]) {
+          next_grid[next_i + next_j * width] =
+              new(Alloc(sizeof(Complex) + 24, kStack1)) Complex(root);
+        }
+
+        double magnitude = abs(root);
+        double angle = arg(root);
+        // To generate other roots, rotate the principal root by increments of
+        // 1/N of a full circle.
+        const double kAngleIncrement = M_PI * 2 / 5;
+
+        // Second root.
+        root = std::polar(magnitude, angle + kAngleIncrement);
+        next_i = ComplexPlane::GetXGridIndex(root);
+        next_j = ComplexPlane::GetYGridIndex(root);
+        if (!next_grid[next_i + next_j * width]) {
+          next_grid[next_i + next_j * width] =
+              new(Alloc(sizeof(Complex) + 40, kStack2)) Complex(root);
+        }
+
+        // In some of the sections below, setting |enable_leaks| to true will
+        // trigger a memory leak by overwriting the old Complex pointer value
+        // without freeing it. Due to the nature of complex roots being confined
+        // to equal sections of the complex plane, each new pointer will
+        // displace an old pointer that was allocated from the same line of
+        // code.
+
+        // Third root.
+        root = std::polar(magnitude, angle + kAngleIncrement * 2);
+        next_i = ComplexPlane::GetXGridIndex(root);
+        next_j = ComplexPlane::GetYGridIndex(root);
+        // *** LEAK ***
+        if (enable_leaks || !next_grid[next_i + next_j * width]) {
+          next_grid[next_i + next_j * width] =
+              new(Alloc(sizeof(Complex) + 40, kStack3)) Complex(root);
+        }
+
+        // Fourth root.
+        root = std::polar(magnitude, angle + kAngleIncrement * 3);
+        next_i = ComplexPlane::GetXGridIndex(root);
+        next_j = ComplexPlane::GetYGridIndex(root);
+        // *** LEAK ***
+        if (enable_leaks || !next_grid[next_i + next_j * width]) {
+          next_grid[next_i + next_j * width] =
+              new(Alloc(sizeof(Complex) + 52, kStack4)) Complex(root);
+        }
+
+        // Fifth root.
+        root = std::polar(magnitude, angle + kAngleIncrement * 4);
+        next_i = ComplexPlane::GetXGridIndex(root);
+        next_j = ComplexPlane::GetYGridIndex(root);
+        if (!next_grid[next_i + next_j * width]) {
+          next_grid[next_i + next_j * width] =
+              new(Alloc(sizeof(Complex) + 52, kStack5)) Complex(root);
+        }
+      }
+    }
+
+    // Clear the previously allocated points.
+    for (Complex*& point : grid) {
+      if (point) {
+        Free(point);
+        point = nullptr;
+      }
+    }
+
+    // Now swap the two grids for the next iteration.
+    grid.swap(next_grid);
+  }
+
+  // Clear the previously allocated points.
+  for (Complex*& point : grid) {
+    if (point) {
+      Free(point);
+      point = nullptr;
+    }
+  }
+}
+
+TEST_F(LeakDetectorImplTest, CheckTestFramework) {
+  EXPECT_EQ(0U, total_num_allocs_);
+  EXPECT_EQ(0U, total_num_frees_);
+  EXPECT_EQ(0U, alloced_ptrs_.size());
+
+  // Allocate some memory.
+  void* ptr0 = Alloc(12, kStack0);
+  void* ptr1 = Alloc(16, kStack0);
+  void* ptr2 = Alloc(24, kStack0);
+  EXPECT_EQ(3U, total_num_allocs_);
+  EXPECT_EQ(0U, total_num_frees_);
+  EXPECT_EQ(3U, alloced_ptrs_.size());
+
+  // Free one of the pointers.
+  Free(ptr1);
+  EXPECT_EQ(3U, total_num_allocs_);
+  EXPECT_EQ(1U, total_num_frees_);
+  EXPECT_EQ(2U, alloced_ptrs_.size());
+
+  // Allocate some more memory.
+  void* ptr3 = Alloc(72, kStack1);
+  void* ptr4 = Alloc(104, kStack1);
+  void* ptr5 = Alloc(96, kStack1);
+  void* ptr6 = Alloc(24, kStack1);
+  EXPECT_EQ(7U, total_num_allocs_);
+  EXPECT_EQ(1U, total_num_frees_);
+  EXPECT_EQ(6U, alloced_ptrs_.size());
+
+  // Free more pointers.
+  Free(ptr2);
+  Free(ptr4);
+  Free(ptr6);
+  EXPECT_EQ(7U, total_num_allocs_);
+  EXPECT_EQ(4U, total_num_frees_);
+  EXPECT_EQ(3U, alloced_ptrs_.size());
+
+  // Free remaining memory.
+  Free(ptr0);
+  Free(ptr3);
+  Free(ptr5);
+  EXPECT_EQ(7U, total_num_allocs_);
+  EXPECT_EQ(7U, total_num_frees_);
+  EXPECT_EQ(0U, alloced_ptrs_.size());
+}
+
+TEST_F(LeakDetectorImplTest, JuliaSetNoLeak) {
+  JuliaSet(false /* enable_leaks */);
+
+  // JuliaSet() should have run cleanly without leaking.
+  EXPECT_EQ(total_num_allocs_, total_num_frees_);
+  EXPECT_EQ(0U, alloced_ptrs_.size());
+  ASSERT_EQ(0U, stored_reports_.size());
+}
+
+TEST_F(LeakDetectorImplTest, JuliaSetWithLeak) {
+  JuliaSet(true /* enable_leaks */);
+
+  // JuliaSet() should have leaked some memory from two call sites.
+  EXPECT_GT(total_num_allocs_, total_num_frees_);
+  EXPECT_GT(alloced_ptrs_.size(), 0U);
+
+  // There should be one unique leak report generated for each leaky call site.
+  ASSERT_EQ(2U, stored_reports_.size());
+
+  // The reports should be stored in order of size.
+
+  // |report1| comes from the call site in JuliaSet() corresponding to
+  // |kStack3|.
+  const InternalLeakReport& report1 = *stored_reports_.begin();
+  EXPECT_EQ(sizeof(Complex) + 40, report1.alloc_size_bytes);
+  EXPECT_EQ(kStack3.depth, report1.call_stack.size());
+  for (size_t i = 0; i < kStack3.depth && i < report1.call_stack.size(); ++i) {
+    // The call stack's addresses may not fall within the mapping address.
+    // Those that don't will not be converted to mapping offsets.
+    if (kStack3.stack[i] >= kMappingAddr &&
+        kStack3.stack[i] <= kMappingAddr + kMappingSize) {
+      EXPECT_EQ(kStack3.stack[i] - kMappingAddr, report1.call_stack[i]);
+    } else {
+      EXPECT_EQ(kStack3.stack[i], report1.call_stack[i]);
+    }
+  }
+
+  // |report2| comes from the call site in JuliaSet() corresponding to
+  // |kStack4|.
+  const InternalLeakReport& report2 = *(++stored_reports_.begin());
+  EXPECT_EQ(sizeof(Complex) + 52, report2.alloc_size_bytes);
+  EXPECT_EQ(kStack4.depth, report2.call_stack.size());
+  for (size_t i = 0; i < kStack4.depth && i < report2.call_stack.size(); ++i) {
+    // The call stack's addresses may not fall within the mapping address.
+    // Those that don't will not be converted to mapping offsets.
+    if (kStack4.stack[i] >= kMappingAddr &&
+        kStack4.stack[i] <= kMappingAddr + kMappingSize) {
+      EXPECT_EQ(kStack4.stack[i] - kMappingAddr, report2.call_stack[i]);
+    } else {
+      EXPECT_EQ(kStack4.stack[i], report2.call_stack[i]);
+    }
+  }
+}
+
+}  // namespace leak_detector
+}  // namespace metrics