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