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