3 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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.
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.
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"
45 //Sequencer::Sequencer(int core_id, MessageBuffer* mandatory_q)
49 Sequencer::Sequencer(const string
& name
)
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;
58 void Sequencer::init(const vector
<string
> & argv
)
60 m_deadlock_check_scheduled
= false;
61 m_outstanding_count
= 0;
63 m_max_outstanding_requests
= 0;
64 m_deadlock_threshold
= 0;
66 m_instCache_ptr
= NULL
;
67 m_dataCache_ptr
= NULL
;
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());
86 cerr
<< "WARNING: Sequencer: Unkown configuration parameter: " << argv
[i
] << endl
;
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
);
98 Sequencer::~Sequencer() {
102 void Sequencer::wakeup() {
103 // Check for deadlock of any of the requests
104 Time current_time
= g_eventQueue_ptr
->getTime();
106 // Check across all outstanding requests
107 int total_outstanding
= 0;
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");
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");
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");
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");
139 total_outstanding
+= m_writeRequestTable
.size() + m_readRequestTable
.size();
141 assert(m_outstanding_count
== total_outstanding
);
143 if (m_outstanding_count
> 0) { // If there are still outstanding requests, keep checking
144 g_eventQueue_ptr
->scheduleEvent(this, m_deadlock_threshold
);
146 m_deadlock_check_scheduled
= false;
150 void 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
;
158 void Sequencer::printProgress(ostream
& out
) const{
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;
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;
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 ){
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;
198 void 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
;
206 // Insert the request on the correct request table. Return true if
207 // the entry was already present.
208 bool Sequencer::insertRequest(SequencerRequest
* request
) {
209 int total_outstanding
= m_writeRequestTable
.size() + m_readRequestTable
.size();
211 assert(m_outstanding_count
== total_outstanding
);
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;
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
;
229 assert(0); // drh5: isn't this an error? do you lose the initial request?
231 m_writeRequestTable
.allocate(line_addr
);
232 m_writeRequestTable
.lookup(line_addr
) = request
;
233 m_outstanding_count
++;
235 if (m_readRequestTable
.exist(line_addr
)) {
236 m_readRequestTable
.lookup(line_addr
) = request
;
238 assert(0); // drh5: isn't this an error? do you lose the initial request?
240 m_readRequestTable
.allocate(line_addr
);
241 m_readRequestTable
.lookup(line_addr
) = request
;
242 m_outstanding_count
++;
245 g_system_ptr
->getProfiler()->sequencerRequests(m_outstanding_count
);
247 total_outstanding
= m_writeRequestTable
.size() + m_readRequestTable
.size();
248 assert(m_outstanding_count
== total_outstanding
);
253 void Sequencer::removeRequest(SequencerRequest
* srequest
) {
255 assert(m_outstanding_count
== m_writeRequestTable
.size() + m_readRequestTable
.size());
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
);
267 m_readRequestTable
.deallocate(line_addr
);
269 m_outstanding_count
--;
271 assert(m_outstanding_count
== m_writeRequestTable
.size() + m_readRequestTable
.size());
274 void Sequencer::writeCallback(const Address
& address
, DataBlock
& data
) {
276 assert(address
== line_address(address
));
277 assert(m_writeRequestTable
.exist(line_address(address
)));
279 SequencerRequest
* request
= m_writeRequestTable
.lookup(address
);
281 removeRequest(request
);
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
);
292 else if (request
->ruby_request
.type
== RubyRequestType_RMW_Read
) {
293 m_controller
->set_atomic(address
);
295 else if (request
->ruby_request
.type
== RubyRequestType_RMW_Write
) {
296 m_controller
->clear_atomic(address
);
299 hitCallback(request
, data
);
302 void Sequencer::readCallback(const Address
& address
, DataBlock
& data
) {
304 assert(address
== line_address(address
));
305 assert(m_readRequestTable
.exist(line_address(address
)));
307 SequencerRequest
* request
= m_readRequestTable
.lookup(address
);
308 removeRequest(request
);
310 assert((request
->ruby_request
.type
== RubyRequestType_LD
) ||
311 (request
->ruby_request
.type
== RubyRequestType_RMW_Read
) ||
312 (request
->ruby_request
.type
== RubyRequestType_IFETCH
));
314 hitCallback(request
, data
);
317 void 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
;
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
);
330 if (m_dataCache_ptr
->isTagPresent(request_line_address
) )
331 m_dataCache_ptr
->setMRU(request_line_address
);
334 assert(g_eventQueue_ptr
->getTime() >= issued_time
);
335 Time miss_latency
= g_eventQueue_ptr
->getTime() - issued_time
;
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
);
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");
347 if (request.getPrefetch() == PrefetchBit_Yes) {
348 return; // Ignore the prefetch
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
);
359 data
.setData(ruby_request
.data
, request_address
.getOffset(), ruby_request
.len
);
363 m_hit_callback(srequest
->id
);
367 // Returns true if the sequencer already has a load or store outstanding
368 int 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
++;
377 m_store_waiting_on_store_cycles
++;
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
++;
385 m_load_waiting_on_load_cycles
++;
387 return LIBRUBY_ALIASED_REQUEST
;
390 if (m_outstanding_count
>= m_max_outstanding_requests
) {
391 return LIBRUBY_BUFFER_FULL
;
397 bool Sequencer::empty() const {
398 return (m_writeRequestTable
.size() == 0) && (m_readRequestTable
.size() == 0);
402 int64_t Sequencer::makeRequest(const RubyRequest
& request
)
404 assert(Address(request
.paddr
).getOffset() + request
.len
<= RubySystem::getBlockSizeBytes());
405 int ready
= isReady(request
);
407 int64_t id
= makeUniqueRequestID();
408 SequencerRequest
*srequest
= new SequencerRequest(request
, id
, g_eventQueue_ptr
->getTime());
409 bool found
= insertRequest(srequest
);
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
)) {
418 m_dataCache_ptr
->clearLocked(line_address(Address(request
.paddr
)));
421 issueRequest(request
);
423 // TODO: issue hardware prefetches here
435 void Sequencer::issueRequest(const RubyRequest
& request
) {
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();
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
;
451 ctype
= CacheRequestType_IFETCH
;
453 case RubyRequestType_LD
:
454 if (m_atomic_reads
> 0 && m_atomic_writes
== 0) {
455 m_controller
->reset_atomics();
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
;
464 ctype
= CacheRequestType_LD
;
466 case RubyRequestType_ST
:
467 if (m_atomic_reads
> 0 && m_atomic_writes
== 0) {
468 m_controller
->reset_atomics();
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
;
477 ctype
= CacheRequestType_ST
;
479 case RubyRequestType_Locked_Read
:
480 case RubyRequestType_Locked_Write
:
481 ctype
= CacheRequestType_ATOMIC
;
483 case RubyRequestType_RMW_Read
:
484 assert(m_atomic_writes
== 0);
486 ctype
= CacheRequestType_ATOMIC
;
488 case RubyRequestType_RMW_Write
:
489 assert(m_atomic_reads
> 0);
490 assert(m_atomic_writes
< m_atomic_reads
);
492 if (m_atomic_reads
== m_atomic_writes
) {
496 ctype
= CacheRequestType_ATOMIC
;
501 AccessModeType amtype
;
502 switch(request
.access_mode
){
503 case RubyAccessMode_User
:
504 amtype
= AccessModeType_UserMode
;
506 case RubyAccessMode_Supervisor
:
507 amtype
= AccessModeType_SupervisorMode
;
509 case RubyAccessMode_Device
:
510 amtype
= AccessModeType_UserMode
;
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
);
519 if (Debug::getProtocolTrace()) {
520 g_system_ptr
->getProfiler()->profileTransition("Seq", m_version
, Address(request
.paddr
),
521 "", "Begin", "", RubyRequestType_to_string(request
.type
));
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());
529 Time latency
= 0; // initialzed to an null value
531 if (request
.type
== RubyRequestType_IFETCH
)
532 latency
= m_instCache_ptr
->getLatency();
534 latency
= m_dataCache_ptr
->getLatency();
536 // Send the message to the cache controller
540 m_mandatory_q_ptr
->enqueue(msg
, latency
);
543 bool 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);
549 return m_dataCache_ptr->tryCacheAccess(line_address(addr), type, data_ptr);
554 void Sequencer::print(ostream
& out
) const {
555 out
<< "[Sequencer: " << m_version
556 << ", outstanding requests: " << m_outstanding_count
;
558 out
<< ", read request table: " << m_readRequestTable
559 << ", write request table: " << m_writeRequestTable
;
563 // this can be called from setState whenever coherence permissions are upgraded
564 // when invoked, coherence violations will be checked for the given block
565 void Sequencer::checkCoherence(const Address
& addr
) {
566 #ifdef CHECK_COHERENCE
567 g_system_ptr
->checkGlobalCoherenceInvariant(addr
);