API tools faq
paste
Guest User

Untitled

a guest
Jul 20th, 2018
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 51.43 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. #include "host.h"
  6. #include "regs.h"
  7. #include "misc.h"
  8. #include "machine.h"
  9. #include "cache.h"
  10.  
  11. /* compute 8-bit PC hash by XOR-ing all 8-bit parts */
  12. #define CBR_HASH_PC8(addr) ((((addr) >> 24) ^ ((addr) >> 16) ^ ((addr) >> 8) ^ (addr)) & 0xFF)
  13.  
  14. /* maximum CBR counter value (= 2^CBR_COUNTER_RESOLUTION - 1) */
  15. #define CBR_COUNTER_MAX ((1 << (CBR_COUNTER_RESOLUTION)) - 1)
  16.  
  17. /* maps 2D prediction table indexing pair (PC, lineAddress) to linear array index */
  18. #define CBR_PRED_TABLE_INDEX(hashed_pc, line_address) (((hashed_pc)*0xFF) + CBR_HASH_PC8(line_address))
  19.  
  20. /* cache access macros */
  21. #define CACHE_TAG(cp, addr) ((addr) >> (cp)->tag_shift)
  22. #define CACHE_SET(cp, addr) (((addr) >> (cp)->set_shift) & (cp)->set_mask)
  23. #define CACHE_BLK(cp, addr) ((addr) & (cp)->blk_mask)
  24. #define CACHE_TAGSET(cp, addr) ((addr) & (cp)->tagset_mask)
  25.  
  26. /* extract/reconstruct a block address */
  27. #define CACHE_BADDR(cp, addr) ((addr) & ~(cp)->blk_mask)
  28. #define CACHE_MK_BADDR(cp, tag, set) \
  29. (((tag) << (cp)->tag_shift)|((set) << (cp)->set_shift))
  30.  
  31. /* index an array of cache blocks, non-trivial due to variable length blocks
  32. (ie. gets (a pointer to) the cache block at index i in block array blks?) */
  33. #define CACHE_BINDEX(cp, blks, i) \
  34. ((struct cache_blk_t *)(((char *)(blks)) + \
  35. (i)*(sizeof(struct cache_blk_t) + \
  36. ((cp)->balloc \
  37. ? (cp)->bsize*sizeof(byte_t) : 0))))
  38.  
  39. /* cache data block accessor, type parameterized */
  40. #define __CACHE_ACCESS(type, data, bofs) \
  41. (*((type *)(((char *)data) + (bofs))))
  42.  
  43. /* cache data block accessors, by type */
  44. #define CACHE_DOUBLE(data, bofs) __CACHE_ACCESS(double, data, bofs)
  45. #define CACHE_FLOAT(data, bofs) __CACHE_ACCESS(float, data, bofs)
  46. #define CACHE_WORD(data, bofs) __CACHE_ACCESS(unsigned int, data, bofs)
  47. #define CACHE_HALF(data, bofs) __CACHE_ACCESS(unsigned short, data, bofs)
  48. #define CACHE_BYTE(data, bofs) __CACHE_ACCESS(unsigned char, data, bofs)
  49.  
  50. /* cache block hashing macros, this macro is used to index into a cache
  51. set hash table (to find the correct block on N in an N-way cache), the
  52. cache set index function is CACHE_SET, defined above */
  53. #define CACHE_HASH(cp, key) \
  54. (((key >> 24) ^ (key >> 16) ^ (key >> 8) ^ key) & ((cp)->hsize-1))
  55.  
  56. /* copy data out of a cache block to buffer indicated by argument pointer p */
  57. #define CACHE_BCOPY(cmd, blk, bofs, p, nbytes) \
  58. if (cmd == Read) \
  59. { \
  60. switch (nbytes) { \
  61. case 1: \
  62. *((byte_t *)p) = CACHE_BYTE(&blk->data[0], bofs); break; \
  63. case 2: \
  64. *((half_t *)p) = CACHE_HALF(&blk->data[0], bofs); break; \
  65. case 4: \
  66. *((word_t *)p) = CACHE_WORD(&blk->data[0], bofs); break; \
  67. default: \
  68. { /* >= 8, power of two, fits in block */ \
  69. int words = nbytes >> 2; \
  70. while (words-- > 0) \
  71. { \
  72. *((word_t *)p) = CACHE_WORD(&blk->data[0], bofs); \
  73. p += 4; bofs += 4; \
  74. }\
  75. }\
  76. }\
  77. }\
  78. else /* cmd == Write */ \
  79. { \
  80. switch (nbytes) { \
  81. case 1: \
  82. CACHE_BYTE(&blk->data[0], bofs) = *((byte_t *)p); break; \
  83. case 2: \
  84. CACHE_HALF(&blk->data[0], bofs) = *((half_t *)p); break; \
  85. case 4: \
  86. CACHE_WORD(&blk->data[0], bofs) = *((word_t *)p); break; \
  87. default: \
  88. { /* >= 8, power of two, fits in block */ \
  89. int words = nbytes >> 2; \
  90. while (words-- > 0) \
  91. { \
  92. CACHE_WORD(&blk->data[0], bofs) = *((word_t *)p); \
  93. p += 4; bofs += 4; \
  94. }\
  95. }\
  96. }\
  97. }
  98.  
  99. /* bound sqword_t/dfloat_t to positive int */
  100. #define BOUND_POS(N) ((int)(MIN(MAX(0, (N)), 2147483647)))
  101.  
  102. /* unlink BLK from the hash table bucket chain in SET */
  103. static void unlink_htab_ent(
  104. struct cache_t *cp, /* cache to update */
  105. struct cache_set_t *set, /* set containing bkt chain */
  106. struct cache_blk_t *blk /* block to unlink */
  107. )
  108. {
  109. struct cache_blk_t *prev, *ent;
  110. int index = CACHE_HASH(cp, blk->tag);
  111.  
  112.  
  113. /* locate the block in the hash table bucket chain */
  114. for(prev = NULL, ent = set->hash[index]; ent; prev = ent, ent = ent->hash_next) {
  115. if(ent == blk) break;
  116. }
  117. assert(ent);
  118.  
  119.  
  120. /* unlink the block from the hash table bucket chain */
  121. if(!prev) {
  122. /* head of hash bucket list */
  123. set->hash[index] = ent->hash_next;
  124. } else {
  125. /* middle or end of hash bucket list */
  126. prev->hash_next = ent->hash_next;
  127. }
  128. ent->hash_next = NULL;
  129. }
  130.  
  131. /* insert BLK onto the head of the hash table bucket chain in SET */
  132. static void
  133. link_htab_ent(struct cache_t *cp, /* cache to update */
  134. struct cache_set_t *set, /* set containing bkt chain */
  135. struct cache_blk_t *blk) /* block to insert */
  136. {
  137. int index = CACHE_HASH(cp, blk->tag);
  138.  
  139.  
  140. /* insert block onto the head of the bucket chain */
  141. blk->hash_next = set->hash[index];
  142. set->hash[index] = blk;
  143. }
  144.  
  145. /* where to insert a block onto the ordered way chain */
  146. enum list_loc_t { Head, Tail };
  147.  
  148. /* HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT HACK ALERT */
  149. /* This should really be done by modifying the calls to cache_access etc and pass the regs as an argument,
  150. * but I'm out of time */
  151. static struct regs_t* regs = NULL;
  152. void cbr_set_regs(struct regs_t* regs_in){
  153. regs = regs_in;
  154. }
  155.  
  156. void cbr_init_pred_table(struct cbr_pred_table_t* pred_table){
  157.  
  158. int i;
  159. for(i = 0; i < CBR_PRED_TABLE_SIZE; i++){
  160. pred_table->entries[i].max_counter = CBR_COUNTER_MAX;
  161. pred_table->entries[i].confidence = FALSE;
  162. }
  163.  
  164. }
  165.  
  166. struct cbr_pred_table_entry_t* cbr_get_pred_table_element(struct cache_t* cp, byte_t hashedPC, md_addr_t lineAddress){
  167.  
  168. int index = CBR_PRED_TABLE_INDEX(hashedPC, lineAddress);
  169. return &cp->cbr_pred_table->entries[index];
  170.  
  171. }
  172.  
  173. void cbr_pred_table_set_entry(struct cache_t* cp, byte_t hashedPC, md_addr_t lineAddress, word_t counter, bool_t confidence){
  174.  
  175. //if(CBR_HASH_PC8(lineAddress) == 0x39) debug("\n\n\n!!! HISTORY(0x%02x, 0x34) = %02d, %d !!!\n\n\n", hashedPC, counter, confidence);
  176. int index = CBR_PRED_TABLE_INDEX(hashedPC, lineAddress);
  177. cp->cbr_pred_table->entries[index].confidence = confidence;
  178. cp->cbr_pred_table->entries[index].max_counter = counter;
  179.  
  180. }
  181.  
  182. /* increments all CBR cache line counters within the provided set */
  183. void aip_increment_set_counters(
  184. struct cache_t* cp, /* pointer to cache structure */
  185. struct cache_set_t* set /* pointer to cache set */
  186. // md_addr_t tag /* tag of hit block (used only for high-associative caches) */
  187. ){
  188.  
  189. struct cache_blk_t* blk = NULL;
  190. //int i = 0;
  191.  
  192. /*debug("\nbefore");
  193. for(i = 0, blk = set->way_head; blk; blk = blk->way_next){
  194. debug("block %d: %d", i, blk->cbr_line_info.counter);
  195. i++;
  196. }*/
  197.  
  198. // loop over all blocks in set
  199. /*for(i=0; i < cp->assoc; i++){
  200. //blk = &set->blks[i]; // current block in set
  201. blk = CACHE_BINDEX(cp, set->blks, i);
  202. blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX);
  203. }*/
  204.  
  205. for(blk = set->way_head; blk; blk = blk->way_next){
  206. blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX);
  207. }
  208.  
  209. /*debug("\nafter");
  210. for(i = 0, blk = set->way_head; blk; blk = blk->way_next){
  211. debug("block %d: %d, confidence %d", i, blk->cbr_line_info.counter, blk->cbr_line_info.confidence);
  212. i++;
  213. }*/
  214.  
  215. }
  216.  
  217. /* returns TRUE if the specified cache line is AIP-expired, FALSE otherwise */
  218. bool_t aip_is_line_expired(struct cache_blk_t* blk){
  219.  
  220. return (blk->cbr_line_info.counter > blk->cbr_line_info.max_counter_present
  221. && blk->cbr_line_info.counter > blk->cbr_line_info.max_counter_past
  222. && blk->cbr_line_info.confidence);
  223.  
  224. }
  225.  
  226. bool_t lvp_is_line_expired(struct cache_blk_t* blk){
  227.  
  228. return (blk->cbr_line_info.counter >= blk->cbr_line_info.max_counter_past
  229. && blk->cbr_line_info.confidence);
  230.  
  231. }
  232.  
  233. /* returns the position of blk in the set SET relative to the MRU (way_head) position, or -1 if not found */
  234. int cbr_get_way_position(struct cache_t* cp, struct cache_set_t* set, struct cache_blk_t* blk){
  235.  
  236. struct cache_blk_t* currentBlock = NULL;
  237.  
  238. int i = 0;
  239. for(currentBlock = set->way_head; currentBlock; currentBlock = currentBlock->way_next){
  240.  
  241. if(currentBlock == blk){
  242. return i;
  243. }
  244.  
  245. i++;
  246. }
  247.  
  248. return -1;
  249.  
  250. }
  251.  
  252. /* finds an AIP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */
  253. struct cache_blk_t* cbr_find_expired_block(
  254. struct cache_t* cp,
  255. struct cache_set_t* set,
  256. bool_t (*is_blk_expired)(struct cache_blk_t* b)
  257. ){
  258.  
  259. struct cache_blk_t* blk = NULL; // generic "current block"-variable
  260. int i = 0;
  261.  
  262. /* identify all expired cache lines */
  263.  
  264. int expiredBlockCount = 0; // amount of AIP-expired block in this cache set
  265. struct cache_blk_t** expiredBlocks = calloc(cp->assoc, sizeof(struct cache_blk_t*)); // array of pointers to expired blocks in the set
  266. if(!expiredBlocks) fatal("could not allocate temporary expiredBlocks pointer array: out of virtual memory");
  267.  
  268. for(i = 0; i < cp->assoc; i++){
  269.  
  270. blk = &set->blks[i];
  271.  
  272. if(is_blk_expired(blk)){
  273.  
  274. expiredBlocks[expiredBlockCount] = blk;
  275. expiredBlockCount++;
  276.  
  277. }
  278.  
  279. }
  280.  
  281. /* find a replacement cache block: random selection */
  282.  
  283. if(expiredBlockCount <= 0){
  284.  
  285. blk = NULL;
  286.  
  287. } else {
  288.  
  289. blk = expiredBlocks[rand() % expiredBlockCount];
  290.  
  291. }
  292.  
  293. free(expiredBlocks);
  294. return blk;
  295.  
  296. }
  297.  
  298. /* finds an AIP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */
  299. struct cache_blk_t* aip_find_expired_block(struct cache_t* cp, struct cache_set_t* set){
  300.  
  301. return cbr_find_expired_block(cp, set, aip_is_line_expired);
  302.  
  303. }
  304.  
  305. /* finds an LvP-expired block in a cache set. returns a pointer to the expired block, or NULL if none exists */
  306. struct cache_blk_t* lvp_find_expired_block(struct cache_t* cp, struct cache_set_t* set){
  307.  
  308. return cbr_find_expired_block(cp, set, lvp_is_line_expired);
  309.  
  310. }
  311.  
  312. /* insert BLK into the order way chain in SET at location WHERE */
  313. static void
  314. update_way_list(
  315. struct cache_set_t *set, /* set contained way chain */
  316. struct cache_blk_t *blk, /* block to insert */
  317. enum list_loc_t where) /* insert location */
  318. {
  319.  
  320. /* unlink entry from the way list */
  321.  
  322. if(!blk->way_prev && !blk->way_next) {
  323.  
  324. /* no previous or next block in the set, ie. only one entry in set list
  325. => (direct-mapped), no action */
  326.  
  327. assert(set->way_head == blk && set->way_tail == blk);
  328. return; /* Head/Tail order already */
  329.  
  330. }
  331. /* else, more than one element in the list */
  332. else if(!blk->way_prev) {
  333.  
  334. // no previous block and more than one element => current block is first in the set list
  335.  
  336. assert(set->way_head == blk && set->way_tail != blk);
  337.  
  338. if(where == Head) {
  339. return; /* already there */
  340. }
  341.  
  342. /* else, unlink */
  343. set->way_head = blk->way_next;
  344. blk->way_next->way_prev = NULL;
  345.  
  346. } else if(!blk->way_next) {
  347.  
  348. // no next blocks and more than one element in list => current block is the last in the set list
  349.  
  350. /* end of list (and not front of list) */
  351. assert(set->way_head != blk && set->way_tail == blk);
  352.  
  353. if(where == Tail) {
  354. return; /* already there */
  355. }
  356.  
  357. /* unlink */
  358. set->way_tail = blk->way_prev;
  359. blk->way_prev->way_next = NULL;
  360.  
  361. } else {
  362.  
  363. /* middle of list (and not front or end of list) */
  364. assert(set->way_head != blk && set->way_tail != blk);
  365.  
  366. /* unlink from list */
  367. blk->way_prev->way_next = blk->way_next;
  368. blk->way_next->way_prev = blk->way_prev;
  369.  
  370. }
  371.  
  372.  
  373. /* link BLK back into the list at the specified position */
  374. if(where == Head) {
  375.  
  376. /* link to the head of the way list */
  377. blk->way_next = set->way_head;
  378. blk->way_prev = NULL;
  379. set->way_head->way_prev = blk;
  380. set->way_head = blk;
  381.  
  382. } else if(where == Tail) {
  383.  
  384. /* link to the tail of the way list */
  385. blk->way_prev = set->way_tail;
  386. blk->way_next = NULL;
  387. set->way_tail->way_next = blk;
  388. set->way_tail = blk;
  389.  
  390. } else {
  391. panic("bogus WHERE designator");
  392. }
  393.  
  394. }
  395.  
  396. char* cache_policy_name(enum cache_policy policy){
  397.  
  398. switch(policy) {
  399. case LRU:
  400. return "LRU";
  401. case Random:
  402. return "Random";
  403. case FIFO:
  404. return "FIFO";
  405. default:
  406. return (abort(), "<no such cache policy>");
  407. }
  408.  
  409. }
  410.  
  411. char* cache_cbr_policy_name(enum cache_cbr_policy cbr_policy){
  412.  
  413. switch(cbr_policy){
  414.  
  415. case AIP:
  416. return "AIP";
  417. case LvP:
  418. return "LvP";
  419. case None:
  420. return "None";
  421. default:
  422. return (abort(), "<no such CBR policy>");
  423.  
  424. }
  425.  
  426. }
  427.  
  428. /* create and initialize a general cache structure */
  429. struct cache_t * /* pointer to cache created */
  430. cache_create(
  431.  
  432. char *name, /* name of the cache */
  433. int nsets, /* total number of sets in cache */
  434. int bsize, /* block (line) size of cache */
  435. int balloc, /* allocate data space for blocks? */
  436. int usize, /* size of user data to alloc w/blks */
  437. int assoc, /* associativity of cache */
  438. enum cache_policy policy, /* replacement policy w/in sets */
  439. enum cache_cbr_policy cbr_policy, /* CBR replacement policy */
  440.  
  441. /* block access function, see description w/in struct cache def */
  442. unsigned int (*blk_access_fn)(
  443. enum mem_cmd cmd,
  444. md_addr_t baddr,
  445. int bsize,
  446. struct cache_blk_t *blk,
  447. tick_t now
  448. ),
  449.  
  450. unsigned int hit_latency /* latency in cycles for a hit */
  451.  
  452. )
  453. {
  454.  
  455. struct cache_t *cp;
  456. struct cache_blk_t *blk;
  457. int i, j, bindex;
  458.  
  459.  
  460. /* check all cache parameters */
  461. if(nsets <= 0) fatal("cache size (in sets) `%d' must be non-zero", nsets);
  462. if((nsets & (nsets - 1)) != 0) fatal("cache size (in sets) `%d' is not a power of two", nsets);
  463.  
  464. /* blocks must be at least one datum large, i.e., 8 bytes for SS */
  465. if(bsize < 8) fatal("cache block size (in bytes) `%d' must be 8 or greater", bsize);
  466. if((bsize & (bsize - 1)) != 0) fatal("cache block size (in bytes) `%d' must be a power of two", bsize);
  467. if(usize < 0) fatal("user data size (in bytes) `%d' must be a positive value", usize);
  468. if(assoc <= 0) fatal("cache associativity `%d' must be non-zero and positive", assoc);
  469. if((assoc & (assoc - 1)) != 0) fatal("cache associativity `%d' must be a power of two", assoc);
  470. if(!blk_access_fn) fatal("must specify miss/replacement functions");
  471.  
  472.  
  473. /* allocate the cache structure */
  474.  
  475. /*
  476. * NOTE: observe how the cache structure is allocated: first a cache_t struct is allocated
  477. * which includes a single tail cache_set_t struct (see definition of cache_t in cache.h).
  478. * Immediately after that cache_t structure (and thus immediately after the single cache_set),
  479. * an additional (nsets - 1) sets are allocated, thus completing the amount of sets and also
  480. * allowing for the sets to be accessed through the tail pointer in cache_t.
  481. */
  482.  
  483. cp = (struct cache_t *) calloc(1, sizeof(struct cache_t) + (nsets - 1) * sizeof(struct cache_set_t));
  484. if(!cp) fatal("out of virtual memory");
  485.  
  486.  
  487. /* initialize user parameters */
  488. cp->name = mystrdup(name);
  489. cp->nsets = nsets;
  490. cp->bsize = bsize;
  491. cp->balloc = balloc;
  492. cp->usize = usize;
  493. cp->assoc = assoc;
  494. cp->policy = policy;
  495. cp->cbr_policy = cbr_policy;
  496. cp->hit_latency = hit_latency;
  497.  
  498. /* allocate CBR prediction table, if required */
  499. if(cp->cbr_policy != None){
  500.  
  501. debug("Allocating CBR prediction table: %d bytes", sizeof(struct cbr_pred_table_t));
  502.  
  503. cp->cbr_pred_table = (struct cbr_pred_table_t*) calloc(1, sizeof(struct cbr_pred_table_t));
  504. if(!cp->cbr_pred_table) fatal("failed to allocate CBR prediction table");
  505.  
  506. cbr_init_pred_table(cp->cbr_pred_table);
  507.  
  508. }
  509.  
  510. /* allocate LRU stack distance histogram table */
  511. cp->stack_dist_histogram = calloc(cp->assoc, sizeof(counter_t));
  512. if(!cp->stack_dist_histogram) fatal("failed to allocate stack distance histogram array");
  513.  
  514. /* miss/replacement functions */
  515. cp->blk_access_fn = blk_access_fn;
  516.  
  517.  
  518. /* compute derived parameters */
  519. cp->hsize = CACHE_HIGHLY_ASSOC(cp) ? (assoc >> 2) : 0;
  520. cp->blk_mask = bsize - 1;
  521. cp->set_shift = log_base2(bsize);
  522. cp->set_mask = nsets - 1;
  523. cp->tag_shift = cp->set_shift + log_base2(nsets);
  524. cp->tag_mask = (1 << (32 - cp->tag_shift)) - 1;
  525. cp->tagset_mask = ~cp->blk_mask;
  526. cp->bus_free = 0;
  527.  
  528.  
  529. /* print derived parameters during debug */
  530. debug("%s: cp->hsize = %d", cp->name, cp->hsize);
  531. debug("%s: cp->blk_mask = 0x%08x", cp->name, cp->blk_mask);
  532. debug("%s: cp->set_shift = %d", cp->name, cp->set_shift);
  533. debug("%s: cp->set_mask = 0x%08x", cp->name, cp->set_mask);
  534. debug("%s: cp->tag_shift = %d", cp->name, cp->tag_shift);
  535. debug("%s: cp->tag_mask = 0x%08x", cp->name, cp->tag_mask);
  536. debug("%s: cp->usize = %d", cp->name, cp->usize);
  537. debug("%s: cp->policy = %s", cp->name, cache_policy_name(cp->policy));
  538. debug("%s: cp->cbr_policy = %s", cp->name, cache_cbr_policy_name(cp->cbr_policy));
  539.  
  540.  
  541. /* initialize cache stats */
  542. cp->hits = 0;
  543. cp->misses = 0;
  544. cp->replacements = 0;
  545. cp->writebacks = 0;
  546. cp->invalidations = 0;
  547.  
  548.  
  549. /* blow away the last block accessed */
  550. cp->last_tagset = 0;
  551. cp->last_blk = NULL;
  552.  
  553.  
  554. /* allocate data blocks */
  555. cp->data = (byte_t *) calloc(nsets * assoc, sizeof(struct cache_blk_t) + (cp->balloc ? (bsize * sizeof(byte_t)) : 0));
  556. if(!cp->data) fatal("out of virtual memory");
  557.  
  558.  
  559. /* slice up the data blocks */
  560. for(bindex = 0, i = 0; i < nsets; i++) {
  561.  
  562. cp->sets[i].way_head = NULL;
  563. cp->sets[i].way_tail = NULL;
  564.  
  565. /* get a hash table, if needed */
  566. if(cp->hsize) {
  567. cp->sets[i].hash = (struct cache_blk_t **) calloc(cp->hsize, sizeof(struct cache_blk_t *));
  568. if(!cp->sets[i].hash) fatal("out of virtual memory");
  569. }
  570.  
  571. /* NOTE: all the blocks in a set *must* be allocated contiguously,
  572. otherwise, block accesses through SET->BLKS will fail (used
  573. during random replacement selection) */
  574. cp->sets[i].blks = CACHE_BINDEX(cp, cp->data, bindex);
  575.  
  576. /* link the data blocks into ordered way chain and hash table bucket
  577. chains, if hash table exists */
  578. for(j = 0; j < assoc; j++) {
  579.  
  580. /* locate next cache block */
  581. blk = CACHE_BINDEX(cp, cp->data, bindex);
  582. bindex++;
  583.  
  584. /* invalidate new cache block */
  585. blk->status = 0;
  586. blk->tag = 0;
  587. blk->ready = 0;
  588. blk->user_data = (usize != 0 ? (byte_t *) calloc(usize, sizeof(byte_t)) : NULL);
  589.  
  590. /* initialize CBR data */
  591. blk->cbr_line_info.counter = 0;
  592. blk->cbr_line_info.confidence = 0;
  593. blk->cbr_line_info.max_counter_past = 0;
  594. blk->cbr_line_info.max_counter_present = 0;
  595. blk->cbr_line_info.hashed_pc = 0;
  596.  
  597. /* insert cache block into set hash table */
  598. if(cp->hsize) link_htab_ent(cp, &cp->sets[i], blk);
  599.  
  600. /* insert into head of way list, order is arbitrary at this point */
  601. blk->way_next = cp->sets[i].way_head;
  602. blk->way_prev = NULL;
  603. if(cp->sets[i].way_head) cp->sets[i].way_head->way_prev = blk;
  604. cp->sets[i].way_head = blk;
  605. if(!cp->sets[i].way_tail) cp->sets[i].way_tail = blk;
  606.  
  607. }
  608.  
  609. }
  610.  
  611. return cp;
  612.  
  613. }
  614.  
  615. /* parse policy */
  616. /* called during cache construction in sim-cache.c:sim_check_options */
  617. enum cache_policy /* replacement policy enum */
  618. cache_char2policy(char c) /* replacement policy as a char */
  619. {
  620.  
  621. switch(c) {
  622. case 'l':
  623. return LRU;
  624. case 'r':
  625. return Random;
  626. case 'f':
  627. return FIFO;
  628. default:
  629. fatal("bogus replacement policy, `%c'", c);
  630. }
  631.  
  632. }
  633.  
  634.  
  635. enum cache_cbr_policy /* CBR policy enum */
  636. cache_char2cbrPolicy(char c) /* CBR policy as a char */
  637. {
  638.  
  639. switch(c) {
  640. case 'a':
  641. return AIP;
  642. case 'l':
  643. return LvP;
  644. default:
  645. return None;
  646. }
  647.  
  648. }
  649.  
  650. /* parses a CBR cache specification string (as from the command line) */
  651. int cache_parse_options(
  652. char* optionsString, /* input string to be parsed */
  653. char* cacheName, /* output pointer: cache name (eg. dl1, il2, ...) */
  654. int* setCount, /* output pointer: cache set count */
  655. int* blockSize, /* output pointer: cache block/line size */
  656. int* assoc, /* output pointer: cache set associativity */
  657. enum cache_policy* replacementPolicy, /* output pointer: cache line replacement policy identifier (eg. 'l' (LRU), 'f' (FIFO), ...) */
  658. enum cache_cbr_policy* cbrPolicy /* output pointer: Counter-Based Replacement policy (on top of replacementPolicy) (eg. 'a' (AIP), 'l' (LvP))
  659. set to NULL to ignore any CBR policy specified in the specification string */
  660. )
  661. {
  662.  
  663. char policyChar = 0;
  664. char cbrPolicyChar = 0;
  665.  
  666. // try to parse CBR format
  667.  
  668. //debug("\n\n\n");
  669. int cbrParsedCount = sscanf(optionsString, "%[^:]:%d:%d:%d:%c:%c", cacheName, setCount, blockSize, assoc, &policyChar, &cbrPolicyChar);
  670. debug("\n\nattempted to parse cache options format: %s (parsed %d/6 options)", optionsString, cbrParsedCount);
  671.  
  672. if(cbrParsedCount < 5) return FALSE;
  673.  
  674. *replacementPolicy = cache_char2policy(policyChar);
  675. if(cbrPolicy != NULL) *cbrPolicy = (cbrParsedCount == 6 ? cache_char2cbrPolicy(cbrPolicyChar) : None);
  676.  
  677. /*debug("cache name: %s", cacheName);
  678. debug("set count: %d", *setCount);
  679. debug("block size: %d", *blockSize);
  680. debug("assoc: %d", *assoc);
  681. debug("replacement policy char: %c", policyChar);
  682. debug("CBR policy char: %c", cbrPolicyChar);
  683. debug("CBR policy: %d", cbrPolicy);*/
  684.  
  685. return TRUE;
  686.  
  687. }
  688.  
  689. /* print cache configuration */
  690. void
  691. cache_config(struct cache_t *cp, /* cache instance */
  692. FILE *stream) /* output stream */
  693. {
  694. fprintf(stream, "cache: %s: %d sets, %d byte blocks, %d bytes user data/block\n", cp->name, cp->nsets, cp->bsize, cp->usize);
  695. fprintf(stream, "cache: %s: %d-way, `%s' replacement policy, write-back\n", cp->name, cp->assoc, cache_policy_name(cp->policy));
  696. }
  697.  
  698. /* register cache stats */
  699. void
  700. cache_reg_stats(struct cache_t *cp, /* cache instance */
  701. struct stat_sdb_t *sdb) /* stats database */
  702. {
  703.  
  704. char buf[512], buf1[512], *name;
  705. int i;
  706.  
  707. /* get a name for this cache */
  708. if(!cp->name || !cp->name[0]) {
  709. name = "<unknown>";
  710. } else {
  711. name = cp->name;
  712. }
  713.  
  714. sprintf(buf, "%s.accesses", name);
  715. sprintf(buf1, "%s.hits + %s.misses", name, name);
  716. stat_reg_formula(sdb, buf, "total number of accesses", buf1, "%12.0f");
  717.  
  718. sprintf(buf, "%s.hits", name);
  719. stat_reg_counter(sdb, buf, "total number of hits", &cp->hits, 0, NULL);
  720.  
  721. sprintf(buf, "%s.misses", name);
  722. stat_reg_counter(sdb, buf, "total number of misses", &cp->misses, 0, NULL);
  723.  
  724. sprintf(buf, "%s.replacements", name);
  725. stat_reg_counter(sdb, buf, "total number of replacements", &cp->replacements, 0, NULL);
  726.  
  727. sprintf(buf, "%s.writebacks", name);
  728. stat_reg_counter(sdb, buf, "total number of writebacks", &cp->writebacks, 0, NULL);
  729.  
  730. sprintf(buf, "%s.evictions_std", name);
  731. sprintf(buf1, "total number of eviction victims chosen by the standard cache replacement policy (%s)", cache_policy_name(cp->policy));
  732. stat_reg_counter(sdb, buf, buf1, &cp->evictions_policy, 0, NULL);
  733.  
  734. sprintf(buf, "%s.evictions_cbr", name);
  735. sprintf(buf1, "total number of eviction victims chosen by the CBR cache replacement policy (%s)", cache_cbr_policy_name(cp->cbr_policy));
  736. stat_reg_counter(sdb, buf, buf1, &cp->evictions_cbr_policy, 0, NULL);
  737.  
  738. sprintf(buf, "%s.invalidations", name);
  739. stat_reg_counter(sdb, buf, "total number of invalidations", &cp->invalidations, 0, NULL);
  740.  
  741. sprintf(buf, "%s.miss_rate", name);
  742. sprintf(buf1, "%s.misses / %s.accesses", name, name);
  743. stat_reg_formula(sdb, buf, "miss rate (i.e., misses/ref)", buf1, NULL);
  744.  
  745. sprintf(buf, "%s.repl_rate", name);
  746. sprintf(buf1, "%s.replacements / %s.accesses", name, name);
  747. stat_reg_formula(sdb, buf, "replacement rate (i.e., repls/ref)", buf1, NULL);
  748.  
  749. sprintf(buf, "%s.wb_rate", name);
  750. sprintf(buf1, "%s.writebacks / %s.accesses", name, name);
  751. stat_reg_formula(sdb, buf, "writeback rate (i.e., wrbks/ref)", buf1, NULL);
  752.  
  753. sprintf(buf, "%s.inv_rate", name);
  754. sprintf(buf1, "%s.invalidations / %s.accesses", name, name);
  755. stat_reg_formula(sdb, buf, "invalidation rate (i.e., invs/ref)", buf1, NULL);
  756.  
  757. /* if a histogram was allocated for this cache, print it out in teh stats */
  758. if(cp->stack_dist_histogram){
  759.  
  760. for(i=0; i<cp->assoc; i++){
  761.  
  762. sprintf(buf, "%s.stack_dist[%d]", name, i);
  763. sprintf(buf1, "amount of cache hits at MRU/stack distance %d", i);
  764. stat_reg_counter(sdb, buf, buf1, &cp->stack_dist_histogram[i], 0, NULL);
  765.  
  766. }
  767.  
  768. }
  769.  
  770. }
  771.  
  772. /* print cache stats */
  773. void
  774. cache_stats(struct cache_t *cp, /* cache instance */
  775. FILE *stream) /* output stream */
  776. {
  777.  
  778. double sum = (double)(cp->hits + cp->misses);
  779.  
  780. fprintf(
  781. stream,
  782. "cache: %s: %.0f hits %.0f misses %.0f repls %.0f invalidations\n",
  783. cp->name, (double)cp->hits, (double)cp->misses, (double)cp->replacements, (double)cp->invalidations
  784. );
  785.  
  786. fprintf(
  787. stream,
  788. "cache: %s: miss rate=%f repl rate=%f invalidation rate=%f\n",
  789. cp->name, (double)cp->misses/sum, (double)(double)cp->replacements/sum, (double)cp->invalidations/sum
  790. );
  791.  
  792. }
  793.  
  794. /* DEBUGGING STUFF */
  795. /*
  796. static long accessed_blocks_counter = 0;
  797. static md_addr_t accessed_blocks[100000];
  798.  
  799. bool_t has_blk_been_accessed(struct cache_t* cp, md_addr_t addr){
  800.  
  801. int i;
  802. md_addr_t blk_addr = CACHE_TAGSET(cp, addr);
  803.  
  804. for(i=0; i<accessed_blocks_counter; i++){
  805. if(accessed_blocks[i] == blk_addr) return TRUE;
  806. }
  807.  
  808. return FALSE;
  809. }
  810.  
  811. void register_blk_access(struct cache_t* cp, md_addr_t addr){
  812.  
  813. md_addr_t blk_addr = CACHE_TAGSET(cp, addr);
  814. accessed_blocks[accessed_blocks_counter++] = blk_addr;
  815.  
  816. }*/
  817.  
  818. bool_t is_cbr_cache(struct cache_t* cp){
  819. return (cp->cbr_policy != None);
  820. }
  821.  
  822. bool_t is_tracking_block(struct cache_t* cp, md_addr_t addr){
  823.  
  824. if(!is_cbr_cache(cp)) return FALSE;
  825. /*md_addr_t blk_addr = CACHE_MK_BADDR(cp, CACHE_TAG(cp, addr), CACHE_SET(cp, addr));//CACHE_TAGSET(cp, addr);
  826. assert(blk_addr == CACHE_TAGSET(cp, addr));
  827. return (blk_addr == 0x20089180);*/
  828.  
  829. md_addr_t set = CACHE_SET(cp, addr);
  830. return (set == 582);
  831.  
  832. }
  833.  
  834. void debug_dump_set(struct cache_t* cp, md_addr_t addr /* address within the set */){
  835.  
  836. if(!is_cbr_cache(cp)) return;
  837.  
  838. md_addr_t tag = CACHE_TAG(cp, addr); /* cache block tag number */
  839. md_addr_t set = CACHE_SET(cp, addr); /* cache set index */
  840. //md_addr_t line_addr = CACHE_MK_BADDR(cp, tag, set); /* block address of accessed cache line */
  841.  
  842. struct cache_blk_t* blk = NULL;
  843. //int i = 0;
  844. bool_t valid;
  845. bool_t dirty;
  846.  
  847. debug("-- SET DUMP: %d --", (long) CACHE_SET(cp, addr));
  848.  
  849. // loop over all blocks in set
  850. //for(i=0; i < cp->assoc; i++){
  851. for(blk = cp->sets[set].way_head; blk; blk = blk->way_next){
  852.  
  853. //blk = CACHE_BINDEX(cp, cp->sets[set].blks, i);
  854.  
  855. valid = ((blk->status & CACHE_BLK_VALID) > 0);
  856. dirty = ((blk->status & CACHE_BLK_DIRTY) > 0);
  857.  
  858. debug("%4s (valid = %d, dirty = %d, tag 0x%04x, counter = %02d, maxCpresent = %02d, maxCpast = %02d, confidence = %d, hashedPC = 0x%02x)",
  859. (blk == cp->sets[set].way_head ? "HEAD" :
  860. (blk == cp->sets[set].way_tail ? "TAIL" : "")),
  861. //i++,
  862. valid,
  863. dirty,
  864. (long) blk->tag,
  865. blk->cbr_line_info.counter,
  866. blk->cbr_line_info.max_counter_present,
  867. blk->cbr_line_info.max_counter_past,
  868. blk->cbr_line_info.confidence,
  869. blk->cbr_line_info.hashed_pc
  870. );
  871.  
  872. }
  873.  
  874. }
  875.  
  876. /* access a cache, perform a CMD operation on cache CP at address ADDR,
  877. places NBYTES of data at *P, returns latency of operation if initiated
  878. at NOW, places pointer to block user data in *UDATA, *P is untouched if
  879. cache blocks are not allocated (!CP->BALLOC), UDATA should be NULL if no
  880. user data is attached to blocks */
  881. unsigned int /* latency of access in cycles */
  882. cache_access(
  883. struct cache_t *cp, /* cache to access */
  884. enum mem_cmd cmd, /* access type, Read or Write */
  885. md_addr_t addr, /* address of access */
  886. void *vp, /* ptr to buffer for input/output */
  887. int nbytes, /* number of bytes to access */
  888. tick_t now, /* time of access */
  889. byte_t **udata, /* for return of user data ptr */
  890. md_addr_t *repl_addr
  891. )
  892. {
  893.  
  894. byte_t *p = vp;
  895. md_addr_t tag = CACHE_TAG(cp, addr); /* cache block tag number */
  896. md_addr_t set = CACHE_SET(cp, addr); /* cache set index */
  897. md_addr_t bofs = CACHE_BLK(cp, addr); /* offset of addr within cache block */
  898. md_addr_t line_addr = CACHE_MK_BADDR(cp, tag, set); /* block address of accessed cache line */
  899. struct cache_blk_t* blk = NULL; /* generic "current block" variable */
  900. struct cache_blk_t* repl = NULL; /* block being evicted on cache miss (ie. block to be replaced) */
  901. int lat = 0;
  902.  
  903. /* -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT -- HACK ALERT */
  904. /* we need the current PC for CBR replacement. unfortunately, the registers are only declared inside the simulators themselves
  905. * 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)
  906. * However, I really can't be bothered at the moment. */
  907. if(regs == NULL){
  908. 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.");
  909. }
  910.  
  911. /* default replacement address */
  912. if(repl_addr) *repl_addr = 0;
  913.  
  914. /* check alignments */
  915. if((nbytes & (nbytes - 1)) != 0 || (addr & (nbytes - 1)) != 0) fatal("cache: access error: bad size or alignment, addr 0x%08x", addr);
  916.  
  917. /* access must fit in cache block */
  918. /* FIXME:
  919. ((addr + (nbytes - 1)) > ((addr & ~cp->blk_mask) + (cp->bsize - 1))) */
  920. if((addr + nbytes) > ((addr & ~cp->blk_mask) + cp->bsize)) fatal("cache: access error: access spans block, addr 0x%08x", addr);
  921.  
  922. //if(is_cbr_cache(cp)){
  923. if(is_tracking_block(cp, addr)){
  924. 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);
  925. //debug_dump_set(cp, addr);
  926. }
  927.  
  928. /* AIP */
  929. if(cp->cbr_policy == AIP){
  930.  
  931. // "on a cache line access, increment the event counter of each (valid?) line in the accessed set"
  932. if(is_tracking_block(cp, addr)) debug("incrementing counters on set %d", set);
  933. aip_increment_set_counters(cp, &cp->sets[set]);
  934.  
  935. if(is_tracking_block(cp, addr)){
  936. debug("after:");
  937. debug_dump_set(cp, addr);
  938. }
  939.  
  940. }
  941.  
  942. /*if(!has_blk_been_accessed(cp, addr)){
  943. debug("initial access to block 0x%08x, set %d, offset %d", (long) line_addr, set, bofs);
  944. register_blk_access(cp, addr);
  945. }*/
  946. //
  947.  
  948. /* permissions are checked on cache misses */
  949.  
  950. bool_t fast_cache_hit = FALSE;
  951.  
  952. /* check for a fast hit: access to same block */
  953. if(CACHE_TAGSET(cp, addr) == cp->last_tagset) {
  954.  
  955. /* hit in the same block */
  956.  
  957. blk = cp->last_blk;
  958.  
  959. fast_cache_hit = TRUE;
  960. goto cache_hit_common;
  961.  
  962. }
  963.  
  964. /* no hit to the same block (the previous if would have caught it), so let's see if we can find one */
  965. if(cp->hsize) {
  966.  
  967. /* highly associative cache; use the per-set hash tables to find a matching block
  968. * remember: the hash table is indexed by hashing the tag. Each entry in the hash table is a pointer
  969. * to the first block in the corresponding hash bucket for that tag (the next one in the bucket is
  970. * linked to by blk->hash_next). Thus, we need only iterate over one hash bucket: the one indexed
  971. * by our tag, because that one will contain all lines with the same tag value. */
  972.  
  973. int hindex = CACHE_HASH(cp, tag);
  974.  
  975. for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) {
  976. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)){
  977. goto cache_hit_common;
  978. }
  979. }
  980.  
  981. } else {
  982.  
  983. /* low-associativity cache, linear search the way list
  984. * scan the block list front-to-back, ie. MRU to LRU */
  985.  
  986. for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) {
  987. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)){
  988. goto cache_hit_common;
  989. }
  990. }
  991.  
  992. }
  993.  
  994.  
  995.  
  996. /* -- CACHE MISS ----------------------------------------- */
  997. /* ie. the requested block is not present in the current cache set. Thus, we must now identify a victim
  998. * block to be removed from the cache and replaced by the newly requested set. */
  999.  
  1000. //cache_miss:
  1001.  
  1002. if(is_tracking_block(cp, addr)) debug("miss on address 0x%08x, block 0x%08x", (long) addr, (long) line_addr);
  1003. cp->misses++;
  1004.  
  1005.  
  1006.  
  1007. // determine replacement block
  1008. repl = NULL;
  1009.  
  1010. // let CBR have a crack at it first
  1011. if(cp->cbr_policy == AIP){
  1012.  
  1013. repl = aip_find_expired_block(cp, &cp->sets[set]);
  1014.  
  1015. } else if(cp->cbr_policy == LvP){
  1016.  
  1017. repl = lvp_find_expired_block(cp, &cp->sets[set]);
  1018.  
  1019. }
  1020.  
  1021. if(repl != NULL){
  1022.  
  1023. cp->evictions_cbr_policy++; // CBR policy found one, increase CBR eviction counter
  1024.  
  1025. if(is_tracking_block(cp, addr)){
  1026.  
  1027. debug(
  1028. "CBR found expired block 0x%08x with: [counter=0x%02x, maxCpresent=%d, maxCpast=%d, confidence=%d]",
  1029. (long)(CACHE_MK_BADDR(cp, repl->tag, set)),
  1030. repl->cbr_line_info.counter,
  1031. (long) repl->cbr_line_info.max_counter_present,
  1032. (long) repl->cbr_line_info.max_counter_past,
  1033. repl->cbr_line_info.confidence
  1034. );
  1035.  
  1036. /*debug("AIP found expired block: 0x%08x", CACHE_MK_BADDR(cp, repl->tag, set));
  1037. debug(" counter: %d", repl->cbr_line_info.counter);
  1038. debug(" maxCpresent: %d", repl->cbr_line_info.max_counter_present);
  1039. debug(" maxCpast: %d", repl->cbr_line_info.max_counter_past);
  1040. debug(" confidence: %d", repl->cbr_line_info.confidence);*/
  1041.  
  1042. }
  1043.  
  1044. assert(repl->cbr_line_info.confidence);
  1045.  
  1046. } else {
  1047.  
  1048. if(is_tracking_block(cp, addr)){
  1049. debug("No CBR expired block found for miss on address 0x%08x", addr);
  1050. }
  1051.  
  1052. }
  1053.  
  1054. /* if there is no expired AIP block, let the standard replacement policy pick one */
  1055. //if(repl == NULL){
  1056.  
  1057. /* select the appropriate block to replace, and re-link this entry to
  1058. the appropriate place in the way list */
  1059.  
  1060. switch(cp->policy) {
  1061.  
  1062. /* For LRU, the blocks are ordered MRU to LRU if you start from set->way_head and make your way to
  1063. * set->way_tail. Thus, the LRU block is always found by just taking the tail.
  1064. * For FIFO, the blocks just run through the chain way_head to way_tail as they enter and leave the
  1065. * set; thus, the FIFO replacement block is found by taking the tail as well */
  1066.  
  1067. case LRU:
  1068. case FIFO:
  1069.  
  1070. // if CBR didn't find a replacement line, let the default replacement policy pick one
  1071. // CAREFUL: this check only works if repl is initialized to NULL! (if no CBR policy is set and repl is
  1072. // declared as simply struct cache_blk_t* repl;, it will contain a garbage value and this NULL check will fail
  1073. // causing segfaults on the update_way_list that comes after this if)
  1074. if(repl == NULL){
  1075. repl = cp->sets[set].way_tail; // tail == LRU
  1076. cp->evictions_policy++;
  1077. if(is_tracking_block(cp, addr)) debug("LRU picked replacement block 0x%04x", (long)(repl->tag));
  1078. }
  1079.  
  1080. // the block "repl" will be removed and replaced; in code, this means it will its data overwritten with the new block's data,
  1081. // so move it up to the front already (MRU position for LRU policy, first position for FIFO)
  1082. update_way_list(&cp->sets[set], repl, Head);
  1083. if(is_tracking_block(cp, addr)){
  1084. debug("Moving LRU-chosen block 0x%04x to head of way list (MRU position)", (long)(repl->tag));
  1085. debug_dump_set(cp, addr);
  1086. }
  1087.  
  1088. break;
  1089.  
  1090. case Random:
  1091.  
  1092. // if CBR didn't find a replacement line, let the default replacement policy pick one
  1093. if(repl == NULL)
  1094. {
  1095. // just pick a random block to be replaced, the way ordering list is not used
  1096. int bindex = myrand() & (cp->assoc - 1);
  1097. repl = CACHE_BINDEX(cp, cp->sets[set].blks, bindex);
  1098. cp->evictions_policy++;
  1099. }
  1100. break;
  1101.  
  1102. default:
  1103. panic("bogus replacement policy");
  1104.  
  1105. }
  1106.  
  1107. //}
  1108.  
  1109. /* -- at this point, the replacement block is known (repl) ---------------------------- */
  1110.  
  1111. // update the prediction table by y's information (y = replacement line):
  1112. // Index the table using y.hashedPC and y's line address
  1113. int y_hashedPC = repl->cbr_line_info.hashed_pc;
  1114.  
  1115. // the line address of y is formed as the tag bits + the set bits + all 0's for the offset bits
  1116. // the tag bits for each cache line are stored in the cache line structure itself; the set is determined
  1117. // by the set it's being replaced from (otherwise it wouldn't have been placed in that set in the first place)
  1118. // thus, we need to combine y's (ie. repl's) tag bits with the current set bits
  1119. // fortunately, simplescalar provides a handy macro to do just that.
  1120. md_addr_t y_lineAddr = CACHE_MK_BADDR(cp, repl->tag, set);
  1121.  
  1122. if(cp->cbr_policy == AIP){
  1123.  
  1124. word_t max_counter = repl->cbr_line_info.max_counter_present;
  1125. bool_t confidence = (repl->cbr_line_info.max_counter_present == repl->cbr_line_info.max_counter_past ? TRUE : FALSE);
  1126.  
  1127. if(!(repl->status & CACHE_BLK_VALID)){
  1128.  
  1129. if(is_tracking_block(cp, addr)){
  1130. debug("Not storing block to be replaced's info in prediction table, invalid block");
  1131. }
  1132.  
  1133. } else {
  1134.  
  1135. // store new information in table
  1136. if(is_tracking_block(cp, addr)){
  1137. //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);
  1138. debug("Storing the block to be replaced's info in the prediction table");
  1139. debug("History entry(hashedPC = 0x%02x, lineAddr = 0x%08x -> hashed 0x%02x) <- maxCstored = %02d, confidence = %d",
  1140. y_hashedPC,
  1141. (long) y_lineAddr,
  1142. (long)(CBR_HASH_PC8(y_lineAddr)),
  1143. max_counter,
  1144. confidence
  1145. );
  1146. }
  1147.  
  1148. // y.maxCstored = y.maxCpresent
  1149. //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].max_counter = repl->cbr_line_info.max_counter_present;
  1150.  
  1151. // if(y.maxCpresent == y.maxCpast)
  1152. // y.conf_stored = 1
  1153. // else
  1154. // y.conf_stored = 0
  1155. //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);
  1156.  
  1157. /*cbr_pred_table_set_entry(cp,
  1158. y_hashedPC, y_lineAddr,
  1159. repl->cbr_line_info.max_counter_present,
  1160. (repl->cbr_line_info.max_counter_present == repl->cbr_line_info.max_counter_past ? TRUE : FALSE)
  1161. );*/
  1162.  
  1163. cbr_pred_table_set_entry(cp,
  1164. y_hashedPC, y_lineAddr,
  1165. max_counter,
  1166. confidence
  1167. );
  1168.  
  1169. }
  1170.  
  1171. } else if(cp->cbr_policy == LvP){
  1172.  
  1173. word_t max_counter = repl->cbr_line_info.counter;
  1174. bool_t confidence = (repl->cbr_line_info.counter == repl->cbr_line_info.max_counter_past ? TRUE : FALSE);
  1175.  
  1176. // y.maxCstored = y.C
  1177. //cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(y_hashedPC, y_lineAddr)].max_counter = repl->cbr_line_info.counter;
  1178.  
  1179. // if(y.maxCpast == y.C)
  1180. // y.conf_stored = 1
  1181. // else
  1182. // y.conf_stored = 0
  1183. //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);
  1184.  
  1185. cbr_pred_table_set_entry(cp,
  1186. y_hashedPC, y_lineAddr,
  1187. max_counter,
  1188. confidence
  1189. );
  1190.  
  1191. }
  1192.  
  1193. /* remove this block from the hash bucket chain, if hash exists
  1194. * why? remember: the repl block will house the new block which will have a different tag.
  1195. * Since the hash table is indexed by tag, this would leave us with an inconsistent hash table */
  1196. if(cp->hsize) unlink_htab_ent(cp, &cp->sets[set], repl);
  1197.  
  1198. /* blow away the last block to hit */
  1199. cp->last_tagset = 0;
  1200. cp->last_blk = NULL;
  1201.  
  1202. /* write back replaced block data */
  1203. if(repl->status & CACHE_BLK_VALID) {
  1204.  
  1205. // amount of replacements is only updated when the victim line is a valid cache line,
  1206. // ie. that contains valid previous content. If the victim were not valid, then its content
  1207. // was just dead space, and so we wouldn't be "replacing" anything other than dead space
  1208. // (which doesn't count as an actual replacement)
  1209. cp->replacements++;
  1210.  
  1211. // block/line address of the block that's getting evicted (see AIP above)
  1212. if(repl_addr) *repl_addr = CACHE_MK_BADDR(cp, repl->tag, set);
  1213.  
  1214. // don't replace the block until outstanding misses are satisfied
  1215. lat += BOUND_POS(repl->ready - now);
  1216.  
  1217. // stall until the bus to next level of memory is available
  1218. lat += BOUND_POS(cp->bus_free - (now + lat));
  1219.  
  1220. // track bus resource usage
  1221. cp->bus_free = MAX(cp->bus_free, (now + lat)) + 1;
  1222.  
  1223. /* the block to be replaced has changes; write them to the higher memory level
  1224. * first before replacing it
  1225. */
  1226.  
  1227. if(repl->status & CACHE_BLK_DIRTY) {
  1228. // write back the cache block
  1229. cp->writebacks++;
  1230. lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, repl->tag, set), cp->bsize, repl, now + lat);
  1231. }
  1232.  
  1233. }
  1234.  
  1235. // update block tags
  1236. repl->tag = tag;
  1237. repl->status = CACHE_BLK_VALID; // newly loaded block is always valid (dirty bit set on update)
  1238.  
  1239. // read new data block
  1240. lat += cp->blk_access_fn(Read, CACHE_BADDR(cp, addr), cp->bsize, repl, now + lat);
  1241.  
  1242. // copy data out of cache block
  1243. if(cp->balloc) {
  1244. CACHE_BCOPY(cmd, repl, bofs, p, nbytes);
  1245. }
  1246.  
  1247. // update dirty status
  1248. if(cmd == Write) repl->status |= CACHE_BLK_DIRTY;
  1249.  
  1250. // get user block data, if requested and it exists
  1251. if(udata) *udata = repl->user_data;
  1252.  
  1253. // update block status
  1254. repl->ready = now + lat;
  1255.  
  1256. // link this entry back into the hash table
  1257. if(cp->hsize) link_htab_ent(cp, &cp->sets[set], repl);
  1258.  
  1259. /* --------------------------------------------------------------------- */
  1260.  
  1261. // note: at this point repl has been updated with the new cache line information;
  1262. // thus, at this point, x = repl
  1263.  
  1264. int x_hashedPC = CBR_HASH_PC8(regs->regs_PC);
  1265. md_addr_t x_lineAddr = CACHE_MK_BADDR(cp, tag, set);
  1266. struct cbr_pred_table_entry_t* pred_table_entry;
  1267.  
  1268. /* AIP: read history from prediction table */
  1269. if(cp->cbr_policy == AIP){
  1270.  
  1271. /* from the paper (x = accessed cache line):
  1272. * Index the prediction table using x.hashedPC and x's line address.
  1273. * x.hashedPC is obtained by performing 8-bit XOR to the instruction PC that causes the miss to x
  1274. *
  1275. * x.C = x.maxCpresent = 0
  1276. * x.maxCpast = x.maxCstored
  1277. * x.conf = x.conf_stored
  1278. */
  1279.  
  1280. pred_table_entry = cbr_get_pred_table_element(cp, x_hashedPC, x_lineAddr);
  1281.  
  1282. repl->cbr_line_info.counter = 0;
  1283. repl->cbr_line_info.hashed_pc = x_hashedPC;
  1284. repl->cbr_line_info.max_counter_present = 0;
  1285. /*repl->cbr_line_info.max_counter_past = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter;
  1286. repl->cbr_line_info.confidence = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence;*/
  1287. repl->cbr_line_info.max_counter_past = pred_table_entry->max_counter;
  1288. repl->cbr_line_info.confidence = pred_table_entry->confidence;
  1289.  
  1290. if(is_tracking_block(cp, addr)){
  1291. debug("Initializing replaced block's AIP parameters");
  1292. debug("History entry(PC = 0x%08x -> hashedPC = 0x%02x, lineAddr = 0x%08x -> hashed 0x%02x): maxCstored = %02d, confidence = %d",
  1293. (long) regs->regs_PC,
  1294. x_hashedPC,
  1295. (long) x_lineAddr,
  1296. (long)(CBR_HASH_PC8(x_lineAddr)),
  1297. /*cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter,
  1298. cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence*/
  1299. pred_table_entry->max_counter,
  1300. pred_table_entry->confidence
  1301. );
  1302. debug(" -> counter = 0, hashed_pc = 0x%02x, maxCpresent = 0, maxCpast = %02d, confidence = %d",
  1303. x_hashedPC,
  1304. /*cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter,
  1305. cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence*/
  1306. pred_table_entry->max_counter,
  1307. pred_table_entry->confidence
  1308. );
  1309. debug_dump_set(cp, addr);
  1310. }
  1311.  
  1312. } else if(cp->cbr_policy == LvP){
  1313.  
  1314. /* from the paper (x = accessed cache line):
  1315. * Index the prediction table using x.hashedPC and x's line address.
  1316. * x.hashedPC is obtained by performing 8-bit XOR to the instruction PC that causes the miss to x
  1317. *
  1318. * x.C = 0
  1319. * x.maxCpast = x.maxCstored
  1320. * x.conf = x.conf_stored
  1321. */
  1322.  
  1323. pred_table_entry = cbr_get_pred_table_element(cp, x_hashedPC, x_lineAddr);
  1324.  
  1325. repl->cbr_line_info.counter = 0;
  1326. repl->cbr_line_info.hashed_pc = x_hashedPC;
  1327. /*repl->cbr_line_info.max_counter_past = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].max_counter;
  1328. repl->cbr_line_info.confidence = cp->cbr_pred_table->entries[CBR_PRED_TABLE_INDEX(x_hashedPC, x_lineAddr)].confidence;*/
  1329. repl->cbr_line_info.max_counter_past = pred_table_entry->max_counter;
  1330. repl->cbr_line_info.confidence = pred_table_entry->confidence;
  1331.  
  1332. }
  1333.  
  1334. // return latency of the operation
  1335. return lat;
  1336.  
  1337.  
  1338.  
  1339.  
  1340. /* -- CACHE HIT ----------------------------------------- */
  1341. // "blk" holds the hit cache line at this point
  1342.  
  1343. cache_hit_common: /* common hit handler */
  1344.  
  1345. cp->hits++;
  1346.  
  1347. /* if we need to calculate a histogram, do it nao */
  1348. if(cp->stack_dist_histogram){
  1349.  
  1350. int stack_dist = cbr_get_way_position(cp, &cp->sets[set], blk);
  1351. assert(stack_dist >= 0);
  1352. cp->stack_dist_histogram[stack_dist]++;
  1353.  
  1354. }
  1355.  
  1356. if(is_tracking_block(cp, addr)){
  1357. debug("%shit on address 0x%08x, block 0x%08x", (fast_cache_hit ? "fast" : ""), (long) addr, (long) line_addr);
  1358. }
  1359.  
  1360. /* AIP */
  1361. if(cp->cbr_policy == AIP){
  1362.  
  1363. // "if the access is a hit, reset x's counter after recording the new threshold maximum"
  1364. blk->cbr_line_info.max_counter_present = MAX(blk->cbr_line_info.counter, blk->cbr_line_info.max_counter_present);
  1365. blk->cbr_line_info.counter = 0;
  1366.  
  1367. if(is_tracking_block(cp, addr)){
  1368. debug("updating maxCpresent = %02d, counter = %02d", blk->cbr_line_info.max_counter_present, blk->cbr_line_info.counter);
  1369. // debug_dump performed after the dirty bit has been set; see cache hit handlers
  1370. }
  1371.  
  1372. } else if(cp->cbr_policy == LvP){
  1373.  
  1374. // "if the access is a hit":
  1375. // x.C = x.C + 1
  1376. blk->cbr_line_info.counter = MIN(blk->cbr_line_info.counter + 1, CBR_COUNTER_MAX);
  1377.  
  1378. }
  1379.  
  1380. if(fast_cache_hit){
  1381. goto cache_fast_hit;
  1382. } else {
  1383. goto cache_hit;
  1384. }
  1385.  
  1386.  
  1387. cache_hit: /* slow hit handler */
  1388.  
  1389.  
  1390. /* copy data out of cache block, if block exists */
  1391. if(cp->balloc) {
  1392. CACHE_BCOPY(cmd, blk, bofs, p, nbytes);
  1393. }
  1394.  
  1395. /* update dirty status */
  1396. if(cmd == Write) blk->status |= CACHE_BLK_DIRTY;
  1397.  
  1398. /* if LRU replacement and this is not the first element of list, reorder */
  1399. if(blk->way_prev && cp->policy == LRU) {
  1400. /* move this block to head of the way (MRU) list */
  1401. update_way_list(&cp->sets[set], blk, Head);
  1402.  
  1403. if(is_tracking_block(cp, addr)){
  1404. debug("Moving hit block 0x%04x to head of way list (MRU position)", (long)(blk->tag));
  1405. }
  1406.  
  1407. }
  1408.  
  1409. if(is_tracking_block(cp, addr)) debug_dump_set(cp, addr);
  1410.  
  1411. /* tag is unchanged, so hash links (if they exist) are still valid */
  1412.  
  1413. /* record the last block to hit */
  1414. cp->last_tagset = CACHE_TAGSET(cp, addr);
  1415. cp->last_blk = blk;
  1416.  
  1417.  
  1418. /* get user block data, if requested and it exists */
  1419. if(udata) *udata = blk->user_data;
  1420.  
  1421.  
  1422. /* return first cycle data is available to access */
  1423. return (int) MAX(cp->hit_latency, (blk->ready - now));
  1424.  
  1425.  
  1426.  
  1427.  
  1428. cache_fast_hit: /* fast hit handler */
  1429.  
  1430. /* copy data out of cache block, if block exists */
  1431. if(cp->balloc) {
  1432. CACHE_BCOPY(cmd, blk, bofs, p, nbytes);
  1433. }
  1434.  
  1435. /* update dirty status */
  1436. if(cmd == Write) blk->status |= CACHE_BLK_DIRTY;
  1437.  
  1438. if(is_tracking_block(cp, addr)) debug_dump_set(cp, addr);
  1439.  
  1440. /* this block hit last, no change in the way list */
  1441.  
  1442. /* tag is unchanged, so hash links (if they exist) are still valid */
  1443.  
  1444. /* get user block data, if requested and it exists */
  1445. if(udata) *udata = blk->user_data;
  1446.  
  1447.  
  1448. /* record the last block to hit */
  1449. cp->last_tagset = CACHE_TAGSET(cp, addr);
  1450. cp->last_blk = blk;
  1451.  
  1452.  
  1453. /* return first cycle data is available to access */
  1454. return (int) MAX(cp->hit_latency, (blk->ready - now));
  1455.  
  1456.  
  1457. }
  1458.  
  1459. /* return non-zero if block containing address ADDR is contained in cache
  1460. CP, this interface is used primarily for debugging and asserting cache
  1461. invariants */
  1462. int /* non-zero if access would hit */
  1463. cache_probe(
  1464. struct cache_t *cp, /* cache instance to probe */
  1465. md_addr_t addr /* address of block to probe */
  1466. )
  1467. {
  1468.  
  1469. md_addr_t tag = CACHE_TAG(cp, addr);
  1470. md_addr_t set = CACHE_SET(cp, addr);
  1471. struct cache_blk_t *blk;
  1472.  
  1473.  
  1474. /* permissions are checked on cache misses */
  1475.  
  1476. if(cp->hsize) {
  1477.  
  1478. /* higly-associativity cache, access through the per-set hash tables */
  1479. int hindex = CACHE_HASH(cp, tag);
  1480.  
  1481. for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) {
  1482. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) return TRUE;
  1483. }
  1484.  
  1485. } else {
  1486.  
  1487. /* low-associativity cache, linear search the way list */
  1488. for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) {
  1489. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) return TRUE;
  1490. }
  1491.  
  1492. }
  1493.  
  1494. /* cache block not found */
  1495. return FALSE;
  1496.  
  1497. }
  1498.  
  1499. /* flush the entire cache, returns latency of the operation */
  1500. unsigned int /* latency of the flush operation */
  1501. cache_flush(
  1502. struct cache_t *cp, /* cache instance to flush */
  1503. tick_t now /* time of cache flush */
  1504. )
  1505. {
  1506.  
  1507. int i, lat = cp->hit_latency; /* min latency to probe cache */
  1508. struct cache_blk_t *blk;
  1509.  
  1510. /* blow away the last block to hit */
  1511. cp->last_tagset = 0;
  1512. cp->last_blk = NULL;
  1513.  
  1514. /* no way list updates required because all blocks are being invalidated */
  1515. for(i = 0; i < cp->nsets; i++) {
  1516. for(blk = cp->sets[i].way_head; blk; blk = blk->way_next) {
  1517.  
  1518. if(blk->status & CACHE_BLK_VALID) {
  1519.  
  1520. cp->invalidations++;
  1521. blk->status &= ~CACHE_BLK_VALID; // mark as invalid
  1522.  
  1523. if(blk->status & CACHE_BLK_DIRTY) {
  1524.  
  1525. /* write back the invalidated block */
  1526. cp->writebacks++;
  1527. lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, blk->tag, i), cp->bsize, blk, now + lat);
  1528.  
  1529. }
  1530.  
  1531. }
  1532.  
  1533. }
  1534. }
  1535.  
  1536. /* return latency of the flush operation */
  1537. return lat;
  1538. }
  1539.  
  1540. /* flush the block containing ADDR from the cache CP, returns the latency of
  1541. the block flush operation */
  1542. unsigned int /* latency of flush operation */
  1543. cache_flush_addr(struct cache_t *cp, /* cache instance to flush */
  1544. md_addr_t addr, /* address of block to flush */
  1545. tick_t now) /* time of cache flush */
  1546. {
  1547. md_addr_t tag = CACHE_TAG(cp, addr);
  1548. md_addr_t set = CACHE_SET(cp, addr);
  1549. struct cache_blk_t *blk;
  1550. int lat = cp->hit_latency; /* min latency to probe cache */
  1551.  
  1552. if(cp->hsize) {
  1553.  
  1554. /* higly-associativity cache, access through the per-set hash tables */
  1555. int hindex = CACHE_HASH(cp, tag);
  1556.  
  1557. for(blk = cp->sets[set].hash[hindex]; blk; blk = blk->hash_next) {
  1558. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) break;
  1559. }
  1560.  
  1561. } else {
  1562.  
  1563. /* low-associativity cache, linear search the way list */
  1564. for(blk = cp->sets[set].way_head; blk; blk = blk->way_next) {
  1565. if(blk->tag == tag && (blk->status & CACHE_BLK_VALID)) break;
  1566. }
  1567.  
  1568. }
  1569.  
  1570. if(blk) {
  1571.  
  1572. cp->invalidations++;
  1573. blk->status &= ~CACHE_BLK_VALID;
  1574.  
  1575. /* blow away the last block to hit */
  1576. cp->last_tagset = 0;
  1577. cp->last_blk = NULL;
  1578.  
  1579. if(blk->status & CACHE_BLK_DIRTY) {
  1580. /* write back the invalidated block */
  1581. cp->writebacks++;
  1582. lat += cp->blk_access_fn(Write, CACHE_MK_BADDR(cp, blk->tag, set), cp->bsize, blk, now + lat);
  1583. }
  1584. /* move this block to tail of the way (LRU) list */
  1585. update_way_list(&cp->sets[set], blk, Tail);
  1586.  
  1587. }
  1588.  
  1589. /* return latency of the operation */
  1590. return lat;
  1591.  
  1592. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!