1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/profiling/memory/bookkeeping.h"
18
19 #include "test/gtest_and_gmock.h"
20
21 namespace perfetto {
22 namespace profiling {
23 namespace {
24
25 using ::testing::AnyOf;
26 using ::testing::Eq;
27
stack()28 std::vector<unwindstack::FrameData> stack() {
29 std::vector<unwindstack::FrameData> res;
30
31 unwindstack::FrameData data{};
32 data.function_name = "fun1";
33 data.pc = 1;
34 res.emplace_back(std::move(data));
35 data = {};
36 data.function_name = "fun2";
37 data.pc = 2;
38 res.emplace_back(std::move(data));
39 return res;
40 }
41
stack2()42 std::vector<unwindstack::FrameData> stack2() {
43 std::vector<unwindstack::FrameData> res;
44 unwindstack::FrameData data{};
45 data.function_name = "fun1";
46 data.pc = 1;
47 res.emplace_back(std::move(data));
48 data = {};
49 data.function_name = "fun3";
50 data.pc = 3;
51 res.emplace_back(std::move(data));
52 return res;
53 }
54
stack3()55 std::vector<unwindstack::FrameData> stack3() {
56 std::vector<unwindstack::FrameData> res;
57 unwindstack::FrameData data{};
58 data.function_name = "fun1";
59 data.pc = 1;
60 res.emplace_back(std::move(data));
61 data = {};
62 data.function_name = "fun4";
63 data.pc = 4;
64 res.emplace_back(std::move(data));
65 return res;
66 }
67
DummyBuildIds(size_t n)68 std::vector<std::string> DummyBuildIds(size_t n) {
69 return std::vector<std::string>(n, "dummy_buildid");
70 }
71
TEST(BookkeepingTest,EmptyStack)72 TEST(BookkeepingTest, EmptyStack) {
73 uint64_t sequence_number = 1;
74 GlobalCallstackTrie c;
75 HeapTracker hd(&c, false);
76
77 hd.RecordMalloc({}, {}, 0x1, 5, 5, sequence_number, 100 * sequence_number);
78 sequence_number++;
79 hd.RecordFree(0x1, sequence_number, 100 * sequence_number);
80 hd.GetCallstackAllocations([](const HeapTracker::CallstackAllocations&) {});
81 }
82
TEST(BookkeepingTest,Replace)83 TEST(BookkeepingTest, Replace) {
84 uint64_t sequence_number = 1;
85 GlobalCallstackTrie c;
86 HeapTracker hd(&c, false);
87
88 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 1, 5, 5,
89 sequence_number, 100 * sequence_number);
90 sequence_number++;
91 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 1, 2, 2,
92 sequence_number, 100 * sequence_number);
93
94 // Call GetCallstackAllocations twice to force GC of old CallstackAllocations.
95 hd.GetCallstackAllocations([](const HeapTracker::CallstackAllocations&) {});
96 hd.GetCallstackAllocations([](const HeapTracker::CallstackAllocations&) {});
97 }
98
TEST(BookkeepingTest,Basic)99 TEST(BookkeepingTest, Basic) {
100 uint64_t sequence_number = 1;
101 GlobalCallstackTrie c;
102 HeapTracker hd(&c, false);
103
104 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 5, 5,
105 sequence_number, 100 * sequence_number);
106 sequence_number++;
107 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x2, 2, 2,
108 sequence_number, 100 * sequence_number);
109 sequence_number++;
110 ASSERT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 5u);
111 ASSERT_EQ(hd.GetSizeForTesting(stack2(), DummyBuildIds(stack2().size())), 2u);
112 ASSERT_EQ(hd.GetTimestampForTesting(), 100 * (sequence_number - 1));
113 hd.RecordFree(0x2, sequence_number, 100 * sequence_number);
114 sequence_number++;
115 ASSERT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 5u);
116 ASSERT_EQ(hd.GetSizeForTesting(stack2(), DummyBuildIds(stack2().size())), 0u);
117 ASSERT_EQ(hd.GetTimestampForTesting(), 100 * (sequence_number - 1));
118 hd.RecordFree(0x1, sequence_number, 100 * sequence_number);
119 sequence_number++;
120 ASSERT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 0u);
121 ASSERT_EQ(hd.GetSizeForTesting(stack2(), DummyBuildIds(stack2().size())), 0u);
122 ASSERT_EQ(hd.GetTimestampForTesting(), 100 * (sequence_number - 1));
123 }
124
TEST(BookkeepingTest,Max)125 TEST(BookkeepingTest, Max) {
126 uint64_t sequence_number = 1;
127 GlobalCallstackTrie c;
128 HeapTracker hd(&c, true);
129
130 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 5, 5,
131 sequence_number, 100 * sequence_number);
132 sequence_number++;
133 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x2, 2, 2,
134 sequence_number, 100 * sequence_number);
135 sequence_number++;
136 hd.RecordFree(0x2, sequence_number, 100 * sequence_number);
137 sequence_number++;
138 hd.RecordFree(0x1, sequence_number, 100 * sequence_number);
139 sequence_number++;
140 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x2, 1, 2,
141 sequence_number, 100 * sequence_number);
142 ASSERT_EQ(hd.dump_timestamp(), 200u);
143 ASSERT_EQ(hd.GetMaxForTesting(stack(), DummyBuildIds(stack().size())), 5u);
144 ASSERT_EQ(hd.GetMaxForTesting(stack2(), DummyBuildIds(stack2().size())), 2u);
145 ASSERT_EQ(hd.GetMaxCountForTesting(stack(), DummyBuildIds(stack().size())),
146 1u);
147 ASSERT_EQ(hd.GetMaxCountForTesting(stack2(), DummyBuildIds(stack2().size())),
148 1u);
149 }
150
TEST(BookkeepingTest,Max2)151 TEST(BookkeepingTest, Max2) {
152 uint64_t sequence_number = 1;
153 GlobalCallstackTrie c;
154 HeapTracker hd(&c, true);
155
156 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 10u, 10u,
157 sequence_number, 100 * sequence_number);
158 sequence_number++;
159 hd.RecordFree(0x1, sequence_number, 100 * sequence_number);
160 sequence_number++;
161 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x2, 15u, 15u,
162 sequence_number, 100 * sequence_number);
163 sequence_number++;
164 hd.RecordMalloc(stack3(), DummyBuildIds(stack3().size()), 0x3, 15u, 15u,
165 sequence_number, 100 * sequence_number);
166 sequence_number++;
167 hd.RecordFree(0x2, sequence_number, 100 * sequence_number);
168 EXPECT_EQ(hd.dump_timestamp(), 400u);
169 EXPECT_EQ(hd.GetMaxForTesting(stack(), DummyBuildIds(stack().size())), 0u);
170 EXPECT_EQ(hd.GetMaxForTesting(stack2(), DummyBuildIds(stack2().size())), 15u);
171 EXPECT_EQ(hd.GetMaxForTesting(stack3(), DummyBuildIds(stack3().size())), 15u);
172 EXPECT_EQ(hd.GetMaxCountForTesting(stack(), DummyBuildIds(stack().size())),
173 0u);
174 EXPECT_EQ(hd.GetMaxCountForTesting(stack2(), DummyBuildIds(stack2().size())),
175 1u);
176 EXPECT_EQ(hd.GetMaxCountForTesting(stack3(), DummyBuildIds(stack3().size())),
177 1u);
178 }
179
TEST(BookkeepingTest,TwoHeapTrackers)180 TEST(BookkeepingTest, TwoHeapTrackers) {
181 uint64_t sequence_number = 1;
182 GlobalCallstackTrie c;
183 HeapTracker hd(&c, false);
184 {
185 HeapTracker hd2(&c, false);
186
187 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 5, 5,
188 sequence_number, 100 * sequence_number);
189 hd2.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x2, 2, 2,
190 sequence_number, 100 * sequence_number);
191 sequence_number++;
192 ASSERT_EQ(hd2.GetSizeForTesting(stack(), DummyBuildIds(stack().size())),
193 2u);
194 ASSERT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 5u);
195 ASSERT_EQ(hd.GetTimestampForTesting(), 100 * (sequence_number - 1));
196 }
197 ASSERT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 5u);
198 }
199
TEST(BookkeepingTest,ReplaceAlloc)200 TEST(BookkeepingTest, ReplaceAlloc) {
201 uint64_t sequence_number = 1;
202 GlobalCallstackTrie c;
203 HeapTracker hd(&c, false);
204
205 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 5, 5,
206 sequence_number, 100 * sequence_number);
207 sequence_number++;
208 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x1, 2, 2,
209 sequence_number, 100 * sequence_number);
210 sequence_number++;
211 EXPECT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 0u);
212 EXPECT_EQ(hd.GetSizeForTesting(stack2(), DummyBuildIds(stack2().size())), 2u);
213 ASSERT_EQ(hd.GetTimestampForTesting(), 100 * (sequence_number - 1));
214 }
215
TEST(BookkeepingTest,OutOfOrder)216 TEST(BookkeepingTest, OutOfOrder) {
217 GlobalCallstackTrie c;
218 HeapTracker hd(&c, false);
219
220 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), 0x1, 5, 5, 2, 2);
221 hd.RecordMalloc(stack2(), DummyBuildIds(stack2().size()), 0x1, 2, 2, 1, 1);
222 EXPECT_EQ(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())), 5u);
223 EXPECT_EQ(hd.GetSizeForTesting(stack2(), DummyBuildIds(stack2().size())), 0u);
224 }
225
TEST(BookkeepingTest,ManyAllocations)226 TEST(BookkeepingTest, ManyAllocations) {
227 GlobalCallstackTrie c;
228 HeapTracker hd(&c, false);
229
230 std::vector<std::pair<uint64_t, uint64_t>> batch_frees;
231
232 for (uint64_t sequence_number = 1; sequence_number < 1000;) {
233 if (batch_frees.size() > 10) {
234 for (const auto& p : batch_frees)
235 hd.RecordFree(p.first, p.second, 100 * p.second);
236 batch_frees.clear();
237 }
238
239 uint64_t addr = sequence_number;
240 hd.RecordMalloc(stack(), DummyBuildIds(stack().size()), addr, 5, 5,
241 sequence_number, sequence_number);
242 sequence_number++;
243 batch_frees.emplace_back(addr, sequence_number++);
244 ASSERT_THAT(hd.GetSizeForTesting(stack(), DummyBuildIds(stack().size())),
245 AnyOf(Eq(0u), Eq(5u)));
246 }
247 }
248
TEST(BookkeepingTest,ArbitraryOrder)249 TEST(BookkeepingTest, ArbitraryOrder) {
250 std::vector<unwindstack::FrameData> s = stack();
251 std::vector<unwindstack::FrameData> s2 = stack2();
252
253 std::vector<std::string> s_b = DummyBuildIds(s.size());
254 std::vector<std::string> s2_b = DummyBuildIds(s2.size());
255
256 enum OperationType { kAlloc, kFree, kDump };
257
258 struct Operation {
259 uint64_t sequence_number;
260 OperationType type;
261 uint64_t address;
262 uint64_t bytes; // 0 for free
263 const std::vector<unwindstack::FrameData>* stack; // nullptr for free
264 const std::vector<std::string>* build_ids; // nullptr for free
265
266 // For std::next_permutation.
267 bool operator<(const Operation& other) const {
268 return sequence_number < other.sequence_number;
269 }
270 } operations[] = {
271 {1, kAlloc, 0x1, 5, &s, &s_b}, //
272 {2, kAlloc, 0x1, 10, &s2, &s2_b}, //
273 {3, kFree, 0x01, 0, nullptr, nullptr}, //
274 {4, kFree, 0x02, 0, nullptr, nullptr}, //
275 {5, kFree, 0x03, 0, nullptr, nullptr}, //
276 {6, kAlloc, 0x3, 2, &s, &s_b}, //
277 {7, kAlloc, 0x4, 3, &s2, &s2_b}, //
278 {0, kDump, 0x00, 0, nullptr, nullptr}, //
279 };
280
281 uint64_t s_size = 2;
282 uint64_t s2_size = 3;
283
284 do {
285 GlobalCallstackTrie c;
286 HeapTracker hd(&c, false);
287
288 for (auto it = std::begin(operations); it != std::end(operations); ++it) {
289 const Operation& operation = *it;
290
291 if (operation.type == OperationType::kFree) {
292 hd.RecordFree(operation.address, operation.sequence_number,
293 100 * operation.sequence_number);
294 } else if (operation.type == OperationType::kAlloc) {
295 hd.RecordMalloc(*operation.stack, DummyBuildIds(stack().size()),
296 operation.address, operation.bytes, operation.bytes,
297 operation.sequence_number,
298 100 * operation.sequence_number);
299 } else {
300 hd.GetCallstackAllocations(
301 [](const HeapTracker::CallstackAllocations&) {});
302 }
303 }
304 ASSERT_EQ(hd.GetSizeForTesting(s, s_b), s_size);
305 ASSERT_EQ(hd.GetSizeForTesting(s2, s2_b), s2_size);
306 } while (std::next_permutation(std::begin(operations), std::end(operations)));
307 }
308
309 } // namespace
310 } // namespace profiling
311 } // namespace perfetto
312