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