[Tracing] Add allocation register for heap profiling

base/trace_event/memory_profiler_allocation_register_unittest.cc

Index: base/trace_event/memory_profiler_allocation_register_unittest.cc
diff --git a/base/trace_event/memory_profiler_allocation_register_unittest.cc b/base/trace_event/memory_profiler_allocation_register_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..eb7e83387845fc65f783e4be6dc6a28217c51c16
--- /dev/null
+++ b/base/trace_event/memory_profiler_allocation_register_unittest.cc
@@ -0,0 +1,229 @@
+// 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 "base/trace_event/memory_profiler_allocation_register.h"
+
+#include "base/process/process_metrics.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace base {
+namespace trace_event {
+
+class AllocationRegisterTest : public testing::Test {
+ public:
+  // Returns the number of cells that the |AllocationlessHashTable| in the
+  // |AllocationRegister| can store per system page.
+  size_t GetNumCellsPerPage() {
+    return GetPageSize() / sizeof(AllocationRegister::Cell);
+  }
+
+  uint32_t GetTableSize(const AllocationRegister& reg) {

[Primiano Tucci (use gerrit), 2015/10/06 13:34:45]

Uh? Aren't this static constants. How is this different from
AllocationRegister::kNumBuckets?

If this is just for getting around the protection (AllocationRegister is friend,
the TEST_F are not) just re-define them using "using" in this class and
everything should work.

I mean:
class ALlocationRegisterTest ... {
using kNumBuckets = AllocationRegister::kNumBuckets;

..
}

TEST_F(ALlocationRegisterTest, Foo)
{
bla = kNumBuckets;
}

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+    return reg.kNumBuckets;
+  }
+
+  uint32_t GetNumCells(const AllocationRegister& reg) { return reg.kNumCells; }

[Primiano Tucci (use gerrit), 2015/10/06 13:34:45]

ditto here

[Ruud van Asseldonk, 2015/10/06 15:44:35]

Done.

+
+  uint32_t GetHighWaterMark(const AllocationRegister& reg) {
+    return reg.next_unused_cell_;
+  }
+};
+
+// Iterates over all entries in the allocation register and returns the bitwise
+// or of all addresses stored in it.
+uintptr_t OrAllAddresses(const AllocationRegister& reg) {
+  uintptr_t acc = 0;
+
+  for (auto i : reg)
+    acc |= reinterpret_cast<uintptr_t>(i.address);
+
+  return acc;
+}
+
+// Iterates over all entries in the allocation register and returns the sum of
+// the sizes of the entries.
+size_t SumAllSizes(const AllocationRegister& reg) {
+  size_t sum = 0;
+
+  for (auto i : reg)
+    sum += i.size;
+
+  return sum;
+}
+
+TEST_F(AllocationRegisterTest, InsertRemoveKeys) {
+  AllocationRegister reg;
+  AllocationContext ctx;
+
+  EXPECT_EQ(0u, OrAllAddresses(reg));
+
+  reg.Insert(reinterpret_cast<void*>(1), 0, ctx);
+
+  EXPECT_EQ(1u, OrAllAddresses(reg));
+
+  reg.Insert(reinterpret_cast<void*>(2), 0, ctx);
+
+  EXPECT_EQ(3u, OrAllAddresses(reg));
+
+  reg.Insert(reinterpret_cast<void*>(4), 0, ctx);
+
+  EXPECT_EQ(7u, OrAllAddresses(reg));
+
+  reg.Remove(reinterpret_cast<void*>(2));
+
+  EXPECT_EQ(5u, OrAllAddresses(reg));
+
+  reg.Remove(reinterpret_cast<void*>(4));
+
+  EXPECT_EQ(1u, OrAllAddresses(reg));
+
+  reg.Remove(reinterpret_cast<void*>(1));
+
+  EXPECT_EQ(0u, OrAllAddresses(reg));
+}
+
+TEST_F(AllocationRegisterTest, DoubleFreeIsAllowed) {
+  AllocationRegister reg;
+  AllocationContext ctx;
+
+  reg.Insert(reinterpret_cast<void*>(1), 0, ctx);
+  reg.Insert(reinterpret_cast<void*>(2), 0, ctx);
+  reg.Remove(reinterpret_cast<void*>(1));
+  reg.Remove(reinterpret_cast<void*>(1));  // Remove for the second time.
+  reg.Remove(reinterpret_cast<void*>(4));  // Remove never inserted address.
+
+  EXPECT_EQ(2u, OrAllAddresses(reg));
+}
+
+TEST_F(AllocationRegisterTest, DoubleInsertOverwrites) {
+  // TODO(ruuda): Although double insert happens in practice, it should not.
+  // Find out the cause and ban double insert if possible.
+  AllocationRegister reg;
+  AllocationContext ctx;
+  StackFrame frame1 = "Foo";
+  StackFrame frame2 = "Bar";
+
+  ctx.backtrace.frames[0] = frame1;
+  reg.Insert(reinterpret_cast<void*>(1), 11, ctx);
+
+  auto elem = *reg.begin();
+
+  EXPECT_EQ(frame1, elem.context.backtrace.frames[0]);
+  EXPECT_EQ(11u, elem.size);
+  EXPECT_EQ(reinterpret_cast<void*>(1), elem.address);
+
+  ctx.backtrace.frames[0] = frame2;
+  reg.Insert(reinterpret_cast<void*>(1), 13, ctx);
+
+  elem = *reg.begin();
+
+  EXPECT_EQ(frame2, elem.context.backtrace.frames[0]);
+  EXPECT_EQ(13u, elem.size);
+  EXPECT_EQ(reinterpret_cast<void*>(1), elem.address);
+}
+
+// Check that even if more entries than the table size are inserted, the
+// register still behaves correctly.
+TEST_F(AllocationRegisterTest, InsertRemoveCollisions) {
+  size_t expected_sum = 0;
+  AllocationRegister reg;
+  AllocationContext ctx;
+
+  // By inserting 100 more entries than the table size, there will be at least
+  // 100 collisions.
+  for (uintptr_t i = 1; i <= GetTableSize(reg) + 100; i++) {
+    size_t size = i % 31;
+    expected_sum += size;
+    reg.Insert(reinterpret_cast<void*>(i), size, ctx);
+
+    // Don't check the sum on every iteration to keep the test fast.
+    if (i % (1 << 14) == 0)
+      EXPECT_EQ(expected_sum, SumAllSizes(reg));
+  }
+
+  EXPECT_EQ(expected_sum, SumAllSizes(reg));
+
+  for (uintptr_t i = 1; i <= GetTableSize(reg) + 100; i++) {
+    size_t size = i % 31;
+    expected_sum -= size;
+    reg.Remove(reinterpret_cast<void*>(i));
+
+    if (i % (1 << 14) == 0)
+      EXPECT_EQ(expected_sum, SumAllSizes(reg));
+  }
+
+  EXPECT_EQ(expected_sum, SumAllSizes(reg));
+}
+
+// The previous tests are not particularly good for testing iterators, because
+// elements are removed and inserted in the same order, meaning that the cells
+// fill up from low to high index, and are then freed from low to high index.
+// This test removes entries in a different order, to ensure that the iterator
+// skips over the freed cells properly. Then insert again to ensure that the
+// free list is utilised properly.
+TEST_F(AllocationRegisterTest, InsertRemoveRandomOrder) {
+  size_t expected_sum = 0;
+  AllocationRegister reg;
+  AllocationContext ctx;
+
+  uintptr_t generator = 3;
+  uintptr_t prime = 1013;
+  uint32_t initial_used = GetHighWaterMark(reg);
+
+  for (uintptr_t i = 2; i < prime; i++) {
+    size_t size = i % 31;
+    expected_sum += size;
+    reg.Insert(reinterpret_cast<void*>(i), size, ctx);
+  }
+
+  // This should have used a fresh slot for each of the |prime - 2| inserts.
+  ASSERT_EQ(prime - 2, GetHighWaterMark(reg) - initial_used);
+
+  // Iterate the numbers 2, 3, ..., prime - 1 in pseudorandom order.
+  for (uintptr_t i = generator; i != 1; i = (i * generator) % prime) {
+    size_t size = i % 31;
+    expected_sum -= size;
+    reg.Remove(reinterpret_cast<void*>(i));
+    EXPECT_EQ(expected_sum, SumAllSizes(reg));
+  }
+
+  ASSERT_EQ(0u, expected_sum);
+
+  // Insert |prime - 2| entries again. This should use cells from the free list,
+  // so the |next_unused_cell_| index should not change.
+  for (uintptr_t i = 2; i < prime; i++)
+    reg.Insert(reinterpret_cast<void*>(i), 0, ctx);
+
+  ASSERT_EQ(prime - 2, GetHighWaterMark(reg) - initial_used);
+
+  // Inserting one more entry should use a fresh cell again.
+  reg.Insert(reinterpret_cast<void*>(prime), 0, ctx);
+  ASSERT_EQ(prime - 1, GetHighWaterMark(reg) - initial_used);
+}
+
+// Check that the process aborts due to hitting the guard page when inserting
+// too many elements.
+TEST_F(AllocationRegisterTest, OverflowDeathTest) {

[Primiano Tucci (use gerrit), 2015/10/06 13:34:44]

Hmm how long does it take to run this test?
Having a test which fills 2.6 Mln objects might take non negligible time and the
benefit here would not be worth the time spent for running the test.
If this takes more than a bunch of hundreds ms it's probably not worth it.

Also, IIRC death test require #ifdef guards, are not supported in all platforms,
see codesearch. I guess they are more for checking security invariants.

[Ruud van Asseldonk, 2015/10/06 15:44:35]

It is pretty heavy (~400 ms on my machine), but I did want to add it to verify
that the guard page works. Perhaps we can keep it as a disabled test?
Thought I fixed that in patchset 6, but then -Werror refused to compile due to
unused variables. Should be fixed now.

+  AllocationRegister reg;
+  AllocationContext ctx;
+  uintptr_t i;
+
+  // Fill up all of the memory allocated for the register. |GetNumCells(reg)|
+  // minus 1 elements are inserted, because cell 0 is unused, so this should
+  // fill up the available cells exactly.
+  for (i = 1; i < GetNumCells(reg); i++) {
+    reg.Insert(reinterpret_cast<void*>(i), 0, ctx);
+  }
+
+  // Adding just one extra element might still work because the allocated memory
+  // is rounded up to the page size. Adding a page full of elements should cause
+  // overflow.
+  const size_t cells_per_page = GetNumCellsPerPage();
+
+  ASSERT_DEATH(for (size_t j = 0; j < cells_per_page; j++) {
+    reg.Insert(reinterpret_cast<void*>(i + j), 0, ctx);
+  }, "");
+}
+
+}  // namespace trace_event
+}  // namespace base