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