mem: Separate waiting for the bus and waiting for a peer

This patch splits the retryList into a list of ports that are waiting
for the bus itself to become available, and a map that tracks the
ports where forwarding failed due to a peer not accepting the
packet. Thus, when a retry reaches the bus, it can be sent to the
appropriate port that initiated that transaction.

As a consequence of this patch, only ports that are really ready to go
will get a retry, thus reducing the amount of redundant failed
attempts. This patch also makes it easier to reason about the order of
servicing requests as the ports waiting for the bus are now clearly
FIFO and much easier to change if desired.

6 files changed, 145 insertions, 127 deletions

diff --git a/src/mem/bus.cc b/src/mem/bus.cc
index 88b91983b..368d49c86 100644
--- a/src/mem/bus.cc
+++ b/src/mem/bus.cc
@@ -157,26 +157,23 @@ BaseBus::calcPacketTiming(PacketPtr pkt)
 }
 
 template <typename PortClass>
-BaseBus::Layer<PortClass>::Layer(BaseBus& _bus, const std::string& _name) :
+BaseBus::Layer<PortClass>::Layer(BaseBus& _bus, const std::string& _name,
+                                 uint16_t num_dest_ports) :
     Drainable(),
     bus(_bus), _name(_name), state(IDLE), drainManager(NULL),
