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/root.hh"
  42 #include "base/trace.hh"
  43
  44 using namespace std;
  45
  46 SplitBlk*
  47 LIFOSet::findBlk(int asid, 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(int asid, Addr addr) const
 220 {
 221     Addr tag = extractTag(addr);
 222     unsigned myset = extractSet(addr);
 223
 224     SplitBlk* blk = sets[myset].findBlk(asid, tag);
 225     return (blk != NULL);
 226 }
 227
 228 SplitBlk*
 229 SplitLIFO::findBlock(Addr addr, int asid, int &lat)
 230 {
 231     Addr tag = extractTag(addr);
 232     unsigned set = extractSet(addr);
 233     SplitBlk *blk = sets[set].findBlk(asid, 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 SplitBlk*
 258 SplitLIFO::findBlock(Packet * &pkt, int &lat)
 259 {
 260     Addr addr = pkt->getAddr();
 261     int asid = pkt->req->getAsid();
 262
 263     Addr tag = extractTag(addr);
 264     unsigned set = extractSet(addr);
 265     SplitBlk *blk = sets[set].findBlk(asid, tag);
 266
 267     if (blk) {
 268         DPRINTF(Split, "Found LIFO blk %#x in set %d, with tag %#x\n",
 269                 addr, set, tag);
 270         hits++;
 271
 272         if (twoQueue) {
 273             blk->isUsed = true;
 274             sets[set].moveToFirstIn(blk);
 275         } else {
 276             sets[set].moveToLastIn(blk);
 277         }
 278     }
 279     lat = hitLatency;
 280
 281     return blk;
 282 }
 283
 284 SplitBlk*
 285 SplitLIFO::findBlock(Addr addr, int asid) const
 286 {
 287     Addr tag = extractTag(addr);
 288     unsigned set = extractSet(addr);
 289     SplitBlk *blk = sets[set].findBlk(asid, tag);
 290
 291     return blk;
 292 }
 293
 294 SplitBlk*
 295 SplitLIFO::findReplacement(Packet * &pkt, PacketList &writebacks,
 296                            BlkList &compress_blocks)
 297 {
 298     unsigned set = extractSet(pkt->getAddr());
 299
 300     SplitBlk *firstIn = sets[set].firstIn;
 301     SplitBlk *lastIn = sets[set].lastIn;
 302
 303     SplitBlk *blk;
 304     if (twoQueue && firstIn->isUsed) {
 305         blk = firstIn;
 306         blk->isUsed = false;
 307         sets[set].moveToLastIn(blk);
 308     } else {
 309         int withValue = sets[set].withValue;
 310         if (withValue == ways) {
 311             blk = lastIn;
 312         } else {
 313             blk = &(sets[set].firstIn[ways - ++withValue]);
 314         }
 315     }
 316
 317     DPRINTF(Split, "just assigned %#x addr into LIFO, replacing %#x status %#x\n",
 318             pkt->getAddr(), regenerateBlkAddr(blk->tag, set), blk->status);
 319     if (blk->isValid()) {
 320         replacements[0]++;
 321         totalRefs += blk->refCount;
 322         ++sampledRefs;
 323         blk->refCount = 0;
 324     } else {
 325         tagsInUse++;
 326         blk->isTouched = true;
 327         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 328             warmedUp = true;
 329             warmupCycle = curTick;
 330         }
 331     }
 332
 333     misses++;
 334
 335     return blk;
 336 }
 337
 338 void
 339 SplitLIFO::invalidateBlk(int asid, Addr addr)
 340 {
 341     SplitBlk *blk = findBlock(addr, asid);
 342     if (blk) {
 343         blk->status = 0;
 344         blk->isTouched = false;
 345         tagsInUse--;
 346         invalidations++;
 347     }
 348 }
 349
 350 void
 351 SplitLIFO::doCopy(Addr source, Addr dest, int asid, PacketList &writebacks)
 352 {
 353 //Copy Unsuported for now
 354 #if 0
 355     assert(source == blkAlign(source));
 356     assert(dest == blkAlign(dest));
 357     SplitBlk *source_blk = findBlock(source, asid);
 358     assert(source_blk);
 359     SplitBlk *dest_blk = findBlock(dest, asid);
 360     if (dest_blk == NULL) {
 361         // Need to do a replacement
 362         Packet * pkt = new Packet();
 363         pkt->paddr = dest;
 364         BlkList dummy_list;
 365         dest_blk = findReplacement(pkt, writebacks, dummy_list);
 366         if (dest_blk->isValid() && dest_blk->isModified()) {
 367             // Need to writeback data.
 368             pkt = buildWritebackReq(regenerateBlkAddr(dest_blk->tag,
 369                                                       dest_blk->set),
 370                                     dest_blk->req->asid,
 371                                     dest_blk->xc,
 372                                     blkSize,
 373                                     (cache->doData())?dest_blk->data:0,
 374                                     dest_blk->size);
 375             writebacks.push_back(pkt);
 376         }
 377         dest_blk->tag = extractTag(dest);
 378         dest_blk->req->asid = asid;
 379         /**
 380          * @todo Do we need to pass in the execution context, or can we
 381          * assume its the same?
 382          */
 383         assert(source_blk->xc);
 384         dest_blk->xc = source_blk->xc;
 385     }
 386     /**
 387      * @todo Can't assume the status once we have coherence on copies.
 388      */
 389
 390     // Set this block as readable, writeable, and dirty.
 391     dest_blk->status = 7;
 392     if (cache->doData()) {
 393         memcpy(dest_blk->data, source_blk->data, blkSize);
 394     }
 395 #endif
 396 }
 397
 398 void
 399 SplitLIFO::cleanupRefs()
 400 {
 401     for (int i = 0; i < numBlks; ++i) {
 402         if (blks[i].isValid()) {
 403             totalRefs += blks[i].refCount;
 404             ++sampledRefs;
 405         }
 406     }
 407 }