src/mem/cache/tags/iic.cc

   1 /*
   2  * Copyright (c) 2002-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 the Indirect Index Cache tagstore.
  34  */
  35
  36 #include <algorithm>
  37 #include <string>
  38 #include <vector>
  39
  40 #include <math.h>
  41
  42 #include "mem/cache/base_cache.hh"
  43 #include "mem/cache/tags/iic.hh"
  44 #include "base/intmath.hh"
  45 #include "sim/root.hh" // for curTick
  46
  47 #include "base/trace.hh" // for DPRINTF
  48
  49
  50 using namespace std;
  51
  52 /** Track the number of accesses to each cache set. */
  53 #define PROFILE_IIC 1
  54
  55 IIC::IIC(IIC::Params &params) :
  56     hashSets(params.numSets), blkSize(params.blkSize), assoc(params.assoc),
  57     hitLatency(params.hitLatency), subSize(params.subblockSize),
  58     numSub(blkSize/subSize),
  59     trivialSize((floorLog2(params.size/subSize)*numSub)/8),
  60     tagShift(floorLog2(blkSize)), blkMask(blkSize - 1),
  61     subShift(floorLog2(subSize)), subMask(numSub - 1),
  62     hashDelay(params.hashDelay),
  63     numBlocks(params.size/subSize),
  64     numTags(hashSets * assoc + params.size/blkSize -1),
  65     numSecondary(params.size/blkSize),
  66     tagNull(numTags),
  67     primaryBound(hashSets * assoc)
  68 {
  69     int i;
  70
  71     // Check parameters
  72     if (blkSize < 4 || !isPowerOf2(blkSize)) {
  73         fatal("Block size must be at least 4 and a power of 2");
  74     }
  75     if (hashSets <= 0 || !isPowerOf2(hashSets)) {
  76         fatal("# of hashsets must be non-zero and a power of 2");
  77     }
  78     if (assoc <= 0) {
  79         fatal("associativity must be greater than zero");
  80     }
  81     if (hitLatency <= 0) {
  82         fatal("access latency must be greater than zero");
  83     }
  84     if (numSub*subSize != blkSize) {
  85         fatal("blocksize must be evenly divisible by subblock size");
  86     }
  87
  88     // debug stuff
  89     freeSecond = numSecondary;
  90
  91     warmedUp = false;
  92     warmupBound = params.size/blkSize;
  93
  94     // Replacement Policy Initialization
  95     repl = params.rp;
  96     repl->setIIC(this);
  97
  98     //last_miss_time = 0
  99
 100     // allocate data reference counters
 101     dataReferenceCount = new int[numBlocks];
 102     memset(dataReferenceCount, 0, numBlocks*sizeof(int));
 103
 104     // Allocate storage for both internal data and block fast access data.
 105     // We allocate it as one large chunk to reduce overhead and to make
 106     // deletion easier.
 107     int data_index = 0;
 108     dataStore = new uint8_t[(numBlocks + numTags) * blkSize];
 109     dataBlks = new uint8_t*[numBlocks];
 110     for (i = 0; i < numBlocks; ++i) {
 111         dataBlks[i] = &dataStore[data_index];
 112         freeDataBlock(i);
 113         data_index += subSize;
 114     }
 115
 116     assert(data_index == numBlocks * subSize);
 117
 118     // allocate and init tag store
 119     tagStore = new IICTag[numTags];
 120
 121     int blkIndex = 0;
 122     // allocate and init sets
 123     sets = new IICSet[hashSets];
 124     for (i = 0; i < hashSets; ++i) {
 125         sets[i].assoc = assoc;
 126         sets[i].tags = new IICTag*[assoc];
 127         sets[i].chain_ptr = tagNull;
 128
 129         for (int j = 0; j < assoc; ++j) {
 130             IICTag *tag = &tagStore[blkIndex++];
 131             tag->chain_ptr = tagNull;
 132             tag->data_ptr.resize(numSub);
 133             tag->size = blkSize;
 134             tag->trivialData = new uint8_t[trivialSize];
 135             tag->numData = 0;
 136             sets[i].tags[j] = tag;
 137             tag->set = i;
 138             tag->data = &dataStore[data_index];
 139             data_index += blkSize;
 140         }
 141     }
 142
 143     assert(blkIndex == primaryBound);
 144
 145     for (i = primaryBound; i < tagNull; i++) {
 146         tagStore[i].chain_ptr = i+1;
 147         //setup data ptrs to subblocks
 148         tagStore[i].data_ptr.resize(numSub);
 149         tagStore[i].size = blkSize;
 150         tagStore[i].trivialData = new uint8_t[trivialSize];
 151         tagStore[i].numData = 0;
 152         tagStore[i].set = 0;
 153         tagStore[i].data = &dataStore[data_index];
 154         data_index += blkSize;
 155     }
 156     freelist = primaryBound;
 157 }
 158
 159 IIC::~IIC()
 160 {
 161     delete [] dataReferenceCount;
 162     delete [] dataStore;
 163     delete [] tagStore;
 164     delete [] sets;
 165 }
 166
 167 /* register cache stats */
 168 void
 169 IIC::regStats(const string &name)
 170 {
 171     using namespace Stats;
 172
 173     BaseTags::regStats(name);
 174
 175     hitHashDepth.init(0, 20, 1);
 176     missHashDepth.init(0, 20, 1);
 177     setAccess.init(0, hashSets, 1);
 178
 179     /** IIC Statistics */
 180     hitHashDepth
 181         .name(name + ".hit_hash_depth_dist")
 182         .desc("Dist. of Hash lookup depths")
 183         .flags(pdf)
 184         ;
 185
 186     missHashDepth
 187         .name(name + ".miss_hash_depth_dist")
 188         .desc("Dist. of Hash lookup depths")
 189         .flags(pdf)
 190         ;
 191
 192     repl->regStats(name);
 193
 194     if (PROFILE_IIC)
 195         setAccess
 196             .name(name + ".set_access_dist")
 197             .desc("Dist. of Accesses across sets")
 198             .flags(pdf)
 199             ;
 200
 201     missDepthTotal
 202         .name(name + ".miss_depth_total")
 203         .desc("Total of miss depths")
 204         ;
 205
 206     hashMiss
 207         .name(name + ".hash_miss")
 208         .desc("Total of misses in hash table")
 209         ;
 210
 211     hitDepthTotal
 212         .name(name + ".hit_depth_total")
 213         .desc("Total of hit depths")
 214         ;
 215
 216     hashHit
 217         .name(name + ".hash_hit")
 218         .desc("Total of hites in hash table")
 219         ;
 220 }
 221
 222 // probe cache for presence of given block.
 223 bool
 224 IIC::probe(int asid, Addr addr) const
 225 {
 226     return (findBlock(addr,asid) != NULL);
 227 }
 228
 229 IICTag*
 230 IIC::findBlock(Addr addr, int asid, int &lat)
 231 {
 232     Addr tag = extractTag(addr);
 233     unsigned set = hash(addr);
 234     int set_lat;
 235
 236     unsigned long chain_ptr;
 237
 238     if (PROFILE_IIC)
 239         setAccess.sample(set);
 240
 241     IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
 242     set_lat = 1;
 243     if (tag_ptr == NULL && chain_ptr != tagNull) {
 244         int secondary_depth;
 245         tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
 246         set_lat += secondary_depth;
 247         // set depth for statistics fix this later!!! egh
 248         sets[set].depth = set_lat;
 249
 250         if (tag_ptr != NULL) {
 251             /* need to move tag into primary table */
 252             // need to preserve chain: fix this egh
 253             sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr;
 254             tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore);
 255             tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
 256             assert(tag_ptr!=NULL);
 257         }
 258
 259     }
 260     set_lat = set_lat * hashDelay + hitLatency;
 261     if (tag_ptr != NULL) {
 262         // IIC replacement: if this is not the first element of
 263         //   list, reorder
 264         sets[set].moveToHead(tag_ptr);
 265
 266         hitHashDepth.sample(sets[set].depth);
 267         hashHit++;
 268         hitDepthTotal += sets[set].depth;
 269         tag_ptr->status |= BlkReferenced;
 270         lat = set_lat;
 271         if (tag_ptr->whenReady > curTick && tag_ptr->whenReady - curTick > set_lat) {
 272             lat = tag_ptr->whenReady - curTick;
 273         }
 274
 275         tag_ptr->refCount += 1;
 276     }
 277     else {
 278         // fall through: cache block not found, not a hit...
 279         missHashDepth.sample(sets[set].depth);
 280         hashMiss++;
 281         missDepthTotal += sets[set].depth;
 282         lat = set_lat;
 283     }
 284     return tag_ptr;
 285 }
 286
 287 IICTag*
 288 IIC::findBlock(Packet * &pkt, int &lat)
 289 {
 290     Addr addr = pkt->getAddr();
 291     int asid = pkt->req->getAsid();
 292
 293     Addr tag = extractTag(addr);
 294     unsigned set = hash(addr);
 295     int set_lat;
 296
 297     unsigned long chain_ptr;
 298
 299     if (PROFILE_IIC)
 300         setAccess.sample(set);
 301
 302     IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
 303     set_lat = 1;
 304     if (tag_ptr == NULL && chain_ptr != tagNull) {
 305         int secondary_depth;
 306         tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
 307         set_lat += secondary_depth;
 308         // set depth for statistics fix this later!!! egh
 309         sets[set].depth = set_lat;
 310
 311         if (tag_ptr != NULL) {
 312             /* need to move tag into primary table */
 313             // need to preserve chain: fix this egh
 314             sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr;
 315             tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore);
 316             tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
 317             assert(tag_ptr!=NULL);
 318         }
 319
 320     }
 321     set_lat = set_lat * hashDelay + hitLatency;
 322     if (tag_ptr != NULL) {
 323         // IIC replacement: if this is not the first element of
 324         //   list, reorder
 325         sets[set].moveToHead(tag_ptr);
 326
 327         hitHashDepth.sample(sets[set].depth);
 328         hashHit++;
 329         hitDepthTotal += sets[set].depth;
 330         tag_ptr->status |= BlkReferenced;
 331         lat = set_lat;
 332         if (tag_ptr->whenReady > curTick && tag_ptr->whenReady - curTick > set_lat) {
 333             lat = tag_ptr->whenReady - curTick;
 334         }
 335
 336         tag_ptr->refCount += 1;
 337     }
 338     else {
 339         // fall through: cache block not found, not a hit...
 340         missHashDepth.sample(sets[set].depth);
 341         hashMiss++;
 342         missDepthTotal += sets[set].depth;
 343         lat = set_lat;
 344     }
 345     return tag_ptr;
 346 }
 347
 348 IICTag*
 349 IIC::findBlock(Addr addr, int asid) const
 350 {
 351     Addr tag = extractTag(addr);
 352     unsigned set = hash(addr);
 353
 354     unsigned long chain_ptr;
 355
 356     IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
 357     if (tag_ptr == NULL && chain_ptr != tagNull) {
 358         int secondary_depth;
 359         tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
 360     }
 361     return tag_ptr;
 362 }
 363
 364
 365 IICTag*
 366 IIC::findReplacement(Packet * &pkt, PacketList &writebacks,
 367                      BlkList &compress_blocks)
 368 {
 369     DPRINTF(IIC, "Finding Replacement for %x\n", pkt->getAddr());
 370     unsigned set = hash(pkt->getAddr());
 371     IICTag *tag_ptr;
 372     unsigned long *tmp_data = new unsigned long[numSub];
 373
 374     // Get a enough subblocks for a full cache line
 375     for (int i = 0; i < numSub; ++i){
 376         tmp_data[i] = getFreeDataBlock(writebacks);
 377         assert(dataReferenceCount[tmp_data[i]]==0);
 378     }
 379
 380     tag_ptr = getFreeTag(set, writebacks);
 381
 382     tag_ptr->set = set;
 383     for (int i=0; i< numSub; ++i) {
 384         tag_ptr->data_ptr[i] = tmp_data[i];
 385         dataReferenceCount[tag_ptr->data_ptr[i]]++;
 386     }
 387     tag_ptr->numData = numSub;
 388     assert(tag_ptr - tagStore < primaryBound); // make sure it is in primary
 389     tag_ptr->chain_ptr = tagNull;
 390     sets[set].moveToHead(tag_ptr);
 391     delete [] tmp_data;
 392
 393     list<unsigned long> tag_indexes;
 394     repl->doAdvance(tag_indexes);
 395     while (!tag_indexes.empty()) {
 396         if (!tagStore[tag_indexes.front()].isCompressed()) {
 397             compress_blocks.push_back(&tagStore[tag_indexes.front()]);
 398         }
 399         tag_indexes.pop_front();
 400     }
 401
 402     tag_ptr->re = (void*)repl->add(tag_ptr-tagStore);
 403
 404     return tag_ptr;
 405 }
 406
 407 void
 408 IIC::freeReplacementBlock(PacketList & writebacks)
 409 {
 410     IICTag *tag_ptr;
 411     unsigned long data_ptr;
 412     /* consult replacement policy */
 413     tag_ptr = &tagStore[repl->getRepl()];
 414     assert(tag_ptr->isValid());
 415
 416     DPRINTF(Cache, "Replacing %x in IIC: %s\n",
 417             regenerateBlkAddr(tag_ptr->tag,0),
 418             tag_ptr->isModified() ? "writeback" : "clean");
 419     /* write back replaced block data */
 420     if (tag_ptr && (tag_ptr->isValid())) {
 421         replacements[0]++;
 422         totalRefs += tag_ptr->refCount;
 423         ++sampledRefs;
 424         tag_ptr->refCount = 0;
 425
 426         if (tag_ptr->isModified()) {
 427 /*          Packet * writeback =
 428                 buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0),
 429                                   tag_ptr->req->asid, tag_ptr->xc, blkSize,
 430                                   tag_ptr->data,
 431                                   tag_ptr->size);
 432 */
 433         Request *writebackReq = new Request(regenerateBlkAddr(tag_ptr->tag, 0),
 434                                            blkSize, 0);
 435         Packet *writeback = new Packet(writebackReq, Packet::Writeback, -1);
 436         writeback->dataDynamic<uint8_t>(tag_ptr->data);
 437
 438             writebacks.push_back(writeback);
 439         }
 440     }
 441
 442     // free the data blocks
 443     for (int i = 0; i < tag_ptr->numData; ++i) {
 444         data_ptr = tag_ptr->data_ptr[i];
 445         assert(dataReferenceCount[data_ptr]>0);
 446         if (--dataReferenceCount[data_ptr] == 0) {
 447             freeDataBlock(data_ptr);
 448         }
 449     }
 450     freeTag(tag_ptr);
 451 }
 452
 453 unsigned long
 454 IIC::getFreeDataBlock(PacketList & writebacks)
 455 {
 456     struct IICTag *tag_ptr;
 457     unsigned long data_ptr;
 458
 459     tag_ptr = NULL;
 460     /* find data block */
 461     while (blkFreelist.empty()) {
 462         freeReplacementBlock(writebacks);
 463     }
 464
 465     data_ptr = blkFreelist.front();
 466     blkFreelist.pop_front();
 467     DPRINTF(IICMore,"Found free data at %d\n",data_ptr);
 468     return data_ptr;
 469 }
 470
 471
 472
 473 IICTag*
 474 IIC::getFreeTag(int set, PacketList & writebacks)
 475 {
 476     unsigned long tag_index;
 477     IICTag *tag_ptr;
 478     // Add new tag
 479     tag_ptr = sets[set].findFree();
 480     // if no free in primary, and secondary exists
 481     if (!tag_ptr && numSecondary) {
 482         // need to spill a tag into secondary storage
 483         while (freelist == tagNull) {
 484             // get replacements until one is in secondary
 485             freeReplacementBlock(writebacks);
 486         }
 487
 488         tag_index = freelist;
 489         freelist = tagStore[freelist].chain_ptr;
 490         freeSecond--;
 491
 492         assert(tag_index != tagNull);
 493         tagSwap(tag_index, sets[set].tags[assoc-1] - tagStore);
 494         tagStore[tag_index].chain_ptr = sets[set].chain_ptr;
 495         sets[set].chain_ptr = tag_index;
 496
 497         tag_ptr = sets[set].tags[assoc-1];
 498     }
 499     DPRINTF(IICMore,"Found free tag at %d\n",tag_ptr - tagStore);
 500     tagsInUse++;
 501     if (!warmedUp && tagsInUse.value() >= warmupBound) {
 502         warmedUp = true;
 503         warmupCycle = curTick;
 504     }
 505
 506     return tag_ptr;
 507 }
 508
 509 void
 510 IIC::freeTag(IICTag *tag_ptr)
 511 {
 512     unsigned long tag_index, tmp_index;
 513     // Fix tag_ptr
 514     if (tag_ptr) {
 515         // we have a tag to clear
 516         DPRINTF(IICMore,"Freeing Tag for %x\n",
 517                 regenerateBlkAddr(tag_ptr->tag,0));
 518         tagsInUse--;
 519         tag_ptr->status = 0;
 520         tag_ptr->numData = 0;
 521         tag_ptr->re = NULL;
 522         tag_index = tag_ptr - tagStore;
 523         if (tag_index >= primaryBound) {
 524             // tag_ptr points to secondary store
 525             assert(tag_index < tagNull); // remove this?? egh
 526             if (tag_ptr->chain_ptr == tagNull) {
 527                 // need to fix chain list
 528                 unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 529                 if (sets[tmp_set].chain_ptr == tag_index) {
 530                     sets[tmp_set].chain_ptr = tagNull;
 531                 } else {
 532                     tmp_index = sets[tmp_set].chain_ptr;
 533                     while (tmp_index != tagNull
 534                            && tagStore[tmp_index].chain_ptr != tag_index) {
 535                         tmp_index = tagStore[tmp_index].chain_ptr;
 536                     }
 537                     assert(tmp_index != tagNull);
 538                     tagStore[tmp_index].chain_ptr = tagNull;
 539                 }
 540                 tag_ptr->chain_ptr = freelist;
 541                 freelist = tag_index;
 542                 freeSecond++;
 543             } else {
 544                 // copy next chained entry to this tag location
 545                 tmp_index = tag_ptr->chain_ptr;
 546                 tagSwap(tmp_index, tag_index);
 547                 tagStore[tmp_index].chain_ptr = freelist;
 548                 freelist = tmp_index;
 549                 freeSecond++;
 550             }
 551         } else {
 552             // tag_ptr in primary hash table
 553             assert(tag_index < primaryBound);
 554             tag_ptr->status = 0;
 555             unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 556             if (sets[tmp_set].chain_ptr != tagNull) { // collapse chain
 557                 tmp_index = sets[tmp_set].chain_ptr;
 558                 tagSwap(tag_index, tmp_index);
 559                 tagStore[tmp_index].chain_ptr = freelist;
 560                 freelist = tmp_index;
 561                 freeSecond++;
 562                 sets[tmp_set].chain_ptr = tag_ptr->chain_ptr;
 563                 sets[tmp_set].moveToTail(tag_ptr);
 564             }
 565         }
 566     }
 567 }
 568
 569 void
 570 IIC::freeDataBlock(unsigned long data_ptr)
 571 {
 572     assert(dataReferenceCount[data_ptr] == 0);
 573     DPRINTF(IICMore, "Freeing data at %d\n", data_ptr);
 574     blkFreelist.push_front(data_ptr);
 575 }
 576
 577 /** Use a simple modulo hash. */
 578 #define SIMPLE_HASH 0
 579
 580 unsigned
 581 IIC::hash(Addr addr) const {
 582 #if SIMPLE_HASH
 583     return extractTag(addr) % iic_hash_size;
 584 #else
 585     Addr tag, mask, x, y;
 586     tag = extractTag(addr);
 587     mask = hashSets-1; /* assumes iic_hash_size is a power of 2 */
 588     x = tag & mask;
 589     y = (tag >> (int)(::log(hashSets)/::log(2))) & mask;
 590     assert (x < hashSets && y < hashSets);
 591     return x ^ y;
 592 #endif
 593 }
 594
 595
 596 void
 597 IICSet::moveToHead(IICTag *tag)
 598 {
 599     if (tags[0] == tag)
 600         return;
 601
 602     // write 'next' block into blks[i], moving up from MRU toward LRU
 603     // until we overwrite the block we moved to head.
 604
 605     // start by setting up to write 'blk' into blks[0]
 606     int i = 0;
 607     IICTag *next = tag;
 608
 609     do {
 610         assert(i < assoc);
 611         // swap blks[i] and next
 612         IICTag *tmp = tags[i];
 613         tags[i] = next;
 614         next = tmp;
 615         ++i;
 616     } while (next != tag);
 617 }
 618
 619 void
 620 IICSet::moveToTail(IICTag *tag)
 621 {
 622     if (tags[assoc-1] == tag)
 623         return;
 624
 625     // write 'next' block into blks[i], moving up from MRU toward LRU
 626     // until we overwrite the block we moved to head.
 627
 628     // start by setting up to write 'blk' into blks[0]
 629     int i = assoc - 1;
 630     IICTag *next = tag;
 631
 632     do {
 633         assert(i >= 0);
 634         // swap blks[i] and next
 635         IICTag *tmp = tags[i];
 636         tags[i] = next;
 637         next = tmp;
 638         --i;
 639     } while (next != tag);
 640 }
 641
 642 void
 643 IIC::tagSwap(unsigned long index1, unsigned long index2)
 644 {
 645     DPRINTF(IIC,"Swapping tag[%d]=%x for tag[%d]=%x\n",index1,
 646             tagStore[index1].tag<<tagShift, index2,
 647             tagStore[index2].tag<<tagShift);
 648     IICTag tmp_tag;
 649     tmp_tag = tagStore[index1];
 650     tagStore[index1] = tagStore[index2];
 651     tagStore[index2] = tmp_tag;
 652     if (tagStore[index1].isValid())
 653         repl->fixTag(tagStore[index1].re, index2, index1);
 654     if (tagStore[index2].isValid())
 655         repl->fixTag(tagStore[index2].re, index1, index2);
 656 }
 657
 658
 659 IICTag *
 660 IIC::secondaryChain(int asid, Addr tag, unsigned long chain_ptr,
 661                     int *_depth) const
 662 {
 663     int depth = 0;
 664     while (chain_ptr != tagNull) {
 665         DPRINTF(IIC,"Searching secondary at %d for %x\n", chain_ptr,
 666                 tag<<tagShift);
 667         if (tagStore[chain_ptr].tag == tag &&
 668             tagStore[chain_ptr].asid == asid &&
 669             (tagStore[chain_ptr].isValid())) {
 670             *_depth = depth;
 671             return &tagStore[chain_ptr];
 672         }
 673         depth++;
 674         chain_ptr = tagStore[chain_ptr].chain_ptr;
 675     }
 676     *_depth = depth;
 677     return NULL;
 678 }
 679
 680 void
 681 IIC::decompressBlock(unsigned long index)
 682 {
 683     IICTag *tag_ptr = &tagStore[index];
 684     if (tag_ptr->isCompressed()) {
 685         // decompress the data here.
 686     }
 687 }
 688
 689 void
 690 IIC::compressBlock(unsigned long index)
 691 {
 692     IICTag *tag_ptr = &tagStore[index];
 693     if (!tag_ptr->isCompressed()) {
 694         // Compress the data here.
 695     }
 696 }
 697
 698 void
 699 IIC::invalidateBlk(int asid, Addr addr)
 700 {
 701     IICTag* tag_ptr = findBlock(addr, asid);
 702     if (tag_ptr) {
 703         for (int i = 0; i < tag_ptr->numData; ++i) {
 704             dataReferenceCount[tag_ptr->data_ptr[i]]--;
 705             if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) {
 706                 freeDataBlock(tag_ptr->data_ptr[i]);
 707             }
 708         }
 709         repl->removeEntry(tag_ptr->re);
 710         freeTag(tag_ptr);
 711     }
 712 }
 713
 714 void
 715 IIC::readData(IICTag *blk, uint8_t *data){
 716 //    assert(cache->doData());
 717     assert(blk->size <= trivialSize || blk->numData > 0);
 718     int data_size = blk->size;
 719     if (data_size > trivialSize) {
 720         for (int i = 0; i < blk->numData; ++i){
 721             memcpy(data+i*subSize,
 722                    &(dataBlks[blk->data_ptr[i]][0]),
 723                    (data_size>subSize)?subSize:data_size);
 724             data_size -= subSize;
 725         }
 726     } else {
 727         memcpy(data,blk->trivialData,data_size);
 728     }
 729 }
 730
 731 void
 732 IIC::writeData(IICTag *blk, uint8_t *write_data, int size,
 733                PacketList & writebacks){
 734 //    assert(cache->doData());
 735     assert(size < blkSize || !blk->isCompressed());
 736     DPRINTF(IIC, "Writing %d bytes to %x\n", size,
 737             blk->tag<<tagShift);
 738     // Find the number of subblocks needed, (round up)
 739     int num_subs = (size + (subSize -1))/subSize;
 740     if (size <= trivialSize) {
 741         num_subs = 0;
 742     }
 743     assert(num_subs <= numSub);
 744     if (num_subs > blk->numData) {
 745         // need to allocate more data blocks
 746         for (int i = blk->numData; i < num_subs; ++i){
 747             blk->data_ptr[i] = getFreeDataBlock(writebacks);
 748             dataReferenceCount[blk->data_ptr[i]] += 1;
 749         }
 750     } else if (num_subs < blk->numData){
 751         // can free data blocks
 752         for (int i=num_subs; i < blk->numData; ++i){
 753             // decrement reference count and compare to zero
 754             /**
 755              * @todo
 756              * Make this work with copying.
 757              */
 758             if (--dataReferenceCount[blk->data_ptr[i]] == 0) {
 759                 freeDataBlock(blk->data_ptr[i]);
 760             }
 761         }
 762     }
 763
 764     blk->numData = num_subs;
 765     blk->size = size;
 766     assert(size <= trivialSize || blk->numData > 0);
 767     if (size > trivialSize){
 768         for (int i = 0; i < blk->numData; ++i){
 769             memcpy(&dataBlks[blk->data_ptr[i]][0], write_data + i*subSize,
 770                    (size>subSize)?subSize:size);
 771             size -= subSize;
 772         }
 773     } else {
 774         memcpy(blk->trivialData,write_data,size);
 775     }
 776 }
 777
 778
 779 /**
 780  * @todo This code can break if the src is evicted to get a tag for the dest.
 781  */
 782 void
 783 IIC::doCopy(Addr source, Addr dest, int asid, PacketList &writebacks)
 784 {
 785 //Copy unsuported now
 786 #if 0
 787     IICTag *dest_tag = findBlock(dest, asid);
 788
 789     if (dest_tag) {
 790         for (int i = 0; i < dest_tag->numData; ++i) {
 791             if (--dataReferenceCount[dest_tag->data_ptr[i]] == 0) {
 792                 freeDataBlock(dest_tag->data_ptr[i]);
 793             }
 794         }
 795         // Reset replacement entry
 796     } else {
 797         dest_tag = getFreeTag(hash(dest), writebacks);
 798         dest_tag->re = (void*) repl->add(dest_tag - tagStore);
 799         dest_tag->set = hash(dest);
 800         dest_tag->tag = extractTag(dest);
 801         dest_tag->asid = asid;
 802         dest_tag->status = BlkValid | BlkWritable;
 803     }
 804     // Find the source tag here since it might move if we need to find a
 805     // tag for the destination.
 806     IICTag *src_tag = findBlock(source, asid);
 807     assert(src_tag);
 808     assert(!cache->doData() || src_tag->size <= trivialSize
 809            || src_tag->numData > 0);
 810     // point dest to source data and inc counter
 811     for (int i = 0; i < src_tag->numData; ++i) {
 812         dest_tag->data_ptr[i] = src_tag->data_ptr[i];
 813         ++dataReferenceCount[dest_tag->data_ptr[i]];
 814     }
 815
 816     // Maintain fast access data.
 817     memcpy(dest_tag->data, src_tag->data, blkSize);
 818
 819     dest_tag->xc = src_tag->xc;
 820     dest_tag->size = src_tag->size;
 821     dest_tag->numData = src_tag->numData;
 822     if (src_tag->numData == 0) {
 823         // Data is stored in the trivial data, just copy it.
 824         memcpy(dest_tag->trivialData, src_tag->trivialData, src_tag->size);
 825     }
 826
 827     dest_tag->status |= BlkDirty;
 828     if (dest_tag->size < blkSize) {
 829         dest_tag->status |= BlkCompressed;
 830     } else {
 831         dest_tag->status &= ~BlkCompressed;
 832     }
 833 #endif
 834 }
 835
 836 void
 837 IIC::fixCopy(Packet * &pkt, PacketList &writebacks)
 838 {
 839 #if 0
 840     // if reference counter is greater than 1, do copy
 841     // else do write
 842     Addr blk_addr = blkAlign(pkt->getAddr);
 843     IICTag* blk = findBlock(blk_addr, pkt->req->getAsid());
 844
 845     if (blk->numData > 0 && dataReferenceCount[blk->data_ptr[0]] != 1) {
 846         // copy the data
 847         // Mark the block as referenced so it doesn't get replaced.
 848         blk->status |= BlkReferenced;
 849         for (int i = 0; i < blk->numData; ++i){
 850             unsigned long new_data = getFreeDataBlock(writebacks);
 851             // Need to refresh pointer
 852             /**
 853              * @todo Remove this refetch once we change IIC to pointer based
 854              */
 855             blk = findBlock(blk_addr, pkt->req->getAsid());
 856             assert(blk);
 857             if (cache->doData()) {
 858                 memcpy(&(dataBlks[new_data][0]),
 859                        &(dataBlks[blk->data_ptr[i]][0]),
 860                        subSize);
 861             }
 862             dataReferenceCount[blk->data_ptr[i]]--;
 863             dataReferenceCount[new_data]++;
 864             blk->data_ptr[i] = new_data;
 865         }
 866     }
 867 #endif
 868 }
 869
 870 void
 871 IIC::cleanupRefs()
 872 {
 873     for (int i = 0; i < numTags; ++i) {
 874         if (tagStore[i].isValid()) {
 875             totalRefs += tagStore[i].refCount;
 876             ++sampledRefs;
 877         }
 878     }
 879 }