1 files changed, 561 insertions, 0 deletions
diff --git a/externals/breakpad/src/processor/range_map_unittest.cc b/externals/breakpad/src/processor/range_map_unittest.cc
new file mode 100644
index 0000000000..8735bb0955
--- /dev/null
+++ b/externals/breakpad/src/processor/range_map_unittest.cc
@@ -0,0 +1,561 @@
+// Copyright 2010 Google LLC
+//
+// 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 LLC 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
+
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>  // Must come first
+#endif
+
+#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::AddIgnoringOverflow;
+using google_breakpad::linked_ptr;
+using google_breakpad::RangeMap;
+using google_breakpad::scoped_ptr;
+
+// 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 = AddIgnoringOverflow(
+          offset, (!side ? range_test->address
+                         : AddIgnoringOverflow(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();
+      AddressType retrieved_delta = AddressType();
+      bool retrieved = range_map->RetrieveRange(address, &object,
+                                                &retrieved_base,
+                                                &retrieved_delta,
+                                                &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_delta = AddressType();
+      AddressType nearest_size = AddressType();
+      bool retrieved_nearest = range_map->RetrieveNearestRange(address,
+                                                               &nearest_object,
+                                                               &nearest_base,
+                                                               &nearest_delta,
+                                                               &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 /* delta */, NULL /* size */)) {
+      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 /* base */,
+                                      NULL /* delta */, NULL /* size */)) {
+    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 /* delta */, NULL /* size */)) {
+      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;
+}