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