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 master_id)
 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
 157     if (blk->isValid()) {
 158         DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n",
 159                 set, regenerateBlkAddr(blk->tag, set));
 160     }
 161     return blk;
 162 }
 163
 164 void
 165 LRU::insertBlock(Addr addr, BlkType *blk, int master_id)
 166 {
 167     if (!blk->isTouched) {
 168         tagsInUse++;
 169         blk->isTouched = true;
 170         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 171             warmedUp = true;
 172             warmupCycle = curTick();
 173         }
 174     }
 175
 176     // If we're replacing a block that was previously valid update
 177     // stats for it. This can't be done in findBlock() because a
 178     // found block might not actually be replaced there if the
 179     // coherence protocol says it can't be.
 180     if (blk->isValid()) {
 181         replacements[0]++;
 182         totalRefs += blk->refCount;
 183         ++sampledRefs;
 184         blk->refCount = 0;
 185
 186         // deal with evicted block
 187         assert(blk->srcMasterId < cache->system->maxMasters());
 188         occupancies[blk->srcMasterId]--;
 189     }
 190
 191     // Set tag for new block.  Caller is responsible for setting status.
 192     blk->tag = extractTag(addr);
 193
 194     // deal with what we are bringing in
 195     assert(master_id < cache->system->maxMasters());
 196     occupancies[master_id]++;
 197     blk->srcMasterId = master_id;
 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         if (blk->isValid()) {
 208             tagsInUse--;
 209             assert(blk->srcMasterId < cache->system->maxMasters());
 210             occupancies[blk->srcMasterId]--;
 211             blk->srcMasterId = Request::invldMasterId;
 212         }
 213         blk->status = 0;
 214         blk->isTouched = false;
 215         blk->clearLoadLocks();
 216
 217         // should be evicted before valid blocks
 218         unsigned set = blk->set;
 219         sets[set].moveToTail(blk);
 220     }
 221 }
 222
 223 void
 224 LRU::clearLocks()
 225 {
 226     for (int i = 0; i < numBlocks; i++){
 227         blks[i].clearLoadLocks();
 228     }
 229 }
 230
 231 void
 232 LRU::cleanupRefs()
 233 {
 234     for (unsigned i = 0; i < numSets*assoc; ++i) {
 235         if (blks[i].isValid()) {
 236             totalRefs += blks[i].refCount;
 237             ++sampledRefs;
 238         }
 239     }
 240 }