src/mem/ruby/system/CacheMemory.hh

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /*
  30  * CacheMemory.hh
  31  *
  32  * Description:
  33  *
  34  * $Id: CacheMemory.hh,v 3.7 2004/06/18 20:15:15 beckmann Exp $
  35  *
  36  */
  37
  38 #ifndef CACHEMEMORY_H
  39 #define CACHEMEMORY_H
  40
  41 #include "mem/ruby/slicc_interface/AbstractChip.hh"
  42 #include "mem/ruby/common/Global.hh"
  43 #include "mem/protocol/AccessPermission.hh"
  44 #include "mem/ruby/common/Address.hh"
  45
  46 //dsm: PRUNED
  47 //#include "mem/ruby/recorder/CacheRecorder.hh"
  48 #include "mem/protocol/CacheRequestType.hh"
  49 #include "mem/gems_common/Vector.hh"
  50 #include "mem/ruby/common/DataBlock.hh"
  51 #include "mem/protocol/MachineType.hh"
  52 #include "mem/ruby/slicc_interface/RubySlicc_ComponentMapping.hh"
  53 #include "mem/ruby/system/PseudoLRUPolicy.hh"
  54 #include "mem/ruby/system/LRUPolicy.hh"
  55 #include <vector>
  56
  57 template<class ENTRY>
  58 class CacheMemory {
  59 public:
  60
  61   // Constructors
  62   CacheMemory(AbstractChip* chip_ptr, int numSetBits, int cacheAssoc, const MachineType machType, const string& description);
  63
  64   // Destructor
  65   ~CacheMemory();
  66
  67   // Public Methods
  68   void printConfig(ostream& out);
  69
  70   // perform a cache access and see if we hit or not.  Return true on a hit.
  71   bool tryCacheAccess(const Address& address, CacheRequestType type, DataBlock*& data_ptr);
  72
  73   // similar to above, but doesn't require full access check
  74   bool testCacheAccess(const Address& address, CacheRequestType type, DataBlock*& data_ptr);
  75
  76   // tests to see if an address is present in the cache
  77   bool isTagPresent(const Address& address) const;
  78
  79   // Returns true if there is:
  80   //   a) a tag match on this address or there is
  81   //   b) an unused line in the same cache "way"
  82   bool cacheAvail(const Address& address) const;
  83
  84   // find an unused entry and sets the tag appropriate for the address
  85   void allocate(const Address& address);
  86
  87   // Explicitly free up this address
  88   void deallocate(const Address& address);
  89
  90   // Returns with the physical address of the conflicting cache line
  91   Address cacheProbe(const Address& address) const;
  92
  93   // looks an address up in the cache
  94   ENTRY& lookup(const Address& address);
  95   const ENTRY& lookup(const Address& address) const;
  96
  97   // Get/Set permission of cache block
  98   AccessPermission getPermission(const Address& address) const;
  99   void changePermission(const Address& address, AccessPermission new_perm);
 100
 101   // Hook for checkpointing the contents of the cache
 102   void recordCacheContents(CacheRecorder& tr) const;
 103   void setAsInstructionCache(bool is_icache) { m_is_instruction_cache = is_icache; }
 104
 105   // Set this address to most recently used
 106   void setMRU(const Address& address);
 107
 108   void getMemoryValue(const Address& addr, char* value,
 109                       unsigned int size_in_bytes );
 110   void setMemoryValue(const Address& addr, char* value,
 111                       unsigned int size_in_bytes );
 112
 113   // Print cache contents
 114   void print(ostream& out) const;
 115   void printData(ostream& out) const;
 116
 117 private:
 118   // Private Methods
 119
 120   // convert a Address to its location in the cache
 121   Index addressToCacheSet(const Address& address) const;
 122
 123   // Given a cache tag: returns the index of the tag in a set.
 124   // returns -1 if the tag is not found.
 125   int findTagInSet(Index line, const Address& tag) const;
 126   int findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const;
 127
 128   // Private copy constructor and assignment operator
 129   CacheMemory(const CacheMemory& obj);
 130   CacheMemory& operator=(const CacheMemory& obj);
 131
 132   // Data Members (m_prefix)
 133   AbstractChip* m_chip_ptr;
 134   MachineType m_machType;
 135   string m_description;
 136   bool m_is_instruction_cache;
 137
 138   // The first index is the # of cache lines.
 139   // The second index is the the amount associativity.
 140   Vector<Vector<ENTRY> > m_cache;
 141
 142   AbstractReplacementPolicy *m_replacementPolicy_ptr;
 143
 144   int m_cache_num_sets;
 145   int m_cache_num_set_bits;
 146   int m_cache_assoc;
 147
 148   bool is_locked; // for LL/SC
 149 };
 150
 151 // Output operator declaration
 152 //ostream& operator<<(ostream& out, const CacheMemory<ENTRY>& obj);
 153
 154 // ******************* Definitions *******************
 155
 156 // Output operator definition
 157 template<class ENTRY>
 158 inline
 159 ostream& operator<<(ostream& out, const CacheMemory<ENTRY>& obj)
 160 {
 161   obj.print(out);
 162   out << flush;
 163   return out;
 164 }
 165
 166
 167 // ****************************************************************
 168
 169 template<class ENTRY>
 170 inline
 171 CacheMemory<ENTRY>::CacheMemory(AbstractChip* chip_ptr, int numSetBits,
 172                                       int cacheAssoc, const MachineType machType, const string& description)
 173
 174 {
 175   //cout << "CacheMemory constructor numThreads = " << numThreads << endl;
 176   m_chip_ptr = chip_ptr;
 177   m_machType = machType;
 178   m_description = MachineType_to_string(m_machType)+"_"+description;
 179   m_cache_num_set_bits = numSetBits;
 180   m_cache_num_sets = 1 << numSetBits;
 181   m_cache_assoc = cacheAssoc;
 182   m_is_instruction_cache = false;
 183
 184   m_cache.setSize(m_cache_num_sets);
 185   if(strcmp(g_REPLACEMENT_POLICY, "PSEDUO_LRU") == 0)
 186     m_replacementPolicy_ptr = new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc);
 187   else if(strcmp(g_REPLACEMENT_POLICY, "LRU") == 0)
 188     m_replacementPolicy_ptr = new LRUPolicy(m_cache_num_sets, m_cache_assoc);
 189   else
 190     assert(false);
 191   for (int i = 0; i < m_cache_num_sets; i++) {
 192     m_cache[i].setSize(m_cache_assoc);
 193     for (int j = 0; j < m_cache_assoc; j++) {
 194       m_cache[i][j].m_Address.setAddress(0);
 195       m_cache[i][j].m_Permission = AccessPermission_NotPresent;
 196     }
 197   }
 198
 199
 200   //  cout << "Before setting trans address list size" << endl;
 201   //create a trans address for each SMT thread
 202 //   m_trans_address_list.setSize(numThreads);
 203 //   for(ThreadID tid = 0; tid < numThreads; ++tid){
 204 //     cout << "Setting list size for list " << tid << endl;
 205 //     m_trans_address_list[tid].setSize(30);
 206 //   }
 207   //cout << "CacheMemory constructor finished" << endl;
 208 }
 209
 210 template<class ENTRY>
 211 inline
 212 CacheMemory<ENTRY>::~CacheMemory()
 213 {
 214   if(m_replacementPolicy_ptr != NULL)
 215     delete m_replacementPolicy_ptr;
 216 }
 217
 218 template<class ENTRY>
 219 inline
 220 void CacheMemory<ENTRY>::printConfig(ostream& out)
 221 {
 222   out << "Cache config: " << m_description << endl;
 223   out << "  cache_associativity: " << m_cache_assoc << endl;
 224   out << "  num_cache_sets_bits: " << m_cache_num_set_bits << endl;
 225   const int cache_num_sets = 1 << m_cache_num_set_bits;
 226   out << "  num_cache_sets: " << cache_num_sets << endl;
 227   out << "  cache_set_size_bytes: " << cache_num_sets * RubyConfig::dataBlockBytes() << endl;
 228   out << "  cache_set_size_Kbytes: "
 229       << double(cache_num_sets * RubyConfig::dataBlockBytes()) / (1<<10) << endl;
 230   out << "  cache_set_size_Mbytes: "
 231       << double(cache_num_sets * RubyConfig::dataBlockBytes()) / (1<<20) << endl;
 232   out << "  cache_size_bytes: "
 233       << cache_num_sets * RubyConfig::dataBlockBytes() * m_cache_assoc << endl;
 234   out << "  cache_size_Kbytes: "
 235       << double(cache_num_sets * RubyConfig::dataBlockBytes() * m_cache_assoc) / (1<<10) << endl;
 236   out << "  cache_size_Mbytes: "
 237       << double(cache_num_sets * RubyConfig::dataBlockBytes() * m_cache_assoc) / (1<<20) << endl;
 238 }
 239
 240 // PRIVATE METHODS
 241
 242 // convert a Address to its location in the cache
 243 template<class ENTRY>
 244 inline
 245 Index CacheMemory<ENTRY>::addressToCacheSet(const Address& address) const
 246 {
 247   assert(address == line_address(address));
 248   Index temp = -1;
 249   switch (m_machType) {
 250   case MACHINETYPE_L1CACHE_ENUM:
 251     temp = map_address_to_L1CacheSet(address, m_cache_num_set_bits);
 252     break;
 253   case MACHINETYPE_L2CACHE_ENUM:
 254     temp = map_address_to_L2CacheSet(address, m_cache_num_set_bits);
 255     break;
 256   default:
 257     ERROR_MSG("Don't recognize m_machType");
 258   }
 259   assert(temp < m_cache_num_sets);
 260   assert(temp >= 0);
 261   return temp;
 262 }
 263
 264 // Given a cache index: returns the index of the tag in a set.
 265 // returns -1 if the tag is not found.
 266 template<class ENTRY>
 267 inline
 268 int CacheMemory<ENTRY>::findTagInSet(Index cacheSet, const Address& tag) const
 269 {
 270   assert(tag == line_address(tag));
 271   // search the set for the tags
 272   for (int i=0; i < m_cache_assoc; i++) {
 273     if ((m_cache[cacheSet][i].m_Address == tag) &&
 274         (m_cache[cacheSet][i].m_Permission != AccessPermission_NotPresent)) {
 275       return i;
 276     }
 277   }
 278   return -1; // Not found
 279 }
 280
 281 // Given a cache index: returns the index of the tag in a set.
 282 // returns -1 if the tag is not found.
 283 template<class ENTRY>
 284 inline
 285 int CacheMemory<ENTRY>::findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const
 286 {
 287   assert(tag == line_address(tag));
 288   // search the set for the tags
 289   for (int i=0; i < m_cache_assoc; i++) {
 290     if (m_cache[cacheSet][i].m_Address == tag)
 291       return i;
 292   }
 293   return -1; // Not found
 294 }
 295
 296 // PUBLIC METHODS
 297 template<class ENTRY>
 298 inline
 299 bool CacheMemory<ENTRY>::tryCacheAccess(const Address& address,
 300                                            CacheRequestType type,
 301                                            DataBlock*& data_ptr)
 302 {
 303   assert(address == line_address(address));
 304   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 305   Index cacheSet = addressToCacheSet(address);
 306   int loc = findTagInSet(cacheSet, address);
 307   if(loc != -1){ // Do we even have a tag match?
 308     ENTRY& entry = m_cache[cacheSet][loc];
 309     m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
 310     data_ptr = &(entry.getDataBlk());
 311
 312     if(entry.m_Permission == AccessPermission_Read_Write) {
 313       return true;
 314     }
 315     if ((entry.m_Permission == AccessPermission_Read_Only) &&
 316         (type == CacheRequestType_LD || type == CacheRequestType_IFETCH)) {
 317       return true;
 318     }
 319     // The line must not be accessible
 320   }
 321   data_ptr = NULL;
 322   return false;
 323 }
 324
 325 template<class ENTRY>
 326 inline
 327 bool CacheMemory<ENTRY>::testCacheAccess(const Address& address,
 328                                            CacheRequestType type,
 329                                            DataBlock*& data_ptr)
 330 {
 331   assert(address == line_address(address));
 332   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 333   Index cacheSet = addressToCacheSet(address);
 334   int loc = findTagInSet(cacheSet, address);
 335   if(loc != -1){ // Do we even have a tag match?
 336     ENTRY& entry = m_cache[cacheSet][loc];
 337     m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
 338     data_ptr = &(entry.getDataBlk());
 339
 340     return (m_cache[cacheSet][loc].m_Permission != AccessPermission_NotPresent);
 341   }
 342   data_ptr = NULL;
 343   return false;
 344 }
 345
 346 // tests to see if an address is present in the cache
 347 template<class ENTRY>
 348 inline
 349 bool CacheMemory<ENTRY>::isTagPresent(const Address& address) const
 350 {
 351   assert(address == line_address(address));
 352   Index cacheSet = addressToCacheSet(address);
 353   int location = findTagInSet(cacheSet, address);
 354
 355   if (location == -1) {
 356     // We didn't find the tag
 357     DEBUG_EXPR(CACHE_COMP, LowPrio, address);
 358     DEBUG_MSG(CACHE_COMP, LowPrio, "No tag match");
 359     return false;
 360   }
 361   DEBUG_EXPR(CACHE_COMP, LowPrio, address);
 362   DEBUG_MSG(CACHE_COMP, LowPrio, "found");
 363   return true;
 364 }
 365
 366 // Returns true if there is:
 367 //   a) a tag match on this address or there is
 368 //   b) an unused line in the same cache "way"
 369 template<class ENTRY>
 370 inline
 371 bool CacheMemory<ENTRY>::cacheAvail(const Address& address) const
 372 {
 373   assert(address == line_address(address));
 374
 375   Index cacheSet = addressToCacheSet(address);
 376
 377   for (int i=0; i < m_cache_assoc; i++) {
 378     if (m_cache[cacheSet][i].m_Address == address) {
 379       // Already in the cache
 380       return true;
 381     }
 382
 383     if (m_cache[cacheSet][i].m_Permission == AccessPermission_NotPresent) {
 384       // We found an empty entry
 385       return true;
 386     }
 387   }
 388   return false;
 389 }
 390
 391 template<class ENTRY>
 392 inline
 393 void CacheMemory<ENTRY>::allocate(const Address& address)
 394 {
 395   assert(address == line_address(address));
 396   assert(!isTagPresent(address));
 397   assert(cacheAvail(address));
 398   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 399
 400   // Find the first open slot
 401   Index cacheSet = addressToCacheSet(address);
 402   for (int i=0; i < m_cache_assoc; i++) {
 403     if (m_cache[cacheSet][i].m_Permission == AccessPermission_NotPresent) {
 404       m_cache[cacheSet][i] = ENTRY();  // Init entry
 405       m_cache[cacheSet][i].m_Address = address;
 406       m_cache[cacheSet][i].m_Permission = AccessPermission_Invalid;
 407
 408       m_replacementPolicy_ptr->touch(cacheSet, i, g_eventQueue_ptr->getTime());
 409
 410       return;
 411     }
 412   }
 413   ERROR_MSG("Allocate didn't find an available entry");
 414 }
 415
 416 template<class ENTRY>
 417 inline
 418 void CacheMemory<ENTRY>::deallocate(const Address& address)
 419 {
 420   assert(address == line_address(address));
 421   assert(isTagPresent(address));
 422   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 423   lookup(address).m_Permission = AccessPermission_NotPresent;
 424 }
 425
 426 // Returns with the physical address of the conflicting cache line
 427 template<class ENTRY>
 428 inline
 429 Address CacheMemory<ENTRY>::cacheProbe(const Address& address) const
 430 {
 431   assert(address == line_address(address));
 432   assert(!cacheAvail(address));
 433
 434   Index cacheSet = addressToCacheSet(address);
 435   return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)].m_Address;
 436 }
 437
 438 // looks an address up in the cache
 439 template<class ENTRY>
 440 inline
 441 ENTRY& CacheMemory<ENTRY>::lookup(const Address& address)
 442 {
 443   assert(address == line_address(address));
 444   Index cacheSet = addressToCacheSet(address);
 445   int loc = findTagInSet(cacheSet, address);
 446   assert(loc != -1);
 447   return m_cache[cacheSet][loc];
 448 }
 449
 450 // looks an address up in the cache
 451 template<class ENTRY>
 452 inline
 453 const ENTRY& CacheMemory<ENTRY>::lookup(const Address& address) const
 454 {
 455   assert(address == line_address(address));
 456   Index cacheSet = addressToCacheSet(address);
 457   int loc = findTagInSet(cacheSet, address);
 458   assert(loc != -1);
 459   return m_cache[cacheSet][loc];
 460 }
 461
 462 template<class ENTRY>
 463 inline
 464 AccessPermission CacheMemory<ENTRY>::getPermission(const Address& address) const
 465 {
 466   assert(address == line_address(address));
 467   return lookup(address).m_Permission;
 468 }
 469
 470 template<class ENTRY>
 471 inline
 472 void CacheMemory<ENTRY>::changePermission(const Address& address, AccessPermission new_perm)
 473 {
 474   assert(address == line_address(address));
 475   lookup(address).m_Permission = new_perm;
 476   assert(getPermission(address) == new_perm);
 477 }
 478
 479 // Sets the most recently used bit for a cache block
 480 template<class ENTRY>
 481 inline
 482 void CacheMemory<ENTRY>::setMRU(const Address& address)
 483 {
 484   Index cacheSet;
 485
 486   cacheSet = addressToCacheSet(address);
 487   m_replacementPolicy_ptr->touch(cacheSet,
 488                                  findTagInSet(cacheSet, address),
 489                                  g_eventQueue_ptr->getTime());
 490 }
 491
 492 template<class ENTRY>
 493 inline
 494 void CacheMemory<ENTRY>::recordCacheContents(CacheRecorder& tr) const
 495 {
 496 //dsm: Uses CacheRecorder, PRUNED
 497 assert(false);
 498
 499 /*  for (int i = 0; i < m_cache_num_sets; i++) {
 500     for (int j = 0; j < m_cache_assoc; j++) {
 501       AccessPermission perm = m_cache[i][j].m_Permission;
 502       CacheRequestType request_type = CacheRequestType_NULL;
 503       if (perm == AccessPermission_Read_Only) {
 504         if (m_is_instruction_cache) {
 505           request_type = CacheRequestType_IFETCH;
 506         } else {
 507           request_type = CacheRequestType_LD;
 508         }
 509       } else if (perm == AccessPermission_Read_Write) {
 510         request_type = CacheRequestType_ST;
 511       }
 512
 513       if (request_type != CacheRequestType_NULL) {
 514         tr.addRecord(m_chip_ptr->getID(), m_cache[i][j].m_Address,
 515                      Address(0), request_type, m_replacementPolicy_ptr->getLastAccess(i, j));
 516       }
 517     }
 518   }*/
 519 }
 520
 521 template<class ENTRY>
 522 inline
 523 void CacheMemory<ENTRY>::print(ostream& out) const
 524 {
 525   out << "Cache dump: " << m_description << endl;
 526   for (int i = 0; i < m_cache_num_sets; i++) {
 527     for (int j = 0; j < m_cache_assoc; j++) {
 528       out << "  Index: " << i
 529           << " way: " << j
 530           << " entry: " << m_cache[i][j] << endl;
 531     }
 532   }
 533 }
 534
 535 template<class ENTRY>
 536 inline
 537 void CacheMemory<ENTRY>::printData(ostream& out) const
 538 {
 539   out << "printData() not supported" << endl;
 540 }
 541
 542 template<class ENTRY>
 543 void CacheMemory<ENTRY>::getMemoryValue(const Address& addr, char* value,
 544                                            unsigned int size_in_bytes ){
 545   ENTRY entry = lookup(line_address(addr));
 546   unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
 547   for(unsigned int i=0; i<size_in_bytes; ++i){
 548     value[i] = entry.m_DataBlk.getByte(i + startByte);
 549   }
 550 }
 551
 552 template<class ENTRY>
 553 void CacheMemory<ENTRY>::setMemoryValue(const Address& addr, char* value,
 554                                            unsigned int size_in_bytes ){
 555   ENTRY& entry = lookup(line_address(addr));
 556   unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
 557   assert(size_in_bytes > 0);
 558   for(unsigned int i=0; i<size_in_bytes; ++i){
 559     entry.m_DataBlk.setByte(i + startByte, value[i]);
 560   }
 561
 562   entry = lookup(line_address(addr));
 563 }
 564
 565 #endif //CACHEMEMORY_H
 566