經過三次重寫,和合計30多個小時的開發,終於把這個簡單的邏輯做完了。(自己太笨) 因為剛剛接觸C,寫的代碼實現方式肯定有不對的地方,邏輯上可能也有疏漏,如果有看官發現問題還望及時給予指正,謝謝。 一、整體概括: 1.1目標: 維護一個單獨的緩存空間,該空間是低一級存儲的緩存。緩存的大小比低級存儲的大 ...
經過三次重寫,和合計30多個小時的開發,終於把這個簡單的邏輯做完了。(自己太笨)
因為剛剛接觸C,寫的代碼實現方式肯定有不對的地方,邏輯上可能也有疏漏,如果有看官發現問題還望及時給予指正,謝謝。
一、整體概括:
1.1目標:
維護一個單獨的緩存空間,該空間是低一級存儲的緩存。緩存的大小比低級存儲的大小要小很多,通過一個邏輯將底層存儲的數據抽到緩存中的一個位置。
1.2 實現思路:
通過閱讀《深入理解電腦系統》一書,瞭解低級存儲與緩存之間關聯規則是基於存儲地址的,通過一個地址映射的規則,將低級存儲的地址映射到緩存的制定位置。
1.2.1 存儲:
存儲是由一個個位構成的,每個位都有一個對應的地址,地址的大小取決於電腦的字長。
1.2.2 低級存儲:
在這次的設計中低級存儲只是一個抽象概念,實際上就是記憶體中的一塊空間,只不過我通過映射值將低級存儲的地址改為從F000開始的地址。
1.2.3 緩存:
緩存是比低級存儲小得多的集合,因為存儲越大定址的時間越長,所以需要一個小的緩存來存儲處理器近期使用到的數據。
這次設計中的緩存也只是一個抽象概念,也是記憶體的一塊空間,也是通過映射值將緩存的地址改為A000開始的地址。
如何將低級存儲的地址映射到緩存——緩存模型:
緩存模型主要分——組、行、緩存單元
1.2.3.1 組
在邏輯上沒有體現,知識對地址進行切割並劃分了一個範圍,是在映射邏輯上有關,在實際記憶體中不會存儲。
1.2.3.2 行
也是一個邏輯體現,主要是為了更好的提升緩存的定址效率而設置的思想。
1.2.3.3 緩存單元:
實際存儲數據的對象,其中包含了標識、是否載入、以及位元組塊。
標識:標識是地址的一部分根據規則截取出來的,通過地址另一部分找到對應的組以後就會對其中的行進行遍歷,根據標識找到對應的行。
是否載入:用來標識該緩存是否已經載入數據。
位元組塊:用來存儲緩存數據。(大小可設置)
1.2.3.4 總結
通過上述的幾個對象,我們將緩存組織成了一個三層的結構,第一層是組、第二層是行、第三層是存儲單元。一個緩存可以有S個組,可以有E個行,每行只能有一個緩存單元。
1.2.4 全相連高速緩存、組相連高速緩存、直接映射高速緩存
全相連高速緩存就是緩存中只有一個組,有E個行的方式實現。
組相連高速緩存就是一個緩存中有S個組,E個行的實現方式。
直接映射高速緩存就是一個緩存中有S個組,1個行和1個緩存單元的實現方式。
1.2.5 緩存各項指標的設置:
組數、行數、緩存數據塊的大小的設置直接影響緩存的效率但也要根據實際情況,大小對不同的情況有不同的策略。
二、具體實現:
2.1 公共常量:
電腦字長:MemAddrLength
2.2 幾個核心對象:
2.2.1 硬體控制器:HWController
屬性:
存儲空間大小
1)寫方法(Write):傳入一個虛擬硬體地址(自己映射的,從F000開始)和一個長度。映射後寫入數據到記憶體。
2)讀方法(Read):傳入一個虛擬硬體地址和一個長度。映射後從記憶體讀出數據,並寫到一個新的記憶體空間並返回該指針。
2.2.2 緩存控制器:CacheController
1)緩存單元查詢器(CacheFinder):
2)讀方法(Read):傳入一個硬體虛擬地址和長度,在緩存中查找對應的單元,如果找不到從硬體中讀取數據寫到緩存,並將數據寫到記憶體新的空間中、返回該指針。
3)寫方法(Write):傳入一個硬體虛擬地址和長度,將數據寫入到硬體中再寫到緩存里(實際上緩存會有多種策略、直寫/不直寫等等)。
4)取下一個(Next):將傳入緩存單元指針移動到相鄰的下一個緩存單元,如果超出緩存範圍則返回0x00。
2.3 執行結果概述
返回四大部分:
1)總體介紹部分,會將地址空間、緩存的S、E、B、t幾個主要參數值顯示出來。
2)記憶體查看部分,會將初始化後虛擬硬體存儲和緩存存儲的值都寫出來。
3)緩存大小顯示
4)緩存讀值測試
下麵的集合是所有緩存單元的參數和右側緩存單元位元組塊中的數據。
上面的集合是根據指令從緩存中讀取出來的數據內容。
通過這兩個集合可以驗證讀取數據是否正確。
剩下沒解決的問題:
在寫緩存的時候,如果該組所有緩存單元都已經初始化了,就需要通過一個科學的方式選擇一個塊覆蓋或驅逐,目前是用隨機數,不太合理。
抽象不夠,沒有悟透和語言不熟導致很多復用問題比較多,有問題望指出。後續有時間我會繼續完善。
說不定有BUG,如果有客觀指正。
三、代碼
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <math.h> 4 #include <unistd.h> 5 6 /* 7 * 基本設定初始化 8 */ 9 const unsigned int _memSize = 1024; //記憶體大小(位元組) 10 const unsigned int _memAddrLength = 16;//地址長度 11 const unsigned int _cacheSize = 256;//緩存大小 12 13 /* 14 * 硬體控制器 15 */ 16 typedef struct HWController{ 17 unsigned long _memStartAddr; //start addr 0XF0 18 unsigned char* _memAddr; 19 unsigned long _memOffset; 20 21 unsigned char* (*Read)(unsigned long memOffset, unsigned long addr, unsigned long length); 22 unsigned char (*Write)(unsigned long memOffset, unsigned long addr, unsigned char *data, unsigned long length); 23 }; 24 25 /* 26 * 緩存控制器: 27 * 1)緩存單元集合指針 CacheUnitArrayPtr 28 * 2)緩存查詢函數 CacheFinder 29 * 3)緩存讀函數 Read 30 * 4)緩存寫函數 Write 31 */ 32 typedef struct CacheController { 33 unsigned int _s; 34 unsigned long _sMask; 35 unsigned int _S; 36 unsigned int _E; 37 unsigned int _b; 38 unsigned long _bMask; 39 unsigned int _B; 40 unsigned int _t; 41 unsigned long _tMask; 42 unsigned int _C; 43 44 unsigned long _unitCount; 45 unsigned long _unitSize; 46 47 unsigned long _cacheSize; 48 unsigned long _cacheStartAddr; 49 unsigned char* _cacheMemAddr; 50 unsigned long _cacheOffset; 51 struct CacheUnit* CacheUnitArrayPtr; 52 53 struct CacheUnit* (*Next)(struct CacheController *ctrl,struct CacheUnit *unit); 54 struct CacheUnit* (*CacheFinder)(struct CacheController *ctrl,unsigned long Addr); 55 unsigned char* (*Read)(struct CacheController *ctrl,struct HWController *hwctrl,unsigned long addr, unsigned long length); 56 unsigned char (*Write)(struct CacheController *ctrl,struct HWController *hwctrl,unsigned long addr, unsigned char *data, unsigned long length); 57 }; 58 59 /* 60 * 緩存單元 61 * 1)數據塊集合指針 BlockArrayPtr; 62 * 2)t標誌位 tCode; 63 * 3)熱標識位 hot; 64 */ 65 typedef struct CacheUnit { 66 unsigned char* BlockArrayPtr; 67 unsigned long tCode; 68 unsigned char Hot; 69 }; 70 71 //HWController 72 unsigned char _hwWrite(unsigned long memOffset, unsigned long addr, unsigned char *data, unsigned long length){ 73 unsigned char* ptr = (unsigned char*)(memOffset + addr); 74 while(length--){ 75 *ptr = *data; 76 ptr++; 77 data++; 78 } 79 return 1; 80 } 81 unsigned char* _hwRead(unsigned long memOffset, unsigned long addr, unsigned long length){ 82 unsigned char *ptr = (unsigned char*)(memOffset + addr); 83 unsigned char *retPtr = malloc(length); 84 unsigned char *loopPtr = retPtr; 85 while(length--){ 86 *loopPtr = *ptr; 87 ptr++; 88 loopPtr++; 89 } 90 91 return retPtr; 92 } 93 struct HWController* GetHWCtroller(){ 94 struct HWController *ctrl = malloc(sizeof(struct HWController)); 95 void *rPtr = malloc(_memSize);//get ptr point to Memory Space. 96 (*ctrl)._memStartAddr = 0xF000; 97 (*ctrl)._memOffset = (unsigned long) (rPtr - (*ctrl)._memStartAddr); 98 (*ctrl)._memAddr = rPtr; 99 (*ctrl).Write = _hwWrite; 100 (*ctrl).Read = _hwRead; 101 102 unsigned char *ptr = rPtr; 103 int i = 0; 104 while( i < _memSize ){ 105 *ptr = i + 1000; 106 ptr++; 107 i++; 108 } 109 110 printf("==>Memory:\r\n startAddr:%X,offset:%X",(unsigned int)(*ctrl)._memStartAddr,(unsigned int)((*ctrl)._memOffset )); 111 112 return ctrl; 113 } 114 115 //CacheController 116 struct CacheUnit* _next(struct CacheController *ctrl,struct CacheUnit *unit){ 117 unit = (struct CacheUnit *)((unsigned long)unit + ctrl->_unitSize); 118 return unit >= (ctrl->_cacheSize + ctrl->_cacheMemAddr) ? 0x00 : unit; 119 } 120 struct CacheUnit* _cacheFinder(struct CacheController *ctrl,unsigned long addr){ 121 unsigned long _tBit = (addr&(*ctrl)._tMask)>>((*ctrl)._b+(*ctrl)._s); 122 unsigned long _sBit = (addr&(*ctrl)._sMask)>>((*ctrl)._b); 123 unsigned long _bBit = (addr&(*ctrl)._bMask); 124 125 // printf("\r\n\r\n====>Find Addr:%X \r\n tMask:%X,tVal:%X \t sMask:%X,sVal:%X \t bMask:%X,bVal:%X",addr,(*ctrl)._tMask,_tBit,(*ctrl)._sMask,_sBit,(*ctrl)._bMask,_bBit); 126 127 struct CacheUnit* _unit = (struct CacheUnit*)((*ctrl)._cacheStartAddr + ctrl->_cacheOffset + _sBit * ((*ctrl)._E * ctrl->_unitSize)); 128 int e = (*ctrl)._E; 129 while ( e-- ) 130 { 131 if((*_unit).tCode == _tBit){ 132 return _unit; 133 } 134 _unit = (struct CacheUnit *)(((unsigned long)_unit)+ ctrl->_unitSize); 135 } 136 return 0; 137 } 138 unsigned char* _cacheRead(struct CacheController *ctrl,struct HWController *hwctrl,unsigned long addr, unsigned long length){ 139 struct CacheUnit *unit = ctrl->CacheFinder(ctrl,addr); 140 //todo: 找時間把Loader抽象出來或者其他方式優化復用。 141 if(!unit || !(*unit).Hot){ 142 unsigned char *read = hwctrl->Read(hwctrl->_memOffset,addr,length); 143 ctrl->Write(ctrl,hwctrl,addr,read,length); 144 unit = ctrl->CacheFinder(ctrl,addr); 145 if(!unit || !(*unit).Hot){ 146 printf("\r\nERROR::can not load cache by %X !!!! \r\n" ,(unsigned int)addr); 147 exit(0); 148 } 149 } 150 unsigned char *memPtr = malloc(length); 151 unsigned char *memLoopPtr = memPtr; 152 unsigned char *blockPtr = (*unit).BlockArrayPtr + (ctrl->_bMask & addr); 153 unsigned long i = 0; 154 while(i < length){ 155 *memLoopPtr = *blockPtr; 156 memLoopPtr++; 157 blockPtr++; 158 if(blockPtr >= (*unit).BlockArrayPtr + (*ctrl)._B){ 159 unit = ctrl->CacheFinder(ctrl,addr + i + 1); 160 if(!unit || !(*unit).Hot){ 161 printf("\r\nERROR::can not load cache by %X !!!! \r\n" ,(unsigned int)(addr + i)); 162 exit(0); 163 } 164 blockPtr = unit->BlockArrayPtr; 165 } 166 i++; 167 } 168 return memPtr; 169 } 170 unsigned char _cacheWrite(struct CacheController *ctrl,struct HWController *hwctrl,unsigned long addr, unsigned char *data, unsigned long length){ 171 //寫入底層記憶體先。 172 hwctrl->Write(hwctrl->_memOffset,addr,data,length); 173 //寫入緩存 174 unsigned char *ptr = data; 175 unsigned long i = 0; 176 177 while(i<length){ 178 struct CacheUnit *unit = ctrl->CacheFinder(ctrl,addr + i); 179 if(!unit||!unit->Hot) 180 { 181 unsigned long startAddr = (unsigned long)(ctrl->_cacheMemAddr + (((ctrl->_sMask & (addr + i)) >> ((*ctrl)._b)) * ctrl->_E) * ctrl->_unitSize) ; 182 unsigned long endAddr = (unsigned long)(ctrl->_cacheMemAddr + (((ctrl->_sMask & (addr + i)) >> ((*ctrl)._b)) * ctrl->_E)) + ctrl->_E * ctrl->_unitSize; 183 unit = (struct CacheUnit *)startAddr; 184 int hit = 0; 185 while(unit){ 186 if(!unit->Hot) 187 { 188 hit=1; 189 break; 190 } 191 unit = ctrl->Next(ctrl,unit); 192 if((unsigned long)unit >= endAddr){ 193 break; 194 } 195 } 196 if(!hit) 197 { 198 printf("\r\rnhit!!!\r\n"); 199 int rm = rand() % ( ctrl->_E ); 200 unit = startAddr + rm * ctrl->_unitSize; 201 } 202 unit->tCode = ((addr + i) & ctrl->_tMask) >> ((*ctrl)._b+(*ctrl)._s); 203 unit->Hot = 1; 204 } 205 unsigned char *blockPtr = unit->BlockArrayPtr + ((addr+i)&ctrl->_bMask); 206 *blockPtr = *ptr; 207 ptr++; 208 i++; 209 } 210 } 211 struct CacheController* GetCacheController(unsigned int _memAddrLength, unsigned int cacheSize, unsigned int blockSize,unsigned int E){ 212 struct CacheController *cache = malloc(sizeof(struct CacheController)); 213 (*cache)._b = (unsigned int)log2(blockSize); 214 (*cache)._B = blockSize; 215 (*cache)._bMask = (unsigned long) pow(2,(*cache)._b) - 1; 216 217 (*cache)._E = E; 218 219 (*cache)._S = cacheSize / (*cache)._B / (*cache)._E; 220 (*cache)._s = (unsigned int)log2((*cache)._S); 221 (*cache)._sMask = (unsigned long) pow(2,((*cache)._b + (*cache)._s)) - (*cache)._bMask - 1; 222 223 (*cache)._C = (*cache)._B * (*cache)._E * (*cache)._S; 224 225 (*cache)._t = _memAddrLength - (*cache)._s - (*cache)._b; 226 (*cache)._tMask = (unsigned long) pow(2,_memAddrLength) - (*cache)._bMask - (*cache)._sMask - 1; 227 228 (*cache)._unitCount = (*cache)._E * (*cache)._S; 229 (*cache)._unitSize = sizeof(struct CacheUnit) + (*cache)._B; 230 231 (*cache)._cacheSize = (*cache)._unitSize * (*cache)._unitCount; 232 //apply mem 233 (*cache)._cacheMemAddr = malloc((*cache)._cacheSize); 234 (*cache)._cacheStartAddr = 0xA000; 235 (*cache)._cacheOffset = (unsigned long)((*cache)._cacheMemAddr - cache->_cacheStartAddr); 236 237 unsigned long counter = (*cache)._unitCount; 238 struct CacheUnit *unit = (struct CacheUnit*)(*cache)._cacheMemAddr; 239 240 while(counter){ 241 (*unit).Hot = 0x00; 242 (*unit).tCode = counter; 243 (*unit).BlockArrayPtr = (unsigned char *)(((unsigned long)unit) + sizeof(struct CacheUnit)); 244 int x; 245 for(x = 0;x < cache->_B ; x++){ 246 *(unit->BlockArrayPtr + x) = (unsigned char)x; 247 } 248 unit = (struct CacheUnit*)((*unit).BlockArrayPtr + (*cache)._B); 249 counter--; 250 } 251 (*cache).Next = _next; 252 (*cache).CacheFinder = _cacheFinder; 253 (*cache).Read = _cacheRead; 254 (*cache).Write = _cacheWrite; 255 256 printf("\r\n==>CacheSize:\r\n MemAddrLength = %d. C = %d, \r\nS = %d, E = %d, B = %d; \r\n s = %d, b = %d, t = %d",_memAddrLength,(*cache)._C,(*cache)._S,(*cache)._E,(*cache)._B,(*cache)._s,(*cache)._b,(*cache)._t); 257 printf("\r\ncacheAddr:%X,cacheStartAddr:%X, cacheOffset:%X, cacheSize:%d",(unsigned int)(*cache)._cacheMemAddr,(unsigned int)(*cache)._cacheStartAddr,(unsigned int)(*cache)._cacheOffset,(unsigned int) (*cache)._cacheSize); 258 printf("\r\nbMask:%x,sMask:%x,tMask:%x",(unsigned int)(*cache)._bMask,(unsigned int)(*cache)._sMask,(unsigned int)(*cache)._tMask); 259 260 return cache; 261 } 262 263 //utility 264 void PrintMem(char* title, unsigned long addr, unsigned long length,int split){ 265 printf("\r\n\r\n=====> title::%s:: Printing Mem %X,Length:%d <=======\r\n",title,(unsigned int)addr,(unsigned int)length); 266 unsigned char *ptr = (unsigned char *)addr; 267 268 int i = 0; 269 while(i < length){ 270 if( i % 16 == 0){ 271 printf("\r\n%d\t%X\t",i,(unsigned int)ptr); 272 } 273 else if( i > 0 && i % 4 == 0){ 274 printf("\t"); 275 } 276 printf("\t%X",*ptr); 277 ptr++; 278 i++; 279 } 280 } 281 void PrintCache(char* title, struct CacheController* ctrl){ 282 printf("\r\n\r\n=====> title::%s:: Printing Mem %X,Length:%d <=======\r\n",title,(unsigned int)(ctrl->_cacheStartAddr + ctrl->_cacheOffset),(unsigned int)ctrl->_unitCount); 283 284 struct CacheUnit *unit = ( struct CacheUnit *)(ctrl->_cacheStartAddr + ctrl->_cacheOffset); 285 unsigned char *blockPtr = unit->BlockArrayPtr; 286 int i = 0; 287 int j = 0; 288 while(i < ctrl->_unitCount){ 289 printf("\r\n--Unit%d[[tCode:%d,BlockPtr:%X,Hot:%d]] Blocks:\t",i+1,(unsigned int)unit->tCode,(unsigned int)unit->BlockArrayPtr,(unsigned int)unit->Hot); 290 j = 0; 291 while(j < ctrl->_B){ 292 printf("\t%X",(unsigned int)*blockPtr); 293 blockPtr++; 294 j++; 295 } 296 unit = (struct CacheUnit *)(((unsigned long)unit) + sizeof(struct CacheUnit) + ctrl->_B); 297 blockPtr = unit->BlockArrayPtr; 298 i++; 299 } 300 } 301 int main() { 302 printf("Hello, World!\n"); 303 struct HWController hwCtrl = *GetHWCtroller(); 304 struct CacheController cacheCtrl = *GetCacheController(_memAddrLength,_cacheSize,32,2); 305 306 //HW Unit Test 307 // PrintMem("",(unsigned long)hwCtrl._memAddr,16,0); 308 // unsigned char temp = 0xAA; 309 // unsigned char *data = &temp; 310 // hwCtrl.Write(hwCtrl._memOffset,0XF002,data,1); 311 // PrintMem(" HWMEM 0~16 ",(unsigned long)hwCtrl._memAddr,16,0); 312 // unsigned char *retData = hwCtrl.Read(hwCtrl._memOffset,0XF002,1); 313 // PrintMem(" HWMEM 0XF002 ",(unsigned long)retData,1,0); 314 // unsigned char *retData = hwCtrl.Read(hwCtrl._memOffset,0XF002,1); 315 PrintMem(" HWMEM ALL ",(unsigned long)hwCtrl._memAddr,_memSize,0); 316 317 318 //Cache Unit Test 319 PrintMem(" CACHE ALL ",(unsigned long)cacheCtrl._cacheMemAddr,cacheCtrl._cacheSize,0); 320 321 322 //struct test 323 struct CacheUnit cu = { 324 0x00, 325 0x00, 326 0x00 327 }; 328 printf("\r\n ============>> CacheUnitTypeSize %d \r\n",sizeof(struct CacheUnit)); 329 printf("\r\n ============>> CacheUnitSize %d \r\n",sizeof(cu)); 330 printf("\r\n ============>> CacheUnitSize.Hot %d \r\n",sizeof(cu.Hot)); 331 printf("\r\n ============>> CacheUnitSize.tCode %d \r\n",sizeof(cu.tCode)); 332 printf("\r\n ============>> CacheUnitSize ptr %d \r\n",sizeof(cu.BlockArrayPtr)); 333 334 //ReadCacheTest 335 PrintMem("",cacheCtrl.Read(&cacheCtrl,&hwCtrl,0XF038,16),16,0); 336 PrintCache("",&cacheCtrl); 337 return 0; 338 }