1 // Copyright 2016 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 // range_map_shrink_down_unittest.cc: Unit tests for RangeMap that specifically
30 // test shrink down when ranges overlap.
31 //
32 // Author: Ivan Penkov
33
34 #ifdef HAVE_CONFIG_H
35 #include <config.h> // Must come first
36 #endif
37
38 #include <limits.h>
39 #include <stdio.h>
40
41 #include "processor/range_map-inl.h"
42
43 #include "breakpad_googletest_includes.h"
44 #include "processor/linked_ptr.h"
45 #include "processor/logging.h"
46
47 namespace {
48
49 using google_breakpad::linked_ptr;
50 using google_breakpad::MergeRangeStrategy;
51 using google_breakpad::RangeMap;
52
53 // A CountedObject holds an int. A global (not thread safe!) count of
54 // allocated CountedObjects is maintained to help test memory management.
55 class CountedObject {
56 public:
CountedObject(int id)57 explicit CountedObject(int id) : id_(id) { ++count_; }
~CountedObject()58 ~CountedObject() { --count_; }
59
count()60 static int count() { return count_; }
id() const61 int id() const { return id_; }
62
63 private:
64 static int count_;
65 int id_;
66 };
67
68 int CountedObject::count_;
69
70 typedef int AddressType;
71 typedef RangeMap<AddressType, linked_ptr<CountedObject>> TestMap;
72
73 // Same range cannot be stored wice.
TEST(RangeMapTruncateUpper,SameRange)74 TEST(RangeMapTruncateUpper, SameRange) {
75 TestMap range_map;
76 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
77 linked_ptr<CountedObject> object_1(new CountedObject(1));
78 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
79 object_1));
80
81 // Same range cannot be stored wice.
82 linked_ptr<CountedObject> object_2(new CountedObject(2));
83 EXPECT_FALSE(range_map.StoreRange(0 /* base address */, 100 /* size */,
84 object_2));
85 }
86
87 // If a range is completely contained by another range, then the larger range
88 // should be shrinked down.
TEST(RangeMapTruncateUpper,CompletelyContained)89 TEST(RangeMapTruncateUpper, CompletelyContained) {
90 TestMap range_map;
91 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
92 // Larger range is added first.
93 linked_ptr<CountedObject> object_1(new CountedObject(1));
94 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
95 object_1));
96 // Smaller (contained) range is added second.
97 linked_ptr<CountedObject> object_2(new CountedObject(2));
98 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */,
99 object_2));
100 linked_ptr<CountedObject> object;
101 AddressType retrieved_base = AddressType();
102 AddressType retrieved_delta = AddressType();
103 AddressType retrieved_size = AddressType();
104 // The first range contains the second, so the first range should have been
105 // shrunk to [90, 99]. Range [0, 9] should be free.
106 EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base,
107 &retrieved_delta, &retrieved_size));
108 EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base,
109 &retrieved_delta, &retrieved_size));
110 EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base,
111 &retrieved_delta, &retrieved_size));
112 EXPECT_EQ(1, object->id());
113 EXPECT_EQ(90, retrieved_base);
114 EXPECT_EQ(90, retrieved_delta);
115 EXPECT_EQ(10, retrieved_size);
116 // Validate the properties of the smaller range (should be untouched).
117 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
118 &retrieved_delta, &retrieved_size));
119 EXPECT_EQ(2, object->id());
120 EXPECT_EQ(10, retrieved_base);
121 EXPECT_EQ(0, retrieved_delta);
122 EXPECT_EQ(80, retrieved_size);
123 }
124
125 // Same as the previous test, however the larger range is added second.
TEST(RangeMapTruncateUpper,CompletelyContained_LargerAddedSecond)126 TEST(RangeMapTruncateUpper, CompletelyContained_LargerAddedSecond) {
127 TestMap range_map;
128 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
129 // Smaller (contained) range is added first.
130 linked_ptr<CountedObject> object_1(new CountedObject(1));
131 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 80 /* size */,
132 object_1));
133 // Larger range is added second.
134 linked_ptr<CountedObject> object_2(new CountedObject(2));
135 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
136 object_2));
137 linked_ptr<CountedObject> object;
138 AddressType retrieved_base = AddressType();
139 AddressType retrieved_delta = AddressType();
140 AddressType retrieved_size = AddressType();
141 // The second range contains the first, so the second range should have been
142 // shrunk to [90, 99]. Range [0, 9] should be free.
143 EXPECT_FALSE(range_map.RetrieveRange(0, &object, &retrieved_base,
144 &retrieved_delta, &retrieved_size));
145 EXPECT_FALSE(range_map.RetrieveRange(9, &object, &retrieved_base,
146 &retrieved_delta, &retrieved_size));
147 EXPECT_TRUE(range_map.RetrieveRange(90, &object, &retrieved_base,
148 &retrieved_delta, &retrieved_size));
149 EXPECT_EQ(2, object->id());
150 EXPECT_EQ(90, retrieved_base);
151 EXPECT_EQ(90, retrieved_delta);
152 EXPECT_EQ(10, retrieved_size);
153 // Validate the properties of the smaller range (should be untouched).
154 EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
155 &retrieved_delta, &retrieved_size));
156 EXPECT_EQ(1, object->id());
157 EXPECT_EQ(10, retrieved_base);
158 EXPECT_EQ(0, retrieved_delta);
159 EXPECT_EQ(80, retrieved_size);
160 }
161
TEST(RangeMapTruncateUpper,PartialOverlap_AtBeginning)162 TEST(RangeMapTruncateUpper, PartialOverlap_AtBeginning) {
163 TestMap range_map;
164 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
165 linked_ptr<CountedObject> object_1(new CountedObject(1));
166 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
167 object_1));
168
169 // Partial overlap at the beginning of the new range.
170 linked_ptr<CountedObject> object_2(new CountedObject(2));
171 EXPECT_TRUE(range_map.StoreRange(90 /* base address */, 110 /* size */,
172 object_2));
173
174 linked_ptr<CountedObject> object;
175 AddressType retrieved_base = AddressType();
176 AddressType retrieved_delta = AddressType();
177 AddressType retrieved_size = AddressType();
178 // The second range is supposed to be shrunk down so the following address
179 // should resize in the first range.
180 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
181 &retrieved_delta, &retrieved_size));
182 EXPECT_EQ(1, object->id());
183 EXPECT_EQ(0, retrieved_base);
184 EXPECT_EQ(0, retrieved_delta);
185 EXPECT_EQ(100, retrieved_size);
186 // Validate the properties of the shrunk down range.
187 EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base,
188 &retrieved_delta, &retrieved_size));
189 EXPECT_EQ(2, object->id());
190 EXPECT_EQ(100, retrieved_base);
191 EXPECT_EQ(10, retrieved_delta);
192 EXPECT_EQ(100, retrieved_size);
193 }
194
TEST(RangeMapTruncateUpper,PartialOverlap_AtEnd)195 TEST(RangeMapTruncateUpper, PartialOverlap_AtEnd) {
196 TestMap range_map;
197 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
198 linked_ptr<CountedObject> object_1(new CountedObject(1));
199 EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 50 /* size */,
200 object_1));
201
202 // Partial overlap at the end of the new range.
203 linked_ptr<CountedObject> object_2(new CountedObject(2));
204 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 70 /* size */,
205 object_2));
206
207 linked_ptr<CountedObject> object;
208 AddressType retrieved_base = AddressType();
209 AddressType retrieved_delta = AddressType();
210 AddressType retrieved_size = AddressType();
211 // The first range is supposed to be shrunk down so the following address
212 // should resize in the first range.
213 EXPECT_TRUE(range_map.RetrieveRange(69, &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(70, retrieved_size);
219 // Validate the properties of the shrunk down range.
220 EXPECT_TRUE(range_map.RetrieveRange(70, &object, &retrieved_base,
221 &retrieved_delta, &retrieved_size));
222 EXPECT_EQ(1, object->id());
223 EXPECT_EQ(70, retrieved_base);
224 EXPECT_EQ(20, retrieved_delta);
225 EXPECT_EQ(30, retrieved_size);
226 }
227
228 // A new range is overlapped at both ends. The new range and the range
229 // that overlaps at the end should be shrink. The range that overlaps at the
230 // beginning should be left untouched.
TEST(RangeMapTruncateUpper,OverlapAtBothEnds)231 TEST(RangeMapTruncateUpper, OverlapAtBothEnds) {
232 TestMap range_map;
233 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
234 // This should overlap object_3 at the beginning.
235 linked_ptr<CountedObject> object_1(new CountedObject(1));
236 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 100 /* size */,
237 object_1));
238
239 // This should overlap object_3 at the end.
240 linked_ptr<CountedObject> object_2(new CountedObject(2));
241 EXPECT_TRUE(range_map.StoreRange(100 /* base address */, 100 /* size */,
242 object_2));
243
244 // This should be overlapped on both ends by object_1 and object_2.
245 linked_ptr<CountedObject> object_3(new CountedObject(3));
246 EXPECT_TRUE(range_map.StoreRange(50 /* base address */, 100 /* size */,
247 object_3));
248
249 linked_ptr<CountedObject> object;
250 AddressType retrieved_base = AddressType();
251 AddressType retrieved_delta = AddressType();
252 AddressType retrieved_size = AddressType();
253 // The first range should be intact.
254 EXPECT_TRUE(range_map.RetrieveRange(0, &object, &retrieved_base,
255 &retrieved_delta, &retrieved_size));
256 EXPECT_EQ(1, object->id());
257 EXPECT_EQ(0, retrieved_base);
258 EXPECT_EQ(0, retrieved_delta);
259 EXPECT_EQ(100, retrieved_size);
260 // The second range should be shrunk down by 50.
261 EXPECT_TRUE(range_map.RetrieveRange(150, &object, &retrieved_base,
262 &retrieved_delta, &retrieved_size));
263 EXPECT_EQ(2, object->id());
264 EXPECT_EQ(150, retrieved_base);
265 EXPECT_EQ(50, retrieved_delta);
266 EXPECT_EQ(50, retrieved_size);
267 // The third range (in the middle) should be shrunk down by 50.
268 EXPECT_TRUE(range_map.RetrieveRange(100, &object, &retrieved_base,
269 &retrieved_delta, &retrieved_size));
270 EXPECT_EQ(3, object->id());
271 EXPECT_EQ(100, retrieved_base);
272 EXPECT_EQ(50, retrieved_delta);
273 EXPECT_EQ(50, retrieved_size);
274 }
275
TEST(RangeMapTruncateUpper,MultipleConflicts)276 TEST(RangeMapTruncateUpper, MultipleConflicts) {
277 TestMap range_map;
278 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
279 // This should overlap with object_3.
280 linked_ptr<CountedObject> object_1(new CountedObject(1));
281 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 90 /* size */,
282 object_1));
283
284 // This should also overlap with object_3 but after object_1.
285 linked_ptr<CountedObject> object_2(new CountedObject(2));
286 EXPECT_TRUE(range_map.StoreRange(100 /* base address */, 100 /* size */,
287 object_2));
288
289 // This should be overlapped on both object_1 and object_2. Since
290 // object_3 ends with the higher address it must be shrunk.
291 linked_ptr<CountedObject> object_3(new CountedObject(3));
292 EXPECT_TRUE(range_map.StoreRange(0 /* base address */, 300 /* size */,
293 object_3));
294
295 linked_ptr<CountedObject> object;
296 AddressType retrieved_base = AddressType();
297 AddressType retrieved_delta = AddressType();
298 AddressType retrieved_size = AddressType();
299 // The first range should be intact.
300 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
301 &retrieved_delta, &retrieved_size));
302 EXPECT_EQ(1, object->id());
303 EXPECT_EQ(10, retrieved_base);
304 EXPECT_EQ(0, retrieved_delta);
305 EXPECT_EQ(90, retrieved_size);
306 // The second range should be intact.
307 EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
308 &retrieved_delta, &retrieved_size));
309 EXPECT_EQ(2, object->id());
310 EXPECT_EQ(100, retrieved_base);
311 EXPECT_EQ(0, retrieved_delta);
312 EXPECT_EQ(100, retrieved_size);
313 // The third range should be shrunk down by 200.
314 EXPECT_TRUE(range_map.RetrieveRange(299, &object, &retrieved_base,
315 &retrieved_delta, &retrieved_size));
316 EXPECT_EQ(3, object->id());
317 EXPECT_EQ(200, retrieved_base);
318 EXPECT_EQ(200, retrieved_delta);
319 EXPECT_EQ(100, retrieved_size);
320 }
321
322 // Adding two ranges without overlap should succeed and the ranges should
323 // be left intact.
TEST(RangeMapTruncateUpper,NoConflicts)324 TEST(RangeMapTruncateUpper, NoConflicts) {
325 TestMap range_map;
326 range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateUpper);
327 // Adding range 1.
328 linked_ptr<CountedObject> object_1(new CountedObject(1));
329 EXPECT_TRUE(range_map.StoreRange(10 /* base address */, 90 /* size */,
330 object_1));
331
332 // Adding range 2 - no overlap with range 1.
333 linked_ptr<CountedObject> object_2(new CountedObject(2));
334 EXPECT_TRUE(range_map.StoreRange(110 /* base address */, 90 /* size */,
335 object_2));
336
337 linked_ptr<CountedObject> object;
338 AddressType retrieved_base = AddressType();
339 AddressType retrieved_delta = AddressType();
340 AddressType retrieved_size = AddressType();
341 // The first range should be intact.
342 EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
343 &retrieved_delta, &retrieved_size));
344 EXPECT_EQ(1, object->id());
345 EXPECT_EQ(10, retrieved_base);
346 EXPECT_EQ(0, retrieved_delta);
347 EXPECT_EQ(90, retrieved_size);
348 // The second range should be intact.
349 EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
350 &retrieved_delta, &retrieved_size));
351 EXPECT_EQ(2, object->id());
352 EXPECT_EQ(110, retrieved_base);
353 EXPECT_EQ(0, retrieved_delta);
354 EXPECT_EQ(90, retrieved_size);
355 }
356
357 } // namespace
358