src/mem/xbar.cc

   1 /*
   2  * Copyright (c) 2011-2015 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  * Authors: Ali Saidi
  41  *          Andreas Hansson
  42  *          William Wang
  43  */
  44
  45 /**
  46  * @file
  47  * Definition of a crossbar object.
  48  */
  49
  50 #include "base/misc.hh"
  51 #include "base/trace.hh"
  52 #include "debug/AddrRanges.hh"
  53 #include "debug/Drain.hh"
  54 #include "debug/XBar.hh"
  55 #include "mem/xbar.hh"
  56
  57 BaseXBar::BaseXBar(const BaseXBarParams *p)
  58     : MemObject(p),
  59       headerCycles(p->header_cycles), width(p->width),
  60       gotAddrRanges(p->port_default_connection_count +
  61                           p->port_master_connection_count, false),
  62       gotAllAddrRanges(false), defaultPortID(InvalidPortID),
  63       useDefaultRange(p->use_default_range)
  64 {}
  65
  66 BaseXBar::~BaseXBar()
  67 {
  68     for (auto m: masterPorts)
  69         delete m;
  70
  71     for (auto s: slavePorts)
  72         delete s;
  73 }
  74
  75 void
  76 BaseXBar::init()
  77 {
  78 }
  79
  80 BaseMasterPort &
  81 BaseXBar::getMasterPort(const std::string &if_name, PortID idx)
  82 {
  83     if (if_name == "master" && idx < masterPorts.size()) {
  84         // the master port index translates directly to the vector position
  85         return *masterPorts[idx];
  86     } else  if (if_name == "default") {
  87         return *masterPorts[defaultPortID];
  88     } else {
  89         return MemObject::getMasterPort(if_name, idx);
  90     }
  91 }
  92
  93 BaseSlavePort &
  94 BaseXBar::getSlavePort(const std::string &if_name, PortID idx)
  95 {
  96     if (if_name == "slave" && idx < slavePorts.size()) {
  97         // the slave port index translates directly to the vector position
  98         return *slavePorts[idx];
  99     } else {
 100         return MemObject::getSlavePort(if_name, idx);
 101     }
 102 }
 103
 104 void
 105 BaseXBar::calcPacketTiming(PacketPtr pkt)
 106 {
 107     // the crossbar will be called at a time that is not necessarily
 108     // coinciding with its own clock, so start by determining how long
 109     // until the next clock edge (could be zero)
 110     Tick offset = clockEdge() - curTick();
 111
 112     // Determine how many cycles are needed to send the data
 113     // If the packet has no data we take into account just the cycle to send
 114     // the header.
 115     unsigned dataCycles = pkt->hasData() ? divCeil(pkt->getSize(), width) : 0;
 116
 117     // before setting the bus delay fields of the packet, ensure that
 118     // the delay from any previous crossbar has been accounted for
 119     if (pkt->headerDelay != 0 || pkt->payloadDelay != 0)
 120         panic("Packet %s already has delay (%d, %d) that should be "
 121               "accounted for.\n", pkt->cmdString(), pkt->headerDelay,
 122               pkt->payloadDelay);
 123
 124     // The headerDelay takes into account the relative time to deliver the
 125     // header of the packet. It will be charged of the additional delay of
 126     // the xbar if the packet goes through it.
 127     pkt->headerDelay = (headerCycles + 1) * clockPeriod() + offset;
 128
 129     // The payloadDelay takes into account the relative time to deliver the
 130     // payload of the packet. If the packet has no data its value is just one
 131     // tick (due to header) plus the offset value.
 132     pkt->payloadDelay = (headerCycles + dataCycles) * clockPeriod() + offset;
 133 }
 134
 135 template <typename SrcType, typename DstType>
 136 BaseXBar::Layer<SrcType,DstType>::Layer(DstType& _port, BaseXBar& _xbar,
 137                                        const std::string& _name) :
 138     port(_port), xbar(_xbar), _name(_name), state(IDLE), drainManager(NULL),
 139     waitingForPeer(NULL), releaseEvent(this)
 140 {
 141 }
 142
 143 template <typename SrcType, typename DstType>
 144 void BaseXBar::Layer<SrcType,DstType>::occupyLayer(Tick until)
 145 {
 146     // ensure the state is busy at this point, as the layer should
 147     // transition from idle as soon as it has decided to forward the
 148     // packet to prevent any follow-on calls to sendTiming seeing an
 149     // unoccupied layer
 150     assert(state == BUSY);
 151
 152     // until should never be 0 as express snoops never occupy the layer
 153     assert(until != 0);
 154     xbar.schedule(releaseEvent, until);
 155
 156     // account for the occupied ticks
 157     occupancy += until - curTick();
 158
 159     DPRINTF(BaseXBar, "The crossbar layer is now busy from tick %d to %d\n",
 160             curTick(), until);
 161 }
 162
 163 template <typename SrcType, typename DstType>
 164 bool
 165 BaseXBar::Layer<SrcType,DstType>::tryTiming(SrcType* src_port)
 166 {
 167     // if we are in the retry state, we will not see anything but the
 168     // retrying port (or in the case of the snoop ports the snoop
 169     // response port that mirrors the actual slave port) as we leave
 170     // this state again in zero time if the peer does not immediately
 171     // call the layer when receiving the retry
 172
 173     // first we see if the layer is busy, next we check if the
 174     // destination port is already engaged in a transaction waiting
 175     // for a retry from the peer
 176     if (state == BUSY || waitingForPeer != NULL) {
 177         // the port should not be waiting already
 178         assert(std::find(waitingForLayer.begin(), waitingForLayer.end(),
 179                          src_port) == waitingForLayer.end());
 180
 181         // put the port at the end of the retry list waiting for the
 182         // layer to be freed up (and in the case of a busy peer, for
 183         // that transaction to go through, and then the layer to free
 184         // up)
 185         waitingForLayer.push_back(src_port);
 186         return false;
 187     }
 188
 189     state = BUSY;
 190
 191     return true;
 192 }
 193
 194 template <typename SrcType, typename DstType>
 195 void
 196 BaseXBar::Layer<SrcType,DstType>::succeededTiming(Tick busy_time)
 197 {
 198     // we should have gone from idle or retry to busy in the tryTiming
 199     // test
 200     assert(state == BUSY);
 201
 202     // occupy the layer accordingly
 203     occupyLayer(busy_time);
 204 }
 205
 206 template <typename SrcType, typename DstType>
 207 void
 208 BaseXBar::Layer<SrcType,DstType>::failedTiming(SrcType* src_port,
 209                                               Tick busy_time)
 210 {
 211     // ensure no one got in between and tried to send something to
 212     // this port
 213     assert(waitingForPeer == NULL);
 214
 215     // if the source port is the current retrying one or not, we have
 216     // failed in forwarding and should track that we are now waiting
 217     // for the peer to send a retry
 218     waitingForPeer = src_port;
 219
 220     // we should have gone from idle or retry to busy in the tryTiming
 221     // test
 222     assert(state == BUSY);
 223
 224     // occupy the bus accordingly
 225     occupyLayer(busy_time);
 226 }
 227
 228 template <typename SrcType, typename DstType>
 229 void
 230 BaseXBar::Layer<SrcType,DstType>::releaseLayer()
 231 {
 232     // releasing the bus means we should now be idle
 233     assert(state == BUSY);
 234     assert(!releaseEvent.scheduled());
 235
 236     // update the state
 237     state = IDLE;
 238
 239     // bus layer is now idle, so if someone is waiting we can retry
 240     if (!waitingForLayer.empty()) {
 241         // there is no point in sending a retry if someone is still
 242         // waiting for the peer
 243         if (waitingForPeer == NULL)
 244             retryWaiting();
 245     } else if (waitingForPeer == NULL && drainManager) {
 246         DPRINTF(Drain, "Crossbar done draining, signaling drain manager\n");
 247         //If we weren't able to drain before, do it now.
 248         drainManager->signalDrainDone();
 249         // Clear the drain event once we're done with it.
 250         drainManager = NULL;
 251     }
 252 }
 253
 254 template <typename SrcType, typename DstType>
 255 void
 256 BaseXBar::Layer<SrcType,DstType>::retryWaiting()
 257 {
 258     // this should never be called with no one waiting
 259     assert(!waitingForLayer.empty());
 260
 261     // we always go to retrying from idle
 262     assert(state == IDLE);
 263
 264     // update the state
 265     state = RETRY;
 266
 267     // set the retrying port to the front of the retry list and pop it
 268     // off the list
 269     SrcType* retryingPort = waitingForLayer.front();
 270     waitingForLayer.pop_front();
 271
 272     // tell the port to retry, which in some cases ends up calling the
 273     // layer again
 274     sendRetry(retryingPort);
 275
 276     // If the layer is still in the retry state, sendTiming wasn't
 277     // called in zero time (e.g. the cache does this), burn a cycle
 278     if (state == RETRY) {
 279         // update the state to busy and reset the retrying port, we
 280         // have done our bit and sent the retry
 281         state = BUSY;
 282
 283         // occupy the crossbar layer until the next cycle ends
 284         occupyLayer(xbar.clockEdge(Cycles(1)));
 285     }
 286 }
 287
 288 template <typename SrcType, typename DstType>
 289 void
 290 BaseXBar::Layer<SrcType,DstType>::recvRetry()
 291 {
 292     // we should never get a retry without having failed to forward
 293     // something to this port
 294     assert(waitingForPeer != NULL);
 295
 296     // add the port where the failed packet originated to the front of
 297     // the waiting ports for the layer, this allows us to call retry
 298     // on the port immediately if the crossbar layer is idle
 299     waitingForLayer.push_front(waitingForPeer);
 300
 301     // we are no longer waiting for the peer
 302     waitingForPeer = NULL;
 303
 304     // if the layer is idle, retry this port straight away, if we
 305     // are busy, then simply let the port wait for its turn
 306     if (state == IDLE) {
 307         retryWaiting();
 308     } else {
 309         assert(state == BUSY);
 310     }
 311 }
 312
 313 PortID
 314 BaseXBar::findPort(Addr addr)
 315 {
 316     // we should never see any address lookups before we've got the
 317     // ranges of all connected slave modules
 318     assert(gotAllAddrRanges);
 319
 320     // Check the cache
 321     PortID dest_id = checkPortCache(addr);
 322     if (dest_id != InvalidPortID)
 323         return dest_id;
 324
 325     // Check the address map interval tree
 326     auto i = portMap.find(addr);
 327     if (i != portMap.end()) {
 328         dest_id = i->second;
 329         updatePortCache(dest_id, i->first);
 330         return dest_id;
 331     }
 332
 333     // Check if this matches the default range
 334     if (useDefaultRange) {
 335         if (defaultRange.contains(addr)) {
 336             DPRINTF(AddrRanges, "  found addr %#llx on default\n",
 337                     addr);
 338             return defaultPortID;
 339         }
 340     } else if (defaultPortID != InvalidPortID) {
 341         DPRINTF(AddrRanges, "Unable to find destination for addr %#llx, "
 342                 "will use default port\n", addr);
 343         return defaultPortID;
 344     }
 345
 346     // we should use the range for the default port and it did not
 347     // match, or the default port is not set
 348     fatal("Unable to find destination for addr %#llx on %s\n", addr,
 349           name());
 350 }
 351
 352 /** Function called by the port when the crossbar is receiving a range change.*/
 353 void
 354 BaseXBar::recvRangeChange(PortID master_port_id)
 355 {
 356     DPRINTF(AddrRanges, "Received range change from slave port %s\n",
 357             masterPorts[master_port_id]->getSlavePort().name());
 358
 359     // remember that we got a range from this master port and thus the
 360     // connected slave module
 361     gotAddrRanges[master_port_id] = true;
 362
 363     // update the global flag
 364     if (!gotAllAddrRanges) {
 365         // take a logical AND of all the ports and see if we got
 366         // ranges from everyone
 367         gotAllAddrRanges = true;
 368         std::vector<bool>::const_iterator r = gotAddrRanges.begin();
 369         while (gotAllAddrRanges &&  r != gotAddrRanges.end()) {
 370             gotAllAddrRanges &= *r++;
 371         }
 372         if (gotAllAddrRanges)
 373             DPRINTF(AddrRanges, "Got address ranges from all slaves\n");
 374     }
 375
 376     // note that we could get the range from the default port at any
 377     // point in time, and we cannot assume that the default range is
 378     // set before the other ones are, so we do additional checks once
 379     // all ranges are provided
 380     if (master_port_id == defaultPortID) {
 381         // only update if we are indeed checking ranges for the
 382         // default port since the port might not have a valid range
 383         // otherwise
 384         if (useDefaultRange) {
 385             AddrRangeList ranges = masterPorts[master_port_id]->getAddrRanges();
 386
 387             if (ranges.size() != 1)
 388                 fatal("Crossbar %s may only have a single default range",
 389                       name());
 390
 391             defaultRange = ranges.front();
 392         }
 393     } else {
 394         // the ports are allowed to update their address ranges
 395         // dynamically, so remove any existing entries
 396         if (gotAddrRanges[master_port_id]) {
 397             for (auto p = portMap.begin(); p != portMap.end(); ) {
 398                 if (p->second == master_port_id)
 399                     // erasing invalidates the iterator, so advance it
 400                     // before the deletion takes place
 401                     portMap.erase(p++);
 402                 else
 403                     p++;
 404             }
 405         }
 406
 407         AddrRangeList ranges = masterPorts[master_port_id]->getAddrRanges();
 408
 409         for (const auto& r: ranges) {
 410             DPRINTF(AddrRanges, "Adding range %s for id %d\n",
 411                     r.to_string(), master_port_id);
 412             if (portMap.insert(r, master_port_id) == portMap.end()) {
 413                 PortID conflict_id = portMap.find(r)->second;
 414                 fatal("%s has two ports responding within range %s:\n\t%s\n\t%s\n",
 415                       name(),
 416                       r.to_string(),
 417                       masterPorts[master_port_id]->getSlavePort().name(),
 418                       masterPorts[conflict_id]->getSlavePort().name());
 419             }
 420         }
 421     }
 422
 423     // if we have received ranges from all our neighbouring slave
 424     // modules, go ahead and tell our connected master modules in
 425     // turn, this effectively assumes a tree structure of the system
 426     if (gotAllAddrRanges) {
 427         DPRINTF(AddrRanges, "Aggregating address ranges\n");
 428         xbarRanges.clear();
 429
 430         // start out with the default range
 431         if (useDefaultRange) {
 432             if (!gotAddrRanges[defaultPortID])
 433                 fatal("Crossbar %s uses default range, but none provided",
 434                       name());
 435
 436             xbarRanges.push_back(defaultRange);
 437             DPRINTF(AddrRanges, "-- Adding default %s\n",
 438                     defaultRange.to_string());
 439         }
 440
 441         // merge all interleaved ranges and add any range that is not
 442         // a subset of the default range
 443         std::vector<AddrRange> intlv_ranges;
 444         for (const auto& r: portMap) {
 445             // if the range is interleaved then save it for now
 446             if (r.first.interleaved()) {
 447                 // if we already got interleaved ranges that are not
 448                 // part of the same range, then first do a merge
 449                 // before we add the new one
 450                 if (!intlv_ranges.empty() &&
 451                     !intlv_ranges.back().mergesWith(r.first)) {
 452                     DPRINTF(AddrRanges, "-- Merging range from %d ranges\n",
 453                             intlv_ranges.size());
 454                     AddrRange merged_range(intlv_ranges);
 455                     // next decide if we keep the merged range or not
 456                     if (!(useDefaultRange &&
 457                           merged_range.isSubset(defaultRange))) {
 458                         xbarRanges.push_back(merged_range);
 459                         DPRINTF(AddrRanges, "-- Adding merged range %s\n",
 460                                 merged_range.to_string());
 461                     }
 462                     intlv_ranges.clear();
 463                 }
 464                 intlv_ranges.push_back(r.first);
 465             } else {
 466                 // keep the current range if not a subset of the default
 467                 if (!(useDefaultRange &&
 468                       r.first.isSubset(defaultRange))) {
 469                     xbarRanges.push_back(r.first);
 470                     DPRINTF(AddrRanges, "-- Adding range %s\n",
 471                             r.first.to_string());
 472                 }
 473             }
 474         }
 475
 476         // if there is still interleaved ranges waiting to be merged,
 477         // go ahead and do it
 478         if (!intlv_ranges.empty()) {
 479             DPRINTF(AddrRanges, "-- Merging range from %d ranges\n",
 480                     intlv_ranges.size());
 481             AddrRange merged_range(intlv_ranges);
 482             if (!(useDefaultRange && merged_range.isSubset(defaultRange))) {
 483                 xbarRanges.push_back(merged_range);
 484                 DPRINTF(AddrRanges, "-- Adding merged range %s\n",
 485                         merged_range.to_string());
 486             }
 487         }
 488
 489         // also check that no range partially overlaps with the
 490         // default range, this has to be done after all ranges are set
 491         // as there are no guarantees for when the default range is
 492         // update with respect to the other ones
 493         if (useDefaultRange) {
 494             for (const auto& r: xbarRanges) {
 495                 // see if the new range is partially
 496                 // overlapping the default range
 497                 if (r.intersects(defaultRange) &&
 498                     !r.isSubset(defaultRange))
 499                     fatal("Range %s intersects the "                    \
 500                           "default range of %s but is not a "           \
 501                           "subset\n", r.to_string(), name());
 502             }
 503         }
 504
 505         // tell all our neighbouring master ports that our address
 506         // ranges have changed
 507         for (const auto& s: slavePorts)
 508             s->sendRangeChange();
 509     }
 510
 511     clearPortCache();
 512 }
 513
 514 AddrRangeList
 515 BaseXBar::getAddrRanges() const
 516 {
 517     // we should never be asked without first having sent a range
 518     // change, and the latter is only done once we have all the ranges
 519     // of the connected devices
 520     assert(gotAllAddrRanges);
 521
 522     // at the moment, this never happens, as there are no cycles in
 523     // the range queries and no devices on the master side of a crossbar
 524     // (CPU, cache, bridge etc) actually care about the ranges of the
 525     // ports they are connected to
 526
 527     DPRINTF(AddrRanges, "Received address range request\n");
 528
 529     return xbarRanges;
 530 }
 531
 532 void
 533 BaseXBar::regStats()
 534 {
 535     using namespace Stats;
 536
 537     transDist
 538         .init(MemCmd::NUM_MEM_CMDS)
 539         .name(name() + ".trans_dist")
 540         .desc("Transaction distribution")
 541         .flags(nozero);
 542
 543     // get the string representation of the commands
 544     for (int i = 0; i < MemCmd::NUM_MEM_CMDS; i++) {
 545         MemCmd cmd(i);
 546         const std::string &cstr = cmd.toString();
 547         transDist.subname(i, cstr);
 548     }
 549
 550     pktCount
 551         .init(slavePorts.size(), masterPorts.size())
 552         .name(name() + ".pkt_count")
 553         .desc("Packet count per connected master and slave (bytes)")
 554         .flags(total | nozero | nonan);
 555
 556     pktSize
 557         .init(slavePorts.size(), masterPorts.size())
 558         .name(name() + ".pkt_size")
 559         .desc("Cumulative packet size per connected master and slave (bytes)")
 560         .flags(total | nozero | nonan);
 561
 562     // both the packet count and total size are two-dimensional
 563     // vectors, indexed by slave port id and master port id, thus the
 564     // neighbouring master and slave, they do not differentiate what
 565     // came from the master and was forwarded to the slave (requests
 566     // and snoop responses) and what came from the slave and was
 567     // forwarded to the master (responses and snoop requests)
 568     for (int i = 0; i < slavePorts.size(); i++) {
 569         pktCount.subname(i, slavePorts[i]->getMasterPort().name());
 570         pktSize.subname(i, slavePorts[i]->getMasterPort().name());
 571         for (int j = 0; j < masterPorts.size(); j++) {
 572             pktCount.ysubname(j, masterPorts[j]->getSlavePort().name());
 573             pktSize.ysubname(j, masterPorts[j]->getSlavePort().name());
 574         }
 575     }
 576 }
 577
 578 template <typename SrcType, typename DstType>
 579 unsigned int
 580 BaseXBar::Layer<SrcType,DstType>::drain(DrainManager *dm)
 581 {
 582     //We should check that we're not "doing" anything, and that noone is
 583     //waiting. We might be idle but have someone waiting if the device we
 584     //contacted for a retry didn't actually retry.
 585     if (state != IDLE) {
 586         DPRINTF(Drain, "Crossbar not drained\n");
 587         drainManager = dm;
 588         return 1;
 589     }
 590     return 0;
 591 }
 592
 593 template <typename SrcType, typename DstType>
 594 void
 595 BaseXBar::Layer<SrcType,DstType>::regStats()
 596 {
 597     using namespace Stats;
 598
 599     occupancy
 600         .name(name() + ".occupancy")
 601         .desc("Layer occupancy (ticks)")
 602         .flags(nozero);
 603
 604     utilization
 605         .name(name() + ".utilization")
 606         .desc("Layer utilization (%)")
 607         .precision(1)
 608         .flags(nozero);
 609
 610     utilization = 100 * occupancy / simTicks;
 611 }
 612
 613 /**
 614  * Crossbar layer template instantiations. Could be removed with _impl.hh
 615  * file, but since there are only two given options (MasterPort and
 616  * SlavePort) it seems a bit excessive at this point.
 617  */
 618 template class BaseXBar::Layer<SlavePort,MasterPort>;
 619 template class BaseXBar::Layer<MasterPort,SlavePort>;