NEMU-PART III

PA3：存储管理

实现高速缓存

经过实践，高速缓存的一级和二级结构最好同时实现，否则会在分页控制中出现难以预料的bug！

定义高速缓存结构

新建文件/nemu/include/memory/cache.h，填写以下内容：

宏定义缓存块：

 1#ifndef __CACHE_H__
 2#define __CACHE_H__
 3
 4#include "common.h"
 5
 6// 定义高速缓存参数
 7#define CACHE_E_L1 8
 8#define CACHE_E_L2 16
 9#define CACHE_BLOCK 64
10#define CACHE_SIZE_L1 64*1024
11#define CACHE_SIZE_L2 4*1024*1024
12
13...
14
15#endif

缓存块的结构体定义：

 1// 定义一级缓存
 2struct cache_l1 {
 3    bool valid;
 4    int tag;
 5    uint8_t byte[CACHE_BLOCK];
 6} cache_L1[CACHE_SIZE_L1 / CACHE_BLOCK];
 7
 8// 定义二级缓存
 9struct cache_l2 {
10    bool valid;
11    bool dirty;
12    int tag;
13    uint8_t byte[CACHE_BLOCK];
14} cache_L2[CACHE_SIZE_L2 / CACHE_BLOCK];
15
16// 定义高速缓存函数
17void init_cache();
18uint32_t cache_read_L1(hwaddr_t addr);
19uint32_t cache_read_L2(hwaddr_t addr);
20void cache_write_L1(hwaddr_t addr, size_t len, uint32_t data);
21void cache_write_L2(hwaddr_t addr, size_t len, uint32_t data);

高速缓存的读写函数

新建文件/nemu/src/memory/cache.c

缓存的初始化

 1void init_cache(){
 2    int i;
 3    for(i = 0; i < CACHE_SIZE_L1 / CACHE_BLOCK; i++) {
 4        cache_L1[i].valid = false;
 5        cache_L1[i].tag = 0;
 6        memset(cache_L1[i].byte, 0, CACHE_BLOCK);
 7    }
 8    for(i = 0; i < CACHE_SIZE_L2 / CACHE_BLOCK; i++) {
 9        cache_L2[i].dirty = false;
10        cache_L2[i].valid = false;
11        cache_L2[i].tag = 0;
12        memset(cache_L2[i].byte, 0, CACHE_BLOCK);
13    }
14}

读取缓存块中的内容

 1uint32_t cache_read_L1(hwaddr_t addr) {
 2    // 取出地址中set的部分（右移block位并 & 1111111）
 3    // set = 7 byte (set = 2^s = 128)
 4    // offset = 6 byte (block = 2^e = 64)
 5    uint32_t set = (addr >> 6) & 0x7f; 
 6    bool hit = false;
 7    int i;
 8    // 一级缓存中找到相应set
 9    for(i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) { 
10        if(cache_L1[i].tag == (addr >> 13) && cache_L1[i].valid) { // 如果tag和地址相符合并且valid == true
11            hit = true; 
12            return i;
13        }
14    }
15     
16    // 一级缓存中找空内存块
17    for(i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) {
18        // 找到空的地方退出
19        if (!cache_L1[i].valid) {
20            break; 
21        }  
22    }
23    // 到最后仍然没有找到空的地方，执行随机替换算法
24    if(i == (set + 1) * CACHE_E_L1) { 
25        srand(0);
26        i = set * CACHE_E_L1 + rand() % CACHE_E_L1;
27    }
28    cache_L1[i].valid = true;
29    cache_L1[i].tag = addr >> 13;
30    int j = cache_read_L2(addr);;
31    memcpy(cache_L1[i].byte, cache_L2[j].byte, CACHE_BLOCK);
32    
33    return i;
34}
35
36uint32_t cache_read_L2(hwaddr_t addr){
37    uint32_t s = (addr >> 6) & ((1 << 12) - 1);
38    uint32_t block = (addr >> 6) << 6;
39    int i;
40    bool hit = false;
41    for (i = s * CACHE_E_L2; i < (s + 1) * CACHE_E_L2; i++) {
42        if (cache_L2[i].tag == (addr >> 18) && cache_L2[i].valid) {
43            hit = true;
44            break;
45        }
46    }
47    if (!hit) {
48        int j;
49        for (i = s * CACHE_E_L2; i < (s + 1) * CACHE_E_L2; i++) {
50            if (!cache_L2[i].valid)
51                break;
52        }
53        if (i == (s + 1) * CACHE_E_L2) {
54            srand(0);
55            i = s * CACHE_E_L2 + rand() % CACHE_E_L2;
56            if (cache_L2[i].dirty) {
57                uint8_t mask[BURST_LEN * 2];
58                memset(mask, 1, BURST_LEN * 2);
59                for (j = 0; j < CACHE_BLOCK / BURST_LEN; j++) {
60                    call_ddr3_write(block + j * BURST_LEN, cache_L2[i].byte + j * BURST_LEN, mask);
61                }	
62            }
63        }
64        cache_L2[i].valid = true;
65        cache_L2[i].tag = addr >> 18;
66        cache_L2[i].dirty = false;
67        for (j = 0; j < BURST_LEN; j++){
68            call_ddr3_read(block + j * BURST_LEN, cache_L2[i].byte + j * BURST_LEN);
69        }
70    }
71    return i;
72}

