1 // Copyright 2018 The Crashpad Authors. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "util/misc/range_set.h"
16
17 #include <sys/types.h>
18
19 #include <memory>
20
21 #include "base/format_macros.h"
22 #include "base/strings/stringprintf.h"
23 #include "gtest/gtest.h"
24 #include "util/misc/address_types.h"
25 #include "util/misc/from_pointer_cast.h"
26
27 namespace crashpad {
28 namespace test {
29 namespace {
30
ExpectRangeIsContained(const RangeSet & ranges,VMAddress base,VMSize size)31 void ExpectRangeIsContained(const RangeSet& ranges,
32 VMAddress base,
33 VMSize size) {
34 for (VMAddress addr = base; addr < base + size; ++addr) {
35 SCOPED_TRACE(base::StringPrintf("0x%" PRIx64 " in range 0x%" PRIx64
36 ":0x%" PRIx64,
37 addr,
38 base,
39 base + size));
40 EXPECT_TRUE(ranges.Contains(addr));
41 }
42 }
43
TEST(RangeSet,Basic)44 TEST(RangeSet, Basic) {
45 RangeSet ranges;
46 auto base = FromPointerCast<VMAddress>(&ranges);
47 VMSize size = sizeof(ranges);
48 ranges.Insert(base, size);
49 ExpectRangeIsContained(ranges, base, size);
50 EXPECT_FALSE(ranges.Contains(base - 1));
51 EXPECT_FALSE(ranges.Contains(base + size));
52 }
53
TEST(RangeSet,ZeroSizedRange)54 TEST(RangeSet, ZeroSizedRange) {
55 RangeSet ranges;
56 auto addr = FromPointerCast<VMAddress>(&ranges);
57 ranges.Insert(addr, 0);
58 EXPECT_FALSE(ranges.Contains(addr));
59 }
60
TEST(RangeSet,DuplicateRanges)61 TEST(RangeSet, DuplicateRanges) {
62 RangeSet ranges;
63 auto base = FromPointerCast<VMAddress>(&ranges);
64 VMSize size = sizeof(ranges);
65 ranges.Insert(base, size);
66 ranges.Insert(base, size);
67 ExpectRangeIsContained(ranges, base, size);
68 }
69
TEST(RangeSet,OverlappingRanges)70 TEST(RangeSet, OverlappingRanges) {
71 RangeSet ranges;
72 ranges.Insert(37, 16);
73 ranges.Insert(9, 9);
74 ranges.Insert(17, 42);
75
76 EXPECT_TRUE(ranges.Contains(9));
77 EXPECT_TRUE(ranges.Contains(17));
78 EXPECT_TRUE(ranges.Contains(36));
79 EXPECT_TRUE(ranges.Contains(37));
80 EXPECT_TRUE(ranges.Contains(52));
81 EXPECT_TRUE(ranges.Contains(58));
82 }
83
TEST(RangeSet,SubRangeInLargeRange)84 TEST(RangeSet, SubRangeInLargeRange) {
85 constexpr size_t kBufferSize = 2 << 22;
86 auto buf = std::make_unique<char[]>(kBufferSize);
87
88 RangeSet ranges;
89 auto addr = FromPointerCast<VMAddress>(buf.get());
90
91 ranges.Insert(addr, kBufferSize);
92 EXPECT_TRUE(ranges.Contains(addr));
93 EXPECT_TRUE(ranges.Contains(addr + kBufferSize - 1));
94
95 ranges.Insert(addr, kBufferSize / 2);
96 EXPECT_TRUE(ranges.Contains(addr));
97 EXPECT_TRUE(ranges.Contains(addr + kBufferSize / 2 - 1));
98 EXPECT_TRUE(ranges.Contains(addr + kBufferSize - 1));
99 }
100
TEST(RangeSet,LargeOverlappingRanges)101 TEST(RangeSet, LargeOverlappingRanges) {
102 constexpr size_t kBufferSize = 2 << 23;
103 auto buf = std::make_unique<char[]>(kBufferSize);
104
105 RangeSet ranges;
106 auto addr = FromPointerCast<VMAddress>(buf.get());
107
108 ranges.Insert(addr, 3 * kBufferSize / 4);
109 ranges.Insert(addr + kBufferSize / 4, 3 * kBufferSize / 4);
110 EXPECT_TRUE(ranges.Contains(addr));
111 EXPECT_TRUE(ranges.Contains(addr + kBufferSize - 1));
112 }
113
114 } // namespace
115 } // namespace test
116 } // namespace crashpad
117