src/mem/xbar.cc

   1 /*
   2  * Copyright (c) 2011-2015, 2018-2020 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2006 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  */
  40
  41 /**
  42  * @file
  43  * Definition of a crossbar object.
  44  */
  45
  46 #include "mem/xbar.hh"
  47
  48 #include "base/logging.hh"
  49 #include "base/trace.hh"
  50 #include "debug/AddrRanges.hh"
  51 #include "debug/Drain.hh"
  52 #include "debug/XBar.hh"
  53
  54 BaseXBar::BaseXBar(const BaseXBarParams &p)
  55     : ClockedObject(p),
  56       frontendLatency(p.frontend_latency),
  57       forwardLatency(p.forward_latency),
  58       responseLatency(p.response_latency),
  59       headerLatency(p.header_latency),
  60       width(p.width),
  61       gotAddrRanges(p.port_default_connection_count +
  62                           p.port_mem_side_ports_connection_count, false),
  63       gotAllAddrRanges(false), defaultPortID(InvalidPortID),
  64       useDefaultRange(p.use_default_range),
  65
  66       ADD_STAT(transDist, UNIT_COUNT, "Transaction distribution"),
  67       ADD_STAT(pktCount, UNIT_COUNT,
  68                "Packet count per connected requestor and responder"),
  69       ADD_STAT(pktSize, UNIT_BYTE,
  70                "Cumulative packet size per connected requestor and responder "
  71                "(bytes)")
  72 {
  73 }
  74
  75 BaseXBar::~BaseXBar()
  76 {
  77     for (auto port: memSidePorts)
  78         delete port;
  79
  80     for (auto port: cpuSidePorts)
  81         delete port;
  82 }
  83
  84 Port &
  85 BaseXBar::getPort(const std::string &if_name, PortID idx)
  86 {
  87     if (if_name == "mem_side_ports" && idx < memSidePorts.size()) {
  88         // the memory-side ports index translates directly to the vector
  89         // position
  90         return *memSidePorts[idx];
  91     } else  if (if_name == "default") {
  92         return *memSidePorts[defaultPortID];
  93     } else if (if_name == "cpu_side_ports" && idx < cpuSidePorts.size()) {
  94         // the CPU-side ports index translates directly to the vector position
  95         return *cpuSidePorts[idx];
  96     } else {
  97         return ClockedObject::getPort(if_name, idx);
  98     }
  99 }
 100
 101 void
 102 BaseXBar::calcPacketTiming(PacketPtr pkt, Tick header_delay)
 103 {
 104     // the crossbar will be called at a time that is not necessarily
 105     // coinciding with its own clock, so start by determining how long
 106     // until the next clock edge (could be zero)
 107     Tick offset = clockEdge() - curTick();
 108
 109     // the header delay depends on the path through the crossbar, and
 110     // we therefore rely on the caller to provide the actual
 111     // value
 112     pkt->headerDelay += offset + header_delay;
 113
 114     // note that we add the header delay to the existing value, and
 115     // align it to the crossbar clock
 116
 117     // do a quick sanity check to ensure the timings are not being
 118     // ignored, note that this specific value may cause problems for
 119     // slower interconnects
 120     panic_if(pkt->headerDelay > SimClock::Int::us,
 121              "Encountered header delay exceeding 1 us\n");
 122
 123     if (pkt->hasData()) {
 124         // the payloadDelay takes into account the relative time to
 125         // deliver the payload of the packet, after the header delay,
 126         // we take the maximum since the payload delay could already
 127         // be longer than what this parcitular crossbar enforces.
 128         pkt->payloadDelay = std::max<Tick>(pkt->payloadDelay,
 129                                            divCeil(pkt->getSize(), width) *
 130                                            clockPeriod());
 131     }
 132
 133     // the payload delay is not paying for the clock offset as that is
 134     // already done using the header delay, and the payload delay is
 135     // also used to determine how long the crossbar layer is busy and
 136     // thus regulates throughput
 137 }
 138
 139 template <typename SrcType, typename DstType>
 140 BaseXBar::Layer<SrcType, DstType>::Layer(DstType& _port, BaseXBar& _xbar,
 141                                        const std::string& _name) :
 142     Stats::Group(&_xbar, _name.c_str()),
 143     port(_port), xbar(_xbar), _name(xbar.name() + "." + _name), state(IDLE),
 144     waitingForPeer(NULL), releaseEvent([this]{ releaseLayer(); }, name()),
 145     ADD_STAT(occupancy, UNIT_TICK, "Layer occupancy (ticks)"),
 146     ADD_STAT(utilization, UNIT_RATIO, "Layer utilization")
 147 {
 148     occupancy
 149         .flags(Stats::nozero);
 150
 151     utilization
 152         .precision(1)
 153         .flags(Stats::nozero);
 154
 155     utilization = occupancy / simTicks;
 156 }
 157
 158 template <typename SrcType, typename DstType>
 159 void BaseXBar::Layer<SrcType, DstType>::occupyLayer(Tick until)
 160 {
 161     // ensure the state is busy at this point, as the layer should
 162     // transition from idle as soon as it has decided to forward the
 163     // packet to prevent any follow-on calls to sendTiming seeing an
 164     // unoccupied layer
 165     assert(state == BUSY);
 166
 167     // until should never be 0 as express snoops never occupy the layer
 168     assert(until != 0);
 169     xbar.schedule(releaseEvent, until);
 170
 171     // account for the occupied ticks
 172     occupancy += until - curTick();
 173
 174     DPRINTF(BaseXBar, "The crossbar layer is now busy from tick %d to %d\n",
 175             curTick(), until);
 176 }
 177
 178 template <typename SrcType, typename DstType>
 179 bool
 180 BaseXBar::Layer<SrcType, DstType>::tryTiming(SrcType* src_port)
 181 {
 182     // if we are in the retry state, we will not see anything but the
 183     // retrying port (or in the case of the snoop ports the snoop
 184     // response port that mirrors the actual CPU-side port) as we leave
 185     // this state again in zero time if the peer does not immediately
 186     // call the layer when receiving the retry
 187
 188     // first we see if the layer is busy, next we check if the
 189     // destination port is already engaged in a transaction waiting
 190     // for a retry from the peer
 191     if (state == BUSY || waitingForPeer != NULL) {
 192         // the port should not be waiting already
 193         assert(std::find(waitingForLayer.begin(), waitingForLayer.end(),
 194                          src_port) == waitingForLayer.end());
 195
 196         // put the port at the end of the retry list waiting for the
 197         // layer to be freed up (and in the case of a busy peer, for
 198         // that transaction to go through, and then the layer to free
 199         // up)
 200         waitingForLayer.push_back(src_port);
 201         return false;
 202     }
 203
 204     state = BUSY;
 205
 206     return true;
 207 }
 208
 209 template <typename SrcType, typename DstType>
 210 void
 211 BaseXBar::Layer<SrcType, DstType>::succeededTiming(Tick busy_time)
 212 {
 213     // we should have gone from idle or retry to busy in the tryTiming
 214     // test
 215     assert(state == BUSY);
 216
 217     // occupy the layer accordingly
 218     occupyLayer(busy_time);
 219 }
 220
 221 template <typename SrcType, typename DstType>
 222 void
 223 BaseXBar::Layer<SrcType, DstType>::failedTiming(SrcType* src_port,
 224                                               Tick busy_time)
 225 {
 226     // ensure no one got in between and tried to send something to
 227     // this port
 228     assert(waitingForPeer == NULL);
 229
 230     // if the source port is the current retrying one or not, we have
 231     // failed in forwarding and should track that we are now waiting
 232     // for the peer to send a retry
 233     waitingForPeer = src_port;
 234
 235     // we should have gone from idle or retry to busy in the tryTiming
 236     // test
 237     assert(state == BUSY);
 238
 239     // occupy the bus accordingly
 240     occupyLayer(busy_time);
 241 }
 242
 243 template <typename SrcType, typename DstType>
 244 void
 245 BaseXBar::Layer<SrcType, DstType>::releaseLayer()
 246 {
 247     // releasing the bus means we should now be idle
 248     assert(state == BUSY);
 249     assert(!releaseEvent.scheduled());
 250
 251     // update the state
 252     state = IDLE;
 253
 254     // bus layer is now idle, so if someone is waiting we can retry
 255     if (!waitingForLayer.empty()) {
 256         // there is no point in sending a retry if someone is still
 257         // waiting for the peer
 258         if (waitingForPeer == NULL)
 259             retryWaiting();
 260     } else if (waitingForPeer == NULL && drainState() == DrainState::Draining) {
 261         DPRINTF(Drain, "Crossbar done draining, signaling drain manager\n");
 262         //If we weren't able to drain before, do it now.
 263         signalDrainDone();
 264     }
 265 }
 266
 267 template <typename SrcType, typename DstType>
 268 void
 269 BaseXBar::Layer<SrcType, DstType>::retryWaiting()
 270 {
 271     // this should never be called with no one waiting
 272     assert(!waitingForLayer.empty());
 273
 274     // we always go to retrying from idle
 275     assert(state == IDLE);
 276
 277     // update the state
 278     state = RETRY;
 279
 280     // set the retrying port to the front of the retry list and pop it
 281     // off the list
 282     SrcType* retryingPort = waitingForLayer.front();
 283     waitingForLayer.pop_front();
 284
 285     // tell the port to retry, which in some cases ends up calling the
 286     // layer again
 287     sendRetry(retryingPort);
 288
 289     // If the layer is still in the retry state, sendTiming wasn't
 290     // called in zero time (e.g. the cache does this when a writeback
 291     // is squashed)
 292     if (state == RETRY) {
 293         // update the state to busy and reset the retrying port, we
 294         // have done our bit and sent the retry
 295         state = BUSY;
 296
 297         // occupy the crossbar layer until the next clock edge
 298         occupyLayer(xbar.clockEdge());
 299     }
 300 }
 301
 302 template <typename SrcType, typename DstType>
 303 void
 304 BaseXBar::Layer<SrcType, DstType>::recvRetry()
 305 {
 306     // we should never get a retry without having failed to forward
 307     // something to this port
 308     assert(waitingForPeer != NULL);
 309
 310     // add the port where the failed packet originated to the front of
 311     // the waiting ports for the layer, this allows us to call retry
 312     // on the port immediately if the crossbar layer is idle
 313     waitingForLayer.push_front(waitingForPeer);
 314
 315     // we are no longer waiting for the peer
 316     waitingForPeer = NULL;
 317
 318     // if the layer is idle, retry this port straight away, if we
 319     // are busy, then simply let the port wait for its turn
 320     if (state == IDLE) {
 321         retryWaiting();
 322     } else {
 323         assert(state == BUSY);
 324     }
 325 }
 326
 327 PortID
 328 BaseXBar::findPort(AddrRange addr_range)
 329 {
 330     // we should never see any address lookups before we've got the
 331     // ranges of all connected CPU-side-port modules
 332     assert(gotAllAddrRanges);
 333
 334     // Check the address map interval tree
 335     auto i = portMap.contains(addr_range);
 336     if (i != portMap.end()) {
 337         return i->second;
 338     }
 339
 340     // Check if this matches the default range
 341     if (useDefaultRange) {
 342         if (addr_range.isSubset(defaultRange)) {
 343             DPRINTF(AddrRanges, "  found addr %s on default\n",
 344                     addr_range.to_string());
 345             return defaultPortID;
 346         }
 347     } else if (defaultPortID != InvalidPortID) {
 348         DPRINTF(AddrRanges, "Unable to find destination for %s, "
 349                 "will use default port\n", addr_range.to_string());
 350         return defaultPortID;
 351     }
 352
 353     // we should use the range for the default port and it did not
 354     // match, or the default port is not set
 355     fatal("Unable to find destination for %s on %s\n", addr_range.to_string(),
 356           name());
 357 }
 358
 359 /** Function called by the port when the crossbar is receiving a range change.*/
 360 void
 361 BaseXBar::recvRangeChange(PortID mem_side_port_id)
 362 {
 363     DPRINTF(AddrRanges, "Received range change from cpu_side_ports %s\n",
 364             memSidePorts[mem_side_port_id]->getPeer());
 365
 366     // remember that we got a range from this memory-side port and thus the
 367     // connected CPU-side-port module
 368     gotAddrRanges[mem_side_port_id] = true;
 369
 370     // update the global flag
 371     if (!gotAllAddrRanges) {
 372         // take a logical AND of all the ports and see if we got
 373         // ranges from everyone
 374         gotAllAddrRanges = true;
 375         std::vector<bool>::const_iterator r = gotAddrRanges.begin();
 376         while (gotAllAddrRanges &&  r != gotAddrRanges.end()) {
 377             gotAllAddrRanges &= *r++;
 378         }
 379         if (gotAllAddrRanges)
 380             DPRINTF(AddrRanges, "Got address ranges from all responders\n");
 381     }
 382
 383     // note that we could get the range from the default port at any
 384     // point in time, and we cannot assume that the default range is
 385     // set before the other ones are, so we do additional checks once
 386     // all ranges are provided
 387     if (mem_side_port_id == defaultPortID) {
 388         // only update if we are indeed checking ranges for the
 389         // default port since the port might not have a valid range
 390         // otherwise
 391         if (useDefaultRange) {
 392             AddrRangeList ranges = memSidePorts[mem_side_port_id]->
 393                                    getAddrRanges();
 394
 395             if (ranges.size() != 1)
 396                 fatal("Crossbar %s may only have a single default range",
 397                       name());
 398
 399             defaultRange = ranges.front();
 400         }
 401     } else {
 402         // the ports are allowed to update their address ranges
 403         // dynamically, so remove any existing entries
 404         if (gotAddrRanges[mem_side_port_id]) {
 405             for (auto p = portMap.begin(); p != portMap.end(); ) {
 406                 if (p->second == mem_side_port_id)
 407                     // erasing invalidates the iterator, so advance it
 408                     // before the deletion takes place
 409                     portMap.erase(p++);
 410                 else
 411                     p++;
 412             }
 413         }
 414
 415         AddrRangeList ranges = memSidePorts[mem_side_port_id]->
 416                                getAddrRanges();
 417
 418         for (const auto& r: ranges) {
 419             DPRINTF(AddrRanges, "Adding range %s for id %d\n",
 420                     r.to_string(), mem_side_port_id);
 421             if (portMap.insert(r, mem_side_port_id) == portMap.end()) {
 422                 PortID conflict_id = portMap.intersects(r)->second;
 423                 fatal("%s has two ports responding within range "
 424                       "%s:\n\t%s\n\t%s\n",
 425                       name(),
 426                       r.to_string(),
 427                       memSidePorts[mem_side_port_id]->getPeer(),
 428                       memSidePorts[conflict_id]->getPeer());
 429             }
 430         }
 431     }
 432
 433     // if we have received ranges from all our neighbouring CPU-side-port
 434     // modules, go ahead and tell our connected memory-side-port modules in
 435     // turn, this effectively assumes a tree structure of the system
 436     if (gotAllAddrRanges) {
 437         DPRINTF(AddrRanges, "Aggregating address ranges\n");
 438         xbarRanges.clear();
 439
 440         // start out with the default range
 441         if (useDefaultRange) {
 442             if (!gotAddrRanges[defaultPortID])
 443                 fatal("Crossbar %s uses default range, but none provided",
 444                       name());
 445
 446             xbarRanges.push_back(defaultRange);
 447             DPRINTF(AddrRanges, "-- Adding default %s\n",
 448                     defaultRange.to_string());
 449         }
 450
 451         // merge all interleaved ranges and add any range that is not
 452         // a subset of the default range
 453         std::vector<AddrRange> intlv_ranges;
 454         for (const auto& r: portMap) {
 455             // if the range is interleaved then save it for now
 456             if (r.first.interleaved()) {
 457                 // if we already got interleaved ranges that are not
 458                 // part of the same range, then first do a merge
 459                 // before we add the new one
 460                 if (!intlv_ranges.empty() &&
 461                     !intlv_ranges.back().mergesWith(r.first)) {
 462                     DPRINTF(AddrRanges, "-- Merging range from %d ranges\n",
 463                             intlv_ranges.size());
 464                     AddrRange merged_range(intlv_ranges);
 465                     // next decide if we keep the merged range or not
 466                     if (!(useDefaultRange &&
 467                           merged_range.isSubset(defaultRange))) {
 468                         xbarRanges.push_back(merged_range);
 469                         DPRINTF(AddrRanges, "-- Adding merged range %s\n",
 470                                 merged_range.to_string());
 471                     }
 472                     intlv_ranges.clear();
 473                 }
 474                 intlv_ranges.push_back(r.first);
 475             } else {
 476                 // keep the current range if not a subset of the default
 477                 if (!(useDefaultRange &&
 478                       r.first.isSubset(defaultRange))) {
 479                     xbarRanges.push_back(r.first);
 480                     DPRINTF(AddrRanges, "-- Adding range %s\n",
 481                             r.first.to_string());
 482                 }
 483             }
 484         }
 485
 486         // if there is still interleaved ranges waiting to be merged,
 487         // go ahead and do it
 488         if (!intlv_ranges.empty()) {
 489             DPRINTF(AddrRanges, "-- Merging range from %d ranges\n",
 490                     intlv_ranges.size());
 491             AddrRange merged_range(intlv_ranges);
 492             if (!(useDefaultRange && merged_range.isSubset(defaultRange))) {
 493                 xbarRanges.push_back(merged_range);
 494                 DPRINTF(AddrRanges, "-- Adding merged range %s\n",
 495                         merged_range.to_string());
 496             }
 497         }
 498
 499         // also check that no range partially intersects with the
 500         // default range, this has to be done after all ranges are set
 501         // as there are no guarantees for when the default range is
 502         // update with respect to the other ones
 503         if (useDefaultRange) {
 504             for (const auto& r: xbarRanges) {
 505                 // see if the new range is partially
 506                 // overlapping the default range
 507                 if (r.intersects(defaultRange) &&
 508                     !r.isSubset(defaultRange))
 509                     fatal("Range %s intersects the "                    \
 510                           "default range of %s but is not a "           \
 511                           "subset\n", r.to_string(), name());
 512             }
 513         }
 514
 515         // tell all our neighbouring memory-side ports that our address
 516         // ranges have changed
 517         for (const auto& port: cpuSidePorts)
 518             port->sendRangeChange();
 519     }
 520 }
 521
 522 AddrRangeList
 523 BaseXBar::getAddrRanges() const
 524 {
 525     // we should never be asked without first having sent a range
 526     // change, and the latter is only done once we have all the ranges
 527     // of the connected devices
 528     assert(gotAllAddrRanges);
 529
 530     // at the moment, this never happens, as there are no cycles in
 531     // the range queries and no devices on the memory side of a crossbar
 532     // (CPU, cache, bridge etc) actually care about the ranges of the
 533     // ports they are connected to
 534
 535     DPRINTF(AddrRanges, "Received address range request\n");
 536
 537     return xbarRanges;
 538 }
 539
 540 void
 541 BaseXBar::regStats()
 542 {
 543     ClockedObject::regStats();
 544
 545     using namespace Stats;
 546
 547     transDist
 548         .init(MemCmd::NUM_MEM_CMDS)
 549         .flags(nozero);
 550
 551     // get the string representation of the commands
 552     for (int i = 0; i < MemCmd::NUM_MEM_CMDS; i++) {
 553         MemCmd cmd(i);
 554         const std::string &cstr = cmd.toString();
 555         transDist.subname(i, cstr);
 556     }
 557
 558     pktCount
 559         .init(cpuSidePorts.size(), memSidePorts.size())
 560         .flags(total | nozero | nonan);
 561
 562     pktSize
 563         .init(cpuSidePorts.size(), memSidePorts.size())
 564         .flags(total | nozero | nonan);
 565
 566     // both the packet count and total size are two-dimensional
 567     // vectors, indexed by CPU-side port id and memory-side port id, thus the
 568     // neighbouring memory-side ports and CPU-side ports, they do not
 569     // differentiate what came from the memory-side ports and was forwarded to
 570     // the CPU-side ports (requests and snoop responses) and what came from
 571     // the CPU-side ports and was forwarded to the memory-side ports (responses
 572     // and snoop requests)
 573     for (int i = 0; i < cpuSidePorts.size(); i++) {
 574         pktCount.subname(i, cpuSidePorts[i]->getPeer().name());
 575         pktSize.subname(i, cpuSidePorts[i]->getPeer().name());
 576         for (int j = 0; j < memSidePorts.size(); j++) {
 577             pktCount.ysubname(j, memSidePorts[j]->getPeer().name());
 578             pktSize.ysubname(j, memSidePorts[j]->getPeer().name());
 579         }
 580     }
 581 }
 582
 583 template <typename SrcType, typename DstType>
 584 DrainState
 585 BaseXBar::Layer<SrcType, DstType>::drain()
 586 {
 587     //We should check that we're not "doing" anything, and that noone is
 588     //waiting. We might be idle but have someone waiting if the device we
 589     //contacted for a retry didn't actually retry.
 590     if (state != IDLE) {
 591         DPRINTF(Drain, "Crossbar not drained\n");
 592         return DrainState::Draining;
 593     } else {
 594         return DrainState::Drained;
 595     }
 596 }
 597
 598 /**
 599  * Crossbar layer template instantiations. Could be removed with _impl.hh
 600  * file, but since there are only two given options (RequestPort and
 601  * ResponsePort) it seems a bit excessive at this point.
 602  */
 603 template class BaseXBar::Layer<ResponsePort, RequestPort>;
 604 template class BaseXBar::Layer<RequestPort, ResponsePort>;