Sequencer.cc revision 7546
1/* 2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 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 29#include "base/str.hh" 30#include "cpu/rubytest/RubyTester.hh" 31#include "mem/protocol/CacheMsg.hh" 32#include "mem/protocol/Protocol.hh" 33#include "mem/protocol/Protocol.hh" 34#include "mem/ruby/buffers/MessageBuffer.hh" 35#include "mem/ruby/common/Global.hh" 36#include "mem/ruby/common/SubBlock.hh" 37#include "mem/ruby/libruby.hh" 38#include "mem/ruby/profiler/Profiler.hh" 39#include "mem/ruby/recorder/Tracer.hh" 40#include "mem/ruby/slicc_interface/AbstractController.hh" 41#include "mem/ruby/system/CacheMemory.hh" 42#include "mem/ruby/system/Sequencer.hh" 43#include "mem/ruby/system/System.hh" 44#include "params/RubySequencer.hh" 45 46using namespace std; 47 48Sequencer * 49RubySequencerParams::create() 50{ 51 return new Sequencer(this); 52} 53 54Sequencer::Sequencer(const Params *p) 55 : RubyPort(p), deadlockCheckEvent(this) 56{ 57 m_store_waiting_on_load_cycles = 0; 58 m_store_waiting_on_store_cycles = 0; 59 m_load_waiting_on_store_cycles = 0; 60 m_load_waiting_on_load_cycles = 0; 61 62 m_outstanding_count = 0; 63 64 m_max_outstanding_requests = 0; 65 m_deadlock_threshold = 0; 66 m_instCache_ptr = NULL; 67 m_dataCache_ptr = NULL; 68 69 m_instCache_ptr = p->icache; 70 m_dataCache_ptr = p->dcache; 71 m_max_outstanding_requests = p->max_outstanding_requests; 72 m_deadlock_threshold = p->deadlock_threshold; 73 m_usingRubyTester = p->using_ruby_tester; 74 75 assert(m_max_outstanding_requests > 0); 76 assert(m_deadlock_threshold > 0); 77 assert(m_instCache_ptr != NULL); 78 assert(m_dataCache_ptr != NULL); 79} 80 81Sequencer::~Sequencer() 82{ 83} 84 85void 86Sequencer::wakeup() 87{ 88 // Check for deadlock of any of the requests 89 Time current_time = g_eventQueue_ptr->getTime(); 90 91 // Check across all outstanding requests 92 int total_outstanding = 0; 93 94 RequestTable::iterator read = m_readRequestTable.begin(); 95 RequestTable::iterator read_end = m_readRequestTable.end(); 96 for (; read != read_end; ++read) { 97 SequencerRequest* request = read->second; 98 if (current_time - request->issue_time < m_deadlock_threshold) 99 continue; 100 101 WARN_MSG("Possible Deadlock detected"); 102 WARN_EXPR(m_version); 103 WARN_EXPR(request->ruby_request.paddr); 104 WARN_EXPR(m_readRequestTable.size()); 105 WARN_EXPR(current_time); 106 WARN_EXPR(request->issue_time); 107 WARN_EXPR(current_time - request->issue_time); 108 ERROR_MSG("Aborting"); 109 } 110 111 RequestTable::iterator write = m_writeRequestTable.begin(); 112 RequestTable::iterator write_end = m_writeRequestTable.end(); 113 for (; write != write_end; ++write) { 114 SequencerRequest* request = write->second; 115 if (current_time - request->issue_time < m_deadlock_threshold) 116 continue; 117 118 WARN_MSG("Possible Deadlock detected"); 119 WARN_EXPR(m_version); 120 WARN_EXPR(request->ruby_request.paddr); 121 WARN_EXPR(current_time); 122 WARN_EXPR(request->issue_time); 123 WARN_EXPR(current_time - request->issue_time); 124 WARN_EXPR(m_writeRequestTable.size()); 125 ERROR_MSG("Aborting"); 126 } 127 128 total_outstanding += m_writeRequestTable.size(); 129 total_outstanding += m_readRequestTable.size(); 130 131 assert(m_outstanding_count == total_outstanding); 132 133 if (m_outstanding_count > 0) { 134 // If there are still outstanding requests, keep checking 135 schedule(deadlockCheckEvent, 136 m_deadlock_threshold * g_eventQueue_ptr->getClock() + 137 curTick); 138 } 139} 140 141void 142Sequencer::printStats(ostream & out) const 143{ 144 out << "Sequencer: " << m_name << endl 145 << " store_waiting_on_load_cycles: " 146 << m_store_waiting_on_load_cycles << endl 147 << " store_waiting_on_store_cycles: " 148 << m_store_waiting_on_store_cycles << endl 149 << " load_waiting_on_load_cycles: " 150 << m_load_waiting_on_load_cycles << endl 151 << " load_waiting_on_store_cycles: " 152 << m_load_waiting_on_store_cycles << endl; 153} 154 155void 156Sequencer::printProgress(ostream& out) const 157{ 158#if 0 159 int total_demand = 0; 160 out << "Sequencer Stats Version " << m_version << endl; 161 out << "Current time = " << g_eventQueue_ptr->getTime() << endl; 162 out << "---------------" << endl; 163 out << "outstanding requests" << endl; 164 165 out << "proc " << m_Read 166 << " version Requests = " << m_readRequestTable.size() << endl; 167 168 // print the request table 169 RequestTable::iterator read = m_readRequestTable.begin(); 170 RequestTable::iterator read_end = m_readRequestTable.end(); 171 for (; read != read_end; ++read) { 172 SequencerRequest* request = read->second; 173 out << "\tRequest[ " << i << " ] = " << request->type 174 << " Address " << rkeys[i] 175 << " Posted " << request->issue_time 176 << " PF " << PrefetchBit_No << endl; 177 total_demand++; 178 } 179 180 out << "proc " << m_version 181 << " Write Requests = " << m_writeRequestTable.size << endl; 182 183 // print the request table 184 RequestTable::iterator write = m_writeRequestTable.begin(); 185 RequestTable::iterator write_end = m_writeRequestTable.end(); 186 for (; write != write_end; ++write) { 187 SequencerRequest* request = write->second; 188 out << "\tRequest[ " << i << " ] = " << request.getType() 189 << " Address " << wkeys[i] 190 << " Posted " << request.getTime() 191 << " PF " << request.getPrefetch() << endl; 192 if (request.getPrefetch() == PrefetchBit_No) { 193 total_demand++; 194 } 195 } 196 197 out << endl; 198 199 out << "Total Number Outstanding: " << m_outstanding_count << endl 200 << "Total Number Demand : " << total_demand << endl 201 << "Total Number Prefetches : " << m_outstanding_count - total_demand 202 << endl << endl << endl; 203#endif 204} 205 206void 207Sequencer::printConfig(ostream& out) const 208{ 209 out << "Seqeuncer config: " << m_name << endl 210 << " controller: " << m_controller->getName() << endl 211 << " version: " << m_version << endl 212 << " max_outstanding_requests: " << m_max_outstanding_requests << endl 213 << " deadlock_threshold: " << m_deadlock_threshold << endl; 214} 215 216// Insert the request on the correct request table. Return true if 217// the entry was already present. 218bool 219Sequencer::insertRequest(SequencerRequest* request) 220{ 221 int total_outstanding = 222 m_writeRequestTable.size() + m_readRequestTable.size(); 223 224 assert(m_outstanding_count == total_outstanding); 225 226 // See if we should schedule a deadlock check 227 if (deadlockCheckEvent.scheduled() == false) { 228 schedule(deadlockCheckEvent, m_deadlock_threshold + curTick); 229 } 230 231 Address line_addr(request->ruby_request.paddr); 232 line_addr.makeLineAddress(); 233 if ((request->ruby_request.type == RubyRequestType_ST) || 234 (request->ruby_request.type == RubyRequestType_RMW_Read) || 235 (request->ruby_request.type == RubyRequestType_RMW_Write) || 236 (request->ruby_request.type == RubyRequestType_Locked_Read) || 237 (request->ruby_request.type == RubyRequestType_Locked_Write)) { 238 pair<RequestTable::iterator, bool> r = 239 m_writeRequestTable.insert(RequestTable::value_type(line_addr, 0)); 240 bool success = r.second; 241 RequestTable::iterator i = r.first; 242 if (!success) { 243 i->second = request; 244 // return true; 245 246 // drh5: isn't this an error? do you lose the initial request? 247 assert(0); 248 } 249 i->second = request; 250 m_outstanding_count++; 251 } else { 252 pair<RequestTable::iterator, bool> r = 253 m_readRequestTable.insert(RequestTable::value_type(line_addr, 0)); 254 bool success = r.second; 255 RequestTable::iterator i = r.first; 256 if (!success) { 257 i->second = request; 258 // return true; 259 260 // drh5: isn't this an error? do you lose the initial request? 261 assert(0); 262 } 263 i->second = request; 264 m_outstanding_count++; 265 } 266 267 g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count); 268 269 total_outstanding = m_writeRequestTable.size() + m_readRequestTable.size(); 270 assert(m_outstanding_count == total_outstanding); 271 272 return false; 273} 274 275void 276Sequencer::markRemoved() 277{ 278 m_outstanding_count--; 279 assert(m_outstanding_count == 280 m_writeRequestTable.size() + m_readRequestTable.size()); 281} 282 283void 284Sequencer::removeRequest(SequencerRequest* srequest) 285{ 286 assert(m_outstanding_count == 287 m_writeRequestTable.size() + m_readRequestTable.size()); 288 289 const RubyRequest & ruby_request = srequest->ruby_request; 290 Address line_addr(ruby_request.paddr); 291 line_addr.makeLineAddress(); 292 if ((ruby_request.type == RubyRequestType_ST) || 293 (ruby_request.type == RubyRequestType_RMW_Read) || 294 (ruby_request.type == RubyRequestType_RMW_Write) || 295 (ruby_request.type == RubyRequestType_Locked_Read) || 296 (ruby_request.type == RubyRequestType_Locked_Write)) { 297 m_writeRequestTable.erase(line_addr); 298 } else { 299 m_readRequestTable.erase(line_addr); 300 } 301 302 markRemoved(); 303} 304 305void 306Sequencer::writeCallback(const Address& address, DataBlock& data) 307{ 308 writeCallback(address, GenericMachineType_NULL, data); 309} 310 311void 312Sequencer::writeCallback(const Address& address, 313 GenericMachineType mach, 314 DataBlock& data) 315{ 316 assert(address == line_address(address)); 317 assert(m_writeRequestTable.count(line_address(address))); 318 319 RequestTable::iterator i = m_writeRequestTable.find(address); 320 assert(i != m_writeRequestTable.end()); 321 SequencerRequest* request = i->second; 322 323 m_writeRequestTable.erase(i); 324 markRemoved(); 325 326 assert((request->ruby_request.type == RubyRequestType_ST) || 327 (request->ruby_request.type == RubyRequestType_RMW_Read) || 328 (request->ruby_request.type == RubyRequestType_RMW_Write) || 329 (request->ruby_request.type == RubyRequestType_Locked_Read) || 330 (request->ruby_request.type == RubyRequestType_Locked_Write)); 331 332 if (request->ruby_request.type == RubyRequestType_Locked_Read) { 333 m_dataCache_ptr->setLocked(address, m_version); 334 } else if (request->ruby_request.type == RubyRequestType_RMW_Read) { 335 m_controller->blockOnQueue(address, m_mandatory_q_ptr); 336 } else if (request->ruby_request.type == RubyRequestType_RMW_Write) { 337 m_controller->unblock(address); 338 } 339 340 hitCallback(request, mach, data); 341} 342 343void 344Sequencer::readCallback(const Address& address, DataBlock& data) 345{ 346 readCallback(address, GenericMachineType_NULL, data); 347} 348 349void 350Sequencer::readCallback(const Address& address, 351 GenericMachineType mach, 352 DataBlock& data) 353{ 354 assert(address == line_address(address)); 355 assert(m_readRequestTable.count(line_address(address))); 356 357 RequestTable::iterator i = m_readRequestTable.find(address); 358 assert(i != m_readRequestTable.end()); 359 SequencerRequest* request = i->second; 360 361 m_readRequestTable.erase(i); 362 markRemoved(); 363 364 assert((request->ruby_request.type == RubyRequestType_LD) || 365 (request->ruby_request.type == RubyRequestType_RMW_Read) || 366 (request->ruby_request.type == RubyRequestType_IFETCH)); 367 368 hitCallback(request, mach, data); 369} 370 371void 372Sequencer::hitCallback(SequencerRequest* srequest, 373 GenericMachineType mach, 374 DataBlock& data) 375{ 376 const RubyRequest & ruby_request = srequest->ruby_request; 377 Address request_address(ruby_request.paddr); 378 Address request_line_address(ruby_request.paddr); 379 request_line_address.makeLineAddress(); 380 RubyRequestType type = ruby_request.type; 381 Time issued_time = srequest->issue_time; 382 383 // Set this cache entry to the most recently used 384 if (type == RubyRequestType_IFETCH) { 385 if (m_instCache_ptr->isTagPresent(request_line_address)) 386 m_instCache_ptr->setMRU(request_line_address); 387 } else { 388 if (m_dataCache_ptr->isTagPresent(request_line_address)) 389 m_dataCache_ptr->setMRU(request_line_address); 390 } 391 392 assert(g_eventQueue_ptr->getTime() >= issued_time); 393 Time miss_latency = g_eventQueue_ptr->getTime() - issued_time; 394 395 // Profile the miss latency for all non-zero demand misses 396 if (miss_latency != 0) { 397 g_system_ptr->getProfiler()->missLatency(miss_latency, type, mach); 398 399 if (Debug::getProtocolTrace()) { 400 g_system_ptr->getProfiler()-> 401 profileTransition("Seq", m_version, 402 Address(ruby_request.paddr), "", "Done", "", 403 csprintf("%d cycles", miss_latency)); 404 } 405 } 406#if 0 407 if (request.getPrefetch() == PrefetchBit_Yes) { 408 return; // Ignore the prefetch 409 } 410#endif 411 412 // update the data 413 if (ruby_request.data != NULL) { 414 if ((type == RubyRequestType_LD) || 415 (type == RubyRequestType_IFETCH) || 416 (type == RubyRequestType_RMW_Read) || 417 (type == RubyRequestType_Locked_Read)) { 418 419 memcpy(ruby_request.data, 420 data.getData(request_address.getOffset(), ruby_request.len), 421 ruby_request.len); 422 } else { 423 data.setData(ruby_request.data, request_address.getOffset(), 424 ruby_request.len); 425 } 426 } else { 427 DPRINTF(MemoryAccess, 428 "WARNING. Data not transfered from Ruby to M5 for type %s\n", 429 RubyRequestType_to_string(type)); 430 } 431 432 // If using the RubyTester, update the RubyTester sender state's 433 // subBlock with the recieved data. The tester will later access 434 // this state. 435 // Note: RubyPort will access it's sender state before the 436 // RubyTester. 437 if (m_usingRubyTester) { 438 RubyPort::SenderState *requestSenderState = 439 safe_cast<RubyPort::SenderState*>(ruby_request.pkt->senderState); 440 RubyTester::SenderState* testerSenderState = 441 safe_cast<RubyTester::SenderState*>(requestSenderState->saved); 442 testerSenderState->subBlock->mergeFrom(data); 443 } 444 445 ruby_hit_callback(ruby_request.pkt); 446 delete srequest; 447} 448 449// Returns true if the sequencer already has a load or store outstanding 450RequestStatus 451Sequencer::getRequestStatus(const RubyRequest& request) 452{ 453 bool is_outstanding_store = 454 !!m_writeRequestTable.count(line_address(Address(request.paddr))); 455 bool is_outstanding_load = 456 !!m_readRequestTable.count(line_address(Address(request.paddr))); 457 if (is_outstanding_store) { 458 if ((request.type == RubyRequestType_LD) || 459 (request.type == RubyRequestType_IFETCH) || 460 (request.type == RubyRequestType_RMW_Read)) { 461 m_store_waiting_on_load_cycles++; 462 } else { 463 m_store_waiting_on_store_cycles++; 464 } 465 return RequestStatus_Aliased; 466 } else if (is_outstanding_load) { 467 if ((request.type == RubyRequestType_ST) || 468 (request.type == RubyRequestType_RMW_Write)) { 469 m_load_waiting_on_store_cycles++; 470 } else { 471 m_load_waiting_on_load_cycles++; 472 } 473 return RequestStatus_Aliased; 474 } 475 476 if (m_outstanding_count >= m_max_outstanding_requests) { 477 return RequestStatus_BufferFull; 478 } 479 480 return RequestStatus_Ready; 481} 482 483bool 484Sequencer::empty() const 485{ 486 return m_writeRequestTable.empty() && m_readRequestTable.empty(); 487} 488 489RequestStatus 490Sequencer::makeRequest(const RubyRequest &request) 491{ 492 assert(Address(request.paddr).getOffset() + request.len <= 493 RubySystem::getBlockSizeBytes()); 494 RequestStatus status = getRequestStatus(request); 495 if (status != RequestStatus_Ready) 496 return status; 497 498 SequencerRequest *srequest = 499 new SequencerRequest(request, g_eventQueue_ptr->getTime()); 500 bool found = insertRequest(srequest); 501 if (found) { 502 panic("Sequencer::makeRequest should never be called if the " 503 "request is already outstanding\n"); 504 return RequestStatus_NULL; 505 } 506 507 if (request.type == RubyRequestType_Locked_Write) { 508 // NOTE: it is OK to check the locked flag here as the 509 // mandatory queue will be checked first ensuring that nothing 510 // comes between checking the flag and servicing the store. 511 512 Address line_addr = line_address(Address(request.paddr)); 513 if (!m_dataCache_ptr->isLocked(line_addr, m_version)) { 514 removeRequest(srequest); 515 if (Debug::getProtocolTrace()) { 516 g_system_ptr->getProfiler()-> 517 profileTransition("Seq", m_version, 518 Address(request.paddr), 519 "", "SC Fail", "", 520 RubyRequestType_to_string(request.type)); 521 } 522 return RequestStatus_LlscFailed; 523 } else { 524 m_dataCache_ptr->clearLocked(line_addr); 525 } 526 } 527 issueRequest(request); 528 529 // TODO: issue hardware prefetches here 530 return RequestStatus_Issued; 531} 532 533void 534Sequencer::issueRequest(const RubyRequest& request) 535{ 536 // TODO: get rid of CacheMsg, CacheRequestType, and 537 // AccessModeTYpe, & have SLICC use RubyRequest and subtypes 538 // natively 539 CacheRequestType ctype; 540 switch(request.type) { 541 case RubyRequestType_IFETCH: 542 ctype = CacheRequestType_IFETCH; 543 break; 544 case RubyRequestType_LD: 545 ctype = CacheRequestType_LD; 546 break; 547 case RubyRequestType_ST: 548 ctype = CacheRequestType_ST; 549 break; 550 case RubyRequestType_Locked_Read: 551 case RubyRequestType_Locked_Write: 552 ctype = CacheRequestType_ATOMIC; 553 break; 554 case RubyRequestType_RMW_Read: 555 ctype = CacheRequestType_ATOMIC; 556 break; 557 case RubyRequestType_RMW_Write: 558 ctype = CacheRequestType_ATOMIC; 559 break; 560 default: 561 assert(0); 562 } 563 564 AccessModeType amtype; 565 switch(request.access_mode){ 566 case RubyAccessMode_User: 567 amtype = AccessModeType_UserMode; 568 break; 569 case RubyAccessMode_Supervisor: 570 amtype = AccessModeType_SupervisorMode; 571 break; 572 case RubyAccessMode_Device: 573 amtype = AccessModeType_UserMode; 574 break; 575 default: 576 assert(0); 577 } 578 579 Address line_addr(request.paddr); 580 line_addr.makeLineAddress(); 581 CacheMsg *msg = new CacheMsg(line_addr, Address(request.paddr), ctype, 582 Address(request.pc), amtype, request.len, PrefetchBit_No, 583 request.proc_id); 584 585 if (Debug::getProtocolTrace()) { 586 g_system_ptr->getProfiler()-> 587 profileTransition("Seq", m_version, Address(request.paddr), 588 "", "Begin", "", 589 RubyRequestType_to_string(request.type)); 590 } 591 592 if (g_system_ptr->getTracer()->traceEnabled()) { 593 g_system_ptr->getTracer()-> 594 traceRequest(this, line_addr, Address(request.pc), 595 request.type, g_eventQueue_ptr->getTime()); 596 } 597 598 Time latency = 0; // initialzed to an null value 599 600 if (request.type == RubyRequestType_IFETCH) 601 latency = m_instCache_ptr->getLatency(); 602 else 603 latency = m_dataCache_ptr->getLatency(); 604 605 // Send the message to the cache controller 606 assert(latency > 0); 607 608 assert(m_mandatory_q_ptr != NULL); 609 m_mandatory_q_ptr->enqueue(msg, latency); 610} 611 612#if 0 613bool 614Sequencer::tryCacheAccess(const Address& addr, CacheRequestType type, 615 AccessModeType access_mode, 616 int size, DataBlock*& data_ptr) 617{ 618 CacheMemory *cache = 619 (type == CacheRequestType_IFETCH) ? m_instCache_ptr : m_dataCache_ptr; 620 621 return cache->tryCacheAccess(line_address(addr), type, data_ptr); 622} 623#endif 624 625template <class KEY, class VALUE> 626std::ostream & 627operator<<(ostream &out, const m5::hash_map<KEY, VALUE> &map) 628{ 629 typename m5::hash_map<KEY, VALUE>::const_iterator i = map.begin(); 630 typename m5::hash_map<KEY, VALUE>::const_iterator end = map.end(); 631 632 out << "["; 633 for (; i != end; ++i) 634 out << " " << i->first << "=" << i->second; 635 out << " ]"; 636 637 return out; 638} 639 640void 641Sequencer::print(ostream& out) const 642{ 643 out << "[Sequencer: " << m_version 644 << ", outstanding requests: " << m_outstanding_count 645 << ", read request table: " << m_readRequestTable 646 << ", write request table: " << m_writeRequestTable 647 << "]"; 648} 649 650// this can be called from setState whenever coherence permissions are 651// upgraded when invoked, coherence violations will be checked for the 652// given block 653void 654Sequencer::checkCoherence(const Address& addr) 655{ 656#ifdef CHECK_COHERENCE 657 g_system_ptr->checkGlobalCoherenceInvariant(addr); 658#endif 659} 660