components/metrics: Add runtime memory leak detector

components/metrics/leak_detector/call_stack_manager_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/call_stack_manager.h"
+
+#include <stdint.h>
+
+#include <algorithm>
+
+#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 {
+
+// Some test call stacks. The addresses are 64-bit but they should automatically
+// be truncated to 32 bits on a 32-bit machine.
+const void* kRawStack0[] = {
+  reinterpret_cast<const void*>(0x8899aabbccddeeff),
+  reinterpret_cast<const void*>(0x0000112233445566),
+  reinterpret_cast<const void*>(0x5566778899aabbcc),
+  reinterpret_cast<const void*>(0x9988776655443322),
+};
+// This is similar to kRawStack0, differing only in one address by 1. It should
+// still produce a distinct CallStack object and hash.
+const void* kRawStack1[] = {
+  kRawStack0[0],
+  kRawStack0[1],
+  reinterpret_cast<const void*>(
+      reinterpret_cast<uintptr_t>(kRawStack0[2]) + 1),
+  kRawStack0[3],
+};
+const void* kRawStack2[] = {
+  reinterpret_cast<const void*>(0x900df00dcab58888),
+  reinterpret_cast<const void*>(0x00001337cafedeed),
+  reinterpret_cast<const void*>(0x0000deafbabe1234),
+};
+const void* kRawStack3[] = {
+  reinterpret_cast<const void*>(0x0000000012345678),
+  reinterpret_cast<const void*>(0x00000000abcdef01),
+  reinterpret_cast<const void*>(0x00000000fdecab98),
+  reinterpret_cast<const void*>(0x0000deadbeef0001),
+  reinterpret_cast<const void*>(0x0000900ddeed0002),
+  reinterpret_cast<const void*>(0x0000f00dcafe0003),
+  reinterpret_cast<const void*>(0x0000f00d900d0004),
+  reinterpret_cast<const void*>(0xdeedcafebabe0005),
+};
+
+// Creates a copy of a call stack as a scoped_ptr to a raw stack. The depth is
+// the same as the original stack, but it is not stored in the result.
+scoped_ptr<const void*[]> CopyStack(const CallStack* stack) {
+  scoped_ptr<const void*[]> stack_copy(new const void*[stack->depth]);
+  std::copy(stack->stack, stack->stack + stack->depth, stack_copy.get());
+  return stack_copy.Pass();
+}
+
+}  // namespace
+
+class CallStackManagerTest : public ::testing::Test {
+ public:
+  CallStackManagerTest() {}
+
+  void SetUp() override {
+    CustomAllocator::Initialize();
+  }
+  void TearDown() override {
+    EXPECT_TRUE(CustomAllocator::Shutdown());
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(CallStackManagerTest);
+};
+
+TEST_F(CallStackManagerTest, NewStacks) {
+  CallStackManager manager;
+  EXPECT_EQ(0U, manager.size());
+
+  // Request some new stacks and make sure their creation is reflected in the
+  // size of |manager|.
+  const CallStack* stack0 =
+      manager.GetCallStack(arraysize(kRawStack0), kRawStack0);
+  EXPECT_EQ(arraysize(kRawStack0), stack0->depth);
+  EXPECT_EQ(1U, manager.size());
+
+  const CallStack* stack1 =
+      manager.GetCallStack(arraysize(kRawStack1), kRawStack1);
+  EXPECT_EQ(arraysize(kRawStack1), stack1->depth);
+  EXPECT_EQ(2U, manager.size());
+
+  const CallStack* stack2 =
+      manager.GetCallStack(arraysize(kRawStack2), kRawStack2);
+  EXPECT_EQ(arraysize(kRawStack2), stack2->depth);
+  EXPECT_EQ(3U, manager.size());
+
+  const CallStack* stack3 =
+      manager.GetCallStack(arraysize(kRawStack3), kRawStack3);
+  EXPECT_EQ(arraysize(kRawStack3), stack3->depth);
+  EXPECT_EQ(4U, manager.size());
+
+  // Call stack objects should be unique.
+  EXPECT_NE(stack0, stack1);
+  EXPECT_NE(stack0, stack2);
+  EXPECT_NE(stack0, stack3);
+  EXPECT_NE(stack1, stack2);
+  EXPECT_NE(stack1, stack3);
+  EXPECT_NE(stack2, stack3);
+}
+
+TEST_F(CallStackManagerTest, Hashes) {
+  CallStackManager manager;
+
+  const CallStack* stack0 =
+      manager.GetCallStack(arraysize(kRawStack0), kRawStack0);
+  const CallStack* stack1 =
+      manager.GetCallStack(arraysize(kRawStack1), kRawStack1);
+  const CallStack* stack2 =
+      manager.GetCallStack(arraysize(kRawStack2), kRawStack2);
+  const CallStack* stack3 =
+      manager.GetCallStack(arraysize(kRawStack3), kRawStack3);
+
+  // Hash values should be nonzero.
+  EXPECT_NE(0U, stack0->hash);

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

The hash function doesn't guarantee non-zero return (I think).

What you can always assume is that with enough differences in the data, that the
hash will be different from any given constant.  To do this, you typically
iterate until you get a "different hash" and then declare victory.  It is
probably too much of a hasssle to try to validate the quality of the hash
function... but I think you are agreeing with your tests... and just want to
make suer the dependency is on the data you meant to depend upon.

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

Yes. The assumption here is that the test call stacks I've chosen all have
nonzero hashes. But thinking about it some more, these checks aren't that
useful.

+  EXPECT_NE(0U, stack1->hash);
+  EXPECT_NE(0U, stack2->hash);
+  EXPECT_NE(0U, stack3->hash);
+
+  // Hash values should be unique.
+  EXPECT_NE(stack0->hash, stack1->hash);

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

The hash function doesn't guarantee that you won't have colisions.

What you can check is that the hash of the same stack does produce the same hash
in two distinct CallStackManagers.

You can also test that *eventually* (if you try enough stacks!) that you'll get
different hashes.

The code, as written, seems brittle, relative to the definition of the
base::Hash function.

It is probably not the end of the world... but uninitialized memory would be
enough to (usually) pass this test.

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

This test is not designed to make sure the hash function is generating unique
hashes, but that the CallStackManager is properly storing the hashes in
CallStack structs.

If there is a collision, then I should be choosing different sets of raw call
stacks that will generate unique hashes.

I've added a test to check for same hashes from different CallStackMgrs.

+  EXPECT_NE(stack0->hash, stack2->hash);
+  EXPECT_NE(stack0->hash, stack3->hash);
+  EXPECT_NE(stack1->hash, stack2->hash);
+  EXPECT_NE(stack1->hash, stack3->hash);
+  EXPECT_NE(stack2->hash, stack3->hash);
+}
+
+TEST_F(CallStackManagerTest, HashWithReducedDepth) {
+  CallStackManager manager;
+  const CallStack* stack =
+      manager.GetCallStack(arraysize(kRawStack3), kRawStack3);
+
+  // Hash function should only operate on the first |CallStack::depth| elements
+  // of CallStack::stack. To test this, reduce the depth value of one of the
+  // stacks and make sure the hash changes.
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 1, stack->stack)->hash);

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

