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