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 "sim/builder.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             return defaultPort;
  52         } else
  53             fatal("Default port already set\n");
  54     }
  55
  56     // if_name ignored?  forced to be empty?
  57     int id = maxId++;
  58     assert(maxId < std::numeric_limits<typeof(maxId)>::max());
  59     BusPort *bp = new BusPort(csprintf("%s-p%d", name(), id), this, id);
  60     interfaces[id] = bp;
  61     return bp;
  62 }
  63
  64 void
  65 Bus::deletePortRefs(Port *p)
  66 {
  67     BusPort *bp =  dynamic_cast<BusPort*>(p);
  68     if (bp == NULL)
  69         panic("Couldn't convert Port* to BusPort*\n");
  70     interfaces.erase(bp->getId());
  71 }
  72
  73 /** Get the ranges of anyone other buses that we are connected to. */
  74 void
  75 Bus::init()
  76 {
  77     m5::hash_map<short,BusPort*>::iterator intIter;
  78
  79     for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
  80         intIter->second->sendStatusChange(Port::RangeChange);
  81 }
  82
  83 Bus::BusFreeEvent::BusFreeEvent(Bus *_bus) : Event(&mainEventQueue), bus(_bus)
  84 {}
  85
  86 void Bus::BusFreeEvent::process()
  87 {
  88     bus->recvRetry(-1);
  89 }
  90
  91 const char * Bus::BusFreeEvent::description()
  92 {
  93     return "bus became available";
  94 }
  95
  96 void Bus::occupyBus(PacketPtr pkt)
  97 {
  98     //Bring tickNextIdle up to the present tick
  99     //There is some potential ambiguity where a cycle starts, which might make
 100     //a difference when devices are acting right around a cycle boundary. Using
 101     //a < allows things which happen exactly on a cycle boundary to take up only
 102     //the following cycle. Anthing that happens later will have to "wait" for
 103     //the end of that cycle, and then start using the bus after that.
 104     while (tickNextIdle < curTick)
 105         tickNextIdle += clock;
 106
 107     // The packet will be sent. Figure out how long it occupies the bus, and
 108     // how much of that time is for the first "word", aka bus width.
 109     int numCycles = 0;
 110     // Requests need one cycle to send an address
 111     if (pkt->isRequest())
 112         numCycles++;
 113     else if (pkt->isResponse() || pkt->hasData()) {
 114         // If a packet has data, it needs ceil(size/width) cycles to send it
 115         // We're using the "adding instead of dividing" trick again here
 116         if (pkt->hasData()) {
 117             int dataSize = pkt->getSize();
 118             for (int transmitted = 0; transmitted < dataSize;
 119                     transmitted += width) {
 120                 numCycles++;
 121             }
 122         } else {
 123             // If the packet didn't have data, it must have been a response.
 124             // Those use the bus for one cycle to send their data.
 125             numCycles++;
 126         }
 127     }
 128
 129     // The first word will be delivered after the current tick, the delivery
 130     // of the address if any, and one bus cycle to deliver the data
 131     pkt->firstWordTime =
 132         tickNextIdle +
 133         pkt->isRequest() ? clock : 0 +
 134         clock;
 135
 136     //Advance it numCycles bus cycles.
 137     //XXX Should this use the repeated addition trick as well?
 138     tickNextIdle += (numCycles * clock);
 139     if (!busIdle.scheduled()) {
 140         busIdle.schedule(tickNextIdle);
 141     } else {
 142         busIdle.reschedule(tickNextIdle);
 143     }
 144     DPRINTF(Bus, "The bus is now occupied from tick %d to %d\n",
 145             curTick, tickNextIdle);
 146
 147     // The bus will become idle once the current packet is delivered.
 148     pkt->finishTime = tickNextIdle;
 149 }
 150
 151 /** Function called by the port when the bus is receiving a Timing
 152  * transaction.*/
 153 bool
 154 Bus::recvTiming(PacketPtr pkt)
 155 {
 156     Port *port;
 157     DPRINTF(Bus, "recvTiming: packet src %d dest %d addr 0x%x cmd %s\n",
 158             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 159
 160     BusPort *pktPort;
 161     if (pkt->getSrc() == defaultId)
 162         pktPort = defaultPort;
 163     else pktPort = interfaces[pkt->getSrc()];
 164
 165     // If the bus is busy, or other devices are in line ahead of the current
 166     // one, put this device on the retry list.
 167     if (tickNextIdle > curTick ||
 168             (retryList.size() && (!inRetry || pktPort != retryList.front()))) {
 169         addToRetryList(pktPort);
 170         return false;
 171     }
 172
 173     short dest = pkt->getDest();
 174     if (dest == Packet::Broadcast) {
 175         port = findPort(pkt->getAddr(), pkt->getSrc());
 176         if (timingSnoop(pkt, port ? port : interfaces[pkt->getSrc()])) {
 177             bool success;
 178
 179             pkt->flags |= SNOOP_COMMIT;
 180             success = timingSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 181             assert(success);
 182
 183             if (pkt->flags & SATISFIED) {
 184                 //Cache-Cache transfer occuring
 185                 if (inRetry) {
 186                     retryList.front()->onRetryList(false);
 187                     retryList.pop_front();
 188                     inRetry = false;
 189                 }
 190                 occupyBus(pkt);
 191                 return true;
 192             }
 193         } else {
 194             //Snoop didn't succeed
 195             DPRINTF(Bus, "Adding a retry to RETRY list %d\n",
 196                     pktPort->getId());
 197             addToRetryList(pktPort);
 198             return false;
 199         }
 200     } else {
 201         assert(dest >= 0 && dest < maxId);
 202         assert(dest != pkt->getSrc()); // catch infinite loops
 203         port = interfaces[dest];
 204     }
 205
 206     occupyBus(pkt);
 207
 208     if (port) {
 209         if (port->sendTiming(pkt))  {
 210             // Packet was successfully sent. Return true.
 211             // Also take care of retries
 212             if (inRetry) {
 213                 DPRINTF(Bus, "Remove retry from list %d\n",
 214                         retryList.front()->getId());
 215                 retryList.front()->onRetryList(false);
 216                 retryList.pop_front();
 217                 inRetry = false;
 218             }
 219             return true;
 220         }
 221
 222         // Packet not successfully sent. Leave or put it on the retry list.
 223         DPRINTF(Bus, "Adding a retry to RETRY list %d\n",
 224                 pktPort->getId());
 225         addToRetryList(pktPort);
 226         return false;
 227     }
 228     else {
 229         //Forwarding up from responder, just return true;
 230         return true;
 231     }
 232 }
 233
 234 void
 235 Bus::recvRetry(int id)
 236 {
 237     DPRINTF(Bus, "Received a retry\n");
 238     // If there's anything waiting, and the bus isn't busy...
 239     if (retryList.size() && curTick >= tickNextIdle) {
 240         //retryingPort = retryList.front();
 241         inRetry = true;
 242         DPRINTF(Bus, "Sending a retry\n");
 243         retryList.front()->sendRetry();
 244         // If inRetry is still true, sendTiming wasn't called
 245         if (inRetry)
 246         {
 247             retryList.front()->onRetryList(false);
 248             retryList.pop_front();
 249             inRetry = false;
 250
 251             //Bring tickNextIdle up to the present
 252             while (tickNextIdle < curTick)
 253                 tickNextIdle += clock;
 254
 255             //Burn a cycle for the missed grant.
 256             tickNextIdle += clock;
 257
 258             if (!busIdle.scheduled()) {
 259                 busIdle.schedule(tickNextIdle);
 260             } else {
 261                 busIdle.reschedule(tickNextIdle);
 262             }
 263         }
 264     }
 265     //If we weren't able to drain before, we might be able to now.
 266     if (drainEvent && retryList.size() == 0 && curTick >= tickNextIdle) {
 267         drainEvent->process();
 268         // Clear the drain event once we're done with it.
 269         drainEvent = NULL;
 270     }
 271 }
 272
 273 Port *
 274 Bus::findPort(Addr addr, int id)
 275 {
 276     /* An interval tree would be a better way to do this. --ali. */
 277     int dest_id = -1;
 278     AddrRangeIter iter;
 279     range_map<Addr,int>::iterator i;
 280
 281     i = portMap.find(RangeSize(addr,1));
 282     if (i != portMap.end())
 283         dest_id = i->second;
 284
 285     // Check if this matches the default range
 286     if (dest_id == -1) {
 287         for (iter = defaultRange.begin(); iter != defaultRange.end(); iter++) {
 288             if (*iter == addr) {
 289                 DPRINTF(Bus, "  found addr %#llx on default\n", addr);
 290                 return defaultPort;
 291             }
 292         }
 293
 294         if (responderSet) {
 295             panic("Unable to find destination for addr (user set default "
 296                   "responder): %#llx", addr);
 297         } else {
 298             DPRINTF(Bus, "Unable to find destination for addr: %#llx, will use "
 299                     "default port", addr);
 300
 301             return defaultPort;
 302         }
 303     }
 304
 305
 306     // we shouldn't be sending this back to where it came from
 307     // do the snoop access and then we should terminate
 308     // the cyclical call.
 309     if (dest_id == id)
 310         return 0;
 311
 312     return interfaces[dest_id];
 313 }
 314
 315 std::vector<int>
 316 Bus::findSnoopPorts(Addr addr, int id)
 317 {
 318     int i = 0;
 319     AddrRangeIter iter;
 320     std::vector<int> ports;
 321
 322     while (i < portSnoopList.size())
 323     {
 324         if (portSnoopList[i].range == addr && portSnoopList[i].portId != id) {
 325             //Careful  to not overlap ranges
 326             //or snoop will be called more than once on the port
 327
 328             //@todo Fix this hack because ranges are overlapping
 329             //need to make sure we dont't create overlapping ranges
 330             bool hack_overlap = false;
 331             int size = ports.size();
 332             for (int j=0; j < size; j++) {
 333                 if (ports[j] == portSnoopList[i].portId)
 334                     hack_overlap = true;
 335             }
 336
 337             if (!hack_overlap)
 338                 ports.push_back(portSnoopList[i].portId);
 339 //            DPRINTF(Bus, "  found snoop addr %#llx on device%d\n", addr,
 340 //                    portSnoopList[i].portId);
 341         }
 342         i++;
 343     }
 344     return ports;
 345 }
 346
 347 Tick
 348 Bus::atomicSnoop(PacketPtr pkt, Port *responder)
 349 {
 350     std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc());
 351     Tick response_time = 0;
 352
 353     while (!ports.empty())
 354     {
 355         if (interfaces[ports.back()] != responder) {
 356             Tick response = interfaces[ports.back()]->sendAtomic(pkt);
 357             if (response) {
 358                 assert(!response_time);  //Multiple responders
 359                 response_time = response;
 360             }
 361         }
 362         ports.pop_back();
 363     }
 364     return response_time;
 365 }
 366
 367 void
 368 Bus::functionalSnoop(PacketPtr pkt, Port *responder)
 369 {
 370     std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc());
 371
 372     //The packet may be changed by another bus on snoops, restore the id after each
 373     int id = pkt->getSrc();
 374     while (!ports.empty() && pkt->result != Packet::Success)
 375     {
 376         if (interfaces[ports.back()] != responder)
 377             interfaces[ports.back()]->sendFunctional(pkt);
 378         ports.pop_back();
 379         pkt->setSrc(id);
 380     }
 381 }
 382
 383 bool
 384 Bus::timingSnoop(PacketPtr pkt, Port* responder)
 385 {
 386     std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc());
 387     bool success = true;
 388
 389     while (!ports.empty() && success)
 390     {
 391         if (interfaces[ports.back()] != responder) //Don't call if responder also, once will do
 392             success = interfaces[ports.back()]->sendTiming(pkt);
 393         ports.pop_back();
 394     }
 395
 396     return success;
 397 }
 398
 399
 400 /** Function called by the port when the bus is receiving a Atomic
 401  * transaction.*/
 402 Tick
 403 Bus::recvAtomic(PacketPtr pkt)
 404 {
 405     DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n",
 406             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 407     assert(pkt->getDest() == Packet::Broadcast);
 408     pkt->flags |= SNOOP_COMMIT;
 409
 410     // Assume one bus cycle in order to get through.  This may have
 411     // some clock skew issues yet again...
 412     pkt->finishTime = curTick + clock;
 413
 414     Port *port = findPort(pkt->getAddr(), pkt->getSrc());
 415     Tick snoopTime = atomicSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 416
 417     if (snoopTime)
 418         return snoopTime;  //Snoop satisfies it
 419     else if (port)
 420         return port->sendAtomic(pkt);
 421     else
 422         return 0;
 423 }
 424
 425 /** Function called by the port when the bus is receiving a Functional
 426  * transaction.*/
 427 void
 428 Bus::recvFunctional(PacketPtr pkt)
 429 {
 430     DPRINTF(Bus, "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n",
 431             pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
 432     assert(pkt->getDest() == Packet::Broadcast);
 433     pkt->flags |= SNOOP_COMMIT;
 434
 435     Port* port = findPort(pkt->getAddr(), pkt->getSrc());
 436     functionalSnoop(pkt, port ? port : interfaces[pkt->getSrc()]);
 437
 438     // If the snooping found what we were looking for, we're done.
 439     if (pkt->result != Packet::Success && port) {
 440         port->sendFunctional(pkt);
 441     }
 442 }
 443
 444 /** Function called by the port when the bus is receiving a status change.*/
 445 void
 446 Bus::recvStatusChange(Port::Status status, int id)
 447 {
 448     AddrRangeList ranges;
 449     AddrRangeList snoops;
 450     AddrRangeIter iter;
 451
 452     assert(status == Port::RangeChange &&
 453            "The other statuses need to be implemented.");
 454
 455     DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id);
 456
 457     if (id == defaultId) {
 458         defaultRange.clear();
 459         // Only try to update these ranges if the user set a default responder.
 460         if (responderSet) {
 461             defaultPort->getPeerAddressRanges(ranges, snoops);
 462             assert(snoops.size() == 0);
 463             for(iter = ranges.begin(); iter != ranges.end(); iter++) {
 464                 defaultRange.push_back(*iter);
 465                 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n",
 466                         iter->start, iter->end);
 467             }
 468         }
 469     } else {
 470
 471         assert((id < maxId && id >= 0) || id == defaultId);
 472         Port *port = interfaces[id];
 473         range_map<Addr,int>::iterator portIter;
 474         std::vector<DevMap>::iterator snoopIter;
 475
 476         // Clean out any previously existent ids
 477         for (portIter = portMap.begin(); portIter != portMap.end(); ) {
 478             if (portIter->second == id)
 479                 portMap.erase(portIter++);
 480             else
 481                 portIter++;
 482         }
 483
 484         for (snoopIter = portSnoopList.begin(); snoopIter != portSnoopList.end(); ) {
 485             if (snoopIter->portId == id)
 486                 snoopIter = portSnoopList.erase(snoopIter);
 487             else
 488                 snoopIter++;
 489         }
 490
 491         port->getPeerAddressRanges(ranges, snoops);
 492
 493         for(iter = snoops.begin(); iter != snoops.end(); iter++) {
 494             DevMap dm;
 495             dm.portId = id;
 496             dm.range = *iter;
 497
 498             //@todo, make sure we don't overlap ranges
 499             DPRINTF(BusAddrRanges, "Adding snoop range %#llx - %#llx for id %d\n",
 500                     dm.range.start, dm.range.end, id);
 501             portSnoopList.push_back(dm);
 502         }
 503
 504         for(iter = ranges.begin(); iter != ranges.end(); iter++) {
 505             DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n",
 506                     iter->start, iter->end, id);
 507             if (portMap.insert(*iter, id) == portMap.end())
 508                 panic("Two devices with same range\n");
 509
 510         }
 511     }
 512     DPRINTF(MMU, "port list has %d entries\n", portMap.size());
 513
 514     // tell all our peers that our address range has changed.
 515     // Don't tell the device that caused this change, it already knows
 516     m5::hash_map<short,BusPort*>::iterator intIter;
 517
 518     for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
 519         if (intIter->first != id)
 520             intIter->second->sendStatusChange(Port::RangeChange);
 521
 522     if (id != defaultId && defaultPort)
 523         defaultPort->sendStatusChange(Port::RangeChange);
 524 }
 525
 526 void
 527 Bus::addressRanges(AddrRangeList &resp, AddrRangeList &snoop, int id)
 528 {
 529     std::vector<DevMap>::iterator snoopIter;
 530     range_map<Addr,int>::iterator portIter;
 531     AddrRangeIter dflt_iter;
 532     bool subset;
 533
 534     resp.clear();
 535     snoop.clear();
 536
 537     DPRINTF(BusAddrRanges, "received address range request, returning:\n");
 538
 539     for (dflt_iter = defaultRange.begin(); dflt_iter != defaultRange.end();
 540             dflt_iter++) {
 541         resp.push_back(*dflt_iter);
 542         DPRINTF(BusAddrRanges, "  -- Dflt: %#llx : %#llx\n",dflt_iter->start,
 543                 dflt_iter->end);
 544     }
 545     for (portIter = portMap.begin(); portIter != portMap.end(); portIter++) {
 546         subset = false;
 547         for (dflt_iter = defaultRange.begin(); dflt_iter != defaultRange.end();
 548                 dflt_iter++) {
 549             if ((portIter->first.start < dflt_iter->start &&
 550                 portIter->first.end >= dflt_iter->start) ||
 551                (portIter->first.start < dflt_iter->end &&
 552                 portIter->first.end >= dflt_iter->end))
 553                 fatal("Devices can not set ranges that itersect the default set\
 554                         but are not a subset of the default set.\n");
 555             if (portIter->first.start >= dflt_iter->start &&
 556                 portIter->first.end <= dflt_iter->end) {
 557                 subset = true;
 558                 DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
 559                     portIter->first.start, portIter->first.end);
 560             }
 561         }
 562         if (portIter->second != id && !subset) {
 563             resp.push_back(portIter->first);
 564             DPRINTF(BusAddrRanges, "  -- %#llx : %#llx\n",
 565                     portIter->first.start, portIter->first.end);
 566         }
 567     }
 568
 569     for (snoopIter = portSnoopList.begin();
 570          snoopIter != portSnoopList.end(); snoopIter++)
 571     {
 572         if (snoopIter->portId != id) {
 573             snoop.push_back(snoopIter->range);
 574             DPRINTF(BusAddrRanges, "  -- Snoop: %#llx : %#llx\n",
 575                     snoopIter->range.start, snoopIter->range.end);
 576             //@todo We need to properly insert snoop ranges
 577             //not overlapping the ranges (multiple)
 578         }
 579     }
 580 }
 581
 582 unsigned int
 583 Bus::drain(Event * de)
 584 {
 585     //We should check that we're not "doing" anything, and that noone is
 586     //waiting. We might be idle but have someone waiting if the device we
 587     //contacted for a retry didn't actually retry.
 588     if (curTick >= tickNextIdle && retryList.size() == 0) {
 589         return 0;
 590     } else {
 591         drainEvent = de;
 592         return 1;
 593     }
 594 }
 595
 596 BEGIN_DECLARE_SIM_OBJECT_PARAMS(Bus)
 597
 598     Param<int> bus_id;
 599     Param<int> clock;
 600     Param<int> width;
 601     Param<bool> responder_set;
 602
 603 END_DECLARE_SIM_OBJECT_PARAMS(Bus)
 604
 605 BEGIN_INIT_SIM_OBJECT_PARAMS(Bus)
 606     INIT_PARAM(bus_id, "a globally unique bus id"),
 607     INIT_PARAM(clock, "bus clock speed"),
 608     INIT_PARAM(width, "width of the bus (bits)"),
 609     INIT_PARAM(responder_set, "Is a default responder set by the user")
 610 END_INIT_SIM_OBJECT_PARAMS(Bus)
 611
 612 CREATE_SIM_OBJECT(Bus)
 613 {
 614     return new Bus(getInstanceName(), bus_id, clock, width, responder_set);
 615 }
 616
 617 REGISTER_SIM_OBJECT("Bus", Bus)