Again, this test seems backwards, as hash collisions are never precluded.  

I think you *can* test to see that the hash remains constant (i.e., a constant
function of the data you *expect* it to hash), when you modify the element
beyond |depth|.  

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

See comment above.

+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 2, stack->stack)->hash);
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 3, stack->stack)->hash);
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 4, stack->stack)->hash);
+
+  // Also try subsets of the stack that don't start from the beginning.
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 1, stack->stack + 1)->hash);
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 2, stack->stack + 2)->hash);
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 3, stack->stack + 3)->hash);
+  EXPECT_NE(stack->hash,
+            manager.GetCallStack(stack->depth - 4, stack->stack + 4)->hash);
+}
+
+TEST_F(CallStackManagerTest, DuplicateStacks) {
+  CallStackManager manager;
+  EXPECT_EQ(0U, manager.size());
+
+  // Calling manager.GetCallStack() multiple times with the same raw stack
+  // arguments will not result in creation of new call stack objects after the
+  // first call. Instead, the previously created object will be returned, and
+  // the size of |manager| will remain unchanged.
+  //
+  // Thus a call to GetCallStack() will always return the same result, given the
+  // same inputs.
+
+  // Add stack0.
+  const CallStack* stack0 =
+      manager.GetCallStack(arraysize(kRawStack0), kRawStack0);
+
+  scoped_ptr<const void*[]> rawstack0_duplicate0 = CopyStack(stack0);
+  const CallStack* stack0_duplicate0 =
+      manager.GetCallStack(arraysize(kRawStack0), rawstack0_duplicate0.get());
+  EXPECT_EQ(1U, manager.size());
+  EXPECT_EQ(stack0, stack0_duplicate0);
+
+  // Add stack1.
+  const CallStack* stack1 =
+      manager.GetCallStack(arraysize(kRawStack1), kRawStack1);
+  EXPECT_EQ(2U, manager.size());
+
+  scoped_ptr<const void*[]> rawstack0_duplicate1 = CopyStack(stack0);
+  const CallStack* stack0_duplicate1 =
+      manager.GetCallStack(arraysize(kRawStack0), rawstack0_duplicate1.get());
+  EXPECT_EQ(2U, manager.size());
+  EXPECT_EQ(stack0, stack0_duplicate1);
+
+  scoped_ptr<const void*[]> rawstack1_duplicate0 = CopyStack(stack1);
+  const CallStack* stack1_duplicate0 =
+      manager.GetCallStack(arraysize(kRawStack1), rawstack1_duplicate0.get());
+  EXPECT_EQ(2U, manager.size());
+  EXPECT_EQ(stack1, stack1_duplicate0);
+
+  // Add stack2 and stack3.
+  const CallStack* stack2 =
+      manager.GetCallStack(arraysize(kRawStack2), kRawStack2);
+  const CallStack* stack3 =
+      manager.GetCallStack(arraysize(kRawStack3), kRawStack3);
+  EXPECT_EQ(4U, manager.size());
+
+  scoped_ptr<const void*[]> rawstack1_duplicate1 = CopyStack(stack1);
+  const CallStack* stack1_duplicate1 =
+      manager.GetCallStack(arraysize(kRawStack1), rawstack1_duplicate1.get());
+  EXPECT_EQ(4U, manager.size());
+  EXPECT_EQ(stack1, stack1_duplicate1);
+
+  scoped_ptr<const void*[]> rawstack0_duplicate2 = CopyStack(stack0);
+  const CallStack* stack0_duplicate2 =
+      manager.GetCallStack(arraysize(kRawStack0), rawstack0_duplicate2.get());
+  EXPECT_EQ(4U, manager.size());
+  EXPECT_EQ(stack0, stack0_duplicate2);
+
+  scoped_ptr<const void*[]> rawstack3_duplicate0 = CopyStack(stack3);
+  const CallStack* stack3_duplicate0 =
+      manager.GetCallStack(arraysize(kRawStack3), rawstack3_duplicate0.get());
+  EXPECT_EQ(4U, manager.size());
+  EXPECT_EQ(stack3, stack3_duplicate0);
+
+  scoped_ptr<const void*[]> rawstack2_duplicate0 = CopyStack(stack2);
+  const CallStack* stack2_duplicate0 =
+      manager.GetCallStack(arraysize(kRawStack2), rawstack2_duplicate0.get());
+  EXPECT_EQ(4U, manager.size());
+  EXPECT_EQ(stack2, stack2_duplicate0);
+}
+
+}  // namespace leak_detector
+}  // namespace metrics