The Tor Browser / file revision

 // 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.

 // range_map_unittest.cc: Unit tests for RangeMap

 //

 // Author: Mark Mentovai

 #include <limits.h>

 #include <stdio.h>

 #include "processor/range_map-inl.h"

 #include "common/scoped_ptr.h"

 #include "processor/linked_ptr.h"

 #include "processor/logging.h"

 namespace {

 using google_breakpad::linked_ptr;

 using google_breakpad::scoped_ptr;

 using google_breakpad::RangeMap;

 // A CountedObject holds an int.  A global (not thread safe!) count of

 // allocated CountedObjects is maintained to help test memory management.

 class CountedObject {

  public:

   explicit CountedObject(int id) : id_(id) { ++count_; }

   ~CountedObject() { --count_; }

   static int count() { return count_; }

   int id() const { return id_; }

  private:

   static int count_;

   int id_;

 };

 int CountedObject::count_;

 typedef int AddressType;

 typedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap;

 // 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

   int 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;

 };

 // 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.

 static bool StoreTest(TestMap *range_map, const RangeTest *range_test) {

   linked_ptr<CountedObject> object(new CountedObject(range_test->id));

   bool stored = range_map->StoreRange(range_test->address,

                                       range_test->size,

                                       object);

   if (stored != range_test->expect_storable) {

     fprintf(stderr, "FAILED: "

             "StoreRange id %d, expected %s, observed %s\n",

             range_test->id,

             range_test->expect_storable ? "storable" : "not storable",

             stored ? "stored" : "not stored");

     return false;

   }

   return true;

 }

 // 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.

 static bool 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.

       }

       linked_ptr<CountedObject> object;

       AddressType retrieved_base = AddressType();

       AddressType retrieved_size = AddressType();

       bool retrieved = range_map->RetrieveRange(address, &object,

                                                 &retrieved_base,

                                                 &retrieved_size);

       bool observed_result = retrieved && object->id() == range_test->id;

       if (observed_result != expected_result) {

         fprintf(stderr, "FAILED: "

                         "RetrieveRange id %d, side %d, offset %d, "

                         "expected %s, observed %s\n",

                         range_test->id,

                         side,

                         offset,

                         expected_result ? "true" : "false",

                         observed_result ? "true" : "false");

         return false;

       }

       // If a range was successfully retrieved, check that the returned

       // bounds match the range as stored.

       if (observed_result == true &&

           (retrieved_base != range_test->address ||

            retrieved_size != range_test->size)) {

         fprintf(stderr, "FAILED: "

                         "RetrieveRange id %d, side %d, offset %d, "

                         "expected base/size %d/%d, observed %d/%d\n",

                         range_test->id,

                         side,

                         offset,

                         range_test->address, range_test->size,

                         retrieved_base, retrieved_size);

         return false;

       }

       // 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;

       linked_ptr<CountedObject> nearest_object;

       AddressType nearest_base = AddressType();

       AddressType nearest_size = AddressType();

       bool retrieved_nearest = range_map->RetrieveNearestRange(address,

                                                                &nearest_object,

                                                                &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 &&

                               nearest_object->id() == range_test->id;

       if (observed_nearest != expected_nearest) {

         fprintf(stderr, "FAILED: "

                         "RetrieveNearestRange id %d, side %d, offset %d, "

                         "expected %s, observed %s\n",

                         range_test->id,

                         side,

                         offset,

                         expected_nearest ? "true" : "false",

                         observed_nearest ? "true" : "false");

         return false;

       }

       // If a range was successfully retrieved, check that the returned

       // bounds match the range as stored.

       if (expected_nearest &&

           (nearest_base != range_test->address ||

            nearest_size != range_test->size)) {

         fprintf(stderr, "FAILED: "

                         "RetrieveNearestRange id %d, side %d, offset %d, "

                         "expected base/size %d/%d, observed %d/%d\n",

                         range_test->id,

                         side,

                         offset,

                         range_test->address, range_test->size,

                         nearest_base, nearest_size);

         return false;

       }

     }

   }

   return true;

 }

 // 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.

 static bool RetrieveIndexTest(TestMap *range_map, int set) {

   linked_ptr<CountedObject> object;

   CountedObject *last_object = NULL;

   AddressType last_base = 0;

   int object_count = range_map->GetCount();

   for (int object_index = 0; object_index < object_count; ++object_index) {

     AddressType base;

     if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) {

       fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "

               "expected success, observed failure\n",

               set, object_index);

       return false;

     }

     if (!object.get()) {

       fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "

               "expected object, observed NULL\n",

               set, object_index);

       return false;

     }

     // It's impossible to do these comparisons unless there's a previous

     // object to compare against.

     if (last_object) {

       // The object must be different from the last one.

       if (object->id() == last_object->id()) {

         fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "

                 "expected different objects, observed same objects (%d)\n",

                 set, object_index, object->id());

         return false;

       }

       // Each object must have a base greater than the previous object's base.

       if (base <= last_base) {

         fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, "

                 "expected different bases, observed same bases (%d)\n",

                 set, object_index, base);

         return false;

       }

     }

     last_object = object.get();

     last_base = base;

   }

   // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that

   // are too high.

   if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL, NULL)) {

     fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), "

             "expected failure, observed success\n",

             set, object_count);

     return false;

   }

   return true;

 }

 // Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex().

 // Bug info: RetrieveRangeAtIndex() previously retrieves the high address of

 // entry, however, it is supposed to retrieve the base address of entry as

 // stated in the comment in range_map.h.

 static bool RetriveAtIndexTest2() {

   scoped_ptr<TestMap> range_map(new TestMap());

   // Store ranges with base address = 2 * object_id:

   const int range_size = 2;

   for (int object_id = 0; object_id < 100; ++object_id) {

     linked_ptr<CountedObject> object(new CountedObject(object_id));

     int base_address = 2 * object_id;

     range_map->StoreRange(base_address, range_size, object);

   }

   linked_ptr<CountedObject> object;

   int object_count = range_map->GetCount();

   for (int object_index = 0; object_index < object_count; ++object_index) {

     AddressType base;

     if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) {

       fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, "

               "expected success, observed failure\n", object_index);

       return false;

     }

     int expected_base = 2 * object->id();

     if (base != expected_base) {

       fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, "

               "expected base %d, observed base %d",

               object_index, expected_base, base);

       return false;

     }

   }

   return true;

 }

 // RunTests runs a series of test sets.

 static bool RunTests() {

   // 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

   };

   // Maintain the range map in a pointer so that deletion can be meaningfully

   // tested.

   scoped_ptr<TestMap> range_map(new TestMap());

   // Run all of the test sets in sequence.

   unsigned int range_test_set_count = sizeof(range_test_sets) /

                                       sizeof(RangeTestSet);

   for (unsigned int range_test_set_index = 0;

        range_test_set_index < range_test_set_count;

        ++range_test_set_index) {

     const RangeTest *range_tests =

         range_test_sets[range_test_set_index].range_tests;

     unsigned int range_test_count =

         range_test_sets[range_test_set_index].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];

       if (!StoreTest(range_map.get(), range_test))

         return false;

       if (range_test->expect_storable)

         ++stored_count;

     }

     // There should be exactly one CountedObject for everything successfully

     // stored in the RangeMap.

     if (CountedObject::count() != stored_count) {

       fprintf(stderr, "FAILED: "

               "stored object counts don't match, expected %d, observed %d\n",

               stored_count,

               CountedObject::count());

       return false;

     }

     // The RangeMap's own count of objects should also match.

     if (range_map->GetCount() != stored_count) {

       fprintf(stderr, "FAILED: stored object count doesn't match GetCount, "

               "expected %d, observed %d\n",

               stored_count, range_map->GetCount());

       return false;

     }

     // 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];

       if (!RetrieveTest(range_map.get(), range_test))

         return false;

     }

     if (!RetrieveIndexTest(range_map.get(), range_test_set_index))

       return false;

     // Clear the map between test sets.  If this is the final test set,

     // delete the map instead to test destruction.

     if (range_test_set_index < range_test_set_count - 1)

       range_map->Clear();

     else

       range_map.reset();

     // Test that all stored objects are freed when the RangeMap is cleared

     // or deleted.

     if (CountedObject::count() != 0) {

       fprintf(stderr, "FAILED: "

               "did not free all objects after %s, %d still allocated\n",

               range_test_set_index < range_test_set_count - 1 ? "clear"

                                                               : "delete",

               CountedObject::count());

       return false;

     }

   }

   if (!RetriveAtIndexTest2()) {

     fprintf(stderr, "FAILED: did not pass RetrieveAtIndexTest2()\n");

     return false;

   }

   return true;

 }

 }  // namespace

 int main(int argc, char **argv) {

   BPLOG_INIT(&argc, &argv);

   return RunTests() ? 0 : 1;

 }