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
58 template <typename Value>
MapEntry(uint64_t start,uint64_t end,Value value)59 auto MapEntry(uint64_t start, uint64_t end, Value value) {
60 return Pair(AddressRange(start, end), value);
61 }
62
AppendRangesTo(std::vector<AddressRange> & ranges)63 auto AppendRangesTo(std::vector<AddressRange>& ranges) {
64 return [&ranges](std::pair<const AddressRange, int>& e) {
65 ranges.push_back(e.first);
66 };
67 }
68
TEST(AddressRange,EmptyByDefault)69 TEST(AddressRange, EmptyByDefault) {
70 constexpr AddressRange kRange;
71 // This is more of an implementation detail (that start and end are
72 // initialized to zero). But this "knowledge" is used for the contains tests,
73 // to probe for those specific values.
74 EXPECT_THAT(kRange.end(), Eq(0u));
75 EXPECT_THAT(kRange.start(), Eq(0u));
76 EXPECT_THAT(kRange.length(), Eq(0u));
77 EXPECT_THAT(kRange, IsEmpty());
78 }
79
TEST(AddressRange,EmptyRangeContainsNothing)80 TEST(AddressRange, EmptyRangeContainsNothing) {
81 constexpr AddressRange kEmptyRange;
82 EXPECT_FALSE(kEmptyRange.Contains(0));
83 }
84
TEST(AddressRange,ContainsAddress)85 TEST(AddressRange, ContainsAddress) {
86 constexpr AddressRange kRange(1, 10);
87 EXPECT_FALSE(kRange.Contains(0));
88 EXPECT_TRUE(kRange.Contains(1));
89 EXPECT_TRUE(kRange.Contains(9));
90 EXPECT_FALSE(kRange.Contains(10));
91 }
92
TEST(AddressRange,MaxRangeContainsAll)93 TEST(AddressRange, MaxRangeContainsAll) {
94 constexpr AddressRange kMaxRange(0, std::numeric_limits<uint64_t>::max());
95 EXPECT_TRUE(kMaxRange.Contains(0));
96 EXPECT_TRUE(kMaxRange.Contains(std::numeric_limits<uint64_t>::max() - 1));
97 // End is not inclusive.
98 EXPECT_FALSE(kMaxRange.Contains(std::numeric_limits<uint64_t>::max()));
99 }
100
TEST(AddressRange,ContainsRange)101 TEST(AddressRange, ContainsRange) {
102 constexpr AddressRange kRange(10, 20);
103 EXPECT_TRUE(kRange.Contains(kRange));
104 EXPECT_TRUE(kRange.Contains(AddressRange(11, 19)));
105 EXPECT_TRUE(kRange.Contains(AddressRange(10, 19)));
106 EXPECT_TRUE(kRange.Contains(AddressRange(11, 20)));
107
108 EXPECT_FALSE(kRange.Contains(AddressRange(9, 20)));
109 EXPECT_FALSE(kRange.Contains(AddressRange(10, 21)));
110 EXPECT_FALSE(kRange.Contains(AddressRange(9, 10)));
111 EXPECT_FALSE(kRange.Contains(AddressRange(20, 21)));
112 }
113
TEST(AddressRange,Intersect)114 TEST(AddressRange, Intersect) {
115 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(0, 10)),
116 Eq(AddressRange(0, 10)));
117
118 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(10, 20)),
119 IsEmpty());
120
121 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(0, 0)),
122 Eq(AddressRange(0, 0)));
123 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange(1, 10)),
124 Eq(AddressRange(1, 10)));
125
126 EXPECT_THAT(AddressRange(0, 10).IntersectWith(AddressRange()), IsEmpty());
127 }
128
TEST(AddressRange,Overlap)129 TEST(AddressRange, Overlap) {
130 EXPECT_FALSE(AddressRange(0, 10).Overlaps(AddressRange(5, 5)));
131 EXPECT_FALSE(AddressRange(5, 5).Overlaps(AddressRange(0, 10)));
132 EXPECT_FALSE(AddressRange(0, 10).Overlaps(AddressRange(10, 20)));
133 EXPECT_FALSE(AddressRange(10, 20).Overlaps(AddressRange(0, 10)));
134
135 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(9, 10)));
136 EXPECT_TRUE(AddressRange(10, 20).Overlaps(AddressRange(0, 11)));
137 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(5, 6)));
138 EXPECT_TRUE(AddressRange(0, 10).Overlaps(AddressRange(5, 20)));
139 }
140
TEST(AddressRangeMap,Empty)141 TEST(AddressRangeMap, Empty) {
142 AddressRangeMap<int> empty;
143 EXPECT_THAT(empty, IsEmpty());
144 }
145
TEST(AddressRangeMap,EmplaceFailsForOverlaps)146 TEST(AddressRangeMap, EmplaceFailsForOverlaps) {
147 AddressRangeMap<int> map;
148 ASSERT_TRUE(map.Emplace(AddressRange(10, 20), 42));
149
150 EXPECT_FALSE(map.Emplace(AddressRange(10, 20)));
151 EXPECT_FALSE(map.Emplace(AddressRange(11, 19)));
152 EXPECT_FALSE(map.Emplace(AddressRange(0, 11)));
153 EXPECT_FALSE(map.Emplace(AddressRange(19, 30)));
154 EXPECT_THAT(map, ElementsAre(MapEntry(10, 20, 42)));
155 }
156
TEST(AddressRangeMap,EmplaceSucceedsForNonOverlaps)157 TEST(AddressRangeMap, EmplaceSucceedsForNonOverlaps) {
158 AddressRangeMap<int> map;
159
160 EXPECT_TRUE(map.Emplace(AddressRange(10, 20)));
161 EXPECT_TRUE(map.Emplace(AddressRange(0, 10)));
162 EXPECT_TRUE(map.Emplace(AddressRange(20, 30)));
163
164 EXPECT_THAT(map, SizeIs(3));
165 }
166
TEST(AddressRangeMap,EmplaceFailsForEmptyRange)167 TEST(AddressRangeMap, EmplaceFailsForEmptyRange) {
168 AddressRangeMap<int> map;
169
170 EXPECT_FALSE(map.Emplace(AddressRange(0, 0)));
171 EXPECT_FALSE(map.Emplace(AddressRange(100, 100)));
172
173 EXPECT_THAT(map, IsEmpty());
174 }
175
TEST(AddressRangeMap,DeleteOverlapsAndEmplaceFailsForEmptyRange)176 TEST(AddressRangeMap, DeleteOverlapsAndEmplaceFailsForEmptyRange) {
177 AddressRangeMap<int> map;
178 EXPECT_TRUE(map.Emplace(AddressRange(0, 10), 42));
179 EXPECT_FALSE(map.Emplace(AddressRange(0, 0)));
180 EXPECT_FALSE(map.Emplace(AddressRange(100, 100)));
181
182 EXPECT_THAT(map, ElementsAre(MapEntry(0, 10, 42)));
183 }
184
TEST(AddressRangeMap,FindAddress)185 TEST(AddressRangeMap, FindAddress) {
186 AddressRangeMap<int> map;
187 map.Emplace(AddressRange(0, 10), 0);
188 map.Emplace(AddressRange(10, 20), 1);
189 map.Emplace(AddressRange(25, 30), 2);
190
191 ASSERT_THAT(map.Find(0), Ne(map.end()));
192 EXPECT_THAT(map.Find(0)->second, Eq(0));
193
194 ASSERT_THAT(map.Find(9), Ne(map.end()));
195 EXPECT_THAT(map.Find(9)->second, Eq(0));
196
197 ASSERT_THAT(map.Find(10), Ne(map.end()));
198 EXPECT_THAT(map.Find(10)->second, Eq(1));
199
200 ASSERT_THAT(map.Find(10), Ne(map.end()));
201 EXPECT_THAT(map.Find(19)->second, Eq(1));
202
203 EXPECT_THAT(map.Find(20), Eq(map.end()));
204
205 EXPECT_THAT(map.Find(24), Eq(map.end()));
206
207 ASSERT_THAT(map.Find(25), Ne(map.end()));
208 EXPECT_THAT(map.Find(25)->second, Eq(2));
209
210 ASSERT_THAT(map.Find(29), Ne(map.end()));
211 EXPECT_THAT(map.Find(29)->second, Eq(2));
212
213 EXPECT_THAT(map.Find(30), Eq(map.end()));
214 }
215
TEST(AddressRangeMap,FindRangeThatContains)216 TEST(AddressRangeMap, FindRangeThatContains) {
217 AddressRangeMap<int> map;
218 map.Emplace(AddressRange(0, 10), 0);
219 map.Emplace(AddressRange(10, 20), 1);
220 map.Emplace(AddressRange(25, 30), 2);
221
222 auto match_1 = IteratorPointsTo(map, MapEntry(0, 10, 0));
223 auto match_2 = IteratorPointsTo(map, MapEntry(10, 20, 1));
224 auto match_3 = IteratorPointsTo(map, MapEntry(25, 30, 2));
225
226 EXPECT_THAT(map.FindRangeThatContains({0, 10}), match_1);
227 EXPECT_THAT(map.FindRangeThatContains({0, 1}), match_1);
228 EXPECT_THAT(map.FindRangeThatContains({3, 4}), match_1);
229 EXPECT_THAT(map.FindRangeThatContains({9, 10}), match_1);
230
231 EXPECT_THAT(map.FindRangeThatContains({10, 11}), match_2);
232 EXPECT_THAT(map.FindRangeThatContains({11, 12}), match_2);
233 EXPECT_THAT(map.FindRangeThatContains({19, 20}), match_2);
234 EXPECT_THAT(map.FindRangeThatContains({10, 20}), match_2);
235
236 EXPECT_THAT(map.FindRangeThatContains({25, 26}), match_3);
237 EXPECT_THAT(map.FindRangeThatContains({26, 27}), match_3);
238 EXPECT_THAT(map.FindRangeThatContains({29, 30}), match_3);
239 EXPECT_THAT(map.FindRangeThatContains({25, 30}), match_3);
240
241 EXPECT_THAT(map.FindRangeThatContains({9, 11}), Eq(map.end()));
242 EXPECT_THAT(map.FindRangeThatContains({20, 21}), Eq(map.end()));
243 EXPECT_THAT(map.FindRangeThatContains({24, 25}), Eq(map.end()));
244 EXPECT_THAT(map.FindRangeThatContains({14, 27}), Eq(map.end()));
245 }
246
TEST(AddressRangeMap,TrimOverlapsAndEmplace)247 TEST(AddressRangeMap, TrimOverlapsAndEmplace) {
248 const AddressRangeMap<int> entries = []() {
249 AddressRangeMap<int> map;
250 map.Emplace(AddressRange(0, 10), 0);
251 map.Emplace(AddressRange(10, 20), 1);
252 map.Emplace(AddressRange(25, 30), 2);
253 return map;
254 }();
255
256 {
257 AddressRangeMap<int> map = entries;
258 map.TrimOverlapsAndEmplace({30, 100}, 5);
259 EXPECT_THAT(map, ElementsAre(MapEntry(0, 10, 0), MapEntry(10, 20, 1),
260 MapEntry(25, 30, 2), MapEntry(30, 100, 5)));
261 }
262
263 {
264 AddressRangeMap<int> map = entries;
265 map.TrimOverlapsAndEmplace({9, 10}, 5);
266 EXPECT_THAT(map, ElementsAre(MapEntry(0, 9, 0), MapEntry(9, 10, 5),
267 MapEntry(10, 20, 1), MapEntry(25, 30, 2)));
268 }
269
270 {
271 AddressRangeMap<int> map = entries;
272 map.TrimOverlapsAndEmplace({5, 11}, 5);
273 EXPECT_THAT(map, ElementsAre(MapEntry(0, 5, 0), MapEntry(5, 11, 5),
274 MapEntry(11, 20, 1), MapEntry(25, 30, 2)));
275 }
276
277 {
278 AddressRangeMap<int> map = entries;
279 map.TrimOverlapsAndEmplace({5, 25}, 5);
280 EXPECT_THAT(map, ElementsAre(MapEntry(0, 5, 0), MapEntry(5, 25, 5),
281 MapEntry(25, 30, 2)));
282 }
283
284 {
285 AddressRangeMap<int> map = entries;
286 map.TrimOverlapsAndEmplace({5, 31}, 5);
287 EXPECT_THAT(map, ElementsAre(MapEntry(0, 5, 0), MapEntry(5, 31, 5)));
288 }
289
290 {
291 AddressRangeMap<int> map = entries;
292 map.TrimOverlapsAndEmplace({0, 100}, 5);
293 EXPECT_THAT(map, ElementsAre(MapEntry(0, 100, 5)));
294 }
295
296 {
297 AddressRangeMap<int> map = entries;
298 map.TrimOverlapsAndEmplace({3, 7}, 5);
299 EXPECT_THAT(map, ElementsAre(MapEntry(0, 3, 0), MapEntry(3, 7, 5),
300 MapEntry(7, 10, 0), MapEntry(10, 20, 1),
301 MapEntry(25, 30, 2)));
302 }
303 }
304
TEST(AddressRangeMap,DeleteOverlapsAndEmplace)305 TEST(AddressRangeMap, DeleteOverlapsAndEmplace) {
306 const AddressRangeMap<int> entries = []() {
307 AddressRangeMap<int> map;
308 map.Emplace(AddressRange(0, 10), 0);
309 map.Emplace(AddressRange(10, 20), 1);
310 map.Emplace(AddressRange(25, 30), 2);
311 return map;
312 }();
313
314 {
315 AddressRangeMap<int> map = entries;
316 std::vector<AddressRange> deleted;
317 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {30, 100}, 5);
318 EXPECT_THAT(deleted, ElementsAre());
319 EXPECT_THAT(map, ElementsAre(MapEntry(0, 10, 0), MapEntry(10, 20, 1),
320 MapEntry(25, 30, 2), MapEntry(30, 100, 5)));
321 }
322
323 {
324 AddressRangeMap<int> map = entries;
325 std::vector<AddressRange> deleted;
326 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {9, 10}, 5);
327 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10)));
328 EXPECT_THAT(map, ElementsAre(MapEntry(9, 10, 5), MapEntry(10, 20, 1),
329 MapEntry(25, 30, 2)));
330 }
331
332 {
333 AddressRangeMap<int> map = entries;
334 std::vector<AddressRange> deleted;
335 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 11}, 5);
336 EXPECT_THAT(deleted,
337 ElementsAre(AddressRange(0, 10), AddressRange(10, 20)));
338 EXPECT_THAT(map, ElementsAre(MapEntry(5, 11, 5), MapEntry(25, 30, 2)));
339 }
340
341 {
342 AddressRangeMap<int> map = entries;
343 std::vector<AddressRange> deleted;
344 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 25}, 5);
345 EXPECT_THAT(deleted,
346 ElementsAre(AddressRange(0, 10), AddressRange(10, 20)));
347 EXPECT_THAT(map, ElementsAre(MapEntry(5, 25, 5), MapEntry(25, 30, 2)));
348 }
349
350 {
351 AddressRangeMap<int> map = entries;
352 std::vector<AddressRange> deleted;
353 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {5, 31}, 5);
354 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10), AddressRange(10, 20),
355 AddressRange(25, 30)));
356 EXPECT_THAT(map, ElementsAre(MapEntry(5, 31, 5)));
357 }
358
359 {
360 AddressRangeMap<int> map = entries;
361 std::vector<AddressRange> deleted;
362 map.DeleteOverlapsAndEmplace(AppendRangesTo(deleted), {0, 100}, 5);
363 EXPECT_THAT(deleted, ElementsAre(AddressRange(0, 10), AddressRange(10, 20),
364 AddressRange(25, 30)));
365 EXPECT_THAT(map, ElementsAre(MapEntry(0, 100, 5)));
366 }
367 }
368
TEST(AddressRangeMap,ForOverlapsEmptyRangeDoesNothing)369 TEST(AddressRangeMap, ForOverlapsEmptyRangeDoesNothing) {
370 AddressRangeMap<int> map;
371 map.Emplace(AddressRange(0, 10), 0);
372 map.Emplace(AddressRange(10, 20), 1);
373 map.Emplace(AddressRange(25, 30), 2);
374
375 MockFunction<void(AddressRangeMap<int>::value_type&)> cb;
376 EXPECT_CALL(cb, Call).Times(0);
377
378 map.ForOverlaps(AddressRange(5, 5), cb.AsStdFunction());
379 }
380
TEST(AddressRangeMap,ForOverlaps)381 TEST(AddressRangeMap, ForOverlaps) {
382 AddressRangeMap<int> map;
383 map.Emplace(AddressRange(0, 10), 0);
384 map.Emplace(AddressRange(10, 20), 1);
385 map.Emplace(AddressRange(20, 30), 2);
386 map.Emplace(AddressRange(35, 40), 3);
387 map.Emplace(AddressRange(40, 50), 4);
388
389 MockFunction<void(AddressRangeMap<int>::value_type&)> cb;
390 EXPECT_CALL(cb, Call(MapEntry(10, 20, 1)));
391 EXPECT_CALL(cb, Call(MapEntry(20, 30, 2)));
392 EXPECT_CALL(cb, Call(MapEntry(35, 40, 3)));
393
394 map.ForOverlaps(AddressRange(15, 36), cb.AsStdFunction());
395 }
396
TEST(AddressSet,Empty)397 TEST(AddressSet, Empty) {
398 AddressSet empty;
399 EXPECT_THAT(empty, ElementsAre());
400 }
401
TEST(AddressSet,EmptyRangesAreNotAdded)402 TEST(AddressSet, EmptyRangesAreNotAdded) {
403 AddressSet empty;
404
405 empty.Add({0, 0});
406 empty.Add({10, 10});
407
408 EXPECT_THAT(empty, ElementsAre());
409 }
410
TEST(AddressSet,NonOverlapingNonContiguousAreNotMerged)411 TEST(AddressSet, NonOverlapingNonContiguousAreNotMerged) {
412 AddressSet set;
413 set.Add({0, 10});
414 set.Add({11, 20});
415
416 EXPECT_THAT(set, ElementsAre(AddressRange(0, 10), AddressRange(11, 20)));
417 }
418
TEST(AddressSet,ContiguousAreMerged)419 TEST(AddressSet, ContiguousAreMerged) {
420 AddressSet set;
421 set.Add({0, 10});
422 set.Add({30, 40});
423 set.Add({10, 30});
424
425 EXPECT_THAT(set, ElementsAre(AddressRange(0, 40)));
426 }
427
TEST(AddressSet,OverlapsAreMerged)428 TEST(AddressSet, OverlapsAreMerged) {
429 AddressSet set;
430 set.Add({0, 10});
431 set.Add({30, 40});
432 set.Add({5, 35});
433
434 EXPECT_THAT(set, ElementsAre(AddressRange(0, 40)));
435 }
436
TEST(AddressSet,SpliceRemove)437 TEST(AddressSet, SpliceRemove) {
438 AddressSet set;
439 set.Add({0, 10});
440 set.Remove({2, 5});
441
442 EXPECT_THAT(set, ElementsAre(AddressRange(0, 2), AddressRange(5, 10)));
443 }
444
TEST(AddressSet,PartialRemove)445 TEST(AddressSet, PartialRemove) {
446 AddressSet set;
447 set.Add({0, 10});
448 set.Remove({0, 2});
449 set.Remove({8, 10});
450
451 EXPECT_THAT(set, ElementsAre(AddressRange(2, 8)));
452 }
453
TEST(AddressSet,MultipleRemove)454 TEST(AddressSet, MultipleRemove) {
455 AddressSet set;
456 set.Add({0, 10});
457 set.Add({12, 15});
458 set.Add({20, 30});
459 set.Remove({5, 25});
460
461 EXPECT_THAT(set, ElementsAre(AddressRange(0, 5), AddressRange(25, 30)));
462 }
463
TEST(AddressSet,RemoveEmptyRangeDoesNothing)464 TEST(AddressSet, RemoveEmptyRangeDoesNothing) {
465 AddressSet set;
466 set.Add({0, 10});
467 set.Add({20, 30});
468
469 set.Remove({0, 0});
470 set.Remove({2, 2});
471 set.Remove({10, 10});
472 set.Remove({11, 11});
473
474 EXPECT_THAT(set, ElementsAre(AddressRange(0, 10), AddressRange(20, 30)));
475 }
476
477 } // namespace
478 } // namespace trace_processor
479 } // namespace perfetto
480