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) {
357 if( m_writeRequestTable.exist(line_address(Address(request.paddr))) ||
358 m_readRequestTable.exist(line_address(Address(request.paddr))) ){
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
395 // TODO: issue hardware prefetches here
396 return id;
423 // TODO: issue hardware prefetches here
424 return id;
425 }
426 else {
427 assert(0);
428 return 0;
429 }
401 }
402 else {
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