src/mem/bus.cc

   1 /*
   2  * Copyright (c) 2006 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Ali Saidi
  29  */
  30
  31 /**
  32  * @file
  33  * Definition of a bus object.
  34  */
  35
  36 #include <algorithm>
  37 #include <limits>
  38
  39 #include "base/misc.hh"
  40 #include "base/trace.hh"
  41 #include "mem/bus.hh"
  42 #include "params/Bus.hh"
  43
  44 Port *
  45 Bus::getPort(const std::string &if_name, int idx)
  46 {
  47     if (if_name == "default") {
  48         if (defaultPort == NULL) {
  49             defaultPort = new BusPort(csprintf("%s-default",name()), this,
  50                                       defaultId);
  51             cachedBlockSizeValid = false;
  52             return defaultPort;
  53         } else
  54             fatal("Default port already set\n");
  55     }
  56     int id;
  57     if (if_name == "functional") {
  58         if (!funcPort) {
  59             id = maxId++;
  60             funcPort = new BusPort(csprintf("%s-p%d-func", name(), id), this, id);
  61             funcPortId = id;
  62             interfaces[id] = funcPort;
  63         }
  64         return funcPort;
  65     }
  66
  67     // if_name ignored?  forced to be empty?
  68     id = maxId++;
  69     assert(maxId < std::numeric_limits<typeof(maxId)>::max());
  70     BusPort *bp = new BusPort(csprintf("%s-p%d", name(), id), this, id);
  71     interfaces[id] = bp;
  72     cachedBlockSizeValid = false;
  73     return bp;
  74 }
  75
  76 void
  77 Bus::deletePortRefs(Port *p)
  78 {
  79
  80     BusPort *bp =  dynamic_cast<BusPort*>(p);
  81     if (bp == NULL)
  82         panic("Couldn't convert Port* to BusPort*\n");
  83     // If this is our one functional port
  84     if (funcPort == bp)
  85         return;
  86     interfaces.erase(bp->getId());
  87     delete bp;
  88 }
  89
  90 /** Get the ranges of anyone other buses that we are connected to. */
  91 void
  92 Bus::init()
  93 {
  94     m5::hash_map<short,BusPort*>::iterator intIter;
  95
  96     for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
  97         intIter->second->sendStatusChange(Port::RangeChange);
  98 }
  99
 100 Bus::BusFreeEvent::BusFreeEvent(Bus *_bus) : Event(&mainEventQueue), bus(_bus)
 101 {}
 102
 103 void Bus::BusFreeEvent::process()
 104 {
 105     bus->recvRetry(-1);
 106 }
 107
 108 const char * Bus::BusFreeEvent::description()
 109 {
 110     return "bus became available";
 111 }
 112
 113 void Bus::occupyBus(PacketPtr pkt)
 114 {
 115     //Bring tickNextIdle up to the present tick
 116     //There is some potential ambiguity where a cycle starts, which might make
 117     //a difference when devices are acting right around a cycle boundary. Using
 118     //a < allows things which happen exactly on a cycle boundary to take up
 119     //only the following cycle. Anything that happens later will have to "wait"
 120     //for the end of that cycle, and then start using the bus after that.
 121     if (tickNextIdle < curTick) {
 122         tickNextIdle = curTick;
 123         if (tickNextIdle % clock != 0)
 124             tickNextIdle = curTick - (curTick % clock) + clock;
 125     }
 126
 127     // The packet will be sent. Figure out how long it occupies the bus, and
 128     // how much of that time is for the first "word", aka bus width.
 129     int numCycles = 0;
 130     // Requests need one cycle to send an address
 131     if (pkt->isRequest())
 132         numCycles++;
 133     else if (pkt->isResponse() || pkt->hasData()) {
 134         // If a packet has data, it needs ceil(size/width) cycles to send it
 135         // We're using the "adding instead of dividing" trick again here
 136         if (pkt->hasData()) {
 137             int dataSize = pkt->getSize();
 138             numCycles += dataSize/width;
 139             if (dataSize % width)
 140                 numCycles++;
 141         } else {
 142             // If the packet didn't have data, it must have been a response.
 143             // Those use the bus for one cycle to send their data.
 144             numCycles++;
 145         }
 146     }
 147
 148     // The first word will be delivered after the current tick, the delivery
 149     // of the address if any, and one bus cycle to deliver the data
 150     pkt->firstWordTime =
 151         tickNextIdle +
 152         pkt->isRequest() ? clock : 0 +
 153         clock;
 154
 155     //Advance it numCycles bus cycles.
 156     //XXX Should this use the repeated addition trick as well?
 157     tickNextIdle += (numCycles * clock);
 158     if (!busIdle.scheduled()) {
 159         busIdle.schedule(tickNextIdle);
 160     } else {
 161         busIdle.reschedule(tickNextIdle);
 162     }
 163     DPRINTF(Bus, "The bus is now occupied from tick %d to %d\n",
 164             curTick, tickNextIdle);
 165
 166     // The bus will become idle once the current packet is delivered.
 167     pkt->finishTime = tickNextIdle;
 168 }
 169
 170 /** Function called by the port when the bus is receiving a Timing
 171  * transaction.*/
 172 bool
 173 Bus::recvTiming(PacketPtr pkt)
 174 {
 175     short src = pkt->getSrc();
 176     DPRINTF(Bus, "recvTiming: packet src %d dest %d addr 0x%x cmd %s\n",
 177             src, pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 178
 179     BusPort *src_port = (src == defaultId) ? defaultPort : interfaces[src];
 180
 181     // If the bus is busy, or other devices are in line ahead of the current
 182     // one, put this device on the retry list.
 183     if (!pkt->isExpressSnoop() &&
 184         (tickNextIdle > curTick ||
 185          (retryList.size() && (!inRetry || src_port != retryList.front()))))
 186     {
 187         addToRetryList(src_port);
 188         DPRINTF(Bus, "recvTiming: Bus is busy, returning false\n");
 189         return false;
 190     }
 191
 192     if (!pkt->isExpressSnoop()) {
 193         occupyBus(pkt);
 194     }
 195
 196     short dest = pkt->getDest();
 197     int dest_port_id;
 198     Port *dest_port;
 199
 200     if (dest == Packet::Broadcast) {
 201         dest_port_id = findPort(pkt->getAddr());
 202         dest_port = (dest_port_id == defaultId) ?
 203             defaultPort : interfaces[dest_port_id];
 204         for (SnoopIter s_iter = snoopPorts.begin();
 205              s_iter != snoopPorts.end();
 206              s_iter++) {
 207             BusPort *p = *s_iter;
 208             if (p != dest_port && p != src_port) {
 209 #ifndef NDEBUG
 210                 // cache is not allowed to refuse snoop
 211                 bool success = p->sendTiming(pkt);
 212                 assert(success);
 213 #else
 214                 // avoid unused variable warning
 215                 p->sendTiming(pkt);
 216 #endif
 217             }
 218         }
 219     } else {
 220         assert(dest >= 0 && dest < maxId);
 221         assert(dest != src); // catch infinite loops
 222         dest_port_id = dest;
 223         dest_port = (dest_port_id == defaultId) ?
 224             defaultPort : interfaces[dest_port_id];
 225     }
 226
 227     if (dest_port_id == src) {
 228         // Must be forwarded snoop up from below...
 229         assert(dest == Packet::Broadcast);
 230     } else {
 231         // send to actual target
 232         if (!dest_port->sendTiming(pkt))  {
 233             // Packet not successfully sent. Leave or put it on the retry list.
 234             // illegal to block responses... can lead to deadlock
 235             assert(!pkt->isResponse());
 236             DPRINTF(Bus, "Adding2 a retry to RETRY list %d\n", src);
 237             addToRetryList(src_port);
 238             return false;
 239         }
 240         // send OK, fall through
 241     }
 242
 243     // Packet was successfully sent.
 244     // Also take care of retries
 245     if (inRetry) {
 246         DPRINTF(Bus, "Remove retry from list %d\n", src);
 247         retryList.front()->onRetryList(false);
 248         retryList.pop_front();
 249         inRetry = false;
 250     }
 251     return true;
 252 }
 253
 254 void
 255 Bus::recvRetry(int id)
 256 {
 257     // If there's anything waiting, and the bus isn't busy...
 258     if (retryList.size() && curTick >= tickNextIdle) {
 259         //retryingPort = retryList.front();
 260         inRetry = true;
 261         DPRINTF(Bus, "Sending a retry to %s\n", retryList.front()->getPeer()->name());
 262         retryList.front()->sendRetry();
 263         // If inRetry is still true, sendTiming wasn't called
 264         if (inRetry)
 265         {
 266             retryList.front()->onRetryList(false);
 267             retryList.pop_front();
 268             inRetry = false;
 269
 270             //Bring tickNextIdle up to the present
 271             while (tickNextIdle < curTick)
 272                 tickNextIdle += clock;
 273
 274             //Burn a cycle for the missed grant.
 275             tickNextIdle += clock;
 276
 277             busIdle.reschedule(tickNextIdle, true);
 278         }
 279     }
 280     //If we weren't able to drain before, we might be able to now.
 281     if (drainEvent && retryList.size() == 0 && curTick >= tickNextIdle) {
 282         drainEvent->process();
 283         // Clear the drain event once we're done with it.
 284         drainEvent = NULL;
 285     }
 286 }
 287
 288 int
 289 Bus::findPort(Addr addr)
 290 {
 291     /* An interval tree would be a better way to do this. --ali. */
 292     int dest_id = -1;
 293
 294     PortIter i = portMap.find(RangeSize(addr,1));
 295     if (i != portMap.end())
 296         dest_id = i->second;
 297
 298     // Check if this matches the default range
 299     if (dest_id == -1) {
 300         for (AddrRangeIter iter = defaultRange.begin();
 301              iter != defaultRange.end(); iter++) {
 302             if (*iter == addr) {
 303                 DPRINTF(Bus, "  found addr %#llx on default\n", addr);
 304                 return defaultId;
 305             }
 306         }
 307
 308         if (responderSet) {
 309             panic("Unable to find destination for addr (user set default "
 310                   "responder): %#llx", addr);
 311         } else {
 312             DPRINTF(Bus, "Unable to find destination for addr: %#llx, will use "
 313                     "default port", addr);
 314
 315             return defaultId;
 316         }
 317     }
 318
 319     return dest_id;
 320 }
 321
 322
 323 /** Function called by the port when the bus is receiving a Atomic
 324  * transaction.*/
 325 Tick
 326 Bus::recvAtomic(PacketPtr pkt)
 327 {
 328     DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n",
 329             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 330     assert(pkt->getDest() == Packet::Broadcast);
 331     assert(pkt->isRequest());
 332
 333     // Variables for recording original command and snoop response (if
 334     // any)... if a snooper respondes, we will need to restore
 335     // original command so that additional snoops can take place
 336     // properly
 337     MemCmd orig_cmd = pkt->cmd;
 338     MemCmd snoop_response_cmd = MemCmd::InvalidCmd;
 339     Tick snoop_response_latency = 0;
 340     int orig_src = pkt->getSrc();
 341
 342     int target_port_id = findPort(pkt->getAddr());
 343     Port *target_port = (target_port_id == defaultId) ?
 344         defaultPort : interfaces[target_port_id];
 345
 346     SnoopIter s_end = snoopPorts.end();
 347     for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) {
 348         BusPort *p = *s_iter;
 349         // same port should not have both target addresses and snooping
 350         assert(p != target_port);
 351         if (p->getId() != pkt->getSrc()) {
 352             Tick latency = p->sendAtomic(pkt);
 353             if (pkt->isResponse()) {
 354                 // response from snoop agent
 355                 assert(pkt->cmd != orig_cmd);
 356                 assert(pkt->memInhibitAsserted());
 357                 // should only happen once
 358                 assert(snoop_response_cmd == MemCmd::InvalidCmd);
 359                 // save response state
 360                 snoop_response_cmd = pkt->cmd;
 361                 snoop_response_latency = latency;
 362                 // restore original packet state for remaining snoopers
 363                 pkt->cmd = orig_cmd;
 364                 pkt->setSrc(orig_src);
 365                 pkt->setDest(Packet::Broadcast);
 366             }
 367         }
 368     }
 369
 370     Tick response_latency = 0;
 371
 372     // we can get requests sent up from the memory side of the bus for
 373     // snooping... don't send them back down!
 374     if (target_port_id != pkt->getSrc()) {
 375         response_latency = target_port->sendAtomic(pkt);
 376     }
 377
 378     // if we got a response from a snooper, restore it here
 379     if (snoop_response_cmd != MemCmd::InvalidCmd) {
 380         // no one else should have responded
 381         assert(!pkt->isResponse());
 382         assert(pkt->cmd == orig_cmd);
 383         pkt->cmd = snoop_response_cmd;
 384         response_latency = snoop_response_latency;
 385     }
 386
 387     // why do we have this packet field and the return value both???
 388     pkt->finishTime = curTick + response_latency;
 389     return response_latency;
 390 }
 391
 392 /** Function called by the port when the bus is receiving a Functional
 393  * transaction.*/
 394 void
 395 Bus::recvFunctional(PacketPtr pkt)
 396 {
 397     DPRINTF(Bus, "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n",
 398             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 399     assert(pkt->getDest() == Packet::Broadcast);
 400
 401     int port_id = findPort(pkt->getAddr());
 402     Port *port = (port_id == defaultId) ? defaultPort : interfaces[port_id];
 403     // The packet may be changed by another bus on snoops, restore the
 404     // id after each
 405     int src_id = pkt->getSrc();
 406
 407     assert(pkt->isRequest()); // hasn't already been satisfied
 408
 409     for (SnoopIter s_iter = snoopPorts.begin();
 410          s_iter != snoopPorts.end();
 411          s_iter++) {
 412         BusPort *p = *s_iter;
 413         if (p != port && p->getId() != src_id) {
 414             p->sendFunctional(pkt);
 415         }
 416         if (pkt->isResponse()) {
 417             break;
 418         }
 419         pkt->setSrc(src_id);
 420     }
 421
 422     // If the snooping hasn't found what we were looking for, keep going.
 423     if (!pkt->isResponse() && port_id != pkt->getSrc()) {
 424         port->sendFunctional(pkt);
 425     }
 426 }
 427
 428 /** Function called by the port when the bus is receiving a status change.*/
 429 void
 430 Bus::recvStatusChange(Port::Status status, int id)
 431 {
 432     AddrRangeList ranges;
 433     bool snoops;
 434     AddrRangeIter iter;
 435
 436     assert(status == Port::RangeChange &&
 437            "The other statuses need to be implemented.");
 438
 439     DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id);
 440
 441     if (id == defaultId) {
 442         defaultRange.clear();
 443         // Only try to update these ranges if the user set a default responder.
 444         if (responderSet) {
 445             defaultPort->getPeerAddressRanges(ranges, snoops);
 446             assert(snoops == false);
 447             for(iter = ranges.begin(); iter != ranges.end(); iter++) {
 448                 defaultRange.push_back(*iter);
 449                 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n",
 450                         iter->start, iter->end);
 451             }
 452         }
 453     } else {
 454
 455         assert((id < maxId && id >= 0) || id == defaultId);
 456         BusPort *port = interfaces[id];
 457
 458         // Clean out any previously existent ids
 459         for (PortIter portIter = portMap.begin();
 460              portIter != portMap.end(); ) {
 461             if (portIter->second == id)
 462                 portMap.erase(portIter++);
 463             else
 464                 portIter++;
 465         }
 466
 467         for (SnoopIter s_iter = snoopPorts.begin();
 468              s_iter != snoopPorts.end(); ) {
 469             if ((*s_iter)->getId() == id)
 470                 s_iter = snoopPorts.erase(s_iter);
 471             else
 472                 s_iter++;
 473         }
 474
 475         port->getPeerAddressRanges(ranges, snoops);
 476
 477         if (snoops) {
 478             DPRINTF(BusAddrRanges, "Adding id %d to snoop list\n", id);
 479             snoopPorts.push_back(port);
 480         }
 481
 482         for (iter = ranges.begin(); iter != ranges.end(); iter++) {
 483             DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n",
 484                     iter->start, iter->end, id);
 485             if (portMap.insert(*iter, id) == portMap.end())
 486                 panic("Two devices with same range\n");
 487
 488         }
 489     }
 490     DPRINTF(MMU, "port list has %d entries\n", portMap.size());
 491
 492     // tell all our peers that our address range has changed.
 493     // Don't tell the device that caused this change, it already knows
 494     m5::hash_map<short,BusPort*>::iterator intIter;
 495
 496     for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
 497         if (intIter->first != id && intIter->first != funcPortId)
 498             intIter->second->sendStatusChange(Port::RangeChange);
 499
 500     if (id != defaultId && defaultPort)
 501         defaultPort->sendStatusChange(Port::RangeChange);
 502 }
 503
 504 void
 505 Bus::addressRanges(AddrRangeList &resp, bool &snoop, int id)
 506 {
 507     resp.clear();
 508     snoop = false;
 509
 510     DPRINTF(BusAddrRanges, "received address range request, returning:\n");
 511
 512     for (AddrRangeIter dflt_iter = defaultRange.begin();
 513          dflt_iter != defaultRange.end(); dflt_iter++) {
 514         resp.push_back(*dflt_iter);
 515         DPRINTF(BusAddrRanges, "  -- Dflt: %#llx : %#llx\n",dflt_iter->start,
 516                 dflt_iter->end);
 517     }
 518     for (PortIter portIter = portMap.begin();
 519          portIter != portMap.end(); portIter++) {
 520         bool subset = false;
 521         for (AddrRangeIter dflt_iter = defaultRange.begin();
 522              dflt_iter != defaultRange.end(); dflt_iter++) {
 523             if ((portIter->first.start < dflt_iter->start &&
 524                 portIter->first.end >= dflt_iter->start) ||
 525                (portIter->first.start < dflt_iter->end &&
 526                 portIter->first.end >= dflt_iter->end))
 527                 fatal("Devices can not set ranges that itersect the default set\
 528                         but are not a subset of the default set.\n");
 529             if (portIter->first.start >= dflt_iter->start &&
 530                 portIter->first.end <= dflt_iter->end) {
 531                 subset = true;
 532                 DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
 533                     portIter->first.start, portIter->first.end);
 534             }
 535         }
 536         if (portIter->second != id && !subset) {
 537             resp.push_back(portIter->first);
 538             DPRINTF(BusAddrRanges, "  -- %#llx : %#llx\n",
 539                     portIter->first.start, portIter->first.end);
 540         }
 541     }
 542
 543     for (SnoopIter s_iter = snoopPorts.begin(); s_iter != snoopPorts.end();
 544          s_iter++) {
 545         if ((*s_iter)->getId() != id) {
 546             snoop = true;
 547             break;
 548         }
 549     }
 550 }
 551
 552 int
 553 Bus::findBlockSize(int id)
 554 {
 555     if (cachedBlockSizeValid)
 556         return cachedBlockSize;
 557
 558     int max_bs = -1;
 559
 560     for (PortIter portIter = portMap.begin();
 561          portIter != portMap.end(); portIter++) {
 562         int tmp_bs = interfaces[portIter->second]->peerBlockSize();
 563         if (tmp_bs > max_bs)
 564             max_bs = tmp_bs;
 565     }
 566     for (SnoopIter s_iter = snoopPorts.begin();
 567          s_iter != snoopPorts.end(); s_iter++) {
 568         int tmp_bs = (*s_iter)->peerBlockSize();
 569         if (tmp_bs > max_bs)
 570             max_bs = tmp_bs;
 571     }
 572     if (max_bs <= 0)
 573         max_bs = defaultBlockSize;
 574
 575     if (max_bs != 64)
 576         warn_once("Blocksize found to not be 64... hmm... probably not.\n");
 577     cachedBlockSize = max_bs;
 578     cachedBlockSizeValid = true;
 579     return max_bs;
 580 }
 581
 582
 583 unsigned int
 584 Bus::drain(Event * de)
 585 {
 586     //We should check that we're not "doing" anything, and that noone is
 587     //waiting. We might be idle but have someone waiting if the device we
 588     //contacted for a retry didn't actually retry.
 589     if (curTick >= tickNextIdle && retryList.size() == 0) {
 590         return 0;
 591     } else {
 592         drainEvent = de;
 593         return 1;
 594     }
 595 }
 596
 597 void
 598 Bus::startup()
 599 {
 600     if (tickNextIdle < curTick)
 601         tickNextIdle = (curTick / clock) * clock + clock;
 602 }
 603
 604 Bus *
 605 BusParams::create()
 606 {
 607     return new Bus(name, bus_id, clock, width, responder_set, block_size);
 608 }