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
|
66FALRU::FALRU(const Params *p) 67 : BaseTags(p), 68 69 cacheTracking(p->min_tracked_cache_size, size, blkSize) 70{ 71 if (!isPowerOf2(blkSize)) 72 fatal("cache block size (in bytes) `%d' must be a power of two", 73 blkSize); 74 if (!isPowerOf2(size)) 75 fatal("Cache Size must be power of 2 for now"); 76 77 blks = new FALRUBlk[numBlocks]; 78} 79 80FALRU::~FALRU() 81{ 82 delete[] blks; 83} 84 85void 86FALRU::init(BaseCache* cache) 87{ 88 // Set parent cache 89 setCache(cache); 90 91 head = &(blks[0]); 92 head->prev = nullptr; 93 head->next = &(blks[1]); 94 head->setPosition(0, 0); 95 head->data = &dataBlks[0]; 96 97 for (unsigned i = 1; i < numBlocks - 1; i++) { 98 blks[i].prev = &(blks[i-1]); 99 blks[i].next = &(blks[i+1]); 100 blks[i].setPosition(0, i); 101 102 // Associate a data chunk to the block 103 blks[i].data = &dataBlks[blkSize*i]; 104 } 105 106 tail = &(blks[numBlocks - 1]); 107 tail->prev = &(blks[numBlocks - 2]); 108 tail->next = nullptr; 109 tail->setPosition(0, numBlocks - 1); 110 tail->data = &dataBlks[(numBlocks - 1) * blkSize]; 111 112 cacheTracking.init(head, tail); 113} 114 115void 116FALRU::regStats() 117{ 118 BaseTags::regStats(); 119 cacheTracking.regStats(name()); 120} 121 122void 123FALRU::invalidate(CacheBlk *blk) 124{ 125 // Erase block entry reference in the hash table 126 auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure())); 127 128 // Sanity check; only one block reference should be erased 129 assert(num_erased == 1); 130 131 // Invalidate block entry. Must be done after the hash is erased 132 BaseTags::invalidate(blk); 133 134 // Decrease the number of tags in use 135 tagsInUse--; 136 137 // Move the block to the tail to make it the next victim 138 moveToTail((FALRUBlk*)blk); 139} 140 141CacheBlk* 142FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat) 143{ 144 return accessBlock(addr, is_secure, lat, 0); 145} 146 147CacheBlk* 148FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, 149 CachesMask *in_caches_mask) 150{ 151 CachesMask mask = 0; 152 FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure)); 153 154 if (blk && blk->isValid()) { 155 // If a cache hit 156 lat = accessLatency; 157 // Check if the block to be accessed is available. If not, 158 // apply the accessLatency on top of block->whenReady. 159 if (blk->whenReady > curTick() && 160 cache->ticksToCycles(blk->whenReady - curTick()) > 161 accessLatency) { 162 lat = cache->ticksToCycles(blk->whenReady - curTick()) + 163 accessLatency; 164 } 165 mask = blk->inCachesMask; 166 167 moveToHead(blk); 168 } else { 169 // If a cache miss 170 lat = lookupLatency; 171 } 172 if (in_caches_mask) { 173 *in_caches_mask = mask; 174 } 175 176 cacheTracking.recordAccess(blk); 177 178 return blk; 179} 180 181CacheBlk* 182FALRU::findBlock(Addr addr, bool is_secure) const 183{ 184 FALRUBlk* blk = nullptr; 185 186 Addr tag = extractTag(addr); 187 auto iter = tagHash.find(std::make_pair(tag, is_secure)); 188 if (iter != tagHash.end()) { 189 blk = (*iter).second; 190 } 191 192 if (blk && blk->isValid()) { 193 assert(blk->tag == tag); 194 assert(blk->isSecure() == is_secure); 195 } 196 197 return blk; 198} 199 200ReplaceableEntry* 201FALRU::findBlockBySetAndWay(int set, int way) const 202{ 203 assert(set == 0); 204 return &blks[way]; 205} 206 207CacheBlk* 208FALRU::findVictim(Addr addr, const bool is_secure, 209 std::vector<CacheBlk*>& evict_blks) const 210{ 211 // The victim is always stored on the tail for the FALRU 212 FALRUBlk* victim = tail; 213 214 // There is only one eviction for this replacement 215 evict_blks.push_back(victim); 216 217 return victim; 218} 219 220void 221FALRU::insertBlock(const Addr addr, const bool is_secure, 222 const int src_master_ID, const uint32_t task_ID, 223 CacheBlk *blk) 224{ 225 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk); 226 227 // Make sure block is not present in the cache 228 assert(falruBlk->inCachesMask == 0); 229 230 // Do common block insertion functionality 231 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk); 232 233 // Increment tag counter 234 tagsInUse++; 235 236 // New block is the MRU 237 moveToHead(falruBlk); 238 239 // Insert new block in the hash table 240 tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk; 241} 242 243void 244FALRU::moveToHead(FALRUBlk *blk) 245{ 246 // If block is not already head, do the moving 247 if (blk != head) { 248 cacheTracking.moveBlockToHead(blk); 249 // If block is tail, set previous block as new tail 250 if (blk == tail){ 251 assert(blk->next == nullptr); 252 tail = blk->prev; 253 tail->next = nullptr; 254 // Inform block's surrounding blocks that it has been moved 255 } else { 256 blk->prev->next = blk->next; 257 blk->next->prev = blk->prev; 258 } 259 260 // Swap pointers 261 blk->next = head; 262 blk->prev = nullptr; 263 head->prev = blk; 264 head = blk; 265 266 cacheTracking.check(head, tail); 267 } 268} 269 270void 271FALRU::moveToTail(FALRUBlk *blk) 272{ 273 // If block is not already tail, do the moving 274 if (blk != tail) { 275 cacheTracking.moveBlockToTail(blk); 276 // If block is head, set next block as new head 277 if (blk == head){ 278 assert(blk->prev == nullptr); 279 head = blk->next; 280 head->prev = nullptr; 281 // Inform block's surrounding blocks that it has been moved 282 } else { 283 blk->prev->next = blk->next; 284 blk->next->prev = blk->prev; 285 } 286 287 // Swap pointers 288 blk->prev = tail; 289 blk->next = nullptr; 290 tail->next = blk; 291 tail = blk; 292 293 cacheTracking.check(head, tail); 294 } 295} 296 297FALRU * 298FALRUParams::create() 299{ 300 return new FALRU(this); 301} 302 303void 304FALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const 305{ 306#ifdef FALRU_DEBUG 307 const FALRUBlk* blk = head; 308 unsigned curr_size = 0; 309 unsigned tracked_cache_size = minTrackedSize; 310 CachesMask in_caches_mask = inAllCachesMask; 311 int j = 0; 312 313 while (blk) { 314 panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask " 315 "%x found %x", blk->inCachesMask, in_caches_mask); 316 317 curr_size += blkSize; 318 if (curr_size == tracked_cache_size && blk != tail) { 319 panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th " 320 "cache", j); 321 tracked_cache_size <<= 1; 322 // from this point, blocks fit only in the larger caches 323 in_caches_mask &= ~(1U << j); 324 ++j; 325 } 326 blk = blk->next; 327 } 328#endif // FALRU_DEBUG 329} 330 331void 332FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail) 333{ 334 // early exit if we are not tracking any extra caches 335 FALRUBlk* blk = numTrackedCaches ? head : nullptr; 336 unsigned curr_size = 0; 337 unsigned tracked_cache_size = minTrackedSize; 338 CachesMask in_caches_mask = inAllCachesMask; 339 int j = 0; 340 341 while (blk) { 342 blk->inCachesMask = in_caches_mask; 343 344 curr_size += blkSize; 345 if (curr_size == tracked_cache_size && blk != tail) { 346 boundaries[j] = blk; 347 348 tracked_cache_size <<= 1; 349 // from this point, blocks fit only in the larger caches 350 in_caches_mask &= ~(1U << j); 351 ++j; 352 } 353 blk = blk->next; 354 } 355} 356 357 358void 359FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk) 360{ 361 // Get the mask of all caches, in which the block didn't fit 362 // before moving it to the head 363 CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask; 364 365 for (int i = 0; i < numTrackedCaches; i++) { 366 CachesMask current_cache_mask = 1U << i; 367 if (current_cache_mask & update_caches_mask) { 368 // if the ith cache didn't fit the block (before it is moved to 369 // the head), move the ith boundary 1 block closer to the 370 // MRU 371 boundaries[i]->inCachesMask &= ~current_cache_mask; 372 boundaries[i] = boundaries[i]->prev; 373 } else if (boundaries[i] == blk) { 374 // Make sure the boundary doesn't point to the block 375 // we are about to move 376 boundaries[i] = blk->prev; 377 } 378 } 379 380 // Make block reside in all caches 381 blk->inCachesMask = inAllCachesMask; 382} 383 384void 385FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk) 386{ 387 CachesMask update_caches_mask = blk->inCachesMask; 388 389 for (int i = 0; i < numTrackedCaches; i++) { 390 CachesMask current_cache_mask = 1U << i; 391 if (current_cache_mask & update_caches_mask) { 392 // if the ith cache fitted the block (before it is moved to 393 // the tail), move the ith boundary 1 block closer to the 394 // LRU 395 boundaries[i] = boundaries[i]->next; 396 if (boundaries[i] == blk) { 397 // Make sure the boundary doesn't point to the block 398 // we are about to move 399 boundaries[i] = blk->next; 400 } 401 boundaries[i]->inCachesMask |= current_cache_mask; 402 } 403 } 404 405 // The block now fits only in the actual cache 406 blk->inCachesMask = 0; 407} 408 409void 410FALRU::CacheTracking::recordAccess(FALRUBlk *blk) 411{ 412 for (int i = 0; i < numTrackedCaches; i++) { 413 if (blk && ((1U << i) & blk->inCachesMask)) { 414 hits[i]++; 415 } else { 416 misses[i]++; 417 } 418 } 419 420 // Record stats for the actual cache too 421 if (blk && blk->isValid()) { 422 hits[numTrackedCaches]++; 423 } else { 424 misses[numTrackedCaches]++; 425 } 426 427 accesses++; 428} 429 430void 431printSize(std::ostream &stream, size_t size) 432{ 433 static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" }; 434 int div = 0; 435 while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) { 436 div++; 437 size >>= 10; 438 } 439 stream << size << SIZES[div]; 440} 441 442void 443FALRU::CacheTracking::regStats(std::string name) 444{ 445 hits 446 .init(numTrackedCaches + 1) 447 .name(name + ".falru_hits") 448 .desc("The number of hits in each cache size.") 449 ; 450 misses 451 .init(numTrackedCaches + 1) 452 .name(name + ".falru_misses") 453 .desc("The number of misses in each cache size.") 454 ; 455 accesses 456 .name(name + ".falru_accesses") 457 .desc("The number of accesses to the FA LRU cache.") 458 ; 459 460 for (unsigned i = 0; i < numTrackedCaches + 1; ++i) { 461 std::stringstream size_str; 462 printSize(size_str, minTrackedSize << i); 463 hits.subname(i, size_str.str()); 464 hits.subdesc(i, "Hits in a " + size_str.str() + " cache"); 465 misses.subname(i, size_str.str()); 466 misses.subdesc(i, "Misses in a " + size_str.str() + " cache"); 467 } 468}
|