Bus: Replace tickNextIdle and inRetry with a state variable

This patch adds a state enum and member variable in the bus, tracking
the bus state, thus eliminating the need for tickNextIdle and inRetry,
and fixing an issue that allowed the bus to be occupied by multiple
packets at once (hopefully it also makes it easier to understand the
code).

The bus, in its current form, uses tickNextIdle and inRetry to keep
track of the state of the bus. However, it only updates tickNextIdle
_after_ forwarding a packet using sendTiming, and the result is that
the bus is still seen as idle, and a module that receives the packet
and starts transmitting new packets in zero time will still see the
bus as idle (and this is done by a number of DMA devices). The issue
can also be seen in isOccupied where the bus calls reschedule on an
event instead of schedule.

This patch addresses the problem by marking the bus as _not_ idle
already by the time we conclude that the bus is not occupied and we
will deal with the packet.

As a result of not allowing multiple packets to occupy the bus, some
regressions have slight changes in their statistics. A separate patch
updates these accordingly.

Further ahead, a follow-on patch will introduce a separate state
variable for request/responses/snoop responses, and thus implement a
split request/response bus with separate flow control for the
different message types (even further ahead it will introduce a
multi-layer bus).

5 files changed, 167 insertions, 124 deletions

diff --git a/src/base/intmath.hh b/src/base/intmath.hh
index b8c83f05a..f46133764 100644
--- a/src/base/intmath.hh
+++ b/src/base/intmath.hh
@@ -193,9 +193,9 @@ ceilPow2(T n)
     return (T)1 << ceilLog2(n);
 }
 
-template <class T>
+template <class T, class U>
 inline T
-divCeil(T a, T b)
+divCeil(const T& a, const U& b)
 {
     return (a + b - 1) / b;
 }
diff --git a/src/mem/bus.cc b/src/mem/bus.cc
index 2e735e03b..a2ddc0b69 100644
--- a/src/mem/bus.cc
+++ b/src/mem/bus.cc
@@ -47,6 +47,7 @@
  * Definition of a bus object.
  */
 
+#include "base/intmath.hh"
 #include "base/misc.hh"
 #include "base/trace.hh"
 #include "debug/Bus.hh"
@@ -54,9 +55,9 @@
 #include "mem/bus.hh"
 
 BaseBus::BaseBus(const BaseBusParams *p)
-    : MemObject(p), clock(p->clock),
-      headerCycles(p->header_cycles), width(p->width), tickNextIdle(0),
-      drainEvent(NULL), busIdleEvent(this), inRetry(false),
+    : MemObject(p), state(IDLE), clock(p->clock),
+      headerCycles(p->header_cycles), width(p->width),
+      drainEvent(NULL), busIdleEvent(this),
       defaultPortID(InvalidPortID),
       useDefaultRange(p->use_default_range),
       defaultBlockSize(p->block_size),
