CSAPP實驗四——cache lab實驗（一）

在學完《深入理解計算機系統(CSAPP)》第六章有關存盤器層次結構方面的知識后，就可以著手做cache lab的實驗了，實驗分為兩個部分，這篇博客只聊聊自己在做第一部分的一點心得，思路部分也是參考了網上其他大神的想法，如果有寫的不對的地方，歡迎大家在評論區指出，

cache lab的第一個實驗是寫一個程式模擬高速快取的行為，需要注意的是這個程式僅僅需要模擬判斷命中、替換演算法和犧牲行的驅逐三個功能，不需要考慮快取里塊中存盤的所需要讀寫的資料到底是什么，最后呈現的方式也是讀取一系列記憶體讀取的指令，給出命中、不命中和驅逐次數，

壓縮檔案中包含了一個csim-ref的可執行檔案，我們寫的程式csim功能上需要與這個csim-ref基本類似，至少對于相同記憶體讀寫時命中、不命中和驅逐次數三個數值相同，所以我們不妨看看csim-ref的基本情況，

根據壓縮包里提供的幫助檔案，可以知道在控制臺輸入的引數格式如下：

其中加上引數v后，會把每一條指令是什么型別（L, M, S)，讀寫記憶體大小和是否命中是否驅逐的資訊逐行逐指令一一顯示，而如果不加引數v只會顯示做完所有指令后統計的命中、不命中和驅逐次數的和，

再來看指令的格式

I表示讀指令，在這個實驗中不需要考慮，L表示加載、S表示存盤，由于這個實驗只需要模擬命中和驅逐次數這些，與記憶體塊內數值是什么并沒有關系，所以可以將L和S看成同一個對快取的操作，M表示修改，對應一個加載一個存盤，所以可以看成兩個操作，

理清思路后就可以著手碼代碼了，

//行
typedef struct{
    int valid;   //一行的有效位（1表示有效）
    int tag;	 //一行的標識位
    int LRUcount;    //LRU替換優先級(越大替換優先級越高）	
}Line;

//組
typedef struct{
    Line* lines;  
}Set;

//快取
typedef struct{
    Set* sets;
    int numset;    //組數
    int numline;   //行數
}Sim_cache;

接著寫從控制臺得到對應的s, E, b等選項引數的輸入，參考了其他博客呼叫的是Linux C下的getopt()函式，需要包含頭檔案<getopt.h>，雖然<getopt.h>也是包含在<unistd.h>頭檔案中，但是我在make時一直報“隱式函式宣告錯誤”的問題，于是索性直接include<getopt.h>本身了，

getopt()函式原型如下：
int getopt(int argc,char * const argv[ ],const char * optstring);

其中第三個引數傳入的字串就是命令列輸入引數對應的格式，有冒號的表示該選項需要引數，全域變數optarg 即會指向此額外引數，這樣就可以得到s, E, b這些數值，
關于getopt()函式的詳細解釋可以參考鏈接

void getOpt(int argc, char** argv, int *verbose, int *s, int *E, int *b){
    char ch;
    while( (ch=getopt(argc, argv, "hvs:E:b:t:") )!= -1 ){
		switch(ch){
	    	case 'h' : printHelpMenu(); break;
	    	case 'v' : *verbose = 1; break;
	    	case 's' : *s = atoi(optarg); break;
	    	case 'E' : *E = atoi(optarg); break;
	    	case 'b' : *b = atoi(optarg); break;
	    	case 't' : tracename = (char*)optarg; break;
	    	default : printHelpMenu(); exit(0);
		}
    }
}

依葫蘆畫瓢，模仿csim-ref的參考檔案寫出csim相應的列印幫助資訊函式，

void printHelpMenu(){
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n");
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n\n");
    printf("Examples:\n");
    printf("  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n");
    printf("  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n\n");
}

核心功能之間的邏輯關系和實作見下圖

其中紅色的標注judgeHit(), judgeFull(), Eviction()和updateLRU()分別是實作相應功能的四個函式，整個邏輯關系還需要用updateCache()一個大函式來整合，

//判斷是否命中
int judgeHit(Sim_cache* sim_cache, int set_idx, int curTag){
    int nl = sim_cache->numline;
    for(int i=0; i< nl ; i++){
		if(sim_cache->sets[set_idx].lines[i].valid == 1  && sim_cache->sets[set_idx].lines[i].tag == curTag){
	    //表示命中了，只需要更新LRU數值
	    updateLRU(sim_cache, set_idx, i);
	    return 1;
		}
    }
    return 0;
} 


//判斷這一組行是否滿了(都滿了回傳-1）
int judgeFull(Sim_cache* sim_cache, int set_idx){
    /*如果這一組中有行未滿，則回傳行號，如果行都被占用了則回傳-1*/
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
	    if (sim_cache->sets[set_idx].lines[i].valid == 0 )
	    return i;
    }
    return -1;
}

