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