src/mem/cache/tags/fa_lru.cc

   1 /*
   2  * Copyright (c) 2003-2005 The Regents of The University of Michigan
   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  * Authors: Erik Hallnor
  29  */
  30
  31 /**
  32  * @file
  33  * Definitions a fully associative LRU tagstore.
  34  */
  35
  36 #include <cassert>
  37 #include <sstream>
  38
  39 #include "base/intmath.hh"
  40 #include "base/misc.hh"
  41 #include "mem/cache/tags/fa_lru.hh"
  42
  43 using namespace std;
  44
  45 FALRU::FALRU(unsigned _blkSize, unsigned _size, unsigned hit_latency)
  46     : blkSize(_blkSize), size(_size), hitLatency(hit_latency)
  47 {
  48     if (!isPowerOf2(blkSize))
  49         fatal("cache block size (in bytes) `%d' must be a power of two",
  50               blkSize);
  51     if (!(hitLatency > 0))
  52         fatal("Access latency in cycles must be at least one cycle");
  53     if (!isPowerOf2(size))
  54         fatal("Cache Size must be power of 2 for now");
  55
  56     // Track all cache sizes from 128K up by powers of 2
  57     numCaches = floorLog2(size) - 17;
  58     if (numCaches >0){
  59         cacheBoundaries = new FALRUBlk *[numCaches];
  60         cacheMask = (1 << numCaches) - 1;
  61     } else {
  62         cacheMask = 0;
  63     }
  64
  65     warmedUp = false;
  66     warmupBound = size/blkSize;
  67     numBlocks = size/blkSize;
  68
  69     blks = new FALRUBlk[numBlocks];
  70     head = &(blks[0]);
  71     tail = &(blks[numBlocks-1]);
  72
  73     head->prev = NULL;
  74     head->next = &(blks[1]);
  75     head->inCache = cacheMask;
  76
  77     tail->prev = &(blks[numBlocks-2]);
  78     tail->next = NULL;
  79     tail->inCache = 0;
  80
  81     unsigned index = (1 << 17) / blkSize;
  82     unsigned j = 0;
  83     int flags = cacheMask;
  84     for (unsigned i = 1; i < numBlocks - 1; i++) {
  85         blks[i].inCache = flags;
  86         if (i == index - 1){
  87             cacheBoundaries[j] = &(blks[i]);
  88             flags &= ~ (1<<j);
  89             ++j;
  90             index = index << 1;
  91         }
  92         blks[i].prev = &(blks[i-1]);
  93         blks[i].next = &(blks[i+1]);
  94         blks[i].isTouched = false;
  95     }
  96     assert(j == numCaches);
  97     assert(index == numBlocks);
  98     //assert(check());
  99 }
 100
 101 FALRU::~FALRU()
 102 {
 103     if (numCaches)
 104         delete[] cacheBoundaries;
 105
 106     delete[] blks;
 107 }
 108
 109 void
 110 FALRU::regStats(const string &name)
 111 {
 112     using namespace Stats;
 113     BaseTags::regStats(name);
 114     hits
 115         .init(numCaches+1)
 116         .name(name + ".falru_hits")
 117         .desc("The number of hits in each cache size.")
 118         ;
 119     misses
 120         .init(numCaches+1)
 121         .name(name + ".falru_misses")
 122         .desc("The number of misses in each cache size.")
 123         ;
 124     accesses
 125         .name(name + ".falru_accesses")
 126         .desc("The number of accesses to the FA LRU cache.")
 127         ;
 128
 129     for (unsigned i = 0; i <= numCaches; ++i) {
 130         stringstream size_str;
 131         if (i < 3){
 132             size_str << (1<<(i+7)) <<"K";
 133         } else {
 134             size_str << (1<<(i-3)) <<"M";
 135         }
 136
 137         hits.subname(i, size_str.str());
 138         hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
 139         misses.subname(i, size_str.str());
 140         misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
 141     }
 142 }
 143
 144 FALRUBlk *
 145 FALRU::hashLookup(Addr addr) const
 146 {
 147     tagIterator iter = tagHash.find(addr);
 148     if (iter != tagHash.end()) {
 149         return (*iter).second;
 150     }
 151     return NULL;
 152 }
 153
 154 void
 155 FALRU::invalidateBlk(FALRU::BlkType *blk)
 156 {
 157     if (blk) {
 158         blk->status = 0;
 159         blk->isTouched = false;
 160         tagsInUse--;
 161     }
 162 }
 163
 164 FALRUBlk*
 165 FALRU::accessBlock(Addr addr, int &lat, int context_src, int *inCache)
 166 {
 167     accesses++;
 168     int tmp_in_cache = 0;
 169     Addr blkAddr = blkAlign(addr);
 170     FALRUBlk* blk = hashLookup(blkAddr);
 171
 172     if (blk && blk->isValid()) {
 173         assert(blk->tag == blkAddr);
 174         tmp_in_cache = blk->inCache;
 175         for (unsigned i = 0; i < numCaches; i++) {
 176             if (1<<i & blk->inCache) {
 177                 hits[i]++;
 178             } else {
 179                 misses[i]++;
 180             }
 181         }
 182         hits[numCaches]++;
 183         if (blk != head){
 184             moveToHead(blk);
 185         }
 186     } else {
 187         blk = NULL;
 188         for (unsigned i = 0; i <= numCaches; ++i) {
 189             misses[i]++;
 190         }
 191     }
 192     if (inCache) {
 193         *inCache = tmp_in_cache;
 194     }
 195
 196     lat = hitLatency;
 197     //assert(check());
 198     return blk;
 199 }
 200
 201
 202 FALRUBlk*
 203 FALRU::findBlock(Addr addr) const
 204 {
 205     Addr blkAddr = blkAlign(addr);
 206     FALRUBlk* blk = hashLookup(blkAddr);
 207
 208     if (blk && blk->isValid()) {
 209         assert(blk->tag == blkAddr);
 210     } else {
 211         blk = NULL;
 212     }
 213     return blk;
 214 }
 215
 216 FALRUBlk*
 217 FALRU::findVictim(Addr addr, PacketList &writebacks)
 218 {
 219     FALRUBlk * blk = tail;
 220     assert(blk->inCache == 0);
 221     moveToHead(blk);
 222     tagHash.erase(blk->tag);
 223     tagHash[blkAlign(addr)] = blk;
 224     if (blk->isValid()) {
 225         replacements[0]++;
 226     } else {
 227         tagsInUse++;
 228         blk->isTouched = true;
 229         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 230             warmedUp = true;
 231             warmupCycle = curTick();
 232         }
 233     }
 234     //assert(check());
 235     return blk;
 236 }
 237
 238 void
 239 FALRU::insertBlock(Addr addr, FALRU::BlkType *blk, int context_src)
 240 {
 241 }
 242
 243 void
 244 FALRU::moveToHead(FALRUBlk *blk)
 245 {
 246     int updateMask = blk->inCache ^ cacheMask;
 247     for (unsigned i = 0; i < numCaches; i++){
 248         if ((1<<i) & updateMask) {
 249             cacheBoundaries[i]->inCache &= ~(1<<i);
 250             cacheBoundaries[i] = cacheBoundaries[i]->prev;
 251         } else if (cacheBoundaries[i] == blk) {
 252             cacheBoundaries[i] = blk->prev;
 253         }
 254     }
 255     blk->inCache = cacheMask;
 256     if (blk != head) {
 257         if (blk == tail){
 258             assert(blk->next == NULL);
 259             tail = blk->prev;
 260             tail->next = NULL;
 261         } else {
 262             blk->prev->next = blk->next;
 263             blk->next->prev = blk->prev;
 264         }
 265         blk->next = head;
 266         blk->prev = NULL;
 267         head->prev = blk;
 268         head = blk;
 269     }
 270 }
 271
 272 bool
 273 FALRU::check()
 274 {
 275     FALRUBlk* blk = head;
 276     int size = 0;
 277     int boundary = 1<<17;
 278     int j = 0;
 279     int flags = cacheMask;
 280     while (blk) {
 281         size += blkSize;
 282         if (blk->inCache != flags) {
 283             return false;
 284         }
 285         if (size == boundary && blk != tail) {
 286             if (cacheBoundaries[j] != blk) {
 287                 return false;
 288             }
 289             flags &=~(1 << j);
 290             boundary = boundary<<1;
 291             ++j;
 292         }
 293         blk = blk->next;
 294     }
 295     return true;
 296 }
 297
 298 void
 299 FALRU::clearLocks()
 300 {
 301     for (int i = 0; i < numBlocks; i++){
 302         blks[i].clearLoadLocks();
 303     }
 304 }