《深入理解计算机系统》自学历程（一）模拟高速缓存逻辑（下）
，和合计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
2 #include
3 #include
4 #include
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(iCacheFinder(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
