1 /*
2 * Copyright (C) 2024 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/trace_processor/importers/common/address_range.h"
18
19 #include <cstdint>
20 #include <limits>
21 #include <utility>
22 #include <vector>
23
24 #include "test/gtest_and_gmock.h"
25
26 namespace perfetto {
27 namespace trace_processor {
28
29 // Limited support for abseil in perfetto so we can not use the recommended
30 // AbslStringify()
PrintTo(const AddressRange & r,std::ostream * os)31 inline void PrintTo(const AddressRange& r, std::ostream* os) {
32 if (r.empty()) {
33 *os << "(empty)";
34 } else {
35 *os << "[" << r.start() << "," << r.end() << ")";
36 }
37 }
38
39 namespace {
40
41 using ::testing::_;
42 using ::testing::A;
43 using ::testing::AllOf;
44 using ::testing::ElementsAre;
45 using ::testing::Eq;
46 using ::testing::IsEmpty;
47 using ::testing::MockFunction;
48 using ::testing::Ne;
49 using ::testing::Pair;
50 using ::testing::Pointee;
51 using ::testing::SizeIs;
52
53 MATCHER_P2(IteratorPointsTo, container, matcher, "") {
54 return ExplainMatchResult(Ne(container.end()), arg, result_listener) &&
55 ExplainMatchResult(matcher, *arg, result_listener);
56 }
57
AppendRangesTo(std::vector<AddressRange> & ranges)58 auto AppendRangesTo(std::vector<AddressRange>& ranges) {
59 return [&ranges](std::pair<const AddressRange, int>& e) {
60 ranges.push_back(e.first);
61 };
62 }
63
TEST(AddressRange,EmptyByDefault)64 TEST(AddressRange, EmptyByDefault) {
65 constexpr AddressRange kRange;
66 // This is more of an implementation detail (that start and end are
67 // initialized to zero). But this "knowledge" is used for the contains tests,
68 // to probe for those specific values.
69 EXPECT_THAT(kRange.end(), Eq(0u));
70 EXPECT_THAT(kRange.start(), Eq(0u));
71 EXPECT_THAT(kRange.length(), Eq(0u));
72 EXPECT_THAT(kRange, IsEmpty());
73 }
74
TEST(AddressRange,EmptyRangeContainsNothing)75 TEST(AddressRange, EmptyRangeContainsNothing) {
76 constexpr AddressRange kEmptyRange;
77 EXPECT_FALSE(kEmptyRange.Contains(0));
78 }
79
TEST(AddressRange,ContainsAddress)80 TEST(AddressRange, ContainsAddress) {
81 constexpr AddressRange kRange(1, 10);
82 EXPECT_FALSE(kRange.Contains(0));
83 EXPECT_TRUE(kRange.Contains(1));
84 EXPECT_TRUE(kRange.Contains(9));
85 EXPECT_FALSE(kRange.Contains(10));
86 }
87
TEST(AddressRange,MaxRangeContainsAll)88 TEST(AddressRange, MaxRangeContainsAll) {
89 constexpr AddressRange kMaxRange(0, std::numeric_limits<uint64_t>::max());
90 EXPECT_TRUE(kMaxRange.Contains(0));
91 EXPECT_TRUE(kMaxRange.Contains(std::numeric_limits<uint64_t>::max() - 1));
92 // End is not inclusive.
93 EXPECT_FALSE(kMaxRange.Contains(std::numeric_limits<uint64_t>::max()));
94 }
95
TEST(AddressRange,ContainsRange)96 TEST(AddressRange, ContainsRange) {
97 constexpr AddressRange kRange(10, 20);
98 EXPECT_TRUE(kRange.Contains(kRange));
99 EXPECT_TRUE(kRange.Contains(AddressRange(11, 19)));
100 EXPECT_TRUE(kRange.Contains(AddressRange(10, 19)));
101 EXPECT_TRUE(kRange.Contains(AddressRange(11, 20)));
102
103 EXPECT_FALSE(kRange.Contains(AddressRange(9, 20)));
104 EXPECT_FALSE(kRange.Contains(AddressRange(10, 21)));
105 EXPECT_FALSE(kRange.Contains(AddressRange(9, 10)));
106 EXPECT_FALSE(kRange.Contains(AddressRange(20, 21)));
107 }
108
TEST(AddressRange,Intersect)109 TEST(AddressRange, Intersect) {
110 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(0, 10)),
111 Eq(AddressRange(0, 10)));
112
113 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(10, 20)),
114 IsEmpty());
115
116 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(0, 0)),
117 Eq(AddressRange(0, 0)));
118 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(1, 10)),
119 Eq(AddressRange(1, 10)));
120
121 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange()), IsEmpty());
122 }
123
TEST(AddressRange,Overlap)124 TEST(AddressRange, Overlap) {
125 EXPECT_FALSE(AddressRange(0, 10).Overlaps(AddressRange(5, 5)));
126 EXPECT_FALSE(AddressRange(5, 5).Overlaps(AddressRange(0, 10)));
127 EXPECT_FALSE(AddressRange(0, 10).Overlaps(AddressRange(10, 20)));
128 EXPECT_FALSE(AddressRange(10, 20).Overlaps(AddressRange(0, 10)));
129
130 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(9, 10)));
131 EXPECT_TRUE(AddressRange(10, 20).Overlaps(AddressRange(0, 11)));
132 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(5, 6)));
133 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(5, 20)));
134 }
135
TEST(AddressRangeMap,Empty)136 TEST(AddressRangeMap, Empty) {
137 AddressRangeMap<int> empty;
138 EXPECT_THAT(empty, IsEmpty());
139 }
140
TEST(AddressRangeMap,EmplaceFailsForOverlaps)141 TEST(AddressRangeMap, EmplaceFailsForOverlaps) {
142 AddressRangeMap<int> map;
143 ASSERT_TRUE(map.Emplace(AddressRange(10, 20), 42));
144
145 EXPECT_FALSE(map.Emplace(AddressRange(10, 20)));
146 EXPECT_FALSE(map.Emplace(AddressRange(11, 19)));
147 EXPECT_FALSE(map.Emplace(AddressRange(0, 11)));
148 EXPECT_FALSE(map.Emplace(AddressRange(19, 30)));
149 EXPECT_THAT(map, ElementsAre(Pair(AddressRange(10, 20), 42)));
150 }
151
TEST(AddressRangeMap,EmplaceSucceedsForNonOverlaps)152 TEST(AddressRangeMap, EmplaceSucceedsForNonOverlaps) {
153 AddressRangeMap<int> map;
154
155 EXPECT_TRUE(map.Emplace(AddressRange(10, 20)));
156 EXPECT_TRUE(map.Emplace(AddressRange(0, 10)));
157 EXPECT_TRUE(map.Emplace(AddressRange(20, 30)));
158
159 EXPECT_THAT(map, SizeIs(3));
160 }
161
TEST(AddressRangeMap,EmplaceFailsForEmptyRange)162 TEST(AddressRangeMap, EmplaceFailsForEmptyRange) {
163 AddressRangeMap<int> map;
164
165 EXPECT_FALSE(map.Emplace(AddressRange(0, 0)));
166 EXPECT_FALSE(map.Emplace(AddressRange(100, 100)));
167
168 EXPECT_THAT(map, IsEmpty());
169 }
170
TEST(AddressRangeMap,DeleteOverlapsAndEmplaceFailsForEmptyRange)171 TEST(AddressRangeMap, DeleteOverlapsAndEmplaceFailsForEmptyRange) {
172 AddressRangeMap<int> map;
173 EXPECT_TRUE(map.Emplace(AddressRange(0, 10), 42));
174 EXPECT_FALSE(map.Emplace(AddressRange(0, 0)));
175 EXPECT_FALSE(map.Emplace(AddressRange(100, 100)));
176
177 EXPECT_THAT(map, ElementsAre(Pair(AddressRange(0, 10), 42)));
178 }
179
TEST(AddressRangeMap,FindAddress)180 TEST(AddressRangeMap, FindAddress) {
181 AddressRangeMap<int> map;
182 map.Emplace(AddressRange(0, 10), 0);
183 map.Emplace(AddressRange(10, 20), 1);
184 map.Emplace(AddressRange(25, 30), 2);
185
186 ASSERT_THAT(map.Find(0), Ne(map.end()));
187 EXPECT_THAT(map.Find(0)->second, Eq(0));
188
189 ASSERT_THAT(map.Find(9), Ne(map.end()));
190 EXPECT_THAT(map.Find(9)->second, Eq(0));
191
192 ASSERT_THAT(map.Find(10), Ne(map.end()));
193 EXPECT_THAT(map.Find(10)->second, Eq(1));
194
195 ASSERT_THAT(map.Find(10), Ne(map.end()));
196 EXPECT_THAT(map.Find(19)->second, Eq(1));
197
198 EXPECT_THAT(map.Find(20), Eq(map.end()));
199
200 EXPECT_THAT(map.Find(24), Eq(map.end()));
201
202 ASSERT_THAT(map.Find(25), Ne(map.end()));
203 EXPECT_THAT(map.Find(25)->second, Eq(2));
204
205 ASSERT_THAT(map.Find(29), Ne(map.end()));
206 EXPECT_THAT(map.Find(29)->second, Eq(2));
207
208 EXPECT_THAT(map.Find(30), Eq(map.end()));
209 }
210
TEST(AddressRangeMap,FindRangeThatContains)211 TEST(AddressRangeMap, FindRangeThatContains) {
212 AddressRangeMap<int> map;
213 map.Emplace(AddressRange(0, 10), 0);
214 map.Emplace(AddressRange(10, 20), 1);
215 map.Emplace(AddressRange(25, 30), 2);
216
217 auto match_1 = IteratorPointsTo(map, Pair(AddressRange(0, 10), 0));
218 auto match_2 = IteratorPointsTo(map, Pair(AddressRange(10, 20), 1));
219 auto match_3 = IteratorPointsTo(map, Pair(AddressRange(25, 30), 2));
220
221 EXPECT_THAT(map.FindRangeThatContains({0, 10}), match_1);
222 EXPECT_THAT(map.FindRangeThatContains({0, 1}), match_1);
223 EXPECT_THAT(map.FindRangeThatContains({3, 4}), match_1);
224 EXPECT_THAT(map.FindRangeThatContains({9, 10}), match_1);
225
226 EXPECT_THAT(map.FindRangeThatContains({10, 11}), match_2);
227 EXPECT_THAT(map.FindRangeThatContains({11, 12}), match_2);
228 EXPECT_THAT(map.FindRangeThatContains({19, 20}), match_2);
229 EXPECT_THAT(map.FindRangeThatContains({10, 20}), match_2);
230
231 EXPECT_THAT(map.FindRangeThatContains({25, 26}), match_3);
232 EXPECT_THAT(map.FindRangeThatContains({26, 27}), match_3);
233 EXPECT_THAT(map.FindRangeThatContains({29, 30}), match_3);
234 EXPECT_THAT(map.FindRangeThatContains({25, 30}), match_3);
235
236 EXPECT_THAT(map.FindRangeThatContains({9, 11}), Eq(map.end()));
237 EXPECT_THAT(map.FindRangeThatContains({20, 21}), Eq(map.end()));
238 EXPECT_THAT(map.FindRangeThatContains({24, 25}), Eq(map.end()));
239 EXPECT_THAT(map.FindRangeThatContains({14, 27}), Eq(map.end()));
240 }
241
TEST(AddressRangeMap,DeleteOverlapsAndEmplace)242 TEST(AddressRangeMap, DeleteOverlapsAndEmplace) {
243 const AddressRangeMap<int> entries = []() {
244 AddressRangeMap<int> map;
245 map.Emplace(AddressRange(0, 10), 0);
246 map.Emplace(AddressRange(10, 20), 1);
247 map.Emplace(AddressRange(25, 30), 2);
248 return map;
249 }();
250 auto entry = [](uint64_t start, uint64_t end, int value) {
251 return std::make_pair(AddressRange(start, end), value);
252 };
253
254 {
255 AddressRangeMap<int> map = entries;
256 std::vector<AddressRange> deleted;
257 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {30, 100}, 5);
258 EXPECT_THAT(deleted, ElementsAre());
259 EXPECT_THAT(map, ElementsAre(entry(0, 10, 0), entry(10, 20, 1),
260 entry(25, 30, 2), entry(30, 100, 5)));
261 }
262
263 {
264 AddressRangeMap<int> map = entries;
265 std::vector<AddressRange> deleted;
266 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {9, 10}, 5);
267 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10)));
268 EXPECT_THAT(
269 map, ElementsAre(entry(9, 10, 5), entry(10, 20, 1), entry(25, 30, 2)));
270 }
271
272 {
273 AddressRangeMap<int> map = entries;
274 std::vector<AddressRange> deleted;
275 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 11}, 5);
276 EXPECT_THAT(deleted,
277 ElementsAre(AddressRange(0, 10), AddressRange(10, 20)));
278 EXPECT_THAT(map, ElementsAre(entry(5, 11, 5), entry(25, 30, 2)));
279 }
280
281 {
282 AddressRangeMap<int> map = entries;
283 std::vector<AddressRange> deleted;
284 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 25}, 5);
285 EXPECT_THAT(deleted,
286 ElementsAre(AddressRange(0, 10), AddressRange(10, 20)));
287 EXPECT_THAT(map, ElementsAre(entry(5, 25, 5), entry(25, 30, 2)));
288 }
289
290 {
291 AddressRangeMap<int> map = entries;
292 std::vector<AddressRange> deleted;
293 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 31}, 5);
294 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10), AddressRange(10, 20),
295 AddressRange(25, 30)));
296 EXPECT_THAT(map, ElementsAre(entry(5, 31, 5)));
297 }
298
299 {
300 AddressRangeMap<int> map = entries;
301 std::vector<AddressRange> deleted;
302 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {0, 100}, 5);
303 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10), AddressRange(10, 20),
304 AddressRange(25, 30)));
305 EXPECT_THAT(map, ElementsAre(entry(0, 100, 5)));
306 }
307 }
308
309 // No need to test all cases as the impl calls the one with callback underneath
310 // and this has already been tested. This test is more about making sure the
311 // template code is correct and it can be instantiated.
TEST(AddressRangeMap,DeleteOverlapsAndEmplaceWithoutCallback)312 TEST(AddressRangeMap, DeleteOverlapsAndEmplaceWithoutCallback) {
313 auto entry = [](uint64_t start, uint64_t end, int value) {
314 return std::make_pair(AddressRange(start, end), value);
315 };
316 AddressRangeMap<int> map;
317 map.Emplace(AddressRange(0, 10), 0);
318 map.Emplace(AddressRange(10, 20), 1);
319 map.Emplace(AddressRange(25, 30), 2);
320
321 std::vector<AddressRange> deleted;
322 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 11}, 5);
323 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10), AddressRange(10, 20)));
324 EXPECT_THAT(map, ElementsAre(entry(5, 11, 5), entry(25, 30, 2)));
325 }
326
TEST(AddressRangeMap,ForOverlapsEmptyRangeDoesNothing)327 TEST(AddressRangeMap, ForOverlapsEmptyRangeDoesNothing) {
328 AddressRangeMap<int> map;
329 map.Emplace(AddressRange(0, 10), 0);
330 map.Emplace(AddressRange(10, 20), 1);
331 map.Emplace(AddressRange(25, 30), 2);
332
333 MockFunction<void(AddressRangeMap<int>::value_type&)> cb;
334 EXPECT_CALL(cb, Call).Times(0);
335
336 map.ForOverlaps(AddressRange(5, 5), cb.AsStdFunction());
337 }
338
TEST(AddressRangeMap,ForOverlaps)339 TEST(AddressRangeMap, ForOverlaps) {
340 AddressRangeMap<int> map;
341 map.Emplace(AddressRange(0, 10), 0);
342 map.Emplace(AddressRange(10, 20), 1);
343 map.Emplace(AddressRange(20, 30), 2);
344 map.Emplace(AddressRange(35, 40), 3);
345 map.Emplace(AddressRange(40, 50), 4);
346
347 MockFunction<void(AddressRangeMap<int>::value_type&)> cb;
348 EXPECT_CALL(cb, Call(Pair(AddressRange(10, 20), 1)));
349 EXPECT_CALL(cb, Call(Pair(AddressRange(20, 30), 2)));
350 EXPECT_CALL(cb, Call(Pair(AddressRange(35, 40), 3)));
351
352 map.ForOverlaps(AddressRange(15, 36), cb.AsStdFunction());
353 }
354
TEST(AddressSet,Empty)355 TEST(AddressSet, Empty) {
356 AddressSet empty;
357 EXPECT_THAT(empty, ElementsAre());
358 }
359
TEST(AddressSet,EmptyRangesAreNotAdded)360 TEST(AddressSet, EmptyRangesAreNotAdded) {
361 AddressSet empty;
362
363 empty.Add({0, 0});
364 empty.Add({10, 10});
365
366 EXPECT_THAT(empty, ElementsAre());
367 }
368
TEST(AddressSet,NonOverlapingNonContiguousAreNotMerged)369 TEST(AddressSet, NonOverlapingNonContiguousAreNotMerged) {
370 AddressSet set;
371 set.Add({0, 10});
372 set.Add({11, 20});
373
374 EXPECT_THAT(set, ElementsAre(AddressRange(0, 10), AddressRange(11, 20)));
375 }
376
TEST(AddressSet,ContiguousAreMerged)377 TEST(AddressSet, ContiguousAreMerged) {
378 AddressSet set;
379 set.Add({0, 10});
380 set.Add({30, 40});
381 set.Add({10, 30});
382
383 EXPECT_THAT(set, ElementsAre(AddressRange(0, 40)));
384 }
385
TEST(AddressSet,OverlapsAreMerged)386 TEST(AddressSet, OverlapsAreMerged) {
387 AddressSet set;
388 set.Add({0, 10});
389 set.Add({30, 40});
390 set.Add({5, 35});
391
392 EXPECT_THAT(set, ElementsAre(AddressRange(0, 40)));
393 }
394
TEST(AddressSet,SpliceRemove)395 TEST(AddressSet, SpliceRemove) {
396 AddressSet set;
397 set.Add({0, 10});
398 set.Remove({2, 5});
399
400 EXPECT_THAT(set, ElementsAre(AddressRange(0, 2), AddressRange(5, 10)));
401 }
402
TEST(AddressSet,PartialRemove)403 TEST(AddressSet, PartialRemove) {
404 AddressSet set;
405 set.Add({0, 10});
406 set.Remove({0, 2});
407 set.Remove({8, 10});
408
409 EXPECT_THAT(set, ElementsAre(AddressRange(2, 8)));
410 }
411
TEST(AddressSet,MultipleRemove)412 TEST(AddressSet, MultipleRemove) {
413 AddressSet set;
414 set.Add({0, 10});
415 set.Add({12, 15});
416 set.Add({20, 30});
417 set.Remove({5, 25});
418
419 EXPECT_THAT(set, ElementsAre(AddressRange(0, 5), AddressRange(25, 30)));
420 }
421
TEST(AddressSet,RemoveEmptyRangeDoesNothing)422 TEST(AddressSet, RemoveEmptyRangeDoesNothing) {
423 AddressSet set;
424 set.Add({0, 10});
425 set.Add({20, 30});
426
427 set.Remove({0, 0});
428 set.Remove({2, 2});
429 set.Remove({10, 10});
430 set.Remove({11, 11});
431
432 EXPECT_THAT(set, ElementsAre(AddressRange(0, 10), AddressRange(20, 30)));
433 }
434
435 } // namespace
436 } // namespace trace_processor
437 } // namespace perfetto
438