src/mem/cache/tags/lru.cc

   1 /*
   2  * Copyright (c) 2012 ARM Limited
   3  * All rights reserved.
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2003-2005 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Erik Hallnor
  41  */
  42
  43 /**
  44  * @file
  45  * Definitions of LRU tag store.
  46  */
  47
  48 #include <string>
  49
  50 #include "base/intmath.hh"
  51 #include "debug/Cache.hh"
  52 #include "debug/CacheRepl.hh"
  53 #include "mem/cache/tags/cacheset.hh"
  54 #include "mem/cache/tags/lru.hh"
  55 #include "mem/cache/base.hh"
  56 #include "sim/core.hh"
  57
  58 using namespace std;
  59
  60 // create and initialize a LRU/MRU cache structure
  61 LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc,
  62          unsigned _hit_latency)
  63     : numSets(_numSets), blkSize(_blkSize), assoc(_assoc),
  64       hitLatency(_hit_latency)
  65 {
  66     // Check parameters
  67     if (blkSize < 4 || !isPowerOf2(blkSize)) {
  68         fatal("Block size must be at least 4 and a power of 2");
  69     }
  70     if (numSets <= 0 || !isPowerOf2(numSets)) {
  71         fatal("# of sets must be non-zero and a power of 2");
  72     }
  73     if (assoc <= 0) {
  74         fatal("associativity must be greater than zero");
  75     }
  76     if (hitLatency <= 0) {
  77         fatal("access latency must be greater than zero");
  78     }
  79
  80     blkMask = blkSize - 1;
  81     setShift = floorLog2(blkSize);
  82     setMask = numSets - 1;
  83     tagShift = setShift + floorLog2(numSets);
  84     warmedUp = false;
  85     /** @todo Make warmup percentage a parameter. */
  86     warmupBound = numSets * assoc;
  87
  88     sets = new CacheSet[numSets];
  89     blks = new BlkType[numSets * assoc];
  90     // allocate data storage in one big chunk
  91     numBlocks = numSets * assoc;
  92     dataBlks = new uint8_t[numBlocks * blkSize];
  93
  94     unsigned blkIndex = 0;       // index into blks array
  95     for (unsigned i = 0; i < numSets; ++i) {
  96         sets[i].assoc = assoc;
  97
  98         sets[i].blks = new BlkType*[assoc];
  99
 100         // link in the data blocks
 101         for (unsigned j = 0; j < assoc; ++j) {
 102             // locate next cache block
 103             BlkType *blk = &blks[blkIndex];
 104             blk->data = &dataBlks[blkSize*blkIndex];
 105             ++blkIndex;
 106
 107             // invalidate new cache block
 108             blk->invalidate();
 109
 110             //EGH Fix Me : do we need to initialize blk?
 111
 112             // Setting the tag to j is just to prevent long chains in the hash
 113             // table; won't matter because the block is invalid
 114             blk->tag = j;
 115             blk->whenReady = 0;
 116             blk->isTouched = false;
 117             blk->size = blkSize;
 118             sets[i].blks[j]=blk;
 119             blk->set = i;
 120         }
 121     }
 122 }
 123
 124 LRU::~LRU()
 125 {
 126     delete [] dataBlks;
 127     delete [] blks;
 128     delete [] sets;
 129 }
 130
 131 LRU::BlkType*
 132 LRU::accessBlock(Addr addr, Cycles &lat, int master_id)
 133 {
 134     Addr tag = extractTag(addr);
 135     unsigned set = extractSet(addr);
 136     BlkType *blk = sets[set].findBlk(tag);
 137     lat = hitLatency;
 138     if (blk != NULL) {
 139         // move this block to head of the MRU list
 140         sets[set].moveToHead(blk);
 141         DPRINTF(CacheRepl, "set %x: moving blk %x to MRU\n",
 142                 set, regenerateBlkAddr(tag, set));
 143         if (blk->whenReady > curTick()
 144             && cache->ticksToCycles(blk->whenReady - curTick()) > hitLatency) {
 145             lat = cache->ticksToCycles(blk->whenReady - curTick());
 146         }
 147         blk->refCount += 1;
 148     }
 149
 150     return blk;
 151 }
 152
 153
 154 LRU::BlkType*
 155 LRU::findBlock(Addr addr) const
 156 {
 157     Addr tag = extractTag(addr);
 158     unsigned set = extractSet(addr);
 159     BlkType *blk = sets[set].findBlk(tag);
 160     return blk;
 161 }
 162
 163 LRU::BlkType*
 164 LRU::findVictim(Addr addr, PacketList &writebacks)
 165 {
 166     unsigned set = extractSet(addr);
 167     // grab a replacement candidate
 168     BlkType *blk = sets[set].blks[assoc-1];
 169
 170     if (blk->isValid()) {
 171         DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n",
 172                 set, regenerateBlkAddr(blk->tag, set));
 173     }
 174     return blk;
 175 }
 176
 177 void
 178 LRU::insertBlock(Addr addr, BlkType *blk, int master_id)
 179 {
 180     if (!blk->isTouched) {
 181         tagsInUse++;
 182         blk->isTouched = true;
 183         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 184             warmedUp = true;
 185             warmupCycle = curTick();
 186         }
 187     }
 188
 189     // If we're replacing a block that was previously valid update
 190     // stats for it. This can't be done in findBlock() because a
 191     // found block might not actually be replaced there if the
 192     // coherence protocol says it can't be.
 193     if (blk->isValid()) {
 194         replacements[0]++;
 195         totalRefs += blk->refCount;
 196         ++sampledRefs;
 197         blk->refCount = 0;
 198
 199         // deal with evicted block
 200         assert(blk->srcMasterId < cache->system->maxMasters());
 201         occupancies[blk->srcMasterId]--;
 202
 203         blk->invalidate();
 204     }
 205
 206     blk->isTouched = true;
 207     // Set tag for new block.  Caller is responsible for setting status.
 208     blk->tag = extractTag(addr);
 209
 210     // deal with what we are bringing in
 211     assert(master_id < cache->system->maxMasters());
 212     occupancies[master_id]++;
 213     blk->srcMasterId = master_id;
 214
 215     unsigned set = extractSet(addr);
 216     sets[set].moveToHead(blk);
 217 }
 218
 219 void
 220 LRU::invalidate(BlkType *blk)
 221 {
 222     assert(blk);
 223     assert(blk->isValid());
 224     tagsInUse--;
 225     assert(blk->srcMasterId < cache->system->maxMasters());
 226     occupancies[blk->srcMasterId]--;
 227     blk->srcMasterId = Request::invldMasterId;
 228
 229     // should be evicted before valid blocks
 230     unsigned set = blk->set;
 231     sets[set].moveToTail(blk);
 232 }
 233
 234 void
 235 LRU::clearLocks()
 236 {
 237     for (int i = 0; i < numBlocks; i++){
 238         blks[i].clearLoadLocks();
 239     }
 240 }
 241
 242 std::string
 243 LRU::print() const {
 244     std::string cache_state;
 245     for (unsigned i = 0; i < numSets; ++i) {
 246         // link in the data blocks
 247         for (unsigned j = 0; j < assoc; ++j) {
 248             BlkType *blk = sets[i].blks[j];
 249             if (blk->isValid())
 250                 cache_state += csprintf("\tset: %d block: %d %s\n", i, j,
 251                         blk->print());
 252         }
 253     }
 254     if (cache_state.empty())
 255         cache_state = "no valid tags\n";
 256     return cache_state;
 257 }
 258
 259 void
 260 LRU::cleanupRefs()
 261 {
 262     for (unsigned i = 0; i < numSets*assoc; ++i) {
 263         if (blks[i].isValid()) {
 264             totalRefs += blks[i].refCount;
 265             ++sampledRefs;
 266         }
 267     }
 268 }