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.

4 files changed, 155 insertions, 18 deletions

diff --git a/src/base/addr_range.hh b/src/base/addr_range.hh
index 1e86aa859..edcc0bf2f 100644
--- a/src/base/addr_range.hh
+++ b/src/base/addr_range.hh
@@ -45,7 +45,9 @@
 #ifndef __BASE_ADDR_RANGE_HH__
 #define __BASE_ADDR_RANGE_HH__
 
+#include "base/bitfield.hh"
 #include "base/cprintf.hh"
+#include "base/misc.hh"
 #include "base/types.hh"
 
 class AddrRange
@@ -53,27 +55,68 @@ class AddrRange
 
   private:
 
-    /// Private fields for the start and end of the range. In the
-    /// future, these will be extended with interleaving functionality
-    /// and hence should never be manipulated directly.
+    /// Private fields for the start and end of the range
     Addr _start;
     Addr _end;
 
+    /// The high bit of the slice that is used for interleaving
+    uint8_t intlvHighBit;
+
+    /// The number of bits used for interleaving, set to 0 to disable
+    uint8_t intlvBits;
+
+    /// The value to compare the slice addr[high:(high - bits + 1)]
+    /// with.
+    uint8_t intlvMatch;
+
   public:
 
     AddrRange()
-        : _start(1), _end(0)
+        : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
+    {}
+
+    AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
+              uint8_t _intlv_bits, uint8_t _intlv_match)
+        : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
+          intlvBits(_intlv_bits), intlvMatch(_intlv_match)
     {}
 
     AddrRange(Addr _start, Addr _end)
-        : _start(_start), _end(_end)
+        : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
+          intlvMatch(0)
     {}
 
     /**
+     * Determine if the range is interleaved or not.
+     *
+     * @return true if interleaved
+     */
+    bool interleaved() const { return intlvBits != 0; }
+
+    /**
+     * Determing the interleaving granularity of the range.
+     *
+     * @return The size of the regions created by the interleaving bits
+     */
+    uint64_t granularity() const { return ULL(1) << intlvHighBit; }
+
+    /**
+     * Determine the number of interleaved address stripes this range
+     * is part of.
+     *
+     * @return The number of stripes spanned by the interleaving bits
+     */
+    uint32_t stripes() const { return ULL(1) << intlvBits; }
+
+    /**
      * Get the size of the address range. For a case where
-     * interleaving is used this should probably cause a panic.
+     * interleaving is used we make the simplifying assumption that
+     * the size is a divisible by the size of the interleaving slice.
      */
-    Addr size() const { return _end - _start + 1; }
+    Addr size() const
+    {
+        return (_end - _start + 1) >> intlvBits;
+    }
 
     /**
      * Determine if the range is valid.
@@ -92,7 +135,27 @@ class AddrRange
      */
     std::string to_string() const
     {
-        return csprintf("[%#llx : %#llx]", _start, _end);
+        if (interleaved())
+            return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
+                            intlvHighBit, intlvHighBit - intlvBits + 1,
+                            intlvMatch);
+        else
+            return csprintf("[%#llx : %#llx]", _start, _end);
+    }
+
+    /**
+     * Determine if another range merges with the current one, i.e. if
+     * they are part of the same contigous range and have the same
+     * interleaving bits.
+     *
+     * @param r Range to evaluate merging with
+     * @return true if the two ranges would merge
+     */
+    bool mergesWith(const AddrRange& r) const
+    {
+        return r._start == _start && r._end == _end &&
+            r.intlvHighBit == intlvHighBit &&
+            r.intlvBits == intlvBits;
     }
 
     /**
@@ -105,7 +168,26 @@ class AddrRange
      */
     bool intersects(const AddrRange& r) const
     {
-        return _start <= r._end && _end >= r._start;
+        if (!interleaved()) {
+            return _start <= r._end && _end >= r._start;
+        }
+
+        // the current range is interleaved, split the check up in
+        // three cases
+        if (r.size() == 1)
+            // keep it simple and check if the address is within
+            // this range
+            return contains(r.start());
+        else if (!r.interleaved())
+            // be conservative and ignore the interleaving
+            return _start <= r._end && _end >= r._start;
+        else if (mergesWith(r))
+            // restrict the check to ranges that belong to the
+            // same chunk
+            return intlvMatch == r.intlvMatch;
+        else
+            panic("Cannot test intersection of interleaved range %s\n",
+                  to_string());
     }
 
     /**
@@ -118,6 +200,8 @@ class AddrRange
      */
     bool isSubset(const AddrRange& r) const
     {
+        if (interleaved())
+            panic("Cannot test subset of interleaved range %s\n", to_string());
         return _start >= r._start && _end <= r._end;
     }
 
