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:
 57    explicit CountedObject(int id) : id_(id) { ++count_; }
 58    ~CountedObject() { --count_; }
 59  
 60    static int count() { return count_; }
 61    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.
 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.
 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.
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  
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  
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.
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  
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.
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