components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/call_stack_table_unittest.cc

Index: components/metrics/leak_detector/call_stack_table_unittest.cc
diff --git a/components/metrics/leak_detector/call_stack_table_unittest.cc b/components/metrics/leak_detector/call_stack_table_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c455f37c7c9015845507c544cdb8388bbe6765c4
--- /dev/null
+++ b/components/metrics/leak_detector/call_stack_table_unittest.cc
@@ -0,0 +1,306 @@
+// 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/call_stack_table.h"
+
+#include <set>
+
+#include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
+#include "components/metrics/leak_detector/call_stack_manager.h"
+#include "components/metrics/leak_detector/custom_allocator.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace metrics {
+namespace leak_detector {
+
+namespace {
+
+// Default threshold used for leak analysis.
+const int kDefaultLeakThreshold = 5;
+
+// Some test call stacks.
+const void* kRawStack0[] = {
+    reinterpret_cast<const void*>(0xaabbccdd),
+    reinterpret_cast<const void*>(0x11223344),
+    reinterpret_cast<const void*>(0x55667788),
+    reinterpret_cast<const void*>(0x99887766),
+};
+const void* kRawStack1[] = {
+    reinterpret_cast<const void*>(0xdeadbeef),
+    reinterpret_cast<const void*>(0x900df00d),
+    reinterpret_cast<const void*>(0xcafedeed),
+    reinterpret_cast<const void*>(0xdeafbabe),
+};
+const void* kRawStack2[] = {
+    reinterpret_cast<const void*>(0x12345678),
+    reinterpret_cast<const void*>(0xabcdef01),
+    reinterpret_cast<const void*>(0xfdecab98),
+};
+const void* kRawStack3[] = {
+    reinterpret_cast<const void*>(0xdead0001),
+    reinterpret_cast<const void*>(0xbeef0002),
+    reinterpret_cast<const void*>(0x900d0003),
+    reinterpret_cast<const void*>(0xf00d0004),
+    reinterpret_cast<const void*>(0xcafe0005),
+    reinterpret_cast<const void*>(0xdeed0006),
+    reinterpret_cast<const void*>(0xdeaf0007),
+    reinterpret_cast<const void*>(0xbabe0008),
+};
+
+}  // namespace
+
+class CallStackTableTest : public ::testing::Test {
+ public:
+  CallStackTableTest()
+      : stack0_(nullptr),
+        stack1_(nullptr),
+        stack2_(nullptr),
+        stack3_(nullptr) {}
+
+  void SetUp() override {
+    CustomAllocator::Initialize();
+
+    manager_.reset(new CallStackManager);
+
+    // The unit tests expect a certain order to the call stack pointers. It is
+    // an important detail when checking the output of LeakAnalyzer's suspected
+    // leaks, which are ordered by the leak value (call stack pointer). Use a
+    // set to sort the pointers as they are created.
+    std::set<const CallStack*> stacks;
+    stacks.insert(manager_->GetCallStack(arraysize(kRawStack0), kRawStack0));
+    stacks.insert(manager_->GetCallStack(arraysize(kRawStack1), kRawStack1));
+    stacks.insert(manager_->GetCallStack(arraysize(kRawStack2), kRawStack2));
+    stacks.insert(manager_->GetCallStack(arraysize(kRawStack3), kRawStack3));
+    ASSERT_EQ(4U, stacks.size());
+
+    std::set<const CallStack*>::const_iterator iter = stacks.begin();
+    stack0_ = *iter++;
+    stack1_ = *iter++;
+    stack2_ = *iter++;
+    stack3_ = *iter++;
+  }
+
+  void TearDown() override {
+    // All call stacks generated by |manager_| will be invalidated when it is
+    // destroyed.
+    stack0_ = nullptr;
+    stack1_ = nullptr;
+    stack2_ = nullptr;
+    stack3_ = nullptr;
+
+    // Destroy the call stack manager before shutting down the allocator.
+    manager_.reset();
+
+    EXPECT_TRUE(CustomAllocator::Shutdown());
+  }
+
+ protected:
+  // Unit tests should directly reference these pointers to CallStack objects.
+  const CallStack* stack0_;
+  const CallStack* stack1_;
+  const CallStack* stack2_;
+  const CallStack* stack3_;
+
+ private:
+  scoped_ptr<CallStackManager> manager_;
+
+  DISALLOW_COPY_AND_ASSIGN(CallStackTableTest);
+};
+
+TEST_F(CallStackTableTest, PointerOrder) {
+  EXPECT_LT(stack0_, stack1_);
+  EXPECT_LT(stack1_, stack2_);
+  EXPECT_LT(stack2_, stack3_);
+}
+
+TEST_F(CallStackTableTest, EmptyTable) {
+  CallStackTable table(kDefaultLeakThreshold);
+  EXPECT_TRUE(table.empty());
+
+  EXPECT_EQ(0U, table.num_allocs());
+  EXPECT_EQ(0U, table.num_frees());
+
+  // The table should be able to gracefully handle an attempt to remove a call
+  // stack entry when none exists.
+  table.Remove(stack0_);
+  table.Remove(stack1_);
+  table.Remove(stack2_);
+  table.Remove(stack3_);
+
+  EXPECT_EQ(0U, table.num_allocs());
+  EXPECT_EQ(0U, table.num_frees());
+}
+
+TEST_F(CallStackTableTest, InsertionAndRemoval) {
+  CallStackTable table(kDefaultLeakThreshold);
+
+  table.Add(stack0_);
+  EXPECT_EQ(1U, table.size());
+  EXPECT_EQ(1U, table.num_allocs());
+  table.Add(stack1_);
+  EXPECT_EQ(2U, table.size());
+  EXPECT_EQ(2U, table.num_allocs());
+  table.Add(stack2_);
+  EXPECT_EQ(3U, table.size());
+  EXPECT_EQ(3U, table.num_allocs());
+  table.Add(stack3_);
+  EXPECT_EQ(4U, table.size());
+  EXPECT_EQ(4U, table.num_allocs());
+
+  // Add some call stacks that have already been added. There should be no
+  // change in the number of entries, as they are aggregated by call stack.
+  table.Add(stack2_);
+  EXPECT_EQ(4U, table.size());
+  EXPECT_EQ(5U, table.num_allocs());
+  table.Add(stack3_);
+  EXPECT_EQ(4U, table.size());
+  EXPECT_EQ(6U, table.num_allocs());
+
+  // Start removing entries.
+  EXPECT_EQ(0U, table.num_frees());
+
+  table.Remove(stack0_);
+  EXPECT_EQ(3U, table.size());
+  EXPECT_EQ(1U, table.num_frees());
+  table.Remove(stack1_);
+  EXPECT_EQ(2U, table.size());
+  EXPECT_EQ(2U, table.num_frees());
+
+  // Removing call stacks with multiple counts will not reduce the overall
+  // number of table entries, until the count reaches 0.
+  table.Remove(stack2_);
+  EXPECT_EQ(2U, table.size());
+  EXPECT_EQ(3U, table.num_frees());
+  table.Remove(stack3_);
+  EXPECT_EQ(2U, table.size());
+  EXPECT_EQ(4U, table.num_frees());
+
+  table.Remove(stack2_);
+  EXPECT_EQ(1U, table.size());
+  EXPECT_EQ(5U, table.num_frees());
+  table.Remove(stack3_);
+  EXPECT_EQ(0U, table.size());
+  EXPECT_EQ(6U, table.num_frees());
+
+  // Now the table should be empty, but attempt to remove some more and make
+  // sure nothing breaks.
+  table.Remove(stack0_);
+  table.Remove(stack1_);
+  table.Remove(stack2_);
+  table.Remove(stack3_);
+
+  EXPECT_TRUE(table.empty());
+  EXPECT_EQ(6U, table.num_allocs());
+  EXPECT_EQ(6U, table.num_frees());
+}
+
+TEST_F(CallStackTableTest, MassiveInsertionAndRemoval) {
+  CallStackTable table(kDefaultLeakThreshold);
+
+  for (int i = 0; i < 100; ++i)
+    table.Add(stack3_);
+  EXPECT_EQ(1U, table.size());
+  EXPECT_EQ(100U, table.num_allocs());
+
+  for (int i = 0; i < 100; ++i)
+    table.Add(stack2_);
+  EXPECT_EQ(2U, table.size());
+  EXPECT_EQ(200U, table.num_allocs());
+
+  for (int i = 0; i < 100; ++i)
+    table.Add(stack1_);
+  EXPECT_EQ(3U, table.size());
+  EXPECT_EQ(300U, table.num_allocs());
+
+  for (int i = 0; i < 100; ++i)
+    table.Add(stack0_);
+  EXPECT_EQ(4U, table.size());
+  EXPECT_EQ(400U, table.num_allocs());
+
+  // Remove them in a different order, by removing one of each stack during one
+  // iteration. The size should not decrease until the last iteration.
+  EXPECT_EQ(0U, table.num_frees());
+
+  for (int i = 0; i < 100; ++i) {
+    table.Remove(stack0_);
+    EXPECT_EQ(4U * i + 1, table.num_frees());
+
+    table.Remove(stack1_);
+    EXPECT_EQ(4U * i + 2, table.num_frees());
+
+    table.Remove(stack2_);
+    EXPECT_EQ(4U * i + 3, table.num_frees());
+
+    table.Remove(stack3_);
+    EXPECT_EQ(4U * i + 4, table.num_frees());
+  }
+  EXPECT_EQ(400U, table.num_frees());
+  EXPECT_TRUE(table.empty());
+
+  // Try to remove some more from an empty table and make sure nothing breaks.
+  table.Remove(stack0_);
+  table.Remove(stack1_);
+  table.Remove(stack2_);
+  table.Remove(stack3_);
+
+  EXPECT_TRUE(table.empty());
+  EXPECT_EQ(400U, table.num_allocs());
+  EXPECT_EQ(400U, table.num_frees());
+}
+
+TEST_F(CallStackTableTest, DetectLeak) {
+  CallStackTable table(kDefaultLeakThreshold);
+
+  // Add some base number of entries.
+  for (int i = 0; i < 60; ++i)
+    table.Add(stack0_);
+  for (int i = 0; i < 50; ++i)
+    table.Add(stack1_);
+  for (int i = 0; i < 64; ++i)
+    table.Add(stack2_);
+  for (int i = 0; i < 72; ++i)
+    table.Add(stack3_);
+
+  table.TestForLeaks();
+  EXPECT_TRUE(table.leak_analyzer().suspected_leaks().empty());
+
+  // Use the following scheme:
+  // - stack0_: increase by 4 each time -- leak suspect
+  // - stack1_: increase by 3 each time -- leak suspect
+  // - stack2_: increase by 1 each time -- not a suspect
+  // - stack3_: alternate between increasing and decreasing - not a suspect
+  bool increase_kstack3 = true;
+  for (int i = 0; i < kDefaultLeakThreshold; ++i) {
+    EXPECT_TRUE(table.leak_analyzer().suspected_leaks().empty());
+
+    for (int j = 0; j < 4; ++j)
+      table.Add(stack0_);
+
+    for (int j = 0; j < 3; ++j)
+      table.Add(stack1_);
+
+    table.Add(stack2_);
+
+    // Alternate between adding and removing.
+    if (increase_kstack3)
+      table.Add(stack3_);
+    else
+      table.Remove(stack3_);
+    increase_kstack3 = !increase_kstack3;
+
+    table.TestForLeaks();
+  }
+
+  // Check that the correct leak values have been detected.
+  const auto& leaks = table.leak_analyzer().suspected_leaks();
+  ASSERT_EQ(2U, leaks.size());
+  // Suspected leaks are reported in increasing leak value -- in this case, the
+  // CallStack object's address.
+  EXPECT_EQ(stack0_, leaks[0].call_stack());
+  EXPECT_EQ(stack1_, leaks[1].call_stack());
+}
+
+}  // namespace leak_detector
+}  // namespace metrics