diff options
Diffstat (limited to 'toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc')
| -rw-r--r-- | toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc | 559 |
1 files changed, 559 insertions, 0 deletions
diff --git a/toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc b/toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc new file mode 100644 index 0000000000..31b89e5de3 --- /dev/null +++ b/toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc @@ -0,0 +1,559 @@ +// Copyright (c) 2010 Google Inc. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// range_map_unittest.cc: Unit tests for RangeMap +// +// Author: Mark Mentovai + + +#include <limits.h> +#include <stdio.h> + +#include "processor/range_map-inl.h" + +#include "common/scoped_ptr.h" +#include "processor/linked_ptr.h" +#include "processor/logging.h" + +namespace { + + +using google_breakpad::linked_ptr; +using google_breakpad::scoped_ptr; +using google_breakpad::RangeMap; + + +// A CountedObject holds an int. A global (not thread safe!) count of +// allocated CountedObjects is maintained to help test memory management. +class CountedObject { + public: + explicit CountedObject(int id) : id_(id) { ++count_; } + ~CountedObject() { --count_; } + + static int count() { return count_; } + int id() const { return id_; } + + private: + static int count_; + int id_; +}; + +int CountedObject::count_; + + +typedef int AddressType; +typedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap; + + +// RangeTest contains data to use for store and retrieve tests. See +// RunTests for descriptions of the tests. +struct RangeTest { + // Base address to use for test + AddressType address; + + // Size of range to use for test + AddressType size; + + // Unique ID of range - unstorable ranges must have unique IDs too + int id; + + // Whether this range is expected to be stored successfully or not + bool expect_storable; +}; + + +// A RangeTestSet encompasses multiple RangeTests, which are run in +// sequence on the same RangeMap. +struct RangeTestSet { + // An array of RangeTests + const RangeTest *range_tests; + + // The number of tests in the set + unsigned int range_test_count; +}; + + +// StoreTest uses the data in a RangeTest and calls StoreRange on the +// test RangeMap. It returns true if the expected result occurred, and +// false if something else happened. +static bool StoreTest(TestMap *range_map, const RangeTest *range_test) { + linked_ptr<CountedObject> object(new CountedObject(range_test->id)); + bool stored = range_map->StoreRange(range_test->address, + range_test->size, + object); + + if (stored != range_test->expect_storable) { + fprintf(stderr, "FAILED: " + "StoreRange id %d, expected %s, observed %s\n", + range_test->id, + range_test->expect_storable ? "storable" : "not storable", + stored ? "stored" : "not stored"); + return false; + } + + return true; +} + + +// RetrieveTest uses the data in RangeTest and calls RetrieveRange on the +// test RangeMap. If it retrieves the expected value (which can be no +// map entry at the specified range,) it returns true, otherwise, it returns +// false. RetrieveTest will check the values around the base address and +// the high address of a range to guard against off-by-one errors. +static bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) { + for (unsigned int side = 0; side <= 1; ++side) { + // When side == 0, check the low side (base address) of each range. + // When side == 1, check the high side (base + size) of each range. + + // Check one-less and one-greater than the target address in addition + // to the target address itself. + + // If the size of the range is only 1, don't check one greater than + // the base or one less than the high - for a successfully stored + // range, these tests would erroneously fail because the range is too + // small. + AddressType low_offset = -1; + AddressType high_offset = 1; + if (range_test->size == 1) { + if (!side) // When checking the low side, + high_offset = 0; // don't check one over the target. + else // When checking the high side, + low_offset = 0; // don't check one under the target. + } + + for (AddressType offset = low_offset; offset <= high_offset; ++offset) { + AddressType address = + offset + + (!side ? range_test->address : + range_test->address + range_test->size - 1); + + bool expected_result = false; // This is correct for tests not stored. + if (range_test->expect_storable) { + if (offset == 0) // When checking the target address, + expected_result = true; // test should always succeed. + else if (offset == -1) // When checking one below the target, + expected_result = side; // should fail low and succeed high. + else // When checking one above the target, + expected_result = !side; // should succeed low and fail high. + } + + linked_ptr<CountedObject> object; + AddressType retrieved_base = AddressType(); + AddressType retrieved_size = AddressType(); + AddressType retrieved_delta = AddressType(); + bool retrieved = range_map->RetrieveRange(address, &object, + &retrieved_base, + &retrieved_delta, + &retrieved_size); + + bool observed_result = retrieved && object->id() == range_test->id; + + if (observed_result != expected_result) { + fprintf(stderr, "FAILED: " + "RetrieveRange id %d, side %d, offset %d, " + "expected %s, observed %s\n", + range_test->id, + side, + offset, + expected_result ? "true" : "false", + observed_result ? "true" : "false"); + return false; + } + + // If a range was successfully retrieved, check that the returned + // bounds match the range as stored. + if (observed_result == true && + (retrieved_base != range_test->address || + retrieved_size != range_test->size)) { + fprintf(stderr, "FAILED: " + "RetrieveRange id %d, side %d, offset %d, " + "expected base/size %d/%d, observed %d/%d\n", + range_test->id, + side, + offset, + range_test->address, range_test->size, + retrieved_base, retrieved_size); + return false; + } + + // Now, check RetrieveNearestRange. The nearest range is always + // expected to be different from the test range when checking one + // less than the low side. + bool expected_nearest = range_test->expect_storable; + if (!side && offset < 0) + expected_nearest = false; + + linked_ptr<CountedObject> nearest_object; + AddressType nearest_base = AddressType(); + AddressType nearest_delta = AddressType(); + AddressType nearest_size = AddressType(); + bool retrieved_nearest = range_map->RetrieveNearestRange(address, + &nearest_object, + &nearest_base, + &nearest_delta, + &nearest_size); + + // When checking one greater than the high side, RetrieveNearestRange + // should usually return the test range. When a different range begins + // at that address, though, then RetrieveNearestRange should return the + // range at the address instead of the test range. + if (side && offset > 0 && nearest_base == address) { + expected_nearest = false; + } + + bool observed_nearest = retrieved_nearest && + nearest_object->id() == range_test->id; + + if (observed_nearest != expected_nearest) { + fprintf(stderr, "FAILED: " + "RetrieveNearestRange id %d, side %d, offset %d, " + "expected %s, observed %s\n", + range_test->id, + side, + offset, + expected_nearest ? "true" : "false", + observed_nearest ? "true" : "false"); + return false; + } + + // If a range was successfully retrieved, check that the returned + // bounds match the range as stored. + if (expected_nearest && + (nearest_base != range_test->address || + nearest_size != range_test->size)) { + fprintf(stderr, "FAILED: " + "RetrieveNearestRange id %d, side %d, offset %d, " + "expected base/size %d/%d, observed %d/%d\n", + range_test->id, + side, + offset, + range_test->address, range_test->size, + nearest_base, nearest_size); + return false; + } + } + } + + return true; +} + + +// Test RetrieveRangeAtIndex, which is supposed to return objects in order +// according to their addresses. This test is performed by looping through +// the map, calling RetrieveRangeAtIndex for all possible indices in sequence, +// and verifying that each call returns a different object than the previous +// call, and that ranges are returned with increasing base addresses. Returns +// false if the test fails. +static bool RetrieveIndexTest(TestMap *range_map, int set) { + linked_ptr<CountedObject> object; + CountedObject *last_object = NULL; + AddressType last_base = 0; + + int object_count = range_map->GetCount(); + for (int object_index = 0; object_index < object_count; ++object_index) { + AddressType base; + if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, + NULL /* delta */, NULL /* size */)) { + fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " + "expected success, observed failure\n", + set, object_index); + return false; + } + + if (!object.get()) { + fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " + "expected object, observed NULL\n", + set, object_index); + return false; + } + + // It's impossible to do these comparisons unless there's a previous + // object to compare against. + if (last_object) { + // The object must be different from the last one. + if (object->id() == last_object->id()) { + fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " + "expected different objects, observed same objects (%d)\n", + set, object_index, object->id()); + return false; + } + + // Each object must have a base greater than the previous object's base. + if (base <= last_base) { + fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " + "expected different bases, observed same bases (%d)\n", + set, object_index, base); + return false; + } + } + + last_object = object.get(); + last_base = base; + } + + // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that + // are too high. + if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL /* base */, + NULL /* delta */, NULL /* size */)) { + fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), " + "expected failure, observed success\n", + set, object_count); + return false; + } + + return true; +} + +// Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex(). +// Bug info: RetrieveRangeAtIndex() previously retrieves the high address of +// entry, however, it is supposed to retrieve the base address of entry as +// stated in the comment in range_map.h. +static bool RetriveAtIndexTest2() { + scoped_ptr<TestMap> range_map(new TestMap()); + + // Store ranges with base address = 2 * object_id: + const int range_size = 2; + for (int object_id = 0; object_id < 100; ++object_id) { + linked_ptr<CountedObject> object(new CountedObject(object_id)); + int base_address = 2 * object_id; + range_map->StoreRange(base_address, range_size, object); + } + + linked_ptr<CountedObject> object; + int object_count = range_map->GetCount(); + for (int object_index = 0; object_index < object_count; ++object_index) { + AddressType base; + if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, + NULL /* delta */, NULL /* size */)) { + fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, " + "expected success, observed failure\n", object_index); + return false; + } + + int expected_base = 2 * object->id(); + if (base != expected_base) { + fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, " + "expected base %d, observed base %d", + object_index, expected_base, base); + return false; + } + } + + return true; +} + + +// RunTests runs a series of test sets. +static bool RunTests() { + // These tests will be run sequentially. The first set of tests exercises + // most functions of RangeTest, and verifies all of the bounds-checking. + const RangeTest range_tests_0[] = { + { INT_MIN, 16, 1, true }, // lowest possible range + { -2, 5, 2, true }, // a range through zero + { INT_MAX - 9, 11, 3, false }, // tests anti-overflow + { INT_MAX - 9, 10, 4, true }, // highest possible range + { 5, 0, 5, false }, // tests anti-zero-size + { 5, 1, 6, true }, // smallest possible range + { -20, 15, 7, true }, // entirely negative + + { 10, 10, 10, true }, // causes the following tests to fail + { 9, 10, 11, false }, // one-less base, one-less high + { 9, 11, 12, false }, // one-less base, identical high + { 9, 12, 13, false }, // completely contains existing + { 10, 9, 14, false }, // identical base, one-less high + { 10, 10, 15, false }, // exactly identical to existing range + { 10, 11, 16, false }, // identical base, one-greater high + { 11, 8, 17, false }, // contained completely within + { 11, 9, 18, false }, // one-greater base, identical high + { 11, 10, 19, false }, // one-greater base, one-greater high + { 9, 2, 20, false }, // overlaps bottom by one + { 10, 1, 21, false }, // overlaps bottom by one, contained + { 19, 1, 22, false }, // overlaps top by one, contained + { 19, 2, 23, false }, // overlaps top by one + + { 9, 1, 24, true }, // directly below without overlap + { 20, 1, 25, true }, // directly above without overlap + + { 6, 3, 26, true }, // exactly between two ranges, gapless + { 7, 3, 27, false }, // tries to span two ranges + { 7, 5, 28, false }, // tries to span three ranges + { 4, 20, 29, false }, // tries to contain several ranges + + { 30, 50, 30, true }, + { 90, 25, 31, true }, + { 35, 65, 32, false }, // tries to span two noncontiguous + { 120, 10000, 33, true }, // > 8-bit + { 20000, 20000, 34, true }, // > 8-bit + { 0x10001, 0x10001, 35, true }, // > 16-bit + + { 27, -1, 36, false } // tests high < base + }; + + // Attempt to fill the entire space. The entire space must be filled with + // three stores because AddressType is signed for these tests, so RangeMap + // treats the size as signed and rejects sizes that appear to be negative. + // Even if these tests were run as unsigned, two stores would be needed + // to fill the space because the entire size of the space could only be + // described by using one more bit than would be present in AddressType. + const RangeTest range_tests_1[] = { + { INT_MIN, INT_MAX, 50, true }, // From INT_MIN to -2, inclusive + { -1, 2, 51, true }, // From -1 to 0, inclusive + { 1, INT_MAX, 52, true }, // From 1 to INT_MAX, inclusive + { INT_MIN, INT_MAX, 53, false }, // Can't fill the space twice + { -1, 2, 54, false }, + { 1, INT_MAX, 55, false }, + { -3, 6, 56, false }, // -3 to 2, inclusive - spans 3 ranges + }; + + // A light round of testing to verify that RetrieveRange does the right + // the right thing at the extremities of the range when nothing is stored + // there. Checks are forced without storing anything at the extremities + // by setting size = 0. + const RangeTest range_tests_2[] = { + { INT_MIN, 0, 100, false }, // makes RetrieveRange check low end + { -1, 3, 101, true }, + { INT_MAX, 0, 102, false }, // makes RetrieveRange check high end + }; + + // Similar to the previous test set, but with a couple of ranges closer + // to the extremities. + const RangeTest range_tests_3[] = { + { INT_MIN + 1, 1, 110, true }, + { INT_MAX - 1, 1, 111, true }, + { INT_MIN, 0, 112, false }, // makes RetrieveRange check low end + { INT_MAX, 0, 113, false } // makes RetrieveRange check high end + }; + + // The range map is cleared between sets of tests listed here. + const RangeTestSet range_test_sets[] = { + { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) }, + { range_tests_1, sizeof(range_tests_1) / sizeof(RangeTest) }, + { range_tests_2, sizeof(range_tests_2) / sizeof(RangeTest) }, + { range_tests_3, sizeof(range_tests_3) / sizeof(RangeTest) }, + { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) } // Run again + }; + + // Maintain the range map in a pointer so that deletion can be meaningfully + // tested. + scoped_ptr<TestMap> range_map(new TestMap()); + + // Run all of the test sets in sequence. + unsigned int range_test_set_count = sizeof(range_test_sets) / + sizeof(RangeTestSet); + for (unsigned int range_test_set_index = 0; + range_test_set_index < range_test_set_count; + ++range_test_set_index) { + const RangeTest *range_tests = + range_test_sets[range_test_set_index].range_tests; + unsigned int range_test_count = + range_test_sets[range_test_set_index].range_test_count; + + // Run the StoreRange test, which validates StoreRange and initializes + // the RangeMap with data for the RetrieveRange test. + int stored_count = 0; // The number of ranges successfully stored + for (unsigned int range_test_index = 0; + range_test_index < range_test_count; + ++range_test_index) { + const RangeTest *range_test = &range_tests[range_test_index]; + if (!StoreTest(range_map.get(), range_test)) + return false; + + if (range_test->expect_storable) + ++stored_count; + } + + // There should be exactly one CountedObject for everything successfully + // stored in the RangeMap. + if (CountedObject::count() != stored_count) { + fprintf(stderr, "FAILED: " + "stored object counts don't match, expected %d, observed %d\n", + stored_count, + CountedObject::count()); + + return false; + } + + // The RangeMap's own count of objects should also match. + if (range_map->GetCount() != stored_count) { + fprintf(stderr, "FAILED: stored object count doesn't match GetCount, " + "expected %d, observed %d\n", + stored_count, range_map->GetCount()); + + return false; + } + + // Run the RetrieveRange test + for (unsigned int range_test_index = 0; + range_test_index < range_test_count; + ++range_test_index) { + const RangeTest *range_test = &range_tests[range_test_index]; + if (!RetrieveTest(range_map.get(), range_test)) + return false; + } + + if (!RetrieveIndexTest(range_map.get(), range_test_set_index)) + return false; + + // Clear the map between test sets. If this is the final test set, + // delete the map instead to test destruction. + if (range_test_set_index < range_test_set_count - 1) + range_map->Clear(); + else + range_map.reset(); + + // Test that all stored objects are freed when the RangeMap is cleared + // or deleted. + if (CountedObject::count() != 0) { + fprintf(stderr, "FAILED: " + "did not free all objects after %s, %d still allocated\n", + range_test_set_index < range_test_set_count - 1 ? "clear" + : "delete", + CountedObject::count()); + + return false; + } + } + + if (!RetriveAtIndexTest2()) { + fprintf(stderr, "FAILED: did not pass RetrieveAtIndexTest2()\n"); + return false; + } + + return true; +} + + +} // namespace + + +int main(int argc, char **argv) { + BPLOG_INIT(&argc, &argv); + + return RunTests() ? 0 : 1; +} |