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->allocate();
 437             memcpy(writeback->getPtr<uint8_t>(), tag_ptr->data, blkSize);
 438
 439             writebacks.push_back(writeback);
 440         }
 441     }
 442
 443     // free the data blocks
 444     for (int i = 0; i < tag_ptr->numData; ++i) {
 445         data_ptr = tag_ptr->data_ptr[i];
 446         assert(dataReferenceCount[data_ptr]>0);
 447         if (--dataReferenceCount[data_ptr] == 0) {
 448             freeDataBlock(data_ptr);
 449         }
 450     }
 451     freeTag(tag_ptr);
 452 }
 453
 454 unsigned long
 455 IIC::getFreeDataBlock(PacketList & writebacks)
 456 {
 457     struct IICTag *tag_ptr;
 458     unsigned long data_ptr;
 459
 460     tag_ptr = NULL;
 461     /* find data block */
 462     while (blkFreelist.empty()) {
 463         freeReplacementBlock(writebacks);
 464     }
 465
 466     data_ptr = blkFreelist.front();
 467     blkFreelist.pop_front();
 468     DPRINTF(IICMore,"Found free data at %d\n",data_ptr);
 469     return data_ptr;
 470 }
 471
 472
 473
 474 IICTag*
 475 IIC::getFreeTag(int set, PacketList & writebacks)
 476 {
 477     unsigned long tag_index;
 478     IICTag *tag_ptr;
 479     // Add new tag
 480     tag_ptr = sets[set].findFree();
 481     // if no free in primary, and secondary exists
 482     if (!tag_ptr && numSecondary) {
 483         // need to spill a tag into secondary storage
 484         while (freelist == tagNull) {
 485             // get replacements until one is in secondary
 486             freeReplacementBlock(writebacks);
 487         }
 488
 489         tag_index = freelist;
 490         freelist = tagStore[freelist].chain_ptr;
 491         freeSecond--;
 492
 493         assert(tag_index != tagNull);
 494         tagSwap(tag_index, sets[set].tags[assoc-1] - tagStore);
 495         tagStore[tag_index].chain_ptr = sets[set].chain_ptr;
 496         sets[set].chain_ptr = tag_index;
 497
 498         tag_ptr = sets[set].tags[assoc-1];
 499     }
 500     DPRINTF(IICMore,"Found free tag at %d\n",tag_ptr - tagStore);
 501     tagsInUse++;
 502     if (!warmedUp && tagsInUse.value() >= warmupBound) {
 503         warmedUp = true;
 504         warmupCycle = curTick;
 505     }
 506
 507     return tag_ptr;
 508 }
 509
 510 void
 511 IIC::freeTag(IICTag *tag_ptr)
 512 {
 513     unsigned long tag_index, tmp_index;
 514     // Fix tag_ptr
 515     if (tag_ptr) {
 516         // we have a tag to clear
 517         DPRINTF(IICMore,"Freeing Tag for %x\n",
 518                 regenerateBlkAddr(tag_ptr->tag,0));
 519         tagsInUse--;
 520         tag_ptr->status = 0;
 521         tag_ptr->numData = 0;
 522         tag_ptr->re = NULL;
 523         tag_index = tag_ptr - tagStore;
 524         if (tag_index >= primaryBound) {
 525             // tag_ptr points to secondary store
 526             assert(tag_index < tagNull); // remove this?? egh
 527             if (tag_ptr->chain_ptr == tagNull) {
 528                 // need to fix chain list
 529                 unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 530                 if (sets[tmp_set].chain_ptr == tag_index) {
 531                     sets[tmp_set].chain_ptr = tagNull;
 532                 } else {
 533                     tmp_index = sets[tmp_set].chain_ptr;
 534                     while (tmp_index != tagNull
 535                            && tagStore[tmp_index].chain_ptr != tag_index) {
 536                         tmp_index = tagStore[tmp_index].chain_ptr;
 537                     }
 538                     assert(tmp_index != tagNull);
 539                     tagStore[tmp_index].chain_ptr = tagNull;
 540                 }
 541                 tag_ptr->chain_ptr = freelist;
 542                 freelist = tag_index;
 543                 freeSecond++;
 544             } else {
 545                 // copy next chained entry to this tag location
 546                 tmp_index = tag_ptr->chain_ptr;
 547                 tagSwap(tmp_index, tag_index);
 548                 tagStore[tmp_index].chain_ptr = freelist;
 549                 freelist = tmp_index;
 550                 freeSecond++;
 551             }
 552         } else {
 553             // tag_ptr in primary hash table
 554             assert(tag_index < primaryBound);
 555             tag_ptr->status = 0;
 556             unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 557             if (sets[tmp_set].chain_ptr != tagNull) { // collapse chain
 558                 tmp_index = sets[tmp_set].chain_ptr;
 559                 tagSwap(tag_index, tmp_index);
 560                 tagStore[tmp_index].chain_ptr = freelist;
 561                 freelist = tmp_index;
 562                 freeSecond++;
 563                 sets[tmp_set].chain_ptr = tag_ptr->chain_ptr;
 564                 sets[tmp_set].moveToTail(tag_ptr);
 565             }
 566         }
 567     }
 568 }
 569
 570 void
 571 IIC::freeDataBlock(unsigned long data_ptr)
 572 {
 573     assert(dataReferenceCount[data_ptr] == 0);
 574     DPRINTF(IICMore, "Freeing data at %d\n", data_ptr);
 575     blkFreelist.push_front(data_ptr);
 576 }
 577
 578 /** Use a simple modulo hash. */
 579 #define SIMPLE_HASH 0
 580
 581 unsigned
 582 IIC::hash(Addr addr) const {
 583 #if SIMPLE_HASH
 584     return extractTag(addr) % iic_hash_size;
 585 #else
 586     Addr tag, mask, x, y;
 587     tag = extractTag(addr);
 588     mask = hashSets-1; /* assumes iic_hash_size is a power of 2 */
 589     x = tag & mask;
 590     y = (tag >> (int)(::log(hashSets)/::log(2))) & mask;
 591     assert (x < hashSets && y < hashSets);
 592     return x ^ y;
 593 #endif
 594 }
 595
 596
 597 void
 598 IICSet::moveToHead(IICTag *tag)
 599 {
 600     if (tags[0] == tag)
 601         return;
 602
 603     // write 'next' block into blks[i], moving up from MRU toward LRU
 604     // until we overwrite the block we moved to head.
 605
 606     // start by setting up to write 'blk' into blks[0]
 607     int i = 0;
 608     IICTag *next = tag;
 609
 610     do {
 611         assert(i < assoc);
 612         // swap blks[i] and next
 613         IICTag *tmp = tags[i];
 614         tags[i] = next;
 615         next = tmp;
 616         ++i;
 617     } while (next != tag);
 618 }
 619
 620 void
 621 IICSet::moveToTail(IICTag *tag)
 622 {
 623     if (tags[assoc-1] == tag)
 624         return;
 625
 626     // write 'next' block into blks[i], moving up from MRU toward LRU
 627     // until we overwrite the block we moved to head.
 628
 629     // start by setting up to write 'blk' into blks[0]
 630     int i = assoc - 1;
 631     IICTag *next = tag;
 632
 633     do {
 634         assert(i >= 0);
 635         // swap blks[i] and next
 636         IICTag *tmp = tags[i];
 637         tags[i] = next;
 638         next = tmp;
 639         --i;
 640     } while (next != tag);
 641 }
 642
 643 void
 644 IIC::tagSwap(unsigned long index1, unsigned long index2)
 645 {
 646     DPRINTF(IIC,"Swapping tag[%d]=%x for tag[%d]=%x\n",index1,
 647             tagStore[index1].tag<<tagShift, index2,
 648             tagStore[index2].tag<<tagShift);
 649     IICTag tmp_tag;
 650     tmp_tag = tagStore[index1];
 651     tagStore[index1] = tagStore[index2];
 652     tagStore[index2] = tmp_tag;
 653     if (tagStore[index1].isValid())
 654         repl->fixTag(tagStore[index1].re, index2, index1);
 655     if (tagStore[index2].isValid())
 656         repl->fixTag(tagStore[index2].re, index1, index2);
 657 }
 658
 659
 660 IICTag *
 661 IIC::secondaryChain(int asid, Addr tag, unsigned long chain_ptr,
 662                     int *_depth) const
 663 {
 664     int depth = 0;
 665     while (chain_ptr != tagNull) {
 666         DPRINTF(IIC,"Searching secondary at %d for %x\n", chain_ptr,
 667                 tag<<tagShift);
 668         if (tagStore[chain_ptr].tag == tag &&
 669             tagStore[chain_ptr].asid == asid &&
 670             (tagStore[chain_ptr].isValid())) {
 671             *_depth = depth;
 672             return &tagStore[chain_ptr];
 673         }
 674         depth++;
 675         chain_ptr = tagStore[chain_ptr].chain_ptr;
 676     }
 677     *_depth = depth;
 678     return NULL;
 679 }
 680
 681 void
 682 IIC::decompressBlock(unsigned long index)
 683 {
 684     IICTag *tag_ptr = &tagStore[index];
 685     if (tag_ptr->isCompressed()) {
 686         // decompress the data here.
 687     }
 688 }
 689
 690 void
 691 IIC::compressBlock(unsigned long index)
 692 {
 693     IICTag *tag_ptr = &tagStore[index];
 694     if (!tag_ptr->isCompressed()) {
 695         // Compress the data here.
 696     }
 697 }
 698
 699 void
 700 IIC::invalidateBlk(int asid, Addr addr)
 701 {
 702     IICTag* tag_ptr = findBlock(addr, asid);
 703     if (tag_ptr) {
 704         for (int i = 0; i < tag_ptr->numData; ++i) {
 705             dataReferenceCount[tag_ptr->data_ptr[i]]--;
 706             if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) {
 707                 freeDataBlock(tag_ptr->data_ptr[i]);
 708             }
 709         }
 710         repl->removeEntry(tag_ptr->re);
 711         freeTag(tag_ptr);
 712     }
 713 }
 714
 715 void
 716 IIC::readData(IICTag *blk, uint8_t *data){
 717 //    assert(cache->doData());
 718     assert(blk->size <= trivialSize || blk->numData > 0);
 719     int data_size = blk->size;
 720     if (data_size > trivialSize) {
 721         for (int i = 0; i < blk->numData; ++i){
 722             memcpy(data+i*subSize,
 723                    &(dataBlks[blk->data_ptr[i]][0]),
 724                    (data_size>subSize)?subSize:data_size);
 725             data_size -= subSize;
 726         }
 727     } else {
 728         memcpy(data,blk->trivialData,data_size);
 729     }
 730 }
 731
 732 void
 733 IIC::writeData(IICTag *blk, uint8_t *write_data, int size,
 734                PacketList & writebacks){
 735 //    assert(cache->doData());
 736     assert(size < blkSize || !blk->isCompressed());
 737     DPRINTF(IIC, "Writing %d bytes to %x\n", size,
 738             blk->tag<<tagShift);
 739     // Find the number of subblocks needed, (round up)
 740     int num_subs = (size + (subSize -1))/subSize;
 741     if (size <= trivialSize) {
 742         num_subs = 0;
 743     }
 744     assert(num_subs <= numSub);
 745     if (num_subs > blk->numData) {
 746         // need to allocate more data blocks
 747         for (int i = blk->numData; i < num_subs; ++i){
 748             blk->data_ptr[i] = getFreeDataBlock(writebacks);
 749             dataReferenceCount[blk->data_ptr[i]] += 1;
 750         }
 751     } else if (num_subs < blk->numData){
 752         // can free data blocks
 753         for (int i=num_subs; i < blk->numData; ++i){
 754             // decrement reference count and compare to zero
 755             /**
 756              * @todo
 757              * Make this work with copying.
 758              */
 759             if (--dataReferenceCount[blk->data_ptr[i]] == 0) {
 760                 freeDataBlock(blk->data_ptr[i]);
 761             }
 762         }
 763     }
 764
 765     blk->numData = num_subs;
 766     blk->size = size;
 767     assert(size <= trivialSize || blk->numData > 0);
 768     if (size > trivialSize){
 769         for (int i = 0; i < blk->numData; ++i){
 770             memcpy(&dataBlks[blk->data_ptr[i]][0], write_data + i*subSize,
 771                    (size>subSize)?subSize:size);
 772             size -= subSize;
 773         }
 774     } else {
 775         memcpy(blk->trivialData,write_data,size);
 776     }
 777 }
 778
 779
 780 /**
 781  * @todo This code can break if the src is evicted to get a tag for the dest.
 782  */
 783 void
 784 IIC::doCopy(Addr source, Addr dest, int asid, PacketList &writebacks)
 785 {
 786 //Copy unsuported now
 787 #if 0
 788     IICTag *dest_tag = findBlock(dest, asid);
 789
 790     if (dest_tag) {
 791         for (int i = 0; i < dest_tag->numData; ++i) {
 792             if (--dataReferenceCount[dest_tag->data_ptr[i]] == 0) {
 793                 freeDataBlock(dest_tag->data_ptr[i]);
 794             }
 795         }
 796         // Reset replacement entry
 797     } else {
 798         dest_tag = getFreeTag(hash(dest), writebacks);
 799         dest_tag->re = (void*) repl->add(dest_tag - tagStore);
 800         dest_tag->set = hash(dest);
 801         dest_tag->tag = extractTag(dest);
 802         dest_tag->asid = asid;
 803         dest_tag->status = BlkValid | BlkWritable;
 804     }
 805     // Find the source tag here since it might move if we need to find a
 806     // tag for the destination.
 807     IICTag *src_tag = findBlock(source, asid);
 808     assert(src_tag);
 809     assert(!cache->doData() || src_tag->size <= trivialSize
 810            || src_tag->numData > 0);
 811     // point dest to source data and inc counter
 812     for (int i = 0; i < src_tag->numData; ++i) {
 813         dest_tag->data_ptr[i] = src_tag->data_ptr[i];
 814         ++dataReferenceCount[dest_tag->data_ptr[i]];
 815     }
 816
 817     // Maintain fast access data.
 818     memcpy(dest_tag->data, src_tag->data, blkSize);
 819
 820     dest_tag->xc = src_tag->xc;
 821     dest_tag->size = src_tag->size;
 822     dest_tag->numData = src_tag->numData;
 823     if (src_tag->numData == 0) {
 824         // Data is stored in the trivial data, just copy it.
 825         memcpy(dest_tag->trivialData, src_tag->trivialData, src_tag->size);
 826     }
 827
 828     dest_tag->status |= BlkDirty;
 829     if (dest_tag->size < blkSize) {
 830         dest_tag->status |= BlkCompressed;
 831     } else {
 832         dest_tag->status &= ~BlkCompressed;
 833     }
 834 #endif
 835 }
 836
 837 void
 838 IIC::fixCopy(Packet * &pkt, PacketList &writebacks)
 839 {
 840 #if 0
 841     // if reference counter is greater than 1, do copy
 842     // else do write
 843     Addr blk_addr = blkAlign(pkt->getAddr);
 844     IICTag* blk = findBlock(blk_addr, pkt->req->getAsid());
 845
 846     if (blk->numData > 0 && dataReferenceCount[blk->data_ptr[0]] != 1) {
 847         // copy the data
 848         // Mark the block as referenced so it doesn't get replaced.
 849         blk->status |= BlkReferenced;
 850         for (int i = 0; i < blk->numData; ++i){
 851             unsigned long new_data = getFreeDataBlock(writebacks);
 852             // Need to refresh pointer
 853             /**
 854              * @todo Remove this refetch once we change IIC to pointer based
 855              */
 856             blk = findBlock(blk_addr, pkt->req->getAsid());
 857             assert(blk);
 858             if (cache->doData()) {
 859                 memcpy(&(dataBlks[new_data][0]),
 860                        &(dataBlks[blk->data_ptr[i]][0]),
 861                        subSize);
 862             }
 863             dataReferenceCount[blk->data_ptr[i]]--;
 864             dataReferenceCount[new_data]++;
 865             blk->data_ptr[i] = new_data;
 866         }
 867     }
 868 #endif
 869 }
 870
 871 void
 872 IIC::cleanupRefs()
 873 {
 874     for (int i = 0; i < numTags; ++i) {
 875         if (tagStore[i].isValid()) {
 876             totalRefs += tagStore[i].refCount;
 877             ++sampledRefs;
 878         }
 879     }
 880 }