Sequencer.cc revision 6859:5de565c4b7bd 
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) {
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
423      // TODO: issue hardware prefetches here
424      return id;
425    }
426    else {
427      assert(0);
428      return 0;
429    }
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
571