Giacomo Travaglini has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/48903 )
Change subject: base: Add an exclude method to the AddrRange class
......................................................................
base: Add an exclude method to the AddrRange class
This will allow us to define a list of ranges provided an exclude
pattern, which is handy when a fragmented memory map is present
Change-Id: Ib3d76ef178355585d80e9e600b7c60e66efa01c1
Signed-off-by: Giacomo Travaglini <[email protected]>
---
M src/base/addr_range.hh
M src/base/addr_range.test.cc
2 files changed, 391 insertions(+), 2 deletions(-)
diff --git a/src/base/addr_range.hh b/src/base/addr_range.hh
index 6531a0b..a1a8761 100644
--- a/src/base/addr_range.hh
+++ b/src/base/addr_range.hh
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012, 2014, 2017-2019 ARM Limited
+ * Copyright (c) 2012, 2014, 2017-2019, 2021 Arm Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -586,6 +586,60 @@
}
/**
+ * Subtract a list of intervals from the range and return
+ * the resulting collection of ranges, so that the union
+ * of the two lists cover the original range
+ *
+ * The exclusion list can contain overlapping ranges
+ * Interleaving ranges are not supported and will fail the
+ * assertion.
+ *
+ * @param the input exclusion list
+ * @return the resulting collection of ranges
+ *
+ *
+ * @ingroup api_addr_range
+ */
+ std::vector<AddrRange>
+ exclude(const std::vector<AddrRange> &exclude_ranges)
+ {
+ assert(!interleaved());
+
+ auto sorted_ranges = exclude_ranges;
+ std::sort(sorted_ranges.begin(), sorted_ranges.end());
+
+ std::vector<AddrRange> ranges;
+
+ Addr next_start = start();
+ for (const auto &e : sorted_ranges) {
+ assert(!e.interleaved());
+ if (!intersects(e))
+ continue;
+
+ if (e.start() <= next_start) {
+ if (e.end() < end()) {
+ if (next_start < e.end())
+ next_start = e.end();
+ } else {
+ return ranges;
+ }
+ } else {
+ ranges.push_back(AddrRange(next_start, e.start()));
+ if (e.end() < end()) {
+ next_start = e.end();
+ } else {
+ return ranges;
+ }
+ }
+ }
+
+ if (next_start < end())
+ ranges.push_back(AddrRange(next_start, end()));
+
+ return ranges;
+ }
+
+ /**
* Less-than operator used to turn an STL map into a binary search
* tree of non-overlapping address ranges.
*
diff --git a/src/base/addr_range.test.cc b/src/base/addr_range.test.cc
index 00cf251..c063296 100644
--- a/src/base/addr_range.test.cc
+++ b/src/base/addr_range.test.cc
@@ -1,6 +1,6 @@
/*
* Copyright (c) 2019 The Regents of the University of California
- * Copyright (c) 2018-2019 ARM Limited
+ * Copyright (c) 2018-2019, 2021 Arm Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -1090,3 +1090,338 @@
EXPECT_EQ(0x5, r.start());
EXPECT_EQ(0xA, r.end());
}
+
+/*
+ * The exclude list is excluding the entire range: return an empty
+ * list of ranges
+ *
+ * |---------------------|
+ * | range |
+ * |---------------------|
+ *
+ * |------------------------------|
+ * | exclude_range |
+ * |------------------------------|
+ */
+TEST(AddrRangeTest, ExcludeAll)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x0, 0x200)
+ };
+
+ AddrRange r(0x00, 0x100);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_TRUE(ranges.empty());
+}
+
+/*
+ * The exclude list is excluding the entire range: return an empty
+ * list of ranges. The exclude_range = range
+ *
+ * |---------------------|
+ * | range |
+ * |---------------------|
+ *
+ * |---------------------|
+ * | exclude_range |
+ * |---------------------|
+ */
+TEST(AddrRangeTest, ExcludeAllEqual)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x0, 0x100)
+ };
+
+ AddrRange r(0x00, 0x100);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_TRUE(ranges.empty());
+}
+
+/*
+ * The exclude list is made of multiple adjacent ranges covering the entire
+ * interval: return an empty list of ranges.
+ *
+ * |---------------------------------------------------------------|
+ * | range |
+ * |---------------------------------------------------------------|
+ *
+ * |--------------------------|---------------|--------------------------|
+ * | exclude_range | exclude_range | exclude_range |
+ * |--------------------------|---------------|--------------------------|
+ */
+TEST(AddrRangeTest, ExcludeAllMultiple)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x0, 0x30),
+ AddrRange(0x30, 0x40),
+ AddrRange(0x40, 0x120)
+ };
+
+ AddrRange r(0x00, 0x100);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_TRUE(ranges.empty());
+}
+
+/*
+ * ExcludeAllOverlapping:
+ * The exclude list is made of multiple overlapping ranges covering the
entire
+ * interval: return an empty list of ranges.
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |-----------------------------|
+ * | exclude_range |
+ * |-----------------------------|
+ * |-----------------------------|
+ * | exclude_range |
+ * |-----------------------------|
+ */
+TEST(AddrRangeTest, ExcludeAllOverlapping)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x0, 0x150),
+ AddrRange(0x140, 0x220)
+ };
+
+ AddrRange r(0x100, 0x200);
+
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_TRUE(ranges.empty());
+}
+
+/*
+ * The exclude list is empty:
+ * the return list contains the unmodified range
+ *
+ * |---------------------|
+ * | range |
+ * |---------------------|
+ *
+ */
+TEST(AddrRangeTest, ExcludeEmpty)
+{
+ const std::vector<AddrRange> exclude_ranges;
+
+ AddrRange r(0x00, 0x100);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 1);
+ EXPECT_EQ(ranges.front(), r);
+}
+
+
+/*
+ * Ranges do not overlap:
+ * the return list contains the unmodified range
+ *
+ * |---------------------|
+ * | range |
+ * |---------------------|
+ *
+ * |------------------------------|
+ * | exclude_range |
+ * |------------------------------|
+ */
+TEST(AddrRangeTest, NoExclusion)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x100, 0x200)
+ };
+
+ AddrRange r(0x00, 0x100);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 1);
+ EXPECT_EQ(ranges.front(), r);
+}
+
+/*
+ * DoubleExclusion:
+ * The exclusion should return two ranges:
+ * AddrRange(0x130, 0x140)
+ * AddrRange(0x170, 0x200)
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |-----------------| |-----------------|
+ * | exclude_range | | exclude_range |
+ * |-----------------| |-----------------|
+ */
+TEST(AddrRangeTest, DoubleExclusion)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x000, 0x130),
+ AddrRange(0x140, 0x170),
+ };
+
+ const AddrRange expected_range1(0x130, 0x140);
+ const AddrRange expected_range2(0x170, 0x200);
+
+ AddrRange r(0x100, 0x200);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 2);
+ EXPECT_EQ(ranges[0], expected_range1);
+ EXPECT_EQ(ranges[1], expected_range2);
+}
+
+/*
+ * MultipleExclusion:
+ * The exclusion should return two ranges:
+ * AddrRange(0x130, 0x140)
+ * AddrRange(0x170, 0x180)
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |-----------------| |-----------------| |-----------------|
+ * | exclude_range | | exclude_range | | exclude_range |
+ * |-----------------| |-----------------| |-----------------|
+ */
+TEST(AddrRangeTest, MultipleExclusion)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x000, 0x130),
+ AddrRange(0x140, 0x170),
+ AddrRange(0x180, 0x210)
+ };
+
+ const AddrRange expected_range1(0x130, 0x140);
+ const AddrRange expected_range2(0x170, 0x180);
+
+ AddrRange r(0x100, 0x200);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 2);
+ EXPECT_EQ(ranges[0], expected_range1);
+ EXPECT_EQ(ranges[1], expected_range2);
+}
+
+/*
+ * MultipleExclusionOverlapping:
+ * The exclusion should return one range:
+ * AddrRange(0x130, 0x140)
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |-----------------| |-----------------|
+ * | exclude_range | | exclude_range |
+ * |-----------------| |-----------------|
+ * |-----------------|
+ * | exclude_range |
+ * |-----------------|
+ */
+TEST(AddrRangeTest, MultipleExclusionOverlapping)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x000, 0x130),
+ AddrRange(0x140, 0x170),
+ AddrRange(0x150, 0x210)
+ };
+
+ const AddrRange expected_range1(0x130, 0x140);
+
+ AddrRange r(0x100, 0x200);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 1);
+ EXPECT_EQ(ranges[0], expected_range1);
+}
+
+/*
+ * InclusionOverlapping:
+ * The exclusion should return two range:
+ * AddrRange(0x100, 0x120)
+ * AddrRange(0x180, 0x200)
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |--------------------|
+ * | exclude_range |
+ * |--------------------|
+ *
+ * |---------------|
+ * | exclude_range |
+ * |---------------|
+ */
+TEST(AddrRangeTest, InclusionOverlapping)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x120, 0x180),
+ AddrRange(0x130, 0x170)
+ };
+
+ const AddrRange expected_range1(0x100, 0x120);
+ const AddrRange expected_range2(0x180, 0x200);
+
+ AddrRange r(0x100, 0x200);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 2);
+ EXPECT_EQ(ranges[0], expected_range1);
+ EXPECT_EQ(ranges[1], expected_range2);
+}
+
+/*
+ * MultipleExclusionUnsorted:
+ * The exclusion should return two ranges:
+ * AddrRange(0x130, 0x140)
+ * AddrRange(0x170, 0x180)
+ * Same as MultipleExclusion, but the exclude list is provided
+ * in unsorted order
+ *
+ * |-----------------------------------|
+ * | range |
+ * |-----------------------------------|
+ *
+ * |-----------------| |-----------------| |-----------------|
+ * | exclude_range | | exclude_range | | exclude_range |
+ * |-----------------| |-----------------| |-----------------|
+ */
+TEST(AddrRangeTest, MultipleExclusionUnsorted)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x180, 0x210),
+ AddrRange(0x000, 0x130),
+ AddrRange(0x140, 0x170)
+ };
+
+ const AddrRange expected_range1(0x130, 0x140);
+ const AddrRange expected_range2(0x170, 0x180);
+
+ AddrRange r(0x100, 0x200);
+ auto ranges = r.exclude(exclude_ranges);
+
+ EXPECT_EQ(ranges.size(), 2);
+ EXPECT_EQ(ranges[0], expected_range1);
+ EXPECT_EQ(ranges[1], expected_range2);
+}
+
+/*
+ * InterleavingRanges:
+ * The exclude method does not support interleaving ranges
+ */
+TEST(AddrRangeDeathTest, InterleavingRanges)
+{
+ const std::vector<AddrRange> exclude_ranges{
+ AddrRange(0x180, 0x210),
+ };
+
+ AddrRange r(0x100, 0x200, {1}, 0);
+
+ EXPECT_TRUE(r.interleaved());
+ EXPECT_DEATH(r.exclude(exclude_ranges), "");
+}
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/48903
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: Ib3d76ef178355585d80e9e600b7c60e66efa01c1
Gerrit-Change-Number: 48903
Gerrit-PatchSet: 1
Gerrit-Owner: Giacomo Travaglini <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
