Mem: Use range operations in bus in preparation for striping

This patch transitions the bus to use the AddrRange operations instead
of directly accessing the start and end. The change facilitates the
move to a more elaborate AddrRange class that also supports address
striping in the bus by specifying interleaving bits in the ranges.

Two new functions are added to the AddrRange to determine if two
ranges intersect, and if one is a subset of another. The bus
propagation of address ranges is also tweaked such that an update is
only propagated if the bus received information from all the
downstream slave modules. This avoids the iteration and need for the
cycle-breaking scheme that was previously used.

3 files changed, 139 insertions, 107 deletions

diff --git a/src/mem/addr_mapper.cc b/src/mem/addr_mapper.cc
index 53e8277cc..28fc85245 100644
--- a/src/mem/addr_mapper.cc
+++ b/src/mem/addr_mapper.cc
@@ -272,14 +272,10 @@ RangeAddrMapper::getAddrRanges() const
         AddrRange range = *r;
 
         for (int j = 0; j < originalRanges.size(); ++j) {
-            if ((range.start < originalRanges[j].start &&
-                 range.end >= originalRanges[j].start) ||
-                (range.start < originalRanges[j].end &&
-                 range.end >= originalRanges[j].end))
+            if (range.intersects(originalRanges[j]))
                 fatal("Cannot remap range that intersects the original"
                       " ranges but are not a subset.\n");
-            if (range.start >= originalRanges[j].start &&
-                range.end <= originalRanges[j].end) {
+            if (range.isSubset(originalRanges[j])) {
                 // range is a subset
                 Addr offset = range.start - originalRanges[j].start;
                 range.start -= offset;
diff --git a/src/mem/bus.cc b/src/mem/bus.cc
index d4157e14d..badf145ac 100644
--- a/src/mem/bus.cc
+++ b/src/mem/bus.cc
@@ -57,7 +57,9 @@
 BaseBus::BaseBus(const BaseBusParams *p)
     : MemObject(p),
       headerCycles(p->header_cycles), width(p->width),
-      defaultPortID(InvalidPortID),
+      gotAddrRanges(p->port_default_connection_count +
+                          p->port_master_connection_count, false),
+      gotAllAddrRanges(false), defaultPortID(InvalidPortID),
       useDefaultRange(p->use_default_range),
       blockSize(p->block_size)
 {}
@@ -335,28 +337,29 @@ BaseBus::Layer<PortClass>::recvRetry()
 PortID
 BaseBus::findPort(Addr addr)
 {
-    /* An interval tree would be a better way to do this. --ali. */
+    // we should never see any address lookups before we've got the
+    // ranges of all connected slave modules
+    assert(gotAllAddrRanges);
+
+    // Check the cache
     PortID dest_id = checkPortCache(addr);
     if (dest_id != InvalidPortID)
         return dest_id;
 
-    // Check normal port ranges
-    PortMapConstIter i = portMap.find(RangeSize(addr,1));
+    // Check the address map interval tree
+    PortMapConstIter i = portMap.find(addr);
     if (i != portMap.end()) {
         dest_id = i->second;
-        updatePortCache(dest_id, i->first.start, i->first.end);
+        updatePortCache(dest_id, i->first);
         return dest_id;
     }
 
     // Check if this matches the default range
     if (useDefaultRange) {
-        AddrRangeConstIter a_end = defaultRange.end();
-        for (AddrRangeConstIter i = defaultRange.begin(); i != a_end; i++) {
-            if (*i == addr) {
-                DPRINTF(BusAddrRanges, "  found addr %#llx on default\n",
-                        addr);
-                return defaultPortID;
-            }
+        if (defaultRange == addr) {
+            DPRINTF(BusAddrRanges, "  found addr %#llx on default\n",
+                    addr);
+            return defaultPortID;
         }
     } else if (defaultPortID != InvalidPortID) {
         DPRINTF(BusAddrRanges, "Unable to find destination for addr %#llx, "
@@ -374,51 +377,62 @@ BaseBus::findPort(Addr addr)
 void
 BaseBus::recvRangeChange(PortID master_port_id)
 {
-    AddrRangeIter iter;
-
-    if (inRecvRangeChange.count(master_port_id))
-        return;
-    inRecvRangeChange.insert(master_port_id);
+    // remember that we got a range from this master port and thus the
+    // connected slave module
+    gotAddrRanges[master_port_id] = true;
+
+    // update the global flag
+    if (!gotAllAddrRanges) {
+        // take a logical AND of all the ports and see if we got
+        // ranges from everyone
+        gotAllAddrRanges = true;
+        std::vector<bool>::const_iterator r = gotAddrRanges.begin();
+        while (gotAllAddrRanges &&  r != gotAddrRanges.end()) {
+            gotAllAddrRanges &= *r++;
+        }
+    }
 
-    DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n",
-            master_port_id);
+    // note that we could get the range from the default port at any
+    // point in time, and we cannot assume that the default range is
+    // set before the other ones are, so we do additional checks once
+    // all ranges are provided
+    DPRINTF(BusAddrRanges, "received RangeChange from slave port %s\n",
+            masterPorts[master_port_id]->getSlavePort().name());
 
-    clearPortCache();
     if (master_port_id == defaultPortID) {
-        defaultRange.clear();
-        // Only try to update these ranges if the user set a default responder.
+        // only update if we are indeed checking ranges for the
+        // default port since the port might not have a valid range
+        // otherwise
         if (useDefaultRange) {
-            // get the address ranges of the connected slave port
-            AddrRangeList ranges =
-                masterPorts[master_port_id]->getAddrRanges();
-            for(iter = ranges.begin(); iter != ranges.end(); iter++) {
-                defaultRange.push_back(*iter);
-                DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n",
-                        iter->start, iter->end);
-            }
-        }
-    } else {
+            AddrRangeList ranges = masterPorts[master_port_id]->getAddrRanges();
 
-        assert(master_port_id < masterPorts.size() && master_port_id >= 0);
-        MasterPort *port = masterPorts[master_port_id];
+            if (ranges.size() != 1)
+                fatal("Bus %s may only have a single default range",
+                      name());
 
-        // Clean out any previously existent ids
-        for (PortMapIter portIter = portMap.begin();
-             portIter != portMap.end(); ) {
-            if (portIter->second == master_port_id)
-                portMap.erase(portIter++);
-            else
-                portIter++;
+            defaultRange = ranges.front();
+        }
+    } else {
+        // the ports are allowed to update their address ranges
+        // dynamically, so remove any existing entries
+        if (gotAddrRanges[master_port_id]) {
+            for (PortMapIter p = portMap.begin(); p != portMap.end(); ) {
+                if (p->second == master_port_id)
+                    // erasing invalidates the iterator, so advance it
+                    // before the deletion takes place
+                    portMap.erase(p++);
+                else
+                    p++;
+            }
         }
 
-        // get the address ranges of the connected slave port
-        AddrRangeList ranges = port->getAddrRanges();
+        AddrRangeList ranges = masterPorts[master_port_id]->getAddrRanges();
 
-        for (iter = ranges.begin(); iter != ranges.end(); iter++) {
-            DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n",
-                    iter->start, iter->end, master_port_id);
-            if (portMap.insert(*iter, master_port_id) == portMap.end()) {
-                PortID conflict_id = portMap.find(*iter)->second;
+        for (AddrRangeConstIter r = ranges.begin(); r != ranges.end(); ++r) {
+            DPRINTF(BusAddrRanges, "Adding range %#llx : %#llx for id %d\n",
+                    r->start, r->end, master_port_id);
+            if (portMap.insert(*r, master_port_id) == portMap.end()) {
+                PortID conflict_id = portMap.find(*r)->second;
                 fatal("%s has two ports with same range:\n\t%s\n\t%s\n",
                       name(),
                       masterPorts[master_port_id]->getSlavePort().name(),
@@ -426,52 +440,74 @@ BaseBus::recvRangeChange(PortID master_port_id)
             }
         }
     }
-    DPRINTF(BusAddrRanges, "port list has %d entries\n", portMap.size());
 
-    // tell all our neighbouring master ports that our address range
-    // has changed
-    for (SlavePortConstIter p = slavePorts.begin(); p != slavePorts.end();
-         ++p)
-        (*p)->sendRangeChange();
+    // if we have received ranges from all our neighbouring slave
+    // modules, go ahead and tell our connected master modules in
+    // turn, this effectively assumes a tree structure of the system
+    if (gotAllAddrRanges) {
+        // also check that no range partially overlaps with the
+        // default range, this has to be done after all ranges are set
+        // as there are no guarantees for when the default range is
+        // update with respect to the other ones
+        if (useDefaultRange) {
+            for (PortID port_id = 0; port_id < masterPorts.size(); ++port_id) {
+                if (port_id == defaultPortID) {
+                    if (!gotAddrRanges[port_id])
+                        fatal("Bus %s uses default range, but none provided",
+                              name());
+                } else {
+                    AddrRangeList ranges =
+                        masterPorts[port_id]->getAddrRanges();
+
+                    for (AddrRangeConstIter r = ranges.begin();
+                         r != ranges.end(); ++r) {
+                        // see if the new range is partially
+                        // overlapping the default range
+                        if (r->intersects(defaultRange) &&
+                            !r->isSubset(defaultRange))
+                            fatal("Range %#llx : %#llx intersects the " \
+                                  "default range of %s but is not a " \
+                                  "subset\n", r->start, r->end, name());
+                    }
+                }
+            }
+        }
+
+        // tell all our neighbouring master ports that our address
+        // ranges have changed
+        for (SlavePortConstIter s = slavePorts.begin(); s != slavePorts.end();
+             ++s)
+            (*s)->sendRangeChange();
+    }
 
-    inRecvRangeChange.erase(master_port_id);
+    clearPortCache();
 }
 
 AddrRangeList
 BaseBus::getAddrRanges() const
 {
-    AddrRangeList ranges;
+    // we should never be asked without first having sent a range
+    // change, and the latter is only done once we have all the ranges
+    // of the connected devices
+    assert(gotAllAddrRanges);
 
     DPRINTF(BusAddrRanges, "received address range request, returning:\n");
 
-    for (AddrRangeConstIter dflt_iter = defaultRange.begin();
-         dflt_iter != defaultRange.end(); dflt_iter++) {
-        ranges.push_back(*dflt_iter);
-        DPRINTF(BusAddrRanges, "  -- Dflt: %#llx : %#llx\n",dflt_iter->start,
-                dflt_iter->end);
-    }
-    for (PortMapConstIter portIter = portMap.begin();
-         portIter != portMap.end(); portIter++) {
-        bool subset = false;
-        for (AddrRangeConstIter dflt_iter = defaultRange.begin();
-             dflt_iter != defaultRange.end(); dflt_iter++) {
-            if ((portIter->first.start < dflt_iter->start &&
-                portIter->first.end >= dflt_iter->start) ||
-               (portIter->first.start < dflt_iter->end &&
-                portIter->first.end >= dflt_iter->end))
-                fatal("Devices can not set ranges that itersect the default set\
-                        but are not a subset of the default set.\n");
-            if (portIter->first.start >= dflt_iter->start &&
-                portIter->first.end <= dflt_iter->end) {
-                subset = true;
-                DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
-                    portIter->first.start, portIter->first.end);
-            }
-        }
-        if (!subset) {
-            ranges.push_back(portIter->first);
+    // start out with the default range
+    AddrRangeList ranges;
+    ranges.push_back(defaultRange);
+    DPRINTF(BusAddrRanges, "  -- %#llx : %#llx DEFAULT\n",
+            defaultRange.start, defaultRange.end);
+
+    // add any range that is not a subset of the default range
+    for (PortMapConstIter p = portMap.begin(); p != portMap.end(); ++p) {
+        if (useDefaultRange && p->first.isSubset(defaultRange)) {
+            DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
+                    p->first.start, p->first.end);
+        } else {
+            ranges.push_back(p->first);
             DPRINTF(BusAddrRanges, "  -- %#llx : %#llx\n",
-                    portIter->first.start, portIter->first.end);
+                    p->first.start, p->first.end);
         }
     }
 
diff --git a/src/mem/bus.hh b/src/mem/bus.hh
index a3469a478..849bef639 100644
--- a/src/mem/bus.hh
+++ b/src/mem/bus.hh
@@ -236,7 +236,7 @@ class BaseBus : public MemObject
     typedef AddrRangeMap<PortID>::const_iterator PortMapConstIter;
     AddrRangeMap<PortID> portMap;
 
-    AddrRangeList defaultRange;
+    AddrRange defaultRange;
 
     /**
      * Function called by the port when the bus is recieving a range change.
@@ -256,25 +256,21 @@ class BaseBus : public MemObject
     struct PortCache {
         bool valid;
         PortID id;
-        Addr start;
-        Addr end;
+        AddrRange range;
     };
 
     PortCache portCache[3];
 
     // Checks the cache and returns the id of the port that has the requested
     // address within its range
-    inline PortID checkPortCache(Addr addr) {
-        if (portCache[0].valid && addr >= portCache[0].start &&
-            addr < portCache[0].end) {
+    inline PortID checkPortCache(Addr addr) const {
+        if (portCache[0].valid && portCache[0].range == addr) {
             return portCache[0].id;
         }
-        if (portCache[1].valid && addr >= portCache[1].start &&
-                   addr < portCache[1].end) {
+        if (portCache[1].valid && portCache[1].range == addr) {
             return portCache[1].id;
         }
-        if (portCache[2].valid && addr >= portCache[2].start &&
-            addr < portCache[2].end) {
+        if (portCache[2].valid && portCache[2].range == addr) {
             return portCache[2].id;
         }
 
@@ -282,21 +278,18 @@ class BaseBus : public MemObject
     }
 
     // Clears the earliest entry of the cache and inserts a new port entry
-    inline void updatePortCache(short id, Addr start, Addr end) {
+    inline void updatePortCache(short id, const AddrRange& range) {
         portCache[2].valid = portCache[1].valid;
         portCache[2].id    = portCache[1].id;
-        portCache[2].start = portCache[1].start;
-        portCache[2].end   = portCache[1].end;
+        portCache[2].range = portCache[1].range;
 
         portCache[1].valid = portCache[0].valid;
         portCache[1].id    = portCache[0].id;
-        portCache[1].start = portCache[0].start;
-        portCache[1].end   = portCache[0].end;
+        portCache[1].range = portCache[0].range;
 
         portCache[0].valid = true;
         portCache[0].id    = id;
-        portCache[0].start = start;
-        portCache[0].end   = end;
+        portCache[0].range = range;
     }
 
     // Clears the cache. Needs to be called in constructor.
@@ -329,7 +322,14 @@ class BaseBus : public MemObject
      */
     unsigned deviceBlockSize() const;
 
-    std::set<PortID> inRecvRangeChange;
+    /**
+     * Remember for each of the master ports of the bus if we got an
+     * address range from the connected slave. For convenience, also
+     * keep track of if we got ranges from all the slave modules or
+     * not.
+     */
+    std::vector<bool> gotAddrRanges;
+    bool gotAllAddrRanges;
 
     /** The master and slave ports of the bus */
     std::vector<SlavePort*> slavePorts;