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