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