CacheMemory.cc revision 9105
1/* 2 * Copyright (c) 1999-2012 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#include "base/intmath.hh" 30#include "debug/RubyCache.hh" 31#include "debug/RubyCacheTrace.hh" 32#include "debug/RubyResourceStalls.hh" 33#include "debug/RubyStats.hh" 34#include "mem/protocol/AccessPermission.hh" 35#include "mem/ruby/system/CacheMemory.hh" 36#include "mem/ruby/system/System.hh" 37 38using namespace std; 39 40ostream& 41operator<<(ostream& out, const CacheMemory& obj) 42{ 43 obj.print(out); 44 out << flush; 45 return out; 46} 47 48CacheMemory * 49RubyCacheParams::create() 50{ 51 return new CacheMemory(this); 52} 53 54CacheMemory::CacheMemory(const Params *p) 55 : SimObject(p), 56 dataArray(p->dataArrayBanks, p->dataAccessLatency, p->start_index_bit), 57 tagArray(p->tagArrayBanks, p->tagAccessLatency, p->start_index_bit) 58{ 59 m_cache_size = p->size; 60 m_latency = p->latency; 61 m_cache_assoc = p->assoc; 62 m_policy = p->replacement_policy; 63 m_profiler_ptr = new CacheProfiler(name()); 64 m_start_index_bit = p->start_index_bit; 65 m_is_instruction_only_cache = p->is_icache; 66 m_resource_stalls = p->resourceStalls; 67} 68 69void 70CacheMemory::init() 71{ 72 m_cache_num_sets = (m_cache_size / m_cache_assoc) / 73 RubySystem::getBlockSizeBytes(); 74 assert(m_cache_num_sets > 1); 75 m_cache_num_set_bits = floorLog2(m_cache_num_sets); 76 assert(m_cache_num_set_bits > 0); 77 78 if (m_policy == "PSEUDO_LRU") 79 m_replacementPolicy_ptr = 80 new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc); 81 else if (m_policy == "LRU") 82 m_replacementPolicy_ptr = 83 new LRUPolicy(m_cache_num_sets, m_cache_assoc); 84 else 85 assert(false); 86 87 m_cache.resize(m_cache_num_sets); 88 for (int i = 0; i < m_cache_num_sets; i++) { 89 m_cache[i].resize(m_cache_assoc); 90 for (int j = 0; j < m_cache_assoc; j++) { 91 m_cache[i][j] = NULL; 92 } 93 } 94} 95 96CacheMemory::~CacheMemory() 97{ 98 if (m_replacementPolicy_ptr != NULL) 99 delete m_replacementPolicy_ptr; 100 delete m_profiler_ptr; 101 for (int i = 0; i < m_cache_num_sets; i++) { 102 for (int j = 0; j < m_cache_assoc; j++) { 103 delete m_cache[i][j]; 104 } 105 } 106} 107 108void 109CacheMemory::printConfig(ostream& out) 110{ 111 int block_size = RubySystem::getBlockSizeBytes(); 112 113 out << "Cache config: " << m_cache_name << endl; 114 out << " cache_associativity: " << m_cache_assoc << endl; 115 out << " num_cache_sets_bits: " << m_cache_num_set_bits << endl; 116 const int cache_num_sets = 1 << m_cache_num_set_bits; 117 out << " num_cache_sets: " << cache_num_sets << endl; 118 out << " cache_set_size_bytes: " << cache_num_sets * block_size << endl; 119 out << " cache_set_size_Kbytes: " 120 << double(cache_num_sets * block_size) / (1<<10) << endl; 121 out << " cache_set_size_Mbytes: " 122 << double(cache_num_sets * block_size) / (1<<20) << endl; 123 out << " cache_size_bytes: " 124 << cache_num_sets * block_size * m_cache_assoc << endl; 125 out << " cache_size_Kbytes: " 126 << double(cache_num_sets * block_size * m_cache_assoc) / (1<<10) 127 << endl; 128 out << " cache_size_Mbytes: " 129 << double(cache_num_sets * block_size * m_cache_assoc) / (1<<20) 130 << endl; 131} 132 133// convert a Address to its location in the cache 134Index 135CacheMemory::addressToCacheSet(const Address& address) const 136{ 137 assert(address == line_address(address)); 138 return address.bitSelect(m_start_index_bit, 139 m_start_index_bit + m_cache_num_set_bits - 1); 140} 141 142// Given a cache index: returns the index of the tag in a set. 143// returns -1 if the tag is not found. 144int 145CacheMemory::findTagInSet(Index cacheSet, const Address& tag) const 146{ 147 assert(tag == line_address(tag)); 148 // search the set for the tags 149 m5::hash_map<Address, int>::const_iterator it = m_tag_index.find(tag); 150 if (it != m_tag_index.end()) 151 if (m_cache[cacheSet][it->second]->m_Permission != 152 AccessPermission_NotPresent) 153 return it->second; 154 return -1; // Not found 155} 156 157// Given a cache index: returns the index of the tag in a set. 158// returns -1 if the tag is not found. 159int 160CacheMemory::findTagInSetIgnorePermissions(Index cacheSet, 161 const Address& tag) const 162{ 163 assert(tag == line_address(tag)); 164 // search the set for the tags 165 m5::hash_map<Address, int>::const_iterator it = m_tag_index.find(tag); 166 if (it != m_tag_index.end()) 167 return it->second; 168 return -1; // Not found 169} 170 171bool 172CacheMemory::tryCacheAccess(const Address& address, RubyRequestType type, 173 DataBlock*& data_ptr) 174{ 175 assert(address == line_address(address)); 176 DPRINTF(RubyCache, "address: %s\n", address); 177 Index cacheSet = addressToCacheSet(address); 178 int loc = findTagInSet(cacheSet, address); 179 if (loc != -1) { 180 // Do we even have a tag match? 181 AbstractCacheEntry* entry = m_cache[cacheSet][loc]; 182 m_replacementPolicy_ptr-> 183 touch(cacheSet, loc, g_eventQueue_ptr->getTime()); 184 data_ptr = &(entry->getDataBlk()); 185 186 if (entry->m_Permission == AccessPermission_Read_Write) { 187 return true; 188 } 189 if ((entry->m_Permission == AccessPermission_Read_Only) && 190 (type == RubyRequestType_LD || type == RubyRequestType_IFETCH)) { 191 return true; 192 } 193 // The line must not be accessible 194 } 195 data_ptr = NULL; 196 return false; 197} 198 199bool 200CacheMemory::testCacheAccess(const Address& address, RubyRequestType type, 201 DataBlock*& data_ptr) 202{ 203 assert(address == line_address(address)); 204 DPRINTF(RubyCache, "address: %s\n", address); 205 Index cacheSet = addressToCacheSet(address); 206 int loc = findTagInSet(cacheSet, address); 207 208 if (loc != -1) { 209 // Do we even have a tag match? 210 AbstractCacheEntry* entry = m_cache[cacheSet][loc]; 211 m_replacementPolicy_ptr-> 212 touch(cacheSet, loc, g_eventQueue_ptr->getTime()); 213 data_ptr = &(entry->getDataBlk()); 214 215 return m_cache[cacheSet][loc]->m_Permission != 216 AccessPermission_NotPresent; 217 } 218 219 data_ptr = NULL; 220 return false; 221} 222 223// tests to see if an address is present in the cache 224bool 225CacheMemory::isTagPresent(const Address& address) const 226{ 227 assert(address == line_address(address)); 228 Index cacheSet = addressToCacheSet(address); 229 int loc = findTagInSet(cacheSet, address); 230 231 if (loc == -1) { 232 // We didn't find the tag 233 DPRINTF(RubyCache, "No tag match for address: %s\n", address); 234 return false; 235 } 236 DPRINTF(RubyCache, "address: %s found\n", address); 237 return true; 238} 239 240// Returns true if there is: 241// a) a tag match on this address or there is 242// b) an unused line in the same cache "way" 243bool 244CacheMemory::cacheAvail(const Address& address) const 245{ 246 assert(address == line_address(address)); 247 248 Index cacheSet = addressToCacheSet(address); 249 250 for (int i = 0; i < m_cache_assoc; i++) { 251 AbstractCacheEntry* entry = m_cache[cacheSet][i]; 252 if (entry != NULL) { 253 if (entry->m_Address == address || 254 entry->m_Permission == AccessPermission_NotPresent) { 255 // Already in the cache or we found an empty entry 256 return true; 257 } 258 } else { 259 return true; 260 } 261 } 262 return false; 263} 264 265AbstractCacheEntry* 266CacheMemory::allocate(const Address& address, AbstractCacheEntry* entry) 267{ 268 assert(address == line_address(address)); 269 assert(!isTagPresent(address)); 270 assert(cacheAvail(address)); 271 DPRINTF(RubyCache, "address: %s\n", address); 272 273 // Find the first open slot 274 Index cacheSet = addressToCacheSet(address); 275 std::vector<AbstractCacheEntry*> &set = m_cache[cacheSet]; 276 for (int i = 0; i < m_cache_assoc; i++) { 277 if (!set[i] || set[i]->m_Permission == AccessPermission_NotPresent) { 278 set[i] = entry; // Init entry 279 set[i]->m_Address = address; 280 set[i]->m_Permission = AccessPermission_Invalid; 281 DPRINTF(RubyCache, "Allocate clearing lock for addr: %x\n", 282 address); 283 set[i]->m_locked = -1; 284 m_tag_index[address] = i; 285 286 m_replacementPolicy_ptr-> 287 touch(cacheSet, i, g_eventQueue_ptr->getTime()); 288 289 return entry; 290 } 291 } 292 panic("Allocate didn't find an available entry"); 293} 294 295void 296CacheMemory::deallocate(const Address& address) 297{ 298 assert(address == line_address(address)); 299 assert(isTagPresent(address)); 300 DPRINTF(RubyCache, "address: %s\n", address); 301 Index cacheSet = addressToCacheSet(address); 302 int loc = findTagInSet(cacheSet, address); 303 if (loc != -1) { 304 delete m_cache[cacheSet][loc]; 305 m_cache[cacheSet][loc] = NULL; 306 m_tag_index.erase(address); 307 } 308} 309 310// Returns with the physical address of the conflicting cache line 311Address 312CacheMemory::cacheProbe(const Address& address) const 313{ 314 assert(address == line_address(address)); 315 assert(!cacheAvail(address)); 316 317 Index cacheSet = addressToCacheSet(address); 318 return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)]-> 319 m_Address; 320} 321 322// looks an address up in the cache 323AbstractCacheEntry* 324CacheMemory::lookup(const Address& address) 325{ 326 assert(address == line_address(address)); 327 Index cacheSet = addressToCacheSet(address); 328 int loc = findTagInSet(cacheSet, address); 329 if(loc == -1) return NULL; 330 return m_cache[cacheSet][loc]; 331} 332 333// looks an address up in the cache 334const AbstractCacheEntry* 335CacheMemory::lookup(const Address& address) const 336{ 337 assert(address == line_address(address)); 338 Index cacheSet = addressToCacheSet(address); 339 int loc = findTagInSet(cacheSet, address); 340 if(loc == -1) return NULL; 341 return m_cache[cacheSet][loc]; 342} 343 344// Sets the most recently used bit for a cache block 345void 346CacheMemory::setMRU(const Address& address) 347{ 348 Index cacheSet = addressToCacheSet(address); 349 int loc = findTagInSet(cacheSet, address); 350 351 if(loc != -1) 352 m_replacementPolicy_ptr-> 353 touch(cacheSet, loc, g_eventQueue_ptr->getTime()); 354} 355 356void 357CacheMemory::profileMiss(const RubyRequest& msg) 358{ 359 m_profiler_ptr->addCacheStatSample(msg.getType(), 360 msg.getAccessMode(), 361 msg.getPrefetch()); 362} 363 364void 365CacheMemory::profileGenericRequest(GenericRequestType requestType, 366 RubyAccessMode accessType, 367 PrefetchBit pfBit) 368{ 369 m_profiler_ptr->addGenericStatSample(requestType, 370 accessType, 371 pfBit); 372} 373 374void 375CacheMemory::recordCacheContents(int cntrl, CacheRecorder* tr) const 376{ 377 uint64 warmedUpBlocks = 0; 378 uint64 totalBlocks M5_VAR_USED = (uint64)m_cache_num_sets 379 * (uint64)m_cache_assoc; 380 381 for (int i = 0; i < m_cache_num_sets; i++) { 382 for (int j = 0; j < m_cache_assoc; j++) { 383 if (m_cache[i][j] != NULL) { 384 AccessPermission perm = m_cache[i][j]->m_Permission; 385 RubyRequestType request_type = RubyRequestType_NULL; 386 if (perm == AccessPermission_Read_Only) { 387 if (m_is_instruction_only_cache) { 388 request_type = RubyRequestType_IFETCH; 389 } else { 390 request_type = RubyRequestType_LD; 391 } 392 } else if (perm == AccessPermission_Read_Write) { 393 request_type = RubyRequestType_ST; 394 } 395 396 if (request_type != RubyRequestType_NULL) { 397 tr->addRecord(cntrl, m_cache[i][j]->m_Address.getAddress(), 398 0, request_type, 399 m_replacementPolicy_ptr->getLastAccess(i, j), 400 m_cache[i][j]->getDataBlk()); 401 warmedUpBlocks++; 402 } 403 } 404 } 405 } 406 407 DPRINTF(RubyCacheTrace, "%s: %lli blocks of %lli total blocks" 408 "recorded %.2f%% \n", name().c_str(), warmedUpBlocks, 409 (uint64)m_cache_num_sets * (uint64)m_cache_assoc, 410 (float(warmedUpBlocks)/float(totalBlocks))*100.0); 411} 412 413void 414CacheMemory::print(ostream& out) const 415{ 416 out << "Cache dump: " << m_cache_name << endl; 417 for (int i = 0; i < m_cache_num_sets; i++) { 418 for (int j = 0; j < m_cache_assoc; j++) { 419 if (m_cache[i][j] != NULL) { 420 out << " Index: " << i 421 << " way: " << j 422 << " entry: " << *m_cache[i][j] << endl; 423 } else { 424 out << " Index: " << i 425 << " way: " << j 426 << " entry: NULL" << endl; 427 } 428 } 429 } 430} 431 432void 433CacheMemory::printData(ostream& out) const 434{ 435 out << "printData() not supported" << endl; 436} 437 438void 439CacheMemory::clearStats() const 440{ 441 m_profiler_ptr->clearStats(); 442} 443 444void 445CacheMemory::printStats(ostream& out) const 446{ 447 m_profiler_ptr->printStats(out); 448} 449 450void 451CacheMemory::setLocked(const Address& address, int context) 452{ 453 DPRINTF(RubyCache, "Setting Lock for addr: %x to %d\n", address, context); 454 assert(address == line_address(address)); 455 Index cacheSet = addressToCacheSet(address); 456 int loc = findTagInSet(cacheSet, address); 457 assert(loc != -1); 458 m_cache[cacheSet][loc]->m_locked = context; 459} 460 461void 462CacheMemory::clearLocked(const Address& address) 463{ 464 DPRINTF(RubyCache, "Clear Lock for addr: %x\n", address); 465 assert(address == line_address(address)); 466 Index cacheSet = addressToCacheSet(address); 467 int loc = findTagInSet(cacheSet, address); 468 assert(loc != -1); 469 m_cache[cacheSet][loc]->m_locked = -1; 470} 471 472bool 473CacheMemory::isLocked(const Address& address, int context) 474{ 475 assert(address == line_address(address)); 476 Index cacheSet = addressToCacheSet(address); 477 int loc = findTagInSet(cacheSet, address); 478 assert(loc != -1); 479 DPRINTF(RubyCache, "Testing Lock for addr: %llx cur %d con %d\n", 480 address, m_cache[cacheSet][loc]->m_locked, context); 481 return m_cache[cacheSet][loc]->m_locked == context; 482} 483 484void 485CacheMemory::recordRequestType(CacheRequestType requestType) { 486 DPRINTF(RubyStats, "Recorded statistic: %s\n", 487 CacheRequestType_to_string(requestType)); 488 switch(requestType) { 489 case CacheRequestType_DataArrayRead: 490 numDataArrayReads++; 491 return; 492 case CacheRequestType_DataArrayWrite: 493 numDataArrayWrites++; 494 return; 495 case CacheRequestType_TagArrayRead: 496 numTagArrayReads++; 497 return; 498 case CacheRequestType_TagArrayWrite: 499 numTagArrayWrites++; 500 return; 501 default: 502 warn("CacheMemory access_type not found: %s", 503 CacheRequestType_to_string(requestType)); 504 } 505} 506 507void 508CacheMemory::regStats() { 509 using namespace Stats; 510 511 numDataArrayReads 512 .name(name() + ".num_data_array_reads") 513 .desc("number of data array reads") 514 ; 515 516 numDataArrayWrites 517 .name(name() + ".num_data_array_writes") 518 .desc("number of data array writes") 519 ; 520 521 numTagArrayReads 522 .name(name() + ".num_tag_array_reads") 523 .desc("number of tag array reads") 524 ; 525 526 numTagArrayWrites 527 .name(name() + ".num_tag_array_writes") 528 .desc("number of tag array writes") 529 ; 530 531 numTagArrayStalls 532 .name(name() + ".num_tag_array_stalls") 533 .desc("number of stalls caused by tag array") 534 ; 535 536 numDataArrayStalls 537 .name(name() + ".num_data_array_stalls") 538 .desc("number of stalls caused by data array") 539 ; 540} 541 542bool 543CacheMemory::checkResourceAvailable(CacheResourceType res, Address addr) 544{ 545 if (!m_resource_stalls) { 546 return true; 547 } 548 549 if (res == CacheResourceType_TagArray) { 550 if (tagArray.tryAccess(addressToCacheSet(addr))) return true; 551 else { 552 DPRINTF(RubyResourceStalls, "Tag array stall on addr %s in set %d\n", addr, addressToCacheSet(addr)); 553 numTagArrayStalls++; 554 return false; 555 } 556 } else if (res == CacheResourceType_DataArray) { 557 if (dataArray.tryAccess(addressToCacheSet(addr))) return true; 558 else { 559 DPRINTF(RubyResourceStalls, "Data array stall on addr %s in set %d\n", addr, addressToCacheSet(addr)); 560 numDataArrayStalls++; 561 return false; 562 } 563 } else { 564 assert(false); 565 return true; 566 } 567} 568 569