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(Addr addr) const
 225 {
 226     return (findBlock(addr) != NULL);
 227 }
 228
 229 IICTag*
 230 IIC::findBlock(Addr addr, 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(tag, chain_ptr);
 242     set_lat = 1;
 243     if (tag_ptr == NULL && chain_ptr != tagNull) {
 244         int secondary_depth;
 245         tag_ptr = secondaryChain(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(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
 292     Addr tag = extractTag(addr);
 293     unsigned set = hash(addr);
 294     int set_lat;
 295
 296     unsigned long chain_ptr;
 297
 298     if (PROFILE_IIC)
 299         setAccess.sample(set);
 300
 301     IICTag *tag_ptr = sets[set].findTag(tag, chain_ptr);
 302     set_lat = 1;
 303     if (tag_ptr == NULL && chain_ptr != tagNull) {
 304         int secondary_depth;
 305         tag_ptr = secondaryChain(tag, chain_ptr, &secondary_depth);
 306         set_lat += secondary_depth;
 307         // set depth for statistics fix this later!!! egh
 308         sets[set].depth = set_lat;
 309
 310         if (tag_ptr != NULL) {
 311             /* need to move tag into primary table */
 312             // need to preserve chain: fix this egh
 313             sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr;
 314             tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore);
 315             tag_ptr = sets[set].findTag(tag, chain_ptr);
 316             assert(tag_ptr!=NULL);
 317         }
 318
 319     }
 320     set_lat = set_lat * hashDelay + hitLatency;
 321     if (tag_ptr != NULL) {
 322         // IIC replacement: if this is not the first element of
 323         //   list, reorder
 324         sets[set].moveToHead(tag_ptr);
 325
 326         hitHashDepth.sample(sets[set].depth);
 327         hashHit++;
 328         hitDepthTotal += sets[set].depth;
 329         tag_ptr->status |= BlkReferenced;
 330         lat = set_lat;
 331         if (tag_ptr->whenReady > curTick && tag_ptr->whenReady - curTick > set_lat) {
 332             lat = tag_ptr->whenReady - curTick;
 333         }
 334
 335         tag_ptr->refCount += 1;
 336     }
 337     else {
 338         // fall through: cache block not found, not a hit...
 339         missHashDepth.sample(sets[set].depth);
 340         hashMiss++;
 341         missDepthTotal += sets[set].depth;
 342         lat = set_lat;
 343     }
 344     return tag_ptr;
 345 }
 346
 347 IICTag*
 348 IIC::findBlock(Addr addr) const
 349 {
 350     Addr tag = extractTag(addr);
 351     unsigned set = hash(addr);
 352
 353     unsigned long chain_ptr;
 354
 355     IICTag *tag_ptr = sets[set].findTag(tag, chain_ptr);
 356     if (tag_ptr == NULL && chain_ptr != tagNull) {
 357         int secondary_depth;
 358         tag_ptr = secondaryChain(tag, chain_ptr, &secondary_depth);
 359     }
 360     return tag_ptr;
 361 }
 362
 363
 364 IICTag*
 365 IIC::findReplacement(Packet * &pkt, PacketList &writebacks,
 366                      BlkList &compress_blocks)
 367 {
 368     DPRINTF(IIC, "Finding Replacement for %x\n", pkt->getAddr());
 369     unsigned set = hash(pkt->getAddr());
 370     IICTag *tag_ptr;
 371     unsigned long *tmp_data = new unsigned long[numSub];
 372
 373     // Get a enough subblocks for a full cache line
 374     for (int i = 0; i < numSub; ++i){
 375         tmp_data[i] = getFreeDataBlock(writebacks);
 376         assert(dataReferenceCount[tmp_data[i]]==0);
 377     }
 378
 379     tag_ptr = getFreeTag(set, writebacks);
 380
 381     tag_ptr->set = set;
 382     for (int i=0; i< numSub; ++i) {
 383         tag_ptr->data_ptr[i] = tmp_data[i];
 384         dataReferenceCount[tag_ptr->data_ptr[i]]++;
 385     }
 386     tag_ptr->numData = numSub;
 387     assert(tag_ptr - tagStore < primaryBound); // make sure it is in primary
 388     tag_ptr->chain_ptr = tagNull;
 389     sets[set].moveToHead(tag_ptr);
 390     delete [] tmp_data;
 391
 392     list<unsigned long> tag_indexes;
 393     repl->doAdvance(tag_indexes);
 394     while (!tag_indexes.empty()) {
 395         if (!tagStore[tag_indexes.front()].isCompressed()) {
 396             compress_blocks.push_back(&tagStore[tag_indexes.front()]);
 397         }
 398         tag_indexes.pop_front();
 399     }
 400
 401     tag_ptr->re = (void*)repl->add(tag_ptr-tagStore);
 402
 403     return tag_ptr;
 404 }
 405
 406 void
 407 IIC::freeReplacementBlock(PacketList & writebacks)
 408 {
 409     IICTag *tag_ptr;
 410     unsigned long data_ptr;
 411     /* consult replacement policy */
 412     tag_ptr = &tagStore[repl->getRepl()];
 413     assert(tag_ptr->isValid());
 414
 415     DPRINTF(Cache, "Replacing %x in IIC: %s\n",
 416             regenerateBlkAddr(tag_ptr->tag,0),
 417             tag_ptr->isModified() ? "writeback" : "clean");
 418     /* write back replaced block data */
 419     if (tag_ptr && (tag_ptr->isValid())) {
 420         replacements[0]++;
 421         totalRefs += tag_ptr->refCount;
 422         ++sampledRefs;
 423         tag_ptr->refCount = 0;
 424
 425         if (tag_ptr->isModified()) {
 426 /*          Packet * writeback =
 427                 buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0),
 428                                   tag_ptr->req->asid, tag_ptr->xc, blkSize,
 429                                   tag_ptr->data,
 430                                   tag_ptr->size);
 431 */
 432             Request *writebackReq = new Request(regenerateBlkAddr(tag_ptr->tag, 0),
 433                                            blkSize, 0);
 434             Packet *writeback = new Packet(writebackReq, Packet::Writeback, -1);
 435             writeback->allocate();
 436             memcpy(writeback->getPtr<uint8_t>(), tag_ptr->data, blkSize);
 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(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].isValid())) {
 669             *_depth = depth;
 670             return &tagStore[chain_ptr];
 671         }
 672         depth++;
 673         chain_ptr = tagStore[chain_ptr].chain_ptr;
 674     }
 675     *_depth = depth;
 676     return NULL;
 677 }
 678
 679 void
 680 IIC::decompressBlock(unsigned long index)
 681 {
 682     IICTag *tag_ptr = &tagStore[index];
 683     if (tag_ptr->isCompressed()) {
 684         // decompress the data here.
 685     }
 686 }
 687
 688 void
 689 IIC::compressBlock(unsigned long index)
 690 {
 691     IICTag *tag_ptr = &tagStore[index];
 692     if (!tag_ptr->isCompressed()) {
 693         // Compress the data here.
 694     }
 695 }
 696
 697 void
 698 IIC::invalidateBlk(Addr addr)
 699 {
 700     IICTag* tag_ptr = findBlock(addr);
 701     if (tag_ptr) {
 702         for (int i = 0; i < tag_ptr->numData; ++i) {
 703             dataReferenceCount[tag_ptr->data_ptr[i]]--;
 704             if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) {
 705                 freeDataBlock(tag_ptr->data_ptr[i]);
 706             }
 707         }
 708         repl->removeEntry(tag_ptr->re);
 709         freeTag(tag_ptr);
 710     }
 711 }
 712
 713 void
 714 IIC::readData(IICTag *blk, uint8_t *data)
 715 {
 716     assert(blk->size <= trivialSize || blk->numData > 0);
 717     int data_size = blk->size;
 718     if (data_size > trivialSize) {
 719         for (int i = 0; i < blk->numData; ++i){
 720             memcpy(data+i*subSize,
 721                    &(dataBlks[blk->data_ptr[i]][0]),
 722                    (data_size>subSize)?subSize:data_size);
 723             data_size -= subSize;
 724         }
 725     } else {
 726         memcpy(data,blk->trivialData,data_size);
 727     }
 728 }
 729
 730 void
 731 IIC::writeData(IICTag *blk, uint8_t *write_data, int size,
 732                PacketList & writebacks)
 733 {
 734     assert(size < blkSize || !blk->isCompressed());
 735     DPRINTF(IIC, "Writing %d bytes to %x\n", size,
 736             blk->tag<<tagShift);
 737     // Find the number of subblocks needed, (round up)
 738     int num_subs = (size + (subSize -1))/subSize;
 739     if (size <= trivialSize) {
 740         num_subs = 0;
 741     }
 742     assert(num_subs <= numSub);
 743     if (num_subs > blk->numData) {
 744         // need to allocate more data blocks
 745         for (int i = blk->numData; i < num_subs; ++i){
 746             blk->data_ptr[i] = getFreeDataBlock(writebacks);
 747             dataReferenceCount[blk->data_ptr[i]] += 1;
 748         }
 749     } else if (num_subs < blk->numData){
 750         // can free data blocks
 751         for (int i=num_subs; i < blk->numData; ++i){
 752             // decrement reference count and compare to zero
 753             if (--dataReferenceCount[blk->data_ptr[i]] == 0) {
 754                 freeDataBlock(blk->data_ptr[i]);
 755             }
 756         }
 757     }
 758
 759     blk->numData = num_subs;
 760     blk->size = size;
 761     assert(size <= trivialSize || blk->numData > 0);
 762     if (size > trivialSize){
 763         for (int i = 0; i < blk->numData; ++i){
 764             memcpy(&dataBlks[blk->data_ptr[i]][0], write_data + i*subSize,
 765                    (size>subSize)?subSize:size);
 766             size -= subSize;
 767         }
 768     } else {
 769         memcpy(blk->trivialData,write_data,size);
 770     }
 771 }
 772
 773
 774 void
 775 IIC::cleanupRefs()
 776 {
 777     for (int i = 0; i < numTags; ++i) {
 778         if (tagStore[i].isValid()) {
 779             totalRefs += tagStore[i].refCount;
 780             ++sampledRefs;
 781         }
 782     }
 783 }