数据写入缓存块

 1void cache_write_L1(hwaddr_t addr, size_t len, uint32_t data) {
 2    uint32_t set = (addr >> 6) & 0x7f;
 3    uint32_t offset = addr & (CACHE_BLOCK - 1); 
 4    int i;
 5    bool hit = false;
 6    for (i = set * CACHE_E_L1; i < (set + 1) * CACHE_E_L1; i++) {
 7        if (cache_L1[i].tag == (addr >> 13) && cache_L1[i].valid) {
 8            hit = true;
 9            break;
10        }
11    }
12    // 写直通
13    if (hit) { 
14        memcpy(cache_L1[i].byte + offset, &data, len);
15    }
16    cache_write_L2(addr, len, data);
17}
18
19void cache_write_L2(swaddr_t addr, size_t len, uint32_t data) {
20    uint32_t set = (addr >> 6) & ((1 << 12) - 1); 
21    uint32_t offset = addr & 0x3f;	
22    int i;
23    bool hit = false;
24    for (i = set * CACHE_E_L2; i < (set + 1) * CACHE_E_L2; i++) {
25        if (cache_L2[i].tag == (addr >> 13) && cache_L2[i].valid) {
26            hit = true;
27            break;
28        }
29    }
30    if (!hit){
31        i = cache_read_L2(addr);
32    }
33    cache_L2[i].dirty = true;
34    memcpy(cache_L2[i].byte + offset, &data, len);
35}

修改内存读写逻辑

在/nemu/src/memory/memory.c中，修改hwaddr_read和hwaddr_write两个函数：

 1uint32_t hwaddr_read(hwaddr_t addr, size_t len) {
 2    uint32_t offset = addr & (CACHE_BLOCK - 1);
 3    uint32_t block = cache_read_L1(addr);
 4    uint8_t temp[4];
 5    memset(temp, 0, sizeof(temp));
 6    if (offset + len >= CACHE_BLOCK) {
 7        uint32_t second_block = cache_read_L1(addr + len);
 8        memcpy(temp, cache[block].byte + offset, CACHE_BLOCK - offset);
 9        memcpy(temp + CACHE_BLOCK - offset, cache[second_block].byte, len - (CACHE_BLOCK - offset));
10    } else {
11        memcpy(temp, cache[block].byte + offset, len);
12    }
13    int zero = 0;
14    uint32_t result = unalign_rw(temp + zero, 4) & (~0u >> ((4 - len) << 3));
15    return result;
16}
17
18void hwaddr_write(hwaddr_t addr, size_t len, uint32_t data) {
19    cache_write_L1(addr, len, data);
20}

实现分段机制

修改kernel

首先需要在kernel中加入切换到保护模式的代码：在kernel/include/common.h中定义宏IA32_SEG，然后重新编译kernel。

1- //#define IA32_SEG
2+ #define IA32_SEG

这一步必须完成！如果你是CV大佬，很容易漏掉这个步骤！

定义段寄存器

在CPU_state结构中添加GDTR，CR0和各种段寄存器，包括CS, DS, ES, SS, 其具体结构参考i386手册。

在libcommon/x86-inc目录下的头文件中定义了一些和x86相关的宏和结构体，你可以在NEMU中包含这些头文件来使用它们。

 1// 段寄存器
 2enum {R_ES, R_CS, R_SS, R_DS};
 3
 4// 定义段寄存器结构体
 5typedef struct {
 6    uint16_t selector;
 7    uint16_t attribute;
 8    uint32_t limit;
 9    uint32_t base;
10} Segment_Reg;
11
12...
13
14typedef struct {
15    ...
16
17    // GDTR寄存器
18    struct GDTR {
19        uint32_t base;
20        uint16_t limit;
21    } gdtr;
22
23    // CR0和CR3寄存器由 /lib-common/x86-inc/cpu.h 定义
24    CR0 cr0;
25    CR3 cr3;
26
27    // 设置段寄存器
28    union {
29        struct {
30            Segment_Reg sreg[4];	
31        };
32        struct {
33            Segment_Reg es, cs, ss, ds;
34        };
35    };
36
37} CPU_state;

完善指令集

添加lgdt指令。
添加opcode为0F 20和0F 22的mov指令，使得我们可以设置/读出CR0。
添加opcode为8E的mov指令，使得我们可以设置段寄存器。
为了设置CS寄存器, 你需要实现ljmp指令

实现段寄存器的捆绑规则

