2c2
< * Copyright (c) 2013,2016-2017 ARM Limited
---
> * Copyright (c) 2013,2016-2018 ARM Limited
40a41
> * Nikos Nikoleris
57c58,60
< : BaseTags(p), cacheBoundaries(nullptr)
---
> : BaseTags(p),
>
> cacheTracking(p->min_tracked_cache_size, size, blkSize)
65,73d67
< // Track all cache sizes from 128K up by powers of 2
< numCaches = floorLog2(size) - 17;
< if (numCaches > 0){
< cacheBoundaries = new FALRUBlk *[numCaches];
< cacheMask = (ULL(1) << numCaches) - 1;
< } else {
< cacheMask = 0;
< }
<
75,76d68
< head = &(blks[0]);
< tail = &(blks[numBlocks-1]);
77a70
> head = &(blks[0]);
80c73,74
< head->inCache = cacheMask;
---
> head->set = 0;
> head->way = 0;
83,90d76
< tail->prev = &(blks[numBlocks-2]);
< tail->next = nullptr;
< tail->inCache = 0;
< tail->data = &dataBlks[(numBlocks-1)*blkSize];
<
< unsigned index = (1 << 17) / blkSize;
< unsigned j = 0;
< int flags = cacheMask;
92,98d77
< blks[i].inCache = flags;
< if (i == index - 1){
< cacheBoundaries[j] = &(blks[i]);
< flags &= ~ (1<<j);
< ++j;
< index = index << 1;
< }
107,109c86,94
< assert(j == numCaches);
< assert(index == numBlocks);
< //assert(check());
---
>
> tail = &(blks[numBlocks - 1]);
> tail->prev = &(blks[numBlocks - 2]);
> tail->next = nullptr;
> tail->set = 0;
> tail->way = numBlocks - 1;
> tail->data = &dataBlks[(numBlocks - 1) * blkSize];
>
> cacheTracking.init(head, tail);
114,116d98
< if (numCaches)
< delete[] cacheBoundaries;
<
124,151c106
< hits
< .init(numCaches+1)
< .name(name() + ".falru_hits")
< .desc("The number of hits in each cache size.")
< ;
< misses
< .init(numCaches+1)
< .name(name() + ".falru_misses")
< .desc("The number of misses in each cache size.")
< ;
< accesses
< .name(name() + ".falru_accesses")
< .desc("The number of accesses to the FA LRU cache.")
< ;
<
< for (unsigned i = 0; i <= numCaches; ++i) {
< std::stringstream size_str;
< if (i < 3){
< size_str << (1<<(i+7)) <<"K";
< } else {
< size_str << (1<<(i-3)) <<"M";
< }
<
< hits.subname(i, size_str.str());
< hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
< misses.subname(i, size_str.str());
< misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
< }
---
> cacheTracking.regStats(name());
183c138,139
< FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
---
> FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat,
> CachesMask *in_caches_mask)
185,186c141
< accesses++;
< int tmp_in_cache = 0;
---
> CachesMask mask = 0;
202,213c157,158
< tmp_in_cache = blk->inCache;
< for (unsigned i = 0; i < numCaches; i++) {
< if (1<<i & blk->inCache) {
< hits[i]++;
< } else {
< misses[i]++;
< }
< }
< hits[numCaches]++;
< if (blk != head){
< moveToHead(blk);
< }
---
> mask = blk->inCachesMask;
> moveToHead(blk);
218,220d162
< for (unsigned i = 0; i <= numCaches; ++i) {
< misses[i]++;
< }
222,223c164,165
< if (inCache) {
< *inCache = tmp_in_cache;
---
> if (in_caches_mask) {
> *in_caches_mask = mask;
226c168,169
< //assert(check());
---
> cacheTracking.recordAccess(blk);
>
264c207
< assert(falruBlk->inCache == 0);
---
> assert(falruBlk->inCachesMask == 0);
274,275d216
<
< //assert(check());
283,303c224
< // Get all caches that this block does not reside in
< int updateMask = blk->inCache ^ cacheMask;
<
< // Update boundaries for all cache sizes
< for (unsigned i = 0; i < numCaches; i++){
< // If block has been moved to a place before this boundary,
< // all blocks in it will be pushed towards the LRU position,
< // making one leave the boundary
< if ((1U<<i) & updateMask) {
< cacheBoundaries[i]->inCache &= ~(1U<<i);
< cacheBoundaries[i] = cacheBoundaries[i]->prev;
< // If the block resides exactly at this boundary, the previous
< // block is pushed to its position
< } else if (cacheBoundaries[i] == blk) {
< cacheBoundaries[i] = blk->prev;
< }
< }
<
< // Make block reside in all caches
< blk->inCache = cacheMask;
<
---
> cacheTracking.moveBlockToHead(blk);
319a241,242
>
> cacheTracking.check(head, tail);
328,347c251
< // Update boundaries for all cache sizes
< for (unsigned i = 0; i < numCaches; i++){
< // If block has been moved to a place after this boundary,
< // all blocks in it will be pushed towards the MRU position,
< // making one enter the boundary
< if ((1U<<i) & blk->inCache) {
< // If the first block after the boundary is the block,
< // get its successor
< if (cacheBoundaries[i]->next == blk){
< cacheBoundaries[i] = cacheBoundaries[i]->next->next;
< } else {
< cacheBoundaries[i] = cacheBoundaries[i]->next;
< }
< cacheBoundaries[i]->inCache |= (1U<<i);
< }
< }
<
< // Make block reside in the last cache only
< blk->inCache = 0;
<
---
> cacheTracking.moveBlockToTail(blk);
363a268,269
>
> cacheTracking.check(head, tail);
367,368c273,274
< bool
< FALRU::check()
---
> FALRU *
> FALRUParams::create()
369a276,282
> return new FALRU(this);
> }
>
> void
> FALRU::CacheTracking::check(FALRUBlk *head, FALRUBlk *tail)
> {
> #ifdef FALRU_DEBUG
371,372c284,286
< int tot_size = 0;
< int boundary = 1<<17;
---
> unsigned curr_size = 0;
> unsigned tracked_cache_size = minTrackedSize;
> CachesMask in_caches_mask = inAllCachesMask;
374c288
< int flags = cacheMask;
---
>
376,378c290,300
< tot_size += blkSize;
< if (blk->inCache != flags) {
< return false;
---
> panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask "
> "%x found %x", blk->inCachesMask, in_caches_mask);
>
> curr_size += blkSize;
> if (curr_size == tracked_cache_size && blk != tail) {
> panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th "
> "cache", j);
> tracked_cache_size <<= 1;
> // from this point, blocks fit only in the larger caches
> in_caches_mask &= ~(1U << j);
> ++j;
380,385c302,326
< if (tot_size == boundary && blk != tail) {
< if (cacheBoundaries[j] != blk) {
< return false;
< }
< flags &=~(1 << j);
< boundary = boundary<<1;
---
> blk = blk->next;
> }
> #endif // FALRU_DEBUG
> }
>
> void
> FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail)
> {
> // early exit if we are not tracking any extra caches
> FALRUBlk* blk = numTrackedCaches ? head : nullptr;
> unsigned curr_size = 0;
> unsigned tracked_cache_size = minTrackedSize;
> CachesMask in_caches_mask = inAllCachesMask;
> int j = 0;
>
> while (blk) {
> blk->inCachesMask = in_caches_mask;
>
> curr_size += blkSize;
> if (curr_size == tracked_cache_size && blk != tail) {
> boundaries[j] = blk;
>
> tracked_cache_size <<= 1;
> // from this point, blocks fit only in the larger caches
> in_caches_mask &= ~(1U << j);
390d330
< return true;
393,394c333,335
< FALRU *
< FALRUParams::create()
---
>
> void
> FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk)
396c337,357
< return new FALRU(this);
---
> // Get the mask of all caches, in which the block didn't fit
> // before moving it to the head
> CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask;
>
> for (int i = 0; i < numTrackedCaches; i++) {
> CachesMask current_cache_mask = 1U << i;
> if (current_cache_mask & update_caches_mask) {
> // if the ith cache didn't fit the block (before it is moved to
> // the head), move the ith boundary 1 block closer to the
> // MRU
> boundaries[i]->inCachesMask &= ~current_cache_mask;
> boundaries[i] = boundaries[i]->prev;
> } else if (boundaries[i] == blk) {
> // Make sure the boundary doesn't point to the block
> // we are about to move
> boundaries[i] = blk->prev;
> }
> }
>
> // Make block reside in all caches
> blk->inCachesMask = inAllCachesMask;
398a360,444
> void
> FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk)
> {
> CachesMask update_caches_mask = blk->inCachesMask;
>
> for (int i = 0; i < numTrackedCaches; i++) {
> CachesMask current_cache_mask = 1U << i;
> if (current_cache_mask & update_caches_mask) {
> // if the ith cache fitted the block (before it is moved to
> // the tail), move the ith boundary 1 block closer to the
> // LRU
> boundaries[i] = boundaries[i]->next;
> if (boundaries[i] == blk) {
> // Make sure the boundary doesn't point to the block
> // we are about to move
> boundaries[i] = blk->next;
> }
> boundaries[i]->inCachesMask |= current_cache_mask;
> }
> }
>
> // The block now fits only in the actual cache
> blk->inCachesMask = 0;
> }
>
> void
> FALRU::CacheTracking::recordAccess(FALRUBlk *blk)
> {
> for (int i = 0; i < numTrackedCaches; i++) {
> if (blk && ((1U << i) & blk->inCachesMask)) {
> hits[i]++;
> } else {
> misses[i]++;
> }
> }
>
> // Record stats for the actual cache too
> if (blk) {
> hits[numTrackedCaches]++;
> } else {
> misses[numTrackedCaches]++;
> }
>
> accesses++;
> }
>
> void
> printSize(std::ostream &stream, size_t size)
> {
> static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" };
> int div = 0;
> while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) {
> div++;
> size >>= 10;
> }
> stream << size << SIZES[div];
> }
>
> void
> FALRU::CacheTracking::regStats(std::string name)
> {
> hits
> .init(numTrackedCaches + 1)
> .name(name + ".falru_hits")
> .desc("The number of hits in each cache size.")
> ;
> misses
> .init(numTrackedCaches + 1)
> .name(name + ".falru_misses")
> .desc("The number of misses in each cache size.")
> ;
> accesses
> .name(name + ".falru_accesses")
> .desc("The number of accesses to the FA LRU cache.")
> ;
>
> for (unsigned i = 0; i < numTrackedCaches + 1; ++i) {
> std::stringstream size_str;
> printSize(size_str, minTrackedSize << i);
> hits.subname(i, size_str.str());
> hits.subdesc(i, "Hits in a " + size_str.str() + " cache");
> misses.subname(i, size_str.str());
> misses.subdesc(i, "Misses in a " + size_str.str() + " cache");
> }
> }
< * Copyright (c) 2013,2016-2017 ARM Limited
---
> * Copyright (c) 2013,2016-2018 ARM Limited
40a41
> * Nikos Nikoleris
57c58,60
< : BaseTags(p), cacheBoundaries(nullptr)
---
> : BaseTags(p),
>
> cacheTracking(p->min_tracked_cache_size, size, blkSize)
65,73d67
< // Track all cache sizes from 128K up by powers of 2
< numCaches = floorLog2(size) - 17;
< if (numCaches > 0){
< cacheBoundaries = new FALRUBlk *[numCaches];
< cacheMask = (ULL(1) << numCaches) - 1;
< } else {
< cacheMask = 0;
< }
<
75,76d68
< head = &(blks[0]);
< tail = &(blks[numBlocks-1]);
77a70
> head = &(blks[0]);
80c73,74
< head->inCache = cacheMask;
---
> head->set = 0;
> head->way = 0;
83,90d76
< tail->prev = &(blks[numBlocks-2]);
< tail->next = nullptr;
< tail->inCache = 0;
< tail->data = &dataBlks[(numBlocks-1)*blkSize];
<
< unsigned index = (1 << 17) / blkSize;
< unsigned j = 0;
< int flags = cacheMask;
92,98d77
< blks[i].inCache = flags;
< if (i == index - 1){
< cacheBoundaries[j] = &(blks[i]);
< flags &= ~ (1<<j);
< ++j;
< index = index << 1;
< }
107,109c86,94
< assert(j == numCaches);
< assert(index == numBlocks);
< //assert(check());
---
>
> tail = &(blks[numBlocks - 1]);
> tail->prev = &(blks[numBlocks - 2]);
> tail->next = nullptr;
> tail->set = 0;
> tail->way = numBlocks - 1;
> tail->data = &dataBlks[(numBlocks - 1) * blkSize];
>
> cacheTracking.init(head, tail);
114,116d98
< if (numCaches)
< delete[] cacheBoundaries;
<
124,151c106
< hits
< .init(numCaches+1)
< .name(name() + ".falru_hits")
< .desc("The number of hits in each cache size.")
< ;
< misses
< .init(numCaches+1)
< .name(name() + ".falru_misses")
< .desc("The number of misses in each cache size.")
< ;
< accesses
< .name(name() + ".falru_accesses")
< .desc("The number of accesses to the FA LRU cache.")
< ;
<
< for (unsigned i = 0; i <= numCaches; ++i) {
< std::stringstream size_str;
< if (i < 3){
< size_str << (1<<(i+7)) <<"K";
< } else {
< size_str << (1<<(i-3)) <<"M";
< }
<
< hits.subname(i, size_str.str());
< hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
< misses.subname(i, size_str.str());
< misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
< }
---
> cacheTracking.regStats(name());
183c138,139
< FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
---
> FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat,
> CachesMask *in_caches_mask)
185,186c141
< accesses++;
< int tmp_in_cache = 0;
---
> CachesMask mask = 0;
202,213c157,158
< tmp_in_cache = blk->inCache;
< for (unsigned i = 0; i < numCaches; i++) {
< if (1<<i & blk->inCache) {
< hits[i]++;
< } else {
< misses[i]++;
< }
< }
< hits[numCaches]++;
< if (blk != head){
< moveToHead(blk);
< }
---
> mask = blk->inCachesMask;
> moveToHead(blk);
218,220d162
< for (unsigned i = 0; i <= numCaches; ++i) {
< misses[i]++;
< }
222,223c164,165
< if (inCache) {
< *inCache = tmp_in_cache;
---
> if (in_caches_mask) {
> *in_caches_mask = mask;
226c168,169
< //assert(check());
---
> cacheTracking.recordAccess(blk);
>
264c207
< assert(falruBlk->inCache == 0);
---
> assert(falruBlk->inCachesMask == 0);
274,275d216
<
< //assert(check());
283,303c224
< // Get all caches that this block does not reside in
< int updateMask = blk->inCache ^ cacheMask;
<
< // Update boundaries for all cache sizes
< for (unsigned i = 0; i < numCaches; i++){
< // If block has been moved to a place before this boundary,
< // all blocks in it will be pushed towards the LRU position,
< // making one leave the boundary
< if ((1U<<i) & updateMask) {
< cacheBoundaries[i]->inCache &= ~(1U<<i);
< cacheBoundaries[i] = cacheBoundaries[i]->prev;
< // If the block resides exactly at this boundary, the previous
< // block is pushed to its position
< } else if (cacheBoundaries[i] == blk) {
< cacheBoundaries[i] = blk->prev;
< }
< }
<
< // Make block reside in all caches
< blk->inCache = cacheMask;
<
---
> cacheTracking.moveBlockToHead(blk);
319a241,242
>
> cacheTracking.check(head, tail);
328,347c251
< // Update boundaries for all cache sizes
< for (unsigned i = 0; i < numCaches; i++){
< // If block has been moved to a place after this boundary,
< // all blocks in it will be pushed towards the MRU position,
< // making one enter the boundary
< if ((1U<<i) & blk->inCache) {
< // If the first block after the boundary is the block,
< // get its successor
< if (cacheBoundaries[i]->next == blk){
< cacheBoundaries[i] = cacheBoundaries[i]->next->next;
< } else {
< cacheBoundaries[i] = cacheBoundaries[i]->next;
< }
< cacheBoundaries[i]->inCache |= (1U<<i);
< }
< }
<
< // Make block reside in the last cache only
< blk->inCache = 0;
<
---
> cacheTracking.moveBlockToTail(blk);
363a268,269
>
> cacheTracking.check(head, tail);
367,368c273,274
< bool
< FALRU::check()
---
> FALRU *
> FALRUParams::create()
369a276,282
> return new FALRU(this);
> }
>
> void
> FALRU::CacheTracking::check(FALRUBlk *head, FALRUBlk *tail)
> {
> #ifdef FALRU_DEBUG
371,372c284,286
< int tot_size = 0;
< int boundary = 1<<17;
---
> unsigned curr_size = 0;
> unsigned tracked_cache_size = minTrackedSize;
> CachesMask in_caches_mask = inAllCachesMask;
374c288
< int flags = cacheMask;
---
>
376,378c290,300
< tot_size += blkSize;
< if (blk->inCache != flags) {
< return false;
---
> panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask "
> "%x found %x", blk->inCachesMask, in_caches_mask);
>
> curr_size += blkSize;
> if (curr_size == tracked_cache_size && blk != tail) {
> panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th "
> "cache", j);
> tracked_cache_size <<= 1;
> // from this point, blocks fit only in the larger caches
> in_caches_mask &= ~(1U << j);
> ++j;
380,385c302,326
< if (tot_size == boundary && blk != tail) {
< if (cacheBoundaries[j] != blk) {
< return false;
< }
< flags &=~(1 << j);
< boundary = boundary<<1;
---
> blk = blk->next;
> }
> #endif // FALRU_DEBUG
> }
>
> void
> FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail)
> {
> // early exit if we are not tracking any extra caches
> FALRUBlk* blk = numTrackedCaches ? head : nullptr;
> unsigned curr_size = 0;
> unsigned tracked_cache_size = minTrackedSize;
> CachesMask in_caches_mask = inAllCachesMask;
> int j = 0;
>
> while (blk) {
> blk->inCachesMask = in_caches_mask;
>
> curr_size += blkSize;
> if (curr_size == tracked_cache_size && blk != tail) {
> boundaries[j] = blk;
>
> tracked_cache_size <<= 1;
> // from this point, blocks fit only in the larger caches
> in_caches_mask &= ~(1U << j);
390d330
< return true;
393,394c333,335
< FALRU *
< FALRUParams::create()
---
>
> void
> FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk)
396c337,357
< return new FALRU(this);
---
> // Get the mask of all caches, in which the block didn't fit
> // before moving it to the head
> CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask;
>
> for (int i = 0; i < numTrackedCaches; i++) {
> CachesMask current_cache_mask = 1U << i;
> if (current_cache_mask & update_caches_mask) {
> // if the ith cache didn't fit the block (before it is moved to
> // the head), move the ith boundary 1 block closer to the
> // MRU
> boundaries[i]->inCachesMask &= ~current_cache_mask;
> boundaries[i] = boundaries[i]->prev;
> } else if (boundaries[i] == blk) {
> // Make sure the boundary doesn't point to the block
> // we are about to move
> boundaries[i] = blk->prev;
> }
> }
>
> // Make block reside in all caches
> blk->inCachesMask = inAllCachesMask;
398a360,444
> void
> FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk)
> {
> CachesMask update_caches_mask = blk->inCachesMask;
>
> for (int i = 0; i < numTrackedCaches; i++) {
> CachesMask current_cache_mask = 1U << i;
> if (current_cache_mask & update_caches_mask) {
> // if the ith cache fitted the block (before it is moved to
> // the tail), move the ith boundary 1 block closer to the
> // LRU
> boundaries[i] = boundaries[i]->next;
> if (boundaries[i] == blk) {
> // Make sure the boundary doesn't point to the block
> // we are about to move
> boundaries[i] = blk->next;
> }
> boundaries[i]->inCachesMask |= current_cache_mask;
> }
> }
>
> // The block now fits only in the actual cache
> blk->inCachesMask = 0;
> }
>
> void
> FALRU::CacheTracking::recordAccess(FALRUBlk *blk)
> {
> for (int i = 0; i < numTrackedCaches; i++) {
> if (blk && ((1U << i) & blk->inCachesMask)) {
> hits[i]++;
> } else {
> misses[i]++;
> }
> }
>
> // Record stats for the actual cache too
> if (blk) {
> hits[numTrackedCaches]++;
> } else {
> misses[numTrackedCaches]++;
> }
>
> accesses++;
> }
>
> void
> printSize(std::ostream &stream, size_t size)
> {
> static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" };
> int div = 0;
> while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) {
> div++;
> size >>= 10;
> }
> stream << size << SIZES[div];
> }
>
> void
> FALRU::CacheTracking::regStats(std::string name)
> {
> hits
> .init(numTrackedCaches + 1)
> .name(name + ".falru_hits")
> .desc("The number of hits in each cache size.")
> ;
> misses
> .init(numTrackedCaches + 1)
> .name(name + ".falru_misses")
> .desc("The number of misses in each cache size.")
> ;
> accesses
> .name(name + ".falru_accesses")
> .desc("The number of accesses to the FA LRU cache.")
> ;
>
> for (unsigned i = 0; i < numTrackedCaches + 1; ++i) {
> std::stringstream size_str;
> printSize(size_str, minTrackedSize << i);
> hits.subname(i, size_str.str());
> hits.subdesc(i, "Hits in a " + size_str.str() + " cache");
> misses.subname(i, size_str.str());
> misses.subdesc(i, "Misses in a " + size_str.str() + " cache");
> }
> }