@@ -129,7 +213,13 @@ class AddrRange
      */
     bool contains(const Addr& a) const
     {
-        return a >= _start && a <= _end;
+        // check if the address is in the range and if there is either
+        // no interleaving, or with interleaving also if the selected
+        // bits from the address match the interleaving value
+        return a >= _start && a <= _end &&
+            (interleaved() ||
+             (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
+              intlvMatch));
     }
 
 /**
@@ -146,7 +236,12 @@ class AddrRange
      */
     bool operator<(const AddrRange& r) const
     {
-        return _start < r._start;
+        if (_start != r._start)
+            return _start < r._start;
+        else
+            // for now assume that the end is also the same, and that
+            // we are looking at the same interleaving bits
+            return intlvMatch < r.intlvMatch;
     }
 
 #endif // SWIG
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();
     }
 
diff --git a/src/mem/physical.cc b/src/mem/physical.cc
index ae5da82fd..140e2b1c0 100644
--- a/src/mem/physical.cc
+++ b/src/mem/physical.cc
@@ -119,9 +119,13 @@ void
 PhysicalMemory::createBackingStore(AddrRange range,
                                    const vector<AbstractMemory*>& _memories)
 {
+    if (range.interleaved())
+        panic("Cannot create backing store for interleaved range %s\n",
+              range.to_string());
+
     // perform the actual mmap
-    DPRINTF(BusAddrRanges, "Creating backing store for range %s\n",
-            range.to_string());
+    DPRINTF(BusAddrRanges, "Creating backing store for range %s with size %d\n",
+            range.to_string(), range.size());
     int map_flags = MAP_ANON | MAP_PRIVATE;
     uint8_t* pmem = (uint8_t*) mmap(NULL, range.size(),
                                     PROT_READ | PROT_WRITE,
diff --git a/src/python/m5/params.py b/src/python/m5/params.py
index cabb91b28..b9a205307 100644
--- a/src/python/m5/params.py
+++ b/src/python/m5/params.py
@@ -553,7 +553,15 @@ class AddrRange(ParamValue):
     cxx_type = 'AddrRange'
 
     def __init__(self, *args, **kwargs):
+        # Disable interleaving by default
+        self.intlvHighBit = 0
+        self.intlvBits = 0
+        self.intlvMatch = 0
+
         def handle_kwargs(self, kwargs):
+            # An address range needs to have an upper limit, specified
+            # either explicitly with an end, or as an offset using the
+            # size keyword.
             if 'end' in kwargs:
                 self.end = Addr(kwargs.pop('end'))
             elif 'size' in kwargs:
@@ -561,6 +569,14 @@ class AddrRange(ParamValue):
             else:
                 raise TypeError, "Either end or size must be specified"
 
+            # Now on to the optional bit
+            if 'intlvHighBit' in kwargs:
+                self.intlvHighBit = int(kwargs.pop('intlvHighBit'))
+            if 'intlvBits' in kwargs:
+                self.intlvBits = int(kwargs.pop('intlvBits'))
+            if 'intlvMatch' in kwargs:
+                self.intlvMatch = int(kwargs.pop('intlvMatch'))
+
         if len(args) == 0:
             self.start = Addr(kwargs.pop('start'))
             handle_kwargs(self, kwargs)
@@ -589,7 +605,8 @@ class AddrRange(ParamValue):
         return '%s:%s' % (self.start, self.end)
 
     def size(self):
-        return long(self.end) - long(self.start) + 1
+        # Divide the size by the size of the interleaving slice
+        return (long(self.end) - long(self.start) + 1) >> self.intlvBits
 
     @classmethod
     def cxx_predecls(cls, code):
@@ -605,7 +622,9 @@ class AddrRange(ParamValue):
         # by swig
         from m5.internal.range import AddrRange
 
-        return AddrRange(long(self.start), long(self.end))
+        return AddrRange(long(self.start), long(self.end),
+                         int(self.intlvHighBit), int(self.intlvBits),
+                         int(self.intlvMatch))
 
 # Boolean parameter type.  Python doesn't let you subclass bool, since
 # it doesn't want to let you create multiple instances of True and