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
 288 IICTag*
 289 IIC::findBlock(Addr addr) const
 290 {
 291     Addr tag = extractTag(addr);
 292     unsigned set = hash(addr);
 293
 294     unsigned long chain_ptr;
 295
 296     IICTag *tag_ptr = sets[set].findTag(tag, chain_ptr);
 297     if (tag_ptr == NULL && chain_ptr != tagNull) {
 298         int secondary_depth;
 299         tag_ptr = secondaryChain(tag, chain_ptr, &secondary_depth);
 300     }
 301     return tag_ptr;
 302 }
 303
 304
 305 IICTag*
 306 IIC::findReplacement(PacketPtr &pkt, PacketList &writebacks,
 307                      BlkList &compress_blocks)
 308 {
 309     DPRINTF(IIC, "Finding Replacement for %x\n", pkt->getAddr());
 310     unsigned set = hash(pkt->getAddr());
 311     IICTag *tag_ptr;
 312     unsigned long *tmp_data = new unsigned long[numSub];
 313
 314     // Get a enough subblocks for a full cache line
 315     for (int i = 0; i < numSub; ++i){
 316         tmp_data[i] = getFreeDataBlock(writebacks);
 317         assert(dataReferenceCount[tmp_data[i]]==0);
 318     }
 319
 320     tag_ptr = getFreeTag(set, writebacks);
 321
 322     tag_ptr->set = set;
 323     for (int i=0; i< numSub; ++i) {
 324         tag_ptr->data_ptr[i] = tmp_data[i];
 325         dataReferenceCount[tag_ptr->data_ptr[i]]++;
 326     }
 327     tag_ptr->numData = numSub;
 328     assert(tag_ptr - tagStore < primaryBound); // make sure it is in primary
 329     tag_ptr->chain_ptr = tagNull;
 330     sets[set].moveToHead(tag_ptr);
 331     delete [] tmp_data;
 332
 333     list<unsigned long> tag_indexes;
 334     repl->doAdvance(tag_indexes);
 335     while (!tag_indexes.empty()) {
 336         if (!tagStore[tag_indexes.front()].isCompressed()) {
 337             compress_blocks.push_back(&tagStore[tag_indexes.front()]);
 338         }
 339         tag_indexes.pop_front();
 340     }
 341
 342     tag_ptr->re = (void*)repl->add(tag_ptr-tagStore);
 343
 344     return tag_ptr;
 345 }
 346
 347 void
 348 IIC::freeReplacementBlock(PacketList & writebacks)
 349 {
 350     IICTag *tag_ptr;
 351     unsigned long data_ptr;
 352     /* consult replacement policy */
 353     tag_ptr = &tagStore[repl->getRepl()];
 354     assert(tag_ptr->isValid());
 355
 356     DPRINTF(Cache, "Replacing %x in IIC: %s\n",
 357             regenerateBlkAddr(tag_ptr->tag,0),
 358             tag_ptr->isModified() ? "writeback" : "clean");
 359     /* write back replaced block data */
 360     if (tag_ptr && (tag_ptr->isValid())) {
 361         replacements[0]++;
 362         totalRefs += tag_ptr->refCount;
 363         ++sampledRefs;
 364         tag_ptr->refCount = 0;
 365
 366         if (tag_ptr->isModified()) {
 367 /*          PacketPtr writeback =
 368                 buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0),
 369                                   tag_ptr->req->asid, tag_ptr->xc, blkSize,
 370                                   tag_ptr->data,
 371                                   tag_ptr->size);
 372 */
 373             Request *writebackReq = new Request(regenerateBlkAddr(tag_ptr->tag, 0),
 374                                            blkSize, 0);
 375             PacketPtr writeback = new Packet(writebackReq, Packet::Writeback, -1);
 376             writeback->allocate();
 377             memcpy(writeback->getPtr<uint8_t>(), tag_ptr->data, blkSize);
 378
 379             writebacks.push_back(writeback);
 380         }
 381     }
 382
 383     // free the data blocks
 384     for (int i = 0; i < tag_ptr->numData; ++i) {
 385         data_ptr = tag_ptr->data_ptr[i];
 386         assert(dataReferenceCount[data_ptr]>0);
 387         if (--dataReferenceCount[data_ptr] == 0) {
 388             freeDataBlock(data_ptr);
 389         }
 390     }
 391     freeTag(tag_ptr);
 392 }
 393
 394 unsigned long
 395 IIC::getFreeDataBlock(PacketList & writebacks)
 396 {
 397     struct IICTag *tag_ptr;
 398     unsigned long data_ptr;
 399
 400     tag_ptr = NULL;
 401     /* find data block */
 402     while (blkFreelist.empty()) {
 403         freeReplacementBlock(writebacks);
 404     }
 405
 406     data_ptr = blkFreelist.front();
 407     blkFreelist.pop_front();
 408     DPRINTF(IICMore,"Found free data at %d\n",data_ptr);
 409     return data_ptr;
 410 }
 411
 412
 413
 414 IICTag*
 415 IIC::getFreeTag(int set, PacketList & writebacks)
 416 {
 417     unsigned long tag_index;
 418     IICTag *tag_ptr;
 419     // Add new tag
 420     tag_ptr = sets[set].findFree();
 421     // if no free in primary, and secondary exists
 422     if (!tag_ptr && numSecondary) {
 423         // need to spill a tag into secondary storage
 424         while (freelist == tagNull) {
 425             // get replacements until one is in secondary
 426             freeReplacementBlock(writebacks);
 427         }
 428
 429         tag_index = freelist;
 430         freelist = tagStore[freelist].chain_ptr;
 431         freeSecond--;
 432
 433         assert(tag_index != tagNull);
 434         tagSwap(tag_index, sets[set].tags[assoc-1] - tagStore);
 435         tagStore[tag_index].chain_ptr = sets[set].chain_ptr;
 436         sets[set].chain_ptr = tag_index;
 437
 438         tag_ptr = sets[set].tags[assoc-1];
 439     }
 440     DPRINTF(IICMore,"Found free tag at %d\n",tag_ptr - tagStore);
 441     tagsInUse++;
 442     if (!warmedUp && tagsInUse.value() >= warmupBound) {
 443         warmedUp = true;
 444         warmupCycle = curTick;
 445     }
 446
 447     return tag_ptr;
 448 }
 449
 450 void
 451 IIC::freeTag(IICTag *tag_ptr)
 452 {
 453     unsigned long tag_index, tmp_index;
 454     // Fix tag_ptr
 455     if (tag_ptr) {
 456         // we have a tag to clear
 457         DPRINTF(IICMore,"Freeing Tag for %x\n",
 458                 regenerateBlkAddr(tag_ptr->tag,0));
 459         tagsInUse--;
 460         tag_ptr->status = 0;
 461         tag_ptr->numData = 0;
 462         tag_ptr->re = NULL;
 463         tag_index = tag_ptr - tagStore;
 464         if (tag_index >= primaryBound) {
 465             // tag_ptr points to secondary store
 466             assert(tag_index < tagNull); // remove this?? egh
 467             if (tag_ptr->chain_ptr == tagNull) {
 468                 // need to fix chain list
 469                 unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 470                 if (sets[tmp_set].chain_ptr == tag_index) {
 471                     sets[tmp_set].chain_ptr = tagNull;
 472                 } else {
 473                     tmp_index = sets[tmp_set].chain_ptr;
 474                     while (tmp_index != tagNull
 475                            && tagStore[tmp_index].chain_ptr != tag_index) {
 476                         tmp_index = tagStore[tmp_index].chain_ptr;
 477                     }
 478                     assert(tmp_index != tagNull);
 479                     tagStore[tmp_index].chain_ptr = tagNull;
 480                 }
 481                 tag_ptr->chain_ptr = freelist;
 482                 freelist = tag_index;
 483                 freeSecond++;
 484             } else {
 485                 // copy next chained entry to this tag location
 486                 tmp_index = tag_ptr->chain_ptr;
 487                 tagSwap(tmp_index, tag_index);
 488                 tagStore[tmp_index].chain_ptr = freelist;
 489                 freelist = tmp_index;
 490                 freeSecond++;
 491             }
 492         } else {
 493             // tag_ptr in primary hash table
 494             assert(tag_index < primaryBound);
 495             tag_ptr->status = 0;
 496             unsigned tmp_set = hash(tag_ptr->tag << tagShift);
 497             if (sets[tmp_set].chain_ptr != tagNull) { // collapse chain
 498                 tmp_index = sets[tmp_set].chain_ptr;
 499                 tagSwap(tag_index, tmp_index);
 500                 tagStore[tmp_index].chain_ptr = freelist;
 501                 freelist = tmp_index;
 502                 freeSecond++;
 503                 sets[tmp_set].chain_ptr = tag_ptr->chain_ptr;
 504                 sets[tmp_set].moveToTail(tag_ptr);
 505             }
 506         }
 507     }
 508 }
 509
 510 void
 511 IIC::freeDataBlock(unsigned long data_ptr)
 512 {
 513     assert(dataReferenceCount[data_ptr] == 0);
 514     DPRINTF(IICMore, "Freeing data at %d\n", data_ptr);
 515     blkFreelist.push_front(data_ptr);
 516 }
 517
 518 /** Use a simple modulo hash. */
 519 #define SIMPLE_HASH 0
 520
 521 unsigned
 522 IIC::hash(Addr addr) const {
 523 #if SIMPLE_HASH
 524     return extractTag(addr) % iic_hash_size;
 525 #else
 526     Addr tag, mask, x, y;
 527     tag = extractTag(addr);
 528     mask = hashSets-1; /* assumes iic_hash_size is a power of 2 */
 529     x = tag & mask;
 530     y = (tag >> (int)(::log(hashSets)/::log(2))) & mask;
 531     assert (x < hashSets && y < hashSets);
 532     return x ^ y;
 533 #endif
 534 }
 535
 536
 537 void
 538 IICSet::moveToHead(IICTag *tag)
 539 {
 540     if (tags[0] == tag)
 541         return;
 542
 543     // write 'next' block into blks[i], moving up from MRU toward LRU
 544     // until we overwrite the block we moved to head.
 545
 546     // start by setting up to write 'blk' into blks[0]
 547     int i = 0;
 548     IICTag *next = tag;
 549
 550     do {
 551         assert(i < assoc);
 552         // swap blks[i] and next
 553         IICTag *tmp = tags[i];
 554         tags[i] = next;
 555         next = tmp;
 556         ++i;
 557     } while (next != tag);
 558 }
 559
 560 void
 561 IICSet::moveToTail(IICTag *tag)
 562 {
 563     if (tags[assoc-1] == tag)
 564         return;
 565
 566     // write 'next' block into blks[i], moving up from MRU toward LRU
 567     // until we overwrite the block we moved to head.
 568
 569     // start by setting up to write 'blk' into blks[0]
 570     int i = assoc - 1;
 571     IICTag *next = tag;
 572
 573     do {
 574         assert(i >= 0);
 575         // swap blks[i] and next
 576         IICTag *tmp = tags[i];
 577         tags[i] = next;
 578         next = tmp;
 579         --i;
 580     } while (next != tag);
 581 }
 582
 583 void
 584 IIC::tagSwap(unsigned long index1, unsigned long index2)
 585 {
 586     DPRINTF(IIC,"Swapping tag[%d]=%x for tag[%d]=%x\n",index1,
 587             tagStore[index1].tag<<tagShift, index2,
 588             tagStore[index2].tag<<tagShift);
 589     IICTag tmp_tag;
 590     tmp_tag = tagStore[index1];
 591     tagStore[index1] = tagStore[index2];
 592     tagStore[index2] = tmp_tag;
 593     if (tagStore[index1].isValid())
 594         repl->fixTag(tagStore[index1].re, index2, index1);
 595     if (tagStore[index2].isValid())
 596         repl->fixTag(tagStore[index2].re, index1, index2);
 597 }
 598
 599
 600 IICTag *
 601 IIC::secondaryChain(Addr tag, unsigned long chain_ptr,
 602                     int *_depth) const
 603 {
 604     int depth = 0;
 605     while (chain_ptr != tagNull) {
 606         DPRINTF(IIC,"Searching secondary at %d for %x\n", chain_ptr,
 607                 tag<<tagShift);
 608         if (tagStore[chain_ptr].tag == tag &&
 609             (tagStore[chain_ptr].isValid())) {
 610             *_depth = depth;
 611             return &tagStore[chain_ptr];
 612         }
 613         depth++;
 614         chain_ptr = tagStore[chain_ptr].chain_ptr;
 615     }
 616     *_depth = depth;
 617     return NULL;
 618 }
 619
 620 void
 621 IIC::decompressBlock(unsigned long index)
 622 {
 623     IICTag *tag_ptr = &tagStore[index];
 624     if (tag_ptr->isCompressed()) {
 625         // decompress the data here.
 626     }
 627 }
 628
 629 void
 630 IIC::compressBlock(unsigned long index)
 631 {
 632     IICTag *tag_ptr = &tagStore[index];
 633     if (!tag_ptr->isCompressed()) {
 634         // Compress the data here.
 635     }
 636 }
 637
 638 void
 639 IIC::invalidateBlk(IIC::BlkType *tag_ptr)
 640 {
 641     if (tag_ptr) {
 642         for (int i = 0; i < tag_ptr->numData; ++i) {
 643             dataReferenceCount[tag_ptr->data_ptr[i]]--;
 644             if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) {
 645                 freeDataBlock(tag_ptr->data_ptr[i]);
 646             }
 647         }
 648         repl->removeEntry(tag_ptr->re);
 649         freeTag(tag_ptr);
 650     }
 651 }
 652
 653 void
 654 IIC::readData(IICTag *blk, uint8_t *data)
 655 {
 656     assert(blk->size <= trivialSize || blk->numData > 0);
 657     int data_size = blk->size;
 658     if (data_size > trivialSize) {
 659         for (int i = 0; i < blk->numData; ++i){
 660             memcpy(data+i*subSize,
 661                    &(dataBlks[blk->data_ptr[i]][0]),
 662                    (data_size>subSize)?subSize:data_size);
 663             data_size -= subSize;
 664         }
 665     } else {
 666         memcpy(data,blk->trivialData,data_size);
 667     }
 668 }
 669
 670 void
 671 IIC::writeData(IICTag *blk, uint8_t *write_data, int size,
 672                PacketList & writebacks)
 673 {
 674     assert(size < blkSize || !blk->isCompressed());
 675     DPRINTF(IIC, "Writing %d bytes to %x\n", size,
 676             blk->tag<<tagShift);
 677     // Find the number of subblocks needed, (round up)
 678     int num_subs = (size + (subSize -1))/subSize;
 679     if (size <= trivialSize) {
 680         num_subs = 0;
 681     }
 682     assert(num_subs <= numSub);
 683     if (num_subs > blk->numData) {
 684         // need to allocate more data blocks
 685         for (int i = blk->numData; i < num_subs; ++i){
 686             blk->data_ptr[i] = getFreeDataBlock(writebacks);
 687             dataReferenceCount[blk->data_ptr[i]] += 1;
 688         }
 689     } else if (num_subs < blk->numData){
 690         // can free data blocks
 691         for (int i=num_subs; i < blk->numData; ++i){
 692             // decrement reference count and compare to zero
 693             if (--dataReferenceCount[blk->data_ptr[i]] == 0) {
 694                 freeDataBlock(blk->data_ptr[i]);
 695             }
 696         }
 697     }
 698
 699     blk->numData = num_subs;
 700     blk->size = size;
 701     assert(size <= trivialSize || blk->numData > 0);
 702     if (size > trivialSize){
 703         for (int i = 0; i < blk->numData; ++i){
 704             memcpy(&dataBlks[blk->data_ptr[i]][0], write_data + i*subSize,
 705                    (size>subSize)?subSize:size);
 706             size -= subSize;
 707         }
 708     } else {
 709         memcpy(blk->trivialData,write_data,size);
 710     }
 711 }
 712
 713
 714 void
 715 IIC::cleanupRefs()
 716 {
 717     for (int i = 0; i < numTags; ++i) {
 718         if (tagStore[i].isValid()) {
 719             totalRefs += tagStore[i].refCount;
 720             ++sampledRefs;
 721         }
 722     }
 723 }