src/mem/cache/tags/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 of LRU tag store.
  34  */
  35
  36 #include <string>
  37
  38 #include "mem/cache/base.hh"
  39 #include "base/intmath.hh"
  40 #include "mem/cache/tags/lru.hh"
  41 #include "sim/core.hh"
  42
  43 using namespace std;
  44
  45 LRUBlk*
  46 CacheSet::findBlk(Addr tag) const
  47 {
  48     for (int i = 0; i < assoc; ++i) {
  49         if (blks[i]->tag == tag && blks[i]->isValid()) {
  50             return blks[i];
  51         }
  52     }
  53     return 0;
  54 }
  55
  56
  57 void
  58 CacheSet::moveToHead(LRUBlk *blk)
  59 {
  60     // nothing to do if blk is already head
  61     if (blks[0] == blk)
  62         return;
  63
  64     // write 'next' block into blks[i], moving up from MRU toward LRU
  65     // until we overwrite the block we moved to head.
  66
  67     // start by setting up to write 'blk' into blks[0]
  68     int i = 0;
  69     LRUBlk *next = blk;
  70
  71     do {
  72         assert(i < assoc);
  73         // swap blks[i] and next
  74         LRUBlk *tmp = blks[i];
  75         blks[i] = next;
  76         next = tmp;
  77         ++i;
  78     } while (next != blk);
  79 }
  80
  81
  82 // create and initialize a LRU/MRU cache structure
  83 LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc,
  84          unsigned _hit_latency)
  85     : numSets(_numSets), blkSize(_blkSize), assoc(_assoc),
  86       hitLatency(_hit_latency)
  87 {
  88     // Check parameters
  89     if (blkSize < 4 || !isPowerOf2(blkSize)) {
  90         fatal("Block size must be at least 4 and a power of 2");
  91     }
  92     if (numSets <= 0 || !isPowerOf2(numSets)) {
  93         fatal("# of sets must be non-zero and a power of 2");
  94     }
  95     if (assoc <= 0) {
  96         fatal("associativity must be greater than zero");
  97     }
  98     if (hitLatency <= 0) {
  99         fatal("access latency must be greater than zero");
 100     }
 101
 102     blkMask = blkSize - 1;
 103     setShift = floorLog2(blkSize);
 104     setMask = numSets - 1;
 105     tagShift = setShift + floorLog2(numSets);
 106     warmedUp = false;
 107     /** @todo Make warmup percentage a parameter. */
 108     warmupBound = numSets * assoc;
 109
 110     sets = new CacheSet[numSets];
 111     blks = new LRUBlk[numSets * assoc];
 112     // allocate data storage in one big chunk
 113     dataBlks = new uint8_t[numSets*assoc*blkSize];
 114
 115     unsigned blkIndex = 0;       // index into blks array
 116     for (unsigned i = 0; i < numSets; ++i) {
 117         sets[i].assoc = assoc;
 118
 119         sets[i].blks = new LRUBlk*[assoc];
 120
 121         // link in the data blocks
 122         for (unsigned j = 0; j < assoc; ++j) {
 123             // locate next cache block
 124             LRUBlk *blk = &blks[blkIndex];
 125             blk->data = &dataBlks[blkSize*blkIndex];
 126             ++blkIndex;
 127
 128             // invalidate new cache block
 129             blk->status = 0;
 130
 131             //EGH Fix Me : do we need to initialize blk?
 132
 133             // Setting the tag to j is just to prevent long chains in the hash
 134             // table; won't matter because the block is invalid
 135             blk->tag = j;
 136             blk->whenReady = 0;
 137             blk->isTouched = false;
 138             blk->size = blkSize;
 139             sets[i].blks[j]=blk;
 140             blk->set = i;
 141         }
 142     }
 143 }
 144
 145 LRU::~LRU()
 146 {
 147     delete [] dataBlks;
 148     delete [] blks;
 149     delete [] sets;
 150 }
 151
 152 LRUBlk*
 153 LRU::accessBlock(Addr addr, int &lat)
 154 {
 155     Addr tag = extractTag(addr);
 156     unsigned set = extractSet(addr);
 157     LRUBlk *blk = sets[set].findBlk(tag);
 158     lat = hitLatency;
 159     if (blk != NULL) {
 160         // move this block to head of the MRU list
 161         sets[set].moveToHead(blk);
 162         DPRINTF(CacheRepl, "set %x: moving blk %x to MRU\n",
 163                 set, regenerateBlkAddr(tag, set));
 164         if (blk->whenReady > curTick
 165             && blk->whenReady - curTick > hitLatency) {
 166             lat = blk->whenReady - curTick;
 167         }
 168         blk->refCount += 1;
 169     }
 170
 171     return blk;
 172 }
 173
 174
 175 LRUBlk*
 176 LRU::findBlock(Addr addr) const
 177 {
 178     Addr tag = extractTag(addr);
 179     unsigned set = extractSet(addr);
 180     LRUBlk *blk = sets[set].findBlk(tag);
 181     return blk;
 182 }
 183
 184 LRUBlk*
 185 LRU::findVictim(Addr addr, PacketList &writebacks)
 186 {
 187     unsigned set = extractSet(addr);
 188     // grab a replacement candidate
 189     LRUBlk *blk = sets[set].blks[assoc-1];
 190     if (blk->isValid()) {
 191         replacements[0]++;
 192         totalRefs += blk->refCount;
 193         ++sampledRefs;
 194         blk->refCount = 0;
 195
 196         DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n",
 197                 set, regenerateBlkAddr(blk->tag, set));
 198     }
 199     return blk;
 200 }
 201
 202 void
 203 LRU::insertBlock(Addr addr, LRU::BlkType *blk)
 204 {
 205     if (!blk->isTouched) {
 206         tagsInUse++;
 207         blk->isTouched = true;
 208         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 209             warmedUp = true;
 210             warmupCycle = curTick;
 211         }
 212     }
 213
 214     // Set tag for new block.  Caller is responsible for setting status.
 215     blk->tag = extractTag(addr);
 216
 217     unsigned set = extractSet(addr);
 218     sets[set].moveToHead(blk);
 219 }
 220
 221 void
 222 LRU::invalidateBlk(LRU::BlkType *blk)
 223 {
 224     if (blk) {
 225         blk->status = 0;
 226         blk->isTouched = false;
 227         blk->clearLoadLocks();
 228         tagsInUse--;
 229     }
 230 }
 231
 232 void
 233 LRU::cleanupRefs()
 234 {
 235     for (unsigned i = 0; i < numSets*assoc; ++i) {
 236         if (blks[i].isValid()) {
 237             totalRefs += blks[i].refCount;
 238             ++sampledRefs;
 239         }
 240     }
 241 }