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