Sequencer.cc revision 6155:2b8fec056712 
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/*
31 * $Id: Sequencer.C 1.131 2006/11/06 17:41:01-06:00 bobba@gratiano.cs.wisc.edu $
32 *
33 */
34
35#include "mem/ruby/common/Global.hh"
36#include "mem/ruby/system/Sequencer.hh"
37#include "mem/ruby/system/System.hh"
38#include "mem/protocol/Protocol.hh"
39#include "mem/ruby/profiler/Profiler.hh"
40#include "mem/ruby/system/CacheMemory.hh"
41#include "mem/ruby/config/RubyConfig.hh"
42//#include "mem/ruby/recorder/Tracer.hh"
43#include "mem/ruby/slicc_interface/AbstractChip.hh"
44#include "mem/protocol/Chip.hh"
45#include "mem/ruby/tester/Tester.hh"
46#include "mem/ruby/common/SubBlock.hh"
47#include "mem/protocol/Protocol.hh"
48#include "mem/gems_common/Map.hh"
49
50Sequencer::Sequencer(AbstractChip* chip_ptr, int version) {
51  m_chip_ptr = chip_ptr;
52  m_version = version;
53
54  m_deadlock_check_scheduled = false;
55  m_outstanding_count = 0;
56
57  int smt_threads = RubyConfig::numberofSMTThreads();
58  m_writeRequestTable_ptr = new Map<Address, CacheMsg>*[smt_threads];
59  m_readRequestTable_ptr = new Map<Address, CacheMsg>*[smt_threads];
60
61  for(int p=0; p < smt_threads; ++p){
62    m_writeRequestTable_ptr[p] = new Map<Address, CacheMsg>;
63    m_readRequestTable_ptr[p] = new Map<Address, CacheMsg>;
64  }
65
66}
67
68Sequencer::~Sequencer() {
69  int smt_threads = RubyConfig::numberofSMTThreads();
70  for(int i=0; i < smt_threads; ++i){
71    if(m_writeRequestTable_ptr[i]){
72      delete m_writeRequestTable_ptr[i];
73    }
74    if(m_readRequestTable_ptr[i]){
75      delete m_readRequestTable_ptr[i];
76    }
77  }
78  if(m_writeRequestTable_ptr){
79    delete [] m_writeRequestTable_ptr;
80  }
81  if(m_readRequestTable_ptr){
82    delete [] m_readRequestTable_ptr;
83  }
84}
85
86void Sequencer::wakeup() {
87  // Check for deadlock of any of the requests
88  Time current_time = g_eventQueue_ptr->getTime();
89  bool deadlock = false;
90
91  // Check across all outstanding requests
92  int smt_threads = RubyConfig::numberofSMTThreads();
93  int total_outstanding = 0;
94  for(int p=0; p < smt_threads; ++p){
95    Vector<Address> keys = m_readRequestTable_ptr[p]->keys();
96    for (int i=0; i<keys.size(); i++) {
97      CacheMsg& request = m_readRequestTable_ptr[p]->lookup(keys[i]);
98      if (current_time - request.getTime() >= g_DEADLOCK_THRESHOLD) {
99        WARN_MSG("Possible Deadlock detected");
100        WARN_EXPR(request);
101        WARN_EXPR(m_chip_ptr->getID());
102        WARN_EXPR(m_version);
103        WARN_EXPR(keys.size());
104        WARN_EXPR(current_time);
105        WARN_EXPR(request.getTime());
106        WARN_EXPR(current_time - request.getTime());
107        WARN_EXPR(*m_readRequestTable_ptr[p]);
108        ERROR_MSG("Aborting");
109        deadlock = true;
110      }
111    }
112
113    keys = m_writeRequestTable_ptr[p]->keys();
114    for (int i=0; i<keys.size(); i++) {
115      CacheMsg& request = m_writeRequestTable_ptr[p]->lookup(keys[i]);
116      if (current_time - request.getTime() >= g_DEADLOCK_THRESHOLD) {
117        WARN_MSG("Possible Deadlock detected");
118        WARN_EXPR(request);
119        WARN_EXPR(m_chip_ptr->getID());
120        WARN_EXPR(m_version);
121        WARN_EXPR(current_time);
122        WARN_EXPR(request.getTime());
123        WARN_EXPR(current_time - request.getTime());
124        WARN_EXPR(keys.size());
125        WARN_EXPR(*m_writeRequestTable_ptr[p]);
126        ERROR_MSG("Aborting");
127        deadlock = true;
128      }
129    }
130    total_outstanding += m_writeRequestTable_ptr[p]->size() + m_readRequestTable_ptr[p]->size();
131  }  // across all request tables
132  assert(m_outstanding_count == total_outstanding);
133
134  if (m_outstanding_count > 0) { // If there are still outstanding requests, keep checking
135    g_eventQueue_ptr->scheduleEvent(this, g_DEADLOCK_THRESHOLD);
136  } else {
137    m_deadlock_check_scheduled = false;
138  }
139}
140
141//returns the total number of requests
142int Sequencer::getNumberOutstanding(){
143  return m_outstanding_count;
144}
145
146// returns the total number of demand requests
147int Sequencer::getNumberOutstandingDemand(){
148  int smt_threads = RubyConfig::numberofSMTThreads();
149  int total_demand = 0;
150  for(int p=0; p < smt_threads; ++p){
151    Vector<Address> keys = m_readRequestTable_ptr[p]->keys();
152    for (int i=0; i< keys.size(); i++) {
153      CacheMsg& request = m_readRequestTable_ptr[p]->lookup(keys[i]);
154      if(request.getPrefetch() == PrefetchBit_No){
155        total_demand++;
156      }
157    }
158
159    keys = m_writeRequestTable_ptr[p]->keys();
160    for (int i=0; i< keys.size(); i++) {
161      CacheMsg& request = m_writeRequestTable_ptr[p]->lookup(keys[i]);
162      if(request.getPrefetch() == PrefetchBit_No){
163        total_demand++;
164      }
165    }
166  }
167
168  return total_demand;
169}
170
171int Sequencer::getNumberOutstandingPrefetch(){
172  int smt_threads = RubyConfig::numberofSMTThreads();
173  int total_prefetch = 0;
174  for(int p=0; p < smt_threads; ++p){
175    Vector<Address> keys = m_readRequestTable_ptr[p]->keys();
176    for (int i=0; i< keys.size(); i++) {
177      CacheMsg& request = m_readRequestTable_ptr[p]->lookup(keys[i]);
178      if(request.getPrefetch() == PrefetchBit_Yes){
179        total_prefetch++;
180      }
181    }
182
183    keys = m_writeRequestTable_ptr[p]->keys();
184    for (int i=0; i< keys.size(); i++) {
185      CacheMsg& request = m_writeRequestTable_ptr[p]->lookup(keys[i]);
186      if(request.getPrefetch() == PrefetchBit_Yes){
187        total_prefetch++;
188      }
189    }
190  }
191
192  return total_prefetch;
193}
194
195bool Sequencer::isPrefetchRequest(const Address & lineaddr){
196  int smt_threads = RubyConfig::numberofSMTThreads();
197  for(int p=0; p < smt_threads; ++p){
198    // check load requests
199    Vector<Address> keys = m_readRequestTable_ptr[p]->keys();
200    for (int i=0; i< keys.size(); i++) {
201      CacheMsg& request = m_readRequestTable_ptr[p]->lookup(keys[i]);
202      if(line_address(request.getAddress()) == lineaddr){
203        if(request.getPrefetch() == PrefetchBit_Yes){
204          return true;
205        }
206        else{
207          return false;
208        }
209      }
210    }
211
212    // check store requests
213    keys = m_writeRequestTable_ptr[p]->keys();
214    for (int i=0; i< keys.size(); i++) {
215      CacheMsg& request = m_writeRequestTable_ptr[p]->lookup(keys[i]);
216      if(line_address(request.getAddress()) == lineaddr){
217        if(request.getPrefetch() == PrefetchBit_Yes){
218          return true;
219        }
220        else{
221          return false;
222        }
223      }
224    }
225  }
226  // we should've found a matching request
227  cout << "isRequestPrefetch() ERROR request NOT FOUND : " << lineaddr << endl;
228  printProgress(cout);
229  assert(0);
230}
231
232AccessModeType Sequencer::getAccessModeOfRequest(Address addr, int thread){
233  if(m_readRequestTable_ptr[thread]->exist(line_address(addr))){
234    CacheMsg& request = m_readRequestTable_ptr[thread]->lookup(addr);
235    return request.getAccessMode();
236  } else if(m_writeRequestTable_ptr[thread]->exist(line_address(addr))){
237    CacheMsg& request = m_writeRequestTable_ptr[thread]->lookup(addr);
238    return request.getAccessMode();
239  } else {
240    printProgress(cout);
241    ERROR_MSG("Request not found in RequestTables");
242  }
243}
244
245Address Sequencer::getLogicalAddressOfRequest(Address addr, int thread){
246  assert(thread >= 0);
247  if(m_readRequestTable_ptr[thread]->exist(line_address(addr))){
248    CacheMsg& request = m_readRequestTable_ptr[thread]->lookup(addr);
249    return request.getLogicalAddress();
250  } else if(m_writeRequestTable_ptr[thread]->exist(line_address(addr))){
251    CacheMsg& request = m_writeRequestTable_ptr[thread]->lookup(addr);
252    return request.getLogicalAddress();
253  } else {
254    printProgress(cout);
255    WARN_MSG("Request not found in RequestTables");
256    WARN_MSG(addr);
257    WARN_MSG(thread);
258    ASSERT(0);
259  }
260}
261
262// returns the ThreadID of the request
263int Sequencer::getRequestThreadID(const Address & addr){
264  int smt_threads = RubyConfig::numberofSMTThreads();
265  int thread = -1;
266  int num_found = 0;
267  for(int p=0; p < smt_threads; ++p){
268    if(m_readRequestTable_ptr[p]->exist(addr)){
269      num_found++;
270      thread = p;
271    }
272    if(m_writeRequestTable_ptr[p]->exist(addr)){
273      num_found++;
274      thread = p;
275    }
276  }
277  if(num_found != 1){
278    cout << "getRequestThreadID ERROR too many matching requests addr = " << addr << endl;
279    printProgress(cout);
280  }
281  ASSERT(num_found == 1);
282  ASSERT(thread != -1);
283
284  return thread;
285}
286
287// given a line address, return the request's physical address
288Address Sequencer::getRequestPhysicalAddress(const Address & lineaddr){
289  int smt_threads = RubyConfig::numberofSMTThreads();
290  Address physaddr;
291  int num_found = 0;
292  for(int p=0; p < smt_threads; ++p){
293    if(m_readRequestTable_ptr[p]->exist(lineaddr)){
294      num_found++;
295      physaddr = (m_readRequestTable_ptr[p]->lookup(lineaddr)).getAddress();
296    }
297    if(m_writeRequestTable_ptr[p]->exist(lineaddr)){
298      num_found++;
299      physaddr = (m_writeRequestTable_ptr[p]->lookup(lineaddr)).getAddress();
300    }
301  }
302  if(num_found != 1){
303    cout << "getRequestPhysicalAddress ERROR too many matching requests addr = " << lineaddr << endl;
304    printProgress(cout);
305  }
306  ASSERT(num_found == 1);
307
308  return physaddr;
309}
310
311void Sequencer::printProgress(ostream& out) const{
312
313  int total_demand = 0;
314  out << "Sequencer Stats Version " << m_version << endl;
315  out << "Current time = " << g_eventQueue_ptr->getTime() << endl;
316  out << "---------------" << endl;
317  out << "outstanding requests" << endl;
318
319  int smt_threads = RubyConfig::numberofSMTThreads();
320  for(int p=0; p < smt_threads; ++p){
321    Vector<Address> rkeys = m_readRequestTable_ptr[p]->keys();
322    int read_size = rkeys.size();
323    out << "proc " << m_chip_ptr->getID() << " thread " << p << " Read Requests = " << read_size << endl;
324    // print the request table
325    for(int i=0; i < read_size; ++i){
326      CacheMsg & request = m_readRequestTable_ptr[p]->lookup(rkeys[i]);
327      out << "\tRequest[ " << i << " ] = " << request.getType() << " Address " << rkeys[i]  << " Posted " << request.getTime() << " PF " << request.getPrefetch() << endl;
328      if( request.getPrefetch() == PrefetchBit_No ){
329        total_demand++;
330      }
331    }
332
333    Vector<Address> wkeys = m_writeRequestTable_ptr[p]->keys();
334    int write_size = wkeys.size();
335    out << "proc " << m_chip_ptr->getID() << " thread " << p << " Write Requests = " << write_size << endl;
336    // print the request table
337    for(int i=0; i < write_size; ++i){
338      CacheMsg & request = m_writeRequestTable_ptr[p]->lookup(wkeys[i]);
339      out << "\tRequest[ " << i << " ] = " << request.getType() << " Address " << wkeys[i]  << " Posted " << request.getTime() << " PF " << request.getPrefetch() << endl;
340      if( request.getPrefetch() == PrefetchBit_No ){
341        total_demand++;
342      }
343    }
344
345    out << endl;
346  }
347  out << "Total Number Outstanding: " << m_outstanding_count << endl;
348  out << "Total Number Demand     : " << total_demand << endl;
349  out << "Total Number Prefetches : " << m_outstanding_count - total_demand << endl;
350  out << endl;
351  out << endl;
352
353}
354
355void Sequencer::printConfig(ostream& out) {
356  if (TSO) {
357    out << "sequencer: Sequencer - TSO" << endl;
358  } else {
359    out << "sequencer: Sequencer - SC" << endl;
360  }
361  out << "  max_outstanding_requests: " << g_SEQUENCER_OUTSTANDING_REQUESTS << endl;
362}
363
364bool Sequencer::empty() const {
365  return m_outstanding_count == 0;
366}
367
368// Insert the request on the correct request table.  Return true if
369// the entry was already present.
370bool Sequencer::insertRequest(const CacheMsg& request) {
371  int thread = request.getThreadID();
372  assert(thread >= 0);
373  int total_outstanding = 0;
374  int smt_threads = RubyConfig::numberofSMTThreads();
375  for(int p=0; p < smt_threads; ++p){
376    total_outstanding += m_writeRequestTable_ptr[p]->size() + m_readRequestTable_ptr[p]->size();
377  }
378  assert(m_outstanding_count == total_outstanding);
379
380  // See if we should schedule a deadlock check
381  if (m_deadlock_check_scheduled == false) {
382    g_eventQueue_ptr->scheduleEvent(this, g_DEADLOCK_THRESHOLD);
383    m_deadlock_check_scheduled = true;
384  }
385
386  if ((request.getType() == CacheRequestType_ST) ||
387      (request.getType() == CacheRequestType_ATOMIC)) {
388    if (m_writeRequestTable_ptr[thread]->exist(line_address(request.getAddress()))) {
389      m_writeRequestTable_ptr[thread]->lookup(line_address(request.getAddress())) = request;
390      return true;
391    }
392    m_writeRequestTable_ptr[thread]->allocate(line_address(request.getAddress()));
393    m_writeRequestTable_ptr[thread]->lookup(line_address(request.getAddress())) = request;
394    m_outstanding_count++;
395  } else {
396    if (m_readRequestTable_ptr[thread]->exist(line_address(request.getAddress()))) {
397      m_readRequestTable_ptr[thread]->lookup(line_address(request.getAddress())) = request;
398      return true;
399    }
400    m_readRequestTable_ptr[thread]->allocate(line_address(request.getAddress()));
401    m_readRequestTable_ptr[thread]->lookup(line_address(request.getAddress())) = request;
402    m_outstanding_count++;
403  }
404
405  g_system_ptr->getProfiler()->sequencerRequests(m_outstanding_count);
406
407  total_outstanding = 0;
408  for(int p=0; p < smt_threads; ++p){
409    total_outstanding += m_writeRequestTable_ptr[p]->size() + m_readRequestTable_ptr[p]->size();
410  }
411
412  assert(m_outstanding_count == total_outstanding);
413  return false;
414}
415
416void Sequencer::removeRequest(const CacheMsg& request) {
417  int thread = request.getThreadID();
418  assert(thread >= 0);
419  int total_outstanding = 0;
420  int smt_threads = RubyConfig::numberofSMTThreads();
421  for(int p=0; p < smt_threads; ++p){
422    total_outstanding += m_writeRequestTable_ptr[p]->size() + m_readRequestTable_ptr[p]->size();
423  }
424  assert(m_outstanding_count == total_outstanding);
425
426  if ((request.getType() == CacheRequestType_ST) ||
427      (request.getType() == CacheRequestType_ATOMIC)) {
428    m_writeRequestTable_ptr[thread]->deallocate(line_address(request.getAddress()));
429  } else {
430    m_readRequestTable_ptr[thread]->deallocate(line_address(request.getAddress()));
431  }
432  m_outstanding_count--;
433
434  total_outstanding = 0;
435  for(int p=0; p < smt_threads; ++p){
436    total_outstanding += m_writeRequestTable_ptr[p]->size() + m_readRequestTable_ptr[p]->size();
437  }
438  assert(m_outstanding_count == total_outstanding);
439}
440
441void Sequencer::writeCallback(const Address& address) {
442  DataBlock data;
443  writeCallback(address, data);
444}
445
446void Sequencer::writeCallback(const Address& address, DataBlock& data) {
447  // process oldest thread first
448  int thread = -1;
449  Time oldest_time = 0;
450  int smt_threads = RubyConfig::numberofSMTThreads();
451  for(int t=0; t < smt_threads; ++t){
452    if(m_writeRequestTable_ptr[t]->exist(address)){
453      CacheMsg & request = m_writeRequestTable_ptr[t]->lookup(address);
454      if(thread == -1 || (request.getTime() < oldest_time) ){
455        thread = t;
456        oldest_time = request.getTime();
457      }
458    }
459  }
460  // make sure we found an oldest thread
461  ASSERT(thread != -1);
462
463  CacheMsg & request = m_writeRequestTable_ptr[thread]->lookup(address);
464
465  writeCallback(address, data, GenericMachineType_NULL, PrefetchBit_No, thread);
466}
467
468void Sequencer::writeCallback(const Address& address, DataBlock& data, GenericMachineType respondingMach, PrefetchBit pf, int thread) {
469
470  assert(address == line_address(address));
471  assert(thread >= 0);
472  assert(m_writeRequestTable_ptr[thread]->exist(line_address(address)));
473
474  writeCallback(address, data, respondingMach, thread);
475
476}
477
478void Sequencer::writeCallback(const Address& address, DataBlock& data, GenericMachineType respondingMach, int thread) {
479  assert(address == line_address(address));
480  assert(m_writeRequestTable_ptr[thread]->exist(line_address(address)));
481  CacheMsg request = m_writeRequestTable_ptr[thread]->lookup(address);
482  assert( request.getThreadID() == thread);
483  removeRequest(request);
484
485  assert((request.getType() == CacheRequestType_ST) ||
486         (request.getType() == CacheRequestType_ATOMIC));
487
488  hitCallback(request, data, respondingMach, thread);
489
490}
491
492void Sequencer::readCallback(const Address& address) {
493  DataBlock data;
494  readCallback(address, data);
495}
496
497void Sequencer::readCallback(const Address& address, DataBlock& data) {
498  // process oldest thread first
499  int thread = -1;
500  Time oldest_time = 0;
501  int smt_threads = RubyConfig::numberofSMTThreads();
502  for(int t=0; t < smt_threads; ++t){
503    if(m_readRequestTable_ptr[t]->exist(address)){
504      CacheMsg & request = m_readRequestTable_ptr[t]->lookup(address);
505      if(thread == -1 || (request.getTime() < oldest_time) ){
506        thread = t;
507        oldest_time = request.getTime();
508      }
509    }
510  }
511  // make sure we found an oldest thread
512  ASSERT(thread != -1);
513
514  CacheMsg & request = m_readRequestTable_ptr[thread]->lookup(address);
515
516  readCallback(address, data, GenericMachineType_NULL, PrefetchBit_No, thread);
517}
518
519void Sequencer::readCallback(const Address& address, DataBlock& data, GenericMachineType respondingMach, PrefetchBit pf, int thread) {
520
521  assert(address == line_address(address));
522  assert(m_readRequestTable_ptr[thread]->exist(line_address(address)));
523
524  readCallback(address, data, respondingMach, thread);
525}
526
527void Sequencer::readCallback(const Address& address, DataBlock& data, GenericMachineType respondingMach, int thread) {
528  assert(address == line_address(address));
529  assert(m_readRequestTable_ptr[thread]->exist(line_address(address)));
530
531  CacheMsg request = m_readRequestTable_ptr[thread]->lookup(address);
532  assert( request.getThreadID() == thread );
533  removeRequest(request);
534
535  assert((request.getType() == CacheRequestType_LD) ||
536         (request.getType() == CacheRequestType_IFETCH)
537         );
538
539  hitCallback(request, data, respondingMach, thread);
540}
541
542void Sequencer::hitCallback(const CacheMsg& request, DataBlock& data, GenericMachineType respondingMach, int thread) {
543  int size = request.getSize();
544  Address request_address = request.getAddress();
545  Address request_logical_address = request.getLogicalAddress();
546  Address request_line_address = line_address(request_address);
547  CacheRequestType type = request.getType();
548  int threadID = request.getThreadID();
549  Time issued_time = request.getTime();
550  int logical_proc_no = ((m_chip_ptr->getID() * RubyConfig::numberOfProcsPerChip()) + m_version) * RubyConfig::numberofSMTThreads() + threadID;
551
552  DEBUG_MSG(SEQUENCER_COMP, MedPrio, size);
553
554  // Set this cache entry to the most recently used
555  if (type == CacheRequestType_IFETCH) {
556    if (Protocol::m_TwoLevelCache) {
557      if (m_chip_ptr->m_L1Cache_L1IcacheMemory_vec[m_version]->isTagPresent(request_line_address)) {
558        m_chip_ptr->m_L1Cache_L1IcacheMemory_vec[m_version]->setMRU(request_line_address);
559      }
560    }
561    else {
562      if (m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->isTagPresent(request_line_address)) {
563        m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->setMRU(request_line_address);
564      }
565    }
566  } else {
567    if (Protocol::m_TwoLevelCache) {
568      if (m_chip_ptr->m_L1Cache_L1DcacheMemory_vec[m_version]->isTagPresent(request_line_address)) {
569        m_chip_ptr->m_L1Cache_L1DcacheMemory_vec[m_version]->setMRU(request_line_address);
570      }
571    }
572    else {
573      if (m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->isTagPresent(request_line_address)) {
574        m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->setMRU(request_line_address);
575      }
576    }
577  }
578
579  assert(g_eventQueue_ptr->getTime() >= issued_time);
580  Time miss_latency = g_eventQueue_ptr->getTime() - issued_time;
581
582  if (PROTOCOL_DEBUG_TRACE) {
583    g_system_ptr->getProfiler()->profileTransition("Seq", (m_chip_ptr->getID()*RubyConfig::numberOfProcsPerChip()+m_version), -1, request.getAddress(), "", "Done", "",
584                                                   int_to_string(miss_latency)+" cycles "+GenericMachineType_to_string(respondingMach)+" "+CacheRequestType_to_string(request.getType())+" "+PrefetchBit_to_string(request.getPrefetch()));
585  }
586
587  DEBUG_MSG(SEQUENCER_COMP, MedPrio, request_address);
588  DEBUG_MSG(SEQUENCER_COMP, MedPrio, request.getPrefetch());
589  if (request.getPrefetch() == PrefetchBit_Yes) {
590    DEBUG_MSG(SEQUENCER_COMP, MedPrio, "return");
591    g_system_ptr->getProfiler()->swPrefetchLatency(miss_latency, type, respondingMach);
592    return; // Ignore the software prefetch, don't callback the driver
593  }
594
595  // Profile the miss latency for all non-zero demand misses
596  if (miss_latency != 0) {
597    g_system_ptr->getProfiler()->missLatency(miss_latency, type, respondingMach);
598
599  }
600
601  bool write =
602    (type == CacheRequestType_ST) ||
603    (type == CacheRequestType_ATOMIC);
604
605  if (TSO && write) {
606    m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->callBack(line_address(request.getAddress()), data);
607  } else {
608
609    // Copy the correct bytes out of the cache line into the subblock
610    SubBlock subblock(request_address, request_logical_address, size);
611    subblock.mergeFrom(data);  // copy the correct bytes from DataBlock in the SubBlock
612
613    // Scan the store buffer to see if there are any outstanding stores we need to collect
614    if (TSO) {
615      m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->updateSubBlock(subblock);
616    }
617
618    // Call into the Driver and let it read and/or modify the sub-block
619    g_system_ptr->getDriver()->hitCallback(m_chip_ptr->getID()*RubyConfig::numberOfProcsPerChip()+m_version, subblock, type, threadID);
620
621    // If the request was a Store or Atomic, apply the changes in the SubBlock to the DataBlock
622    // (This is only triggered for the non-TSO case)
623    if (write) {
624      assert(!TSO);
625      subblock.mergeTo(data);    // copy the correct bytes from SubBlock into the DataBlock
626    }
627  }
628}
629
630void Sequencer::readConflictCallback(const Address& address) {
631  std::cout << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
632}
633
634void Sequencer::readConflictCallback(const Address& address, GenericMachineType respondingMach, int thread) {
635  std::cout << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
636}
637
638void Sequencer::writeConflictCallback(const Address& address) {
639  std::cout << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
640}
641
642void Sequencer::writeConflictCallback(const Address& address, GenericMachineType respondingMach, int thread) {
643  std::cout << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
644}
645
646void Sequencer::conflictCallback(const CacheMsg& request, GenericMachineType respondingMach, int thread) {
647  std::cout << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
648}
649
650void Sequencer::printDebug(){
651  //notify driver of debug
652  g_system_ptr->getDriver()->printDebug();
653}
654
655// Returns true if the sequencer already has a load or store outstanding
656bool
657Sequencer::isReady(const Packet* pkt) const
658{
659
660  int cpu_number = pkt->req->contextId();
661  la_t logical_addr = pkt->req->getVaddr();
662  pa_t physical_addr = pkt->req->getPaddr();
663  CacheRequestType type_of_request;
664  if ( pkt->req->isInstFetch() ) {
665    type_of_request = CacheRequestType_IFETCH;
666  } else if ( pkt->req->isLocked() || pkt->req->isSwap() ) {
667    type_of_request = CacheRequestType_ATOMIC;
668  } else if ( pkt->isRead() ) {
669    type_of_request = CacheRequestType_LD;
670  } else if ( pkt->isWrite() ) {
671    type_of_request = CacheRequestType_ST;
672  } else {
673    assert(false);
674  }
675  int thread = pkt->req->threadId();
676
677  CacheMsg request(Address( physical_addr ),
678                   Address( physical_addr ),
679                   type_of_request,
680                   Address(0),
681                   AccessModeType_UserMode,   // User/supervisor mode
682                   0,   // Size in bytes of request
683                   PrefetchBit_No,  // Not a prefetch
684                   0,              // Version number
685                   Address(logical_addr),   // Virtual Address
686                   thread              // SMT thread
687                   );
688  isReady(request);
689}
690
691bool
692Sequencer::isReady(const CacheMsg& request) const
693{
694  if (m_outstanding_count >= g_SEQUENCER_OUTSTANDING_REQUESTS) {
695    //cout << "TOO MANY OUTSTANDING: " << m_outstanding_count << " " << g_SEQUENCER_OUTSTANDING_REQUESTS << " VER " << m_version << endl;
696    //printProgress(cout);
697    return false;
698  }
699
700  // This code allows reads to be performed even when we have a write
701  // request outstanding for the line
702  bool write =
703    (request.getType() == CacheRequestType_ST) ||
704    (request.getType() == CacheRequestType_ATOMIC);
705
706  // LUKE - disallow more than one request type per address
707  //     INVARIANT: at most one request type per address, per processor
708  int smt_threads = RubyConfig::numberofSMTThreads();
709  for(int p=0; p < smt_threads; ++p){
710    if( m_writeRequestTable_ptr[p]->exist(line_address(request.getAddress())) ||
711        m_readRequestTable_ptr[p]->exist(line_address(request.getAddress())) ){
712      //cout << "OUTSTANDING REQUEST EXISTS " << p << " VER " << m_version << endl;
713      //printProgress(cout);
714      return false;
715    }
716  }
717
718  if (TSO) {
719    return m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->isReady();
720  }
721  return true;
722}
723
724// Called by Driver
725void
726Sequencer::makeRequest(const Packet* pkt, void* data)
727{
728  int cpu_number = pkt->req->contextId();
729  la_t logical_addr = pkt->req->getVaddr();
730  pa_t physical_addr = pkt->req->getPaddr();
731  int request_size = pkt->getSize();
732  CacheRequestType type_of_request;
733  if ( pkt->req->isInstFetch() ) {
734    type_of_request = CacheRequestType_IFETCH;
735  } else if ( pkt->req->isLocked() || pkt->req->isSwap() ) {
736    type_of_request = CacheRequestType_ATOMIC;
737  } else if ( pkt->isRead() ) {
738    type_of_request = CacheRequestType_LD;
739  } else if ( pkt->isWrite() ) {
740    type_of_request = CacheRequestType_ST;
741  } else {
742    assert(false);
743  }
744  la_t virtual_pc = pkt->req->getPC();
745  int isPriv = false;  // TODO: get permission data
746  int thread = pkt->req->threadId();
747
748  AccessModeType access_mode = AccessModeType_UserMode; // TODO: get actual permission
749
750  CacheMsg request(Address( physical_addr ),
751                   Address( physical_addr ),
752                   type_of_request,
753                   Address(virtual_pc),
754                   access_mode,   // User/supervisor mode
755                   request_size,   // Size in bytes of request
756                   PrefetchBit_No, // Not a prefetch
757                   0,              // Version number
758                   Address(logical_addr),   // Virtual Address
759                   thread         // SMT thread
760                   );
761  makeRequest(request);
762}
763
764void
765Sequencer::makeRequest(const CacheMsg& request)
766{
767  bool write = (request.getType() == CacheRequestType_ST) ||
768    (request.getType() == CacheRequestType_ATOMIC);
769
770  if (TSO && (request.getPrefetch() == PrefetchBit_No) && write) {
771    assert(m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->isReady());
772    m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->insertStore(request);
773    return;
774  }
775
776  bool hit = doRequest(request);
777
778}
779
780bool Sequencer::doRequest(const CacheMsg& request) {
781  bool hit = false;
782  // Check the fast path
783  DataBlock* data_ptr;
784
785  int thread = request.getThreadID();
786
787  hit = tryCacheAccess(line_address(request.getAddress()),
788                       request.getType(),
789                       request.getProgramCounter(),
790                       request.getAccessMode(),
791                       request.getSize(),
792                       data_ptr);
793
794  if (hit && (request.getType() == CacheRequestType_IFETCH || !REMOVE_SINGLE_CYCLE_DCACHE_FAST_PATH) ) {
795    DEBUG_MSG(SEQUENCER_COMP, MedPrio, "Fast path hit");
796    hitCallback(request, *data_ptr, GenericMachineType_L1Cache, thread);
797    return true;
798  }
799
800  if (TSO && (request.getType() == CacheRequestType_LD || request.getType() == CacheRequestType_IFETCH)) {
801
802    // See if we can satisfy the load entirely from the store buffer
803    SubBlock subblock(line_address(request.getAddress()), request.getSize());
804    if (m_chip_ptr->m_L1Cache_storeBuffer_vec[m_version]->trySubBlock(subblock)) {
805      DataBlock dummy;
806      hitCallback(request, dummy, GenericMachineType_NULL, thread);  // Call with an 'empty' datablock, since the data is in the store buffer
807      return true;
808    }
809  }
810
811  DEBUG_MSG(SEQUENCER_COMP, MedPrio, "Fast path miss");
812  issueRequest(request);
813  return hit;
814}
815
816void Sequencer::issueRequest(const CacheMsg& request) {
817  bool found = insertRequest(request);
818
819  if (!found) {
820    CacheMsg msg = request;
821    msg.getAddress() = line_address(request.getAddress()); // Make line address
822
823    // Fast Path L1 misses are profiled here - all non-fast path misses are profiled within the generated protocol code
824    if (!REMOVE_SINGLE_CYCLE_DCACHE_FAST_PATH) {
825      g_system_ptr->getProfiler()->addPrimaryStatSample(msg, m_chip_ptr->getID());
826    }
827
828    if (PROTOCOL_DEBUG_TRACE) {
829      g_system_ptr->getProfiler()->profileTransition("Seq", (m_chip_ptr->getID()*RubyConfig::numberOfProcsPerChip() + m_version), -1, msg.getAddress(),"", "Begin", "", CacheRequestType_to_string(request.getType()));
830    }
831
832#if 0
833    // Commented out by nate binkert because I removed the trace stuff
834    if (g_system_ptr->getTracer()->traceEnabled()) {
835      g_system_ptr->getTracer()->traceRequest((m_chip_ptr->getID()*RubyConfig::numberOfProcsPerChip()+m_version), msg.getAddress(), msg.getProgramCounter(),
836                                              msg.getType(), g_eventQueue_ptr->getTime());
837    }
838#endif
839
840    Time latency = 0;  // initialzed to an null value
841
842    latency = SEQUENCER_TO_CONTROLLER_LATENCY;
843
844    // Send the message to the cache controller
845    assert(latency > 0);
846    m_chip_ptr->m_L1Cache_mandatoryQueue_vec[m_version]->enqueue(msg, latency);
847
848  }  // !found
849}
850
851bool Sequencer::tryCacheAccess(const Address& addr, CacheRequestType type,
852                               const Address& pc, AccessModeType access_mode,
853                               int size, DataBlock*& data_ptr) {
854  if (type == CacheRequestType_IFETCH) {
855    if (Protocol::m_TwoLevelCache) {
856      return m_chip_ptr->m_L1Cache_L1IcacheMemory_vec[m_version]->tryCacheAccess(line_address(addr), type, data_ptr);
857    }
858    else {
859      return m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->tryCacheAccess(line_address(addr), type, data_ptr);
860    }
861  } else {
862    if (Protocol::m_TwoLevelCache) {
863      return m_chip_ptr->m_L1Cache_L1DcacheMemory_vec[m_version]->tryCacheAccess(line_address(addr), type, data_ptr);
864    }
865    else {
866      return m_chip_ptr->m_L1Cache_cacheMemory_vec[m_version]->tryCacheAccess(line_address(addr), type, data_ptr);
867    }
868  }
869}
870
871void Sequencer::resetRequestTime(const Address& addr, int thread){
872  assert(thread >= 0);
873  //reset both load and store requests, if they exist
874  if(m_readRequestTable_ptr[thread]->exist(line_address(addr))){
875    CacheMsg& request = m_readRequestTable_ptr[thread]->lookup(addr);
876    if( request.m_AccessMode != AccessModeType_UserMode){
877      cout << "resetRequestType ERROR read request addr = " << addr << " thread = "<< thread << " is SUPERVISOR MODE" << endl;
878      printProgress(cout);
879    }
880    //ASSERT(request.m_AccessMode == AccessModeType_UserMode);
881    request.setTime(g_eventQueue_ptr->getTime());
882  }
883  if(m_writeRequestTable_ptr[thread]->exist(line_address(addr))){
884    CacheMsg& request = m_writeRequestTable_ptr[thread]->lookup(addr);
885    if( request.m_AccessMode != AccessModeType_UserMode){
886      cout << "resetRequestType ERROR write request addr = " << addr << " thread = "<< thread << " is SUPERVISOR MODE" << endl;
887      printProgress(cout);
888    }
889    //ASSERT(request.m_AccessMode == AccessModeType_UserMode);
890    request.setTime(g_eventQueue_ptr->getTime());
891  }
892}
893
894// removes load request from queue
895void Sequencer::removeLoadRequest(const Address & addr, int thread){
896  removeRequest(getReadRequest(addr, thread));
897}
898
899void Sequencer::removeStoreRequest(const Address & addr, int thread){
900  removeRequest(getWriteRequest(addr, thread));
901}
902
903// returns the read CacheMsg
904CacheMsg & Sequencer::getReadRequest( const Address & addr, int thread ){
905  Address temp = addr;
906  assert(thread >= 0);
907  assert(temp == line_address(temp));
908  assert(m_readRequestTable_ptr[thread]->exist(addr));
909  return m_readRequestTable_ptr[thread]->lookup(addr);
910}
911
912CacheMsg & Sequencer::getWriteRequest( const Address & addr, int thread){
913  Address temp = addr;
914  assert(thread >= 0);
915  assert(temp == line_address(temp));
916  assert(m_writeRequestTable_ptr[thread]->exist(addr));
917  return m_writeRequestTable_ptr[thread]->lookup(addr);
918}
919
920void Sequencer::print(ostream& out) const {
921  out << "[Sequencer: " << m_chip_ptr->getID()
922      << ", outstanding requests: " << m_outstanding_count;
923
924  int smt_threads = RubyConfig::numberofSMTThreads();
925  for(int p=0; p < smt_threads; ++p){
926    out << ", read request table[ " << p << " ]: " << *m_readRequestTable_ptr[p]
927        << ", write request table[ " << p << " ]: " << *m_writeRequestTable_ptr[p];
928  }
929  out << "]";
930}
931
932// this can be called from setState whenever coherence permissions are upgraded
933// when invoked, coherence violations will be checked for the given block
934void Sequencer::checkCoherence(const Address& addr) {
935#ifdef CHECK_COHERENCE
936  g_system_ptr->checkGlobalCoherenceInvariant(addr);
937#endif
938}
939
940bool Sequencer::getRubyMemoryValue(const Address& addr, char* value,
941                                   unsigned int size_in_bytes ) {
942  if(g_SIMULATING){
943    for(unsigned int i=0; i < size_in_bytes; i++) {
944      std::cerr << __FILE__ << "(" << __LINE__ << "): Not implemented. " << std::endl;
945      value[i] = 0; // _read_physical_memory( m_chip_ptr->getID()*RubyConfig::numberOfProcsPerChip()+m_version,
946                    //                          addr.getAddress() + i, 1 );
947    }
948    return false; // Do nothing?
949  } else {
950    bool found = false;
951    const Address lineAddr = line_address(addr);
952    DataBlock data;
953    PhysAddress paddr(addr);
954    DataBlock* dataPtr = &data;
955    Chip* n = dynamic_cast<Chip*>(m_chip_ptr);
956    // LUKE - use variable names instead of macros
957    assert(n->m_L1Cache_L1IcacheMemory_vec[m_version] != NULL);
958    assert(n->m_L1Cache_L1DcacheMemory_vec[m_version] != NULL);
959
960    MachineID l2_mach = map_L2ChipId_to_L2Cache(addr, m_chip_ptr->getID() );
961    int l2_ver = l2_mach.num%RubyConfig::numberOfL2CachePerChip();
962
963    if (Protocol::m_TwoLevelCache) {
964      if(Protocol::m_CMP){
965        assert(n->m_L2Cache_L2cacheMemory_vec[l2_ver] != NULL);
966      }
967      else{
968        assert(n->m_L1Cache_cacheMemory_vec[m_version] != NULL);
969      }
970    }
971
972    if (n->m_L1Cache_L1IcacheMemory_vec[m_version]->tryCacheAccess(lineAddr, CacheRequestType_IFETCH, dataPtr)){
973      n->m_L1Cache_L1IcacheMemory_vec[m_version]->getMemoryValue(addr, value, size_in_bytes);
974      found = true;
975    } else if (n->m_L1Cache_L1DcacheMemory_vec[m_version]->tryCacheAccess(lineAddr, CacheRequestType_LD, dataPtr)){
976      n->m_L1Cache_L1DcacheMemory_vec[m_version]->getMemoryValue(addr, value, size_in_bytes);
977      found = true;
978    } else if (Protocol::m_CMP && n->m_L2Cache_L2cacheMemory_vec[l2_ver]->tryCacheAccess(lineAddr, CacheRequestType_LD, dataPtr)){
979      n->m_L2Cache_L2cacheMemory_vec[l2_ver]->getMemoryValue(addr, value, size_in_bytes);
980      found = true;
981      // } else if (n->TBE_TABLE_MEMBER_VARIABLE->isPresent(lineAddr)){
982      //       ASSERT(n->TBE_TABLE_MEMBER_VARIABLE->isPresent(lineAddr));
983      //       L1Cache_TBE tbeEntry = n->TBE_TABLE_MEMBER_VARIABLE->lookup(lineAddr);
984
985      //       int offset = addr.getOffset();
986      //       for(int i=0; i<size_in_bytes; ++i){
987      //         value[i] = tbeEntry.getDataBlk().getByte(offset + i);
988      //       }
989
990      //       found = true;
991    } else {
992      // Address not found
993      //cout << "  " << m_chip_ptr->getID() << " NOT IN CACHE, Value at Directory is: " << (int) value[0] << endl;
994      n = dynamic_cast<Chip*>(g_system_ptr->getChip(map_Address_to_DirectoryNode(addr)/RubyConfig::numberOfDirectoryPerChip()));
995      int dir_version = map_Address_to_DirectoryNode(addr)%RubyConfig::numberOfDirectoryPerChip();
996      for(unsigned int i=0; i<size_in_bytes; ++i){
997        int offset = addr.getOffset();
998        value[i] = n->m_Directory_directory_vec[dir_version]->lookup(lineAddr).m_DataBlk.getByte(offset + i);
999      }
1000      // Address not found
1001      //WARN_MSG("Couldn't find address");
1002      //WARN_EXPR(addr);
1003      found = false;
1004    }
1005    return true;
1006  }
1007}
1008
1009bool Sequencer::setRubyMemoryValue(const Address& addr, char *value,
1010                                   unsigned int size_in_bytes) {
1011  char test_buffer[64];
1012
1013  if(g_SIMULATING){
1014    return false; // Do nothing?
1015  } else {
1016    // idea here is that coherent cache should find the
1017    // latest data, the update it
1018    bool found = false;
1019    const Address lineAddr = line_address(addr);
1020    PhysAddress paddr(addr);
1021    DataBlock data;
1022    DataBlock* dataPtr = &data;
1023    Chip* n = dynamic_cast<Chip*>(m_chip_ptr);
1024
1025    MachineID l2_mach = map_L2ChipId_to_L2Cache(addr, m_chip_ptr->getID() );
1026    int l2_ver = l2_mach.num%RubyConfig::numberOfL2CachePerChip();
1027    // LUKE - use variable names instead of macros
1028    //cout << "number of L2caches per chip = " << RubyConfig::numberOfL2CachePerChip(m_version) << endl;
1029    //cout << "L1I cache vec size = " << n->m_L1Cache_L1IcacheMemory_vec.size() << endl;
1030    //cout << "L1D cache vec size = " << n->m_L1Cache_L1DcacheMemory_vec.size() << endl;
1031    //cout << "L1cache_cachememory size = " << n->m_L1Cache_cacheMemory_vec.size() << endl;
1032    //cout << "L1cache_l2cachememory size = " << n->m_L1Cache_L2cacheMemory_vec.size() << endl;
1033    // if (Protocol::m_TwoLevelCache) {
1034    //       if(Protocol::m_CMP){
1035    //         cout << "CMP L2 cache vec size = " << n->m_L2Cache_L2cacheMemory_vec.size() << endl;
1036    //       }
1037    //       else{
1038    //        cout << "L2 cache vec size = " << n->m_L1Cache_cacheMemory_vec.size() << endl;
1039    //       }
1040    //     }
1041
1042    assert(n->m_L1Cache_L1IcacheMemory_vec[m_version] != NULL);
1043    assert(n->m_L1Cache_L1DcacheMemory_vec[m_version] != NULL);
1044    if (Protocol::m_TwoLevelCache) {
1045      if(Protocol::m_CMP){
1046        assert(n->m_L2Cache_L2cacheMemory_vec[l2_ver] != NULL);
1047      }
1048      else{
1049        assert(n->m_L1Cache_cacheMemory_vec[m_version] != NULL);
1050      }
1051    }
1052
1053    if (n->m_L1Cache_L1IcacheMemory_vec[m_version]->tryCacheAccess(lineAddr, CacheRequestType_IFETCH, dataPtr)){
1054      n->m_L1Cache_L1IcacheMemory_vec[m_version]->setMemoryValue(addr, value, size_in_bytes);
1055      found = true;
1056    } else if (n->m_L1Cache_L1DcacheMemory_vec[m_version]->tryCacheAccess(lineAddr, CacheRequestType_LD, dataPtr)){
1057      n->m_L1Cache_L1DcacheMemory_vec[m_version]->setMemoryValue(addr, value, size_in_bytes);
1058      found = true;
1059    } else if (Protocol::m_CMP && n->m_L2Cache_L2cacheMemory_vec[l2_ver]->tryCacheAccess(lineAddr, CacheRequestType_LD, dataPtr)){
1060      n->m_L2Cache_L2cacheMemory_vec[l2_ver]->setMemoryValue(addr, value, size_in_bytes);
1061      found = true;
1062      // } else if (n->TBE_TABLE_MEMBER_VARIABLE->isTagPresent(lineAddr)){
1063      //       L1Cache_TBE& tbeEntry = n->TBE_TABLE_MEMBER_VARIABLE->lookup(lineAddr);
1064      //       DataBlock tmpData;
1065      //       int offset = addr.getOffset();
1066      //       for(int i=0; i<size_in_bytes; ++i){
1067      //         tmpData.setByte(offset + i, value[i]);
1068      //       }
1069      //       tbeEntry.setDataBlk(tmpData);
1070      //       tbeEntry.setDirty(true);
1071    } else {
1072      // Address not found
1073      n = dynamic_cast<Chip*>(g_system_ptr->getChip(map_Address_to_DirectoryNode(addr)/RubyConfig::numberOfDirectoryPerChip()));
1074      int dir_version = map_Address_to_DirectoryNode(addr)%RubyConfig::numberOfDirectoryPerChip();
1075      for(unsigned int i=0; i<size_in_bytes; ++i){
1076        int offset = addr.getOffset();
1077        n->m_Directory_directory_vec[dir_version]->lookup(lineAddr).m_DataBlk.setByte(offset + i, value[i]);
1078      }
1079      found = false;
1080    }
1081
1082    if (found){
1083      found = getRubyMemoryValue(addr, test_buffer, size_in_bytes);
1084      assert(found);
1085      if(value[0] != test_buffer[0]){
1086        WARN_EXPR((int) value[0]);
1087        WARN_EXPR((int) test_buffer[0]);
1088        ERROR_MSG("setRubyMemoryValue failed to set value.");
1089      }
1090    }
1091
1092    return true;
1093  }
1094}
1095
1096