xbar.cc revision 3470
15081Sgblack@eecs.umich.edu/* 25081Sgblack@eecs.umich.edu * Copyright (c) 2006 The Regents of The University of Michigan 35081Sgblack@eecs.umich.edu * All rights reserved. 47087Snate@binkert.org * 57087Snate@binkert.org * Redistribution and use in source and binary forms, with or without 67087Snate@binkert.org * modification, are permitted provided that the following conditions are 77087Snate@binkert.org * met: redistributions of source code must retain the above copyright 87087Snate@binkert.org * notice, this list of conditions and the following disclaimer; 97087Snate@binkert.org * redistributions in binary form must reproduce the above copyright 107087Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 117087Snate@binkert.org * documentation and/or other materials provided with the distribution; 125081Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 137087Snate@binkert.org * contributors may be used to endorse or promote products derived from 147087Snate@binkert.org * this software without specific prior written permission. 157087Snate@binkert.org * 167087Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 177087Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 187087Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 197087Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 207087Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215081Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 227087Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235081Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245081Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255081Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265081Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275081Sgblack@eecs.umich.edu * 285081Sgblack@eecs.umich.edu * Authors: Ali Saidi 295081Sgblack@eecs.umich.edu */ 305081Sgblack@eecs.umich.edu 315081Sgblack@eecs.umich.edu/** 325081Sgblack@eecs.umich.edu * @file 335081Sgblack@eecs.umich.edu * Definition of a bus object. 345081Sgblack@eecs.umich.edu */ 355081Sgblack@eecs.umich.edu 365081Sgblack@eecs.umich.edu 375081Sgblack@eecs.umich.edu#include "base/misc.hh" 385081Sgblack@eecs.umich.edu#include "base/trace.hh" 395081Sgblack@eecs.umich.edu#include "mem/bus.hh" 406705Svince@csl.cornell.edu#include "sim/builder.hh" 416705Svince@csl.cornell.edu 426799Sgblack@eecs.umich.eduPort * 436799Sgblack@eecs.umich.eduBus::getPort(const std::string &if_name, int idx) 446705Svince@csl.cornell.edu{ 456705Svince@csl.cornell.edu if (if_name == "default") 466705Svince@csl.cornell.edu if (defaultPort == NULL) { 476705Svince@csl.cornell.edu defaultPort = new BusPort(csprintf("%s-default",name()), this, 486705Svince@csl.cornell.edu defaultId); 496705Svince@csl.cornell.edu return defaultPort; 506799Sgblack@eecs.umich.edu } else 516799Sgblack@eecs.umich.edu fatal("Default port already set\n"); 526705Svince@csl.cornell.edu 536705Svince@csl.cornell.edu // if_name ignored? forced to be empty? 546705Svince@csl.cornell.edu int id = interfaces.size(); 556705Svince@csl.cornell.edu BusPort *bp = new BusPort(csprintf("%s-p%d", name(), id), this, id); 566705Svince@csl.cornell.edu interfaces.push_back(bp); 576705Svince@csl.cornell.edu return bp; 586799Sgblack@eecs.umich.edu} 596799Sgblack@eecs.umich.edu 606705Svince@csl.cornell.edu/** Get the ranges of anyone other buses that we are connected to. */ 615081Sgblack@eecs.umich.eduvoid 62Bus::init() 63{ 64 std::vector<BusPort*>::iterator intIter; 65 66 for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++) 67 (*intIter)->sendStatusChange(Port::RangeChange); 68} 69 70Bus::BusFreeEvent::BusFreeEvent(Bus *_bus) : Event(&mainEventQueue), bus(_bus) 71{} 72 73void Bus::BusFreeEvent::process() 74{ 75 bus->recvRetry(-1); 76} 77 78const char * Bus::BusFreeEvent::description() 79{ 80 return "bus became available"; 81} 82 83void Bus::occupyBus(PacketPtr pkt) 84{ 85 //Bring tickNextIdle up to the present tick 86 //There is some potential ambiguity where a cycle starts, which might make 87 //a difference when devices are acting right around a cycle boundary. Using 88 //a < allows things which happen exactly on a cycle boundary to take up only 89 //the following cycle. Anthing that happens later will have to "wait" for 90 //the end of that cycle, and then start using the bus after that. 91 while (tickNextIdle < curTick) 92 tickNextIdle += clock; 93 94 // The packet will be sent. Figure out how long it occupies the bus, and 95 // how much of that time is for the first "word", aka bus width. 96 int numCycles = 0; 97 // Requests need one cycle to send an address 98 if (pkt->isRequest()) 99 numCycles++; 100 else if (pkt->isResponse() || pkt->hasData()) { 101 // If a packet has data, it needs ceil(size/width) cycles to send it 102 // We're using the "adding instead of dividing" trick again here 103 if (pkt->hasData()) { 104 int dataSize = pkt->getSize(); 105 for (int transmitted = 0; transmitted < dataSize; 106 transmitted += width) { 107 numCycles++; 108 } 109 } else { 110 // If the packet didn't have data, it must have been a response. 111 // Those use the bus for one cycle to send their data. 112 numCycles++; 113 } 114 } 115 116 // The first word will be delivered after the current tick, the delivery 117 // of the address if any, and one bus cycle to deliver the data 118 pkt->firstWordTime = 119 tickNextIdle + 120 pkt->isRequest() ? clock : 0 + 121 clock; 122 123 //Advance it numCycles bus cycles. 124 //XXX Should this use the repeated addition trick as well? 125 tickNextIdle += (numCycles * clock); 126 if (!busIdle.scheduled()) { 127 busIdle.schedule(tickNextIdle); 128 } else { 129 busIdle.reschedule(tickNextIdle); 130 } 131 DPRINTF(Bus, "The bus is now occupied from tick %d to %d\n", 132 curTick, tickNextIdle); 133 134 // The bus will become idle once the current packet is delivered. 135 pkt->finishTime = tickNextIdle; 136} 137 138/** Function called by the port when the bus is receiving a Timing 139 * transaction.*/ 140bool 141Bus::recvTiming(PacketPtr pkt) 142{ 143 Port *port; 144 DPRINTF(Bus, "recvTiming: packet src %d dest %d addr 0x%x cmd %s\n", 145 pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString()); 146 147 BusPort *pktPort; 148 if (pkt->getSrc() == defaultId) 149 pktPort = defaultPort; 150 else pktPort = interfaces[pkt->getSrc()]; 151 152 // If the bus is busy, or other devices are in line ahead of the current 153 // one, put this device on the retry list. 154 if (tickNextIdle > curTick || 155 (retryList.size() && (!inRetry || pktPort != retryList.front()))) { 156 addToRetryList(pktPort); 157 return false; 158 } 159 160 short dest = pkt->getDest(); 161 if (dest == Packet::Broadcast) { 162 if (timingSnoop(pkt)) { 163 bool success; 164 165 pkt->flags |= SNOOP_COMMIT; 166 success = timingSnoop(pkt); 167 assert(success); 168 169 if (pkt->flags & SATISFIED) { 170 //Cache-Cache transfer occuring 171 if (inRetry) { 172 retryList.front()->onRetryList(false); 173 retryList.pop_front(); 174 inRetry = false; 175 } 176 occupyBus(pkt); 177 return true; 178 } 179 port = findPort(pkt->getAddr(), pkt->getSrc()); 180 } else { 181 //Snoop didn't succeed 182 DPRINTF(Bus, "Adding a retry to RETRY list %i\n", pktPort); 183 addToRetryList(pktPort); 184 return false; 185 } 186 } else { 187 assert(dest >= 0 && dest < interfaces.size()); 188 assert(dest != pkt->getSrc()); // catch infinite loops 189 port = interfaces[dest]; 190 } 191 192 occupyBus(pkt); 193 194 if (port->sendTiming(pkt)) { 195 // Packet was successfully sent. Return true. 196 // Also take care of retries 197 if (inRetry) { 198 DPRINTF(Bus, "Remove retry from list %i\n", retryList.front()); 199 retryList.front()->onRetryList(false); 200 retryList.pop_front(); 201 inRetry = false; 202 } 203 return true; 204 } 205 206 // Packet not successfully sent. Leave or put it on the retry list. 207 DPRINTF(Bus, "Adding a retry to RETRY list %i\n", pktPort); 208 addToRetryList(pktPort); 209 return false; 210} 211 212void 213Bus::recvRetry(int id) 214{ 215 DPRINTF(Bus, "Received a retry\n"); 216 // If there's anything waiting, and the bus isn't busy... 217 if (retryList.size() && curTick >= tickNextIdle) { 218 //retryingPort = retryList.front(); 219 inRetry = true; 220 DPRINTF(Bus, "Sending a retry\n"); 221 retryList.front()->sendRetry(); 222 // If inRetry is still true, sendTiming wasn't called 223 if (inRetry) 224 { 225 retryList.front()->onRetryList(false); 226 retryList.pop_front(); 227 inRetry = false; 228 229 //Bring tickNextIdle up to the present 230 while (tickNextIdle < curTick) 231 tickNextIdle += clock; 232 233 //Burn a cycle for the missed grant. 234 tickNextIdle += clock; 235 236 if (!busIdle.scheduled()) { 237 busIdle.schedule(tickNextIdle); 238 } else { 239 busIdle.reschedule(tickNextIdle); 240 } 241 } 242 //If we weren't able to drain before, we might be able to now. 243 if (drainEvent && retryList.size() == 0 && curTick >= tickNextIdle) 244 drainEvent->process(); 245 } 246} 247 248Port * 249Bus::findPort(Addr addr, int id) 250{ 251 /* An interval tree would be a better way to do this. --ali. */ 252 int dest_id = -1; 253 int i = 0; 254 bool found = false; 255 AddrRangeIter iter; 256 257 while (i < portList.size() && !found) 258 { 259 if (portList[i].range == addr) { 260 dest_id = portList[i].portId; 261 found = true; 262 DPRINTF(Bus, " found addr %#llx on device %d\n", addr, dest_id); 263 } 264 i++; 265 } 266 267 // Check if this matches the default range 268 if (dest_id == -1) { 269 for (iter = defaultRange.begin(); iter != defaultRange.end(); iter++) { 270 if (*iter == addr) { 271 DPRINTF(Bus, " found addr %#llx on default\n", addr); 272 return defaultPort; 273 } 274 } 275 panic("Unable to find destination for addr: %#llx", addr); 276 } 277 278 279 // we shouldn't be sending this back to where it came from 280 assert(dest_id != id); 281 282 return interfaces[dest_id]; 283} 284 285std::vector<int> 286Bus::findSnoopPorts(Addr addr, int id) 287{ 288 int i = 0; 289 AddrRangeIter iter; 290 std::vector<int> ports; 291 292 while (i < portSnoopList.size()) 293 { 294 if (portSnoopList[i].range == addr && portSnoopList[i].portId != id) { 295 //Careful to not overlap ranges 296 //or snoop will be called more than once on the port 297 ports.push_back(portSnoopList[i].portId); 298// DPRINTF(Bus, " found snoop addr %#llx on device%d\n", addr, 299// portSnoopList[i].portId); 300 } 301 i++; 302 } 303 return ports; 304} 305 306Tick 307Bus::atomicSnoop(PacketPtr pkt) 308{ 309 std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc()); 310 Tick response_time = 0; 311 312 while (!ports.empty()) 313 { 314 Tick response = interfaces[ports.back()]->sendAtomic(pkt); 315 if (response) { 316 assert(!response_time); //Multiple responders 317 response_time = response; 318 } 319 ports.pop_back(); 320 } 321 return response_time; 322} 323 324void 325Bus::functionalSnoop(PacketPtr pkt) 326{ 327 std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc()); 328 329 while (!ports.empty() && pkt->result != Packet::Success) 330 { 331 interfaces[ports.back()]->sendFunctional(pkt); 332 ports.pop_back(); 333 } 334} 335 336bool 337Bus::timingSnoop(PacketPtr pkt) 338{ 339 std::vector<int> ports = findSnoopPorts(pkt->getAddr(), pkt->getSrc()); 340 bool success = true; 341 342 while (!ports.empty() && success) 343 { 344 success = interfaces[ports.back()]->sendTiming(pkt); 345 ports.pop_back(); 346 } 347 348 return success; 349} 350 351 352/** Function called by the port when the bus is receiving a Atomic 353 * transaction.*/ 354Tick 355Bus::recvAtomic(PacketPtr pkt) 356{ 357 DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n", 358 pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString()); 359 assert(pkt->getDest() == Packet::Broadcast); 360 Tick snoopTime = atomicSnoop(pkt); 361 if (snoopTime) 362 return snoopTime; //Snoop satisfies it 363 else 364 return findPort(pkt->getAddr(), pkt->getSrc())->sendAtomic(pkt); 365} 366 367/** Function called by the port when the bus is receiving a Functional 368 * transaction.*/ 369void 370Bus::recvFunctional(PacketPtr pkt) 371{ 372 DPRINTF(Bus, "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n", 373 pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString()); 374 assert(pkt->getDest() == Packet::Broadcast); 375 functionalSnoop(pkt); 376 377 // If the snooping found what we were looking for, we're done. 378 if (pkt->result != Packet::Success) 379 findPort(pkt->getAddr(), pkt->getSrc())->sendFunctional(pkt); 380} 381 382/** Function called by the port when the bus is receiving a status change.*/ 383void 384Bus::recvStatusChange(Port::Status status, int id) 385{ 386 AddrRangeList ranges; 387 AddrRangeList snoops; 388 int x; 389 AddrRangeIter iter; 390 391 assert(status == Port::RangeChange && 392 "The other statuses need to be implemented."); 393 394 DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id); 395 396 if (id == defaultId) { 397 defaultRange.clear(); 398 defaultPort->getPeerAddressRanges(ranges, snoops); 399 assert(snoops.size() == 0); 400 for(iter = ranges.begin(); iter != ranges.end(); iter++) { 401 defaultRange.push_back(*iter); 402 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n", 403 iter->start, iter->end); 404 } 405 } else { 406 407 assert((id < interfaces.size() && id >= 0) || id == defaultId); 408 Port *port = interfaces[id]; 409 std::vector<DevMap>::iterator portIter; 410 std::vector<DevMap>::iterator snoopIter; 411 412 // Clean out any previously existent ids 413 for (portIter = portList.begin(); portIter != portList.end(); ) { 414 if (portIter->portId == id) 415 portIter = portList.erase(portIter); 416 else 417 portIter++; 418 } 419 420 for (snoopIter = portSnoopList.begin(); snoopIter != portSnoopList.end(); ) { 421 if (snoopIter->portId == id) 422 snoopIter = portSnoopList.erase(snoopIter); 423 else 424 snoopIter++; 425 } 426 427 port->getPeerAddressRanges(ranges, snoops); 428 429 for(iter = snoops.begin(); iter != snoops.end(); iter++) { 430 DevMap dm; 431 dm.portId = id; 432 dm.range = *iter; 433 434 DPRINTF(BusAddrRanges, "Adding snoop range %#llx - %#llx for id %d\n", 435 dm.range.start, dm.range.end, id); 436 portSnoopList.push_back(dm); 437 } 438 439 for(iter = ranges.begin(); iter != ranges.end(); iter++) { 440 DevMap dm; 441 dm.portId = id; 442 dm.range = *iter; 443 444 DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n", 445 dm.range.start, dm.range.end, id); 446 portList.push_back(dm); 447 } 448 } 449 DPRINTF(MMU, "port list has %d entries\n", portList.size()); 450 451 // tell all our peers that our address range has changed. 452 // Don't tell the device that caused this change, it already knows 453 for (x = 0; x < interfaces.size(); x++) 454 if (x != id) 455 interfaces[x]->sendStatusChange(Port::RangeChange); 456 457 if (id != defaultId && defaultPort) 458 defaultPort->sendStatusChange(Port::RangeChange); 459} 460 461void 462Bus::addressRanges(AddrRangeList &resp, AddrRangeList &snoop, int id) 463{ 464 std::vector<DevMap>::iterator portIter; 465 AddrRangeIter dflt_iter; 466 bool subset; 467 468 resp.clear(); 469 snoop.clear(); 470 471 DPRINTF(BusAddrRanges, "received address range request, returning:\n"); 472 473 for (dflt_iter = defaultRange.begin(); dflt_iter != defaultRange.end(); 474 dflt_iter++) { 475 resp.push_back(*dflt_iter); 476 DPRINTF(BusAddrRanges, " -- %#llx : %#llx\n",dflt_iter->start, 477 dflt_iter->end); 478 } 479 for (portIter = portList.begin(); portIter != portList.end(); portIter++) { 480 subset = false; 481 for (dflt_iter = defaultRange.begin(); dflt_iter != defaultRange.end(); 482 dflt_iter++) { 483 if ((portIter->range.start < dflt_iter->start && 484 portIter->range.end >= dflt_iter->start) || 485 (portIter->range.start < dflt_iter->end && 486 portIter->range.end >= dflt_iter->end)) 487 fatal("Devices can not set ranges that itersect the default set\ 488 but are not a subset of the default set.\n"); 489 if (portIter->range.start >= dflt_iter->start && 490 portIter->range.end <= dflt_iter->end) { 491 subset = true; 492 DPRINTF(BusAddrRanges, " -- %#llx : %#llx is a SUBSET\n", 493 portIter->range.start, portIter->range.end); 494 } 495 } 496 if (portIter->portId != id && !subset) { 497 resp.push_back(portIter->range); 498 DPRINTF(BusAddrRanges, " -- %#llx : %#llx\n", 499 portIter->range.start, portIter->range.end); 500 } 501 } 502} 503 504unsigned int 505Bus::drain(Event * de) 506{ 507 //We should check that we're not "doing" anything, and that noone is 508 //waiting. We might be idle but have someone waiting if the device we 509 //contacted for a retry didn't actually retry. 510 if (curTick >= tickNextIdle && retryList.size() == 0) { 511 drainEvent = de; 512 return 1; 513 } else { 514 return 0; 515 } 516} 517 518BEGIN_DECLARE_SIM_OBJECT_PARAMS(Bus) 519 520 Param<int> bus_id; 521 Param<int> clock; 522 Param<int> width; 523 524END_DECLARE_SIM_OBJECT_PARAMS(Bus) 525 526BEGIN_INIT_SIM_OBJECT_PARAMS(Bus) 527 INIT_PARAM(bus_id, "a globally unique bus id"), 528 INIT_PARAM(clock, "bus clock speed"), 529 INIT_PARAM(width, "width of the bus (bits)") 530END_INIT_SIM_OBJECT_PARAMS(Bus) 531 532CREATE_SIM_OBJECT(Bus) 533{ 534 return new Bus(getInstanceName(), bus_id, clock, width); 535} 536 537REGISTER_SIM_OBJECT("Bus", Bus) 538