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 // range_map_unittest.cc: Unit tests for RangeMap
31 //
32 // Author: Mark Mentovai
33
34
35 #include <limits.h>
36 #include <stdio.h>
37
38 #include "processor/range_map-inl.h"
39
40 #include "common/scoped_ptr.h"
41 #include "processor/linked_ptr.h"
42 #include "processor/logging.h"
43
44 namespace {
45
46
47 using google_breakpad::linked_ptr;
48 using google_breakpad::scoped_ptr;
49 using google_breakpad::RangeMap;
50
51
52 // A CountedObject holds an int. A global (not thread safe!) count of
53 // allocated CountedObjects is maintained to help test memory management.
54 class CountedObject {
55 public:
CountedObject(int id)56 explicit CountedObject(int id) : id_(id) { ++count_; }
~CountedObject()57 ~CountedObject() { --count_; }
58
count()59 static int count() { return count_; }
id() const60 int id() const { return id_; }
61
62 private:
63 static int count_;
64 int id_;
65 };
66
67 int CountedObject::count_;
68
69
70 typedef int AddressType;
71 typedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap;
72
73
74 // RangeTest contains data to use for store and retrieve tests. See
75 // RunTests for descriptions of the tests.
76 struct RangeTest {
77 // Base address to use for test
78 AddressType address;
79
80 // Size of range to use for test
81 AddressType size;
82
83 // Unique ID of range - unstorable ranges must have unique IDs too
84 int id;
85
86 // Whether this range is expected to be stored successfully or not
87 bool expect_storable;
88 };
89
90
91 // A RangeTestSet encompasses multiple RangeTests, which are run in
92 // sequence on the same RangeMap.
93 struct RangeTestSet {
94 // An array of RangeTests
95 const RangeTest *range_tests;
96
97 // The number of tests in the set
98 unsigned int range_test_count;
99 };
100
101
102 // StoreTest uses the data in a RangeTest and calls StoreRange on the
103 // test RangeMap. It returns true if the expected result occurred, and
104 // false if something else happened.
StoreTest(TestMap * range_map,const RangeTest * range_test)105 static bool StoreTest(TestMap *range_map, const RangeTest *range_test) {
106 linked_ptr<CountedObject> object(new CountedObject(range_test->id));
107 bool stored = range_map->StoreRange(range_test->address,
108 range_test->size,
109 object);
110
111 if (stored != range_test->expect_storable) {
112 fprintf(stderr, "FAILED: "
113 "StoreRange id %d, expected %s, observed %s\n",
114 range_test->id,
115 range_test->expect_storable ? "storable" : "not storable",
116 stored ? "stored" : "not stored");
117 return false;
118 }
119
120 return true;
121 }
122
123
124 // RetrieveTest uses the data in RangeTest and calls RetrieveRange on the
125 // test RangeMap. If it retrieves the expected value (which can be no
126 // map entry at the specified range,) it returns true, otherwise, it returns
127 // false. RetrieveTest will check the values around the base address and
128 // the high address of a range to guard against off-by-one errors.
RetrieveTest(TestMap * range_map,const RangeTest * range_test)129 static bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) {
130 for (unsigned int side = 0; side <= 1; ++side) {
131 // When side == 0, check the low side (base address) of each range.
132 // When side == 1, check the high side (base + size) of each range.
133
134 // Check one-less and one-greater than the target address in addition
135 // to the target address itself.
136
137 // If the size of the range is only 1, don't check one greater than
138 // the base or one less than the high - for a successfully stored
139 // range, these tests would erroneously fail because the range is too
140 // small.
141 AddressType low_offset = -1;
142 AddressType high_offset = 1;
143 if (range_test->size == 1) {
144 if (!side) // When checking the low side,
145 high_offset = 0; // don't check one over the target.
146 else // When checking the high side,
147 low_offset = 0; // don't check one under the target.
148 }
149
150 for (AddressType offset = low_offset; offset <= high_offset; ++offset) {
151 AddressType address =
152 offset +
153 (!side ? range_test->address :
154 range_test->address + range_test->size - 1);
155
156 bool expected_result = false; // This is correct for tests not stored.
157 if (range_test->expect_storable) {
158 if (offset == 0) // When checking the target address,
159 expected_result = true; // test should always succeed.
160 else if (offset == -1) // When checking one below the target,
161 expected_result = side; // should fail low and succeed high.
162 else // When checking one above the target,
163 expected_result = !side; // should succeed low and fail high.
164 }
165
166 linked_ptr<CountedObject> object;
167 AddressType retrieved_base = AddressType();
168 AddressType retrieved_size = AddressType();
169 AddressType retrieved_delta = AddressType();
170 bool retrieved = range_map->RetrieveRange(address, &object,
171 &retrieved_base,
172 &retrieved_delta,
173 &retrieved_size);
174
175 bool observed_result = retrieved && object->id() == range_test->id;
176
177 if (observed_result != expected_result) {
178 fprintf(stderr, "FAILED: "
179 "RetrieveRange id %d, side %d, offset %d, "
180 "expected %s, observed %s\n",
181 range_test->id,
182 side,
183 offset,
184 expected_result ? "true" : "false",
185 observed_result ? "true" : "false");
186 return false;
187 }
188
189 // If a range was successfully retrieved, check that the returned
190 // bounds match the range as stored.
191 if (observed_result == true &&
192 (retrieved_base != range_test->address ||
193 retrieved_size != range_test->size)) {
194 fprintf(stderr, "FAILED: "
195 "RetrieveRange id %d, side %d, offset %d, "
196 "expected base/size %d/%d, observed %d/%d\n",
197 range_test->id,
198 side,
199 offset,
200 range_test->address, range_test->size,
201 retrieved_base, retrieved_size);
202 return false;
203 }
204
205 // Now, check RetrieveNearestRange. The nearest range is always
206 // expected to be different from the test range when checking one
207 // less than the low side.
208 bool expected_nearest = range_test->expect_storable;
209 if (!side && offset < 0)
210 expected_nearest = false;
211
212 linked_ptr<CountedObject> nearest_object;
213 AddressType nearest_base = AddressType();
214 AddressType nearest_delta = AddressType();
215 AddressType nearest_size = AddressType();
216 bool retrieved_nearest = range_map->RetrieveNearestRange(address,
217 &nearest_object,
218 &nearest_base,
219 &nearest_delta,
220 &nearest_size);
221
222 // When checking one greater than the high side, RetrieveNearestRange
223 // should usually return the test range. When a different range begins
224 // at that address, though, then RetrieveNearestRange should return the
225 // range at the address instead of the test range.
226 if (side && offset > 0 && nearest_base == address) {
227 expected_nearest = false;
228 }
229
230 bool observed_nearest = retrieved_nearest &&
231 nearest_object->id() == range_test->id;
232
233 if (observed_nearest != expected_nearest) {
234 fprintf(stderr, "FAILED: "
235 "RetrieveNearestRange id %d, side %d, offset %d, "
236 "expected %s, observed %s\n",
237 range_test->id,
238 side,
239 offset,
240 expected_nearest ? "true" : "false",
241 observed_nearest ? "true" : "false");
242 return false;
243 }
244
245 // If a range was successfully retrieved, check that the returned
246 // bounds match the range as stored.
247 if (expected_nearest &&
248 (nearest_base != range_test->address ||
249 nearest_size != range_test->size)) {
250 fprintf(stderr, "FAILED: "
251 "RetrieveNearestRange id %d, side %d, offset %d, "
252 "expected base/size %d/%d, observed %d/%d\n",
253 range_test->id,
254 side,
255 offset,
256 range_test->address, range_test->size,
257 nearest_base, nearest_size);
258 return false;
259 }
260 }
261 }
262
263 return true;
264 }
265
266
267 // Test RetrieveRangeAtIndex, which is supposed to return objects in order
268 // according to their addresses. This test is performed by looping through
269 // the map, calling RetrieveRangeAtIndex for all possible indices in sequence,
270 // and verifying that each call returns a different object than the previous
271 // call, and that ranges are returned with increasing base addresses. Returns
272 // false if the test fails.
RetrieveIndexTest(TestMap * range_map,int set)273 static bool RetrieveIndexTest(TestMap *range_map, int set) {
274 linked_ptr<CountedObject> object;
275 CountedObject *last_object = NULL;
276 AddressType last_base = 0;
277
278 int object_count = range_map->GetCount();
279 for (int object_index = 0; object_index < object_count; ++object_index) {
280 AddressType base;
281 if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base,
282 NULL /* delta */, NULL /* size */)) {
283 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
284 "expected success, observed failure\n",
285 set, object_index);
286 return false;
287 }
288
289 if (!object.get()) {
290 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
291 "expected object, observed NULL\n",
292 set, object_index);
293 return false;
294 }
295
296 // It's impossible to do these comparisons unless there's a previous
297 // object to compare against.
298 if (last_object) {
299 // The object must be different from the last one.
300 if (object->id() == last_object->id()) {
301 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
302 "expected different objects, observed same objects (%d)\n",
303 set, object_index, object->id());
304 return false;
305 }
306
307 // Each object must have a base greater than the previous object's base.
308 if (base <= last_base) {
309 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "
310 "expected different bases, observed same bases (%d)\n",
311 set, object_index, base);
312 return false;
313 }
314 }
315
316 last_object = object.get();
317 last_base = base;
318 }
319
320 // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that
321 // are too high.
322 if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL /* base */,
323 NULL /* delta */, NULL /* size */)) {
324 fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), "
325 "expected failure, observed success\n",
326 set, object_count);
327 return false;
328 }
329
330 return true;
331 }
332
333 // Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex().
334 // Bug info: RetrieveRangeAtIndex() previously retrieves the high address of
335 // entry, however, it is supposed to retrieve the base address of entry as
336 // stated in the comment in range_map.h.
RetriveAtIndexTest2()337 static bool RetriveAtIndexTest2() {
338 scoped_ptr<TestMap> range_map(new TestMap());
339
340 // Store ranges with base address = 2 * object_id:
341 const int range_size = 2;
342 for (int object_id = 0; object_id < 100; ++object_id) {
343 linked_ptr<CountedObject> object(new CountedObject(object_id));
344 int base_address = 2 * object_id;
345 range_map->StoreRange(base_address, range_size, object);
346 }
347
348 linked_ptr<CountedObject> object;
349 int object_count = range_map->GetCount();
350 for (int object_index = 0; object_index < object_count; ++object_index) {
351 AddressType base;
352 if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base,
353 NULL /* delta */, NULL /* size */)) {
354 fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, "
355 "expected success, observed failure\n", object_index);
356 return false;
357 }
358
359 int expected_base = 2 * object->id();
360 if (base != expected_base) {
361 fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, "
362 "expected base %d, observed base %d",
363 object_index, expected_base, base);
364 return false;
365 }
366 }
367
368 return true;
369 }
370
371
372 // RunTests runs a series of test sets.
RunTests()373 static bool RunTests() {
374 // These tests will be run sequentially. The first set of tests exercises
375 // most functions of RangeTest, and verifies all of the bounds-checking.
376 const RangeTest range_tests_0[] = {
377 { INT_MIN, 16, 1, true }, // lowest possible range
378 { -2, 5, 2, true }, // a range through zero
379 { INT_MAX - 9, 11, 3, false }, // tests anti-overflow
380 { INT_MAX - 9, 10, 4, true }, // highest possible range
381 { 5, 0, 5, false }, // tests anti-zero-size
382 { 5, 1, 6, true }, // smallest possible range
383 { -20, 15, 7, true }, // entirely negative
384
385 { 10, 10, 10, true }, // causes the following tests to fail
386 { 9, 10, 11, false }, // one-less base, one-less high
387 { 9, 11, 12, false }, // one-less base, identical high
388 { 9, 12, 13, false }, // completely contains existing
389 { 10, 9, 14, false }, // identical base, one-less high
390 { 10, 10, 15, false }, // exactly identical to existing range
391 { 10, 11, 16, false }, // identical base, one-greater high
392 { 11, 8, 17, false }, // contained completely within
393 { 11, 9, 18, false }, // one-greater base, identical high
394 { 11, 10, 19, false }, // one-greater base, one-greater high
395 { 9, 2, 20, false }, // overlaps bottom by one
396 { 10, 1, 21, false }, // overlaps bottom by one, contained
397 { 19, 1, 22, false }, // overlaps top by one, contained
398 { 19, 2, 23, false }, // overlaps top by one
399
400 { 9, 1, 24, true }, // directly below without overlap
401 { 20, 1, 25, true }, // directly above without overlap
402
403 { 6, 3, 26, true }, // exactly between two ranges, gapless
404 { 7, 3, 27, false }, // tries to span two ranges
405 { 7, 5, 28, false }, // tries to span three ranges
406 { 4, 20, 29, false }, // tries to contain several ranges
407
408 { 30, 50, 30, true },
409 { 90, 25, 31, true },
410 { 35, 65, 32, false }, // tries to span two noncontiguous
411 { 120, 10000, 33, true }, // > 8-bit
412 { 20000, 20000, 34, true }, // > 8-bit
413 { 0x10001, 0x10001, 35, true }, // > 16-bit
414
415 { 27, -1, 36, false } // tests high < base
416 };
417
418 // Attempt to fill the entire space. The entire space must be filled with
419 // three stores because AddressType is signed for these tests, so RangeMap
420 // treats the size as signed and rejects sizes that appear to be negative.
421 // Even if these tests were run as unsigned, two stores would be needed
422 // to fill the space because the entire size of the space could only be
423 // described by using one more bit than would be present in AddressType.
424 const RangeTest range_tests_1[] = {
425 { INT_MIN, INT_MAX, 50, true }, // From INT_MIN to -2, inclusive
426 { -1, 2, 51, true }, // From -1 to 0, inclusive
427 { 1, INT_MAX, 52, true }, // From 1 to INT_MAX, inclusive
428 { INT_MIN, INT_MAX, 53, false }, // Can't fill the space twice
429 { -1, 2, 54, false },
430 { 1, INT_MAX, 55, false },
431 { -3, 6, 56, false }, // -3 to 2, inclusive - spans 3 ranges
432 };
433
434 // A light round of testing to verify that RetrieveRange does the right
435 // the right thing at the extremities of the range when nothing is stored
436 // there. Checks are forced without storing anything at the extremities
437 // by setting size = 0.
438 const RangeTest range_tests_2[] = {
439 { INT_MIN, 0, 100, false }, // makes RetrieveRange check low end
440 { -1, 3, 101, true },
441 { INT_MAX, 0, 102, false }, // makes RetrieveRange check high end
442 };
443
444 // Similar to the previous test set, but with a couple of ranges closer
445 // to the extremities.
446 const RangeTest range_tests_3[] = {
447 { INT_MIN + 1, 1, 110, true },
448 { INT_MAX - 1, 1, 111, true },
449 { INT_MIN, 0, 112, false }, // makes RetrieveRange check low end
450 { INT_MAX, 0, 113, false } // makes RetrieveRange check high end
451 };
452
453 // The range map is cleared between sets of tests listed here.
454 const RangeTestSet range_test_sets[] = {
455 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) },
456 { range_tests_1, sizeof(range_tests_1) / sizeof(RangeTest) },
457 { range_tests_2, sizeof(range_tests_2) / sizeof(RangeTest) },
458 { range_tests_3, sizeof(range_tests_3) / sizeof(RangeTest) },
459 { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) } // Run again
460 };
461
462 // Maintain the range map in a pointer so that deletion can be meaningfully
463 // tested.
464 scoped_ptr<TestMap> range_map(new TestMap());
465
466 // Run all of the test sets in sequence.
467 unsigned int range_test_set_count = sizeof(range_test_sets) /
468 sizeof(RangeTestSet);
469 for (unsigned int range_test_set_index = 0;
470 range_test_set_index < range_test_set_count;
471 ++range_test_set_index) {
472 const RangeTest *range_tests =
473 range_test_sets[range_test_set_index].range_tests;
474 unsigned int range_test_count =
475 range_test_sets[range_test_set_index].range_test_count;
476
477 // Run the StoreRange test, which validates StoreRange and initializes
478 // the RangeMap with data for the RetrieveRange test.
479 int stored_count = 0; // The number of ranges successfully stored
480 for (unsigned int range_test_index = 0;
481 range_test_index < range_test_count;
482 ++range_test_index) {
483 const RangeTest *range_test = &range_tests[range_test_index];
484 if (!StoreTest(range_map.get(), range_test))
485 return false;
486
487 if (range_test->expect_storable)
488 ++stored_count;
489 }
490
491 // There should be exactly one CountedObject for everything successfully
492 // stored in the RangeMap.
493 if (CountedObject::count() != stored_count) {
494 fprintf(stderr, "FAILED: "
495 "stored object counts don't match, expected %d, observed %d\n",
496 stored_count,
497 CountedObject::count());
498
499 return false;
500 }
501
502 // The RangeMap's own count of objects should also match.
503 if (range_map->GetCount() != stored_count) {
504 fprintf(stderr, "FAILED: stored object count doesn't match GetCount, "
505 "expected %d, observed %d\n",
506 stored_count, range_map->GetCount());
507
508 return false;
509 }
510
511 // Run the RetrieveRange test
512 for (unsigned int range_test_index = 0;
513 range_test_index < range_test_count;
514 ++range_test_index) {
515 const RangeTest *range_test = &range_tests[range_test_index];
516 if (!RetrieveTest(range_map.get(), range_test))
517 return false;
518 }
519
520 if (!RetrieveIndexTest(range_map.get(), range_test_set_index))
521 return false;
522
523 // Clear the map between test sets. If this is the final test set,
524 // delete the map instead to test destruction.
525 if (range_test_set_index < range_test_set_count - 1)
526 range_map->Clear();
527 else
528 range_map.reset();
529
530 // Test that all stored objects are freed when the RangeMap is cleared
531 // or deleted.
532 if (CountedObject::count() != 0) {
533 fprintf(stderr, "FAILED: "
534 "did not free all objects after %s, %d still allocated\n",
535 range_test_set_index < range_test_set_count - 1 ? "clear"
536 : "delete",
537 CountedObject::count());
538
539 return false;
540 }
541 }
542
543 if (!RetriveAtIndexTest2()) {
544 fprintf(stderr, "FAILED: did not pass RetrieveAtIndexTest2()\n");
545 return false;
546 }
547
548 return true;
549 }
550
551
552 } // namespace
553
554
main(int argc,char ** argv)555 int main(int argc, char **argv) {
556 BPLOG_INIT(&argc, &argv);
557
558 return RunTests() ? 0 : 1;
559 }
560