[gem5-dev] Change in gem5/gem5[master]: base, mem: Disambiguate if an addr range is contained or overlaps
Nikos Nikoleris has submitted this change and it was merged. (
https://gem5-review.googlesource.com/5 )
Change subject: base, mem: Disambiguate if an addr range is contained or
overlaps
..
base, mem: Disambiguate if an addr range is contained or overlaps
We need to determined whether an address range is fully contained or
it overlaps with an address range in the address range in the mmap. As
an example, we use address range maps to associate ports to address
ranges and we determine which port we will forward the request based
on which address range contains the addresses accessed by the
request. We also need to make sure that when we add a new port to the
address range map, its address range does not overlap with any of the
existing ports.
This patch splits the function find() into two functions contains()
and intersects() to implement this distinct functionality. It also
changes the xbar and the physical memory to use the right function.
Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008
Reviewed-on: https://gem5-review.googlesource.com/5
Reviewed-by: Daniel Carvalho
Maintainer: Nikos Nikoleris
---
M src/base/addr_range_map.hh
M src/mem/physical.cc
M src/mem/xbar.cc
M src/unittest/rangemaptest.cc
4 files changed, 95 insertions(+), 61 deletions(-)
Approvals:
Daniel Carvalho: Looks good to me, approved
Nikos Nikoleris: Looks good to me, approved
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 30bd624..5c627be 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012 ARM Limited
+ * Copyright (c) 2012, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -59,71 +59,63 @@
{
private:
typedef std::map RangeMap;
-RangeMap tree;
public:
typedef typename RangeMap::iterator iterator;
typedef typename RangeMap::const_iterator const_iterator;
+/**
+ * Find entry that contains the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address range. Returns end() if none found.
+ *
+ * @param r An input address range
+ * @return An iterator that contains the input address range
+ */
const_iterator
-find(const AddrRange ) const
+contains(const AddrRange ) const
{
-if (tree.empty())
-return tree.end();
-
-const_iterator i = tree.upper_bound(r);
-
-if (i == tree.begin()) {
-if (i->first.intersects(r)) {
-return i;
-} else {
-return tree.end();
-}
-}
-
---i;
-
-if (i->first.intersects(r))
-return i;
-
-// if we are looking at an interleaved range, also step
-// backwards through the ranges while we are looking at ranges
-// that are part of the same contigous chunk
-if (i->first.interleaved()) {
-AddrRange orig_range = i->first;
-
-while (i != tree.begin() && i->first.mergesWith(orig_range)) {
---i;
-if (i->first.intersects(r)) {
-return i;
-}
-}
-
-// we could leave the loop based on reaching the first
-// element, so we must still check for an intersection
-if (i->first.intersects(r))
-return i;
-}
-
-return tree.end();
+return find(r, [r](const AddrRange r1) { return r.isSubset(r1); });
}
+/**
+ * Find entry that contains the given address
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address. Returns end() if none found.
+ *
+ * @param r An input address
+ * @return An iterator that contains the input address
+ */
const_iterator
-find(const Addr ) const
+contains(Addr r) const
{
-return find(RangeSize(r, 1));
+return contains(RangeSize(r, 1));
}
-bool
-intersect(const AddrRange ) const
+/**
+ * Find entry that intersects with the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the first entry which range intersects with the
+ * input address.
+ *
+ * @param r An input address
+ * @return An iterator that intersects with the input address range
+ */
+const_iterator
+intersects(const AddrRange ) const
{
-return find(r) != tree.end();
+return find(r, [r](const AddrRange r1) { return r.intersects(r1);
});
}
const_iterator
insert(const AddrRange , const V& d)
{
-if (intersect(r))
+if
[gem5-dev] Change in gem5/gem5[master]: base, mem: Disambiguate if an addr range is contained or overlaps
Hello Gabe Black, Jason Lowe-Power, Daniel Carvalho, I'd like you to reexamine a change. Please visit https://gem5-review.googlesource.com/5 to look at the new patch set (#3). Change subject: base, mem: Disambiguate if an addr range is contained or overlaps .. base, mem: Disambiguate if an addr range is contained or overlaps We need to determined whether an address range is fully contained or it overlaps with an address range in the address range in the mmap. As an example, we use address range maps to associate ports to address ranges and we determine which port we will forward the request based on which address range contains the addresses accessed by the request. We also need to make sure that when we add a new port to the address range map, its address range does not overlap with any of the existing ports. This patch splits the function find() into two functions contains() and intersects() to implement this distinct functionality. It also changes the xbar and the physical memory to use the right function. Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008 --- M src/base/addr_range_map.hh M src/mem/physical.cc M src/mem/xbar.cc M src/unittest/rangemaptest.cc 4 files changed, 95 insertions(+), 61 deletions(-) -- To view, visit https://gem5-review.googlesource.com/5 To unsubscribe, or for help writing mail filters, visit https://gem5-review.googlesource.com/settings Gerrit-Project: public/gem5 Gerrit-Branch: master Gerrit-Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008 Gerrit-Change-Number: 5 Gerrit-PatchSet: 3 Gerrit-Owner: Nikos Nikoleris Gerrit-Reviewer: Daniel Carvalho Gerrit-Reviewer: Gabe Black Gerrit-Reviewer: Jason Lowe-Power Gerrit-Reviewer: Nikos Nikoleris Gerrit-MessageType: newpatchset ___ gem5-dev mailing list gem5-dev@gem5.org http://m5sim.org/mailman/listinfo/gem5-dev
[gem5-dev] Change in gem5/gem5[master]: base, mem: Disambiguate if an addr range is contained or overlaps
Nikos Nikoleris has uploaded a new patch set (#2). ( https://gem5-review.googlesource.com/5 ) Change subject: base, mem: Disambiguate if an addr range is contained or overlaps .. base, mem: Disambiguate if an addr range is contained or overlaps We need to determined whether an address range is fully contained or it overlaps with an address range in the address range in the mmap. As an example, we use address range maps to associate ports to address ranges and we determine which port we will forward the request based on which address range contains the addresses accessed by the request. We also need to make sure that when we add a new port to the address range map, its address range does not overlap with any of the existing ports. This patch splits the function find() into two functions contains() and intersects() to implement this distinct functionality. It also changes the xbar and the physical memory to use the right function. Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008 --- M src/base/addr_range_map.hh M src/mem/physical.cc M src/mem/xbar.cc M src/unittest/rangemaptest.cc 4 files changed, 95 insertions(+), 61 deletions(-) -- To view, visit https://gem5-review.googlesource.com/5 To unsubscribe, or for help writing mail filters, visit https://gem5-review.googlesource.com/settings Gerrit-Project: public/gem5 Gerrit-Branch: master Gerrit-Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008 Gerrit-Change-Number: 5 Gerrit-PatchSet: 2 Gerrit-Owner: Nikos Nikoleris Gerrit-CC: Daniel Carvalho Gerrit-MessageType: newpatchset ___ gem5-dev mailing list gem5-dev@gem5.org http://m5sim.org/mailman/listinfo/gem5-dev
[gem5-dev] Change in gem5/gem5[master]: base, mem: Disambiguate if an addr range is contained or overlaps
Nikos Nikoleris has uploaded this change for review. (
https://gem5-review.googlesource.com/5
Change subject: base, mem: Disambiguate if an addr range is contained or
overlaps
..
base, mem: Disambiguate if an addr range is contained or overlaps
We need to determined whether an address range is fully contained or
it overlaps with an address range in the address range in the mmap. As
an example, we use address range maps to associate ports to address
ranges and we determine which port we will forward the request based
on which address range contains the addresses accessed by the
request. We also need to make sure that when we add a new port to the
address range map, its address range does not overlap with any of the
existing ports.
This patch splits the function find() into two functions contains()
and intersects() to implement this distinct functionality. It also
changes the xbar and the physical memory to use the right function.
Change-Id: If3fd3f774a16b27db2df76dc04f1d61824938008
---
M src/base/addr_range_map.hh
M src/mem/physical.cc
M src/mem/xbar.cc
M src/unittest/rangemaptest.cc
4 files changed, 96 insertions(+), 60 deletions(-)
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 30bd624..96678ba 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012 ARM Limited
+ * Copyright (c) 2012, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -65,65 +65,97 @@
typedef typename RangeMap::iterator iterator;
typedef typename RangeMap::const_iterator const_iterator;
+/**
+ * Find entry that contains the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address range. Returns end() if none found.
+ *
+ * @param r An input address range
+ * @return An iterator that contains the input address range
+ */
const_iterator
-find(const AddrRange ) const
+contains(const AddrRange ) const
{
-if (tree.empty())
-return tree.end();
+const_iterator next = tree.upper_bound(r);
+if (next != end() && r.isSubset(next->first)) {
+return next;
+}
+if (next == begin())
+return end();
+next--;
-const_iterator i = tree.upper_bound(r);
+const_iterator i;
+do {
+i = next;
+if (r.isSubset(i->first)) {
+return i;
+}
+// Keep looking if the next range merges with the current one.
+} while (next != tree.begin() &&
+ (--next)->first.mergesWith(i->first));
-if (i == tree.begin()) {
+return tree.end();
+}
+
+/**
+ * Find entry that contains the given address
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address. Returns end() if none found.
+ *
+ * @param r An input address
+ * @return An iterator that contains the input address
+ */
+const_iterator
+contains(Addr r) const
+{
+return contains(RangeSize(r, 1));
+}
+
+/**
+ * Find entry that intersects with the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range intersects with the input
+ * address.
+ *
+ * @param r An input address
+ * @return An iterator that intersects with the input address range
+ */
+const_iterator
+intersects(const AddrRange ) const
+{
+// find the first range r1 for which r.start < r1.start() and
+// check if r1 intersects or otherwise if the previous range
+// intersects
+const_iterator next = tree.upper_bound(r);
+if (next != end() && next->first.intersects(r)) {
+return next;
+}
+if (next == begin())
+return end();
+next--;
+
+const_iterator i;
+do {
+i = next;
if (i->first.intersects(r)) {
return i;
-} else {
-return tree.end();
}
-}
-
---i;
-
-if (i->first.intersects(r))
-return i;
-
-// if we are looking at an interleaved range, also step
-// backwards through the ranges while we are looking at ranges
-// that are part of the same contigous chunk
-if (i->first.interleaved()) {
-AddrRange orig_range = i->first;
-
-while (i != tree.begin() && i->first.mergesWith(orig_range)) {
---i;
-if (i->first.intersects(r)) {
-return i;
-
