range_map_unittest.cc
1 // Copyright 2010 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_unittest.cc: Unit tests for RangeMap 30 // 31 // Author: Mark Mentovai 32 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 "common/scoped_ptr.h" 44 #include "processor/linked_ptr.h" 45 #include "processor/logging.h" 46 47 namespace { 48 49 using google_breakpad::AddIgnoringOverflow; 50 using google_breakpad::linked_ptr; 51 using google_breakpad::RangeMap; 52 using google_breakpad::scoped_ptr; 53 54 // A CountedObject holds an int. A global (not thread safe!) count of 55 // allocated CountedObjects is maintained to help test memory management. 56 class CountedObject { 57 public: 58 explicit CountedObject(int id) : id_(id) { ++count_; } 59 ~CountedObject() { --count_; } 60 61 static int count() { return count_; } 62 int id() const { return id_; } 63 64 private: 65 static int count_; 66 int id_; 67 }; 68 69 int CountedObject::count_; 70 71 72 typedef int AddressType; 73 typedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap; 74 75 76 // RangeTest contains data to use for store and retrieve tests. See 77 // RunTests for descriptions of the tests. 78 struct RangeTest { 79 // Base address to use for test 80 AddressType address; 81 82 // Size of range to use for test 83 AddressType size; 84 85 // Unique ID of range - unstorable ranges must have unique IDs too 86 int id; 87 88 // Whether this range is expected to be stored successfully or not 89 bool expect_storable; 90 }; 91 92 93 // A RangeTestSet encompasses multiple RangeTests, which are run in 94 // sequence on the same RangeMap. 95 struct RangeTestSet { 96 // An array of RangeTests 97 const RangeTest* range_tests; 98 99 // The number of tests in the set 100 unsigned int range_test_count; 101 }; 102 103 104 // StoreTest uses the data in a RangeTest and calls StoreRange on the 105 // test RangeMap. It returns true if the expected result occurred, and 106 // false if something else happened. 107 static bool StoreTest(TestMap* range_map, const RangeTest* range_test) { 108 linked_ptr<CountedObject> object(new CountedObject(range_test->id)); 109 bool stored = range_map->StoreRange(range_test->address, 110 range_test->size, 111 object); 112 113 if (stored != range_test->expect_storable) { 114 fprintf(stderr, "FAILED: " 115 "StoreRange id %d, expected %s, observed %s\n", 116 range_test->id, 117 range_test->expect_storable ? "storable" : "not storable", 118 stored ? "stored" : "not stored"); 119 return false; 120 } 121 122 return true; 123 } 124 125 126 // RetrieveTest uses the data in RangeTest and calls RetrieveRange on the 127 // test RangeMap. If it retrieves the expected value (which can be no 128 // map entry at the specified range,) it returns true, otherwise, it returns 129 // false. RetrieveTest will check the values around the base address and 130 // the high address of a range to guard against off-by-one errors. 131 static bool RetrieveTest(TestMap* range_map, const RangeTest* range_test) { 132 for (unsigned int side = 0; side <= 1; ++side) { 133 // When side == 0, check the low side (base address) of each range. 134 // When side == 1, check the high side (base + size) of each range. 135 136 // Check one-less and one-greater than the target address in addition 137 // to the target address itself. 138 139 // If the size of the range is only 1, don't check one greater than 140 // the base or one less than the high - for a successfully stored 141 // range, these tests would erroneously fail because the range is too 142 // small. 143 AddressType low_offset = -1; 144 AddressType high_offset = 1; 145 if (range_test->size == 1) { 146 if (!side) // When checking the low side, 147 high_offset = 0; // don't check one over the target. 148 else // When checking the high side, 149 low_offset = 0; // don't check one under the target. 150 } 151 152 for (AddressType offset = low_offset; offset <= high_offset; ++offset) { 153 AddressType address = AddIgnoringOverflow( 154 offset, (!side ? range_test->address 155 : AddIgnoringOverflow(range_test->address, 156 range_test->size - 1))); 157 158 bool expected_result = false; // This is correct for tests not stored. 159 if (range_test->expect_storable) { 160 if (offset == 0) // When checking the target address, 161 expected_result = true; // test should always succeed. 162 else if (offset == -1) // When checking one below the target, 163 expected_result = side; // should fail low and succeed high. 164 else // When checking one above the target, 165 expected_result = !side; // should succeed low and fail high. 166 } 167 168 linked_ptr<CountedObject> object; 169 AddressType retrieved_base = AddressType(); 170 AddressType retrieved_size = AddressType(); 171 AddressType retrieved_delta = AddressType(); 172 bool retrieved = range_map->RetrieveRange(address, &object, 173 &retrieved_base, 174 &retrieved_delta, 175 &retrieved_size); 176 177 bool observed_result = retrieved && object->id() == range_test->id; 178 179 if (observed_result != expected_result) { 180 fprintf(stderr, "FAILED: " 181 "RetrieveRange id %d, side %d, offset %d, " 182 "expected %s, observed %s\n", 183 range_test->id, 184 side, 185 offset, 186 expected_result ? "true" : "false", 187 observed_result ? "true" : "false"); 188 return false; 189 } 190 191 // If a range was successfully retrieved, check that the returned 192 // bounds match the range as stored. 193 if (observed_result == true && 194 (retrieved_base != range_test->address || 195 retrieved_size != range_test->size)) { 196 fprintf(stderr, "FAILED: " 197 "RetrieveRange id %d, side %d, offset %d, " 198 "expected base/size %d/%d, observed %d/%d\n", 199 range_test->id, 200 side, 201 offset, 202 range_test->address, range_test->size, 203 retrieved_base, retrieved_size); 204 return false; 205 } 206 207 // Now, check RetrieveNearestRange. The nearest range is always 208 // expected to be different from the test range when checking one 209 // less than the low side. 210 bool expected_nearest = range_test->expect_storable; 211 if (!side && offset < 0) 212 expected_nearest = false; 213 214 linked_ptr<CountedObject> nearest_object; 215 AddressType nearest_base = AddressType(); 216 AddressType nearest_delta = AddressType(); 217 AddressType nearest_size = AddressType(); 218 bool retrieved_nearest = range_map->RetrieveNearestRange(address, 219 &nearest_object, 220 &nearest_base, 221 &nearest_delta, 222 &nearest_size); 223 224 // When checking one greater than the high side, RetrieveNearestRange 225 // should usually return the test range. When a different range begins 226 // at that address, though, then RetrieveNearestRange should return the 227 // range at the address instead of the test range. 228 if (side && offset > 0 && nearest_base == address) { 229 expected_nearest = false; 230 } 231 232 bool observed_nearest = retrieved_nearest && 233 nearest_object->id() == range_test->id; 234 235 if (observed_nearest != expected_nearest) { 236 fprintf(stderr, "FAILED: " 237 "RetrieveNearestRange id %d, side %d, offset %d, " 238 "expected %s, observed %s\n", 239 range_test->id, 240 side, 241 offset, 242 expected_nearest ? "true" : "false", 243 observed_nearest ? "true" : "false"); 244 return false; 245 } 246 247 // If a range was successfully retrieved, check that the returned 248 // bounds match the range as stored. 249 if (expected_nearest && 250 (nearest_base != range_test->address || 251 nearest_size != range_test->size)) { 252 fprintf(stderr, "FAILED: " 253 "RetrieveNearestRange id %d, side %d, offset %d, " 254 "expected base/size %d/%d, observed %d/%d\n", 255 range_test->id, 256 side, 257 offset, 258 range_test->address, range_test->size, 259 nearest_base, nearest_size); 260 return false; 261 } 262 } 263 } 264 265 return true; 266 } 267 268 269 // Test RetrieveRangeAtIndex, which is supposed to return objects in order 270 // according to their addresses. This test is performed by looping through 271 // the map, calling RetrieveRangeAtIndex for all possible indices in sequence, 272 // and verifying that each call returns a different object than the previous 273 // call, and that ranges are returned with increasing base addresses. Returns 274 // false if the test fails. 275 static bool RetrieveIndexTest(TestMap* range_map, int set) { 276 linked_ptr<CountedObject> object; 277 CountedObject* last_object = NULL; 278 AddressType last_base = 0; 279 280 int object_count = range_map->GetCount(); 281 for (int object_index = 0; object_index < object_count; ++object_index) { 282 AddressType base; 283 if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, 284 NULL /* delta */, NULL /* size */)) { 285 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 286 "expected success, observed failure\n", 287 set, object_index); 288 return false; 289 } 290 291 if (!object.get()) { 292 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 293 "expected object, observed NULL\n", 294 set, object_index); 295 return false; 296 } 297 298 // It's impossible to do these comparisons unless there's a previous 299 // object to compare against. 300 if (last_object) { 301 // The object must be different from the last one. 302 if (object->id() == last_object->id()) { 303 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 304 "expected different objects, observed same objects (%d)\n", 305 set, object_index, object->id()); 306 return false; 307 } 308 309 // Each object must have a base greater than the previous object's base. 310 if (base <= last_base) { 311 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 312 "expected different bases, observed same bases (%d)\n", 313 set, object_index, base); 314 return false; 315 } 316 } 317 318 last_object = object.get(); 319 last_base = base; 320 } 321 322 // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that 323 // are too high. 324 if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL /* base */, 325 NULL /* delta */, NULL /* size */)) { 326 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), " 327 "expected failure, observed success\n", 328 set, object_count); 329 return false; 330 } 331 332 return true; 333 } 334 335 // Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex(). 336 // Bug info: RetrieveRangeAtIndex() previously retrieves the high address of 337 // entry, however, it is supposed to retrieve the base address of entry as 338 // stated in the comment in range_map.h. 339 static bool RetriveAtIndexTest2() { 340 scoped_ptr<TestMap> range_map(new TestMap()); 341 342 // Store ranges with base address = 2 * object_id: 343 const int range_size = 2; 344 for (int object_id = 0; object_id < 100; ++object_id) { 345 linked_ptr<CountedObject> object(new CountedObject(object_id)); 346 int base_address = 2 * object_id; 347 range_map->StoreRange(base_address, range_size, object); 348 } 349 350 linked_ptr<CountedObject> object; 351 int object_count = range_map->GetCount(); 352 for (int object_index = 0; object_index < object_count; ++object_index) { 353 AddressType base; 354 if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, 355 NULL /* delta */, NULL /* size */)) { 356 fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, " 357 "expected success, observed failure\n", object_index); 358 return false; 359 } 360 361 int expected_base = 2 * object->id(); 362 if (base != expected_base) { 363 fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, " 364 "expected base %d, observed base %d", 365 object_index, expected_base, base); 366 return false; 367 } 368 } 369 370 return true; 371 } 372 373 374 // RunTests runs a series of test sets. 375 static bool RunTests() { 376 // These tests will be run sequentially. The first set of tests exercises 377 // most functions of RangeTest, and verifies all of the bounds-checking. 378 const RangeTest range_tests_0[] = { 379 { INT_MIN, 16, 1, true }, // lowest possible range 380 { -2, 5, 2, true }, // a range through zero 381 { INT_MAX - 9, 11, 3, false }, // tests anti-overflow 382 { INT_MAX - 9, 10, 4, true }, // highest possible range 383 { 5, 0, 5, false }, // tests anti-zero-size 384 { 5, 1, 6, true }, // smallest possible range 385 { -20, 15, 7, true }, // entirely negative 386 387 { 10, 10, 10, true }, // causes the following tests to fail 388 { 9, 10, 11, false }, // one-less base, one-less high 389 { 9, 11, 12, false }, // one-less base, identical high 390 { 9, 12, 13, false }, // completely contains existing 391 { 10, 9, 14, false }, // identical base, one-less high 392 { 10, 10, 15, false }, // exactly identical to existing range 393 { 10, 11, 16, false }, // identical base, one-greater high 394 { 11, 8, 17, false }, // contained completely within 395 { 11, 9, 18, false }, // one-greater base, identical high 396 { 11, 10, 19, false }, // one-greater base, one-greater high 397 { 9, 2, 20, false }, // overlaps bottom by one 398 { 10, 1, 21, false }, // overlaps bottom by one, contained 399 { 19, 1, 22, false }, // overlaps top by one, contained 400 { 19, 2, 23, false }, // overlaps top by one 401 402 { 9, 1, 24, true }, // directly below without overlap 403 { 20, 1, 25, true }, // directly above without overlap 404 405 { 6, 3, 26, true }, // exactly between two ranges, gapless 406 { 7, 3, 27, false }, // tries to span two ranges 407 { 7, 5, 28, false }, // tries to span three ranges 408 { 4, 20, 29, false }, // tries to contain several ranges 409 410 { 30, 50, 30, true }, 411 { 90, 25, 31, true }, 412 { 35, 65, 32, false }, // tries to span two noncontiguous 413 { 120, 10000, 33, true }, // > 8-bit 414 { 20000, 20000, 34, true }, // > 8-bit 415 { 0x10001, 0x10001, 35, true }, // > 16-bit 416 417 { 27, -1, 36, false } // tests high < base 418 }; 419 420 // Attempt to fill the entire space. The entire space must be filled with 421 // three stores because AddressType is signed for these tests, so RangeMap 422 // treats the size as signed and rejects sizes that appear to be negative. 423 // Even if these tests were run as unsigned, two stores would be needed 424 // to fill the space because the entire size of the space could only be 425 // described by using one more bit than would be present in AddressType. 426 const RangeTest range_tests_1[] = { 427 { INT_MIN, INT_MAX, 50, true }, // From INT_MIN to -2, inclusive 428 { -1, 2, 51, true }, // From -1 to 0, inclusive 429 { 1, INT_MAX, 52, true }, // From 1 to INT_MAX, inclusive 430 { INT_MIN, INT_MAX, 53, false }, // Can't fill the space twice 431 { -1, 2, 54, false }, 432 { 1, INT_MAX, 55, false }, 433 { -3, 6, 56, false }, // -3 to 2, inclusive - spans 3 ranges 434 }; 435 436 // A light round of testing to verify that RetrieveRange does the right 437 // the right thing at the extremities of the range when nothing is stored 438 // there. Checks are forced without storing anything at the extremities 439 // by setting size = 0. 440 const RangeTest range_tests_2[] = { 441 { INT_MIN, 0, 100, false }, // makes RetrieveRange check low end 442 { -1, 3, 101, true }, 443 { INT_MAX, 0, 102, false }, // makes RetrieveRange check high end 444 }; 445 446 // Similar to the previous test set, but with a couple of ranges closer 447 // to the extremities. 448 const RangeTest range_tests_3[] = { 449 { INT_MIN + 1, 1, 110, true }, 450 { INT_MAX - 1, 1, 111, true }, 451 { INT_MIN, 0, 112, false }, // makes RetrieveRange check low end 452 { INT_MAX, 0, 113, false } // makes RetrieveRange check high end 453 }; 454 455 // The range map is cleared between sets of tests listed here. 456 const RangeTestSet range_test_sets[] = { 457 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) }, 458 { range_tests_1, sizeof(range_tests_1) / sizeof(RangeTest) }, 459 { range_tests_2, sizeof(range_tests_2) / sizeof(RangeTest) }, 460 { range_tests_3, sizeof(range_tests_3) / sizeof(RangeTest) }, 461 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) } // Run again 462 }; 463 464 // Maintain the range map in a pointer so that deletion can be meaningfully 465 // tested. 466 scoped_ptr<TestMap> range_map(new TestMap()); 467 468 // Run all of the test sets in sequence. 469 unsigned int range_test_set_count = sizeof(range_test_sets) / 470 sizeof(RangeTestSet); 471 for (unsigned int range_test_set_index = 0; 472 range_test_set_index < range_test_set_count; 473 ++range_test_set_index) { 474 const RangeTest* range_tests = 475 range_test_sets[range_test_set_index].range_tests; 476 unsigned int range_test_count = 477 range_test_sets[range_test_set_index].range_test_count; 478 479 // Run the StoreRange test, which validates StoreRange and initializes 480 // the RangeMap with data for the RetrieveRange test. 481 int stored_count = 0; // The number of ranges successfully stored 482 for (unsigned int range_test_index = 0; 483 range_test_index < range_test_count; 484 ++range_test_index) { 485 const RangeTest* range_test = &range_tests[range_test_index]; 486 if (!StoreTest(range_map.get(), range_test)) 487 return false; 488 489 if (range_test->expect_storable) 490 ++stored_count; 491 } 492 493 // There should be exactly one CountedObject for everything successfully 494 // stored in the RangeMap. 495 if (CountedObject::count() != stored_count) { 496 fprintf(stderr, "FAILED: " 497 "stored object counts don't match, expected %d, observed %d\n", 498 stored_count, 499 CountedObject::count()); 500 501 return false; 502 } 503 504 // The RangeMap's own count of objects should also match. 505 if (range_map->GetCount() != stored_count) { 506 fprintf(stderr, "FAILED: stored object count doesn't match GetCount, " 507 "expected %d, observed %d\n", 508 stored_count, range_map->GetCount()); 509 510 return false; 511 } 512 513 // Run the RetrieveRange test 514 for (unsigned int range_test_index = 0; 515 range_test_index < range_test_count; 516 ++range_test_index) { 517 const RangeTest* range_test = &range_tests[range_test_index]; 518 if (!RetrieveTest(range_map.get(), range_test)) 519 return false; 520 } 521 522 if (!RetrieveIndexTest(range_map.get(), range_test_set_index)) 523 return false; 524 525 // Clear the map between test sets. If this is the final test set, 526 // delete the map instead to test destruction. 527 if (range_test_set_index < range_test_set_count - 1) 528 range_map->Clear(); 529 else 530 range_map.reset(); 531 532 // Test that all stored objects are freed when the RangeMap is cleared 533 // or deleted. 534 if (CountedObject::count() != 0) { 535 fprintf(stderr, "FAILED: " 536 "did not free all objects after %s, %d still allocated\n", 537 range_test_set_index < range_test_set_count - 1 ? "clear" 538 : "delete", 539 CountedObject::count()); 540 541 return false; 542 } 543 } 544 545 if (!RetriveAtIndexTest2()) { 546 fprintf(stderr, "FAILED: did not pass RetrieveAtIndexTest2()\n"); 547 return false; 548 } 549 550 return true; 551 } 552 553 554 } // namespace 555 556 557 int main(int argc, char** argv) { 558 BPLOG_INIT(&argc, &argv); 559 560 return RunTests() ? 0 : 1; 561 }