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 // static_range_map_unittest.cc: Unit tests for StaticRangeMap. 31 // 32 // Author: Siyang Xie (lambxsy (at) google.com) 33 34 #include "breakpad_googletest_includes.h" 35 #include "common/scoped_ptr.h" 36 #include "processor/range_map-inl.h" 37 #include "processor/static_range_map-inl.h" 38 #include "processor/simple_serializer-inl.h" 39 #include "processor/map_serializers-inl.h" 40 #include "processor/logging.h" 41 42 43 namespace { 44 // Types used for testing. 45 typedef int AddressType; 46 typedef int EntryType; 47 typedef google_breakpad::StaticRangeMap< AddressType, EntryType > TestMap; 48 typedef google_breakpad::RangeMap< AddressType, EntryType > RMap; 49 50 // RangeTest contains data to use for store and retrieve tests. See 51 // RunTests for descriptions of the tests. 52 struct RangeTest { 53 // Base address to use for test 54 AddressType address; 55 56 // Size of range to use for test 57 AddressType size; 58 59 // Unique ID of range - unstorable ranges must have unique IDs too 60 EntryType id; 61 62 // Whether this range is expected to be stored successfully or not 63 bool expect_storable; 64 }; 65 66 // A RangeTestSet encompasses multiple RangeTests, which are run in 67 // sequence on the same RangeMap. 68 struct RangeTestSet { 69 // An array of RangeTests 70 const RangeTest* range_tests; 71 72 // The number of tests in the set 73 unsigned int range_test_count; 74 }; 75 76 // These tests will be run sequentially. The first set of tests exercises 77 // most functions of RangeTest, and verifies all of the bounds-checking. 78 const RangeTest range_tests_0[] = { 79 { INT_MIN, 16, 1, true }, // lowest possible range 80 { -2, 5, 2, true }, // a range through zero 81 { INT_MAX - 9, 11, 3, false }, // tests anti-overflow 82 { INT_MAX - 9, 10, 4, true }, // highest possible range 83 { 5, 0, 5, false }, // tests anti-zero-size 84 { 5, 1, 6, true }, // smallest possible range 85 { -20, 15, 7, true }, // entirely negative 86 87 { 10, 10, 10, true }, // causes the following tests to fail 88 { 9, 10, 11, false }, // one-less base, one-less high 89 { 9, 11, 12, false }, // one-less base, identical high 90 { 9, 12, 13, false }, // completely contains existing 91 { 10, 9, 14, false }, // identical base, one-less high 92 { 10, 10, 15, false }, // exactly identical to existing range 93 { 10, 11, 16, false }, // identical base, one-greater high 94 { 11, 8, 17, false }, // contained completely within 95 { 11, 9, 18, false }, // one-greater base, identical high 96 { 11, 10, 19, false }, // one-greater base, one-greater high 97 { 9, 2, 20, false }, // overlaps bottom by one 98 { 10, 1, 21, false }, // overlaps bottom by one, contained 99 { 19, 1, 22, false }, // overlaps top by one, contained 100 { 19, 2, 23, false }, // overlaps top by one 101 102 { 9, 1, 24, true }, // directly below without overlap 103 { 20, 1, 25, true }, // directly above without overlap 104 105 { 6, 3, 26, true }, // exactly between two ranges, gapless 106 { 7, 3, 27, false }, // tries to span two ranges 107 { 7, 5, 28, false }, // tries to span three ranges 108 { 4, 20, 29, false }, // tries to contain several ranges 109 110 { 30, 50, 30, true }, 111 { 90, 25, 31, true }, 112 { 35, 65, 32, false }, // tries to span two noncontiguous 113 { 120, 10000, 33, true }, // > 8-bit 114 { 20000, 20000, 34, true }, // > 8-bit 115 { 0x10001, 0x10001, 35, true }, // > 16-bit 116 117 { 27, -1, 36, false } // tests high < base 118 }; 119 120 // Attempt to fill the entire space. The entire space must be filled with 121 // three stores because AddressType is signed for these tests, so RangeMap 122 // treats the size as signed and rejects sizes that appear to be negative. 123 // Even if these tests were run as unsigned, two stores would be needed 124 // to fill the space because the entire size of the space could only be 125 // described by using one more bit than would be present in AddressType. 126 const RangeTest range_tests_1[] = { 127 { INT_MIN, INT_MAX, 50, true }, // From INT_MIN to -2, inclusive 128 { -1, 2, 51, true }, // From -1 to 0, inclusive 129 { 1, INT_MAX, 52, true }, // From 1 to INT_MAX, inclusive 130 { INT_MIN, INT_MAX, 53, false }, // Can't fill the space twice 131 { -1, 2, 54, false }, 132 { 1, INT_MAX, 55, false }, 133 { -3, 6, 56, false }, // -3 to 2, inclusive - spans 3 ranges 134 }; 135 136 // A light round of testing to verify that RetrieveRange does the right 137 // the right thing at the extremities of the range when nothing is stored 138 // there. Checks are forced without storing anything at the extremities 139 // by setting size = 0. 140 const RangeTest range_tests_2[] = { 141 { INT_MIN, 0, 100, false }, // makes RetrieveRange check low end 142 { -1, 3, 101, true }, 143 { INT_MAX, 0, 102, false }, // makes RetrieveRange check high end 144 }; 145 146 // Similar to the previous test set, but with a couple of ranges closer 147 // to the extremities. 148 const RangeTest range_tests_3[] = { 149 { INT_MIN + 1, 1, 110, true }, 150 { INT_MAX - 1, 1, 111, true }, 151 { INT_MIN, 0, 112, false }, // makes RetrieveRange check low end 152 { INT_MAX, 0, 113, false } // makes RetrieveRange check high end 153 }; 154 155 // The range map is cleared between sets of tests listed here. 156 const RangeTestSet range_test_sets[] = { 157 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) }, 158 { range_tests_1, sizeof(range_tests_1) / sizeof(RangeTest) }, 159 { range_tests_2, sizeof(range_tests_2) / sizeof(RangeTest) }, 160 { range_tests_3, sizeof(range_tests_3) / sizeof(RangeTest) }, 161 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) } // Run again 162 }; 163 164 } // namespace 165 166 namespace google_breakpad { 167 class TestStaticRangeMap : public ::testing::Test { 168 protected: 169 void SetUp() { 170 kTestCasesCount_ = sizeof(range_test_sets) / sizeof(RangeTestSet); 171 } 172 173 // StoreTest uses the data in a RangeTest and calls StoreRange on the 174 // test RangeMap. It returns true if the expected result occurred, and 175 // false if something else happened. 176 void StoreTest(RMap* range_map, const RangeTest* range_test); 177 178 // RetrieveTest uses the data in RangeTest and calls RetrieveRange on the 179 // test RangeMap. If it retrieves the expected value (which can be no 180 // map entry at the specified range,) it returns true, otherwise, it returns 181 // false. RetrieveTest will check the values around the base address and 182 // the high address of a range to guard against off-by-one errors. 183 void RetrieveTest(TestMap* range_map, const RangeTest* range_test); 184 185 // Test RetrieveRangeAtIndex, which is supposed to return objects in order 186 // according to their addresses. This test is performed by looping through 187 // the map, calling RetrieveRangeAtIndex for all possible indices in sequence, 188 // and verifying that each call returns a different object than the previous 189 // call, and that ranges are returned with increasing base addresses. Returns 190 // false if the test fails. 191 void RetrieveIndexTest(const TestMap* range_map, int set); 192 193 void RunTestCase(int test_case); 194 195 unsigned int kTestCasesCount_; 196 RangeMapSerializer<AddressType, EntryType> serializer_; 197 }; 198 199 void TestStaticRangeMap::StoreTest(RMap* range_map, 200 const RangeTest* range_test) { 201 bool stored = range_map->StoreRange(range_test->address, 202 range_test->size, 203 range_test->id); 204 EXPECT_EQ(stored, range_test->expect_storable) 205 << "StoreRange id " << range_test->id << "FAILED"; 206 } 207 208 void TestStaticRangeMap::RetrieveTest(TestMap* range_map, 209 const RangeTest* range_test) { 210 for (unsigned int side = 0; side <= 1; ++side) { 211 // When side == 0, check the low side (base address) of each range. 212 // When side == 1, check the high side (base + size) of each range. 213 214 // Check one-less and one-greater than the target address in addition 215 // to the target address itself. 216 217 // If the size of the range is only 1, don't check one greater than 218 // the base or one less than the high - for a successfully stored 219 // range, these tests would erroneously fail because the range is too 220 // small. 221 AddressType low_offset = -1; 222 AddressType high_offset = 1; 223 if (range_test->size == 1) { 224 if (!side) // When checking the low side, 225 high_offset = 0; // don't check one over the target. 226 else // When checking the high side, 227 low_offset = 0; // don't check one under the target. 228 } 229 230 for (AddressType offset = low_offset; offset <= high_offset; ++offset) { 231 AddressType address = 232 offset + 233 (!side ? range_test->address : 234 range_test->address + range_test->size - 1); 235 236 bool expected_result = false; // This is correct for tests not stored. 237 if (range_test->expect_storable) { 238 if (offset == 0) // When checking the target address, 239 expected_result = true; // test should always succeed. 240 else if (offset == -1) // When checking one below the target, 241 expected_result = side; // should fail low and succeed high. 242 else // When checking one above the target, 243 expected_result = !side; // should succeed low and fail high. 244 } 245 246 const EntryType* id; 247 AddressType retrieved_base; 248 AddressType retrieved_size; 249 bool retrieved = range_map->RetrieveRange(address, id, 250 &retrieved_base, 251 &retrieved_size); 252 253 bool observed_result = retrieved && *id == range_test->id; 254 EXPECT_EQ(observed_result, expected_result) 255 << "RetrieveRange id " << range_test->id 256 << ", side " << side << ", offset " << offset << " FAILED."; 257 258 // If a range was successfully retrieved, check that the returned 259 // bounds match the range as stored. 260 if (observed_result == true) { 261 EXPECT_EQ(retrieved_base, range_test->address) 262 << "RetrieveRange id " << range_test->id 263 << ", side " << side << ", offset " << offset << " FAILED."; 264 EXPECT_EQ(retrieved_size, range_test->size) 265 << "RetrieveRange id " << range_test->id 266 << ", side " << side << ", offset " << offset << " FAILED."; 267 } 268 269 // Now, check RetrieveNearestRange. The nearest range is always 270 // expected to be different from the test range when checking one 271 // less than the low side. 272 bool expected_nearest = range_test->expect_storable; 273 if (!side && offset < 0) 274 expected_nearest = false; 275 276 AddressType nearest_base; 277 AddressType nearest_size; 278 bool retrieved_nearest = range_map->RetrieveNearestRange(address, 279 id, 280 &nearest_base, 281 &nearest_size); 282 283 // When checking one greater than the high side, RetrieveNearestRange 284 // should usually return the test range. When a different range begins 285 // at that address, though, then RetrieveNearestRange should return the 286 // range at the address instead of the test range. 287 if (side && offset > 0 && nearest_base == address) { 288 expected_nearest = false; 289 } 290 291 bool observed_nearest = retrieved_nearest && 292 *id == range_test->id; 293 294 EXPECT_EQ(observed_nearest, expected_nearest) 295 << "RetrieveRange id " << range_test->id 296 << ", side " << side << ", offset " << offset << " FAILED."; 297 298 // If a range was successfully retrieved, check that the returned 299 // bounds match the range as stored. 300 if (expected_nearest ==true) { 301 EXPECT_EQ(nearest_base, range_test->address) 302 << "RetrieveRange id " << range_test->id 303 << ", side " << side << ", offset " << offset << " FAILED."; 304 EXPECT_EQ(nearest_size, range_test->size) 305 << "RetrieveRange id " << range_test->id 306 << ", side " << side << ", offset " << offset << " FAILED."; 307 } 308 } 309 } 310 } 311 312 void TestStaticRangeMap::RetrieveIndexTest(const TestMap* range_map, int set) { 313 AddressType last_base = 0; 314 const EntryType* last_entry = 0; 315 const EntryType* entry; 316 int object_count = range_map->GetCount(); 317 for (int object_index = 0; object_index < object_count; ++object_index) { 318 AddressType base; 319 ASSERT_TRUE(range_map->RetrieveRangeAtIndex(object_index, 320 entry, 321 &base, 322 NULL)) 323 << "FAILED: RetrieveRangeAtIndex set " << set 324 << " index " << object_index; 325 326 ASSERT_TRUE(entry) << "FAILED: RetrieveRangeAtIndex set " << set 327 << " index " << object_index; 328 329 // It's impossible to do these comparisons unless there's a previous 330 // object to compare against. 331 if (last_entry) { 332 // The object must be different from the last_entry one. 333 EXPECT_NE(*entry, *last_entry) << "FAILED: RetrieveRangeAtIndex set " 334 << set << " index " << object_index; 335 // Each object must have a base greater than the previous object's base. 336 EXPECT_GT(base, last_base) << "FAILED: RetrieveRangeAtIndex set " << set 337 << " index " << object_index; 338 } 339 last_entry = entry; 340 last_base = base; 341 } 342 343 // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that 344 // are too high. 345 ASSERT_FALSE(range_map->RetrieveRangeAtIndex( 346 object_count, entry, NULL, NULL)) << "FAILED: RetrieveRangeAtIndex set " 347 << set << " index " << object_count 348 << " (too large)"; 349 } 350 351 // RunTests runs a series of test sets. 352 void TestStaticRangeMap::RunTestCase(int test_case) { 353 // Maintain the range map in a pointer so that deletion can be meaningfully 354 // tested. 355 scoped_ptr<RMap> rmap(new RMap()); 356 357 const RangeTest* range_tests = range_test_sets[test_case].range_tests; 358 unsigned int range_test_count = range_test_sets[test_case].range_test_count; 359 360 // Run the StoreRange test, which validates StoreRange and initializes 361 // the RangeMap with data for the RetrieveRange test. 362 int stored_count = 0; // The number of ranges successfully stored 363 for (unsigned int range_test_index = 0; 364 range_test_index < range_test_count; 365 ++range_test_index) { 366 const RangeTest* range_test = &range_tests[range_test_index]; 367 StoreTest(rmap.get(), range_test); 368 369 if (range_test->expect_storable) 370 ++stored_count; 371 } 372 373 scoped_array<char> memaddr(serializer_.Serialize(*rmap, NULL)); 374 scoped_ptr<TestMap> static_range_map(new TestMap(memaddr.get())); 375 376 // The RangeMap's own count of objects should also match. 377 EXPECT_EQ(static_range_map->GetCount(), stored_count); 378 379 // Run the RetrieveRange test 380 for (unsigned int range_test_index = 0; 381 range_test_index < range_test_count; 382 ++range_test_index) { 383 const RangeTest* range_test = &range_tests[range_test_index]; 384 RetrieveTest(static_range_map.get(), range_test); 385 } 386 387 RetrieveIndexTest(static_range_map.get(), test_case); 388 } 389 390 TEST_F(TestStaticRangeMap, TestCase0) { 391 int test_case = 0; 392 RunTestCase(test_case); 393 } 394 395 TEST_F(TestStaticRangeMap, TestCase1) { 396 int test_case = 1; 397 RunTestCase(test_case); 398 } 399 400 TEST_F(TestStaticRangeMap, TestCase2) { 401 int test_case = 2; 402 RunTestCase(test_case); 403 } 404 405 TEST_F(TestStaticRangeMap, TestCase3) { 406 int test_case = 3; 407 RunTestCase(test_case); 408 } 409 410 TEST_F(TestStaticRangeMap, RunTestCase0Again) { 411 int test_case = 0; 412 RunTestCase(test_case); 413 } 414 415 } // namespace google_breakpad 416 417 int main(int argc, char *argv[]) { 418 ::testing::InitGoogleTest(&argc, argv); 419 420 return RUN_ALL_TESTS(); 421 } 422
