Sequencer.cc revision 6863:21fbf0412e0d 
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  for (size_t i=0; i<argv.size(); i+=2) {
70    if ( argv[i] == "controller") {
71      m_controller = RubySystem::getController(argv[i+1]); // args[i] = "L1Cache"
72      m_mandatory_q_ptr = m_controller->getMandatoryQueue();
73    } else if ( argv[i] == "icache")
74      m_instCache_ptr = RubySystem::getCache(argv[i+1]);
75    else if ( argv[i] == "dcache")
76      m_dataCache_ptr = RubySystem::getCache(argv[i+1]);
77    else if ( argv[i] == "version")
78      m_version = atoi(argv[i+1].c_str());
79    else if ( argv[i] == "max_outstanding_requests")
80      m_max_outstanding_requests = atoi(argv[i+1].c_str());
81    else if ( argv[i] == "deadlock_threshold")
82      m_deadlock_threshold = atoi(argv[i+1].c_str());
83    else {
84      cerr << "WARNING: Sequencer: Unkown configuration parameter: " << argv[i] << endl;
85      assert(false);
86    }
87  }
88  assert(m_max_outstanding_requests > 0);
89  assert(m_deadlock_threshold > 0);
90  assert(m_version > -1);
91  assert(m_instCache_ptr != NULL);
92  assert(m_dataCache_ptr != NULL);
93  assert(m_controller != NULL);
94}
95
96Sequencer::~Sequencer() {
97
98}
99
100void Sequencer::wakeup() {
101  // Check for deadlock of any of the requests
102  Time current_time = g_eventQueue_ptr->getTime();
103
104  // Check across all outstanding requests
105  int total_outstanding = 0;
106
107  Vector<Address> keys = m_readRequestTable.keys();
108  for (int i=0; i<keys.size(); i++) {
109    SequencerRequest* request = m_readRequestTable.lookup(keys[i]);
110    if (current_time - request->issue_time >= m_deadlock_threshold) {
111      WARN_MSG("Possible Deadlock detected");
112      WARN_EXPR(request);
113      WARN_EXPR(m_version);
114      WARN_EXPR(request->ruby_request.paddr);
115      WARN_EXPR(keys.size());
116      WARN_EXPR(current_time);
117      WARN_EXPR(request->issue_time);
118      WARN_EXPR(current_time - request->issue_time);
119      ERROR_MSG("Aborting");
120    }
121  }
122
123  keys = m_writeRequestTable.keys();
124  for (int i=0; i<keys.size(); i++) {
125    SequencerRequest* request = m_writeRequestTable.lookup(keys[i]);
126    if (current_time - request->issue_time >= m_deadlock_threshold) {
127      WARN_MSG("Possible Deadlock detected");
128      WARN_EXPR(request);
129      WARN_EXPR(m_version);
130      WARN_EXPR(current_time);
131      WARN_EXPR(request->issue_time);
132      WARN_EXPR(current_time - request->issue_time);
133      WARN_EXPR(keys.size());
134      ERROR_MSG("Aborting");
135    }
136  }
137  total_outstanding += m_writeRequestTable.size() + m_readRequestTable.size();
138
139  assert(m_outstanding_count == total_outstanding);
140
141  if (m_outstanding_count > 0) { // If there are still outstanding requests, keep checking
142    g_eventQueue_ptr->scheduleEvent(this, m_deadlock_threshold);
143  } else {
144    m_deadlock_check_scheduled = false;
145  }
146}
147
148void Sequencer::printStats(ostream & out) const {
149  out << "Sequencer: " << m_name << endl;
150  out << "  store_waiting_on_load_cycles: " << m_store_waiting_on_load_cycles << endl;
151  out << "  store_waiting_on_store_cycles: " << m_store_waiting_on_store_cycles << endl;
152  out << "  load_waiting_on_load_cycles: " << m_load_waiting_on_load_cycles << endl;
153  out << "  load_waiting_on_store_cycles: " << m_load_waiting_on_store_cycles << endl;
154}
155
156void Sequencer::printProgress(ostream& out) const{
157  /*
158  int total_demand = 0;
159  out << "Sequencer Stats Version " << m_version << endl;
160  out << "Current time = " << g_eventQueue_ptr->getTime() << endl;
161  out << "---------------" << endl;
162  out << "outstanding requests" << endl;
163
164  Vector<Address> rkeys = m_readRequestTable.keys();
165  int read_size = rkeys.size();
166  out << "proc " << m_version << " Read Requests = " << read_size << endl;
167  // print the request table
168  for(int i=0; i < read_size; ++i){
169    SequencerRequest * request = m_readRequestTable.lookup(rkeys[i]);
170    out << "\tRequest[ " << i << " ] = " << request->type << " Address " << rkeys[i]  << " Posted " << request->issue_time << " PF " << PrefetchBit_No << endl;
171    total_demand++;
172  }
173
174  Vector<Address> wkeys = m_writeRequestTable.keys();
175  int write_size = wkeys.size();
176  out << "proc " << m_version << " Write Requests = " << write_size << endl;
177  // print the request table
178  for(int i=0; i < write_size; ++i){
179      CacheMsg & request = m_writeRequestTable.lookup(wkeys[i]);
180      out << "\tRequest[ " << i << " ] = " << request.getType() << " Address " << wkeys[i]  << " Posted " << request.getTime() << " PF " << request.getPrefetch() << endl;
181      if( request.getPrefetch() == PrefetchBit_No ){
182        total_demand++;
183      }
184  }
185
186  out << endl;
187
188  out << "Total Number Outstanding: " << m_outstanding_count << endl;
189  out << "Total Number Demand     : " << total_demand << endl;
190  out << "Total Number Prefetches : " << m_outstanding_count - total_demand << endl;
191  out << endl;
192  out << endl;
193  */
194}
195
196void Sequencer::printConfig(ostream& out) const {
197  out << "Seqeuncer config: " << m_name << endl;
198  out << "  controller: " << m_controller->getName() << endl;
199  out << "  version: " << m_version << endl;
200  out << "  max_outstanding_requests: " << m_max_outstanding_requests << endl;
201  out << "  deadlock_threshold: " << m_deadlock_threshold << endl;
202}
203
204// Insert the request on the correct request table.  Return true if
205// the entry was already present.
206bool Sequencer::insertRequest(SequencerRequest* request) {
207  int total_outstanding = m_writeRequestTable.size() + m_readRequestTable.size();
208
209  assert(m_outstanding_count == total_outstanding);
210
211  // See if we should schedule a deadlock check
212  if (m_deadlock_check_scheduled == false) {
213    g_eventQueue_ptr->scheduleEvent(this, m_deadlock_threshold);
214    m_deadlock_check_scheduled = true;
215  }
216
217  Address line_addr(request->ruby_request.paddr);
218  line_addr.makeLineAddress();
219  if ((request->ruby_request.type == RubyRequestType_ST) ||
220      (request->ruby_request.type == RubyRequestType_RMW_Read) ||
221      (request->ruby_request.type == RubyRequestType_RMW_Write) ||
222      (request->ruby_request.type == RubyRequestType_Locked_Read) ||
223      (request->ruby_request.type == RubyRequestType_Locked_Write)) {
224    if (m_writeRequestTable.exist(line_addr)) {
225      m_writeRequestTable.lookup(line_addr) = request;
226      //      return true;
227      assert(0); // drh5: isn't this an error?  do you lose the initial request?
228    }
229    m_writeRequestTable.allocate(line_addr);
230    m_writeRequestTable.lookup(line_addr) = request;
231    m_outstanding_count++;
232  } else {
233    if (m_readRequestTable.exist(line_addr)) {
234      m_readRequestTable.lookup(line_addr) = request;
235      //      return true;
236      assert(0); // drh5: isn't this an error?  do you lose the initial request?
237    }
238    m_readRequestTable.allocate(line_addr);
239    m_readRequestTable.lookup(line_addr) = request;
240    m_outstanding_count++;
241  }
242
243  g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count);
244
245  total_outstanding = m_writeRequestTable.size() + m_readRequestTable.size();
246  assert(m_outstanding_count == total_outstanding);
247
248  return false;
249}
250
251void Sequencer::removeRequest(SequencerRequest* srequest) {
252
253  assert(m_outstanding_count == m_writeRequestTable.size() + m_readRequestTable.size());
254
255  const RubyRequest & ruby_request = srequest->ruby_request;
256  Address line_addr(ruby_request.paddr);
257  line_addr.makeLineAddress();
258  if ((ruby_request.type == RubyRequestType_ST) ||
259      (ruby_request.type == RubyRequestType_RMW_Read) ||
260      (ruby_request.type == RubyRequestType_RMW_Write) ||
261      (ruby_request.type == RubyRequestType_Locked_Read) ||
262      (ruby_request.type == RubyRequestType_Locked_Write)) {
263    m_writeRequestTable.deallocate(line_addr);
264  } else {
265    m_readRequestTable.deallocate(line_addr);
266  }
267  m_outstanding_count--;
268
269  assert(m_outstanding_count == m_writeRequestTable.size() + m_readRequestTable.size());
270}
271
272void Sequencer::writeCallback(const Address& address, DataBlock& data) {
273
274  assert(address == line_address(address));
275  assert(m_writeRequestTable.exist(line_address(address)));
276
277  SequencerRequest* request = m_writeRequestTable.lookup(address);
278
279  removeRequest(request);
280
281  assert((request->ruby_request.type == RubyRequestType_ST) ||
282         (request->ruby_request.type == RubyRequestType_RMW_Read) ||
283         (request->ruby_request.type == RubyRequestType_RMW_Write) ||
284         (request->ruby_request.type == RubyRequestType_Locked_Read) ||
285         (request->ruby_request.type == RubyRequestType_Locked_Write));
286
287  if (request->ruby_request.type == RubyRequestType_Locked_Read) {
288    m_dataCache_ptr->setLocked(address, m_version);
289  }
290  else if (request->ruby_request.type == RubyRequestType_RMW_Read) {
291    m_controller->blockOnQueue(address, m_mandatory_q_ptr);
292  }
293  else if (request->ruby_request.type == RubyRequestType_RMW_Write) {
294    m_controller->unblock(address);
295  }
296
297  hitCallback(request, data);
298}
299
300void Sequencer::readCallback(const Address& address, DataBlock& data) {
301
302  assert(address == line_address(address));
303  assert(m_readRequestTable.exist(line_address(address)));
304
305  SequencerRequest* request = m_readRequestTable.lookup(address);
306  removeRequest(request);
307
308  assert((request->ruby_request.type == RubyRequestType_LD) ||
309	 (request->ruby_request.type == RubyRequestType_RMW_Read) ||
310         (request->ruby_request.type == RubyRequestType_IFETCH));
311
312  hitCallback(request, data);
313}
314
315void Sequencer::hitCallback(SequencerRequest* srequest, DataBlock& data) {
316  const RubyRequest & ruby_request = srequest->ruby_request;
317  Address request_address(ruby_request.paddr);
318  Address request_line_address(ruby_request.paddr);
319  request_line_address.makeLineAddress();
320  RubyRequestType type = ruby_request.type;
321  Time issued_time = srequest->issue_time;
322
323  // Set this cache entry to the most recently used
324  if (type == RubyRequestType_IFETCH) {
325    if (m_instCache_ptr->isTagPresent(request_line_address) )
326      m_instCache_ptr->setMRU(request_line_address);
327  } else {
328    if (m_dataCache_ptr->isTagPresent(request_line_address) )
329      m_dataCache_ptr->setMRU(request_line_address);
330  }
331
332  assert(g_eventQueue_ptr->getTime() >= issued_time);
333  Time miss_latency = g_eventQueue_ptr->getTime() - issued_time;
334
335  // Profile the miss latency for all non-zero demand misses
336  if (miss_latency != 0) {
337    g_system_ptr->getProfiler()->missLatency(miss_latency, type);
338
339    if (Debug::getProtocolTrace()) {
340      g_system_ptr->getProfiler()->profileTransition("Seq", m_version, Address(ruby_request.paddr),
341                                                     "", "Done", "", int_to_string(miss_latency)+" cycles");
342    }
343  }
344  /*
345  if (request.getPrefetch() == PrefetchBit_Yes) {
346    return; // Ignore the prefetch
347  }
348  */
349
350  // update the data
351  if (ruby_request.data != NULL) {
352    if ((type == RubyRequestType_LD) ||
353        (type == RubyRequestType_IFETCH) ||
354        (type == RubyRequestType_RMW_Read)) {
355      memcpy(ruby_request.data, data.getData(request_address.getOffset(), ruby_request.len), ruby_request.len);
356    } else {
357      data.setData(ruby_request.data, request_address.getOffset(), ruby_request.len);
358    }
359  }
360
361  m_hit_callback(srequest->id);
362  delete srequest;
363}
364
365// Returns true if the sequencer already has a load or store outstanding
366int Sequencer::isReady(const RubyRequest& request) {
367  bool is_outstanding_store = m_writeRequestTable.exist(line_address(Address(request.paddr)));
368  bool is_outstanding_load = m_readRequestTable.exist(line_address(Address(request.paddr)));
369  if ( is_outstanding_store ) {
370    if ((request.type == RubyRequestType_LD) ||
371        (request.type == RubyRequestType_IFETCH) ||
372        (request.type == RubyRequestType_RMW_Read)) {
373      m_store_waiting_on_load_cycles++;
374    } else {
375      m_store_waiting_on_store_cycles++;
376    }
377    return LIBRUBY_ALIASED_REQUEST;
378  } else if ( is_outstanding_load ) {
379    if ((request.type == RubyRequestType_ST) ||
380        (request.type == RubyRequestType_RMW_Write) ) {
381      m_load_waiting_on_store_cycles++;
382    } else {
383      m_load_waiting_on_load_cycles++;
384    }
385    return LIBRUBY_ALIASED_REQUEST;
386  }
387
388  if (m_outstanding_count >= m_max_outstanding_requests) {
389    return LIBRUBY_BUFFER_FULL;
390  }
391
392  return 1;
393}
394
395bool Sequencer::empty() const {
396  return (m_writeRequestTable.size() == 0) && (m_readRequestTable.size() == 0);
397}
398
399
400int64_t Sequencer::makeRequest(const RubyRequest & request)
401{
402  assert(Address(request.paddr).getOffset() + request.len <= RubySystem::getBlockSizeBytes());
403  int ready = isReady(request);
404  if (ready > 0) {
405    int64_t id = makeUniqueRequestID();
406    SequencerRequest *srequest = new SequencerRequest(request, id, g_eventQueue_ptr->getTime());
407    bool found = insertRequest(srequest);
408    if (!found) {
409      if (request.type == RubyRequestType_Locked_Write) {
410        // NOTE: it is OK to check the locked flag here as the mandatory queue will be checked first
411        // ensuring that nothing comes between checking the flag and servicing the store
412        if (!m_dataCache_ptr->isLocked(line_address(Address(request.paddr)), m_version)) {
413          return LLSC_FAIL;
414        }
415        else {
416          m_dataCache_ptr->clearLocked(line_address(Address(request.paddr)));
417        }
418      }
419      issueRequest(request);
420
421      // TODO: issue hardware prefetches here
422      return id;
423    }
424    else {
425      assert(0);
426      return 0;
427    }
428  } else {
429    return ready;
430  }
431}
432
433void Sequencer::issueRequest(const RubyRequest& request) {
434
435  // TODO: get rid of CacheMsg, CacheRequestType, and AccessModeTYpe, & have SLICC use RubyRequest and subtypes natively
436  CacheRequestType ctype;
437  switch(request.type) {
438  case RubyRequestType_IFETCH:
439    ctype = CacheRequestType_IFETCH;
440    break;
441  case RubyRequestType_LD:
442    ctype = CacheRequestType_LD;
443    break;
444  case RubyRequestType_ST:
445    ctype = CacheRequestType_ST;
446    break;
447  case RubyRequestType_Locked_Read:
448  case RubyRequestType_Locked_Write:
449    ctype = CacheRequestType_ATOMIC;
450    break;
451  case RubyRequestType_RMW_Read:
452    ctype = CacheRequestType_ATOMIC;
453    break;
454  case RubyRequestType_RMW_Write:
455    ctype = CacheRequestType_ATOMIC;
456    break;
457  default:
458    assert(0);
459  }
460  AccessModeType amtype;
461  switch(request.access_mode){
462  case RubyAccessMode_User:
463    amtype = AccessModeType_UserMode;
464    break;
465  case RubyAccessMode_Supervisor:
466    amtype = AccessModeType_SupervisorMode;
467    break;
468  case RubyAccessMode_Device:
469    amtype = AccessModeType_UserMode;
470    break;
471  default:
472    assert(0);
473  }
474  Address line_addr(request.paddr);
475  line_addr.makeLineAddress();
476  CacheMsg msg(line_addr, Address(request.paddr), ctype, Address(request.pc), amtype, request.len, PrefetchBit_No, request.proc_id);
477
478  if (Debug::getProtocolTrace()) {
479    g_system_ptr->getProfiler()->profileTransition("Seq", m_version, Address(request.paddr),
480                                                   "", "Begin", "", RubyRequestType_to_string(request.type));
481  }
482
483  if (g_system_ptr->getTracer()->traceEnabled()) {
484    g_system_ptr->getTracer()->traceRequest(m_name, line_addr, Address(request.pc),
485                                            request.type, g_eventQueue_ptr->getTime());
486  }
487
488  Time latency = 0;  // initialzed to an null value
489
490  if (request.type == RubyRequestType_IFETCH)
491    latency = m_instCache_ptr->getLatency();
492  else
493    latency = m_dataCache_ptr->getLatency();
494
495  // Send the message to the cache controller
496  assert(latency > 0);
497
498
499  m_mandatory_q_ptr->enqueue(msg, latency);
500}
501/*
502bool Sequencer::tryCacheAccess(const Address& addr, CacheRequestType type,
503                               AccessModeType access_mode,
504                               int size, DataBlock*& data_ptr) {
505  if (type == CacheRequestType_IFETCH) {
506    return m_instCache_ptr->tryCacheAccess(line_address(addr), type, data_ptr);
507  } else {
508    return m_dataCache_ptr->tryCacheAccess(line_address(addr), type, data_ptr);
509  }
510}
511*/
512
513void Sequencer::print(ostream& out) const {
514  out << "[Sequencer: " << m_version
515      << ", outstanding requests: " << m_outstanding_count;
516
517  out << ", read request table: " << m_readRequestTable
518      << ", write request table: " << m_writeRequestTable;
519  out << "]";
520}
521
522// this can be called from setState whenever coherence permissions are upgraded
523// when invoked, coherence violations will be checked for the given block
524void Sequencer::checkCoherence(const Address& addr) {
525#ifdef CHECK_COHERENCE
526  g_system_ptr->checkGlobalCoherenceInvariant(addr);
527#endif
528}
529
530