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