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