-    retryingPort(NULL), releaseEvent(this)
+    retryingPort(NULL), waitingForPeer(num_dest_ports, NULL),
+    releaseEvent(this)
 {
 }
 
 template <typename PortClass>
 void BaseBus::Layer<PortClass>::occupyLayer(Tick until)
 {
-    // ensure the state is busy or in retry and never idle at this
-    // point, as the bus should transition from idle as soon as it has
-    // decided to forward the packet to prevent any follow-on calls to
-    // sendTiming seeing an unoccupied bus
-    assert(state != IDLE);
-
-    // note that we do not change the bus state here, if we are going
-    // from idle to busy it is handled by tryTiming, and if we
-    // are in retry we should remain in retry such that
-    // succeededTiming still sees the accurate state
+    // ensure the state is busy at this point, as the bus should
+    // transition from idle as soon as it has decided to forward the
+    // packet to prevent any follow-on calls to sendTiming seeing an
+    // unoccupied bus
+    assert(state == BUSY);
 
     // until should never be 0 as express snoops never occupy the bus
     assert(until != 0);
@@ -188,26 +185,28 @@ void BaseBus::Layer<PortClass>::occupyLayer(Tick until)
 
 template <typename PortClass>
 bool
-BaseBus::Layer<PortClass>::tryTiming(PortClass* port)
+BaseBus::Layer<PortClass>::tryTiming(PortClass* port, PortID dest_port_id)
 {
     // first we see if the bus is busy, next we check if we are in a
-    // retry with a port other than the current one
-    if (state == BUSY || (state == RETRY && port != retryingPort)) {
-        // put the port at the end of the retry list
-        retryList.push_back(port);
+    // retry with a port other than the current one, lastly we check
+    // if the destination port is already engaged in a transaction
+    // waiting for a retry from the peer
+    if (state == BUSY || (state == RETRY && port != retryingPort) ||
+        (dest_port_id != InvalidPortID &&
+         waitingForPeer[dest_port_id] != NULL)) {
+        // put the port at the end of the retry list waiting for the
+        // layer to be freed up (and in the case of a busy peer, for
+        // that transaction to go through, and then the bus to free
+        // up)
+        waitingForLayer.push_back(port);
         return false;
     }
 
-    // @todo: here we should no longer consider this port retrying
-    // once we can differentiate retries due to a busy bus and a
-    // failed forwarding, for now keep it so we can stick it back at
-    // the front of the retry list if needed
+    // update the state to busy
+    state = BUSY;
 
-    // update the state which is shared for request, response and
-    // snoop responses, if we were idle we are now busy, if we are in
-    // a retry, then do not change
-    if (state == IDLE)
-        state = BUSY;
+    // reset the retrying port
+    retryingPort = NULL;
 
     return true;
 }
@@ -216,17 +215,8 @@ template <typename PortClass>
 void
 BaseBus::Layer<PortClass>::succeededTiming(Tick busy_time)
 {
-    // if a retrying port succeeded, update the state and reset the
-    // retrying port
-    if (state == RETRY) {
-        DPRINTF(BaseBus, "Succeeded retry from %s\n",
-                retryingPort->name());
-        state = BUSY;
-        retryingPort = NULL;
-    }
-
-    // we should either have gone from idle to busy in the
-    // tryTiming test, or just gone from a retry to busy
+    // we should have gone from idle or retry to busy in the tryTiming
+    // test
     assert(state == BUSY);
 
     // occupy the bus accordingly
@@ -235,25 +225,21 @@ BaseBus::Layer<PortClass>::succeededTiming(Tick busy_time)
 
 template <typename PortClass>
 void
-BaseBus::Layer<PortClass>::failedTiming(PortClass* port, Tick busy_time)
+BaseBus::Layer<PortClass>::failedTiming(PortClass* src_port,
+                                        PortID dest_port_id, Tick busy_time)
 {
-    // if the current failing port is the retrying one, then for now stick it
-    // back at the front of the retry list to not change any regressions
-    if (state == RETRY) {
-        // we should never see a retry from any port but the current
-        // retry port at this point
-        assert(port == retryingPort);
-        retryList.push_front(port);
-        retryingPort = NULL;
-    } else {
-        // if we are not in a retry, i.e. busy (but never idle), then
-        // add the port at the end of the retry list
-        retryList.push_back(port);
-    }
+    // ensure no one got in between and tried to send something to
+    // this port
+    assert(waitingForPeer[dest_port_id] == NULL);
 
-    // even if we retried the current one and did not succeed,
-    // we are no longer retrying but instead busy
-    state = BUSY;
+    // if the source port is the current retrying one or not, we have
+    // failed in forwarding and should track that we are now waiting
+    // for the peer to send a retry
+    waitingForPeer[dest_port_id] = src_port;
+
+    // we should have gone from idle or retry to busy in the tryTiming
+    // test
+    assert(state == BUSY);
 
     // occupy the bus accordingly
     occupyLayer(busy_time);
@@ -270,12 +256,8 @@ BaseBus::Layer<PortClass>::releaseLayer()
     // update the state
     state = IDLE;
 
-    // bus is now idle, so if someone is waiting we can retry
-    if (!retryList.empty()) {
-        // note that we block (return false on recvTiming) both
-        // because the bus is busy and because the destination is
-        // busy, and in the latter case the bus may be released before
-        // we see a retry from the destination
+    // bus layer is now idle, so if someone is waiting we can retry
+    if (!waitingForLayer.empty()) {
         retryWaiting();
     } else if (drainManager) {
         DPRINTF(Drain, "Bus done draining, signaling drain manager\n");
@@ -290,8 +272,8 @@ template <typename PortClass>
 void
 BaseBus::Layer<PortClass>::retryWaiting()
 {
-    // this should never be called with an empty retry list
-    assert(!retryList.empty());
+    // this should never be called with no one waiting
+    assert(!waitingForLayer.empty());
 
     // we always go to retrying from idle
     assert(state == IDLE);
@@ -302,20 +284,18 @@ BaseBus::Layer<PortClass>::retryWaiting()
     // set the retrying port to the front of the retry list and pop it
     // off the list
     assert(retryingPort == NULL);
-    retryingPort = retryList.front();
-    retryList.pop_front();
+    retryingPort = waitingForLayer.front();
+    waitingForLayer.pop_front();
 
-    // note that we might have blocked on the receiving port being
-    // busy (rather than the bus itself) and now call retry before the
-    // destination called retry on the bus
+    // tell the port to retry, which in some cases ends up calling the
+    // bus
     retryingPort->sendRetry();
 
     // If the bus is still in the retry state, sendTiming wasn't
-    // called in zero time (e.g. the cache does this)
+    // called in zero time (e.g. the cache does this), burn a cycle
     if (state == RETRY) {
-        //Burn a cycle for the missed grant.
-
-        // update the state to busy and reset the retrying port
+        // update the state to busy and reset the retrying port, we
+        // have done our bit and sent the retry
         state = BUSY;
         retryingPort = NULL;
 
@@ -326,22 +306,28 @@ BaseBus::Layer<PortClass>::retryWaiting()
 
 template <typename PortClass>
 void
-BaseBus::Layer<PortClass>::recvRetry()
+BaseBus::Layer<PortClass>::recvRetry(PortID port_id)
 {
-    // we got a retry from a peer that we tried to send something to
-    // and failed, but we sent it on the account of someone else, and
-    // that source port should be on our retry list, however if the
-    // bus layer is released before this happens and the retry (from
-    // the bus point of view) is successful then this no longer holds
-    // and we could in fact have an empty retry list
-    if (retryList.empty())
-        return;
-
-    // if the bus layer is idle
+    // we should never get a retry without having failed to forward
+    // something to this port
+    assert(waitingForPeer[port_id] != NULL);
+
+    // find the port where the failed packet originated and remove the
+    // item from the waiting list
+    PortClass* retry_port = waitingForPeer[port_id];
+    waitingForPeer[port_id] = NULL;
+
+    // add this port at the front of the waiting ports for the layer,
+    // this allows us to call retry on the port immediately if the bus
+    // layer is idle
+    waitingForLayer.push_front(retry_port);
+
+    // if the bus layer is idle, retry this port straight away, if we
+    // are busy, then simply let the port wait for its turn
     if (state == IDLE) {
-        // note that we do not care who told us to retry at the moment, we
-        // merely let the first one on the retry list go
         retryWaiting();
+    } else {
+        assert(state == BUSY);
     }
 }
 
@@ -579,7 +565,7 @@ BaseBus::Layer<PortClass>::drain(DrainManager *dm)
     //We should check that we're not "doing" anything, and that noone is
     //waiting. We might be idle but have someone waiting if the device we
     //contacted for a retry didn't actually retry.
-    if (!retryList.empty() || state != IDLE) {
+    if (state != IDLE) {
         DPRINTF(Drain, "Bus not drained\n");
         drainManager = dm;
         return 1;
diff --git a/src/mem/bus.hh b/src/mem/bus.hh
index 2cd21ff85..16345537a 100644
--- a/src/mem/bus.hh
+++ b/src/mem/bus.hh
@@ -105,8 +105,9 @@ class BaseBus : public MemObject
          *
          * @param _bus the bus this layer belongs to
          * @param _name the layer's name
+         * @param num_dest_ports number of destination ports
          */
-        Layer(BaseBus& _bus, const std::string& _name);
+        Layer(BaseBus& _bus, const std::string& _name, uint16_t num_dest_ports);
 
         /**
          * Drain according to the normal semantics, so that the bus
@@ -128,14 +129,16 @@ class BaseBus : public MemObject
         /**
          * Determine if the bus layer accepts a packet from a specific
          * port. If not, the port in question is also added to the
-         * retry list. In either case the state of the layer is updated
-         * accordingly.
+         * retry list. In either case the state of the layer is
+         * updated accordingly. To ignore checking the destination
+         * port (used by snoops), pass InvalidPortID.
          *
-         * @param port Source port resenting the packet
+         * @param port Source port presenting the packet
+         * @param dest_port_id Destination port id
          *
          * @return True if the bus layer accepts the packet
          */
-        bool tryTiming(PortClass* port);
+        bool tryTiming(PortClass* port, PortID dest_port_id);
 
         /**
          * Deal with a destination port accepting a packet by potentially
@@ -152,26 +155,30 @@ class BaseBus : public MemObject
          * not already at the front) and occupying the bus layer
          * accordingly.
          *
+         * @param src_port Source port
+         * @param dest_port_id Destination port id
          * @param busy_time Time to spend as a result of a failed send
          */
-        void failedTiming(PortClass* port, Tick busy_time);
+        void failedTiming(PortClass* src_port, PortID dest_port_id,
+                          Tick busy_time);
 
         /** Occupy the bus layer until until */
         void occupyLayer(Tick until);
 
         /**
-         * Send a retry to the port at the head of the retryList. The
+         * Send a retry to the port at the head of waitingForLayer. The
          * caller must ensure that the list is not empty.
          */
         void retryWaiting();
 
         /**
-         * Handler a retry from a neighbouring module. Eventually this
-         * should be all encapsulated in the bus. This wraps
+         * Handle a retry from a neighbouring module. This wraps
          * retryWaiting by verifying that there are ports waiting
          * before calling retryWaiting.
+         *
+         * @param port_id Id of the port that received the retry
          */
-        void recvRetry();
+        void recvRetry(PortID port_id);
 
       private:
 
@@ -190,7 +197,7 @@ class BaseBus : public MemObject
          * spent. Once the bus layer leaves the busy state, it can
          * either go back to idle, if no packets have arrived while it
          * was busy, or the bus layer goes on to retry the first port
-         * on the retryList. A similar transition takes place from
+         * in waitingForLayer. A similar transition takes place from
          * idle to retry if the bus layer receives a retry from one of
          * its connected ports. The retry state lasts until the port
          * in questions calls sendTiming and returns control to the
@@ -206,10 +213,10 @@ class BaseBus : public MemObject
         DrainManager *drainManager;
 
         /**
-         * An array of ports that retry should be called
-         * on because the original send failed for whatever reason.
+         * A deque of ports that retry should be called on because
+         * the original send was delayed due to a busy layer.
          */
-        std::deque<PortClass*> retryList;
+        std::deque<PortClass*> waitingForLayer;
 
         /**
          * Port that we are currently in the process of telling to
@@ -220,6 +227,17 @@ class BaseBus : public MemObject
         PortClass* retryingPort;
 
         /**
+         * A vector that tracks who is waiting for the retry when
+         * receiving it from a peer. The vector indices are port ids
+         * of the outgoing ports for the specific layer. The values
+         * are the incoming ports that tried to forward something to
+         * the outgoing port, but was told to wait and is now waiting
+         * for a retry. If no port is waiting NULL is stored on the
+         * location in question.
+         */
+        std::vector<PortClass*> waitingForPeer;
+
+        /**
          * Release the bus layer after being occupied and return to an
          * idle state where we proceed to send a retry to any
          * potential waiting port, or drain if asked to do so.
diff --git a/src/mem/coherent_bus.cc b/src/mem/coherent_bus.cc
index 0166872a7..8bc183fd0 100644
--- a/src/mem/coherent_bus.cc
+++ b/src/mem/coherent_bus.cc
@@ -55,9 +55,13 @@
 #include "sim/system.hh"
 
 CoherentBus::CoherentBus(const CoherentBusParams *p)
-    : BaseBus(p), reqLayer(*this, ".reqLayer"),
-      respLayer(*this, ".respLayer"),
-      snoopRespLayer(*this, ".snoopRespLayer"),
+    : BaseBus(p),
+      reqLayer(*this, ".reqLayer", p->port_master_connection_count +
+               p->port_default_connection_count),
+      respLayer(*this, ".respLayer", p->port_slave_connection_count),
+      snoopRespLayer(*this, ".snoopRespLayer",
+                     p->port_master_connection_count +
+                     p->port_default_connection_count),
       system(p->system)
 {
     // create the ports based on the size of the master and slave
@@ -120,10 +124,13 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     // remember if the packet is an express snoop
     bool is_express_snoop = pkt->isExpressSnoop();
 
+    // determine the destination based on the address
+    PortID dest_port_id = findPort(pkt->getAddr());
+
     // test if the bus should be considered occupied for the current
     // port, and exclude express snoops from the check
-    if (!is_express_snoop && !reqLayer.tryTiming(src_port)) {
-        DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x BUSY\n",
+    if (!is_express_snoop && !reqLayer.tryTiming(src_port, dest_port_id)) {
+        DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x BUS BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
     }
@@ -161,9 +168,8 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
         outstandingReq.insert(pkt->req);
     }
 
-    // since it is a normal request, determine the destination
-    // based on the address and attempt to send the packet
-    bool success = masterPorts[findPort(pkt->getAddr())]->sendTimingReq(pkt);
+    // since it is a normal request, attempt to send the packet
+    bool success = masterPorts[dest_port_id]->sendTimingReq(pkt);
 
     // if this is an express snoop, we are done at this point
     if (is_express_snoop) {
@@ -186,7 +192,8 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
                     src_port->name(), pkt->cmdString(), pkt->getAddr());
 
             // update the bus state and schedule an idle event
-            reqLayer.failedTiming(src_port, clockEdge(Cycles(headerCycles)));
+            reqLayer.failedTiming(src_port, dest_port_id,
+                                  clockEdge(Cycles(headerCycles)));
         } else {
             // update the bus state and schedule an idle event
             reqLayer.succeededTiming(packetFinishTime);
@@ -204,7 +211,7 @@ CoherentBus::recvTimingResp(PacketPtr pkt, PortID master_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (!respLayer.tryTiming(src_port)) {
+    if (!respLayer.tryTiming(src_port, pkt->getDest())) {
         DPRINTF(CoherentBus, "recvTimingResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -267,8 +274,10 @@ CoherentBus::recvTimingSnoopResp(PacketPtr pkt, PortID slave_port_id)
     SlavePort* src_port = slavePorts[slave_port_id];
 
     // test if the bus should be considered occupied for the current
-    // port
-    if (!snoopRespLayer.tryTiming(src_port)) {
+    // port, do not use the destination port in the check as we do not
+    // know yet if it is to be passed on as a snoop response or normal
+    // response and we never block on either
+    if (!snoopRespLayer.tryTiming(src_port, InvalidPortID)) {
         DPRINTF(CoherentBus, "recvTimingSnoopResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -346,12 +355,12 @@ CoherentBus::forwardTiming(PacketPtr pkt, PortID exclude_slave_port_id)
 }
 
 void
-CoherentBus::recvRetry()
+CoherentBus::recvRetry(PortID master_port_id)
 {
     // responses and snoop responses never block on forwarding them,
     // so the retry will always be coming from a port to which we
     // tried to forward a request
-    reqLayer.recvRetry();
+    reqLayer.recvRetry(master_port_id);
 }
 
 Tick
diff --git a/src/mem/coherent_bus.hh b/src/mem/coherent_bus.hh
index 865bfe857..203d7f6b3 100644
--- a/src/mem/coherent_bus.hh
+++ b/src/mem/coherent_bus.hh
@@ -205,7 +205,7 @@ class CoherentBus : public BaseBus
         /** When reciving a retry from the peer port (at id),
             pass it to the bus. */
         virtual void recvRetry()
-        { bus.recvRetry(); }
+        { bus.recvRetry(id); }
 
         // Ask the bus to ask everyone on the bus what their block size is and
         // take the max of it. This might need to be changed a bit if we ever
@@ -248,7 +248,7 @@ class CoherentBus : public BaseBus
 
     /** Timing function called by port when it is once again able to process
      * requests. */
-    void recvRetry();
+    void recvRetry(PortID master_port_id);
 
     /**
      * Forward a timing packet to our snoopers, potentially excluding
diff --git a/src/mem/noncoherent_bus.cc b/src/mem/noncoherent_bus.cc
index f0955bb8f..f6c315297 100644
--- a/src/mem/noncoherent_bus.cc
+++ b/src/mem/noncoherent_bus.cc
@@ -55,8 +55,10 @@
 #include "mem/noncoherent_bus.hh"
 
 NoncoherentBus::NoncoherentBus(const NoncoherentBusParams *p)
-    : BaseBus(p), reqLayer(*this, ".reqLayer"),
-      respLayer(*this, ".respLayer")
+    : BaseBus(p),
+      reqLayer(*this, ".reqLayer", p->port_master_connection_count +
+               p->port_default_connection_count),
+      respLayer(*this, ".respLayer", p->port_slave_connection_count)
 {
     // create the ports based on the size of the master and slave
     // vector ports, and the presence of the default port, the ports
@@ -96,9 +98,12 @@ NoncoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     // we should never see express snoops on a non-coherent bus
     assert(!pkt->isExpressSnoop());
 
+    // determine the destination based on the address
+    PortID dest_port_id = findPort(pkt->getAddr());
+
     // test if the bus should be considered occupied for the current
     // port
-    if (!reqLayer.tryTiming(src_port)) {
+    if (!reqLayer.tryTiming(src_port, dest_port_id)) {
         DPRINTF(NoncoherentBus, "recvTimingReq: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -113,9 +118,8 @@ NoncoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     calcPacketTiming(pkt);
     Tick packetFinishTime = pkt->busLastWordDelay + curTick();
 
-    // since it is a normal request, determine the destination
-    // based on the address and attempt to send the packet
-    bool success = masterPorts[findPort(pkt->getAddr())]->sendTimingReq(pkt);
+    // since it is a normal request, attempt to send the packet
+    bool success = masterPorts[dest_port_id]->sendTimingReq(pkt);
 
     if (!success)  {
         // inhibited packets should never be forced to retry
@@ -128,7 +132,8 @@ NoncoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
         pkt->busFirstWordDelay = pkt->busLastWordDelay = 0;
 
         // occupy until the header is sent
-        reqLayer.failedTiming(src_port, clockEdge(Cycles(headerCycles)));
+        reqLayer.failedTiming(src_port, dest_port_id,
+                              clockEdge(Cycles(headerCycles)));
 
         return false;
     }
@@ -146,7 +151,7 @@ NoncoherentBus::recvTimingResp(PacketPtr pkt, PortID master_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (!respLayer.tryTiming(src_port)) {
+    if (!respLayer.tryTiming(src_port, pkt->getDest())) {
         DPRINTF(NoncoherentBus, "recvTimingResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -172,12 +177,12 @@ NoncoherentBus::recvTimingResp(PacketPtr pkt, PortID master_port_id)
 }
 
 void
-NoncoherentBus::recvRetry()
+NoncoherentBus::recvRetry(PortID master_port_id)
 {
     // responses never block on forwarding them, so the retry will
     // always be coming from a port to which we tried to forward a
     // request
-    reqLayer.recvRetry();
+    reqLayer.recvRetry(master_port_id);
 }
 
 Tick
diff --git a/src/mem/noncoherent_bus.hh b/src/mem/noncoherent_bus.hh
index 38b69a180..5d20a11b2 100644
--- a/src/mem/noncoherent_bus.hh
+++ b/src/mem/noncoherent_bus.hh
@@ -173,7 +173,7 @@ class NoncoherentBus : public BaseBus
         /** When reciving a retry from the peer port (at id),
             pass it to the bus. */
         virtual void recvRetry()
-        { bus.recvRetry(); }
+        { bus.recvRetry(id); }
 
         /**
          * Get the maximum block size as seen by the bus.
@@ -193,7 +193,7 @@ class NoncoherentBus : public BaseBus
 
     /** Timing function called by port when it is once again able to process
      * requests. */
-    void recvRetry();
+    void recvRetry(PortID master_port_id);
 
     /** Function called by the port when the bus is recieving a Atomic
       transaction.*/