fa_lru.cc revision 13215
1/* 2 * Copyright (c) 2018 Inria 3 * Copyright (c) 2013,2016-2018 ARM Limited 4 * All rights reserved. 5 * 6 * The license below extends only to copyright in the software and shall 7 * not be construed as granting a license to any other intellectual 8 * property including but not limited to intellectual property relating 9 * to a hardware implementation of the functionality of the software 10 * licensed hereunder. You may use the software subject to the license 11 * terms below provided that you ensure that this notice is replicated 12 * unmodified and in its entirety in all distributions of the software, 13 * modified or unmodified, in source code or in binary form. 14 * 15 * Copyright (c) 2003-2005 The Regents of The University of Michigan 16 * All rights reserved. 17 * 18 * Redistribution and use in source and binary forms, with or without 19 * modification, are permitted provided that the following conditions are 20 * met: redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer; 22 * redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution; 25 * neither the name of the copyright holders nor the names of its 26 * contributors may be used to endorse or promote products derived from 27 * this software without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 40 * 41 * Authors: Erik Hallnor 42 * Nikos Nikoleris 43 * Daniel Carvalho 44 */ 45 46/** 47 * @file 48 * Definitions a fully associative LRU tagstore. 49 */ 50 51#include "mem/cache/tags/fa_lru.hh" 52 53#include <cassert> 54#include <sstream> 55 56#include "base/intmath.hh" 57#include "base/logging.hh" 58#include "mem/cache/base.hh" 59 60FALRU::FALRU(const Params *p) 61 : BaseTags(p), 62 63 cacheTracking(p->min_tracked_cache_size, size, blkSize) 64{ 65 if (!isPowerOf2(blkSize)) 66 fatal("cache block size (in bytes) `%d' must be a power of two", 67 blkSize); 68 if (!isPowerOf2(size)) 69 fatal("Cache Size must be power of 2 for now"); 70 71 blks = new FALRUBlk[numBlocks]; 72 73 head = &(blks[0]); 74 head->prev = nullptr; 75 head->next = &(blks[1]); 76 head->set = 0; 77 head->way = 0; 78 head->data = &dataBlks[0]; 79 80 for (unsigned i = 1; i < numBlocks - 1; i++) { 81 blks[i].prev = &(blks[i-1]); 82 blks[i].next = &(blks[i+1]); 83 blks[i].set = 0; 84 blks[i].way = i; 85 86 // Associate a data chunk to the block 87 blks[i].data = &dataBlks[blkSize*i]; 88 } 89 90 tail = &(blks[numBlocks - 1]); 91 tail->prev = &(blks[numBlocks - 2]); 92 tail->next = nullptr; 93 tail->set = 0; 94 tail->way = numBlocks - 1; 95 tail->data = &dataBlks[(numBlocks - 1) * blkSize]; 96 97 cacheTracking.init(head, tail); 98} 99 100FALRU::~FALRU() 101{ 102 delete[] blks; 103} 104 105void 106FALRU::regStats() 107{ 108 BaseTags::regStats(); 109 cacheTracking.regStats(name()); 110} 111 112void 113FALRU::invalidate(CacheBlk *blk) 114{ 115 // Erase block entry reference in the hash table 116 auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure())); 117 118 // Sanity check; only one block reference should be erased 119 assert(num_erased == 1); 120 121 // Invalidate block entry. Must be done after the hash is erased 122 BaseTags::invalidate(blk); 123 124 // Decrease the number of tags in use 125 tagsInUse--; 126 127 // Move the block to the tail to make it the next victim 128 moveToTail((FALRUBlk*)blk); 129} 130 131CacheBlk* 132FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat) 133{ 134 return accessBlock(addr, is_secure, lat, 0); 135} 136 137CacheBlk* 138FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, 139 CachesMask *in_caches_mask) 140{ 141 CachesMask mask = 0; 142 FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure)); 143 144 if (blk && blk->isValid()) { 145 // If a cache hit 146 lat = accessLatency; 147 // Check if the block to be accessed is available. If not, 148 // apply the accessLatency on top of block->whenReady. 149 if (blk->whenReady > curTick() && 150 cache->ticksToCycles(blk->whenReady - curTick()) > 151 accessLatency) { 152 lat = cache->ticksToCycles(blk->whenReady - curTick()) + 153 accessLatency; 154 } 155 mask = blk->inCachesMask; 156 157 moveToHead(blk); 158 } else { 159 // If a cache miss 160 lat = lookupLatency; 161 } 162 if (in_caches_mask) { 163 *in_caches_mask = mask; 164 } 165 166 cacheTracking.recordAccess(blk); 167 168 return blk; 169} 170 171CacheBlk* 172FALRU::findBlock(Addr addr, bool is_secure) const 173{ 174 FALRUBlk* blk = nullptr; 175 176 Addr tag = extractTag(addr); 177 auto iter = tagHash.find(std::make_pair(tag, is_secure)); 178 if (iter != tagHash.end()) { 179 blk = (*iter).second; 180 } 181 182 if (blk && blk->isValid()) { 183 assert(blk->tag == tag); 184 assert(blk->isSecure() == is_secure); 185 } 186 187 return blk; 188} 189 190ReplaceableEntry* 191FALRU::findBlockBySetAndWay(int set, int way) const 192{ 193 assert(set == 0); 194 return &blks[way]; 195} 196 197CacheBlk* 198FALRU::findVictim(Addr addr, const bool is_secure, 199 std::vector<CacheBlk*>& evict_blks) const 200{ 201 // The victim is always stored on the tail for the FALRU 202 FALRUBlk* victim = tail; 203 204 // There is only one eviction for this replacement 205 evict_blks.push_back(victim); 206 207 return victim; 208} 209 210void 211FALRU::insertBlock(const Addr addr, const bool is_secure, 212 const int src_master_ID, const uint32_t task_ID, 213 CacheBlk *blk) 214{ 215 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk); 216 217 // Make sure block is not present in the cache 218 assert(falruBlk->inCachesMask == 0); 219 220 // Do common block insertion functionality 221 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 222 223 // Increment tag counter 224 tagsInUse++; 225 226 // New block is the MRU 227 moveToHead(falruBlk); 228 229 // Insert new block in the hash table 230 tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk; 231} 232 233void 234FALRU::moveToHead(FALRUBlk *blk) 235{ 236 // If block is not already head, do the moving 237 if (blk != head) { 238 cacheTracking.moveBlockToHead(blk); 239 // If block is tail, set previous block as new tail 240 if (blk == tail){ 241 assert(blk->next == nullptr); 242 tail = blk->prev; 243 tail->next = nullptr; 244 // Inform block's surrounding blocks that it has been moved 245 } else { 246 blk->prev->next = blk->next; 247 blk->next->prev = blk->prev; 248 } 249 250 // Swap pointers 251 blk->next = head; 252 blk->prev = nullptr; 253 head->prev = blk; 254 head = blk; 255 256 cacheTracking.check(head, tail); 257 } 258} 259 260void 261FALRU::moveToTail(FALRUBlk *blk) 262{ 263 // If block is not already tail, do the moving 264 if (blk != tail) { 265 cacheTracking.moveBlockToTail(blk); 266 // If block is head, set next block as new head 267 if (blk == head){ 268 assert(blk->prev == nullptr); 269 head = blk->next; 270 head->prev = nullptr; 271 // Inform block's surrounding blocks that it has been moved 272 } else { 273 blk->prev->next = blk->next; 274 blk->next->prev = blk->prev; 275 } 276 277 // Swap pointers 278 blk->prev = tail; 279 blk->next = nullptr; 280 tail->next = blk; 281 tail = blk; 282 283 cacheTracking.check(head, tail); 284 } 285} 286 287FALRU * 288FALRUParams::create() 289{ 290 return new FALRU(this); 291} 292 293void 294FALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const 295{ 296#ifdef FALRU_DEBUG 297 const FALRUBlk* blk = head; 298 unsigned curr_size = 0; 299 unsigned tracked_cache_size = minTrackedSize; 300 CachesMask in_caches_mask = inAllCachesMask; 301 int j = 0; 302 303 while (blk) { 304 panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask " 305 "%x found %x", blk->inCachesMask, in_caches_mask); 306 307 curr_size += blkSize; 308 if (curr_size == tracked_cache_size && blk != tail) { 309 panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th " 310 "cache", j); 311 tracked_cache_size <<= 1; 312 // from this point, blocks fit only in the larger caches 313 in_caches_mask &= ~(1U << j); 314 ++j; 315 } 316 blk = blk->next; 317 } 318#endif // FALRU_DEBUG 319} 320 321void 322FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail) 323{ 324 // early exit if we are not tracking any extra caches 325 FALRUBlk* blk = numTrackedCaches ? head : nullptr; 326 unsigned curr_size = 0; 327 unsigned tracked_cache_size = minTrackedSize; 328 CachesMask in_caches_mask = inAllCachesMask; 329 int j = 0; 330 331 while (blk) { 332 blk->inCachesMask = in_caches_mask; 333 334 curr_size += blkSize; 335 if (curr_size == tracked_cache_size && blk != tail) { 336 boundaries[j] = blk; 337 338 tracked_cache_size <<= 1; 339 // from this point, blocks fit only in the larger caches 340 in_caches_mask &= ~(1U << j); 341 ++j; 342 } 343 blk = blk->next; 344 } 345} 346 347 348void 349FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk) 350{ 351 // Get the mask of all caches, in which the block didn't fit 352 // before moving it to the head 353 CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask; 354 355 for (int i = 0; i < numTrackedCaches; i++) { 356 CachesMask current_cache_mask = 1U << i; 357 if (current_cache_mask & update_caches_mask) { 358 // if the ith cache didn't fit the block (before it is moved to 359 // the head), move the ith boundary 1 block closer to the 360 // MRU 361 boundaries[i]->inCachesMask &= ~current_cache_mask; 362 boundaries[i] = boundaries[i]->prev; 363 } else if (boundaries[i] == blk) { 364 // Make sure the boundary doesn't point to the block 365 // we are about to move 366 boundaries[i] = blk->prev; 367 } 368 } 369 370 // Make block reside in all caches 371 blk->inCachesMask = inAllCachesMask; 372} 373 374void 375FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk) 376{ 377 CachesMask update_caches_mask = blk->inCachesMask; 378 379 for (int i = 0; i < numTrackedCaches; i++) { 380 CachesMask current_cache_mask = 1U << i; 381 if (current_cache_mask & update_caches_mask) { 382 // if the ith cache fitted the block (before it is moved to 383 // the tail), move the ith boundary 1 block closer to the 384 // LRU 385 boundaries[i] = boundaries[i]->next; 386 if (boundaries[i] == blk) { 387 // Make sure the boundary doesn't point to the block 388 // we are about to move 389 boundaries[i] = blk->next; 390 } 391 boundaries[i]->inCachesMask |= current_cache_mask; 392 } 393 } 394 395 // The block now fits only in the actual cache 396 blk->inCachesMask = 0; 397} 398 399void 400FALRU::CacheTracking::recordAccess(FALRUBlk *blk) 401{ 402 for (int i = 0; i < numTrackedCaches; i++) { 403 if (blk && ((1U << i) & blk->inCachesMask)) { 404 hits[i]++; 405 } else { 406 misses[i]++; 407 } 408 } 409 410 // Record stats for the actual cache too 411 if (blk && blk->isValid()) { 412 hits[numTrackedCaches]++; 413 } else { 414 misses[numTrackedCaches]++; 415 } 416 417 accesses++; 418} 419 420void 421printSize(std::ostream &stream, size_t size) 422{ 423 static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" }; 424 int div = 0; 425 while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) { 426 div++; 427 size >>= 10; 428 } 429 stream << size << SIZES[div]; 430} 431 432void 433FALRU::CacheTracking::regStats(std::string name) 434{ 435 hits 436 .init(numTrackedCaches + 1) 437 .name(name + ".falru_hits") 438 .desc("The number of hits in each cache size.") 439 ; 440 misses 441 .init(numTrackedCaches + 1) 442 .name(name + ".falru_misses") 443 .desc("The number of misses in each cache size.") 444 ; 445 accesses 446 .name(name + ".falru_accesses") 447 .desc("The number of accesses to the FA LRU cache.") 448 ; 449 450 for (unsigned i = 0; i < numTrackedCaches + 1; ++i) { 451 std::stringstream size_str; 452 printSize(size_str, minTrackedSize << i); 453 hits.subname(i, size_str.str()); 454 hits.subdesc(i, "Hits in a " + size_str.str() + " cache"); 455 misses.subname(i, size_str.str()); 456 misses.subdesc(i, "Misses in a " + size_str.str() + " cache"); 457 } 458} 459