//組內行都滿了則尋找需要被替換的行
int Eviction(Sim_cache* sim_cache, int set_idx){
    /*找到組內LRU最大的行,回傳行號*/
    int replace_line=0; 
    int maxLRU = -1; 
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
		if (sim_cache->sets[set_idx].lines[i].LRUcount > maxLRU ){
	    	maxLRU = sim_cache->sets[set_idx].lines[i].LRUcount;
	    	replace_line = i;
		}
    }
    return replace_line;   
}

//更新LRU的數值
void updateLRU(Sim_cache *sim_cache, int set_idx, int line_idx){
    /*LRU越大表示下次越有可能覆寫它，最小為0（表示剛剛訪問）*/
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
		sim_cache->sets[set_idx].lines[i].LRUcount ++ ; //這一組其他的行都LRU都增1   
    }
    sim_cache->sets[set_idx].lines[line_idx].LRUcount = 0;       
}

//整合上面四個函式，實作每次讀寫快取的操作
void updateCache(Sim_cache* sim_cache, int set_idx, int curTag, int verbose){
    //整合一系列操作（判斷命中，未命中判斷是否需要進行行的替換）
    if(judgeHit(sim_cache, set_idx, curTag)){   //命中后操作
		hitcount++;
		if(verbose)  printf("hit  ");   
    }else{  
		misscount++;
		if(verbose)  printf("miss  ");
		//未命中先判斷是否有空行
		int replace_line = judgeFull(sim_cache, set_idx);
		if(replace_line != -1){
	    	sim_cache->sets[set_idx].lines[replace_line].valid = 1;
	    	sim_cache->sets[set_idx].lines[replace_line].tag = curTag;
	    	updateLRU(sim_cache, set_idx, replace_line);
		}else{
	    	evictioncount++;
	    	if(verbose)  printf("eviction  ");
	    	replace_line = Eviction(sim_cache, set_idx);
	    	sim_cache->sets[set_idx].lines[replace_line].valid = 1;
	    	sim_cache->sets[set_idx].lines[replace_line].tag = curTag;
	    	updateLRU(sim_cache, set_idx, replace_line);	    
		}
    }
}

每次進行讀寫操作時都改變組內所有行的LRU的數值大小，LRU越大表示下次越有可能覆寫它，剛剛訪問行的LRU設定為0，其余未被訪問的LRU都增1，

void initCache(int s, int E, int b, Sim_cache* sim_cache){
    if(s<=0 || E<=0 ) exit(0);
    //初始化sim_cache部分
    sim_cache-> numset = 2<<s;  //2^s次方組
    sim_cache-> numline = E;
    sim_cache->sets = (Set*) malloc(sizeof(Set) * sim_cache->numset);
    if(!sim_cache->sets)   exit(0);
    //初始化set部分
    for(int i=0; i< sim_cache-> numset; i++){
		sim_cache->sets[i].lines = (Line*)malloc(sizeof(Line) * sim_cache->numline);
		//初始化line部分
		for(int j=0; j<E; j++){
	    	sim_cache->sets[i].lines[j].valid = 0;
	    	sim_cache->sets[i].lines[j].LRUcount = 0;
		}
    }
}

其次由于核心函式中比較的標識位Tag和組號set_idx是由指令的地址得到的，需要有兩個轉換函式，

int getTag(int addr, int s, int b){
    addr = (unsigned) addr;
    return addr >> (s+b);
}

int getSet(int addr, int s, int b){
    int set = addr >> b;
    int mask = (1 << s)-1;
    return mask & set;
}

最后就是main函式啦，涉及到從檔案讀的操作，以及初始化initCache()和updateCache()函式的呼叫，

int main(int argc, char** argv)
{
    int s=0, E=0, b=0,verbose=0;    
    char option;
    Sim_cache sim_cache;
    unsigned long long addr;
    int size;
    getOpt(argc, argv, &verbose, &s, &E, &b);  //讀控制臺輸入
    initCache(s, E, b, &sim_cache);  //初始化cache
    printf("%s" ,tracename);
    FILE * pFile = fopen (tracename,"r"); 
    while(fscanf(pFile, " %c %llx,%d" , &option, &addr, &size)>0){
		if(option=='I') continue;
		int set_idx = getSet(addr,s,b);
		int curTag = getTag(addr,s,b);
		if(option=='L' || option=='S')
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
		if(option=='M'){
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
		}
		if(verbose==1) printf("\n");	
    }
    //fclose(pFile); 
    printSummary(hitcount, misscount, evictioncount);
    return 0;
}

最后make以下程式，得到的結果與csim-ref結果一樣，cache lab第一個實驗就算做完啦，