· 8 years ago · Jul 20, 2018, 08:42 AM
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 */
103static 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 */
132static void
133link_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 */
146enum 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 */
151static struct regs_t* regs = NULL;
152void cbr_set_regs(struct regs_t* regs_in){
153 regs = regs_in;
154}
155
156void 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
166struct 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
173void 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 */
183void 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 */
218bool_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
226bool_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 */
234int 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 */
253struct 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 */
299struct 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 */
306struct 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 */
313static void
314update_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
396char* 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
411char* 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 */
429struct cache_t * /* pointer to cache created */
430cache_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 */
617enum cache_policy /* replacement policy enum */
618cache_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
635enum cache_cbr_policy /* CBR policy enum */
636cache_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) */
651int 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 */
690void
691cache_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 */
699void
700cache_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 */
773void
774cache_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/*
796static long accessed_blocks_counter = 0;
797static md_addr_t accessed_blocks[100000];
798
799bool_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
811void 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
818bool_t is_cbr_cache(struct cache_t* cp){
819 return (cp->cbr_policy != None);
820}
821
822bool_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
834void 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 */
881unsigned int /* latency of access in cycles */
882cache_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
1343cache_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
1387cache_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
1428cache_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 */
1462int /* non-zero if access would hit */
1463cache_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 */
1500unsigned int /* latency of the flush operation */
1501cache_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 */
1542unsigned int /* latency of flush operation */
1543cache_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}