/* cache.c - cache module routines */ /* SimpleScalar(TM) Tool Suite * Copyright (C) 1994-2003 by Todd M. Austin, Ph.D. and SimpleScalar, LLC. * All Rights Reserved. * * THIS IS A LEGAL DOCUMENT, BY USING SIMPLESCALAR, * YOU ARE AGREEING TO THESE TERMS AND CONDITIONS. * * No portion of this work may be used by any commercial entity, or for any * commercial purpose, without the prior, written permission of SimpleScalar, * LLC (info@simplescalar.com). Nonprofit and noncommercial use is permitted * as described below. * * 1. SimpleScalar is provided AS IS, with no warranty of any kind, express * or implied. The user of the program accepts full responsibility for the * application of the program and the use of any results. * * 2. Nonprofit and noncommercial use is encouraged. SimpleScalar may be * downloaded, compiled, executed, copied, and modified solely for nonprofit, * educational, noncommercial research, and noncommercial scholarship * purposes provided that this notice in its entirety accompanies all copies. * Copies of the modified software can be delivered to persons who use it * solely for nonprofit, educational, noncommercial research, and * noncommercial scholarship purposes provided that this notice in its * entirety accompanies all copies. * * 3. ALL COMMERCIAL USE, AND ALL USE BY FOR PROFIT ENTITIES, IS EXPRESSLY * PROHIBITED WITHOUT A LICENSE FROM SIMPLESCALAR, LLC (info@simplescalar.com). * * 4. No nonprofit user may place any restrictions on the use of this software, * including as modified by the user, by any other authorized user. * * 5. Noncommercial and nonprofit users may distribute copies of SimpleScalar * in compiled or executable form as set forth in Section 2, provided that * either: (A) it is accompanied by the corresponding machine-readable source * code, or (B) it is accompanied by a written offer, with no time limit, to * give anyone a machine-readable copy of the corresponding source code in * return for reimbursement of the cost of distribution. This written offer * must permit verbatim duplication by anyone, or (C) it is distributed by * someone who received only the executable form, and is accompanied by a * copy of the written offer of source code. * * 6. SimpleScalar was developed by Todd M. Austin, Ph.D. The tool suite is * currently maintained by SimpleScalar LLC (info@simplescalar.com). US Mail: * 2395 Timbercrest Court, Ann Arbor, MI 48105. * * Copyright (C) 1994-2003 by Todd M. Austin, Ph.D. and SimpleScalar, LLC. */ #include #include #include #include #include "host.h" #include "regs.h" #include "misc.h" #include "machine.h" #include "cache.h" /* compute 8-bit PC hash by XOR-ing all 8-bit parts */ #define CBR_HASH_PC8(addr) ((((addr) >> 24) ^ ((addr) >> 16) ^ ((addr) >> 8) ^ (addr)) & 0xFF) /* maximum CBR counter value (= 2^CBR_COUNTER_RESOLUTION - 1) */ #define CBR_COUNTER_MAX ((1 << (CBR_COUNTER_RESOLUTION)) - 1) /* maps 2D prediction table indexing pair (PC, lineAddress) to linear array index */ #define CBR_PRED_TABLE_INDEX(hashed_pc, line_address) (((hashed_pc)*0xFF) + CBR_HASH_PC8(line_address)) /* cache access macros */ #define CACHE_TAG(cp, addr) ((addr) >> (cp)->tag_shift) #define CACHE_SET(cp, addr) (((addr) >> (cp)->set_shift) & (cp)->set_mask) #define CACHE_BLK(cp, addr) ((addr) & (cp)->blk_mask) #define CACHE_TAGSET(cp, addr) ((addr) & (cp)->tagset_mask) /* extract/reconstruct a block address */ #define CACHE_BADDR(cp, addr) ((addr) & ~(cp)->blk_mask) #define CACHE_MK_BADDR(cp, tag, set) \ (((tag) << (cp)->tag_shift)|((set) << (cp)->set_shift)) /* index an array of cache blocks, non-trivial due to variable length blocks (ie. gets (a pointer to) the cache block at index i in block array blks?) */ #define CACHE_BINDEX(cp, blks, i) \ ((struct cache_blk_t *)(((char *)(blks)) + \ (i)*(sizeof(struct cache_blk_t) + \ ((cp)->balloc \ ? (cp)->bsize*sizeof(byte_t) : 0)))) /* cache data block accessor, type parameterized */ #define __CACHE_ACCESS(type, data, bofs) \ (*((type *)(((char *)data) + (bofs)))) /* cache data block accessors, by type */ #define CACHE_DOUBLE(data, bofs) __CACHE_ACCESS(double, data, bofs) #define CACHE_FLOAT(data, bofs) __CACHE_ACCESS(float, data, bofs) #define CACHE_WORD(data, bofs) __CACHE_ACCESS(unsigned int, data, bofs) #define CACHE_HALF(data, bofs) __CACHE_ACCESS(unsigned short, data, bofs) #define CACHE_BYTE(data, bofs) __CACHE_ACCESS(unsigned char, data, bofs) /* cache block hashing macros, this macro is used to index into a cache set hash table (to find the correct block on N in an N-way cache), the cache set index function is CACHE_SET, defined above */ #define CACHE_HASH(cp, key) \ (((key >> 24) ^ (key >> 16) ^ (key >> 8) ^ key) & ((cp)->hsize-1)) /* copy data out of a cache block to buffer indicated by argument pointer p */ #define CACHE_BCOPY(cmd, blk, bofs, p, nbytes) \ if (cmd == Read) \ { \ switch (nbytes) { \ case 1: \ *((byte_t *)p) = CACHE_BYTE(&blk->data[0], bofs); break; \ case 2: \ *((half_t *)p) = CACHE_HALF(&blk->data[0], bofs); break; \ case 4: \ *((word_t *)p) = CACHE_WORD(&blk->data[0], bofs); break; \ default: \ { /* >= 8, power of two, fits in block */ \ int words = nbytes >> 2; \ while (words-- > 0) \ { \ *((word_t *)p) = CACHE_WORD(&blk->data[0], bofs); \ p += 4; bofs += 4; \ }\ }\ }\ }\ else /* cmd == Write */ \ { \ switch (nbytes) { \ case 1: \ CACHE_BYTE(&blk->data[0], bofs) = *((byte_t *)p); break; \ case 2: \ CACHE_HALF(&blk->data[0], bofs) = *((half_t *)p); break; \ case 4: \ CACHE_WORD(&blk->data[0], bofs) = *((word_t *)p); break; \ default: \ { /* >= 8, power of two, fits in block */ \ int words = nbytes >> 2; \ while (words-- > 0) \ { \ CACHE_WORD(&blk->data[0], bofs) = *((word_t *)p); \ p += 4; bofs += 4; \ }\ }\ }\ } /* bound sqword_t/dfloat_t to positive int */ #define BOUND_POS(N) ((int)(MIN(MAX(0, (N)), 2147483647))) /* unlink BLK from the hash table bucket chain in SET */ static void unlink_htab_ent( struct cache_t *cp, /* cache to update */ struct cache_set_t *set, /* set containing bkt chain */ struct cache_blk_t *blk /* block to unlink */ ) { struct cache_blk_t *prev, *ent; int index = CACHE_HASH(cp, blk->tag); /* locate the block in the hash table bucket chain */ for(prev = NULL, ent = set->hash[index]; ent; prev = ent, ent = ent->hash_next) { if(ent == blk) break; } assert(ent); /* unlink the block from the hash table bucket chain */ if(!prev) { /* head of hash bucket list */ set->hash[index] = ent->hash_next; } else { /* middle or end of hash bucket list */ prev->hash_next = ent->hash_next; } ent->hash_next = NULL; } /* insert BLK onto the head of the hash table bucket chain in SET */ static void link_htab_ent(struct cache_t *cp, /* cache to update */ struct cache_set_t *set, /* set containing bkt chain */ struct cache_blk_t *blk) /* block to insert */ { int index = CACHE_HASH(cp, blk->tag); /* insert block onto the head of the bucket chain */ blk->hash_next = set->hash[index]; set->hash[index] = blk; } /* where to insert a block onto the ordered way chain */ enum list_loc_t { Head, Tail }; /* HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT */ /* This should really be done by modifying the calls to cache_access etc and pass the regs as an argument, * but I'm out of time */ static struct regs_t* regs = NULL; void cbr_set_regs(struct regs_t* regs_in){ regs = regs_in; } void cbr_init_pred_table(struct cbr_pred_table_t* pred_table){ int i; for(i = 0; i < CBR_PRED_TABLE_SIZE; i++){ pred_table->entries[i].max_counter = CBR_COUNTER_MAX; pred_table->entries[i].confidence = FALSE; } } struct cbr_pred_table_entry_t* cbr_get_pred_table_element(struct cache_t* cp, byte_t hashedPC, md_addr_t lineAddress){ int index = CBR_PRED_TABLE_INDEX(hashedPC, lineAddress); return &cp->cbr_pred_table->entries[index]; } void cbr_pred_table_set_entry(struct cache_t* cp, byte_t hashedPC, md_addr_t lineAddress, word_t counter, bool_t confidence){ //if(CBR_HASH_PC8(lineAddress) == 0x39) debug("\n\n\n!!! HISTORY(0x%02x, 0x34) = %02d, %d !!!\n\n\n", hashedPC, counter, confidence); int index = CBR_PRED_TABLE_INDEX(hashedPC, lineAddress); cp->cbr_pred_table->entries[index].confidence = confidence; cp->cbr_pred_table->entries[index].max_counter = counter; } /* increments all CBR cache line counters within the provided set */ void aip_increment_set_counters( struct cache_t* cp, /* pointer to cache structure */ struct cache_set_t* set /* pointer to cache set */ // md_addr_t tag /* tag of hit block (used only for high-associative caches) */ ){ struct cache_blk_t* blk = NULL; //int i = 0; /*debug("\nbefore"); for(i = 0, blk = set->way_head; blk; blk = blk->way_next){ debug("block %d: %d", i, blk->cbr_line_info.counter); i++; }*/ // loop over all blocks in set /*for(i=0; i < cp->assoc; i++){ //blk = &set->blks[i]; // current block in set blk = CACHE_BINDEX(cp, set->blks, i); blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX); }*/ for(blk = set->way_head; blk; blk = blk->way_next){ blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX); } /*debug("\nafter"); for(i = 0, blk = set->way_head; blk; blk = blk->way_next){ debug("block %d: %d, confidence %d", i, blk->cbr_line_info.counter, blk->cbr_line_info.confidence); i++; }*/ } /* returns TRUE if the specified cache line is AIP-expired, FALSE otherwise */ bool_t aip_is_line_expired(struct cache_blk_t* blk){ return (blk->cbr_line_info.counter > blk->cbr_line_info.max_counter_present && blk->cbr_line_info.counter > blk->cbr_line_info.max_counter_past && blk->cbr_line_info.confidence); } bool_t lvp_is_line_expired(struct cache_blk_t* blk){ return (blk->cbr_line_info.counter >= blk->cbr_line_info.max_counter_past && blk->cbr_line_info.confidence); } /* returns the position of blk in the set SET relative to the MRU (way_head) position, or -1 if not found */ int cbr_get_way_position(struct cache_t* cp, struct cache_set_t* set, struct cache_blk_t* blk){ struct cache_blk_t* currentBlock = NULL; int i = 0; for(currentBlock = set->way_head; currentBlock; currentBlock = currentBlock->way_next){ if(currentBlock == blk){ return i; } i++; } return -1; } /* finds an AIP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */ struct cache_blk_t* cbr_find_expired_block( struct cache_t* cp, struct cache_set_t* set, bool_t (*is_blk_expired)(struct cache_blk_t* b) ){ struct cache_blk_t* blk = NULL; // generic "current block"-variable int i = 0; /* identify all expired cache lines */ int expiredBlockCount = 0; // amount of AIP-expired block in this cache set struct cache_blk_t** expiredBlocks = calloc(cp->assoc, sizeof(struct cache_blk_t*)); // array of pointers to expired blocks in the set if(!expiredBlocks) fatal("could not allocate temporary expiredBlocks pointer array: out of virtual memory"); for(i = 0; i < cp->assoc; i++){ blk = &set->blks[i]; if(is_blk_expired(blk)){ expiredBlocks[expiredBlockCount] = blk; expiredBlockCount++; } } /* find a replacement cache block: random selection */ if(expiredBlockCount <= 0){ blk = NULL; } else { blk = expiredBlocks[rand() % expiredBlockCount]; } free(expiredBlocks); return blk; } /* finds an AIP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */ struct cache_blk_t* aip_find_expired_block(struct cache_t* cp, struct cache_set_t* set){ return cbr_find_expired_block(cp, set, aip_is_line_expired); } /* finds an LvP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */ struct cache_blk_t* lvp_find_expired_block(struct cache_t* cp, struct cache_set_t* set){ return cbr_find_expired_block(cp, set, lvp_is_line_expired); } /* insert BLK into the order way chain in SET at location WHERE */ static void update_way_list( struct cache_set_t *set, /* set contained way chain */ struct cache_blk_t *blk, /* block to insert */ enum list_loc_t where) /* insert location */ { /* unlink entry from the way list */ if(!blk->way_prev && !blk->way_next) { /* no previous or next block in the set, ie. only one entry in set list => (direct-mapped), no action */ assert(set->way_head == blk && set->way_tail == blk); return; /* Head/Tail order already */ } /* else, more than one element in the list */ else if(!blk->way_prev) { // no previous block and more than one element => current block is first in the set list assert(set->way_head == blk && set->way_tail != blk); if(where == Head) { return; /* already there */ } /* else, unlink */ set->way_head = blk->way_next; blk->way_next->way_prev = NULL; } else if(!blk->way_next) { // no next blocks and more than one element in list => current block is the last in the set list /* end of list (and not front of list) */ assert(set->way_head != blk && set->way_tail == blk); if(where == Tail) { return; /* already there */ } /* unlink */ set->way_tail = blk->way_prev; blk->way_prev->way_next = NULL; } else { /* middle of list (and not front or end of list) */ assert(set->way_head != blk && set->way_tail != blk); /* unlink from list */ blk->way_prev->way_next = blk->way_next; blk->way_next->way_prev = blk->way_prev; } /* link BLK back into the list at the specified position */ if(where == Head) { /* link to the head of the way list */ blk->way_next = set->way_head; blk->way_prev = NULL; set->way_head->way_prev = blk; set->way_head = blk; } else if(where == Tail) { /* link to the tail of the way list */ blk->way_prev = set->way_tail; blk->way_next = NULL; set->way_tail->way_next = blk; set->way_tail = blk; } else { panic("bogus WHERE designator"); } } char* cache_policy_name(enum cache_policy policy){ switch(policy) { case LRU: return "LRU"; case Random: return "Random"; case FIFO: return "FIFO"; default: return (abort(), ""); } } char* cache_cbr_policy_name(enum cache_cbr_policy cbr_policy){ switch(cbr_policy){ case AIP: return "AIP"; case LvP: return "LvP"; case None: return "None"; default: return (abort(), ""); } } /* create and initialize a general cache structure */ struct cache_t * /* pointer to cache created */ cache_create( char *name, /* name of the cache */ int nsets, /* total number of sets in cache */ int bsize, /* block (line) size of cache */ int balloc, /* allocate data space for blocks? */ int usize, /* size of user data to alloc w/blks */ int assoc, /* associativity of cache */ enum cache_policy policy, /* replacement policy w/in sets */ enum cache_cbr_policy cbr_policy, /* CBR replacement policy */ /* block access function, see description w/in struct cache def */ unsigned int (*blk_access_fn)( enum mem_cmd cmd, md_addr_t baddr, int bsize, struct cache_blk_t *blk, tick_t now ), unsigned int hit_latency /* latency in cycles for a hit */ ) { struct cache_t *cp; struct cache_blk_t *blk; int i, j, bindex; /* check all cache parameters */ if(nsets <= 0) fatal("cache size (in sets) `%d' must be non-zero", nsets); if((nsets & (nsets - 1)) != 0) fatal("cache size (in sets) `%d' is not a power of two", nsets); /* blocks must be at least one datum large, i.e., 8 bytes for SS */ if(bsize < 8) fatal("cache block size (in bytes) `%d' must be 8 or greater", bsize); if((bsize & (bsize - 1)) != 0) fatal("cache block size (in bytes) `%d' must be a power of two", bsize); if(usize < 0) fatal("user data size (in bytes) `%d' must be a positive value", usize); if(assoc <= 0) fatal("cache associativity `%d' must be non-zero and positive", assoc); if((assoc & (assoc - 1)) != 0) fatal("cache associativity `%d' must be a power of two", assoc); if(!blk_access_fn) fatal("must specify miss/replacement functions"); /* allocate the cache structure */ /* * NOTE: observe how the cache structure is allocated: first a cache_t struct is allocated * which includes a single tail cache_set_t struct (see definition of cache_t in cache.h). * Immediately after that cache_t structure (and thus immediately after the single cache_set), * an additional (nsets - 1) sets are allocated, thus completing the amount of sets and also * allowing for the sets to be accessed through the tail pointer in cache_t. */ cp = (struct cache_t *) calloc(1, sizeof(struct cache_t) + (nsets - 1) * sizeof(struct cache_set_t)); if(!cp) fatal("out of virtual memory"); /* initialize user parameters */ cp->name = mystrdup(name); cp->nsets = nsets; cp->bsize = bsize; cp->balloc = balloc; cp->usize = usize; cp->assoc = assoc; cp->policy = policy; cp->cbr_policy = cbr_policy; cp->hit_latency = hit_latency; /* allocate CBR prediction table, if required */ if(cp->cbr_policy != None){ debug("Allocating CBR prediction table: %d bytes", sizeof(struct cbr_pred_table_t)); /* allocate prediction table */ cp->cbr_pred_table = (struct cbr_pred_table_t*) calloc(1, sizeof(struct cbr_pred_table_t)); if(!cp->cbr_pred_table) fatal("failed to allocate CBR prediction table"); cbr_init_pred_table(cp->cbr_pred_table); // TODO: create a flag for activating histograms or sth if(strcmp(name, "ul2") == 0){ debug("Allocating CBR replacement stack distance histogram table: %d entries", cp->assoc); cp->cbr_repl_dist_histogram = calloc(cp->assoc, sizeof(counter_t)); if(!cp->cbr_repl_dist_histogram) fatal("failed to allocate CBR replacement stack distance histogram array"); } } // TODO: create a flag for activating histograms or sth if(strcmp(name, "ul2") == 0){ debug("Allocating stack distance histogram table: %d entries", cp->assoc); /* allocate LRU stack distance histogram table */ cp->stack_dist_histogram = calloc(cp->assoc, sizeof(counter_t)); if(!cp->stack_dist_histogram) fatal("failed to allocate stack distance histogram array"); } /* miss/replacement functions */ cp->blk_access_fn = blk_access_fn; /* compute derived parameters */ cp->hsize = CACHE_HIGHLY_ASSOC(cp) ? (assoc >> 2) : 0; cp->blk_mask = bsize - 1; cp->set_shift = log_base2(bsize); cp->set_mask = nsets - 1; cp->tag_shift = cp->set_shift + log_base2(nsets); cp->tag_mask = (1 << (32 - cp->tag_shift)) - 1; cp->tagset_mask = ~cp->blk_mask; cp->bus_free = 0; /* print derived parameters during debug */ debug("%s: cp->hsize = %d", cp->name, cp->hsize); debug("%s: cp->blk_mask = 0x%08x", cp->name, cp->blk_mask); debug("%s: cp->set_shift = %d", cp->name, cp->set_shift); debug("%s: cp->set_mask = 0x%08x", cp->name, cp->set_mask); debug("%s: cp->tag_shift = %d", cp->name, cp->tag_shift); debug("%s: cp->tag_mask = 0x%08x", cp->name, cp->tag_mask); debug("%s: cp->usize = %d", cp->name, cp->usize); debug("%s: cp->policy = %s", cp->name, cache_policy_name(cp->policy)); debug("%s: cp->cbr_policy = %s", cp->name, cache_cbr_policy_name(cp->cbr_policy)); /* initialize cache stats */ cp->hits = 0; cp->misses = 0; cp->replacements = 0; cp->writebacks = 0; cp->invalidations = 0; /* blow away the last block accessed */ cp->last_tagset = 0; cp->last_blk = NULL; /* allocate data blocks */ cp->data = (byte_t *) calloc(nsets * assoc, sizeof(struct cache_blk_t) + (cp->balloc ? (bsize * sizeof(byte_t)) : 0)); if(!cp->data) fatal("out of virtual memory"); /* slice up the data blocks */ for(bindex = 0, i = 0; i < nsets; i++) { cp->sets[i].way_head = NULL; cp->sets[i].way_tail = NULL; /* get a hash table, if needed */ if(cp->hsize) { cp->sets[i].hash = (struct cache_blk_t **) calloc(cp->hsize, sizeof(struct cache_blk_t *)); if(!cp->sets[i].hash) fatal("out of virtual memory"); } /* NOTE: all the blocks in a set *must* be allocated contiguously, otherwise, block accesses through SET->BLKS will fail (used during random replacement selection) */ cp->sets[i].blks = CACHE_BINDEX(cp, cp->data, bindex); /* link the data blocks into ordered way chain and hash table bucket chains, if hash table exists */ for(j = 0; j < assoc; j++) { /* locate next cache block */ blk = CACHE_BINDEX(cp, cp->data, bindex); bindex++; /* invalidate new cache block */ blk->status = 0; blk->tag = 0; blk->ready = 0; blk->user_data = (usize != 0 ? (byte_t *) calloc(usize, sizeof(byte_t)) : NULL); /* initialize CBR data */ blk->cbr_line_info.counter = 0; blk->cbr_line_info.confidence = 0; blk->cbr_line_info.max_counter_past = 0; blk->cbr_line_info.max_counter_present = 0; blk->cbr_line_info.hashed_pc = 0; /* insert cache block into set hash table */ if(cp->hsize) link_htab_ent(cp, &cp->sets[i], blk); /* insert into head of way list, order is arbitrary at this point */ blk->way_next = cp->sets[i].way_head; blk->way_prev = NULL; if(cp->sets[i].way_head) cp->sets[i].way_head->way_prev = blk; cp->sets[i].way_head = blk; if(!cp->sets[i].way_tail) cp->sets[i].way_tail = blk; } } return cp; } /* parse policy */ /* called during cache construction in sim-cache.c:sim_check_options */ enum cache_policy /* replacement policy enum */ cache_char2policy(char c) /* replacement policy as a char */ { switch(c) { case 'l': return LRU; case 'r': return Random; case 'f': return FIFO; default: fatal("bogus replacement policy, `%c'", c); } } enum cache_cbr_policy /* CBR policy enum */ cache_char2cbrPolicy(char c) /* CBR policy as a char */ { switch(c) { case 'a': return AIP; case 'l': return LvP; default: return None; } } /* parses a CBR cache specification string (as from the command line) */ int cache_parse_options( char* optionsString, /* input string to be parsed */ char* cacheName, /* output pointer: cache name (eg. dl1, il2, ...) */ int* setCount, /* output pointer: cache set count */ int* blockSize, /* output pointer: cache block/line size */ int* assoc, /* output pointer: cache set associativity */ enum cache_policy* replacementPolicy, /* output pointer: cache line replacement policy identifier (eg. 'l' (LRU), 'f' (FIFO), ...) */ enum cache_cbr_policy* cbrPolicy /* output pointer: Counter-Based Replacement policy (on top of replacementPolicy) (eg. 'a' (AIP), 'l' (LvP)) set to NULL to ignore any CBR policy specified in the specification string */ ) { char policyChar = 0; char cbrPolicyChar = 0; // try to parse CBR format //debug("\n\n\n"); int cbrParsedCount = sscanf(optionsString, "%[^:]:%d:%d:%d:%c:%c", cacheName, setCount, blockSize, assoc, &policyChar, &cbrPolicyChar); debug("\n\nattempted to parse cache options format: %s (parsed %d/6 options)", optionsString, cbrParsedCount); if(cbrParsedCount < 5) return FALSE; *replacementPolicy = cache_char2policy(policyChar); if(cbrPolicy != NULL) *cbrPolicy = (cbrParsedCount == 6 ? cache_char2cbrPolicy(cbrPolicyChar) : None); /*debug("cache name: %s", cacheName); debug("set count: %d", *setCount); debug("block size: %d", *blockSize); debug("assoc: %d", *assoc); debug("replacement policy char: %c", policyChar); debug("CBR policy char: %c", cbrPolicyChar); debug("CBR policy: %d", cbrPolicy);*/ return TRUE; } /* print cache configuration */ void cache_config(struct cache_t *cp, /* cache instance */ FILE *stream) /* output stream */ { fprintf(stream, "cache: %s: %d sets, %d byte blocks, %d bytes user data/block\n", cp->name, cp->nsets, cp->bsize, cp->usize); fprintf(stream, "cache: %s: %d-way, `%s' replacement policy, write-back\n", cp->name, cp->assoc, cache_policy_name(cp->policy)); } /* register cache stats */ void cache_reg_stats(struct cache_t *cp, /* cache instance */ struct stat_sdb_t *sdb) /* stats database */ { char buf[512], buf1[512], *name; int i; /* get a name for this cache */ if(!cp->name || !cp->name[0]) { name = ""; } else { name = cp->name; } sprintf(buf, "%s.accesses", name); sprintf(buf1, "%s.hits + %s.misses", name, name); stat_reg_formula(sdb, buf, "total number of accesses", buf1, "%12.0f"); sprintf(buf, "%s.hits", name); stat_reg_counter(sdb, buf, "total number of hits", &cp->hits, 0, NULL); sprintf(buf, "%s.misses", name); stat_reg_counter(sdb, buf, "total number of misses", &cp->misses, 0, NULL); sprintf(buf, "%s.replacements", name); stat_reg_counter(sdb, buf, "total number of replacements", &cp->replacements, 0, NULL); sprintf(buf, "%s.writebacks", name); stat_reg_counter(sdb, buf, "total number of writebacks", &cp->writebacks, 0, NULL); sprintf(buf, "%s.evictions_std", name); sprintf(buf1, "total number of eviction victims chosen by the standard cache replacement policy (%s)", cache_policy_name(cp->policy)); stat_reg_counter(sdb, buf, buf1, &cp->evictions_policy, 0, NULL); sprintf(buf, "%s.evictions_cbr", name); sprintf(buf1, "total number of eviction victims chosen by the CBR cache replacement policy (%s)", cache_cbr_policy_name(cp->cbr_policy)); stat_reg_counter(sdb, buf, buf1, &cp->evictions_cbr_policy, 0, NULL); sprintf(buf, "%s.invalidations", name); stat_reg_counter(sdb, buf, "total number of invalidations", &cp->invalidations, 0, NULL); sprintf(buf, "%s.miss_rate", name); sprintf(buf1, "%s.misses / %s.accesses", name, name); stat_reg_formula(sdb, buf, "miss rate (i.e., misses/ref)", buf1, NULL); sprintf(buf, "%s.repl_rate", name); sprintf(buf1, "%s.replacements / %s.accesses", name, name); stat_reg_formula(sdb, buf, "replacement rate (i.e., repls/ref)", buf1, NULL); sprintf(buf, "%s.wb_rate", name); sprintf(buf1, "%s.writebacks / %s.accesses", name, name); stat_reg_formula(sdb, buf, "writeback rate (i.e., wrbks/ref)", buf1, NULL); sprintf(buf, "%s.inv_rate", name); sprintf(buf1, "%s.invalidations / %s.accesses", name, name); stat_reg_formula(sdb, buf, "invalidation rate (i.e., invs/ref)", buf1, NULL); /* if a histogram was allocated for this cache, print it out in teh stats */ if(cp->stack_dist_histogram){ for(i=0; iassoc; i++){ sprintf(buf, "%s.stack_dist[%d]", name, i); sprintf(buf1, "amount of cache hits at MRU/stack distance %d", i); stat_reg_counter(sdb, buf, buf1, &cp->stack_dist_histogram[i], 0, NULL); } } if(cp->cbr_repl_dist_histogram){ for(i=0; iassoc; i++){ sprintf(buf, "%s.cbr_repl_stack_dist[%d]", name, i); sprintf(buf1, "amount of blocks evicted by CBR policy %s at MRU/stack distance %d", cache_cbr_policy_name(cp->cbr_policy), i); stat_reg_counter(sdb, buf, buf1, &cp->cbr_repl_dist_histogram[i], 0, NULL); } } } /* print cache stats */ void cache_stats(struct cache_t *cp, /* cache instance */ FILE *stream) /* output stream */ { double sum = (double)(cp->hits + cp->misses); fprintf( stream, "cache: %s: %.0f hits %.0f misses %.0f repls %.0f invalidations\n", cp->name, (double)cp->hits, (double)cp->misses, (double)cp->replacements, (double)cp->invalidations ); fprintf( stream, "cache: %s: miss rate=%f repl rate=%f invalidation rate=%f\n", cp->name, (double)cp->misses/sum, (double)(double)cp->replacements/sum, (double)cp->invalidations/sum ); } /* DEBUGGING STUFF */ /* static long accessed_blocks_counter = 0; static md_addr_t accessed_blocks[100000]; bool_t has_blk_been_accessed(struct cache_t* cp, md_addr_t addr){ int i; md_addr_t blk_addr = CACHE_TAGSET(cp, addr); for(i=0; icbr_policy != None); } bool_t is_tracking_block(struct cache_t* cp, md_addr_t addr){ // TODO: temporary measure to improve runtime performance while we're not debugging return FALSE; if(!is_cbr_cache(cp)) return FALSE; /*md_addr_t blk_addr = CACHE_MK_BADDR(cp, CACHE_TAG(cp, addr), CACHE_SET(cp, addr));//CACHE_TAGSET(cp, addr); assert(blk_addr == CACHE_TAGSET(cp, addr)); return (blk_addr == 0x20089180);*/ md_addr_t set = CACHE_SET(cp, addr); return (set == 582); } void debug_dump_set(struct cache_t* cp, md_addr_t addr /* address within the set */){ if(!is_cbr_cache(cp)) return; md_addr_t tag = CACHE_TAG(cp, addr); /* cache block tag number */ md_addr_t set = CACHE_SET(cp, addr); /* cache set index */ //md_addr_t line_addr = CACHE_MK_BADDR(cp, tag, set); /* block address of accessed cache line */ struct cache_blk_t* blk = NULL; //int i = 0; bool_t valid; bool_t dirty; debug("-- SET DUMP: %d --", (long) CACHE_SET(cp, addr)); // loop over all blocks in set //for(i=0; i < cp->assoc; i++){ for(blk = cp->sets[set].way_head; blk; blk = blk->way_next){ //blk = CACHE_BINDEX(cp, cp->sets[set].blks, i); valid = ((blk->status & CACHE_BLK_VALID) > 0); dirty = ((blk->status & CACHE_BLK_DIRTY) > 0); debug("%4s (valid = %d, dirty = %d, tag 0x%04x, counter = %02d, maxCpresent = %02d, maxCpast = %02d, confidence = %d, hashedPC = 0x%02x)", (blk == cp->sets[set].way_head ? "HEAD" : (blk == cp->sets[set].way_tail ? "TAIL" : "")), //i++, valid, dirty, (long) blk->tag, blk->cbr_line_info.counter, blk->cbr_line_info.max_counter_present, blk->cbr_line_info.max_counter_past, blk->cbr_line_info.confidence, blk->cbr_line_info.hashed_pc ); } } /* access a cache, perform a CMD operation on cache CP at address ADDR, places NBYTES of data at *P, returns latency of operation if initiated at NOW, places pointer to block user data in *UDATA, *P is untouched if cache blocks are not allocated (!CP->BALLOC), UDATA should be NULL if no user data is attached to blocks */ unsigned int /* latency of access in cycles */ cache_access( struct cache_t *cp, /* cache to access */ enum mem_cmd cmd, /* access type, Read or Write */ md_addr_t addr, /* address of access */ void *vp, /* ptr to buffer for input/output */ int nbytes, /* number of bytes to access */ tick_t now, /* time of access */ byte_t **udata, /* for return of user data ptr */ md_addr_t *repl_addr ) { byte_t *p = vp; md_addr_t tag = CACHE_TAG(cp, addr); /* cache block tag number */ md_addr_t set = CACHE_SET(cp, addr); /* cache set index */ md_addr_t bofs = CACHE_BLK(cp, addr); /* offset of addr within cache block */ md_addr_t line_addr = CACHE_MK_BADDR(cp, tag, set); /* block address of accessed cache line */ struct cache_blk_t* blk = NULL; /* generic "current block" variable */ struct cache_blk_t* repl = NULL; /* block being evicted on cache miss (ie. block to be replaced) */ int lat = 0; /* -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT */ /* we need the current PC for CBR replacement. unfortunately, the registers are only declared inside the simulators themselves * so we would need to modify the cache access function signature to add a param to pass them (or just use the user data pointer) * However, I really can't be bothered at the moment. */ if(regs == NULL){ fatal("cache: registry not found! call cbr_set_regs(struct regs_t*) in your main simulator to register the registry (yo dawg) - it's usually defined in the main simulator file (sim-outorder.c, sim-cache.c, ...) as \"regs\" . and yes, this is a hack."); } /* default replacement address */ if(repl_addr) *repl_addr = 0; /* check alignments */ if((nbytes & (nbytes - 1)) != 0 || (addr & (nbytes - 1)) != 0) fatal("cache: access error: bad size or alignment, addr 0x%08x", addr); /* access must fit in cache block */ /* FIXME: ((addr + (nbytes - 1)) > ((addr & ~cp->blk_mask) + (cp->bsize - 1))) */ if((addr + nbytes) > ((addr & ~cp->blk_mask) + cp->bsize)) fatal("cache: access error: access spans block, addr 0x%08x", addr); //if(is_cbr_cache(cp)){ if(is_tracking_block(cp, addr)){ debug("\n\n\n%s access to address 0x%08x, block 0x%08x, set %d, instruction 0x%08x", (cmd == Read ? "read" : "write"), (long) addr, (long) line_addr, set, regs->regs_PC); //debug_dump_set(cp, addr); } /* AIP */ if(cp->cbr_policy == AIP){ // "on a cache line access, increment the event counter of each (valid?) line in the accessed set" if(is_tracking_block(cp, addr)) debug("incrementing counters on set %d", set); aip_increment_set_counters(cp, &cp->sets[set]); if(is_tracking_block(cp, addr)){ debug("after:"); debug_dump_set(cp, addr); } } /*if(!has_blk_been_accessed(cp, addr)){ debug("initial access to block 0x%08x, set %d, offset %d", (long) line_addr, set, bofs); register_blk_access(cp, addr); }*/ // /* permissions are checked on cache misses */ bool_t fast_cache_hit = FALSE; /* check for a fast hit: access to same block */ if(CACHE_TAGSET(cp, addr) == cp->last_tagset) { /* hit in the same block */ blk = cp->last_blk; fast_cache_hit = TRUE; goto cache_hit_common; } /* no hit to the same block (the previous if would have caught it), so let's see if we can find one */ if(cp->hsize) { /* highly associative cache; use the per-set hash tables to find a matching block * remember: the hash table is indexed by hashing the tag. Each entry in the hash table is a pointer * to the first block in the corresponding hash bucket for that tag (the next one in the bucket is * linked to by blk->hash_next). Thus, we need only iterate over one hash bucket: the one indexed * by our tag, because that one will contain all lines with the same tag value. */ int hindex = CACHE_HASH(cp, tag); for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)){ goto cache_hit_common; } } } else { /* low-associativity cache, linear search the way list * scan the block list front-to-back, ie. MRU to LRU */ for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)){ goto cache_hit_common; } } } /* -- CACHE MISS ----------------------------------------- */ /* ie. the requested block is not present in the current cache set. Thus, we must now identify a victim * block to be removed from the cache and replaced by the newly requested set. */ //cache_miss: if(is_tracking_block(cp, addr)) debug("miss on address 0x%08x, block 0x%08x", (long) addr, (long) line_addr); cp->misses++; // determine replacement block repl = NULL; // let CBR have a crack at it first if(cp->cbr_policy == AIP){ repl = aip_find_expired_block(cp, &cp->sets[set]); } else if(cp->cbr_policy == LvP){ repl = lvp_find_expired_block(cp, &cp->sets[set]); } if(repl != NULL){ cp->evictions_cbr_policy++; // CBR policy found one, increase CBR eviction counter // record the MRU stack position of the evicted block (well, the one that's about to evicted anyway) if(cp->cbr_repl_dist_histogram){ int stack_dist = cbr_get_way_position(cp, &cp->sets[set], repl); cp->cbr_repl_dist_histogram[stack_dist]++; } if(is_tracking_block(cp, addr)){ debug( "CBR found expired block 0x%08x with: [counter=0x%02x, maxCpresent=%d, maxCpast=%d, confidence=%d]", (long)(CACHE_MK_BADDR(cp, repl->tag, set)), repl->cbr_line_info.counter, (long) repl->cbr_line_info.max_counter_present, (long) repl->cbr_line_info.max_counter_past, repl->cbr_line_info.confidence ); /*debug("AIP found expired block: 0x%08x", CACHE_MK_BADDR(cp, repl->tag, set)); debug(" counter: %d", repl->cbr_line_info.counter); debug(" maxCpresent: %d", repl->cbr_line_info.max_counter_present); debug(" maxCpast: %d", repl->cbr_line_info.max_counter_past); debug(" confidence: %d", repl->cbr_line_info.confidence);*/ } assert(repl->cbr_line_info.confidence); } else { if(is_tracking_block(cp, addr)){ debug("No CBR expired block found for miss on address 0x%08x", addr); } } /* if there is no expired AIP block, let the standard replacement policy pick one */ //if(repl == NULL){ /* select the appropriate block to replace, and re-link this entry to the appropriate place in the way list */ switch(cp->policy) { /* For LRU, the blocks are ordered MRU to LRU if you start from set->way_head and make your way to * set->way_tail. Thus, the LRU block is always found by just taking the tail. * For FIFO, the blocks just run through the chain way_head to way_tail as they enter and leave the * set; thus, the FIFO replacement block is found by taking the tail as well */ case LRU: case FIFO: // if CBR didn't find a replacement line, let the default replacement policy pick one // CAREFUL: this check only works if repl is initialized to NULL! (if no CBR policy is set and repl is // declared as simply struct cache_blk_t* repl;, it will contain a garbage value and this NULL check will fail // causing segfaults on the update_way_list that comes after this if) if(repl == NULL){ repl = cp->sets[set].way_tail; // tail == LRU cp->evictions_policy++; if(is_tracking_block(cp, addr)) debug("LRU picked replacement block 0x%04x", (long)(repl->tag)); } // the block "repl" will be removed and replaced; in code, this means it will its data overwritten with the new block's data, // so move it up to the front already (MRU position for LRU policy, first position for FIFO) update_way_list(&cp->sets[set], repl, Head); if(is_tracking_block(cp, addr)){ debug("Moving LRU-chosen block 0x%04x to head of way list (MRU position)", (long)(repl->tag)); debug_dump_set(cp, addr); } break; case Random: // if CBR didn't find a replacement line, let the default replacement policy pick one if(repl == NULL) { // just pick a random block to be replaced, the way ordering list is not used int bindex = myrand() & (cp->assoc - 1); repl = CACHE_BINDEX(cp, cp->sets[set].blks, bindex); cp->evictions_policy++; } break; default: panic("bogus replacement policy"); } //} /* -- at this point, the replacement block is known (repl) ---------------------------- */ // update the prediction table by y's information (y = replacement line): // Index the table using y.hashedPC and y's line address int y_hashedPC = repl->cbr_line_info.hashed_pc; // the line address of y is formed as the tag bits + the set bits + all 0's for the offset bits // the tag bits for each cache line are stored in the cache line structure itself; the set is determined // by the set it's being replaced from (otherwise it wouldn't have been placed in that set in the first place) // thus, we need to combine y's (ie. repl's) tag bits with the current set bits // fortunately, simplescalar provides a handy macro to do just that. md_addr_t y_lineAddr = CACHE_MK_BADDR(cp, repl->tag, set); if(cp->cbr_policy == AIP){ word_t max_counter = repl->cbr_line_info.max_counter_present; bool_t confidence = (repl->cbr_line_info.max_counter_present == repl->cbr_line_info.max_counter_past ? TRUE : FALSE); if(!(repl->status & CACHE_BLK_VALID)){ if(is_tracking_block(cp, addr)){ debug("Not storing block to be replaced's info in prediction table, invalid block"); } } else { // store new information in table if(is_tracking_block(cp, addr)){ //debug("Storing replacement block's information in prediction table; PC = 0x%08x, hashedPC = 0x%02x, block addr = 0x%08x", (long) regs->regs_PC, y_hashedPC, (long) y_lineAddr); debug("Storing the block to be replaced's info in the prediction table"); debug("History entry(hashedPC = 0x%02x, lineAddr = 0x%08x -> hashed 0x%02x) <- maxCstored = %02d, confidence = %d", y_hashedPC, (long) y_lineAddr, (long)(CBR_HASH_PC8(y_lineAddr)), max_counter, confidence ); } // y.maxCstored = y.maxCpresent //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].max_counter = repl->cbr_line_info.max_counter_present; // if(y.maxCpresent == y.maxCpast) // y.conf_stored = 1 // else // y.conf_stored = 0 //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].confidence = (repl->cbr_line_info.max_counter_present == repl->cbr_line_info.max_counter_past ? TRUE : FALSE); /*cbr_pred_table_set_entry(cp, y_hashedPC, y_lineAddr, repl->cbr_line_info.max_counter_present, (repl->cbr_line_info.max_counter_present == repl->cbr_line_info.max_counter_past ? TRUE : FALSE) );*/ cbr_pred_table_set_entry(cp, y_hashedPC, y_lineAddr, max_counter, confidence ); } } else if(cp->cbr_policy == LvP){ word_t max_counter = repl->cbr_line_info.counter; bool_t confidence = (repl->cbr_line_info.counter == repl->cbr_line_info.max_counter_past ? TRUE : FALSE); // y.maxCstored = y.C //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].max_counter = repl->cbr_line_info.counter; // if(y.maxCpast == y.C) // y.conf_stored = 1 // else // y.conf_stored = 0 //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].confidence = (repl->cbr_line_info.counter == repl->cbr_line_info.max_counter_past ? TRUE : FALSE); cbr_pred_table_set_entry(cp, y_hashedPC, y_lineAddr, max_counter, confidence ); } /* remove this block from the hash bucket chain, if hash exists * why? remember: the repl block will house the new block which will have a different tag. * Since the hash table is indexed by tag, this would leave us with an inconsistent hash table */ if(cp->hsize) unlink_htab_ent(cp, &cp->sets[set], repl); /* blow away the last block to hit */ cp->last_tagset = 0; cp->last_blk = NULL; /* write back replaced block data */ if(repl->status & CACHE_BLK_VALID) { // amount of replacements is only updated when the victim line is a valid cache line, // ie. that contains valid previous content. If the victim were not valid, then its content // was just dead space, and so we wouldn't be "replacing" anything other than dead space // (which doesn't count as an actual replacement) cp->replacements++; // block/line address of the block that's getting evicted (see AIP above) if(repl_addr) *repl_addr = CACHE_MK_BADDR(cp, repl->tag, set); // don't replace the block until outstanding misses are satisfied lat += BOUND_POS(repl->ready - now); // stall until the bus to next level of memory is available lat += BOUND_POS(cp->bus_free - (now + lat)); // track bus resource usage cp->bus_free = MAX(cp->bus_free, (now + lat)) + 1; /* the block to be replaced has changes; write them to the higher memory level * first before replacing it */ if(repl->status & CACHE_BLK_DIRTY) { // write back the cache block cp->writebacks++; lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, repl->tag, set), cp->bsize, repl, now + lat); } } // update block tags repl->tag = tag; repl->status = CACHE_BLK_VALID; // newly loaded block is always valid (dirty bit set on update) // read new data block lat += cp->blk_access_fn(Read, CACHE_BADDR(cp, addr), cp->bsize, repl, now + lat); // copy data out of cache block if(cp->balloc) { CACHE_BCOPY(cmd, repl, bofs, p, nbytes); } // update dirty status if(cmd == Write) repl->status |= CACHE_BLK_DIRTY; // get user block data, if requested and it exists if(udata) *udata = repl->user_data; // update block status repl->ready = now + lat; // link this entry back into the hash table if(cp->hsize) link_htab_ent(cp, &cp->sets[set], repl); /* --------------------------------------------------------------------- */ // note: at this point repl has been updated with the new cache line information; // thus, at this point, x = repl int x_hashedPC = CBR_HASH_PC8(regs->regs_PC); md_addr_t x_lineAddr = CACHE_MK_BADDR(cp, tag, set); struct cbr_pred_table_entry_t* pred_table_entry; /* AIP: read history from prediction table */ if(cp->cbr_policy == AIP){ /* from the paper (x = accessed cache line): * Index the prediction table using x.hashedPC and x's line address. * x.hashedPC is obtained by performing 8-bit XOR to the instruction PC that causes the miss to x * * x.C = x.maxCpresent = 0 * x.maxCpast = x.maxCstored * x.conf = x.conf_stored */ pred_table_entry = cbr_get_pred_table_element(cp, x_hashedPC, x_lineAddr); repl->cbr_line_info.counter = 0; repl->cbr_line_info.hashed_pc = x_hashedPC; repl->cbr_line_info.max_counter_present = 0; /*repl->cbr_line_info.max_counter_past = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter; repl->cbr_line_info.confidence = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence;*/ repl->cbr_line_info.max_counter_past = pred_table_entry->max_counter; repl->cbr_line_info.confidence = pred_table_entry->confidence; if(is_tracking_block(cp, addr)){ debug("Initializing replaced block's AIP parameters"); debug("History entry(PC = 0x%08x -> hashedPC = 0x%02x, lineAddr = 0x%08x -> hashed 0x%02x): maxCstored = %02d, confidence = %d", (long) regs->regs_PC, x_hashedPC, (long) x_lineAddr, (long)(CBR_HASH_PC8(x_lineAddr)), /*cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter, cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence*/ pred_table_entry->max_counter, pred_table_entry->confidence ); debug(" -> counter = 0, hashed_pc = 0x%02x, maxCpresent = 0, maxCpast = %02d, confidence = %d", x_hashedPC, /*cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter, cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence*/ pred_table_entry->max_counter, pred_table_entry->confidence ); debug_dump_set(cp, addr); } } else if(cp->cbr_policy == LvP){ /* from the paper (x = accessed cache line): * Index the prediction table using x.hashedPC and x's line address. * x.hashedPC is obtained by performing 8-bit XOR to the instruction PC that causes the miss to x * * x.C = 0 * x.maxCpast = x.maxCstored * x.conf = x.conf_stored */ pred_table_entry = cbr_get_pred_table_element(cp, x_hashedPC, x_lineAddr); repl->cbr_line_info.counter = 0; repl->cbr_line_info.hashed_pc = x_hashedPC; /*repl->cbr_line_info.max_counter_past = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter; repl->cbr_line_info.confidence = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence;*/ repl->cbr_line_info.max_counter_past = pred_table_entry->max_counter; repl->cbr_line_info.confidence = pred_table_entry->confidence; } // return latency of the operation return lat; /* -- CACHE HIT ----------------------------------------- */ // "blk" holds the hit cache line at this point cache_hit_common: /* common hit handler */ cp->hits++; if(is_tracking_block(cp, addr)){ debug("%shit on address 0x%08x, block 0x%08x", (fast_cache_hit ? "fast" : ""), (long) addr, (long) line_addr); } /* AIP */ if(cp->cbr_policy == AIP){ // "if the access is a hit, reset x's counter after recording the new threshold maximum" blk->cbr_line_info.max_counter_present = MAX(blk->cbr_line_info.counter, blk->cbr_line_info.max_counter_present); blk->cbr_line_info.counter = 0; if(is_tracking_block(cp, addr)){ debug("updating maxCpresent = %02d, counter = %02d", blk->cbr_line_info.max_counter_present, blk->cbr_line_info.counter); // debug_dump performed after the dirty bit has been set; see cache hit handlers } } else if(cp->cbr_policy == LvP){ // "if the access is a hit": // x.C = x.C + 1 blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX); } if(fast_cache_hit){ goto cache_fast_hit; } else { goto cache_hit; } cache_hit: /* slow hit handler */ /* if we need to calculate a histogram, do it nao */ if(cp->stack_dist_histogram){ int stack_dist = cbr_get_way_position(cp, &cp->sets[set], blk); cp->stack_dist_histogram[stack_dist]++; } /* copy data out of cache block, if block exists */ if(cp->balloc) { CACHE_BCOPY(cmd, blk, bofs, p, nbytes); } /* update dirty status */ if(cmd == Write) blk->status |= CACHE_BLK_DIRTY; /* if LRU replacement and this is not the first element of list, reorder */ if(blk->way_prev && cp->policy == LRU) { /* move this block to head of the way (MRU) list */ update_way_list(&cp->sets[set], blk, Head); if(is_tracking_block(cp, addr)){ debug("Moving hit block 0x%04x to head of way list (MRU position)", (long)(blk->tag)); } } if(is_tracking_block(cp, addr)) debug_dump_set(cp, addr); /* tag is unchanged, so hash links (if they exist) are still valid */ /* record the last block to hit */ cp->last_tagset = CACHE_TAGSET(cp, addr); cp->last_blk = blk; /* get user block data, if requested and it exists */ if(udata) *udata = blk->user_data; /* return first cycle data is available to access */ return (int) MAX(cp->hit_latency, (blk->ready - now)); cache_fast_hit: /* fast hit handler */ /* if we need to calculate a histogram, do it nao */ if(cp->stack_dist_histogram){ cp->stack_dist_histogram[0]++; // access to same block as last time, increment first counter } /* copy data out of cache block, if block exists */ if(cp->balloc) { CACHE_BCOPY(cmd, blk, bofs, p, nbytes); } /* update dirty status */ if(cmd == Write) blk->status |= CACHE_BLK_DIRTY; if(is_tracking_block(cp, addr)) debug_dump_set(cp, addr); /* this block hit last, no change in the way list */ /* tag is unchanged, so hash links (if they exist) are still valid */ /* get user block data, if requested and it exists */ if(udata) *udata = blk->user_data; /* record the last block to hit */ cp->last_tagset = CACHE_TAGSET(cp, addr); cp->last_blk = blk; /* return first cycle data is available to access */ return (int) MAX(cp->hit_latency, (blk->ready - now)); } /* return non-zero if block containing address ADDR is contained in cache CP, this interface is used primarily for debugging and asserting cache invariants */ int /* non-zero if access would hit */ cache_probe( struct cache_t *cp, /* cache instance to probe */ md_addr_t addr /* address of block to probe */ ) { md_addr_t tag = CACHE_TAG(cp, addr); md_addr_t set = CACHE_SET(cp, addr); struct cache_blk_t *blk; /* permissions are checked on cache misses */ if(cp->hsize) { /* higly-associativity cache, access through the per-set hash tables */ int hindex = CACHE_HASH(cp, tag); for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) return TRUE; } } else { /* low-associativity cache, linear search the way list */ for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) return TRUE; } } /* cache block not found */ return FALSE; } /* flush the entire cache, returns latency of the operation */ unsigned int /* latency of the flush operation */ cache_flush( struct cache_t *cp, /* cache instance to flush */ tick_t now /* time of cache flush */ ) { int i, lat = cp->hit_latency; /* min latency to probe cache */ struct cache_blk_t *blk; /* blow away the last block to hit */ cp->last_tagset = 0; cp->last_blk = NULL; /* no way list updates required because all blocks are being invalidated */ for(i = 0; i < cp->nsets; i++) { for(blk = cp->sets[i].way_head; blk; blk = blk->way_next) { if(blk->status & CACHE_BLK_VALID) { cp->invalidations++; blk->status &= ~CACHE_BLK_VALID; // mark as invalid if(blk->status & CACHE_BLK_DIRTY) { /* write back the invalidated block */ cp->writebacks++; lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, blk->tag, i), cp->bsize, blk, now + lat); } } } } /* return latency of the flush operation */ return lat; } /* flush the block containing ADDR from the cache CP, returns the latency of the block flush operation */ unsigned int /* latency of flush operation */ cache_flush_addr(struct cache_t *cp, /* cache instance to flush */ md_addr_t addr, /* address of block to flush */ tick_t now) /* time of cache flush */ { md_addr_t tag = CACHE_TAG(cp, addr); md_addr_t set = CACHE_SET(cp, addr); struct cache_blk_t *blk; int lat = cp->hit_latency; /* min latency to probe cache */ if(cp->hsize) { /* higly-associativity cache, access through the per-set hash tables */ int hindex = CACHE_HASH(cp, tag); for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) break; } } else { /* low-associativity cache, linear search the way list */ for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) { if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) break; } } if(blk) { cp->invalidations++; blk->status &= ~CACHE_BLK_VALID; /* blow away the last block to hit */ cp->last_tagset = 0; cp->last_blk = NULL; if(blk->status & CACHE_BLK_DIRTY) { /* write back the invalidated block */ cp->writebacks++; lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, blk->tag, set), cp->bsize, blk, now + lat); } /* move this block to tail of the way (LRU) list */ update_way_list(&cp->sets[set], blk, Tail); } /* return latency of the operation */ return lat; }