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, 0 insertions, 559 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 deleted file mode 100644 index 31b89e5de..000000000 --- a/toolkit/crashreporter/google-breakpad/src/processor/range_map_unittest.cc +++ /dev/null @@ -1,559 +0,0 @@ -// 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; -} |