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