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