src/mem/cache/tags/split_lru.cc

   1 /*
   2  * Copyright (c) 2004-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: Lisa Hsu
  29  */
  30
  31 /**
  32  * @file
  33  * Definitions of LRU tag store for a partitioned cache.
  34  */
  35
  36 #include <string>
  37
  38 #include "mem/cache/base_cache.hh"
  39 #include "base/intmath.hh"
  40 #include "mem/cache/tags/split_lru.hh"
  41 #include "sim/root.hh"
  42
  43 using namespace std;
  44
  45 SplitBlk*
  46 SplitCacheSet::findBlk(int asid, 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 SplitCacheSet::moveToHead(SplitBlk *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     SplitBlk *next = blk;
  70
  71     do {
  72         assert(i < assoc);
  73         // swap blks[i] and next
  74         SplitBlk *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 SplitLRU::SplitLRU(int _numSets, int _blkSize, int _assoc, int _hit_latency, int _part) :
  84     numSets(_numSets), blkSize(_blkSize), assoc(_assoc), hitLatency(_hit_latency), part(_part)
  85 {
  86     // Check parameters
  87     if (blkSize < 4 || !isPowerOf2(blkSize)) {
  88         fatal("Block size must be at least 4 and a power of 2");
  89     }
  90     if (numSets <= 0 || !isPowerOf2(numSets)) {
  91         fatal("# of sets must be non-zero and a power of 2");
  92     }
  93     if (assoc <= 0) {
  94         fatal("associativity must be greater than zero");
  95     }
  96     if (hitLatency <= 0) {
  97         fatal("access latency must be greater than zero");
  98     }
  99
 100     SplitBlk  *blk;
 101     int i, j, blkIndex;
 102
 103     blkMask = blkSize - 1;
 104     setShift = floorLog2(blkSize);
 105     setMask = numSets - 1;
 106     tagShift = setShift + floorLog2(numSets);
 107     warmedUp = false;
 108     /** @todo Make warmup percentage a parameter. */
 109     warmupBound = numSets * assoc;
 110
 111     sets = new SplitCacheSet[numSets];
 112     blks = new SplitBlk[numSets * assoc];
 113     // allocate data storage in one big chunk
 114     dataBlks = new uint8_t[numSets*assoc*blkSize];
 115
 116     blkIndex = 0;       // index into blks array
 117     for (i = 0; i < numSets; ++i) {
 118         sets[i].assoc = assoc;
 119
 120         sets[i].blks = new SplitBlk*[assoc];
 121
 122         // link in the data blocks
 123         for (j = 0; j < assoc; ++j) {
 124             // locate next cache block
 125             blk = &blks[blkIndex];
 126             blk->data = &dataBlks[blkSize*blkIndex];
 127             ++blkIndex;
 128
 129             // invalidate new cache block
 130             blk->status = 0;
 131
 132             //EGH Fix Me : do we need to initialize blk?
 133
 134             // Setting the tag to j is just to prevent long chains in the hash
 135             // table; won't matter because the block is invalid
 136             blk->tag = j;
 137             blk->whenReady = 0;
 138             blk->asid = -1;
 139             blk->isTouched = false;
 140             blk->size = blkSize;
 141             sets[i].blks[j]=blk;
 142             blk->set = i;
 143             blk->part = part;
 144         }
 145     }
 146 }
 147
 148 SplitLRU::~SplitLRU()
 149 {
 150     delete [] dataBlks;
 151     delete [] blks;
 152     delete [] sets;
 153 }
 154
 155 void
 156 SplitLRU::regStats(const std::string &name)
 157 {
 158     BaseTags::regStats(name);
 159
 160     hits
 161         .name(name + ".hits")
 162         .desc("number of hits on this partition")
 163         .precision(0)
 164         ;
 165
 166     misses
 167         .name(name + ".misses")
 168         .desc("number of misses in this partition")
 169         .precision(0)
 170         ;
 171 }
 172
 173 // probe cache for presence of given block.
 174 bool
 175 SplitLRU::probe(int asid, Addr addr) const
 176 {
 177     //  return(findBlock(Read, addr, asid) != 0);
 178     Addr tag = extractTag(addr);
 179     unsigned myset = extractSet(addr);
 180
 181     SplitBlk *blk = sets[myset].findBlk(asid, tag);
 182
 183     return (blk != NULL);       // true if in cache
 184 }
 185
 186 SplitBlk*
 187 SplitLRU::findBlock(Addr addr, int asid, int &lat)
 188 {
 189     Addr tag = extractTag(addr);
 190     unsigned set = extractSet(addr);
 191     SplitBlk *blk = sets[set].findBlk(asid, tag);
 192     lat = hitLatency;
 193     if (blk != NULL) {
 194         // move this block to head of the MRU list
 195         sets[set].moveToHead(blk);
 196         if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency){
 197             lat = blk->whenReady - curTick;
 198         }
 199         blk->refCount += 1;
 200         hits++;
 201     }
 202
 203     return blk;
 204 }
 205
 206 SplitBlk*
 207 SplitLRU::findBlock(Packet * &pkt, int &lat)
 208 {
 209     Addr addr = pkt->getAddr();
 210     int asid = pkt->req->getAsid();
 211
 212     Addr tag = extractTag(addr);
 213     unsigned set = extractSet(addr);
 214     SplitBlk *blk = sets[set].findBlk(asid, tag);
 215     lat = hitLatency;
 216     if (blk != NULL) {
 217         // move this block to head of the MRU list
 218         sets[set].moveToHead(blk);
 219         if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency){
 220             lat = blk->whenReady - curTick;
 221         }
 222         blk->refCount += 1;
 223         hits++;
 224     }
 225
 226     return blk;
 227 }
 228
 229 SplitBlk*
 230 SplitLRU::findBlock(Addr addr, int asid) const
 231 {
 232     Addr tag = extractTag(addr);
 233     unsigned set = extractSet(addr);
 234     SplitBlk *blk = sets[set].findBlk(asid, tag);
 235     return blk;
 236 }
 237
 238 SplitBlk*
 239 SplitLRU::findReplacement(Packet * &pkt, PacketList &writebacks,
 240                      BlkList &compress_blocks)
 241 {
 242     unsigned set = extractSet(pkt->getAddr());
 243     // grab a replacement candidate
 244     SplitBlk *blk = sets[set].blks[assoc-1];
 245     sets[set].moveToHead(blk);
 246     if (blk->isValid()) {
 247         replacements[0]++;
 248         totalRefs += blk->refCount;
 249         ++sampledRefs;
 250         blk->refCount = 0;
 251     } else if (!blk->isTouched) {
 252         tagsInUse++;
 253         blk->isTouched = true;
 254         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 255             warmedUp = true;
 256             warmupCycle = curTick;
 257         }
 258     }
 259
 260     misses++;
 261
 262     return blk;
 263 }
 264
 265 void
 266 SplitLRU::invalidateBlk(int asid, Addr addr)
 267 {
 268     SplitBlk *blk = findBlock(addr, asid);
 269     if (blk) {
 270         blk->status = 0;
 271         blk->isTouched = false;
 272         tagsInUse--;
 273     }
 274 }
 275
 276 void
 277 SplitLRU::doCopy(Addr source, Addr dest, int asid, PacketList &writebacks)
 278 {
 279 //Copy not supported for now
 280 #if 0
 281     assert(source == blkAlign(source));
 282     assert(dest == blkAlign(dest));
 283     SplitBlk *source_blk = findBlock(source, asid);
 284     assert(source_blk);
 285     SplitBlk *dest_blk = findBlock(dest, asid);
 286     if (dest_blk == NULL) {
 287         // Need to do a replacement
 288         Packet * pkt = new Packet();
 289         pkt->paddr = dest;
 290         BlkList dummy_list;
 291         dest_blk = findReplacement(pkt, writebacks, dummy_list);
 292         if (dest_blk->isValid() && dest_blk->isModified()) {
 293             // Need to writeback data.
 294             pkt = buildWritebackReq(regenerateBlkAddr(dest_blk->tag,
 295                                                       dest_blk->set),
 296                                     dest_blk->req->asid,
 297                                     dest_blk->xc,
 298                                     blkSize,
 299                                     (cache->doData())?dest_blk->data:0,
 300                                     dest_blk->size);
 301             writebacks.push_back(pkt);
 302         }
 303         dest_blk->tag = extractTag(dest);
 304         dest_blk->req->asid = asid;
 305         /**
 306          * @todo Do we need to pass in the execution context, or can we
 307          * assume its the same?
 308          */
 309         assert(source_blk->xc);
 310         dest_blk->xc = source_blk->xc;
 311     }
 312     /**
 313      * @todo Can't assume the status once we have coherence on copies.
 314      */
 315
 316     // Set this block as readable, writeable, and dirty.
 317     dest_blk->status = 7;
 318     if (cache->doData()) {
 319         memcpy(dest_blk->data, source_blk->data, blkSize);
 320     }
 321 #endif
 322 }
 323
 324 void
 325 SplitLRU::cleanupRefs()
 326 {
 327     for (int i = 0; i < numSets*assoc; ++i) {
 328         if (blks[i].isValid()) {
 329             totalRefs += blks[i].refCount;
 330             ++sampledRefs;
 331         }
 332     }
 333 }