在Operand结构体中添加成员sreg，位置：/nemu/include/cpu/decode/operand.h

 1typedef struct {
 2    uint32_t type;
 3    size_t size;
 4    union {
 5        uint32_t reg;
 6-       swaddr_t addr;
 7+		struct {
 8+			swaddr_t addr;
 9+			uint8_t sreg;
10+		};
11        uint32_t imm;
12        int32_t simm;
13    };
14    uint32_t val;
15    char str[OP_STR_SIZE];
16} Operand;

修改所有调用swaddr_read()和swaddr_write()的代码，为它们添加段寄存器的参数。具体要求如下：

指令	实现要求
`opcode`为`A0`, `A1`, `A2`, `A3` 的`mov`指令	使用`DS`寄存器
一些堆栈操作指令	隐式使用`SS`寄存器
`instr_fetch()`	总是使用`CS`寄存器
`monitor`中，`x`和`p`命令读出内存时	使用`DS`寄存器
`bt`命令打印栈帧链	使用`SS`寄存器
字符串操作指令使用的段寄存器	请查阅 i386 手册

修改内存读写函数

设置CR0后，如果发现CR0的PE位为 1，则进入IA-32保护模式，从此所有虚拟地址的访问（包括swaddr_read()和 swaddr_write()）都需要经过段级地址转换。

为了实现段级地址转换，需要对/nemu/src/memory/memory.c中的swaddr_read()和swaddr_write()函数作少量修改：

1uint32_t swaddr_read(swaddr_t addr, size_t len) {
2#ifdef DEBUG
3    assert(len == 1 || len == 2 || len == 4);
4#endif
5    lnaddr_t lnaddr = seg_translate(addr, len, current_sreg);
6    return lnaddr_read(lnaddr, len);
7}
8
9// swaddr_write()函数采取类似操作

其中sreg记录了当前段级地址转换所用到的段寄存器的编码。关于段寄存器的编码，请查阅i386手册。

然后实现seg_translate()函数。再次提醒，在 NEMU 中，只有进入保护模式之后才会进行段级地址转换。

1lnaddr_t seg_translate(swaddr_t addr, size_t len, uint8_t sreg_id) {
2    if (cpu.cr0.protect_enable == 0) {
3        return addr;
4    }
5    else {
6        return cpu.sreg[sreg_id].base + addr;
7    }
8}

实现分页机制

思考题

GDT能有多大段选择符的结构中，INDEX有13位，故GDT最大能容纳2^13个段描述符
为什么是线性地址？不可以。虚拟地址需要经GDT中的段表翻译才能得出地址，而如果GDTR中存放虚拟地址则找不到GDT在哪里了。
如何提高寻找段描述符的效率可以按照高速缓存的思想，建立类似cache 和 TLB 的结构来提高寻找效率。
段式存储管理的缺点分段管理要求分配一大段连续的存储空间，难以实现并且容易造成大量的外部碎片出现。
页式存储管理的优点没有外部碎片，并且不再需要大段连续的存储空间，提高了内存的利用率。
一些问题 Q：为什么页表表项中的基地址信息只有20位而不是32位 A：分页基地址有20位是8086的传统在8086的分段机制中，每个段的基地址由seg_reg（即段寄存器的值）«4得到，而段寄存器是16位的，左移4位得到20位的基地址。 Q：表项和CR3中的基地址都是物理地址，这是必须的吗？能否采用虚拟地址或者线性地址？ A：是必须的，如果cr3中的基地址是虚拟地址，则无从寻找页表翻译成物理地址，进入鸡生蛋蛋生鸡的死循环。至于其他表项的虚拟地址与线性地址问题同理。 Q：为什么不采用一级页表？采用一级页表会有什么缺点？ A：多级页表可以有效地节约内存空间，如果仅采用一级页表，将可能导致较大的页表长期驻留在内存中。
空指针是“空”的吗？空指针只是未分配或者未指向内存任何位置的指针，并不是“NULL”的。
在扁平模式下如何进行保护对于数据有不同的访问权限，未达到需要的权限时不能进行写操作
地址映射
分页机制因为这里定义的ｘ生成的地址是虚拟地址，超过了物理地址的界限，报错0xc014a000 outside of the physical memory。而ｋvm.c 中的虚拟地址都经过了 va_to_pa 的转换，在物理地址范围之内。进行反汇编后，其地址如下： c01003d6: e8 65 09 00 00 call c0100d40 <init_page> 该call指令的opcode为e8，实现的是跳转到：该条指令的下一条指令的首地址+偏移量的位置。由于未进行寻址，故不需要进行虚实地址转化。分页的环境下，在没有初始化页表时，0～128M的虚拟地址到物理地址的映射相当于一个简易的页表，使得高位的地址可以通过该虚拟地址（即经过va_to_pa）访问到物理地址，从而进行初始化页表的操作。 init_mm()函数执行退出时。该函数将nemu映射到了高位地址并且将之前的PDE全部置为无效，此时返回main.c时，栈中保存的返回地址需要经过虚实转换，可由于页面被置为了无效，所以报错。查看汇编代码，直接调用此函数时，nemu运行在物理地址上，由于在init_mm中将之前的PDE都置为无效，所以在loader()函数寻址时页面无效，导致报错。