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