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
  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     Port *port;
 176     DPRINTF(Bus, "recvTiming: packet src %d dest %d addr 0x%x cmd %s\n",
 177             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 178
 179     BusPort *pktPort;
 180     if (pkt->getSrc() == defaultId)
 181         pktPort = defaultPort;
 182     else pktPort = interfaces[pkt->getSrc()];
 183
 184     // If the bus is busy, or other devices are in line ahead of the current
 185     // one, put this device on the retry list.
 186     if (tickNextIdle > curTick ||
 187             (retryList.size() && (!inRetry || pktPort != retryList.front()))) {
 188         addToRetryList(pktPort);
 189         DPRINTF(Bus, "recvTiming: Bus is busy, returning false\n");
 190         return false;
 191     }
 192
 193     short dest = pkt->getDest();
 194
 195     // Make sure to clear the snoop commit flag so it doesn't think an
 196     // access has been handled twice.
 197     if (dest == Packet::Broadcast) {
 198         port = findPort(pkt->getAddr(), pkt->getSrc());
 199         pkt->flags &= ~SNOOP_COMMIT;
 200         if (timingSnoop(pkt, port ? port : interfaces[pkt->getSrc()])) {
 201             bool success;
 202
 203             pkt->flags |= SNOOP_COMMIT;
 204             success = timingSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 205             assert(success);
 206
 207             if (pkt->flags & SATISFIED) {
 208                 //Cache-Cache transfer occuring
 209                 if (inRetry) {
 210                     retryList.front()->onRetryList(false);
 211                     retryList.pop_front();
 212                     inRetry = false;
 213                 }
 214                 occupyBus(pkt);
 215                 DPRINTF(Bus, "recvTiming: Packet sucessfully sent\n");
 216                 return true;
 217             }
 218         } else {
 219             //Snoop didn't succeed
 220             DPRINTF(Bus, "Adding1 a retry to RETRY list %d\n",
 221                     pktPort->getId());
 222             addToRetryList(pktPort);
 223             return false;
 224         }
 225     } else {
 226         assert(dest >= 0 && dest < maxId);
 227         assert(dest != pkt->getSrc()); // catch infinite loops
 228         port = interfaces[dest];
 229     }
 230
 231     occupyBus(pkt);
 232
 233     if (port) {
 234         if (port->sendTiming(pkt))  {
 235             // Packet was successfully sent. Return true.
 236             // Also take care of retries
 237             if (inRetry) {
 238                 DPRINTF(Bus, "Remove retry from list %d\n",
 239                         retryList.front()->getId());
 240                 retryList.front()->onRetryList(false);
 241                 retryList.pop_front();
 242                 inRetry = false;
 243             }
 244             return true;
 245         }
 246
 247         // Packet not successfully sent. Leave or put it on the retry list.
 248         DPRINTF(Bus, "Adding2 a retry to RETRY list %d\n",
 249                 pktPort->getId());
 250         addToRetryList(pktPort);
 251         return false;
 252     }
 253     else {
 254         //Forwarding up from responder, just return true;
 255         DPRINTF(Bus, "recvTiming: can we be here?\n");
 256         return true;
 257     }
 258 }
 259
 260 void
 261 Bus::recvRetry(int id)
 262 {
 263     // If there's anything waiting, and the bus isn't busy...
 264     if (retryList.size() && curTick >= tickNextIdle) {
 265         //retryingPort = retryList.front();
 266         inRetry = true;
 267         DPRINTF(Bus, "Sending a retry to %s\n", retryList.front()->getPeer()->name());
 268         retryList.front()->sendRetry();
 269         // If inRetry is still true, sendTiming wasn't called
 270         if (inRetry)
 271         {
 272             retryList.front()->onRetryList(false);
 273             retryList.pop_front();
 274             inRetry = false;
 275
 276             //Bring tickNextIdle up to the present
 277             while (tickNextIdle < curTick)
 278                 tickNextIdle += clock;
 279
 280             //Burn a cycle for the missed grant.
 281             tickNextIdle += clock;
 282
 283             busIdle.reschedule(tickNextIdle, true);
 284         }
 285     }
 286     //If we weren't able to drain before, we might be able to now.
 287     if (drainEvent && retryList.size() == 0 && curTick >= tickNextIdle) {
 288         drainEvent->process();
 289         // Clear the drain event once we're done with it.
 290         drainEvent = NULL;
 291     }
 292 }
 293
 294 Port *
 295 Bus::findPort(Addr addr, int id)
 296 {
 297     /* An interval tree would be a better way to do this. --ali. */
 298     int dest_id = -1;
 299
 300     PortIter i = portMap.find(RangeSize(addr,1));
 301     if (i != portMap.end())
 302         dest_id = i->second;
 303
 304     // Check if this matches the default range
 305     if (dest_id == -1) {
 306         for (AddrRangeIter iter = defaultRange.begin();
 307              iter != defaultRange.end(); iter++) {
 308             if (*iter == addr) {
 309                 DPRINTF(Bus, "  found addr %#llx on default\n", addr);
 310                 return defaultPort;
 311             }
 312         }
 313
 314         if (responderSet) {
 315             panic("Unable to find destination for addr (user set default "
 316                   "responder): %#llx", addr);
 317         } else {
 318             DPRINTF(Bus, "Unable to find destination for addr: %#llx, will use "
 319                     "default port", addr);
 320
 321             return defaultPort;
 322         }
 323     }
 324
 325
 326     // we shouldn't be sending this back to where it came from
 327     // do the snoop access and then we should terminate
 328     // the cyclical call.
 329     if (dest_id == id)
 330         return 0;
 331
 332     return interfaces[dest_id];
 333 }
 334
 335 Tick
 336 Bus::atomicSnoop(PacketPtr pkt, Port *responder)
 337 {
 338     Tick response_time = 0;
 339
 340     for (SnoopIter s_iter = snoopPorts.begin();
 341          s_iter != snoopPorts.end();
 342          s_iter++) {
 343         BusPort *p = *s_iter;
 344         if (p != responder && p->getId() != pkt->getSrc()) {
 345             Tick response = p->sendAtomic(pkt);
 346             if (response) {
 347                 assert(!response_time);  //Multiple responders
 348                 response_time = response;
 349             }
 350         }
 351     }
 352
 353     return response_time;
 354 }
 355
 356 void
 357 Bus::functionalSnoop(PacketPtr pkt, Port *responder)
 358 {
 359     // The packet may be changed by another bus on snoops, restore the
 360     // id after each
 361     int src_id = pkt->getSrc();
 362
 363     for (SnoopIter s_iter = snoopPorts.begin();
 364          s_iter != snoopPorts.end();
 365          s_iter++) {
 366         BusPort *p = *s_iter;
 367         if (p != responder && p->getId() != src_id) {
 368             p->sendFunctional(pkt);
 369         }
 370         if (pkt->result == Packet::Success) {
 371             break;
 372         }
 373         pkt->setSrc(src_id);
 374     }
 375 }
 376
 377 bool
 378 Bus::timingSnoop(PacketPtr pkt, Port* responder)
 379 {
 380     for (SnoopIter s_iter = snoopPorts.begin();
 381          s_iter != snoopPorts.end();
 382          s_iter++) {
 383         BusPort *p = *s_iter;
 384         if (p != responder && p->getId() != pkt->getSrc()) {
 385             bool success = p->sendTiming(pkt);
 386             if (!success)
 387                 return false;
 388         }
 389     }
 390
 391     return true;
 392 }
 393
 394
 395 /** Function called by the port when the bus is receiving a Atomic
 396  * transaction.*/
 397 Tick
 398 Bus::recvAtomic(PacketPtr pkt)
 399 {
 400     DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n",
 401             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 402     assert(pkt->getDest() == Packet::Broadcast);
 403     pkt->flags |= SNOOP_COMMIT;
 404
 405     // Assume one bus cycle in order to get through.  This may have
 406     // some clock skew issues yet again...
 407     pkt->finishTime = curTick + clock;
 408
 409     Port *port = findPort(pkt->getAddr(), pkt->getSrc());
 410     Tick snoopTime = atomicSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 411
 412     if (snoopTime)
 413         return snoopTime;  //Snoop satisfies it
 414     else if (port)
 415         return port->sendAtomic(pkt);
 416     else
 417         return 0;
 418 }
 419
 420 /** Function called by the port when the bus is receiving a Functional
 421  * transaction.*/
 422 void
 423 Bus::recvFunctional(PacketPtr pkt)
 424 {
 425     DPRINTF(Bus, "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n",
 426             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 427     assert(pkt->getDest() == Packet::Broadcast);
 428     pkt->flags |= SNOOP_COMMIT;
 429
 430     Port* port = findPort(pkt->getAddr(), pkt->getSrc());
 431     functionalSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 432
 433     // If the snooping found what we were looking for, we're done.
 434     if (pkt->result != Packet::Success && port) {
 435         port->sendFunctional(pkt);
 436     }
 437 }
 438
 439 /** Function called by the port when the bus is receiving a status change.*/
 440 void
 441 Bus::recvStatusChange(Port::Status status, int id)
 442 {
 443     AddrRangeList ranges;
 444     bool snoops;
 445     AddrRangeIter iter;
 446
 447     assert(status == Port::RangeChange &&
 448            "The other statuses need to be implemented.");
 449
 450     DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id);
 451
 452     if (id == defaultId) {
 453         defaultRange.clear();
 454         // Only try to update these ranges if the user set a default responder.
 455         if (responderSet) {
 456             defaultPort->getPeerAddressRanges(ranges, snoops);
 457             assert(snoops == false);
 458             for(iter = ranges.begin(); iter != ranges.end(); iter++) {
 459                 defaultRange.push_back(*iter);
 460                 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n",
 461                         iter->start, iter->end);
 462             }
 463         }
 464     } else {
 465
 466         assert((id < maxId && id >= 0) || id == defaultId);
 467         BusPort *port = interfaces[id];
 468
 469         // Clean out any previously existent ids
 470         for (PortIter portIter = portMap.begin();
 471              portIter != portMap.end(); ) {
 472             if (portIter->second == id)
 473                 portMap.erase(portIter++);
 474             else
 475                 portIter++;
 476         }
 477
 478         for (SnoopIter s_iter = snoopPorts.begin();
 479              s_iter != snoopPorts.end(); ) {
 480             if ((*s_iter)->getId() == id)
 481                 s_iter = snoopPorts.erase(s_iter);
 482             else
 483                 s_iter++;
 484         }
 485
 486         port->getPeerAddressRanges(ranges, snoops);
 487
 488         if (snoops) {
 489             DPRINTF(BusAddrRanges, "Adding id %d to snoop list\n", id);
 490             snoopPorts.push_back(port);
 491         }
 492
 493         for (iter = ranges.begin(); iter != ranges.end(); iter++) {
 494             DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n",
 495                     iter->start, iter->end, id);
 496             if (portMap.insert(*iter, id) == portMap.end())
 497                 panic("Two devices with same range\n");
 498
 499         }
 500     }
 501     DPRINTF(MMU, "port list has %d entries\n", portMap.size());
 502
 503     // tell all our peers that our address range has changed.
 504     // Don't tell the device that caused this change, it already knows
 505     m5::hash_map<short,BusPort*>::iterator intIter;
 506
 507     for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
 508         if (intIter->first != id && intIter->first != funcPortId)
 509             intIter->second->sendStatusChange(Port::RangeChange);
 510
 511     if (id != defaultId && defaultPort)
 512         defaultPort->sendStatusChange(Port::RangeChange);
 513 }
 514
 515 void
 516 Bus::addressRanges(AddrRangeList &resp, bool &snoop, int id)
 517 {
 518     resp.clear();
 519     snoop = false;
 520
 521     DPRINTF(BusAddrRanges, "received address range request, returning:\n");
 522
 523     for (AddrRangeIter dflt_iter = defaultRange.begin();
 524          dflt_iter != defaultRange.end(); dflt_iter++) {
 525         resp.push_back(*dflt_iter);
 526         DPRINTF(BusAddrRanges, "  -- Dflt: %#llx : %#llx\n",dflt_iter->start,
 527                 dflt_iter->end);
 528     }
 529     for (PortIter portIter = portMap.begin();
 530          portIter != portMap.end(); portIter++) {
 531         bool subset = false;
 532         for (AddrRangeIter dflt_iter = defaultRange.begin();
 533              dflt_iter != defaultRange.end(); dflt_iter++) {
 534             if ((portIter->first.start < dflt_iter->start &&
 535                 portIter->first.end >= dflt_iter->start) ||
 536                (portIter->first.start < dflt_iter->end &&
 537                 portIter->first.end >= dflt_iter->end))
 538                 fatal("Devices can not set ranges that itersect the default set\
 539                         but are not a subset of the default set.\n");
 540             if (portIter->first.start >= dflt_iter->start &&
 541                 portIter->first.end <= dflt_iter->end) {
 542                 subset = true;
 543                 DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
 544                     portIter->first.start, portIter->first.end);
 545             }
 546         }
 547         if (portIter->second != id && !subset) {
 548             resp.push_back(portIter->first);
 549             DPRINTF(BusAddrRanges, "  -- %#llx : %#llx\n",
 550                     portIter->first.start, portIter->first.end);
 551         }
 552     }
 553
 554     for (SnoopIter s_iter = snoopPorts.begin(); s_iter != snoopPorts.end();
 555          s_iter++) {
 556         if ((*s_iter)->getId() != id) {
 557             snoop = true;
 558             break;
 559         }
 560     }
 561 }
 562
 563 int
 564 Bus::findBlockSize(int id)
 565 {
 566     if (cachedBlockSizeValid)
 567         return cachedBlockSize;
 568
 569     int max_bs = -1;
 570
 571     for (PortIter portIter = portMap.begin();
 572          portIter != portMap.end(); portIter++) {
 573         int tmp_bs = interfaces[portIter->second]->peerBlockSize();
 574         if (tmp_bs > max_bs)
 575             max_bs = tmp_bs;
 576     }
 577     for (SnoopIter s_iter = snoopPorts.begin();
 578          s_iter != snoopPorts.end(); s_iter++) {
 579         int tmp_bs = (*s_iter)->peerBlockSize();
 580         if (tmp_bs > max_bs)
 581             max_bs = tmp_bs;
 582     }
 583     if (max_bs <= 0)
 584         max_bs = defaultBlockSize;
 585
 586     if (max_bs != 64)
 587         warn_once("Blocksize found to not be 64... hmm... probably not.\n");
 588     cachedBlockSize = max_bs;
 589     cachedBlockSizeValid = true;
 590     return max_bs;
 591 }
 592
 593
 594 unsigned int
 595 Bus::drain(Event * de)
 596 {
 597     //We should check that we're not "doing" anything, and that noone is
 598     //waiting. We might be idle but have someone waiting if the device we
 599     //contacted for a retry didn't actually retry.
 600     if (curTick >= tickNextIdle && retryList.size() == 0) {
 601         return 0;
 602     } else {
 603         drainEvent = de;
 604         return 1;
 605     }
 606 }
 607
 608 void
 609 Bus::startup()
 610 {
 611     if (tickNextIdle < curTick)
 612         tickNextIdle = (curTick / clock) * clock + clock;
 613 }
 614
 615 Bus *
 616 BusParams::create()
 617 {
 618     return new Bus(name, bus_id, clock, width, responder_set, block_size);
 619 }