coherent_xbar.cc revision 8663
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 "debug/Bus.hh" 42#include "debug/BusAddrRanges.hh" 43#include "debug/MMU.hh" 44#include "mem/bus.hh" 45 46Bus::Bus(const BusParams *p) 47 : MemObject(p), busId(p->bus_id), clock(p->clock), 48 headerCycles(p->header_cycles), width(p->width), tickNextIdle(0), 49 drainEvent(NULL), busIdle(this), inRetry(false), maxId(0), 50 defaultPort(NULL), funcPort(NULL), funcPortId(-4), 51 useDefaultRange(p->use_default_range), defaultBlockSize(p->block_size), 52 cachedBlockSize(0), cachedBlockSizeValid(false) 53{ 54 //width, clock period, and header cycles must be positive 55 if (width <= 0) 56 fatal("Bus width must be positive\n"); 57 if (clock <= 0) 58 fatal("Bus clock period must be positive\n"); 59 if (headerCycles <= 0) 60 fatal("Number of header cycles must be positive\n"); 61 clearBusCache(); 62 clearPortCache(); 63} 64 65Port * 66Bus::getPort(const std::string &if_name, int idx) 67{ 68 if (if_name == "default") { 69 if (defaultPort == NULL) { 70 defaultPort = new BusPort(csprintf("%s-default",name()), this, 71 defaultId); 72 cachedBlockSizeValid = false; 73 return defaultPort; 74 } else 75 fatal("Default port already set\n"); 76 } 77 int id; 78 if (if_name == "functional") { 79 if (!funcPort) { 80 id = maxId++; 81 funcPort = new BusPort(csprintf("%s-p%d-func", name(), id), this, id); 82 funcPortId = id; 83 interfaces[id] = funcPort; 84 } 85 return funcPort; 86 } 87 88 // if_name ignored? forced to be empty? 89 id = maxId++; 90 assert(maxId < std::numeric_limits<typeof(maxId)>::max()); 91 BusPort *bp = new BusPort(csprintf("%s-p%d", name(), id), this, id); 92 interfaces[id] = bp; 93 cachedBlockSizeValid = false; 94 return bp; 95} 96 97void 98Bus::deletePortRefs(Port *p) 99{ 100 101 BusPort *bp = dynamic_cast<BusPort*>(p); 102 if (bp == NULL) 103 panic("Couldn't convert Port* to BusPort*\n"); 104 // If this is our one functional port 105 if (funcPort == bp) 106 return; 107 interfaces.erase(bp->getId()); 108 clearBusCache(); 109 delete bp; 110} 111 112/** Get the ranges of anyone other buses that we are connected to. */ 113void 114Bus::init() 115{ 116 m5::hash_map<short,BusPort*>::iterator intIter; 117 118 for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++) 119 intIter->second->sendStatusChange(Port::RangeChange); 120} 121 122Bus::BusFreeEvent::BusFreeEvent(Bus *_bus) 123 : bus(_bus) 124{} 125 126void 127Bus::BusFreeEvent::process() 128{ 129 bus->recvRetry(-1); 130} 131 132const char * 133Bus::BusFreeEvent::description() const 134{ 135 return "bus became available"; 136} 137 138Tick 139Bus::calcPacketTiming(PacketPtr pkt) 140{ 141 // Bring tickNextIdle up to the present tick. 142 // There is some potential ambiguity where a cycle starts, which 143 // might make a difference when devices are acting right around a 144 // cycle boundary. Using a < allows things which happen exactly on 145 // a cycle boundary to take up only the following cycle. Anything 146 // that happens later will have to "wait" for the end of that 147 // cycle, and then start using the bus after that. 148 if (tickNextIdle < curTick()) { 149 tickNextIdle = curTick(); 150 if (tickNextIdle % clock != 0) 151 tickNextIdle = curTick() - (curTick() % clock) + clock; 152 } 153 154 Tick headerTime = tickNextIdle + headerCycles * clock; 155 156 // The packet will be sent. Figure out how long it occupies the bus, and 157 // how much of that time is for the first "word", aka bus width. 158 int numCycles = 0; 159 if (pkt->hasData()) { 160 // If a packet has data, it needs ceil(size/width) cycles to send it 161 int dataSize = pkt->getSize(); 162 numCycles += dataSize/width; 163 if (dataSize % width) 164 numCycles++; 165 } 166 167 // The first word will be delivered after the current tick, the delivery 168 // of the address if any, and one bus cycle to deliver the data 169 pkt->firstWordTime = headerTime + clock; 170 171 pkt->finishTime = headerTime + numCycles * clock; 172 173 return headerTime; 174} 175 176void Bus::occupyBus(Tick until) 177{ 178 if (until == 0) { 179 // shortcut for express snoop packets 180 return; 181 } 182 183 tickNextIdle = until; 184 reschedule(busIdle, tickNextIdle, true); 185 186 DPRINTF(Bus, "The bus is now occupied from tick %d to %d\n", 187 curTick(), tickNextIdle); 188} 189 190/** Function called by the port when the bus is receiving a Timing 191 * transaction.*/ 192bool 193Bus::recvTiming(PacketPtr pkt) 194{ 195 short src = pkt->getSrc(); 196 197 BusPort *src_port; 198 if (src == defaultId) 199 src_port = defaultPort; 200 else { 201 src_port = checkBusCache(src); 202 if (src_port == NULL) { 203 src_port = interfaces[src]; 204 updateBusCache(src, src_port); 205 } 206 } 207 208 // If the bus is busy, or other devices are in line ahead of the current 209 // one, put this device on the retry list. 210 if (!pkt->isExpressSnoop() && 211 (tickNextIdle > curTick() || 212 (retryList.size() && (!inRetry || src_port != retryList.front())))) 213 { 214 addToRetryList(src_port); 215 DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x BUSY\n", 216 src, pkt->getDest(), pkt->cmdString(), pkt->getAddr()); 217 return false; 218 } 219 220 DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x\n", 221 src, pkt->getDest(), pkt->cmdString(), pkt->getAddr()); 222 223 Tick headerFinishTime = pkt->isExpressSnoop() ? 0 : calcPacketTiming(pkt); 224 Tick packetFinishTime = pkt->isExpressSnoop() ? 0 : pkt->finishTime; 225 226 short dest = pkt->getDest(); 227 int dest_port_id; 228 Port *dest_port; 229 230 if (dest == Packet::Broadcast) { 231 dest_port_id = findPort(pkt->getAddr()); 232 dest_port = (dest_port_id == defaultId) ? 233 defaultPort : interfaces[dest_port_id]; 234 SnoopIter s_end = snoopPorts.end(); 235 for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) { 236 BusPort *p = *s_iter; 237 if (p != dest_port && p != src_port) { 238 // cache is not allowed to refuse snoop 239 bool success M5_VAR_USED = p->sendTiming(pkt); 240 assert(success); 241 } 242 } 243 } else { 244 assert(dest < maxId); 245 assert(dest != src); // catch infinite loops 246 dest_port_id = dest; 247 if (dest_port_id == defaultId) 248 dest_port = defaultPort; 249 else { 250 dest_port = checkBusCache(dest); 251 if (dest_port == NULL) { 252 dest_port = interfaces[dest_port_id]; 253 // updateBusCache(dest_port_id, dest_port); 254 } 255 } 256 dest_port = (dest_port_id == defaultId) ? 257 defaultPort : interfaces[dest_port_id]; 258 } 259 260 if (dest_port_id == src) { 261 // Must be forwarded snoop up from below... 262 assert(dest == Packet::Broadcast); 263 } else { 264 // send to actual target 265 if (!dest_port->sendTiming(pkt)) { 266 // Packet not successfully sent. Leave or put it on the retry list. 267 // illegal to block responses... can lead to deadlock 268 assert(!pkt->isResponse()); 269 // It's also illegal to force a transaction to retry after 270 // someone else has committed to respond. 271 assert(!pkt->memInhibitAsserted()); 272 DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x TGT RETRY\n", 273 src, pkt->getDest(), pkt->cmdString(), pkt->getAddr()); 274 addToRetryList(src_port); 275 occupyBus(headerFinishTime); 276 return false; 277 } 278 // send OK, fall through... pkt may have been deleted by 279 // target at this point, so it should *not* be referenced 280 // again. We'll set it to NULL here just to be safe. 281 pkt = NULL; 282 } 283 284 occupyBus(packetFinishTime); 285 286 // Packet was successfully sent. 287 // Also take care of retries 288 if (inRetry) { 289 DPRINTF(Bus, "Remove retry from list %d\n", src); 290 retryList.front()->onRetryList(false); 291 retryList.pop_front(); 292 inRetry = false; 293 } 294 return true; 295} 296 297void 298Bus::recvRetry(int id) 299{ 300 // If there's anything waiting, and the bus isn't busy... 301 if (retryList.size() && curTick() >= tickNextIdle) { 302 //retryingPort = retryList.front(); 303 inRetry = true; 304 DPRINTF(Bus, "Sending a retry to %s\n", retryList.front()->getPeer()->name()); 305 retryList.front()->sendRetry(); 306 // If inRetry is still true, sendTiming wasn't called 307 if (inRetry) 308 { 309 retryList.front()->onRetryList(false); 310 retryList.pop_front(); 311 inRetry = false; 312 313 //Bring tickNextIdle up to the present 314 while (tickNextIdle < curTick()) 315 tickNextIdle += clock; 316 317 //Burn a cycle for the missed grant. 318 tickNextIdle += clock; 319 320 reschedule(busIdle, tickNextIdle, true); 321 } 322 } 323 //If we weren't able to drain before, we might be able to now. 324 if (drainEvent && retryList.size() == 0 && curTick() >= tickNextIdle) { 325 drainEvent->process(); 326 // Clear the drain event once we're done with it. 327 drainEvent = NULL; 328 } 329} 330 331int 332Bus::findPort(Addr addr) 333{ 334 /* An interval tree would be a better way to do this. --ali. */ 335 int dest_id; 336 337 dest_id = checkPortCache(addr); 338 if (dest_id != -1) 339 return dest_id; 340 341 // Check normal port ranges 342 PortIter i = portMap.find(RangeSize(addr,1)); 343 if (i != portMap.end()) { 344 dest_id = i->second; 345 updatePortCache(dest_id, i->first.start, i->first.end); 346 return dest_id; 347 } 348 349 // Check if this matches the default range 350 if (useDefaultRange) { 351 AddrRangeIter a_end = defaultRange.end(); 352 for (AddrRangeIter i = defaultRange.begin(); i != a_end; i++) { 353 if (*i == addr) { 354 DPRINTF(Bus, " found addr %#llx on default\n", addr); 355 return defaultId; 356 } 357 } 358 359 panic("Unable to find destination for addr %#llx\n", addr); 360 } 361 362 DPRINTF(Bus, "Unable to find destination for addr %#llx, " 363 "will use default port\n", addr); 364 return defaultId; 365} 366 367 368/** Function called by the port when the bus is receiving a Atomic 369 * transaction.*/ 370Tick 371Bus::recvAtomic(PacketPtr pkt) 372{ 373 DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n", 374 pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString()); 375 assert(pkt->getDest() == Packet::Broadcast); 376 assert(pkt->isRequest()); 377 378 // Variables for recording original command and snoop response (if 379 // any)... if a snooper respondes, we will need to restore 380 // original command so that additional snoops can take place 381 // properly 382 MemCmd orig_cmd = pkt->cmd; 383 MemCmd snoop_response_cmd = MemCmd::InvalidCmd; 384 Tick snoop_response_latency = 0; 385 int orig_src = pkt->getSrc(); 386 387 int target_port_id = findPort(pkt->getAddr()); 388 BusPort *target_port; 389 if (target_port_id == defaultId) 390 target_port = defaultPort; 391 else { 392 target_port = checkBusCache(target_port_id); 393 if (target_port == NULL) { 394 target_port = interfaces[target_port_id]; 395 updateBusCache(target_port_id, target_port); 396 } 397 } 398 399 SnoopIter s_end = snoopPorts.end(); 400 for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) { 401 BusPort *p = *s_iter; 402 // same port should not have both target addresses and snooping 403 assert(p != target_port); 404 if (p->getId() != pkt->getSrc()) { 405 Tick latency = p->sendAtomic(pkt); 406 if (pkt->isResponse()) { 407 // response from snoop agent 408 assert(pkt->cmd != orig_cmd); 409 assert(pkt->memInhibitAsserted()); 410 // should only happen once 411 assert(snoop_response_cmd == MemCmd::InvalidCmd); 412 // save response state 413 snoop_response_cmd = pkt->cmd; 414 snoop_response_latency = latency; 415 // restore original packet state for remaining snoopers 416 pkt->cmd = orig_cmd; 417 pkt->setSrc(orig_src); 418 pkt->setDest(Packet::Broadcast); 419 } 420 } 421 } 422 423 Tick response_latency = 0; 424 425 // we can get requests sent up from the memory side of the bus for 426 // snooping... don't send them back down! 427 if (target_port_id != pkt->getSrc()) { 428 response_latency = target_port->sendAtomic(pkt); 429 } 430 431 // if we got a response from a snooper, restore it here 432 if (snoop_response_cmd != MemCmd::InvalidCmd) { 433 // no one else should have responded 434 assert(!pkt->isResponse()); 435 assert(pkt->cmd == orig_cmd); 436 pkt->cmd = snoop_response_cmd; 437 response_latency = snoop_response_latency; 438 } 439 440 // why do we have this packet field and the return value both??? 441 pkt->finishTime = curTick() + response_latency; 442 return response_latency; 443} 444 445/** Function called by the port when the bus is receiving a Functional 446 * transaction.*/ 447void 448Bus::recvFunctional(PacketPtr pkt) 449{ 450 assert(pkt->getDest() == Packet::Broadcast); 451 452 int port_id = findPort(pkt->getAddr()); 453 Port *port = (port_id == defaultId) ? defaultPort : interfaces[port_id]; 454 // The packet may be changed by another bus on snoops, restore the 455 // id after each 456 int src_id = pkt->getSrc(); 457 458 if (!pkt->isPrint()) { 459 // don't do DPRINTFs on PrintReq as it clutters up the output 460 DPRINTF(Bus, 461 "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n", 462 src_id, port_id, pkt->getAddr(), 463 pkt->cmdString()); 464 } 465 466 assert(pkt->isRequest()); // hasn't already been satisfied 467 468 SnoopIter s_end = snoopPorts.end(); 469 for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) { 470 BusPort *p = *s_iter; 471 if (p != port && p->getId() != src_id) { 472 p->sendFunctional(pkt); 473 } 474 if (pkt->isResponse()) { 475 break; 476 } 477 pkt->setSrc(src_id); 478 } 479 480 // If the snooping hasn't found what we were looking for, keep going. 481 if (!pkt->isResponse() && port_id != pkt->getSrc()) { 482 port->sendFunctional(pkt); 483 } 484} 485 486/** Function called by the port when the bus is receiving a status change.*/ 487void 488Bus::recvStatusChange(Port::Status status, int id) 489{ 490 AddrRangeList ranges; 491 bool snoops; 492 AddrRangeIter iter; 493 494 if (inRecvStatusChange.count(id)) 495 return; 496 inRecvStatusChange.insert(id); 497 498 assert(status == Port::RangeChange && 499 "The other statuses need to be implemented."); 500 501 DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id); 502 503 clearPortCache(); 504 if (id == defaultId) { 505 defaultRange.clear(); 506 // Only try to update these ranges if the user set a default responder. 507 if (useDefaultRange) { 508 defaultPort->getPeerAddressRanges(ranges, snoops); 509 assert(snoops == false); 510 for(iter = ranges.begin(); iter != ranges.end(); iter++) { 511 defaultRange.push_back(*iter); 512 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n", 513 iter->start, iter->end); 514 } 515 } 516 } else { 517 518 assert((id < maxId && id >= 0) || id == defaultId); 519 BusPort *port = interfaces[id]; 520 521 // Clean out any previously existent ids 522 for (PortIter portIter = portMap.begin(); 523 portIter != portMap.end(); ) { 524 if (portIter->second == id) 525 portMap.erase(portIter++); 526 else 527 portIter++; 528 } 529 530 for (SnoopIter s_iter = snoopPorts.begin(); 531 s_iter != snoopPorts.end(); ) { 532 if ((*s_iter)->getId() == id) 533 s_iter = snoopPorts.erase(s_iter); 534 else 535 s_iter++; 536 } 537 538 port->getPeerAddressRanges(ranges, snoops); 539 540 if (snoops) { 541 DPRINTF(BusAddrRanges, "Adding id %d to snoop list\n", id); 542 snoopPorts.push_back(port); 543 } 544 545 for (iter = ranges.begin(); iter != ranges.end(); iter++) { 546 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n", 547 iter->start, iter->end, id); 548 if (portMap.insert(*iter, id) == portMap.end()) { 549 int conflict_id = portMap.find(*iter)->second; 550 fatal("%s has two ports with same range:\n\t%s\n\t%s\n", 551 name(), interfaces[id]->getPeer()->name(), 552 interfaces[conflict_id]->getPeer()->name()); 553 } 554 } 555 } 556 DPRINTF(MMU, "port list has %d entries\n", portMap.size()); 557 558 // tell all our peers that our address range has changed. 559 // Don't tell the device that caused this change, it already knows 560 m5::hash_map<short,BusPort*>::iterator intIter; 561 562 for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++) 563 if (intIter->first != id && intIter->first != funcPortId) 564 intIter->second->sendStatusChange(Port::RangeChange); 565 566 if (id != defaultId && defaultPort) 567 defaultPort->sendStatusChange(Port::RangeChange); 568 inRecvStatusChange.erase(id); 569} 570 571void 572Bus::addressRanges(AddrRangeList &resp, bool &snoop, int id) 573{ 574 resp.clear(); 575 snoop = false; 576 577 DPRINTF(BusAddrRanges, "received address range request, returning:\n"); 578 579 for (AddrRangeIter dflt_iter = defaultRange.begin(); 580 dflt_iter != defaultRange.end(); dflt_iter++) { 581 resp.push_back(*dflt_iter); 582 DPRINTF(BusAddrRanges, " -- Dflt: %#llx : %#llx\n",dflt_iter->start, 583 dflt_iter->end); 584 } 585 for (PortIter portIter = portMap.begin(); 586 portIter != portMap.end(); portIter++) { 587 bool subset = false; 588 for (AddrRangeIter dflt_iter = defaultRange.begin(); 589 dflt_iter != defaultRange.end(); dflt_iter++) { 590 if ((portIter->first.start < dflt_iter->start && 591 portIter->first.end >= dflt_iter->start) || 592 (portIter->first.start < dflt_iter->end && 593 portIter->first.end >= dflt_iter->end)) 594 fatal("Devices can not set ranges that itersect the default set\ 595 but are not a subset of the default set.\n"); 596 if (portIter->first.start >= dflt_iter->start && 597 portIter->first.end <= dflt_iter->end) { 598 subset = true; 599 DPRINTF(BusAddrRanges, " -- %#llx : %#llx is a SUBSET\n", 600 portIter->first.start, portIter->first.end); 601 } 602 } 603 if (portIter->second != id && !subset) { 604 resp.push_back(portIter->first); 605 DPRINTF(BusAddrRanges, " -- %#llx : %#llx\n", 606 portIter->first.start, portIter->first.end); 607 } 608 } 609 610 for (SnoopIter s_iter = snoopPorts.begin(); s_iter != snoopPorts.end(); 611 s_iter++) { 612 if ((*s_iter)->getId() != id) { 613 snoop = true; 614 break; 615 } 616 } 617} 618 619unsigned 620Bus::findBlockSize(int id) 621{ 622 if (cachedBlockSizeValid) 623 return cachedBlockSize; 624 625 unsigned max_bs = 0; 626 627 PortIter p_end = portMap.end(); 628 for (PortIter p_iter = portMap.begin(); p_iter != p_end; p_iter++) { 629 unsigned tmp_bs = interfaces[p_iter->second]->peerBlockSize(); 630 if (tmp_bs > max_bs) 631 max_bs = tmp_bs; 632 } 633 SnoopIter s_end = snoopPorts.end(); 634 for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) { 635 unsigned tmp_bs = (*s_iter)->peerBlockSize(); 636 if (tmp_bs > max_bs) 637 max_bs = tmp_bs; 638 } 639 if (max_bs == 0) 640 max_bs = defaultBlockSize; 641 642 if (max_bs != 64) 643 warn_once("Blocksize found to not be 64... hmm... probably not.\n"); 644 cachedBlockSize = max_bs; 645 cachedBlockSizeValid = true; 646 return max_bs; 647} 648 649 650unsigned int 651Bus::drain(Event * de) 652{ 653 //We should check that we're not "doing" anything, and that noone is 654 //waiting. We might be idle but have someone waiting if the device we 655 //contacted for a retry didn't actually retry. 656 if (retryList.size() || (curTick() < tickNextIdle && busIdle.scheduled())) { 657 drainEvent = de; 658 return 1; 659 } 660 return 0; 661} 662 663void 664Bus::startup() 665{ 666 if (tickNextIdle < curTick()) 667 tickNextIdle = (curTick() / clock) * clock + clock; 668} 669 670Bus * 671BusParams::create() 672{ 673 return new Bus(this); 674} 675