aboutsummaryrefslogtreecommitdiff
path: root/externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc
diff options
context:
space:
mode:
authorDawid Potocki <dawid@dawidpotocki.com>2024-03-05 14:09:27 +1300
committerDawid Potocki <dawid@dawidpotocki.com>2024-03-05 20:34:15 +1300
commit063e15900bda8453fb0fc6751e78d064501ccbae (patch)
treea4cd5f01dbca33a262333aff10e1e035217a30c8 /externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc
parent537296095ab24eddcb196b5ef98004f91de9c8c2 (diff)
Replace broken submodules with vendored source codeHEADpatched
Diffstat (limited to 'externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc')
-rw-r--r--externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc349
1 files changed, 349 insertions, 0 deletions
diff --git a/externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc b/externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc
new file mode 100644
index 0000000000..b3599fc506
--- /dev/null
+++ b/externals/breakpad/src/processor/range_map_truncate_lower_unittest.cc
@@ -0,0 +1,349 @@
+// Copyright 2019 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.
+
+#ifdef HAVE_CONFIG_H
+#include <config.h> // Must come first
+#endif
+
+#include <limits.h>
+#include <stdio.h>
+
+#include "processor/range_map-inl.h"
+
+#include "breakpad_googletest_includes.h"
+#include "processor/linked_ptr.h"
+#include "processor/logging.h"
+
+namespace {
+
+using google_breakpad::linked_ptr;
+using google_breakpad::MergeRangeStrategy;
+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;
+
+// Same range cannot be stored wice.
+TEST(RangeMapTruncateLower, SameRange) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
+
+ // Same range cannot be stored wice.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_FALSE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_2));
+}
+
+// If a range is completely contained by another range, then the larger range
+// should be truncated.
+TEST(RangeMapTruncateLower, CompletelyContained) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ // Larger range is added first.
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
+ // Smaller (contained) range is added second.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(10 /* base address */, 80 /* size */, object_2));
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The first range contains the second, so the first range should have been
+ // shrunk to [0, 10]. Range [90, 99] should be free.
+ EXPECT_FALSE(range_map.RetrieveRange(90, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_FALSE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(10, retrieved_size);
+ // Validate the properties of the smaller range (should be untouched).
+ EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(10, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(80, retrieved_size);
+}
+
+// Same as the previous test, however the larger range is added second.
+TEST(RangeMapTruncateLower, CompletelyContained_LargerAddedSecond) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ // Smaller (contained) range is added first.
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(10 /* base address */, 80 /* size */, object_1));
+ // Larger range is added second.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_2));
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The second range contains the first, so the second range should have been
+ // truncated to [0, 9]. Range [90, 99] should be free.
+ EXPECT_FALSE(range_map.RetrieveRange(90, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_FALSE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(10, retrieved_size);
+ // Validate the properties of the smaller range (should be untouched).
+ EXPECT_TRUE(range_map.RetrieveRange(10, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(10, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(80, retrieved_size);
+}
+
+TEST(RangeMapTruncateLower, PartialOverlap_AtBeginning) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
+
+ // Partial overlap at the beginning of the new range.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(90 /* base address */, 110 /* size */, object_2));
+
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The first range should be truncated, so 99 should address the second range.
+ EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(90, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(110, retrieved_size);
+ // Validate the properties of the truncated range.
+ EXPECT_TRUE(range_map.RetrieveRange(89, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(90, retrieved_size);
+}
+
+TEST(RangeMapTruncateLower, PartialOverlap_AtEnd) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(50 /* base address */, 50 /* size */, object_1));
+
+ // Partial overlap at the end of the new range.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 70 /* size */, object_2));
+
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The second range should be truncated so 69 addresses the first range.
+ EXPECT_TRUE(range_map.RetrieveRange(69, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(50, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(50, retrieved_size);
+ // Validate the properties of the truncated range.
+ EXPECT_TRUE(range_map.RetrieveRange(49, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(50, retrieved_size);
+}
+
+// A new range is overlapped at both ends. The new range and the range
+// that overlaps at the beginning should be truncated. The range that overlaps
+// at the end should be left untouched.
+TEST(RangeMapTruncateLower, OverlapAtBothEnds) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ // This should overlap object_3 at the beginning.
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 100 /* size */, object_1));
+
+ // This should overlap object_3 at the end.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(100 /* base address */, 100 /* size */, object_2));
+
+ // This should be overlapped on both ends by object_1 and object_2.
+ linked_ptr<CountedObject> object_3(new CountedObject(3));
+ EXPECT_TRUE(
+ range_map.StoreRange(50 /* base address */, 100 /* size */, object_3));
+
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The first range should be truncated.
+ EXPECT_TRUE(range_map.RetrieveRange(0, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(50, retrieved_size);
+ // The second range should be intact.
+ EXPECT_TRUE(range_map.RetrieveRange(150, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(100, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(100, retrieved_size);
+ // The third range (in the middle) should be truncated.
+ EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(3, object->id());
+ EXPECT_EQ(50, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(50, retrieved_size);
+}
+
+TEST(RangeMapTruncateLower, MultipleConflicts) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ // This should overlap with object_3.
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(10 /* base address */, 90 /* size */, object_1));
+
+ // This should also overlap with object_3 but after object_1.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(100 /* base address */, 100 /* size */, object_2));
+
+ // This should be overlapped on both object_1 and object_2.
+ linked_ptr<CountedObject> object_3(new CountedObject(3));
+ EXPECT_TRUE(
+ range_map.StoreRange(0 /* base address */, 300 /* size */, object_3));
+
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The first range should be intact.
+ EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(10, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(90, retrieved_size);
+ // The second range should be intact.
+ EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(100, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(100, retrieved_size);
+ // The third range should be truncated.
+ EXPECT_TRUE(range_map.RetrieveRange(9, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(3, object->id());
+ EXPECT_EQ(0, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(10, retrieved_size);
+}
+
+// Adding two ranges without overlap should succeed and the ranges should
+// be left intact.
+TEST(RangeMapTruncateLower, NoConflicts) {
+ TestMap range_map;
+ range_map.SetMergeStrategy(MergeRangeStrategy::kTruncateLower);
+ // Adding range 1.
+ linked_ptr<CountedObject> object_1(new CountedObject(1));
+ EXPECT_TRUE(
+ range_map.StoreRange(10 /* base address */, 90 /* size */, object_1));
+
+ // Adding range 2 - no overlap with range 1.
+ linked_ptr<CountedObject> object_2(new CountedObject(2));
+ EXPECT_TRUE(
+ range_map.StoreRange(110 /* base address */, 90 /* size */, object_2));
+
+ linked_ptr<CountedObject> object;
+ AddressType retrieved_base = AddressType();
+ AddressType retrieved_delta = AddressType();
+ AddressType retrieved_size = AddressType();
+ // The first range should be intact.
+ EXPECT_TRUE(range_map.RetrieveRange(99, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(1, object->id());
+ EXPECT_EQ(10, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(90, retrieved_size);
+ // The second range should be intact.
+ EXPECT_TRUE(range_map.RetrieveRange(199, &object, &retrieved_base,
+ &retrieved_delta, &retrieved_size));
+ EXPECT_EQ(2, object->id());
+ EXPECT_EQ(110, retrieved_base);
+ EXPECT_EQ(0, retrieved_delta);
+ EXPECT_EQ(90, retrieved_size);
+}
+
+} // namespace
generated by cgit v1.2.3-70-g09d2 (git 2.49.0) at 2025-04-11 02:00:45 +0000