src/mem/cache/tags/split_lifo.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 LIFO tag store usable in 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_lifo.hh"
  41 #include "sim/core.hh"
  42 #include "base/trace.hh"
  43
  44 using namespace std;
  45
  46 SplitBlk*
  47 LIFOSet::findBlk(Addr tag) const
  48 {
  49     for (SplitBlk *blk = firstIn; blk != NULL; blk = blk->next) {
  50         if (blk->tag == tag && blk->isValid()) {
  51             return blk;
  52         }
  53     }
  54     return NULL;
  55 }
  56
  57 void
  58 LIFOSet::moveToLastIn(SplitBlk *blk)
  59 {
  60     if (blk == lastIn)
  61         return;
  62
  63     if (blk == firstIn) {
  64         blk->next->prev = NULL;
  65     } else {
  66         blk->prev->next = blk->next;
  67         blk->next->prev = blk->prev;
  68     }
  69     blk->next = NULL;
  70     blk->prev = lastIn;
  71     lastIn->next = blk;
  72
  73     lastIn = blk;
  74 }
  75
  76 void
  77 LIFOSet::moveToFirstIn(SplitBlk *blk)
  78 {
  79     if (blk == firstIn)
  80         return;
  81
  82     if (blk == lastIn) {
  83         blk->prev->next = NULL;
  84     } else {
  85         blk->next->prev = blk->prev;
  86         blk->prev->next = blk->next;
  87     }
  88
  89     blk->prev = NULL;
  90     blk->next = firstIn;
  91     firstIn->prev = blk;
  92
  93     firstIn = blk;
  94 }
  95
  96 // create and initialize a LIFO cache structure
  97 SplitLIFO::SplitLIFO(int _blkSize, int _size, int _ways, int _hit_latency, bool two_Queue, int _part) :
  98     blkSize(_blkSize), size(_size), numBlks(_size/_blkSize), numSets((_size/_ways)/_blkSize), ways(_ways),
  99     hitLatency(_hit_latency), twoQueue(two_Queue), part(_part)
 100 {
 101     if (!isPowerOf2(blkSize))
 102         fatal("cache block size (in bytes) must be a power of 2");
 103     if (!(hitLatency > 0))
 104         fatal("access latency in cycles must be at least on cycle");
 105     if (_ways == 0)
 106         fatal("if instantiating a splitLIFO, needs non-zero size!");
 107
 108
 109     SplitBlk  *blk;
 110     int i, j, blkIndex;
 111
 112     setShift = floorLog2(blkSize);
 113     blkMask = blkSize - 1;
 114     setMask = numSets - 1;
 115     tagShift = setShift + floorLog2(numSets);
 116
 117     warmedUp = false;
 118     /** @todo Make warmup percentage a parameter. */
 119     warmupBound = size/blkSize;
 120
 121     // allocate data blocks
 122     blks = new SplitBlk[numBlks];
 123     sets = new LIFOSet[numSets];
 124     dataBlks = new uint8_t[size];
 125
 126 /*
 127     // these start off point to same blk
 128     top = &(blks[0]);
 129     head = top;
 130 */
 131
 132     blkIndex = 0;
 133     for (i=0; i < numSets; ++i) {
 134         sets[i].ways = ways;
 135         sets[i].lastIn = &blks[blkIndex];
 136         sets[i].firstIn = &blks[blkIndex + ways - 1];
 137
 138         /* 3 cases:  if there is 1 way, if there are 2 ways, or if there are 3+.
 139            in the case of 1 way, last in and first out point to the same blocks,
 140            and the next and prev pointers need to be assigned specially.  and so on
 141         */
 142         /* deal with the first way */
 143         blk = &blks[blkIndex];
 144         blk->prev = &blks[blkIndex + 1];
 145         blk->next = NULL;
 146         blk->data = &dataBlks[blkSize*blkIndex];
 147         blk->size = blkSize;
 148         blk->part = part;
 149         blk->set = i;
 150         ++blkIndex;
 151
 152         /* if there are "middle" ways, do them here */
 153         if (ways > 2) {
 154             for (j=1; j < ways-1; ++j) {
 155                 blk = &blks[blkIndex];
 156                 blk->data = &dataBlks[blkSize*blkIndex];
 157                 blk->prev = &blks[blkIndex+1];
 158                 blk->next = &blks[blkIndex-1];
 159                 blk->data = &(dataBlks[blkSize*blkIndex]);
 160                 blk->size = blkSize;
 161                 blk->part = part;
 162                 blk->set = i;
 163                 ++blkIndex;
 164             }
 165         }
 166
 167         /* do the final way here, depending on whether the final way is the only
 168            way or not
 169         */
 170         if (ways > 1) {
 171             blk =  &blks[blkIndex];
 172             blk->prev = NULL;
 173             blk->next = &blks[blkIndex - 1];
 174             blk->data = &dataBlks[blkSize*blkIndex];
 175             blk->size = blkSize;
 176             blk->part = part;
 177             blk->set = i;
 178             ++blkIndex;
 179         } else {
 180             blk->prev = NULL;
 181         }
 182     }
 183     assert(blkIndex == numBlks);
 184 }
 185
 186 SplitLIFO::~SplitLIFO()
 187 {
 188     delete [] blks;
 189     delete [] sets;
 190     delete [] dataBlks;
 191 }
 192
 193 void
 194 SplitLIFO::regStats(const std::string &name)
 195 {
 196     BaseTags::regStats(name);
 197
 198     hits
 199         .name(name + ".hits")
 200         .desc("number of hits on this partition")
 201         .precision(0)
 202         ;
 203
 204     misses
 205         .name(name + ".misses")
 206         .desc("number of misses in this partition")
 207         .precision(0)
 208         ;
 209
 210     invalidations
 211         .name(name + ".invalidations")
 212         .desc("number of invalidations in this partition")
 213         .precision(0)
 214         ;
 215 }
 216
 217 // probe cache for presence of given block.
 218 bool
 219 SplitLIFO::probe(Addr addr) const
 220 {
 221     Addr tag = extractTag(addr);
 222     unsigned myset = extractSet(addr);
 223
 224     SplitBlk* blk = sets[myset].findBlk(tag);
 225     return (blk != NULL);
 226 }
 227
 228 SplitBlk*
 229 SplitLIFO::findBlock(Addr addr, int &lat)
 230 {
 231     Addr tag = extractTag(addr);
 232     unsigned set = extractSet(addr);
 233     SplitBlk *blk = sets[set].findBlk(tag);
 234
 235     lat = hitLatency;
 236
 237     if (blk) {
 238         DPRINTF(Split, "Found LIFO blk %#x in set %d, with tag %#x\n",
 239                 addr, set, tag);
 240         hits++;
 241
 242         if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency)
 243             lat = blk->whenReady - curTick;
 244         blk->refCount +=1;
 245
 246         if (twoQueue) {
 247             blk->isUsed = true;
 248             sets[set].moveToFirstIn(blk);
 249         } else {
 250             sets[set].moveToLastIn(blk);
 251         }
 252     }
 253
 254     return blk;
 255 }
 256
 257
 258 SplitBlk*
 259 SplitLIFO::findBlock(Addr addr) const
 260 {
 261     Addr tag = extractTag(addr);
 262     unsigned set = extractSet(addr);
 263     SplitBlk *blk = sets[set].findBlk(tag);
 264
 265     return blk;
 266 }
 267
 268 SplitBlk*
 269 SplitLIFO::findReplacement(Addr addr, PacketList &writebacks)
 270 {
 271     unsigned set = extractSet(addr);
 272
 273     SplitBlk *firstIn = sets[set].firstIn;
 274     SplitBlk *lastIn = sets[set].lastIn;
 275
 276     SplitBlk *blk;
 277     if (twoQueue && firstIn->isUsed) {
 278         blk = firstIn;
 279         blk->isUsed = false;
 280         sets[set].moveToLastIn(blk);
 281     } else {
 282         int withValue = sets[set].withValue;
 283         if (withValue == ways) {
 284             blk = lastIn;
 285         } else {
 286             blk = &(sets[set].firstIn[ways - ++withValue]);
 287         }
 288     }
 289
 290     DPRINTF(Split, "just assigned %#x addr into LIFO, replacing %#x status %#x\n",
 291             addr, regenerateBlkAddr(blk->tag, set), blk->status);
 292     if (blk->isValid()) {
 293         replacements[0]++;
 294         totalRefs += blk->refCount;
 295         ++sampledRefs;
 296         blk->refCount = 0;
 297     } else {
 298         tagsInUse++;
 299         blk->isTouched = true;
 300         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 301             warmedUp = true;
 302             warmupCycle = curTick;
 303         }
 304     }
 305
 306     misses++;
 307
 308     return blk;
 309 }
 310
 311 void
 312 SplitLIFO::invalidateBlk(SplitLIFO::BlkType *blk)
 313 {
 314     if (blk) {
 315         blk->status = 0;
 316         blk->isTouched = false;
 317         tagsInUse--;
 318         invalidations++;
 319     }
 320 }
 321
 322 void
 323 SplitLIFO::cleanupRefs()
 324 {
 325     for (int i = 0; i < numBlks; ++i) {
 326         if (blks[i].isValid()) {
 327             totalRefs += blks[i].refCount;
 328             ++sampledRefs;
 329         }
 330     }
 331 }