OLD | NEW |
(Empty) | |
| 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "base/trace_event/memory_profiler_allocation_register.h" |
| 6 |
| 7 #include "base/process/process_metrics.h" |
| 8 #include "testing/gtest/include/gtest/gtest.h" |
| 9 |
| 10 namespace base { |
| 11 namespace trace_event { |
| 12 |
| 13 class AllocationRegisterTest : public testing::Test { |
| 14 public: |
| 15 static const uint32_t kNumBuckets = AllocationRegister::kNumBuckets; |
| 16 static const uint32_t kNumCells = AllocationRegister::kNumCells; |
| 17 |
| 18 // Returns the number of cells that the |AllocationRegister| can store per |
| 19 // system page. |
| 20 size_t GetNumCellsPerPage() { |
| 21 return GetPageSize() / sizeof(AllocationRegister::Cell); |
| 22 } |
| 23 |
| 24 uint32_t GetHighWaterMark(const AllocationRegister& reg) { |
| 25 return reg.next_unused_cell_; |
| 26 } |
| 27 }; |
| 28 |
| 29 // Iterates over all entries in the allocation register and returns the bitwise |
| 30 // or of all addresses stored in it. |
| 31 uintptr_t OrAllAddresses(const AllocationRegister& reg) { |
| 32 uintptr_t acc = 0; |
| 33 |
| 34 for (auto i : reg) |
| 35 acc |= reinterpret_cast<uintptr_t>(i.address); |
| 36 |
| 37 return acc; |
| 38 } |
| 39 |
| 40 // Iterates over all entries in the allocation register and returns the sum of |
| 41 // the sizes of the entries. |
| 42 size_t SumAllSizes(const AllocationRegister& reg) { |
| 43 size_t sum = 0; |
| 44 |
| 45 for (auto i : reg) |
| 46 sum += i.size; |
| 47 |
| 48 return sum; |
| 49 } |
| 50 |
| 51 TEST_F(AllocationRegisterTest, InsertRemove) { |
| 52 AllocationRegister reg; |
| 53 AllocationContext ctx; |
| 54 |
| 55 EXPECT_EQ(0u, OrAllAddresses(reg)); |
| 56 |
| 57 reg.Insert(reinterpret_cast<void*>(1), 0, ctx); |
| 58 |
| 59 EXPECT_EQ(1u, OrAllAddresses(reg)); |
| 60 |
| 61 reg.Insert(reinterpret_cast<void*>(2), 0, ctx); |
| 62 |
| 63 EXPECT_EQ(3u, OrAllAddresses(reg)); |
| 64 |
| 65 reg.Insert(reinterpret_cast<void*>(4), 0, ctx); |
| 66 |
| 67 EXPECT_EQ(7u, OrAllAddresses(reg)); |
| 68 |
| 69 reg.Remove(reinterpret_cast<void*>(2)); |
| 70 |
| 71 EXPECT_EQ(5u, OrAllAddresses(reg)); |
| 72 |
| 73 reg.Remove(reinterpret_cast<void*>(4)); |
| 74 |
| 75 EXPECT_EQ(1u, OrAllAddresses(reg)); |
| 76 |
| 77 reg.Remove(reinterpret_cast<void*>(1)); |
| 78 |
| 79 EXPECT_EQ(0u, OrAllAddresses(reg)); |
| 80 } |
| 81 |
| 82 TEST_F(AllocationRegisterTest, DoubleFreeIsAllowed) { |
| 83 AllocationRegister reg; |
| 84 AllocationContext ctx; |
| 85 |
| 86 reg.Insert(reinterpret_cast<void*>(1), 0, ctx); |
| 87 reg.Insert(reinterpret_cast<void*>(2), 0, ctx); |
| 88 reg.Remove(reinterpret_cast<void*>(1)); |
| 89 reg.Remove(reinterpret_cast<void*>(1)); // Remove for the second time. |
| 90 reg.Remove(reinterpret_cast<void*>(4)); // Remove never inserted address. |
| 91 |
| 92 EXPECT_EQ(2u, OrAllAddresses(reg)); |
| 93 } |
| 94 |
| 95 TEST_F(AllocationRegisterTest, DoubleInsertOverwrites) { |
| 96 // TODO(ruuda): Although double insert happens in practice, it should not. |
| 97 // Find out the cause and ban double insert if possible. |
| 98 AllocationRegister reg; |
| 99 AllocationContext ctx; |
| 100 StackFrame frame1 = "Foo"; |
| 101 StackFrame frame2 = "Bar"; |
| 102 |
| 103 ctx.backtrace.frames[0] = frame1; |
| 104 reg.Insert(reinterpret_cast<void*>(1), 11, ctx); |
| 105 |
| 106 auto elem = *reg.begin(); |
| 107 |
| 108 EXPECT_EQ(frame1, elem.context.backtrace.frames[0]); |
| 109 EXPECT_EQ(11u, elem.size); |
| 110 EXPECT_EQ(reinterpret_cast<void*>(1), elem.address); |
| 111 |
| 112 ctx.backtrace.frames[0] = frame2; |
| 113 reg.Insert(reinterpret_cast<void*>(1), 13, ctx); |
| 114 |
| 115 elem = *reg.begin(); |
| 116 |
| 117 EXPECT_EQ(frame2, elem.context.backtrace.frames[0]); |
| 118 EXPECT_EQ(13u, elem.size); |
| 119 EXPECT_EQ(reinterpret_cast<void*>(1), elem.address); |
| 120 } |
| 121 |
| 122 // Check that even if more entries than the number of buckets are inserted, the |
| 123 // register still behaves correctly. |
| 124 TEST_F(AllocationRegisterTest, InsertRemoveCollisions) { |
| 125 size_t expected_sum = 0; |
| 126 AllocationRegister reg; |
| 127 AllocationContext ctx; |
| 128 |
| 129 // By inserting 100 more entries than the number of buckets, there will be at |
| 130 // least 100 collisions. |
| 131 for (uintptr_t i = 1; i <= kNumBuckets + 100; i++) { |
| 132 size_t size = i % 31; |
| 133 expected_sum += size; |
| 134 reg.Insert(reinterpret_cast<void*>(i), size, ctx); |
| 135 |
| 136 // Don't check the sum on every iteration to keep the test fast. |
| 137 if (i % (1 << 14) == 0) |
| 138 EXPECT_EQ(expected_sum, SumAllSizes(reg)); |
| 139 } |
| 140 |
| 141 EXPECT_EQ(expected_sum, SumAllSizes(reg)); |
| 142 |
| 143 for (uintptr_t i = 1; i <= kNumBuckets + 100; i++) { |
| 144 size_t size = i % 31; |
| 145 expected_sum -= size; |
| 146 reg.Remove(reinterpret_cast<void*>(i)); |
| 147 |
| 148 if (i % (1 << 14) == 0) |
| 149 EXPECT_EQ(expected_sum, SumAllSizes(reg)); |
| 150 } |
| 151 |
| 152 EXPECT_EQ(expected_sum, SumAllSizes(reg)); |
| 153 } |
| 154 |
| 155 // The previous tests are not particularly good for testing iterators, because |
| 156 // elements are removed and inserted in the same order, meaning that the cells |
| 157 // fill up from low to high index, and are then freed from low to high index. |
| 158 // This test removes entries in a different order, to ensure that the iterator |
| 159 // skips over the freed cells properly. Then insert again to ensure that the |
| 160 // free list is utilised properly. |
| 161 TEST_F(AllocationRegisterTest, InsertRemoveRandomOrder) { |
| 162 size_t expected_sum = 0; |
| 163 AllocationRegister reg; |
| 164 AllocationContext ctx; |
| 165 |
| 166 uintptr_t generator = 3; |
| 167 uintptr_t prime = 1013; |
| 168 uint32_t initial_water_mark = GetHighWaterMark(reg); |
| 169 |
| 170 for (uintptr_t i = 2; i < prime; i++) { |
| 171 size_t size = i % 31; |
| 172 expected_sum += size; |
| 173 reg.Insert(reinterpret_cast<void*>(i), size, ctx); |
| 174 } |
| 175 |
| 176 // This should have used a fresh slot for each of the |prime - 2| inserts. |
| 177 ASSERT_EQ(prime - 2, GetHighWaterMark(reg) - initial_water_mark); |
| 178 |
| 179 // Iterate the numbers 2, 3, ..., prime - 1 in pseudorandom order. |
| 180 for (uintptr_t i = generator; i != 1; i = (i * generator) % prime) { |
| 181 size_t size = i % 31; |
| 182 expected_sum -= size; |
| 183 reg.Remove(reinterpret_cast<void*>(i)); |
| 184 EXPECT_EQ(expected_sum, SumAllSizes(reg)); |
| 185 } |
| 186 |
| 187 ASSERT_EQ(0u, expected_sum); |
| 188 |
| 189 // Insert |prime - 2| entries again. This should use cells from the free list, |
| 190 // so the |next_unused_cell_| index should not change. |
| 191 for (uintptr_t i = 2; i < prime; i++) |
| 192 reg.Insert(reinterpret_cast<void*>(i), 0, ctx); |
| 193 |
| 194 ASSERT_EQ(prime - 2, GetHighWaterMark(reg) - initial_water_mark); |
| 195 |
| 196 // Inserting one more entry should use a fresh cell again. |
| 197 reg.Insert(reinterpret_cast<void*>(prime), 0, ctx); |
| 198 ASSERT_EQ(prime - 1, GetHighWaterMark(reg) - initial_water_mark); |
| 199 } |
| 200 |
| 201 // Check that the process aborts due to hitting the guard page when inserting |
| 202 // too many elements. |
| 203 #if GTEST_HAS_DEATH_TEST |
| 204 TEST_F(AllocationRegisterTest, OverflowDeathTest) { |
| 205 AllocationRegister reg; |
| 206 AllocationContext ctx; |
| 207 uintptr_t i; |
| 208 |
| 209 // Fill up all of the memory allocated for the register. |kNumCells| minus 1 |
| 210 // elements are inserted, because cell 0 is unused, so this should fill up |
| 211 // the available cells exactly. |
| 212 for (i = 1; i < kNumCells; i++) { |
| 213 reg.Insert(reinterpret_cast<void*>(i), 0, ctx); |
| 214 } |
| 215 |
| 216 // Adding just one extra element might still work because the allocated memory |
| 217 // is rounded up to the page size. Adding a page full of elements should cause |
| 218 // overflow. |
| 219 const size_t cells_per_page = GetNumCellsPerPage(); |
| 220 |
| 221 ASSERT_DEATH(for (size_t j = 0; j < cells_per_page; j++) { |
| 222 reg.Insert(reinterpret_cast<void*>(i + j), 0, ctx); |
| 223 }, ""); |
| 224 } |
| 225 #endif |
| 226 |
| 227 } // namespace trace_event |
| 228 } // namespace base |
OLD | NEW |