mem: Add interleaving bits to the address ranges

This patch adds support for interleaving bits for the address
ranges. What was previously just a start and end address, now has an
additional three fields, for the high bit, and number of bits to use
for interleaving, and a match value to compare against. If the number
of interleaving bits is set to zero it is effectively disabled.

A number of convenience functions are added to the range to enquire
about the interleaving, its granularity and the number of stripes it
is part of.

1 files changed, 22 insertions, 3 deletions

diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index e38e25702..30bd62456 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -74,11 +74,11 @@ class AddrRangeMap
         const_iterator i = tree.upper_bound(r);
 
         if (i == tree.begin()) {
-            if (i->first.intersects(r))
+            if (i->first.intersects(r)) {
                 return i;
-            else
-                // Nothing could match, so return end()
+            } else {
                 return tree.end();
+            }
         }
 
         --i;
@@ -86,6 +86,25 @@ class AddrRangeMap
         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();
     }