1 // Copyright 2019 Google LLC
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above
10 // copyright notice, this list of conditions and the following disclaimer
11 // in the documentation and/or other materials provided with the
12 // distribution.
13 // * Neither the name of Google LLC nor the names of its
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 #ifdef HAVE_CONFIG_H
30 #include <config.h> // Must come first
31 #endif
32
33 #include <limits.h>
34 #include <stdio.h>
35
36 #include "processor/range_map-inl.h"
37
38 #include "breakpad_googletest_includes.h"
39 #include "processor/linked_ptr.h"
40 #include "processor/logging.h"
41
42 namespace {
43
44 using google_breakpad::linked_ptr;
45 using google_breakpad::MergeRangeStrategy;
46 using google_breakpad::RangeMap;
47
48 // A CountedObject holds an int. A global (not thread safe!) count of
49 // allocated CountedObjects is maintained to help test memory management.
50 class CountedObject {
51 public:
CountedObject(int id)52 explicit CountedObject(int id) : id_(id) { ++count_; }
~CountedObject()53 ~CountedObject() { --count_; }
54
count()55 static int count() { return count_; }
id() const56 int id() const { return id_; }
57
58 private:
59 static int count_;
60 int id_;
61 };
62
63 int CountedObject::count_;
64
65 typedef int AddressType;
66 typedef RangeMap<AddressType, linked_ptr<CountedObject>> TestMap;
67
68 // Same range cannot be stored wice.
TEST(RangeMapTruncateLower,SameRange)69 TEST(RangeMapTruncateLower, SameRange) {
70 TestMap range_map;
71 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
72 linked_ptr<CountedObject> object_1(new CountedObject(1));
73 EXPECT_TRUE(
74 range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
75
76 // Same range cannot be stored wice.
77 linked_ptr<CountedObject> object_2(new CountedObject(2));
78 EXPECT_FALSE(
79 range_map.StoreRange(0 /* base address */, 100 /* size */, object_2));
80 }
81
82 // If a range is completely contained by another range, then the larger range
83 // should be truncated.
TEST(RangeMapTruncateLower,CompletelyContained)84 TEST(RangeMapTruncateLower, CompletelyContained) {
85 TestMap range_map;
86 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
87 // Larger range is added first.
88 linked_ptr<CountedObject> object_1(new CountedObject(1));
89 EXPECT_TRUE(
90 range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
91 // Smaller (contained) range is added second.
92 linked_ptr<CountedObject> object_2(new CountedObject(2));
93 EXPECT_TRUE(
94 range_map.StoreRange(10 /* base address */, 80 /* size */, object_2));
95 linked_ptr<CountedObject> object;
96 AddressType retrieved_base = AddressType();
97 AddressType retrieved_delta = AddressType();
98 AddressType retrieved_size = AddressType();
99 // The first range contains the second, so the first range should have been
100 // shrunk to [0, 10]. Range [90, 99] should be free.
101 EXPECT_FALSE(range_map.RetrieveRange(90, &object, &retrieved_base,
102 &retrieved_delta, &retrieved_size));
103 EXPECT_FALSE(range_map.RetrieveRange(99, &object, &retrieved_base,
104 &retrieved_delta, &retrieved_size));
105 EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
106 &retrieved_delta, &retrieved_size));
107 EXPECT_EQ(1, object->id());
108 EXPECT_EQ(0, retrieved_base);
109 EXPECT_EQ(0, retrieved_delta);
110 EXPECT_EQ(10, retrieved_size);
111 // Validate the properties of the smaller range (should be untouched).
112 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
113 &retrieved_delta, &retrieved_size));
114 EXPECT_EQ(2, object->id());
115 EXPECT_EQ(10, retrieved_base);
116 EXPECT_EQ(0, retrieved_delta);
117 EXPECT_EQ(80, retrieved_size);
118 }
119
120 // Same as the previous test, however the larger range is added second.
TEST(RangeMapTruncateLower,CompletelyContained_LargerAddedSecond)121 TEST(RangeMapTruncateLower, CompletelyContained_LargerAddedSecond) {
122 TestMap range_map;
123 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
124 // Smaller (contained) range is added first.
125 linked_ptr<CountedObject> object_1(new CountedObject(1));
126 EXPECT_TRUE(
127 range_map.StoreRange(10 /* base address */, 80 /* size */, object_1));
128 // Larger range is added second.
129 linked_ptr<CountedObject> object_2(new CountedObject(2));
130 EXPECT_TRUE(
131 range_map.StoreRange(0 /* base address */, 100 /* size */, object_2));
132 linked_ptr<CountedObject> object;
133 AddressType retrieved_base = AddressType();
134 AddressType retrieved_delta = AddressType();
135 AddressType retrieved_size = AddressType();
136 // The second range contains the first, so the second range should have been
137 // truncated to [0, 9]. Range [90, 99] should be free.
138 EXPECT_FALSE(range_map.RetrieveRange(90, &object, &retrieved_base,
139 &retrieved_delta, &retrieved_size));
140 EXPECT_FALSE(range_map.RetrieveRange(99, &object, &retrieved_base,
141 &retrieved_delta, &retrieved_size));
142 EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
143 &retrieved_delta, &retrieved_size));
144 EXPECT_EQ(2, object->id());
145 EXPECT_EQ(0, retrieved_base);
146 EXPECT_EQ(0, retrieved_delta);
147 EXPECT_EQ(10, retrieved_size);
148 // Validate the properties of the smaller range (should be untouched).
149 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
150 &retrieved_delta, &retrieved_size));
151 EXPECT_EQ(1, object->id());
152 EXPECT_EQ(10, retrieved_base);
153 EXPECT_EQ(0, retrieved_delta);
154 EXPECT_EQ(80, retrieved_size);
155 }
156
TEST(RangeMapTruncateLower,PartialOverlap_AtBeginning)157 TEST(RangeMapTruncateLower, PartialOverlap_AtBeginning) {
158 TestMap range_map;
159 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
160 linked_ptr<CountedObject> object_1(new CountedObject(1));
161 EXPECT_TRUE(
162 range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
163
164 // Partial overlap at the beginning of the new range.
165 linked_ptr<CountedObject> object_2(new CountedObject(2));
166 EXPECT_TRUE(
167 range_map.StoreRange(90 /* base address */, 110 /* size */, object_2));
168
169 linked_ptr<CountedObject> object;
170 AddressType retrieved_base = AddressType();
171 AddressType retrieved_delta = AddressType();
172 AddressType retrieved_size = AddressType();
173 // The first range should be truncated, so 99 should address the second range.
174 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
175 &retrieved_delta, &retrieved_size));
176 EXPECT_EQ(2, object->id());
177 EXPECT_EQ(90, retrieved_base);
178 EXPECT_EQ(0, retrieved_delta);
179 EXPECT_EQ(110, retrieved_size);
180 // Validate the properties of the truncated range.
181 EXPECT_TRUE(range_map.RetrieveRange(89, &object, &retrieved_base,
182 &retrieved_delta, &retrieved_size));
183 EXPECT_EQ(1, object->id());
184 EXPECT_EQ(0, retrieved_base);
185 EXPECT_EQ(0, retrieved_delta);
186 EXPECT_EQ(90, retrieved_size);
187 }
188
TEST(RangeMapTruncateLower,PartialOverlap_AtEnd)189 TEST(RangeMapTruncateLower, PartialOverlap_AtEnd) {
190 TestMap range_map;
191 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
192 linked_ptr<CountedObject> object_1(new CountedObject(1));
193 EXPECT_TRUE(
194 range_map.StoreRange(50 /* base address */, 50 /* size */, object_1));
195
196 // Partial overlap at the end of the new range.
197 linked_ptr<CountedObject> object_2(new CountedObject(2));
198 EXPECT_TRUE(
199 range_map.StoreRange(0 /* base address */, 70 /* size */, object_2));
200
201 linked_ptr<CountedObject> object;
202 AddressType retrieved_base = AddressType();
203 AddressType retrieved_delta = AddressType();
204 AddressType retrieved_size = AddressType();
205 // The second range should be truncated so 69 addresses the first range.
206 EXPECT_TRUE(range_map.RetrieveRange(69, &object, &retrieved_base,
207 &retrieved_delta, &retrieved_size));
208 EXPECT_EQ(1, object->id());
209 EXPECT_EQ(50, retrieved_base);
210 EXPECT_EQ(0, retrieved_delta);
211 EXPECT_EQ(50, retrieved_size);
212 // Validate the properties of the truncated range.
213 EXPECT_TRUE(range_map.RetrieveRange(49, &object, &retrieved_base,
214 &retrieved_delta, &retrieved_size));
215 EXPECT_EQ(2, object->id());
216 EXPECT_EQ(0, retrieved_base);
217 EXPECT_EQ(0, retrieved_delta);
218 EXPECT_EQ(50, retrieved_size);
219 }
220
221 // A new range is overlapped at both ends. The new range and the range
222 // that overlaps at the beginning should be truncated. The range that overlaps
223 // at the end should be left untouched.
TEST(RangeMapTruncateLower,OverlapAtBothEnds)224 TEST(RangeMapTruncateLower, OverlapAtBothEnds) {
225 TestMap range_map;
226 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
227 // This should overlap object_3 at the beginning.
228 linked_ptr<CountedObject> object_1(new CountedObject(1));
229 EXPECT_TRUE(
230 range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
231
232 // This should overlap object_3 at the end.
233 linked_ptr<CountedObject> object_2(new CountedObject(2));
234 EXPECT_TRUE(
235 range_map.StoreRange(100 /* base address */, 100 /* size */, object_2));
236
237 // This should be overlapped on both ends by object_1 and object_2.
238 linked_ptr<CountedObject> object_3(new CountedObject(3));
239 EXPECT_TRUE(
240 range_map.StoreRange(50 /* base address */, 100 /* size */, object_3));
241
242 linked_ptr<CountedObject> object;
243 AddressType retrieved_base = AddressType();
244 AddressType retrieved_delta = AddressType();
245 AddressType retrieved_size = AddressType();
246 // The first range should be truncated.
247 EXPECT_TRUE(range_map.RetrieveRange(0, &object, &retrieved_base,
248 &retrieved_delta, &retrieved_size));
249 EXPECT_EQ(1, object->id());
250 EXPECT_EQ(0, retrieved_base);
251 EXPECT_EQ(0, retrieved_delta);
252 EXPECT_EQ(50, retrieved_size);
253 // The second range should be intact.
254 EXPECT_TRUE(range_map.RetrieveRange(150, &object, &retrieved_base,
255 &retrieved_delta, &retrieved_size));
256 EXPECT_EQ(2, object->id());
257 EXPECT_EQ(100, retrieved_base);
258 EXPECT_EQ(0, retrieved_delta);
259 EXPECT_EQ(100, retrieved_size);
260 // The third range (in the middle) should be truncated.
261 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
262 &retrieved_delta, &retrieved_size));
263 EXPECT_EQ(3, object->id());
264 EXPECT_EQ(50, retrieved_base);
265 EXPECT_EQ(0, retrieved_delta);
266 EXPECT_EQ(50, retrieved_size);
267 }
268
TEST(RangeMapTruncateLower,MultipleConflicts)269 TEST(RangeMapTruncateLower, MultipleConflicts) {
270 TestMap range_map;
271 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
272 // This should overlap with object_3.
273 linked_ptr<CountedObject> object_1(new CountedObject(1));
274 EXPECT_TRUE(
275 range_map.StoreRange(10 /* base address */, 90 /* size */, object_1));
276
277 // This should also overlap with object_3 but after object_1.
278 linked_ptr<CountedObject> object_2(new CountedObject(2));
279 EXPECT_TRUE(
280 range_map.StoreRange(100 /* base address */, 100 /* size */, object_2));
281
282 // This should be overlapped on both object_1 and object_2.
283 linked_ptr<CountedObject> object_3(new CountedObject(3));
284 EXPECT_TRUE(
285 range_map.StoreRange(0 /* base address */, 300 /* size */, object_3));
286
287 linked_ptr<CountedObject> object;
288 AddressType retrieved_base = AddressType();
289 AddressType retrieved_delta = AddressType();
290 AddressType retrieved_size = AddressType();
291 // The first range should be intact.
292 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
293 &retrieved_delta, &retrieved_size));
294 EXPECT_EQ(1, object->id());
295 EXPECT_EQ(10, retrieved_base);
296 EXPECT_EQ(0, retrieved_delta);
297 EXPECT_EQ(90, retrieved_size);
298 // The second range should be intact.
299 EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
300 &retrieved_delta, &retrieved_size));
301 EXPECT_EQ(2, object->id());
302 EXPECT_EQ(100, retrieved_base);
303 EXPECT_EQ(0, retrieved_delta);
304 EXPECT_EQ(100, retrieved_size);
305 // The third range should be truncated.
306 EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
307 &retrieved_delta, &retrieved_size));
308 EXPECT_EQ(3, object->id());
309 EXPECT_EQ(0, retrieved_base);
310 EXPECT_EQ(0, retrieved_delta);
311 EXPECT_EQ(10, retrieved_size);
312 }
313
314 // Adding two ranges without overlap should succeed and the ranges should
315 // be left intact.
TEST(RangeMapTruncateLower,NoConflicts)316 TEST(RangeMapTruncateLower, NoConflicts) {
317 TestMap range_map;
318 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
319 // Adding range 1.
320 linked_ptr<CountedObject> object_1(new CountedObject(1));
321 EXPECT_TRUE(
322 range_map.StoreRange(10 /* base address */, 90 /* size */, object_1));
323
324 // Adding range 2 - no overlap with range 1.
325 linked_ptr<CountedObject> object_2(new CountedObject(2));
326 EXPECT_TRUE(
327 range_map.StoreRange(110 /* base address */, 90 /* size */, object_2));
328
329 linked_ptr<CountedObject> object;
330 AddressType retrieved_base = AddressType();
331 AddressType retrieved_delta = AddressType();
332 AddressType retrieved_size = AddressType();
333 // The first range should be intact.
334 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
335 &retrieved_delta, &retrieved_size));
336 EXPECT_EQ(1, object->id());
337 EXPECT_EQ(10, retrieved_base);
338 EXPECT_EQ(0, retrieved_delta);
339 EXPECT_EQ(90, retrieved_size);
340 // The second range should be intact.
341 EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
342 &retrieved_delta, &retrieved_size));
343 EXPECT_EQ(2, object->id());
344 EXPECT_EQ(110, retrieved_base);
345 EXPECT_EQ(0, retrieved_delta);
346 EXPECT_EQ(90, retrieved_size);
347 }
348
349 } // namespace
350