Sequencer.cc revision 6862:3d308cbd1657
1 2/* 3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are 8 * met: redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer; 10 * redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution; 13 * neither the name of the copyright holders nor the names of its 14 * contributors may be used to endorse or promote products derived from 15 * this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#include "mem/ruby/libruby.hh" 31#include "mem/ruby/common/Global.hh" 32#include "mem/ruby/system/Sequencer.hh" 33#include "mem/ruby/system/System.hh" 34#include "mem/protocol/Protocol.hh" 35#include "mem/ruby/profiler/Profiler.hh" 36#include "mem/ruby/system/CacheMemory.hh" 37#include "mem/protocol/CacheMsg.hh" 38#include "mem/ruby/recorder/Tracer.hh" 39#include "mem/ruby/common/SubBlock.hh" 40#include "mem/protocol/Protocol.hh" 41#include "mem/gems_common/Map.hh" 42#include "mem/ruby/buffers/MessageBuffer.hh" 43#include "mem/ruby/slicc_interface/AbstractController.hh" 44 45//Sequencer::Sequencer(int core_id, MessageBuffer* mandatory_q) 46 47#define LLSC_FAIL -2 48long int already = 0; 49Sequencer::Sequencer(const string & name) 50 :RubyPort(name) 51{ 52 m_store_waiting_on_load_cycles = 0; 53 m_store_waiting_on_store_cycles = 0; 54 m_load_waiting_on_store_cycles = 0; 55 m_load_waiting_on_load_cycles = 0; 56} 57 58void Sequencer::init(const vector<string> & argv) 59{ 60 m_deadlock_check_scheduled = false; 61 m_outstanding_count = 0; 62 63 m_max_outstanding_requests = 0; 64 m_deadlock_threshold = 0; 65 m_version = -1; 66 m_instCache_ptr = NULL; 67 m_dataCache_ptr = NULL; 68 m_controller = NULL; 69 m_atomic_reads = 0; 70 m_atomic_writes = 0; 71 for (size_t i=0; i<argv.size(); i+=2) { 72 if ( argv[i] == "controller") { 73 m_controller = RubySystem::getController(argv[i+1]); // args[i] = "L1Cache" 74 m_mandatory_q_ptr = m_controller->getMandatoryQueue(); 75 } else if ( argv[i] == "icache") 76 m_instCache_ptr = RubySystem::getCache(argv[i+1]); 77 else if ( argv[i] == "dcache") 78 m_dataCache_ptr = RubySystem::getCache(argv[i+1]); 79 else if ( argv[i] == "version") 80 m_version = atoi(argv[i+1].c_str()); 81 else if ( argv[i] == "max_outstanding_requests") 82 m_max_outstanding_requests = atoi(argv[i+1].c_str()); 83 else if ( argv[i] == "deadlock_threshold") 84 m_deadlock_threshold = atoi(argv[i+1].c_str()); 85 else { 86 cerr << "WARNING: Sequencer: Unkown configuration parameter: " << argv[i] << endl; 87 assert(false); 88 } 89 } 90 assert(m_max_outstanding_requests > 0); 91 assert(m_deadlock_threshold > 0); 92 assert(m_version > -1); 93 assert(m_instCache_ptr != NULL); 94 assert(m_dataCache_ptr != NULL); 95 assert(m_controller != NULL); 96} 97 98Sequencer::~Sequencer() { 99 100} 101 102void Sequencer::wakeup() { 103 // Check for deadlock of any of the requests 104 Time current_time = g_eventQueue_ptr->getTime(); 105 106 // Check across all outstanding requests 107 int total_outstanding = 0; 108 109 Vector<Address> keys = m_readRequestTable.keys(); 110 for (int i=0; i<keys.size(); i++) { 111 SequencerRequest* request = m_readRequestTable.lookup(keys[i]); 112 if (current_time - request->issue_time >= m_deadlock_threshold) { 113 WARN_MSG("Possible Deadlock detected"); 114 WARN_EXPR(request); 115 WARN_EXPR(m_version); 116 WARN_EXPR(request->ruby_request.paddr); 117 WARN_EXPR(keys.size()); 118 WARN_EXPR(current_time); 119 WARN_EXPR(request->issue_time); 120 WARN_EXPR(current_time - request->issue_time); 121 ERROR_MSG("Aborting"); 122 } 123 } 124 125 keys = m_writeRequestTable.keys(); 126 for (int i=0; i<keys.size(); i++) { 127 SequencerRequest* request = m_writeRequestTable.lookup(keys[i]); 128 if (current_time - request->issue_time >= m_deadlock_threshold) { 129 WARN_MSG("Possible Deadlock detected"); 130 WARN_EXPR(request); 131 WARN_EXPR(m_version); 132 WARN_EXPR(current_time); 133 WARN_EXPR(request->issue_time); 134 WARN_EXPR(current_time - request->issue_time); 135 WARN_EXPR(keys.size()); 136 ERROR_MSG("Aborting"); 137 } 138 } 139 total_outstanding += m_writeRequestTable.size() + m_readRequestTable.size(); 140 141 assert(m_outstanding_count == total_outstanding); 142 143 if (m_outstanding_count > 0) { // If there are still outstanding requests, keep checking 144 g_eventQueue_ptr->scheduleEvent(this, m_deadlock_threshold); 145 } else { 146 m_deadlock_check_scheduled = false; 147 } 148} 149 150void Sequencer::printStats(ostream & out) const { 151 out << "Sequencer: " << m_name << endl; 152 out << " store_waiting_on_load_cycles: " << m_store_waiting_on_load_cycles << endl; 153 out << " store_waiting_on_store_cycles: " << m_store_waiting_on_store_cycles << endl; 154 out << " load_waiting_on_load_cycles: " << m_load_waiting_on_load_cycles << endl; 155 out << " load_waiting_on_store_cycles: " << m_load_waiting_on_store_cycles << endl; 156} 157 158void Sequencer::printProgress(ostream& out) const{ 159 /* 160 int total_demand = 0; 161 out << "Sequencer Stats Version " << m_version << endl; 162 out << "Current time = " << g_eventQueue_ptr->getTime() << endl; 163 out << "---------------" << endl; 164 out << "outstanding requests" << endl; 165 166 Vector<Address> rkeys = m_readRequestTable.keys(); 167 int read_size = rkeys.size(); 168 out << "proc " << m_version << " Read Requests = " << read_size << endl; 169 // print the request table 170 for(int i=0; i < read_size; ++i){ 171 SequencerRequest * request = m_readRequestTable.lookup(rkeys[i]); 172 out << "\tRequest[ " << i << " ] = " << request->type << " Address " << rkeys[i] << " Posted " << request->issue_time << " PF " << PrefetchBit_No << endl; 173 total_demand++; 174 } 175 176 Vector<Address> wkeys = m_writeRequestTable.keys(); 177 int write_size = wkeys.size(); 178 out << "proc " << m_version << " Write Requests = " << write_size << endl; 179 // print the request table 180 for(int i=0; i < write_size; ++i){ 181 CacheMsg & request = m_writeRequestTable.lookup(wkeys[i]); 182 out << "\tRequest[ " << i << " ] = " << request.getType() << " Address " << wkeys[i] << " Posted " << request.getTime() << " PF " << request.getPrefetch() << endl; 183 if( request.getPrefetch() == PrefetchBit_No ){ 184 total_demand++; 185 } 186 } 187 188 out << endl; 189 190 out << "Total Number Outstanding: " << m_outstanding_count << endl; 191 out << "Total Number Demand : " << total_demand << endl; 192 out << "Total Number Prefetches : " << m_outstanding_count - total_demand << endl; 193 out << endl; 194 out << endl; 195 */ 196} 197 198void Sequencer::printConfig(ostream& out) const { 199 out << "Seqeuncer config: " << m_name << endl; 200 out << " controller: " << m_controller->getName() << endl; 201 out << " version: " << m_version << endl; 202 out << " max_outstanding_requests: " << m_max_outstanding_requests << endl; 203 out << " deadlock_threshold: " << m_deadlock_threshold << endl; 204} 205 206// Insert the request on the correct request table. Return true if 207// the entry was already present. 208bool Sequencer::insertRequest(SequencerRequest* request) { 209 int total_outstanding = m_writeRequestTable.size() + m_readRequestTable.size(); 210 211 assert(m_outstanding_count == total_outstanding); 212 213 // See if we should schedule a deadlock check 214 if (m_deadlock_check_scheduled == false) { 215 g_eventQueue_ptr->scheduleEvent(this, m_deadlock_threshold); 216 m_deadlock_check_scheduled = true; 217 } 218 219 Address line_addr(request->ruby_request.paddr); 220 line_addr.makeLineAddress(); 221 if ((request->ruby_request.type == RubyRequestType_ST) || 222 (request->ruby_request.type == RubyRequestType_RMW_Read) || 223 (request->ruby_request.type == RubyRequestType_RMW_Write) || 224 (request->ruby_request.type == RubyRequestType_Locked_Read) || 225 (request->ruby_request.type == RubyRequestType_Locked_Write)) { 226 if (m_writeRequestTable.exist(line_addr)) { 227 m_writeRequestTable.lookup(line_addr) = request; 228 // return true; 229 assert(0); // drh5: isn't this an error? do you lose the initial request? 230 } 231 m_writeRequestTable.allocate(line_addr); 232 m_writeRequestTable.lookup(line_addr) = request; 233 m_outstanding_count++; 234 } else { 235 if (m_readRequestTable.exist(line_addr)) { 236 m_readRequestTable.lookup(line_addr) = request; 237 // return true; 238 assert(0); // drh5: isn't this an error? do you lose the initial request? 239 } 240 m_readRequestTable.allocate(line_addr); 241 m_readRequestTable.lookup(line_addr) = request; 242 m_outstanding_count++; 243 } 244 245 g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count); 246 247 total_outstanding = m_writeRequestTable.size() + m_readRequestTable.size(); 248 assert(m_outstanding_count == total_outstanding); 249 250 return false; 251} 252 253void Sequencer::removeRequest(SequencerRequest* srequest) { 254 255 assert(m_outstanding_count == m_writeRequestTable.size() + m_readRequestTable.size()); 256 257 const RubyRequest & ruby_request = srequest->ruby_request; 258 Address line_addr(ruby_request.paddr); 259 line_addr.makeLineAddress(); 260 if ((ruby_request.type == RubyRequestType_ST) || 261 (ruby_request.type == RubyRequestType_RMW_Read) || 262 (ruby_request.type == RubyRequestType_RMW_Write) || 263 (ruby_request.type == RubyRequestType_Locked_Read) || 264 (ruby_request.type == RubyRequestType_Locked_Write)) { 265 m_writeRequestTable.deallocate(line_addr); 266 } else { 267 m_readRequestTable.deallocate(line_addr); 268 } 269 m_outstanding_count--; 270 271 assert(m_outstanding_count == m_writeRequestTable.size() + m_readRequestTable.size()); 272} 273 274void Sequencer::writeCallback(const Address& address, DataBlock& data) { 275 276 assert(address == line_address(address)); 277 assert(m_writeRequestTable.exist(line_address(address))); 278 279 SequencerRequest* request = m_writeRequestTable.lookup(address); 280 281 removeRequest(request); 282 283 assert((request->ruby_request.type == RubyRequestType_ST) || 284 (request->ruby_request.type == RubyRequestType_RMW_Read) || 285 (request->ruby_request.type == RubyRequestType_RMW_Write) || 286 (request->ruby_request.type == RubyRequestType_Locked_Read) || 287 (request->ruby_request.type == RubyRequestType_Locked_Write)); 288 // POLINA: the assumption is that atomics are only on data cache and not instruction cache 289 if (request->ruby_request.type == RubyRequestType_Locked_Read) { 290 m_dataCache_ptr->setLocked(address, m_version); 291 } 292 else if (request->ruby_request.type == RubyRequestType_RMW_Read) { 293 m_controller->set_atomic(address); 294 } 295 else if (request->ruby_request.type == RubyRequestType_RMW_Write) { 296 m_controller->clear_atomic(address); 297 } 298 299 hitCallback(request, data); 300} 301 302void Sequencer::readCallback(const Address& address, DataBlock& data) { 303 304 assert(address == line_address(address)); 305 assert(m_readRequestTable.exist(line_address(address))); 306 307 SequencerRequest* request = m_readRequestTable.lookup(address); 308 removeRequest(request); 309 310 assert((request->ruby_request.type == RubyRequestType_LD) || 311 (request->ruby_request.type == RubyRequestType_RMW_Read) || 312 (request->ruby_request.type == RubyRequestType_IFETCH)); 313 314 hitCallback(request, data); 315} 316 317void Sequencer::hitCallback(SequencerRequest* srequest, DataBlock& data) { 318 const RubyRequest & ruby_request = srequest->ruby_request; 319 Address request_address(ruby_request.paddr); 320 Address request_line_address(ruby_request.paddr); 321 request_line_address.makeLineAddress(); 322 RubyRequestType type = ruby_request.type; 323 Time issued_time = srequest->issue_time; 324 325 // Set this cache entry to the most recently used 326 if (type == RubyRequestType_IFETCH) { 327 if (m_instCache_ptr->isTagPresent(request_line_address) ) 328 m_instCache_ptr->setMRU(request_line_address); 329 } else { 330 if (m_dataCache_ptr->isTagPresent(request_line_address) ) 331 m_dataCache_ptr->setMRU(request_line_address); 332 } 333 334 assert(g_eventQueue_ptr->getTime() >= issued_time); 335 Time miss_latency = g_eventQueue_ptr->getTime() - issued_time; 336 337 // Profile the miss latency for all non-zero demand misses 338 if (miss_latency != 0) { 339 g_system_ptr->getProfiler()->missLatency(miss_latency, type); 340 341 if (Debug::getProtocolTrace()) { 342 g_system_ptr->getProfiler()->profileTransition("Seq", m_version, Address(ruby_request.paddr), 343 "", "Done", "", int_to_string(miss_latency)+" cycles"); 344 } 345 } 346 /* 347 if (request.getPrefetch() == PrefetchBit_Yes) { 348 return; // Ignore the prefetch 349 } 350 */ 351 352 // update the data 353 if (ruby_request.data != NULL) { 354 if ((type == RubyRequestType_LD) || 355 (type == RubyRequestType_IFETCH) || 356 (type == RubyRequestType_RMW_Read)) { 357 memcpy(ruby_request.data, data.getData(request_address.getOffset(), ruby_request.len), ruby_request.len); 358 } else { 359 data.setData(ruby_request.data, request_address.getOffset(), ruby_request.len); 360 } 361 } 362 363 m_hit_callback(srequest->id); 364 delete srequest; 365} 366 367// Returns true if the sequencer already has a load or store outstanding 368int Sequencer::isReady(const RubyRequest& request) { 369 bool is_outstanding_store = m_writeRequestTable.exist(line_address(Address(request.paddr))); 370 bool is_outstanding_load = m_readRequestTable.exist(line_address(Address(request.paddr))); 371 if ( is_outstanding_store ) { 372 if ((request.type == RubyRequestType_LD) || 373 (request.type == RubyRequestType_IFETCH) || 374 (request.type == RubyRequestType_RMW_Read)) { 375 m_store_waiting_on_load_cycles++; 376 } else { 377 m_store_waiting_on_store_cycles++; 378 } 379 return LIBRUBY_ALIASED_REQUEST; 380 } else if ( is_outstanding_load ) { 381 if ((request.type == RubyRequestType_ST) || 382 (request.type == RubyRequestType_RMW_Write) ) { 383 m_load_waiting_on_store_cycles++; 384 } else { 385 m_load_waiting_on_load_cycles++; 386 } 387 return LIBRUBY_ALIASED_REQUEST; 388 } 389 390 if (m_outstanding_count >= m_max_outstanding_requests) { 391 return LIBRUBY_BUFFER_FULL; 392 } 393 394 return 1; 395} 396 397bool Sequencer::empty() const { 398 return (m_writeRequestTable.size() == 0) && (m_readRequestTable.size() == 0); 399} 400 401 402int64_t Sequencer::makeRequest(const RubyRequest & request) 403{ 404 assert(Address(request.paddr).getOffset() + request.len <= RubySystem::getBlockSizeBytes()); 405 int ready = isReady(request); 406 if (ready > 0) { 407 int64_t id = makeUniqueRequestID(); 408 SequencerRequest *srequest = new SequencerRequest(request, id, g_eventQueue_ptr->getTime()); 409 bool found = insertRequest(srequest); 410 if (!found) { 411 if (request.type == RubyRequestType_Locked_Write) { 412 // NOTE: it is OK to check the locked flag here as the mandatory queue will be checked first 413 // ensuring that nothing comes between checking the flag and servicing the store 414 if (!m_dataCache_ptr->isLocked(line_address(Address(request.paddr)), m_version)) { 415 return LLSC_FAIL; 416 } 417 else { 418 m_dataCache_ptr->clearLocked(line_address(Address(request.paddr))); 419 } 420 } 421 issueRequest(request); 422 423 // TODO: issue hardware prefetches here 424 return id; 425 } 426 else { 427 assert(0); 428 return 0; 429 } 430 } else { 431 return ready; 432 } 433} 434 435void Sequencer::issueRequest(const RubyRequest& request) { 436 437 // TODO: get rid of CacheMsg, CacheRequestType, and AccessModeTYpe, & have SLICC use RubyRequest and subtypes natively 438 CacheRequestType ctype; 439 switch(request.type) { 440 case RubyRequestType_IFETCH: 441 if (m_atomic_reads > 0 && m_atomic_writes == 0) { 442 m_controller->reset_atomics(); 443 m_atomic_writes = 0; 444 m_atomic_reads = 0; 445 } 446 else if (m_atomic_writes > 0) { 447 assert(m_atomic_reads > m_atomic_writes); 448 cerr << "WARNING: Expected: " << m_atomic_reads << " RMW_Writes, but only received: " << m_atomic_writes << endl; 449 assert(false); 450 } 451 ctype = CacheRequestType_IFETCH; 452 break; 453 case RubyRequestType_LD: 454 if (m_atomic_reads > 0 && m_atomic_writes == 0) { 455 m_controller->reset_atomics(); 456 m_atomic_writes = 0; 457 m_atomic_reads = 0; 458 } 459 else if (m_atomic_writes > 0) { 460 assert(m_atomic_reads > m_atomic_writes); 461 cerr << "WARNING: Expected: " << m_atomic_reads << " RMW_Writes, but only received: " << m_atomic_writes << endl; 462 assert(false); 463 } 464 ctype = CacheRequestType_LD; 465 break; 466 case RubyRequestType_ST: 467 if (m_atomic_reads > 0 && m_atomic_writes == 0) { 468 m_controller->reset_atomics(); 469 m_atomic_writes = 0; 470 m_atomic_reads = 0; 471 } 472 else if (m_atomic_writes > 0) { 473 assert(m_atomic_reads > m_atomic_writes); 474 cerr << "WARNING: Expected: " << m_atomic_reads << " RMW_Writes, but only received: " << m_atomic_writes << endl; 475 assert(false); 476 } 477 ctype = CacheRequestType_ST; 478 break; 479 case RubyRequestType_Locked_Read: 480 case RubyRequestType_Locked_Write: 481 ctype = CacheRequestType_ATOMIC; 482 break; 483 case RubyRequestType_RMW_Read: 484 assert(m_atomic_writes == 0); 485 m_atomic_reads++; 486 ctype = CacheRequestType_ATOMIC; 487 break; 488 case RubyRequestType_RMW_Write: 489 assert(m_atomic_reads > 0); 490 assert(m_atomic_writes < m_atomic_reads); 491 m_atomic_writes++; 492 if (m_atomic_reads == m_atomic_writes) { 493 m_atomic_reads = 0; 494 m_atomic_writes = 0; 495 } 496 ctype = CacheRequestType_ATOMIC; 497 break; 498 default: 499 assert(0); 500 } 501 AccessModeType amtype; 502 switch(request.access_mode){ 503 case RubyAccessMode_User: 504 amtype = AccessModeType_UserMode; 505 break; 506 case RubyAccessMode_Supervisor: 507 amtype = AccessModeType_SupervisorMode; 508 break; 509 case RubyAccessMode_Device: 510 amtype = AccessModeType_UserMode; 511 break; 512 default: 513 assert(0); 514 } 515 Address line_addr(request.paddr); 516 line_addr.makeLineAddress(); 517 CacheMsg msg(line_addr, Address(request.paddr), ctype, Address(request.pc), amtype, request.len, PrefetchBit_No, request.proc_id); 518 519 if (Debug::getProtocolTrace()) { 520 g_system_ptr->getProfiler()->profileTransition("Seq", m_version, Address(request.paddr), 521 "", "Begin", "", RubyRequestType_to_string(request.type)); 522 } 523 524 if (g_system_ptr->getTracer()->traceEnabled()) { 525 g_system_ptr->getTracer()->traceRequest(m_name, line_addr, Address(request.pc), 526 request.type, g_eventQueue_ptr->getTime()); 527 } 528 529 Time latency = 0; // initialzed to an null value 530 531 if (request.type == RubyRequestType_IFETCH) 532 latency = m_instCache_ptr->getLatency(); 533 else 534 latency = m_dataCache_ptr->getLatency(); 535 536 // Send the message to the cache controller 537 assert(latency > 0); 538 539 540 m_mandatory_q_ptr->enqueue(msg, latency); 541} 542/* 543bool Sequencer::tryCacheAccess(const Address& addr, CacheRequestType type, 544 AccessModeType access_mode, 545 int size, DataBlock*& data_ptr) { 546 if (type == CacheRequestType_IFETCH) { 547 return m_instCache_ptr->tryCacheAccess(line_address(addr), type, data_ptr); 548 } else { 549 return m_dataCache_ptr->tryCacheAccess(line_address(addr), type, data_ptr); 550 } 551} 552*/ 553 554void Sequencer::print(ostream& out) const { 555 out << "[Sequencer: " << m_version 556 << ", outstanding requests: " << m_outstanding_count; 557 558 out << ", read request table: " << m_readRequestTable 559 << ", write request table: " << m_writeRequestTable; 560 out << "]"; 561} 562 563// this can be called from setState whenever coherence permissions are upgraded 564// when invoked, coherence violations will be checked for the given block 565void Sequencer::checkCoherence(const Address& addr) { 566#ifdef CHECK_COHERENCE 567 g_system_ptr->checkGlobalCoherenceInvariant(addr); 568#endif 569} 570 571