aboutsummaryrefslogtreecommitdiff
path: root/src/processor/static_range_map_unittest.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/processor/static_range_map_unittest.cc')
-rw-r--r--src/processor/static_range_map_unittest.cc427
1 files changed, 427 insertions, 0 deletions
diff --git a/src/processor/static_range_map_unittest.cc b/src/processor/static_range_map_unittest.cc
new file mode 100644
index 00000000..d4163e28
--- /dev/null
+++ b/src/processor/static_range_map_unittest.cc
@@ -0,0 +1,427 @@
+// 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.
+
+// static_range_map_unittest.cc: Unit tests for StaticRangeMap.
+//
+// Author: Siyang Xie (lambxsy@google.com)
+
+#include "breakpad_googletest_includes.h"
+#include "processor/range_map-inl.h"
+#include "processor/static_range_map-inl.h"
+#include "processor/simple_serializer-inl.h"
+#include "processor/map_serializers-inl.h"
+
+#include "processor/logging.h"
+#include "processor/scoped_ptr.h"
+
+using google_breakpad::StaticRangeMap;
+using google_breakpad::RangeMap;
+
+// Types used for testing.
+typedef int AddressType;
+typedef int EntryType;
+typedef StaticRangeMap< AddressType, EntryType > TestMap;
+typedef RangeMap< AddressType, EntryType > RMap;
+
+// 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
+ EntryType 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;
+};
+
+namespace {
+ // 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
+ };
+}
+
+class TestStaticRangeMap : public ::testing::Test {
+ protected:
+ void SetUp() {
+ kTestCasesCount_ = sizeof(range_test_sets) / sizeof(RangeTestSet);
+ }
+
+ // 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.
+ void StoreTest(RMap* range_map, const RangeTest* range_test);
+
+ // 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.
+ void RetrieveTest(TestMap* range_map, const RangeTest* range_test);
+
+ // 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.
+ void RetrieveIndexTest(const TestMap* range_map, int set);
+
+ void RunTestCase(int test_case);
+
+ unsigned int kTestCasesCount_;
+ google_breakpad::RangeMapSerializer<AddressType, EntryType> serializer_;
+};
+
+void TestStaticRangeMap::StoreTest(RMap* range_map,
+ const RangeTest* range_test) {
+ bool stored = range_map->StoreRange(range_test->address,
+ range_test->size,
+ range_test->id);
+ EXPECT_EQ(stored, range_test->expect_storable)
+ << "StoreRange id " << range_test->id << "FAILED";
+}
+
+void TestStaticRangeMap::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.
+ }
+
+ const EntryType* id;
+ AddressType retrieved_base;
+ AddressType retrieved_size;
+ bool retrieved = range_map->RetrieveRange(address, id,
+ &retrieved_base,
+ &retrieved_size);
+
+ bool observed_result = retrieved && *id == range_test->id;
+ EXPECT_EQ(observed_result, expected_result)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+
+ // If a range was successfully retrieved, check that the returned
+ // bounds match the range as stored.
+ if (observed_result == true) {
+ EXPECT_EQ(retrieved_base, range_test->address)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+ EXPECT_EQ(retrieved_size, range_test->size)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+ }
+
+ // 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;
+
+ AddressType nearest_base;
+ AddressType nearest_size;
+ bool retrieved_nearest = range_map->RetrieveNearestRange(address,
+ id,
+ &nearest_base,
+ &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 &&
+ *id == range_test->id;
+
+ EXPECT_EQ(observed_nearest, expected_nearest)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+
+ // If a range was successfully retrieved, check that the returned
+ // bounds match the range as stored.
+ if (expected_nearest ==true) {
+ EXPECT_EQ(nearest_base, range_test->address)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+ EXPECT_EQ(nearest_size, range_test->size)
+ << "RetrieveRange id " << range_test->id
+ << ", side " << side << ", offset " << offset << " FAILED.";
+ }
+ }
+ }
+}
+
+void TestStaticRangeMap::RetrieveIndexTest(const TestMap* range_map, int set) {
+ AddressType last_base = 0;
+ const EntryType* last_entry = 0;
+ const EntryType* entry;
+ int object_count = range_map->GetCount();
+ for (int object_index = 0; object_index < object_count; ++object_index) {
+ AddressType base;
+ ASSERT_TRUE(range_map->RetrieveRangeAtIndex(object_index,
+ entry,
+ &base,
+ NULL))
+ << "FAILED: RetrieveRangeAtIndex set " << set
+ << " index " << object_index;
+
+ ASSERT_TRUE(entry) << "FAILED: RetrieveRangeAtIndex set " << set
+ << " index " << object_index;
+
+ // It's impossible to do these comparisons unless there's a previous
+ // object to compare against.
+ if (last_entry) {
+ // The object must be different from the last_entry one.
+ EXPECT_NE(*entry, *last_entry) << "FAILED: RetrieveRangeAtIndex set "
+ << set << " index " << object_index;
+ // Each object must have a base greater than the previous object's base.
+ EXPECT_GT(base, last_base) << "FAILED: RetrieveRangeAtIndex set " << set
+ << " index " << object_index;
+ }
+ last_entry = entry;
+ last_base = base;
+ }
+
+ // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that
+ // are too high.
+ ASSERT_FALSE(range_map->RetrieveRangeAtIndex(
+ object_count, entry, NULL, NULL)) << "FAILED: RetrieveRangeAtIndex set "
+ << set << " index " << object_count
+ << " (too large)";
+}
+
+// RunTests runs a series of test sets.
+void TestStaticRangeMap::RunTestCase(int test_case) {
+ // Maintain the range map in a pointer so that deletion can be meaningfully
+ // tested.
+ RMap* rmap = new RMap();
+
+ const RangeTest* range_tests = range_test_sets[test_case].range_tests;
+ unsigned int range_test_count = range_test_sets[test_case].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];
+ StoreTest(rmap, range_test);
+
+ if (range_test->expect_storable)
+ ++stored_count;
+ }
+
+ char *memaddr = serializer_.Serialize(*rmap, NULL);
+ TestMap* static_range_map = new TestMap(memaddr);
+
+ // The RangeMap's own count of objects should also match.
+ EXPECT_EQ(static_range_map->GetCount(), stored_count);
+
+ // 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];
+ RetrieveTest(static_range_map, range_test);
+ }
+
+ RetrieveIndexTest(static_range_map, test_case);
+
+ // Clear the map between test sets. If this is the final test set,
+ // delete the map instead to test destruction.
+ delete memaddr;
+ delete static_range_map;
+ rmap->Clear();
+ delete rmap;
+}
+
+TEST_F(TestStaticRangeMap, TestCase0) {
+ int test_case = 0;
+ RunTestCase(test_case);
+}
+
+TEST_F(TestStaticRangeMap, TestCase1) {
+ int test_case = 1;
+ RunTestCase(test_case);
+}
+
+TEST_F(TestStaticRangeMap, TestCase2) {
+ int test_case = 2;
+ RunTestCase(test_case);
+}
+
+TEST_F(TestStaticRangeMap, TestCase3) {
+ int test_case = 3;
+ RunTestCase(test_case);
+}
+
+TEST_F(TestStaticRangeMap, RunTestCase0Again) {
+ int test_case = 0;
+ RunTestCase(test_case);
+}
+
+int main(int argc, char *argv[]) {
+ ::testing::InitGoogleTest(&argc, argv);
+
+ return RUN_ALL_TESTS();
+}