43#include "mem/ruby/common/Global.hh" 44#include "mem/ruby/profiler/Profiler.hh" 45#include "mem/ruby/slicc_interface/RubyRequest.hh" 46#include "mem/ruby/system/Sequencer.hh" 47#include "mem/ruby/system/System.hh" 48#include "mem/packet.hh" 49 50using namespace std; 51 52Sequencer * 53RubySequencerParams::create() 54{ 55 return new Sequencer(this); 56} 57 58Sequencer::Sequencer(const Params *p) 59 : RubyPort(p), deadlockCheckEvent(this) 60{ 61 m_store_waiting_on_load_cycles = 0; 62 m_store_waiting_on_store_cycles = 0; 63 m_load_waiting_on_store_cycles = 0; 64 m_load_waiting_on_load_cycles = 0; 65 66 m_outstanding_count = 0; 67 68 m_instCache_ptr = p->icache; 69 m_dataCache_ptr = p->dcache; 70 m_max_outstanding_requests = p->max_outstanding_requests; 71 m_deadlock_threshold = p->deadlock_threshold; 72 73 assert(m_max_outstanding_requests > 0); 74 assert(m_deadlock_threshold > 0); 75 assert(m_instCache_ptr != NULL); 76 assert(m_dataCache_ptr != NULL); 77 78 m_usingNetworkTester = p->using_network_tester; 79} 80 81Sequencer::~Sequencer() 82{ 83} 84 85void 86Sequencer::wakeup() 87{ 88 assert(getDrainState() != Drainable::Draining); 89 90 // Check for deadlock of any of the requests 91 Cycles current_time = curCycle(); 92 93 // Check across all outstanding requests 94 int total_outstanding = 0; 95 96 RequestTable::iterator read = m_readRequestTable.begin(); 97 RequestTable::iterator read_end = m_readRequestTable.end(); 98 for (; read != read_end; ++read) { 99 SequencerRequest* request = read->second; 100 if (current_time - request->issue_time < m_deadlock_threshold) 101 continue; 102 103 panic("Possible Deadlock detected. Aborting!\n" 104 "version: %d request.paddr: 0x%x m_readRequestTable: %d " 105 "current time: %u issue_time: %d difference: %d\n", m_version, 106 Address(request->pkt->getAddr()), m_readRequestTable.size(), 107 current_time * clockPeriod(), request->issue_time * clockPeriod(), 108 (current_time * clockPeriod()) - (request->issue_time * clockPeriod())); 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 panic("Possible Deadlock detected. Aborting!\n" 119 "version: %d request.paddr: 0x%x m_writeRequestTable: %d " 120 "current time: %u issue_time: %d difference: %d\n", m_version, 121 Address(request->pkt->getAddr()), m_writeRequestTable.size(), 122 current_time * clockPeriod(), request->issue_time * clockPeriod(), 123 (current_time * clockPeriod()) - (request->issue_time * clockPeriod())); 124 } 125 126 total_outstanding += m_writeRequestTable.size(); 127 total_outstanding += m_readRequestTable.size(); 128 129 assert(m_outstanding_count == total_outstanding); 130 131 if (m_outstanding_count > 0) { 132 // If there are still outstanding requests, keep checking 133 schedule(deadlockCheckEvent, clockEdge(m_deadlock_threshold)); 134 } 135} 136 137void 138Sequencer::printStats(ostream & out) const 139{ 140 out << "Sequencer: " << m_name << endl 141 << " store_waiting_on_load_cycles: " 142 << m_store_waiting_on_load_cycles << endl 143 << " store_waiting_on_store_cycles: " 144 << m_store_waiting_on_store_cycles << endl 145 << " load_waiting_on_load_cycles: " 146 << m_load_waiting_on_load_cycles << endl 147 << " load_waiting_on_store_cycles: " 148 << m_load_waiting_on_store_cycles << endl; 149} 150 151void 152Sequencer::printProgress(ostream& out) const 153{ 154#if 0 155 int total_demand = 0; 156 out << "Sequencer Stats Version " << m_version << endl; 157 out << "Current time = " << g_system_ptr->getTime() << endl; 158 out << "---------------" << endl; 159 out << "outstanding requests" << endl; 160 161 out << "proc " << m_Read 162 << " version Requests = " << m_readRequestTable.size() << endl; 163 164 // print the request table 165 RequestTable::iterator read = m_readRequestTable.begin(); 166 RequestTable::iterator read_end = m_readRequestTable.end(); 167 for (; read != read_end; ++read) { 168 SequencerRequest* request = read->second; 169 out << "\tRequest[ " << i << " ] = " << request->type 170 << " Address " << rkeys[i] 171 << " Posted " << request->issue_time 172 << " PF " << PrefetchBit_No << endl; 173 total_demand++; 174 } 175 176 out << "proc " << m_version 177 << " Write Requests = " << m_writeRequestTable.size << endl; 178 179 // print the request table 180 RequestTable::iterator write = m_writeRequestTable.begin(); 181 RequestTable::iterator write_end = m_writeRequestTable.end(); 182 for (; write != write_end; ++write) { 183 SequencerRequest* request = write->second; 184 out << "\tRequest[ " << i << " ] = " << request.getType() 185 << " Address " << wkeys[i] 186 << " Posted " << request.getTime() 187 << " PF " << request.getPrefetch() << endl; 188 if (request.getPrefetch() == PrefetchBit_No) { 189 total_demand++; 190 } 191 } 192 193 out << endl; 194 195 out << "Total Number Outstanding: " << m_outstanding_count << endl 196 << "Total Number Demand : " << total_demand << endl 197 << "Total Number Prefetches : " << m_outstanding_count - total_demand 198 << endl << endl << endl; 199#endif 200} 201 202// Insert the request on the correct request table. Return true if 203// the entry was already present. 204RequestStatus 205Sequencer::insertRequest(PacketPtr pkt, RubyRequestType request_type) 206{ 207 assert(m_outstanding_count == 208 (m_writeRequestTable.size() + m_readRequestTable.size())); 209 210 // See if we should schedule a deadlock check 211 if (!deadlockCheckEvent.scheduled() && 212 getDrainState() != Drainable::Draining) { 213 schedule(deadlockCheckEvent, clockEdge(m_deadlock_threshold)); 214 } 215 216 Address line_addr(pkt->getAddr()); 217 line_addr.makeLineAddress(); 218 // Create a default entry, mapping the address to NULL, the cast is 219 // there to make gcc 4.4 happy 220 RequestTable::value_type default_entry(line_addr, 221 (SequencerRequest*) NULL); 222 223 if ((request_type == RubyRequestType_ST) || 224 (request_type == RubyRequestType_RMW_Read) || 225 (request_type == RubyRequestType_RMW_Write) || 226 (request_type == RubyRequestType_Load_Linked) || 227 (request_type == RubyRequestType_Store_Conditional) || 228 (request_type == RubyRequestType_Locked_RMW_Read) || 229 (request_type == RubyRequestType_Locked_RMW_Write) || 230 (request_type == RubyRequestType_FLUSH)) { 231 232 // Check if there is any outstanding read request for the same 233 // cache line. 234 if (m_readRequestTable.count(line_addr) > 0) { 235 m_store_waiting_on_load_cycles++; 236 return RequestStatus_Aliased; 237 } 238 239 pair<RequestTable::iterator, bool> r = 240 m_writeRequestTable.insert(default_entry); 241 if (r.second) { 242 RequestTable::iterator i = r.first; 243 i->second = new SequencerRequest(pkt, request_type, curCycle()); 244 m_outstanding_count++; 245 } else { 246 // There is an outstanding write request for the cache line 247 m_store_waiting_on_store_cycles++; 248 return RequestStatus_Aliased; 249 } 250 } else { 251 // Check if there is any outstanding write request for the same 252 // cache line. 253 if (m_writeRequestTable.count(line_addr) > 0) { 254 m_load_waiting_on_store_cycles++; 255 return RequestStatus_Aliased; 256 } 257 258 pair<RequestTable::iterator, bool> r = 259 m_readRequestTable.insert(default_entry); 260 261 if (r.second) { 262 RequestTable::iterator i = r.first; 263 i->second = new SequencerRequest(pkt, request_type, curCycle()); 264 m_outstanding_count++; 265 } else { 266 // There is an outstanding read request for the cache line 267 m_load_waiting_on_load_cycles++; 268 return RequestStatus_Aliased; 269 } 270 } 271 272 g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count); 273 assert(m_outstanding_count == 274 (m_writeRequestTable.size() + m_readRequestTable.size())); 275 276 return RequestStatus_Ready; 277} 278 279void 280Sequencer::markRemoved() 281{ 282 m_outstanding_count--; 283 assert(m_outstanding_count == 284 m_writeRequestTable.size() + m_readRequestTable.size()); 285} 286 287void 288Sequencer::removeRequest(SequencerRequest* srequest) 289{ 290 assert(m_outstanding_count == 291 m_writeRequestTable.size() + m_readRequestTable.size()); 292 293 Address line_addr(srequest->pkt->getAddr()); 294 line_addr.makeLineAddress(); 295 if ((srequest->m_type == RubyRequestType_ST) || 296 (srequest->m_type == RubyRequestType_RMW_Read) || 297 (srequest->m_type == RubyRequestType_RMW_Write) || 298 (srequest->m_type == RubyRequestType_Load_Linked) || 299 (srequest->m_type == RubyRequestType_Store_Conditional) || 300 (srequest->m_type == RubyRequestType_Locked_RMW_Read) || 301 (srequest->m_type == RubyRequestType_Locked_RMW_Write)) { 302 m_writeRequestTable.erase(line_addr); 303 } else { 304 m_readRequestTable.erase(line_addr); 305 } 306 307 markRemoved(); 308} 309 310bool 311Sequencer::handleLlsc(const Address& address, SequencerRequest* request) 312{ 313 // 314 // The success flag indicates whether the LLSC operation was successful. 315 // LL ops will always succeed, but SC may fail if the cache line is no 316 // longer locked. 317 // 318 bool success = true; 319 if (request->m_type == RubyRequestType_Store_Conditional) { 320 if (!m_dataCache_ptr->isLocked(address, m_version)) { 321 // 322 // For failed SC requests, indicate the failure to the cpu by 323 // setting the extra data to zero. 324 // 325 request->pkt->req->setExtraData(0); 326 success = false; 327 } else { 328 // 329 // For successful SC requests, indicate the success to the cpu by 330 // setting the extra data to one. 331 // 332 request->pkt->req->setExtraData(1); 333 } 334 // 335 // Independent of success, all SC operations must clear the lock 336 // 337 m_dataCache_ptr->clearLocked(address); 338 } else if (request->m_type == RubyRequestType_Load_Linked) { 339 // 340 // Note: To fully follow Alpha LLSC semantics, should the LL clear any 341 // previously locked cache lines? 342 // 343 m_dataCache_ptr->setLocked(address, m_version); 344 } else if ((m_dataCache_ptr->isTagPresent(address)) && 345 (m_dataCache_ptr->isLocked(address, m_version))) { 346 // 347 // Normal writes should clear the locked address 348 // 349 m_dataCache_ptr->clearLocked(address); 350 } 351 return success; 352} 353 354void 355Sequencer::writeCallback(const Address& address, DataBlock& data) 356{ 357 writeCallback(address, GenericMachineType_NULL, data); 358} 359 360void 361Sequencer::writeCallback(const Address& address, 362 GenericMachineType mach, 363 DataBlock& data) 364{ 365 writeCallback(address, mach, data, Cycles(0), Cycles(0), Cycles(0)); 366} 367 368void 369Sequencer::writeCallback(const Address& address, 370 GenericMachineType mach, 371 DataBlock& data, 372 Cycles initialRequestTime, 373 Cycles forwardRequestTime, 374 Cycles firstResponseTime) 375{ 376 assert(address == line_address(address)); 377 assert(m_writeRequestTable.count(line_address(address))); 378 379 RequestTable::iterator i = m_writeRequestTable.find(address); 380 assert(i != m_writeRequestTable.end()); 381 SequencerRequest* request = i->second; 382 383 m_writeRequestTable.erase(i); 384 markRemoved(); 385 386 assert((request->m_type == RubyRequestType_ST) || 387 (request->m_type == RubyRequestType_ATOMIC) || 388 (request->m_type == RubyRequestType_RMW_Read) || 389 (request->m_type == RubyRequestType_RMW_Write) || 390 (request->m_type == RubyRequestType_Load_Linked) || 391 (request->m_type == RubyRequestType_Store_Conditional) || 392 (request->m_type == RubyRequestType_Locked_RMW_Read) || 393 (request->m_type == RubyRequestType_Locked_RMW_Write) || 394 (request->m_type == RubyRequestType_FLUSH)); 395 396 397 // 398 // For Alpha, properly handle LL, SC, and write requests with respect to 399 // locked cache blocks. 400 // 401 // Not valid for Network_test protocl 402 // 403 bool success = true; 404 if(!m_usingNetworkTester) 405 success = handleLlsc(address, request); 406 407 if (request->m_type == RubyRequestType_Locked_RMW_Read) { 408 m_controller->blockOnQueue(address, m_mandatory_q_ptr); 409 } else if (request->m_type == RubyRequestType_Locked_RMW_Write) { 410 m_controller->unblock(address); 411 } 412 413 hitCallback(request, mach, data, success, 414 initialRequestTime, forwardRequestTime, firstResponseTime); 415} 416 417void 418Sequencer::readCallback(const Address& address, DataBlock& data) 419{ 420 readCallback(address, GenericMachineType_NULL, data); 421} 422 423void 424Sequencer::readCallback(const Address& address, 425 GenericMachineType mach, 426 DataBlock& data) 427{ 428 readCallback(address, mach, data, Cycles(0), Cycles(0), Cycles(0)); 429} 430 431void 432Sequencer::readCallback(const Address& address, 433 GenericMachineType mach, 434 DataBlock& data, 435 Cycles initialRequestTime, 436 Cycles forwardRequestTime, 437 Cycles firstResponseTime) 438{ 439 assert(address == line_address(address)); 440 assert(m_readRequestTable.count(line_address(address))); 441 442 RequestTable::iterator i = m_readRequestTable.find(address); 443 assert(i != m_readRequestTable.end()); 444 SequencerRequest* request = i->second; 445 446 m_readRequestTable.erase(i); 447 markRemoved(); 448 449 assert((request->m_type == RubyRequestType_LD) || 450 (request->m_type == RubyRequestType_IFETCH)); 451 452 hitCallback(request, mach, data, true, 453 initialRequestTime, forwardRequestTime, firstResponseTime); 454} 455 456void 457Sequencer::hitCallback(SequencerRequest* srequest, 458 GenericMachineType mach, 459 DataBlock& data, 460 bool success, 461 Cycles initialRequestTime, 462 Cycles forwardRequestTime, 463 Cycles firstResponseTime) 464{ 465 PacketPtr pkt = srequest->pkt; 466 Address request_address(pkt->getAddr()); 467 Address request_line_address(pkt->getAddr()); 468 request_line_address.makeLineAddress(); 469 RubyRequestType type = srequest->m_type; 470 Cycles issued_time = srequest->issue_time; 471 472 // Set this cache entry to the most recently used 473 if (type == RubyRequestType_IFETCH) { 474 m_instCache_ptr->setMRU(request_line_address); 475 } else { 476 m_dataCache_ptr->setMRU(request_line_address); 477 } 478 479 assert(curCycle() >= issued_time); 480 Cycles miss_latency = curCycle() - issued_time; 481 482 // Profile the miss latency for all non-zero demand misses 483 if (miss_latency != 0) { 484 g_system_ptr->getProfiler()->missLatency(miss_latency, type, mach); 485 486 if (mach == GenericMachineType_L1Cache_wCC) { 487 g_system_ptr->getProfiler()->missLatencyWcc(issued_time, 488 initialRequestTime, forwardRequestTime, 489 firstResponseTime, curCycle()); 490 } 491 492 if (mach == GenericMachineType_Directory) { 493 g_system_ptr->getProfiler()->missLatencyDir(issued_time, 494 initialRequestTime, forwardRequestTime, 495 firstResponseTime, curCycle()); 496 } 497 498 DPRINTFR(ProtocolTrace, "%15s %3s %10s%20s %6s>%-6s %s %d cycles\n", 499 curTick(), m_version, "Seq", 500 success ? "Done" : "SC_Failed", "", "", 501 request_address, miss_latency); 502 } 503 504 // update the data 505 if (g_system_ptr->m_warmup_enabled) { 506 assert(pkt->getPtr<uint8_t>(false) != NULL); 507 data.setData(pkt->getPtr<uint8_t>(false), 508 request_address.getOffset(), pkt->getSize()); 509 } else if (pkt->getPtr<uint8_t>(true) != NULL) { 510 if ((type == RubyRequestType_LD) || 511 (type == RubyRequestType_IFETCH) || 512 (type == RubyRequestType_RMW_Read) || 513 (type == RubyRequestType_Locked_RMW_Read) || 514 (type == RubyRequestType_Load_Linked)) { 515 memcpy(pkt->getPtr<uint8_t>(true), 516 data.getData(request_address.getOffset(), pkt->getSize()), 517 pkt->getSize()); 518 } else { 519 data.setData(pkt->getPtr<uint8_t>(true), 520 request_address.getOffset(), pkt->getSize()); 521 } 522 } else { 523 DPRINTF(MemoryAccess, 524 "WARNING. Data not transfered from Ruby to M5 for type %s\n", 525 RubyRequestType_to_string(type)); 526 } 527 528 // If using the RubyTester, update the RubyTester sender state's 529 // subBlock with the recieved data. The tester will later access 530 // this state. 531 // Note: RubyPort will access it's sender state before the 532 // RubyTester. 533 if (m_usingRubyTester) { 534 RubyPort::SenderState *requestSenderState = 535 safe_cast<RubyPort::SenderState*>(pkt->senderState); 536 RubyTester::SenderState* testerSenderState = 537 safe_cast<RubyTester::SenderState*>(requestSenderState->saved); 538 testerSenderState->subBlock->mergeFrom(data); 539 } 540 541 delete srequest; 542 543 if (g_system_ptr->m_warmup_enabled) { 544 delete pkt; 545 g_system_ptr->m_cache_recorder->enqueueNextFetchRequest(); 546 } else if (g_system_ptr->m_cooldown_enabled) { 547 delete pkt; 548 g_system_ptr->m_cache_recorder->enqueueNextFlushRequest(); 549 } else { 550 ruby_hit_callback(pkt); 551 } 552} 553 554bool 555Sequencer::empty() const 556{ 557 return m_writeRequestTable.empty() && m_readRequestTable.empty(); 558} 559 560RequestStatus 561Sequencer::makeRequest(PacketPtr pkt) 562{ 563 if (m_outstanding_count >= m_max_outstanding_requests) { 564 return RequestStatus_BufferFull; 565 } 566 567 RubyRequestType primary_type = RubyRequestType_NULL; 568 RubyRequestType secondary_type = RubyRequestType_NULL; 569 570 if (pkt->isLLSC()) { 571 // 572 // Alpha LL/SC instructions need to be handled carefully by the cache 573 // coherence protocol to ensure they follow the proper semantics. In 574 // particular, by identifying the operations as atomic, the protocol 575 // should understand that migratory sharing optimizations should not 576 // be performed (i.e. a load between the LL and SC should not steal 577 // away exclusive permission). 578 // 579 if (pkt->isWrite()) { 580 DPRINTF(RubySequencer, "Issuing SC\n"); 581 primary_type = RubyRequestType_Store_Conditional; 582 } else { 583 DPRINTF(RubySequencer, "Issuing LL\n"); 584 assert(pkt->isRead()); 585 primary_type = RubyRequestType_Load_Linked; 586 } 587 secondary_type = RubyRequestType_ATOMIC; 588 } else if (pkt->req->isLocked()) { 589 // 590 // x86 locked instructions are translated to store cache coherence 591 // requests because these requests should always be treated as read 592 // exclusive operations and should leverage any migratory sharing 593 // optimization built into the protocol. 594 // 595 if (pkt->isWrite()) { 596 DPRINTF(RubySequencer, "Issuing Locked RMW Write\n"); 597 primary_type = RubyRequestType_Locked_RMW_Write; 598 } else { 599 DPRINTF(RubySequencer, "Issuing Locked RMW Read\n"); 600 assert(pkt->isRead()); 601 primary_type = RubyRequestType_Locked_RMW_Read; 602 } 603 secondary_type = RubyRequestType_ST; 604 } else { 605 if (pkt->isRead()) { 606 if (pkt->req->isInstFetch()) { 607 primary_type = secondary_type = RubyRequestType_IFETCH; 608 } else { 609#if THE_ISA == X86_ISA 610 uint32_t flags = pkt->req->getFlags(); 611 bool storeCheck = flags & 612 (TheISA::StoreCheck << TheISA::FlagShift); 613#else 614 bool storeCheck = false; 615#endif // X86_ISA 616 if (storeCheck) { 617 primary_type = RubyRequestType_RMW_Read; 618 secondary_type = RubyRequestType_ST; 619 } else { 620 primary_type = secondary_type = RubyRequestType_LD; 621 } 622 } 623 } else if (pkt->isWrite()) { 624 // 625 // Note: M5 packets do not differentiate ST from RMW_Write 626 // 627 primary_type = secondary_type = RubyRequestType_ST; 628 } else if (pkt->isFlush()) { 629 primary_type = secondary_type = RubyRequestType_FLUSH; 630 } else { 631 panic("Unsupported ruby packet type\n"); 632 } 633 } 634 635 RequestStatus status = insertRequest(pkt, primary_type); 636 if (status != RequestStatus_Ready) 637 return status; 638 639 issueRequest(pkt, secondary_type); 640 641 // TODO: issue hardware prefetches here 642 return RequestStatus_Issued; 643} 644 645void 646Sequencer::issueRequest(PacketPtr pkt, RubyRequestType secondary_type) 647{ 648 assert(pkt != NULL); 649 int proc_id = -1; 650 if (pkt->req->hasContextId()) { 651 proc_id = pkt->req->contextId(); 652 } 653 654 // If valid, copy the pc to the ruby request 655 Addr pc = 0; 656 if (pkt->req->hasPC()) { 657 pc = pkt->req->getPC(); 658 } 659
| 42#include "mem/ruby/common/Global.hh" 43#include "mem/ruby/profiler/Profiler.hh" 44#include "mem/ruby/slicc_interface/RubyRequest.hh" 45#include "mem/ruby/system/Sequencer.hh" 46#include "mem/ruby/system/System.hh" 47#include "mem/packet.hh" 48 49using namespace std; 50 51Sequencer * 52RubySequencerParams::create() 53{ 54 return new Sequencer(this); 55} 56 57Sequencer::Sequencer(const Params *p) 58 : RubyPort(p), deadlockCheckEvent(this) 59{ 60 m_store_waiting_on_load_cycles = 0; 61 m_store_waiting_on_store_cycles = 0; 62 m_load_waiting_on_store_cycles = 0; 63 m_load_waiting_on_load_cycles = 0; 64 65 m_outstanding_count = 0; 66 67 m_instCache_ptr = p->icache; 68 m_dataCache_ptr = p->dcache; 69 m_max_outstanding_requests = p->max_outstanding_requests; 70 m_deadlock_threshold = p->deadlock_threshold; 71 72 assert(m_max_outstanding_requests > 0); 73 assert(m_deadlock_threshold > 0); 74 assert(m_instCache_ptr != NULL); 75 assert(m_dataCache_ptr != NULL); 76 77 m_usingNetworkTester = p->using_network_tester; 78} 79 80Sequencer::~Sequencer() 81{ 82} 83 84void 85Sequencer::wakeup() 86{ 87 assert(getDrainState() != Drainable::Draining); 88 89 // Check for deadlock of any of the requests 90 Cycles current_time = curCycle(); 91 92 // Check across all outstanding requests 93 int total_outstanding = 0; 94 95 RequestTable::iterator read = m_readRequestTable.begin(); 96 RequestTable::iterator read_end = m_readRequestTable.end(); 97 for (; read != read_end; ++read) { 98 SequencerRequest* request = read->second; 99 if (current_time - request->issue_time < m_deadlock_threshold) 100 continue; 101 102 panic("Possible Deadlock detected. Aborting!\n" 103 "version: %d request.paddr: 0x%x m_readRequestTable: %d " 104 "current time: %u issue_time: %d difference: %d\n", m_version, 105 Address(request->pkt->getAddr()), m_readRequestTable.size(), 106 current_time * clockPeriod(), request->issue_time * clockPeriod(), 107 (current_time * clockPeriod()) - (request->issue_time * clockPeriod())); 108 } 109 110 RequestTable::iterator write = m_writeRequestTable.begin(); 111 RequestTable::iterator write_end = m_writeRequestTable.end(); 112 for (; write != write_end; ++write) { 113 SequencerRequest* request = write->second; 114 if (current_time - request->issue_time < m_deadlock_threshold) 115 continue; 116 117 panic("Possible Deadlock detected. Aborting!\n" 118 "version: %d request.paddr: 0x%x m_writeRequestTable: %d " 119 "current time: %u issue_time: %d difference: %d\n", m_version, 120 Address(request->pkt->getAddr()), m_writeRequestTable.size(), 121 current_time * clockPeriod(), request->issue_time * clockPeriod(), 122 (current_time * clockPeriod()) - (request->issue_time * clockPeriod())); 123 } 124 125 total_outstanding += m_writeRequestTable.size(); 126 total_outstanding += m_readRequestTable.size(); 127 128 assert(m_outstanding_count == total_outstanding); 129 130 if (m_outstanding_count > 0) { 131 // If there are still outstanding requests, keep checking 132 schedule(deadlockCheckEvent, clockEdge(m_deadlock_threshold)); 133 } 134} 135 136void 137Sequencer::printStats(ostream & out) const 138{ 139 out << "Sequencer: " << m_name << endl 140 << " store_waiting_on_load_cycles: " 141 << m_store_waiting_on_load_cycles << endl 142 << " store_waiting_on_store_cycles: " 143 << m_store_waiting_on_store_cycles << endl 144 << " load_waiting_on_load_cycles: " 145 << m_load_waiting_on_load_cycles << endl 146 << " load_waiting_on_store_cycles: " 147 << m_load_waiting_on_store_cycles << endl; 148} 149 150void 151Sequencer::printProgress(ostream& out) const 152{ 153#if 0 154 int total_demand = 0; 155 out << "Sequencer Stats Version " << m_version << endl; 156 out << "Current time = " << g_system_ptr->getTime() << endl; 157 out << "---------------" << endl; 158 out << "outstanding requests" << endl; 159 160 out << "proc " << m_Read 161 << " version Requests = " << m_readRequestTable.size() << endl; 162 163 // print the request table 164 RequestTable::iterator read = m_readRequestTable.begin(); 165 RequestTable::iterator read_end = m_readRequestTable.end(); 166 for (; read != read_end; ++read) { 167 SequencerRequest* request = read->second; 168 out << "\tRequest[ " << i << " ] = " << request->type 169 << " Address " << rkeys[i] 170 << " Posted " << request->issue_time 171 << " PF " << PrefetchBit_No << endl; 172 total_demand++; 173 } 174 175 out << "proc " << m_version 176 << " Write Requests = " << m_writeRequestTable.size << endl; 177 178 // print the request table 179 RequestTable::iterator write = m_writeRequestTable.begin(); 180 RequestTable::iterator write_end = m_writeRequestTable.end(); 181 for (; write != write_end; ++write) { 182 SequencerRequest* request = write->second; 183 out << "\tRequest[ " << i << " ] = " << request.getType() 184 << " Address " << wkeys[i] 185 << " Posted " << request.getTime() 186 << " PF " << request.getPrefetch() << endl; 187 if (request.getPrefetch() == PrefetchBit_No) { 188 total_demand++; 189 } 190 } 191 192 out << endl; 193 194 out << "Total Number Outstanding: " << m_outstanding_count << endl 195 << "Total Number Demand : " << total_demand << endl 196 << "Total Number Prefetches : " << m_outstanding_count - total_demand 197 << endl << endl << endl; 198#endif 199} 200 201// Insert the request on the correct request table. Return true if 202// the entry was already present. 203RequestStatus 204Sequencer::insertRequest(PacketPtr pkt, RubyRequestType request_type) 205{ 206 assert(m_outstanding_count == 207 (m_writeRequestTable.size() + m_readRequestTable.size())); 208 209 // See if we should schedule a deadlock check 210 if (!deadlockCheckEvent.scheduled() && 211 getDrainState() != Drainable::Draining) { 212 schedule(deadlockCheckEvent, clockEdge(m_deadlock_threshold)); 213 } 214 215 Address line_addr(pkt->getAddr()); 216 line_addr.makeLineAddress(); 217 // Create a default entry, mapping the address to NULL, the cast is 218 // there to make gcc 4.4 happy 219 RequestTable::value_type default_entry(line_addr, 220 (SequencerRequest*) NULL); 221 222 if ((request_type == RubyRequestType_ST) || 223 (request_type == RubyRequestType_RMW_Read) || 224 (request_type == RubyRequestType_RMW_Write) || 225 (request_type == RubyRequestType_Load_Linked) || 226 (request_type == RubyRequestType_Store_Conditional) || 227 (request_type == RubyRequestType_Locked_RMW_Read) || 228 (request_type == RubyRequestType_Locked_RMW_Write) || 229 (request_type == RubyRequestType_FLUSH)) { 230 231 // Check if there is any outstanding read request for the same 232 // cache line. 233 if (m_readRequestTable.count(line_addr) > 0) { 234 m_store_waiting_on_load_cycles++; 235 return RequestStatus_Aliased; 236 } 237 238 pair<RequestTable::iterator, bool> r = 239 m_writeRequestTable.insert(default_entry); 240 if (r.second) { 241 RequestTable::iterator i = r.first; 242 i->second = new SequencerRequest(pkt, request_type, curCycle()); 243 m_outstanding_count++; 244 } else { 245 // There is an outstanding write request for the cache line 246 m_store_waiting_on_store_cycles++; 247 return RequestStatus_Aliased; 248 } 249 } else { 250 // Check if there is any outstanding write request for the same 251 // cache line. 252 if (m_writeRequestTable.count(line_addr) > 0) { 253 m_load_waiting_on_store_cycles++; 254 return RequestStatus_Aliased; 255 } 256 257 pair<RequestTable::iterator, bool> r = 258 m_readRequestTable.insert(default_entry); 259 260 if (r.second) { 261 RequestTable::iterator i = r.first; 262 i->second = new SequencerRequest(pkt, request_type, curCycle()); 263 m_outstanding_count++; 264 } else { 265 // There is an outstanding read request for the cache line 266 m_load_waiting_on_load_cycles++; 267 return RequestStatus_Aliased; 268 } 269 } 270 271 g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count); 272 assert(m_outstanding_count == 273 (m_writeRequestTable.size() + m_readRequestTable.size())); 274 275 return RequestStatus_Ready; 276} 277 278void 279Sequencer::markRemoved() 280{ 281 m_outstanding_count--; 282 assert(m_outstanding_count == 283 m_writeRequestTable.size() + m_readRequestTable.size()); 284} 285 286void 287Sequencer::removeRequest(SequencerRequest* srequest) 288{ 289 assert(m_outstanding_count == 290 m_writeRequestTable.size() + m_readRequestTable.size()); 291 292 Address line_addr(srequest->pkt->getAddr()); 293 line_addr.makeLineAddress(); 294 if ((srequest->m_type == RubyRequestType_ST) || 295 (srequest->m_type == RubyRequestType_RMW_Read) || 296 (srequest->m_type == RubyRequestType_RMW_Write) || 297 (srequest->m_type == RubyRequestType_Load_Linked) || 298 (srequest->m_type == RubyRequestType_Store_Conditional) || 299 (srequest->m_type == RubyRequestType_Locked_RMW_Read) || 300 (srequest->m_type == RubyRequestType_Locked_RMW_Write)) { 301 m_writeRequestTable.erase(line_addr); 302 } else { 303 m_readRequestTable.erase(line_addr); 304 } 305 306 markRemoved(); 307} 308 309bool 310Sequencer::handleLlsc(const Address& address, SequencerRequest* request) 311{ 312 // 313 // The success flag indicates whether the LLSC operation was successful. 314 // LL ops will always succeed, but SC may fail if the cache line is no 315 // longer locked. 316 // 317 bool success = true; 318 if (request->m_type == RubyRequestType_Store_Conditional) { 319 if (!m_dataCache_ptr->isLocked(address, m_version)) { 320 // 321 // For failed SC requests, indicate the failure to the cpu by 322 // setting the extra data to zero. 323 // 324 request->pkt->req->setExtraData(0); 325 success = false; 326 } else { 327 // 328 // For successful SC requests, indicate the success to the cpu by 329 // setting the extra data to one. 330 // 331 request->pkt->req->setExtraData(1); 332 } 333 // 334 // Independent of success, all SC operations must clear the lock 335 // 336 m_dataCache_ptr->clearLocked(address); 337 } else if (request->m_type == RubyRequestType_Load_Linked) { 338 // 339 // Note: To fully follow Alpha LLSC semantics, should the LL clear any 340 // previously locked cache lines? 341 // 342 m_dataCache_ptr->setLocked(address, m_version); 343 } else if ((m_dataCache_ptr->isTagPresent(address)) && 344 (m_dataCache_ptr->isLocked(address, m_version))) { 345 // 346 // Normal writes should clear the locked address 347 // 348 m_dataCache_ptr->clearLocked(address); 349 } 350 return success; 351} 352 353void 354Sequencer::writeCallback(const Address& address, DataBlock& data) 355{ 356 writeCallback(address, GenericMachineType_NULL, data); 357} 358 359void 360Sequencer::writeCallback(const Address& address, 361 GenericMachineType mach, 362 DataBlock& data) 363{ 364 writeCallback(address, mach, data, Cycles(0), Cycles(0), Cycles(0)); 365} 366 367void 368Sequencer::writeCallback(const Address& address, 369 GenericMachineType mach, 370 DataBlock& data, 371 Cycles initialRequestTime, 372 Cycles forwardRequestTime, 373 Cycles firstResponseTime) 374{ 375 assert(address == line_address(address)); 376 assert(m_writeRequestTable.count(line_address(address))); 377 378 RequestTable::iterator i = m_writeRequestTable.find(address); 379 assert(i != m_writeRequestTable.end()); 380 SequencerRequest* request = i->second; 381 382 m_writeRequestTable.erase(i); 383 markRemoved(); 384 385 assert((request->m_type == RubyRequestType_ST) || 386 (request->m_type == RubyRequestType_ATOMIC) || 387 (request->m_type == RubyRequestType_RMW_Read) || 388 (request->m_type == RubyRequestType_RMW_Write) || 389 (request->m_type == RubyRequestType_Load_Linked) || 390 (request->m_type == RubyRequestType_Store_Conditional) || 391 (request->m_type == RubyRequestType_Locked_RMW_Read) || 392 (request->m_type == RubyRequestType_Locked_RMW_Write) || 393 (request->m_type == RubyRequestType_FLUSH)); 394 395 396 // 397 // For Alpha, properly handle LL, SC, and write requests with respect to 398 // locked cache blocks. 399 // 400 // Not valid for Network_test protocl 401 // 402 bool success = true; 403 if(!m_usingNetworkTester) 404 success = handleLlsc(address, request); 405 406 if (request->m_type == RubyRequestType_Locked_RMW_Read) { 407 m_controller->blockOnQueue(address, m_mandatory_q_ptr); 408 } else if (request->m_type == RubyRequestType_Locked_RMW_Write) { 409 m_controller->unblock(address); 410 } 411 412 hitCallback(request, mach, data, success, 413 initialRequestTime, forwardRequestTime, firstResponseTime); 414} 415 416void 417Sequencer::readCallback(const Address& address, DataBlock& data) 418{ 419 readCallback(address, GenericMachineType_NULL, data); 420} 421 422void 423Sequencer::readCallback(const Address& address, 424 GenericMachineType mach, 425 DataBlock& data) 426{ 427 readCallback(address, mach, data, Cycles(0), Cycles(0), Cycles(0)); 428} 429 430void 431Sequencer::readCallback(const Address& address, 432 GenericMachineType mach, 433 DataBlock& data, 434 Cycles initialRequestTime, 435 Cycles forwardRequestTime, 436 Cycles firstResponseTime) 437{ 438 assert(address == line_address(address)); 439 assert(m_readRequestTable.count(line_address(address))); 440 441 RequestTable::iterator i = m_readRequestTable.find(address); 442 assert(i != m_readRequestTable.end()); 443 SequencerRequest* request = i->second; 444 445 m_readRequestTable.erase(i); 446 markRemoved(); 447 448 assert((request->m_type == RubyRequestType_LD) || 449 (request->m_type == RubyRequestType_IFETCH)); 450 451 hitCallback(request, mach, data, true, 452 initialRequestTime, forwardRequestTime, firstResponseTime); 453} 454 455void 456Sequencer::hitCallback(SequencerRequest* srequest, 457 GenericMachineType mach, 458 DataBlock& data, 459 bool success, 460 Cycles initialRequestTime, 461 Cycles forwardRequestTime, 462 Cycles firstResponseTime) 463{ 464 PacketPtr pkt = srequest->pkt; 465 Address request_address(pkt->getAddr()); 466 Address request_line_address(pkt->getAddr()); 467 request_line_address.makeLineAddress(); 468 RubyRequestType type = srequest->m_type; 469 Cycles issued_time = srequest->issue_time; 470 471 // Set this cache entry to the most recently used 472 if (type == RubyRequestType_IFETCH) { 473 m_instCache_ptr->setMRU(request_line_address); 474 } else { 475 m_dataCache_ptr->setMRU(request_line_address); 476 } 477 478 assert(curCycle() >= issued_time); 479 Cycles miss_latency = curCycle() - issued_time; 480 481 // Profile the miss latency for all non-zero demand misses 482 if (miss_latency != 0) { 483 g_system_ptr->getProfiler()->missLatency(miss_latency, type, mach); 484 485 if (mach == GenericMachineType_L1Cache_wCC) { 486 g_system_ptr->getProfiler()->missLatencyWcc(issued_time, 487 initialRequestTime, forwardRequestTime, 488 firstResponseTime, curCycle()); 489 } 490 491 if (mach == GenericMachineType_Directory) { 492 g_system_ptr->getProfiler()->missLatencyDir(issued_time, 493 initialRequestTime, forwardRequestTime, 494 firstResponseTime, curCycle()); 495 } 496 497 DPRINTFR(ProtocolTrace, "%15s %3s %10s%20s %6s>%-6s %s %d cycles\n", 498 curTick(), m_version, "Seq", 499 success ? "Done" : "SC_Failed", "", "", 500 request_address, miss_latency); 501 } 502 503 // update the data 504 if (g_system_ptr->m_warmup_enabled) { 505 assert(pkt->getPtr<uint8_t>(false) != NULL); 506 data.setData(pkt->getPtr<uint8_t>(false), 507 request_address.getOffset(), pkt->getSize()); 508 } else if (pkt->getPtr<uint8_t>(true) != NULL) { 509 if ((type == RubyRequestType_LD) || 510 (type == RubyRequestType_IFETCH) || 511 (type == RubyRequestType_RMW_Read) || 512 (type == RubyRequestType_Locked_RMW_Read) || 513 (type == RubyRequestType_Load_Linked)) { 514 memcpy(pkt->getPtr<uint8_t>(true), 515 data.getData(request_address.getOffset(), pkt->getSize()), 516 pkt->getSize()); 517 } else { 518 data.setData(pkt->getPtr<uint8_t>(true), 519 request_address.getOffset(), pkt->getSize()); 520 } 521 } else { 522 DPRINTF(MemoryAccess, 523 "WARNING. Data not transfered from Ruby to M5 for type %s\n", 524 RubyRequestType_to_string(type)); 525 } 526 527 // If using the RubyTester, update the RubyTester sender state's 528 // subBlock with the recieved data. The tester will later access 529 // this state. 530 // Note: RubyPort will access it's sender state before the 531 // RubyTester. 532 if (m_usingRubyTester) { 533 RubyPort::SenderState *requestSenderState = 534 safe_cast<RubyPort::SenderState*>(pkt->senderState); 535 RubyTester::SenderState* testerSenderState = 536 safe_cast<RubyTester::SenderState*>(requestSenderState->saved); 537 testerSenderState->subBlock->mergeFrom(data); 538 } 539 540 delete srequest; 541 542 if (g_system_ptr->m_warmup_enabled) { 543 delete pkt; 544 g_system_ptr->m_cache_recorder->enqueueNextFetchRequest(); 545 } else if (g_system_ptr->m_cooldown_enabled) { 546 delete pkt; 547 g_system_ptr->m_cache_recorder->enqueueNextFlushRequest(); 548 } else { 549 ruby_hit_callback(pkt); 550 } 551} 552 553bool 554Sequencer::empty() const 555{ 556 return m_writeRequestTable.empty() && m_readRequestTable.empty(); 557} 558 559RequestStatus 560Sequencer::makeRequest(PacketPtr pkt) 561{ 562 if (m_outstanding_count >= m_max_outstanding_requests) { 563 return RequestStatus_BufferFull; 564 } 565 566 RubyRequestType primary_type = RubyRequestType_NULL; 567 RubyRequestType secondary_type = RubyRequestType_NULL; 568 569 if (pkt->isLLSC()) { 570 // 571 // Alpha LL/SC instructions need to be handled carefully by the cache 572 // coherence protocol to ensure they follow the proper semantics. In 573 // particular, by identifying the operations as atomic, the protocol 574 // should understand that migratory sharing optimizations should not 575 // be performed (i.e. a load between the LL and SC should not steal 576 // away exclusive permission). 577 // 578 if (pkt->isWrite()) { 579 DPRINTF(RubySequencer, "Issuing SC\n"); 580 primary_type = RubyRequestType_Store_Conditional; 581 } else { 582 DPRINTF(RubySequencer, "Issuing LL\n"); 583 assert(pkt->isRead()); 584 primary_type = RubyRequestType_Load_Linked; 585 } 586 secondary_type = RubyRequestType_ATOMIC; 587 } else if (pkt->req->isLocked()) { 588 // 589 // x86 locked instructions are translated to store cache coherence 590 // requests because these requests should always be treated as read 591 // exclusive operations and should leverage any migratory sharing 592 // optimization built into the protocol. 593 // 594 if (pkt->isWrite()) { 595 DPRINTF(RubySequencer, "Issuing Locked RMW Write\n"); 596 primary_type = RubyRequestType_Locked_RMW_Write; 597 } else { 598 DPRINTF(RubySequencer, "Issuing Locked RMW Read\n"); 599 assert(pkt->isRead()); 600 primary_type = RubyRequestType_Locked_RMW_Read; 601 } 602 secondary_type = RubyRequestType_ST; 603 } else { 604 if (pkt->isRead()) { 605 if (pkt->req->isInstFetch()) { 606 primary_type = secondary_type = RubyRequestType_IFETCH; 607 } else { 608#if THE_ISA == X86_ISA 609 uint32_t flags = pkt->req->getFlags(); 610 bool storeCheck = flags & 611 (TheISA::StoreCheck << TheISA::FlagShift); 612#else 613 bool storeCheck = false; 614#endif // X86_ISA 615 if (storeCheck) { 616 primary_type = RubyRequestType_RMW_Read; 617 secondary_type = RubyRequestType_ST; 618 } else { 619 primary_type = secondary_type = RubyRequestType_LD; 620 } 621 } 622 } else if (pkt->isWrite()) { 623 // 624 // Note: M5 packets do not differentiate ST from RMW_Write 625 // 626 primary_type = secondary_type = RubyRequestType_ST; 627 } else if (pkt->isFlush()) { 628 primary_type = secondary_type = RubyRequestType_FLUSH; 629 } else { 630 panic("Unsupported ruby packet type\n"); 631 } 632 } 633 634 RequestStatus status = insertRequest(pkt, primary_type); 635 if (status != RequestStatus_Ready) 636 return status; 637 638 issueRequest(pkt, secondary_type); 639 640 // TODO: issue hardware prefetches here 641 return RequestStatus_Issued; 642} 643 644void 645Sequencer::issueRequest(PacketPtr pkt, RubyRequestType secondary_type) 646{ 647 assert(pkt != NULL); 648 int proc_id = -1; 649 if (pkt->req->hasContextId()) { 650 proc_id = pkt->req->contextId(); 651 } 652 653 // If valid, copy the pc to the ruby request 654 Addr pc = 0; 655 if (pkt->req->hasPC()) { 656 pc = pkt->req->getPC(); 657 } 658
|
661 pkt->getPtr<uint8_t>(true), 662 pkt->getSize(), pc, secondary_type, 663 RubyAccessMode_Supervisor, pkt, 664 PrefetchBit_No, proc_id); 665 666 DPRINTFR(ProtocolTrace, "%15s %3s %10s%20s %6s>%-6s %s %s\n", 667 curTick(), m_version, "Seq", "Begin", "", "", 668 msg->getPhysicalAddress(), 669 RubyRequestType_to_string(secondary_type)); 670 671 Cycles latency(0); // initialzed to an null value 672 673 if (secondary_type == RubyRequestType_IFETCH) 674 latency = m_instCache_ptr->getLatency(); 675 else 676 latency = m_dataCache_ptr->getLatency(); 677 678 // Send the message to the cache controller 679 assert(latency > 0); 680 681 assert(m_mandatory_q_ptr != NULL); 682 m_mandatory_q_ptr->enqueue(msg, latency); 683} 684 685template <class KEY, class VALUE> 686std::ostream & 687operator<<(ostream &out, const m5::hash_map<KEY, VALUE> &map) 688{ 689 typename m5::hash_map<KEY, VALUE>::const_iterator i = map.begin(); 690 typename m5::hash_map<KEY, VALUE>::const_iterator end = map.end(); 691 692 out << "["; 693 for (; i != end; ++i) 694 out << " " << i->first << "=" << i->second; 695 out << " ]"; 696 697 return out; 698} 699 700void 701Sequencer::print(ostream& out) const 702{ 703 out << "[Sequencer: " << m_version 704 << ", outstanding requests: " << m_outstanding_count 705 << ", read request table: " << m_readRequestTable 706 << ", write request table: " << m_writeRequestTable 707 << "]"; 708} 709 710// this can be called from setState whenever coherence permissions are 711// upgraded when invoked, coherence violations will be checked for the 712// given block 713void 714Sequencer::checkCoherence(const Address& addr) 715{ 716#ifdef CHECK_COHERENCE 717 g_system_ptr->checkGlobalCoherenceInvariant(addr); 718#endif 719} 720 721void 722Sequencer::recordRequestType(SequencerRequestType requestType) { 723 DPRINTF(RubyStats, "Recorded statistic: %s\n", 724 SequencerRequestType_to_string(requestType)); 725} 726 727 728void 729Sequencer::evictionCallback(const Address& address) 730{ 731 ruby_eviction_callback(address); 732}
| 660 pkt->getPtr<uint8_t>(true), 661 pkt->getSize(), pc, secondary_type, 662 RubyAccessMode_Supervisor, pkt, 663 PrefetchBit_No, proc_id); 664 665 DPRINTFR(ProtocolTrace, "%15s %3s %10s%20s %6s>%-6s %s %s\n", 666 curTick(), m_version, "Seq", "Begin", "", "", 667 msg->getPhysicalAddress(), 668 RubyRequestType_to_string(secondary_type)); 669 670 Cycles latency(0); // initialzed to an null value 671 672 if (secondary_type == RubyRequestType_IFETCH) 673 latency = m_instCache_ptr->getLatency(); 674 else 675 latency = m_dataCache_ptr->getLatency(); 676 677 // Send the message to the cache controller 678 assert(latency > 0); 679 680 assert(m_mandatory_q_ptr != NULL); 681 m_mandatory_q_ptr->enqueue(msg, latency); 682} 683 684template <class KEY, class VALUE> 685std::ostream & 686operator<<(ostream &out, const m5::hash_map<KEY, VALUE> &map) 687{ 688 typename m5::hash_map<KEY, VALUE>::const_iterator i = map.begin(); 689 typename m5::hash_map<KEY, VALUE>::const_iterator end = map.end(); 690 691 out << "["; 692 for (; i != end; ++i) 693 out << " " << i->first << "=" << i->second; 694 out << " ]"; 695 696 return out; 697} 698 699void 700Sequencer::print(ostream& out) const 701{ 702 out << "[Sequencer: " << m_version 703 << ", outstanding requests: " << m_outstanding_count 704 << ", read request table: " << m_readRequestTable 705 << ", write request table: " << m_writeRequestTable 706 << "]"; 707} 708 709// this can be called from setState whenever coherence permissions are 710// upgraded when invoked, coherence violations will be checked for the 711// given block 712void 713Sequencer::checkCoherence(const Address& addr) 714{ 715#ifdef CHECK_COHERENCE 716 g_system_ptr->checkGlobalCoherenceInvariant(addr); 717#endif 718} 719 720void 721Sequencer::recordRequestType(SequencerRequestType requestType) { 722 DPRINTF(RubyStats, "Recorded statistic: %s\n", 723 SequencerRequestType_to_string(requestType)); 724} 725 726 727void 728Sequencer::evictionCallback(const Address& address) 729{ 730 ruby_eviction_callback(address); 731}
|