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