《深入理解计算机系统》自学历程（一）模拟高速缓存逻辑（下）

经过三次重写，和合计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 }