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