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/common/Global.hh"
  42 #include "mem/protocol/AccessPermission.hh"
  43 #include "mem/ruby/common/Address.hh"
  44 #include "mem/ruby/recorder/CacheRecorder.hh"
  45 #include "mem/protocol/CacheRequestType.hh"
  46 #include "mem/gems_common/Vector.hh"
  47 #include "mem/ruby/common/DataBlock.hh"
  48 #include "mem/protocol/MachineType.hh"
  49 #include "mem/ruby/slicc_interface/RubySlicc_ComponentMapping.hh"
  50 #include "mem/ruby/system/PseudoLRUPolicy.hh"
  51 #include "mem/ruby/system/LRUPolicy.hh"
  52 #include "mem/ruby/slicc_interface/AbstractCacheEntry.hh"
  53 #include "mem/ruby/system/System.hh"
  54 #include "mem/ruby/slicc_interface/AbstractController.hh"
  55 #include <vector>
  56
  57 class CacheMemory {
  58 public:
  59
  60   // Constructors
  61   CacheMemory(const string & name);
  62   void init(const vector<string> & argv);
  63
  64   // Destructor
  65   ~CacheMemory();
  66
  67   // factory
  68   //  static CacheMemory* createCache(int level, int num, char split_type, AbstractCacheEntry* (*entry_factory)());
  69   //  static CacheMemory* getCache(int cache_id);
  70
  71   // Public Methods
  72   void printConfig(ostream& out);
  73
  74   // perform a cache access and see if we hit or not.  Return true on a hit.
  75   bool tryCacheAccess(const Address& address, CacheRequestType type, DataBlock*& data_ptr);
  76
  77   // similar to above, but doesn't require full access check
  78   bool testCacheAccess(const Address& address, CacheRequestType type, DataBlock*& data_ptr);
  79
  80   // tests to see if an address is present in the cache
  81   bool isTagPresent(const Address& address) const;
  82
  83   // Returns true if there is:
  84   //   a) a tag match on this address or there is
  85   //   b) an unused line in the same cache "way"
  86   bool cacheAvail(const Address& address) const;
  87
  88   // find an unused entry and sets the tag appropriate for the address
  89   void allocate(const Address& address, AbstractCacheEntry* new_entry);
  90
  91   // Explicitly free up this address
  92   void deallocate(const Address& address);
  93
  94   // Returns with the physical address of the conflicting cache line
  95   Address cacheProbe(const Address& address) const;
  96
  97   // looks an address up in the cache
  98   AbstractCacheEntry& lookup(const Address& address);
  99   const AbstractCacheEntry& lookup(const Address& address) const;
 100
 101   // Get/Set permission of cache block
 102   AccessPermission getPermission(const Address& address) const;
 103   void changePermission(const Address& address, AccessPermission new_perm);
 104
 105   int getLatency() const { return m_latency; }
 106
 107   // Hook for checkpointing the contents of the cache
 108   void recordCacheContents(CacheRecorder& tr) const;
 109   void setAsInstructionCache(bool is_icache) { m_is_instruction_only_cache = is_icache; }
 110
 111   // Set this address to most recently used
 112   void setMRU(const Address& address);
 113
 114   void getMemoryValue(const Address& addr, char* value,
 115                       unsigned int size_in_bytes );
 116   void setMemoryValue(const Address& addr, char* value,
 117                       unsigned int size_in_bytes );
 118
 119   void setLocked (const Address& addr, int context);
 120   void clearLocked (const Address& addr);
 121   bool isLocked (const Address& addr, int context);
 122   // Print cache contents
 123   void print(ostream& out) const;
 124   void printData(ostream& out) const;
 125
 126 private:
 127   // Private Methods
 128
 129   // convert a Address to its location in the cache
 130   Index addressToCacheSet(const Address& address) const;
 131
 132   // Given a cache tag: returns the index of the tag in a set.
 133   // returns -1 if the tag is not found.
 134   int findTagInSet(Index line, const Address& tag) const;
 135   int findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const;
 136
 137   // Private copy constructor and assignment operator
 138   CacheMemory(const CacheMemory& obj);
 139   CacheMemory& operator=(const CacheMemory& obj);
 140
 141 private:
 142   const string m_cache_name;
 143   AbstractController* m_controller;
 144   int m_latency;
 145
 146   // Data Members (m_prefix)
 147   bool m_is_instruction_only_cache;
 148   bool m_is_data_only_cache;
 149
 150   // The first index is the # of cache lines.
 151   // The second index is the the amount associativity.
 152   Vector<Vector<AbstractCacheEntry*> > m_cache;
 153   Vector<Vector<int> > m_locked;
 154
 155   AbstractReplacementPolicy *m_replacementPolicy_ptr;
 156
 157   int m_cache_num_sets;
 158   int m_cache_num_set_bits;
 159   int m_cache_assoc;
 160
 161   static Vector< CacheMemory* > m_all_caches;
 162 };
 163
 164 // Output operator declaration
 165 //ostream& operator<<(ostream& out, const CacheMemory<ENTRY>& obj);
 166
 167 // ******************* Definitions *******************
 168
 169 // Output operator definition
 170 inline
 171 ostream& operator<<(ostream& out, const CacheMemory& obj)
 172 {
 173   obj.print(out);
 174   out << flush;
 175   return out;
 176 }
 177
 178
 179 // ****************************************************************
 180
 181 inline
 182 CacheMemory::CacheMemory(const string & name)
 183   : m_cache_name(name)
 184 {
 185 }
 186
 187 inline
 188 void CacheMemory::init(const vector<string> & argv)
 189 {
 190   int cache_size = 0;
 191   string policy;
 192
 193   m_controller = NULL;
 194   for (uint32 i=0; i<argv.size(); i+=2) {
 195     if (argv[i] == "size_kb") {
 196       cache_size = atoi(argv[i+1].c_str());
 197     } else if (argv[i] == "latency") {
 198       m_latency = atoi(argv[i+1].c_str());
 199     } else if (argv[i] == "assoc") {
 200       m_cache_assoc = atoi(argv[i+1].c_str());
 201     } else if (argv[i] == "replacement_policy") {
 202       policy = argv[i+1];
 203     } else if (argv[i] == "controller") {
 204       m_controller = RubySystem::getController(argv[i+1]);
 205     } else {
 206       cerr << "WARNING: CacheMemory: Unknown configuration parameter: " << argv[i] << endl;
 207     }
 208   }
 209
 210   m_cache_num_sets = cache_size / m_cache_assoc;
 211   m_cache_num_set_bits = log_int(m_cache_num_sets);
 212
 213   if(policy == "PSEUDO_LRU")
 214     m_replacementPolicy_ptr = new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc);
 215   else if (policy == "LRU")
 216     m_replacementPolicy_ptr = new LRUPolicy(m_cache_num_sets, m_cache_assoc);
 217   else
 218     assert(false);
 219
 220   m_cache.setSize(m_cache_num_sets);
 221   m_locked.setSize(m_cache_num_sets);
 222   for (int i = 0; i < m_cache_num_sets; i++) {
 223     m_cache[i].setSize(m_cache_assoc);
 224     m_locked[i].setSize(m_cache_assoc);
 225     for (int j = 0; j < m_cache_assoc; j++) {
 226       m_cache[i][j] = NULL;
 227       m_locked[i][j] = -1;
 228     }
 229   }
 230 }
 231
 232 inline
 233 CacheMemory::~CacheMemory()
 234 {
 235   if(m_replacementPolicy_ptr != NULL)
 236     delete m_replacementPolicy_ptr;
 237 }
 238
 239 inline
 240 void CacheMemory::printConfig(ostream& out)
 241 {
 242   out << "Cache config: " << m_cache_name << endl;
 243   if (m_controller != NULL)
 244     out << "  controller: " << m_controller->getName() << endl;
 245   out << "  cache_associativity: " << m_cache_assoc << endl;
 246   out << "  num_cache_sets_bits: " << m_cache_num_set_bits << endl;
 247   const int cache_num_sets = 1 << m_cache_num_set_bits;
 248   out << "  num_cache_sets: " << cache_num_sets << endl;
 249   out << "  cache_set_size_bytes: " << cache_num_sets * RubySystem::getBlockSizeBytes() << endl;
 250   out << "  cache_set_size_Kbytes: "
 251       << double(cache_num_sets * RubySystem::getBlockSizeBytes()) / (1<<10) << endl;
 252   out << "  cache_set_size_Mbytes: "
 253       << double(cache_num_sets * RubySystem::getBlockSizeBytes()) / (1<<20) << endl;
 254   out << "  cache_size_bytes: "
 255       << cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc << endl;
 256   out << "  cache_size_Kbytes: "
 257       << double(cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc) / (1<<10) << endl;
 258   out << "  cache_size_Mbytes: "
 259       << double(cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc) / (1<<20) << endl;
 260 }
 261
 262 // PRIVATE METHODS
 263
 264 // convert a Address to its location in the cache
 265 inline
 266 Index CacheMemory::addressToCacheSet(const Address& address) const
 267 {
 268   assert(address == line_address(address));
 269   return address.bitSelect(RubySystem::getBlockSizeBits(), RubySystem::getBlockSizeBits() + m_cache_num_set_bits-1);
 270 }
 271
 272 // Given a cache index: returns the index of the tag in a set.
 273 // returns -1 if the tag is not found.
 274 inline
 275 int CacheMemory::findTagInSet(Index cacheSet, const Address& tag) const
 276 {
 277   assert(tag == line_address(tag));
 278   // search the set for the tags
 279   for (int i=0; i < m_cache_assoc; i++) {
 280     if ((m_cache[cacheSet][i] != NULL) &&
 281         (m_cache[cacheSet][i]->m_Address == tag) &&
 282         (m_cache[cacheSet][i]->m_Permission != AccessPermission_NotPresent)) {
 283       return i;
 284     }
 285   }
 286   return -1; // Not found
 287 }
 288
 289 // Given a cache index: returns the index of the tag in a set.
 290 // returns -1 if the tag is not found.
 291 inline
 292 int CacheMemory::findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const
 293 {
 294   assert(tag == line_address(tag));
 295   // search the set for the tags
 296   for (int i=0; i < m_cache_assoc; i++) {
 297     if (m_cache[cacheSet][i] != NULL && m_cache[cacheSet][i]->m_Address == tag)
 298       return i;
 299   }
 300   return -1; // Not found
 301 }
 302
 303 // PUBLIC METHODS
 304 inline
 305 bool CacheMemory::tryCacheAccess(const Address& address,
 306                                  CacheRequestType type,
 307                                  DataBlock*& data_ptr)
 308 {
 309   assert(address == line_address(address));
 310   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 311   Index cacheSet = addressToCacheSet(address);
 312   int loc = findTagInSet(cacheSet, address);
 313   if(loc != -1){ // Do we even have a tag match?
 314     AbstractCacheEntry* entry = m_cache[cacheSet][loc];
 315     m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
 316     data_ptr = &(entry->getDataBlk());
 317
 318     if(entry->m_Permission == AccessPermission_Read_Write) {
 319       return true;
 320     }
 321     if ((entry->m_Permission == AccessPermission_Read_Only) &&
 322         (type == CacheRequestType_LD || type == CacheRequestType_IFETCH)) {
 323       return true;
 324     }
 325     // The line must not be accessible
 326   }
 327   data_ptr = NULL;
 328   return false;
 329 }
 330
 331 inline
 332 bool CacheMemory::testCacheAccess(const Address& address,
 333                                   CacheRequestType type,
 334                                   DataBlock*& data_ptr)
 335 {
 336   assert(address == line_address(address));
 337   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 338   Index cacheSet = addressToCacheSet(address);
 339   int loc = findTagInSet(cacheSet, address);
 340   if(loc != -1){ // Do we even have a tag match?
 341     AbstractCacheEntry* entry = m_cache[cacheSet][loc];
 342     m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
 343     data_ptr = &(entry->getDataBlk());
 344
 345     return (m_cache[cacheSet][loc]->m_Permission != AccessPermission_NotPresent);
 346   }
 347   data_ptr = NULL;
 348   return false;
 349 }
 350
 351 // tests to see if an address is present in the cache
 352 inline
 353 bool CacheMemory::isTagPresent(const Address& address) const
 354 {
 355   assert(address == line_address(address));
 356   Index cacheSet = addressToCacheSet(address);
 357   int location = findTagInSet(cacheSet, address);
 358
 359   if (location == -1) {
 360     // We didn't find the tag
 361     DEBUG_EXPR(CACHE_COMP, LowPrio, address);
 362     DEBUG_MSG(CACHE_COMP, LowPrio, "No tag match");
 363     return false;
 364   }
 365   DEBUG_EXPR(CACHE_COMP, LowPrio, address);
 366   DEBUG_MSG(CACHE_COMP, LowPrio, "found");
 367   return true;
 368 }
 369
 370 // Returns true if there is:
 371 //   a) a tag match on this address or there is
 372 //   b) an unused line in the same cache "way"
 373 inline
 374 bool CacheMemory::cacheAvail(const Address& address) const
 375 {
 376   assert(address == line_address(address));
 377
 378   Index cacheSet = addressToCacheSet(address);
 379
 380   for (int i=0; i < m_cache_assoc; i++) {
 381     AbstractCacheEntry* entry = m_cache[cacheSet][i];
 382     if (entry != NULL) {
 383       if (entry->m_Address == address ||                         // Already in the cache
 384           entry->m_Permission == AccessPermission_NotPresent) {  // We found an empty entry
 385         return true;
 386       }
 387     } else {
 388       return true;
 389     }
 390   }
 391   return false;
 392 }
 393
 394 inline
 395 void CacheMemory::allocate(const Address& address, AbstractCacheEntry* entry)
 396 {
 397   assert(address == line_address(address));
 398   assert(!isTagPresent(address));
 399   assert(cacheAvail(address));
 400   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 401
 402   // Find the first open slot
 403   Index cacheSet = addressToCacheSet(address);
 404   for (int i=0; i < m_cache_assoc; i++) {
 405     if (m_cache[cacheSet][i] == NULL ||
 406         m_cache[cacheSet][i]->m_Permission == AccessPermission_NotPresent) {
 407       m_cache[cacheSet][i] = entry;  // Init entry
 408       m_cache[cacheSet][i]->m_Address = address;
 409       m_cache[cacheSet][i]->m_Permission = AccessPermission_Invalid;
 410       m_locked[cacheSet][i] = -1;
 411
 412       m_replacementPolicy_ptr->touch(cacheSet, i, g_eventQueue_ptr->getTime());
 413
 414       return;
 415     }
 416   }
 417   ERROR_MSG("Allocate didn't find an available entry");
 418 }
 419
 420 inline
 421 void CacheMemory::deallocate(const Address& address)
 422 {
 423   assert(address == line_address(address));
 424   assert(isTagPresent(address));
 425   DEBUG_EXPR(CACHE_COMP, HighPrio, address);
 426   Index cacheSet = addressToCacheSet(address);
 427   int location = findTagInSet(cacheSet, address);
 428   if (location != -1){
 429     delete m_cache[cacheSet][location];
 430     m_cache[cacheSet][location] = NULL;
 431     m_locked[cacheSet][location] = -1;
 432   }
 433 }
 434
 435 // Returns with the physical address of the conflicting cache line
 436 inline
 437 Address CacheMemory::cacheProbe(const Address& address) const
 438 {
 439   assert(address == line_address(address));
 440   assert(!cacheAvail(address));
 441
 442   Index cacheSet = addressToCacheSet(address);
 443   return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)]->m_Address;
 444 }
 445
 446 // looks an address up in the cache
 447 inline
 448 AbstractCacheEntry& CacheMemory::lookup(const Address& address)
 449 {
 450   assert(address == line_address(address));
 451   Index cacheSet = addressToCacheSet(address);
 452   int loc = findTagInSet(cacheSet, address);
 453   assert(loc != -1);
 454   return *m_cache[cacheSet][loc];
 455 }
 456
 457 // looks an address up in the cache
 458 inline
 459 const AbstractCacheEntry& CacheMemory::lookup(const Address& address) const
 460 {
 461   assert(address == line_address(address));
 462   Index cacheSet = addressToCacheSet(address);
 463   int loc = findTagInSet(cacheSet, address);
 464   assert(loc != -1);
 465   return *m_cache[cacheSet][loc];
 466 }
 467
 468 inline
 469 AccessPermission CacheMemory::getPermission(const Address& address) const
 470 {
 471   assert(address == line_address(address));
 472   return lookup(address).m_Permission;
 473 }
 474
 475 inline
 476 void CacheMemory::changePermission(const Address& address, AccessPermission new_perm)
 477 {
 478   assert(address == line_address(address));
 479   lookup(address).m_Permission = new_perm;
 480   Index cacheSet = addressToCacheSet(address);
 481   int loc = findTagInSet(cacheSet, address);
 482   m_locked[cacheSet][loc] = -1;
 483   assert(getPermission(address) == new_perm);
 484 }
 485
 486 // Sets the most recently used bit for a cache block
 487 inline
 488 void CacheMemory::setMRU(const Address& address)
 489 {
 490   Index cacheSet;
 491
 492   cacheSet = addressToCacheSet(address);
 493   m_replacementPolicy_ptr->touch(cacheSet,
 494                                  findTagInSet(cacheSet, address),
 495                                  g_eventQueue_ptr->getTime());
 496 }
 497
 498 inline
 499 void CacheMemory::recordCacheContents(CacheRecorder& tr) const
 500 {
 501   for (int i = 0; i < m_cache_num_sets; i++) {
 502     for (int j = 0; j < m_cache_assoc; j++) {
 503       AccessPermission perm = m_cache[i][j]->m_Permission;
 504       CacheRequestType request_type = CacheRequestType_NULL;
 505       if (perm == AccessPermission_Read_Only) {
 506         if (m_is_instruction_only_cache) {
 507           request_type = CacheRequestType_IFETCH;
 508         } else {
 509           request_type = CacheRequestType_LD;
 510         }
 511       } else if (perm == AccessPermission_Read_Write) {
 512         request_type = CacheRequestType_ST;
 513       }
 514
 515       if (request_type != CacheRequestType_NULL) {
 516         //        tr.addRecord(m_chip_ptr->getID(), m_cache[i][j].m_Address,
 517         //                     Address(0), request_type, m_replacementPolicy_ptr->getLastAccess(i, j));
 518       }
 519     }
 520   }
 521 }
 522
 523 inline
 524 void CacheMemory::print(ostream& out) const
 525 {
 526   out << "Cache dump: " << m_cache_name << endl;
 527   for (int i = 0; i < m_cache_num_sets; i++) {
 528     for (int j = 0; j < m_cache_assoc; j++) {
 529       if (m_cache[i][j] != NULL) {
 530         out << "  Index: " << i
 531             << " way: " << j
 532             << " entry: " << *m_cache[i][j] << endl;
 533       } else {
 534         out << "  Index: " << i
 535             << " way: " << j
 536             << " entry: NULL" << endl;
 537       }
 538     }
 539   }
 540 }
 541
 542 inline
 543 void CacheMemory::printData(ostream& out) const
 544 {
 545   out << "printData() not supported" << endl;
 546 }
 547
 548 inline
 549 void CacheMemory::getMemoryValue(const Address& addr, char* value,
 550                                  unsigned int size_in_bytes ){
 551   AbstractCacheEntry& entry = lookup(line_address(addr));
 552   unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
 553   for(unsigned int i=0; i<size_in_bytes; ++i){
 554     value[i] = entry.getDataBlk().getByte(i + startByte);
 555   }
 556 }
 557
 558 inline
 559 void CacheMemory::setMemoryValue(const Address& addr, char* value,
 560                                  unsigned int size_in_bytes ){
 561   AbstractCacheEntry& entry = lookup(line_address(addr));
 562   unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
 563   assert(size_in_bytes > 0);
 564   for(unsigned int i=0; i<size_in_bytes; ++i){
 565     entry.getDataBlk().setByte(i + startByte, value[i]);
 566   }
 567
 568   //  entry = lookup(line_address(addr));
 569 }
 570
 571 inline
 572 void
 573 CacheMemory::setLocked(const Address& address, int context)
 574 {
 575   assert(address == line_address(address));
 576   Index cacheSet = addressToCacheSet(address);
 577   int loc = findTagInSet(cacheSet, address);
 578   assert(loc != -1);
 579   m_locked[cacheSet][loc] = context;
 580 }
 581
 582 inline
 583 void
 584 CacheMemory::clearLocked(const Address& address)
 585 {
 586   assert(address == line_address(address));
 587   Index cacheSet = addressToCacheSet(address);
 588   int loc = findTagInSet(cacheSet, address);
 589   assert(loc != -1);
 590   m_locked[cacheSet][loc] = -1;
 591 }
 592
 593 inline
 594 bool
 595 CacheMemory::isLocked(const Address& address, int context)
 596 {
 597   assert(address == line_address(address));
 598   Index cacheSet = addressToCacheSet(address);
 599   int loc = findTagInSet(cacheSet, address);
 600   assert(loc != -1);
 601   return m_locked[cacheSet][loc] == context;
 602 }
 603
 604 #endif //CACHEMEMORY_H
 605