2 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
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.
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.
34 * $Id: CacheMemory.hh,v 3.7 2004/06/18 20:15:15 beckmann Exp $
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"
61 CacheMemory(const string & name);
62 void init(const vector<string> & argv);
68 // static CacheMemory* createCache(int level, int num, char split_type, AbstractCacheEntry* (*entry_factory)());
69 // static CacheMemory* getCache(int cache_id);
72 void printConfig(ostream& out);
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);
77 // similar to above, but doesn't require full access check
78 bool testCacheAccess(const Address& address, CacheRequestType type, DataBlock*& data_ptr);
80 // tests to see if an address is present in the cache
81 bool isTagPresent(const Address& address) const;
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;
88 // find an unused entry and sets the tag appropriate for the address
89 void allocate(const Address& address, AbstractCacheEntry* new_entry);
91 // Explicitly free up this address
92 void deallocate(const Address& address);
94 // Returns with the physical address of the conflicting cache line
95 Address cacheProbe(const Address& address) const;
97 // looks an address up in the cache
98 AbstractCacheEntry& lookup(const Address& address);
99 const AbstractCacheEntry& lookup(const Address& address) const;
101 // Get/Set permission of cache block
102 AccessPermission getPermission(const Address& address) const;
103 void changePermission(const Address& address, AccessPermission new_perm);
105 int getLatency() const { return m_latency; }
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; }
111 // Set this address to most recently used
112 void setMRU(const Address& address);
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 );
119 // Print cache contents
120 void print(ostream& out) const;
121 void printData(ostream& out) const;
126 // convert a Address to its location in the cache
127 Index addressToCacheSet(const Address& address) const;
129 // Given a cache tag: returns the index of the tag in a set.
130 // returns -1 if the tag is not found.
131 int findTagInSet(Index line, const Address& tag) const;
132 int findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const;
134 // Private copy constructor and assignment operator
135 CacheMemory(const CacheMemory& obj);
136 CacheMemory& operator=(const CacheMemory& obj);
139 const string m_cache_name;
140 AbstractController* m_controller;
143 // Data Members (m_prefix)
144 bool m_is_instruction_only_cache;
145 bool m_is_data_only_cache;
147 // The first index is the # of cache lines.
148 // The second index is the the amount associativity.
149 Vector<Vector<AbstractCacheEntry*> > m_cache;
151 AbstractReplacementPolicy *m_replacementPolicy_ptr;
153 int m_cache_num_sets;
154 int m_cache_num_set_bits;
157 static Vector< CacheMemory* > m_all_caches;
161 CacheMemory* CacheMemory::getCache(int cache_id)
163 assert(cache_id < RubyConfig::getNumberOfCaches());
164 if (m_all_caches[cache_id] == NULL) {
165 cerr << "ERROR: Tried to obtain CacheMemory that hasn't been created yet." << endl;
168 return m_all_caches[cache_id];
172 CacheMemory* CacheMemory::createCache(int level, int num, char split_type_c, AbstractCacheEntry* (*entry_factory)())
175 switch(split_type_c) {
177 split_type = "instruction"; break;
179 split_type = "data"; break;
181 split_type = "unified"; break;
183 int cache_id = RubyConfig::getCacheIDFromParams(level, num, split_type);
184 assert(cache_id < RubyConfig::getNumberOfCaches());
185 if (m_all_caches.size() == 0) {
186 m_all_caches.setSize(RubyConfig::getNumberOfCaches());
187 for (int i=0; i<m_all_caches.size(); i++)
188 m_all_caches[i] = NULL;
191 string type = RubyConfig::getCacheType(cache_id);
192 if ( type == "SetAssociativeCache" ) {
193 m_all_caches[cache_id] = new CacheMemory(cache_id, entry_factory);
195 return m_all_caches[cache_id];
198 // Output operator declaration
199 //ostream& operator<<(ostream& out, const CacheMemory<ENTRY>& obj);
201 // ******************* Definitions *******************
203 // Output operator definition
205 ostream& operator<<(ostream& out, const CacheMemory& obj)
213 // ****************************************************************
216 CacheMemory::CacheMemory(const string & name)
222 void CacheMemory::init(const vector<string> & argv)
228 for (uint32 i=0; i<argv.size(); i+=2) {
229 if (argv[i] == "size_kb") {
230 cache_size = atoi(argv[i+1].c_str());
231 } else if (argv[i] == "latency") {
232 m_latency = atoi(argv[i+1].c_str());
233 } else if (argv[i] == "assoc") {
234 m_cache_assoc = atoi(argv[i+1].c_str());
235 } else if (argv[i] == "replacement_policy") {
237 } else if (argv[i] == "controller") {
238 m_controller = RubySystem::getController(argv[i+1]);
240 cerr << "WARNING: CacheMemory: Unknown configuration parameter: " << argv[i] << endl;
244 m_cache_num_sets = cache_size / m_cache_assoc;
245 m_cache_num_set_bits = log_int(m_cache_num_sets);
247 if(policy == "PSEUDO_LRU")
248 m_replacementPolicy_ptr = new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc);
249 else if (policy == "LRU")
250 m_replacementPolicy_ptr = new LRUPolicy(m_cache_num_sets, m_cache_assoc);
254 m_cache.setSize(m_cache_num_sets);
255 for (int i = 0; i < m_cache_num_sets; i++) {
256 m_cache[i].setSize(m_cache_assoc);
257 for (int j = 0; j < m_cache_assoc; j++) {
258 m_cache[i][j] = NULL;
264 CacheMemory::CacheMemory(int cache_id, AbstractCacheEntry* (*entry_factory)())
268 m_cache_id = cache_id;
269 m_entry_factory = entry_factory;
271 m_cache_num_set_bits = RubyConfig::getNumberOfCacheSetBits(cache_id);
272 m_cache_num_sets = RubyConfig::getNumberOfCacheSets(cache_id);
273 m_cache_assoc = RubyConfig::getCacheAssoc(cache_id);
274 split_type = RubyConfig::getCacheSplitType(cache_id);
275 m_is_instruction_only_cache = m_is_data_only_cache = false;
276 if (split_type == "instruction")
277 m_is_instruction_only_cache = true;
278 else if (split_type == "data")
279 m_is_data_only_cache = true;
281 assert(split_type == "unified");
283 if(RubyConfig::getCacheReplacementPolicy(cache_id) == "PSEUDO_LRU")
284 m_replacementPolicy_ptr = new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc);
285 else if(RubyConfig::getCacheReplacementPolicy(cache_id) == "LRU")
286 m_replacementPolicy_ptr = new LRUPolicy(m_cache_num_sets, m_cache_assoc);
290 m_cache.setSize(m_cache_num_sets);
291 for (int i = 0; i < m_cache_num_sets; i++) {
292 m_cache[i].setSize(m_cache_assoc);
293 for (int j = 0; j < m_cache_assoc; j++) {
294 m_cache[i][j] = m_entry_factory();
300 CacheMemory::~CacheMemory()
302 if(m_replacementPolicy_ptr != NULL)
303 delete m_replacementPolicy_ptr;
307 void CacheMemory::printConfig(ostream& out)
309 out << "Cache config: " << m_cache_name << endl;
310 if (m_controller != NULL)
311 out << " controller: " << m_controller->getName() << endl;
312 out << " cache_associativity: " << m_cache_assoc << endl;
313 out << " num_cache_sets_bits: " << m_cache_num_set_bits << endl;
314 const int cache_num_sets = 1 << m_cache_num_set_bits;
315 out << " num_cache_sets: " << cache_num_sets << endl;
316 out << " cache_set_size_bytes: " << cache_num_sets * RubySystem::getBlockSizeBytes() << endl;
317 out << " cache_set_size_Kbytes: "
318 << double(cache_num_sets * RubySystem::getBlockSizeBytes()) / (1<<10) << endl;
319 out << " cache_set_size_Mbytes: "
320 << double(cache_num_sets * RubySystem::getBlockSizeBytes()) / (1<<20) << endl;
321 out << " cache_size_bytes: "
322 << cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc << endl;
323 out << " cache_size_Kbytes: "
324 << double(cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc) / (1<<10) << endl;
325 out << " cache_size_Mbytes: "
326 << double(cache_num_sets * RubySystem::getBlockSizeBytes() * m_cache_assoc) / (1<<20) << endl;
331 // convert a Address to its location in the cache
333 Index CacheMemory::addressToCacheSet(const Address& address) const
335 assert(address == line_address(address));
336 return address.bitSelect(RubySystem::getBlockSizeBits(), RubySystem::getBlockSizeBits() + m_cache_num_set_bits-1);
339 // Given a cache index: returns the index of the tag in a set.
340 // returns -1 if the tag is not found.
342 int CacheMemory::findTagInSet(Index cacheSet, const Address& tag) const
344 assert(tag == line_address(tag));
345 // search the set for the tags
346 for (int i=0; i < m_cache_assoc; i++) {
347 if ((m_cache[cacheSet][i] != NULL) &&
348 (m_cache[cacheSet][i]->m_Address == tag) &&
349 (m_cache[cacheSet][i]->m_Permission != AccessPermission_NotPresent)) {
353 return -1; // Not found
356 // Given a cache index: returns the index of the tag in a set.
357 // returns -1 if the tag is not found.
359 int CacheMemory::findTagInSetIgnorePermissions(Index cacheSet, const Address& tag) const
361 assert(tag == line_address(tag));
362 // search the set for the tags
363 for (int i=0; i < m_cache_assoc; i++) {
364 if (m_cache[cacheSet][i] != NULL && m_cache[cacheSet][i]->m_Address == tag)
367 return -1; // Not found
372 bool CacheMemory::tryCacheAccess(const Address& address,
373 CacheRequestType type,
374 DataBlock*& data_ptr)
376 assert(address == line_address(address));
377 DEBUG_EXPR(CACHE_COMP, HighPrio, address);
378 Index cacheSet = addressToCacheSet(address);
379 int loc = findTagInSet(cacheSet, address);
380 if(loc != -1){ // Do we even have a tag match?
381 AbstractCacheEntry* entry = m_cache[cacheSet][loc];
382 m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
383 data_ptr = &(entry->getDataBlk());
385 if(entry->m_Permission == AccessPermission_Read_Write) {
388 if ((entry->m_Permission == AccessPermission_Read_Only) &&
389 (type == CacheRequestType_LD || type == CacheRequestType_IFETCH)) {
392 // The line must not be accessible
399 bool CacheMemory::testCacheAccess(const Address& address,
400 CacheRequestType type,
401 DataBlock*& data_ptr)
403 assert(address == line_address(address));
404 DEBUG_EXPR(CACHE_COMP, HighPrio, address);
405 Index cacheSet = addressToCacheSet(address);
406 int loc = findTagInSet(cacheSet, address);
407 if(loc != -1){ // Do we even have a tag match?
408 AbstractCacheEntry* entry = m_cache[cacheSet][loc];
409 m_replacementPolicy_ptr->touch(cacheSet, loc, g_eventQueue_ptr->getTime());
410 data_ptr = &(entry->getDataBlk());
412 return (m_cache[cacheSet][loc]->m_Permission != AccessPermission_NotPresent);
418 // tests to see if an address is present in the cache
420 bool CacheMemory::isTagPresent(const Address& address) const
422 assert(address == line_address(address));
423 Index cacheSet = addressToCacheSet(address);
424 int location = findTagInSet(cacheSet, address);
426 if (location == -1) {
427 // We didn't find the tag
428 DEBUG_EXPR(CACHE_COMP, LowPrio, address);
429 DEBUG_MSG(CACHE_COMP, LowPrio, "No tag match");
432 DEBUG_EXPR(CACHE_COMP, LowPrio, address);
433 DEBUG_MSG(CACHE_COMP, LowPrio, "found");
437 // Returns true if there is:
438 // a) a tag match on this address or there is
439 // b) an unused line in the same cache "way"
441 bool CacheMemory::cacheAvail(const Address& address) const
443 assert(address == line_address(address));
445 Index cacheSet = addressToCacheSet(address);
447 for (int i=0; i < m_cache_assoc; i++) {
448 AbstractCacheEntry* entry = m_cache[cacheSet][i];
450 if (entry->m_Address == address || // Already in the cache
451 entry->m_Permission == AccessPermission_NotPresent) { // We found an empty entry
462 void CacheMemory::allocate(const Address& address, AbstractCacheEntry* entry)
464 assert(address == line_address(address));
465 assert(!isTagPresent(address));
466 assert(cacheAvail(address));
467 DEBUG_EXPR(CACHE_COMP, HighPrio, address);
469 // Find the first open slot
470 Index cacheSet = addressToCacheSet(address);
471 for (int i=0; i < m_cache_assoc; i++) {
472 if (m_cache[cacheSet][i] == NULL ||
473 m_cache[cacheSet][i]->m_Permission == AccessPermission_NotPresent) {
474 m_cache[cacheSet][i] = entry; // Init entry
475 m_cache[cacheSet][i]->m_Address = address;
476 m_cache[cacheSet][i]->m_Permission = AccessPermission_Invalid;
478 m_replacementPolicy_ptr->touch(cacheSet, i, g_eventQueue_ptr->getTime());
483 ERROR_MSG("Allocate didn't find an available entry");
487 void CacheMemory::deallocate(const Address& address)
489 assert(address == line_address(address));
490 assert(isTagPresent(address));
491 DEBUG_EXPR(CACHE_COMP, HighPrio, address);
492 Index cacheSet = addressToCacheSet(address);
493 int location = findTagInSet(cacheSet, address);
495 delete m_cache[cacheSet][location];
496 m_cache[cacheSet][location] = NULL;
500 // Returns with the physical address of the conflicting cache line
502 Address CacheMemory::cacheProbe(const Address& address) const
504 assert(address == line_address(address));
505 assert(!cacheAvail(address));
507 Index cacheSet = addressToCacheSet(address);
508 return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)]->m_Address;
511 // looks an address up in the cache
513 AbstractCacheEntry& CacheMemory::lookup(const Address& address)
515 assert(address == line_address(address));
516 Index cacheSet = addressToCacheSet(address);
517 int loc = findTagInSet(cacheSet, address);
519 return *m_cache[cacheSet][loc];
522 // looks an address up in the cache
524 const AbstractCacheEntry& CacheMemory::lookup(const Address& address) const
526 assert(address == line_address(address));
527 Index cacheSet = addressToCacheSet(address);
528 int loc = findTagInSet(cacheSet, address);
530 return *m_cache[cacheSet][loc];
534 AccessPermission CacheMemory::getPermission(const Address& address) const
536 assert(address == line_address(address));
537 return lookup(address).m_Permission;
541 void CacheMemory::changePermission(const Address& address, AccessPermission new_perm)
543 assert(address == line_address(address));
544 lookup(address).m_Permission = new_perm;
545 assert(getPermission(address) == new_perm);
548 // Sets the most recently used bit for a cache block
550 void CacheMemory::setMRU(const Address& address)
554 cacheSet = addressToCacheSet(address);
555 m_replacementPolicy_ptr->touch(cacheSet,
556 findTagInSet(cacheSet, address),
557 g_eventQueue_ptr->getTime());
561 void CacheMemory::recordCacheContents(CacheRecorder& tr) const
563 for (int i = 0; i < m_cache_num_sets; i++) {
564 for (int j = 0; j < m_cache_assoc; j++) {
565 AccessPermission perm = m_cache[i][j]->m_Permission;
566 CacheRequestType request_type = CacheRequestType_NULL;
567 if (perm == AccessPermission_Read_Only) {
568 if (m_is_instruction_only_cache) {
569 request_type = CacheRequestType_IFETCH;
571 request_type = CacheRequestType_LD;
573 } else if (perm == AccessPermission_Read_Write) {
574 request_type = CacheRequestType_ST;
577 if (request_type != CacheRequestType_NULL) {
578 // tr.addRecord(m_chip_ptr->getID(), m_cache[i][j].m_Address,
579 // Address(0), request_type, m_replacementPolicy_ptr->getLastAccess(i, j));
586 void CacheMemory::print(ostream& out) const
588 out << "Cache dump: " << m_cache_name << endl;
589 for (int i = 0; i < m_cache_num_sets; i++) {
590 for (int j = 0; j < m_cache_assoc; j++) {
591 if (m_cache[i][j] != NULL) {
592 out << " Index: " << i
594 << " entry: " << *m_cache[i][j] << endl;
596 out << " Index: " << i
598 << " entry: NULL" << endl;
605 void CacheMemory::printData(ostream& out) const
607 out << "printData() not supported" << endl;
611 void CacheMemory::getMemoryValue(const Address& addr, char* value,
612 unsigned int size_in_bytes ){
613 AbstractCacheEntry& entry = lookup(line_address(addr));
614 unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
615 for(unsigned int i=0; i<size_in_bytes; ++i){
616 value[i] = entry.getDataBlk().getByte(i + startByte);
621 void CacheMemory::setMemoryValue(const Address& addr, char* value,
622 unsigned int size_in_bytes ){
623 AbstractCacheEntry& entry = lookup(line_address(addr));
624 unsigned int startByte = addr.getAddress() - line_address(addr).getAddress();
625 assert(size_in_bytes > 0);
626 for(unsigned int i=0; i<size_in_bytes; ++i){
627 entry.getDataBlk().setByte(i + startByte, value[i]);
630 // entry = lookup(line_address(addr));
633 #endif //CACHEMEMORY_H