@@ -113,10 +114,7 @@ BaseBus::calcPacketTiming(PacketPtr pkt)
 {
     // determine the current time rounded to the closest following
     // clock edge
-    Tick now = curTick();
-    if (now % clock != 0) {
-        now = ((now / clock) + 1) * clock;
-    }
+    Tick now = divCeil(curTick(), clock) * clock;
 
     Tick headerTime = now + headerCycles * clock;
 
@@ -142,52 +140,91 @@ BaseBus::calcPacketTiming(PacketPtr pkt)
 
 void BaseBus::occupyBus(Tick until)
 {
-    if (until == 0) {
-        // shortcut for express snoop packets
-        return;
-    }
-
-    tickNextIdle = until;
-    reschedule(busIdleEvent, tickNextIdle, true);
-
-    DPRINTF(BaseBus, "The bus is now occupied from tick %d to %d\n",
-            curTick(), tickNextIdle);
+    // 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
+
+    // until should never be 0 as express snoops never occupy the bus
+    assert(until != 0);
+    schedule(busIdleEvent, until);
+
+    DPRINTF(BaseBus, "The bus is now busy from tick %d to %d\n",
+            curTick(), until);
 }
 
 bool
-BaseBus::isOccupied(Port* port)
+BaseBus::tryTiming(Port* port)
 {
-    // first we see if the next idle tick is in the future, next the
-    // bus is considered occupied if there are ports on the retry list
-    // and we are not in a retry with the current port
-    if (tickNextIdle > curTick() ||
-        (!retryList.empty() && !(inRetry && port == retryList.front()))) {
-        addToRetryList(port);
-        return true;
+    // 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 != retryList.front())) {
+        // put the port at the end of the retry list
+        retryList.push_back(port);
+        return false;
     }
-    return false;
+
+    // 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;
+
+    return true;
 }
 
 void
 BaseBus::succeededTiming(Tick busy_time)
 {
-    // occupy the bus accordingly
-    occupyBus(busy_time);
-
     // if a retrying port succeeded, also take it off the retry list
-    if (inRetry) {
+    if (state == RETRY) {
         DPRINTF(BaseBus, "Remove retry from list %s\n",
                 retryList.front()->name());
         retryList.pop_front();
-        inRetry = false;
+        state = BUSY;
+    }
+
+    // we should either have gone from idle to busy in the
+    // tryTiming test, or just gone from a retry to busy
+    assert(state == BUSY);
+
+    // occupy the bus accordingly
+    occupyBus(busy_time);
+}
+
+void
+BaseBus::failedTiming(SlavePort* port, Tick busy_time)
+{
+    // if we are not in a retry, i.e. busy (but never idle), or we are
+    // in a retry but not for the current port, then add the port at
+    // the end of the retry list
+    if (state != RETRY || port != retryList.front()) {
+        retryList.push_back(port);
     }
+
+    // even if we retried the current one and did not succeed,
+    // we are no longer retrying but instead busy
+    state = BUSY;
+
+    // occupy the bus accordingly
+    occupyBus(busy_time);
 }
 
 void
 BaseBus::releaseBus()
 {
     // releasing the bus means we should now be idle
-    assert(curTick() >= tickNextIdle);
+    assert(state == BUSY);
+    assert(!busIdleEvent.scheduled());
+
+    // update the state
+    state = IDLE;
 
     // bus is now idle, so if someone is waiting we can retry
     if (!retryList.empty()) {
@@ -196,10 +233,8 @@ BaseBus::releaseBus()
         // busy, and in the latter case the bus may be released before
         // we see a retry from the destination
         retryWaiting();
-    }
-
-    //If we weren't able to drain before, we might be able to now.
-    if (drainEvent && retryList.empty() && curTick() >= tickNextIdle) {
+    } else if (drainEvent) {
+        //If we weren't able to drain before, do it now.
         drainEvent->process();
         // Clear the drain event once we're done with it.
         drainEvent = NULL;
@@ -212,8 +247,12 @@ BaseBus::retryWaiting()
     // this should never be called with an empty retry list
     assert(!retryList.empty());
 
-    // send a retry to the port at the head of the retry list
-    inRetry = true;
+    // we always go to retrying from idle
+    assert(state == IDLE);
+
+    // update the state which is shared for request, response and
+    // snoop responses
+    state = RETRY;
 
     // note that we might have blocked on the receiving port being
     // busy (rather than the bus itself) and now call retry before the
@@ -223,20 +262,22 @@ BaseBus::retryWaiting()
     else
         (dynamic_cast<MasterPort*>(retryList.front()))->sendRetry();
 
-    // If inRetry is still true, sendTiming wasn't called in zero time
-    // (e.g. the cache does this)
-    if (inRetry) {
+    // If the bus is still in the retry state, sendTiming wasn't
+    // called in zero time (e.g. the cache does this)
+    if (state == RETRY) {
         retryList.pop_front();
-        inRetry = false;
-
-        //Bring tickNextIdle up to the present
-        while (tickNextIdle < curTick())
-            tickNextIdle += clock;
 
         //Burn a cycle for the missed grant.
-        tickNextIdle += clock;
 
-        reschedule(busIdleEvent, tickNextIdle, true);
+        // update the state which is shared for request, response and
+        // snoop responses
+        state = BUSY;
+
+        // determine the current time rounded to the closest following
+        // clock edge
+        Tick now = divCeil(curTick(), clock) * clock;
+
+        occupyBus(now + clock);
     }
 }
 
@@ -252,8 +293,8 @@ BaseBus::recvRetry()
     if (retryList.empty())
         return;
 
-    // if the bus isn't busy
-    if (curTick() >= tickNextIdle) {
+    // if the bus is idle
+    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();
@@ -445,17 +486,9 @@ BaseBus::drain(Event * de)
     //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() || (curTick() < tickNextIdle &&
-                               busIdleEvent.scheduled())) {
+    if (!retryList.empty() || state != IDLE) {
         drainEvent = de;
         return 1;
     }
     return 0;
 }
-
-void
-BaseBus::startup()
-{
-    if (tickNextIdle < curTick())
-        tickNextIdle = (curTick() / clock) * clock + clock;
-}
diff --git a/src/mem/bus.hh b/src/mem/bus.hh
index 94068d897..db0686683 100644
--- a/src/mem/bus.hh
+++ b/src/mem/bus.hh
@@ -74,14 +74,32 @@ class BaseBus : public MemObject
 
   protected:
 
+    /**
+     * We declare an enum to track the state of the bus. The starting
+     * point is an idle state where the bus is waiting for a packet to
+     * arrive. Upon arrival, the bus transitions to the busy state,
+     * where it remains either until the packet transfer is done, or
+     * the header time is spent. Once the bus leaves the busy state,
+     * it can either go back to idle, if no packets have arrived while
+     * it was busy, or the bus goes on to retry the first port on the
+     * retryList. A similar transition takes place from idle to retry
+     * if the bus 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 bus, or goes to a busy
+     * state if the port does not immediately react to the retry by
+     * calling sendTiming.
+     */
+    enum State { IDLE, BUSY, RETRY };
+
+    /** track the state of the bus */
+    State state;
+
     /** the clock speed for the bus */
     int clock;
     /** cycles of overhead per transaction */
     int headerCycles;
     /** the width of the bus in bytes */
     int width;
-    /** the next tick at which the bus will be idle */
-    Tick tickNextIdle;
 
     Event * drainEvent;
 
@@ -92,15 +110,15 @@ class BaseBus : public MemObject
     AddrRangeList defaultRange;
 
     /**
-     * Determine if the bus is to be considered occupied when being
-     * presented with a packet from a specific port. If so, the port
-     * in question is also added to the retry list.
+     * Determine if the bus 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 bus is updated accordingly.
      *
      * @param port Source port on the bus presenting the packet
      *
-     * @return True if the bus is to be considered occupied
+     * @return True if the bus accepts the packet
      */
-    bool isOccupied(Port* port);
+    bool tryTiming(Port* port);
 
     /**
      * Deal with a destination port accepting a packet by potentially
@@ -111,6 +129,15 @@ class BaseBus : public MemObject
      */
     void succeededTiming(Tick busy_time);
 
+    /**
+     * Deal with a destination port not accepting a packet by
+     * potentially adding the source port to the retry list (if
+     * not already at the front) and occupying the bus accordingly.
+     *
+     * @param busy_time Time to spend as a result of a failed send
+     */
+    void failedTiming(SlavePort* port, Tick busy_time);
+
     /** Timing function called by port when it is once again able to process
      * requests. */
     void recvRetry();
@@ -223,7 +250,6 @@ class BaseBus : public MemObject
     // event used to schedule a release of the bus
     EventWrapper<BaseBus, &BaseBus::releaseBus> busIdleEvent;
 
-    bool inRetry;
     std::set<PortID> inRecvRangeChange;
 
     /** The master and slave ports of the bus */
@@ -240,25 +266,6 @@ class BaseBus : public MemObject
      * original send failed for whatever reason.*/
     std::list<Port*> retryList;
 
-    void addToRetryList(Port* port)
-    {
-        if (!inRetry) {
-            // The device wasn't retrying a packet, or wasn't at an
-            // appropriate time.
-            retryList.push_back(port);
-        } else {
-            if (!retryList.empty() && port == retryList.front()) {
-                // The device was retrying a packet. It didn't work,
-                // so we'll leave it at the head of the retry list.
-                inRetry = false;
-            } else {
-                // We are in retry, but not for this port, put it at
-                // the end.
-                retryList.push_back(port);
-            }
-        }
-    }
-
     /** Port that handles requests that don't match any of the interfaces.*/
     PortID defaultPortID;
 
@@ -282,8 +289,6 @@ class BaseBus : public MemObject
     virtual MasterPort& getMasterPort(const std::string& if_name, int idx = -1);
     virtual SlavePort& getSlavePort(const std::string& if_name, int idx = -1);
 
-    virtual void startup();
-
     unsigned int drain(Event *de);
 
 };
diff --git a/src/mem/coherent_bus.cc b/src/mem/coherent_bus.cc
index ef8d68f00..f7d4b9d11 100644
--- a/src/mem/coherent_bus.cc
+++ b/src/mem/coherent_bus.cc
@@ -110,22 +110,26 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     // determine the source port based on the id
     SlavePort *src_port = slavePorts[slave_port_id];
 
+    // remember if the packet is an express snoop
+    bool is_express_snoop = pkt->isExpressSnoop();
+
     // test if the bus should be considered occupied for the current
     // port, and exclude express snoops from the check
-    if (!pkt->isExpressSnoop() && isOccupied(src_port)) {
+    if (!is_express_snoop && !tryTiming(src_port)) {
         DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
     }
 
-    DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x\n",
-            src_port->name(), pkt->cmdString(), pkt->getAddr());
+    DPRINTF(CoherentBus, "recvTimingReq: src %s %s expr %d 0x%x\n",
+            src_port->name(), pkt->cmdString(), is_express_snoop,
+            pkt->getAddr());
 
     // set the source port for routing of the response
     pkt->setSrc(slave_port_id);
 
-    Tick headerFinishTime = pkt->isExpressSnoop() ? 0 : calcPacketTiming(pkt);
-    Tick packetFinishTime = pkt->isExpressSnoop() ? 0 : pkt->finishTime;
+    Tick headerFinishTime = is_express_snoop ? 0 : calcPacketTiming(pkt);
+    Tick packetFinishTime = is_express_snoop ? 0 : pkt->finishTime;
 
     // uncacheable requests need never be snooped
     if (!pkt->req->isUncacheable()) {
@@ -138,7 +142,7 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     // necessary, if the packet needs a response, we should add it
     // as outstanding and express snoops never fail so there is
     // not need to worry about them
-    bool add_outstanding = !pkt->isExpressSnoop() && pkt->needsResponse();
+    bool add_outstanding = !is_express_snoop && pkt->needsResponse();
 
     // keep track that we have an outstanding request packet
     // matching this request, this is used by the coherency
@@ -154,27 +158,32 @@ CoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
     // based on the address and attempt to send the packet
     bool success = masterPorts[findPort(pkt->getAddr())]->sendTimingReq(pkt);
 
-    if (!success)  {
-        // inhibited packets should never be forced to retry
-        assert(!pkt->memInhibitAsserted());
-
-        // if it was added as outstanding and the send failed, then
-        // erase it again
-        if (add_outstanding)
-            outstandingReq.erase(pkt->req);
-
-        DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x RETRY\n",
-                src_port->name(), pkt->cmdString(), pkt->getAddr());
-
-        addToRetryList(src_port);
-        occupyBus(headerFinishTime);
-
-        return false;
+    // if this is an express snoop, we are done at this point
+    if (is_express_snoop) {
+        assert(success);
+    } else {
+        // for normal requests, check if successful
+        if (!success)  {
+            // inhibited packets should never be forced to retry
+            assert(!pkt->memInhibitAsserted());
+
+            // if it was added as outstanding and the send failed, then
+            // erase it again
+            if (add_outstanding)
+                outstandingReq.erase(pkt->req);
+
+            DPRINTF(CoherentBus, "recvTimingReq: src %s %s 0x%x RETRY\n",
+                    src_port->name(), pkt->cmdString(), pkt->getAddr());
+
+            // update the bus state and schedule an idle event
+            failedTiming(src_port, headerFinishTime);
+        } else {
+            // update the bus state and schedule an idle event
+            succeededTiming(packetFinishTime);
+        }
     }
 
-    succeededTiming(packetFinishTime);
-
-    return true;
+    return success;
 }
 
 bool
@@ -185,7 +194,7 @@ CoherentBus::recvTimingResp(PacketPtr pkt, PortID master_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (isOccupied(src_port)) {
+    if (!tryTiming(src_port)) {
         DPRINTF(CoherentBus, "recvTimingResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -239,9 +248,6 @@ CoherentBus::recvTimingSnoopReq(PacketPtr pkt, PortID master_port_id)
     // wrong, hence there is nothing further to do as the packet
     // would be going back to where it came from
     assert(master_port_id == findPort(pkt->getAddr()));
-
-    // this is an express snoop and is never forced to retry
-    assert(!inRetry);
 }
 
 bool
@@ -252,7 +258,7 @@ CoherentBus::recvTimingSnoopResp(PacketPtr pkt, PortID slave_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (isOccupied(src_port)) {
+    if (!tryTiming(src_port)) {
         DPRINTF(CoherentBus, "recvTimingSnoopResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
diff --git a/src/mem/noncoherent_bus.cc b/src/mem/noncoherent_bus.cc
index 4faad757a..718bbebdd 100644
--- a/src/mem/noncoherent_bus.cc
+++ b/src/mem/noncoherent_bus.cc
@@ -97,7 +97,7 @@ NoncoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (isOccupied(src_port)) {
+    if (!tryTiming(src_port)) {
         DPRINTF(NoncoherentBus, "recvTimingReq: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;
@@ -123,8 +123,7 @@ NoncoherentBus::recvTimingReq(PacketPtr pkt, PortID slave_port_id)
         DPRINTF(NoncoherentBus, "recvTimingReq: src %s %s 0x%x RETRY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
 
-        addToRetryList(src_port);
-        occupyBus(headerFinishTime);
+        failedTiming(src_port, headerFinishTime);
 
         return false;
     }
@@ -142,7 +141,7 @@ NoncoherentBus::recvTimingResp(PacketPtr pkt, PortID master_port_id)
 
     // test if the bus should be considered occupied for the current
     // port
-    if (isOccupied(src_port)) {
+    if (!tryTiming(src_port)) {
         DPRINTF(NoncoherentBus, "recvTimingResp: src %s %s 0x%x BUSY\n",
                 src_port->name(), pkt->cmdString(), pkt->getAddr());
         return false;