#include <stdio.h> //printf()
#include <time.h> //clock_t
#include <stdlib.h> //atoi()
#include <getopt.h> //getopt()
#include "cachelab.h"
typedef struct
{
unsigned tag; /* tag bits per line */
_Bool valid; /* 1 valid bit per line */
clock_t stamp; /* time stamp, to implement LRU algorithm */
}cache_line;
cache_line** init_cache(int s, int E) {
/* cache size = S(=2^s sets per cache) * E(lines per set) * B(=2^b bytes per block)
* we use cache_line_size here instead of B
*/
int sets_cnt = 1<<s, cache_line_size = sizeof(cache_line);
/* cache_line** cache is a two dimensional array, and cache[i] means
* the ith set in the cache.
*/
cache_line** cache = (cache_line**) malloc(cache_line_size * sets_cnt);
for(int i = 0; i < sets_cnt; ++i) {
int set_size = cache_line_size * E;
//initial the ith set
cache[i] = (cache_line*) malloc(set_size);
//the for loop can be replaced by
//memset(cache[i], 0, set_size) //#include <string.h>
for(int j = 0; j < E; ++j) {
cache[i][j].tag = 0;
cache[i][j].valid = 0;
cache[i][j].stamp = 0;
}
}
return cache;
}
void free_cache(cache_line** cache, int s) {
int sets_cnt = 1<<s;
for(int i = 0; i < sets_cnt; ++i) {
free(cache[i]);
}
free(cache);
}
_Bool set_insert(cache_line* set, unsigned long tag, int E) {
int old_stamp_index = 0;
for(int i = 0; i < E; ++i) {
if(set[i].stamp < set[old_stamp_index].stamp) old_stamp_index = i;
if(!set[i].valid) {
set[i].valid = 1;
set[i].tag = tag;
set[i].stamp = clock();
return 0;
}
}
//all lines valid, evict the Least-Recent-Used
set[old_stamp_index].tag = tag;
set[old_stamp_index].stamp = clock();
return 1;
}
//hit=1, miss=0
_Bool set_inspect(cache_line* set, unsigned tag, int E) {
for(int i = 0; i < E; ++i) {
if(set[i].valid && set[i].tag == tag) {
//hit, renew time stamp
set[i].stamp = clock();
return 1;
}
}
//miss
return 0;
}
void cache_simulate(cache_line** cache, char type, unsigned address,
int bytes, int s, int E, int b, int v,
int* hits, int* misses, int* evictions) {
//address = tag + set index + block offset
//unsigned int has 32 bits
unsigned tag = address>>s>>b, set_index = address<<(32-b-s)>>(32-s);
cache_line* set = cache[set_index];
_Bool hit_or_not = set_inspect(set, tag, E), eviction_or_not = 0;
if(!hit_or_not) {
eviction_or_not = set_insert(set, tag, E);
}
//print detailed info
if(v) {
printf("%c %x,%d", type, address, bytes);
if(hit_or_not) {
printf(" hit");
} else {
if(eviction_or_not) printf(" eviction");
printf(" miss");
}
if(type == 'M') printf(" hit");
printf("\n");
}
//summary
if(type == 'M') ++*hits;
if(hit_or_not) ++*hits;
else ++*misses;
if(eviction_or_not) ++*evictions;
}
void print_usage(){
printf(
"Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>\n"
"Options\n"
" -h Print this help message.\n"
" -v Optional verbose flag.\n"
" -s <num>: Number of set index bits.\n"
" -E <num>: Number of lines per set.\n"
" -b <num>: Number of block offset bits.\n"
" -t <file>: Trace file.\n"
"\n"
"Exampes:\n"
" linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n"
" linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n"
);
}
int main(int argc, char** argv) {
//no arg
if(argc == 1) {
printf("./csim-ref: Missing required command line argument\n");
print_usage();
return 0;
}
/* access command line */
int s, E, b, v = 0;
char ch;
char* file_path;
while((ch = getopt(argc, argv, "s:E:b:t:vh")) != -1) {
switch(ch) {
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
file_path = optarg;
break;
case 'v':
v = 1;
break;
case 'h':
print_usage();
return 0;
default:
break;
}
}
//initialize cache
cache_line** cache = init_cache(s, E);
//open file
FILE* fp = fopen(file_path, "r");//r: read only
if(!fp) {
printf("%s: No such file or directory\n", file_path);
return 1;
}
//file format: S 7ff000398,8
/* read file */
char type;
unsigned address;
int bytes, hits = 0, misses = 0, evictions = 0;
while(fscanf(fp, " %c %x,%d", &type, &address, &bytes) != EOF) {
if(type == 'I') continue;
//enter core function
cache_simulate(cache, type, address, bytes, s, E, b, v,
&hits, &misses, &evictions);
}
fclose(fp);
printSummary(hits, misses, evictions);
free_cache(cache, s);
return 0;
}
气膜阻力/总阻力=(1/KG)/(1/kG)
这是csapp里面关于callee-saved registers怎么用的讲解。当时看得还是不明就里，现在已经做了2个汇编相关的lab，才明白它确实讲得非常清楚。