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